diff options
Diffstat (limited to 'boost/geometry/index/detail/rtree')
16 files changed, 432 insertions, 163 deletions
diff --git a/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp b/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp index c794a64267..a0635acab1 100644 --- a/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp +++ b/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp @@ -5,6 +5,10 @@ // Copyright (c) 2008 Federico J. Fernandez. // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -15,6 +19,7 @@ #include <boost/core/ignore_unused.hpp> #include <boost/type_traits/is_unsigned.hpp> +#include <boost/geometry/index/detail/algorithms/bounds.hpp> #include <boost/geometry/index/detail/algorithms/content.hpp> #include <boost/geometry/index/detail/bounded_view.hpp> @@ -90,7 +95,11 @@ struct find_greatest_normalized_separation typedef typename geometry::point_type<indexable_type>::type point_type; typedef geometry::model::box<point_type> bounds_type; - typedef index::detail::bounded_view<indexable_type, bounds_type> bounded_view_type; + typedef index::detail::bounded_view + < + indexable_type, bounds_type, + typename index::detail::strategy_type<Parameters>::type + > bounded_view_type; static inline void apply(Elements const& elements, Parameters const& parameters, @@ -103,8 +112,12 @@ struct find_greatest_normalized_separation BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements"); BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements"); + typename index::detail::strategy_type<Parameters>::type const& + strategy = index::detail::get_strategy(parameters); + // find the lowest low, highest high - bounded_view_type bounded_indexable_0(rtree::element_indexable(elements[0], translator)); + bounded_view_type bounded_indexable_0(rtree::element_indexable(elements[0], translator), + strategy); coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_0); coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(bounded_indexable_0); @@ -113,7 +126,8 @@ struct find_greatest_normalized_separation size_t lowest_high_index = 0; for ( size_t i = 1 ; i < elements_count ; ++i ) { - bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator)); + bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator), + strategy); coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable); coordinate_type max_coord = geometry::get<max_corner, DimensionIndex>(bounded_indexable); @@ -132,11 +146,13 @@ struct find_greatest_normalized_separation // find the highest low size_t highest_low_index = lowest_high_index == 0 ? 1 : 0; - bounded_view_type bounded_indexable_hl(rtree::element_indexable(elements[highest_low_index], translator)); + bounded_view_type bounded_indexable_hl(rtree::element_indexable(elements[highest_low_index], translator), + strategy); coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_hl); for ( size_t i = highest_low_index ; i < elements_count ; ++i ) { - bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator)); + bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator), + strategy); coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable); if ( highest_low < min_coord && i != lowest_high_index ) @@ -329,6 +345,9 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; typedef typename index::detail::default_content_result<Box>::type content_type; + typename index::detail::strategy_type<parameters_type>::type const& + strategy = index::detail::get_strategy(parameters); + elements_type & elements1 = rtree::elements(n); elements_type & elements2 = rtree::elements(second_node); const size_t elements1_count = parameters.get_max_elements() + 1; @@ -357,8 +376,10 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy) // calculate boxes - detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1); - detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2); + detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), + box1, strategy); + detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), + box2, strategy); // initialize areas content_type content1 = index::detail::content(box1); @@ -380,13 +401,13 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear if ( elements1.size() + remaining <= parameters.get_min_elements() ) { elements1.push_back(elem); // MAY THROW, STRONG (copy) - geometry::expand(box1, indexable); + index::detail::expand(box1, indexable, strategy); content1 = index::detail::content(box1); } else if ( elements2.size() + remaining <= parameters.get_min_elements() ) { elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy) - geometry::expand(box2, indexable); + index::detail::expand(box2, indexable, strategy); content2 = index::detail::content(box2); } // choose better node and insert element @@ -395,8 +416,8 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear // calculate enlarged boxes and areas Box enlarged_box1(box1); Box enlarged_box2(box2); - geometry::expand(enlarged_box1, indexable); - geometry::expand(enlarged_box2, indexable); + index::detail::expand(enlarged_box1, indexable, strategy); + index::detail::expand(enlarged_box2, indexable, strategy); content_type enlarged_content1 = index::detail::content(enlarged_box1); content_type enlarged_content2 = index::detail::content(enlarged_box2); diff --git a/boost/geometry/index/detail/rtree/node/node.hpp b/boost/geometry/index/detail/rtree/node/node.hpp index 2b270319f6..51ba2c7e74 100644 --- a/boost/geometry/index/detail/rtree/node/node.hpp +++ b/boost/geometry/index/detail/rtree/node/node.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -42,8 +46,9 @@ namespace detail { namespace rtree { // elements box -template <typename Box, typename FwdIter, typename Translator> -inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr) +template <typename Box, typename FwdIter, typename Translator, typename Strategy> +inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr, + Strategy const& strategy) { Box result; @@ -57,11 +62,11 @@ inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr) if ( first == last ) return result; - detail::bounds(element_indexable(*first, tr), result); + detail::bounds(element_indexable(*first, tr), result, strategy); ++first; for ( ; first != last ; ++first ) - geometry::expand(result, element_indexable(*first, tr)); + detail::expand(result, element_indexable(*first, tr), strategy); return result; } @@ -71,15 +76,16 @@ inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr) // This ensures that leafs bounds correspond to the stored elements. // NOTE: this is done only if the Indexable is not a Box // in the future don't do it also for NSphere -template <typename Box, typename FwdIter, typename Translator> -inline Box values_box(FwdIter first, FwdIter last, Translator const& tr) +template <typename Box, typename FwdIter, typename Translator, typename Strategy> +inline Box values_box(FwdIter first, FwdIter last, Translator const& tr, + Strategy const& strategy) { typedef typename std::iterator_traits<FwdIter>::value_type element_type; BOOST_MPL_ASSERT_MSG((is_leaf_element<element_type>::value), SHOULD_BE_CALLED_ONLY_FOR_LEAF_ELEMENTS, (element_type)); - Box result = elements_box<Box>(first, last, tr); + Box result = elements_box<Box>(first, last, tr, strategy); #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON if (BOOST_GEOMETRY_CONDITION(( diff --git a/boost/geometry/index/detail/rtree/options.hpp b/boost/geometry/index/detail/rtree/options.hpp index ff772834d7..ba104b0c29 100644 --- a/boost/geometry/index/detail/rtree/options.hpp +++ b/boost/geometry/index/detail/rtree/options.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -148,6 +152,21 @@ struct options_type< index::dynamic_rstar > > type; }; +template <typename Parameters, typename Strategy> +struct options_type< index::parameters<Parameters, Strategy> > + : options_type<Parameters> +{ + typedef typename options_type<Parameters>::type opt; + typedef options< + index::parameters<Parameters, Strategy>, + typename opt::insert_tag, + typename opt::choose_next_node_tag, + typename opt::split_tag, + typename opt::redistribute_tag, + typename opt::node_tag + > type; +}; + }} // namespace detail::rtree }}} // namespace boost::geometry::index diff --git a/boost/geometry/index/detail/rtree/pack_create.hpp b/boost/geometry/index/detail/rtree/pack_create.hpp index 78e4712d2f..f8565bfb3e 100644 --- a/boost/geometry/index/detail/rtree/pack_create.hpp +++ b/boost/geometry/index/detail/rtree/pack_create.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -137,6 +141,7 @@ class pack typedef typename geometry::coordinate_type<point_type>::type coordinate_type; typedef typename detail::default_content_result<Box>::type content_type; typedef typename Options::parameters_type parameters_type; + typedef typename detail::strategy_type<parameters_type>::type strategy_type; static const std::size_t dimension = geometry::dimension<point_type>::value; typedef typename rtree::container_from_elements_type< @@ -165,7 +170,7 @@ public: values_count = static_cast<size_type>(diff); entries.reserve(values_count); - expandable_box<Box> hint_box; + expandable_box<Box, strategy_type> hint_box(detail::get_strategy(parameters)); for ( ; first != last ; ++first ) { // NOTE: support for iterators not returning true references adapted @@ -194,19 +199,19 @@ public: } private: - template <typename BoxType> + template <typename BoxType, typename Strategy> class expandable_box { public: - expandable_box() - : m_initialized(false) + explicit expandable_box(Strategy const& strategy) + : m_strategy(strategy), m_initialized(false) {} template <typename Indexable> - explicit expandable_box(Indexable const& indexable) - : m_initialized(true) + explicit expandable_box(Indexable const& indexable, Strategy const& strategy) + : m_strategy(strategy), m_initialized(true) { - detail::bounds(indexable, m_box); + detail::bounds(indexable, m_box, m_strategy); } template <typename Indexable> @@ -217,12 +222,12 @@ private: // it's guaranteed that the Box will be initialized // only for Points, Boxes and Segments but that's ok // since only those Geometries can be stored - detail::bounds(indexable, m_box); + detail::bounds(indexable, m_box, m_strategy); m_initialized = true; } else { - geometry::expand(m_box, indexable); + detail::expand(m_box, indexable, m_strategy); } } @@ -238,8 +243,9 @@ private: } private: - bool m_initialized; BoxType m_box; + Strategy m_strategy; + bool m_initialized; }; struct subtree_elements_counts @@ -273,7 +279,8 @@ private: // calculate values box and copy values // initialize the box explicitly to avoid GCC-4.4 uninitialized variable warnings with O2 - expandable_box<Box> elements_box(translator(*(first->second))); + expandable_box<Box, strategy_type> elements_box(translator(*(first->second)), + detail::get_strategy(parameters)); rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C) for ( ++first ; first != last ; ++first ) { @@ -319,7 +326,7 @@ private: std::size_t nodes_count = calculate_nodes_count(values_count, subtree_counts); rtree::elements(in).reserve(nodes_count); // MAY THROW (A) // calculate values box and copy values - expandable_box<Box> elements_box; + expandable_box<Box, strategy_type> elements_box(detail::get_strategy(parameters)); per_level_packets(first, last, hint_box, values_count, subtree_counts, next_subtree_counts, rtree::elements(in), elements_box, diff --git a/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp b/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp index 1ee7554f09..3fd51d56ff 100644 --- a/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp +++ b/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -41,12 +45,18 @@ inline void pick_seeds(Elements const& elements, typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; typedef Box box_type; typedef typename index::detail::default_content_result<box_type>::type content_type; - typedef index::detail::bounded_view<indexable_type, box_type> bounded_indexable_view; + typedef typename index::detail::strategy_type<Parameters>::type strategy_type; + typedef index::detail::bounded_view + < + indexable_type, box_type, strategy_type + > bounded_indexable_view; const size_t elements_count = parameters.get_max_elements() + 1; BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements"); BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements"); + strategy_type const& strategy = index::detail::get_strategy(parameters); + content_type greatest_free_content = 0; seed1 = 0; seed2 = 1; @@ -59,11 +69,11 @@ inline void pick_seeds(Elements const& elements, indexable_type const& ind2 = rtree::element_indexable(elements[j], tr); box_type enlarged_box; - detail::bounds(ind1, enlarged_box); - geometry::expand(enlarged_box, ind2); + index::detail::bounds(ind1, enlarged_box, strategy); + index::detail::expand(enlarged_box, ind2, strategy); - bounded_indexable_view bounded_ind1(ind1); - bounded_indexable_view bounded_ind2(ind2); + bounded_indexable_view bounded_ind1(ind1, strategy); + bounded_indexable_view bounded_ind2(ind2, strategy); content_type free_content = ( index::detail::content(enlarged_box) - index::detail::content(bounded_ind1) ) - index::detail::content(bounded_ind2); @@ -129,13 +139,18 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadra BOOST_TRY { + typename index::detail::strategy_type<parameters_type>::type const& + strategy = index::detail::get_strategy(parameters); + // add seeds elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy) elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy) // calculate boxes - detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1); - detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2); + detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), + box1, strategy); + detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), + box2, strategy); // remove seeds if (seed1 < seed2) @@ -185,7 +200,8 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadra content_type content_increase1 = 0; content_type content_increase2 = 0; el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(), - box1, box2, content1, content2, translator, + box1, box2, content1, content2, + translator, strategy, content_increase1, content_increase2); if ( content_increase1 < content_increase2 || @@ -208,13 +224,13 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadra if ( insert_into_group1 ) { elements1.push_back(elem); // MAY THROW, STRONG (copy) - geometry::expand(box1, indexable); + index::detail::expand(box1, indexable, strategy); content1 = index::detail::content(box1); } else { elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy) - geometry::expand(box2, indexable); + index::detail::expand(box2, indexable, strategy); content2 = index::detail::content(box2); } @@ -248,6 +264,7 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadra Box const& box1, Box const& box2, content_type const& content1, content_type const& content2, Translator const& translator, + typename index::detail::strategy_type<parameters_type>::type const& strategy, content_type & out_content_increase1, content_type & out_content_increase2) { typedef typename boost::iterator_value<It>::type element_type; @@ -266,8 +283,8 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadra // calculate enlarged boxes and areas Box enlarged_box1(box1); Box enlarged_box2(box2); - geometry::expand(enlarged_box1, indexable); - geometry::expand(enlarged_box2, indexable); + index::detail::expand(enlarged_box1, indexable, strategy); + index::detail::expand(enlarged_box2, indexable, strategy); content_type enlarged_content1 = index::detail::content(enlarged_box1); content_type enlarged_content2 = index::detail::content(enlarged_box2); diff --git a/boost/geometry/index/detail/rtree/query_iterators.hpp b/boost/geometry/index/detail/rtree/query_iterators.hpp index 83be106b8b..84a5e5df04 100644 --- a/boost/geometry/index/detail/rtree/query_iterators.hpp +++ b/boost/geometry/index/detail/rtree/query_iterators.hpp @@ -61,6 +61,7 @@ struct end_query_iterator template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates> class spatial_query_iterator { + typedef typename Options::parameters_type parameters_type; typedef visitors::spatial_query_incremental<Value, Options, Translator, Box, Allocators, Predicates> visitor_type; typedef typename visitor_type::node_pointer node_pointer; @@ -74,12 +75,12 @@ public: inline spatial_query_iterator() {} - inline spatial_query_iterator(Translator const& t, Predicates const& p) - : m_visitor(t, p) + inline spatial_query_iterator(parameters_type const& par, Translator const& t, Predicates const& p) + : m_visitor(par, t, p) {} - inline spatial_query_iterator(node_pointer root, Translator const& t, Predicates const& p) - : m_visitor(t, p) + inline spatial_query_iterator(node_pointer root, parameters_type const& par, Translator const& t, Predicates const& p) + : m_visitor(par, t, p) { m_visitor.initialize(root); } @@ -129,6 +130,7 @@ private: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex> class distance_query_iterator { + typedef typename Options::parameters_type parameters_type; typedef visitors::distance_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type; typedef typename visitor_type::node_pointer node_pointer; @@ -142,12 +144,12 @@ public: inline distance_query_iterator() {} - inline distance_query_iterator(Translator const& t, Predicates const& p) - : m_visitor(t, p) + inline distance_query_iterator(parameters_type const& par, Translator const& t, Predicates const& p) + : m_visitor(par, t, p) {} - inline distance_query_iterator(node_pointer root, Translator const& t, Predicates const& p) - : m_visitor(t, p) + inline distance_query_iterator(node_pointer root, parameters_type const& par, Translator const& t, Predicates const& p) + : m_visitor(par, t, p) { m_visitor.initialize(root); } diff --git a/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp b/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp index 2ac6eb27c9..209f6ebb20 100644 --- a/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp +++ b/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2019 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -57,11 +61,16 @@ public: // children are leafs if ( node_relative_level <= 1 ) { - return choose_by_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold()); + return choose_by_minimum_overlap_cost(children, indexable, + parameters.get_overlap_cost_threshold(), + index::detail::get_strategy(parameters)); } // children are internal nodes else - return choose_by_minimum_content_cost(children, indexable); + { + return choose_by_minimum_content_cost(children, indexable, + index::detail::get_strategy(parameters)); + } } private: @@ -79,10 +88,11 @@ private: } }; - template <typename Indexable> + template <typename Indexable, typename Strategy> static inline size_t choose_by_minimum_overlap_cost(children_type const& children, Indexable const& indexable, - size_t overlap_cost_threshold) + size_t overlap_cost_threshold, + Strategy const& strategy) { const size_t children_count = children.size(); @@ -100,7 +110,7 @@ private: // expanded child node's box Box box_exp(ch_i.first); - geometry::expand(box_exp, indexable); + index::detail::expand(box_exp, indexable, strategy); // areas difference content_type content = index::detail::content(box_exp); @@ -131,7 +141,11 @@ private: } // calculate minimum or nearly minimum overlap cost - choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable, first_n_children_count, children_count, children_contents); + choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable, + first_n_children_count, + children_count, + children_contents, + strategy); } return choosen_index; @@ -143,12 +157,13 @@ private: || (p1.content_diff == p2.content_diff && (p1.content) < (p2.content)); } - template <typename Indexable, typename ChildrenContents> + template <typename Indexable, typename ChildrenContents, typename Strategy> static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children, Indexable const& indexable, size_t const first_n_children_count, size_t const children_count, - ChildrenContents const& children_contents) + ChildrenContents const& children_contents, + Strategy const& strategy) { BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value"); BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements"); @@ -170,7 +185,7 @@ private: Box box_exp(ch_i.first); // calculate expanded box of child node ch_i - geometry::expand(box_exp, indexable); + index::detail::expand(box_exp, indexable, strategy); content_type overlap_diff = 0; @@ -181,10 +196,10 @@ private: { child_type const& ch_j = children[j]; - content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first); + content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first, strategy); if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp ) { - overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first); + overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first, strategy); } } } @@ -205,8 +220,10 @@ private: return choosen_index; } - template <typename Indexable> - static inline size_t choose_by_minimum_content_cost(children_type const& children, Indexable const& indexable) + template <typename Indexable, typename Strategy> + static inline size_t choose_by_minimum_content_cost(children_type const& children, + Indexable const& indexable, + Strategy const& strategy) { size_t children_count = children.size(); @@ -222,7 +239,7 @@ private: // expanded child node's box Box box_exp(ch_i.first); - geometry::expand(box_exp, indexable); + index::detail::expand(box_exp, indexable, strategy); // areas difference content_type content = index::detail::content(box_exp); diff --git a/boost/geometry/index/detail/rtree/rstar/insert.hpp b/boost/geometry/index/detail/rtree/rstar/insert.hpp index 0abf96ddfc..73a5ccefce 100644 --- a/boost/geometry/index/detail/rtree/rstar/insert.hpp +++ b/boost/geometry/index/detail/rtree/rstar/insert.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -21,6 +25,37 @@ namespace detail { namespace rtree { namespace visitors { namespace rstar { +// Utility to distinguish between default and non-default index strategy +template <typename Point1, typename Point2, typename Strategy> +struct comparable_distance_point_point +{ + typedef typename Strategy::comparable_distance_point_point_strategy_type strategy_type; + typedef typename geometry::comparable_distance_result + < + Point1, Point2, strategy_type + >::type result_type; + + static inline strategy_type get_strategy(Strategy const& strategy) + { + return strategy.get_comparable_distance_point_point_strategy(); + } +}; + +template <typename Point1, typename Point2> +struct comparable_distance_point_point<Point1, Point2, default_strategy> +{ + typedef default_strategy strategy_type; + typedef typename geometry::default_comparable_distance_result + < + Point1, Point2 + >::type result_type; + + static inline strategy_type get_strategy(default_strategy const& ) + { + return strategy_type(); + } +}; + template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> class remove_elements_to_reinsert { @@ -46,10 +81,13 @@ public: typedef typename rtree::elements_type<Node>::type elements_type; typedef typename elements_type::value_type element_type; typedef typename geometry::point_type<Box>::type point_type; + typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; // TODO: awulkiew - change second point_type to the point type of the Indexable? - typedef typename - geometry::default_comparable_distance_result<point_type>::type - comparable_distance_type; + typedef rstar::comparable_distance_point_point + < + point_type, point_type, strategy_type + > comparable_distance_pp; + typedef typename comparable_distance_pp::result_type comparable_distance_type; elements_type & elements = rtree::elements(n); @@ -74,13 +112,16 @@ public: // If constructor is used instead of resize() MS implementation leaks here sorted_elements.reserve(elements_count); // MAY THROW, STRONG (V, E: alloc, copy) + typename comparable_distance_pp::strategy_type + cdist_strategy = comparable_distance_pp::get_strategy(index::detail::get_strategy(parameters)); + for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it ) { point_type element_center; geometry::centroid( rtree::element_indexable(*it, translator), element_center); sorted_elements.push_back(std::make_pair( - geometry::comparable_distance(node_center, element_center), + geometry::comparable_distance(node_center, element_center, cdist_strategy), *it)); // MAY THROW (V, E: copy) } @@ -246,13 +287,17 @@ struct level_insert_base inline void recalculate_aabb(Node const& n) const { base::m_traverse_data.current_element().first = - elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); + elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), + base::m_translator, + index::detail::get_strategy(base::m_parameters)); } inline void recalculate_aabb(leaf const& n) const { base::m_traverse_data.current_element().first = - values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); + values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), + base::m_translator, + index::detail::get_strategy(base::m_parameters)); } size_type result_relative_level; diff --git a/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp b/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp index 6a9261ba5b..0b19a9e9bd 100644 --- a/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp +++ b/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -30,23 +34,27 @@ namespace detail { namespace rtree { namespace rstar { -template <typename Element, typename Translator, typename Tag, size_t Corner, size_t AxisIndex> +template <typename Element, typename Parameters, typename Translator, typename Tag, size_t Corner, size_t AxisIndex> class element_axis_corner_less { typedef typename rtree::element_indexable_type<Element, Translator>::type indexable_type; typedef typename geometry::point_type<indexable_type>::type point_type; typedef geometry::model::box<point_type> bounds_type; - typedef index::detail::bounded_view<indexable_type, bounds_type> bounded_view_type; + typedef typename index::detail::strategy_type<Parameters>::type strategy_type; + typedef index::detail::bounded_view + < + indexable_type, bounds_type, strategy_type + > bounded_view_type; public: - element_axis_corner_less(Translator const& tr) - : m_tr(tr) + element_axis_corner_less(Translator const& tr, strategy_type const& strategy) + : m_tr(tr), m_strategy(strategy) {} bool operator()(Element const& e1, Element const& e2) const { - bounded_view_type bounded_ind1(rtree::element_indexable(e1, m_tr)); - bounded_view_type bounded_ind2(rtree::element_indexable(e2, m_tr)); + bounded_view_type bounded_ind1(rtree::element_indexable(e1, m_tr), m_strategy); + bounded_view_type bounded_ind2(rtree::element_indexable(e2, m_tr), m_strategy); return geometry::get<Corner, AxisIndex>(bounded_ind1) < geometry::get<Corner, AxisIndex>(bounded_ind2); @@ -54,13 +62,16 @@ public: private: Translator const& m_tr; + strategy_type const& m_strategy; }; -template <typename Element, typename Translator, size_t Corner, size_t AxisIndex> -class element_axis_corner_less<Element, Translator, box_tag, Corner, AxisIndex> +template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex> +class element_axis_corner_less<Element, Parameters, Translator, box_tag, Corner, AxisIndex> { + typedef typename index::detail::strategy_type<Parameters>::type strategy_type; + public: - element_axis_corner_less(Translator const& tr) + element_axis_corner_less(Translator const& tr, strategy_type const&) : m_tr(tr) {} @@ -74,11 +85,13 @@ private: Translator const& m_tr; }; -template <typename Element, typename Translator, size_t Corner, size_t AxisIndex> -class element_axis_corner_less<Element, Translator, point_tag, Corner, AxisIndex> +template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex> +class element_axis_corner_less<Element, Parameters, Translator, point_tag, Corner, AxisIndex> { + typedef typename index::detail::strategy_type<Parameters>::type strategy_type; + public: - element_axis_corner_less(Translator const& tr) + element_axis_corner_less(Translator const& tr, strategy_type const& ) : m_tr(tr) {} @@ -113,6 +126,9 @@ struct choose_split_axis_and_index_for_corner BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements"); + typename index::detail::strategy_type<Parameters>::type const& + strategy = index::detail::get_strategy(parameters); + // copy elements Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy) @@ -120,7 +136,10 @@ struct choose_split_axis_and_index_for_corner size_t const index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2; // sort elements - element_axis_corner_less<element_type, Translator, indexable_tag, Corner, AxisIndex> elements_less(translator); + element_axis_corner_less + < + element_type, Parameters, Translator, indexable_tag, Corner, AxisIndex + > elements_less(translator, strategy); std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) // { // typename Elements::iterator f = elements_copy.begin() + index_first; @@ -143,12 +162,14 @@ struct choose_split_axis_and_index_for_corner // TODO - awulkiew: may be optimized - box of group 1 may be initialized with // box of min_elems number of elements and expanded for each iteration by another element - Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, translator); - Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), translator); + Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, + translator, strategy); + Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), + translator, strategy); sum_of_margins += index::detail::comparable_margin(box1) + index::detail::comparable_margin(box2); - content_type ovl = index::detail::intersection_content(box1, box2); + content_type ovl = index::detail::intersection_content(box1, box2, strategy); content_type con = index::detail::content(box1) + index::detail::content(box2); // TODO - shouldn't here be < instead of <= ? @@ -337,14 +358,15 @@ struct nth_element BOOST_STATIC_ASSERT(0 < Dimension); BOOST_STATIC_ASSERT(I < Dimension); - template <typename Elements, typename Translator> - static inline void apply(Elements & elements, const size_t axis, const size_t index, Translator const& tr) + template <typename Elements, typename Parameters, typename Translator> + static inline void apply(Elements & elements, Parameters const& parameters, + const size_t axis, const size_t index, Translator const& tr) { //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value"); if ( axis != I ) { - nth_element<Corner, Dimension, I + 1>::apply(elements, axis, index, tr); // MAY THROW, BASIC (copy) + nth_element<Corner, Dimension, I + 1>::apply(elements, parameters, axis, index, tr); // MAY THROW, BASIC (copy) } else { @@ -352,7 +374,13 @@ struct nth_element typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; typedef typename tag<indexable_type>::type indexable_tag; - element_axis_corner_less<element_type, Translator, indexable_tag, Corner, I> less(tr); + typename index::detail::strategy_type<Parameters>::type + strategy = index::detail::get_strategy(parameters); + + element_axis_corner_less + < + element_type, Parameters, Translator, indexable_tag, Corner, I + > less(tr, strategy); index::detail::nth_element(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy) } } @@ -361,8 +389,9 @@ struct nth_element template <size_t Corner, size_t Dimension> struct nth_element<Corner, Dimension, Dimension> { - template <typename Elements, typename Translator> - static inline void apply(Elements & /*elements*/, const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/) + template <typename Elements, typename Parameters, typename Translator> + static inline void apply(Elements & /*elements*/, Parameters const& /*parameters*/, + const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/) {} }; @@ -432,23 +461,28 @@ struct redistribute_elements<Value, Options, Translator, Box, Allocators, rstar_ if ( split_corner == static_cast<size_t>(min_corner) ) { rstar::nth_element<min_corner, dimension> - ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy) + ::apply(elements_copy, parameters, split_axis, split_index, translator); // MAY THROW, BASIC (copy) } else { rstar::nth_element<max_corner, dimension> - ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy) + ::apply(elements_copy, parameters, split_axis, split_index, translator); // MAY THROW, BASIC (copy) } BOOST_TRY { + typename index::detail::strategy_type<parameters_type>::type const& + strategy = index::detail::get_strategy(parameters); + // copy elements to nodes elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index); // MAY THROW, BASIC elements2.assign(elements_copy.begin() + split_index, elements_copy.end()); // MAY THROW, BASIC // calculate boxes - box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator); - box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), translator); + box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), + translator, strategy); + box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), + translator, strategy); } BOOST_CATCH(...) { diff --git a/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp b/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp index 8e0560379b..b5fe5a0e28 100644 --- a/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp +++ b/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -22,12 +26,14 @@ template <typename Value, typename Options, typename Translator, typename Box, t class are_boxes_ok : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type { - 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; + + typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; public: - are_boxes_ok(Translator const& tr, bool exact_match) - : result(false), m_tr(tr), m_is_root(true), m_exact_match(exact_match) + are_boxes_ok(parameters_type const& parameters, Translator const& tr, bool exact_match) + : result(false), m_parameters(parameters), m_tr(tr), m_is_root(true), m_exact_match(exact_match) {} void operator()(internal_node const& n) @@ -60,7 +66,8 @@ public: m_box = box_bckup; m_is_root = is_root_bckup; - Box box_exp = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr); + Box box_exp = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr, + index::detail::get_strategy(m_parameters)); if ( m_exact_match ) result = m_is_root || geometry::equals(box_exp, m_box); @@ -82,7 +89,8 @@ public: return; } - Box box_exp = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr); + Box box_exp = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr, + index::detail::get_strategy(m_parameters)); if ( m_exact_match ) result = geometry::equals(box_exp, m_box); @@ -96,6 +104,7 @@ public: bool result; private: + parameters_type const& m_parameters; Translator const& m_tr; Box m_box; bool m_is_root; @@ -116,7 +125,7 @@ bool are_boxes_ok(Rtree const& tree, bool exact_match = true) typename RTV::translator_type, typename RTV::box_type, typename RTV::allocators_type - > v(rtv.translator(), exact_match); + > v(tree.parameters(), rtv.translator(), exact_match); rtv.apply_visitor(v); diff --git a/boost/geometry/index/detail/rtree/visitors/children_box.hpp b/boost/geometry/index/detail/rtree/visitors/children_box.hpp index 6c1bafd3de..0d26a79c3e 100644 --- a/boost/geometry/index/detail/rtree/visitors/children_box.hpp +++ b/boost/geometry/index/detail/rtree/visitors/children_box.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -19,12 +23,14 @@ template <typename Value, typename Options, typename Translator, typename Box, t class children_box : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type { - 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; + + typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; public: - inline children_box(Box & result, Translator const& tr) - : m_result(result), m_tr(tr) + inline children_box(Box & result, parameters_type const& parameters, Translator const& tr) + : m_result(result), m_parameters(parameters), m_tr(tr) {} inline void operator()(internal_node const& n) @@ -32,7 +38,8 @@ public: typedef typename rtree::elements_type<internal_node>::type elements_type; elements_type const& elements = rtree::elements(n); - m_result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr); + m_result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr, + index::detail::get_strategy(m_parameters)); } inline void operator()(leaf const& n) @@ -40,11 +47,13 @@ public: typedef typename rtree::elements_type<leaf>::type elements_type; elements_type const& elements = rtree::elements(n); - m_result = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr); + m_result = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr, + index::detail::get_strategy(m_parameters)); } private: Box & m_result; + parameters_type const& m_parameters; Translator const& m_tr; }; diff --git a/boost/geometry/index/detail/rtree/visitors/count.hpp b/boost/geometry/index/detail/rtree/visitors/count.hpp index 7efd5b7028..2cdbd8c0ed 100644 --- a/boost/geometry/index/detail/rtree/visitors/count.hpp +++ b/boost/geometry/index/detail/rtree/visitors/count.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -23,10 +27,10 @@ struct count_helper { return i; } - template <typename Translator> - static inline bool equals(Indexable const& i, Value const& v, Translator const& tr) + template <typename Translator, typename Strategy> + static inline bool equals(Indexable const& i, Value const& v, Translator const& tr, Strategy const& s) { - return geometry::equals(i, tr(v)); + return index::detail::equals<Indexable>::apply(i, tr(v), s); } }; @@ -38,10 +42,10 @@ struct count_helper<Value, Value> { return tr(v); } - template <typename Translator> - static inline bool equals(Value const& v1, Value const& v2, Translator const& tr) + template <typename Translator, typename Strategy> + static inline bool equals(Value const& v1, Value const& v2, Translator const& tr, Strategy const& s) { - return tr.equals(v1, v2); + return tr.equals(v1, v2, s); } }; @@ -49,14 +53,16 @@ template <typename ValueOrIndexable, typename Value, typename Options, typename struct count : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type { - 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; + + typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; + typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; typedef count_helper<ValueOrIndexable, Value> count_help; - inline count(ValueOrIndexable const& vori, Translator const& t) - : value_or_indexable(vori), tr(t), found_count(0) + inline count(ValueOrIndexable const& vori, parameters_type const& parameters, Translator const& t) + : value_or_indexable(vori), m_parameters(parameters), tr(t), found_count(0) {} inline void operator()(internal_node const& n) @@ -68,10 +74,9 @@ struct count for (typename elements_type::const_iterator it = elements.begin(); it != elements.end(); ++it) { - if ( geometry::covered_by( - return_ref_or_bounds( - count_help::indexable(value_or_indexable, tr)), - it->first) ) + if ( index::detail::covered_by_bounds(count_help::indexable(value_or_indexable, tr), + it->first, + index::detail::get_strategy(m_parameters)) ) { rtree::apply_visitor(*this, *it->second); } @@ -88,7 +93,8 @@ struct count it != elements.end(); ++it) { // if value meets predicates - if ( count_help::equals(value_or_indexable, *it, tr) ) + if ( count_help::equals(value_or_indexable, *it, tr, + index::detail::get_strategy(m_parameters)) ) { ++found_count; } @@ -96,6 +102,7 @@ struct count } ValueOrIndexable const& value_or_indexable; + parameters_type const& m_parameters; Translator const& tr; typename Allocators::size_type found_count; }; diff --git a/boost/geometry/index/detail/rtree/visitors/distance_query.hpp b/boost/geometry/index/detail/rtree/visitors/distance_query.hpp index b930714433..20a954dc4e 100644 --- a/boost/geometry/index/detail/rtree/visitors/distance_query.hpp +++ b/boost/geometry/index/detail/rtree/visitors/distance_query.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -104,6 +108,7 @@ class distance_query { public: typedef typename Options::parameters_type parameters_type; + typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; @@ -113,8 +118,8 @@ public: typedef typename nearest_predicate_access::type nearest_predicate_type; typedef typename indexable_type<Translator>::type indexable_type; - typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, value_tag> calculate_value_distance; - typedef index::detail::calculate_distance<nearest_predicate_type, Box, bounds_tag> calculate_node_distance; + typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance; + typedef index::detail::calculate_distance<nearest_predicate_type, Box, strategy_type, bounds_tag> calculate_node_distance; typedef typename calculate_value_distance::result_type value_distance_type; typedef typename calculate_node_distance::result_type node_distance_type; @@ -124,6 +129,7 @@ public: : m_parameters(parameters), m_translator(translator) , m_pred(pred) , m_result(nearest_predicate_access::get(m_pred).count, out_it) + , m_strategy(index::detail::get_strategy(parameters)) {} inline void operator()(internal_node const& n) @@ -147,12 +153,16 @@ public: { // if current node meets predicates // 0 - dummy value - if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) ) + if ( index::detail::predicates_check + < + index::detail::bounds_tag, 0, predicates_len + >(m_pred, 0, it->first, m_strategy) ) { // calculate node's distance(s) for distance predicate node_distance_type node_distance; // if distance isn't ok - move to the next node - if ( !calculate_node_distance::apply(predicate(), it->first, node_distance) ) + if ( !calculate_node_distance::apply(predicate(), it->first, + m_strategy, node_distance) ) { continue; } @@ -226,12 +236,16 @@ public: it != elements.end(); ++it) { // if value meets predicates - if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, m_translator(*it)) ) + if ( index::detail::predicates_check + < + index::detail::value_tag, 0, predicates_len + >(m_pred, *it, m_translator(*it), m_strategy) ) { // calculate values distance for distance predicate value_distance_type value_distance; // if distance is ok - if ( calculate_value_distance::apply(predicate(), m_translator(*it), value_distance) ) + if ( calculate_value_distance::apply(predicate(), m_translator(*it), + m_strategy, value_distance) ) { // store value m_result.store(*it, value_distance); @@ -276,6 +290,8 @@ private: Predicates m_pred; distance_query_result<Value, Translator, value_distance_type, OutIter> m_result; + + strategy_type m_strategy; }; template < @@ -292,6 +308,7 @@ class distance_query_incremental { public: typedef typename Options::parameters_type parameters_type; + typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; @@ -301,8 +318,8 @@ public: typedef typename nearest_predicate_access::type nearest_predicate_type; typedef typename indexable_type<Translator>::type indexable_type; - typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, value_tag> calculate_value_distance; - typedef index::detail::calculate_distance<nearest_predicate_type, Box, bounds_tag> calculate_node_distance; + typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance; + typedef index::detail::calculate_distance<nearest_predicate_type, Box, strategy_type, bounds_tag> calculate_node_distance; typedef typename calculate_value_distance::result_type value_distance_type; typedef typename calculate_node_distance::result_type node_distance_type; @@ -342,14 +359,15 @@ public: // , m_pred() , current_neighbor((std::numeric_limits<size_type>::max)()) // , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) +// , m_strategy_type() {} - inline distance_query_incremental(Translator const& translator, Predicates const& pred) + inline distance_query_incremental(parameters_type const& params, Translator const& translator, Predicates const& pred) : m_translator(::boost::addressof(translator)) , m_pred(pred) , current_neighbor((std::numeric_limits<size_type>::max)()) - , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) + , m_strategy(index::detail::get_strategy(params)) { BOOST_GEOMETRY_INDEX_ASSERT(0 < max_count(), "k must be greather than 0"); } @@ -457,12 +475,16 @@ public: { // if current node meets predicates // 0 - dummy value - if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) ) + if ( index::detail::predicates_check + < + index::detail::bounds_tag, 0, predicates_len + >(m_pred, 0, it->first, m_strategy) ) { // calculate node's distance(s) for distance predicate node_distance_type node_distance; // if distance isn't ok - move to the next node - if ( !calculate_node_distance::apply(predicate(), it->first, node_distance) ) + if ( !calculate_node_distance::apply(predicate(), it->first, + m_strategy, node_distance) ) { continue; } @@ -502,12 +524,16 @@ public: for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it) { // if value meets predicates - if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, (*m_translator)(*it)) ) + if ( index::detail::predicates_check + < + index::detail::value_tag, 0, predicates_len + >(m_pred, *it, (*m_translator)(*it), m_strategy) ) { // calculate values distance for distance predicate value_distance_type value_distance; // if distance is ok - if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), value_distance) ) + if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), + m_strategy, value_distance) ) { // if there is not enough values or current value is closer than furthest neighbour if ( not_enough_neighbors || value_distance < greatest_distance ) @@ -574,11 +600,13 @@ private: const Translator * m_translator; Predicates m_pred; - + internal_stack_type internal_stack; std::vector< std::pair<value_distance_type, const Value *> > neighbors; size_type current_neighbor; node_distance_type next_closest_node_distance; + + strategy_type m_strategy; }; }}} // namespace detail::rtree::visitors diff --git a/boost/geometry/index/detail/rtree/visitors/insert.hpp b/boost/geometry/index/detail/rtree/visitors/insert.hpp index 87d5bbbcca..3c9501f370 100644 --- a/boost/geometry/index/detail/rtree/visitors/insert.hpp +++ b/boost/geometry/index/detail/rtree/visitors/insert.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -16,6 +20,7 @@ #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> #include <boost/geometry/util/condition.hpp> +#include <boost/geometry/index/detail/algorithms/bounds.hpp> #include <boost/geometry/index/detail/algorithms/content.hpp> namespace boost { namespace geometry { namespace index { @@ -43,7 +48,7 @@ public: template <typename Indexable> static inline size_t apply(internal_node & n, Indexable const& indexable, - parameters_type const& /*parameters*/, + parameters_type const& parameters, size_t /*node_relative_level*/) { children_type & children = rtree::elements(n); @@ -65,7 +70,8 @@ public: // expanded child node's box Box box_exp(ch_i.first); - geometry::expand(box_exp, indexable); + index::detail::expand(box_exp, indexable, + index::detail::get_strategy(parameters)); // areas difference content_type content = index::detail::content(box_exp); @@ -274,7 +280,9 @@ protected: // NOTE: This is actually only needed because conditionally the bounding // object may be expanded below. Otherwise the indexable could be // directly used instead - index::detail::bounds(rtree::element_indexable(m_element, m_translator), m_element_bounds); + 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 // Enlarge it in case if it's not bounding geometry type. @@ -300,10 +308,10 @@ protected: apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_traverse_data.current_level); // expand the node to contain value - geometry::expand( + index::detail::expand( rtree::elements(n)[choosen_node_index].first, - m_element_bounds - /*rtree::element_indexable(m_element, m_translator)*/); + m_element_bounds, + index::detail::get_strategy(m_parameters)); // next traversing step traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc) diff --git a/boost/geometry/index/detail/rtree/visitors/remove.hpp b/boost/geometry/index/detail/rtree/visitors/remove.hpp index 7e6162a616..1a3ccd7965 100644 --- a/boost/geometry/index/detail/rtree/visitors/remove.hpp +++ b/boost/geometry/index/detail/rtree/visitors/remove.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -71,9 +75,9 @@ public: internal_size_type child_node_index = 0; for ( ; child_node_index < children.size() ; ++child_node_index ) { - if ( geometry::covered_by( - return_ref_or_bounds(m_translator(m_value)), - children[child_node_index].first) ) + if ( index::detail::covered_by_bounds(m_translator(m_value), + children[child_node_index].first, + index::detail::get_strategy(m_parameters)) ) { // next traversing step traverse_apply_visitor(n, child_node_index); // MAY THROW @@ -112,7 +116,8 @@ public: BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state"); rtree::elements(*m_parent)[m_current_child_index].first - = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator); + = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator, + index::detail::get_strategy(m_parameters)); } // n is root node else @@ -145,11 +150,11 @@ public: { typedef typename rtree::elements_type<leaf>::type elements_type; elements_type & elements = rtree::elements(n); - + // find value and remove it for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it ) { - if ( m_translator.equals(*it, m_value) ) + if ( m_translator.equals(*it, m_value, index::detail::get_strategy(m_parameters)) ) { rtree::move_from_back(elements, it); // MAY THROW (V: copy) elements.pop_back(); @@ -170,7 +175,8 @@ public: if ( 0 != m_parent ) { rtree::elements(*m_parent)[m_current_child_index].first - = rtree::values_box<Box>(elements.begin(), elements.end(), m_translator); + = rtree::values_box<Box>(elements.begin(), elements.end(), m_translator, + index::detail::get_strategy(m_parameters)); } } } diff --git a/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp b/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp index b9cd0ae2c0..c94248cfd0 100644 --- a/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp +++ b/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp @@ -4,6 +4,10 @@ // // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. // +// This file was modified by Oracle on 2019. +// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// // 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) @@ -19,16 +23,19 @@ template <typename Value, typename Options, typename Translator, typename Box, t struct spatial_query : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type { - 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; + typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; + + typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; + typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; typedef typename Allocators::size_type size_type; static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value; - inline spatial_query(Translator const& t, Predicates const& p, OutIter out_it) - : tr(t), pred(p), out_iter(out_it), found_count(0) + inline spatial_query(parameters_type const& par, Translator const& t, Predicates const& p, OutIter out_it) + : tr(t), pred(p), out_iter(out_it), found_count(0), strategy(index::detail::get_strategy(par)) {} inline void operator()(internal_node const& n) @@ -42,8 +49,13 @@ struct spatial_query { // if node meets predicates // 0 - dummy value - if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(pred, 0, it->first) ) + if ( index::detail::predicates_check + < + index::detail::bounds_tag, 0, predicates_len + >(pred, 0, it->first, strategy) ) + { rtree::apply_visitor(*this, *it->second); + } } } @@ -57,7 +69,10 @@ struct spatial_query it != elements.end(); ++it) { // if value meets predicates - if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, *it, tr(*it)) ) + if ( index::detail::predicates_check + < + index::detail::value_tag, 0, predicates_len + >(pred, *it, tr(*it), strategy) ) { *out_iter = *it; ++out_iter; @@ -73,12 +88,17 @@ struct spatial_query OutIter out_iter; size_type found_count; + + strategy_type strategy; }; template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates> class spatial_query_incremental : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type { + typedef typename Options::parameters_type parameters_type; + typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; + public: 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; @@ -99,13 +119,15 @@ public: // , m_pred() , m_values(NULL) , m_current() +// , m_strategy() {} - inline spatial_query_incremental(Translator const& t, Predicates const& p) + inline spatial_query_incremental(parameters_type const& params, Translator const& t, Predicates const& p) : m_translator(::boost::addressof(t)) , m_pred(p) , m_values(NULL) , m_current() + , m_strategy(index::detail::get_strategy(params)) {} inline void operator()(internal_node const& n) @@ -151,8 +173,13 @@ public: { // return if next value is found Value const& v = *m_current; - if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, v, (*m_translator)(v)) ) + if (index::detail::predicates_check + < + index::detail::value_tag, 0, predicates_len + >(m_pred, v, (*m_translator)(v), m_strategy)) + { return; + } ++m_current; } @@ -180,8 +207,13 @@ public: ++m_internal_stack.back().first; // next node is found, push it to the stack - if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) ) + if (index::detail::predicates_check + < + index::detail::bounds_tag, 0, predicates_len + >(m_pred, 0, it->first, m_strategy)) + { rtree::apply_visitor(*this, *(it->second)); + } } } } @@ -205,6 +237,8 @@ private: std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack; const leaf_elements * m_values; leaf_iterator m_current; + + strategy_type m_strategy; }; }}} // namespace detail::rtree::visitors |