Class: DynamicArray

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

Direct Known Subclasses

DataStruct::DynamicArray

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ DynamicArray

Returns a new instance of DynamicArray.



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

def initialize(size)
  @num_items = 0
  @size = size
  @start = 0
  @store = Array.new(size)
end

Instance Attribute Details

#num_items ⇒ Object (readonly)

Returns the value of attribute num_items.



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

def num_items
  @num_items
end

#size ⇒ Object

dynamic array with ring buffer



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

def size
  @size
end

#start ⇒ Object

dynamic array with ring buffer



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

def start
  @start
end

#store ⇒ Object

dynamic array with ring buffer



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

def store
  @store
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  # will refactor to check num_items because I'm not testing that variable right now
  return @store.empty?
end

#insert(val, idx) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/dynamic_array.rb', line 18

def insert(val, idx)
  # O(n) because you need to copy
  idx += @start
  validate_idx(idx)
  resize! if @num_items == @size

  queue = [val]
  count = 0 # in case @store is full, then @store[idx] will never be nil, 
            # break you move all the way around

  until queue.empty? || count > @num_items
    count += 1
    queue.push(@store[idx]) unless @store[idx].nil?
    @store[idx] = queue.shift
    idx += 1
  end
  @num_items += 1

  @store
end

#pop ⇒ Object 



39
40
41
42
43
44
45
46
 
# File 'lib/dynamic_array.rb', line 39

def pop
  # O(1)
  @num_items -= 1
  idx = @start + @num_items
  val, @store[idx] = @store[idx], nil

  val
end

#push(val) ⇒ Object 



48
49
50
51
52
53
54
55
56
 
# File 'lib/dynamic_array.rb', line 48

def push(val)
  # O(1) ammortized; not called on every push
  resize! if @num_items == @size
  idx = (@start + @num_items) % @size
  @num_items += 1
  @store[idx] = val

  @store
end

#shift ⇒ Object

@store end



75
76
77
78
79
80
81
82
 
# File 'lib/dynamic_array.rb', line 75

def shift
  # O(1)
  val, @store[@start] = @store[@start], nil
  @num_items -= 1
  @start += 1

  val
end

#unshift(val) ⇒ Object 



84
85
86
87
88
89
90
91
92
93
 
# File 'lib/dynamic_array.rb', line 84

def unshift(val)
  # O(1) ammortized; not called on every unshift
  resize! if @num_items == @size
  @start -= 1
  idx = (@start) % @size
  @num_items += 1
  @store[idx] = val

  @store
end