############################################################################
#
#       File:     pqueue.icn
#
#       Subject:  Class MaxPQueue, implementing a max-priority queue.
#                 Also see Steve Wampler's more general priority queue.
#
#       Authors:  Kostas Oikonomou
#                 Based on pqueue.icn in the IPL, by William S. Evans and
#                 Gregg M. Townsend.
#
#       Date:     September 15, 2004
#
############################################################################
#
#   This file is in the public domain.
#
############################################################################
#
#       Methods:
#
#	construct(S)	returns a max-priority queue containing the elements
#			in  the structure (list, table, or set) S of "elem"
#                       records, each containing a "data" and a numeric
#                       "priority" field.
#
#	get()	        removes and returns the highest priority element
#			from the priority queue.
#
#	put(e)	        adds element e (a "elem" record) to the queue.
#
#	gen()	        generates (non-destructively) the elements of the queue
#                       in order, highest priority first.
#
#       len()           returns the number of elements in the queue.
#       maxlen()        returns the maximum length reached by the queue during
#                       its lifetime.
#
#	elem(d, p)	constructs a record with data d and priority p.
#
#
############################################################################
#
#	The priority queue is implemented as a max-heap.  The heap is
#	implemented by a list in the usual fashion.
#
############################################################################

class MaxPQueue(Q, elem, L)

  # Create the queue from a list, table, or set of "elem"
  method construct(S)	
    local i
    /S := list()
    Q := list()
    every self.put(!S)
    every down(i := *Q/2 to 1 by -1)
    L := *Q
    return
  end

  # Queue length and maximum length
  method len()
    return *Q
  end
  method maxlen()
    return L
  end

  # Remove first element
  method get()
    local e
    e := ::get(Q) | fail  # this is Icon's ordinary "get"
    push(Q, pull(Q))
    down(1)
    L <:= *Q
    return e
  end

  # Insert element
  method put(e)
    ::put(Q, e)           # this is Icon's ordinary "put"
    up(*Q)
    L <:= *Q
    return
  end

  # Generate the elements
  method gen()	
    local q, e
    q := copy(Q)
    while e := copy(self.get(q)) do
      suspend e
  end


  method down(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]
      down(largest)
    }
    return
  end

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


  initially
    elem := constructor("elem", "data", "priority")
    Q := []
    L := 0

end