1
/*
2
    RawSpeed - RAW file decoder.
3

4
    Copyright (C) 2018 Roman Lebedev
5

6
    This library is free software; you can redistribute it and/or
7
    modify it under the terms of the GNU Lesser General Public
8
    License as published by the Free Software Foundation; either
9
    version 2 of the License, or (at your option) any later version.
10

11
    This library is distributed in the hope that it will be useful,
12
    but WITHOUT ANY WARRANTY; withexpected even the implied warranty of
13
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
    Lesser General Public License for more details.
15

16
    You should have received a copy of the GNU Lesser General Public
17
    License along with this library; if not, write to the Free Software
18
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19
*/
20

21
#include "decompressors/BinaryHuffmanTree.h" // for BinaryHuffmanTree, Bina...
22
#include <cstdlib>                           // for exit
23
#include <gtest/gtest.h>                     // for AssertionResult, Message
24
#include <initializer_list>                  // for initializer_list
25
#include <memory>                            // for unique_ptr, make_unique
26
#include <vector>                            // for vector
27

28
using rawspeed::BinaryHuffmanTree;
29

30
namespace rawspeed_test {
31

32 1
TEST(BinaryHuffmanTreeTest, EmptyByDefault) {
33
  {
34 1
    const BinaryHuffmanTree<int> b;
35 0
    ASSERT_FALSE(b.root);
36
  }
37
  {
38 1
    BinaryHuffmanTree<int> b;
39 0
    ASSERT_FALSE(b.root);
40
  }
41
  {
42
    struct T {
43
      int i;
44
    };
45 1
    const BinaryHuffmanTree<T> b;
46 0
    ASSERT_FALSE(b.root);
47
  }
48
}
49

50
#ifndef NDEBUG
51 1
TEST(BinaryHuffmanTreeDeathTest, getAllBranchesOfNegativeDepth) {
52 0
  ASSERT_DEATH(
53
      {
54
        BinaryHuffmanTree<int> b;
55
        b.getAllBranchesOfDepth(-1);
56
        exit(0);
57
      },
58
      "depth >= 0");
59
}
60
#endif
61

62 1
TEST(BinaryHuffmanTreeTest, getAllBranchesOfDepth_0_Base) {
63 1
  BinaryHuffmanTree<int> b;
64 1
  const auto zero = b.getAllBranchesOfDepth(0);
65 0
  ASSERT_EQ(zero.size(), 1);
66 0
  ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*(b.root)),
67
            decltype(b)::Node::Type::Branch);
68 0
  ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
69 1
  for (const auto& branch : zero) {
70 0
    ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*branch),
71
              decltype(b)::Node::Type::Branch);
72 0
    ASSERT_FALSE(branch->hasLeafs());
73
  }
74 0
  ASSERT_EQ(zero[0], b.root.get());
75
}
76 1
TEST(BinaryHuffmanTreeTest, getAllBranchesOfDepth_1_Base) {
77 1
  BinaryHuffmanTree<int> b;
78 1
  const auto one = b.getAllBranchesOfDepth(1);
79 0
  ASSERT_EQ(one.size(), 2);
80 0
  ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*(b.root)),
81
            decltype(b)::Node::Type::Branch);
82 0
  ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
83 1
  for (const auto& branch : one) {
84 0
    ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*branch),
85
              decltype(b)::Node::Type::Branch);
86 0
    ASSERT_FALSE(branch->hasLeafs());
87
  }
88 0
  ASSERT_EQ(one[0], &(b.root->getAsBranch().zero->getAsBranch()));
89 0
  ASSERT_EQ(one[1], &(b.root->getAsBranch().one->getAsBranch()));
90
}
91

92
#ifndef NDEBUG
93 1
TEST(BinaryHuffmanTreeDeathTest, getAllNodesAtZeroDepth) {
94 0
  ASSERT_DEATH(
95
      {
96
        BinaryHuffmanTree<int> b;
97
        b.getAllVacantNodesAtDepth(0);
98
        exit(0);
99
      },
100
      "depth > 0");
101
}
102
#endif
103

104 1
TEST(BinaryHuffmanTreeTest, getAllVacantNodesAtDepth_1_Base) {
105 1
  BinaryHuffmanTree<int> b;
106 1
  const auto one = b.getAllVacantNodesAtDepth(1);
107 0
  ASSERT_EQ(one.size(), 2);
108 0
  ASSERT_EQ(one[0], &(b.root->getAsBranch().zero));
109 0
  ASSERT_EQ(one[1], &(b.root->getAsBranch().one));
110
}
111

112 1
TEST(BinaryHuffmanTreeTest,
113
     getAllVacantNodesAtDepth_2_fills_depth_1_with_branches) {
114 1
  BinaryHuffmanTree<int> b;
115
  {
116 1
    const auto one = b.getAllVacantNodesAtDepth(1);
117 0
    ASSERT_EQ(one.size(), 2);
118
  }
119 1
  const auto two = b.getAllVacantNodesAtDepth(2);
120 0
  ASSERT_EQ(two.size(), 4);
121
  {
122
    // All vacant nodes on previous depths are auto-filled with Branches
123 1
    const auto one = b.getAllVacantNodesAtDepth(1);
124 0
    ASSERT_EQ(one.size(), 0);
125
  }
126
}
127

