diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/partition.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/partition.hpp | 456 |
1 files changed, 221 insertions, 235 deletions
diff --git a/boost/geometry/algorithms/detail/partition.hpp b/boost/geometry/algorithms/detail/partition.hpp index 25a34ba2ec..8b19add479 100644 --- a/boost/geometry/algorithms/detail/partition.hpp +++ b/boost/geometry/algorithms/detail/partition.hpp @@ -1,6 +1,11 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2011-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, 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 @@ -9,10 +14,13 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP +#include <cstddef> #include <vector> -#include <boost/range/algorithm/copy.hpp> -#include <boost/geometry/algorithms/assign.hpp> +#include <boost/range.hpp> +#include <boost/geometry/core/access.hpp> #include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/algorithms/assign.hpp> + namespace boost { namespace geometry { @@ -20,8 +28,6 @@ namespace boost { namespace geometry namespace detail { namespace partition { -typedef std::vector<std::size_t> index_vector_type; - template <int Dimension, typename Box> inline void divide_box(Box const& box, Box& lower_box, Box& upper_box) { @@ -38,31 +44,26 @@ inline void divide_box(Box const& box, Box& lower_box, Box& upper_box) geometry::set<min_corner, Dimension>(upper_box, mid); } -// Divide collection into three subsets: lower, upper and oversized +// Divide forward_range into three subsets: lower, upper and oversized // (not-fitting) // (lower == left or bottom, upper == right or top) -template <typename OverlapsPolicy, typename InputCollection, typename Box> +template <typename OverlapsPolicy, typename Box, typename IteratorVector> inline void divide_into_subsets(Box const& lower_box, Box const& upper_box, - InputCollection const& collection, - index_vector_type const& input, - index_vector_type& lower, - index_vector_type& upper, - index_vector_type& exceeding) + IteratorVector const& input, + IteratorVector& lower, + IteratorVector& upper, + IteratorVector& exceeding) { - typedef boost::range_iterator + typedef typename boost::range_iterator < - index_vector_type const - >::type index_iterator_type; + IteratorVector const + >::type it_type; - for(index_iterator_type it = boost::begin(input); - it != boost::end(input); - ++it) + for(it_type it = boost::begin(input); it != boost::end(input); ++it) { - bool const lower_overlapping = OverlapsPolicy::apply(lower_box, - collection[*it]); - bool const upper_overlapping = OverlapsPolicy::apply(upper_box, - collection[*it]); + bool const lower_overlapping = OverlapsPolicy::apply(lower_box, **it); + bool const upper_overlapping = OverlapsPolicy::apply(upper_box, **it); if (lower_overlapping && upper_overlapping) { @@ -84,99 +85,109 @@ inline void divide_into_subsets(Box const& lower_box, } } -template <typename ExpandPolicy, typename Box, typename InputCollection> -inline void expand_with_elements(Box& total, - InputCollection const& collection, - index_vector_type const& input) +template +< + typename ExpandPolicy, + typename Box, + typename IteratorVector +> +inline void expand_with_elements(Box& total, IteratorVector const& input) { - typedef boost::range_iterator<index_vector_type const>::type it_type; + typedef typename boost::range_iterator<IteratorVector const>::type it_type; for(it_type it = boost::begin(input); it != boost::end(input); ++it) { - ExpandPolicy::apply(total, collection[*it]); + ExpandPolicy::apply(total, **it); } } -// Match collection with itself -template <typename InputCollection, typename Policy> -inline void handle_one(InputCollection const& collection, - index_vector_type const& input, - Policy& policy) +// Match forward_range with itself +template <typename Policy, typename IteratorVector> +inline void handle_one(IteratorVector const& input, Policy& policy) { if (boost::size(input) == 0) { return; } - typedef boost::range_iterator<index_vector_type const>::type - index_iterator_type; + typedef typename boost::range_iterator<IteratorVector const>::type it_type; // Quadratic behaviour at lowest level (lowest quad, or all exceeding) - for(index_iterator_type it1 = boost::begin(input); - it1 != boost::end(input); - ++it1) + for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1) { - index_iterator_type it2 = it1; - for(++it2; it2 != boost::end(input); ++it2) + it_type it2 = it1; + for (++it2; it2 != boost::end(input); ++it2) { - policy.apply(collection[*it1], collection[*it2]); + policy.apply(**it1, **it2); } } } -// Match collection 1 with collection 2 +// Match forward range 1 with forward range 2 template < - typename InputCollection1, - typename InputCollection2, - typename Policy + typename Policy, + typename IteratorVector1, + typename IteratorVector2 > -inline void handle_two( - InputCollection1 const& collection1, index_vector_type const& input1, - InputCollection2 const& collection2, index_vector_type const& input2, +inline void handle_two(IteratorVector1 const& input1, + IteratorVector2 const& input2, Policy& policy) { + typedef typename boost::range_iterator + < + IteratorVector1 const + >::type iterator_type1; + + typedef typename boost::range_iterator + < + IteratorVector2 const + >::type iterator_type2; + if (boost::size(input1) == 0 || boost::size(input2) == 0) { return; } - typedef boost::range_iterator - < - index_vector_type const - >::type index_iterator_type; - - for(index_iterator_type it1 = boost::begin(input1); + for(iterator_type1 it1 = boost::begin(input1); it1 != boost::end(input1); ++it1) { - for(index_iterator_type it2 = boost::begin(input2); + for(iterator_type2 it2 = boost::begin(input2); it2 != boost::end(input2); ++it2) { - policy.apply(collection1[*it1], collection2[*it2]); + policy.apply(**it1, **it2); } } } -inline bool recurse_ok(index_vector_type const& input, +template <typename IteratorVector> +inline bool recurse_ok(IteratorVector const& input, std::size_t min_elements, std::size_t level) { return boost::size(input) >= min_elements && level < 100; } -inline bool recurse_ok(index_vector_type const& input1, - index_vector_type const& input2, +template <typename IteratorVector1, typename IteratorVector2> +inline bool recurse_ok(IteratorVector1 const& input1, + IteratorVector2 const& input2, std::size_t min_elements, std::size_t level) { return boost::size(input1) >= min_elements && recurse_ok(input2, min_elements, level); } -inline bool recurse_ok(index_vector_type const& input1, - index_vector_type const& input2, - index_vector_type const& input3, +template +< + typename IteratorVector1, + typename IteratorVector2, + typename IteratorVector3 +> +inline bool recurse_ok(IteratorVector1 const& input1, + IteratorVector2 const& input2, + IteratorVector3 const& input3, std::size_t min_elements, std::size_t level) { return boost::size(input1) >= min_elements @@ -193,7 +204,7 @@ template typename ExpandPolicy2, typename VisitBoxPolicy > -class partition_two_collections; +class partition_two_ranges; template @@ -204,79 +215,71 @@ template typename ExpandPolicy, typename VisitBoxPolicy > -class partition_one_collection +class partition_one_range { - typedef std::vector<std::size_t> index_vector_type; - - template <typename InputCollection> - static inline Box get_new_box(InputCollection const& collection, - index_vector_type const& input) + template <typename IteratorVector> + static inline Box get_new_box(IteratorVector const& input) { Box box; geometry::assign_inverse(box); - expand_with_elements<ExpandPolicy>(box, collection, input); + expand_with_elements<ExpandPolicy>(box, input); return box; } - template <typename InputCollection, typename Policy> + template <typename Policy, typename IteratorVector> static inline void next_level(Box const& box, - InputCollection const& collection, - index_vector_type const& input, + IteratorVector const& input, std::size_t level, std::size_t min_elements, Policy& policy, VisitBoxPolicy& box_policy) { if (recurse_ok(input, min_elements, level)) { - partition_one_collection + partition_one_range < 1 - Dimension, Box, OverlapsPolicy, ExpandPolicy, VisitBoxPolicy - >::apply(box, collection, input, - level + 1, min_elements, policy, box_policy); + >::apply(box, input, level + 1, min_elements, policy, box_policy); } else { - handle_one(collection, input, policy); + handle_one(input, policy); } } - // Function to switch to two collections if there are geometries exceeding - // the separation line - template <typename InputCollection, typename Policy> + // Function to switch to two forward ranges if there are + // geometries exceeding the separation line + template <typename Policy, typename IteratorVector> static inline void next_level2(Box const& box, - InputCollection const& collection, - index_vector_type const& input1, - index_vector_type const& input2, + IteratorVector const& input1, + IteratorVector const& input2, std::size_t level, std::size_t min_elements, Policy& policy, VisitBoxPolicy& box_policy) { - if (recurse_ok(input1, input2, min_elements, level)) { - partition_two_collections + partition_two_ranges < 1 - Dimension, Box, OverlapsPolicy, OverlapsPolicy, ExpandPolicy, ExpandPolicy, VisitBoxPolicy - >::apply(box, collection, input1, collection, input2, - level + 1, min_elements, policy, box_policy); + >::apply(box, input1, input2, level + 1, min_elements, + policy, box_policy); } else { - handle_two(collection, input1, collection, input2, policy); + handle_two(input1, input2, policy); } } public : - template <typename InputCollection, typename Policy> + template <typename Policy, typename IteratorVector> static inline void apply(Box const& box, - InputCollection const& collection, - index_vector_type const& input, + IteratorVector const& input, std::size_t level, std::size_t min_elements, Policy& policy, VisitBoxPolicy& box_policy) @@ -286,33 +289,31 @@ public : Box lower_box, upper_box; divide_box<Dimension>(box, lower_box, upper_box); - index_vector_type lower, upper, exceeding; - divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection, + IteratorVector lower, upper, exceeding; + divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, input, lower, upper, exceeding); if (boost::size(exceeding) > 0) { // Get the box of exceeding-only - Box exceeding_box = get_new_box(collection, exceeding); + Box exceeding_box = get_new_box(exceeding); // Recursively do exceeding elements only, in next dimension they // will probably be less exceeding within the new box - next_level(exceeding_box, collection, exceeding, level, - min_elements, policy, box_policy); - - // Switch to two collections, combine exceeding with lower resp upper - // but not lower/lower, upper/upper - next_level2(exceeding_box, collection, exceeding, lower, level, - min_elements, policy, box_policy); - next_level2(exceeding_box, collection, exceeding, upper, level, - min_elements, policy, box_policy); + next_level(exceeding_box, exceeding, level, min_elements, + policy, box_policy); + + // Switch to two forward ranges, combine exceeding with + // lower resp upper, but not lower/lower, upper/upper + next_level2(exceeding_box, exceeding, lower, level, min_elements, + policy, box_policy); + next_level2(exceeding_box, exceeding, upper, level, min_elements, + policy, box_policy); } // Recursively call operation both parts - next_level(lower_box, collection, lower, level, min_elements, - policy, box_policy); - next_level(upper_box, collection, upper, level, min_elements, - policy, box_policy); + next_level(lower_box, lower, level, min_elements, policy, box_policy); + next_level(upper_box, upper, level, min_elements, policy, box_policy); } }; @@ -326,25 +327,21 @@ template typename ExpandPolicy2, typename VisitBoxPolicy > -class partition_two_collections +class partition_two_ranges { - typedef std::vector<std::size_t> index_vector_type; - template < - typename InputCollection1, - typename InputCollection2, - typename Policy + typename Policy, + typename IteratorVector1, + typename IteratorVector2 > static inline void next_level(Box const& box, - InputCollection1 const& collection1, - index_vector_type const& input1, - InputCollection2 const& collection2, - index_vector_type const& input2, + IteratorVector1 const& input1, + IteratorVector2 const& input2, std::size_t level, std::size_t min_elements, Policy& policy, VisitBoxPolicy& box_policy) { - partition_two_collections + partition_two_ranges < 1 - Dimension, Box, @@ -353,50 +350,38 @@ class partition_two_collections ExpandPolicy1, ExpandPolicy2, VisitBoxPolicy - >::apply(box, collection1, input1, collection2, input2, - level + 1, min_elements, - policy, box_policy); + >::apply(box, input1, input2, level + 1, min_elements, + policy, box_policy); } - template - < - typename ExpandPolicy, - typename InputCollection - > - static inline Box get_new_box(InputCollection const& collection, - index_vector_type const& input) + template <typename ExpandPolicy, typename IteratorVector> + static inline Box get_new_box(IteratorVector const& input) { Box box; geometry::assign_inverse(box); - expand_with_elements<ExpandPolicy>(box, collection, input); + expand_with_elements<ExpandPolicy>(box, input); return box; } - template - < - typename InputCollection1, - typename InputCollection2 - > - static inline Box get_new_box(InputCollection1 const& collection1, - index_vector_type const& input1, - InputCollection2 const& collection2, - index_vector_type const& input2) + template <typename IteratorVector1, typename IteratorVector2> + static inline Box get_new_box(IteratorVector1 const& input1, + IteratorVector2 const& input2) { - Box box = get_new_box<ExpandPolicy1>(collection1, input1); - expand_with_elements<ExpandPolicy2>(box, collection2, input2); + Box box = get_new_box<ExpandPolicy1>(input1); + expand_with_elements<ExpandPolicy2>(box, input2); return box; } public : template < - typename InputCollection1, - typename InputCollection2, - typename Policy + typename Policy, + typename IteratorVector1, + typename IteratorVector2 > static inline void apply(Box const& box, - InputCollection1 const& collection1, index_vector_type const& input1, - InputCollection2 const& collection2, index_vector_type const& input2, + IteratorVector1 const& input1, + IteratorVector2 const& input2, std::size_t level, std::size_t min_elements, Policy& policy, VisitBoxPolicy& box_policy) @@ -406,11 +391,11 @@ public : Box lower_box, upper_box; divide_box<Dimension>(box, lower_box, upper_box); - index_vector_type lower1, upper1, exceeding1; - index_vector_type lower2, upper2, exceeding2; - divide_into_subsets<OverlapsPolicy1>(lower_box, upper_box, collection1, + IteratorVector1 lower1, upper1, exceeding1; + IteratorVector2 lower2, upper2, exceeding2; + divide_into_subsets<OverlapsPolicy1>(lower_box, upper_box, input1, lower1, upper1, exceeding1); - divide_into_subsets<OverlapsPolicy2>(lower_box, upper_box, collection2, + divide_into_subsets<OverlapsPolicy2>(lower_box, upper_box, input2, lower2, upper2, exceeding2); if (boost::size(exceeding1) > 0) @@ -419,35 +404,31 @@ public : if (recurse_ok(exceeding1, exceeding2, min_elements, level)) { - Box exceeding_box = get_new_box(collection1, exceeding1, - collection2, exceeding2); - next_level(exceeding_box, collection1, exceeding1, - collection2, exceeding2, level, - min_elements, policy, box_policy); + Box exceeding_box = get_new_box(exceeding1, exceeding2); + next_level(exceeding_box, exceeding1, exceeding2, level, + min_elements, policy, box_policy); } else { - handle_two(collection1, exceeding1, collection2, exceeding2, - policy); + handle_two(exceeding1, exceeding2, policy); } // All exceeding from 1 with lower and upper of 2: - // (Check sizes of all three collections to avoid recurse into + // (Check sizes of all three forward ranges to avoid recurse into // the same combinations again and again) if (recurse_ok(lower2, upper2, exceeding1, min_elements, level)) { - Box exceeding_box - = get_new_box<ExpandPolicy1>(collection1, exceeding1); - next_level(exceeding_box, collection1, exceeding1, - collection2, lower2, level, min_elements, policy, box_policy); - next_level(exceeding_box, collection1, exceeding1, - collection2, upper2, level, min_elements, policy, box_policy); + Box exceeding_box = get_new_box<ExpandPolicy1>(exceeding1); + next_level(exceeding_box, exceeding1, lower2, level, + min_elements, policy, box_policy); + next_level(exceeding_box, exceeding1, upper2, level, + min_elements, policy, box_policy); } else { - handle_two(collection1, exceeding1, collection2, lower2, policy); - handle_two(collection1, exceeding1, collection2, upper2, policy); + handle_two(exceeding1, lower2, policy); + handle_two(exceeding1, upper2, policy); } } @@ -456,37 +437,36 @@ public : // All exceeding from 2 with lower and upper of 1: if (recurse_ok(lower1, upper1, exceeding2, min_elements, level)) { - Box exceeding_box - = get_new_box<ExpandPolicy2>(collection2, exceeding2); - next_level(exceeding_box, collection1, lower1, - collection2, exceeding2, level, min_elements, policy, box_policy); - next_level(exceeding_box, collection1, upper1, - collection2, exceeding2, level, min_elements, policy, box_policy); + Box exceeding_box = get_new_box<ExpandPolicy2>(exceeding2); + next_level(exceeding_box, lower1, exceeding2, level, + min_elements, policy, box_policy); + next_level(exceeding_box, upper1, exceeding2, level, + min_elements, policy, box_policy); } else { - handle_two(collection1, lower1, collection2, exceeding2, policy); - handle_two(collection1, upper1, collection2, exceeding2, policy); + handle_two(lower1, exceeding2, policy); + handle_two(upper1, exceeding2, policy); } } if (recurse_ok(lower1, lower2, min_elements, level)) { - next_level(lower_box, collection1, lower1, collection2, lower2, level, - min_elements, policy, box_policy); + next_level(lower_box, lower1, lower2, level, + min_elements, policy, box_policy); } else { - handle_two(collection1, lower1, collection2, lower2, policy); + handle_two(lower1, lower2, policy); } if (recurse_ok(upper1, upper2, min_elements, level)) { - next_level(upper_box, collection1, upper1, collection2, upper2, level, - min_elements, policy, box_policy); + next_level(upper_box, upper1, upper2, level, + min_elements, policy, box_policy); } else { - handle_two(collection1, upper1, collection2, upper2, policy); + handle_two(upper1, upper2, policy); } } }; @@ -523,63 +503,67 @@ template > class partition { - typedef std::vector<std::size_t> index_vector_type; - - template <typename ExpandPolicy, typename IncludePolicy, typename InputCollection> - static inline void expand_to_collection(InputCollection const& collection, - Box& total, index_vector_type& index_vector) + template + < + typename ExpandPolicy, + typename IncludePolicy, + typename ForwardRange, + typename IteratorVector + > + static inline void expand_to_range(ForwardRange const& forward_range, + Box& total, IteratorVector& iterator_vector) { - std::size_t index = 0; - for(typename boost::range_iterator<InputCollection const>::type it - = boost::begin(collection); - it != boost::end(collection); - ++it, ++index) + for(typename boost::range_iterator<ForwardRange const>::type it + = boost::begin(forward_range); + it != boost::end(forward_range); + ++it) { if (IncludePolicy::apply(*it)) { ExpandPolicy::apply(total, *it); - index_vector.push_back(index); + iterator_vector.push_back(it); } } } public : - template <typename InputCollection, typename VisitPolicy> - static inline void apply(InputCollection const& collection, + template <typename ForwardRange, typename VisitPolicy> + static inline void apply(ForwardRange const& forward_range, VisitPolicy& visitor, std::size_t min_elements = 16, VisitBoxPolicy box_visitor = detail::partition::visit_no_policy() ) { - if (std::size_t(boost::size(collection)) > min_elements) + typedef typename boost::range_iterator + < + ForwardRange const + >::type iterator_type; + + if (std::size_t(boost::size(forward_range)) > min_elements) { - index_vector_type index_vector; + std::vector<iterator_type> iterator_vector; Box total; assign_inverse(total); - expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection, - total, index_vector); + expand_to_range<ExpandPolicy1, IncludePolicy1>(forward_range, + total, iterator_vector); - detail::partition::partition_one_collection + detail::partition::partition_one_range < 0, Box, OverlapsPolicy1, ExpandPolicy1, VisitBoxPolicy - >::apply(total, collection, index_vector, 0, min_elements, - visitor, box_visitor); + >::apply(total, iterator_vector, 0, min_elements, + visitor, box_visitor); } else { - typedef typename boost::range_iterator - < - InputCollection const - >::type iterator_type; - for(iterator_type it1 = boost::begin(collection); - it1 != boost::end(collection); + for(iterator_type it1 = boost::begin(forward_range); + it1 != boost::end(forward_range); ++it1) { iterator_type it2 = it1; - for(++it2; it2 != boost::end(collection); ++it2) + for(++it2; it2 != boost::end(forward_range); ++it2) { visitor.apply(*it1, *it2); } @@ -589,53 +573,55 @@ public : template < - typename InputCollection1, - typename InputCollection2, + typename ForwardRange1, + typename ForwardRange2, typename VisitPolicy > - static inline void apply(InputCollection1 const& collection1, - InputCollection2 const& collection2, + static inline void apply(ForwardRange1 const& forward_range1, + ForwardRange2 const& forward_range2, VisitPolicy& visitor, std::size_t min_elements = 16, - VisitBoxPolicy box_visitor = detail::partition::visit_no_policy() + VisitBoxPolicy box_visitor + = detail::partition::visit_no_policy() ) { - if (std::size_t(boost::size(collection1)) > min_elements - && std::size_t(boost::size(collection2)) > min_elements) + typedef typename boost::range_iterator + < + ForwardRange1 const + >::type iterator_type1; + + typedef typename boost::range_iterator + < + ForwardRange2 const + >::type iterator_type2; + + if (std::size_t(boost::size(forward_range1)) > min_elements + && std::size_t(boost::size(forward_range2)) > min_elements) { - index_vector_type index_vector1, index_vector2; + std::vector<iterator_type1> iterator_vector1; + std::vector<iterator_type2> iterator_vector2; Box total; assign_inverse(total); - expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection1, - total, index_vector1); - expand_to_collection<ExpandPolicy2, IncludePolicy2>(collection2, - total, index_vector2); + expand_to_range<ExpandPolicy1, IncludePolicy1>(forward_range1, + total, iterator_vector1); + expand_to_range<ExpandPolicy2, IncludePolicy2>(forward_range2, + total, iterator_vector2); - detail::partition::partition_two_collections + detail::partition::partition_two_ranges < 0, Box, OverlapsPolicy1, OverlapsPolicy2, ExpandPolicy1, ExpandPolicy2, VisitBoxPolicy - >::apply(total, - collection1, index_vector1, - collection2, index_vector2, - 0, min_elements, visitor, box_visitor); + >::apply(total, iterator_vector1, iterator_vector2, + 0, min_elements, visitor, box_visitor); } else { - typedef typename boost::range_iterator - < - InputCollection1 const - >::type iterator_type1; - typedef typename boost::range_iterator - < - InputCollection2 const - >::type iterator_type2; - for(iterator_type1 it1 = boost::begin(collection1); - it1 != boost::end(collection1); + for(iterator_type1 it1 = boost::begin(forward_range1); + it1 != boost::end(forward_range1); ++it1) { - for(iterator_type2 it2 = boost::begin(collection2); - it2 != boost::end(collection2); + for(iterator_type2 it2 = boost::begin(forward_range2); + it2 != boost::end(forward_range2); ++it2) { visitor.apply(*it1, *it2); |