[@DEFINITION MODULE module;

(* Generic Priority Queue Template *)

(* ---------------------------------------------------------------------------

 * This template is expanded by the M 2 R 10? template engine utility. Expansion
 * can be invoked from within a compiling source file using the MAKE pragma:
 * <* MAKE = "m2te Priority Queue module:'Foo PQ?' component:'Foo Record?'" *>
 * IMPORT Foo PQ?;
 * ------------------------------------------------------------------------ *)

FROM Collections IMPORT Capacity, Status;

(* ---------------------------------------------------------------------------

 * Default queue size
 * ------------------------------------------------------------------------ *)

    defaultCapacity = 256;  (* 256 entries *)

(* ---------------------------------------------------------------------------

 * Maximum queue size
 * ------------------------------------------------------------------------ *)

    maximumCapacity = 1024*1024*1024;  (* more than 1 billion entries *)

(* ---------------------------------------------------------------------------

 * Synonyms for status codes
 * ------------------------------------------------------------------------ *)

    invalidQueue = invalidCollection;
    queueEmpty = collectionEmpty;
    queueFull = collectionFull;

(* ---------------------------------------------------------------------------

 * Opaque handle type:  module
 * ------------------------------------------------------------------------ *)

    module = OPAQUE;

    Value Type? = component;

(* ---------------------------------------------------------------------------

 * Priority Comparison Handler type
 * ---------------------------------------------------------------------------
 *
 * Priority comparison handlers  are called by  priority queues  whenever  the
 * priority  of a value needs to be determined.  The handler associated with a
 * priority queue is authoritative to determine priority for the queue.
 *
 * Handlers take two arguments of type Data Ptr? and return:
 *
 *  o  TRUE to indicate <value1> has higher than or equal priority to <value2>
 *  o  FALSE to indicate <value1> has lower priority than <value2> *)

    Comparison Handler? =
        PROCEDURE ( (* value1 *) Value Type?, (* value2 *) Value Type? ) : BOOLEAN ;

(* ---------------------------------------------------------------------------

 * function:  module.new ( size, handler, status )
 * ---------------------------------------------------------------------------
 *
 * Creates and returns a new priority queue object.  The capacity of the queue
 * depends on the value passed in for <size>.  If <size> is less than or equal
 * to defaultCapacity,  the capacity will be defaultCapacity.  If <size>
 * is greater than maximumCapacity or if memory could not be allocated then
 * no queue will be created  and NIL will be returned.  Otherwise the capacity
 * of the new queue will be equal to the value of <size>.
 *
 * The  capacity of a queue  is the number of entries it can hold.  The under-
 * lying implementation uses a binomial queue (a set of power-of-two heaps) as
 * its internal storage structure.  Whilst storage for entries  are  allocated
 * dynamically,  pointers for the  power-of-two heaps  are allocated  when the
 * queue is created.  The number of heap pointers is determined by the queue's
 * capacity using the formula:  heap count = log2 ( capacity + 1).
 *
 * The  priority  of entries to be added to the queue is determined by calling
 * the priority comparison handler  passed in for <handler>.  If NIL is passed
 * in for handler, no queue will be created and NIL will be returned.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE new ( size : Capacity;

                handler    : Comparison Handler?;
                VAR status : Status ) : module;

(* ---------------------------------------------------------------------------

 * function:  module.enqueue( queue, value, status )
 * ---------------------------------------------------------------------------
 *
 * Adds a new entry <value> to priority queue <queue>.  The new entry is added
 * by reference, no data is copied.  No entry is added if the queue's capacity
 * is insufficient to hold the new entry,  if memory could not be allocated or
 * if NIL is passed in for <queue> or <value>.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE enqueue ( queue : module; value : Value Type?; VAR status : Status );

(* ---------------------------------------------------------------------------

 * function:  module.inspectNext( queue, status )
 * ---------------------------------------------------------------------------
 *
 * Retrieves the entry with the highest priority from <queue>  and  returns it
 * without removing the entry.  If the queue is empty  or if  NIL is passed in
 * for <queue> then NIL is returned.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE inspectNext ( queue : module; VAR status : Status ) : Value Type?;

(* ---------------------------------------------------------------------------

 * function:  module.dequeue( queue, status )
 * ---------------------------------------------------------------------------
 *
 * Removes  the entry with the highest priority  from <queue>  and returns it.
 * If the queue is empty or NIL is passed in for <queue> then NIL is returned.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE dequeue ( queue : module; VAR status : Status ) : Value Type?;

(* ---------------------------------------------------------------------------

 * function:  module.capacity( queue )
 * ---------------------------------------------------------------------------
 *
 * Returns the total capacity of queue <queue>,  returns zero if NIL is passed
 * in for <queue>. *)

PROCEDURE capacity ( queue : module ) : Capacity;

(* ---------------------------------------------------------------------------

 * function:  module.entryCount( queue )
 * ---------------------------------------------------------------------------
 *
 * Returns the number of entries stored in queue <queue>,  returns zero if NIL
 * is passed in for <queue>. *)

PROCEDURE entryCount ( queue : module ) : Capacity;

(* ---------------------------------------------------------------------------

 * function:  module.isResizable( queue )
 * ---------------------------------------------------------------------------
 *
 * Returns TRUE  if the  capacity of <queue> can change after <queue> has been
 * instatiated,  returns FALSE otherwise. *)

PROCEDURE isResizable ( queue : module ) : BOOLEAN;

(* ---------------------------------------------------------------------------

 * function:  module.dispose( queue )
 * ---------------------------------------------------------------------------
 *
 * Disposes of priority queue object <queue> and returns NIL. *)

PROCEDURE dispose ( VAR queue : module ) : module;

END module.@]