1 // Boost.Geometry Index
3 // R-tree kmeans split algorithm implementation
5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
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)
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
14 #include <boost/geometry/index/rtree/node/node.hpp>
15 #include <boost/geometry/index/rtree/visitors/insert.hpp>
17 namespace boost { namespace geometry { namespace index {
19 namespace detail { namespace rtree {
29 // split_clusters_tag and redistribute_kmeans_tag - then redistribute will probably slightly different interface
30 // or some other than "redistribute"
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
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
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?
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
59 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
60 class split<Value, Options, Translator, Box, Allocators, split_kmeans_tag>
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;
67 typedef typename Options::parameters_type parameters_type;
70 template <typename Node>
71 static inline void apply(node* & root_node,
74 internal_node *parent_node,
75 size_t current_child_index,
77 Allocators & allocators)
83 }} // namespace detail::rtree
85 }}} // namespace boost::geometry::index
87 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP