=begin rdoc

= RubyLabs

Common methods used by two or more lab projects.

Methods used to monitor execution of programs during experiments.  

=end

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

module RubyLabs

=begin rdoc
  
=== hello

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

=end

  def hello
    "Hello, you have successfully installed RubyLabs!"
  end

=begin rdoc
Log base 2.
=end

  def log2(x)
    log(x) / log(2.0)
  end
  
=begin rdoc
  Return the larger of a and b
=end

  def max(a,b)
    a > b ? a : b
  end
  
=begin rdoc
  Return the smaller of +a+ and +b+
=end

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

  
=begin rdoc
  
Call +time { foo(...) }+ to measure the execution time of a call to +foo+.  This
method will time any arbitrary Ruby expression.

=end

  def time(&f)
    tstart = Time.now
    f.call
    return Time.now - tstart
  end
  
=begin rdoc
  
Call trace { foo(...) } to monitor the execution of the call to foo.  Sets up
a callback method which checks to see if a probe has been attached to a line
via a call to Source.probe, and if so evaluates the expression associated with 
the probe.

=end

# 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

=begin rdoc

A call to count { foo(...) } is similar to a call to trace, but instead of evaluating
the expression associated with a probe it just counts the number of times the
lines are executed and returns the count.

Note: this version assumes there are two different kinds of probes.  Probes monitored
by the trace method are expressions that are evaluated when the probed expression is
encountered, and probes monitored by the count method are :count tags.

=end

  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 numbers to use in testing searching and sorting
algorithms.  Call TestArray.new(n) to make an array of n unique random numbers.

A method named +random+ will return a random element to use as a search target.
Call +a.random(:success)+ to get a value that is in the array +a+, or call 
+a.random(:fail)+ to get a number that is not in the array.  

=end

# 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
 
  class TestArray < Array

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

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

		def TestArray.sources
		  return @@sources.keys.sort { |a,b| a.to_s <=> b.to_s }
	  end
	      
  end       # class TestArray	
  
  
  def TestArray(n, type = nil)
    TestArray.new(n, type)
  end
	
	
=begin
  The Source module has methods that access the source code for a lab
  project.  Since the outer module (RubyLabs) assigns SCRIPT_LINES__ the 
  source code has already been read from the file -- these methods just have
  to look for the code in memory.  The methods assume the code students will
  look at has been delimited by comments containing the strings :begin and :end.
=end

  module Source
    
    @@probes = Hash.new
		@@file = Hash.new
		@@size = Hash.new
		@@base = Hash.new
		@@helpers = Hash.new
		@@line = nil
    
=begin
  Print the source code for method +name+.
=end
    
    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
    
=begin
  Write a copy of the source code for method +name+.  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.
=end

    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
    
    def Source.print_source(f, id)
  		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
    
=begin rdoc
  Attach a probe to a line in method +name+.  The line can be specified
  by line number or a pattern.  If a string is passed as a third parameter
  that string will be evaluated when the method is called from a block passed
  to trace, otherwise a count probe is created.
=end
    
    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
	  
=begin rdoc
  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).
=end

    def Source.probing(filename, method, line)
      return nil if line == @@line
      @@line = line
      return nil unless @@probes[method] && @@file[method] == filename
      return @@probes[method][line] 
    end
	  
=begin rdoc
  Print the currently defined probes. 
=end

    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
    
=begin rdoc
  Clear the probes on a designated method (or all methods)
=end

    def Source.clear(name = nil)
      @@probes.each do |id, plist|
        next if ! name.nil? && id != name
        plist.clear
      end
      return true
    end
    
=begin
  Internal use only -- locate the filename, starting line number, and length
  of a method named +name+ (+name+ can be a string or a symbol), 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....
  
  TODO:  save helper files listed on :begin line
=end

    def Source.find(name)
      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
    
=begin rdoc
  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.
=end

    def Source.lines(spec, id)
      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)
      max = @@size[id]
      raise "line number must be between 1 and #{max}" unless n >= 1 && n <= max
      return true
    end
    
=begin rdoc
  Internal use only -- show info about method
=end

    def Source.info(name)
      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
  Module for interactive graphics.
=end

  module Canvas
    
    def Canvas.init(width, height, title, *opts)
      require 'tk'
      
      @@title = "RubyLabs::#{title}"
      @@width = width
      @@height = height
      
      if @@tkroot.nil?
        #         @@tkroot = TkRoot.new { title @@title }
        # @@content = TkFrame.new(@@tkroot)
        # @@canvas = TkCanvas.new(@@content, :width => width, :height => height) 
        #         @@canvas.grid :column => 0, :row => 0, :columnspan => 4, :padx => 10, :pady => 10
        # @@content.pack :pady => 20

      	@@tkroot = TkRoot.new { title @@title }
        # @@content = TkFrame.new(@@tkroot)
    		@@canvas = TkCanvas.new(@@tkroot, :width => width, :height => height) 
        # @@canvas.grid :column => 0, :row => 0, :columnspan => 4, :padx => 10, :pady => 10
        @@canvas.pack :padx => 10, :pady => 10
        # @@content.pack :pady => 20

      	@@threads = []
      	@@threads << Thread.new() do
      		Tk.mainloop
      	end
    	else
    	  Canvas.clear
    	  @@canvas.height = height
    	  @@canvas.width = width
    	  @@tkroot.title = @@title
    	end
    	return opts[0] == :debug ? @@canvas : true
    end
    
    def Canvas.width
      @@width
    end
    
    def Canvas.height
      @@height
    end
    
    def Canvas.root
      @@tkroot
    end
    
    def Canvas.create(*args)
      @@canvas.send(:create, *args)
    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
    
    def Canvas.clear
      @@objects.each { |x| x.delete }
      @@objects.clear
    end
    
    # total hack -- if on OS X and version is 1.8 and called directly from irb pause to
    # synch the drawing thread....
    
    def Canvas.sync
      if RUBY_VERSION =~ %r{^1\.8} && RUBY_PLATFORM =~ %r{darwin} && caller[1].index("(irb)") == 0
        sleep(0.1)
      end
      # @@tkroot.update :idletasks
    end
    
