Class: DS::IndexedHeapStore

Inherits:
HeapStore show all
Defined in:
lib/ds/arrays/indexed_heap_store.rb

Overview

HeapStore with constant access to any element

Instance Method Summary collapse

Methods inherited from HeapStore

#empty?, #first, #length, #to_a

Constructor Details

#initialize(*args) ⇒ IndexedHeapStore

Returns a new instance of IndexedHeapStore.



7
8
9
10
11
12
13
14
15
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 7

def initialize(*args)
  args = args.to_a
  @map = {}
  args.each_with_index do |e, i|
    raise ArgumentError, 'Duplicates are not allowed' if @map[e.value]
    @map[e.value] = i + 1
  end
  @store = [nil] + args
end

Instance Method Details

#[]=(i, x) ⇒ Object 



23
24
25
26
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 23

def []=(i, x)
  @map[x.value] = i
  @store[i] = x
end

#get(x) ⇒ Object 



39
40
41
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 39

def get(x)
  self[index(x)] if index(x)
end

#index(x) ⇒ Object 



35
36
37
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 35

def index(x)
  @map[x]
end

#pop ⇒ Object 



17
18
19
20
21
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 17

def pop
  x = @store.pop
  @map.delete(x)
  x
end

#push(x) ⇒ Object 



28
29
30
31
32
33
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 28

def push(x)
  return if @map[x.value]
  last = @store.size
  @store.push x
  @map[x.value] = last
end

#swap(x, y) ⇒ Object 



43
44
45
46
47
 
# File 'lib/ds/arrays/indexed_heap_store.rb', line 43

def swap(x, y)
  super
  @map[self[x].value] = x
  @map[self[y].value] = y
end