TDPQueueTest.cpp 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205
  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. #include "include/utils/SkRandom.h"
  8. #include "src/core/SkTDPQueue.h"
  9. #include "tests/Test.h"
  10. namespace { bool intless(const int& a, const int& b) { return a < b; } }
  11. static void simple_test(skiatest::Reporter* reporter) {
  12. SkTDPQueue<int, intless> heap;
  13. REPORTER_ASSERT(reporter, 0 == heap.count());
  14. heap.insert(0);
  15. REPORTER_ASSERT(reporter, 1 == heap.count());
  16. REPORTER_ASSERT(reporter, 0 == heap.peek());
  17. heap.pop();
  18. REPORTER_ASSERT(reporter, 0 == heap.count());
  19. heap.insert(0);
  20. heap.insert(1);
  21. REPORTER_ASSERT(reporter, 2 == heap.count());
  22. REPORTER_ASSERT(reporter, 0 == heap.peek());
  23. heap.pop();
  24. REPORTER_ASSERT(reporter, 1 == heap.count());
  25. REPORTER_ASSERT(reporter, 1 == heap.peek());
  26. heap.pop();
  27. REPORTER_ASSERT(reporter, 0 == heap.count());
  28. heap.insert(2);
  29. heap.insert(1);
  30. heap.insert(0);
  31. REPORTER_ASSERT(reporter, 3 == heap.count());
  32. REPORTER_ASSERT(reporter, 0 == heap.peek());
  33. heap.pop();
  34. REPORTER_ASSERT(reporter, 2 == heap.count());
  35. REPORTER_ASSERT(reporter, 1 == heap.peek());
  36. heap.pop();
  37. REPORTER_ASSERT(reporter, 1 == heap.count());
  38. REPORTER_ASSERT(reporter, 2 == heap.peek());
  39. heap.pop();
  40. REPORTER_ASSERT(reporter, 0 == heap.count());
  41. heap.insert(2);
  42. heap.insert(3);
  43. heap.insert(0);
  44. heap.insert(1);
  45. REPORTER_ASSERT(reporter, 4 == heap.count());
  46. REPORTER_ASSERT(reporter, 0 == heap.peek());
  47. heap.pop();
  48. REPORTER_ASSERT(reporter, 3 == heap.count());
  49. REPORTER_ASSERT(reporter, 1 == heap.peek());
  50. heap.pop();
  51. REPORTER_ASSERT(reporter, 2 == heap.count());
  52. REPORTER_ASSERT(reporter, 2 == heap.peek());
  53. heap.pop();
  54. REPORTER_ASSERT(reporter, 1 == heap.count());
  55. REPORTER_ASSERT(reporter, 3 == heap.peek());
  56. heap.pop();
  57. REPORTER_ASSERT(reporter, 0 == heap.count());
  58. }
  59. struct Dummy {
  60. int fValue;
  61. int fPriority;
  62. mutable int fIndex;
  63. static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; }
  64. static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; }
  65. bool operator== (const Dummy& that) const {
  66. return fValue == that.fValue && fPriority == that.fPriority;
  67. }
  68. bool operator!= (const Dummy& that) const { return !(*this == that); }
  69. };
  70. void random_test(skiatest::Reporter* reporter) {
  71. SkRandom random;
  72. static const Dummy kSentinel = {-1, -1, -1};
  73. for (int i = 0; i < 100; ++i) {
  74. // Create a random set of Dummy objects.
  75. int count = random.nextULessThan(100);
  76. SkTDArray<Dummy> array;
  77. array.setReserve(count);
  78. for (int j = 0; j < count; ++j) {
  79. Dummy* dummy = array.append();
  80. dummy->fPriority = random.nextS();
  81. dummy->fValue = random.nextS();
  82. dummy->fIndex = -1;
  83. if (*dummy == kSentinel) {
  84. array.pop();
  85. --j;
  86. }
  87. }
  88. // Stick the dummy objects in the pqueue.
  89. SkTDPQueue<Dummy*, Dummy::LessP, Dummy::PQIndex> pq;
  90. for (int j = 0; j < count; ++j) {
  91. pq.insert(&array[j]);
  92. }
  93. REPORTER_ASSERT(reporter, pq.count() == array.count());
  94. for (int j = 0; j < count; ++j) {
  95. // every item should have an entry in the queue.
  96. REPORTER_ASSERT(reporter, -1 != array[j].fIndex);
  97. }
  98. // Begin the test.
  99. while (pq.count()) {
  100. // Make sure the top of the queue is really the highest priority.
  101. Dummy* top = pq.peek();
  102. for (int k = 0; k < count; ++k) {
  103. REPORTER_ASSERT(reporter, kSentinel == array[k] ||
  104. array[k].fPriority >= top->fPriority);
  105. }
  106. // Do one of three random actions:
  107. unsigned action = random.nextULessThan(3);
  108. switch (action) {
  109. case 0: { // pop the top,
  110. Dummy* top = pq.peek();
  111. REPORTER_ASSERT(reporter, array.begin() <= top && top < array.end());
  112. pq.pop();
  113. *top = kSentinel;
  114. break;
  115. }
  116. case 1: { // remove a random element,
  117. int item;
  118. do {
  119. item = random.nextULessThan(count);
  120. } while (array[item] == kSentinel);
  121. pq.remove(&array[item]);
  122. array[item] = kSentinel;
  123. break;
  124. }
  125. case 2: { // or change an element's priority.
  126. int item;
  127. do {
  128. item = random.nextULessThan(count);
  129. } while (array[item] == kSentinel);
  130. array[item].fPriority = random.nextS();
  131. pq.priorityDidChange(&array[item]);
  132. break;
  133. }
  134. }
  135. }
  136. }
  137. }
  138. void sort_test(skiatest::Reporter* reporter) {
  139. SkRandom random;
  140. SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqTest;
  141. SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqControl;
  142. // Create a random set of Dummy objects and populate the test queue.
  143. int count = random.nextULessThan(100);
  144. SkTDArray<Dummy> testArray;
  145. testArray.setReserve(count);
  146. for (int i = 0; i < count; i++) {
  147. Dummy *dummy = testArray.append();
  148. dummy->fPriority = random.nextS();
  149. dummy->fValue = random.nextS();
  150. dummy->fIndex = -1;
  151. pqTest.insert(&testArray[i]);
  152. }
  153. // Stick equivalent dummy objects into the control queue.
  154. SkTDArray<Dummy> controlArray;
  155. controlArray.setReserve(count);
  156. for (int i = 0; i < count; i++) {
  157. Dummy *dummy = controlArray.append();
  158. dummy->fPriority = testArray[i].fPriority;
  159. dummy->fValue = testArray[i].fValue;
  160. dummy->fIndex = -1;
  161. pqControl.insert(&controlArray[i]);
  162. }
  163. // Sort the queue
  164. pqTest.sort();
  165. // Compare elements in the queue to ensure they are in sorted order
  166. int prevPriority = pqTest.peek()->fPriority;
  167. for (int i = 0; i < count; i++) {
  168. REPORTER_ASSERT(reporter, i <= pqTest.at(i)->fIndex);
  169. REPORTER_ASSERT(reporter, prevPriority <= pqTest.at(i)->fPriority);
  170. prevPriority = pqTest.at(i)->fPriority;
  171. }
  172. // Verify that after sorting the queue still produces the same result as the control queue
  173. for (int i = 0; i < count; i++) {
  174. REPORTER_ASSERT(reporter, *pqControl.peek() == *pqTest.peek());
  175. pqControl.pop();
  176. pqTest.pop();
  177. }
  178. }
  179. DEF_TEST(TDPQueueTest, reporter) {
  180. simple_test(reporter);
  181. random_test(reporter);
  182. sort_test(reporter);
  183. }