1/*
2 * Copyright (C) 2010 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef PODIntervalTree_h
27#define PODIntervalTree_h
28
29#include "PODInterval.h"
30#include "PODRedBlackTree.h"
31#include <wtf/Assertions.h>
32#include <wtf/Noncopyable.h>
33#include <wtf/Optional.h>
34#include <wtf/Vector.h>
35#include <wtf/text/ValueToString.h>
36
37namespace WebCore {
38
39template <class T, class UserData = void*>
40class PODIntervalSearchAdapter {
41public:
42 typedef PODInterval<T, UserData> IntervalType;
43
44 PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
45 : m_result(result)
46 , m_lowValue(lowValue)
47 , m_highValue(highValue)
48 {
49 }
50
51 const T& lowValue() const { return m_lowValue; }
52 const T& highValue() const { return m_highValue; }
53 void collectIfNeeded(const IntervalType& data) const
54 {
55 if (data.overlaps(m_lowValue, m_highValue))
56 m_result.append(data);
57 }
58
59private:
60 Vector<IntervalType>& m_result;
61 T m_lowValue;
62 T m_highValue;
63};
64
65// An interval tree, which is a form of augmented red-black tree. It
66// supports efficient (O(lg n)) insertion, removal and querying of
67// intervals in the tree.
68template<class T, class UserData = void*>
69class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData>> {
70 WTF_MAKE_FAST_ALLOCATED;
71 WTF_MAKE_NONCOPYABLE(PODIntervalTree);
72public:
73 // Typedef to reduce typing when declaring intervals to be stored in
74 // this tree.
75 typedef PODInterval<T, UserData> IntervalType;
76 typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
77
78 PODIntervalTree()
79 : PODRedBlackTree<IntervalType>()
80 {
81 init();
82 }
83
84 // Returns all intervals in the tree which overlap the given query
85 // interval. The returned intervals are sorted by increasing low
86 // endpoint.
87 Vector<IntervalType> allOverlaps(const IntervalType& interval) const
88 {
89 Vector<IntervalType> result;
90 allOverlaps(interval, result);
91 return result;
92 }
93
94 // Returns all intervals in the tree which overlap the given query
95 // interval. The returned intervals are sorted by increasing low
96 // endpoint.
97 void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const
98 {
99 // Explicit dereference of "this" required because of
100 // inheritance rules in template classes.
101 IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
102 searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
103 }
104
105 template <class AdapterType>
106 void allOverlapsWithAdapter(AdapterType& adapter) const
107 {
108 // Explicit dereference of "this" required because of
109 // inheritance rules in template classes.
110 searchForOverlapsFrom<AdapterType>(this->root(), adapter);
111 }
112
113 // Helper to create interval objects.
114 static IntervalType createInterval(const T& low, const T& high, const UserData data = 0)
115 {
116 return IntervalType(low, high, data);
117 }
118
119 Optional<IntervalType> nextIntervalAfter(const IntervalType& interval)
120 {
121 auto next = smallestNodeGreaterThanFrom(interval, this->root());
122 if (!next)
123 return WTF::nullopt;
124
125 return next->data();
126 }
127
128 bool checkInvariants() const override
129 {
130 if (!PODRedBlackTree<IntervalType>::checkInvariants())
131 return false;
132 if (!this->root())
133 return true;
134 return checkInvariantsFromNode(this->root(), 0);
135 }
136
137private:
138 typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode;
139
140 // Initializes the tree.
141 void init()
142 {
143 // Explicit dereference of "this" required because of
144 // inheritance rules in template classes.
145 this->setNeedsFullOrderingComparisons(true);
146 }
147
148 // Starting from the given node, adds all overlaps with the given
149 // interval to the result vector. The intervals are sorted by
150 // increasing low endpoint.
151 template <class AdapterType>
152 void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
153 {
154 if (!node)
155 return;
156
157 // Because the intervals are sorted by left endpoint, inorder
158 // traversal produces results sorted as desired.
159
160 // See whether we need to traverse the left subtree.
161 IntervalNode* left = node->left();
162 if (left
163 // This is phrased this way to avoid the need for operator
164 // <= on type T.
165 && !(left->data().maxHigh() < adapter.lowValue()))
166 searchForOverlapsFrom<AdapterType>(left, adapter);
167
168 // Check for overlap with current node.
169 adapter.collectIfNeeded(node->data());
170
171 // See whether we need to traverse the right subtree.
172 // This is phrased this way to avoid the need for operator <=
173 // on type T.
174 if (!(adapter.highValue() < node->data().low()))
175 searchForOverlapsFrom<AdapterType>(node->right(), adapter);
176 }
177
178 IntervalNode* smallestNodeGreaterThanFrom(const IntervalType& interval, IntervalNode* node) const
179 {
180 if (!node)
181 return nullptr;
182
183 if (!(interval.high() < node->data().low()))
184 return smallestNodeGreaterThanFrom(interval, node->right());
185
186 if (auto left = smallestNodeGreaterThanFrom(interval, node->right()))
187 return left;
188
189 return node;
190}
191
192 bool updateNode(IntervalNode* node) override
193 {
194 // Would use const T&, but need to reassign this reference in this
195 // function.
196 const T* curMax = &node->data().high();
197 IntervalNode* left = node->left();
198 if (left) {
199 if (*curMax < left->data().maxHigh())
200 curMax = &left->data().maxHigh();
201 }
202 IntervalNode* right = node->right();
203 if (right) {
204 if (*curMax < right->data().maxHigh())
205 curMax = &right->data().maxHigh();
206 }
207 // This is phrased like this to avoid needing operator!= on type T.
208 if (!(*curMax == node->data().maxHigh())) {
209 node->data().setMaxHigh(*curMax);
210 return true;
211 }
212 return false;
213 }
214
215 bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const
216 {
217 // These assignments are only done in order to avoid requiring
218 // a default constructor on type T.
219 T leftMaxValue(node->data().maxHigh());
220 T rightMaxValue(node->data().maxHigh());
221 IntervalNode* left = node->left();
222 IntervalNode* right = node->right();
223 if (left) {
224 if (!checkInvariantsFromNode(left, &leftMaxValue))
225 return false;
226 }
227 if (right) {
228 if (!checkInvariantsFromNode(right, &rightMaxValue))
229 return false;
230 }
231 if (!left && !right) {
232 // Base case.
233 if (currentMaxValue)
234 *currentMaxValue = node->data().high();
235 return (node->data().high() == node->data().maxHigh());
236 }
237 T localMaxValue(node->data().maxHigh());
238 if (!left || !right) {
239 if (left)
240 localMaxValue = leftMaxValue;
241 else
242 localMaxValue = rightMaxValue;
243 } else
244 localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue;
245 if (localMaxValue < node->data().high())
246 localMaxValue = node->data().high();
247 if (!(localMaxValue == node->data().maxHigh())) {
248#ifndef NDEBUG
249 String localMaxValueString = ValueToString<T>::string(localMaxValue);
250 LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
251 node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
252#endif
253 return false;
254 }
255 if (currentMaxValue)
256 *currentMaxValue = localMaxValue;
257 return true;
258 }
259};
260
261} // namespace WebCore
262
263#ifndef NDEBUG
264namespace WTF {
265
266// Support for printing PODIntervals at the PODRedBlackTree level.
267template<class T, class UserData>
268struct ValueToString<WebCore::PODInterval<T, UserData>> {
269 static String string(const WebCore::PODInterval<T, UserData>& interval)
270 {
271 return interval.toString();
272 }
273};
274
275} // namespace WTF
276#endif
277
278#endif // PODIntervalTree_h
279