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 "SkTypes.h" | 12 #include "SkTypes.h" |
12 | 13 |
13 template <typename T> | 14 template <typename T> |
14 class GrLess { | 15 class GrLess { |
15 public: | 16 public: |
16 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; } |
17 }; | 18 }; |
18 | 19 |
19 template <typename T> | 20 template <typename T> |
20 class GrLess<T*> { | 21 class GrLess<T*> { |
(...skipping 913 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
934 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { | 935 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { |
935 return validateChildRelationsFailed(); | 936 return validateChildRelationsFailed(); |
936 } | 937 } |
937 } | 938 } |
938 } | 939 } |
939 } | 940 } |
940 return true; | 941 return true; |
941 } | 942 } |
942 #endif | 943 #endif |
943 | 944 |
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 | |
1115 #endif | 945 #endif |
OLD | NEW |