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