huffman_btreepic.H File Reference

Huffman tree visualization for btreepic LaTeX package. More...

#include <cstdlib>
#include <ostream>
#include <algorithm>
#include <tpl_dynMapTree.H>
#include <Huffman.H>

Include dependency graph for huffman_btreepic.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Infix_Desc
	Descriptor for infix (in-order) traversal position. More...
struct	Level_Desc
	Descriptor for level-order traversal information. More...

Typedefs
using	Level_Table = DynMapTree< Freq_Node *, Level_Desc, Treap >
	Type alias for the level descriptor map.

Enumerations
enum	Offset { NO_OFFSET , LEFT , RIGHT }
	Horizontal offset direction for node label adjustment. More...

Functions
long double	get_offset (size_t index) noexcept
	Get safe offset value with bounds checking.
void	reset_huffman_btreepic_state () noexcept
	Reset global state for a new tree processing.
void	save_infix_pos (Freq_Node *p, int level, int pos)
	Save infix position for a node.
void	save_level_pos_1 (Freq_Node *p, int pos, bool is_left)
	First pass level-order callback: record child direction.
void	save_level_pos_2 (Freq_Node *p, int pos, bool is_left)
	Second pass level-order callback: link successors.
void	write_prefix (Freq_Node *p, int level, int prefix_pos)
	Write node position in prefix order.
void	write_freq (Freq_Node *p, int level, int pos)
	Write node frequency value.
void	write_leaves (Freq_Node *p, int level, int pos)
	Write leaf node labels with LaTeX escaping.
size_t	num_digits (const int &n)
	Compute number of decimal digits in an integer.
void	adjust_nodes (Freq_Node *p, int p_level, int p_infix_pos)
	Adjust node positions to prevent label overlap.
void	huffman_to_btreepic (Freq_Node *p, const bool with_level_adjust=false)
	Generate btreepic specification for a Huffman tree.
void	huffman_to_btreepic (Freq_Node *p, std::ostream &output, bool with_level_adjust=false)
	Generate btreepic specification to an output stream.

Variables
DynMapTree< Freq_Node *, Infix_Desc, Treap >	infix_table
	Map from node pointer to infix position descriptor.
Level_Table	level_table
	Map from node pointer to level traversal descriptor.
std::ostream *	output_ptr = nullptr
	Output stream pointer for btreepic commands.
Freq_Node *	pred = nullptr
	Predecessor node in level-order traversal.
int	minimal_gap = 4
	Minimum gap (in nodes) before applying offset adjustment.
constexpr size_t	MAX_OFFSET_INDEX = 7
	Maximum valid index for offset array.
const long double	offset [] = { 10, 15, 25, 40, 55, 65, 85, 90 }
	Offset values indexed by symbol string length (bounded by MAX_OFFSET_INDEX)

Detailed Description

Huffman tree visualization for btreepic LaTeX package.

This header provides utilities for generating btreepic specifications from Huffman trees. The btreepic package is a LaTeX tool for drawing binary trees with customizable node labels, positions, and annotations.

Features

• Generates btreepic format output for Huffman frequency trees
• Supports automatic node positioning with level-based adjustments
• Handles special LaTeX characters in symbol labels
• Produces publication-quality tree diagrams

Output Format

The generated output consists of:

• start-prefix: Node positions in prefix order
• start-key: Frequency values for each node
• TAG commands: Leaf node labels with symbol names
• xoffset commands: Horizontal adjustments for overlapping labels

Usage Example

#include <Huffman.H>
#include <huffman_btreepic.H>
#include <fstream>
 
// Build Huffman tree
Huffman_Encoder_Engine encoder;
encoder.read_input("sample text", true);
 
// Method 1: Using output stream parameter (preferred)
std::ofstream out("tree.btreepic");
huffman_to_btreepic(encoder.get_freq_root(), out);
 
// Method 2: Using global output_ptr (legacy, deprecated)
output_ptr = &out;
huffman_to_btreepic(encoder.get_freq_root());
 
// With level adjustment for dense trees
huffman_to_btreepic(encoder.get_freq_root(), out, true);

Thread Safety

Warning

This module uses global state for tree traversal and is NOT thread-safe. Each call to huffman_to_btreepic() must complete before another call begins.

See also

Huffman.H for the Huffman encoding implementation

btreepic LaTeX package documentation

Author

Leandro Rabindranath Leon

