1 /* 2 * Copyright 2015 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkTDPQueue.h" 9 #include "SkRandom.h" 10 #include "Test.h" 11 12 namespace { bool intless(const int& a, const int& b) { return a < b; } } 13 14 static void simple_test(skiatest::Reporter* reporter) { 15 SkTDPQueue<int, intless> heap; 16 REPORTER_ASSERT(reporter, 0 == heap.count()); 17 18 heap.insert(0); 19 REPORTER_ASSERT(reporter, 1 == heap.count()); 20 REPORTER_ASSERT(reporter, 0 == heap.peek()); 21 heap.pop(); 22 REPORTER_ASSERT(reporter, 0 == heap.count()); 23 24 heap.insert(0); 25 heap.insert(1); 26 REPORTER_ASSERT(reporter, 2 == heap.count()); 27 REPORTER_ASSERT(reporter, 0 == heap.peek()); 28 heap.pop(); 29 REPORTER_ASSERT(reporter, 1 == heap.count()); 30 REPORTER_ASSERT(reporter, 1 == heap.peek()); 31 heap.pop(); 32 REPORTER_ASSERT(reporter, 0 == heap.count()); 33 34 heap.insert(2); 35 heap.insert(1); 36 heap.insert(0); 37 REPORTER_ASSERT(reporter, 3 == heap.count()); 38 REPORTER_ASSERT(reporter, 0 == heap.peek()); 39 heap.pop(); 40 REPORTER_ASSERT(reporter, 2 == heap.count()); 41 REPORTER_ASSERT(reporter, 1 == heap.peek()); 42 heap.pop(); 43 REPORTER_ASSERT(reporter, 1 == heap.count()); 44 REPORTER_ASSERT(reporter, 2 == heap.peek()); 45 heap.pop(); 46 REPORTER_ASSERT(reporter, 0 == heap.count()); 47 48 heap.insert(2); 49 heap.insert(3); 50 heap.insert(0); 51 heap.insert(1); 52 REPORTER_ASSERT(reporter, 4 == heap.count()); 53 REPORTER_ASSERT(reporter, 0 == heap.peek()); 54 heap.pop(); 55 REPORTER_ASSERT(reporter, 3 == heap.count()); 56 REPORTER_ASSERT(reporter, 1 == heap.peek()); 57 heap.pop(); 58 REPORTER_ASSERT(reporter, 2 == heap.count()); 59 REPORTER_ASSERT(reporter, 2 == heap.peek()); 60 heap.pop(); 61 REPORTER_ASSERT(reporter, 1 == heap.count()); 62 REPORTER_ASSERT(reporter, 3 == heap.peek()); 63 heap.pop(); 64 REPORTER_ASSERT(reporter, 0 == heap.count()); 65 } 66 67 struct Dummy { 68 int fValue; 69 int fPriority; 70 mutable int fIndex; 71 72 static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; } 73 static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; } 74 75 bool operator== (const Dummy& that) const { 76 return fValue == that.fValue && fPriority == that.fPriority; 77 } 78 bool operator!= (const Dummy& that) const { return !(*this == that); } 79 }; 80 81 void random_test(skiatest::Reporter* reporter) { 82 SkRandom random; 83 static const Dummy kSentinel = {-1, -1, -1}; 84 85 for (int i = 0; i < 100; ++i) { 86 // Create a random set of Dummy objects. 87 int count = random.nextULessThan(100); 88 SkTDArray<Dummy> array; 89 array.setReserve(count); 90 for (int j = 0; j < count; ++j) { 91 Dummy* dummy = array.append(); 92 dummy->fPriority = random.nextS(); 93 dummy->fValue = random.nextS(); 94 dummy->fIndex = -1; 95 if (*dummy == kSentinel) { 96 array.pop(); 97 --j; 98 } 99 } 100 101 // Stick the dummy objects in the pqueue. 102 SkTDPQueue<Dummy*, Dummy::LessP, Dummy::PQIndex> pq; 103 for (int j = 0; j < count; ++j) { 104 pq.insert(&array[j]); 105 } 106 REPORTER_ASSERT(reporter, pq.count() == array.count()); 107 for (int j = 0; j < count; ++j) { 108 // every item should have an entry in the queue. 109 REPORTER_ASSERT(reporter, -1 != array[j].fIndex); 110 } 111 112 // Begin the test. 113 while (pq.count()) { 114 // Make sure the top of the queue is really the highest priority. 115 Dummy* top = pq.peek(); 116 for (int k = 0; k < count; ++k) { 117 REPORTER_ASSERT(reporter, kSentinel == array[k] || 118 array[k].fPriority >= top->fPriority); 119 } 120 // Do one of three random actions: 121 unsigned action = random.nextULessThan(3); 122 switch (action) { 123 case 0: { // pop the top, 124 Dummy* top = pq.peek(); 125 REPORTER_ASSERT(reporter, array.begin() <= top && top < array.end()); 126 pq.pop(); 127 *top = kSentinel; 128 break; 129 } 130 case 1: { // remove a random element, 131 int item; 132 do { 133 item = random.nextULessThan(count); 134 } while (array[item] == kSentinel); 135 pq.remove(&array[item]); 136 array[item] = kSentinel; 137 break; 138 } 139 case 2: { // or change an element's priority. 140 int item; 141 do { 142 item = random.nextULessThan(count); 143 } while (array[item] == kSentinel); 144 array[item].fPriority = random.nextS(); 145 pq.priorityDidChange(&array[item]); 146 break; 147 } 148 } 149 } 150 } 151 } 152 153 void sort_test(skiatest::Reporter* reporter) { 154 SkRandom random; 155 156 SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqTest; 157 SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqControl; 158 159 // Create a random set of Dummy objects and populate the test queue. 160 int count = random.nextULessThan(100); 161 SkTDArray<Dummy> testArray; 162 testArray.setReserve(count); 163 for (int i = 0; i < count; i++) { 164 Dummy *dummy = testArray.append(); 165 dummy->fPriority = random.nextS(); 166 dummy->fValue = random.nextS(); 167 dummy->fIndex = -1; 168 pqTest.insert(&testArray[i]); 169 } 170 171 // Stick equivalent dummy objects into the control queue. 172 SkTDArray<Dummy> controlArray; 173 controlArray.setReserve(count); 174 for (int i = 0; i < count; i++) { 175 Dummy *dummy = controlArray.append(); 176 dummy->fPriority = testArray[i].fPriority; 177 dummy->fValue = testArray[i].fValue; 178 dummy->fIndex = -1; 179 pqControl.insert(&controlArray[i]); 180 } 181 182 // Sort the queue 183 pqTest.sort(); 184 185 // Compare elements in the queue to ensure they are in sorted order 186 int prevPriority = pqTest.peek()->fPriority; 187 for (int i = 0; i < count; i++) { 188 REPORTER_ASSERT(reporter, i <= pqTest.at(i)->fIndex); 189 REPORTER_ASSERT(reporter, prevPriority <= pqTest.at(i)->fPriority); 190 prevPriority = pqTest.at(i)->fPriority; 191 } 192 193 // Verify that after sorting the queue still produces the same result as the control queue 194 for (int i = 0; i < count; i++) { 195 REPORTER_ASSERT(reporter, *pqControl.peek() == *pqTest.peek()); 196 pqControl.pop(); 197 pqTest.pop(); 198 } 199 } 200 201 DEF_TEST(TDPQueueTest, reporter) { 202 simple_test(reporter); 203 random_test(reporter); 204 sort_test(reporter); 205 } 206
