Home | History | Annotate | Download | only in tests
      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 DEF_TEST(TDPQueueTest, reporter) {
    154     simple_test(reporter);
    155     random_test(reporter);
    156 }
    157