OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
3 * | 3 * |
4 * 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 |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef GrRedBlackTree_DEFINED | 8 #ifndef GrRedBlackTree_DEFINED |
9 #define GrRedBlackTree_DEFINED | 9 #define GrRedBlackTree_DEFINED |
10 | 10 |
(...skipping 22 matching lines...) Expand all Loading... |
33 * is called on insert and remove. Useful for debugging but very slow. | 33 * is called on insert and remove. Useful for debugging but very slow. |
34 */ | 34 */ |
35 #define DEEP_VALIDATE 0 | 35 #define DEEP_VALIDATE 0 |
36 | 36 |
37 /** | 37 /** |
38 * A sorted tree that uses the red-black tree algorithm. Allows duplicate | 38 * A sorted tree that uses the red-black tree algorithm. Allows duplicate |
39 * entries. Data is of type T and is compared using functor C. A single C object | 39 * entries. Data is of type T and is compared using functor C. A single C object |
40 * will be created and used for all comparisons. | 40 * will be created and used for all comparisons. |
41 */ | 41 */ |
42 template <typename T, typename C = GrLess<T> > | 42 template <typename T, typename C = GrLess<T> > |
43 class GrRedBlackTree : public SkNoncopyable { | 43 class GrRedBlackTree : SkNoncopyable { |
44 public: | 44 public: |
45 /** | 45 /** |
46 * Creates an empty tree. | 46 * Creates an empty tree. |
47 */ | 47 */ |
48 GrRedBlackTree(); | 48 GrRedBlackTree(); |
49 virtual ~GrRedBlackTree(); | 49 virtual ~GrRedBlackTree(); |
50 | 50 |
51 /** | 51 /** |
52 * Class used to iterater through the tree. The valid range of the tree | 52 * Class used to iterater through the tree. The valid range of the tree |
53 * is given by [begin(), end()). It is legal to dereference begin() but not | 53 * is given by [begin(), end()). It is legal to dereference begin() but not |
(...skipping 885 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
939 return validateChildRelationsFailed(); | 939 return validateChildRelationsFailed(); |
940 } | 940 } |
941 } | 941 } |
942 } | 942 } |
943 } | 943 } |
944 return true; | 944 return true; |
945 } | 945 } |
946 #endif | 946 #endif |
947 | 947 |
948 #endif | 948 #endif |
OLD | NEW |