module RubyLabs

=begin rdoc
  
== BitLab

The BitLab module has definitions of classes and methods used in the projects for Chapter 7
of <em>Explorations in Computing</em>.  The module has methods used to experiment
with binary codes, including fixed-width codes and Huffman codes.  Methods create
messages by encoding strings, decode messages back to the original text, and run experiments 
that introduce errors into messages and test for errors with simple parity checks. 

The file bitlab.rb also adds a method to the PriorityQueue class, which is defined in
the top level RubyLabs module.  The methods that insert and remove items have a "hook" that can be called called when
when the queue is being displayed on the canvas.
The +update+ method defined here will move nodes of a Huffman tree around on the screen when
they are removed from or added to the queue.
=end

module BitLab

  QueueView = Struct.new(:queue, :options)
  NodeView = Struct.new(:circle, :text, :ftext, :lseg, :rseg)
  NodeCoords = Struct.new(:x, :y, :leftedge, :leftdepth, :rightedge, :rightdepth)

  # def test_setup
  #   vf = read_frequencies(:hvfreq)
  #   pq = init_queue(vf)
  #   view_queue(pq)
  #   return pq
  # end
  
  # Options for drawing trees on the canvas:

  @@unit = 24           # pixels per "tree unit"
  
  @@queueViewOptions = {
    :width => 42 * @@unit,
    :height => 15 * @@unit,
    :qy => 50,
    :qx => 50,
  }
  
  # Data directory for BitLab:

  @@bitsDirectory = File.join(File.dirname(__FILE__), '..', 'data', 'huffman')

  # Make a unique binary code for each item in array +a+, returning a Hash that
  # associates each item with a unique Code object.  The codes are fixed-size
  # binary codes, with a number of bits that depends on the number of items in +a+.  
  #
  # Example -- make a 2-bit encoding for each of the 4 objects in this array:
  #   
  #   >> nt_code = make_codes( ["a", "t", "c", "g"] )
  #   => {"a"=>00, "c"=>10, "g"=>11, "t"=>01}
  #   >> nt_code["c"]
  #   => 10

  def make_codes(a)
    n = log2(a.length).ceil
    res = Hash.new
    a.each_with_index do |x,i|
      res[x] = i.code(n)
    end
    return res
  end

  # Print the codes in +a+, which should be an associative array made by +make_codes+ or 
  # +assign_codes+, the method that creates binary codes for a Huffman tree.  
  # An option specifies how to order the
  # output, either <tt>:by_code</tt> (the default) or <tt>:by_name</tt>.
  #
  # Example:
  #   >> nt_code
  #   => {"a"=>00, "c"=>10, "g"=>11, "t"=>01}
  #
  #   >> print_codes(nt_code)
  #   00  a
  #   01  t
  #   10  c
  #   11  g
  #   => true
  #
  #   >> print_codes(nt_code, :by_name)
  #   a  00
  #   c  10
  #   g  11
  #   t  01
  #   => true
  
  def print_codes(a, mode = :by_code)
    if mode == :by_code
      a.sort { |x,y| x[1] <=> y[1] }.each do |sym, code|
        printf "%s  %s\n", code, sym
      end
    elsif mode == :by_name
      width = a.keys.map{ |x| x.to_s.length }.max
      a.keys.sort { |x,y| x.to_s <=> y.to_s }.each do |x|
        printf "%-#{width}s  %s\n", x, a[x]
      end
    else
      raise "print_codes: mode must be :by_code or :by_name"
    end
    return true
  end

  # Make a Message object for the characters in string +s+.  The second
  # parameter determines the code to use.  It can be <tt>:ascii</tt>, <tt>:parity</tt>, a hash
  # object that has code mappings for letters, or a Huffman tree.  If a hash 
  # or tree is passed, the message type is set to <tt>:packed</tt>, otherwise it's <tt>:unpacked</tt>.
  # The encoding type is saved so it can be used later in decoding.
  #
  # Example:
  #   >> encode("atg", :ascii)
  #   => 01100001 01110100 01100111
  #   
  #   >> nt_code
  #   => {"a"=>00, "c"=>10, "g"=>11, "t"=>01}
  #   >> encode("atg", nt_code)
  #   => 000111
  
  def encode(s, type, opt = nil)
    if (type.class == Hash || type.class == Node)
      code = (type.class == Node) ? assign_codes(type) : type
      msg = Message.new(:packed)
      s.each_byte do |ch|
        msg << code[ch.chr]
        printf("%s: %s\n", ch.chr, code[ch.chr]) if opt == :trace
      end
    else
      msg = Message.new(:unpacked)
      s.each_byte do |ch|
        code = ch.code(8)
        code.add_parity_bit if type == :parity
        msg << code
        printf("%s: %s\n", ch.chr, code) if opt == :trace
      end
    end
    return msg  
  end

  # Decode a sequence of bits (represented by Message object +m+) using the
  # specified decoding scheme.  
  # 
  # Note: if the decoding scheme is not the same as the one used to create
  # the message the results are unpredictable.
  # 
  # See also Message#decode, which generates a string using the coding scheme 
  # specified when the message was created.  Message#decode always gives the 
  # right result -- the point of this stand-alone decode method
  # is to show what happens if the decoding scheme does not match the 
  # encoding scheme.
  #
  # Example:
  #   >> msg = encode("aloha", :ascii)
  #   => 01100001 01101100 01101111 01101000 01100001
  #   >> decode(msg, :ascii)
  #   => "aloha"
  #   >> decode(msg, :parity)
  #   => "?67??"

  def decode(m, scheme)
    raise "not a message" unless m.class == Message  
    res = ""
    if scheme.class == Node
      res = huffman_decode(m, scheme)
    elsif scheme.class == Hash
      raise "packed decode not implemented"
    elsif scheme == :ascii
      m.array.each do |x|
        res << x.value.chr
      end
    elsif scheme == :parity
      m.array.each do |x|
        if x.even_parity?
          res << (x.value >> 1).chr
        elsif $KCODE[0] == ?U
          res << "\xe2\x80\xa2"
        else
          res << "?"
        end
      end
    else
      raise "unknown scheme: #{scheme}"
    end
    return res
  end

  # Simulate noisy transmission of a message represented by a Message object +m+. 
  # Returns a copy of +m+ after making +n+ calls to the +flip+ method (which changes
  # a random bit in the message).
  #
  # Example:
  #   >> msg = encode("hola", :ascii)
  #   => 01101000 01101111 01101100 01100001
  #   >> recvd = garbled(msg, 3)
  #   => 01001000 01000111 01101100 01100001
  #   >> decode(recvd, :ascii)
  #   => "HGla"
  
  def garbled(m, n)
    res = m.copy
    n.times do
      c = res.array[ rand(res.array.length) ]
      c.flip( rand(c.length) )
    end
    return res
  end

  # Read letters and frequencies from file +fn+, save them in a hash indexed by letter name.
  # The hash can be passed to build_tree, the method that creates a Huffman tree from
  # a set of letter frequencies.  If +fn+ is a symbol it should be the name of one of the
  # letter frequency files included with RubyLabs; if it's a string is should be the name
  # of a file in the current working directory.
  #
  # Example:
  #   >> read_frequencies( :hvfreq )
  #   => {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}

  def read_frequencies(fn)
    a = Hash.new
    if fn.class == Symbol
      fn = File.join(@@bitsDirectory, fn.to_s + ".txt")
    end
    File.open(fn).each do |line|
      line.chomp!
      next if line.length == 0
      next if line[0] == ?#
      x = line[/^./]
      f = line[/\d+\.\d+/].to_f
      a[x] = f
    end
    return a
  end

  # Build a Huffane tree using frequencies in hash +f+ (typically created
  # by calling read_frequencies).  The return value is a Node object that
  # represents the root of the tree. 
  #
  # Example:
  #   >> f = read_frequencies( :hvfreq )
  #   => {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}
  #   >> build_tree(f)
  #   => ( 1.000 ( A: 0.450 ) ( ... ) )
  #
  #-- 
  # :begin :build_tree
  def build_tree(f)
    pq = init_queue(f)

    while pq.length > 1
      n1 = pq.shift
      n2 = pq.shift
      pq << Node.combine(n1, n2)
    end

    return pq[0]
  end
  # :end :build_tree

  # Helper method for build_tree:  initialize a priority queue with Node
  # objects for each letter in hash +a+, returning the queue as the result
  # of the call.
  #
  # Example:
  #   >> f
  #   => {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}
  #   >> init_queue(f)
  #   => [( U: 0.100 ), ( E: 0.120 ), ( I: 0.150 ), ( O: 0.180 ), ( A: 0.450 )]
  #--
  # :begin :init_queue
    def init_queue(a)
      q = PriorityQueue.new
      a.each do |x,f|
        q << Node.new(x,f)
      end
      return q
    end
  # :end :init_queue

  # Traverse a Huffman tree to make a Code object for each
  # leaf node, returning the codes in a Hash object.  When users call this
  # method, they should pass only one argument (+tree+).  On recursive calls
  # the other two arguments will be the set of codes defined so far and the
  # binary prefix for the path to the current node.  
  # 
  # Users normally pass a tree to +encode+, which will call this method to make the code.
  # The same tree should also be passed to +decode+ to decode the message.
  #
  # Example:
  #   >> t = build_tree(f)
  #   => ( 1.000 ( A: 0.450 ) ( ... ) )
  #   >> assign_codes(t)
  #   => {"A"=>0, "O"=>111, "E"=>101, "I"=>110, "U"=>100}
  #
  #--
  # :begin :assign_codes
  def assign_codes(tree, code = {}, prefix = Code.new(0,0))
    if tree.char != nil
      code[tree.char] = prefix
    else
      assign_codes(tree.left,  code, prefix + 0)
      assign_codes(tree.right, code, prefix + 1)
    end
    return code
  end
  # :end :assign_codes

  # Helper method used by decode and Message#decode:  decode the binary codes in message +m+,
  # using +tree+ as a guide.  

  def huffman_decode(m, tree)
    res = ""
    path = tree
    m.each_bit do |bit|
      if path.leaf?
        res << path.char
        path = tree
      end
      path = (bit == 0) ? path.left : path.right
    end
    res << path.char if path.leaf?
    return res
  end

  # The data directory BitLabs has a file named "testcodes.txt" that contains a set
  # of binary encodings of Hawaiian words.  Call this method to read the encodings and return
  # and an array of Message objects, one for each encoding.  Users can try decoding the messages
  # by hand before verifying their answer by passing them to decode.  The messages are ordered
  # from shortest to longest.
  #
  # Example (assuming +t+ is the Huffman tree for the full Hawaiian alphabet):
  #   >> msgs = read_codes
  #   => [011010, ... 000101101100001100001011011000011011100110001011011100110001011010110011011010011110]
  #   >> decode(msgs[-1], t)
  #   => "HUMUHUMUNUKUNUKUAPUA'A"

  def read_codes
    codes = Array.new
    fn = File.join(@@bitsDirectory, "testcodes.txt")
    File.open(fn).each do |line|
      line.chomp!
      code = Code.new(0,0)
      line.each_byte do |byte|
        code << byte[0]                # add least significant digit of ASCII "0" or "1"
      end
      msg = Message.new(:packed)
      msg << code
      codes << msg
    end
    return codes
  end

  # The data directory for BitLabs has a file named "testwords.txt" with a few Hawaiian words.
  # Call this method to read the file and return a list of strings for experiments with encoding
  # Hawaiian words with a Huffman code.
  
  def read_words
    fn = File.join(@@bitsDirectory, "testwords.txt")
    words = File.open(fn).readlines
    return words.map { |x| x.chomp }
  end

