(* Copyright (C) 1992, Digital Equipment Corporation                         *)
(* All rights reserved.                                                      *)
(* See the file COPYRIGHT for a full description.                            *)
(*                                                                           *)
(* Last modified on Tue Jun 16 10:12:01 PDT 1992 by muller                   *)
(*      modified on Tue Mar 17  0:48:39 PST 1992 by meehan                   *)

GENERIC INTERFACE GenList (Elt);

IMPORT Thread;

TYPE
  T = OBJECT
        first: Elt.T;
        tail : T       := NIL
      END;

  MapProc = PROCEDURE (element: Elt.T): Elt.T;
  (* The type of procedures for mapping over lists. *)

  WalkProc = PROCEDURE (element: Elt.T) RAISES {};
  (* The type of procedures for walking over lists. *)

  CompareProc =
    PROCEDURE (item1, item2: Elt.T): [-1 .. 1] RAISES {Thread.Alerted};
  (* The type of client-supplied comparison functions. *)

  TestProc = PROCEDURE (item1, item2: Elt.T): BOOLEAN;
  Predicate = PROCEDURE (item: Elt.T): BOOLEAN;

PROCEDURE New (first: Elt.T; tail: T): T RAISES {};
(* Constructs a new list cell (cf. Lisp CONS). *)

PROCEDURE List1 (x1: Elt.T): T RAISES {};
PROCEDURE List2 (x1, x2: Elt.T): T RAISES {};
PROCEDURE List3 (x1, x2, x3: Elt.T): T RAISES {};
(** Constructors for convenience:

    List1( x1 )     = New( x1, NIL )
    List2( x1, x2 ) = New( x1, New( x2, NIL ) )
    ...
*)

PROCEDURE Push (VAR (* inOut *) l: T; x: Elt.T) RAISES {};
(* Pushes a new element onto the front of "l", and sets "l" to be the new
   list. Equivalent to:

   l := New( x, l );

   *)

PROCEDURE Pop (VAR (* inOut *) l: T): Elt.T RAISES {};
(** Removes one element from the front of "l", and sets "l" to the new
list.   Equivalent to:

    result := l.first
    l      := l.tail;
*)


PROCEDURE Length (l: T): CARDINAL RAISES {};
(* Returns the length of a list. *)

PROCEDURE Tail (l: T): T RAISES {};
PROCEDURE First (l: T): Elt.T RAISES {};
PROCEDURE Second (l: T): Elt.T RAISES {};
PROCEDURE Third (l: T): Elt.T RAISES {};
(* Procedural accessors of list elements.  They're included for
completeness. *)

PROCEDURE Nth (l: T; n: CARDINAL): Elt.T RAISES {};
(* The nth element of a list;  n=0 gets the first element.   Undefined
if n >= Length( l ). *)

PROCEDURE SetNth (l: T; n: CARDINAL; x: Elt.T) RAISES {};
(* Destructively changes the nth element of a list to be x.  Undefined
if n >= Length( l ). *)

PROCEDURE NthTail (l: T; n: CARDINAL): T RAISES {};
(* The result of applying Tail to l n times.   Undefined if
n >= Length( l ). *)

PROCEDURE SetNthTail (l: T; n: [1 .. LAST(CARDINAL)]; x: T) RAISES {};
(* Destructively changes the nth tail of a list to be x.  Undefined
if n < 1 or n >= Length (l). *)

PROCEDURE Last (l: T): Elt.T RAISES {};
(* The last element of l, equivalent to Nth( l, Length( l ) - 1 ). *)

PROCEDURE LastTail (l: T): T RAISES {};
(* The last tail of l, equivalent to NthTail( l, Length( l ) - 1 ). *)

PROCEDURE FirstN (l: T; n: CARDINAL): T RAISES {};
(* A new list consisting of the first n elements of l. Undefined if n >
   Length (l). *)

PROCEDURE Append (l1: T; l2: T): T RAISES {};
PROCEDURE AppendD (l1: T; l2: T): T RAISES {};
(* Appends two lists together, returning the new list. AppendD doesn't
   create any new list cells, but it destroys its first argument. *)

PROCEDURE Append1 (l1: T; x: Elt.T): T RAISES {};
PROCEDURE Append1D (l1: T; x: Elt.T): T RAISES {};
(* Appends an element onto the end of a list, returning the new list. *)

PROCEDURE Copy (l: T): T RAISES {};
(* Copy returns a copy of a list, where only the top level of the list is
   copied (the elements are not copied). *)
    
PROCEDURE Reverse (l: T): T RAISES {};
PROCEDURE ReverseD (l: T): T RAISES {};
(* Reverses a list. *)

PROCEDURE Sort (l: T; c: CompareProc): T RAISES {Thread.Alerted};
PROCEDURE SortD (l: T; c: CompareProc): T RAISES {Thread.Alerted};
(* Sorts a list in ascending order. The implementation is time- and
   cons-efficient but is not stable. *)

PROCEDURE FromVector (v: REF ARRAY OF Elt.T): T RAISES {};
(* Returns a list of the elements in vector v. *)

PROCEDURE ToVector (l: T): REF ARRAY OF Elt.T RAISES {};
(* Returns a new vector containing the elements of list l. *)

PROCEDURE Map (l: T; p: MapProc): T (* RAISES ANY *);
(* Applies p to each of the elements of l, returning a list of the results
   returned by p. The only exceptions raised are those possibly raised by
   p. *)

PROCEDURE Walk (l: T; p: WalkProc) (* RAISES ANY *);
(* Applies p to each of the elements of l in turn.  The only exceptions raised
are those possibly raised by p. *)

PROCEDURE Find (l            : T;
                item         : Elt.T;
                test, testNot: TestProc := NIL;
                start        : CARDINAL := 0;
                end          : CARDINAL := LAST (CARDINAL);
                fromEnd                 := FALSE            ): Elt.T;

PROCEDURE FindIf (l      : T;
                  pred   : Predicate;
                  start  : CARDINAL    := 0;
                  end    : CARDINAL    := LAST (CARDINAL);
                  fromEnd              := FALSE            ): Elt.T;

PROCEDURE Position (l            : T;
                    item         : Elt.T;
                    test, testNot: TestProc := NIL;
                    start        : CARDINAL := 0;
                    end          : CARDINAL := LAST (CARDINAL);
                    fromEnd                 := FALSE            ):
  [-1 .. LAST (CARDINAL)];
  
PROCEDURE PositionIf (l      : T;
                      pred   : Predicate;
                      start  : CARDINAL    := 0;
                      end    : CARDINAL    := LAST (CARDINAL);
                      fromEnd              := FALSE            ):
  [-1 .. LAST (CARDINAL)];

PROCEDURE Delete (l: T; item: Elt.T): T;

PROCEDURE DeleteD (VAR (* inOut *) l: T; item: Elt.T);

END GenList.