Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(149)

Side by Side Diff: Source/platform/PODIntervalTree.h

Issue 131003004: Update platform classes to use OVERRIDE / FINAL when needed (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 6 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/platform/PODArena.h ('k') | Source/platform/RefCountedSupplement.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
OLDNEW
« no previous file with comments | « Source/platform/PODArena.h ('k') | Source/platform/RefCountedSupplement.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698