class LazyPriorityQueue

# File lib/lazy_priority_queue.rb, line 9
def initialize(top_condition, &heap_property)
  @top = nil
  @roots = []
  @references = {}
  @top_condition = top_condition
  @heap_property = heap_property
end

# File lib/lazy_priority_queue.rb, line 33
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

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

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

  element
end

# File lib/lazy_priority_queue.rb, line 80
def delete(element)
  change_priority element, @top_condition
  dequeue
end

# File lib/lazy_priority_queue.rb, line 56
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

# File lib/lazy_priority_queue.rb, line 85
def empty?
  @references.empty?
end

# File lib/lazy_priority_queue.rb, line 17
def enqueue(element, key)
  if @references[element]
    raise 'The provided element already is in the queue.'
  end

  node = Node.new element, key, 0

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

  element
end

# File lib/lazy_priority_queue.rb, line 52
def peek
  @top && @top.element
end

# File lib/lazy_priority_queue.rb, line 89
def size
  @references.size
end