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



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

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

#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



165
166
167
 
# File 'lib/iterationlab.rb', line 165

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). – updated 10/9/2012 for visualization :begin :move_left



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/iterationlab.rb', line 123

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    
  if @@drawing
    touch(i) 
    set_region(i+1)
    sleep(@@drawing.options[:delay])
  end
  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

#set_region(loc) ⇒ Object 



232
233
234
235
236
 
# File 'lib/iterationlab.rb', line 232

def set_region(loc)
  x1, y1, x2, y2 = @@drawing.bar.coords
  x1 = @@drawing.options[:x0] + loc * @@drawing.options[:dx]
  @@drawing.bar.coords = [x1, y1, x2, y2]
end

#swap(a, i, j) ⇒ Object

Helper method called by move_left to exchange the items at specified locations in an array. – :begin :swap



146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/iterationlab.rb', line 146

def swap(a, i, j)
  a[i], a[j] = a[j], a[i]
  if @@drawing.class == ArrayView
    dist = (j - i) * @@drawing.options[:dx]
    ri = @@drawing.rects[i]
    rj = @@drawing.rects[j]
    Canvas.move(ri, dist, 0)
    Canvas.move(rj, -dist, 0)
    @@drawing.rects[i], @@drawing.rects[j] = @@drawing.rects[j], @@drawing.rects[i]
    sleep(@@drawing.options[:delay])
  end
end

#touch(loc) ⇒ Object 



222
223
224
225
226
227
228
229
230
 
# File 'lib/iterationlab.rb', line 222

def touch(loc)
  rect = @@drawing.rects[loc]
  pmax = @@drawing.palette.length
  @@drawing.history.pop if @@drawing.history.length >= pmax
  @@drawing.history.insert(0, rect)
  @@drawing.history.each_with_index do |r, i|
    r.fill = @@drawing.palette[i]
  end   
end

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

Visualization



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/iterationlab.rb', line 203

def view_array(a, userOptions = {})
  Canvas.init(800, 200, "IterationLab")
  options = @@viewOptions.merge(userOptions)
  
  amax = a.max
  rects = []
  a.each_with_index do |val, i| 
    rx = options[:x0] + i * options[:dx]
    y = Float(val)
    dy = options[:y1] - options[:y0] - options[:ymin]     # height of tallest bar
    ry = options[:y1] - options[:ymin] - (y/amax)*dy      # height of this bar 
    rects << Canvas::Rectangle.new( rx, ry, rx + options[:dx], options[:y1], :fill => options[:array_fill], :outline => options[:canvas_fill] ) 
  end
  bar = 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, bar, ['#000080','#BADFEB'], [], options)
  return true
end