//
// R-tree R*-tree next node choosing algorithm implementation
//
-// Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
+// 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
#include <algorithm>
+#include <boost/core/ignore_unused.hpp>
+
#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/index/detail/algorithms/content.hpp>
parameters_type const& parameters,
size_t node_relative_level)
{
- ::boost::ignore_unused_variable_warning(parameters);
+ ::boost::ignore_unused(parameters);
children_type & children = rtree::elements(n);
// 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:
- template <typename Indexable>
+ struct child_contents
+ {
+ content_type content_diff;
+ content_type content;
+ size_t i;
+
+ void set(size_t i_, content_type const& content_, content_type const& content_diff_)
+ {
+ i = i_;
+ content = content_;
+ content_diff = content_diff_;
+ }
+ };
+
+ 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();
size_t choosen_index = 0;
// create container of children sorted by content enlargement needed to include the new value
- typedef boost::tuple<size_t, content_type, content_type> child_contents;
-
- typename rtree::container_from_elements_type<children_type, child_contents>::type children_contents;
- children_contents.resize(children_count);
+ typename rtree::container_from_elements_type<children_type, child_contents>::type
+ children_contents(children_count);
for ( size_t i = 0 ; i < children_count ; ++i )
{
// 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);
content_type content_diff = content - index::detail::content(ch_i.first);
- children_contents[i] = boost::make_tuple(i, content_diff, content);
+ children_contents[i].set(i, content, content_diff);
if ( content_diff < min_content_diff ||
(content_diff == min_content_diff && content < min_content) )
}
// 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;
}
- static inline bool content_diff_less(boost::tuple<size_t, content_type, content_type> const& p1, boost::tuple<size_t, content_type, content_type> const& p2)
+ static inline bool content_diff_less(child_contents const& p1, child_contents const& p2)
{
- return boost::get<1>(p1) < boost::get<1>(p2) ||
- (boost::get<1>(p1) == boost::get<1>(p2) && boost::get<2>(p1) < boost::get<2>(p2));
+ return p1.content_diff < p2.content_diff
+ || (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");
content_type smallest_content = (std::numeric_limits<content_type>::max)();
// for each child node
- for (size_t i = 0 ; i < first_n_children_count ; ++i )
+ for (size_t first_i = 0 ; first_i < first_n_children_count ; ++first_i)
{
+ size_t i = children_contents[first_i].i;
+ content_type const& content = children_contents[first_i].content;
+ content_type const& content_diff = children_contents[first_i].content_diff;
+
child_type const& ch_i = children[i];
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;
{
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);
}
}
}
- content_type content = boost::get<2>(children_contents[i]);
- content_type content_diff = boost::get<1>(children_contents[i]);
-
// update result
if ( overlap_diff < smallest_overlap_diff ||
( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
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();
// 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);
projects / ceph.git / blobdiff