module RubyLabs

=begin rdoc
  
== IterationLab

The IterationLab module has definitions of methods from Chapter 4
of <em>Explorations in Computing</em>.

The methods demonstrate how a simple strategy of repeatedly comparing
items in an array can be used to search the array and to sort it. 
The module has two implementations of linear search (<tt>contains?</tt> 
and +search+) and an implementation of insertion sort (+isort+).

Helper methods called by the searching and sorting methods are also
documented here. 

=end

module IterationLab

# The RubyLabs implementation of Ruby's <tt>include?</tt> method.
# Does a linear search of array +a+ to find item +k+, returning
# +true+ or +false+ depending on whether the item was found.  
#
# Example:
#   >> a = TestArray.new(10)
#   => [89, 41, 69, 14, 4, 7, 8, 26, 81, 12]
#   >> contains?(a, 7)
#   => true
#   >> contains?(a, 42)
#   => false
#
# :call-seq:
#   contains?(a,k) => Boolean
#
#-- 
# :begin :contains?
  def contains?(a, k)
    a.each { |x| return true if x == k}
    return false
  end
# :end :contains?

# The RubyLabs implementation of Ruby's <tt>index</tt> method.
# Does a linear search of array +a+ to find item +k+, returning
# the index of the first occurrence of +k+ or +nil+ if +k+ is
# not found. 
#
# Example:
#   >> a = TestArray.new(10)
#   => [89, 41, 69, 14, 4, 7, 8, 26, 81, 12]
#   >> search(a, 42)
#   => nil
#   >> search(a, 7)
#   => 5
#
# :call-seq:
#   search(a,k) => Fixnum
#
#-- 
# :begin :search
  def search(a, k)
    i = 0
    while i < a.length
      return i if a[i] == k
      i += 1
    end
    return nil
  end
# :end :search

# Return a copy of +a+, sorted using the insertion sort algorithm.  
# On each iteration remove an item from the
# array, find a location for it to the left of its original position,
# and insert it back into the array at the new location.
#
# Example:
#   >> a = TestArray.new(10)
#   => [97, 87, 16, 2, 81, 80, 7, 64, 5, 71]
#   >> isort(a)
#   => [2, 5, 7, 16, 64, 71, 80, 81, 87, 97]
#
# :call-seq:
#   isort(a) => Array
#
#-- 
# :begin :isort :move_left :less
  def isort(array)
    a = array.clone           # don't modify the input array....
    i = 1
    while i < a.length
      move_left(a, i)       # find a place for a[i] somewhere to the left
      i += 1
    end
    return a
  end
# :end :isort

# Helper method called by +isort+ to remove the item at locaton +i+
# and reinsert it at a location between 0 and +i+ (i.e. move the item
# to the left in the array).
#--
# :begin :move_left
  def move_left(a, i)
    x = a.slice!(i)                 # remove the item at location i
    j = i-1                         # start scanning from the left of i
    while j >= 0 && less(x, a[j])
      j = j-1                       # move left
    end
    a.insert(j+1, x)                # insert x back into a at location j    
  end
# :end :move_left

# +less+ is called by +isort+ to compare two items.
# It is implemented as a helper method in order to allow users to
# attach a probe to count the number of comparisons.
#--
# :begin :less
  def less(x, y)
    return x < y
  end
# :end :less

# A helper method that can be called from a probe to display the contents
# of an array during a search or sort.
#
# A call to <tt>brackets(a,i)</tt> will return a string that includes
# all the items in +a+, with a left bracket before <tt>a[i]</tt>
# and a right bracket after the last item.
#
# See also RecursionLab#brackets.
#
# Example:
#   >> a = TestArray.new(10)
#   => [55, 29, 72, 33, 14, 57, 85, 42, 26, 97]
#   >> puts brackets(a, 3)
#   29  55  72 [33  14  57  85  42  26  97]
#   => nil
#  
# :call-seq:
#   brackets(a,i) => String
#
  def brackets(a, i)
    if i <= 0
      return ("[" + a.join("  ") + "]")
    elsif i >= a.length
      return " " + a.join("  ") + "  [ ]"
    else
      pre = a.slice(0..(i-1))
      post = a.slice(i..-1)
      return " " + pre.join("  ") + " [" + post.join("  ") + "]"
    end
  end
  
end # IterationLab

end # RubyLabs