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