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