]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | /* | |
5 | * Copyright (C) 2016 Red Hat Inc. | |
6 | */ | |
7 | ||
8 | #include <iostream> | |
9 | #include <memory> | |
10 | #include <set> | |
11 | ||
12 | #include "gtest/gtest.h" | |
13 | ||
14 | #include "indirect_intrusive_heap.h" | |
15 | ||
16 | ||
17 | struct Elem { | |
18 | int data; | |
19 | ||
20 | crimson::IndIntruHeapData heap_data; | |
21 | crimson::IndIntruHeapData heap_data_alt; | |
22 | ||
23 | Elem(int _data) : data(_data) { } | |
24 | ||
25 | bool operator==(const Elem& other) { | |
26 | return data == other.data; | |
27 | } | |
28 | ||
29 | friend std::ostream& operator<<(std::ostream& out, const Elem& d) { | |
30 | out << d.data; | |
31 | return out; | |
32 | } | |
33 | }; | |
34 | ||
35 | ||
36 | // sorted low to high | |
37 | struct ElemCompare { | |
38 | bool operator()(const Elem& d1, const Elem& d2) const { | |
39 | return d1.data < d2.data; | |
40 | } | |
41 | }; | |
42 | ||
43 | ||
44 | // first all evens precede all odds, then they're sorted high to low | |
45 | struct ElemCompareAlt { | |
46 | bool operator()(const Elem& d1, const Elem& d2) { | |
47 | if (0 == d1.data % 2) { | |
48 | if (0 == d2.data % 2) { | |
49 | return d1.data > d2.data; | |
50 | } else { | |
51 | return true; | |
52 | } | |
53 | } else if (0 == d2.data % 2) { | |
54 | return false; | |
55 | } else { | |
56 | return d1.data > d2.data; | |
57 | } | |
58 | } | |
59 | }; | |
60 | ||
61 | ||
62 | class HeapFixture1: public ::testing::Test { | |
63 | ||
64 | public: | |
65 | ||
66 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
67 | Elem, | |
68 | &Elem::heap_data, | |
69 | ElemCompare> heap; | |
70 | ||
71 | std::shared_ptr<Elem> data1, data2, data3, data4, data5, data6, data7; | |
72 | ||
73 | void SetUp() { | |
74 | data1 = std::make_shared<Elem>(2); | |
75 | data2 = std::make_shared<Elem>(99); | |
76 | data3 = std::make_shared<Elem>(1); | |
77 | data4 = std::make_shared<Elem>(-5); | |
78 | data5 = std::make_shared<Elem>(12); | |
79 | data6 = std::make_shared<Elem>(-12); | |
80 | data7 = std::make_shared<Elem>(-7); | |
81 | ||
82 | heap.push(data1); | |
83 | heap.push(data2); | |
84 | heap.push(data3); | |
85 | heap.push(data4); | |
86 | heap.push(data5); | |
87 | heap.push(data6); | |
88 | heap.push(data7); | |
89 | } | |
90 | ||
91 | void TearDown() { | |
92 | // nothing to do | |
93 | } | |
94 | }; // class HeapFixture1 | |
95 | ||
96 | TEST(IndIntruHeap, shared_ptr) { | |
97 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
98 | Elem, | |
99 | &Elem::heap_data, | |
100 | ElemCompare> heap; | |
101 | ||
102 | EXPECT_TRUE(heap.empty()); | |
103 | ||
104 | heap.push(std::make_shared<Elem>(2)); | |
105 | ||
106 | EXPECT_FALSE(heap.empty()); | |
107 | ||
108 | heap.push(std::make_shared<Elem>(99)); | |
109 | heap.push(std::make_shared<Elem>(1)); | |
110 | heap.push(std::make_shared<Elem>(-5)); | |
111 | heap.push(std::make_shared<Elem>(12)); | |
112 | heap.push(std::make_shared<Elem>(-12)); | |
113 | heap.push(std::make_shared<Elem>(-7)); | |
114 | ||
115 | // std::cout << heap << std::endl; | |
116 | ||
117 | EXPECT_FALSE(heap.empty()); | |
118 | ||
119 | EXPECT_EQ(-12, heap.top().data); | |
120 | heap.pop(); | |
121 | EXPECT_EQ(-7, heap.top().data); | |
122 | heap.pop(); | |
123 | EXPECT_EQ(-5, heap.top().data); | |
124 | heap.pop(); | |
125 | EXPECT_EQ(1, heap.top().data); | |
126 | heap.pop(); | |
127 | EXPECT_EQ(2, heap.top().data); | |
128 | heap.pop(); | |
129 | EXPECT_EQ(12, heap.top().data); | |
130 | heap.pop(); | |
131 | EXPECT_EQ(99, heap.top().data); | |
132 | ||
133 | EXPECT_FALSE(heap.empty()); | |
134 | heap.pop(); | |
135 | EXPECT_TRUE(heap.empty()); | |
136 | } | |
137 | ||
138 | ||
139 | TEST(IndIntruHeap, unique_ptr) { | |
140 | crimson::IndIntruHeap<std::unique_ptr<Elem>, | |
141 | Elem, | |
142 | &Elem::heap_data, | |
143 | ElemCompare> heap; | |
144 | ||
145 | EXPECT_TRUE(heap.empty()); | |
146 | ||
147 | heap.push(std::unique_ptr<Elem>(new Elem(2))); | |
148 | ||
149 | EXPECT_FALSE(heap.empty()); | |
150 | ||
151 | heap.push(std::unique_ptr<Elem>(new Elem(99))); | |
152 | heap.push(std::unique_ptr<Elem>(new Elem(1))); | |
153 | heap.push(std::unique_ptr<Elem>(new Elem(-5))); | |
154 | heap.push(std::unique_ptr<Elem>(new Elem(12))); | |
155 | heap.push(std::unique_ptr<Elem>(new Elem(-12))); | |
156 | heap.push(std::unique_ptr<Elem>(new Elem(-7))); | |
157 | ||
158 | EXPECT_FALSE(heap.empty()); | |
159 | ||
160 | EXPECT_EQ(-12, heap.top().data); | |
161 | heap.pop(); | |
162 | EXPECT_EQ(-7, heap.top().data); | |
163 | heap.pop(); | |
164 | EXPECT_EQ(-5, heap.top().data); | |
165 | heap.pop(); | |
166 | EXPECT_EQ(1, heap.top().data); | |
167 | heap.pop(); | |
168 | EXPECT_EQ(2, heap.top().data); | |
169 | heap.pop(); | |
170 | EXPECT_EQ(12, heap.top().data); | |
171 | heap.pop(); | |
172 | EXPECT_EQ(99, heap.top().data); | |
173 | ||
174 | EXPECT_FALSE(heap.empty()); | |
175 | heap.pop(); | |
176 | EXPECT_TRUE(heap.empty()); | |
177 | } | |
178 | ||
179 | ||
180 | TEST(IndIntruHeap, regular_ptr) { | |
181 | crimson::IndIntruHeap<Elem*, Elem, &Elem::heap_data, ElemCompare> heap; | |
182 | ||
183 | EXPECT_TRUE(heap.empty()); | |
184 | ||
185 | heap.push(new Elem(2)); | |
186 | ||
187 | EXPECT_FALSE(heap.empty()); | |
188 | ||
189 | heap.push(new Elem(99)); | |
190 | heap.push(new Elem(1)); | |
191 | heap.push(new Elem(-5)); | |
192 | heap.push(new Elem(12)); | |
193 | heap.push(new Elem(-12)); | |
194 | heap.push(new Elem(-7)); | |
195 | ||
196 | EXPECT_FALSE(heap.empty()); | |
197 | ||
198 | EXPECT_EQ(-12, heap.top().data); | |
199 | delete &heap.top(); | |
200 | heap.pop(); | |
201 | EXPECT_EQ(-7, heap.top().data); | |
202 | delete &heap.top(); | |
203 | heap.pop(); | |
204 | EXPECT_EQ(-5, heap.top().data); | |
205 | delete &heap.top(); | |
206 | heap.pop(); | |
207 | EXPECT_EQ(1, heap.top().data); | |
208 | delete &heap.top(); | |
209 | heap.pop(); | |
210 | EXPECT_EQ(2, heap.top().data); | |
211 | delete &heap.top(); | |
212 | heap.pop(); | |
213 | EXPECT_EQ(12, heap.top().data); | |
214 | delete &heap.top(); | |
215 | heap.pop(); | |
216 | EXPECT_EQ(99, heap.top().data); | |
217 | ||
218 | delete &heap.top(); | |
219 | ||
220 | EXPECT_FALSE(heap.empty()); | |
221 | heap.pop(); | |
222 | EXPECT_TRUE(heap.empty()); | |
223 | } | |
224 | ||
225 | ||
226 | TEST(IndIntruHeap, K_3) { | |
227 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
228 | Elem, | |
229 | &Elem::heap_data, | |
230 | ElemCompare, | |
231 | 3> heap; | |
232 | ||
233 | EXPECT_TRUE(heap.empty()); | |
234 | ||
235 | heap.push(std::make_shared<Elem>(2)); | |
236 | ||
237 | EXPECT_FALSE(heap.empty()); | |
238 | ||
239 | heap.push(std::make_shared<Elem>(99)); | |
240 | heap.push(std::make_shared<Elem>(1)); | |
241 | heap.push(std::make_shared<Elem>(-5)); | |
242 | heap.push(std::make_shared<Elem>(12)); | |
243 | heap.push(std::make_shared<Elem>(-12)); | |
244 | heap.push(std::make_shared<Elem>(-7)); | |
245 | ||
246 | // std::cout << heap << std::endl; | |
247 | ||
248 | EXPECT_FALSE(heap.empty()); | |
249 | ||
250 | EXPECT_EQ(-12, heap.top().data); | |
251 | heap.pop(); | |
252 | EXPECT_EQ(-7, heap.top().data); | |
253 | heap.pop(); | |
254 | EXPECT_EQ(-5, heap.top().data); | |
255 | heap.pop(); | |
256 | EXPECT_EQ(1, heap.top().data); | |
257 | heap.pop(); | |
258 | EXPECT_EQ(2, heap.top().data); | |
259 | heap.pop(); | |
260 | EXPECT_EQ(12, heap.top().data); | |
261 | heap.pop(); | |
262 | EXPECT_EQ(99, heap.top().data); | |
263 | ||
264 | EXPECT_FALSE(heap.empty()); | |
265 | heap.pop(); | |
266 | EXPECT_TRUE(heap.empty()); | |
267 | } | |
268 | ||
269 | ||
270 | TEST(IndIntruHeap, K_4) { | |
271 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
272 | Elem, | |
273 | &Elem::heap_data, | |
274 | ElemCompare, | |
275 | 4> heap; | |
276 | ||
277 | EXPECT_TRUE(heap.empty()); | |
278 | ||
279 | heap.push(std::make_shared<Elem>(2)); | |
280 | ||
281 | EXPECT_FALSE(heap.empty()); | |
282 | ||
283 | heap.push(std::make_shared<Elem>(99)); | |
284 | heap.push(std::make_shared<Elem>(1)); | |
285 | heap.push(std::make_shared<Elem>(-5)); | |
286 | heap.push(std::make_shared<Elem>(12)); | |
287 | heap.push(std::make_shared<Elem>(-12)); | |
288 | heap.push(std::make_shared<Elem>(-7)); | |
289 | ||
290 | // std::cout << heap << std::endl; | |
291 | ||
292 | EXPECT_FALSE(heap.empty()); | |
293 | ||
294 | EXPECT_EQ(-12, heap.top().data); | |
295 | heap.pop(); | |
296 | EXPECT_EQ(-7, heap.top().data); | |
297 | heap.pop(); | |
298 | EXPECT_EQ(-5, heap.top().data); | |
299 | heap.pop(); | |
300 | EXPECT_EQ(1, heap.top().data); | |
301 | heap.pop(); | |
302 | EXPECT_EQ(2, heap.top().data); | |
303 | heap.pop(); | |
304 | EXPECT_EQ(12, heap.top().data); | |
305 | heap.pop(); | |
306 | EXPECT_EQ(99, heap.top().data); | |
307 | ||
308 | EXPECT_FALSE(heap.empty()); | |
309 | heap.pop(); | |
310 | EXPECT_TRUE(heap.empty()); | |
311 | } | |
312 | ||
313 | ||
314 | TEST(IndIntruHeap, K_10) { | |
315 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
316 | Elem, | |
317 | &Elem::heap_data, | |
318 | ElemCompare, | |
319 | 10> heap; | |
320 | ||
321 | EXPECT_TRUE(heap.empty()); | |
322 | ||
323 | heap.push(std::make_shared<Elem>(2)); | |
324 | ||
325 | EXPECT_FALSE(heap.empty()); | |
326 | ||
327 | heap.push(std::make_shared<Elem>(99)); | |
328 | heap.push(std::make_shared<Elem>(1)); | |
329 | heap.push(std::make_shared<Elem>(-5)); | |
330 | heap.push(std::make_shared<Elem>(12)); | |
331 | heap.push(std::make_shared<Elem>(-12)); | |
332 | heap.push(std::make_shared<Elem>(-7)); | |
333 | ||
334 | // std::cout << heap << std::endl; | |
335 | ||
336 | EXPECT_FALSE(heap.empty()); | |
337 | ||
338 | EXPECT_EQ(-12, heap.top().data); | |
339 | heap.pop(); | |
340 | EXPECT_EQ(-7, heap.top().data); | |
341 | heap.pop(); | |
342 | EXPECT_EQ(-5, heap.top().data); | |
343 | heap.pop(); | |
344 | EXPECT_EQ(1, heap.top().data); | |
345 | heap.pop(); | |
346 | EXPECT_EQ(2, heap.top().data); | |
347 | heap.pop(); | |
348 | EXPECT_EQ(12, heap.top().data); | |
349 | heap.pop(); | |
350 | EXPECT_EQ(99, heap.top().data); | |
351 | ||
352 | EXPECT_FALSE(heap.empty()); | |
353 | heap.pop(); | |
354 | EXPECT_TRUE(heap.empty()); | |
355 | } | |
356 | ||
357 | ||
358 | TEST(IndIntruHeap, multi_K) { | |
359 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
360 | Elem, | |
361 | &Elem::heap_data, | |
362 | ElemCompare, | |
363 | 2> heap2; | |
364 | ||
365 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
366 | Elem, | |
367 | &Elem::heap_data, | |
368 | ElemCompare, | |
369 | 3> heap3; | |
370 | ||
371 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
372 | Elem, | |
373 | &Elem::heap_data, | |
374 | ElemCompare, | |
375 | 4> heap4; | |
376 | ||
377 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
378 | Elem, | |
379 | &Elem::heap_data, | |
380 | ElemCompare, | |
381 | 10> heap10; | |
382 | ||
383 | // 250 should give us at least 4 levels on all heaps | |
384 | constexpr size_t count = 250; | |
385 | ||
386 | std::srand(std::time(0)); // use current time as seed for random generator | |
387 | ||
388 | // insert same set of random values into the four heaps | |
389 | for (size_t i = 0; i < count; ++i) { | |
390 | int value = std::rand() % 201 - 100; // -100...+100 | |
391 | auto data = std::make_shared<Elem>(value); | |
392 | heap2.push(data); | |
393 | heap3.push(data); | |
394 | heap4.push(data); | |
395 | heap10.push(data); | |
396 | } | |
397 | ||
398 | auto bound = std::numeric_limits<decltype(Elem::data)>::min(); | |
399 | ||
400 | for (size_t i = 0; i < count; ++i) { | |
401 | auto current = heap2.top().data; | |
402 | ||
403 | EXPECT_GE(current, bound) << | |
404 | "we should never go down, only increase or remain the same"; | |
405 | EXPECT_EQ(current, heap3.top().data) << | |
406 | "heap1's data and heap3's data should match"; | |
407 | EXPECT_EQ(current, heap4.top().data) << | |
408 | "heap1's data and heap4's data should match"; | |
409 | EXPECT_EQ(current, heap10.top().data) << | |
410 | "heap1's data and heap10's data should match"; | |
411 | ||
412 | heap2.pop(); | |
413 | heap3.pop(); | |
414 | heap4.pop(); | |
415 | heap10.pop(); | |
416 | ||
417 | bound = current; | |
418 | } | |
419 | ||
420 | EXPECT_TRUE(heap2.empty()) << "should be empty after all elements popped"; | |
421 | EXPECT_TRUE(heap3.empty()) << "should be empty after all elements popped"; | |
422 | EXPECT_TRUE(heap4.empty()) << "should be empty after all elements popped"; | |
423 | EXPECT_TRUE(heap10.empty()) << "should be empty after all elements popped"; | |
424 | } | |
425 | ||
426 | ||
427 | TEST(IndIntruHeap, demote) { | |
428 | crimson::IndIntruHeap<std::unique_ptr<Elem>, | |
429 | Elem, | |
430 | &Elem::heap_data, | |
431 | ElemCompare> heap; | |
432 | ||
433 | heap.push(std::unique_ptr<Elem>(new Elem(2))); | |
434 | heap.push(std::unique_ptr<Elem>(new Elem(99))); | |
435 | heap.push(std::unique_ptr<Elem>(new Elem(1))); | |
436 | heap.push(std::unique_ptr<Elem>(new Elem(-5))); | |
437 | heap.push(std::unique_ptr<Elem>(new Elem(12))); | |
438 | heap.push(std::unique_ptr<Elem>(new Elem(-12))); | |
439 | heap.push(std::unique_ptr<Elem>(new Elem(-7))); | |
440 | ||
441 | heap.top().data = 24; | |
442 | ||
443 | heap.demote(heap.top()); | |
444 | ||
445 | EXPECT_EQ(-7, heap.top().data); | |
446 | ||
447 | heap.pop(); | |
448 | heap.pop(); | |
449 | heap.pop(); | |
450 | heap.pop(); | |
451 | heap.pop(); | |
452 | ||
453 | EXPECT_EQ(24, heap.top().data); | |
454 | } | |
455 | ||
456 | ||
457 | TEST(IndIntruHeap, demote_not) { | |
458 | crimson::IndIntruHeap<std::unique_ptr<Elem>, | |
459 | Elem, | |
460 | &Elem::heap_data, | |
461 | ElemCompare> heap; | |
462 | ||
463 | heap.push(std::unique_ptr<Elem>(new Elem(2))); | |
464 | heap.push(std::unique_ptr<Elem>(new Elem(99))); | |
465 | heap.push(std::unique_ptr<Elem>(new Elem(1))); | |
466 | heap.push(std::unique_ptr<Elem>(new Elem(-5))); | |
467 | heap.push(std::unique_ptr<Elem>(new Elem(12))); | |
468 | heap.push(std::unique_ptr<Elem>(new Elem(-12))); | |
469 | heap.push(std::unique_ptr<Elem>(new Elem(-7))); | |
470 | ||
471 | heap.top().data = -99; | |
472 | ||
473 | heap.demote(heap.top()); | |
474 | ||
475 | EXPECT_EQ(-99, heap.top().data); | |
476 | ||
477 | heap.pop(); | |
478 | ||
479 | EXPECT_EQ(-7, heap.top().data); | |
480 | } | |
481 | ||
482 | ||
483 | TEST(IndIntruHeap, promote_and_demote) { | |
484 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
485 | Elem, | |
486 | &Elem::heap_data, | |
487 | ElemCompare> heap; | |
488 | ||
489 | auto data1 = std::make_shared<Elem>(1); | |
490 | ||
491 | heap.push(std::make_shared<Elem>(2)); | |
492 | heap.push(std::make_shared<Elem>(99)); | |
493 | heap.push(data1); | |
494 | heap.push(std::make_shared<Elem>(-5)); | |
495 | heap.push(std::make_shared<Elem>(12)); | |
496 | heap.push(std::make_shared<Elem>(-12)); | |
497 | heap.push(std::make_shared<Elem>(-7)); | |
498 | ||
499 | EXPECT_EQ(-12, heap.top().data); | |
500 | ||
501 | data1->data = -99; | |
502 | heap.promote(*data1); | |
503 | ||
504 | EXPECT_EQ(-99, heap.top().data); | |
505 | ||
506 | data1->data = 999; | |
507 | heap.demote(*data1); | |
508 | ||
509 | EXPECT_EQ(-12, heap.top().data); | |
510 | ||
511 | data1->data = 9; | |
512 | heap.promote(*data1); | |
513 | ||
514 | heap.pop(); // remove -12 | |
515 | heap.pop(); // remove -7 | |
516 | heap.pop(); // remove -5 | |
517 | heap.pop(); // remove 2 | |
518 | ||
519 | EXPECT_EQ(9, heap.top().data); | |
520 | } | |
521 | ||
522 | ||
523 | TEST(IndIntruHeap, adjust) { | |
524 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
525 | Elem, | |
526 | &Elem::heap_data, | |
527 | ElemCompare> heap; | |
528 | ||
529 | auto data1 = std::make_shared<Elem>(1); | |
530 | ||
531 | heap.push(std::make_shared<Elem>(2)); | |
532 | heap.push(std::make_shared<Elem>(99)); | |
533 | heap.push(data1); | |
534 | heap.push(std::make_shared<Elem>(-5)); | |
535 | heap.push(std::make_shared<Elem>(12)); | |
536 | heap.push(std::make_shared<Elem>(-12)); | |
537 | heap.push(std::make_shared<Elem>(-7)); | |
538 | ||
539 | // heap.display_sorted(std::cout); | |
540 | ||
541 | EXPECT_EQ(-12, heap.top().data); | |
542 | ||
543 | data1->data = 999; | |
544 | heap.adjust(*data1); | |
545 | ||
546 | EXPECT_EQ(-12, heap.top().data); | |
547 | ||
548 | data1->data = -99; | |
549 | heap.adjust(*data1); | |
550 | ||
551 | EXPECT_EQ(-99, heap.top().data); | |
552 | ||
553 | data1->data = 9; | |
554 | heap.adjust(*data1); | |
555 | ||
556 | EXPECT_EQ(-12, heap.top().data); | |
557 | ||
558 | heap.pop(); // remove -12 | |
559 | heap.pop(); // remove -7 | |
560 | heap.pop(); // remove -5 | |
561 | heap.pop(); // remove 2 | |
562 | ||
563 | EXPECT_EQ(9, heap.top().data); | |
564 | } | |
565 | ||
566 | ||
567 | TEST(IndIntruHeap, remove_careful) { | |
568 | // here we test whether a common mistake in implementing remove is | |
569 | // done; if after we remove an item and move the last element of the | |
570 | // heap to the position of the removed element, we need to sift it | |
571 | // rather than sift_down it. | |
572 | ||
573 | crimson::IndIntruHeap<std::shared_ptr<Elem>, | |
574 | Elem, | |
575 | &Elem::heap_data, | |
576 | ElemCompare, | |
577 | 2> heap; | |
578 | ||
579 | heap.push(std::make_shared<Elem>(0)); | |
580 | heap.push(std::make_shared<Elem>(10)); | |
581 | heap.push(std::make_shared<Elem>(100)); | |
582 | heap.push(std::make_shared<Elem>(20)); | |
583 | heap.push(std::make_shared<Elem>(30)); | |
584 | heap.push(std::make_shared<Elem>(200)); | |
585 | heap.push(std::make_shared<Elem>(300)); | |
586 | heap.push(std::make_shared<Elem>(40)); | |
587 | ||
588 | auto k = heap.find(Elem(200)); | |
589 | EXPECT_NE(heap.end(), k) << | |
590 | "we should have found an element with the value 200, which we'll remove"; | |
591 | heap.remove(k); | |
592 | ||
593 | auto i = heap.cbegin(); | |
594 | EXPECT_EQ(0, i->data); | |
595 | ++i; | |
596 | EXPECT_EQ(10, i->data); | |
597 | ++i; | |
598 | EXPECT_EQ(40, i->data) << | |
599 | "this needs to be 40 or there's a mistake in implementation"; | |
600 | ++i; | |
601 | EXPECT_EQ(20, i->data); | |
602 | ++i; | |
603 | EXPECT_EQ(30, i->data); | |
604 | ++i; | |
605 | EXPECT_EQ(100, i->data) << | |
606 | "this needs to be 100 or there's a mistake in implementation"; | |
607 | } | |
608 | ||
609 | ||
610 | TEST_F(HeapFixture1, shared_data) { | |
611 | ||
612 | crimson::IndIntruHeap<std::shared_ptr<Elem>,Elem,&Elem::heap_data_alt,ElemCompareAlt> heap2; | |
613 | ||
614 | heap2.push(data1); | |
615 | heap2.push(data2); | |
616 | heap2.push(data3); | |
617 | heap2.push(data4); | |
618 | heap2.push(data5); | |
619 | heap2.push(data6); | |
620 | heap2.push(data7); | |
621 | ||
622 | data3->data = 32; | |
623 | heap.adjust(*data3); | |
624 | heap2.adjust(*data3); | |
625 | ||
626 | EXPECT_EQ(-12, heap.top().data); | |
627 | heap.pop(); | |
628 | EXPECT_EQ(-7, heap.top().data); | |
629 | heap.pop(); | |
630 | EXPECT_EQ(-5, heap.top().data); | |
631 | heap.pop(); | |
632 | EXPECT_EQ(2, heap.top().data); | |
633 | heap.pop(); | |
634 | EXPECT_EQ(12, heap.top().data); | |
635 | heap.pop(); | |
636 | EXPECT_EQ(32, heap.top().data); | |
637 | heap.pop(); | |
638 | EXPECT_EQ(99, heap.top().data); | |
639 | ||
640 | EXPECT_EQ(32, heap2.top().data); | |
641 | heap2.pop(); | |
642 | EXPECT_EQ(12, heap2.top().data); | |
643 | heap2.pop(); | |
644 | EXPECT_EQ(2, heap2.top().data); | |
645 | heap2.pop(); | |
646 | EXPECT_EQ(-12, heap2.top().data); | |
647 | heap2.pop(); | |
648 | EXPECT_EQ(99, heap2.top().data); | |
649 | heap2.pop(); | |
650 | EXPECT_EQ(-5, heap2.top().data); | |
651 | heap2.pop(); | |
652 | EXPECT_EQ(-7, heap2.top().data); | |
653 | } | |
654 | ||
655 | ||
656 | TEST_F(HeapFixture1, iterator_basics) { | |
657 | { | |
658 | uint count = 0; | |
659 | for(auto i = heap.begin(); i != heap.end(); ++i) { | |
660 | ++count; | |
661 | } | |
662 | ||
663 | EXPECT_EQ(7u, count) << "count should be 7"; | |
664 | } | |
665 | ||
666 | auto i1 = heap.begin(); | |
667 | ||
668 | EXPECT_EQ(-12, i1->data) << | |
669 | "first member with * operator must be smallest"; | |
670 | ||
671 | EXPECT_EQ(-12, (*i1).data) << | |
672 | "first member with -> operator must be smallest"; | |
673 | ||
674 | Elem& e1 = *i1; | |
675 | EXPECT_EQ(-12, e1.data) << | |
676 | "first member with -> operator must be smallest"; | |
677 | ||
678 | { | |
679 | std::set<int> values; | |
680 | values.insert(2); | |
681 | values.insert(99); | |
682 | values.insert(1); | |
683 | values.insert(-5); | |
684 | values.insert(12); | |
685 | values.insert(-12); | |
686 | values.insert(-7); | |
687 | ||
688 | for(auto i = heap.begin(); i != heap.end(); ++i) { | |
689 | auto v = *i; | |
690 | EXPECT_NE(values.end(), values.find(v.data)) << | |
691 | "value in heap must be part of original set"; | |
692 | values.erase(v.data); | |
693 | } | |
694 | EXPECT_EQ(0u, values.size()) << "all values must have been seen"; | |
695 | } | |
696 | } | |
697 | ||
698 | ||
699 | TEST_F(HeapFixture1, const_iterator_basics) { | |
700 | const auto& cheap = heap; | |
701 | ||
702 | { | |
703 | uint count = 0; | |
704 | for(auto i = cheap.cbegin(); i != cheap.cend(); ++i) { | |
705 | ++count; | |
706 | } | |
707 | ||
708 | EXPECT_EQ(7u, count) << "count should be 7"; | |
709 | } | |
710 | ||
711 | auto i1 = heap.cbegin(); | |
712 | ||
713 | EXPECT_EQ(-12, i1->data) << | |
714 | "first member with * operator must be smallest"; | |
715 | ||
716 | EXPECT_EQ(-12, (*i1).data) << | |
717 | "first member with -> operator must be smallest"; | |
718 | ||
719 | const Elem& e1 = *i1; | |
720 | EXPECT_EQ(-12, e1.data) << | |
721 | "first member with -> operator must be smallest"; | |
722 | ||
723 | { | |
724 | std::set<int> values; | |
725 | values.insert(2); | |
726 | values.insert(99); | |
727 | values.insert(1); | |
728 | values.insert(-5); | |
729 | values.insert(12); | |
730 | values.insert(-12); | |
731 | values.insert(-7); | |
732 | ||
733 | for(auto i = heap.cbegin(); i != heap.cend(); ++i) { | |
734 | auto v = *i; | |
735 | EXPECT_NE(values.end(), values.find(v.data)) << | |
736 | "value in heap must be part of original set"; | |
737 | values.erase(v.data); | |
738 | } | |
739 | EXPECT_EQ(0u, values.size()) << "all values must have been seen"; | |
740 | } | |
741 | } | |
742 | ||
743 | ||
744 | TEST_F(HeapFixture1, iterator_find_rfind) { | |
745 | { | |
746 | auto it1 = heap.find(data7); | |
747 | EXPECT_NE(heap.end(), it1) << | |
748 | "find by indirection for included element should succeed"; | |
749 | EXPECT_EQ(-7, it1->data) << | |
750 | "find by indirection for included element should result in right value"; | |
751 | ||
752 | auto fake_data = std::make_shared<Elem>(-7); | |
753 | auto it2 = heap.find(fake_data); | |
754 | EXPECT_EQ(heap.end(), it2) << | |
755 | "find by indirection for not included element should fail"; | |
756 | } | |
757 | ||
758 | { | |
759 | auto it1 = heap.find(Elem(-7)); | |
760 | EXPECT_NE(heap.end(), it1) << | |
761 | "find by value for included element should succeed"; | |
762 | EXPECT_EQ(-7, it1->data) << | |
763 | "find by value for included element should result in right value"; | |
764 | ||
765 | auto it2 = heap.find(Elem(7)); | |
766 | EXPECT_EQ(heap.end(), it2) << | |
767 | "find by value for not included element should fail"; | |
768 | } | |
769 | ||
770 | { | |
771 | auto it1 = heap.rfind(data7); | |
772 | EXPECT_NE(heap.end(), it1) << | |
773 | "reverse find by indirecton for included element should succeed"; | |
774 | EXPECT_EQ(-7, it1->data) << | |
775 | "reverse find by indirection for included element should result " | |
776 | "in right value"; | |
777 | ||
778 | auto fake_data = std::make_shared<Elem>(-7); | |
779 | auto it2 = heap.rfind(fake_data); | |
780 | EXPECT_EQ(heap.end(), it2) << | |
781 | "reverse find by indirection for not included element should fail"; | |
782 | } | |
783 | ||
784 | { | |
785 | auto it1 = heap.rfind(Elem(-7)); | |
786 | EXPECT_NE(heap.end(), it1) << | |
787 | "reverse find by value for included element should succeed"; | |
788 | EXPECT_EQ(-7, it1->data) << | |
789 | "reverse find by value for included element should result " | |
790 | "in right value"; | |
791 | ||
792 | auto it2 = heap.rfind(Elem(7)); | |
793 | EXPECT_EQ(heap.end(), it2) << | |
794 | "reverse find by value for not included element should fail"; | |
795 | } | |
796 | } | |
797 | ||
798 | ||
799 | TEST_F(HeapFixture1, const_iterator_find_rfind) { | |
800 | const auto& c_heap = heap; | |
801 | ||
802 | { | |
803 | auto it1 = c_heap.find(data7); | |
804 | EXPECT_NE(c_heap.cend(), it1) << | |
805 | "find by indirection for included element should succeed"; | |
806 | EXPECT_EQ(-7, it1->data) << | |
807 | "find by indirection for included element should result in right value"; | |
808 | ||
809 | auto fake_data = std::make_shared<Elem>(-7); | |
810 | auto it2 = c_heap.find(fake_data); | |
811 | EXPECT_EQ(c_heap.cend(), it2) << | |
812 | "find by indirection for not included element should fail"; | |
813 | } | |
814 | ||
815 | { | |
816 | auto it1 = c_heap.find(Elem(-7)); | |
817 | EXPECT_NE(c_heap.cend(), it1) << | |
818 | "find by value for included element should succeed"; | |
819 | EXPECT_EQ(-7, it1->data) << | |
820 | "find by value for included element should result in right value"; | |
821 | ||
822 | auto it2 = c_heap.find(Elem(7)); | |
823 | EXPECT_EQ(c_heap.cend(), it2) << | |
824 | "find by value for not included element should fail"; | |
825 | } | |
826 | ||
827 | { | |
828 | auto it1 = c_heap.rfind(data7); | |
829 | EXPECT_NE(c_heap.cend(), it1) << | |
830 | "reverse find by indirecton for included element should succeed"; | |
831 | EXPECT_EQ(-7, it1->data) << | |
832 | "reverse find by indirection for included element should result " | |
833 | "in right value"; | |
834 | ||
835 | auto fake_data = std::make_shared<Elem>(-7); | |
836 | auto it2 = c_heap.rfind(fake_data); | |
837 | EXPECT_EQ(c_heap.cend(), it2) << | |
838 | "reverse find by indirection for not included element should fail"; | |
839 | } | |
840 | ||
841 | { | |
842 | auto it1 = c_heap.rfind(Elem(-7)); | |
843 | EXPECT_NE(c_heap.cend(), it1) << | |
844 | "reverse find by value for included element should succeed"; | |
845 | EXPECT_EQ(-7, it1->data) << | |
846 | "reverse find by value for included element should result " | |
847 | "in right value"; | |
848 | ||
849 | auto it2 = c_heap.rfind(Elem(7)); | |
850 | EXPECT_EQ(c_heap.cend(), it2) << | |
851 | "reverse find by value for not included element should fail"; | |
852 | } | |
853 | } | |
854 | ||
855 | ||
856 | TEST_F(HeapFixture1, iterator_remove) { | |
857 | auto it1 = heap.find(data7); | |
858 | EXPECT_NE(heap.end(), it1) << "find for included element should succeed"; | |
859 | ||
860 | heap.remove(it1); | |
861 | ||
862 | auto it2 = heap.find(data7); | |
863 | EXPECT_EQ(heap.end(), it2) << "find for removed element should fail"; | |
864 | ||
865 | for (auto it3 = heap.begin(); it3 != heap.end(); ++it3) { | |
866 | EXPECT_NE(-7, it3->data) << | |
867 | "iterating through heap should not find removed value"; | |
868 | } | |
869 | ||
870 | // move through heap without -7 | |
871 | EXPECT_EQ(-12, heap.top().data); | |
872 | heap.pop(); | |
873 | EXPECT_EQ(-5, heap.top().data); | |
874 | heap.pop(); | |
875 | EXPECT_EQ(1, heap.top().data); | |
876 | heap.pop(); | |
877 | EXPECT_EQ(2, heap.top().data); | |
878 | heap.pop(); | |
879 | EXPECT_EQ(12, heap.top().data); | |
880 | heap.pop(); | |
881 | EXPECT_EQ(99, heap.top().data); | |
882 | heap.pop(); | |
883 | } | |
884 | ||
885 | ||
886 | TEST_F(HeapFixture1, four_tops) { | |
887 | Elem& top1 = heap.top(); | |
888 | EXPECT_EQ(-12, top1.data); | |
889 | ||
890 | const Elem& top2 = heap.top(); | |
891 | EXPECT_EQ(-12, top2.data); | |
892 | ||
893 | std::shared_ptr<Elem> top3 = heap.top_ind(); | |
894 | EXPECT_EQ(-12, top3->data); | |
895 | ||
896 | const std::shared_ptr<Elem> top4 = heap.top_ind(); | |
897 | EXPECT_EQ(-12, top4->data); | |
898 | ||
899 | const auto& c_heap = heap; | |
900 | ||
901 | const Elem& top5 = c_heap.top(); | |
902 | EXPECT_EQ(-12, top5.data); | |
903 | ||
904 | const std::shared_ptr<Elem> top6 = c_heap.top_ind(); | |
905 | EXPECT_EQ(-12, top6->data); | |
906 | } | |
907 | ||
908 | ||
909 | TEST_F(HeapFixture1, display_sorted) { | |
910 | std::stringstream ss; | |
911 | ||
912 | heap.display_sorted(ss); | |
913 | ||
914 | std::string s = ss.str(); | |
915 | ||
916 | EXPECT_GT(s.length(), 0u); | |
917 | ||
918 | auto negseven = s.find("-7"); | |
919 | EXPECT_NE(negseven, std::string::npos); | |
920 | ||
921 | auto ninetynine = s.find("99"); | |
922 | EXPECT_NE(ninetynine, std::string::npos); | |
923 | ||
924 | // index of -7 should be less than index of 99 | |
925 | EXPECT_LT(negseven, ninetynine); | |
926 | ||
927 | #if 0 | |
928 | std::cout << s << std::endl; | |
929 | #endif | |
930 | } |