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
intless(const int & a,const int & b)12 namespace { bool intless(const int& a, const int& b) { return a < b; } }
13
simple_test(skiatest::Reporter * reporter)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
LessPDummy72 static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; }
PQIndexDummy73 static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; }
74
operator ==Dummy75 bool operator== (const Dummy& that) const {
76 return fValue == that.fValue && fPriority == that.fPriority;
77 }
operator !=Dummy78 bool operator!= (const Dummy& that) const { return !(*this == that); }
79 };
80
random_test(skiatest::Reporter * reporter)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
sort_test(skiatest::Reporter * reporter)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
DEF_TEST(TDPQueueTest,reporter)201 DEF_TEST(TDPQueueTest, reporter) {
202 simple_test(reporter);
203 random_test(reporter);
204 sort_test(reporter);
205 }
206