Class: LazyPriorityQueue

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

Direct Known Subclasses

MaxPriorityQueue, MinPriorityQueue

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(top_condition, &heap_property) ⇒ LazyPriorityQueue

Returns a new instance of LazyPriorityQueue.



10
11
12
13
14
15
 
# File 'lib/lazy_priority_queue.rb', line 10

def initialize top_condition, &heap_property
  @roots = []
  @references = {}
  @top_condition = top_condition
  @heap_property = heap_property
end

Instance Method Details

#change_priority(element, new_key) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/lazy_priority_queue.rb', line 29

def change_priority element, new_key
  node = @references[element]

  raise 'Element provided is not in the queue.' unless node

  test_node = node.clone
  test_node.key = new_key
  raise 'Priority can only be changed to a more prioritary value.' unless @heap_property[test_node, node]

  node.key = new_key
  node = sift_up node
  @top = select(@top, node) unless node.parent

  element
end

#delete(element) ⇒ Object 



72
73
74
75
 
# File 'lib/lazy_priority_queue.rb', line 72

def delete element
  change_priority element, @top_condition
  dequeue
end

#dequeue ⇒ Object 



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/lazy_priority_queue.rb', line 49

def dequeue
  return unless @top

  element = @top.element
  @references.delete element
  @roots.delete @top

  child = @top.left_child

  while child
    next_child = child.right_sibling
    child.parent = nil
    child.right_sibling = nil
    @roots << child
    child = next_child
  end

  @roots = coalesce @roots
  @top = @roots.inject { |top, node| select top, node }

  element
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


77
 
# File 'lib/lazy_priority_queue.rb', line 77

def empty?; @references.empty? end

#enqueue(element, key) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/lazy_priority_queue.rb', line 17

def enqueue element, key
  raise 'The provided element already is in the queue.' if @references[element]

  node = Node.new element, key, 0

  @top = @top ? select(@top, node) : node
  @roots << node
  @references[element] = node

  element
end

#peek ⇒ Object 



45
46
47
 
# File 'lib/lazy_priority_queue.rb', line 45

def peek
  @top and @top.element
end

#size ⇒ Object 



78
 
# File 'lib/lazy_priority_queue.rb', line 78

def size; @references.size end