(* Copyright (C) 1992, Digital Equipment Corporation                         *)
(* All rights reserved.                                                      *)
(* See the file COPYRIGHT for a full description.                            *)

(* Last modified on Wed Jul 15 09:08:14 PDT 1992 by kalsow                   *)
(*      modified on Tue Feb 11 20:51:43 PST 1992 by muller                   *)

GENERIC INTERFACE PQueueADT (Order);

(* The Priority Queue abstract data type.

   The type 'T' defines the basic operations available from all 
   implementations of priority queues.  The 'new' operation may be 
   redefined with a different signature in subtypes of 'T'.  Also, 
   subtypes may define additional methods.  

   Interfaces that define implementations of PQueue may require actual 
   arguments that are more strict than Order.

   A simple implementation is provided by the PQueue interface. *)

EXCEPTION
  Empty;

TYPE
  F = PROCEDURE (x: Order.T) RAISES ANY;
        (* to iterate over the elements of a pqueue *)

  T = OBJECT METHODS
        new (): T := new;
          (* create (self = NIL) or initialize (self # NIL) a PQueue.T *)

        insert (x: Order.T);
          (* insert 'e' in 'self' *)
        delete (): Order.T RAISES {Empty};
          (* if 'self' is not emtpy, remove the element at the front
             of 'self' and return that element.  Otherwise, raise Emtpy. *)
        first  (): Order.T RAISES {Empty};
          (* if 'self' is not emtpy, return the element at the front
             of 'self'.  Otherwise, raise Emtpy. *)


        equal (s: T): BOOLEAN;
          (* TRUE iff 'self' and 't' are equal *)
        isEmpty (): BOOLEAN;
          (* TRUE iff 'self' is empty *)
        size (): CARDINAL;
          (* return the number of elements in 'self' *)
        copy (): T;
          (* return a copy of 'self' *)
        map (f: F) RAISES ANY;
          (* apply 'f' to each element of 'self'.  It is an unchecked runtime
             error to modify 'self' while this procedure is active *)
        END;

PROCEDURE new (self: T): T;

END PQueueADT.