ceph/src/boost/boost/geometry/index/detail/rtree/kmeans/split.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree kmeans split algorithm implementation
   4 //
   5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
  13
  14 #include <boost/geometry/index/rtree/node/node.hpp>
  15 #include <boost/geometry/index/rtree/visitors/insert.hpp>
  16
  17 namespace boost { namespace geometry { namespace index {
  18
  19 namespace detail { namespace rtree {
  20
  21 namespace kmeans {
  22
  23 // some details
  24
  25 } // namespace kmeans
  26
  27 // split_kmeans_tag
  28 // OR
  29 // split_clusters_tag and redistribute_kmeans_tag - then redistribute will probably slightly different interface
  30 // or some other than "redistribute"
  31
  32 // 1. for this algorithm one probably MUST USE NON-STATIC NODES with node_default_tag
  33 //    or the algorithm must be changed somehow - to not store additional nodes in the current node
  34 //    but return excessive element/elements container instead (possibly pushable_array<1> or std::vector)
  35 //    this would also cause building of smaller trees since +1 element in nodes wouldn't be needed in different redistributing algorithms
  36 // 2. it is probably possible to add e.g. 2 levels of tree in one insert
  37
  38 // Edge case is that every node split generates M + 1 children, in parent containing M nodes
  39 // result is 2M + 1 nodes in parent on this level
  40 // On next level the same, next the same and so on.
  41 // We have Depth*M+1 nodes in the root
  42 // The tree may then gain some > 1 levels in one insert
  43 // split::apply() manages this but special attention is required
  44
  45 // which algorithm should be used to choose current node in traversing while inserting?
  46 // some of the currently used ones or some using mean values as well?
  47
  48 // TODO
  49 // 1. Zmienic troche algorytm zeby przekazywal nadmiarowe elementy do split
  50 //    i pobieral ze split nadmiarowe elementy rodzica
  51 //    W zaleznosci od algorytmu w rozny sposob - l/q/r* powinny zwracac np pushable_array<1>
  52 //    wtedy tez is_overerflow (z R* insert?) bedzie nieportrzebne
  53 //    Dla kmeans zapewne std::vector, jednak w wezlach nadal moglaby byc pushable_array
  54 // 2. Fajnie byloby tez uproscic te wszystkie parametry root,parent,index itd. Mozliwe ze okazalyby sie zbedne
  55 // 3. Sprawdzyc czasy wykonywania i zajetosc pamieci
  56 // 4. Pamietac o parametryzacji kontenera z nadmiarowymi elementami
  57 // PS. Z R* reinsertami moze byc masakra
  58
  59 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
  60 class split<Value, Options, Translator, Box, Allocators, split_kmeans_tag>
  61 {
  62 protected:
  63     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
  64     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  65     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  66
  67     typedef typename Options::parameters_type parameters_type;
  68
  69 public:
  70     template <typename Node>
  71     static inline void apply(node* & root_node,
  72                              size_t & leafs_level,
  73                              Node & n,
  74                              internal_node *parent_node,
  75                              size_t current_child_index,
  76                              Translator const& tr,
  77                              Allocators & allocators)
  78     {
  79
  80     }
  81 };
  82
  83 }} // namespace detail::rtree
  84
  85 }}} // namespace boost::geometry::index
  86
  87 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP