class DynamicArray
Attributes
capacity[RW]
length[RW]
store[RW]
Public Class Methods
new(size = 8)
click to toggle source
# File lib/simms_structures/dynamic_array.rb, line 6 def initialize(size = 8) @store = StaticArray.new(size) @length = 0 @capacity = size end
Public Instance Methods
[](index)
click to toggle source
O(1)
# File lib/simms_structures/dynamic_array.rb, line 13 def [](index) raise 'index out of bounds' if index >= (@length) @store[index] end
[]=(index, value)
click to toggle source
O(1)
# File lib/simms_structures/dynamic_array.rb, line 19 def []=(index, value) @store[index] = value end
pop()
click to toggle source
O(1)
# File lib/simms_structures/dynamic_array.rb, line 24 def pop raise 'index out of bounds' if @length == 0 value = self[@length - 1] @length -= 1 value end
push(value)
click to toggle source
O(1) ammortized; O(n) worst case. Variable because of the possible resize.
# File lib/simms_structures/dynamic_array.rb, line 33 def push(value) resize! if @length == @capacity self[@length] = value @length += 1 end
shift()
click to toggle source
O(n): has to shift over all the elements.
# File lib/simms_structures/dynamic_array.rb, line 40 def shift raise 'index out of bounds' if @length == 0 1.upto(@length - 1) do |idx| self[idx - 1] = self[idx] end @length -= 1 end
unshift(value)
click to toggle source
O(n): has to shift over all the elements.
# File lib/simms_structures/dynamic_array.rb, line 49 def unshift(value) resize! if @length == @capacity (@length - 1).downto(0) do |idx| self[idx + 1] = self[idx] end if @length > 0 self[0] = value @length += 1 end
Protected Instance Methods
check_index(index)
click to toggle source
# File lib/simms_structures/dynamic_array.rb, line 63 def check_index(index) end
resize!()
click to toggle source
O(n): has to copy over all the elements to the new store.
# File lib/simms_structures/dynamic_array.rb, line 68 def resize! new_capacity = @capacity * 2 new_store = StaticArray.new(new_capacity) @length.times { |idx| new_store[idx] = self[idx] } @store = new_store @capacity = new_capacity end