=begin rdoc
  Add text at (x, y).  Note -- looks like :anchor is required, otherwise runtime error
  from Tk (something about illegal coords).
=end

    def Canvas.text(s, x, y, opts = {})
      return nil unless @@canvas
      opts[:anchor] = :nw unless opts.has_key?(:anchor)
      opts[:text] = s
      text = TkcText.new( @@canvas, x, y, opts)
      @@objects << text
      return text
    end
    
    def Canvas.font(options)
      return TkFont.new(options)
    end
    
=begin rdoc
  Draw a line from (x0,y0) to (x1,y1)
=end

    def Canvas.line(x0, y0, x1, y1, opts = {})
      return nil unless @@canvas
      line = TkcLine.new( @@canvas, x0, y0, x1, y1, opts )
      @@objects << line
      return line
    end
    
=begin rdoc
  Draw a rectangle with upper left at (x0,y0) and lower right at (x1,y1).
=end
        
    def Canvas.rectangle(x0, y0, x1, y1, opts = {})
      return nil unless @@canvas
      rect = TkcRectangle.new( @@canvas, x0, y0, x1, y1, opts)
      Canvas.makeObject(rect, (x1-x0)/2, (y1-y0)/2)
    end
    
=begin rdoc
  Draw a circle with center at (x,y) and radius r
=end

    def Canvas.circle(x, y, r, opts = {})
      return nil unless @@canvas
      ulx, uly, lrx, lry = x-r, y-r, x+r, y+r 
      circ = TkcOval.new( @@canvas, ulx, uly, lrx, lry, opts )
      Canvas.makeObject(circ, r, r)
    end
    
=begin rdoc
  Draw a polygon with vertices defined by array a.  The array can be a flat
  list of x's and y's (e.g. [100,100,100,200,200,100]) or a list of (x,y)
  pairs (e.g. [[100,100], [100,200], [200,100]]).
=end

    def Canvas.polygon(a, opts = {})
      return nil unless @@canvas
      poly = TkcPolygon.new( @@canvas, a, opts)
      Canvas.makeObject(poly, 0, 0)
    end
    
=begin rdoc
  Move an object by an amount dx, dy
=end

    def Canvas.move(obj, dx, dy, option = nil)
      a = obj.coords
      if option == :track
        x0 = a[0] + obj.penx
        y0 = a[1] + obj.peny
      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.penx
        y1 = a[1] + obj.peny
        @@objects << TkcLine.new( @@canvas, x0, y0, x1, y1, :width => 1, :fill => '#777777' )
        obj.raise
      end
      return a
    end
    
=begin rdoc
  Attach a "pen point" to an object by adding new accessor methods named penx and peny,
  and save the object in a local list so it can be erased by Canvas.clear
=end

    def Canvas.makeObject(obj, xoff, yoff)
      class <<obj
        attr_accessor :penx, :peny
      end
      obj.penx = xoff
      obj.peny = yoff
      @@objects << obj
      return obj
    end
    
=begin rdoc
  Rotate an object by an angle theta (expressed in degrees).  The object is
  rotated about the point defined by the first pair of (x,y) coordinates.
=end

    def Canvas.rotate(obj, theta)
      theta = Canvas.radians(theta)
      a = obj.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
      obj.coords = a
      return a
    end
       
    def Canvas.radians(deg)
      deg * Math::PI / 180
    end
    
    def Canvas.degrees(rad)
      180 * rad / Math::PI
    end
    
    @@tkroot = nil
    @@objects = Array.new
    @@title = ""
    @@height = 0
    @@width = 0
    @@map = lambda { |x,y| return x, y }
    
=begin rdoc
  Make an array of n colors that vary from first to last.
=end
    
    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
    
  end # Canvas
  
=begin rdoc
  Priority queue class -- simple wrapper for an array that can only be updated via
  +<<+ and +shift+ operations.  Also responds to +length+, +first+, and +last+, 
  and allows direct access to an item through an index expression, but does not allow 
  assignment via an index or any other array operation.
  The +<<+ method checks to make sure an object is comparable (responds to <) before 
  adding it to the queue.
  
  If a program that uses a priority queue adds an instance variable named @on_canvas
  the shift and << methods will call a method named update so drawings that show
  a queue can be updated.
=end

  class PriorityQueue

    def initialize
      @q = Array.new
    end

    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
    
    def shift
      res = @q.shift
      update(:shift, res) if @on_canvas
      return res
    end

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

    def [](i)
      @q[i]
    end
    
    def collect(&f)
      @q.map { |x| f.call(x) }
    end
    
    def each(&b)
      @q.each &b
    end
    
    def each_with_index(&b)
      @q.each_with_index &b
    end

  end # PriorityQueue

end # RubyLabs

class Fixnum
  
=begin rdoc

An 'ord' method for the Fixnum class that maps ASCII codes for letters
to numbers between 0 and 25.

<b>NOTE:</b> +ord+ is built in to Ruby 1.9, and will be sligthly different; for 
characters (1-letter strings) +ord+ will return the ASCII value.
  
=end

	def ord
		if self >= ?a && self <= ?z
			self - ?a
		elsif self >= ?A && self <= ?Z
			self - ?A
		else
			self
		end
	end

end # Fixnum

include RubyLabs