1 /* Copyright (c) 2014, 2021, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23 // First include (the generated) my_config.h, to get correct platform defines.
24 #include "my_config.h"
25 #include <gtest/gtest.h>
26 #include <algorithm>
27 #include <functional>
28 #include <iostream>
29 #include <sstream>
30 #include <iterator>
31 #include <vector>
32
33 #include "priority_queue.h"
34
35 namespace priority_queue_unittest {
36
37 // random integer generator -- start
38 template <typename IntegerType>
39 class random_integer_generator
40 {
41 public:
random_integer_generator(unsigned int seed=0)42 random_integer_generator(unsigned int seed = 0)
43 {
44 srand(seed);
45 }
46
operator ()(IntegerType const & low,IntegerType const & high)47 IntegerType operator()(IntegerType const& low,
48 IntegerType const& high)
49 {
50 IntegerType i = rand() % (high - low + 1);
51 i += low;
52 return i;
53 }
54 };
55 // random integer generator -- end
56
57
58 //--------------------------------------------------------
59
60
61 // handle support -- start
62 template <typename T>
63 struct handle
64 {
65 T* ptr;
66
handlepriority_queue_unittest::handle67 handle() : ptr(NULL) {}
handlepriority_queue_unittest::handle68 handle(T& t) : ptr(&t) {}
69 };
70
71
72 template <typename T>
operator <<(std::ostream & os,handle<T> const & h)73 inline std::ostream& operator<<(std::ostream& os, handle<T> const& h)
74 {
75 os << *h.ptr;
76 return os;
77 }
78
79 template
80 <
81 typename Handle,
82 typename Value,
83 typename Less = std::less<Value>
84 >
85 struct handle_less
86 {
operator ()priority_queue_unittest::handle_less87 inline bool operator()(Handle const& p1, Handle const& p2) const
88 {
89 return Less()(*p1.ptr, *p2.ptr);
90 }
91 };
92 // handle support -- end
93
94
95 //--------------------------------------------------------
96
97
98 // dummy stream that "eats" all input
99 struct null_stream : public std::ostream
100 {
101 // Visual Studio needs a default constructor.
null_streampriority_queue_unittest::null_stream102 null_stream() : std::ostream(NULL) {}
103 };
104
105
106 template <typename T>
operator <<(null_stream & ns,T const &)107 inline null_stream& operator<<(null_stream& ns, T const&)
108 {
109 return ns;
110 }
111
112
113 //--------------------------------------------------------
114
115
116 // i/o support -- start
117 template <typename InputIterator>
print_range(std::ostream & os,InputIterator first,InputIterator last)118 inline void print_range(std::ostream& os,
119 InputIterator first,
120 InputIterator last)
121 {
122 for (InputIterator it = first; it != last; ++it)
123 {
124 os << " " << *it;
125 }
126 os << std::endl;
127 }
128
129 template <typename InputIterator>
print_range(std::ostream & os,std::string const & header,InputIterator first,InputIterator last)130 inline void print_range(std::ostream& os,
131 std::string const& header,
132 InputIterator first,
133 InputIterator last)
134 {
135 os << header;
136 print_range(os, first, last);
137 }
138 // i/o support -- end
139
140
141 //--------------------------------------------------------
142
143
144 // Some template functions below do not play well with gtest internals
assert_true_helper(bool val)145 static void assert_true_helper(bool val)
146 {
147 ASSERT_TRUE(val);
148 }
149
150
151 // k min elements algorithm -- start
152 template <bool UseSorting>
153 struct min_k_elements
154 {
155 template <typename InputIterator, typename OutputIterator>
applypriority_queue_unittest::min_k_elements156 static inline OutputIterator apply(InputIterator first,
157 InputIterator last,
158 size_t k,
159 OutputIterator oit)
160 {
161 SCOPED_TRACE("");
162 assert_true_helper(static_cast<size_t>(std::distance(first, last)) > k);
163
164 typedef typename std::iterator_traits
165 <
166 InputIterator
167 >::value_type value_type;
168
169 std::vector<value_type> values;
170
171 // copy locally
172 std::copy(first, last, std::back_inserter(values));
173
174 // sort
175 std::sort(values.begin(), values.end());
176
177 // output k smallest values
178 std::copy(values.begin(), values.begin() + k, oit);
179 return oit;
180 }
181 };
182
183
184
185 template <>
186 struct min_k_elements<false>
187 {
188 template <typename RandomAccessIterator, typename OutputIterator>
applypriority_queue_unittest::min_k_elements189 static inline OutputIterator apply(RandomAccessIterator first,
190 RandomAccessIterator last,
191 size_t k,
192 OutputIterator oit)
193 {
194 SCOPED_TRACE("");
195 assert_true_helper(static_cast<size_t>(std::distance(first, last)) > k);
196
197 typedef typename std::iterator_traits
198 <
199 RandomAccessIterator
200 >::value_type value_type;
201
202 typedef handle<value_type> handle_type;
203
204 typedef handle_less
205 <
206 handle_type, value_type, std::less<value_type>
207 > handle_less_type;
208
209 typedef Priority_queue
210 <
211 handle_type,
212 std::vector<handle_type>,
213 handle_less_type
214 > queue_type;
215
216 typedef typename queue_type::const_iterator queue_iterator;
217
218 // copy k + 1 values locally
219 std::vector<value_type> values;
220 values.reserve(k + 1);
221
222 std::copy(first, first + k + 1, std::back_inserter(values));
223
224 // create a queue of k + 1 handles to the local values
225 queue_type queue;
226 assert_true_helper(!queue.reserve(k + 1));
227
228 for (size_t i = 0; i < k + 1; ++i)
229 {
230 EXPECT_FALSE(queue.push(handle_type(values[i])));
231 }
232 SCOPED_TRACE("");
233 assert_true_helper(queue.is_valid());
234
235 // for the remaining values update the queue's root node
236 // and rebuild the heap
237 for (RandomAccessIterator it = first + k + 1; it != last; ++it)
238 {
239 *queue[0].ptr = *it;
240 queue.update(0);
241 }
242
243 // output the k minimum values (all but the root)
244 for (queue_iterator it = ++queue.begin(); it != queue.end(); ++it)
245 {
246 *oit++ = *it->ptr;
247 }
248
249 return oit;
250 }
251 };
252 // k min elements algorithm -- end
253
254
255 //--------------------------------------------------------
256
257
258 template <typename RandomAccessIterator>
test_min_k_elements(RandomAccessIterator first,RandomAccessIterator last,size_t k)259 inline void test_min_k_elements(RandomAccessIterator first,
260 RandomAccessIterator last,
261 size_t k)
262 {
263 std::vector<int> keys_copy(first, last);
264 std::sort(keys_copy.begin(), keys_copy.end());
265
266 #ifdef PRIORITY_QUEUE_TEST_DEBUG
267 std::ostream& os = std::cout;
268 #else
269 null_stream os;
270 #endif
271
272 print_range(os, "elements: ", first, last);
273
274 print_range(os, "sorted elements: ", keys_copy.begin(), keys_copy.end());
275 os << std::endl;
276
277 std::vector<int> min_elements_sort, min_elements_heap;
278
279 // using the heap
280 min_k_elements<false>::apply(first, last, k,
281 std::back_inserter(min_elements_heap));
282
283 os << "min " << k << " elements (heap): ";
284 print_range(os, min_elements_heap.begin(), min_elements_heap.end());
285
286 std::sort(min_elements_heap.begin(), min_elements_heap.end());
287 os << "min " << k << " elements (hp/s): ";
288 print_range(os, min_elements_heap.begin(), min_elements_heap.end());
289 os << std::endl;
290
291 // using sorting
292 min_k_elements<true>::apply(first, last, k,
293 std::back_inserter(min_elements_sort));
294
295 os << "min " << k << " elements (sort): ";
296 print_range(os, min_elements_sort.begin(), min_elements_sort.end());
297 os << std::endl;
298
299 ASSERT_TRUE(std::equal(min_elements_sort.begin(),
300 min_elements_sort.end(),
301 min_elements_heap.begin()));
302 }
303
304
305 //--------------------------------------------------------
306
307 template <typename Queue>
print_update_msg(std::ostream & os,std::string header,Queue const & q,typename Queue::size_type pos,typename Queue::value_type const & old_value,typename Queue::value_type const & new_value)308 inline void print_update_msg(std::ostream& os,
309 std::string header,
310 Queue const& q,
311 typename Queue::size_type pos,
312 typename Queue::value_type const& old_value,
313 typename Queue::value_type const& new_value)
314 {
315 os << header
316 << " priority of element " << old_value
317 << " at position " << pos
318 << " to new value " << new_value
319 << "; new_queue: " << q
320 << std::endl;
321 }
322
323
324 template <typename RandomAccessIterator>
test_heap(RandomAccessIterator first,RandomAccessIterator last)325 inline void test_heap(RandomAccessIterator first, RandomAccessIterator last)
326 {
327 typedef typename std::iterator_traits
328 <
329 RandomAccessIterator
330 >::value_type value_type;
331
332 typedef Priority_queue<value_type> queue;
333 typedef typename queue::size_type size_type;
334 typedef typename queue::iterator iterator;
335 typedef typename queue::const_iterator const_iterator;
336
337 #ifdef PRIORITY_QUEUE_TEST_DEBUG
338 std::ostream& os = std::cout;
339 #else
340 null_stream os;
341 #endif
342
343 queue pq;
344
345 for (RandomAccessIterator it = first; it != last; ++it)
346 {
347 EXPECT_FALSE(pq.push(*it));
348 ASSERT_TRUE(pq.is_valid());
349 os << "queue: " << pq << std::endl;
350 }
351
352 // test constructor with iterators
353 {
354 queue pq2(first, last);
355 ASSERT_TRUE(pq2.is_valid());
356 os << "queue (constructor with iterators): "
357 << pq2
358 << std::endl;
359 }
360
361 // test top
362 os << "top element: " << pq.top() << std::endl;
363 ASSERT_TRUE(pq.top() == pq[0]);
364
365 // test push
366 value_type new_value = *std::min_element(pq.begin(), pq.end()) - 1;
367 EXPECT_FALSE(pq.push(new_value));
368 ASSERT_TRUE(pq.is_valid());
369 os << "pushed " << new_value << "; new queue: " << pq << std::endl;
370
371 // test pop
372 pq.pop();
373 ASSERT_TRUE(pq.is_valid());
374 os << "popped top element; new queue: " << pq << std::endl;
375
376 // test decrease
377 // decrease priority of element at position 3
378 {
379 size_type pos = 3;
380 value_type old_priority = pq[pos];
381 value_type new_priority = pq[pos];
382 pq.decrease(pos, new_priority);
383 ASSERT_TRUE(pq.is_valid());
384 print_update_msg(os, "decreasing (2)", pq, pos,
385 old_priority, new_priority);
386
387 old_priority = pq[pos];
388 new_priority = pq[pos];
389 *(pq.begin() + pos) = new_priority;
390 pq.decrease(pos);
391 ASSERT_TRUE(pq.is_valid());
392 print_update_msg(os, "decreasing (1)", pq, pos,
393 old_priority, new_priority);
394
395 old_priority = pq[pos];
396 new_priority = pq[pos] - 10;
397 pq.decrease(pos, new_priority);
398 ASSERT_TRUE(pq.is_valid());
399 print_update_msg(os, "decreasing (2)", pq, pos,
400 old_priority, new_priority);
401
402 old_priority = pq[pos];
403 new_priority = pq[pos] - 20;
404 pq[pos] = new_priority;
405 pq.decrease(pos);
406 ASSERT_TRUE(pq.is_valid());
407 print_update_msg(os, "decreasing (1)", pq, pos,
408 old_priority, new_priority);
409 }
410
411 // test increase
412 // increase priority of element at position 4
413 {
414 size_type pos = 4;
415 value_type old_priority = pq[pos];
416 value_type new_priority = pq[pos];
417 pq.increase(pos, new_priority);
418 ASSERT_TRUE(pq.is_valid());
419 print_update_msg(os, "increasing (2)", pq, pos,
420 old_priority, new_priority);
421
422 old_priority = pq[pos];
423 new_priority = pq[pos];
424 *(pq.begin() + pos) = new_priority;
425 pq.increase(pos);
426 ASSERT_TRUE(pq.is_valid());
427 print_update_msg(os, "increasing (1)", pq, pos,
428 old_priority, new_priority);
429
430 old_priority = pq[pos];
431 new_priority = pq[pos] + 30;
432 pq.increase(pos, new_priority);
433 ASSERT_TRUE(pq.is_valid());
434 print_update_msg(os, "increasing (2)", pq, pos,
435 old_priority, new_priority);
436
437 old_priority = pq[pos];
438 new_priority = pq[pos] + 50;
439 pq[pos] = new_priority;
440 pq.increase(pos);
441 ASSERT_TRUE(pq.is_valid());
442 print_update_msg(os, "increasing (1)", pq, pos,
443 old_priority, new_priority);
444 }
445
446 // test update
447 // update priority of element at position 2
448 {
449 size_type pos = 2;
450 value_type old_priority = pq[pos];
451 value_type new_priority = pq[pos];
452 pq.update(pos, new_priority);
453 ASSERT_TRUE(pq.is_valid());
454 print_update_msg(os, "updating (2)", pq, pos,
455 old_priority, new_priority);
456
457 old_priority = pq[pos];
458 new_priority = pq[pos];
459 *(pq.begin() + pos) = new_priority;
460 pq.update(pos);
461 ASSERT_TRUE(pq.is_valid());
462 print_update_msg(os, "updating (1)", pq, pos,
463 old_priority, new_priority);
464
465 old_priority = pq[pos];
466 new_priority = pq[pos] - 20;
467 *(pq.begin() + pos) = new_priority;
468 pq.update(pos);
469 ASSERT_TRUE(pq.is_valid());
470 print_update_msg(os, "updating (2)", pq, pos,
471 old_priority, new_priority);
472
473 old_priority = pq[pos];
474 new_priority = pq[pos] + 100;
475 pq[pos] = new_priority;
476 pq.update(pos);
477 ASSERT_TRUE(pq.is_valid());
478 print_update_msg(os, "updating (1)", pq, pos,
479 old_priority, new_priority);
480 }
481
482 // test size
483 ASSERT_TRUE(pq.size() ==
484 static_cast<size_t>(std::distance(first, last)));
485 ASSERT_TRUE(pq.is_valid());
486 os << "size: " << pq.size() << std::endl;
487
488 // test empty
489 ASSERT_TRUE(!pq.empty());
490 ASSERT_TRUE(pq.is_valid());
491 os << "empty? " << std::boolalpha << pq.empty()
492 << std::noboolalpha << std::endl;
493
494 // print all elements in queue using operator[]
495 os << "queue (using operator[]):";
496 for (size_type i = 0; i < pq.size(); ++i)
497 {
498 os << " " << pq[i];
499 }
500 os << std::endl;
501
502 // print all elements in queue using const/non-const iterators
503 os << "queue (using const iterators):";
504 for (const_iterator it = pq.begin(); it != pq.end(); ++it)
505 {
506 os << " " << *it;
507 }
508 os << std::endl;
509
510 os << "queue (using non-const iterators):";
511 for (iterator it = pq.begin(); it != pq.end(); ++it)
512 {
513 os << " " << *it;
514 }
515 os << std::endl;
516
517 // testing swap
518 queue other;
519
520 ASSERT_TRUE(pq.is_valid() && !pq.empty());
521 ASSERT_TRUE(other.is_valid() && other.empty());
522 os << "before swap: " << pq << "; " << other << std::endl;
523 pq.swap(other);
524 ASSERT_TRUE(pq.is_valid() && pq.empty());
525 ASSERT_TRUE(other.is_valid() && !other.empty());
526 os << "after swap: " << pq << "; " << other << std::endl;
527
528 // clear the heap
529 pq.clear();
530 ASSERT_TRUE(pq.is_valid());
531 ASSERT_TRUE(pq.empty());
532 os << "clearing the queue" << std::endl;
533
534 // reserve 10 heap elements and push 10 elements in the heap
535 os << "testing reserve" << std::endl;
536 ASSERT_TRUE(pq.empty());
537 ASSERT_FALSE(pq.reserve(2 * pq.capacity()));
538 ASSERT_TRUE(pq.empty());
539 for (size_type i = 0;
540 i < static_cast<size_t>(std::distance(first, last)); ++i)
541 {
542 ASSERT_TRUE(pq.size() == i);
543 EXPECT_FALSE(pq.push(*(last - 1 - i)));
544 ASSERT_TRUE(pq.is_valid());
545 os << "queue: " << pq << std::endl;
546 }
547
548 // now use the non-const top() method to update the root element
549 os << "testing non-const top()" << std::endl;
550 {
551 value_type old_priority = pq.top();
552 value_type new_priority = pq.top() - 40;
553 pq.top() = pq.top() - 40;
554 pq.update(0);
555 ASSERT_TRUE(pq.is_valid());
556 print_update_msg(os, "updating (using top)", pq, 0,
557 old_priority, new_priority);
558 }
559 }
560
561
562 //--------------------------------------------------------
563
564
565 template <typename RandomAccessIterator>
test_heap_of_handles(RandomAccessIterator first,RandomAccessIterator last)566 inline void test_heap_of_handles(RandomAccessIterator first,
567 RandomAccessIterator last)
568 {
569 typedef typename std::iterator_traits
570 <
571 RandomAccessIterator
572 >::value_type value_type;
573
574 typedef handle<value_type> handle_type;
575
576 typedef handle_less
577 <
578 handle_type, value_type, std::greater<value_type>
579 > handle_greater_type;
580
581 typedef Priority_queue
582 <
583 handle_type,
584 std::vector<handle_type>,
585 handle_less<handle_type, value_type>
586 > queue;
587
588 typedef typename queue::const_iterator const_iterator;
589
590 #ifdef PRIORITY_QUEUE_TEST_DEBUG
591 std::ostream& os = std::cout;
592 #else
593 null_stream os;
594 #endif
595
596 size_t const N = static_cast<size_t>(std::distance(first, last));
597
598 std::vector<handle_type> handles;
599 for (size_t i = 0; i < N; ++i)
600 {
601 handles.push_back(handle_type(*(first + i)));
602 }
603 for (size_t i = 0; i < N; ++i)
604 {
605 os << handles[i] << std::endl;
606 }
607
608 queue pq;
609 for (size_t i = 0; i < N; ++i)
610 {
611 EXPECT_FALSE(pq.push(handles[i]));
612 ASSERT_TRUE(pq.is_valid());
613 os << "queue: " << pq << std::endl;
614 }
615
616 {
617 queue pq2(handles.begin(), handles.end());
618 ASSERT_TRUE(pq2.is_valid());
619 os << "queue: " << pq2 << std::endl;
620 }
621
622 const_iterator it_max = std::max_element(pq.begin(),
623 pq.end(),
624 handle_greater_type());
625 *pq[0].ptr = *it_max->ptr + 1000;
626 os << "queue: " << pq << std::endl;
627 pq.update_top();
628 ASSERT_TRUE(pq.is_valid());
629 os << "queue: " << pq << std::endl;
630
631 it_max = std::max_element(pq.begin(),
632 pq.end(),
633 handle_greater_type());
634 *pq[0].ptr = *it_max->ptr + 500;
635 os << "queue: " << pq << std::endl;
636 pq.update_top();
637 ASSERT_TRUE(pq.is_valid());
638 os << "queue: " << pq << std::endl;
639 }
640
641
642 //--------------------------------------------------------
643
644
645 class PriorityQueueTest : public ::testing::Test
646 {
647 protected:
SetUp()648 virtual void SetUp()
649 {
650 int xkeys[10] = {10, 4, 7, 8, 21, -5, 6, 10, 7, 9};
651 memcpy(keys, xkeys, sizeof(xkeys));
652 pq= Priority_queue<int>(xkeys, xkeys + 10);
653 keys2.assign(5, 50);
654 }
655
parent(size_t i)656 size_t parent(size_t i)
657 {
658 return Priority_queue<int>::parent(i);
659 }
left(size_t i)660 size_t left(size_t i)
661 {
662 return Priority_queue<int>::left(i);
663 }
right(size_t i)664 size_t right(size_t i)
665 {
666 return Priority_queue<int>::right(i);
667 }
668
669 int keys[10];
670 Priority_queue<int> pq;
671 std::vector<unsigned> keys2;
672 };
673
674
TEST_F(PriorityQueueTest,ParentLeftRight)675 TEST_F(PriorityQueueTest, ParentLeftRight)
676 {
677 EXPECT_EQ(0U, parent(1));
678 EXPECT_EQ(0U, parent(2));
679 EXPECT_EQ(1U, left(0));
680 EXPECT_EQ(2U, right(0));
681 for (size_t ix= 0; ix < 42; ++ix)
682 {
683 EXPECT_EQ(ix, parent(left(ix)));
684 EXPECT_EQ(ix, parent(right(ix)));
685 EXPECT_EQ(1 + left(ix), right(ix));
686 }
687 }
688
689
690 struct My_less
691 {
operator ()priority_queue_unittest::My_less692 bool operator()(int a, int b) const
693 {
694 return a < b;
695 }
696 };
697
698 struct My_greater
699 {
operator ()priority_queue_unittest::My_greater700 bool operator()(int a, int b) const
701 {
702 return a > b;
703 }
704 };
705
706
TEST_F(PriorityQueueTest,MaxVsMinHeap)707 TEST_F(PriorityQueueTest, MaxVsMinHeap)
708 {
709 Priority_queue<int, std::vector<int>, My_less> pql;
710 Priority_queue<int, std::vector<int>, My_greater> pqg;
711 for (int ix= 0; ix < 10; ++ix)
712 {
713 EXPECT_FALSE(pql.push(ix));
714 EXPECT_FALSE(pqg.push(ix));
715 EXPECT_EQ(ix, pql.top());
716 EXPECT_EQ(0, pqg.top());
717 EXPECT_TRUE(pql.is_valid());
718 EXPECT_TRUE(pqg.is_valid());
719 }
720 std::stringstream ss1, ss2;
721 ss1 << pql;
722 EXPECT_STREQ("9 8 5 6 7 1 4 0 3 2 ", ss1.str().c_str());
723 ss2 << pqg;
724 EXPECT_STREQ("0 1 2 3 4 5 6 7 8 9 ", ss2.str().c_str());
725 }
726
727
TEST_F(PriorityQueueTest,DifferentCtors)728 TEST_F(PriorityQueueTest, DifferentCtors)
729 {
730 Priority_queue<int, std::vector<int>, My_less> pql;
731 std::vector<int> intvec;
732 for (int ix= 0; ix < 10; ++ix)
733 {
734 Priority_queue<int> pq_ix(intvec.begin(), intvec.end());
735 EXPECT_TRUE(pq_ix.is_valid());
736 EXPECT_FALSE(pql.push(ix));
737 EXPECT_EQ(ix, pql.top());
738 intvec.push_back(ix);
739 }
740 Priority_queue<int, std::vector<int>, My_less>
741 pql_range(intvec.begin(), intvec.end());
742
743 EXPECT_EQ(10U, pql.size());
744 EXPECT_FALSE(pql.empty());
745 EXPECT_TRUE(pql.is_valid());
746 EXPECT_EQ(10U, pql_range.size());
747 EXPECT_FALSE(pql_range.empty());
748 EXPECT_TRUE(pql_range.is_valid());
749
750 std::stringstream ss1, ss2;
751 ss1 << pql;
752 ss2 << pql_range;
753 // Different heaps, both are valid:
754 EXPECT_STREQ("9 8 5 6 7 1 4 0 3 2 ", ss1.str().c_str());
755 EXPECT_STREQ("9 8 6 7 4 5 2 0 3 1 ", ss2.str().c_str());
756 }
757
758
TEST_F(PriorityQueueTest,Swap)759 TEST_F(PriorityQueueTest, Swap)
760 {
761 std::random_shuffle(keys, keys + 10);
762 Priority_queue<int> pq(keys, keys + 10);
763 std::stringstream ss1, ss2;
764 ss1 << pq;
765 Priority_queue<int> pq_swap;
766 pq_swap.swap(pq);
767 ss2 << pq_swap;
768 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
769 EXPECT_EQ(0U, pq.size());
770 }
771
772
TEST_F(PriorityQueueTest,DecreaseNoop)773 TEST_F(PriorityQueueTest, DecreaseNoop)
774 {
775 std::stringstream ss1, ss2;
776 ss1 << pq;
777 for (size_t ix= 0; ix < 10; ++ix)
778 {
779 pq.decrease(ix);
780 int val= pq[ix];
781 pq.decrease(ix, val);
782 *(pq.begin() + ix) = val;
783 pq.decrease(ix);
784 EXPECT_TRUE(pq.is_valid());
785 }
786 ss2 << pq;
787 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
788 }
789
790
TEST_F(PriorityQueueTest,IncreaseNoop)791 TEST_F(PriorityQueueTest, IncreaseNoop)
792 {
793 std::stringstream ss1, ss2;
794 ss1 << pq;
795 for (size_t ix= 0; ix < 10; ++ix)
796 {
797 pq.increase(ix);
798 int val= pq[ix];
799 pq.increase(ix, val);
800 *(pq.begin() + ix) = val;
801 pq.increase(ix);
802 EXPECT_TRUE(pq.is_valid());
803 }
804 ss2 << pq;
805 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
806 }
807
808
TEST_F(PriorityQueueTest,UpdateNoop)809 TEST_F(PriorityQueueTest, UpdateNoop)
810 {
811 std::stringstream ss1, ss2;
812 ss1 << pq;
813 for (size_t ix= 0; ix < 10; ++ix)
814 {
815 pq.update(ix);
816 int val= pq[ix];
817 pq.update(ix, val);
818 *(pq.begin() + ix) = val;
819 pq.update(ix);
820 EXPECT_TRUE(pq.is_valid());
821 }
822 ss2 << pq;
823 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
824 }
825
826
TEST_F(PriorityQueueTest,Decrease3)827 TEST_F(PriorityQueueTest, Decrease3)
828 {
829 Priority_queue<int> pqcopy= pq;
830 const int old_priority= pq[3];
831 const int new_priority= old_priority - 10;
832
833 pq.decrease(3, new_priority);
834 pqcopy[3] = new_priority;
835 pqcopy.decrease(3);
836
837 std::stringstream ss1, ss2;
838 ss1 << pq;
839 ss2 << pqcopy;
840 EXPECT_TRUE(pq.is_valid());
841 EXPECT_TRUE(pqcopy.is_valid());
842 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
843 }
844
845
TEST_F(PriorityQueueTest,Increase4)846 TEST_F(PriorityQueueTest, Increase4)
847 {
848 Priority_queue<int> pqcopy= pq;
849 const int old_priority= pq[4];
850 const int new_priority= old_priority + 10;
851
852 pq.increase(4, new_priority);
853 pqcopy[4] = new_priority;
854 pqcopy.increase(4);
855
856 std::stringstream ss1, ss2;
857 ss1 << pq;
858 ss2 << pqcopy;
859 EXPECT_TRUE(pq.is_valid());
860 EXPECT_TRUE(pqcopy.is_valid());
861 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
862 }
863
864
TEST_F(PriorityQueueTest,Update2)865 TEST_F(PriorityQueueTest, Update2)
866 {
867 Priority_queue<int> pqcopy= pq;
868
869 for (int i = -10; i <= 10; ++i)
870 {
871 const int old_priority= pq[2];
872 const int new_priority= old_priority + i;
873
874 pq.update(2, new_priority);
875 pqcopy[2] = new_priority;
876 pqcopy.update(2);
877
878 std::stringstream ss1, ss2;
879 ss1 << pq;
880 ss2 << pqcopy;
881 EXPECT_TRUE(pq.is_valid()) << "i:" << i << " pq:" << pq;
882 EXPECT_TRUE(pqcopy.is_valid());
883 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
884 }
885 }
886
887
TEST_F(PriorityQueueTest,UpdateTop)888 TEST_F(PriorityQueueTest, UpdateTop)
889 {
890 Priority_queue<int> pqcopy= pq;
891 const int old_priority= pq.top();
892 const int new_priority= old_priority + 10;
893
894 pq.top()= new_priority;
895 pq.update_top();
896 pqcopy.update(0, new_priority);
897 std::stringstream ss1, ss2;
898 ss1 << pq;
899 ss2 << pqcopy;
900 EXPECT_TRUE(pq.is_valid());
901 EXPECT_TRUE(pqcopy.is_valid());
902 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
903 }
904
905
TEST_F(PriorityQueueTest,PopAndRemove)906 TEST_F(PriorityQueueTest, PopAndRemove)
907 {
908 Priority_queue<int> pqcopy= pq;
909
910 EXPECT_TRUE(pqcopy.size() == 10U);
911 pqcopy.pop();
912 EXPECT_TRUE(pqcopy.is_valid());
913 EXPECT_TRUE(pqcopy.size() == 9U);
914 pqcopy.remove(3);
915 EXPECT_TRUE(pqcopy.is_valid());
916 EXPECT_TRUE(pqcopy.size() == 8U);
917 pqcopy.remove(pqcopy.size() - 1);
918 EXPECT_TRUE(pqcopy.is_valid());
919 EXPECT_TRUE(pqcopy.size() == 7U);
920
921 Priority_queue<int> singleton;
922 EXPECT_FALSE(singleton.push(10));
923 singleton.pop();
924 EXPECT_TRUE(singleton.empty());
925 EXPECT_TRUE(singleton.is_valid());
926 }
927
928
TEST_F(PriorityQueueTest,Iterators)929 TEST_F(PriorityQueueTest, Iterators)
930 {
931 Priority_queue<int>::iterator it;
932 Priority_queue<int>::const_iterator cit;
933 std::stringstream ss1, ss2;
934 for (it= pq.begin(); it != pq.end(); ++it)
935 ss1 << *it << " ";
936 for (cit= pq.begin(); cit != pq.end(); ++cit)
937 ss2 << *cit << " ";
938 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
939 }
940
941
TEST_F(PriorityQueueTest,Clear)942 TEST_F(PriorityQueueTest, Clear)
943 {
944 EXPECT_EQ(10U, pq.size());
945 EXPECT_TRUE(pq.is_valid());
946 pq.clear();
947 EXPECT_EQ(0U, pq.size());
948 EXPECT_TRUE(pq.is_valid());
949 }
950
951
TEST_F(PriorityQueueTest,Reserve)952 TEST_F(PriorityQueueTest, Reserve)
953 {
954 EXPECT_EQ(10U, pq.capacity());
955 EXPECT_EQ(10U, pq.size());
956 EXPECT_FALSE(pq.reserve(10));
957 EXPECT_EQ(10U, pq.capacity());
958 EXPECT_EQ(10U, pq.size());
959 EXPECT_FALSE(pq.reserve(5));
960 EXPECT_EQ(10U, pq.capacity());
961 EXPECT_EQ(10U, pq.size());
962 EXPECT_FALSE(pq.reserve(20));
963 EXPECT_EQ(20U, pq.capacity());
964 EXPECT_EQ(10U, pq.size());
965 }
966
967
TEST_F(PriorityQueueTest,Sort)968 TEST_F(PriorityQueueTest, Sort)
969 {
970 Priority_queue<int> pqcopy= pq;
971 std::vector<int> keyscopy(keys, keys + 10);
972
973 pqcopy.sort();
974 std::sort(keyscopy.begin(), keyscopy.end());
975
976 std::stringstream ss1, ss2;
977 ss1 << pqcopy;
978 for (size_t i= 0; i < keyscopy.size(); ++i)
979 {
980 ss2 << keyscopy[i] << " ";
981 }
982 EXPECT_STREQ(ss1.str().c_str(), ss2.str().c_str());
983 }
984
985
TEST_F(PriorityQueueTest,TestHeapKeys)986 TEST_F(PriorityQueueTest, TestHeapKeys)
987 {
988 SCOPED_TRACE("");
989 test_heap(keys, keys + 10);
990 }
991
992
TEST_F(PriorityQueueTest,TestHeapKeys2)993 TEST_F(PriorityQueueTest, TestHeapKeys2)
994 {
995 SCOPED_TRACE("");
996 test_heap(keys2.begin(), keys2.end());
997 }
998
999
TEST_F(PriorityQueueTest,TestHeapOfHandles)1000 TEST_F(PriorityQueueTest, TestHeapOfHandles)
1001 {
1002 SCOPED_TRACE("");
1003 test_heap_of_handles(keys, keys + 10);
1004 }
1005
1006
TEST_F(PriorityQueueTest,TestHeapOfHandles2)1007 TEST_F(PriorityQueueTest, TestHeapOfHandles2)
1008 {
1009 SCOPED_TRACE("");
1010 test_heap_of_handles(keys2.begin(), keys2.end());
1011 }
1012
1013
TEST_F(PriorityQueueTest,TestMinKElements)1014 TEST_F(PriorityQueueTest, TestMinKElements)
1015 {
1016 SCOPED_TRACE("");
1017 test_min_k_elements(keys, keys + 10, 7);
1018 }
1019
1020
TEST_F(PriorityQueueTest,TestMinKElements2)1021 TEST_F(PriorityQueueTest, TestMinKElements2)
1022 {
1023 SCOPED_TRACE("");
1024 test_min_k_elements(keys2.begin(), keys2.end(), 4);
1025 }
1026
1027
TEST_F(PriorityQueueTest,RandomIntegerGenerator)1028 TEST_F(PriorityQueueTest, RandomIntegerGenerator)
1029 {
1030 random_integer_generator<int> g;
1031 std::vector<int> many_keys;
1032
1033 for (int i = 0; i < 200; ++i)
1034 {
1035 int value = g(0, 300);
1036 many_keys.push_back(value);
1037 }
1038
1039 SCOPED_TRACE("");
1040 test_min_k_elements(many_keys.begin(), many_keys.end(), 20);
1041 }
1042
1043 /**
1044 Bug#30301356 - SOME EVENTS ARE DELAYED AFTER DROPPING EVENT
1045
1046 Test that ensures heap property is not violated if we remove an
1047 element from an interior node. In the below test, we remove the
1048 element 90 at index 6 in the array. After 90 is removed, the
1049 parent node's of the deleted node violates the heap property.
1050 In order to restore the heap property, we need to move up the
1051 heap until we reach a node which satisfies the heap property or
1052 the root. Without the fix, we adjust the heap downwards.
1053 */
1054
TEST_F(PriorityQueueTest,TestElementRemove)1055 TEST_F(PriorityQueueTest, TestElementRemove) {
1056 Priority_queue<int, std::vector<int>, My_greater> pq;
1057
1058 int keys[11] = {60, 65, 84, 75, 80, 85, 90, 95, 100, 105, 82};
1059 pq = Priority_queue<int, std::vector<int>, My_greater>(keys, keys + 11);
1060 pq.remove(6);
1061 EXPECT_TRUE(pq.is_valid());
1062 }
1063
1064 }
1065