(*
7.1 Weight Balanced Binary Search Tree Interface

This module provides operations for weight balanced binary search
tree as an abstract data type. These trees obey a balance criterion
on the subtrees of every node. Each node of the tree has a weight
attached to it. A tree is said to be of weighted balance "a" or of
bounded balance "a", or in the set BB[a], for 0 <= a <= 1/2, if for
every node in the tree has balance, p(t), between a and 1 - a. The
balance of a node is defined as

                number of leaves in t^.left
        p(t) = -----------------------------
                number of leaves in t

The empty binary tree is in BB[a] by convention.

This module trees are weight balanced trees with a = 1-Sqrt(2)/2 = 0.292893≡

Each node of a tree is assumed to consist of two data elements ≡ a key
field and a data field. Keys are used to structure the tree, while the
data field simply represents information associated with a key but is
not a part of it. While this separation may be less efficient in operation,
it does lead to a cleaner interface.

Keys are assumed to have the following operations available:
        * a routine that assigns key values;
        * a routine that compares key values returning the ordering
          relation between them (i.e., less, equal, or greater); and
        * optionally, a routine that disposes of key values that have been
          allocated on the heap.

Data values are assumed to the the following operations:
        * a routine that assigns data values; and
        * optionally, a routine that disposes of data values stored on the
          heap.

In both cases, keys and data values, along with the above operations, are
identified by a TypeID that is unique for a given data type. This data type
may be a standard Modula-2 type or one formed by the programmer using data
type forming operations (e.g., RECORDs).

The subsections are divided as follows:
        * 7.1.1 Type Declarations
        * 7.1.2 Exception Handling
        * 7.1.3 Tree Constructors
        * 7.1.4 Tree Selectors
        * 7.1.5 Passive Iterators
        * 7.1.6 Active Iterators
*)

DEFINITION MODULE BBSUMI;
(*==============================================================
    Version  : V2.01  08 December 1989.
    Compiler : JPI TopSpeed Modula-2
    Component: Monolithic Structures - Tree (Opaque version)
               Sequential Unbounded Managed Iterator

    REVISION HISTORY
    v1.01  18 May 1988  C. Lins
      Initial implementation for TML Modula-2.
    v1.02  01 Oct 1988  C. Lins
      Updated and improved comments.
    v1.03  29 Jan 1989  C. Lins
      Added aliases for generic Items as Keys and Data to enhance
          readability.
    v1.04  06 Feb 1989  C. Lins
          Added use of InsertProc instead of FoundProc in Insert.
    v1.05  09 Feb 1989  C. Lins
          Removed VAR from Clear, Insert, & Remove (the tree itself
          does not change).
    v1.06  18 Apr 1989  C. Lins
          Changed module id.
    v2.00  08 Oct 1989  C. Lins
          Created generic pc version
    v2.01  08 Dec 1989  I.S.C. Houston.
          Adapted to JPI Compiler:
          Use of type transfer functions instead of VAL.
          Use of shortened library module names.

        (C) Copyright 1989 Charles A. Lins
==============================================================*)

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

FROM TreeTypes IMPORT
    (*--Type*) Exceptions, Key, Data,
               AccessProc, InsertProc, FoundProc, NotFoundProc;

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

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


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

(*
7.1.1 Type Declarations

Each instance of the Weighted Binary Tree abstract data type is
represented by the type, Tree, using Modula-2's opaque type definition
facility. The undefined tree is represented by a Tree constant of NIL.
*)

TYPE  Tree;
VAR   NullTree : Tree;


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

(*
7.1.2 Exceptions

The following types and routines are used to support the exception
handling mechanism. This mechanism is consistent across all modules
in this series.

ModuleID        is a constant that uniquely identifies this module,
                        in this case the number 2008. This allows exception
                        handlers to know the module raising an exception.

TreeError       returns the most recent exception condition from the last
                        tree operation or the constant noerr if an exception was
                        not raised.
GetHandler      returns the exception handler for the given exception condition.

SetHandler      allows client modules to assign an exception handling routine
                        for specific exceptions. In this way the client may override
                        the default exception handling mechanism (which does nothing).
*)

CONST ModuleID = 3;

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

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

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


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

(*
7.1.3 Constructors

Constructor operations update or change the state of a tree object. In
this section we briefly describe each tree operation and its effect on
a tree object. Exception conditions raised by these routines have been
previously discussed in 3.3, Binary Search Tree Operations.

Create  attempts to form a new, empty binary tree object having the given
                key and data type identifiers.

MakeTree does the same as Create, except that it also attempts to add
                the given key and data items as the root of the new tree.

Destroy attempts to demolish an existing tree object, clearing the tree
                of all its contents and making the tree ≡undefined≡.

Clear   empties an existing tree of its contents returning the tree to
                an empty state.

Assign  attempts to duplicate (e.g., make a copy) of an existing tree.
                The target tree, where the copy is stored, is cleared of its
                contents, if any, before the assignment commences.

Insert  attempts to add a node having the given key and data values
                to the given tree. The tree is rebalanced if necessary to ensure
                that the weight-balanced property is maintained. If a node
                already exists in the tree with the given key the found procedure
                parameter is invoked and the new element is not added to the tree.

Remove  searches the given tree for the node containing the specified key
                value and removing this node from the tree. If a node does not
                exist in the tree with the given key the notFound procedure
                parameter is invoked. Following the removal of the node, the
                tree is rebalanced, if necessary, to maintain the weight-balance
                property.
*)

PROCEDURE Create    (    keyType  : TypeID       (*--in   *);
                                                 dataType : TypeID       (*--in   *))
                                  : Tree         (*--out  *);

PROCEDURE MakeTree  (    keyType  : TypeID       (*--in   *);
                                                 dataType : TypeID       (*--in   *);
                         theKey   : Key          (*--in   *);
                                                 theData  : Data         (*--in   *))
                                  : Tree         (*--out  *);

PROCEDURE Destroy   (VAR theTree  : Tree         (*--inout*));

PROCEDURE Clear     (    theTree  : Tree         (*--inout*));

PROCEDURE Assign    (    theTree  : Tree         (*--in   *);
                     VAR toTree   : Tree         (*--inout*));

PROCEDURE Insert    (    theTree  : Tree         (*--inout*);
                         theKey   : Key          (*--in   *);
                         theData  : Data         (*--in   *);
                                                 found    : InsertProc   (*--in   *));

PROCEDURE Remove    (    theTree  : Tree         (*--inout*);
                         theKey   : Key          (*--in   *);
                                                 notFound : NotFoundProc (*--in   *));


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

(*
7.1.4 Selectors

Selector operations allow a client module to examine the state of a tree
without changing that state.

IsDefined       verifies whether theTree has been created and is still an
                        active object. For our purposes, a tree object is considered
                        defined if it is not equal to the NullTree.

IsEmpty         returns true if the given tree does not contain any nodes, and
                        false otherwise.

IsEqual         returns true if and only if the two trees have the same key and
                        data item types, contain the same items, and have the same
                        relationships between each item.

KeyTypeOf       simpy returns the data type ID of the keys associated with this tree.

DataTypeOf      returns the data item type ID of the given tree.

ExtentOf        returns a count indicating the total number of nodes in the tree.

IsPresent       searches the given tree for the item with the given key value.
                        If the item is found the found procedure parameter is called,
                        otherwise the notFound procedure parameter is called.
*)

PROCEDURE IsDefined  (    theTree  : Tree         (*--in   *))
                                   : BOOLEAN      (*--out  *);

PROCEDURE IsEmpty    (    theTree  : Tree         (*--in   *))
                                   : BOOLEAN      (*--out  *);

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

PROCEDURE KeyTypeOf  (    theTree  : Tree         (*--in   *))
                                   : TypeID       (*--out  *);

PROCEDURE DataTypeOf (    theTree  : Tree         (*--in   *))
                                   : TypeID       (*--out  *);

PROCEDURE ExtentOf   (    theTree  : Tree         (*--in   *))
                                   : CARDINAL     (*--out  *);

PROCEDURE IsPresent  (    theTree  : Tree         (*--in   *);
                          theKey   : Key          (*--in   *);
                                                  found    : FoundProc    (*--in   *);
                                                  notFound : NotFoundProc (*--in   *));


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

(*
7.1.5 Passive Iterators

Three passive iterators are provided each implementing one of the standard
tree traversal algorithms. Passive iterators allow the client module
to traverse the tree as through it were a single, monolithic data structure.
*)

PROCEDURE Preorder  (    theTree   : Tree       (*--in   *);
                         theProcess: AccessProc (*--in   *));

PROCEDURE Inorder   (    theTree   : Tree       (*--in   *);
                         theProcess: AccessProc (*--in   *));

PROCEDURE Postorder (    theTree   : Tree       (*--in   *);
                         theProcess: AccessProc (*--in   *));


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

(*
7.1.6 Active Iterators

While passive iterators are most useful for tree objects, there may
be situations when the client module requires more control over the
iteration process (e.g., when printing the internal binary tree
representation). In this case, it is necessary to use an active
iteration mechanism, where the internal structure of a tree is made
visible to the client in a controlled manner that ensures the safety
of the abstraction.

In the form presented here, the internal structure is made visible
through the opaque type NodePtr, representing a subtree node of a tree.
An empty subtree is modelled by the constant NullNode. Balance represents
the number of external nodes rooted at a given subtree. If the subtree is
empty, by convention, the balance is one.

The reader should note that none of the active iterator operations
raise exceptions.

NodePtr         is a type used to represent and individual node of the tree.

NullNode        is a constant representing an empty subtree.

Weight          represents the number of nodes rooted at a given subtree.

RootOf          returns a reference to the root node of the given tree. If
                        the tree is empty then the NullNode is returned.

LeftOf          returns the node that is the left subtree from the given
                        node. If the given node has no left subtree then the NullNode
                        is returned.

RightOf         returns the node that is the right subtree from the given
                        node. If the given node has no right subtree then the NullNode
                        is returned.

IsNull          returns true is the given node is equal to the NullNode and
                        false otherwise.

KeyOf           returns the key value associated with the given node. If the
                        node is empty (i.e., equal to the NullNode) the NullItem is
                        returned instead.

DataOf          returns the data value associated with the given node. If the
                        node is empty (i.e., equal to the NullNode) the NullItem is
                        returned instead.

WeightOf        returns the weight factor for the given node. If the node is
                        null, then a balance of zero (0) is returned.
*)

TYPE  NodePtr;
CONST NullNode = NodePtr(NIL);

TYPE  Weight   = CARDINAL;


PROCEDURE RootOf   (    theTree : Tree    (*--in   *))
                                                            : NodePtr (*--out  *);

PROCEDURE LeftOf   (    theNode : NodePtr (*--in   *))
                                                            : NodePtr (*--out  *);

PROCEDURE RightOf  (    theNode : NodePtr (*--in   *))
                                                            : NodePtr (*--out  *);

PROCEDURE IsNull   (    theNode : NodePtr (*--in   *))
                                                            : BOOLEAN (*--out  *);

PROCEDURE KeyOf    (    theNode : NodePtr (*--in   *))
                                                            : Key     (*--out  *);

PROCEDURE DataOf   (    theNode : NodePtr (*--in   *))
                                                            : Data    (*--out  *);

PROCEDURE WeightOf (    theNode : NodePtr (*--in   *))
                                                            : Weight  (*--out  *);

END BBSUMI.

(*
                                Algorithmic     Code
Operation Name  Complexity      Size
                                (bytes)
TreeError               O(1)             26             Exception Handling Routines
GetHandler              O(1)             42
SetHandler              O(1)             38

Create                  O(1)             88             Constructors
Destroy                 O(1)             44
MakeTree                O(1)            146
Clear                   O(n)            218
Assign                  O(m+n)          514
Insert                  O(log2 n)       848
Remove                  O(log2 n)       732

IsDefined               O(1)             36             Selectors
IsEmpty                 O(1)             74
IsEqual                 O(Min(m,n))     326
ExtentOf                O(n)            148
KeyTypeOf               O(1)             64
DataTypeOf              O(1)             66
IsPresent               O(log2 n)       212

Inorder                 O(n)            146             Passive Iterators
Preorder                O(n)            146
Postorder               O(n)            146

RootOf                  O(1)             50             Active Iterators
LeftOf                  O(1)             50
RightOf                 O(1)             50
IsNull                  O(1)             36
KeyOf                   O(1)             48
DataOf                  O(1)             50
WeightOf                O(1)             50

RaiseErrIn              O(1)             58      Local Routines
NewNode                 O(1)             78
Wt                              O(1)             52
LeftRotation    O(1)            128
RightRotation   O(1)            128
Initialization  O(1)             92

Grand Total                                4550

Table 7.1 Unbounded Weight Balanced Binary Tree Operations Summary
*)
