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