Definition in file huffman_btreepic.H.

Typedef Documentation

Level_Table

using Level_Table = DynMapTree<Freq_Node *, Level_Desc, Treap>

Type alias for the level descriptor map.

Definition at line 163 of file huffman_btreepic.H.

Enumeration Type Documentation

Offset

enum Offset

Horizontal offset direction for node label adjustment.

Used to track whether a node's label has been shifted left or right to avoid overlapping with adjacent nodes at the same level.

Enumerator
NO_OFFSET	No offset applied.
LEFT	Shifted to the left.
RIGHT	Shifted to the right.

Definition at line 107 of file huffman_btreepic.H.

Function Documentation

adjust_nodes()

void adjust_nodes ( Freq_Node *  p, int  p_level, int  p_infix_pos  )

inline

Adjust node positions to prevent label overlap.

Callback for in-order traversal that checks if adjacent nodes at the same level are too close together. If they have opposite orientations, xoffset commands are generated to shift labels apart.

Parameters

p	Node pointer
p_level	Tree level of node
p_infix_pos	In-order position of node

Definition at line 391 of file huffman_btreepic.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::BinNode< Key >::get_key(), get_offset(), infix_table, LEFT, level_table, minimal_gap, NO_OFFSET, output_ptr, Infix_Desc::pos, RIGHT, and Aleph::DynSetTree< Key, Tree, Compare >::size().

Referenced by huffman_to_btreepic().

get_offset()

long double get_offset ( size_t  index )

inlinenoexcept

Get safe offset value with bounds checking.

Parameters

index

Symbol length

Returns

Offset value, clamped to valid range

Definition at line 195 of file huffman_btreepic.H.

References MAX_OFFSET_INDEX, and offset.

Referenced by adjust_nodes(), TEST_F(), and TEST_F().

huffman_to_btreepic() [1/2]

void huffman_to_btreepic ( Freq_Node *  p, const bool  with_level_adjust = false  )

inline

Generate btreepic specification for a Huffman tree.

Produces a complete btreepic specification that can be compiled with LaTeX to render the Huffman frequency tree. The output includes:

1. Tree structure (start-prefix line)
2. Node labels with frequencies (start-key line)
3. Leaf symbol annotations (TAG commands)
4. Optional position adjustments (xoffset commands)

Parameters

p	Root of the Huffman frequency tree
with_level_adjust	If true, apply automatic position adjustments to prevent overlapping labels at dense levels

Precondition

output_ptr must be set to a valid output stream before calling

p must be a valid Freq_Node pointer (may be nullptr for empty tree)

Note

This function uses global state and is NOT thread-safe.

See also

Huffman_Encoder_Engine::get_freq_root() for obtaining the root

Definition at line 476 of file huffman_btreepic.H.

References adjust_nodes(), Aleph::divide_and_conquer_partition_dp(), Aleph::inOrderRec(), Aleph::levelOrder(), output_ptr, Aleph::preOrderRec(), reset_huffman_btreepic_state(), save_infix_pos(), save_level_pos_1(), save_level_pos_2(), write_freq(), write_leaves(), and write_prefix().

Referenced by huffman_to_btreepic(), main(), main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

huffman_to_btreepic() [2/2]

void huffman_to_btreepic ( Freq_Node *  p, std::ostream &  output, bool  with_level_adjust = false  )

inline

Generate btreepic specification to an output stream.

Preferred overload that takes an explicit output stream parameter instead of using the global output_ptr.

Parameters

p	Root of the Huffman frequency tree
output	Output stream for btreepic commands
with_level_adjust	If true, apply automatic position adjustments

See also

huffman_to_btreepic(Freq_Node*, bool) for details

Definition at line 523 of file huffman_btreepic.H.

References Aleph::divide_and_conquer_partition_dp(), huffman_to_btreepic(), output, and output_ptr.

num_digits()

size_t num_digits ( const int &  n )

inline

Compute number of decimal digits in an integer.

Parameters

n	Integer value

Returns

Number of digits

Definition at line 375 of file huffman_btreepic.H.

Referenced by TEST_F(), and TEST_F().

reset_huffman_btreepic_state()

void reset_huffman_btreepic_state ( )

inlinenoexcept

Reset global state for a new tree processing.

Clears all traversal tables and resets the predecessor pointer. Called automatically at the start of huffman_to_btreepic().

