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
12namespace { bool intless(const int& a, const int& b) { return a < b; } }
13
14static 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
67struct 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
81void 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
153void 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
201DEF_TEST(TDPQueueTest, reporter) {
202    simple_test(reporter);
203    random_test(reporter);
204    sort_test(reporter);
205}
206