(*
Doubly-Linked List Utilities - Interface

In this section is provided a list utilities module for doubly-linked
unbounded lists.  The routines implement such useful list operations as:

Constructors
∙ constructing a list from an array of items (Construct and Build),
∙ merging two lists
∙ inserting an item to the end of a list (AddToTail),

Selectors
∙ retrieving the link to the last item of a list (LastOf),
*)

DEFINITION MODULE ListDBMTools; 
(*==========================================================
    Version  : 1.00  18 May 1989  C. Lins
    Compiler : TopSpeed Modula-2
    Component: Tools - Structure Utility - Doubly-Linked List

    Revision History
    v1.00  18 May 1989  C. Lins
      Initial implementation.
	(C) Copyright 1989 Charles A. Lins
=============================================================*)

FROM Items IMPORT
    (*--Type*) Item;

FROM ListDBM IMPORT
    (*--Type*) List, Pool;

    (*--------------------*)

TYPE  Position     = CARDINAL;
CONST NullPosition = 0;


    (*--------------------*)

(*
Constructors

Construct builds a list from an array of Items.  If theList is not
empty it is cleared of its contents before the construction commences.
Build is similar except that only the first n items (numItems) are used to
construct the list.

AddToTail adds theItem to the end of theList.  Complexity: O(n).

Split divides theList into two lists at theItem.  If theItem is not present
in theList then the toList is unchanged.
*)

PROCEDURE Construct (    theItems : ARRAY OF Item (*-- in    *);
	VAR theList  : List	(*-- inout *);
					     thePool  : Pool		  (*-- in    *));

PROCEDURE Build     (    theItems : ARRAY OF Item (*-- in    *);
	numItems : CARDINAL      (*-- in    *);
	VAR theList  : List	(*-- inout *);
					     thePool  : Pool		  (*-- in    *));

PROCEDURE AddToTail (    theItem  : Item	(*-- in    *);
	VAR theList  : List	(*-- inout *);
					     thePool  : Pool		  (*-- in    *));

PROCEDURE Split     (VAR theList  : List	(*-- inout *);
	theItem  : Item	(*-- in    *);
	VAR toList   : List	(*-- inout *);
					     thePool  : Pool		  (*-- in    *));


(*
Selectors

LastOf returns the list containing the last item of theList or the NullList
if theList is empty.

PositionOf searches for theItem in theList returning theItem's position such
that:
	Position = 1 when theItem is at the front of theList,
	Position = LengthOf(theList) when theItem is at the end of theList, and
	Position = 0 when theItem is not present within theList.

LocationOf returns a list beginning with the item at theIndex in theList.  If
theList does not have such a positionthe NullList is returned.
*)

PROCEDURE LastOf     (    thePool : Pool     (*-- in    *);
					      theList : List	 (*-- in    *))
	: List     (*-- out   *);

PROCEDURE PositionOf (    theItem : Item     (*-- in    *);
	theList : List     (*-- in    *);
					      thePool : Pool	 (*-- in    *))
							: Position (*-- out   *);

PROCEDURE LocationOf (    theIndex: Position (*-- in    *);
	theList : List     (*-- in    *);
					      thePool : Pool	 (*-- in    *))
							: List     (*-- out   *);

END ListDBMTools.