1 // Copyright 2018 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "src/base/bottom_n.h"
16
17 #include <gmock/gmock.h>
18 #include <gtest/gtest.h>
19
20 namespace astc_codec {
21 namespace base {
22
23 using ::testing::ElementsAre;
24
25 template<typename T, size_t N>
pushAll(BottomN<T> & heap,const T (& arr)[N])26 static void pushAll(BottomN<T>& heap, const T (&arr)[N]) {
27 for (auto i : arr) {
28 heap.Push(i);
29 }
30 }
31
TEST(BottomN,Sort)32 TEST(BottomN, Sort) {
33 {
34 BottomN<int> heap(10);
35 EXPECT_TRUE(heap.Empty());
36 int list[] = { 1,2 };
37 pushAll(heap, list);
38
39 EXPECT_EQ(heap.Size(), 2);
40 EXPECT_FALSE(heap.Empty());
41 EXPECT_THAT(heap.Pop(), ElementsAre(1, 2));
42 }
43
44 {
45 BottomN<int> heap(6);
46 int list[] = {1, 4, 3, 2, 2, 1};
47 pushAll(heap, list);
48
49 EXPECT_EQ(heap.Size(), 6);
50 EXPECT_THAT(heap.Pop(), ElementsAre(1, 1, 2, 2, 3, 4));
51 }
52 }
53
TEST(BottomN,Bounds)54 TEST(BottomN, Bounds) {
55 {
56 BottomN<int> heap(4);
57 int list[] = { 1, 2, 3, 4 };
58 pushAll(heap, list);
59 EXPECT_EQ(heap.Size(), 4);
60
61 heap.Push(0);
62 EXPECT_EQ(heap.Size(), 4);
63
64 EXPECT_THAT(heap.Pop(), ElementsAre(0, 1, 2, 3));
65 }
66
67 {
68 BottomN<int> heap(4);
69 int list[] = { 4, 3, 2,1 };
70 pushAll(heap, list);
71 EXPECT_EQ(heap.Size(), 4);
72
73 int list2[] = { 4,4,4,4 };
74 pushAll(heap, list2);
75 EXPECT_EQ(heap.Size(), 4);
76
77 EXPECT_THAT(heap.Pop(), ElementsAre(1, 2, 3, 4));
78 }
79
80 {
81 BottomN<int> heap(4);
82 int list[] = { 4, 3, 2, 1 };
83 pushAll(heap, list);
84 EXPECT_EQ(heap.Size(), 4);
85
86 int list2[] = { 5, 5, 5, 5 };
87 pushAll(heap, list2);
88 EXPECT_EQ(heap.Size(), 4);
89
90 EXPECT_THAT(heap.Pop(), ElementsAre(1, 2, 3, 4));
91 }
92
93 {
94 BottomN<int> heap(4);
95 int list[] = { 4, 3, 2, 1 };
96 pushAll(heap, list);
97 EXPECT_EQ(heap.Size(), 4);
98
99 int list2[] = { 0, 0, 0, 0 };
100 pushAll(heap, list2);
101 EXPECT_EQ(heap.Size(), 4);
102
103 EXPECT_THAT(heap.Pop(), ElementsAre(0, 0, 0, 0));
104 }
105 }
106
107 } // namespace base
108 } // namespace astc_codec
109