Module: RubyLabs::IterationLab

Defined in:
lib/iterationlab.rb

Overview

IterationLab

The IterationLab module has definitions of methods from Chapter 4 of Explorations in Computing.

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 (contains? and search) and an implementation of insertion sort (isort).

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

Defined Under Namespace

Classes: ArrayView

Constant Summary collapse

@@viewOptions = 
{
  :array_fill => 'lightblue',
  :bar_fill => 'darkblue',
  :canvas_fill => 'white',
  :mark_color => 'blue',
  :x0 => 10,                  # left edge of leftmost bar
  :dx => 10,                  # distance between left edges of adjacent bars
  :y0 => 50,                  # top edege of tallest bar
  :y1 => 150,                 # bottom edge of array bars
  :ymin => 3,                 # minimum height of bar
  :delay => 0.01,
}
@@drawing = 
nil

Instance Method Summary collapse

Instance Method Details

#brackets(a, i) ⇒ Object

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 brackets(a,i) will return a string that includes all the items in a, with a left bracket before a[i] 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



174
175
176
177
178
179
180
181
182
183
184
 
# File 'lib/iterationlab.rb', line 174

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

#contains?(a, k) ⇒ Boolean

The RubyLabs implementation of Ruby’s include? 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?

Returns:

  • (Boolean) 


56
57
58
59
 
# File 'lib/iterationlab.rb', line 56

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

#init_step(a, i) ⇒ Object

Helper method called at the start of each top level iteration if the array is on the canvas – change the color of the bar for a and resize the progress bar to show a has been moved.



205
206
207
208
209
210
 
# File 'lib/iterationlab.rb', line 205

def init_step(a, i)
  rect = @@drawing.rects[i]
  a.touch(rect, @@drawing.history, @@drawing.palette) 
  a.set_region(i+1, a.length, @@drawing.bar, @@drawing.options)
  sleep(@@drawing.options[:delay])    
end

#isort(array) ⇒ Object

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



106
107
108
109
110
111
112
113
114
 
# File 'lib/iterationlab.rb', line 106

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

#less(x, y) ⇒ Object

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



150
151
152
 
# File 'lib/iterationlab.rb', line 150

def less(x, y)
  return x < y
end

#move_left(a, i) ⇒ Object

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



122
123
124
125
126
127
128
 
# File 'lib/iterationlab.rb', line 122

def move_left(a, i)
  init_step(a, i) if @@drawing
  while i > 0 && less(a[i], a[i-1])
    swap(a, i-1, i)
    i -= 1
  end
end

#search(a, k) ⇒ Object

The RubyLabs implementation of Ruby’s index 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



80
81
82
83
84
85
86
87
 
# File 'lib/iterationlab.rb', line 80

def search(a, k)
  i = 0
  while i < a.length
    return i if a[i] == k
    i += 1
  end
  return nil
end

#swap(a, i, j) ⇒ Object

Helper method called by move_left to exchange the items at specified locations in an array. If there is a visualization on the screen call the helper method that swaps the locations of bars for a and a. – :begin :swap



136
137
138
139
140
141
142
 
# File 'lib/iterationlab.rb', line 136

def swap(a, i, j)
  a[i], a[j] = a[j], a[i]
  if @@drawing
    a.swap_bars(@@drawing.rects, i, j, @@drawing.options)
    sleep(@@drawing.options[:delay])
  end
end

#view_array(a, userOptions = {}) ⇒ Object

Visualization for isort. Draw a vertical bar for each item in the array, setting the height of bar i according to the value of a. Draw a horizontal progress bar below the array values.



190
191
192
193
194
195
196
197
198
199
 
# File 'lib/iterationlab.rb', line 190

def view_array(a, userOptions = {})
  Canvas.init(800, 200, "IterationLab")
  options = @@viewOptions.merge(userOptions)

  rects = TestArray.draw_bars(a, options)
  progress = Canvas::Rectangle.new( options[:x0], options[:y1] + 10, options[:x0] + a.length*options[:dx], options[:y1]+15, :fill => options[:bar_fill] )
  
  @@drawing = ArrayView.new(a, rects, progress, ['#000080','#BADFEB'], [], options)
  return true
end