# RubyLabs gem, top level module.

SCRIPT_LINES__ = Hash.new unless defined? SCRIPT_LINES__

autoload :IntroLab,       "introlab.rb"
autoload :SieveLab,       "sievelab.rb"
autoload :IterationLab,   "iterationlab.rb"
autoload :RecursionLab,   "recursionlab.rb"
autoload :HashLab,        "hashlab.rb"
autoload :BitLab,         "bitlab.rb"
autoload :MARSLab,        "marslab.rb"
autoload :RandomLab,      "randomlab.rb"
autoload :EncryptionLab,  "encryptionlab.rb"
autoload :ElizaLab,       "elizalab.rb"
autoload :SphereLab,      "spherelab.rb"
autoload :TSPLab,         "tsplab.rb"

autoload :Demos,          "demos.rb"

include Math

=begin rdoc

== RubyLabs

RubyLabs is a collection of modules for projects described in 
<em>Explorations in Computing: An Introduction to Computer Science</em>.

There is one submodule for each project, e.g. RubyLabs::SieveLab has
methods used in the Sieve of Eratosthenes project in Chapter 3.
The top level RubyLabs module also has common methods used in
several projects.
=end

module RubyLabs

# A simple 'hello world' method to test the installation.

  def hello
    "Hello, you have successfully installed RubyLabs!"
    begin
      Canvas.init(200, 200, "RubyLabs::Hello")
      Canvas::Text.new("Hello from RubyLabs!",40,90)
    rescue Exception => e
      puts e
      puts "Did you install Tk, the software module used to display graphics?  See your Lab Manual for installtion instructions..."
    end
    return nil 
  end

# Return the larger of +a+ and +b+ (determined by calling <tt>a < b</tt>).
#
# :call-seq:
#   max(a,b) => Object
#

  def max(a,b)
    a < b ? b : a
  end
  
# Return the smaller of +a+ and +b+ (determined by calling <tt>a < b</tt>).
#
# :call-seq:
#   min(a,b) => Object
#

  def min(a,b)
    a < b ? a : b
  end

# Compute the logarithm (base 2) of a number +x+.
#
# :call-seq:
#   log2(x) => Float
#

  def log2(x)
    log(x) / log(2.0)
  end
  
# Measure the execution time of a block of code, which can be any Ruby expression
# enclosed in braces after the method name.  The return value is the number of seconds
# required to evaluate the block.
# Any output produced by the block is discarded.
#
# Example:
#   >> time { sieve(1000) }
#   => 0.014921
#
# :call-seq:
#   time { f } => Float
#

  def time(&f)
    tstart = Time.now
    f.call
    return Time.now - tstart
  end
  
# Monitor the execution of a block of code, which can be any Ruby expression enclosed in braces.  Sets up
# a callback method which checks to see if a probe has been attached to a line in
# a method called by the block.  See Source#probe for information about attaching
# probes.  If a probe is attached, the expression associated with 
# the probe is evaluated.  The value returned from trace is the value returned 
# by the block.
#
# See also RubyLabs#count.
#
# Example -- call a method named +brackets+ to print brackets around array
# elements as the arry is being sorted by a call to +isort+:
#   >> Source.probe( "isort", 5, "puts brackets(a,i)" )
#   => true
#   >> trace { isort(cars) }
#     mazda [ford  bmw  saab  chrysler]
#     ford  mazda [bmw  saab  chrysler]
#     bmw  ford  mazda [saab  chrysler]
#     ...
#   => ["bmw", "chrysler", "ford", "mazda", "saab"]    
#
# :call-seq:
#   trace { f } => Object
#
#--
# Debugging aid:  put this line at the front of the trace_func:
#       p [event, file, line, id, binding, classname]
  
  def trace(&f)
    set_trace_func proc { |event, file, line, id, binding, classname|
      if expr = Source.probing(file, id, line) 
        eval(expr, binding) if expr != :count
      end
    }
    res = f.call
    set_trace_func nil
    res
  end

# Monitor the execution of a block of code, which can be any Ruby expression enclosed in braces.
# If a counting probe (see Source#probe) is attached to any lines of code evaluated by the block 
# this method will return the total number of times those lines are executed.
#
# See also RubyLabs#trace.
#
# Example -- count the number of times line 2 in the method named +less+ is executed
# during a call to +isort+:
#   >> Source.probe("less", 2, :count)
#   => true
#   >> count { isort(cars) }
#   => 8    
#
# :call-seq:
#   count { f } => Fixnum
#

  def count(&f)
    counter = 0
    set_trace_func proc { |event, file, line, id, binding, classname|
      if expr = Source.probing(file, id, line) 
        counter += 1 if expr == :count
      end
    }
    f.call
    set_trace_func nil
    return counter
  end


=begin rdoc

== TestArray

A TestArray is an array of random values that can be used to test searching and sorting
algorithms.  
A method named +random+ will return a random element to use as a search target.
If +a+ is a TestArray object, 
call <tt>a.random(:success)</tt> to get a value that is in the array +a+, or call 
<tt>a.random(:fail)</tt> to get a number that is not in the array.  

