class RingBuffer
Attributes
capacity[RW]
length[RW]
start_idx[RW]
store[RW]
Public Class Methods
new(size = 8)
click to toggle source
# File lib/simms_structures/ring_buffer.rb, line 7 def initialize(size = 8) @store = StaticArray.new(size) @start_idx = 0 @length = 0 @capacity = size end
Public Instance Methods
[](index)
click to toggle source
O(1)
# File lib/simms_structures/ring_buffer.rb, line 19 def [](index) check_index(index) @store[relative_index(index)] end
[]=(index, value)
click to toggle source
O(1)
# File lib/simms_structures/ring_buffer.rb, line 25 def []=(index, value) check_index(index) @store[relative_index(index)] = value end
pop()
click to toggle source
O(1)
# File lib/simms_structures/ring_buffer.rb, line 31 def pop check_index(0) @length -= 1 @store[(@start_idx + @length) % @capacity] end
push(value)
click to toggle source
O(1) ammortized
# File lib/simms_structures/ring_buffer.rb, line 38 def push(value) resize! if @length == @capacity @store[(@start_idx + @length) % @capacity] = value @length += 1 nil # debugger end
relative_index(index)
click to toggle source
# File lib/simms_structures/ring_buffer.rb, line 14 def relative_index(index) (@start_idx + index) % @capacity end
shift()
click to toggle source
O(1)
# File lib/simms_structures/ring_buffer.rb, line 47 def shift check_index(0) value = self[0] @start_idx = (@start_idx + 1) % @capacity @length -= 1 value end
unshift(value)
click to toggle source
O(1) ammortized
# File lib/simms_structures/ring_buffer.rb, line 56 def unshift(value) resize! if @length == @capacity @start_idx = (@start_idx - 1) % @capacity @store[@start_idx] = value @length += 1 end
Protected Instance Methods
check_index(index)
click to toggle source
# File lib/simms_structures/ring_buffer.rb, line 67 def check_index(index) raise 'index out of bounds' if index >= @length end
resize!()
click to toggle source
# File lib/simms_structures/ring_buffer.rb, line 71 def resize! new_capacity = @capacity * 2 new_store = StaticArray.new(new_capacity) @length.times { |idx| new_store[idx] = @store[relative_index(idx)]} @store = new_store @capacity = new_capacity @start_idx = 0 end