Class: CodeCook::Greedy::NodeQueue

Inherits:

Object

• Object
• CodeCook::Greedy::NodeQueue

show all

Defined in:

手写代码必备手册(Ruby版).rb

Instance Attribute Summary (collapse)

• - (Object) huffman_root

  Returns the value of attribute huffman_root.

• - (Object) nodes

  Returns the value of attribute nodes.

Instance Method Summary (collapse)

• - (Object) generate_tree
• - (NodeQueue) initialize(string) constructor

  A new instance of NodeQueue.

• - (Object) merge_nodes(node1, node2)

579
580
581
582
583
584
585
586
587
588
589
590

# File '手写代码必备手册(Ruby版).rb', line 579

def initialize(string)
    frequencies = {}
    string.each_char do |c|
        frequencies[c] ||= 0
        frequencies[c] += 1
    end
    @nodes = []
    frequencies.each do |c, w|
        @nodes << Node.new(:symbol => c, :weight => w)
    end
    generate_tree
end

577
578
579

# File '手写代码必备手册(Ruby版).rb', line 577

def huffman_root
  @huffman_root
end

577
578
579

# File '手写代码必备手册(Ruby版).rb', line 577

def nodes
  @nodes
end

592
593
594
595
596
597
598
599
600
601

# File '手写代码必备手册(Ruby版).rb', line 592

def generate_tree
    while @nodes.size > 1
        sorted = @nodes.sort { |a,b| a.weight <=> b.weight }
        to_merge = []
        2.times { to_merge << sorted.shift }
        sorted << merge_nodes(to_merge[0], to_merge[1])
        @nodes = sorted
    end
    @huffman_root = @nodes.first
end

603
604
605
606
607
608
609

# File '手写代码必备手册(Ruby版).rb', line 603

def merge_nodes(node1, node2)
    left = node1.weight > node2.weight ? node2 : node1
    right = left == node1 ? node2 : node1
    node = Node.new(:weight => left.weight + right.weight, :left => left, :right => right)
    left.parent = right.parent = node
    node
end