| OLD | NEW |
| 1 | |
| 2 /* | 1 /* |
| 3 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
| 4 * | 3 * |
| 5 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 6 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 7 */ | 6 */ |
| 8 | 7 |
| 9 | |
| 10 #ifndef GrRedBlackTree_DEFINED | 8 #ifndef GrRedBlackTree_DEFINED |
| 11 #define GrRedBlackTree_DEFINED | 9 #define GrRedBlackTree_DEFINED |
| 12 | 10 |
| 13 #include "GrNoncopyable.h" | 11 #include "SkTypes.h" |
| 14 | 12 |
| 15 template <typename T> | 13 template <typename T> |
| 16 class GrLess { | 14 class GrLess { |
| 17 public: | 15 public: |
| 18 bool operator()(const T& a, const T& b) const { return a < b; } | 16 bool operator()(const T& a, const T& b) const { return a < b; } |
| 19 }; | 17 }; |
| 20 | 18 |
| 21 template <typename T> | 19 template <typename T> |
| 22 class GrLess<T*> { | 20 class GrLess<T*> { |
| 23 public: | 21 public: |
| 24 bool operator()(const T* a, const T* b) const { return *a < *b; } | 22 bool operator()(const T* a, const T* b) const { return *a < *b; } |
| 25 }; | 23 }; |
| 26 | 24 |
| 27 /** | 25 /** |
| 28 * In debug build this will cause full traversals of the tree when the validate | 26 * In debug build this will cause full traversals of the tree when the validate |
| 29 * is called on insert and remove. Useful for debugging but very slow. | 27 * is called on insert and remove. Useful for debugging but very slow. |
| 30 */ | 28 */ |
| 31 #define DEEP_VALIDATE 0 | 29 #define DEEP_VALIDATE 0 |
| 32 | 30 |
| 33 /** | 31 /** |
| 34 * A sorted tree that uses the red-black tree algorithm. Allows duplicate | 32 * A sorted tree that uses the red-black tree algorithm. Allows duplicate |
| 35 * entries. Data is of type T and is compared using functor C. A single C object | 33 * entries. Data is of type T and is compared using functor C. A single C object |
| 36 * will be created and used for all comparisons. | 34 * will be created and used for all comparisons. |
| 37 */ | 35 */ |
| 38 template <typename T, typename C = GrLess<T> > | 36 template <typename T, typename C = GrLess<T> > |
| 39 class GrRedBlackTree : public GrNoncopyable { | 37 class GrRedBlackTree : public SkNoncopyable { |
| 40 public: | 38 public: |
| 41 /** | 39 /** |
| 42 * Creates an empty tree. | 40 * Creates an empty tree. |
| 43 */ | 41 */ |
| 44 GrRedBlackTree(); | 42 GrRedBlackTree(); |
| 45 virtual ~GrRedBlackTree(); | 43 virtual ~GrRedBlackTree(); |
| 46 | 44 |
| 47 /** | 45 /** |
| 48 * Class used to iterater through the tree. The valid range of the tree | 46 * Class used to iterater through the tree. The valid range of the tree |
| 49 * is given by [begin(), end()). It is legal to dereference begin() but not | 47 * is given by [begin(), end()). It is legal to dereference begin() but not |
| (...skipping 1058 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1108 // remove all entries | 1106 // remove all entries |
| 1109 while (!tree.empty()) { | 1107 while (!tree.empty()) { |
| 1110 tree.remove(tree.begin()); | 1108 tree.remove(tree.begin()); |
| 1111 } | 1109 } |
| 1112 | 1110 |
| 1113 // test reset on empty tree. | 1111 // test reset on empty tree. |
| 1114 tree.reset(); | 1112 tree.reset(); |
| 1115 } | 1113 } |
| 1116 | 1114 |
| 1117 #endif | 1115 #endif |
| OLD | NEW |