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.



326
327
328
329
330
331
332
333
334
335
336
337
 
# File 'lib/rubylabs.rb', line 326

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



398
399
400
 
# File 'lib/rubylabs.rb', line 398

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.



374
375
376
377
378
379
 
# File 'lib/rubylabs.rb', line 374

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



384
385
386
387
388
389
 
# File 'lib/rubylabs.rb', line 384

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



305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/rubylabs.rb', line 305

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



353
354
355
356
357
358
 
# File 'lib/rubylabs.rb', line 353

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

#sort ⇒ Object 



280
281
282
283
284
 
# File 'lib/rubylabs.rb', line 280

def sort
  tmp = self.clone
  tmp.sort!
  return tmp
end

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

Exchange the locations of rectangles i and j



362
363
364
365
366
367
368
369
 
# File 'lib/rubylabs.rb', line 362

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



342
343
344
345
346
347
348
349
 
# File 'lib/rubylabs.rb', line 342

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