Module: RubyLabs::LinearDSLab

Defined in:
lib/lineardslab.rb

Defined Under Namespace

Classes: Queue, QueueView, Stack, StackView

Instance Method Summary collapse

Instance Method Details

#brackets(a, left, right = a.length-1, mid = nil) ⇒ Object

This brackets method is taken from RubyLabs. A helper method that can be called from a probe to display the contents of an array during a search or sort. See also IterationLab#brackets.

The version implemented in this module accepts an additional argument, which specifies the location of the right bracket in the output string (if this argument is not give the right bracket is inserted at the end).

An optional third argument, intended for experiments with binary search, tells the method where to insert an asterisk before an item.

Examples:

>> a = TestArray.new(15)
=> [22, 3, 70, 74, 35, 0, 82, 64, 90, 54, 88, 26, 75, 18, 17]
>> puts brackets(a, 8, 10)
 22  3  70  74  35  0  82  64 [90  54  88] 26  75  18  17
=> nil
>> puts brackets(a, 8, 10, 9)
 22  3  70  74  35  0  82  64 [90 *54  88] 26  75  18  17
=> nil



382
383
384
385
386
387
388
389
390
391
392
393
 
# File 'lib/lineardslab.rb', line 382

def brackets(a, left, right = a.length-1, mid = nil)
  left = 0 if left < 0
  right = a.length-1 if right >= a.length
  pre = left == 0 ? "" : " " + a.slice(0..(left-1)).join("  ") + " "
  inner = left <= right ? a.slice(left..right).join("  ") : ""
  post = " " + a.slice(right+1..-1).join("  ")
  res = pre + "[" + inner + "]" + post
  if mid && left < right
    res[res.index(a[mid].to_s)-1] = ?*
  end
  return res
end

#check_braces(t) ⇒ Object

checks whether an array contains balanced braces using stack :begin :check_braces



270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
 
# File 'lib/lineardslab.rb', line 270

def check_braces(t)
  s = Stack.new
  balancedSoFar = true
  i = 0
  while i < t.count and balancedSoFar
    if t[i] == "{"
      s.push(t[i])
    elsif t[i] == "}"
      if s.count > 0
        s.pop
      else
        balancedSoFar = false
      end
    end		
    i += 1
  end
  return (balancedSoFar and s.count==0)
end

#fibonacci(n) ⇒ Object

:begin :fibonacci



311
312
313
314
315
316
317
318
319
 
# File 'lib/lineardslab.rb', line 311

def fibonacci(n)
  if n == 0
    return 0
  elsif n == 1
    return 1
  else
    return fibonacci(n-1) + fibonacci(n-2)
  end
end

#fibonacci_stack(n) ⇒ Object

:begin :fibonacci_stack



291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
 
# File 'lib/lineardslab.rb', line 291

def fibonacci_stack(n)
  s = Stack.new
  s.push(n)
  result = 0
  while s.count > 0
    current = s.pop
    if current == 0
      result += 0
    elsif current == 1
      result += 1
    else
      s.push(current - 2)
      s.push(current - 1)
    end
  end
  return result
end

#is_palindrome(v) ⇒ Object

checks whether an array is a palindrome using both stack and queue :begin :is_palindrome



253
254
255
256
257
258
259
260
261
262
263
264
265
 
# File 'lib/lineardslab.rb', line 253

