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