=begin rdoc
  
== IterationLab

The methods implemented in this module are 
+contains?+ (linear search returning true or false),
+location+ (linear search returning the index of specified item), and
+isort+ (insertion sort).  See the RecursionLab module for more
sophisticated "divide and conquer" searching and sorting algorithms.  

=end

module RubyLabs

module IterationLab

=begin rdoc
Do a linear search of array +a+ to find item +key+, returning
+true+ or +false+ depending on whether the item was found.  
=end

# :begin :contains?
	def contains?(a, k)
	  a.each { |x| return true if x == k}
		return false
	end
# :end :contains?

=begin rdoc
Do 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.  
=end

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

=begin rdoc
Return a copy of +array+, sorted with 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.
=end

# :begin :isort :insert_left :less
	def isort(array)
	  a = array.clone           # don't modify the input array....
	  i = 1
	  while i < a.length
	    insert_left(a, i)       # find a place for a[i] somewhere to the left
	    i += 1
	  end
	  return a
	end
# :end :isort

# :begin :insert_left
  def insert_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 :insert_left

# :begin :less
  def less(x, y)
    return x < y
  end
# :end :less

=begin rdoc
Simple demonstration of why nested loops lead to n^2 operations
=end

# :begin :nested
  def nested(n)
    n.times do |i|
      n.times do |j|
        puts "i = #{i}, j = #{j}"
      end
    end
  end
# :end :nested

# code used in figure next to nested

  def isnest(n)
    i = 1
    while i < n
      j = i-1
      while j >= 0 
        puts "i = #{i}, j = #{j}"
        j = j-1
      end
      i = i+1
    end
  end

=begin rdoc
A helper method that can be called from a probe to display the contents
of an array during a search or sort.
=end

	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