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