Class: Mayak::Collections::PriorityQueue

Inherits:
Object
  • Object
show all
Extended by:
T::Generic, T::Sig
Defined in:
lib/mayak/collections/priority_queue.rb

Constant Summary collapse

Element = 
type_member
Priority = 
type_member

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&compare) ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



17
18
19
20
21
 
# File 'lib/mayak/collections/priority_queue.rb', line 17

def initialize(&compare)
  @array   = T.let([], T::Array[T.nilable([Element, Priority])])
  @compare = T.let(compare, T.proc.params(arg0: Priority, arg2: Priority).returns(T::Boolean))
  @size    = T.let(0, Integer)
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



14
15
16
 
# File 'lib/mayak/collections/priority_queue.rb', line 14

def size
  @size
end

Instance Method Details

#clear ⇒ Object 



54
55
56
57
 
# File 'lib/mayak/collections/priority_queue.rb', line 54

def clear
  @array = []
  @size = 0
end

#dequeue ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/mayak/collections/priority_queue.rb', line 31

def dequeue
  element_index = 0
  result = @array[element_index]

  if @size > 1
    @size -= 1
    @array[element_index] = @array[@size]
    sift_down(element_index)
  else
    @size = 0
  end

  @array[@size] = nil

  result
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


65
66
67
 
# File 'lib/mayak/collections/priority_queue.rb', line 65

def empty?
  size == 0
end

#enqueue(element, priority) ⇒ Object 



24
25
26
27
28
 
# File 'lib/mayak/collections/priority_queue.rb', line 24

def enqueue(element, priority)
  @array[@size] = [element, priority]
  @size += 1
  sift_up(size - 1)
end

#peak ⇒ Object 



49
50
51
 
# File 'lib/mayak/collections/priority_queue.rb', line 49

def peak
  @array.first
end

#to_a ⇒ Object 



60
61
62
 
# File 'lib/mayak/collections/priority_queue.rb', line 60

def to_a
  @array.compact
end