Definition at line 206 of file huffman_btreepic.H.

References Aleph::DynSetTree< Key, Tree, Compare >::empty(), infix_table, level_table, and pred.

Referenced by huffman_to_btreepic(), HuffmanBtreepicTest::SetUp(), HuffmanBtreepicTest::TearDown(), TEST_F(), TEST_F(), and TEST_F().

save_infix_pos()

void save_infix_pos ( Freq_Node *  p, int  level, int  pos  )

inline

Save infix position for a node.

Callback for in-order traversal that records each node's position and level in the infix_table.

Parameters

p	Node pointer
level	Tree level
pos	In-order position

Definition at line 227 of file huffman_btreepic.H.

References infix_table.

Referenced by huffman_to_btreepic().

save_level_pos_1()

void save_level_pos_1 ( Freq_Node *  p, int  pos, bool  is_left  )

inline

First pass level-order callback: record child direction.

Callback for level-order traversal that records whether each node is a left or right child.

Parameters

p	Node pointer
pos	Position in level (unused)
is_left	True if node is a left child

Definition at line 242 of file huffman_btreepic.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), and level_table.

Referenced by huffman_to_btreepic().

save_level_pos_2()

void save_level_pos_2 ( Freq_Node *  p, int  pos, bool  is_left  )

inline

Second pass level-order callback: link successors.

Callback for level-order traversal that links each node to its successor in level-order.

Parameters

p	Node pointer
pos	Position in level-order traversal
is_left	Unused

Definition at line 258 of file huffman_btreepic.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), level_table, and pred.

Referenced by huffman_to_btreepic().

write_freq()

void write_freq ( Freq_Node *  p, int  level, int  pos  )

inline

Write node frequency value.

Callback for in-order traversal that outputs the frequency value of each node as a quoted string for btreepic labels.

Parameters

p	Node pointer
level	Unused
pos	Unused

Definition at line 305 of file huffman_btreepic.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::BinNode< Key >::get_key(), and output_ptr.

Referenced by huffman_to_btreepic().

write_leaves()

void write_leaves ( Freq_Node *  p, int  level, int  pos  )

inline

Write leaf node labels with LaTeX escaping.

Callback for in-order traversal that outputs TAG commands for leaf nodes (symbols). Handles special LaTeX characters and whitespace with appropriate escaping.

Parameters

p	Node pointer
level	Unused
pos	In-order position

Definition at line 325 of file huffman_btreepic.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::BinNode< Key >::get_key(), LLINK, output_ptr, and RLINK.

Referenced by huffman_to_btreepic().

write_prefix()

void write_prefix ( Freq_Node *  p, int  level, int  prefix_pos  )

inline

Write node position in prefix order.

Callback for prefix-order traversal that outputs the infix position of each node, building the btreepic structure specification.

Parameters

p	Node pointer
level	Unused
prefix_pos	Unused

Definition at line 286 of file huffman_btreepic.H.

References Aleph::divide_and_conquer_partition_dp(), and infix_table.

Referenced by huffman_to_btreepic().

Variable Documentation

infix_table

DynMapTree<Freq_Node *, Infix_Desc, Treap> infix_table

inline

Map from node pointer to infix position descriptor.

Definition at line 170 of file huffman_btreepic.H.

Referenced by adjust_nodes(), reset_huffman_btreepic_state(), save_infix_pos(), TEST_F(), TEST_F(), and write_prefix().

level_table

Level_Table level_table

inline

Map from node pointer to level traversal descriptor.

Definition at line 173 of file huffman_btreepic.H.

Referenced by adjust_nodes(), reset_huffman_btreepic_state(), save_level_pos_1(), save_level_pos_2(), TEST_F(), and TEST_F().

MAX_OFFSET_INDEX

constexpr size_t MAX_OFFSET_INDEX = 7

inlineconstexpr

Maximum valid index for offset array.

Definition at line 185 of file huffman_btreepic.H.

Referenced by get_offset().

minimal_gap

int minimal_gap = 4

inline

Minimum gap (in nodes) before applying offset adjustment.

Definition at line 182 of file huffman_btreepic.H.

Referenced by adjust_nodes(), TEST_F(), TEST_F(), and TEST_F().

offset

const long double offset[] = { 10, 15, 25, 40, 55, 65, 85, 90 }

inline

Offset values indexed by symbol string length (bounded by MAX_OFFSET_INDEX)

