|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r75238 - in sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree: . kmeans visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2011-11-01 16:30:08
Author: awulkiew
Date: 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
New Revision: 75238
URL: http://svn.boost.org/trac/boost/changeset/75238
Log:
cR-tree kmeans options and files added (not yet implemented)
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/split.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp | 21 +++++++++++++++++++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 1 +
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 16 ++++++++++++++--
3 files changed, 36 insertions(+), 2 deletions(-)
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
@@ -0,0 +1,15 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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_EXTENSIONS_INDEX_RTREE_KMEANS_KMEANS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_KMEANS_KMEANS_HPP
+
+#include <boost/geometry/extensions/index/rtree/kmeans/split.hpp>
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_KMEANS_KMEANS_HPP
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/split.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/kmeans/split.hpp 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
@@ -0,0 +1,91 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree linear split algorithm implementation
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// 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_EXTENSIONS_INDEX_RTREE_KMEANS_SPLIT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_KMEANS_SPLIT_HPP
+
+#include <boost/geometry/extensions/index/rtree/node/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+namespace detail {
+
+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
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_KMEANS_SPLIT_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
@@ -22,6 +22,7 @@
// SplitTag
struct split_default_tag {};
+//struct split_kmeans_tag {};
// RedistributeTag
struct linear_tag {};
@@ -92,6 +93,13 @@
} // namespace options
+//template <size_t MaxElements, size_t MinElements>
+//struct kmeans
+//{
+// static const size_t max_elements = MaxElements;
+// static const size_t min_elements = MinElements;
+//};
+
namespace detail { namespace rtree {
template <typename Parameters>
@@ -139,6 +147,19 @@
> type;
};
+//template <size_t MaxElements, size_t MinElements>
+//struct options_type< kmeans<MaxElements, MinElements> >
+//{
+// typedef options::rtree<
+// kmeans<MaxElements, MinElements>,
+// insert_default_tag,
+// choose_by_content_diff_tag, // change it?
+// split_kmeans_tag,
+// int, // dummy tag - not used for now
+// node_default_static_tag
+// > type;
+//};
+
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
@@ -40,6 +40,7 @@
#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
#include <boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp>
#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
+//#include <boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-11-01 16:30:06 EDT (Tue, 01 Nov 2011)
@@ -81,13 +81,25 @@
// Not implemented here
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename RedistributeTag>
-struct redistribute_elements;
+struct redistribute_elements
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_REDISTRIBUTE_TAG_TYPE,
+ (redistribute_elements));
+};
// ----------------------------------------------------------------------- //
// Split algorithm
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename SplitTag>
-class split;
+class split
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_SPLIT_TAG_TYPE,
+ (split));
+};
// Default split algorithm
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk