The Modula-2 Software Component Library

Inhaltsverzeichnis

• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• Appendices.
• A Modula-2 Syntax Diagrams.
• B Standard Modula-2 Routines.
• C Modula-2 Compilers.
• D Module Tables.
• E Import Graphs.