-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathsolution.rb
More file actions
84 lines (71 loc) · 1.42 KB
/
solution.rb
File metadata and controls
84 lines (71 loc) · 1.42 KB
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
if __FILE__ == $0
exit 1 unless system "rspec #{__FILE__}"
end
require 'rspec'
class Queue
def initialize()
@data = []
@size = 0
@begin = 0
end
def empty
@size == 0
end
def pushBack(item)
if @size + 1 > @data.length
if @begin == 0
@data += [nil] * (2 * (@data.length + 1))
else
p1begin = @begin
p1len = @size - @begin
p2begin = 0
p2len = p1begin
@data = @data[p1begin, p1len] + @data[p2begin, p2len] + [nil] * (@data.length + 1)
end
@begin = 0
end
index = (@begin + @size) % @data.length
@data[index] = item
@size += 1
end
def popFront()
result = @data[@begin]
@begin = (@begin + 1) % @data.length
@size -= 1
result
end
end
describe "queue" do
it "works" do
q = Queue.new
q.empty.should == true
q.pushBack(1)
q.pushBack(2)
q.pushBack(3)
q.empty.should == false
q.popFront().should == 1
q.popFront().should == 2
q.popFront().should == 3
q.empty.should == true
q.pushBack(4)
q.empty.should == false
q.popFront().should == 4
q.empty.should == true
inv = 0
out = 0
(1..100).each do |i|
(0..i).each do |j|
q.pushBack(inv)
inv += 1
end
x = q.popFront()
x.should == out
out += 1
end
while !q.empty()
x = q.popFront()
x.should == out
out += 1
end
end
end