Class: Cabriolet::HLP::QuickHelp::HuffmanTree

Inherits:
Object
  • Object
show all
Defined in:
lib/cabriolet/hlp/quickhelp/huffman_tree.rb

Overview

Huffman tree for QuickHelp topic compression

Represents a Huffman tree that encodes symbols 0-255. Based on the QuickHelp binary format specification.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ HuffmanTree

Initialize empty tree



29
30
31
32
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 29

def initialize
  @root = nil
  @symbol_count = 0
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



11
12
13
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 11

def root
  @root
end

#symbol_count ⇒ Object (readonly)

Returns the value of attribute symbol_count.



11
12
13
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 11

def symbol_count
  @symbol_count
end

Class Method Details

.deserialize(node_values) ⇒ HuffmanTree

Deserialize Huffman tree from node values

Parameters:

  • node_values (Array<Integer>) —

    Array of 16-bit node values

Returns:

Raises:



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 53

def self.deserialize(node_values)
  tree = new
  return tree if node_values.empty?

  n = node_values.length
  if n.even?
    raise Cabriolet::ParseError,
          "Invalid Huffman tree: expected odd number of nodes"
  end

  nodes = Array.new(n) { Node.new }
  symbol_exists = Array.new(256, false)

  n.times do |i|
    node = nodes[i]
    node_value = node_values[i]

    if node_value.negative? # Leaf node (bit 15 set)
      symbol = node_value & 0xFF
      if symbol_exists[symbol]
        raise Cabriolet::ParseError,
              "Invalid Huffman tree: symbol #{symbol} already encoded"
      end

      node.symbol = symbol
      symbol_exists[symbol] = true
    else # Internal node
      child0 = node_value / 2
      child1 = i + 1

      # Validate child indices are within bounds
      unless child0 < n && child1 < n
        raise Cabriolet::ParseError,
              "Invalid Huffman tree: invalid child node location (child0=#{child0}, child1=#{child1}, n=#{n})"
      end

      # Check for cycles by verifying left child hasn't been assigned yet
      if !nodes[child0].nil? && nodes[child0].left_child
        raise Cabriolet::ParseError,
              "Invalid Huffman tree: cycle detected"
      end

      node.left_child = nodes[child0]
      node.right_child = nodes[child1]
    end
  end

  tree.instance_variable_set(:@root, nodes[0])
  tree.instance_variable_set(:@symbol_count, (n / 2) + 1)
  tree
end

Instance Method Details

#create_decoder ⇒ HuffmanDecoder

Create a decoder for this tree

Returns:



108
109
110
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 108

def create_decoder
  HuffmanDecoder.new(self)
end

#empty? ⇒ Boolean

Check if tree is empty

Returns:

  • (Boolean) —

    true if empty



37
38
39
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 37

def empty?
  @root.nil?
end

#singular? ⇒ Boolean

Check if tree has single node

Returns:

  • (Boolean) —

    true if singular



44
45
46
 
# File 'lib/cabriolet/hlp/quickhelp/huffman_tree.rb', line 44

def singular?
  !@root.nil? && @root.leaf?
end