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 



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

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 



75
76
77
78
 
# File 'lib/lazy_priority_queue.rb', line 75

def delete element
  change_priority element, @top_condition
  dequeue
end

#dequeue ⇒ Object Also known as: pop 



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

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) 


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

def empty?; @references.empty? end

#enqueue(element, key) ⇒ Object Also known as: push, insert 



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 



47
48
49
 
# File 'lib/lazy_priority_queue.rb', line 47

def peek
  @top and @top.element
end

#size ⇒ Object Also known as: length 



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

def size; @references.size end