BinaryHuffmanTreeTest.cpp at 59b0d20 ⋅ darktable-org/rawspeed

/*
    RawSpeed - RAW file decoder.

    Copyright (C) 2018 Roman Lebedev

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

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

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

#include "decompressors/BinaryHuffmanTree.h" // for BinaryHuffmanTree, Bina...
#include <cstdlib>                           // for exit
#include <gtest/gtest.h>                     // for AssertionResult, Message
#include <initializer_list>                  // for initializer_list
#include <memory>                            // for unique_ptr, make_unique
#include <vector>                            // for vector

using rawspeed::BinaryHuffmanTree;

namespace rawspeed_test {

TEST(BinaryHuffmanTreeTest, EmptyByDefault) {
  {
    const BinaryHuffmanTree<int> b;
    ASSERT_FALSE(b.root);
  }
  {
    BinaryHuffmanTree<int> b;
    ASSERT_FALSE(b.root);
  }
  {
    struct T {
      int i;
    };
    const BinaryHuffmanTree<T> b;
    ASSERT_FALSE(b.root);
  }
}

#ifndef NDEBUG
TEST(BinaryHuffmanTreeDeathTest, getAllBranchesOfNegativeDepth) {
  ASSERT_DEATH(
      {
        BinaryHuffmanTree<int> b;
        b.getAllBranchesOfDepth(-1);
        exit(0);
      },
      "depth >= 0");
}
#endif

TEST(BinaryHuffmanTreeTest, getAllBranchesOfDepth_0_Base) {
  BinaryHuffmanTree<int> b;
  const auto zero = b.getAllBranchesOfDepth(0);
  ASSERT_EQ(zero.size(), 1);
  ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*(b.root)),
            decltype(b)::Node::Type::Branch);
  ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
  for (const auto& branch : zero) {
    ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*branch),
              decltype(b)::Node::Type::Branch);
    ASSERT_FALSE(branch->hasLeafs());
  }
  ASSERT_EQ(zero[0], b.root.get());
}
TEST(BinaryHuffmanTreeTest, getAllBranchesOfDepth_1_Base) {
  BinaryHuffmanTree<int> b;
  const auto one = b.getAllBranchesOfDepth(1);
  ASSERT_EQ(one.size(), 2);
  ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*(b.root)),
            decltype(b)::Node::Type::Branch);
  ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
  for (const auto& branch : one) {
    ASSERT_EQ(static_cast<typename decltype(b)::Node::Type>(*branch),
              decltype(b)::Node::Type::Branch);
    ASSERT_FALSE(branch->hasLeafs());
  }
  ASSERT_EQ(one[0], &(b.root->getAsBranch().zero->getAsBranch()));
  ASSERT_EQ(one[1], &(b.root->getAsBranch().one->getAsBranch()));
}

#ifndef NDEBUG
TEST(BinaryHuffmanTreeDeathTest, getAllNodesAtZeroDepth) {
  ASSERT_DEATH(
      {
        BinaryHuffmanTree<int> b;
        b.getAllVacantNodesAtDepth(0);
        exit(0);
      },
      "depth > 0");
}
#endif

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

TEST(BinaryHuffmanTreeTest,
     getAllVacantNodesAtDepth_2_fills_depth_1_with_branches) {
  BinaryHuffmanTree<int> b;
  {
    const auto one = b.getAllVacantNodesAtDepth(1);
    ASSERT_EQ(one.size(), 2);
  }
  const auto two = b.getAllVacantNodesAtDepth(2);
  ASSERT_EQ(two.size(), 4);
  {
    // All vacant nodes on previous depths are auto-filled with Branches
    const auto one = b.getAllVacantNodesAtDepth(1);
    ASSERT_EQ(one.size(), 0);
  }
}

TEST(BinaryHuffmanTreeTest, getAllVacantNodesAtDepth_2_Base) {
  BinaryHuffmanTree<int> b;
  const auto two = b.getAllVacantNodesAtDepth(2);
  ASSERT_EQ(two.size(), 4);
  ASSERT_EQ(two[0], &(b.root->getAsBranch().zero->getAsBranch().zero));
  ASSERT_EQ(two[1], &(b.root->getAsBranch().zero->getAsBranch().one));
  ASSERT_EQ(two[2], &(b.root->getAsBranch().one->getAsBranch().zero));
  ASSERT_EQ(two[3], &(b.root->getAsBranch().one->getAsBranch().one));
}

TEST(BinaryHuffmanTreeTest, pruneLeaflessBranches_purges_all) {
  BinaryHuffmanTree<int> b;
  b.getAllVacantNodesAtDepth(2);
  ASSERT_TRUE(b.root);
  b.pruneLeaflessBranches();
  ASSERT_FALSE(b.root);
}

TEST(BinaryHuffmanTreeTest,
     getAllVacantNodesAtDepth_1_after_adding_1_depth_1_leaf) {
  BinaryHuffmanTree<int> b;
  {
    const auto one = b.getAllVacantNodesAtDepth(1);
    ASSERT_EQ(one.size(), 2);
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
    // Add one leaf at the depth of one
    *one.front() = std::make_unique<decltype(b)::Leaf>();
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());

    // Now let's try pruning
    b.pruneLeaflessBranches();
    ASSERT_TRUE(b.root);
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());
  }
  {
    const auto one = b.getAllVacantNodesAtDepth(1);
    ASSERT_EQ(one.size(), 1);
    ASSERT_EQ(one[0], &(b.root->getAsBranch().one));
  }
}

TEST(BinaryHuffmanTreeTest,
     getAllVacantNodesAtDepth_2_after_adding_1_depth_1_leaf) {
  BinaryHuffmanTree<int> b;
  {
    const auto two = b.getAllVacantNodesAtDepth(2);
    ASSERT_EQ(two.size(), 4);
    ASSERT_TRUE(b.root);
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
    ASSERT_TRUE(b.root->getAsBranch().zero);
    ASSERT_TRUE(b.root->getAsBranch().one);
    ASSERT_FALSE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().hasLeafs());

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

    ASSERT_TRUE(b.root);
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
    ASSERT_TRUE(b.root->getAsBranch().zero);
    ASSERT_TRUE(b.root->getAsBranch().one);
    ASSERT_TRUE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().hasLeafs());
  }
  {
    const auto two = b.getAllVacantNodesAtDepth(2);
    ASSERT_EQ(two.size(), 3);
    ASSERT_EQ(two[0], &(b.root->getAsBranch().zero->getAsBranch().one));
    ASSERT_EQ(two[1], &(b.root->getAsBranch().one->getAsBranch().zero));
    ASSERT_EQ(two[2], &(b.root->getAsBranch().one->getAsBranch().one));
  }
  {
    // And prune
    b.pruneLeaflessBranches();
    ASSERT_TRUE(b.root);
    ASSERT_FALSE(b.root->getAsBranch().hasLeafs());
    ASSERT_TRUE(b.root->getAsBranch().zero);
    ASSERT_FALSE(b.root->getAsBranch().one);
    ASSERT_TRUE(b.root->getAsBranch().zero->getAsBranch().hasLeafs());
  }
}

TEST(BinaryHuffmanTreeTest,
     getAllVacantNodesAtDepth_2_after_adding_1_depth_1_and_1_depth_2_leaf) {
  BinaryHuffmanTree<int> b;
  {
    const auto one = b.getAllVacantNodesAtDepth(1);
    ASSERT_EQ(one.size(), 2);
    // Add one leaf at the depth of one
    *one.front() = std::make_unique<decltype(b)::Leaf>();
  }
  {
    const auto two = b.getAllVacantNodesAtDepth(2);
    ASSERT_EQ(two.size(), 2);
    // Add one leaf at the depth of two
    *two.front() = std::make_unique<decltype(b)::Leaf>();
  }
  {
    const auto two = b.getAllVacantNodesAtDepth(2);
    ASSERT_EQ(two.size(), 1);
    ASSERT_EQ(two[0], &(b.root->getAsBranch().one->getAsBranch().one));
  }
  {
    // And prune
    b.pruneLeaflessBranches();
    ASSERT_TRUE(b.root);
    ASSERT_TRUE(b.root->getAsBranch().hasLeafs());
    ASSERT_TRUE(b.root->getAsBranch().zero);
    ASSERT_TRUE(b.root->getAsBranch().one);
    ASSERT_TRUE(b.root->getAsBranch().one->getAsBranch().hasLeafs());
    ASSERT_TRUE(b.root->getAsBranch().one->getAsBranch().zero);
    ASSERT_FALSE(b.root->getAsBranch().one->getAsBranch().one);
  }
}

} // namespace rawspeed_test

Read our documentation on viewing source code .

Navigation	Overlay
`t` Navigate files	`h` Toggle hits
`y` Change url to tip of branch	`m` Toggle misses
`b / v` Jump to prev/next hit line	`p` Toggle partial
`z / x` Jump to prev/next missed or partial line	`1..9` Toggle flags
`shift + o` Open current page in GitHub	`a` Toggle all on
`/ or ?` Show keyboard shortcuts dialog	`c` Toggle context lines or commits

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