TRESBMIU.DEF

(*
5.3 Bounded Binary Search Tree Utilities

This module provides the facility for displaying the hierarchy of
a binary tree on the terminal while presenting an example using
active iterators. Printing the tree is also possible depending
on whether standard output has been so redirected.
*)

DEFINITION MODULE TreSBMIU;
(*==============================================================
    Version  : V2.01  08 December 1989.
    Compiler : JPI TopSpeed Modula-2
    Component: Binary Tree SBMI Utilities - Print Tree Tool

    REVISION HISTORY
    v1.00  18 May 1988  C. Lins
      Initial implementation for TML Modula-2.
    v1.01  01 Oct 1988  C. Lins
      Cleanup of comments.
          Changed PrintTree is use a single procedure parameter.
          Added HeightOf selector.
    v1.02  29 Jan 1989  C. Lins
          Changed to use Key and Data aliases for generic Items.
    v2.00  08 Oct 1989  C. Lins
          Created generic pc version
    v2.01  08 Dec 1989  I.S.C. Houston.
          Adapted to JPI Compiler:
          Used type transfer functions instead of VAL.
          Used shortened library module names for DOS and OS/2.

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

FROM TreeTypes IMPORT
    (*--Type*) Key, Data;

FROM TreSBMI IMPORT
    (*--Type*) Tree;


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

(*
6.3.1 Utility Selectors

HeightOf returns the height of the given tree.
*)

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

(*
5.3.2 Debugging Iterators

PrintTree iterates over the given tree such that the nodes may be
printed. Trees are normally displayed with the root at the top and
the leaves at the bottom. To simplify the printing process, PrintTree
displays the tree rotated 90Æ to the left. Thus the root is shown at
the left of the page/screen with the leaves at the right. Furthermore,
the left branches are shown towards the bottom of the display and the
right branches at the top. The PrintProc routine is responsible for
indenting the display appropriately based on the level parameter.
*)

TYPE  Level      = CARDINAL;
TYPE  PrintProc  = PROCEDURE (Level, Key, Data);

PROCEDURE PrintTree (    theTree: Tree       (*--in   *);
                         print  : PrintProc  (*--in   *));

END TreSBMIU.

(*

                                Algorithmic     Code
Operation Name  Complexity      Size
                                (bytes)
HeightOf             O(n)            206
PrintTree            O(n)            208
Initialization       O(1)             48

Grand Total                                     462

Table 5.2 Bounded Binary Search Tree Utilities Summary

1       With debugging labels turned off (the -gx option of the
        TML compiler) the code sizes are slightly less than
        the figures given above.
*)