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