def is_palindrome(v)
	t = v.split(//)
	q = Queue.new
	s = Stack.new
	t.each { |x| q.enqueue(x) }			
	t.each { |x| s.push(x) }			
	while s.count > 0
		left = q.dequeue
		right = s.pop			
		return false if(left != right)
	end
	return true
end

#rbsearch(a, k, lower = -1,, upper = a.length) ⇒ Object

recursive version of binary search (from Conery’s book) :begin :rbsearch



324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/lineardslab.rb', line 324

def rbsearch(a, k, lower = -1, upper = a.length)
  mid = (lower + upper)/2
  return nil if upper == lower + 1
  return mid if k == a[mid]
   
  if k < a[mid]
    return rbsearch(a, k, lower, mid)
  else
  	return rbsearch(a, k, mid, upper)
  end
end

#rbsearch_stack(a, k, lower = -1,, upper = a.length) ⇒ Object

non-recursive, stack-based version of binary searh :begin :rbsearch_stack



339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
 
# File 'lib/lineardslab.rb', line 339

def rbsearch_stack(a, k, lower = -1, upper = a.length)
  s = Stack.new
  s.push(lower)
  s.push(upper)  
  while s.count > 0
  	upper = s.pop
  	lower = s.pop  	
  	mid = (lower + upper)/ 2
  	return nil if upper == lower + 1
  	return mid if k == a[mid]  	
  	if k < a[mid]
  		s.push(lower)
  		s.push(mid)
  	else
  		s.push(mid)
  		s.push(upper)
  	end
  end
end

#view_queue(q, *peek) ⇒ Object

Generates the view for a queue visualization



125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/lineardslab.rb', line 125

def view_queue(q, *peek)
	# Initializes the canvas and font type
	Canvas.init(400, 400, "Queue")
	Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 11)
	
	queue = q.items

	cells = []
	values = []
	
	# Define starting height of first rectangle
	y0 = 50
	Canvas::Text.new("Queue Lab", 10, 1, {:font => :bucketfont})
	Canvas::Line.new(0, 20, 400, 20, :fill => :gray, :width => 1)
	
	# If generating a peek view, color last rectangle red, and place it on the right
	if peek[0] && queue[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'red'
		y1 = y0+3
		values << Canvas::Text.new(queue[0], 65, y1, {:font => :bucketfont})
		Canvas::Text.new("<- Head of the Queue", 200, y1, {:font => :bucketfont})
		
	# Else place a normal rectangle
	elsif queue[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'grey'
		y1 = y0+3
		values << Canvas::Text.new(queue[0], 65, y1, {:font => :bucketfont})
		Canvas::Text.new("<- Head of the Queue", 200, y1, {:font => :bucketfont})
	end
	
	iterations = queue.length-1
	
	# Iterate as many times as the number of elements in the array minus one. The first element is already handled above.
	iterations.times do |i|
		y0 += 25
		# Draw a rectangle and store a reference to this rectangle in the cells array
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[i+1].fill = 'grey'
		# Draw the text value and store a reference to this value in the values array
		values << Canvas::Text.new(queue[i+1], 65, y0+3, {:font => :bucketfont})
	end
	
	if queue.length-1 > 0
		Canvas::Text.new("<- Tail of the Queue", 200, y0+3,{:font => :bucketfont})
	end	
		
	# Store the properties of this drawing as a Struct object
	q.drawing = QueueView.new(cells, values)
	return true
end

#view_stack(s, *peek) ⇒ Object

Generates the view for a stack visualization



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/lineardslab.rb', line 13

def view_stack(s, *peek)
	# Initializes the canvas and font type
	Canvas.init(400, 400, "Stack")
	Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 11)
	
	stack = s.items

	cells = []
	values = []
	
	# Define starting height of first rectangle
	y0 = 50
	Canvas::Text.new("Stack Lab", 10, 1, {:font => :bucketfont})
	Canvas::Line.new(0, 20, 400, 20, :fill => :gray, :width => 1)
	
	# If generating a peek view, color first rectangle red, and place it on the right
	if peek[0] && stack[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'red'
		y1 = y0+3
		values << Canvas::Text.new(stack[0], 65, y0+3, {:font => :bucketfont})
		Canvas::Text.new("<- Top of the Stack", 200, y1, {:font => :bucketfont})
		
	# Else place a normal rectangle
	elsif stack[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'grey'
		y1 = y0+3
		values << Canvas::Text.new(stack[0], 65, y0+3, {:font => :bucketfont})
		Canvas::Text.new("<- Top of the Stack", 200, y1, {:font => :bucketfont})
	end
	
	iterations = stack.length-1
	
	# Iterate as many times as the number of elements in the array minus one. The first element is already handled above.
	iterations.times do |i|
		y0 += 25
		# Draw a rectangle and store a reference to this rectangle in the cells array
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[i+1].fill = 'grey'
		# Draw the text value and store a reference to this value in the values array
		values << Canvas::Text.new(stack[i+1], 65, y0+3, {:font => :bucketfont})
	end
	
	if stack.length-1 > 0
		Canvas::Text.new("<- Bottom of the Stack", 200, y0+3, {:font => :bucketfont})
	end	
		
	# Store the properties of this drawing as a Struct object
	s.drawing = StackView.new(cells, values)
	return true
end