Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree kmeans split algorithm implementation
Chris@16: //
Chris@16: // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP
Chris@16: 
Chris@16: #include <boost/geometry/index/rtree/node/node.hpp>
Chris@16: #include <boost/geometry/index/rtree/visitors/insert.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index {
Chris@16: 
Chris@16: namespace detail { namespace rtree {
Chris@16: 
Chris@16: namespace kmeans {
Chris@16: 
Chris@16: // some details
Chris@16: 
Chris@16: } // namespace kmeans
Chris@16: 
Chris@16: // split_kmeans_tag
Chris@16: // OR
Chris@16: // split_clusters_tag and redistribute_kmeans_tag - then redistribute will probably slightly different interface
Chris@16: // or some other than "redistribute"
Chris@16: 
Chris@16: // 1. for this algorithm one probably MUST USE NON-STATIC NODES with node_default_tag
Chris@16: //    or the algorithm must be changed somehow - to not store additional nodes in the current node
Chris@16: //    but return excessive element/elements container instead (possibly pushable_array<1> or std::vector)
Chris@16: //    this would also cause building of smaller trees since +1 element in nodes wouldn't be needed in different redistributing algorithms
Chris@16: // 2. it is probably possible to add e.g. 2 levels of tree in one insert
Chris@16: 
Chris@16: // Edge case is that every node split generates M + 1 children, in parent containing M nodes
Chris@16: // result is 2M + 1 nodes in parent on this level
Chris@16: // On next level the same, next the same and so on.
Chris@16: // We have Depth*M+1 nodes in the root
Chris@16: // The tree may then gain some > 1 levels in one insert
Chris@16: // split::apply() manages this but special attention is required
Chris@16: 
Chris@16: // which algorithm should be used to choose current node in traversing while inserting?
Chris@16: // some of the currently used ones or some using mean values as well?
Chris@16: 
Chris@16: // TODO
Chris@16: // 1. Zmienic troche algorytm zeby przekazywal nadmiarowe elementy do split
Chris@16: //    i pobieral ze split nadmiarowe elementy rodzica
Chris@16: //    W zaleznosci od algorytmu w rozny sposob - l/q/r* powinny zwracac np pushable_array<1>
Chris@16: //    wtedy tez is_overerflow (z R* insert?) bedzie nieportrzebne
Chris@16: //    Dla kmeans zapewne std::vector, jednak w wezlach nadal moglaby byc pushable_array
Chris@16: // 2. Fajnie byloby tez uproscic te wszystkie parametry root,parent,index itd. Mozliwe ze okazalyby sie zbedne
Chris@16: // 3. Sprawdzyc czasy wykonywania i zajetosc pamieci
Chris@16: // 4. Pamietac o parametryzacji kontenera z nadmiarowymi elementami
Chris@16: // PS. Z R* reinsertami moze byc masakra
Chris@16: 
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: class split<Value, Options, Translator, Box, Allocators, split_kmeans_tag>
Chris@16: {
Chris@16: protected:
Chris@16:     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
Chris@16:     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16: public:
Chris@16:     template <typename Node>
Chris@16:     static inline void apply(node* & root_node,
Chris@16:                              size_t & leafs_level,
Chris@16:                              Node & n,
Chris@16:                              internal_node *parent_node,
Chris@16:                              size_t current_child_index,
Chris@16:                              Translator const& tr,
Chris@16:                              Allocators & allocators)
Chris@16:     {
Chris@16: 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }} // namespace detail::rtree
Chris@16: 
Chris@16: }}} // namespace boost::geometry::index
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_KMEANS_SPLIT_HPP