Critical Mass Modula-3: libm3/src/pqueue/PQueue.ig

libm3/src/pqueue/PQueue.ig

PQueue is a generic interface defining priority queues. A priority queue is a multiset of elements. If pq is a priority queue, we denote its multiset by mset(pq). The basic priority queue operations are to insert a new element into the queue and to delete one of its elements with minimal priority value.

GENERIC INTERFACE PQueue(Priority);

Where Priority.T is a type that is not an open array type, and the Priority interface contains:

CONST Brand = <text-constant>; PROCEDURE Compare(p1, p2: T): [-1..1]
Brand must be a text constant. It will be used to construct a brand for the opaque types PQueue.Elt and PQueue.Default, and any generic types instantiated with the PQueue interface. For a non-generic interface, we recommend choosing the name of the interface.
Compare must be a total order. Compare may be declared with a parameter mode of either VALUE or READONLY, but not VAR.


CONST
  EltBrand = "(PQueueElt " & Priority.Brand & ")";
  (* The type "PQueue.Elt" is revealed to have the brand "EltBrand". *)

TYPE
  Elt <: OBJECT
    priority: Priority.T
  END;

A PQueue.Elt is an {\it element\/} of a priority queue. Every element elt has a priority elt.priority.

EXCEPTION Empty; NotInQueue;

The Empty exception is raised when mset(pq) is empty. The NotInQueue exception is raised if the element to delete or change is not currently in the queue.

CONST
  Brand = "(PQueue " & Priority.Brand & ")";
  DefaultBrand = "(Default " & Brand & ")";
  (* The type "PQueue.Default" is revealed to have the brand "DefaultBrand". *)

TYPE
  T = OBJECT METHODS
    insert(READONLY elt: Elt);
    delete(elt: Elt) RAISES {NotInQueue};
    size(): CARDINAL;
    min(): Elt RAISES {Empty};
    deleteMin(): Elt RAISES {Empty};
    change(elt: Elt; newP: Priority.T) RAISES {NotInQueue};
  END;

Do not instantiate a T; instead, instantiate one of its subtypes, such as the Default implementation below. The methods have the following specifications:

The call pq.insert(elt) adds elt to mset(pq).

The call pq.delete(elt) removes element elt from the queue.

The call pq.size() returns the number of elements in the queue.

The call pq.min() returns an element in the queue with minimal priority value.

The assignment elt := pq.deleteMin() is equivalent to the code

         elt := pq.min(); pq.delete(elt)

However, deleteMin can be implemented more efficiently than by simply composing the min and delete operations.

The call pq.change(elt, newP) changes the priority of the element elt to newP. It is equivalent to:

         pq.delete(elt);
         elt.priority := newP;
         pq.insert(elt)

However, change can be implemented more efficiently than by simply composing the delete and insert operations.

Default <: DefaultPub;
  DefaultPub = T OBJECT METHODS
    init(sizeHint: CARDINAL := 10): Default;
    fromArray(READONLY e: ARRAY OF Elt): Default;
    pCompare(READONLY p1, p2: Priority.T): [-1..1]
  END;

The type PQueue.Default is an implementation of priority queues that uses a heap represented by an array. This implementation guarantees that the insert, delete, deleteMin, and change operations will take O(log n) time (where n is the number of elements in the queue), and that the size and min operations will take O(1) time.

The call NEW(PQueue.Default).init(sizeHint) creates a new, empty priority queue. The init method resets mset(pq) of an existing priority queue pq to the empty set.

The call NEW(PQueue.Default).fromArray(elts) creates a new priority queue containing the elements elts[FIRST(elts)], ..., elts[LAST(elts)]. Initializing a priority queue in this way takes linear time, whereas creating an empty queue and adding the elements to it one at a time takes O(n log n) time in the worst case.

By default, the method call pq.pCompare(p1, p2) returns the result of the call Priority.Compare(p1, p2). Clients are free to override the pCompare method to change the total order on priorities.

For efficiency, a PQueue.Default is unmonitored: it is up to clients to avoid illegal concurrent accesses on its methods. The readonly methods are size and min.

END PQueue.