=begin rdoc
  Initialize the canvas with a drawing of a priority queue.
=end

# Initialize the RubyLabs Canvas and draw a picture of priority queue +pq+.
# Future calls to the queue's <tt><<</tt> and <tt>shift</tt> methods will update the drawing.

  def view_queue(pq, userOptions = {} )
    options = @@queueViewOptions.merge(userOptions)
    Canvas.init(options[:width], options[:height], "BitLab")
    @@drawing = QueueView.new(pq, options)
    options[:nodefill] = "lightgray"
    options[:freqfont] = Canvas::Font.new('freqfont', :family => 'Helvetica', :size => 10)
    pq.on_canvas = true
    x = options[:qx]
    pq.each_with_index do |node, i|
      draw_node(node, x, options[:qy])
      x += 3 * @@unit
    end
    return true    
  end

  def move_tree(tree, dx, dy)   # :nodoc:
    tree.coords.x += dx
    tree.coords.y += dy
    Canvas.move(tree.drawing.circle, dx, dy)
    Canvas.move(tree.drawing.text, dx, dy)
    Canvas.move(tree.drawing.ftext, dx, dy) if tree.drawing.ftext
    if tree.left
      Canvas.move(tree.drawing.lseg, dx, dy)
      move_tree(tree.left, dx, dy) 
    end
    if tree.right
      Canvas.move(tree.drawing.rseg, dx, dy)
      move_tree(tree.right, dx, dy)
    end
  end

  def draw_root(node, left, right)  # :nodoc:
    opts = @@drawing.options
    x = (left.coords.x + right.coords.x) / 2
    y = left.coords.y - 2 * @@unit
    draw_node(node, x, y)
    node.drawing.lseg = Canvas::Line.new(x, y, left.coords.x, left.coords.y)
    node.drawing.rseg = Canvas::Line.new(x, y, right.coords.x, right.coords.y)
    node.drawing.lseg.lower
    node.drawing.rseg.lower
    # [left, right].each do |desc|
    #   desc.drawing.ftext.delete
    #   desc.drawing.ftext = nil
    # end
  end

  def draw_node(node, x, y)   # :nodoc:
    return nil unless @@drawing
    opts = @@drawing.options
    d = @@unit
    circ = Canvas::Circle.new( x, y, d / 2, :fill => opts[:nodefill] )
    text = Canvas::Text.new( node.char, x, y, :anchor => :center )
    ftext = Canvas::Text.new( node.freq.to_s, x, y-d, {:font => opts[:freqfont].name, :anchor => :center} )
    node.drawing = NodeView.new(circ, text, ftext, nil, nil)
    node.coords = NodeCoords.new(x, y, x, 0, x, 0)
  end


