264e6dfd51835e74c1a7cf7e09a1cfab5a1c6875
[WebKit-https.git] / Source / WebCore / platform / PODIntervalTree.h
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 "PODArena.h"
30 #include "PODInterval.h"
31 #include "PODRedBlackTree.h"
32 #include <wtf/Assertions.h>
33 #include <wtf/Noncopyable.h>
34 #include <wtf/Vector.h>
35
36 namespace WebCore {
37
38 #ifndef NDEBUG
39 template<class T>
40 struct ValueToString;
41 #endif
42
43 template <class T, class UserData = void*>
44 class PODIntervalSearchAdapter {
45 public:
46     typedef PODInterval<T, UserData> IntervalType;
47     
48     PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
49         : m_result(result)
50         , m_lowValue(lowValue)
51         , m_highValue(highValue)
52     {
53     }
54     
55     const T& lowValue() const { return m_lowValue; }
56     const T& highValue() const { return m_highValue; }
57     void collectIfNeeded(const IntervalType& data) const
58     {
59         if (data.overlaps(m_lowValue, m_highValue))
60             m_result.append(data);
61     }
62
63 private:
64     Vector<IntervalType>& m_result;
65     T m_lowValue;
66     T m_highValue;
67 };
68
69 // An interval tree, which is a form of augmented red-black tree. It
70 // supports efficient (O(lg n)) insertion, removal and querying of
71 // intervals in the tree.
72 template<class T, class UserData = void*>
73 class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData>> {
74     WTF_MAKE_NONCOPYABLE(PODIntervalTree);
75 public:
76     // Typedef to reduce typing when declaring intervals to be stored in
77     // this tree.
78     typedef PODInterval<T, UserData> IntervalType;
79     typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
80
81     PODIntervalTree(UninitializedTreeEnum unitializedTree)
82         : PODRedBlackTree<IntervalType>(unitializedTree)
83     {
84         init();
85     }
86     
87     PODIntervalTree()
88         : PODRedBlackTree<IntervalType>()
89     {
90         init();
91     }
92
93     explicit PODIntervalTree(PassRefPtr<PODArena> arena)
94         : PODRedBlackTree<IntervalType>(arena)
95     {
96         init();
97     }
98
99     // Returns all intervals in the tree which overlap the given query
100     // interval. The returned intervals are sorted by increasing low
101     // endpoint.
102     Vector<IntervalType> allOverlaps(const IntervalType& interval) const
103     {
104         Vector<IntervalType> result;
105         allOverlaps(interval, result);
106         return result;
107     }
108
109     // Returns all intervals in the tree which overlap the given query
110     // interval. The returned intervals are sorted by increasing low
111     // endpoint.
112     void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const
113     {
114         // Explicit dereference of "this" required because of
115         // inheritance rules in template classes.
116         IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
117         searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
118     }
119     
120     template <class AdapterType>
121     void allOverlapsWithAdapter(AdapterType& adapter) const
122     {
123         // Explicit dereference of "this" required because of
124         // inheritance rules in template classes.
125         searchForOverlapsFrom<AdapterType>(this->root(), adapter);
126     }
127
128     // Helper to create interval objects.
129     static IntervalType createInterval(const T& low, const T& high, const UserData data = 0)
130     {
131         return IntervalType(low, high, data);
132     }
133
134     virtual bool checkInvariants() const OVERRIDE
135     {
136         if (!PODRedBlackTree<IntervalType>::checkInvariants())
137             return false;
138         if (!this->root())
139             return true;
140         return checkInvariantsFromNode(this->root(), 0);
141     }
142
143 private:
144     typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode;
145
146     // Initializes the tree.
147     void init()
148     {
149         // Explicit dereference of "this" required because of
150         // inheritance rules in template classes.
151         this->setNeedsFullOrderingComparisons(true);
152     }
153
154     // Starting from the given node, adds all overlaps with the given
155     // interval to the result vector. The intervals are sorted by
156     // increasing low endpoint.
157     template <class AdapterType>
158     void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
159     {
160         if (!node)
161             return;
162
163         // Because the intervals are sorted by left endpoint, inorder
164         // traversal produces results sorted as desired.
165
166         // See whether we need to traverse the left subtree.
167         IntervalNode* left = node->left();
168         if (left
169             // This is phrased this way to avoid the need for operator
170             // <= on type T.
171             && !(left->data().maxHigh() < adapter.lowValue()))
172             searchForOverlapsFrom<AdapterType>(left, adapter);
173
174         // Check for overlap with current node.
175         adapter.collectIfNeeded(node->data());
176
177         // See whether we need to traverse the right subtree.
178         // This is phrased this way to avoid the need for operator <=
179         // on type T.
180         if (!(adapter.highValue() < node->data().low()))
181             searchForOverlapsFrom<AdapterType>(node->right(), adapter);
182     }
183
184     virtual bool updateNode(IntervalNode* node) OVERRIDE
185     {
186         // Would use const T&, but need to reassign this reference in this
187         // function.
188         const T* curMax = &node->data().high();
189         IntervalNode* left = node->left();
190         if (left) {
191             if (*curMax < left->data().maxHigh())
192                 curMax = &left->data().maxHigh();
193         }
194         IntervalNode* right = node->right();
195         if (right) {
196             if (*curMax < right->data().maxHigh())
197                 curMax = &right->data().maxHigh();
198         }
199         // This is phrased like this to avoid needing operator!= on type T.
200         if (!(*curMax == node->data().maxHigh())) {
201             node->data().setMaxHigh(*curMax);
202             return true;
203         }
204         return false;
205     }
206
207     bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const
208     {
209         // These assignments are only done in order to avoid requiring
210         // a default constructor on type T.
211         T leftMaxValue(node->data().maxHigh());
212         T rightMaxValue(node->data().maxHigh());
213         IntervalNode* left = node->left();
214         IntervalNode* right = node->right();
215         if (left) {
216             if (!checkInvariantsFromNode(left, &leftMaxValue))
217                 return false;
218         }
219         if (right) {
220             if (!checkInvariantsFromNode(right, &rightMaxValue))
221                 return false;
222         }
223         if (!left && !right) {
224             // Base case.
225             if (currentMaxValue)
226                 *currentMaxValue = node->data().high();
227             return (node->data().high() == node->data().maxHigh());
228         }
229         T localMaxValue(node->data().maxHigh());
230         if (!left || !right) {
231             if (left)
232                 localMaxValue = leftMaxValue;
233             else
234                 localMaxValue = rightMaxValue;
235         } else
236             localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue;
237         if (localMaxValue < node->data().high())
238             localMaxValue = node->data().high();
239         if (!(localMaxValue == node->data().maxHigh())) {
240 #ifndef NDEBUG
241             String localMaxValueString = ValueToString<T>::string(localMaxValue);
242             LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
243                       node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
244 #endif
245             return false;
246         }
247         if (currentMaxValue)
248             *currentMaxValue = localMaxValue;
249         return true;
250     }
251 };
252
253 #ifndef NDEBUG
254 // Support for printing PODIntervals at the PODRedBlackTree level.
255 template<class T, class UserData>
256 struct ValueToString<PODInterval<T, UserData>> {
257     static String string(const PODInterval<T, UserData>& interval)
258     {
259         return interval.toString();
260     }
261 };
262 #endif
263
264 } // namespace WebCore
265
266 #endif // PODIntervalTree_h