This book is the third and final volume in a series entitled "The Modula-2 Software Component Library." C. Lins' collection of reusable standard software components could be the basis for every programmer's software project in Modula-2. Components that are implementations of commonly used data structures are presented, along with a description of their functionality and efficiency. Moreover, the books provide the background necessary to tailor these components to the specific needs of any Modula-2 environment. For Modula-2 programmers, this series of books could prove as useful and indispensible as the original language reference by Niklaus Wirth. This third volume discusses the concepts of trees and graphs, shows their specifications, and provides implementations for various forms of trees and graphs.
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.
Overview
This book is the third and final volume in a series entitled "The Modula-2 Software Component Library." C. Lins' collection of reusable standard software components could be the basis for every programmer's software project in Modula-2. Components that are implementations of commonly used data structures are presented, along with a description of their functionality and efficiency. Moreover, the books provide the background necessary to tailor these components to the specific needs of any Modula-2 environment. ...