=begin rdoc

== 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. 

=end

  class Node

    attr_accessor :freq, :char, :left, :right, :drawing, :coords, :lfchain, :rfchain, :depth
    
    # Create a new leaf node for +char+ with frequency +freq+.
     
    def initialize(char,freq)
      @char = char
      @freq = freq
      @left = @right = nil
      @drawing = @coords = nil
      @lfchain = @rfchain = self
      @depth = 0
    end

    # 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

    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
    
    # Compare this node and node +x+ according to their frequency values
    # so they can be ordered in a priority queue.

    def <(x)
      x.class == Node && @freq < x.freq
    end
    
    # Return +true+ if this node is a leaf (i.e. it has no descendants).
  
    def leaf?
      return @char != nil
    end
    
    # 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.

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

    alias to_s inspect

  end # Node

=begin rdoc

== Code

Code objects are variable-length binary numbers representing integers, letters, or members
of a set. 

In the projects described in the text readers do not create Code objects directly -- 
instead Codes are created by methods in 
other classes, e.g. the +code+ method added to the Fixnum class or the top level +encode+ method
defined in the BitLab module.

See also HexCode, a derived class that has the same operations and attributes but displays
values with hexadecimal (base 16) digits.

#--
Way cool -- this class used to have a maxcodesize (set to 60) to make sure codes fit within
a single 64-bit word.  But a typo during one experiment created an 80-bit code.  Turns out
indexing etc work just fine on Bignums:

