]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/boost/geometry/algorithms/detail/partition.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
import new upstream nautilus stable release 14.2.8
[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / partition.hpp
CommitLineData
b32b8144
FG		 1// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3// Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands.
4// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5
92f5a8d4
TL		 6// This file was modified by Oracle on 2015, 2017, 2018, 2019.
7// Modifications copyright (c) 2015-2019 Oracle and/or its affiliates.
b32b8144
FG		 8
9// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11
12// Use, modification and distribution is subject to the Boost Software License,
13// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
14// http://www.boost.org/LICENSE_1_0.txt)
15
16#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
17#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
18
19#include <cstddef>
20#include <vector>
21#include <boost/range.hpp>
92f5a8d4
TL		 22#include <boost/type_traits/is_integral.hpp>
23
b32b8144
FG		 24#include <boost/geometry/core/access.hpp>
25#include <boost/geometry/core/coordinate_type.hpp>
26#include <boost/geometry/algorithms/assign.hpp>
27
28
29namespace boost { namespace geometry
30{
31
32namespace detail { namespace partition
33{
34
92f5a8d4
TL		 35template <typename T, bool IsIntegral = boost::is_integral<T>::value>
36struct divide_interval
37{
38 static inline T apply(T const& mi, T const& ma)
39 {
40 static T const two = 2;
41 return (mi + ma) / two;
42 }
43};
44
45template <typename T>
46struct divide_interval<T, true>
47{
48 static inline T apply(T const& mi, T const& ma)
49 {
50 // avoid overflow
51 return mi / 2 + ma / 2 + (mi % 2 + ma % 2) / 2;
52 }
53};
54
b32b8144
FG		 55template <int Dimension, typename Box>
56inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
57{
58 typedef typename coordinate_type<Box>::type ctype;
59
60 // Divide input box into two parts, e.g. left/right
92f5a8d4
TL		 61 ctype mid = divide_interval<ctype>::apply(
62 geometry::get<min_corner, Dimension>(box),
63 geometry::get<max_corner, Dimension>(box));
b32b8144
FG		 64
65 lower_box = box;
66 upper_box = box;
67 geometry::set<max_corner, Dimension>(lower_box, mid);
68 geometry::set<min_corner, Dimension>(upper_box, mid);
69}
70
71// Divide forward_range into three subsets: lower, upper and oversized
72// (not-fitting)
73// (lower == left or bottom, upper == right or top)
74template <typename Box, typename IteratorVector, typename OverlapsPolicy>
75inline void divide_into_subsets(Box const& lower_box,
76 Box const& upper_box,
77 IteratorVector const& input,
78 IteratorVector& lower,
79 IteratorVector& upper,
80 IteratorVector& exceeding,
81 OverlapsPolicy const& overlaps_policy)
82{
83 typedef typename boost::range_iterator
84 <
85 IteratorVector const
86 >::type it_type;
87
88 for(it_type it = boost::begin(input); it != boost::end(input); ++it)
89 {
90 bool const lower_overlapping = overlaps_policy.apply(lower_box, **it);
91 bool const upper_overlapping = overlaps_policy.apply(upper_box, **it);
92
93 if (lower_overlapping && upper_overlapping)
94 {
95 exceeding.push_back(*it);
96 }
97 else if (lower_overlapping)
98 {
99 lower.push_back(*it);
100 }
101 else if (upper_overlapping)
102 {
103 upper.push_back(*it);
104 }
105 else
106 {
107 // Is nowhere. That is (since 1.58) possible, it might be
108 // skipped by the OverlapsPolicy to enhance performance
109 }
110 }
111}
112
113template
114<
115 typename Box,
116 typename IteratorVector,
117 typename ExpandPolicy
118>
119inline void expand_with_elements(Box& total, IteratorVector const& input,
120 ExpandPolicy const& expand_policy)
121{
122 typedef typename boost::range_iterator<IteratorVector const>::type it_type;
123 for(it_type it = boost::begin(input); it != boost::end(input); ++it)
124 {
125 expand_policy.apply(total, **it);
126 }
127}
128
129
130// Match forward_range with itself
131template <typename IteratorVector, typename VisitPolicy>
132inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor)
133{
134 if (boost::empty(input))
135 {
136 return true;
137 }
138
139 typedef typename boost::range_iterator<IteratorVector const>::type it_type;
140
141 // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
142 for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
143 {
144 it_type it2 = it1;
145 for (++it2; it2 != boost::end(input); ++it2)
146 {
147 if (! visitor.apply(**it1, **it2))
148 {
149 return false; // interrupt
150 }
151 }
152 }
153
154 return true;
155}
156
157// Match forward range 1 with forward range 2
158template
159<
160 typename IteratorVector1,
161 typename IteratorVector2,
162 typename VisitPolicy
163>
164inline bool handle_two(IteratorVector1 const& input1,
165 IteratorVector2 const& input2,
166 VisitPolicy& visitor)
167{
168 typedef typename boost::range_iterator
169 <
170 IteratorVector1 const
171 >::type iterator_type1;
172
173 typedef typename boost::range_iterator
174 <
175 IteratorVector2 const
176 >::type iterator_type2;
177
178 if (boost::empty(input1) || boost::empty(input2))
179 {
180 return true;
181 }
182
183 for(iterator_type1 it1 = boost::begin(input1);
184 it1 != boost::end(input1);
185 ++it1)
186 {
187 for(iterator_type2 it2 = boost::begin(input2);
188 it2 != boost::end(input2);
189 ++it2)
190 {
191 if (! visitor.apply(**it1, **it2))
192 {
193 return false; // interrupt
194 }
195 }
196 }
197
198 return true;
199}
200
201template <typename IteratorVector>
202inline bool recurse_ok(IteratorVector const& input,
203 std::size_t min_elements, std::size_t level)
204{
205 return boost::size(input) >= min_elements
206 && level < 100;
207}
208
209template <typename IteratorVector1, typename IteratorVector2>
210inline bool recurse_ok(IteratorVector1 const& input1,
211 IteratorVector2 const& input2,
212 std::size_t min_elements, std::size_t level)
213{
214 return boost::size(input1) >= min_elements
215 && recurse_ok(input2, min_elements, level);
216}
217
218template
219<
220 typename IteratorVector1,
221 typename IteratorVector2,
222 typename IteratorVector3
223>
224inline bool recurse_ok(IteratorVector1 const& input1,
225 IteratorVector2 const& input2,
226 IteratorVector3 const& input3,
227 std::size_t min_elements, std::size_t level)
228{
229 return boost::size(input1) >= min_elements
230 && recurse_ok(input2, input3, min_elements, level);
231}
232
233
234template <int Dimension, typename Box>
235class partition_two_ranges;
236
237
238template <int Dimension, typename Box>
239class partition_one_range
240{
241 template <typename IteratorVector, typename ExpandPolicy>
242 static inline Box get_new_box(IteratorVector const& input,
243 ExpandPolicy const& expand_policy)
244 {
245 Box box;
246 geometry::assign_inverse(box);
247 expand_with_elements(box, input, expand_policy);
248 return box;
249 }
250
251 template
252 <
253 typename IteratorVector,
254 typename VisitPolicy,
255 typename ExpandPolicy,
256 typename OverlapsPolicy,
257 typename VisitBoxPolicy
258 >
259 static inline bool next_level(Box const& box,
260 IteratorVector const& input,
261 std::size_t level, std::size_t min_elements,
262 VisitPolicy& visitor,
263 ExpandPolicy const& expand_policy,
264 OverlapsPolicy const& overlaps_policy,
265 VisitBoxPolicy& box_policy)
266 {
267 if (recurse_ok(input, min_elements, level))
268 {
269 return partition_one_range
270 <
271 1 - Dimension,
272 Box
273 >::apply(box, input, level + 1, min_elements,
274 visitor, expand_policy, overlaps_policy, box_policy);
275 }
276 else
277 {
278 return handle_one(input, visitor);
279 }
280 }
281
282 // Function to switch to two forward ranges if there are
283 // geometries exceeding the separation line
284 template
285 <
286 typename IteratorVector,
287 typename VisitPolicy,
288 typename ExpandPolicy,
289 typename OverlapsPolicy,
290 typename VisitBoxPolicy
291 >
292 static inline bool next_level2(Box const& box,
293 IteratorVector const& input1,
294 IteratorVector const& input2,
295 std::size_t level, std::size_t min_elements,
296 VisitPolicy& visitor,
297 ExpandPolicy const& expand_policy,
298 OverlapsPolicy const& overlaps_policy,
299 VisitBoxPolicy& box_policy)
300 {
301 if (recurse_ok(input1, input2, min_elements, level))
302 {
303 return partition_two_ranges
304 <
305 1 - Dimension, Box
306 >::apply(box, input1, input2, level + 1, min_elements,
307 visitor, expand_policy, overlaps_policy,
308 expand_policy, overlaps_policy, box_policy);
309 }
310 else
311 {
312 return handle_two(input1, input2, visitor);
313 }
314 }
315
316public :
317 template
318 <
319 typename IteratorVector,
320 typename VisitPolicy,
321 typename ExpandPolicy,
322 typename OverlapsPolicy,
323 typename VisitBoxPolicy
324 >
325 static inline bool apply(Box const& box,
326 IteratorVector const& input,
327 std::size_t level,
328 std::size_t min_elements,
329 VisitPolicy& visitor,
330 ExpandPolicy const& expand_policy,
331 OverlapsPolicy const& overlaps_policy,
332 VisitBoxPolicy& box_policy)
333 {
334 box_policy.apply(box, level);
335
336 Box lower_box, upper_box;
337 divide_box<Dimension>(box, lower_box, upper_box);
338
339 IteratorVector lower, upper, exceeding;
340 divide_into_subsets(lower_box, upper_box,
341 input, lower, upper, exceeding,
342 overlaps_policy);
343
344 if (! boost::empty(exceeding))
345 {
346 // Get the box of exceeding-only
347 Box exceeding_box = get_new_box(exceeding, expand_policy);
348
349 // Recursively do exceeding elements only, in next dimension they
350 // will probably be less exceeding within the new box
351 if (! (next_level(exceeding_box, exceeding, level, min_elements,
352 visitor, expand_policy, overlaps_policy, box_policy)
353 // Switch to two forward ranges, combine exceeding with
354 // lower resp upper, but not lower/lower, upper/upper
355 && next_level2(exceeding_box, exceeding, lower, level, min_elements,
356 visitor, expand_policy, overlaps_policy, box_policy)
357 && next_level2(exceeding_box, exceeding, upper, level, min_elements,
358 visitor, expand_policy, overlaps_policy, box_policy)) )
359 {
360 return false; // interrupt
361 }
362 }
363
364 // Recursively call operation both parts
365 return next_level(lower_box, lower, level, min_elements,
366 visitor, expand_policy, overlaps_policy, box_policy)
367 && next_level(upper_box, upper, level, min_elements,
368 visitor, expand_policy, overlaps_policy, box_policy);
369 }
370};
371
372template
373<
374 int Dimension,
375 typename Box
376>
377class partition_two_ranges
378{
379 template
380 <
381 typename IteratorVector1,
382 typename IteratorVector2,
383 typename VisitPolicy,
384 typename ExpandPolicy1,
385 typename OverlapsPolicy1,
386 typename ExpandPolicy2,
387 typename OverlapsPolicy2,
388 typename VisitBoxPolicy
389 >
390 static inline bool next_level(Box const& box,
391 IteratorVector1 const& input1,
392 IteratorVector2 const& input2,
393 std::size_t level, std::size_t min_elements,
394 VisitPolicy& visitor,
395 ExpandPolicy1 const& expand_policy1,
396 OverlapsPolicy1 const& overlaps_policy1,
397 ExpandPolicy2 const& expand_policy2,
398 OverlapsPolicy2 const& overlaps_policy2,
399 VisitBoxPolicy& box_policy)
400 {
401 return partition_two_ranges
402 <
403 1 - Dimension, Box
404 >::apply(box, input1, input2, level + 1, min_elements,
405 visitor, expand_policy1, overlaps_policy1,
406 expand_policy2, overlaps_policy2, box_policy);
407 }
408
409 template <typename IteratorVector, typename ExpandPolicy>
410 static inline Box get_new_box(IteratorVector const& input,
411 ExpandPolicy const& expand_policy)
412 {
413 Box box;
414 geometry::assign_inverse(box);
415 expand_with_elements(box, input, expand_policy);
416 return box;
417 }
418
419 template
420 <
421 typename IteratorVector1, typename IteratorVector2,
422 typename ExpandPolicy1, typename ExpandPolicy2
423 >
424 static inline Box get_new_box(IteratorVector1 const& input1,
425 IteratorVector2 const& input2,
426 ExpandPolicy1 const& expand_policy1,
427 ExpandPolicy2 const& expand_policy2)
428 {
429 Box box = get_new_box(input1, expand_policy1);
430 expand_with_elements(box, input2, expand_policy2);
431 return box;
432 }
433
434public :
435 template
436 <
437 typename IteratorVector1,
438 typename IteratorVector2,
439 typename VisitPolicy,
440 typename ExpandPolicy1,
441 typename OverlapsPolicy1,
442 typename ExpandPolicy2,
443 typename OverlapsPolicy2,
444 typename VisitBoxPolicy
445 >
446 static inline bool apply(Box const& box,
447 IteratorVector1 const& input1,
448 IteratorVector2 const& input2,
449 std::size_t level,
450 std::size_t min_elements,
451 VisitPolicy& visitor,
452 ExpandPolicy1 const& expand_policy1,
453 OverlapsPolicy1 const& overlaps_policy1,
454 ExpandPolicy2 const& expand_policy2,
455 OverlapsPolicy2 const& overlaps_policy2,
456 VisitBoxPolicy& box_policy)
457 {
458 box_policy.apply(box, level);
459
460 Box lower_box, upper_box;
461 divide_box<Dimension>(box, lower_box, upper_box);
462
463 IteratorVector1 lower1, upper1, exceeding1;
464 IteratorVector2 lower2, upper2, exceeding2;
465 divide_into_subsets(lower_box, upper_box,
466 input1, lower1, upper1, exceeding1,
467 overlaps_policy1);
468 divide_into_subsets(lower_box, upper_box,
469 input2, lower2, upper2, exceeding2,
470 overlaps_policy2);
471
472 if (! boost::empty(exceeding1))
473 {
474 // All exceeding from 1 with 2:
475
476 if (recurse_ok(exceeding1, exceeding2, min_elements, level))
477 {
478 Box exceeding_box = get_new_box(exceeding1, exceeding2,
479 expand_policy1, expand_policy2);
480 if (! next_level(exceeding_box, exceeding1, exceeding2, level,
481 min_elements, visitor, expand_policy1, overlaps_policy1,
482 expand_policy2, overlaps_policy2, box_policy))
483 {
484 return false; // interrupt
485 }
486 }
487 else
488 {
489 if (! handle_two(exceeding1, exceeding2, visitor))
490 {
491 return false; // interrupt
492 }
493 }
494
495 // All exceeding from 1 with lower and upper of 2:
496
497 // (Check sizes of all three forward ranges to avoid recurse into
498 // the same combinations again and again)
499 if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
500 {
501 Box exceeding_box = get_new_box(exceeding1, expand_policy1);
502 if (! (next_level(exceeding_box, exceeding1, lower2, level,
503 min_elements, visitor, expand_policy1, overlaps_policy1,
504 expand_policy2, overlaps_policy2, box_policy)
505 && next_level(exceeding_box, exceeding1, upper2, level,
506 min_elements, visitor, expand_policy1, overlaps_policy1,
507 expand_policy2, overlaps_policy2, box_policy)) )
508 {
509 return false; // interrupt
510 }
511 }
512 else
513 {
514 if (! (handle_two(exceeding1, lower2, visitor)
515 && handle_two(exceeding1, upper2, visitor)) )
516 {
517 return false; // interrupt
518 }
519 }
520 }
521
522 if (! boost::empty(exceeding2))
523 {
524 // All exceeding from 2 with lower and upper of 1:
525 if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
526 {
527 Box exceeding_box = get_new_box(exceeding2, expand_policy2);
528 if (! (next_level(exceeding_box, lower1, exceeding2, level,
529 min_elements, visitor, expand_policy1, overlaps_policy1,
530 expand_policy2, overlaps_policy2, box_policy)
531 && next_level(exceeding_box, upper1, exceeding2, level,
532 min_elements, visitor, expand_policy1, overlaps_policy1,
533 expand_policy2, overlaps_policy2, box_policy)) )
534 {
535 return false; // interrupt
536 }
537 }
538 else
539 {
540 if (! (handle_two(lower1, exceeding2, visitor)
541 && handle_two(upper1, exceeding2, visitor)) )
542 {
543 return false; // interrupt
544 }
545 }
546 }
547
548 if (recurse_ok(lower1, lower2, min_elements, level))
549 {
550 if (! next_level(lower_box, lower1, lower2, level,
551 min_elements, visitor, expand_policy1, overlaps_policy1,
552 expand_policy2, overlaps_policy2, box_policy) )
553 {
554 return false; // interrupt
555 }
556 }
557 else
558 {
559 if (! handle_two(lower1, lower2, visitor))
560 {
561 return false; // interrupt
562 }
563 }
564
565 if (recurse_ok(upper1, upper2, min_elements, level))
566 {
567 if (! next_level(upper_box, upper1, upper2, level,
568 min_elements, visitor, expand_policy1, overlaps_policy1,
569 expand_policy2, overlaps_policy2, box_policy) )
570 {
571 return false; // interrupt
572 }
573 }
574 else
575 {
576 if (! handle_two(upper1, upper2, visitor))
577 {
578 return false; // interrupt
579 }
580 }
581
582 return true;
583 }
584};
585
586struct visit_no_policy
587{
588 template <typename Box>
589 static inline void apply(Box const&, std::size_t )
590 {}
591};
592
593struct include_all_policy
594{
595 template <typename Item>
596 static inline bool apply(Item const&)
597 {
598 return true;
599 }
600};
601
602
603}} // namespace detail::partition
604
605template
606<
607 typename Box,
608 typename IncludePolicy1 = detail::partition::include_all_policy,
609 typename IncludePolicy2 = detail::partition::include_all_policy
610>
611class partition
612{
613 static const std::size_t default_min_elements = 16;
614
615 template
616 <
617 typename IncludePolicy,
618 typename ForwardRange,
619 typename IteratorVector,
620 typename ExpandPolicy
621 >
622 static inline void expand_to_range(ForwardRange const& forward_range,
623 Box& total,
624 IteratorVector& iterator_vector,
625 ExpandPolicy const& expand_policy)
626 {
627 for(typename boost::range_iterator<ForwardRange const>::type
628 it = boost::begin(forward_range);
629 it != boost::end(forward_range);
630 ++it)
631 {
632 if (IncludePolicy::apply(*it))
633 {
634 expand_policy.apply(total, *it);
635 iterator_vector.push_back(it);
636 }
637 }
638 }
639
640public:
641 template
642 <
643 typename ForwardRange,
644 typename VisitPolicy,
645 typename ExpandPolicy,
646 typename OverlapsPolicy
647 >
648 static inline bool apply(ForwardRange const& forward_range,
649 VisitPolicy& visitor,
650 ExpandPolicy const& expand_policy,
651 OverlapsPolicy const& overlaps_policy)
652 {
653 return apply(forward_range, visitor, expand_policy, overlaps_policy,
654 default_min_elements, detail::partition::visit_no_policy());
655 }
656
657 template
658 <
659 typename ForwardRange,
660 typename VisitPolicy,
661 typename ExpandPolicy,
662 typename OverlapsPolicy
663 >
664 static inline bool apply(ForwardRange const& forward_range,
665 VisitPolicy& visitor,
666 ExpandPolicy const& expand_policy,
667 OverlapsPolicy const& overlaps_policy,
668 std::size_t min_elements)
669 {
670 return apply(forward_range, visitor, expand_policy, overlaps_policy,
671 min_elements, detail::partition::visit_no_policy());
672 }
673
674 template
675 <
676 typename ForwardRange,
677 typename VisitPolicy,
678 typename ExpandPolicy,
679 typename OverlapsPolicy,
680 typename VisitBoxPolicy
681 >
682 static inline bool apply(ForwardRange const& forward_range,
683 VisitPolicy& visitor,
684 ExpandPolicy const& expand_policy,
685 OverlapsPolicy const& overlaps_policy,
686 std::size_t min_elements,
687 VisitBoxPolicy box_visitor)
688 {
689 typedef typename boost::range_iterator
690 <
691 ForwardRange const
692 >::type iterator_type;
693
694 if (std::size_t(boost::size(forward_range)) > min_elements)
695 {
696 std::vector<iterator_type> iterator_vector;
697 Box total;
698 assign_inverse(total);
699 expand_to_range<IncludePolicy1>(forward_range, total,
700 iterator_vector, expand_policy);
701
702 return detail::partition::partition_one_range
703 <
704 0, Box
705 >::apply(total, iterator_vector, 0, min_elements,
706 visitor, expand_policy, overlaps_policy, box_visitor);
707 }
708 else
709 {
710 for(iterator_type it1 = boost::begin(forward_range);
711 it1 != boost::end(forward_range);
712 ++it1)
713 {
714 iterator_type it2 = it1;
715 for(++it2; it2 != boost::end(forward_range); ++it2)
716 {
717 if (! visitor.apply(*it1, *it2))
718 {
719 return false; // interrupt
720 }
721 }
722 }
723 }
724
725 return true;
726 }
727
728 template
729 <
730 typename ForwardRange1,
731 typename ForwardRange2,
732 typename VisitPolicy,
733 typename ExpandPolicy1,
734 typename OverlapsPolicy1
735 >
736 static inline bool apply(ForwardRange1 const& forward_range1,
737 ForwardRange2 const& forward_range2,
738 VisitPolicy& visitor,
739 ExpandPolicy1 const& expand_policy1,
740 OverlapsPolicy1 const& overlaps_policy1)
741 {
742 return apply(forward_range1, forward_range2, visitor,
743 expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1,
744 default_min_elements, detail::partition::visit_no_policy());
745 }
746
747 template
748 <
749 typename ForwardRange1,
750 typename ForwardRange2,
751 typename VisitPolicy,
752 typename ExpandPolicy1,
753 typename OverlapsPolicy1,
754 typename ExpandPolicy2,
755 typename OverlapsPolicy2
756 >
757 static inline bool apply(ForwardRange1 const& forward_range1,
758 ForwardRange2 const& forward_range2,
759 VisitPolicy& visitor,
760 ExpandPolicy1 const& expand_policy1,
761 OverlapsPolicy1 const& overlaps_policy1,
762 ExpandPolicy2 const& expand_policy2,
763 OverlapsPolicy2 const& overlaps_policy2)
764 {
765 return apply(forward_range1, forward_range2, visitor,
766 expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
767 default_min_elements, detail::partition::visit_no_policy());
768 }
769
770 template
771 <
772 typename ForwardRange1,
773 typename ForwardRange2,
774 typename VisitPolicy,
775 typename ExpandPolicy1,
776 typename OverlapsPolicy1,
777 typename ExpandPolicy2,
778 typename OverlapsPolicy2
779 >
780 static inline bool apply(ForwardRange1 const& forward_range1,
781 ForwardRange2 const& forward_range2,
782 VisitPolicy& visitor,
783 ExpandPolicy1 const& expand_policy1,
784 OverlapsPolicy1 const& overlaps_policy1,
785 ExpandPolicy2 const& expand_policy2,
786 OverlapsPolicy2 const& overlaps_policy2,
787 std::size_t min_elements)
788 {
789 return apply(forward_range1, forward_range2, visitor,
11fdf7f2 790 expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
b32b8144
FG		 791 min_elements, detail::partition::visit_no_policy());
792 }
793
794 template
795 <
796 typename ForwardRange1,
797 typename ForwardRange2,
798 typename VisitPolicy,
799 typename ExpandPolicy1,
800 typename OverlapsPolicy1,
801 typename ExpandPolicy2,
802 typename OverlapsPolicy2,
803 typename VisitBoxPolicy
804 >
805 static inline bool apply(ForwardRange1 const& forward_range1,
806 ForwardRange2 const& forward_range2,
807 VisitPolicy& visitor,
808 ExpandPolicy1 const& expand_policy1,
809 OverlapsPolicy1 const& overlaps_policy1,
810 ExpandPolicy2 const& expand_policy2,
811 OverlapsPolicy2 const& overlaps_policy2,
812 std::size_t min_elements,
813 VisitBoxPolicy box_visitor)
814 {
815 typedef typename boost::range_iterator
816 <
817 ForwardRange1 const
818 >::type iterator_type1;
819
820 typedef typename boost::range_iterator
821 <
822 ForwardRange2 const
823 >::type iterator_type2;
824
825 if (std::size_t(boost::size(forward_range1)) > min_elements
826 && std::size_t(boost::size(forward_range2)) > min_elements)
827 {
828 std::vector<iterator_type1> iterator_vector1;
829 std::vector<iterator_type2> iterator_vector2;
830 Box total;
831 assign_inverse(total);
832 expand_to_range<IncludePolicy1>(forward_range1, total,
833 iterator_vector1, expand_policy1);
834 expand_to_range<IncludePolicy2>(forward_range2, total,
835 iterator_vector2, expand_policy2);
836
837 return detail::partition::partition_two_ranges
838 <
839 0, Box
840 >::apply(total, iterator_vector1, iterator_vector2,
841 0, min_elements, visitor, expand_policy1,
842 overlaps_policy1, expand_policy2, overlaps_policy2,
843 box_visitor);
844 }
845 else
846 {
847 for(iterator_type1 it1 = boost::begin(forward_range1);
848 it1 != boost::end(forward_range1);
849 ++it1)
850 {
851 for(iterator_type2 it2 = boost::begin(forward_range2);
852 it2 != boost::end(forward_range2);
853 ++it2)
854 {
855 if (! visitor.apply(*it1, *it2))
856 {
857 return false; // interrupt
858 }
859 }
860 }
861 }
862
863 return true;
864 }
865};
866
867
868}} // namespace boost::geometry
869
870#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
Ceph