| 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 |