(*
7.1 Doubly-Linked Bounded List Interface

Below is the equivalent interface for the doubly-linked bounded
list.
*)

DEFINITION MODULE ListDBM;
(*==========================================================
    Version  : 1.00  18 May 1989  C. Lins
    Compiler : TopSpeed Modula-2
    Component: Polylithic Structures - List
	Doubly-Linked Bounded Managed

    The Abstraction
    This module provides the List ADT for generic Items.

    Revision History
    v1.00  18 May 1989  C. Lins
      Initial implementation for TopSpeed Modula-2.
	(C) Copyright 1989 Charles A. Lins
==========================================================*)

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

FROM ErrorHandling IMPORT
    (*--Type*) HandlerProc;

FROM ListEnum IMPORT
    (*--Type*) Exceptions;

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

(*
7.1.1 Type Declarations

The reader may remember from the bounded structures in Volume 1
it was sufficient to modify the Create operation to include a
parameter specifying the structure's desired maximum size.  And
to allow the client to easily retrieve this limit, the selector
SizeOf was also added as a convenience.  This approach could be
taken for bounded lists as well resulting in each list created
being associated with its own pool of nodes.  This is not necessarily
bad, but potentially would be very wasteful of space since the
pools (and the nodes resident there) could not be shared by all
bounded lists of the same type.  

The approach taken for the bounded list is in addition to the
abstract type List, the abstract type Pool is exported along
with a subrange representing the limits on the size of a node
pool.  Now the client can create a number of Pools and associate
Lists with a given pool.  The only constraint is that a List may
not draw nodes from more than a single pool and all operations
must identify the pool on which to operate.

List cannot be declared opaque and then in the 
implementation defined as a CARDINAL (at least in the TML Modula-2
compiler); for this reason transparent export is used.  Furthermore,
the pool size is restricted to a greater extent than in the
singly-linked list due to compiler constraints on the size of
arrays.  The constant NullList is used to terminate a sequence
of links, either forward or backward.
*)

TYPE  Pool;
TYPE  PoolSize = [1 .. 4000];

TYPE  List     = CARDINAL;
CONST NullList = 0;


(*
7.1.2 Exceptions

The ModuleID uniquely identifies this module.  ListError returns
the result code from the most recently invoked list operation.
GetHandler and SetHandler allow assignment and retrieval,
respectively, of exception handlers for specific exceptions.

The undefined exception is associated with the type Pool, and the
listisnull exception used to identify invalid operations on an
empty list.  Overflow is raised when attempting to expand a list
and there are no more nodes left in the pool.
*)

CONST ModuleID = 1;

PROCEDURE ListError   ()	: Exceptions  (*-- out   *);

PROCEDURE GetHandler  (    ofError   : Exceptions  (*-- in    *))
	: HandlerProc (*-- out   *);

PROCEDURE SetHandler  (    ofError   : Exceptions  (*-- in    *);
	theHandler: HandlerProc (*-- in    *));


(*
7.1.3 Constructors

InitPool attempts to construct a node pool of the given size and
FreePool releases the existing node pool.  In the list operations
the internal state of the pool may change as a result of the operation
but the actual value for the pool itself does not change; this is
why thePool is labeled as inout without an accompanying VAR.

Create retrieves a node from the given pool, raising overflow and
returning the NullList if the node pool is already full.  It is
equivalent to the routine GetNode seen in Pascal texts.

Destroy returns theList node to the node pool and is equivalent
to the routine FreeNode seen in Pascal texts.

Definitions for the other constructors was given in Section 3.3,
under Constructor Operations.
*)

PROCEDURE InitPool  (    theSize : PoolSize (*-- in    *))
	: Pool     (*-- out   *);

PROCEDURE FreePool  (    thePool : Pool     (*-- inout *));


PROCEDURE Create    (    thePool : Pool     (*-- inout *))
	: List     (*-- out   *);

PROCEDURE Destroy   (    thePool : Pool     (*-- inout *);
	VAR theList : List     (*-- inout *));

PROCEDURE Clear     (    thePool : Pool     (*-- inout *);
	VAR theList : List     (*-- inout *));

PROCEDURE Assign    (    thePool : Pool     (*-- inout *);
	theList : List     (*-- in    *);
	VAR toList  : List     (*-- inout *));

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

PROCEDURE SetNext   (    thePool : Pool     (*-- inout *);
	theList : List     (*-- inout *);
	newNext : List     (*-- in    *));

PROCEDURE SetPrev   (    thePool : Pool     (*-- inout *);
	theList : List     (*-- inout *);
	newPrev : List     (*-- in    *));

PROCEDURE SetList   (    thePool : Pool     (*-- inout *);
	theItem : Item     (*-- in    *))
	: List     (*-- out   *);

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


(*
7.1.4 Selectors

The selectors have all been modified from the unbounded form to
accept thePool parameter.  IsDefined has been added to test whether
a given pool variable has been initialized.
Definitions for the other selectors was given in Section 3.4,
under Selector Operations.  All list selectors have a complexity
of O(1) except for IsEqual which is O(Min(m,n)) and LengthOf which
is O(n).
*)

PROCEDURE IsDefined (    thePool : Pool     (*-- in    *))
	: BOOLEAN  (*-- out   *);

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

PROCEDURE IsEqual   (    thePool : Pool     (*-- in    *);
	left    : List     (*-- in    *);
	right   : List     (*-- in    *))
	: BOOLEAN  (*-- out   *);

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

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

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

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

END ListDBM.

(*

References

[1] Aho, Hopcroft, and Ullman, Data Structures and Algorithms,
    Addison-Wesley, Reading MA 1983.
[2] G. Booch, Software Components with Ada, Structures, Tools, and Subsystems,
    Benjamin/Cummings, Menlo Park, CA 1987.
[3] D. Knuth, The Art of Computer Programming, Volume 1, Fundamental
    Algorithms, Addison-Wesley, Reading MA 1973.
[4] R. Wiener and R. Sincovec, Data Structures Using Modula-2,
    John Wiley & Sons, New York, NY, 1986, pg. 198.
*)