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" | |
12 #include "SkTypes.h" | 11 #include "SkTypes.h" |
13 | 12 |
14 template <typename T> | 13 template <typename T> |
15 class GrLess { | 14 class GrLess { |
16 public: | 15 public: |
17 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; } |
18 }; | 17 }; |
19 | 18 |
20 template <typename T> | 19 template <typename T> |
21 class GrLess<T*> { | 20 class GrLess<T*> { |
(...skipping 913 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
935 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { | 934 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { |
936 return validateChildRelationsFailed(); | 935 return validateChildRelationsFailed(); |
937 } | 936 } |
938 } | 937 } |
939 } | 938 } |
940 } | 939 } |
941 return true; | 940 return true; |
942 } | 941 } |
943 #endif | 942 #endif |
944 | 943 |
| 944 #include "SkRandom.h" |
| 945 |
| 946 template <typename T, typename C> |
| 947 void GrRedBlackTree<T,C>::UnitTest() { |
| 948 GrRedBlackTree<int> tree; |
| 949 |
| 950 SkRandom r; |
| 951 |
| 952 int count[100] = {0}; |
| 953 // add 10K ints |
| 954 for (int i = 0; i < 10000; ++i) { |
| 955 int x = r.nextU()%100; |
| 956 SkDEBUGCODE(Iter xi = ) tree.insert(x); |
| 957 SkASSERT(*xi == x); |
| 958 ++count[x]; |
| 959 } |
| 960 |
| 961 tree.insert(0); |
| 962 ++count[0]; |
| 963 tree.insert(99); |
| 964 ++count[99]; |
| 965 SkASSERT(*tree.begin() == 0); |
| 966 SkASSERT(*tree.last() == 99); |
| 967 SkASSERT(--(++tree.begin()) == tree.begin()); |
| 968 SkASSERT(--tree.end() == tree.last()); |
| 969 SkASSERT(tree.count() == 10002); |
| 970 |
| 971 int c = 0; |
| 972 // check that we iterate through the correct number of |
| 973 // elements and they are properly sorted. |
| 974 for (Iter a = tree.begin(); tree.end() != a; ++a) { |
| 975 Iter b = a; |
| 976 ++b; |
| 977 ++c; |
| 978 SkASSERT(b == tree.end() || *a <= *b); |
| 979 } |
| 980 SkASSERT(c == tree.count()); |
| 981 |
| 982 // check that the tree reports the correct number of each int |
| 983 // and that we can iterate through them correctly both forward |
| 984 // and backward. |
| 985 for (int i = 0; i < 100; ++i) { |
| 986 int c; |
| 987 c = tree.countOf(i); |
| 988 SkASSERT(c == count[i]); |
| 989 c = 0; |
| 990 Iter iter = tree.findFirst(i); |
| 991 while (iter != tree.end() && *iter == i) { |
| 992 ++c; |
| 993 ++iter; |
| 994 } |
| 995 SkASSERT(count[i] == c); |
| 996 c = 0; |
| 997 iter = tree.findLast(i); |
| 998 if (iter != tree.end()) { |
| 999 do { |
| 1000 if (*iter == i) { |
| 1001 ++c; |
| 1002 } else { |
| 1003 break; |
| 1004 } |
| 1005 if (iter != tree.begin()) { |
| 1006 --iter; |
| 1007 } else { |
| 1008 break; |
| 1009 } |
| 1010 } while (true); |
| 1011 } |
| 1012 SkASSERT(c == count[i]); |
| 1013 } |
| 1014 // remove all the ints between 25 and 74. Randomly chose to remove |
| 1015 // the first, last, or any entry for each. |
| 1016 for (int i = 25; i < 75; ++i) { |
| 1017 while (0 != tree.countOf(i)) { |
| 1018 --count[i]; |
| 1019 int x = r.nextU() % 3; |
| 1020 Iter iter; |
| 1021 switch (x) { |
| 1022 case 0: |
| 1023 iter = tree.findFirst(i); |
| 1024 break; |
| 1025 case 1: |
| 1026 iter = tree.findLast(i); |
| 1027 break; |
| 1028 case 2: |
| 1029 default: |
| 1030 iter = tree.find(i); |
| 1031 break; |
| 1032 } |
| 1033 tree.remove(iter); |
| 1034 } |
| 1035 SkASSERT(0 == count[i]); |
| 1036 SkASSERT(tree.findFirst(i) == tree.end()); |
| 1037 SkASSERT(tree.findLast(i) == tree.end()); |
| 1038 SkASSERT(tree.find(i) == tree.end()); |
| 1039 } |
| 1040 // remove all of the 0 entries. (tests removing begin()) |
| 1041 SkASSERT(*tree.begin() == 0); |
| 1042 SkASSERT(*(--tree.end()) == 99); |
| 1043 while (0 != tree.countOf(0)) { |
| 1044 --count[0]; |
| 1045 tree.remove(tree.find(0)); |
| 1046 } |
| 1047 SkASSERT(0 == count[0]); |
| 1048 SkASSERT(tree.findFirst(0) == tree.end()); |
| 1049 SkASSERT(tree.findLast(0) == tree.end()); |
| 1050 SkASSERT(tree.find(0) == tree.end()); |
| 1051 SkASSERT(0 < *tree.begin()); |
| 1052 |
| 1053 // remove all the 99 entries (tests removing last()). |
| 1054 while (0 != tree.countOf(99)) { |
| 1055 --count[99]; |
| 1056 tree.remove(tree.find(99)); |
| 1057 } |
| 1058 SkASSERT(0 == count[99]); |
| 1059 SkASSERT(tree.findFirst(99) == tree.end()); |
| 1060 SkASSERT(tree.findLast(99) == tree.end()); |
| 1061 SkASSERT(tree.find(99) == tree.end()); |
| 1062 SkASSERT(99 > *(--tree.end())); |
| 1063 SkASSERT(tree.last() == --tree.end()); |
| 1064 |
| 1065 // Make sure iteration still goes through correct number of entries |
| 1066 // and is still sorted correctly. |
| 1067 c = 0; |
| 1068 for (Iter a = tree.begin(); tree.end() != a; ++a) { |
| 1069 Iter b = a; |
| 1070 ++b; |
| 1071 ++c; |
| 1072 SkASSERT(b == tree.end() || *a <= *b); |
| 1073 } |
| 1074 SkASSERT(c == tree.count()); |
| 1075 |
| 1076 // repeat check that correct number of each entry is in the tree |
| 1077 // and iterates correctly both forward and backward. |
| 1078 for (int i = 0; i < 100; ++i) { |
| 1079 SkASSERT(tree.countOf(i) == count[i]); |
| 1080 int c = 0; |
| 1081 Iter iter = tree.findFirst(i); |
| 1082 while (iter != tree.end() && *iter == i) { |
| 1083 ++c; |
| 1084 ++iter; |
| 1085 } |
| 1086 SkASSERT(count[i] == c); |
| 1087 c = 0; |
| 1088 iter = tree.findLast(i); |
| 1089 if (iter != tree.end()) { |
| 1090 do { |
| 1091 if (*iter == i) { |
| 1092 ++c; |
| 1093 } else { |
| 1094 break; |
| 1095 } |
| 1096 if (iter != tree.begin()) { |
| 1097 --iter; |
| 1098 } else { |
| 1099 break; |
| 1100 } |
| 1101 } while (true); |
| 1102 } |
| 1103 SkASSERT(count[i] == c); |
| 1104 } |
| 1105 |
| 1106 // remove all entries |
| 1107 while (!tree.empty()) { |
| 1108 tree.remove(tree.begin()); |
| 1109 } |
| 1110 |
| 1111 // test reset on empty tree. |
| 1112 tree.reset(); |
| 1113 } |
| 1114 |
945 #endif | 1115 #endif |
OLD | NEW |