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