1 #include "gtest/gtest.h" 2 #include "chre/util/heap.h" 3 4 #include <algorithm> 5 #include <array> 6 7 using chre::DynamicVector; 8 using chre::FixedSizeVector; 9 10 TEST(HeapDeathTest, PushHeapWhenEmpty) { 11 DynamicVector<int> v; 12 std::less<int> comp; 13 EXPECT_DEATH(chre::push_heap(v, comp), ""); 14 } 15 16 TEST(HeapDeathTest, PopHeapWhenEmpty) { 17 DynamicVector<int> v; 18 std::less<int> comp; 19 EXPECT_DEATH(chre::pop_heap(v, comp), ""); 20 } 21 22 TEST(HeapTest, NestedPushPopHeap) { 23 DynamicVector<int> v; 24 std::less<int> comp; 25 26 // generate random test data 27 const size_t MaxSize = 1000; 28 std::array<int, MaxSize> array; 29 std::array<int, MaxSize> array_sorted; 30 std::srand(0xcafe); 31 for (size_t i = 0; i < MaxSize; ++i) { 32 array[i] = std::rand(); 33 array_sorted[i] = array[i]; 34 } 35 36 // make sure the popped data is in the right order of various array sizes. 37 for (size_t s = 1; s < MaxSize + 1; ++s) { 38 for (size_t i = 0; i < s; ++i) { 39 v.push_back(array[i]); 40 chre::push_heap(v, comp); 41 } 42 43 std::sort(array_sorted.begin(), array_sorted.begin() + s, std::greater<int>()); 44 45 for (size_t i = 0; i < s; ++i) { 46 chre::pop_heap(v, comp); 47 EXPECT_EQ(array_sorted[i], v[v.size() - 1]); 48 v.erase(v.size() - 1); 49 } 50 } 51 } 52 53 TEST(HeapDeathTest, RemoveHeapWithInvalidIndex) { 54 DynamicVector<int> v; 55 std::less<int> comp; 56 57 v.push_back(0); 58 chre::push_heap(v, comp); 59 EXPECT_DEATH(chre::remove_heap(v, 1, comp), ""); 60 } 61 62 TEST(HeapTest, NestedRemoveHeap) { 63 DynamicVector<int> v; 64 std::less<int> comp; 65 66 // generate random test data 67 const size_t MaxSize = 1000; 68 std::array<int, MaxSize> array; 69 std::array<int, MaxSize> array_sorted; 70 std::srand(0xcafe); 71 for (size_t i = 0; i < MaxSize; ++i) { 72 array[i] = std::rand(); 73 array_sorted[i] = array[i]; 74 } 75 76 for (size_t s = 1; s < MaxSize + 1; ++s) { 77 for (size_t i = 0; i < s; ++i) { 78 v.push_back(array[i]); 79 chre::push_heap(v, comp); 80 } 81 82 std::sort(array_sorted.begin(), array_sorted.begin() + s, std::greater<int>()); 83 84 // randomly remove one 85 chre::remove_heap(v, std::rand() % s, comp); 86 int data = v[v.size() - 1]; 87 v.erase(v.size() - 1); 88 89 for (size_t i = 0; i < s; ++i) { 90 if (array_sorted[i] == data) { 91 continue; 92 } 93 94 chre::pop_heap(v, comp); 95 EXPECT_EQ(array_sorted[i], v[v.size() - 1]); 96 v.erase(v.size() - 1); 97 } 98 } 99 } 100 101 TEST(HeapTest, FixedSizeVectorMinHeap) { 102 FixedSizeVector<int, 16> v; 103 104 for (size_t i = 0; i < 5; ++i) { 105 v.push_back(i); 106 chre::push_heap(v, std::greater<int>()); 107 } 108 109 for (size_t i = 0; i < 5; ++i) { 110 chre::pop_heap(v, std::greater<int>()); 111 EXPECT_EQ(i, v[v.size() - 1]); 112 v.erase(v.size() - 1); 113 } 114 } 115
