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 |