123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635 |
- #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
- #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
- #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
- #include <type_traits>
- #endif
- #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
- #include <boost/geometry/core/static_assert.hpp>
- #include <boost/geometry/index/detail/algorithms/bounds.hpp>
- #include <boost/geometry/index/detail/algorithms/content.hpp>
- #include <boost/geometry/index/detail/rtree/node/node.hpp>
- #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
- #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
- #include <boost/geometry/index/detail/rtree/options.hpp>
- #include <boost/geometry/util/constexpr.hpp>
- namespace boost { namespace geometry { namespace index {
- namespace detail { namespace rtree {
- template
- <
- typename MembersHolder,
- typename ChooseNextNodeTag = typename MembersHolder::options_type::choose_next_node_tag
- >
- class choose_next_node;
- template <typename MembersHolder>
- class choose_next_node<MembersHolder, choose_by_content_diff_tag>
- {
- public:
- typedef typename MembersHolder::box_type box_type;
- typedef typename MembersHolder::parameters_type parameters_type;
- typedef typename MembersHolder::node node;
- typedef typename MembersHolder::internal_node internal_node;
- typedef typename MembersHolder::leaf leaf;
- typedef typename rtree::elements_type<internal_node>::type children_type;
- typedef typename index::detail::default_content_result<box_type>::type content_type;
- template <typename Indexable>
- static inline size_t apply(internal_node & n,
- Indexable const& indexable,
- parameters_type const& parameters,
- size_t )
- {
- children_type & children = rtree::elements(n);
- BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
- size_t children_count = children.size();
-
- size_t choosen_index = 0;
- content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
- content_type smallest_content = (std::numeric_limits<content_type>::max)();
-
- for ( size_t i = 0 ; i < children_count ; ++i )
- {
- typedef typename children_type::value_type child_type;
- child_type const& ch_i = children[i];
-
- box_type box_exp(ch_i.first);
- index::detail::expand(box_exp, indexable,
- index::detail::get_strategy(parameters));
-
- content_type content = index::detail::content(box_exp);
- content_type content_diff = content - index::detail::content(ch_i.first);
-
- if ( content_diff < smallest_content_diff ||
- ( content_diff == smallest_content_diff && content < smallest_content ) )
- {
- smallest_content_diff = content_diff;
- smallest_content = content;
- choosen_index = i;
- }
- }
- return choosen_index;
- }
- };
- template
- <
- typename MembersHolder,
- typename RedistributeTag = typename MembersHolder::options_type::redistribute_tag
- >
- struct redistribute_elements
- {
- BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
- "Not implemented for this RedistributeTag type.",
- MembersHolder, RedistributeTag);
- };
- template
- <
- typename MembersHolder,
- typename SplitTag = typename MembersHolder::options_type::split_tag
- >
- class split
- {
- BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
- "Not implemented for this SplitTag type.",
- MembersHolder, SplitTag);
- };
- template <typename MembersHolder>
- class split<MembersHolder, split_default_tag>
- {
- protected:
- typedef typename MembersHolder::parameters_type parameters_type;
- typedef typename MembersHolder::box_type box_type;
- typedef typename MembersHolder::translator_type translator_type;
- typedef typename MembersHolder::allocators_type allocators_type;
- typedef typename MembersHolder::size_type size_type;
- typedef typename MembersHolder::node node;
- typedef typename MembersHolder::internal_node internal_node;
- typedef typename MembersHolder::leaf leaf;
- typedef typename MembersHolder::node_pointer node_pointer;
- public:
- typedef index::detail::varray<
- typename rtree::elements_type<internal_node>::type::value_type,
- 1
- > nodes_container_type;
- template <typename Node>
- static inline void apply(nodes_container_type & additional_nodes,
- Node & n,
- box_type & n_box,
- parameters_type const& parameters,
- translator_type const& translator,
- allocators_type & allocators)
- {
-
-
- node_pointer n2_ptr = rtree::create_node<allocators_type, Node>::apply(allocators);
-
- Node & n2 = rtree::get<Node>(*n2_ptr);
- BOOST_TRY
- {
-
-
-
-
-
-
-
-
-
- box_type box2;
- redistribute_elements<MembersHolder>
- ::apply(n, n2, n_box, box2, parameters, translator, allocators);
-
- BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
- rtree::elements(n).size() <= parameters.get_max_elements(),
- "unexpected number of elements");
- BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
- rtree::elements(n2).size() <= parameters.get_max_elements(),
- "unexpected number of elements");
-
- additional_nodes.push_back(rtree::make_ptr_pair(box2, n2_ptr));
- }
- BOOST_CATCH(...)
- {
-
-
-
- typename rtree::elements_type<Node>::type & elements = rtree::elements(n);
- size_type const max_size = parameters.get_max_elements();
- if (elements.size() > max_size)
- {
- rtree::destroy_element<MembersHolder>::apply(elements[max_size], allocators);
- elements.pop_back();
- }
- rtree::visitors::destroy<MembersHolder>::apply(n2_ptr, allocators);
- BOOST_RETHROW
- }
- BOOST_CATCH_END
- }
- };
- namespace visitors { namespace detail {
- template <typename InternalNode, typename InternalNodePtr, typename SizeType>
- struct insert_traverse_data
- {
- typedef typename rtree::elements_type<InternalNode>::type elements_type;
- typedef typename elements_type::value_type element_type;
- typedef typename elements_type::size_type elements_size_type;
- typedef SizeType size_type;
- insert_traverse_data()
- : parent(0), current_child_index(0), current_level(0)
- {}
- void move_to_next_level(InternalNodePtr new_parent,
- elements_size_type new_child_index)
- {
- parent = new_parent;
- current_child_index = new_child_index;
- ++current_level;
- }
- bool current_is_root() const
- {
- return 0 == parent;
- }
- elements_type & parent_elements() const
- {
- BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
- return rtree::elements(*parent);
- }
- element_type & current_element() const
- {
- BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
- return rtree::elements(*parent)[current_child_index];
- }
- InternalNodePtr parent;
- elements_size_type current_child_index;
- size_type current_level;
- };
- template <typename Element, typename MembersHolder>
- class insert
- : public MembersHolder::visitor
- {
- protected:
- typedef typename MembersHolder::box_type box_type;
- typedef typename MembersHolder::value_type value_type;
- typedef typename MembersHolder::parameters_type parameters_type;
- typedef typename MembersHolder::translator_type translator_type;
- typedef typename MembersHolder::allocators_type allocators_type;
- typedef typename MembersHolder::node node;
- typedef typename MembersHolder::internal_node internal_node;
- typedef typename MembersHolder::leaf leaf;
- typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
- typedef typename allocators_type::node_pointer node_pointer;
- typedef typename allocators_type::size_type size_type;
-
- typedef internal_node * internal_node_pointer;
- inline insert(node_pointer & root,
- size_type & leafs_level,
- Element const& element,
- parameters_type const& parameters,
- translator_type const& translator,
- allocators_type & allocators,
- size_type relative_level = 0
- )
- : m_element(element)
- , m_parameters(parameters)
- , m_translator(translator)
- , m_relative_level(relative_level)
- , m_level(leafs_level - relative_level)
- , m_root_node(root)
- , m_leafs_level(leafs_level)
- , m_traverse_data()
- , m_allocators(allocators)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
- BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
- BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node");
-
-
-
-
-
-
-
-
- index::detail::bounds(rtree::element_indexable(m_element, m_translator),
- m_element_bounds,
- index::detail::get_strategy(m_parameters));
- #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
-
-
-
- if BOOST_GEOMETRY_CONSTEXPR ((std::is_same<Element, value_type>::value)
- && ! index::detail::is_bounding_geometry
- <
- typename indexable_type<translator_type>::type
- >::value)
- {
- geometry::detail::expand_by_epsilon(m_element_bounds);
- }
- #endif
- }
- template <typename Visitor>
- inline void traverse(Visitor & visitor, internal_node & n)
- {
-
- size_t choosen_node_index = rtree::choose_next_node<MembersHolder>
- ::apply(n, rtree::element_indexable(m_element, m_translator),
- m_parameters,
- m_leafs_level - m_traverse_data.current_level);
-
- index::detail::expand(
- rtree::elements(n)[choosen_node_index].first,
- m_element_bounds,
- index::detail::get_strategy(m_parameters));
-
- traverse_apply_visitor(visitor, n, choosen_node_index);
- }
-
- template <typename Node>
- inline void post_traverse(Node &n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
- &n == &rtree::get<Node>(*m_traverse_data.current_element().second),
- "if node isn't the root current_child_index should be valid");
-
- if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
- {
-
-
- split(n);
- }
- }
- template <typename Visitor>
- inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
- {
-
- insert_traverse_data<internal_node, internal_node_pointer, size_type>
- backup_traverse_data = m_traverse_data;
-
- m_traverse_data.move_to_next_level(&n, choosen_node_index);
-
- rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
-
- m_traverse_data = backup_traverse_data;
- }
-
- template <typename Node>
- inline void split(Node & n) const
- {
- typedef rtree::split<MembersHolder> split_algo;
- typename split_algo::nodes_container_type additional_nodes;
- box_type n_box;
- split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);
- BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
-
-
-
-
-
-
-
-
-
-
- subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators);
- #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
-
-
-
- if BOOST_GEOMETRY_CONSTEXPR ((std::is_same<Node, leaf>::value)
- && ! index::detail::is_bounding_geometry
- <
- typename indexable_type<translator_type>::type
- >::value)
- {
- geometry::detail::expand_by_epsilon(n_box);
- geometry::detail::expand_by_epsilon(additional_nodes[0].first);
- }
- #endif
-
- if ( !m_traverse_data.current_is_root() )
- {
-
- m_traverse_data.current_element().first = n_box;
-
- m_traverse_data.parent_elements().push_back(additional_nodes[0]);
- }
-
- else
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
-
- subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators);
- BOOST_TRY
- {
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(rtree::make_ptr_pair(n_box, m_root_node));
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);
- }
- BOOST_CATCH(...)
- {
-
- rtree::elements(rtree::get<internal_node>(*new_root)).clear();
- BOOST_RETHROW
- }
- BOOST_CATCH_END
- m_root_node = new_root.get();
- ++m_leafs_level;
- new_root.release();
- }
- additional_node_ptr.release();
- }
-
- Element const& m_element;
- box_type m_element_bounds;
- parameters_type const& m_parameters;
- translator_type const& m_translator;
- size_type const m_relative_level;
- size_type const m_level;
- node_pointer & m_root_node;
- size_type & m_leafs_level;
-
- insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
- allocators_type & m_allocators;
- };
- }
- template
- <
- typename Element,
- typename MembersHolder,
- typename InsertTag = typename MembersHolder::options_type::insert_tag
- >
- class insert;
- template <typename Element, typename MembersHolder>
- class insert<Element, MembersHolder, insert_default_tag>
- : public detail::insert<Element, MembersHolder>
- {
- public:
- typedef detail::insert<Element, MembersHolder> base;
- typedef typename base::parameters_type parameters_type;
- typedef typename base::translator_type translator_type;
- typedef typename base::allocators_type allocators_type;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
- typedef typename base::node_pointer node_pointer;
- typedef typename base::size_type size_type;
- inline insert(node_pointer & root,
- size_type & leafs_level,
- Element const& element,
- parameters_type const& parameters,
- translator_type const& translator,
- allocators_type & allocators,
- size_type relative_level = 0
- )
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
- {}
- inline void operator()(internal_node & n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- if ( base::m_traverse_data.current_level < base::m_level )
- {
-
- base::traverse(*this, n);
- }
- else
- {
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
- BOOST_TRY
- {
-
- rtree::elements(n).push_back(base::m_element);
- }
- BOOST_CATCH(...)
- {
-
- rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
- BOOST_RETHROW
- }
- BOOST_CATCH_END
- }
- base::post_traverse(n);
- }
- inline void operator()(leaf &)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
- }
- };
- template <typename MembersHolder>
- class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag>
- : public detail::insert<typename MembersHolder::value_type, MembersHolder>
- {
- public:
- typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base;
- typedef typename base::value_type value_type;
- typedef typename base::parameters_type parameters_type;
- typedef typename base::translator_type translator_type;
- typedef typename base::allocators_type allocators_type;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
- typedef typename base::node_pointer node_pointer;
- typedef typename base::size_type size_type;
- inline insert(node_pointer & root,
- size_type & leafs_level,
- value_type const& value,
- parameters_type const& parameters,
- translator_type const& translator,
- allocators_type & allocators,
- size_type relative_level = 0
- )
- : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
- {}
- inline void operator()(internal_node & n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
-
- base::traverse(*this, n);
- base::post_traverse(n);
- }
- inline void operator()(leaf & n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
- base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
- rtree::elements(n).push_back(base::m_element);
- base::post_traverse(n);
- }
- };
- }}}
- }}}
- #endif
|