mootoh (owner)

Revisions

gist: 223440 Download_button fork
public
Description:
Introduction to Algorithms 10.1.
Public Clone URL: git://gist.github.com/223440.git
Embed All Files: show embed
queue.rb #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
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

class Queue                                                         
   def initialize(n = 6)                                            
      @s = Array.new(n, nil)                                        
      @tail = @head = 0                                             
   end                                                              
                                                                    
   def inc(x)                                                       
      (x + 1) % @s.size                                             
   end                                                              
                                                                    
   def empty?                                                       
      @tail == @head                                                
   end                                                              
 
   def full?
      @head == inc(@tail)
   end
 
   def enqueue(x)
      raise 'overflow' if full?
      @s[@tail] = x
      @tail = inc(@tail)
   end
 
   def dequeue
      raise "underflow" if empty?
      ret = @s[@head]
      @head = inc(@head)
      ret
   end
end
 
class QueueTest < Test::Unit::TestCase
   def setup
      @queue = Queue.new
   end
 
   def test_empty
      assert(@queue.empty?)
      assert(!@queue.full?)
   end
 
   def test_enqueue
      5.times {|x| @queue.enqueue x}
      assert_raise(RuntimeError) { @queue.enqueue 6}
   end
 
   def test_dequeue
      assert_raise(RuntimeError) { @queue.dequeue }
 
      5.times {|x| @queue.enqueue x}
      5.times {|x|
         assert_equal(x, @queue.dequeue)
      }
   end
end