huffman_btreepic.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#ifndef HUFFMAN_BTREEPIC_H
#define HUFFMAN_BTREEPIC_H
 
#include <cstdlib>
#include <ostream>
#include <algorithm>
#include <tpl_dynMapTree.H>
#include <Huffman.H>
 
enum Offset
{
  NO_OFFSET,  
  LEFT,       
  RIGHT       
};
 
struct Infix_Desc
{
  int pos = 0;       
  int level = 0;     
  Offset offset;     
 
  Infix_Desc() : offset(NO_OFFSET) {}
 
  Infix_Desc(int i, int l) : pos(i), level(l), offset(NO_OFFSET) {}
};
 
struct Level_Desc
{
  bool is_left = false;             
  Freq_Node * level_succ = nullptr; 
 
  Level_Desc() = default;
 
  Level_Desc(bool il, Freq_Node * succ = nullptr)
    : is_left(il), level_succ(succ) {}
};
 
using Level_Table = DynMapTree<Freq_Node *, Level_Desc, Treap>;
 
// ============================================================================
// Global state (module-level, not thread-safe)
// ============================================================================
 
inline DynMapTree<Freq_Node *, Infix_Desc, Treap> infix_table;
 
inline Level_Table level_table;
 
inline std::ostream * output_ptr = nullptr;
 
inline Freq_Node * pred = nullptr;
 
inline int minimal_gap = 4;
 
inline constexpr size_t MAX_OFFSET_INDEX = 7;
 
inline const long double offset[] = { 10, 15, 25, 40, 55, 65, 85, 90 };
 
[[nodiscard]] inline long double get_offset(size_t index) noexcept
{
  return offset[std::min(index, MAX_OFFSET_INDEX)];
}
 
inline void reset_huffman_btreepic_state() noexcept
{
  infix_table.empty();
  level_table.empty();
  pred = nullptr;
}
 
// ============================================================================
// Traversal callback functions
// ============================================================================
 
inline void save_infix_pos(Freq_Node * p, int level, int pos)
{
  infix_table.insert(p, Infix_Desc(pos, level));
}
 
inline void save_level_pos_1(Freq_Node * p, int pos, bool is_left)
{
  (void)pos;
  level_table.insert(p, Level_Desc(is_left));
}
 
inline void save_level_pos_2(Freq_Node * p, int pos, bool is_left)
{
  (void)is_left;
 
  if (pos == 0)
    {
      assert(pred == nullptr);
      pred = p;
      return;
    }
 
  assert(pred != nullptr and pred != p);
 
  Level_Desc & level_desc_pred = level_table.find(pred);
  level_desc_pred.level_succ = p;
  pred = p;
}
 
inline void write_prefix(Freq_Node * p, int level, int prefix_pos)
{
  (void)level;
  (void)prefix_pos;
 
  const Infix_Desc & infix_desc = infix_table[p];
  *output_ptr << static_cast<int>(infix_desc.pos) << " ";
}
 
inline void write_freq(Freq_Node * p, int level, int pos)
{
  (void)level;
  (void)pos;
 
  const size_t & freq = p->get_key().second;
  *output_ptr << "\"" << freq << "\" ";
}
 
inline void write_leaves(Freq_Node * p, int level, int pos)
{
  (void)level;
 
  // Only process leaf nodes
  if (not (LLINK(p) == nullptr and RLINK(p) == nullptr))
    return;
 
  const std::string & key = p->get_key().first;
 
  *output_ptr << "TAG " << pos << " \"";
 
  // Escape special LaTeX characters
  if (key == "\n")
    *output_ptr << "$\\backslash$n";
  else if (key == "")
    *output_ptr << "$\\neg$";
  else if (key == "$")
    *output_ptr << "\\$";
  else if (key == "&")
    *output_ptr << "\\&";
  else if (key == "#")
    *output_ptr << "\\#";
  else if (key == "%")
    *output_ptr << "\\%";
  else if (key == "{")
    *output_ptr << "$\\{$";
  else if (key == "}")
    *output_ptr << "$\\}$";
  else if (key == "^")
    *output_ptr << "\\^";
  else if (key == "_")
    *output_ptr << "\\_";
  else if (key == "\\")
    *output_ptr << "$\\backslash$";
  else if (key == " ")
    *output_ptr << "$\\square$";
  else if (key == "\"")
    *output_ptr << "$\\prime\\prime$";
  else
    *output_ptr << key;
 
  *output_ptr << "\" S 0 -20 " << std::endl;
}
 
