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 final : 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 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
247 } | 247 } |
248 if (currentMaxValue) | 248 if (currentMaxValue) |
249 *currentMaxValue = localMaxValue; | 249 *currentMaxValue = localMaxValue; |
250 return true; | 250 return true; |
251 } | 251 } |
252 }; | 252 }; |
253 | 253 |
254 #ifndef NDEBUG | 254 #ifndef NDEBUG |
255 // Support for printing PODIntervals at the PODRedBlackTree level. | 255 // Support for printing PODIntervals at the PODRedBlackTree level. |
256 template<class T, class UserData> | 256 template<class T, class UserData> |
257 struct ValueToString<PODInterval<T, UserData> > { | 257 struct ValueToString<PODInterval<T, UserData>> { |
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 |