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