Created
June 26, 2023 19:13
-
-
Save jasonyork/262fcab37f1b9146e125377d55ef7b0d to your computer and use it in GitHub Desktop.
Ring Buffer Example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class RingBuffer | |
attr_accessor :head, :tail, :items, :size, :count | |
def initialize(size:) | |
@size = size | |
@head = @tail = @count = 0 | |
@items = [] | |
end | |
def push(item) | |
advance_head | |
increment_count | |
@items[head] = item | |
self | |
end | |
def pop | |
return nil if empty? | |
result = items[tail] | |
advance_tail | |
decrement_count | |
result | |
end | |
def empty? | |
count.zero? | |
end | |
def full? | |
count == size | |
end | |
private | |
def advance_head | |
return if empty? | |
@head = @head == size - 1 ? 0 : @head += 1 | |
advance_tail if full? | |
end | |
def advance_tail | |
@tail = @tail == size - 1 ? 0 : @tail += 1 | |
end | |
def decrement_count | |
@count = count - 1 | |
end | |
def increment_count | |
@count = count + 1 | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'rspec' | |
require_relative './ring_buffer' | |
RSpec.describe RingBuffer do | |
let(:size) { 3 } | |
subject(:buffer) { RingBuffer.new(size:) } | |
it 'should have a size' do | |
expect(buffer.size).to eq(3) | |
end | |
describe "#push" do | |
it 'can push an item' do | |
buffer.push(1) | |
expect(buffer.items).to eq [1] | |
end | |
it 'can push two items' do | |
buffer.push(1).push(2) | |
expect(buffer.items).to eq [1, 2] | |
end | |
it 'can push three items' do | |
buffer.push(1).push(2).push(3) | |
expect(buffer.items).to eq [1, 2, 3] | |
end | |
it 'can push four items and wrap' do | |
buffer.push(1).push(2).push(3).push(4) | |
expect(buffer.items).to eq [4, 2, 3] | |
end | |
end | |
describe "#pop" do | |
it 'returns nil when there are no items' do | |
expect(buffer.pop).to be_nil | |
end | |
it 'can push and pop the same item' do | |
expect(buffer.push(1).pop).to eq(1) | |
end | |
it 'returns the oldest of two items' do | |
expect(buffer.push(1).push(2).pop).to eq(1) | |
end | |
it 'returns the oldest of three items' do | |
expect(buffer.push(1).push(2).push(3).pop).to eq(1) | |
end | |
it 'returns the oldest of four items' do | |
expect(buffer.push(1).push(2).push(3).push(4).pop).to eq(2) | |
end | |
it 'can pop all of two items' do | |
expect(buffer.push(1).push(2).pop).to eq(1) | |
expect(buffer.pop).to eq(2) | |
end | |
it 'can pop all of three items' do | |
expect(buffer.push(1).push(2).push(3).pop).to eq(1) | |
expect(buffer.pop).to eq(2) | |
expect(buffer.pop).to eq(3) | |
end | |
it 'returns nil when all items are popped' do | |
buffer.push(1).push(2).push(3) | |
buffer.pop | |
buffer.pop | |
buffer.pop | |
expect(buffer.pop).to eq(nil) | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment