Priority queue

# title: Priority queue
# source: https://rosettacode.org/wiki/Priority_queue
# category: Rosetta Code
# difficulty: Medium
# summary: Model a simple highest-priority-first queue with sorted insertion over an array-backed store.
# tags: popular, data-structures, sorting, queues
# vibe: 0.2

def new_priority_queue
  {
    items: []
  }
end

def compare_entries(left, right)
  priority_gap = left[:priority] - right[:priority]
  if priority_gap != 0
    priority_gap
  elsif left[:value] < right[:value]
    -1
  elsif left[:value] > right[:value]
    1
  else
    0
  end
end

def enqueue(queue, priority, value)
  items = queue[:items] + [{ priority: priority, value: value }]
  queue[:items] = items.sort do |left, right|
    compare_entries(left, right)
  end
  queue
end

def peek(queue)
  items = queue[:items]
  if items.empty?
    nil
  else
    items[items.length - 1]
  end
end

def dequeue(queue)
  popped = queue[:items].pop
  queue[:items] = popped[:array]
  {
    queue: queue,
    item: popped[:popped]
  }
end

def run
  queue = new_priority_queue
  queue = enqueue(queue, 2, "write tests")
  queue = enqueue(queue, 5, "ship feature")
  queue = enqueue(queue, 3, "review docs")
  queue = enqueue(queue, 5, "answer support")

  top_before = peek(queue)
  first = dequeue(queue)
  queue = first[:queue]
  second = dequeue(queue)

  {
    peek_before_dequeue: top_before,
    first_out: first[:item],
    second_out: second[:item],
    remaining: second[:queue][:items]
  }
end