128 1
TEST(BinaryHuffmanTreeTest, getAllVacantNodesAtDepth_2_Base) {
129 1
  BinaryHuffmanTree<int> b;
130 1
  const auto two = b.getAllVacantNodesAtDepth(2);
131 0
  ASSERT_EQ(two.size(), 4);
132 0
  ASSERT_EQ(two[0], &(b.root->getAsBranch().zero->getAsBranch().zero));
133 0
  ASSERT_EQ(two[1], &(b.root->getAsBranch().zero->getAsBranch().one));
134 0
  ASSERT_EQ(two[2], &(b.root->getAsBranch().one->getAsBranch().zero));
135 0
  ASSERT_EQ(two[3], &(b.root->getAsBranch().one->getAsBranch().one));
136
}
137

138 1
TEST(BinaryHuffmanTreeTest, pruneLeaflessBranches_purges_all) {
139 1
  BinaryHuffmanTree<int> b;
140 1
  b.getAllVacantNodesAtDepth(2);
141 0
  ASSERT_TRUE(b.root);
142 1
  b.pruneLeaflessBranches();
143 0
  ASSERT_FALSE(b.root);
144
}
145

146 1
TEST(BinaryHuffmanTreeTest,
147
     getAllVacantNodesAtDepth_1_after_adding_1_depth_1_leaf) {
148 1
  BinaryHuffmanTree<int> b;
149
  {
150 1
    const auto one = b.getAllVacantNodesAtDepth(1);
151 0
    ASSERT_EQ(one.size(), 2);
152 0
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
153
    // Add one leaf at the depth of one
154 1
    *one.front() = std::make_unique<decltype(b)::Leaf>();
155 0
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());
156

157
    // Now let's try pruning
158 1
    b.pruneLeaflessBranches();
159 0
    ASSERT_TRUE(b.root);
160 0
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());
161
  }
162
  {
163 1
    const auto one = b.getAllVacantNodesAtDepth(1);
164 0
    ASSERT_EQ(one.size(), 1);
165 0
    ASSERT_EQ(one[0], &(b.root->getAsBranch().one));
166
  }
167
}
168

169 1
TEST(BinaryHuffmanTreeTest,
170
     getAllVacantNodesAtDepth_2_after_adding_1_depth_1_leaf) {
171 1
  BinaryHuffmanTree<int> b;
172
  {
173 1
    const auto two = b.getAllVacantNodesAtDepth(2);
174 0
    ASSERT_EQ(two.size(), 4);
175 0
    ASSERT_TRUE(b.root);
176 0
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
177 0
    ASSERT_TRUE(b.root->getAsBranch().zero);
178 0
    ASSERT_TRUE(b.root->getAsBranch().one);
179 0
    ASSERT_FALSE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
180 0
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().hasLeafs());
181

182
    // Add one leaf at the depth of two
183 1
    *two.front() = std::make_unique<decltype(b)::Leaf>();
184

185 0
    ASSERT_TRUE(b.root);
186 0
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
187 0
    ASSERT_TRUE(b.root->getAsBranch().zero);
188 0
    ASSERT_TRUE(b.root->getAsBranch().one);
189 0
    ASSERT_TRUE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
190 0
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().hasLeafs());
191
  }
192
  {
193 1
    const auto two = b.getAllVacantNodesAtDepth(2);
194 0
    ASSERT_EQ(two.size(), 3);
195 0
    ASSERT_EQ(two[0], &(b.root->getAsBranch().zero->getAsBranch().one));
196 0
    ASSERT_EQ(two[1], &(b.root->getAsBranch().one->getAsBranch().zero));
197 0
    ASSERT_EQ(two[2], &(b.root->getAsBranch().one->getAsBranch().one));
198
  }
199
  {
200
    // And prune
201 1
    b.pruneLeaflessBranches();
202 0
    ASSERT_TRUE(b.root);
203 0
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
204 0
    ASSERT_TRUE(b.root->getAsBranch().zero);
205 0
    ASSERT_FALSE(b.root->getAsBranch().one);
206 0
    ASSERT_TRUE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
207
  }
208
}
209

210 1
TEST(BinaryHuffmanTreeTest,
211
     getAllVacantNodesAtDepth_2_after_adding_1_depth_1_and_1_depth_2_leaf) {
212 1
  BinaryHuffmanTree<int> b;
213
  {
214 1
    const auto one = b.getAllVacantNodesAtDepth(1);
215 0
    ASSERT_EQ(one.size(), 2);
216
    // Add one leaf at the depth of one
217 1
    *one.front() = std::make_unique<decltype(b)::Leaf>();
218
  }
219
  {
220 1
    const auto two = b.getAllVacantNodesAtDepth(2);
221 0
    ASSERT_EQ(two.size(), 2);
222
    // Add one leaf at the depth of two
223 1
    *two.front() = std::make_unique<decltype(b)::Leaf>();
224
  }
225
  {
226 1
    const auto two = b.getAllVacantNodesAtDepth(2);
227 0
    ASSERT_EQ(two.size(), 1);
228 0
    ASSERT_EQ(two[0], &(b.root->getAsBranch().one->getAsBranch().one));
229
  }
230
  {
231
    // And prune
232 1
    b.pruneLeaflessBranches();
233 0
    ASSERT_TRUE(b.root);
234 0
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());
235 0
    ASSERT_TRUE(b.root->getAsBranch().zero);
236 0
    ASSERT_TRUE(b.root->getAsBranch().one);
237 0
    ASSERT_TRUE(b.root->getAsBranch().one->getAsBranch().hasLeafs());
238 0
    ASSERT_TRUE(b.root->getAsBranch().one->getAsBranch().zero);
239 0
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().one);
240
  }
241
}
242

243
} // namespace rawspeed_test

Read our documentation on viewing source code .

Loading