>> c1 = s[1].code(80)
=> 00000000000000000000000000000000000000000000000000000000000000000000000001101000
>> c1.flip(0)
=> 10000000000000000000000000000000000000000000000000000000000000000000000001101000
=end

  class Code
    attr_accessor :value, :length
    
    # Create a new code for the number +x+.  An optional argument specifies the number
    # of bits in the code, in which case the code will be padded with leading 0s (if the
    # value is small enough to fit in that number of bits) or truncated (if the number
    # is too big to fit in that number of bits).
    #
    # Examples:
    #    >> Code.new(26)
    #    => 11010
    #    >> Code.new(26, 8)
    #    => 00011010
    #    >> Code.new(26,4)
    #    => 1010   
    
    def initialize(x, length = log2(x+1).ceil)
      @value = x % (1 << length)
      @length = length
      @has_parity_bit = false
    end
      
    # Create a new code by copying this code and extending it by one bit.  The extra bit is appended
    # on the right.  The argument on the right side of the <tt>+</tt> operator should be an integer;
    # the bit appended to the code is the least significant bit of this number.
    #
    # Examples:
    #    >> x = Code.new(4)
    #    => 100
    #    >> x + 0
    #    => 1000
    #    >> x + 1
    #    => 1001

    def +(bit)
      val = (@value << 1) | bit[0]
      return Code.new(val, @length+1)
    end
  
    # Extend this code by attaching bits in +x+ to the end of this code.  The argument
    # +x+ can either be an integer, in which case one bit, corresponding to the least significant
    # bit of +x+, is added to the end of the this code, or another Code object, in which case
    # all the bits in +x+ are added to the end of the this code.
    #
    # Examples:
    #    >> x = Code.new(4)
    #    => 100
    #    >> y = Code.new(5)
    #    => 101
    #    >> x << 1
    #    => 1001
    #    >> x << y
    #    => 1001101

    def <<(x)
      if x.class == Code
        val = x.value     # val known to fit in x.length bits
        n = x.length
      else
        val = x[0]        # val is a single bit
        n = 1
      end
      @value <<= n
      @value |= val       # val can't have any higher order bits set -- see above
      @length += n
      return self
    end
    
    # Return one or more bits from this code.
    # If the argument passed to this method is an integer, the method returns a single integer, 
    # either 0 or 1.
    # If the argument is a Range, the method returns a new Code object with the specified bits
    # from this code.
    #
    # Note: The index operator for Fixnums orders bits from right to left, consistent with standard
    # usage but the opposite of Strings and Arrays.  In this module bits are ordered from
    # left to right to be consistent with Strings and Arrays.
    #
    # Example:
    #    >> x = Code.new(117)
    #    => 1110101
    #    >> x[1]
    #    => 1
    #    >> x[1..3]
    #    => 110
    
    def [](i)
      if i.class == Range
        res = 0
        n = 0
        i.each { |j| res <<= 1; res |= @value[@length-j-1]; n += 1 }
        return Code.new(res, n)
      else
        return @value[@length-i-1]
      end
    end
    
    # Return the bit value that would give this code an even parity, i.e. if this code
    # already has an even number of 1s return 0, if it has an odd number of 1s return 1.
    #
    # Example:
    #    >> x = Code.new(17)
    #    => 10001
    #    >> x.parity_bit
    #    => 0
    #    >> x << 1
    #    => 100011
    #    >> x.parity_bit
    #    => 1    

    def parity_bit
      bit = 0
      for i in 0...@length
        bit ^= @value[i]
      end
      return bit
    end
  
    # Extend this code by adding a new bit, chosen so that this code will now have even parity.
    #
    # Example:
    #    >> x = Code.new(17)
    #    => 10001
    #    >> x.add_parity_bit
    #    => 100010

    def add_parity_bit
      @has_parity_bit = true
      return self << parity_bit
    end
  
    # Return +true+ or +false+, depending on whether this code has an even or odd number of 1 bits.
    
    def even_parity?
      return parity_bit() == 0
    end
    
    # Invert bit +i+ of this code object, where bit 0 is the leftmost bit 
    # (see the note about bit order in the documentation for the [] operator
    # for Code objects).
    #
    # Example:
    #    >> x = Code.new(17)
    #    => 10001
    #    >> x.flip(3)
    #    => 10011
  
    def flip(i)
      raise "bit index out of range" unless i < @length
      @value ^= (1 << (@length - i - 1))
      return self
    end
    
    # Return a one-letter string containing the character encoded by this Code object,
    # which must have fewer than 8 bits.
    # Ignores the parity bit if it has been attached. 
  
    def chr
      raise "code must have fewer than 8 bits" unless @value < 256
      if @has_parity_bit
        if even_parity?
          return (@value >> 1).chr
        else
          return "?"
        end
      else 
        return @value.chr
      end
    end
    
    # Compare the numeric values of this object and Code object +x+.
    
    def <=>(x)
      return x.class == Code && @value <=> x.value
    end
    
    # Return a string with the binary digits of the value represented by this Code object.
  
    def inspect
      if @length == 0
        return ""
      else
        return sprintf "%0#{@length}b", @value
      end
    end
  
    alias to_s inspect
  
  end # Code
  
