Skip to content

Instantly share code, notes, and snippets.

@trobrock
Created May 23, 2012 15:19
Show Gist options
  • Save trobrock/2775846 to your computer and use it in GitHub Desktop.
Save trobrock/2775846 to your computer and use it in GitHub Desktop.
Queue with an expanding buffer
class Queue
attr_reader :elements
def initialize
@elements = Buffer.new
end
def push(element)
@elements << element
end
def pop
@elements.pop
end
def peek
@elements.peek
end
def size
@elements.size
end
def empty?
@elements.empty?
end
end
class Buffer < Array [3/1847]
def initialize
@current = 0
@insert = 0
super
end
def <<(val)
update_insert_index!
self[@insert] = val
@insert += 1
end
def pop
update_current_index!
item = self[@current]
self[@current] = nil
@current += 1
item
end
def peek
self[current_index]
end
def size
self.compact.size
end
def empty?
self.compact.empty?
end
private
def update_current_index!
@current = current_index
end
def current_index
return 0 if @current == self.to_a.size
@current
end
def update_insert_index!
if @current > 0
@insert = 0 if @insert == self.to_a.size
while !self[@insert].nil?
if @insert == @current
new_array = Array.new(self.to_a.size)
self.insert(@insert, *new_array)
@current += new_array.size
else
@insert += 1
end
end
end
end
end
require File.join(File.dirname(__FILE__), 'queue')
describe Queue do
before(:each) do
@queue = Queue.new
end
it "should be able to push things on the queue" do
@queue.push(1)
@queue.size.should == 1
end
it "should pop of the first item on the queue" do
@queue.push(1)
@queue.push(2)
@queue.pop.should == 1
@queue.size.should == 1
end
it "should be able to get the next element without removing it" do
@queue.push(1)
@queue.peek.should == 1
@queue.size.should == 1
end
it "should know if it's empty" do
@queue.should be_empty
@queue.push(1)
@queue.pop
@queue.should be_empty
@queue.push(1)
@queue.should_not be_empty
end
it "should not adjust the length of the internal array if not needed" do
@queue.push(1)
@queue.push(2)
@queue.push(3)
@queue.push(4)
@queue.push(5)
@queue.elements.size.should == 5
@queue.pop.should == 1
@queue.pop.should == 2
@queue.elements.size.should == 3
@queue.push(6)
@queue.push(7)
@queue.push(8)
@queue.elements.size.should == 6
@queue.pop.should == 3
@queue.pop.should == 4
@queue.pop.should == 5
@queue.pop.should == 6
@queue.pop.should == 7
@queue.pop.should == 8
@queue.push(9)
@queue.pop.should == 9
@queue.elements.size.should == 0
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment