############################################################################
#
#       File:     pqueue.icn
#
#       Subject:  Procedures for manipulating priority queues
#
#       Authors:  William S. Evans and Gregg M. Townsend
#
#       Date:     May 3, 2001
#
############################################################################
#
#   This file is in the public domain.
#
############################################################################
#
#       These procedures manipulate priority queues.
#
#	pq(L)		returns a priority queue containing the elements
#			in L.  L is a list (or table or set) of pqelem
#			records, each containing a data and priority field.
#			If L is &null, pq() returns an empty priority queue.
#
#	pqget(Q)	returns and removes the highest priority element
#			from Q.  Q is a priority queue returned by pq().
#
#	pqput(Q, e)	adds element e (a pqelem record) to Q.
#
#	pqgen(Q)	generates the elements in Q in priority order.
#
#	pqelem(d, p)	constructs a record with data d and priority p.
#
############################################################################
#
#	Priority queues are implemented as heaps.  Heaps are
#	implemented as lists in the usual fashion.
#
############################################################################

record pqelem (
   data,		# element's data
   priority		# element's priority
   )

procedure pq(L)				#: create priority queue
   local Q, i, e

   /L := list()
   Q := list()
   every e := !L do
      put(Q, pqelem(e.data, numeric(e.priority) | runerr(102, e.priority)))
   every i := *Q / 2 to 1 by -1 do
      pq__down(Q, i)
   return Q
end

procedure pqget(Q)			#: remove first priority queue element
   local e

   e := get(Q) | fail
   push(Q, pull(Q))
   pq__down(Q, 1)
   return e
end

procedure pqgen(Q)			#: generate priority queue elements
   local q, e

   q := copy(Q)
   while e := copy(pqget(q)) do
      suspend e
end

procedure pqput(Q, e)			#: insert priority queue element
   put(Q, pqelem(e.data, numeric(e.priority) | runerr(102, e.priority)))
   pq__up(Q, *Q)
   return Q
end

# Procedures named with a "pq__" prefix are not
# intended for access outside this file.

procedure pq__down(Q, i)
   local left, right, largest

   left := i * 2
   right := left + 1

   if Q[left].priority > Q[i].priority then largest := left
   else largest := i
   if Q[right].priority > Q[largest].priority then largest := right
   if largest ~= i then {
      Q[i] :=: Q[largest]
      pq__down(Q, largest)
      }
   return
end

procedure pq__up(Q, i)
   local parent

   parent := i / 2
   if Q[i].priority > Q[parent].priority then {
      Q[i] :=: Q[parent]
      pq__up(Q, parent)
      }
   return
end