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

# $LOAD_PATH.unshift(File.join(File.dirname(__FILE__), '..', 'bin'))

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 :Viewer,         "viewer.rb"

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)
    Math.log(x) / Math.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
#   Return a copy of object x with the elements in a new, scrambled order.  The
#   parameter x can be any object that has an index operator (e.g. strings or
#   arrays).
# =end
#   
#   def permutation(x)
#     res = x.clone
#     for i in 0..res.length-2
#       r = rand(res.length-i) + i
#       res[i], res[r] = res[r], res[i]
#     end
#     return res
#   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.

# The @spread variable controls the average spacing between items.  The 6.667 for
# small arrays means an array of 15 will have numbers between 0 and 99.

# 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
        
    def initialize(size)
      @spread = (size > 50) ? 10 : 6.667
  		@h = Hash.new

  		while @h.size < size
  			@h[ rand( size * @spread ) ] = 1		
  		end

  		@h.keys.each do |k|
  		  self << k
  		end    
    end
    
    def random(outcome)
      if outcome == :success
        return self[ rand(self.length) ]
      elsif outcome == :fail
        loop do
          i = rand( self.length * @spread )
          return i if @h[i] == nil
        end
      else
        return nil
      end
    end
    
  end       # class TestArray	
	
=begin rdoc
	
=== RandomArray

Similar to TestArray, but draws random words from a file.

=end

  class RandomArray < Array

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

		def initialize(src, n)
			fn = @@sources[src] or raise "RandomArray: undefined array type: #{src}"
			words = File.open(fn).readlines
			a = Hash.new
			while a.size < n
			  w = words[rand(words.length)].chomp
				a[w] = 1		
			end
			a.keys.each do |w|
			  self << w
			end
		end
		
		def RandomArray.sources
		  return @@sources.keys.sort { |a,b| a.to_s <=> b.to_s }
	  end

	end # RandomArray
	
	
=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 !~ /\.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 = nil, nil, nil
      names = []
      
			catch (:found) do
				SCRIPT_LINES__.each do |file, lines|
					line_num = 0
					lines.each do |s|
						line_num += 1
						if match = s.match(/:begin\s+(.*)/)
						  names = match[1].split.collect{|x| eval(x)}
						  if names[0] == id
  							filename = file
  							base = line_num + 1
  							next
					    end
						end
						if s =~ /:end\s+:#{id.to_s}/
						  size = line_num - base
							throw :found
						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] = names[1..-1]
			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[name]
    printf "size: %d\n", @@size[name]
    printf "base: %d\n", @@base[name]
    printf "probes: %s\n", @@probes[name].inspect
  end
  
  end # Source
  
=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.
=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)
    end

    %w{shift 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

  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