=begin rdoc

== HexCode

HexCodes are Code objects that are printed in hexadecimal.  All of the attributes
and methods of the Code class are applicable to HexCodes -- the only differences
are in <tt>to_s</tt>, which generates the string of digits used to print a number,
and in the method that compares objects (Codes can only be compared to other Codes,
HexCodes to other HexCodes).

=end
  
  class HexCode < Code
    
    # Create a new HexCode object for the number +x+.  The optional second
    # argument specifies the number of bits to use in the encoding.
    
    def initialize(x, length = log2(x+1).ceil)
      super
    end
    
    # Compare the numeric values of this object and HexCode object +x+.
    
    def <=>(x)
      return x.class == HexCode && @value <=> x.value
    end
    
    # Return a string with the hexadecimal digits of the value represented by this Code object.

    def inspect
      if @length == 0
        return ""
      else
        return sprintf "%0#{@length/4}X", @value
      end
    end
    
    alias to_s inspect
    
  end

=begin rdoc

== Message

Message objects are arrays of Code objects.  
There are two types of messages:  packed and unpacked.
If the message is unpacked, each code is stored in its own array element.
This is the standard form for messages created with the
<tt>:ascii</tt> or <tt>:parity</tt> encodings.  
If the message is packed,
codes are repackaged into 8-bit bytes, and individual codes may cross
array item boundaries.  This form is used by the method that uses a 
Huffman code to encode a string.
#--
TODO: allow for the possibility that a code word being added to a packed code can be longer than 8 bits

