| OLD | NEW |
|---|
| (Empty) |
| 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 "platform/PODArena.h" | |
| 30 #include "platform/PODInterval.h" | |
| 31 #include "platform/PODRedBlackTree.h" | |
| 32 #include "wtf/Assertions.h" | |
| 33 #include "wtf/Noncopyable.h" | |
| 34 #include "wtf/Vector.h" | |
| 35 | |
| 36 namespace blink { | |
| 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, co
nst 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 final : 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 UserDa
ta 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 : lef
tMaxValue; | |
| 237 } | |
| 238 if (localMaxValue < node->data().high()) | |
| 239 localMaxValue = node->data().high(); | |
| 240 if (!(localMaxValue == node->data().maxHigh())) { | |
| 241 #ifndef NDEBUG | |
| 242 String localMaxValueString = ValueToString<T>::string(localMaxValue)
; | |
| 243 WTF_LOG_ERROR("PODIntervalTree verification failed at node 0x%p: loc
alMaxValue=%s and data=%s", | |
| 244 node, localMaxValueString.utf8().data(), node->data().toString()
.utf8().data()); | |
| 245 #endif | |
| 246 return false; | |
| 247 } | |
| 248 if (currentMaxValue) | |
| 249 *currentMaxValue = localMaxValue; | |
| 250 return true; | |
| 251 } | |
| 252 }; | |
| 253 | |
| 254 #ifndef NDEBUG | |
| 255 // Support for printing PODIntervals at the PODRedBlackTree level. | |
| 256 template<class T, class UserData> | |
| 257 struct ValueToString<PODInterval<T, UserData> > { | |
| 258 static String string(const PODInterval<T, UserData>& interval) | |
| 259 { | |
| 260 return interval.toString(); | |
| 261 } | |
| 262 }; | |
| 263 #endif | |
| 264 | |
| 265 } // namespace blink | |
| 266 | |
| 267 #endif // PODIntervalTree_h | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 705373003:
Remove PODIntervalTree and machinery. (Closed)
Base URL: git@github.com:domokit/mojo.git@master