Class: RubyLabs::TestArray

Inherits:
Array
  • Object
show all
Defined in:
lib/rubylabs.rb

Overview

TestArray

A TestArray is an array of random values that can be used to test searching and sorting algorithms.

A method named random will return a random element to use as a search target. If a is a TestArray object, 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.

#–

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.

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

Constant Summary collapse

@@sources = 
{
  :cars => "#{data}/cars.txt",
  :colors => "#{data}/colors.txt",
  :elements => "#{data}/elements.txt",
  :fruits => "#{data}/fruit.txt",
  :fish => "#{data}/fish.txt",
  :languages => "#{data}/languages.txt",
  :words => "#{data}/wordlist.txt",
}

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size, src = nil) ⇒ TestArray

Create a new TestArray of size n containing items of the specified type. If a type is not supplied, create an array of integers. Types are identified by symbols, e.g. :cars tells the constructor to return an array of car names (see TestArray.sources). If a type is specified, the symbol :all can be given instead of an array size, in which case the constructor returns all items of that type.

Examples:

>> TestArray.new(5)
=> [3, 28, 48, 64, 4]
>> TestArray.new(5, :cars)
=> ["lamborghini", "lincoln", "chrysler", "toyota", "rolls-royce"]    
>> TestArray.new(:all, :colors)
=> ["almond", "antique white", ... "yellow green"]

:call-seq:

TestArray.new(n, type) => Array



231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
 
# File 'lib/rubylabs.rb', line 231

def initialize(size, src = nil)
  
  if src.nil? || src.class == Fixnum
    raise "TestArray: array size must be an integer" unless size.class == Fixnum
    if src.nil?
      @max = (size < 50) ? 100 : (10 * size)
    else
      @max = src
      raise "TestArray: max must be at least 2x larger than size" unless @max >= 2 * size
    end
  else
    raise "TestArray: array size must be an integer or :all" unless size.class == Fixnum || size == :all
  end
   
  @h = Hash.new
  
  # if @max is defined make an array of integers, otherwise src defines the type of data;
  # size might be :all, in which case return the whole file, and set @all to true so random
  # doesn't try to make a random value not in the array.
  
  if @max
    while @h.size < size
      @h[ rand( @max ) ] = 1    
    end
  else
    fn = @@sources[src] or raise "TestArray: undefined source: #{src}"
    @words = File.open(fn).readlines
    if size != :all
      max = @words.length
      raise "TestArray: size must be less than #{max} for an array of #{src}" unless size < max
      while @h.size < size
        @h[ @words[ rand(max) ].chomp ] = 1
      end
    end
  end
      
  if size == :all
    self.concat @words.map { |s| s.chomp! }
    @all = true
  else
    self.concat @h.keys
    for i in 0..length-2
      r = rand(length-i) + i      # i <= r < length
      self[i],self[r] = self[r],self[i]
    end
  end
  
end

Class Method Details

.draw_bars(a, options) ⇒ Object

Visualization methods called by searching and sorting algorithms in IterationLab and RecursionLab.



319
320
321
322
323
324
325
326
327
328
329
330
 
# File 'lib/rubylabs.rb', line 319

def TestArray.draw_bars(a, options)
  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
  return rects    
end

.sources ⇒ Object

Return a list of types of items that can be passed as arguments to TestArray.new

:call-seq:

TestArray.sources() => Array



391
392
393
 
# File 'lib/rubylabs.rb', line 391

def TestArray.sources
  return @@sources.keys.sort { |a,b| a.to_s <=> b.to_s }
end

Instance Method Details

#move_down(rect, groupstart, group, options) ⇒ Object

Move a bar down to the auxilliary area below the progress bar. Argument ‘groupstart’ is the index of the first bar in the area, group is the current set of bars in the area.



367
368
369
370
371
372
 
# File 'lib/rubylabs.rb', line 367

def move_down(rect, groupstart, group, options)
  x0, y0, x1, y1 = rect.coords
  newx = options[:x0] + (groupstart + group.length) * options[:dx]
  Canvas.move(rect, newx - x0, options[:gdy])
  group << rect
end

#move_up(rects, groupstart, group, options) ⇒ Object

Move all the bars in the auxilliary area straight up so they fill the space in the main array, update the array of rectangles so they correspond to the new order of bars



377
378
379
380
381
382
 
# File 'lib/rubylabs.rb', line 377

def move_up(rects, groupstart, group, options)
  group.each do |rect|
    Canvas.move(rect, 0, -options[:gdy])
  end
  rects[groupstart ... (groupstart + group.length)] = group
end

#random(outcome) ⇒ Object

Return a value that is guaranteed to be in the array or not in the array, depending on the value of outcome. Pass :success to get a random value in the array, or pass :fail to get an item of the same type as the items in the array but which is not itself in the array. Call a.random(:fail) to get a value that will cause a search algorithm to do the maximum number of comparisons.

Example:

>> a = TestArray.new(10).sort
=> [13, 23, 24, 26, 47, 49, 86, 88, 92, 95]
>> x = a.random(:fail)
=> 22
>> search(a, x)
=> nil

:call-seq:

a.random(outcome) => Object



298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/rubylabs.rb', line 298

def random(outcome)
  if outcome == :success
    return self[ rand(self.length) ]
  elsif outcome == :fail
    raise "TestArray#random: array is universal set" if @all
    loop do
      if @max
        x = rand( @max )
      else
        x = @words[ rand( @words.length ) ].chomp
      end
      return x if @h[x] == nil
    end
  else
    return nil
  end
end

#set_region(i, j, bar, options) ⇒ Object

Set the left and right ends of the progress bar



346
347
348
349
350
351
 
# File 'lib/rubylabs.rb', line 346

def set_region(i, j, bar, options)
  x0, y0, x1, y1 = bar.coords
  x0 = options[:x0] + i * options[:dx]
  x1 = options[:x0] + j * options[:dx]
  bar.coords = [x0, y0, x1, y1]
end

#swap_bars(rects, i, j, options) ⇒ Object

Exchange the locations of rectangles i and j



355
356
357
358
359
360
361
362
 
# File 'lib/rubylabs.rb', line 355

def swap_bars(rects, i, j, options)
  dist = (j - i) * options[:dx]
  ri = rects[i]
  rj = rects[j]
  Canvas.move(ri, dist, 0)
  Canvas.move(rj, -dist, 0)
  rects[i], rects[j] = rects[j], rects[i]
end

#touch(rect, history, palette) ⇒ Object

Add rectangle i to the history list, then set the color of each bar in the list to the corresponding palette color



335
336
337
338
339
340
341
342
 
# File 'lib/rubylabs.rb', line 335

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