Class: Huffman::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/huffman/tree.rb

Instance Method Summary collapse

Constructor Details

#initialize(frequencies) ⇒ Tree

Returns a new instance of Tree.



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/huffman/tree.rb', line 16

def initialize(frequencies)

	# Liste de noeuds feuilles toujours triés par ordre croissant qui vont nous permettre de créer l'arbre de Huffman
	nodes = PriorityQueue.new	

	frequencies.map{ |freq| nodes.push(Node.new(freq[1], freq[0]), freq[1]) }

	# Tant qu'il y'a pas plus qu'un seul noeud dans la liste
	until nodes.length == 1
		# 1) On créer un noeud dont ses fils sont les deux premiers noeuds du tableau triés de noeud et la valeur leur somme	
		# On enlève les deux premiers noeuds
		node1, node2 = nodes.delete_min.first, nodes.delete_min.first
		# On créer un noeud parent
		parent = Node.new(node1.value+node2.value,nil,node1,node2)
		# 2) On ajoute le noeud à la liste 
		nodes.push(parent, parent.value) 
	end	
	@root = nodes.delete_min.first
	set_binary_values 
end

Instance Method Details

#dictionnary ⇒ Object

On récupére la table de correspondance



38
39
40
41
42
43
44
45
 
# File 'lib/huffman/tree.rb', line 38

def dictionnary
	h = {}
	#set_binary_values{|node| h[node.binary_value] = node.symbol if node.symbol}
	# Equivalent mais plus rapide que :
	# set_binary_values 
	visit(:postorder){|node| h[node.binary_value] = node.symbol if node.symbol }
	h
end

#display_as_png(path = "tree") ⇒ Object 



48
49
50
51
52
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
 
# File 'lib/huffman/tree.rb', line 48

def display_as_png(path="tree")
	# Create a new graph
	g = GraphViz.new(:G)
	visit(:postorder) do |node|
		# C'est un noeud parent inventé
		color = node.symbol ? "yellow" : "red"
		symbol = case node.symbol
			when EOT
				"EOT"
			when "\t"
				"TAB"
			when "\b"
				"BACKSPACE"
			when " "
				"WHITESPACE"
			when "\n"
				"LINE RETURN"		
			else 
				"#{node.symbol ? node.symbol : ""}"
		end

		label = "#{node.value}"
		label += "➠#{node.binary_value}" if not node.binary_value == '' 
		label += "➡︎#{symbol}" if node.symbol

		graphviz_node = g.add_nodes(node.__id__.to_s, label: label, "style" => "filled", "color" => color )
		# On créer les arretes de ses enfants
		g.add_edges(graphviz_node, g.get_node(node.left.__id__.to_s)) if node.left
		g.add_edges(graphviz_node, g.get_node(node.right.__id__.to_s)) if node.right

	end
	g.output( :png => "#{path}.png" )

end