Class: DynamicArray

Inherits:
Object
  • Object
show all
Defined in:
lib/simms_structures/dynamic_array.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size = 8) ⇒ DynamicArray

Returns a new instance of DynamicArray.



6
7
8
9
10
 
# File 'lib/simms_structures/dynamic_array.rb', line 6

def initialize(size = 8)
  @store = StaticArray.new(size)
  @length = 0
  @capacity = size
end

Instance Attribute Details

#length ⇒ Object

Returns the value of attribute length.



4
5
6
 
# File 'lib/simms_structures/dynamic_array.rb', line 4

def length
  @length
end

Instance Method Details

#[](index) ⇒ Object

O(1)



13
14
15
16
 
# File 'lib/simms_structures/dynamic_array.rb', line 13

def [](index)
  raise 'index out of bounds' if index >= (@length)
  @store[index]
end

#[]=(index, value) ⇒ Object

O(1)



19
20
21
 
# File 'lib/simms_structures/dynamic_array.rb', line 19

def []=(index, value)
  @store[index] = value
end

#pop ⇒ Object

O(1)



24
25
26
27
28
29
 
# 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) ⇒ Object

O(1) ammortized; O(n) worst case. Variable because of the possible resize.



33
34
35
36
37
 
# File 'lib/simms_structures/dynamic_array.rb', line 33

def push(value)
  resize! if @length == @capacity
  self[@length] = value
  @length += 1
end

#shift ⇒ Object

O(n): has to shift over all the elements.



40
41
42
43
44
45
46
 
# 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) ⇒ Object

O(n): has to shift over all the elements.



49
50
51
52
53
54
55
56
57
 
# 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