Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
huffman_btreepic_test.cc
Go to the documentation of this file.
1
2/*
3 Aleph_w
4
5 Data structures & Algorithms
6 version 2.0.0b
7 https://github.com/lrleon/Aleph-w
8
9 This file is part of Aleph-w library
10
11 Copyright (c) 2002-2026 Leandro Rabindranath Leon
12
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19
20 The above copyright notice and this permission notice shall be included in all
21 copies or substantial portions of the Software.
22
23 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29 SOFTWARE.
30*/
31
32
38#include <gtest/gtest.h>
39#include <sstream>
40#include <Huffman.H>
41#include <huffman_btreepic.H>
42
43using namespace std;
44
45// =============================================================================
46// Test Fixtures
47// =============================================================================
48
49class HuffmanBtreepicTest : public ::testing::Test
50{
51protected:
52 void SetUp() override
53 {
54 reset_huffman_btreepic_state();
55 output_ptr = nullptr;
56 }
57
58 void TearDown() override
59 {
60 reset_huffman_btreepic_state();
61 output_ptr = nullptr;
62 }
63
64 // Helper to create a simple Huffman tree from a string
65 Huffman_Encoder_Engine create_encoder(const string & text)
66 {
67 Huffman_Encoder_Engine encoder;
68 char * str = const_cast<char*>(text.c_str());
69 encoder.read_input(str, true);
70 return encoder;
71 }
72};
73
74// =============================================================================
75// Infix_Desc Tests
76// =============================================================================
77
85
93
94// =============================================================================
95// Level_Desc Tests
96// =============================================================================
97
104
105TEST_F(HuffmanBtreepicTest, LevelDescParameterizedConstruction)
106{
107 Freq_Node node;
108 Level_Desc desc(true, &node);
109 EXPECT_TRUE(desc.is_left);
110 EXPECT_EQ(desc.level_succ, &node);
111}
112
113// =============================================================================
114// Offset Enum Tests
115// =============================================================================
116
123
124// =============================================================================
125// get_offset Tests
126// =============================================================================
127
135
136TEST_F(HuffmanBtreepicTest, GetOffsetClampedIndices)
137{
138 // Indices beyond MAX_OFFSET_INDEX should be clamped
139 EXPECT_DOUBLE_EQ(get_offset(8), 90);
140 EXPECT_DOUBLE_EQ(get_offset(100), 90);
141 EXPECT_DOUBLE_EQ(get_offset(1000), 90);
142}
143
144// =============================================================================
145// num_digits Tests
146// =============================================================================
147
154
162
163// =============================================================================
164// reset_huffman_btreepic_state Tests
165// =============================================================================
166
167TEST_F(HuffmanBtreepicTest, ResetStateClearsInfixTable)
168{
169 // Add something to the infix table
170 Freq_Node node;
171 node.get_key().first = "a";
172 node.get_key().second = 5;
173 infix_table.insert(&node, Infix_Desc(1, 2));
174 EXPECT_EQ(infix_table.size(), 1u);
175
176 reset_huffman_btreepic_state();
177 EXPECT_EQ(infix_table.size(), 0u);
178}
179
189
190TEST_F(HuffmanBtreepicTest, ResetStateClearsPred)
191{
192 Freq_Node node;
193 pred = &node;
194 EXPECT_NE(pred, nullptr);
195
196 reset_huffman_btreepic_state();
197 EXPECT_EQ(pred, nullptr);
198}
199
200// =============================================================================
201// huffman_to_btreepic Basic Tests
202// =============================================================================
203
204TEST_F(HuffmanBtreepicTest, NullptrRootProducesNoOutput)
205{
206 stringstream ss;
207 output_ptr = &ss;
208 huffman_to_btreepic(nullptr, false);
209 EXPECT_TRUE(ss.str().empty());
210}
211
212TEST_F(HuffmanBtreepicTest, NullOutputPtrDoesNotCrash)
213{
214 Freq_Node node;
215 node.get_key().first = "a";
216 node.get_key().second = 1;
217 LLINK(&node) = nullptr;
218 RLINK(&node) = nullptr;
219
220 output_ptr = nullptr;
221 // Should not crash
222 EXPECT_NO_THROW(huffman_to_btreepic(&node, false));
223}
224
225TEST_F(HuffmanBtreepicTest, SingleNodeTree)
226{
227 Freq_Node node;
228 node.get_key().first = "a";
229 node.get_key().second = 5;
230 LLINK(&node) = nullptr;
231 RLINK(&node) = nullptr;
232
233 stringstream ss;
234 output_ptr = &ss;
235 huffman_to_btreepic(&node, false);
236
237 string output = ss.str();
238 EXPECT_TRUE(output.find("start-prefix") != string::npos);
239 EXPECT_TRUE(output.find("start-key") != string::npos);
240 EXPECT_TRUE(output.find("\"5\"") != string::npos);
241 EXPECT_TRUE(output.find("TAG 0") != string::npos);
242}
243
244TEST_F(HuffmanBtreepicTest, StreamOverload)
245{
246 Freq_Node node;
247 node.get_key().first = "a";
248 node.get_key().second = 5;
249 LLINK(&node) = nullptr;
250 RLINK(&node) = nullptr;
251
252 stringstream ss;
253 huffman_to_btreepic(&node, ss, false);
254
255 string output = ss.str();
256 EXPECT_TRUE(output.find("start-prefix") != string::npos);
257 EXPECT_TRUE(output.find("start-key") != string::npos);
258}
259
260// =============================================================================
261// LaTeX Character Escaping Tests
262// =============================================================================
263
264TEST_F(HuffmanBtreepicTest, EscapeNewline)
265{
266 Freq_Node node;
267 node.get_key().first = "\n";
268 node.get_key().second = 1;
269 LLINK(&node) = nullptr;
270 RLINK(&node) = nullptr;
271
272 stringstream ss;
273 output_ptr = &ss;
274 huffman_to_btreepic(&node, false);
275
276 EXPECT_TRUE(ss.str().find("$\\backslash$n") != string::npos);
277}
278
279TEST_F(HuffmanBtreepicTest, EscapeDollar)
280{
281 Freq_Node node;
282 node.get_key().first = "$";
283 node.get_key().second = 1;
284 LLINK(&node) = nullptr;
285 RLINK(&node) = nullptr;
286
287 stringstream ss;
288 output_ptr = &ss;
289 huffman_to_btreepic(&node, false);
290
291 EXPECT_TRUE(ss.str().find("\\$") != string::npos);
292}
293
294TEST_F(HuffmanBtreepicTest, EscapeAmpersand)
295{
296 Freq_Node node;
297 node.get_key().first = "&";
298 node.get_key().second = 1;
299 LLINK(&node) = nullptr;
300 RLINK(&node) = nullptr;
301
302 stringstream ss;
303 output_ptr = &ss;
304 huffman_to_btreepic(&node, false);
305
306 EXPECT_TRUE(ss.str().find("\\&") != string::npos);
307}
308
309TEST_F(HuffmanBtreepicTest, EscapeHash)
310{
311 Freq_Node node;
312 node.get_key().first = "#";
313 node.get_key().second = 1;
314 LLINK(&node) = nullptr;
315 RLINK(&node) = nullptr;
316
317 stringstream ss;
318 output_ptr = &ss;
319 huffman_to_btreepic(&node, false);
320
321 EXPECT_TRUE(ss.str().find("\\#") != string::npos);
322}
323
324TEST_F(HuffmanBtreepicTest, EscapePercent)
325{
326 Freq_Node node;
327 node.get_key().first = "%";
328 node.get_key().second = 1;
329 LLINK(&node) = nullptr;
330 RLINK(&node) = nullptr;
331
332 stringstream ss;
333 output_ptr = &ss;
334 huffman_to_btreepic(&node, false);
335
336 EXPECT_TRUE(ss.str().find("\\%") != string::npos);
337}
338
339TEST_F(HuffmanBtreepicTest, EscapeSpace)
340{
341 Freq_Node node;
342 node.get_key().first = " ";
343 node.get_key().second = 1;
344 LLINK(&node) = nullptr;
345 RLINK(&node) = nullptr;
346
347 stringstream ss;
348 output_ptr = &ss;
349 huffman_to_btreepic(&node, false);
350
351 EXPECT_TRUE(ss.str().find("$\\square$") != string::npos);
352}
353
354TEST_F(HuffmanBtreepicTest, EscapeBackslash)
355{
356 Freq_Node node;
357 node.get_key().first = "\\";
358 node.get_key().second = 1;
359 LLINK(&node) = nullptr;
360 RLINK(&node) = nullptr;
361
362 stringstream ss;
363 output_ptr = &ss;
364 huffman_to_btreepic(&node, false);
365
366 EXPECT_TRUE(ss.str().find("$\\backslash$") != string::npos);
367}
368
369TEST_F(HuffmanBtreepicTest, EscapeQuote)
370{
371 Freq_Node node;
372 node.get_key().first = "\"";
373 node.get_key().second = 1;
374 LLINK(&node) = nullptr;
375 RLINK(&node) = nullptr;
376
377 stringstream ss;
378 output_ptr = &ss;
379 huffman_to_btreepic(&node, false);
380
381 EXPECT_TRUE(ss.str().find("$\\prime\\prime$") != string::npos);
382}
383
384TEST_F(HuffmanBtreepicTest, EscapeEmptyString)
385{
386 Freq_Node node;
387 node.get_key().first = "";
388 node.get_key().second = 1;
389 LLINK(&node) = nullptr;
390 RLINK(&node) = nullptr;
391
392 stringstream ss;
393 output_ptr = &ss;
394 huffman_to_btreepic(&node, false);
395
396 EXPECT_TRUE(ss.str().find("$\\neg$") != string::npos);
397}
398
399TEST_F(HuffmanBtreepicTest, EscapeBraces)
400{
401 Freq_Node node1, node2;
402 node1.get_key().first = "{";
403 node1.get_key().second = 1;
404 node2.get_key().first = "}";
405 node2.get_key().second = 1;
406 LLINK(&node1) = nullptr;
407 RLINK(&node1) = nullptr;
408 LLINK(&node2) = nullptr;
409 RLINK(&node2) = nullptr;
410
411 stringstream ss1, ss2;
412 output_ptr = &ss1;
413 huffman_to_btreepic(&node1, false);
414 output_ptr = &ss2;
415 huffman_to_btreepic(&node2, false);
416
417 EXPECT_TRUE(ss1.str().find("$\\{$") != string::npos);
418 EXPECT_TRUE(ss2.str().find("$\\}$") != string::npos);
419}
420
421// =============================================================================
422// Full Huffman Tree Tests
423// =============================================================================
424
425TEST_F(HuffmanBtreepicTest, SimpleTextEncoding)
426{
427 Huffman_Encoder_Engine encoder = create_encoder("aab");
428 Freq_Node * root = encoder.get_freq_root();
429
430 stringstream ss;
431 output_ptr = &ss;
432 huffman_to_btreepic(root, false);
433
434 string output = ss.str();
435
436 // Should have start-prefix line
437 EXPECT_TRUE(output.find("start-prefix") != string::npos);
438
439 // Should have start-key line
440 EXPECT_TRUE(output.find("start-key") != string::npos);
441
442 // Should have TAG commands for leaves
443 EXPECT_TRUE(output.find("TAG") != string::npos);
444
445 // Clean up
446 destroyRec(encoder.get_root());
447 destroyRec(encoder.get_freq_root());
448}
449
450TEST_F(HuffmanBtreepicTest, WithLevelAdjustment)
451{
452 Huffman_Encoder_Engine encoder = create_encoder("abcdefgh");
453 Freq_Node * root = encoder.get_freq_root();
454
455 stringstream ss;
456 output_ptr = &ss;
457 huffman_to_btreepic(root, true);
458
459 string output = ss.str();
460
461 // Should have all the standard elements
462 EXPECT_TRUE(output.find("start-prefix") != string::npos);
463 EXPECT_TRUE(output.find("start-key") != string::npos);
464
465 // Clean up
466 destroyRec(encoder.get_root());
467 destroyRec(encoder.get_freq_root());
468}
469
470TEST_F(HuffmanBtreepicTest, RepeatedCallsResetState)
471{
472 Huffman_Encoder_Engine encoder1 = create_encoder("aab");
473 Huffman_Encoder_Engine encoder2 = create_encoder("xyz");
474
475 stringstream ss1, ss2;
476
477 output_ptr = &ss1;
478 huffman_to_btreepic(encoder1.get_freq_root(), false);
479
480 output_ptr = &ss2;
481 huffman_to_btreepic(encoder2.get_freq_root(), false);
482
483 // Both outputs should be valid and independent
484 EXPECT_TRUE(ss1.str().find("start-prefix") != string::npos);
485 EXPECT_TRUE(ss2.str().find("start-prefix") != string::npos);
486
487 // They should be different
488 EXPECT_NE(ss1.str(), ss2.str());
489
490 // Clean up
491 destroyRec(encoder1.get_root());
492 destroyRec(encoder1.get_freq_root());
493 destroyRec(encoder2.get_root());
494 destroyRec(encoder2.get_freq_root());
495}
496
497// =============================================================================
498// Output Format Tests
499// =============================================================================
500
501TEST_F(HuffmanBtreepicTest, OutputStartsWithStartPrefix)
502{
503 Huffman_Encoder_Engine encoder = create_encoder("abc");
504 Freq_Node * root = encoder.get_freq_root();
505
506 stringstream ss;
507 output_ptr = &ss;
508 huffman_to_btreepic(root, false);
509
510 string output = ss.str();
511 EXPECT_EQ(output.substr(0, 12), "start-prefix");
512
513 destroyRec(encoder.get_root());
514 destroyRec(encoder.get_freq_root());
515}
516
517TEST_F(HuffmanBtreepicTest, OutputContainsKeyLine)
518{
519 Huffman_Encoder_Engine encoder = create_encoder("abc");
520 Freq_Node * root = encoder.get_freq_root();
521
522 stringstream ss;
523 output_ptr = &ss;
524 huffman_to_btreepic(root, false);
525
526 string output = ss.str();
527 EXPECT_TRUE(output.find("\nstart-key ") != string::npos);
528
529 destroyRec(encoder.get_root());
530 destroyRec(encoder.get_freq_root());
531}
532
533TEST_F(HuffmanBtreepicTest, TagCommandFormat)
534{
535 Freq_Node node;
536 node.get_key().first = "x";
537 node.get_key().second = 7;
538 LLINK(&node) = nullptr;
539 RLINK(&node) = nullptr;
540
541 stringstream ss;
542 output_ptr = &ss;
543 huffman_to_btreepic(&node, false);
544
545 string output = ss.str();
546 // TAG format: TAG <pos> "<symbol>" S 0 -20
547 EXPECT_TRUE(output.find("TAG 0 \"x\" S 0 -20") != string::npos);
548}
549
550// =============================================================================
551// minimal_gap Tests
552// =============================================================================
553
558
566
567// =============================================================================
568// Binary Tree Structure Tests
569// =============================================================================
570
571TEST_F(HuffmanBtreepicTest, ThreeNodeTree)
572{
573 /*
574 * Create a simple 3-node tree:
575 * root (3)
576 * / \
577 * left(1) right(2)
578 */
579 Freq_Node root, left, right;
580
581 root.get_key().first = "";
582 root.get_key().second = 3;
583 left.get_key().first = "a";
584 left.get_key().second = 1;
585 right.get_key().first = "b";
586 right.get_key().second = 2;
587
588 LLINK(&root) = &left;
589 RLINK(&root) = &right;
590 LLINK(&left) = nullptr;
591 RLINK(&left) = nullptr;
592 LLINK(&right) = nullptr;
593 RLINK(&right) = nullptr;
594
595 stringstream ss;
596 output_ptr = &ss;
597 huffman_to_btreepic(&root, false);
598
599 string output = ss.str();
600
601 // Should have TAGs for both leaves
602 EXPECT_TRUE(output.find("TAG") != string::npos);
603 EXPECT_TRUE(output.find("\"a\"") != string::npos);
604 EXPECT_TRUE(output.find("\"b\"") != string::npos);
605}
606
607// =============================================================================
608// Backward Compatibility Tests
609// =============================================================================
610
611TEST_F(HuffmanBtreepicTest, GlobalVariablesExist)
612{
613 // These should compile and be accessible
614 EXPECT_EQ(&infix_table, &infix_table);
615 EXPECT_EQ(&level_table, &level_table);
616 EXPECT_EQ(&pred, &pred);
617 EXPECT_EQ(&minimal_gap, &minimal_gap);
618}
619
620TEST_F(HuffmanBtreepicTest, LegacyApiWorks)
621{
622 Freq_Node node;
623 node.get_key().first = "a";
624 node.get_key().second = 1;
625 LLINK(&node) = nullptr;
626 RLINK(&node) = nullptr;
627
628 stringstream ss;
629 output_ptr = &ss; // Legacy: set global output pointer
630
631 // Legacy API call
632 huffman_to_btreepic(&node);
633
634 EXPECT_FALSE(ss.str().empty());
635}
636
637// =============================================================================
638// Edge Cases
639// =============================================================================
640
641TEST_F(HuffmanBtreepicTest, VeryLongSymbol)
642{
643 Freq_Node node;
644 node.get_key().first = "verylongsymbolname";
645 node.get_key().second = 1;
646 LLINK(&node) = nullptr;
647 RLINK(&node) = nullptr;
648
649 stringstream ss;
650 output_ptr = &ss;
651
652 // Should not crash due to offset array bounds
653 EXPECT_NO_THROW(huffman_to_btreepic(&node, true));
654}
655
656TEST_F(HuffmanBtreepicTest, ZeroFrequency)
657{
658 Freq_Node node;
659 node.get_key().first = "a";
660 node.get_key().second = 0;
661 LLINK(&node) = nullptr;
662 RLINK(&node) = nullptr;
663
664 stringstream ss;
665 output_ptr = &ss;
666 huffman_to_btreepic(&node, false);
667
668 EXPECT_TRUE(ss.str().find("\"0\"") != string::npos);
669}
670
671TEST_F(HuffmanBtreepicTest, LargeFrequency)
672{
673 Freq_Node node;
674 node.get_key().first = "a";
675 node.get_key().second = 1000000;
676 LLINK(&node) = nullptr;
677 RLINK(&node) = nullptr;
678
679 stringstream ss;
680 output_ptr = &ss;
681 huffman_to_btreepic(&node, false);
682
683 EXPECT_TRUE(ss.str().find("\"1000000\"") != string::npos);
684}
685
686// =============================================================================
687// Integration Test with Real Huffman Encoding
688// =============================================================================
689
690TEST_F(HuffmanBtreepicTest, IntegrationWithHuffmanEncoder)
691{
692 const char * text = "hello world";
693 Huffman_Encoder_Engine encoder;
694 char * str = const_cast<char*>(text);
695 encoder.read_input(str, true);
696
697 stringstream ss;
698 huffman_to_btreepic(encoder.get_freq_root(), ss, false);
699
700 string output = ss.str();
701
702 // Verify output structure
703 EXPECT_TRUE(output.find("start-prefix") != string::npos);
704 EXPECT_TRUE(output.find("start-key") != string::npos);
705
706 // Should have TAGs for leaf nodes
707 size_t tag_count = 0;
708 size_t pos = 0;
709 while ((pos = output.find("TAG", pos)) != string::npos)
710 {
711 tag_count++;
712 pos += 3;
713 }
714
715 // "hello world" has unique chars: h, e, l, o, ' ', w, r, d
716 // But l appears 3 times, o 2 times, so we have fewer unique symbols
717 EXPECT_GE(tag_count, 1u);
718
719 // Clean up
720 destroyRec(encoder.get_root());
721 destroyRec(encoder.get_freq_root());
722}
723
724int main(int argc, char **argv)
725{
726 ::testing::InitGoogleTest(&argc, argv);
727 return RUN_ALL_TESTS();
728}
Huffman.H
Huffman coding for data compression.
main
int main()
Definition ah_parallel_example.cc:690
LEFT
@ LEFT
Definition btreepic.C:171
RIGHT
@ RIGHT
Definition btreepic.C:171
Aleph::BinNode
Node for binary search tree.
Definition tpl_binNode.H:392
Aleph::BinNode::get_key
Key & get_key() noexcept
Definition tpl_binNode.H:392
Aleph::DynList::empty
void empty() noexcept
empty the list
Definition htlist.H:1689
Aleph::DynMapTree::insert
Pair * insert(const Key &key, const Data &data)
Insert a key-value pair.
Definition tpl_dynMapTree.H:144
Aleph::DynSetTree::size
const size_t & size() const
Returns the cardinality of the set.
Definition tpl_dynSetTree.H:1004
Aleph::Huffman_Encoder_Engine
Huffman encoder.
Definition Huffman.H:122
HuffmanBtreepicTest::create_encoder
Huffman_Encoder_Engine create_encoder(const string &text)
Definition huffman_btreepic_test.cc:65
root
__gmp_expr< T, __gmp_binary_expr< __gmp_expr< T, U >, unsigned long int, __gmp_root_function > > root(const __gmp_expr< T, U > &expr, unsigned long int l)
Definition gmpfrxx.h:4060
Aleph::RLINK
constexpr Node *& RLINK(Node *p) noexcept
Return the right tree of p.
Definition tpl_binNode.H:338
Aleph::destroyRec
void destroyRec(Node *&root) noexcept
Free recursively all the memory occupied by the tree root
Definition tpl_binNodeUtils.H:524
Aleph::LLINK
constexpr Node *& LLINK(Node *p) noexcept
Return a pointer to left subtree.
Definition tpl_binNode.H:322
huffman_btreepic.H
Huffman tree visualization for btreepic LaTeX package.
reset_huffman_btreepic_state
void reset_huffman_btreepic_state() noexcept
Reset global state for a new tree processing.
Definition huffman_btreepic.H:206
pred
Freq_Node * pred
Predecessor node in level-order traversal.
Definition huffman_btreepic.H:179
get_offset
long double get_offset(size_t index) noexcept
Get safe offset value with bounds checking.
Definition huffman_btreepic.H:195
NO_OFFSET
@ NO_OFFSET
No offset applied.
Definition huffman_btreepic.H:109
num_digits
size_t num_digits(const int &n)
Compute number of decimal digits in an integer.
Definition huffman_btreepic.H:375
infix_table
DynMapTree< Freq_Node *, Infix_Desc, Treap > infix_table
Map from node pointer to infix position descriptor.
Definition huffman_btreepic.H:170
minimal_gap
int minimal_gap
Minimum gap (in nodes) before applying offset adjustment.
Definition huffman_btreepic.H:182
huffman_to_btreepic
void huffman_to_btreepic(Freq_Node *p, const bool with_level_adjust=false)
Generate btreepic specification for a Huffman tree.
Definition huffman_btreepic.H:476
output_ptr
std::ostream * output_ptr
Output stream pointer for btreepic commands.
Definition huffman_btreepic.H:176
level_table
Level_Table level_table
Map from node pointer to level traversal descriptor.
Definition huffman_btreepic.H:173
TEST_F
TEST_F(HuffmanBtreepicTest, InfixDescDefaultConstruction)
Definition huffman_btreepic_test.cc:78
Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693
std
STL namespace.
Infix_Desc
Descriptor for infix (in-order) traversal position.
Definition huffman_btreepic.H:122
Level_Desc
Descriptor for level-order traversal information.
Definition huffman_btreepic.H:146
output
ofstream output
Definition writeHeap.C:213