1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27
28#include "MoveOnly.h"
29
30#include <type_traits>
31#include <wtf/HashSet.h>
32#include <wtf/PriorityQueue.h>
33
34constexpr std::size_t operator "" _z ( unsigned long long n ) { return n; }
35
36template<typename T, bool (*isHigherPriority)(const T&, const T&)>
37static void enqueue(PriorityQueue<T, isHigherPriority>& queue, T element)
38{
39 size_t sizeBefore = queue.size();
40 queue.enqueue(WTFMove(element));
41 EXPECT_EQ(sizeBefore + 1, queue.size());
42 EXPECT_FALSE(queue.isEmpty());
43}
44
45template<typename T, bool (*isHigherPriority)(const T&, const T&)>
46static T dequeue(PriorityQueue<T, isHigherPriority>& queue)
47{
48 EXPECT_FALSE(queue.isEmpty());
49 size_t sizeBefore = queue.size();
50 T result = queue.dequeue();
51 EXPECT_EQ(sizeBefore - 1, queue.size());
52 return result;
53}
54
55
56TEST(WTF_PriorityQueue, Basic)
57{
58 const unsigned numElements = 10;
59 PriorityQueue<unsigned> queue;
60
61 EXPECT_EQ(0_z, queue.size());
62 EXPECT_TRUE(queue.isEmpty());
63
64 for (unsigned i = 0; i < numElements; ++i)
65 enqueue(queue, i);
66
67 for (unsigned i = 0; i < numElements; ++i) {
68 EXPECT_EQ(i, queue.peek());
69 EXPECT_EQ(i, dequeue(queue));
70 EXPECT_EQ(numElements - i - 1, queue.size());
71 }
72
73 EXPECT_TRUE(queue.isEmpty());
74}
75
76TEST(WTF_PriorityQueue, CustomPriorityFunction)
77{
78 const unsigned numElements = 10;
79 PriorityQueue<unsigned, &isGreaterThan<unsigned>> queue;
80
81 EXPECT_EQ(0_z, queue.size());
82 EXPECT_TRUE(queue.isEmpty());
83
84 for (unsigned i = 0; i < numElements; ++i) {
85 enqueue(queue, i);
86 EXPECT_EQ(i + 1, queue.size());
87 EXPECT_FALSE(queue.isEmpty());
88 }
89
90 for (unsigned i = 0; i < numElements; ++i) {
91 EXPECT_EQ(numElements - i - 1, queue.peek());
92 EXPECT_EQ(numElements - i - 1, dequeue(queue));
93 EXPECT_EQ(numElements - i - 1, queue.size());
94 }
95
96 EXPECT_TRUE(queue.isEmpty());
97}
98
99template<bool (*isHigherPriority)(const unsigned&, const unsigned&)>
100struct CompareMove {
101 static bool compare(const MoveOnly& m1, const MoveOnly& m2)
102 {
103 return isHigherPriority(m1.value(), m2.value());
104 }
105};
106
107TEST(WTF_PriorityQueue, MoveOnly)
108{
109 PriorityQueue<MoveOnly, &CompareMove<&isLessThan<unsigned>>::compare> queue;
110
111 Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
112 Vector<unsigned> sorted = values;
113 std::sort(sorted.begin(), sorted.end());
114
115 for (auto value : values)
116 queue.enqueue(MoveOnly(value));
117
118 for (auto sortedValue : sorted) {
119 auto value = queue.dequeue();
120 EXPECT_EQ(sortedValue, value.value());
121 }
122}
123
124TEST(WTF_PriorityQueue, DecreaseKey)
125{
126 PriorityQueue<MoveOnly, &CompareMove<&isLessThan<unsigned>>::compare> queue;
127
128 Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
129 Vector<unsigned> sorted = values;
130 sorted[3] = 12;
131 std::sort(sorted.begin(), sorted.end());
132
133 for (auto value : values)
134 queue.enqueue(MoveOnly(value));
135
136 queue.decreaseKey([] (MoveOnly& m) {
137 if (m.value() == 8) {
138 m = MoveOnly(12);
139 return true;
140 }
141 return false;
142 });
143
144 for (auto sortedValue : sorted) {
145 auto value = queue.dequeue();
146 EXPECT_EQ(sortedValue, value.value());
147 }
148}
149
150TEST(WTF_PriorityQueue, IncreaseKey)
151{
152 PriorityQueue<MoveOnly, &CompareMove<&isGreaterThan<unsigned>>::compare> queue;
153
154 Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
155 Vector<unsigned> sorted = values;
156 sorted[3] = 12;
157 std::sort(sorted.begin(), sorted.end(), std::greater<unsigned>());
158
159 for (auto value : values)
160 queue.enqueue(MoveOnly(value));
161
162 queue.increaseKey([] (MoveOnly& m) {
163 if (m.value() == 8) {
164 m = MoveOnly(12);
165 return true;
166 }
167 return false;
168 });
169
170 for (auto sortedValue : sorted) {
171 auto value = queue.dequeue();
172 EXPECT_EQ(sortedValue, value.value());
173 }
174}
175
176TEST(WTF_PriorityQueue, Iteration)
177{
178 PriorityQueue<MoveOnly, &CompareMove<&isGreaterThan<unsigned>>::compare> queue;
179
180 Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
181 Vector<unsigned> sorted = values;
182 std::sort(sorted.begin(), sorted.end(), std::greater<unsigned>());
183
184 for (auto value : values)
185 queue.enqueue(MoveOnly(value));
186
187 values.clear();
188 for (auto& element : queue)
189 values.append(element.value());
190
191 std::sort(values.begin(), values.end(), std::greater<unsigned>());
192 EXPECT_EQ(values.size(), sorted.size());
193 if (values.size() == sorted.size()) {
194 for (size_t i = 0; i < values.size(); ++i)
195 EXPECT_EQ(sorted[i], values[i]);
196 }
197}
198
199TEST(WTF_PriorityQueue, RandomActions)
200{
201 const uint64_t prime1 = 15487237;
202 const uint64_t prime2 = 179428283;
203 uint64_t randomNumber = 19405709;
204
205 auto nextRandom = [&] () -> uint64_t {
206 randomNumber = randomNumber * prime1 + prime2;
207 return randomNumber;
208 };
209
210 PriorityQueue<uint64_t> queue;
211 Vector<uint64_t> values;
212
213 enum Cases {
214 Enqueue,
215 Dequeue,
216 NumberOfCases
217 };
218
219 // Seed the queue.
220 for (unsigned i = 0; i < 100; ++i) {
221 auto number = nextRandom();
222 queue.enqueue(number);
223 values.append(number);
224 EXPECT_TRUE(queue.isValidHeap());
225 }
226
227 for (unsigned i = 0; i < 10000; ++i) {
228 auto number = nextRandom();
229 switch (number % NumberOfCases) {
230 case Enqueue: {
231 queue.enqueue(number);
232 values.append(number);
233 EXPECT_TRUE(queue.isValidHeap());
234 EXPECT_EQ(values.size(), queue.size());
235 continue;
236 }
237
238 case Dequeue: {
239 EXPECT_EQ(values.size(), queue.size());
240 if (values.size() != queue.size())
241 break;
242
243 if (!values.size())
244 continue;
245
246 // Sort with greater so the last element should be the one we dequeue.
247 std::sort(values.begin(), values.end(), std::greater<uint64_t>());
248 EXPECT_EQ(values.takeLast(), queue.dequeue());
249
250 continue;
251 }
252 default:
253 RELEASE_ASSERT_NOT_REACHED();
254 }
255 EXPECT_TRUE(queue.isValidHeap());
256 }
257}
258