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 |
11 #include "GrConfig.h" | 11 #include "GrConfig.h" |
12 #include "SkTypes.h" | 12 #include "SkTypes.h" |
13 | 13 |
14 template <typename T> | 14 template <typename T> |
15 class GrLess { | 15 class GrLess { |
16 public: | 16 public: |
17 bool operator()(const T& a, const T& b) const { return a < b; } | 17 bool operator()(const T& a, const T& b) const { return a < b; } |
18 }; | 18 }; |
19 | 19 |
20 template <typename T> | 20 template <typename T> |
21 class GrLess<T*> { | 21 class GrLess<T*> { |
22 public: | 22 public: |
23 bool operator()(const T* a, const T* b) const { return *a < *b; } | 23 bool operator()(const T* a, const T* b) const { return *a < *b; } |
24 }; | 24 }; |
25 | 25 |
| 26 class GrStrLess { |
| 27 public: |
| 28 bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0
; } |
| 29 }; |
| 30 |
26 /** | 31 /** |
27 * In debug build this will cause full traversals of the tree when the validate | 32 * In debug build this will cause full traversals of the tree when the validate |
28 * 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. |
29 */ | 34 */ |
30 #define DEEP_VALIDATE 0 | 35 #define DEEP_VALIDATE 0 |
31 | 36 |
32 /** | 37 /** |
33 * 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 |
34 * 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 |
35 * will be created and used for all comparisons. | 40 * will be created and used for all comparisons. |
(...skipping 898 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
934 return validateChildRelationsFailed(); | 939 return validateChildRelationsFailed(); |
935 } | 940 } |
936 } | 941 } |
937 } | 942 } |
938 } | 943 } |
939 return true; | 944 return true; |
940 } | 945 } |
941 #endif | 946 #endif |
942 | 947 |
943 #endif | 948 #endif |
OLD | NEW |