The Modula-2 Software Component Library : Volume 3

2 Source Code Availability All of the source code in this volume, and some that is not, is available from the author for $20. The author is also interested in learning of any errors that may be found, though care has been taken in the construction of the modules to minimize the possibility of their occurence. Any other comments, suggestions, recommenda­ tions, questions, or experiences with the use of these modules would also be of interest. The reader may contact the author via the publisher at the following address: C. Lins: Modula-2 Source Code c/o Springer-Verlag 815 De La Vina Street Santa Barbara, CA 93101 USA As of February 1989, source code is available on two 3. 5" Macintosh diskettes (800K HFS format) for Bob Campbell's Modula-2 compiler for MPW(formerly TML Modula-2) and the MacMETH Modula-2 compiler from ETH Zurich. The author intends to port this software to both the SemperSoft and MetCom Modula- 2 compilers on the Macintosh. For the IBM PC (and compatibles) the software is available for TopSpeed Modula-2 (a product of JPI). The source code will soon be converted to work with Logitech's Modula-2 compiler as well as Stony Brook's Modula-2. Please mention your hardware platform as well as the volume(s) in which you are interested Development Environment The software for this volume was developed using the MPW (Macintosh™ Programmer' s Workshop) version 3. 0 and Bob Campbell's Modula-2 compiler ver­ sion 1. 4d7.