#--
  The constructor uses a hash to create unique numbers -- it draws random numbers
  and uses them as keys to insert into the hash, and returns when the hash has n
  items.  The hash is saved so it can be reused by a call to random(:fail) -- this
  time draw random numbers until one is not a key in the hash.  A lot of machinery
  to keep around for very few calls, but it's efficient enough -- making an array
  of 100K items takes less than a second.

  An earlier version used a method named test_array to make a regular Array object
  and augment it with the location method, but the singleton's methods were not passed
  on to copies made by a call to sort:
    >> x = test_array(3)
    => [16, 13, 4]
    >> x.sort.random(:fail)
    NoMethodError: undefined method `random' for [4, 13, 16]:Array
  
=end

  class TestArray < Array

    data = File.join(File.dirname(__FILE__), '..', 'data', 'arrays')    
    
    @@sources = {
      :cars => "#{data}/cars.txt",
      :colors => "#{data}/colors.txt",
      :elements => "#{data}/elements.txt",
      :fruits => "#{data}/fruit.txt",
      :fish => "#{data}/fish.txt",
      :languages => "#{data}/languages.txt",
      :words => "#{data}/wordlist.txt",
    }

# Create a new TestArray of size +n+ containing items of the specified +type+.
# If a type is not supplied, create an array of integers.  Types are identified
# by symbols, e.g. <tt>:cars</tt> tells the constructor to return an array of
# car names (see TestArray.sources).  If a type is specified, the symbol <tt>:all</tt>
# can be given instead of an array size, in which case the constructor returns
# all items of that type.
#
# Examples:
#   >> TestArray.new(5)
#   => [3, 28, 48, 64, 4]
#   >> TestArray.new(5, :cars)
#   => ["lamborghini", "lincoln", "chrysler", "toyota", "rolls-royce"]    
#   >> TestArray.new(:all, :colors)
#   => ["almond", "antique white", ... "yellow green"]
#
# :call-seq:
#   TestArray.new(n, type) => Array
#

    def initialize(size, src = nil)
      
      if src.nil? || src.class == Fixnum
        raise "TestArray: array size must be an integer" unless size.class == Fixnum
        if src.nil?
          @max = (size < 50) ? 100 : (10 * size)
        else
          @max = src
          raise "TestArray: max must be at least 2x larger than size" unless @max >= 2 * size
        end
      else
        raise "TestArray: array size must be an integer or :all" unless size.class == Fixnum || size == :all
      end
       
      @h = Hash.new
      
      # if @max is defined make an array of integers, otherwise src defines the type of data;
      # size might be :all, in which case return the whole file, and set @all to true so random
      # doesn't try to make a random value not in the array.
      
      if @max
        while @h.size < size
          @h[ rand( @max ) ] = 1    
        end
      else
        fn = @@sources[src] or raise "TestArray: undefined source: #{src}"
        @words = File.open(fn).readlines
        if size != :all
          max = @words.length
          raise "TestArray: size must be less than #{max} for an array of #{src}" unless size < max
          while @h.size < size
            @h[ @words[ rand(max) ].chomp ] = 1
          end
        end
      end
          
      if size == :all
        self.concat @words.map { |s| s.chomp! }
        @all = true
      else
        self.concat @h.keys
        for i in 0..length-2
          r = rand(length-i) + i      # i <= r < length
          self[i],self[r] = self[r],self[i]
        end
      end
      
    end
    
# Return a value that is guaranteed to be in the array or not in the array,
# depending on the value of +outcome+.  Pass <tt>:success</tt> to get a random
# value in the array, or pass <tt>:fail</tt> to get an item of the same type as the
# items in the array but which is not itself in the array.  Call <tt>a.random(:fail)</tt>
# to get a value that will cause a search algorithm to do the maximum number of comparisons.
#
# Example:
#   >> a = TestArray.new(10).sort
#   => [13, 23, 24, 26, 47, 49, 86, 88, 92, 95]
#   >> x = a.random(:fail)
#   => 22
#   >> search(a, x)
#   => nil
#
# :call-seq:
#   a.random(outcome) => Object
#    
    
    def random(outcome)
      if outcome == :success
        return self[ rand(self.length) ]
      elsif outcome == :fail
        raise "TestArray#random: array is universal set" if @all
        loop do
          if @max
            x = rand( @max )
          else
            x = @words[ rand( @words.length ) ].chomp
          end
          return x if @h[x] == nil
        end
      else
        return nil
      end
    end
    
# Return a list of types of items that can be passed as arguments
# to <tt>TestArray.new</tt>
#
# :call-seq:
#    TestArray.sources() => Array
#

    def TestArray.sources
      return @@sources.keys.sort { |a,b| a.to_s <=> b.to_s }
    end
        
  end       # class TestArray 
  
  
# Equivalent to calling <tt>TestArray.new</tt>.
#
# Examples:
#   >> TestArray(5)
#   => [65, 79, 60, 88, 30]
#   >> TestArray(5, :cars)
#   => ["mini", "opel", "chevrolet", "isuzu", "cadillac"]
#
# :call-seq:
#   TestArray(n, type) => Array
#

  def TestArray(n, type = nil)
    TestArray.new(n, type)
  end
  
  
=begin rdoc

== Source

The Source module provides access the source code for a lab
project.  When IRB reads the modules from a file, the source is
saved in a global array named <tt>SCRIPT_LINES__</tt>.  The methods
defined in this module scan the source code to look for tags that
mark the first and last lines of methods described in the book.

A method name can be passed either as a String or a Symbol.  For
example, to print a listing of the +isort+ method a user can call
  Source.listing("isort")
or
  Source.listing(:isort)

#--
Code that will be accessed by methods in this module should be delimited
by :begin and :end tags.  See the definition of isort in iterationlab.rb
for an example of how to name a method and its helper methods.

=end

  module Source
    
    @@probes = Hash.new
    @@file = Hash.new
    @@size = Hash.new
    @@base = Hash.new
    @@helpers = Hash.new
    @@line = nil
    
# Print a listing (source code along with line numbers) for method +name+.
#
# :call-seq:
#    Source.listing(name)
#

    def Source.listing(name)
      begin
        id = Source.find(name)
        for i in @@base[id]..(@@base[id]+@@size[id]-1)
          line = SCRIPT_LINES__[@@file[id]][i-1].chomp
          printf "%3d:  %s\n", i - @@base[id] + 1, line.gsub(/\t/,"  ")
        end
      rescue Exception => e
        puts e
      end
      return true
    end
    
# Save a copy of the source code for method +name+ in a file.  If a file name is not
# specified, the output file name is the name of the method with ".rb" appended.
# Prompts the user before overwriting an existing file.
#
# Example -- Write the source for the method +isort+ to "isort.rb":
#   Source.checkout("isort")
#
# Example -- Write the source for +isort+ to "mysort.rb"
#   Source.checkout("isort", "mysort.rb")
#
# :call-seq:
#    Source.checkout(name)
#

    def Source.checkout(name, newfilename = nil)
      begin
        id = Source.find(name)
        if newfilename.nil?
          newfilename = id.to_s
        end
        if newfilename[-1] == ?? || newfilename[1] == ?!
          newfilename.chop!
        end
        if newfilename !~ /\.rb$/
          newfilename += ".rb"
        end
        if File.exists?(newfilename)
          print "Replace existing #{newfilename}? [yn] "
          if STDIN.gets[0] != ?y
            puts "File not written"
            return false
          end
        end
        File.open(newfilename, "w") do |f|
          f.puts "# #{name} method exported from #{File.basename(@@file[id])}"
          f.puts
          Source.print_source(f, id)
          @@helpers[id].each do |m|
            f.puts 
            xid = Source.find(m)
            Source.print_source(f, xid)
          end     
        end
      rescue Exception => e
        puts e
      end
      puts "Saved a copy of source in #{newfilename}"
      return true
    end
    
# Helper method called from Source.checkout -- print the code for
# method +id+ in the file +f+
    
    def Source.print_source(f, id)    # :nodoc:
      for i in @@base[id]..(@@base[id]+@@size[id]-1)
        line = SCRIPT_LINES__[@@file[id]][i-1].chomp
        f.puts line.gsub(/\t/,"  ")
      end      
    end
    
# Attach a software probe to a line in method +name+.  The line can be specified
# by line number relative to the start of the method or a string the specifies a pattern.  The third argument
# is either a string or the symbol <tt>:count</tt>.
# If the third argument is a string, it should be a Ruby expression that will be
# evaluated whenever the probe is activated via a call to +trace+ (see RubyLabs#trace).
# If the third argument is <tt>:count</tt>, a call to +count+ (see RubyLabs#count)
# will count the number of times the specified line is executed.
#
# Example:  attach a probe to the +sieve+ method, so that when +sieve+ is called
# via +trace+ the statement "p worklist" will be evaluated whenever line 6 is executed:
#   >> Source.probe("sieve", 6, "p worksheet")
#   => true
#
# Example:  attach a counting probe, so +count+ can record how many times line 6 is executed:
#   >> Source.probe("sieve", 6, :count)
#   => true
#
# If the second argument to Source.probe is a string, the probe is attached to every line that
# contains that string.  For example, to attach a counting probe to every line in +merge+ that
# has a call to the << operator:
#   >> Source.probe("merge", '<<', :count)
#   => true
#
# :call-seq:
#    Source.probe(name, line, spec)
#

    
    def Source.probe(name, spec, expr = :count)
      begin
        id = Source.find(name)
        Source.lines(spec, id).each do |n|
          n += @@base[id] - 1
          @@probes[id][n] = expr
        end
      rescue Exception => e
        puts e
      end
      return true
    end
  
# -- Method for internal use only --  
# Return probes (if any) attached to the specified file, method, and line number.
# Intended to be called from a trace func callback (which is why the file is one
# of the parameters).

    def Source.probing(filename, method, line)  # :nodoc:
      return nil if line == @@line
      @@line = line
      return nil unless @@probes[method] && @@file[method] == filename
      return @@probes[method][line] 
    end
    
# Print a description of all the currently defined probes. 
#
# :call-seq:
#    Source.probes()
#

    def Source.probes
      @@probes.each do |name, plist|
        plist.each do |line, exprs|
          n = line - @@base[name] + 1
          printf "%s %2d: %s\n", name, n, exprs
        end
      end
      return true
    end
    
# Remove all the probes on a designated method, or if no method name is passed,
# remove all probes from all methods.
#
# :call-seq:
#    Source.clear(name)
#

    def Source.clear(name = nil)
      @@probes.each do |id, plist|
        next if ! name.nil? && id != name
        plist.clear
      end
      return true
    end
    
# Internal use only -- locate the filename, starting line number, and length
# of method +name+, record the
# information for any methods that need it.  This information only needs to
# be found once, so it is recorded in a set of class variables.  Revisit this
# decision if monitoring user-defined methods....
  
    def Source.find(name)   # :nodoc:
      id = name.to_sym
      return id if @@file[id]     # return if we looked for this source previously
      
      filename, base, size, helpers = nil, nil, nil, nil
      
      catch (:found) do
        SCRIPT_LINES__.each do |file, lines|
          line_num = 0
          lines.each do |s|
            line_num += 1
            if match = s.match(/:(begin|end)\s+(.*)/)
              verb = match[1]
              names = match[2].split.collect{|x| eval(x)}
              if names[0] == id
                if verb == "begin"
                  filename = file
                  base = line_num + 1
                  helpers = names[1..-1]
                else
                  size = line_num - base
                  throw :found
                end
              end
            end
          end
        end
      end
      
      raise "Can't find method named '#{name}'" if size.nil?

      @@file[id] = filename
      @@size[id] = size
      @@base[id] = base
      @@probes[id] = Hash.new
      @@helpers[id] = helpers
      return id      
    end
    
# Internal use only -- make an array of line numbers to use for probing method +name+.
# Argument can be a single line number, an array of line numbers, or a pattern.  Checks
# to make sure line numbers are valid.

    def Source.lines(spec, id)    # :nodoc:
      if spec.class == Fixnum && Source.range_check(spec, id)
        return [spec]
      elsif spec.class == Array
        res = Array.new
        spec.each do |line|
          raise "line number must be an integer" unless line.class == Fixnum
          res << line if Source.range_check(line, id)
        end
        return res
      elsif spec.class == String
        res = Array.new
        for i in @@base[id]..(@@base[id]+@@size[id]-1)
          line = SCRIPT_LINES__[@@file[id]][i-1].chomp
          res << i - @@base[id] + 1 if line.index(spec)
        end
        return res
      else
        raise "invalid spec: '#{spec}' (must be an integer, array of integers, or a pattern)"
      end    
    end
  
    def Source.range_check(n, id)   # :nodoc:
      max = @@size[id]
      raise "line number must be between 1 and #{max}" unless n >= 1 && n <= max
      return true
    end
    
# Internal use only -- show info about method to verify it's being found by Source.lines

    def Source.info(name)   # :nodoc:
      unless id = Source.find(name)
        puts "Can't find method named '#{name}'"
        return
      end

      printf "file:     %s\n", @@file[id]
      printf "size:     %d\n", @@size[id]
      printf "base:     %d\n", @@base[id]
      printf "helpers:  %s\n", @@helpers[id].inspect
      printf "probes:   %s\n", @@probes[id].inspect
    end
  
  end # Source
  
  
=begin rdoc

== Canvas

The Canvas module defines a graphics window that can be used
for interactive visualizations.  Classes in this module describe objects that are
drawn in the window; for example, objects of type Canvas::Circle are circles
on the canvas.

In the current implementation all drawing objects are derived from a base class
named TkObject, which provides an interface to the Tk library of ActiveTcl.
Instances of TkObject are proxies for the actual objects defined in Tk.
When the user calls a method that opens the RubyLabs Canvas, the method 
initializes a pipe to a new process running the Tcl shell (wish).  If a TkObject is
updated, it sends a Tcl command over the pipe, and the wish process updates
the window.

=end

  module Canvas
    
=begin rdoc
  
== TkObject

Base class of all objects defined for RubyLabs::Canvas.  Objects derived from
this class are proxies for Tk objects in a wish shell, opened when the canvas
is initialized.  

Applications should not try to instantiate a TkObject directly,
but instead should call a constructor of one of the derived classes.  For
example, to draw a circle on the canvas:

  c = Canvas::Circle.new(x, y, r)

Public instance methods defined here are inherited by all objects derived from TkObject,
and can be used to manipulate the object.  For example, to change the color of the circle:

  c.fill = 'green'

The current implementation is very sparse:  the only operations defined are the
ones needs for the visualizations described in the textbook, which are just
the basic methods that create an object or move it around on the screen.

In addition to the usual attributes, these objects have a "pen point", which is
the location of an imaginary pen relative to the object's base
coordinate.  The pen point is used by methods that draw a track as an object is
moved (e.g. see the methods that control the motion of the robot in SphereLab)

=end
  
    class TkObject

      attr_accessor :name, :coords, :penpoint
      
      # Initialization:  set the object ID to 0 and save the file descriptor
      # for the connection to the wish shell.
      #
      # :call-seq:
      #    TkObject.reset(p)
      #
      
      def TkObject.reset(p)
        @@pipe = p
        @@id = 0
      end
      
      # Return a unique ID number for a new proxy object.  
      #
      # :call-seq:
      #    TkObject.nextId()
      #
      
      def TkObject.nextId
        @@id += 1
        return "obj" + @@id.to_s
      end
      
      # Translate a Ruby hash +h+ into a Tk option string.  Example:
      #   >> Canvas::TkObject.options( { :outline => :black, :fill => :red } )
      #   => "-fill red -outline black"
      # Note the ordering of the options in the Tk string may not be the same as
      # the order they are listed when the hash object is created.
      #
      # :call-seq:
      #    TkObject.options(h) => String
      #
            
      def TkObject.options(h)
        a = []
        h.each do |k,v| 
          a << "-#{k} #{v}"
        end
        return a.join(" ")
      end
      
      # Bring an object to the foreground (on top of all other objects on the canvas).
      #
      # :call-seq:
      #    x.raise()
      #    
      
      def raise
        @@pipe.puts ".canvas raise $#{@name}"
      end
      
      # Put an object in the background (below all other objects on the canvas).
      #
      # :call-seq:
      #    x.lower()
      #    

      def lower
        @@pipe.puts ".canvas lower $#{@name}"
      end
      
      # Remove an object from the canvas.
      #
      # :call-seq:
      #    x.erase()
      #    

      def erase
        @@pipe.puts ".canvas delete $#{@name}"
      end
      
      # Assign new coordinates for an object.  Can be used to move or resize an
      # object, but applications should use the more abstract interface defined by class methods in Canvas
      # (e.g. Canvas#move).
      #
      # Example: if an object x is a proxy for a rectangle 
      # that has an upper left corner at (10,10) and 
      # a lower right corner at (20,50), this call will move it down and to the right
      # by 10 pixels:
      #   >> x.coords = [20, 20, 30, 60]
      #   => [20, 20, 30, 60]
      #
      # :call-seq:
      #    x.coords = [...]
      #    

      def coords=(a)
        @coords = a
        @@pipe.puts ".canvas coords $#{@name} #{a.join(' ')}"
      end
      
      # Set the fill color for an object.  Example:
      #   >> x.fill = "green"
      #   => "green"
      #
      # :call-seq:
      #    x.fill = String
      #    

      def fill=(x)
        @@pipe.puts ".canvas itemconfigure $#{name} -fill #{x}"
      end
      
    end
    
=begin rdoc

  == Line
  
  A Line object is a proxy for a line segment defined by a pair of (x,y) coordinates.  
  
  There are no instance methods for Lines beyond those defined in the TkObject base class.
=end

    class Line < TkObject
      
      # Create a new line segment that runs from (x0,y0) to (x1,y1).  Attributes
      # of the line can be passed in a hash object at the end of the argument list.
      #
      # Example -- create a gray line one pixel wide from (0,0) to (100,100):
      #   >> z = Line.new(0, 0, 100, 100, :fill => :gray, :width => 1)
      #   => #<RubyLabs::Canvas::Line:...> 
      #
      # :call-seq:
      #    x = Line.new(x0, y0, x1, y1, args = {})
      #    
      
      def initialize(x0, y0, x1, y1, args = {})
        raise "No canvas" unless @@pipe
        @name = TkObject.nextId
        @coords = [ x0, y0, x1, y1 ] 
        @penpoint = nil
        cmnd = "set #{@name} [.canvas create line #{@coords.join(" ")} #{TkObject.options(args)}]"
        @@pipe.puts cmnd
      end
      
      # Erase all Line objects that are tagged with the ID +tag+.  Tags are optional
      # arguments defined by passing <tt>-tag x</tt> to <tt>Line.new</tt> (see the
      # visualization methods in tsplab.rb, which uses tags to erase all
      # edges from a graph in a single call).
      #
      # :call-seq:
      #    Line.erase_all(tag)
      #    
      
      def Line.erase_all(tag)
        @@pipe.puts ".canvas delete withtag #{tag}"
      end
      
    end
    
=begin rdoc

  == Circle

  A Circle object is a proxy for a Tk oval.  

  There are no instance methods for Circles beyond those defined in the TkObject base class.
=end

    class Circle < TkObject

      # Create a new circle with center at (x,y) and radius r.  Attributes
      # of the circle can be passed in a hash object at the end of the argument list.
      #
      # Example -- create a green cicle with radius 5 at location (20,20):
      #   >> x = Canvas::Circle.new(20, 20, 5, :fill => "green")
      #   => #<RubyLabs::Canvas::Circle:...> 
      #
      # :call-seq:
      #    x = Circle.new(x, y, r, args = {})
      #    

      def initialize(x, y, r, args = {})
        raise "No canvas" unless @@pipe
        @name = TkObject.nextId
        @coords = [ x-r, y-r, x+r, y+r ] 
        @penpoint = [ r, r ]
        cmnd = "set #{@name} [.canvas create oval #{@coords.join(" ")} #{TkObject.options(args)}]"
        @@pipe.puts cmnd
      end
    end
    
=begin rdoc

  == Rectangle

  A Rectangle object is a proxy for a Tk rectangle.  

  There are no instance methods for Rectangles beyond those defined in the TkObject base class.
=end

    class Rectangle < TkObject

      # Create a new rectangle with its upper left corner at (x0,y0) 
      # lower right corner at (x1,y1).  Attributes
      # of the rectangle can be passed in a hash object at the end of the argument list.
      #
      # Example -- create a 20x20 square with upper left corner at (10,10), with a dark green
      # outline and yellow interior:
      #   >> x = Canvas::Rectangle.new(10, 10, 30, 30, :fill => "yellow", :outline => "darkgreen")
      #   => #<RubyLabs::Canvas::Rectangle:...> 
      #
      # :call-seq:
      #    x = Rectangle.new(x0, y0, x1, y1, args = {})
      #    

      def initialize(x0, y0, x1, y1, args = {})
        raise "No canvas" unless @@pipe
        @name = TkObject.nextId
        @coords = [ x0, y0, x1, y1 ] 
        @penpoint = [ (x1-x0)/2, (y1-y0)/2 ]
        cmnd = "set #{@name} [.canvas create rectangle #{@coords.join(" ")} #{TkObject.options(args)}]"
        @@pipe.puts cmnd
      end
    end

=begin rdoc

  == Polygon

  A Polygon object is a proxy for a Tk polygon.  

  In addition to the methods defined in the TkObject base class, a method named +rotate+
  will rotate a Polygon by a specified angle.
=end

    class Polygon < TkObject

      # Create a new polygon.  The first argument is an array of vertex coordinates.  If
      # the polygon has +n+ vertices, the argument should be a flat array of 2*n points.
      # Attributes of the polygon can be passed in a hash object at the end of the argument list.
      #
      # Example -- create a small triangle in the upper left corner of the canvas, with a black
      # outline and green interior:
      #   >> x = Canvas::Polygon.new([10,10,20,20,30,10], :fill => "green", :outline => "black")
      #   => #<RubyLabs::Canvas::Polygon ... >
      #
      # :call-seq:
      #    x = Polygon.new(a, args = {})
      #    

      def initialize(a, args = {})
        raise "No canvas" unless @@pipe
        @name = TkObject.nextId
        @coords = a
        @penpoint = [0,0]
        cmnd = "set #{@name} [.canvas create polygon #{@coords.join(" ")} #{TkObject.options(args)}]"
        @@pipe.puts cmnd
      end
      
      # Rotate the polygon by an angle +theta+ (expressed in degrees).  The object is
      # rotated about the point defined by the first pair of (x,y) coordinates.  The
      # return value is an array with the new coordinates.
      #
      # Example: Suppose +x+ is a square with coordinates (10,10), (20,10), (20,20), and (10,20).
      # This call will rotate it clockwise by 45 degrees and return the new vertices:
      #   >> x.rotate(45)
      #   => [10.0, 10.0, 17.07, 17.07, 10.0, 24.14, 2.93, 17.07]

        def rotate(theta)
          theta = Canvas.radians(theta)
          a = self.coords
          x0 = a[0]
          y0 = a[1]
          (0...a.length).step(2) do |i| 
            x = a[i] - x0
            y = a[i+1] - y0
            a[i]   = x0 + x * cos(theta) - y * sin(theta)
            a[i+1] = y0 + x * sin(theta) + y * cos(theta)
          end
          self.coords = a
          return a
        end
    end
    
=begin rdoc

  == Text

  A Text object is a string displayed on the RubyLabs canvas.  

=end

    class Text < TkObject

      # Display string +s+ at location (+x+,+y+) on the canvas.  By default the coordinates
      # specify the location of the top left of the first character in the string (in Tk
      # terminology, the anchor point for the text is "northwest").  A different anchor
      # position and other attributes of the text can be passed in a hash object at the 
      # end of the argument list.
      #
      # Example -- display a message in dark green letters:
      #   >> x = Canvas::Text.new("hello", 50, 50, :fill => 'darkgreen')
      #   => #<RubyLabs::Canvas::Text: ... >
      #
      # :call-seq:
      #    x = Text.new(s, x, y, args = {})
      #    

      def initialize(s, x, y, args = {})
        raise "No canvas" unless @@pipe
        @name = TkObject.nextId
        @coords = [ x, y ]
        @penpoint = nil
        args[:anchor] = :nw unless args.has_key?(:anchor)
        args[:text] = "\"#{s}\""
        cmnd = "set #{@name} [.canvas create text #{@coords.join(" ")} #{TkObject.options(args)}]"
        @@pipe.puts cmnd
      end
      
      # Replace the string displayed by a text object.  Example:  erase the current string
      # for object +x+ and replace it with "hello, world":
      #   >> x.update("hello, world")
      #   => nil
      # The new string is displayed at the same location and with the same attributes
      # as the old string.
      
      def update(s)
        @@pipe.puts ".canvas itemconfigure $#{name} -text \"#{s}\""
      end
    end
    
=begin rdoc

  == Font

  A Font object defines the appearance of strings displayed by a Text object.  A Font
  object is a proxy for a Tk font object.  The proxy is never used by an application;
  instead, when text is created, it is passed the name of the Tk font (see the example in 
  the description of Font.new).

=end

    class Font < TkObject
      
      @@fonts = []
      
      # Create a font named +name+ with attributes defined in +args+.  When creating
      # a new Text object, +name+ can be passed as an argument to Text.new so the
      # string will be displayed in the specified font. 
      #
      # Example -- create a new font for displaying fixed width text, and then display
      # a message using this font:
      #   >> f = Canvas::Font.new('code', :family => 'Courier', :size => 20)
      #   => #<RubyLabs::Canvas::Font:0x1012587b0 @name="code">
      #   >> t = Canvas::Text.new("Go Ducks!", 100, 100, :font => 'code')
      #   => #<RubyLabs::Canvas::Text:0x101249300 @coords=[100, 100], @name="obj3", @penpoint=nil>
      #
      # :call-seq:
      #    x = Font.new(name,args)
      #    

      def initialize(name, args)
        @name = name
        if @@fonts.index(name).nil?
          cmnd = "font create #{name} #{TkObject.options(args)}"
          @@pipe.puts cmnd
          @@fonts << name
        end
      end
      
    end

# Initialize a drawing canvas with the specified width and height.  If this is the first
# call in an IRB session, open a connection to a wish shell and send it Tcl commands to
# make a window with a single widget, a canvas centered in the middle.  The +title+ argument
# passed to Canvas.init becomes part of the new window.
#
# If this is not the first call to Canvas.init, the existing Tk canvas is resized according
# to the new width and height arguments and the window is renamed using the new name.
#
# An optional fourth argument can be the symbol <tt>:debug</tt>, in which case the return
# value is the Ruby Pipe object used to communicate with Tk.  The Pipe can be useful for
# developing new TkObject objects, since it can be used to see how Tcl commands are
# processed.  Example:
#
#   >> p = Canvas.init(200, 200, "Test", :debug)
#   => #<IO:0x1012a1cd0>
#   >> p.puts ".canvas create text 30 30 -text hello"
#   => nil
#
# :call-seq:
#    Canvas.init(width, height, title, opts = nil)
#
#--
#   TODO Read the path to wish from a configuration file, so users can alter it
#   TODO there are probably other configuration options that can go there, too
#   TODO use popen3 on OSX, capture stderr

    def Canvas.init(width, height, title, *opts)
      
      @@title = "RubyLabs::#{title}"
      @@width = width
      @@height = height
      pad = 12
      
      if @@tkpipe.nil?
        if Canvas.OS == "Windows"
          @@tkpipe = IO.popen("wish", "w")
        elsif Canvas.OS == "Linux"
          @@tkpipe = IO.popen("/opt/ActiveTcl-8.5/bin/wish", "w")
        else
          @@tkpipe = IO.popen("/usr/local/bin/wish", "w")
        end
        at_exit { Canvas.close }
        @@tkpipe.puts "tk::canvas .canvas -bg white -width #{width} -height #{height}"
        @@tkpipe.puts ". configure -bg gray"
        @@tkpipe.puts "pack .canvas -padx #{pad} -pady #{pad}"
        TkObject.reset(@@tkpipe)
      else
        @@tkpipe.puts ".canvas delete all"
        @@tkpipe.puts ".canvas configure -width #{width} -height #{height}"
      end
      
      @@tkpipe.puts "wm geometry . #{width+2*pad}x#{height+2*pad}+30+50"
      @@tkpipe.puts "wm title . #{@@title}"
        
      return opts[0] == :debug ? @@tkpipe : true
    end
    
    # Send an +exit+ command to the wish shell, which closes the drawing window and
    # terminates the shell.
    #
    # :call-seq:
    #    Canvas.close()
    #
    
    def Canvas.close
      if @@tkpipe
        @@tkpipe.puts "exit"
        @@tkpipe = nil
        TkObject.reset(nil)
      end
    end
    
    # Return the current width of the canvas.
    #
    # :call-seq:
    #    Canvas.width() => Fixnum
    #
    
    def Canvas.width
      @@width
    end
    
    # Return the current height of the canvas.
    #
    # :call-seq:
    #    Canvas.height() => Fixnum
    #
    
    def Canvas.height
      @@height
    end
    
    # Return a reference to the Pipe object used to communicate with the wish shell.
    #
    # :call-seq:
    #    Canvas.pipe() => IO
    #
    
    def Canvas.pipe
      @@tkpipe
    end
            
    #--
    # Idea for the future, abandoned for now: allow applications to define a coordinate
    # system, e.g. cartesian with the origin in the middle of the canvas, and map coords
    # pass to line, rectangle, etc from user-specified coordinates to Tk coordinates.
    # Lots of complications, though -- e.g. if an application calls the coords method to
    # get object coordinates (e.g. RandomLab#add_tick gets y coordinate of number line)
    # it will have to map back from Tk to the selected mapping.....
    
    # def Canvas.origin(option)
    #   case option
    #   when :tk
    #     @@map = lambda { |x,y| return x, y }
    #   when :quadrant
    #     @@map = lambda { |x,y| return x, @@height - y }
    #   when :cartesian
    #     @@map = lambda { |x,y| return x + @@width/2, @@height/2 - y }
    #   end
    # end
    # 
    # def Canvas.map(a)
    #   (0...a.length).step(2) do |i| 
    #     a[i], a[i+1] = @@map.call( a[i], a[i+1] )
    #   end
    # end
    #++
        
    # Return a string that uses the <tt>RUBY_PLATFORM</tt> environment variable to
    # determine the host operating system type.  Possible return values are "Mac OS X",
    # "Linux", or "Windows". 
    #
    # :call-seq:
    #    Canvas.OS() => String
    #
    #-- 
    # TODO:  find out what the platform string is for the legacy windows one-click installer;
    # the new installer uses the "mingw" compiler.
    
    def Canvas.OS
      if RUBY_PLATFORM =~ %r{darwin}
        return "Mac OS X"
      elsif RUBY_PLATFORM =~ %r{linux}
        return "Linux"
      elsif RUBY_PLATFORM =~ %r{mingw}
        return "Windows"
      else
        return "Unknown"
      end
    end
    
    # Move an object by a distance +dx+ vertically and a distance +dy+ horizontally.
    # If the fourth argument is the symbol <tt>:track</tt> a line segment is drawn
    # connecting the pen position of the object's previous location with the
    # pen position of its new location.  The return value is an array with the new
    # coordinates.
    #
    # Example: Suppose +x+ is a Polygon with coordinates (10,10), (20,20), and (30,10).
    # This call moves it down and to the right by 10 pixels and returns the new location:
    #   >> Canvas.move(x, 10, 10)
    #   => [20, 20, 30, 30, 40, 20]
    #
    # :call-seq:
    #    Canvas.move(obj, dx, dy, track = nil)
    #

    def Canvas.move(obj, dx, dy, option = nil)
      a = obj.coords
      if option == :track
        x0 = a[0] + obj.penpoint[0]
        y0 = a[1] + obj.penpoint[1]
      end
      (0...a.length).step(2) do |i| 
        a[i] += dx
        a[i+1] += dy
      end
      obj.coords = a
      if option == :track
        x1 = a[0] + obj.penpoint[0]
        y1 = a[1] + obj.penpoint[1]
        Canvas::Line.new( x0, y0, x1, y1, :width => 1, :fill => '#777777' )
        obj.raise
      end
      return a
    end
    
    # Convert an angle from degrees to radians.  Example:
    #   >> Math::PI / 4
    #   => 0.785398163397448
    #   >> Canvas.radians(45)
    #   => 0.785398163397448
    #
    # :call-seq:
    #    Canvas.radians(deg) => Float
    #
           
    def Canvas.radians(deg)
      deg * Math::PI / 180
    end
    
    # Convert an angle from radians to degrees.  Example:
    #   >> Canvas.degrees( Math::PI / 2 )
    #   => 90.0
    #
    # :call-seq:
    #    Canvas.degrees(rad) => Float
    #

    def Canvas.degrees(rad)
      180 * rad / Math::PI
    end
        
    # Make a range of colors starting from +first+ and going to +last+ in +n+ steps.
    # Color arguments should be be 3-tuples of integer RGB values.  The
    # result is an array that starts with +first+, has +n+-1 intermediate colors,
    # and ends with +last+.  
    #
    # Example: 
    #   >> Canvas.palette( [255,0,0], [0,0,0], 10)
    #   => ["#FF0000", "#E60000", "#CD0000", ... "#1E0000", "#000000"]
    # The return value is an array of 11 colors starting with red and ending with black.
    #
    # :call-seq:
    #    Canvas.palette(first, last, n) => Array
    #
    
    def Canvas.palette(first, last, n)
      d = Array.new(3)
      3.times { |i| d[i] = (first[i] - last[i]) / n }
      a = [first]
      (n-1).times do |i|
        a << a.last.clone 
        3.times { |j| a.last[j] -= d[j] }
      end
      a << last
      a.map { |c| sprintf("#%02X%02X%02X",c[0],c[1],c[2]) }
    end
   
    @@tkpipe = nil
    @@title = ""
    @@height = 0
    @@width = 0
 
  end # Canvas
  
=begin rdoc

== PriorityQueue

A PriorityQueue is a collection of objects that is always maintained in order.
Any kind of object can be in the queue as long as it can be compared with the < operator.
More precisely, if an object +x+ responds to the < operator, and +x+ < +y+ is
defined for every object +y+ already in the queue, then +x+ can be inserted.

The methods that insert and remove items check to see if an instance variable
named <tt>@on_canvas</tt> is +true+.  If so, a method named +update+ is called.  
+update+ is not defined here, but is added to the class by modules that 
use the queue during visualizations (see the definition of the priority queue
used in the Huffman tree project in bitlab.rb for an example).  

Several methods of the Array class are defined dynamically in the PriorityQueue
class when this module
is loaded.  These methods have the same meaning for PriorityQueue objects as
they do for Array objects:

+length+:: return the number of items in the queue
+first+:: return a reference to the first item in the queue
+last+:: return a reference to the last item in the queue
+to_s+:: generate a String representation of the queue (by calling Array#to_s)
+inspect+:: generate a String representation of the queue (by calling Array#inspect)
+clear+:: remove all items from the queue
<tt>empty?</tt>:: return +true+ if the queue has no items

=end

  class PriorityQueue

    # Create a new, initially empty, priority queue.
    
    def initialize
      @q = Array.new
    end
    
    # Insert an item into the queue.  The item's location is determined by how
    # it compares with other items, according to the < operator.  Specifically,
    # when item +x+ is added to a queue, it it put before the first item +y+
    # where +x+ < +y+.
    #
    # Example: suppose object +q+ has three strings:
    #   >> q
    #   => ["Au", "He", "O"]
    # This expression adds the string "Fe" to the queue:
    #   >> q << "Fe"
    #   => ["Au", "Fe", "He", "O"]
    # The new string went into the second position because "Fe" < "Au" is false but "Fe" < "He" is true. 
    
    def <<(obj)
      raise "Object cannot be inserted into priority queue" unless obj.respond_to?(:<)
      i = 0
      while (i < @q.length)
        break if obj < @q[i]
        i += 1
      end
      @q.insert(i, obj)
      update(:insert, obj) if @on_canvas
      return @q
    end
    
    # Remove the first item from the queue, returning a reference to that item.
    #
    # Example: suppose object +q+ has three strings:
    #   >> q
    #   => ["Au", "He", "O"]
    # Then a call to shift removes the string "Au" and leaves the remaining items in order in the queue:
    #   >> x = q.shift
    #   => "Au"
    #   >> q
    #   => ["He", "O"]
    #
    
    def shift
      res = @q.shift
      update(:shift, res) if @on_canvas
      return res
    end
    
    # Return the item at location +i+ in the queue.  *Note*: unlike Array objects, an
    # index expression cannot be used on the left side of an assignment.  If 
    # +q+ is a PriorityQueue object,
    #    x = q[i]
    # is valid, but
    #    q[i] = x
    # is undefined.

    def [](i)
      @q[i]
    end
    
    # Call +f+ for every item in the queue, and return an array with
    # the result of each call (essentially the same as the +map+ operation
    # defined for Ruby's Enumeration interface).
    #
    # Example:
    #   >> q
    #   => ["avocado", "boysenberry", "clementine", "elderberry", "loquat"]
    #   >> q.collect { |x| x.length }
    #   => [7, 11, 10, 10, 6]
    
    def collect(&f)
      @q.map { |x| f.call(x) }
    end
    
    # Evaluate block +b+ for every item in the queue (equivalent to <tt>Array#each</tt>)
    #
    # Example:
    #   >> q
    #   => ["Au", "He", "O"]
    #   >> q.each { |x| puts x }
    #   Ar
    #   He
    #   O
    #   => ["Au", "He", "O"]    
    
    def each(&b)
      @q.each &b
    end
    
    # Evaluate block +b+ for every item in the queue, also passing the item's
    # location in the queue to the block (equivalent to <tt>Array#each_with_index</tt>)
    #
    # Example:
    #   >> q
    #   => ["Au", "He", "O"]
    #   >> q.each_with_index { |x,i| puts "#{i}: #{x}" }
    #   0: Ar
    #   1: He
    #   2: O
    #   => ["Au", "He", "O"]  
      
    def each_with_index(&b)
      @q.each_with_index &b
    end

    %w{length first last to_s inspect clear empty?}.each do |name|
      eval "def #{name}() @q.#{name} end"
    end

  end # PriorityQueue

end # RubyLabs

=begin rdoc

== Fixnum

When the RubyLabs module is loaded it defines a new method named +ord+ to the
Fixnum class.  In Ruby 1.8, using the <tt>[]</tt> operator to access items in a String object 
returns the ASCII value of a character.  The +ord+ method defined here (and used by hash functions defined in hashlab.rb)
maps the ASCII value of a letter to a number between 0 and 25.

The BitLab module also extends Fixnum by defining a method named +code+ that returns a Code
object containing the binary or hexadecimal representation of an integer.
#--
NOTE: +ord+ is built in to Ruby 1.9, so this method will have to be renamed or reimplemented
when RubyLabs is ported to 1.9.
=end

class Fixnum
  
  # If a number is the ASCII code for a letter from the Roman alphabet (upper or lower case,
  # in the range 'A' to 'Z') map it to a number between 0 and 25, otherwise just return the
  # value of the number.
  #
  # Example:
  #   >> "Ducks!".each_byte { |x| puts x.ord }
  #   3
  #   20
  #   2
  #   10
  #   18
  #   33
  
  def ord
    if self >= ?a && self <= ?z
      self - ?a
    elsif self >= ?A && self <= ?Z
      self - ?A
    else
      self
    end
  end

end # Fixnum

include RubyLabs