diff options
author | bsalomon <bsalomon@google.com> | 2015-02-13 11:08:21 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-02-13 11:08:21 -0800 |
commit | 3555bd88a6513d219a084eabd41e9dff9e513605 (patch) | |
tree | ce441f52e090c5d86c5abb48230eacaa5431a8dd /tests/TDPQueueTest.cpp | |
parent | 2b816bacc0696f03d88c8060b21eda1e5cc7e8b1 (diff) |
Add a templated priority queue class.
Review URL: https://codereview.chromium.org/914003004
Diffstat (limited to 'tests/TDPQueueTest.cpp')
-rw-r--r-- | tests/TDPQueueTest.cpp | 156 |
1 files changed, 156 insertions, 0 deletions
diff --git a/tests/TDPQueueTest.cpp b/tests/TDPQueueTest.cpp new file mode 100644 index 0000000000..70367a7b82 --- /dev/null +++ b/tests/TDPQueueTest.cpp @@ -0,0 +1,156 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "SkTDPQueue.h" +#include "SkRandom.h" +#include "Test.h" + +namespace { bool intless(const int& a, const int& b) { return a < b; } } + +static void simple_test(skiatest::Reporter* reporter) { + 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()); +} + +struct Dummy { + int fValue; + int fPriority; + mutable int fIndex; + + static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; } + static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; } + + bool operator== (const Dummy& that) const { + return fValue == that.fValue && fPriority == that.fPriority; + } + bool operator!= (const Dummy& that) const { return !(*this == that); } +}; + +void random_test(skiatest::Reporter* reporter) { + SkRandom random; + static const Dummy kSentinel = {-1, -1, -1}; + + for (int i = 0; i < 100; ++i) { + // Create a random set of Dummy objects. + int count = random.nextULessThan(100); + SkTDArray<Dummy> array; + array.setReserve(count); + for (int j = 0; j < count; ++j) { + Dummy* dummy = array.append(); + dummy->fPriority = random.nextS(); + dummy->fValue = random.nextS(); + dummy->fIndex = -1; + if (*dummy == kSentinel) { + array.pop(); + --j; + } + } + + // Stick the dummy objects in the pqueue. + SkTDPQueue<Dummy*, Dummy::LessP, Dummy::PQIndex> pq; + for (int j = 0; j < count; ++j) { + pq.insert(&array[j]); + } + REPORTER_ASSERT(reporter, pq.count() == array.count()); + 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. + Dummy* 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, + Dummy* 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; + } + } + } + } +} + +DEF_TEST(TDPQueueTest, reporter) { + simple_test(reporter); + random_test(reporter); +} |