=end

  class Message
  
    attr_accessor :packed, :array
  
    @@packsize = 8          # number of bits to pack into single code
  
    # Create a new Message of the specified type (<tt>:packed</tt> or <tt>:unpacked</tt>).  
    # The message is initially empty; new characters are added by with the <tt><<</tt> operator.
    
    def initialize(type)
      raise "Message: unknown type" unless [:packed, :unpacked].include? type
      if type == :packed
        @packed = true
        @array = [ Code.new(0,0) ]
      else
        @packed = false
        @array = [ ]
      end
    end
  
    # Create a new Message object that is a copy of this message. 
    
    def copy
      dup = self.clone                              # copies @packed
      dup.array = Array.new
      @array.each { |x| dup.array << x.clone }      # deep copy of @array
      return dup
    end
  
    # Iterate over each bit in a message, without regard for code boundaries.
    #
    # Example:
    #    >> m
    #    => 10011
    #    >> m.each_bit { |b| puts b }
    #    1
    #    0
    #    0
    #    1
    #    1
    #    => 10011

    def each_bit
      @array.each do |byte|
        for i in 0...byte.length
          yield(byte[i])
        end
      end
      return self
    end
    
    # Append the bits in Code object +x+ to the end of this message.
    #
    # Example:
    #    >> m = Message.new(:packed)
    #    => 
    #    >> m << Code.new(4)
    #    => 100
    #    >> m << Code.new(3)
    #    => 10011
  
    def <<(x)
      raise "Message#<<: not a code" unless x.class == Code 
      if @packed
        if @array[-1].length + x.length <= @@packsize
          @array[-1] << x
        else
          n = @@packsize - @array[-1].length
          m = x.length - n
          @array[-1] << x[0...n] 
          @array << x[n...x.length]
        end
      else
        @array << x
      end
      return self
    end
  
    # Deprecated -- use standalone BitLab#decode instead
    
    # def decode    :nodoc:
    #   res = ""
    #   if @encoding.class == Symbol
    #     @array.each do |code|
    #       res << code.chr
    #     end
    #   elsif @encoding.class == Node
    #     res = huffman_decode(self, @encoding)
    #   else
    #     res = unpack
    #   end
    #   return res
    # end
  
    # def unpack
    #   "unpack: not implemented"
    # end
  
    # Return the length (in bits) of this message.
    
    def length
      @array.inject(0) { |sum, code| sum += code.length }
    end
  
    # Create a string of binary digits representing the Codes in this message.

    def inspect
      if @packed
        return @array.join("")
      else
        return @array.join(" ")
      end    
    end
  
    alias to_s inspect
  
  end # Message

