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

(* Last modified on Tue Feb 11 20:53:23 PST 1992 by muller                   *)

GENERIC MODULE Stack (Elt, EltStackADT);

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

REVEAL 
  T = EltStackADT.T OBJECT METHODS
        new (): T; END
      BRANDED OBJECT 
        front: Node;
      OVERRIDES
        new     := new;
        push    := push;
        pop     := pop;
        top     := top;
        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 EltStackADT.T.new (self);

    self.front := NIL;

    RETURN self;
  END new;


PROCEDURE push (self: T; e: Elt.T) =
  BEGIN
    self.front := NEW (Node, first := e, rest := self.front);
  END push;

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

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

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

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

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

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

BEGIN
END Stack.