The Modula-2 Software Component Library: Volume 2

ISBN-13: 9781468463736 / Angielski / Miękka / 2012 / 368 str.

Charles Lins

Opis

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.

Spis treści

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.