Debian Codegraph @

libcextract/IntervalTree.hh

raw
1 /******************************************************************************
2 **
3 ** Copyright (C) 2020 Ivan Pinezhaninov <[email protected]>
4 **
5 ** This file is part of the IntervalTree - Red-Black balanced interval tree
6 ** which can be found at https://github.com/IvanPinezhaninov/IntervalTree/.
7 **
8 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
9 ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
10 ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
11 ** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
12 ** DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
13 ** OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
14 ** THE USE OR OTHER DEALINGS IN THE SOFTWARE.
15 **
16 ******************************************************************************/
17
18 /* Giuliano Belinassi: Implementation taken from
19 https://github.com/IvanPinezhaninov/IntervalTree/blob/master/include/intervaltree.hpp.
20 MIT and Apache license are compatible with each other. */
21
22 #ifndef INTERVALTREE_H
23 #define INTERVALTREE_H
24
25 #include <algorithm>
26 #include <cassert>
27 #include <cstddef>
28 #include <ostream>
29 #include <tuple>
30 #include <utility>
31 #include <vector>
32
33 #define CLANG_SOURCELOC
34 #ifdef CLANG_SOURCELOC
35 /* Expand this to use clang's SourceLocation. */
36 #include "clang/Basic/SourceLocation.h"
37 #endif
38
39 namespace Intervals {
40
41 constexpr static const double VECTOR_RESERVE_RATE = 0.25;
42
43
44 template <typename IntervalType, typename ValueType = size_t>
45 struct Interval
46 {
47 using interval_type = typename std::decay<IntervalType>::type;
48 using value_type = typename std::decay<ValueType>::type;
49
50
51 template <typename I, typename V = ValueType,
52 typename = typename std::enable_if<std::is_scalar<typename std::decay<I>::type>::value>::type,
53 typename = typename std::enable_if<std::is_scalar<typename std::decay<V>::type>::value>::type>
54 Interval(I a, I b, V val = {}) :
55 low(std::min(a, b)),
56 high(std::max(a, b)),
57 value(val)
58 {
59 }
60
61
62 template <typename I, typename V = ValueType,
63 typename = typename std::enable_if<!std::is_scalar<typename std::decay<I>::type>::value>::type,
64 typename = typename std::enable_if<!std::is_scalar<typename std::decay<V>::type>::value>::type>
65 Interval(I &&a, I &&b, V &&val = {}) :
66 low(std::forward<I>(a < b ? a : b)),
67 high(std::forward<I>(b < a ? a : b)),
68 value(std::forward<V>(val))
69 {
70 }
71
72
73 template <typename I, typename V = ValueType,
74 typename = typename std::enable_if<!std::is_scalar<typename std::decay<I>::type>::value>::type,
75 typename = typename std::enable_if<std::is_scalar<typename std::decay<V>::type>::value>::type>
76 Interval(I &&a, I &&b, V val = {}) :
77 low(std::forward<I>(a < b ? a : b)),
78 high(std::forward<I>(b < a ? a : b)),
79 value(val)
80 {
81 }
82
83
84 template <typename I, typename V = ValueType,
85 typename = typename std::enable_if<std::is_scalar<typename std::decay<I>::type>::value>::type,
86 typename = typename std::enable_if<!std::is_scalar<typename std::decay<V>::type>::value>::type>
87 Interval(I a, I b, V &&val = {}) :
88 low(std::min(a, b)),
89 high(std::max(a, b)),
90 value(std::forward<V>(val))
91 {
92 }
93
94 #ifdef CLANG_SOURCELOC
95 template <typename V = ValueType>
96 Interval(const clang::SourceRange &interval, V val = {})
97 : low(std::min(interval.getBegin(), interval.getEnd())),
98 high(std::max(interval.getEnd(), interval.getEnd())),
99 value(std::forward<V>(val))
100 {
101 }
102 #endif
103
104 template <typename V = ValueType,
105 typename = typename std::enable_if<std::is_scalar<typename std::decay<V>::type>::value>::type>
106 explicit Interval(const std::tuple<IntervalType, IntervalType> &interval, V val = {}) :
107 Interval(std::get<0>(interval), std::get<1>(interval), val)
108 {
109 }
110
111
112 template <typename V = ValueType,
113 typename = typename std::enable_if<!std::is_scalar<typename std::decay<V>::type>::value>::type>
114 explicit Interval(const std::tuple<IntervalType, IntervalType> &interval, V &&val = {}) :
115 Interval(std::get<0>(interval), std::get<1>(interval), std::forward<V>(val))
116 {
117 }
118
119 Interval(const Interval &) = default;
120 Interval(Interval &&) = default;
121 Interval &operator=(const Interval &) = default;
122 Interval &operator=(Interval &&) = default;
123 virtual ~Interval() = default;
124
125
126 bool operator==(const Interval &other) const
127 {
128 return !(low < other.low || other.low < low
129 || high < other.high || other.high < high
130 || value < other.value || other.value < value);
131 }
132
133
134 bool operator<(const Interval &other) const
135 {
136 return (low < other.low || high < other.high);
137 }
138
139
140 interval_type low;
141 interval_type high;
142 value_type value;
143 };
144
145
146 template <typename IntervalType, typename ValueType = size_t>
147 class IntervalTree
148 {
149 public:
150 using Interval = Intervals::Interval<IntervalType, ValueType>;
151 using Intervals = std::vector<Interval>;
152 using size_type = std::size_t;
153
154
155 IntervalTree() :
156 m_nill(new Node()),
157 m_root(m_nill)
158 {
159 }
160
161
162 template <typename Container>
163 explicit IntervalTree(const Container &intervals) :
164 IntervalTree()
165 {
166 for (const auto &interval : intervals) {
167 insert(interval);
168 }
169 }
170
171
172 template <typename ForwardIterator>
173 IntervalTree(ForwardIterator begin, const ForwardIterator &end) :
174 IntervalTree()
175 {
176 while (begin != end) {
177 insert(*begin);
178 ++begin;
179 }
180 }
181
182
183 virtual ~IntervalTree()
184 {
185 if (nullptr != m_root) {
186 destroySubtree(m_root);
187 }
188
189 delete m_nill;
190 }
191
192
193 IntervalTree(const IntervalTree &other) :
194 m_nill(new Node()),
195 m_root(copySubtree(other.m_root, other.m_nill, m_nill)),
196 m_size(other.m_size)
197 {
198 }
199
200
201 IntervalTree(IntervalTree &&other) noexcept :
202 m_nill(other.m_nill),
203 m_root(other.m_root),
204 m_size(other.m_size)
205 {
206 other.m_nill = nullptr;
207 other.m_root = nullptr;
208 }
209
210
211 IntervalTree &operator=(const IntervalTree &other)
212 {
213 if (this != &other) {
214 IntervalTree(other).swap(*this);
215 }
216
217 return *this;
218 }
219
220
221 IntervalTree &operator=(IntervalTree &&other) noexcept
222 {
223 other.swap(*this);
224 return *this;
225 }
226
227
228 void swap(IntervalTree &other) noexcept
229 {
230 std::swap(m_nill, other.m_nill);
231 std::swap(m_root, other.m_root);
232 std::swap(m_size, other.m_size);
233 }
234
235
236 bool insert(Interval interval)
237 {
238 assert(nullptr != m_root && nullptr != m_nill);
239
240 if (m_root == m_nill) {
241 // Tree is empty
242 assert(0 == m_size);
243 m_root = new Node(std::move(interval), Color::Black, m_nill);
244 m_size = 1;
245 return true;
246 }
247
248 Node *node = findNode(m_root, interval);
249 assert(node != m_nill);
250
251 if (interval.low < node->intervals.front().low) {
252 createChildNode(node, std::move(interval), Position::Left);
253 return true;
254 }
255
256 if (node->intervals.front().low < interval.low) {
257 createChildNode(node, std::move(interval), Position::Right);
258 return true;
259 }
260
261 if (!isNodeHasInterval(node, interval)) {
262 auto it = std::lower_bound(node->intervals.begin(), node->intervals.end(), interval, HighComparator());
263
264 if (node->high < interval.high) {
265 node->high = interval.high;
266 }
267
268 if (node->highest < node->high) {
269 node->highest = node->high;
270 insertionFixNodeLimits(node);
271 }
272
273 node->intervals.emplace(it, std::move(interval));
274 ++m_size;
275
276 return true;
277 }
278
279 // Value already exists
280 return false;
281 }
282
283
284 bool remove(const Interval &interval)
285 {
286 assert(nullptr != m_root && nullptr != m_nill);
287
288 if (m_root == m_nill) {
289 // Tree is empty
290 assert(0 == m_size);
291 return false;
292 }
293
294 auto node = findNode(m_root, interval);
295 assert(node != m_nill);
296
297 auto it = std::find(node->intervals.begin(), node->intervals.end(), interval);
298 if (it != node->intervals.cend()) {
299 node->intervals.erase(it);
300 if (isNodeAboutToBeDestroyed(node)) {
301 auto child = m_nill;
302 if (node->right == m_nill) {
303 child = node->left;
304 } else if (node->left == m_nill) {
305 child = node->right;
306 } else {
307 auto nextValueNode = node->right;
308 while (nextValueNode->left != m_nill) {
309 nextValueNode = nextValueNode->left;
310 }
311 node->intervals = std::move(nextValueNode->intervals);
312 node->high = std::move(nextValueNode->high);
313 removeFixNodeLimits(node);
314 node = nextValueNode;
315 child = nextValueNode->right;
316 }
317
318 if (child == m_nill && node->parent == m_nill) {
319 // Node is root without children
320 swapRelations(node, child);
321 destroyNode(node);
322 return true;
323 }
324
325 if (Color::Red == node->color || Color::Red == child->color) {
326 swapRelations(node, child);
327 if (Color::Red == child->color) {
328 child->color = Color::Black;
329 }
330 } else {
331 assert(Color::Black == node->color);
332
333 if (child == m_nill) {
334 child = node;
335 } else {
336 swapRelations(node, child);
337 }
338
339 removeFix(child);
340
341 if (node->parent != m_nill) {
342 setChildNode(node->parent, m_nill, nodePosition(node));
343 }
344 }
345
346 if (node->parent != m_nill) {
347 removeFixNodeLimits(node->parent, 1);
348 }
349 destroyNode(node);
350 } else {
351 if (isEqual(interval.high, node->high)) {
352 node->high = findHighest(node->intervals);
353 }
354
355 if (isEqual(interval.high, node->highest)) {
356 removeFixNodeLimits(node);
357 }
358
359 --m_size;
360 }
361
362 return true;
363 }
364
365 // Value not found
366 return false;
367 }
368
369
370 bool contains(const Interval &interval) const
371 {
372 assert(nullptr != m_root && nullptr != m_nill);
373
374 if (m_root == m_nill) {
375 // Tree is empty
376 assert(0 == m_size);
377 return false;
378 }
379
380 auto node = findNode(m_root, interval);
381 assert(node != m_nill);
382
383 return isNodeHasInterval(node, interval);
384 }
385
386
387 Intervals intervals() const
388 {
389 Intervals out;
390 out.reserve(m_size);
391
392 if (m_root != m_nill) {
393 subtreeIntervals(m_root, out);
394 }
395
396 return out;
397 }
398
399
400 void findOverlappingIntervals(const Interval &interval, Intervals &out, bool boundary = true) const
401 {
402 if (!out.empty()) {
403 out.clear();
404 }
405
406 if (m_root != m_nill) {
407 subtreeOverlappingIntervals(m_root, interval, boundary, Appender{out});
408 }
409
410 out.shrink_to_fit();
411 }
412
413
414 Intervals findOverlappingIntervals(const Interval &interval, bool boundary = true) const
415 {
416 Intervals out;
417 out.reserve(size_t(m_size * VECTOR_RESERVE_RATE));
418 findOverlappingIntervals(interval, out, boundary);
419 return out;
420 }
421
422
423 void findInnerIntervals(const Interval &interval, Intervals &out, bool boundary = true) const
424 {
425 if (!out.empty()) {
426 out.clear();
427 }
428
429 if (m_root != m_nill) {
430 subtreeInnerIntervals(m_root, interval, boundary, Appender{out});
431 }
432
433 out.shrink_to_fit();
434 }
435
436
437 Intervals findInnerIntervals(const Interval &interval, bool boundary = true) const
438 {
439 Intervals out;
440 out.reserve(size_t(m_size * VECTOR_RESERVE_RATE));
441 findInnerIntervals(interval, out, boundary);
442 return out;
443 }
444
445
446 void findOuterIntervals(const Interval &interval, Intervals &out, bool boundary = true) const
447 {
448 if (!out.empty()) {
449 out.clear();
450 }
451
452 if (m_root != m_nill) {
453 subtreeOuterIntervals(m_root, interval, boundary, Appender{out});
454 }
455
456 out.shrink_to_fit();
457 }
458
459
460 Intervals findOuterIntervals(const Interval &interval, bool boundary = true) const
461 {
462 Intervals out;
463 out.reserve(size_t(m_size * VECTOR_RESERVE_RATE));
464 findOuterIntervals(interval, out, boundary);
465 return out;
466 }
467
468
469 void findIntervalsContainPoint(const IntervalType &point, Intervals &out, bool boundary = true) const
470 {
471 if (!out.empty()) {
472 out.clear();
473 }
474
475 if (m_root != m_nill) {
476 subtreeIntervalsContainPoint(m_root, point, boundary, Appender{out});
477 }
478
479 out.shrink_to_fit();
480 }
481
482
483 Intervals findIntervalsContainPoint(const IntervalType &point, bool boundary = true) const
484 {
485 Intervals out;
486 out.reserve(size_t(m_size * VECTOR_RESERVE_RATE));
487 findIntervalsContainPoint(point, out, boundary);
488 return out;
489 }
490
491
492 size_type countOverlappingIntervals(const Interval &interval, bool boundary = true) const
493 {
494 size_type count = 0;
495
496 if (m_root != m_nill) {
497 subtreeOverlappingIntervals(m_root, interval, boundary, Counter{count});
498 }
499
500 return count;
501 }
502
503
504 size_type countInnerIntervals(const Interval &interval, bool boundary = true) const
505 {
506 size_type count = 0;
507
508 if (m_root != m_nill) {
509 subtreeInnerIntervals(m_root, interval, boundary, Counter{count});
510 }
511
512 return count;
513 }
514
515
516 size_type countOuterIntervals(const Interval &interval, bool boundary = true) const
517 {
518 size_type count = 0;
519
520 if (m_root != m_nill) {
521 subtreeOuterIntervals(m_root, interval, boundary, Counter{count});
522 }
523
524 return count;
525 }
526
527
528 size_type countIntervalsContainPoint(const IntervalType &point, bool boundary = true) const
529 {
530 size_type count = 0;
531
532 if (m_root != m_nill) {
533 subtreeIntervalsContainPoint(m_root, point, boundary, Counter{count});
534 }
535
536 return count;
537 }
538
539
540 bool isEmpty() const
541 {
542 return (0 == m_size);
543 }
544
545
546 size_type size() const
547 {
548 return m_size;
549 }
550
551
552 void clear()
553 {
554 assert(nullptr != m_root && nullptr != m_nill);
555
556 destroySubtree(m_root);
557 m_root = m_nill;
558 m_size = 0;
559 }
560
561
562 private:
563 enum class Color : char {
564 Black,
565 Red
566 };
567
568
569 enum class Position : char {
570 Left,
571 Right
572 };
573
574
575 struct Appender final
576 {
577 template <typename Interval>
578 void operator()(Interval &&interval)
579 {
580 intervals.emplace_back(std::forward<Interval>(interval));
581 }
582
583 Intervals &intervals;
584 };
585
586
587 struct Counter final
588 {
589 template <typename Interval>
590 void operator()(Interval &&)
591 {
592 ++count;
593 }
594
595 size_type &count;
596 };
597
598
599 struct HighComparator final
600 {
601 template <typename T>
602 bool operator()(const T &lhs, const T &rhs) const
603 {
604 return (lhs.high < rhs.high);
605 }
606 };
607
608
609 struct Node
610 {
611 using interval_type = typename Interval::interval_type;
612
613 Node() = default;
614
615 Node(Interval interval, Color col, Node *nill) :
616 color(col),
617 parent(nill),
618 left(nill),
619 right(nill),
620 high(interval.high),
621 lowest(interval.low),
622 highest(interval.high)
623 {
624 intervals.emplace_back(std::move(interval));
625 }
626
627 Color color = Color::Black;
628 Node *parent = nullptr;
629 Node *left = nullptr;
630 Node *right = nullptr;
631
632 interval_type high{};
633 interval_type lowest{};
634 interval_type highest{};
635 Intervals intervals;
636 };
637
638
639 Node *copySubtree(Node *otherNode, Node *otherNill, Node *parent) const
640 {
641 assert(nullptr != otherNode && nullptr != otherNill && nullptr != parent);
642
643 if (otherNode == otherNill) {
644 return m_nill;
645 }
646
647 auto node = new Node();
648 node->intervals = otherNode->intervals;
649 node->high = otherNode->high;
650 node->lowest = otherNode->lowest;
651 node->highest = otherNode->highest;
652 node->color = otherNode->color;
653 node->parent = parent;
654 node->left = copySubtree(otherNode->left, otherNill, node);
655 node->right = copySubtree(otherNode->right, otherNill, node);
656
657 return node;
658 }
659
660
661 void destroySubtree(Node *node) const
662 {
663 assert(nullptr != node);
664
665 if (node == m_nill) {
666 return;
667 }
668
669 destroySubtree(node->left);
670 destroySubtree(node->right);
671
672 delete node;
673 }
674
675
676 Node *findNode(Node *node, const Interval &interval) const
677 {
678 assert(nullptr != node);
679 assert(node != m_nill);
680
681 auto child = m_nill;
682 if (interval.low < node->intervals.front().low) {
683 child = childNode(node, Position::Left);
684 } else if (node->intervals.front().low < interval.low) {
685 child = childNode(node, Position::Right);
686 } else {
687 return node;
688 }
689
690 return (child == m_nill) ? node : findNode(child, interval);
691 }
692
693
694 Node *siblingNode(Node *node) const
695 {
696 assert(nullptr != node);
697
698 return (Position::Left == nodePosition(node))
699 ? childNode(node->parent, Position::Right)
700 : childNode(node->parent, Position::Left);
701 }
702
703
704 Node *childNode(Node *node, Position position) const
705 {
706 assert(nullptr != node);
707
708 switch (position) {
709 case Position::Left:
710 return node->left;
711 case Position::Right:
712 return node->right;
713 default:
714 assert(false);
715 return nullptr;
716 }
717 }
718
719
720 void setChildNode(Node *node, Node *child, Position position) const
721 {
722 assert(nullptr != node && nullptr != child);
723 assert(node != m_nill);
724
725 switch (position) {
726 case Position::Left:
727 node->left = child;
728 break;
729 case Position::Right:
730 node->right = child;
731 break;
732 default:
733 assert(false);
734 break;
735 }
736
737 if (child != m_nill) {
738 child->parent = node;
739 }
740 }
741
742
743 Position nodePosition(Node *node) const
744 {
745 assert(nullptr != node && nullptr != node->parent);
746
747 return (node->parent->left == node) ? Position::Left : Position::Right;
748 }
749
750
751 void createChildNode(Node *parent, Interval interval, Position position)
752 {
753 assert(nullptr != parent);
754 assert(childNode(parent, position) == m_nill);
755
756 auto child = new Node(std::move(interval), Color::Red, m_nill);
757 setChildNode(parent, child, position);
758 insertionFixNodeLimits(child);
759 insertionFix(child);
760 ++m_size;
761 }
762
763
764 void destroyNode(Node *node)
765 {
766 --m_size;
767 delete node;
768 }
769
770
771 void updateNodeLimits(Node *node) const
772 {
773 assert(nullptr != node);
774
775 auto left = isNodeAboutToBeDestroyed(node->left) ? m_nill : node->left;
776 auto right = isNodeAboutToBeDestroyed(node->right) ? m_nill : node->right;
777
778 const auto &lowest = (left != m_nill) ? left->lowest : node->intervals.front().low;
779
780 if (isNotEqual(node->lowest, lowest)) {
781 node->lowest = lowest;
782 }
783
784 const auto &highest = std::max({ left->highest, right->highest, node->high });
785
786 if (isNotEqual(node->highest, highest)) {
787 node->highest = highest;
788 }
789 }
790
791
792 bool isNodeAboutToBeDestroyed(Node *node) const
793 {
794 assert(nullptr != node);
795
796 return (node != m_nill && node->intervals.empty());
797 }
798
799
800 void subtreeIntervals(Node *node, Intervals &out) const
801 {
802 assert(nullptr != node);
803
804 if (node == m_nill) {
805 return;
806 }
807
808 subtreeIntervals(node->left, out);
809
810 out.insert(out.end(), node->intervals.begin(), node->intervals.end());
811
812 subtreeIntervals(node->right, out);
813 }
814
815
816 template <typename Callback>
817 void subtreeOverlappingIntervals(Node *node, const Interval &interval, bool boundary, Callback &&callback) const
818 {
819 assert(nullptr != node);
820
821 if (node == m_nill) {
822 return;
823 }
824
825 if (node->left != m_nill
826 && (boundary ? !(node->left->highest < interval.low) : interval.low < node->left->highest)) {
827 subtreeOverlappingIntervals(node->left, interval, boundary, callback);
828 }
829
830 if (boundary ? !(interval.high < node->intervals.front().low) : node->intervals.front().low < interval.high) {
831 for (auto it = node->intervals.rbegin(); it != node->intervals.rend(); ++it) {
832 if (boundary ? !(it->high < interval.low) : interval.low < it->high) {
833 callback(*it);
834 } else {
835 break;
836 }
837 }
838
839 subtreeOverlappingIntervals(node->right, interval, boundary, std::forward<Callback>(callback));
840 }
841 }
842
843
844 template <typename Callback>
845 void subtreeInnerIntervals(Node *node, const Interval &interval, bool boundary, Callback &&callback) const
846 {
847 assert(nullptr != node);
848
849 if (node == m_nill) {
850 return;
851 }
852
853 if (boundary ? !(node->intervals.front().low < interval.low) : interval.low < node->intervals.front().low) {
854 subtreeInnerIntervals(node->left, interval, boundary, callback);
855 for (auto it = node->intervals.begin(); it != node->intervals.end(); ++it) {
856 if (boundary ? !(interval.high < it->high) : it->high < interval.high) {
857 callback(*it);
858 } else {
859 break;
860 }
861 }
862 }
863
864 if (node->right != m_nill
865 && (boundary ? !(interval.high < node->right->lowest) : node->right->lowest < interval.high)) {
866 subtreeInnerIntervals(node->right, interval, boundary, std::forward<Callback>(callback));
867 }
868 }
869
870
871 template <typename Callback>
872 void subtreeOuterIntervals(Node *node, const Interval &interval, bool boundary, Callback &&callback) const
873 {
874 assert(nullptr != node);
875
876 if (node == m_nill) {
877 return;
878 }
879
880 if (node->left != m_nill
881 && (boundary ? !(node->left->highest < interval.high) : interval.high < node->left->highest)) {
882 subtreeOuterIntervals(node->left, interval, boundary, callback);
883 }
884
885 if (boundary ? !(interval.low < node->intervals.front().low) : node->intervals.front().low < interval.low) {
886 for (auto it = node->intervals.rbegin(); it != node->intervals.rend(); ++it) {
887 if (boundary ? !(it->high < interval.high) : interval.high < it->high) {
888 callback(*it);
889 } else {
890 break;
891 }
892 }
893
894 subtreeOuterIntervals(node->right, interval, boundary, std::forward<Callback>(callback));
895 }
896 }
897
898
899 template <typename Callback>
900 void subtreeIntervalsContainPoint(Node *node, const IntervalType &point, bool boundary, Callback &&callback) const
901 {
902 assert(nullptr != node);
903
904 if (node == m_nill) {
905 return;
906 }
907
908 if (node->left != m_nill
909 && (boundary ? !(node->left->highest < point) : point < node->left->highest)) {
910 subtreeIntervalsContainPoint(node->left, point, boundary, callback);
911 }
912
913 if (boundary ? !(point < node->intervals.front().low) : node->intervals.front().low < point) {
914 for (auto it = node->intervals.rbegin(); it != node->intervals.rend(); ++it) {
915 if (boundary ? !(it->high < point) : point < it->high) {
916 callback(*it);
917 } else {
918 break;
919 }
920 }
921
922 subtreeIntervalsContainPoint(node->right, point, boundary, std::forward<Callback>(callback));
923 }
924 }
925
926
927 bool isNodeHasInterval(Node *node, const Interval &interval) const
928 {
929 assert(nullptr != node);
930
931 return (node->intervals.cend() != std::find(node->intervals.cbegin(), node->intervals.cend(), interval));
932 }
933
934
935 IntervalType findHighest(const Intervals &intervals) const
936 {
937 assert(!intervals.empty());
938
939 auto it = std::max_element(intervals.cbegin(), intervals.cend(), HighComparator());
940
941 assert(it != intervals.cend());
942
943 return it->high;
944 }
945
946
947 bool isNotEqual(const IntervalType &lhs, const IntervalType &rhs) const
948 {
949 return (lhs < rhs || rhs < lhs);
950 }
951
952
953 bool isEqual(const IntervalType &lhs, const IntervalType &rhs) const
954 {
955 return !isNotEqual(lhs, rhs);
956 }
957
958
959 void swapRelations(Node *node, Node *child)
960 {
961 assert(nullptr != node && nullptr != child);
962
963 if (node->parent == m_nill) {
964 if (child != m_nill) {
965 child->parent = m_nill;
966 }
967 m_root = child;
968 } else {
969 setChildNode(node->parent, child, nodePosition(node));
970 }
971 }
972
973
974 void rotateCommon(Node *node, Node *child) const
975 {
976 assert(nullptr != node && nullptr != child);
977 assert(node != m_nill && child != m_nill);
978
979 std::swap(node->color, child->color);
980
981 updateNodeLimits(node);
982
983 if (child->highest < node->highest) {
984 child->highest = node->highest;
985 }
986
987 if (node->lowest < child->lowest) {
988 child->lowest = node->lowest;
989 }
990 }
991
992
993 Node *rotateLeft(Node *node)
994 {
995 assert(nullptr != node && nullptr != node->right);
996
997 auto child = node->right;
998 swapRelations(node, child);
999 setChildNode(node, child->left, Position::Right);
1000 setChildNode(child, node, Position::Left);
1001 rotateCommon(node, child);
1002
1003 return child;
1004 }
1005
1006
1007 Node *rotateRight(Node *node)
1008 {
1009 assert(nullptr != node && nullptr != node->left);
1010
1011 auto child = node->left;
1012 swapRelations(node, child);
1013 setChildNode(node, child->right, Position::Left);
1014 setChildNode(child, node, Position::Right);
1015 rotateCommon(node, child);
1016
1017 return child;
1018 }
1019
1020
1021 Node *rotate(Node *node)
1022 {
1023 assert(nullptr != node);
1024
1025 switch (nodePosition(node)) {
1026 case Position::Left:
1027 return rotateRight(node->parent);
1028 case Position::Right:
1029 return rotateLeft(node->parent);
1030 default:
1031 assert(false);
1032 return nullptr;
1033 }
1034 }
1035
1036
1037 void insertionFixNodeLimits(Node *node)
1038 {
1039 assert(nullptr != node && nullptr != node->parent);
1040
1041 while (node->parent != m_nill) {
1042 auto finish = true;
1043
1044 if (node->parent->highest < node->highest) {
1045 node->parent->highest = node->highest;
1046 finish = false;
1047 }
1048
1049 if (node->lowest < node->parent->lowest) {
1050 node->parent->lowest = node->lowest;
1051 finish = false;
1052 }
1053
1054 if (finish) {
1055 break;
1056 }
1057
1058 node = node->parent;
1059 }
1060 }
1061
1062
1063 void removeFixNodeLimits(Node *node, size_type minRange = 0)
1064 {
1065 assert(nullptr != node && nullptr != node->parent);
1066
1067 size_type range = 0;
1068 while (node != m_nill) {
1069 bool finish = (minRange < range);
1070
1071 updateNodeLimits(node);
1072
1073 if (isNotEqual(node->highest, node->parent->highest)) {
1074 finish = false;
1075 }
1076
1077 if (isNotEqual(node->lowest, node->parent->lowest)) {
1078 finish = false;
1079 }
1080
1081 if (finish) {
1082 break;
1083 }
1084
1085 node = node->parent;
1086 ++range;
1087 }
1088 }
1089
1090
1091 void insertionFix(Node *node)
1092 {
1093 assert(nullptr != node && nullptr != node->parent);
1094
1095 while (Color::Red == node->color && Color::Red == node->parent->color) {
1096 auto parent = node->parent;
1097 auto uncle = siblingNode(parent);
1098 switch (uncle->color) {
1099 case Color::Red:
1100 uncle->color = Color::Black;
1101 parent->color = Color::Black;
1102 parent->parent->color = Color::Red;
1103 node = parent->parent;
1104 break;
1105 case Color::Black:
1106 if (nodePosition(node) != nodePosition(parent)) {
1107 parent = rotate(node);
1108 }
1109 node = rotate(parent);
1110 break;
1111 default:
1112 assert(false);
1113 break;
1114 }
1115 }
1116
1117 if (node->parent == m_nill && Color::Black != node->color) {
1118 node->color = Color::Black;
1119 }
1120 }
1121
1122
1123 void removeFix(Node *node)
1124 {
1125 assert(nullptr != node && nullptr != node->parent);
1126
1127 while (Color::Black == node->color && node->parent != m_nill) {
1128 auto sibling = siblingNode(node);
1129 if (Color::Red == sibling->color) {
1130 rotate(sibling);
1131 sibling = siblingNode(node);
1132 }
1133
1134 assert(nullptr != sibling && nullptr != sibling->left && nullptr != sibling->right);
1135 assert(Color::Black == sibling->color);
1136
1137 if (Color::Black == sibling->left->color && Color::Black == sibling->right->color) {
1138 sibling->color = Color::Red;
1139 node = node->parent;
1140 } else {
1141 if (Position::Left == nodePosition(sibling) && Color::Black == sibling->left->color) {
1142 sibling = rotateLeft(sibling);
1143 } else if (Position::Right == nodePosition(sibling) && Color::Black == sibling->right->color) {
1144 sibling = rotateRight(sibling);
1145 }
1146 rotate(sibling);
1147 node = siblingNode(node->parent);
1148 }
1149 }
1150
1151 if (Color::Black != node->color) {
1152 node->color = Color::Black;
1153 }
1154 }
1155
1156
1157 Node *m_nill;
1158 Node *m_root;
1159 size_type m_size{0};
1160 };
1161
1162
1163 template <typename IntervalType, typename ValueType>
1164 void swap(IntervalTree<IntervalType, ValueType> &lhs, IntervalTree<IntervalType, ValueType> &rhs)
1165 {
1166 lhs.swap(rhs);
1167 }
1168
1169 } // namespace Intervals
1170
1171
1172 template <typename IntervalType, typename ValueType>
1173 std::ostream &operator<<(std::ostream &out, const Intervals::Interval<IntervalType, ValueType> &interval) {
1174 out << "Interval(" << interval.low << ", " << interval.high << ")";
1175 if (interval.value != ValueType{}) {
1176 out << ": " << interval.value;
1177 }
1178 return out;
1179 }
1180
1181
1182 template <typename IntervalType, typename ValueType>
1183 std::ostream &operator<<(std::ostream &out, const Intervals::IntervalTree<IntervalType, ValueType> &tree) {
1184 out << "IntervalTree(" << tree.size() << ")";
1185 return out;
1186 }
1187
1188 #endif // INTERVALTREE_H