0 Introduction to Volume 3.- 1 ― Preliminaries.- 1 Specification.- 1.1 Specification of Procedure Abstractions.- 1.1.1 Header Section.- 1.1.2 Requires Section.- 1.1.3 Where Section.- 1.1.4 Modifies Section.- 1.1.5 Effects Section.- 1.1.6 Signals Section.- 1.2 Specification of Data Abstractions.- 1.3 Special Symbols.- References.- 2 Module Guide.- 2.1 Purpose.- 2.2 Characterization of Modules.- 2.3 Module Guide Organization.- 2.4 Binary Trees.- 2.4.1 Tree Types.- 2.4.2 AVL Tree ― Sequential Unbounded Managed Iterator.- 2.4.3 BB Tree ― Sequential Unbounded Managed Iterator.- 2.4.4 Binary Tree ― Sequential Bounded Managed Iterator.- 2.4.5 Binary Tree ― Sequential Unbounded Managed Iterator.- 2.4.6 IPB Tree ― Sequential Unbounded Managed Iterator.- 2.5 Graphs.- 2.5.1 Graph Types.- 2.5.2 Graph ― Directed Sequential Bounded Managed Iterator.- 2.5.3 Graph ― Directed Sequential Unbounded Managed Iterator.- 2.5.4 Graph ― Undirected Sequential Bounded Managed Iterator.- 2.5.5 Graph ― Undirected Sequential Unbounded Managed Iterator.- 2.6 Graph Utilities.- 2.7 Module Names.- References.- 2 ― Trees.- 3 Tree Abstraction.- 3.1 Concepts and Definitions.- 3.1.1 Basic Tree Definitions.- 3.1.2 Attributes of Nodes.- 3.1.3 Relationships Between Nodes.- 3.1.4 Attributes of Trees.- 3.1.5 Kinds of Trees.- 3.1.6 Tree Traversals.- 3.1.6.1 General Tree Traversals.- 3.1.6.2 Binary Tree Traversals.- 3.1.7 Forests.- 3.2 Applications and Uses.- 3.3 Binary Search Tree Operations.- 3.3.1 Constructors.- 3.3.1.1 Create.- 3.3.1.2 Destroy.- 3.3.1.3 Clear.- 3.3.1.4 Assign.- 3.3.1.5 Insert.- 3.3.1.6 MakeTree.- 3.3.1.7 Remove.- 3.3.2 Selectors.- 3.3.2.1 IsDefined.- 3.3.2.2 IsEmpty.- 3.3.2.3 IsEqual.- 3.3.2.4 ExtentOf.- 3.3.2.5 IsPresent.- 3.3.3 Passive Iterators.- 3.3.3.1 Preorder.- 3.3.3.2 Inorder.- 3.3.3.3 Postorder.- 3.3.4 Active Iterators.- 3.3.4.1 RootOf.- 3.3.4.2 LeftOf.- 3.3.4.3 RightOf.- 3.3.4.4 IsNull.- 3.3.4.5 KeyOf.- 3.3.4.6 DataOf.- 3.4 Balanced Binary Trees.- 3.4.1 Height-Balanced (AVL) Trees.- 3.4.2 Weight-Balanced (BB) Trees.- 3.4.3 Path-Balanced (IPB) Trees.- 3.4.4 Rotations.- 3.5 Tree Exceptions.- 3.5.1 Initialization Failed.- 3.5.2 Overflow.- 3.5.3 Tree is Null.- 3.5.4 Type Error.- 3.5.5 Undefined.- 3.6 Summary.- 3.6.1 Operations Summary.- 3.6.2 Exceptions Summary.- References.- 4 The Unbounded Binary Tree.- 4.1 Tree Types Module.- 4.1.1 Tree Operations.- 4.1.2 Tree Exceptions.- 4.1.3 Tree Types and Procedure Types.- 4.2 Unbounded Binary Search Tree Interface.- 4.2.1 Type Declarations.- 4.2.2 Exception Handling.- 4.2.3 Constructors.- 4.2.4 Selectors.- 4.2.5 Passive Iterators.- 4.2.6 Active Iterators.- 4.3 Unbounded Binary Search Tree Implementation.- 4.3.1 Internal Representation.- 4.3.2 Exception Handling.- 4.3.3 Local Operations.- 4.3.4 Constructors.- 4.3.5 Selectors.- 4.3.6 Passive Iterators.- 4.3.7 Active Iterators.- 4.3.8 Module Initialization.- 4.4 Unbounded Binary Search Tree Utilities Interface.- 4.4.1 Utility Selectors.- 4.4.2 Debugging Iterators.- 4.5 Unbounded Binary Search Tree Utilities Implementation.- 4.5.1 Utility Selectors.- 4.5.2 Debugging Iterators.- References.- 5. The Bounded Binary Tree.- 5.1 Bounded Binary Search Tree Interface.- 5.1.1 Type Declarations.- 5.1.2 Exception Handling.- 5.1.3 Constructors.- 5.1.4 Selectors.- 5.1.5 Passive Iterators.- 5.1.6 Active Iterators.- 5.2 Bounded Binary Search Tree Implementation.- 5.2.1 Internal Representation.- 5.2.2 Exception Handling.- 5.2.3 Free List Management.- 5.2.4 Local Operations.- 5.2.5 Constructors.- 5.2.6 Selectors.- 5.2.7 Passive Iterators.- 5.2.8 Active Iterators.- 5.2.9 Module Initialization.- References.- 6 The Unbounded AVL Tree.- 6.1 Unbounded AVL Tree Interface.- 6.1.1 Type Declarations.- 6.1.2 Exception Handling.- 6.1.3 Constructors.- 6.1.4 Selectors.- 6.1.5 Passive Iterators.- 6.1.6 Active Iterators.- 6.2 Unbounded AVL Tree Implementation.- 6.2.1 Internal Representation.- 6.2.2 Exception Handling.- 6.2.3 Local Operations.- 6.2.4 Constructors.- 6.2.5 Selectors.- 6.2.6 Passive Iterators.- 6.2.7 Active Iterators.- 6.2.8 Module Initialization.- 6.3 Unbounded AVL Tree Utilities Interface.- 6.3.1 Utility Selectors.- 6.3.2 Debugging Iterators.- 6.4 Unbounded AVL Tree Utilities Implementation.- 6.4.1 Utility Selectors.- 6.4.2 Debugging Iterators.- References.- 7 The Unbounded BB Tree.- 7.1 Unbounded BB Tree Interface.- 7.1.1 Type Declarations.- 7.1.2 Exception Handling.- 7.1.3 Constructors.- 7.1.4 Selectors.- 7.1.5 Passive Iterators.- 7.1.6 Active Iterators.- 7.2 Unbounded BB Tree Implementation.- 7.2.1 Internal Representation.- 7.2.2 Exception Handling.- 7.2.3 Local Operations.- 7.2.4 Constructors.- 7.2.5 Selectors.- 7.2.6 Passive Iterators.- 7.2.7 Active Iterators.- 7.2.8 Module Initialization.- References.- 8 The Unbounded k-Balanced Binary Tree.- 8.1 Unbounded k-Balanced Binary Tree Interface.- 8.1.1 Type Declarations.- 8.1.2 Exception Handling.- 8.1.3 Constructors.- 8.1.4 Selectors.- 8.1.5 Passive Iterators.- 8.1.6 Active Iterators.- 8.2 Unbounded k-Balanced Binary Tree Implementation.- 8.2.1 Internal Representation.- 8.2.2 Exception Handling.- 8.2.3 Local Operations.- 8.2.4 Constructors.- 8.2.5 Selectors.- 8.2.6 Passive Iterators.- 8.2.7 Active Iterators.- 8.2.8 Module Initialization.- 8.3 Unbounded k-Balanced Binary Tree Utilities Interface.- 8.3.1 Utility Selectors.- 8.3.2 Debugging Iterators.- 8.4 Unbounded k-Balanced Binary Tree Utilities Implementation.- 8.4.1 Utility Selectors.- 8.4.2 Debugging Iterators.- References.- 3 Graphs.- 9 Graph Abstraction.- 9.1 Concepts and Definitions.- 9.1.1 Directed Graphs.- 9.1.2 Undirected Graphs.- 9.1.3 Labeled and Weighted Graphs.- 9.2 Applications and Uses.- 9.3 Directed Graph Specifications.- 9.3.1 Directed Graph Types.- 9.3.2 Directed Graph Constructors.- 9.3.2.1 Create.- 9.3.2.2 Destroy.- 9.3.2.3 Clear.- 9.3.2.4 Assign.- 9.3.2.5 Insert.- 9.3.2.6 Remove.- 9.3.2.7 SetLabel.- 9.3.2.8 Link.- 9.3.2.9 Unlink.- 9.3.2.10 SetAttribute.- 9.3.3 Directed Graph Selectors.- 9.3.3.1 IsDefined.- 9.3.3.2 IsEmpty.- 9.3.3.3 OrderOf.- 9.3.3.4 SizeOf.- 9.3.3.5 OutDegree.- 9.3.3.6 InDegree.- 9.3.3.7 LabelOf.- 9.3.3.8 IsVertex.- 9.3.3.9 GraphOf.- 9.3.3.10 IsEdge.- 9.3.3.11 AttributeOf.- 9.3.3.12 InitialOf.- 9.3.3.13 FinalOf.- 9.3.4 Directed Graph Passive Iterators.- 9.3.4.1 Traverse Vertices.- 9.3.4.2 TraverseEdges.- 9.3.4.3 Iterate.- 9.3.4.4 LoopVertices.- 9.3.4.5 LoopEdges.- 9.3.4.6 Looplterate.- 9.3.5 Directed Graph Active Iterators.- 9.3.5.1 FirstVertex.- 9.3.5.2 NextVertex.- 9.3.5.3 FirstEdge.- 9.3.5.4 NextVertex.- 9.4 Undirected Graph Specifications.- 9.4.1 Undirected Graph Constructors.- 9.4.1.1 Remove.- 9.4.1.2 Link.- 9.4.2 Undirected Graph Selectors.- 9.4.2.1 DegreeOf.- 9.4.2.2 FirstOf.- 9.4.2.3 SecondOf.- 9.4.2.4 IncidentOn.- 9.4.3 Undirected Graph Passive Iterators.- 9.5 Graph Exceptions.- 9.5.1 EdgeIsNull.- 9.5.2 EdgeNotInGraph.- 9.5.3 Initialization Failed.- 9.5.4 Overflow.- 9.5.5 Undefined.- 9.5.6 VertexIsNull.- 9.5.7 VertexNotInGraph.- 9.6 Graph Utilities.- 9.6.1 BreadthFirstSearch.- 9.6.2 DepthFirstSearch.- 9.6.3 HasSelfLoops.- 9.6.4 IsIsolated.- 9.6.5 IsReachable.- 9.6.6 IsTerminal.- 9.6.7 MaxDegree.- 9.6.7 MinDegree.- 9.7 Summary.- 9.7.1 Directed Graph Operations Summary.- 9.7.2 Directed Graph Exceptions Summary.- 9.7.3 Undirected Graph Operations Summary.- 9.7.4 Undirected Graph Exceptions Summary.- 9.7.5 Graph Utility Operations Summary.- 9.7.6 Graph Utility Exceptions Summary.- References.- 10 The Unbounded Directed Graph.- 10.1 Graph Types Interface.- 10.2 Unbounded Directed Graph Interface.- 10.2.1 Type Declarations.- 10.2.2 Exception Handling.- 10.2.3 Graph Constructors.- 10.2.4 Vertex Constructors.- 10.2.5 Edge Constructors.- 10.2.6 Graph Selectors.- 10.2.7 Vertex Selectors.- 10.2.8 Edge Selectors.- 10.2.9 Passive Iterators.- 10.2.10 Active Iterators.- 10.3 Unbounded Directed Graph Implementation.- 10.3.1 Internal Representation.- 10.3.2 Exception Handling.- 10.3.3 Local Routines.- 10.3.4 Graph Constructors.- 10.3.5 Vertex Constructors.- 10.3.6 Edge Constructors.- 10.3.7 Graph Selectors.- 10.3.8 Vertex Selectors.- 10.3.9 Edge Selectors.- 10.3.10 Passive Iterators.- 10.3.11 Active Iterators.- 10.3.12 Module Initialization.- References.- 11 The Bounded Directed Graph.- 11.1 Bounded Directed Graph Interface.- 11.1.1 Type Declarations.- 11.1.2 Exception Handling.- 11.1.3 Graph Constructors.- 11.1.4 Vertex Constructors.- 11.1.5 Edge Constructors.- 11.1.6 Graph Selectors.- 11.1.7 Vertex Selectors.- 11.1.8 Edge Selectors.- 11.1.9 Passive Iterators.- 11.1.10 Active Iterators.- 11.2 Bounded Directed Graph Implementation.- 11.2.1 Internal Representation.- 11.2.2 Exception Handling.- 11.2.3 Local Routines.- 11.2.4 Graph Constructors.- 11.2.5 Vertex Constructors.- 11.2.6 Edge Constructors.- 11.2.7 Graph Selectors.- 11.2.8 Vertex Selectors.- 11.2.9 Edge Selectors.- 11.2.10 Passive Iterators.- 11.2.11 Active Iterators.- 11.2.12 Module Initialization.- References.- 12 The Unbounded Undirected Graph.- 12.1 Unbounded Undirected Graph Interface.- 12.1.1 Type Declarations.- 12.1.2 Exception Handling.- 12.1.3 Graph Constructors.- 12.1.4 Vertex Constructors.- 12.1.5 Edge Constructors.- 12.1.6 Graph Selectors.- 12.1.7 Vertex Selectors.- 12.1.8 Edge Selectors.- 12.1.9 Passive Iterators.- 12.1.10 Active Iterators.- 12.2 Unbounded Undirected Graph Implementation.- 12.2.1 Internal Representation.- 12.2.2 Exception Handling.- 12.2.3 Local Routines.- 12.2.4 Graph Constructors.- 12.2.5 Vertex Constructors.- 12.2.6 Edge Constructors.- 12.2.7 Graph Selectors.- 12.2.8 Vertex Selectors.- 12.2.9 Edge Selectors.- 12.2.10 Passive Iterators.- 12.2.11 Active Iterators.- 12.2.12 Module Initialization.- References.- 13 Graph Utilities.- 13.1 DigraphSUMI Utilities Interface.- 13.1.1 Graph Selector Utilities.- 13.1.2 Vertex Selector Utilities.- 13.1.3 Graph Traversal Utilities.- 13.2 DigraphSUMI Utilities Implementation.- 13.2.1 Graph Selector Utilities.- 13.2.2 Vertex Selector Utilities.- 13.2.3 Graph Traversal Utilities.- References.- Appendices.- A Modula-2 Syntax Diagrams.- B Standard Modula-2 Routines.- C Modula-2 Compilers.- D Module Tables.- E Import Graphs.