[[nodiscard]] inline size_t num_digits(const int & n)
{
  return std::to_string(n).size();
}
 
inline void adjust_nodes(Freq_Node * p, int p_level, int p_infix_pos)
{
  // Last node has no successor to check
  if (static_cast<size_t>(p_infix_pos) == level_table.size() - 1)
    return;
 
  Level_Desc & p_level_desc = level_table[p];
  Freq_Node *& p_succ = p_level_desc.level_succ;
 
  // No successor in level-order?
  if (p_succ == nullptr)
    return;
 
  Infix_Desc & p_succ_infix_desc = infix_table[p_succ];
 
  // Not at the same level?
  if (p_level != p_succ_infix_desc.level)
    return;
 
  const int & p_succ_infix_pos = p_succ_infix_desc.pos;
 
  // Separation in nodes between the two
  const int diff_pos = p_succ_infix_pos - p_infix_pos;
 
  // Sufficiently separated?
  if (diff_pos > minimal_gap)
    return;
 
  Level_Desc & p_suc_level_desc = level_table[p_succ];
 
  // Same orientation (both left or both right children)?
  if (p_suc_level_desc.is_left == p_level_desc.is_left)
    return;
 
  Infix_Desc & p_infix_desc = infix_table[p];
 
  const std::string & kp = p->get_key().first;
  const size_t kp_sz = kp.size();
 
  // Apply left offset to current node if not already offset
  if (p_infix_desc.offset == NO_OFFSET)
    {
      *output_ptr << "xoffset " << p_infix_pos << " "
                  << -get_offset(kp_sz) << std::endl;
      p_infix_desc.offset = LEFT;
    }
 
  assert(p_succ_infix_desc.offset == NO_OFFSET);
 
  const std::string & k_succ = p_succ->get_key().first;
  const size_t k_succ_sz = k_succ.size();
 
  // Apply right offset to successor
  *output_ptr << "xoffset " << p_succ_infix_pos << " "
              << static_cast<int>(get_offset(k_succ_sz) / 2) << std::endl;
 
  p_succ_infix_desc.offset = RIGHT;
}
 
// ============================================================================
// Main API
// ============================================================================
 
inline void huffman_to_btreepic(Freq_Node * p, const bool with_level_adjust = false)
{
  if (p == nullptr or output_ptr == nullptr)
    return;
 
  // Reset state for new tree
  reset_huffman_btreepic_state();
 
  // First pass: record infix positions
  inOrderRec(p, save_infix_pos);
 
  // Write tree structure in prefix order
  *output_ptr << "start-prefix ";
  preOrderRec(p, write_prefix);
  *output_ptr << std::endl << "start-key ";
 
  // Write frequency labels
  inOrderRec(p, write_freq);
  *output_ptr << std::endl;
 
  // Write leaf node tags
  inOrderRec(p, write_leaves);
  *output_ptr << std::endl;
 
  if (not with_level_adjust)
    return;
 
  // Level adjustment: two passes for linking successors
  levelOrder(p, save_level_pos_1);
  levelOrder(p, save_level_pos_2);
 
  // Final pass: adjust overlapping labels
  inOrderRec(p, adjust_nodes);
}
 
inline void huffman_to_btreepic(Freq_Node * p,
                                std::ostream & output,
                                bool with_level_adjust = false)
{
  output_ptr = &output;
  huffman_to_btreepic(p, with_level_adjust);
}
 
#endif // HUFFMAN_BTREEPIC_H