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

(* Last modified on Tue Feb 11 20:51:43 PST 1992 by muller                   *)

GENERIC MODULE PQueue (Order, OrderPQueueADT);

(* This implementation of priority queues uses a heap to represent the 
   partially ordered tree of queue elements.  See 'Data Structures and
   Algorithms', by Aho, Hopcroft and Ullman, p 143 *)

REVEAL
  T = OrderPQueueADT.T OBJECT METHODS
        new (initialSize: CARDINAL := 0): T; END
      BRANDED OBJECT 
        a: REF ARRAY OF Order.T;
        n: CARDINAL;
      OVERRIDES
        new     := new;
        insert  := insert;
        first   := first;
        delete  := delete;
        equal   := equal;
        isEmpty := isEmpty;
        size    := size;
        copy    := copy;
        map     := map; END;

PROCEDURE new (self: T; initialSize: CARDINAL := 0): T =
  BEGIN
    IF self = NIL THEN
      self := NEW (T); END;

    EVAL OrderPQueueADT.T.new (self);

    self.a := NEW (REF ARRAY OF Order.T, initialSize);
    self.n := 0;

    RETURN self;
  END new;

PROCEDURE expand (self: T) =
  VAR newSize: CARDINAL; newA: REF ARRAY OF Order.T;
  BEGIN
    IF NUMBER (self.a^) = 0 THEN 
      newSize := 1;
    ELSE 
      newSize := 2 * NUMBER (self.a^); END;
    newA := NEW (REF ARRAY OF Order.T, newSize);
    SUBARRAY (newA^, 0, self.n) := SUBARRAY (self.a^, 0, self.n);
    self.a  := newA;
  END expand;

PROCEDURE insert (self: T; x: Order.T) =
  VAR i: CARDINAL; temp: Order.T;
  BEGIN
    IF self.n = NUMBER (self.a^) THEN
      expand (self); END;

    INC (self.n);
    i := self.n;
    self.a [i - 1] := x;

    WHILE i > 1 AND Order.Compare (self.a [i-1], self.a [(i DIV 2) - 1]) < 0 DO
      temp := self.a [i-1];
      self.a [i-1] := self.a [(i DIV 2) - 1];
      self.a [(i DIV 2) - 1] := temp;
      i := i DIV 2; END;
  END insert;

PROCEDURE first  (self: T): Order.T RAISES {OrderPQueueADT.Empty} =
  BEGIN
    IF self.n = 0 THEN
      RAISE OrderPQueueADT.Empty;
    ELSE
      RETURN self.a[0]; END;
  END first;

PROCEDURE delete (self: T): Order.T RAISES {OrderPQueueADT.Empty} =
  VAR res, temp: Order.T; i, j: CARDINAL;
  BEGIN
    IF self.n = 0 THEN
      RAISE OrderPQueueADT.Empty;
    ELSE
      res := self.a[0];
      self.a[0] := self.a [self.n - 1];
      DEC (self.n);
      i := 1;

      WHILE i <= self.n DIV 2 DO 
        IF Order.Compare (self.a [2*i - 1], self.a [2*i]) < 0 
             OR 2*i = self.n THEN
          j := 2*i;
        ELSE 
          j := 2*i + 1; END;
        IF Order.Compare (self.a [j-1], self.a [i-1]) < 0 THEN
          temp := self.a [i-1];
          self.a [i-1] := self.a [j-1];
          self.a [j-1] := temp;
          i := j; 
        ELSE
          RETURN res; END; END;
      RETURN res; END;
  END delete;

PROCEDURE equal (self: T; t: OrderPQueueADT.T): BOOLEAN =
  VAR uu := self.copy (); 
      tt := t.copy ();
      uo, to: Order.T;
  BEGIN
    LOOP
      TRY
        uo := uu.delete ();
      EXCEPT
        | OrderPQueueADT.Empty =>  RETURN tt.isEmpty (); END;
      TRY
        to := tt.delete ();
      EXCEPT
        | OrderPQueueADT.Empty =>  RETURN FALSE; END;
      IF NOT Order.Equal (uo, to) THEN
        RETURN FALSE; END; END;
  END equal;

PROCEDURE isEmpty (self: T): BOOLEAN =
  BEGIN
    RETURN self.n = 0;
  END isEmpty;

PROCEDURE size (self: T): CARDINAL =
  BEGIN
    RETURN self.n;
  END size;

PROCEDURE copy (self: T): OrderPQueueADT.T =
  BEGIN
    WITH res = NEW (T, a := NEW (REF ARRAY OF Order.T, self.n), n := self.n) DO
      res.a^ := SUBARRAY (self.a^, 0, self.n);
      RETURN res; END;
  END copy;

PROCEDURE map (self: T; f: OrderPQueueADT.F) RAISES ANY =
  BEGIN
    CASE self.n OF
    | 0 => RETURN;
    | 1 => f (self.a[0]);
    | 2 => f (self.a[0]);
           f (self.a[1]);
    ELSE
      WITH t = Copy (self) DO
        FOR i := 0 TO self.n - 1 DO
          f (t.delete ()); END; END; END;
  END map;


BEGIN
END PQueue.