(*

Title:   Lists as Stacks
Author:  William M. Farmer
Revised: 06-NOV-2002

Interface:

INTERFACE Lists;
  TYPE List;
  CONST Nil: List;
  PROCEDURE Cons(i: INTEGER; k: List): List;
  PROCEDURE Member(i: INTEGER, k: List): INTEGER;
  PROCEDURE Take(i: INTEGER, k: List): List;
  PROCEDURE Drop(i: INTEGER, k: List): List;
END Lists.

*)

MODULE Lists;

IMPORT Stacks, Out;


(* Types *)

TYPE List* = Stacks.Stack;


(* Constants *)

VAR Nil-: List;


(* Exceptions: *)

PROCEDURE BadIndexException();
BEGIN
  Out.String("List.BadIndexException: The index is out of range.");
  HALT(33)  (* Abort program *)
END BadIndexException;


(* Interface procedures defined using procedures from Stacks *)

PROCEDURE Cons*(i: INTEGER; k: List): List;
BEGIN
  RETURN Stacks.Push(i,k)
END Cons;

PROCEDURE Member*(i: INTEGER; k: List): INTEGER;
BEGIN
  IF (i < 0) OR Empty(k) THEN
    BadIndexException()
  ELSIF i = 0 THEN
    RETURN Stacks.Top(k)
  ELSE
    RETURN Member(i - 1, Stacks.Pop(k))
  END
END Member;


PROCEDURE Drop*(i: INTEGER; k: List): List;
BEGIN
  IF (i < 0) THEN
    BadIndexException()
  ELSIF (i = 0) OR (k = Nil) THEN
    RETURN k
  ELSE
    RETURN Drop(i - 1, Stacks.Pop(k))
  END
END Drop;


(* Interface procedures without using procedures from Stacks *)

PROCEDURE Take*(i: INTEGER; k: List): List;

  PROCEDURE TakeAux(i: INTEGER; k1,k2: List): List;
  BEGIN
    IF (i < 0) THEN
      BadIndexException()
    ELSIF (i = 0) OR (k2 = Nil) THEN
      RETURN Reverse(k1)
    ELSE
      RETURN TakeAux(i - 1, 
                     Cons(Head(k2), k1), 
                     Tail(k2))
    END
  END TakeAux;

BEGIN
  RETURN TakeAux(i, Nil, k)
END Take;


(* Local functions *)

PROCEDURE Empty(k: List): BOOLEAN;
BEGIN
  RETURN k = Nil
END Empty;

PROCEDURE Head(k: List): INTEGER;
BEGIN
  RETURN Member(0, k)
END Head;

PROCEDURE Tail(k: List): List;
BEGIN
  RETURN Drop(1, k)
END Tail;

PROCEDURE Reverse(k: List): List;
  VAR k1: List;
BEGIN
  k1 := Nil;
  WHILE k # Nil DO
    k1 := Cons(Head(k), k1);
    k := Tail(k)
  END;
  RETURN k1
END Reverse;


BEGIN
  Nil := Stacks.Bottom;    (* Initialize Nil *) 
END Lists.
