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 113 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 OVERRIDE | 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) OVERRIDE | 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 blink | 265 } // namespace blink |
266 | 266 |
267 #endif // PODIntervalTree_h | 267 #endif // PODIntervalTree_h |
OLD | NEW |