Definition at line 188 of file huffman_btreepic.H.

Referenced by Aleph::FFT< Real >::PartitionedConvolver::PartitionedConvolver(), Aleph::FFT< Real >::ISTFTProcessor::accumulate_frame(), Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar(), Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range(), Aleph::FFT< Real >::axis_base_offsets(), Aleph::parallel_detail::bounds_for_chunk(), Aleph::FFT< Real >::OverlapAddBank::build_signal_batch(), Aleph::FFT< Real >::OverlapAdd::build_signal_block(), Aleph::FFT< Real >::OverlapAddBank::build_signal_block(), Aleph::FFT< Real >::OverlapAddBank::convolve_impl(), Aleph::FFT< Real >::OverlapAdd::convolve_impl(), Aleph::Dnode< T >::data_to_node(), Aleph::find_position(), Aleph::FFT< Real >::frame_offsets_impl(), Aleph::FFT< Real >::frame_signal(), get_offset(), Aleph::FFT< Real >::Plan::initialize_power_of_two_plan(), Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles(), RingFileCache< T >::is_valid_offset(), Aleph::FFT< Real >::istft_impl(), Aleph::DynHashTable< Key, HashTable, Cmp >::key_to_bucket(), Aleph::ODhashTable< Key, Cmp >::key_to_bucket(), Aleph::OLhashTable< Key, Cmp >::key_to_bucket(), Aleph::parallel_zip_detail::make_iterators_at(), Aleph::Init_Arc< GT >::operator()(), Aleph::FFT< Real >::overlap_add_frames(), Aleph::pminmax(), Aleph::FFT< Real >::OverlapAddBank::pprocess_block(), Aleph::FFT< Real >::OverlapAdd::pprocess_block(), Aleph::FFT< Real >::OverlapAddBank::process_block(), Aleph::FFT< Real >::OverlapAdd::process_block(), process_text_arc(), Aleph::pzip_all_n(), Aleph::pzip_count_if_n(), Aleph::pzip_exists_n(), Aleph::pzip_foldl_n(), Aleph::pzip_for_each_n(), Aleph::pzip_maps_n(), Aleph::Gen_File_B_Tree< Key, Compare, MinDegree, Codec >::read_storage_page_if_current(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::read_storage_page_if_current(), Aleph::ArrayQueue< T >::rear_item(), Aleph::DynLhashTable< Key, Record, Cmp >::record_to_bucket(), Aleph::Gen_File_B_Tree< Key, Compare, MinDegree, Codec >::seekp_to(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::seekp_to(), Aleph::sift_down_subrange(), Aleph::FFT< Real >::OverlapAddBank::slice_chunk(), Aleph::FFT< Real >::slice_copy(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), Aleph::FFT< Real >::transform_stft_frames(), Aleph::FFT< Real >::unwrap_phase(), and Aleph::z_search().

output_ptr

std::ostream* output_ptr = nullptr

inline

Output stream pointer for btreepic commands.

Definition at line 176 of file huffman_btreepic.H.

Referenced by adjust_nodes(), huffman_to_btreepic(), huffman_to_btreepic(), main(), main(), HuffmanBtreepicTest::SetUp(), HuffmanBtreepicTest::TearDown(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), write_freq(), and write_leaves().

pred

Freq_Node* pred = nullptr

inline

Predecessor node in level-order traversal.

Definition at line 179 of file huffman_btreepic.H.

Referenced by Aleph::DynSkipList< Key, Compare >::all(), Aleph::DynSkipList< Key, Compare >::all(), Aleph::all_of_tuple(), Aleph::zip_index_detail::all_of_tuple_impl(), Aleph::all_perm(), Aleph::all_perm(), Aleph::analyze_fit(), Aleph::any_of_tuple(), Aleph::zip_index_detail::any_of_tuple_impl(), Aleph::MonotonePolygonTriangulation::build_faces_from_diagonals(), GraphCommon< GT, Node, Arc >::collect_arcs_if(), Aleph::count_if(), Aleph::FunctionalMixin< Derived, Type >::count_if(), Aleph::drop_while(), Aleph::DynSkipList< Key, Compare >::exists(), Aleph::DynSkipList< Key, Compare >::exists(), Aleph::exists_perm(), Aleph::exists_perm(), Aleph::detail::fallback_all_of(), Aleph::detail::fallback_any_of(), Aleph::detail::fallback_none_of(), Aleph::filter_perm(), Aleph::filter_perm(), Aleph::Filter_Iterator< Container, It, Show_Item >::find_if(), Aleph::FunctionalMixin< Derived, Type >::find_index(), Aleph::find_opt(), Aleph::find_opt(), Aleph::find_ptr(), Aleph::find_ptr(), Aleph::find_ptr(), Aleph::find_ptr(), Aleph::GenTdRbTree< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_ridge(), Aleph::SweepLineSegmentIntersection::StatusTree::fresh_label_between(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::fresh_label_between(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::insert(), Aleph::SweepLineSegmentIntersection::StatusTree::insert(), Aleph::karp_minimum_mean_cycle(), Aleph::DynSkipList< Key, Compare >::none(), Aleph::DynSkipList< Key, Compare >::none(), Aleph::FunctionalMixin< Derived, Type >::none(), Aleph::FunctionalMixin< Derived, Type >::none(), Aleph::none_of_tuple(), Aleph::none_perm(), Aleph::none_perm(), Aleph::SweepLineSegmentIntersection::operator()(), Aleph::pall(), Aleph::pcount_if(), Aleph::pexists(), Aleph::pfilter(), Aleph::pfind(), Aleph::pfind_value(), Aleph::pnone(), Aleph::ppartition(), Aleph::SweepLineSegmentIntersection::StatusTree::predecessor(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::predecessor_for_insert(), Aleph::SweepLineSegmentIntersection::StatusTree::predecessor_for_insert(), Aleph::pzip_all_n(), Aleph::pzip_all_n(), Aleph::pzip_count_if_n(), Aleph::pzip_count_if_n(), Aleph::pzip_exists_n(), Aleph::pzip_exists_n(), Aleph::detail::ranges_all_of(), Aleph::detail::ranges_any_of(), Aleph::detail::ranges_count_if(), Aleph::detail::ranges_none_of(), GraphCommon< GT, Node, Arc >::remove_arcs_if(), Aleph::Gen_File_B_Tree< Key, Compare, MinDegree, Codec >::remove_from(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::remove_from(), reset_huffman_btreepic_state(), save_level_pos_2(), Aleph::stl_adjacent_all(), Aleph::stl_adjacent_exists(), Aleph::stl_all(), Aleph::stl_any(), Aleph::stl_count(), Aleph::stl_drop_while(), Aleph::stl_exists(), Aleph::stl_filter(), Aleph::stl_filteri(), Aleph::stl_find(), Aleph::stl_find_index(), Aleph::stl_find_last(), Aleph::stl_none(), Aleph::stl_partition(), Aleph::stl_reject(), Aleph::stl_span(), Aleph::stl_take_while(), Aleph::stl_zip_all(), Aleph::stl_zip_all_eq(), Aleph::stl_zip_any(), Aleph::stl_zip_count(), Aleph::stl_zip_drop_while(), Aleph::stl_zip_exists(), Aleph::stl_zip_filter(), Aleph::stl_zip_filteri(), Aleph::stl_zip_find_first(), Aleph::stl_zip_find_index(), Aleph::stl_zip_find_last(), Aleph::stl_zip_none(), Aleph::stl_zip_partition(), Aleph::stl_zip_take_while(), Aleph::stl_zip_traverse(), Aleph::stl_zip_traverse_eq(), Aleph::take_while(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), Aleph::uni_all(), Aleph::uni_any(), Aleph::uni_count(), Aleph::uni_drop_while(), Aleph::uni_exists(), Aleph::uni_filter(), Aleph::uni_filteri(), Aleph::uni_find(), Aleph::uni_find_index(), Aleph::uni_none(), Aleph::uni_partition(), Aleph::uni_take_while(), Aleph::uni_zip_all(), Aleph::uni_zip_all_eq(), Aleph::uni_zip_any(), Aleph::uni_zip_count(), Aleph::uni_zip_drop_while(), Aleph::uni_zip_exists(), Aleph::uni_zip_filter(), Aleph::uni_zip_filteri(), Aleph::uni_zip_find_first(), Aleph::uni_zip_none(), Aleph::uni_zip_partition(), Aleph::uni_zip_take_while(), Aleph::uni_zip_traverse(), Aleph::BoundedChannel< T >::wait_with_cancellation(), Aleph::zip_drop_while(), and Aleph::zip_take_while().