OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2010 Google Inc. All rights reserved. | 2 * Copyright (C) 2010 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * | 7 * |
8 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 private: | 63 private: |
64 Vector<IntervalType>& m_result; | 64 Vector<IntervalType>& m_result; |
65 T m_lowValue; | 65 T m_lowValue; |
66 T m_highValue; | 66 T m_highValue; |
67 }; | 67 }; |
68 | 68 |
69 // An interval tree, which is a form of augmented red-black tree. It | 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 | 70 // supports efficient (O(lg n)) insertion, removal and querying of |
71 // intervals in the tree. | 71 // intervals in the tree. |
72 template<class T, class UserData = void*> | 72 template<class T, class UserData = void*> |
73 class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData> > { | 73 class PODIntervalTree FINAL : public PODRedBlackTree<PODInterval<T, UserData> >
{ |
74 WTF_MAKE_NONCOPYABLE(PODIntervalTree); | 74 WTF_MAKE_NONCOPYABLE(PODIntervalTree); |
75 public: | 75 public: |
76 // Typedef to reduce typing when declaring intervals to be stored in | 76 // Typedef to reduce typing when declaring intervals to be stored in |
77 // this tree. | 77 // this tree. |
78 typedef PODInterval<T, UserData> IntervalType; | 78 typedef PODInterval<T, UserData> IntervalType; |
79 typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType; | 79 typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType; |
80 | 80 |
81 PODIntervalTree(UninitializedTreeEnum unitializedTree) | 81 PODIntervalTree(UninitializedTreeEnum unitializedTree) |
82 : PODRedBlackTree<IntervalType>(unitializedTree) | 82 : PODRedBlackTree<IntervalType>(unitializedTree) |
83 { | 83 { |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
124 // inheritance rules in template classes. | 124 // inheritance rules in template classes. |
125 searchForOverlapsFrom<AdapterType>(this->root(), adapter); | 125 searchForOverlapsFrom<AdapterType>(this->root(), adapter); |
126 } | 126 } |
127 | 127 |
128 // Helper to create interval objects. | 128 // Helper to create interval objects. |
129 static IntervalType createInterval(const T& low, const T& high, const UserDa
ta data = 0) | 129 static IntervalType createInterval(const T& low, const T& high, const UserDa
ta data = 0) |
130 { | 130 { |
131 return IntervalType(low, high, data); | 131 return IntervalType(low, high, data); |
132 } | 132 } |
133 | 133 |
134 virtual bool checkInvariants() const | 134 virtual bool checkInvariants() const OVERRIDE |
135 { | 135 { |
136 if (!PODRedBlackTree<IntervalType>::checkInvariants()) | 136 if (!PODRedBlackTree<IntervalType>::checkInvariants()) |
137 return false; | 137 return false; |
138 if (!this->root()) | 138 if (!this->root()) |
139 return true; | 139 return true; |
140 return checkInvariantsFromNode(this->root(), 0); | 140 return checkInvariantsFromNode(this->root(), 0); |
141 } | 141 } |
142 | 142 |
143 private: | 143 private: |
144 typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode; | 144 typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode; |
(...skipping 29 matching lines...) Expand all Loading... |
174 // Check for overlap with current node. | 174 // Check for overlap with current node. |
175 adapter.collectIfNeeded(node->data()); | 175 adapter.collectIfNeeded(node->data()); |
176 | 176 |
177 // See whether we need to traverse the right subtree. | 177 // See whether we need to traverse the right subtree. |
178 // This is phrased this way to avoid the need for operator <= | 178 // This is phrased this way to avoid the need for operator <= |
179 // on type T. | 179 // on type T. |
180 if (!(adapter.highValue() < node->data().low())) | 180 if (!(adapter.highValue() < node->data().low())) |
181 searchForOverlapsFrom<AdapterType>(node->right(), adapter); | 181 searchForOverlapsFrom<AdapterType>(node->right(), adapter); |
182 } | 182 } |
183 | 183 |
184 virtual bool updateNode(IntervalNode* node) | 184 virtual bool updateNode(IntervalNode* node) OVERRIDE |
185 { | 185 { |
186 // Would use const T&, but need to reassign this reference in this | 186 // Would use const T&, but need to reassign this reference in this |
187 // function. | 187 // function. |
188 const T* curMax = &node->data().high(); | 188 const T* curMax = &node->data().high(); |
189 IntervalNode* left = node->left(); | 189 IntervalNode* left = node->left(); |
190 if (left) { | 190 if (left) { |
191 if (*curMax < left->data().maxHigh()) | 191 if (*curMax < left->data().maxHigh()) |
192 curMax = &left->data().maxHigh(); | 192 curMax = &left->data().maxHigh(); |
193 } | 193 } |
194 IntervalNode* right = node->right(); | 194 IntervalNode* right = node->right(); |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
258 static String string(const PODInterval<T, UserData>& interval) | 258 static String string(const PODInterval<T, UserData>& interval) |
259 { | 259 { |
260 return interval.toString(); | 260 return interval.toString(); |
261 } | 261 } |
262 }; | 262 }; |
263 #endif | 263 #endif |
264 | 264 |
265 } // namespace WebCore | 265 } // namespace WebCore |
266 | 266 |
267 #endif // PODIntervalTree_h | 267 #endif // PODIntervalTree_h |
OLD | NEW |