STKSUMI.DEF

(*
7	The Unbounded Stack

An implementation of the stack abstraction, described in chapter 8, is presented here.
This particular form has the properties: Sequential, Unbounded, Managed, and Iterator.
These describe specific aspects of the implementation as follows:

Sequential:	Can only be used in a non-tasking environment, or by only one task.
Unbounded:	The size of a stack varies dynamically as items are added and removed.
Managed:	Memory space for items and objects is returned to the system when no
			longer needed.
Iterator:	Routines for looping over each of the stack items are provided.


Section 7.1 contains the interface to the Unbounded Stack module followed by its
implementation in Section 7.2.


7.1		StackSUMI Interface

The interface to the unbounded stack is presented below.  The purpose and
implementation specifics of each routine is briefly described along with mention of the
complexity measure of the actual implementation.
*)


DEFINITION MODULE StkSUMI;
(*============================================================
    Version  : 1.00  28 Apr 1989  C. Lins
    Compiler : JPI TopSpeed Modula-2 Compiler
    Component: Monolithic Structures - Stack (Opaque version)
               Sequential Unbounded Managed Iterator

    INTRODUCTION
    This module provides the stack ADT composed of generic Items.

    REVISION HISTORY
    v1.00  28 Apr 1989  C. Lins:
      Initial implementation.
============================================================*)

FROM Items IMPORT
    (*--Type*) Item, AccessProc, LoopAccessProc, ChangeProc,
               LoopChangeProc;

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

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

FROM TypeManager IMPORT
    (*--Type*) TypeID;

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


TYPE  Stack;
CONST NullStack  = Stack(NIL);


(*
7.1.1	Exceptions

The ModuleID  is used by the exception handling mechanism to distinguish this module
from other modules.

StackError  returns the exception code from the most recent stack operation.  A result of
noerr  indicates successful completion of the operation. O(1).

GetHandler  returns the exception handler routine associated with the given exception. 
Though the routine is a function procedure returning a procedure as its result, the
HandlerProc  may not be called from within the GetHandler  call itself.  The procedure
result must be first assigned to a procedure variable before invocation.  Exception handlers
are given an initial value of ExitOnError  except for the handler for noerr  which is
initialized to the null exception handler. O(1).

SetHandler  associates an exception handler routine with the given exception and is the
inverse of GetHandler.  This routine may be used to override the default settings for the
exception handlers. O(1).
*)

CONST ModuleID = 2;

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

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

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


(*
7.1.2	Constructors

The Create operation attempts to generate a new, empty stack associated with the given
data type identifier (theType) and Item operations.  The TypeID is the method by which
Items of any data type are supported.  Using theType, the component can assign one item
to another and release any dynamically allocated resources associated with an Item without
knowledge of the Item's internal composition.  In this way, one may create a stack whose
items consist of other (dynamically allocated) structures, as well as stacks consisting of
the basic data types.  Create returns the new stack upon successful completion of the
routine.  If it is not possible for the stack to be created, the overflow exception is raised
and the constant NullStack  will be returned. O(1).

Destroy  takes the given stack, clears it of any items, and then destroys the stack itself. 
Where Create makes a defined stack, Destroy is its inverse, making the stack undefined.
O(1).

Clear  takes the given stack and removes all of its items.  theType attribute of the stack 
(assigned when the stack was created) is used to retrieve the item deallocation routine for
the items of the stack.  Clearing the stack returns it to the empty state. O(n).

The Assign  operation attempts to generate a duplicate of the source stack (theStack) in
the target stack (toStack).  The target stack is automatically created using the data type
attribute of the source stack, if necessary.  If this step is unnecessary, (the target stack has
been previously created), the target is cleared of its present contents, and its data type is
set to that of the source stack.  O(n).

In order to allow Items of any data type, a method must be provided to assign the contents
of one item to another item.  This is accomplished, as above for Create, through the
TypeID of the source stack.

The Push  operation adds items to the given stack.  The given item is placed on the stack
top.  If the stack cannot be expanded for theItem the overflow  exception is raised and the
stack remains unchanged. O(1).

The Pop  operation removes the topmost item from the given stack.  If the given stack is 
empty on entry to Pop  the underflow  exception is raised and the stack remains
unchanged. O(1).

PopTopOf  is a convenience routine combining the semantics of the constructor Pop and
the selector TopOf.  The only difference from Pop is that the item's value is not disposed
of, but is returned instead. O(1).
*)


