The Modula-2 Software Component Library : Volume 2

This book is the second volume in a series entitled The Modula-2 Software Component Library. Charles 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 every Modula-2 programmer, this series of books could prove as useful and indispensable as the original language reference by Niklaus Wirth. This second volume introduces software modules for lists, queues, and deques.

0 Introduction to Volume 4.- 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 8 References.- References.- 2 Module Guide.- 2.1 Purpose.- 2.2 Characterization of Modules.- 2.3 Module Guide Organization.- 2.4 Sorting.- 2.5 Hash Tables.- 2.5.1 Hash Types.- 2.5.2 Linear Probing Hashing.- 2.5.3 Double Hashing.- 2.5.4 Ordered Hash Table with Double Hashing.- 2.5.5 Double Hashing with Brent’s Reorganization.- 2.5.6 Hash Table with Direct Chaining.- 2.5.7 Hash Table with Linear Hashing.- 2.6 Maps.- 2.6.1 Map Types.- 2.6.2 Map ― Sequential Bounded Managed Iterator (unordered array).- 2.6.3 Map ― Sequential Bounded Managed Iterator (ordered array).- 2.6.4 Map ― Sequential Bounded Managed Iterator (double hashing).- 2.6.5 Map ― Sequential Unbounded Managed Iterator (unordered list).- 2.6.6 Map ― Sequential Unbounded Managed Iterator (linear hashing).- 2.7 Module Names 20 References.- References.- 2 ― Sorting.- 3 Sorting.- 3.1 Sorting: Concepts and Definitions.- 3.2 Applications and Uses.- 3.3 Sorting Interface.- 3.3.1 Sort.- 3.3.2 CompareProc.- 3.3.3 SwapProc.- 3.3.4 AssignProc.- 3.4 Sort Algorithm Taxonomy.- 3.5 Sort Algorithm Interfaces.- 3.5.1 Binary Insertion Sort.- 3.5.2 BSort.- 3.5.3 Exchange Sort.- 3.5.4 Heap Sort.- 3.5.5 Insertion Sort.- 3.5.6 Mean Sort.- 3.5.7 Quicksort.- 3.5.8 Selection Sort.- 3.5.9 Shaker Sort.- 3.5.10 Shell Sort.- 3.5.11 Straight Merge Sort.- 3.6 Empirical Results.- 3.7 Sort Definition Module.- 3.8 Sort Implementation Module.- 3.8.1 Insertion Sort.- 3.8.2 Binary Insertion Sort.- 3.8.3 Selection Sort.- 3.8.4 Shell Sort.- 3.8.5 Heap Sort.- 3.8.6 Quicksort.- 3.8.7 BSort.- 3.8.8 MeanSort.- 3.8.9 Straight Merge Sort.- 3.8.10 Exchange Sort.- 3.8.11 Shaker Sort.- References.- 3 ― Hash Tables.- 4 The Hash Table Abstraction.- 4.1 Concepts and Definitions.- 4.1.1 Hash Tables and Hashing Functions.- 4.1.2 Collisions and Collision Resolution.- 4.1.3 Load Factor.- 4.1.4 Open Hashing.- 4.1.5 Closed Hashing.- 4.2 Applications and Uses.- 4.3 Hash Table Types.- 4.4 Hash Table Constructors.- 4.4.1 Create.- 4.4.2 Destroy.- 4.4.3 Clear.- 4.4.4 Assign.- 4.4.5 Insert.- 4.4.6 Remove.- 4.4.7 Update.- 4.5 Hash Table Selectors.- 4.5.1 IsDefined.- 4.5.2 IsEmpty.- 4.5.3 SizeOf.- 4.5.4 ExtentOf.- 4.5.5 IsPresent.- 4.6 Hash Table Iterators.- 4.6.1 LoopOver.- 4.6.2 Traverse.- 4.6.3 Iterate [Closed Hash Table Form].- 4.6.4 Iterate [Open Hash Table Form].- 4.6.5 IsNull [Open Hash Table Form].- 4.6.6 KeyOf [Open Hash Table Form].- 4.6.7 DataOf [Open Hash Table Form].- 4.6.8 NextOf [Open Hash Table Form].- 4.7 Hash Table Exceptions.- 4.7.1 Duplicate Key.- 4.7.2 Initialization Failed.- 4.7.3 Overflow.- 4.7.4 Undefined.- 4.8 Hash Table Summary.- 4.8.1 Hash Table Operations Summary.- 4.8.2 Hash Table Exceptions Summary.- References.- 5 Linear Probing Hashing.- 5.1 Hash Types Interface.- 5.1.1 Exception Handling.- 5.1.2 Closed Hash Table Entry States.- 5.1.3 Hash Table Procedure Types.- 5.1.4 Hash Types Definition Module.- 5.2 Linear Probing Hashing Interface.- 5.2.1 Type Declarations.- 5.2.2 Exception Handling.- 5.2.3 Hash Table Constructors.- 5.2.4 Hash Table Selectors.- 5.2.5 Hash Table Iterators.- 5.3 Linear Probing Hashing Implementation.- 5.3.1 Internal Representation.- 5.3.2 Exception Handling.- 5.3.3 Local Operations.- 5.3.4 Hash Table Constructors.- 5.3.5 Hash Table Selectors.- 5.3.6 Hash Table Iterators.- 5.3.7 Module Initialization.- References.- 6 Double Hashing.- 6.1 Double Hashing Interface.- 6.1.1 Type Declarations.- 6.1.2 Exception Handling.- 6.1.3 Hash Table Constructors.- 6.1.4 Hash Table Selectors.- 6.1.5 Hash Table Iterators.- 6.2 Double Hashing Implementation.- 6.2.1 Internal Representation.- 6.2.2 Exception Handling.- 6.2.3 Local Operations.- 6.2.4 Hash Table Constructors.- 6.2.5 Hash Table Selectors.- 6.2.6 Hash Table Iterators.- 6.2.7 Module Initialization.- References.- 7 Reorganization Schemes for Double Hashing.- 7.1 Ordered Hashing Definition Module.- 7.1.1 Type Declarations.- 7.1.2 Exception Handling.- 7.1.3 Hash Table Constructors.- 7.1.4 Hash Table Selectors.- 7.1.5 Hash Table Iterators.- 7.2 Ordered Hashing Implementation Module.- 7.2.1 Internal Representation.- 7.2.2 Exception Handling.- 7.2.3 Local Operations.- 7.2.4 Hash Table Constructors.- 7.2.5 Hash Table Selectors.- 7.2.6 Hash Table Iterators.- 7.2.7 Module Initialization.- 7.3 Brent’s Reorganization Definition Module.- 7.3.1 Type Declarations.- 7.3.2 Exception Handling.- 7.3.3 Hash Table Constructors.- 7.3.4 Hash Table Selectors.- 7.3.5 Hash Table Iterators.- 7.4 Brent’s Reorganization Implementation Module.- 7.4.1 Internal Representation.- 7.4.2 Exception Handling.- 7.4.3 Local Operations.- 7.4.4 Hash Table Constructors.- 7.4.5 Hash Table Selectors.- 7.4.6 Hash Table Iterators.- 7.4.7 Module Initialization.- References.- 8 Direct Chaining Hashing.- 8.1 Direct Chaining Interface.- 8.1.1 Type Declarations.- 8.1.2 Exception Handling.- 8.1.3 Hash Table Constructors.- 8.1.4 Hash Table Selectors.- 8.1.5 Hash Table Iterators.- 8.2 Direct Chaining Implementation.- 8.2.1 Internal Representation.- 8.2.2 Exception Handling.- 8.2.3 Local Operations.- 8.2.4 Hash Table Constructors.- 8.2.5 Hash Table Selectors.- 8.2.6 Hash Table Iterators.- 8.2.7 Module Initialization.- References.- 9 Linear Hashing.- 9.1 Linear Hashing Interface.- 9.1.1 Type Declarations.- 9.1.2 Exception Handling.- 9.1.3 Hash Table Constructors.- 9.1.4 Hash Table Selectors.- 9.1.5 Hash Table Iterators.- 9.2 Linear Hashing Implementation.- 9.2.1 Internal Representation.- 9.2.2 Exception Handling.- 9.2.3 Local Operations.- 9.2.4 Hash Table Constructors.- 9.2.5 Hash Table Selectors.- 9.2.6 Hash Table Iterators.- 9.2.7 Module Initialization.- References.- 4 ― Maps.- 10 Map Abstraction.- 10.1 Concepts and Definitions 241 10.1.1 Static vs. Dynamic Mappings.- 10.2 Applications and Uses.- 10.3 Map Constructors.- 10.3.1 Create.- 10.3.2 Destroy.- 10.3.3 Clear.- 10.3.4 Assign.- 10.3.5 Bind.- 10.3.6 Unbind.- 10.4 Map Selectors.- 10.4.1 IsDefined.- 10.4.2 IsEmpty.- 10.4.3 IsEqual.- 10.4.4 ExtentOf.- 10.4.5 DomainOf.- 10.4.6 RangeOf.- 10.4.7 IsBound.- 10.4.8 BoundTo.- 10.4.9 IsBoundTo.- 10.5 Map Iterators.- 10.5.1 LoopOver.- 10.5.2 LoopChange.- 10.5.3 Traverse.- 10.5.4 TraverseChange.- 10.6 Map Exceptions.- 10.6.1 Initialization Failed.- 10.6.2 Not Bound.- 10.6.3 Overflow.- 10.6.4 Type Error.- 10.6.5 Undefined.- 10.7 Map Summary.- 10.7.1 Map Operations Summary.- 10.7.2 Map Exceptions Summary.- References.- 11 The Bounded Map.- 11.1 Map Types Interface.- 11.2 Bounded Map Interface.- 10.2.1 Type Declarations.- 10.2.2 Exception Handling.- 10.2.3 Map Constructors.- 10.2.4 Map Selectors.- 10.2.5 Map Iterators.- 11.3 Bounded Map Unordered Array Implementation.- 11.3.1 Internal Representation.- 11.3.2 Exception Handling.- 11.3.3 Local Operations.- 11.3.4 Map Constructors.- 11.3.5 Map Selectors.- 11.3.6 Map Iterators.- 11.3.7 Module Initialization.- 11.4 Bounded Map Ordered Array Implementation.- 11.4.1 Search.- 11.4.2 Bind.- 11.4.3 Unbind.- 11.4.4 IsEqual.- References.- 12 The Unbounded Map.- 12.1 Unbounded Map Interface.- 12.1.1 Type Declarations.- 12.1.2 Exception Handling.- 12.1.3 Map Constructors.- 12.1.4 Map Selectors.- 12.1.5 Map Iterators.- 12.2 Unbounded Map Unordered List Implementation.- 12.2.1 Internal Representation.- 12.2.2 Exception Handling.- 12.2.3 Local Operations.- 12.2.4 Map Constructors.- 12.2.5 Map Selectors.- 12.2.6 Map Iterators.- 12.2.7 Module Initialization.- References.- 13 Example Program.- 13.1 EBNF Scanner Definition Module.- 13.2 EBNF Scanner Implementation Module.- 13.3 EBNF Symbol Table Definition.- 13.4 EBNF Symbol Table Implementation.- 13.5 EBNF Module.- References.- Appendices.- A Modula-2 Syntax Diagrams.- B Standard Modula-2 Routines.- C Modula-2 Compilers.- D Module Tables.- E Import Graphs.