TDPQueueTest.cpp File Reference

#include "include/private/base/SkTDArray.h"
#include "src/base/SkRandom.h"
#include "src/base/SkTDPQueue.h"
#include "tests/Test.h"

Go to the source code of this file.

Classes
struct	Mock

Functions
static void	simple_test (skiatest::Reporter *reporter)
void	random_test (skiatest::Reporter *reporter)
void	sort_test (skiatest::Reporter *reporter)
	DEF_TEST (TDPQueueTest, reporter)

Function Documentation

DEF_TEST()

DEF_TEST	(	TDPQueueTest	,
		reporter
	)

Definition at line 202 of file TDPQueueTest.cpp.

                                 {
    simple_test(reporter);
    random_test(reporter);
    sort_test(reporter);
}

random_test()

void random_test

(

skiatest::Reporter *

reporter

)

Definition at line 82 of file TDPQueueTest.cpp.

                                             {
    SkRandom random;
    static const Mock kSentinel = {-1, -1, -1};
 
    for (int i = 0; i < 100; ++i) {
        // Create a random set of Mock objects.
        int count = random.nextULessThan(100);
        SkTDArray<Mock> array;
        array.reserve(count);
        for (int j = 0; j < count; ++j) {
            Mock* mock = array.append();
            mock->fPriority = random.nextS();
            mock->fValue = random.nextS();
            mock->fIndex = -1;
            if (*mock == kSentinel) {
                array.pop_back();
                --j;
            }
        }
 
        // Stick the mock objects in the pqueue.
        SkTDPQueue<Mock*, Mock::LessP, Mock::PQIndex> pq;
        for (int j = 0; j < count; ++j) {
            pq.insert(&array[j]);
        }
        REPORTER_ASSERT(reporter, pq.count() == array.size());
        for (int j = 0; j < count; ++j) {
            // every item should have an entry in the queue.
            REPORTER_ASSERT(reporter, -1 != array[j].fIndex);
        }
 
        // Begin the test.
        while (pq.count()) {
            // Make sure the top of the queue is really the highest priority.
            Mock* top = pq.peek();
            for (int k = 0; k < count; ++k) {
                REPORTER_ASSERT(reporter, kSentinel == array[k] ||
                                            array[k].fPriority >= top->fPriority);
            }
            // Do one of three random actions:
            unsigned action = random.nextULessThan(3);
            switch (action) {
                case 0: { // pop the top,
                    top = pq.peek();
                    REPORTER_ASSERT(reporter, array.begin() <= top && top < array.end());
                    pq.pop();
                    *top = kSentinel;
                    break;
                }
                case 1: { // remove a random element,
                    int item;
                    do {
                        item = random.nextULessThan(count);
                    } while (array[item] == kSentinel);
                    pq.remove(&array[item]);
                    array[item] = kSentinel;
                    break;
                }
                case 2: { // or change an element's priority.
                    int item;
                    do {
                        item = random.nextULessThan(count);
                    } while (array[item] == kSentinel);
                    array[item].fPriority = random.nextS();
                    pq.priorityDidChange(&array[item]);
                    break;
                }
            }
        }
   }
}

simple_test()

static void simple_test ( skiatest::Reporter *  reporter )

static

Definition at line 15 of file TDPQueueTest.cpp.

                                                    {
    SkTDPQueue<int, intless> heap;
    REPORTER_ASSERT(reporter, 0 == heap.count());
 
    heap.insert(0);
    REPORTER_ASSERT(reporter, 1 == heap.count());
    REPORTER_ASSERT(reporter, 0 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 0 == heap.count());
 
    heap.insert(0);
    heap.insert(1);
    REPORTER_ASSERT(reporter, 2 == heap.count());
    REPORTER_ASSERT(reporter, 0 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 1 == heap.count());
    REPORTER_ASSERT(reporter, 1 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 0 == heap.count());
 
    heap.insert(2);
    heap.insert(1);
    heap.insert(0);
    REPORTER_ASSERT(reporter, 3 == heap.count());
    REPORTER_ASSERT(reporter, 0 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 2 == heap.count());
    REPORTER_ASSERT(reporter, 1 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 1 == heap.count());
    REPORTER_ASSERT(reporter, 2 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 0 == heap.count());
 
    heap.insert(2);
    heap.insert(3);
    heap.insert(0);
    heap.insert(1);
    REPORTER_ASSERT(reporter, 4 == heap.count());
    REPORTER_ASSERT(reporter, 0 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 3 == heap.count());
    REPORTER_ASSERT(reporter, 1 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 2 == heap.count());
    REPORTER_ASSERT(reporter, 2 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 1 == heap.count());
    REPORTER_ASSERT(reporter, 3 == heap.peek());
    heap.pop();
    REPORTER_ASSERT(reporter, 0 == heap.count());
}

sort_test()

void sort_test

(

skiatest::Reporter *

reporter

)

Definition at line 154 of file TDPQueueTest.cpp.

                                           {
    SkRandom random;
 
    SkTDPQueue<Mock *, Mock::LessP, Mock::PQIndex> pqTest;
    SkTDPQueue<Mock *, Mock::LessP, Mock::PQIndex> pqControl;
 
    // Create a random set of Mock objects and populate the test queue.
    int count = random.nextULessThan(100);
    SkTDArray<Mock> testArray;
    testArray.reserve(count);
    for (int i = 0; i < count; i++) {
        Mock *mock = testArray.append();
        mock->fPriority = random.nextS();
        mock->fValue = random.nextS();
        mock->fIndex = -1;
        pqTest.insert(&testArray[i]);
    }
 
    // Stick equivalent mock objects into the control queue.
    SkTDArray<Mock> controlArray;
    controlArray.reserve(count);
    for (int i = 0; i < count; i++) {
        Mock *mock = controlArray.append();
        mock->fPriority = testArray[i].fPriority;
        mock->fValue = testArray[i].fValue;
        mock->fIndex = -1;
        pqControl.insert(&controlArray[i]);
    }
 
    // Sort the queue
    pqTest.sort();
 
    // Compare elements in the queue to ensure they are in sorted order
    int prevPriority = pqTest.peek()->fPriority;
    for (int i = 0; i < count; i++) {
        REPORTER_ASSERT(reporter, i <= pqTest.at(i)->fIndex);
        REPORTER_ASSERT(reporter, prevPriority <= pqTest.at(i)->fPriority);
        prevPriority = pqTest.at(i)->fPriority;
    }
 
    // Verify that after sorting the queue still produces the same result as the control queue
    for (int i = 0; i < count; i++) {
        REPORTER_ASSERT(reporter, *pqControl.peek() == *pqTest.peek());
        pqControl.pop();
        pqTest.pop();
    }
}