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

(* Last modified on Tue Feb 11 20:50:16 PST 1992 by muller                   *)

GENERIC MODULE Queue (Elt, EltQueueADT);

TYPE
  Node = REF RECORD
           first: Elt.T;
           rest: Node; END;

REVEAL 
  T = EltQueueADT.T OBJECT METHODS
        new (): T; END
      BRANDED OBJECT
        front, back: Node;
      OVERRIDES
        new     := new;
        insert  := insert;
        first   := first;
        delete  := delete;
        equal   := equal;
        isEmpty := isEmpty;
        size    := size;
        copy    := copy;
        map     := map;
      END;

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

    EVAL EltQueueADT.T.new (self);

    self.front := NIL;
    self.back := NIL;

    RETURN self;
  END new;

PROCEDURE insert (self:T; e: Elt.T) =
  BEGIN
    WITH e = NEW (Node, first := e, rest := NIL) DO
      IF self.back = NIL THEN
        self.front := e;
        self.back :=  e;
      ELSE
        self.back.rest := e;
        self.back := e; END; END;
  END insert;

PROCEDURE first (self: T): Elt.T RAISES {EltQueueADT.Empty} =
  BEGIN
    IF self.front = NIL THEN
      RAISE EltQueueADT.Empty; 
    ELSE
      RETURN self.front.first; END;
  END first;

PROCEDURE delete (self: T): Elt.T RAISES {EltQueueADT.Empty} =
  VAR x: Elt.T;
  BEGIN
    IF self.front = NIL THEN
      RAISE EltQueueADT.Empty;
    ELSE
      x := self.front.first;
      self.front := self.front.rest;
      IF self.front = NIL THEN
        self.back := NIL; END;
      RETURN x; END;
  END delete;

PROCEDURE equal (self: T; t: EltQueueADT.T): BOOLEAN =
  VAR u := self.front;
      tt := t.copy ();
  BEGIN
    TRY
      WHILE u # NIL DO
        IF NOT Elt.Equal (u.first, tt.delete ()) THEN
          RETURN FALSE; END;
        u := u.rest; END;
      RETURN tt.isEmpty ();
    EXCEPT
      | EltQueueADT.Empty => RETURN FALSE; END;
  END equal;

PROCEDURE isEmpty (self: T): BOOLEAN =
  BEGIN
    RETURN self.front = NIL;
  END isEmpty;
    
PROCEDURE size (self: T): CARDINAL =
  VAR count: CARDINAL := 0; u := self.front;
  BEGIN
    WHILE u # NIL DO 
      INC (count);
      u := u.rest; END;
    RETURN count;    
  END size;

PROCEDURE copy (self: T): EltQueueADT.T =
  VAR t := self.front; res := new (NIL);
  BEGIN
    IF t = NIL THEN
      RETURN res;
    ELSE
      res.front := NEW (Node, first := Elt.Copy (t.first), rest := NIL);
      res.back  := res.front;
      t := t.rest;
      WHILE t # NIL DO
        WITH e = NEW (Node, first := Elt.Copy (t.first), rest := NIL) DO
          res.back.rest := e;
          res.back := e;
          t := t.rest; END; END;
      RETURN res; END;
  END copy;

PROCEDURE map (self: T; f: EltQueueADT.F) RAISES ANY =
  VAR u := self.front;
  BEGIN
    WHILE u # NIL DO
      f (u.first);
      u := u.rest; END;
  END map;

BEGIN
END Queue.