PROCEDURE Create    (    theType   : TypeID    (*-- in    *))
                                   : Stack     (*-- out   *);

PROCEDURE Destroy   (VAR theStack  : Stack     (*-- inout *));

PROCEDURE Clear     (VAR theStack  : Stack     (*-- inout *));

PROCEDURE Assign    (    theStack  : Stack     (*-- in    *);
                     VAR toStack   : Stack     (*-- inout *));

PROCEDURE Push      (VAR toStack   : Stack     (*-- inout *);
                         theItem   : Item      (*-- in    *));

PROCEDURE Pop       (VAR theStack  : Stack     (*-- inout *));

PROCEDURE PopTopOf  (VAR theStack  : Stack     (*-- inout *))
                                   : Item      (*-- out   *);


(*
7.1.3	Selectors

IsDefined  attempts to determine whether the given stack is valid, e.g., has been created
and not yet destroyed.  How this is accomplished may be as simple or complicated as the
implementor desires and the requirements of the application. O(1).

IsEmpty  returns true if the given stack contains no items; in other words, its depth is
zero.  Undefined stacks are always considered to be empty. O(1).

IsEqual  returns true if the left and right stacks contain the same items.  Obviously, both
must also have the same data type and have been created.  An undefined stack is not equal
to any other stack, including itself. O(n).

The routine TypeOf  returns the type ID value given  to the stack when it was created or
used as the target of an assignment operation, and is provided so that the user of the
module need not maintain a separate variable recording this information. O(1).

DepthOf  returns the number of items present on the given stack.  Undefined stacks are
considered to have a depth of zero. O(1).

TopOf  returns the item currently at the top of the stack.  If the stack is empty a stack
underflow occurs and the NullItem is returned (since some Item must be).  Undefined
stacks also cause the NullItem to be returned. O(1).
*)


PROCEDURE IsDefined (    theStack  : Stack     (*-- in    *))
                                   : BOOLEAN   (*-- out   *);

PROCEDURE IsEmpty   (    theStack  : Stack     (*-- in    *))
                                   : BOOLEAN   (*-- out   *);

PROCEDURE IsEqual   (    left      : Stack     (*-- in    *);
                         right     : Stack     (*-- in    *))
                                   : BOOLEAN   (*-- out   *);

PROCEDURE TypeOf    (    theStack  : Stack     (*-- in    *))
                                   : TypeID    (*-- out   *);

PROCEDURE DepthOf   (    theStack  : Stack     (*-- in    *))
                                   : CARDINAL  (*-- out   *);

PROCEDURE TopOf     (    theStack  : Stack     (*-- in    *))
                                   : Item      (*-- out   *);


(*
7.1.4	Iterators

The iterator routines LoopOver and LoopChange provide facilities for looping over some
or all items of a stack, with read-only and read-write access to each item, respectively. 
theProcess  procedure parameter to these routines return a BOOLEAN function result
where TRUE allows the iteration to proceed to the next item and FALSE causes the
iteration to be terminated. O(n).

Traverse  and TravChange iterators provide facilities for looping over all items of a stack,
with read-only and read-write access to each item, respectively. O(n).

All four iterators traverse the given stack from the topmost item towards the bottom of
the stack.  Obviously, if given an empty stack the processing procedure will not be
invoked.
*)


PROCEDURE LoopOver   (    theStack  : Stack          (*-- in    *);
                          theProcess: LoopAccessProc (*-- in    *));

PROCEDURE LoopChange (    theStack  : Stack          (*-- in    *);
                          theProcess: LoopChangeProc (*-- in    *));

PROCEDURE Traverse   (    theStack  : Stack          (*-- in    *);
                          theProcess: AccessProc     (*-- in    *));

PROCEDURE TravChange (    theStack  : Stack          (*-- in    *);
                          theProcess: ChangeProc     (*-- in    *));

END StkSUMI.