Class: RubyLabs::BitLab::Node

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

Overview

Node

A Node object represents a node of a Huffman tree. All nodes have an attribute named freq, the frequency used to determine the node’s place in a priority queue as the tree is built. The char attribute is nil for interior nodes, or the character stored at a leaf node. Descendants of a node can be found by calling the left or right accessor methods (which return nil for leaf nodes). The remaining attributes (drawing, coords, etc) are used by methods that display a tree on the RubyLabs Canvas.

Use new to create a new leaf node. Call the class method combine (an alternative constructor) to make a new interior node from two existing nodes. If the tree is being displayed on the Canvas, a call to combine will make a graphic for the new interior node directly above its two descandants.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(char, freq) ⇒ Node

Create a new leaf node for char with frequency freq.



455
456
457
458
459
460
461
462
 
# File 'lib/bitlab.rb', line 455

def initialize(char,freq)
  @char = char
  @freq = freq
  @left = @right = nil
  @drawing = @coords = nil
  @lfchain = @rfchain = self
  @depth = 0
end

Instance Attribute Details

#char ⇒ Object

Returns the value of attribute char.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def char
  @char
end

#coords ⇒ Object

Returns the value of attribute coords.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def coords
  @coords
end

#depth ⇒ Object

Returns the value of attribute depth.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def depth
  @depth
end

#drawing ⇒ Object

Returns the value of attribute drawing.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def drawing
  @drawing
end

#freq ⇒ Object

Returns the value of attribute freq.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def freq
  @freq
end

#left ⇒ Object

Returns the value of attribute left.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def left
  @left
end

#lfchain ⇒ Object

Returns the value of attribute lfchain.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def lfchain
  @lfchain
end

#rfchain ⇒ Object

Returns the value of attribute rfchain.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def rfchain
  @rfchain
end

#right ⇒ Object

Returns the value of attribute right.



451
452
453
 
# File 'lib/bitlab.rb', line 451

def right
  @right
end

Class Method Details

.combine(leftdesc, rightdesc) ⇒ Object

Create a new interior node with descendants leftdesc and rightdesc. If the tree is being displayed, draw the new node above and between its two descendants. – todo – need to follow chains to end when updating shallower tree



469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
 
# File 'lib/bitlab.rb', line 469

def Node.combine(leftdesc, rightdesc)
  node = Node.new(nil, leftdesc.freq + rightdesc.freq)
  node.left = leftdesc
  node.right = rightdesc
  node.depth = 1 + max(leftdesc.depth, rightdesc.depth)
  node.lfchain = leftdesc
  node.rfchain = rightdesc
  if leftdesc.depth > rightdesc.depth
    rightdesc.rfchain = leftdesc.rfchain
  elsif leftdesc.depth < rightdesc.depth
    leftdesc.lfchain = rightdesc.lfchain
  end
  draw_root(node, leftdesc, rightdesc) if (leftdesc.drawing && rightdesc.drawing)
  return node
end

Instance Method Details

#<(x) ⇒ Object

Compare this node and node x according to their frequency values so they can be ordered in a priority queue.



488
489
490
 
# File 'lib/bitlab.rb', line 488

def <(x)
  x.class == Node && @freq < x.freq
end

#inspect ⇒ Object Also known as: to_s

Return a String with a concise representation of this node, including its character and frequency if it’s a leaf, or it’s frequency and two descendants if it’s an interior node.



502
503
504
505
506
507
508
 
# File 'lib/bitlab.rb', line 502

def inspect
  if leaf?
    sprintf "( %s: %.3f )", @char, @freq
  else
    sprintf "( %.3f %s %s )", @freq, @left.to_s, @right.to_s
  end
end

#leaf? ⇒ Boolean

Return true if this node is a leaf (i.e. it has no descendants).

Returns:

  • (Boolean) 


494
495
496
 
# File 'lib/bitlab.rb', line 494

def leaf?
  return @char != nil
end