end # BitLab

class PriorityQueue

  attr_accessor :on_canvas
  
  # Update the drawing of the priority queue after operation +op+ has been performed
  # on +node+.  Operation is either <tt>:shift</tt> or <tt><<</tt>, and +node+ is a 
  # reference to the Node object being removed or inserted into the queue.
  #
  # Calls helper methods <tt>left_edge</tt>, <tt>right_edge</tt>, and <tt>tree_sep</tt>
  # to figure out how to place subtrees to use the minimum amount of horizontal space
  # (see bitlab.rb).
  
  def update(op, node)
    if op == :shift
      move_tree(node, 0, 4 * @@unit)         # move subtree rooted at node down 4 units
    else
      i = 0
      dx = @@drawing.options[:qx] - left_edge(@q[0])
      while @q[i] != node
        move_tree(@q[i], dx, 0)
        dx = 3 * @@unit - tree_sep(@q[i], node)
        move_tree(node, dx, 0)
        dx = 3 * @@unit - tree_sep(@q[i], @q[i+1])
        i += 1
        sleep(0.2)
      end
      move_tree(node, 0, -2 * @@unit)
      if i < @q.length - 1
        dx = 3 * @@unit - tree_sep(@q[i], @q[i+1])
        i += 1
        while i < @q.length
          sleep(0.2)
          move_tree(@q[i], dx, 0)
          i += 1
        end
      end
    end
  end
  
  def left_edge(tree)   # :nodoc:
    x = tree.coords.x
    while tree.lfchain != tree
      tree = tree.lfchain
      x = min(x, tree.coords.x)
    end
    return x
  end
  
  def right_edge(tree)  # :nodoc:
    x = tree.coords.x
    while tree.rfchain != tree
      tree = tree.rfchain
      x = max(x, tree.coords.x)
    end
    return x
  end
  
  def tree_sep(left, right)   # :nodoc:
    res = right.coords.x - left.coords.x
    while (left.rfchain != left && right.lfchain != right)
      left = left.rfchain
      right = right.lfchain
      dist = right.coords.x - left.coords.x
      res = dist if dist < res
    end
    # loop do
    #   puts "res = #{res}"
    #   break if left == left.rfchain || right == right.lfchain
    #   left = left.rfchain
    #   right = right.lfchain
    #   puts "down #{left.inspect} --- #{right.inspect}"
    #   dist = right.coords.x - left.coords.x
    #   res = dist if dist < res
    # end
    return res
  end
  
end

end # RubyLabs

class Fixnum
  
=begin rdoc

== Fixnum

Add a method to +Fixnum+ to make a +Code+ object showing the binary or
hexadecimal representation of a number.  Intended mainly to show codes for
characters in +String+ objects.
=end

  # Create a Code object showing the binary or hexadecimal representation of
  # this number.  The two arguments, both optional, define the type of
  # representation and the number of digits:
  #   x.code            make a binary code for x, using as many bits as necessary
  #   x.code(n)         make a binary code for x, using n bits
  #   x.code(:hex)      make a hex code for x, using as many digits as necessary
  #   x.code(:hex,n)    make a hex code for x, using n digits (i.e. 4*n bits)
  #
  # Example:
  #   >> x = 26
  #   => 26
  #   >> x.code
  #   => 11010
  #   >> x.code(8)
  #   => 00011010
  #   >> x.code(:hex)
  #   => 1A
  #   >> x.code(:hex, 3)
  #   => 01A

  def code(*args)
    if args.first == :hex
      base = args.shift
    else
      base = :binary
    end
    if args.first.kind_of? Integer
      digits = args.shift
    elsif args.empty?
      b = (self == 0) ? 1 : log2(self+1).ceil
      digits = (base == :hex) ? (b/4.0).ceil : b
    else
      raise "code: can't understand #{args}"
    end
    if base == :hex
      return HexCode.new(self, 4*digits)
    else
      return Code.new(self, digits)
    end
    # bits = (base == :hex) ? digits * 4 : digits
    # return Code.new(self, bits, base)
  end
  
end