The Modula-2 Software Component Library : Volume 4

Source Code Availability All of the source code found in this volume, and some that is not, is available from the author at a nominal fee. The author is interested in learning of any errors that may be found, though care has been taken in the construction of the modules to minimize these. The author is also interested in other comments, suggestions, recommendations, questions or experiences with the use of these modules. Contact the author through the following address: Modula-2 Software c/o Springer-Verlag 815 De La Vina St. Santa Barbara, CA 93101 As of February 1988, source code is available on 3.5" Macintosh diskettes (800K HFS format) for the TML Modula-2 compiler for MPW and the Mac­ METH Modula-2 compiler from ETH Ziirich. 1 Specification Requirements for specification of procedure and data abstractions were previously covered in Volume 1, Chapter 2. A summary is provided of the specification for­ mat used in this book. The format is adapted from that Guttag and Liskov [10] developed for the CLU language. It consists of relatively few constructs, is semi­ formal by providing a rigorous definition of the syntax and semantics of opera­ tions, and it provides powerful facilities for defining abstract data types. 1.1 Specification of Procedure Abstractions Specification of a procedure requires a full description of syntax and semantics. Syntax the name of the procedure by name, the name and type of each ar­ gument or result, and the order in which the arguments and results occur.

Volume 2 Table of Contents.- 0 Introduction to Volume 2.- 1 Specification.- 1.1 Specification of Procedure Abstractions.- 1.2 Specifying Data Abstractions.- 1.3 Special Symbols.- References.- 2 Module Guide.- 2.1 Purpose.- 2.2 Lists.- 2.2.1 List Enumerations.- 2.2.2 Doubly-Linked List.- 2.2.3 Singly-Linked Lists.- 2.2.4 Singly-Linked List Utilities.- 2.3 Queues.- 2.3.1 Queue Enumerations.- 2.3.2 Non-Priority Balking Sequential Queue.- 2.3.3 Non-Priority Non-Balking Sequential Queue.- 2.3.4 Priority Balking Sequential Queue.- 2.4 Deques.- 2.4.1 Deque Enumerations.- 2.4.2 Non-Priority Balking Sequential Deque.- 2.4.3 Non-Priority Non-Balking Sequential Deque.- 2.4.4 Priority Balking Sequential Deque.- 2.5 Module Names 23 References.- 3 The List Abstraction.- 3.1 Lists: Concept and Definitions.- 3.2 Selected Summary of List Applications and Uses.- 3.3 List Constructor Operations.- 3.3.1 Create.- 3.3.2 Destroy.- 3.3.3 Clear.- 3.3.4 Assign.- 3.3.5 Insert.- 3.3.6 SetList.- 3.3.7 Setltem.- 3.3.8 SetNext.- 3.3.9 SetPrev.- 3.4 List Selector Operations.- 3.4.1 IsDefined.- 3.4.2 IsEmpty.- 3.4.3 IsEqual.- 3.4.4 Length of.- 3.4.5 Gefltem.- 3.4.6 GetNext.- 3.4.7 GetPrev.- 3.5 List Exceptions.- 3.5.1 InitFailed.- 3.5.2 Overflow.- 3.5.3 List Is Null.- 3.5.4 Undefined.- 3.6 Summary.- 3.6.1 Operations Summary.- 3.6.2 Exceptions Summary.- References.- 4 Singly-Linked Unbounded List.- 4.1 List Enumerations.- 4.2 Singly-Linked Unbounded List Interface.- 4.2.1 Type Declarations.- 4.2.2 Exceptions.- 4.2.3 Constructors.- 4.2.4 Selectors.- 4.3 Singly-Linked Unbounded List Implementation.- 4.3.1 Internal Singly-Linked Unbounded List Representation.- 4.3.2 Exceptions.- 4.3.3 Constructors.- 4.3.4 Selectors.- 4.3.5 Module Initialization.- References.- 5 The Doubly-Linked Unbounded List.- 5.1 Doubly-Linked Unbounded List Interface.- 5.1.1 Type Declarations.- 5.1.2 Exceptions.- 5.1.3 Constructors.- 5.1.4 Selectors.- 5.2 Doubly-Linked Unbounded List Implementation.- 5.2.1 Internal Doubly-Linked Unbounded List Representation.- 5.2.2 Exceptions.- 5.2.3 Constructors.- 5.2.4 Selectors.- 5.2.5 Module Initialization.- References.- 6 The Singly-Linked Bounded List.- 6.1 Singly-Linked Bounded List Interface.- 6.1.1 Type Declarations.- 6.1.2 Exceptions.- 6.1.3 Constructors.- 6.1.4 Selectors.- 6.2 Singly-Linked Bounded List Implementation.- 6.2.1 Internal Singly-Linked Bounded List Representation.- 6.2.2 Exceptions.- 6.2.3 Pool Constructors.- 6.2.4 List Constuctors.- 6.2.5 Selectors.- 6.2.6 Module Initialization.- References.- 7 The Doubly-Linked Bounded List.- 7.1 Doubly-Linked Bounded List Interface.- 7.1.1 Type Declarations.- 7.1.2 Exceptions.- 7.1.3 Constructors.- 7.1.4 Selectors.- 7.2 Doubly-Linked Bounded List Implementation.- 7.2.1 Internal Doubly-Linked Bounded List Representation.- 7.2.2 Exceptions.- 7.2.3 Pool Constructors.- 7.2.4 List Constructors.- 7.2.5 Selectors.- 7.2.6 Module Initialization.- References.- 8 List Utilities.- 8.1 Sequential Search Utilities ― Interface.- 8.1.1 PrimarySearch.- 8.1.2 SecondarySearch.- 8.1.3 Self-Organizing Sequential Search ― MoveToFront.- 8.1.4 Self-Organizing Sequential Search ― Transpose.- 8.2 Sequential Search Utilities ― Implementation.- 8.2.1 PrimarySearch.- 8.2.2 SecondarySearch.- 8.2.3 Self-Organizing Sequential Search ― MoveToFront.- 8.2.4 Self-Organizing Sequential Search ― Transpose.- 8.3 List Utilities ― Interface.- 8.3.1 Type Declarations.- 8.3.2 Constructors.- 8.3.3 Selectors.- 8.4 List Utilités ― Implementation.- 8.4.1 Constructors.- 8.4.2 Selectors.- References.- 9 The Queue and Deque Abstractions.- 9.1 Queues and Deques: Concept and Definitions.- 9.1.1 Queue.- 9.1.2 Deque.- 9.1.3 Priority Queue/Deque.- 9.1.4 Balking Queue/Deque.- 9.2 Summary of Queue/Deque Applications and Uses.- 9.3 Queue Constructor Operations.- 9.3.1 Create.- 9.3.2 Destroy.- 9.3.3 Clear.- 9.3.4 Assign.- 9.3.5 Arrive.- 9.3.6 Depart.- 9.4 Queue Selector Operations.- 9.4.1 IsDefined.- 9.4.2 IsEmpty.- 9.4.3 IsEqual.- 9.4.4 LengthOf.- 9.4.5 FrontOf.- 9.5 Queue Iterator Operations.- 9.5.1 LoopOver.- 9.5.2 Traverse.- 9.6 Deque Operations.- 9.6.1 Arrive.- 9.6.2 Depart.- 9.6.3 BackOf.- 9.6.4 EndOf.- 9.6.5 LoopOver.- 9.6.6 Traverse.- 9.7 Priority Queue/Deque Operations.- 9.7.1 Create (Queue).- 9.7.2 Create (Deque).- 9.8 Balking Queue/Deque Operations.- 9.8.1 Leave (Queue).- 9.8.2 Leave (Deque).- 9.9 Queue/Deque Exceptions.- 9.9.1 InitFailed.- 9.9.2 Not Found.- 9.9.3 Overflow.- 9.9.4 Underflow.- 9.9.5 Undefined.- 9.10 Summary.- 9.10.1 Queue Operations Summary.- 9.10.2 Queue Exceptions Summary.- 9.10.3 Deque Operations Summary.- 9.10.4 Deque Exceptions Summary.- 9.10.5 Priority Queue Operations Summary.- 9.10.6 Balking Queue Operations Summary.- 9.10.7 Balking Queue Exceptions Summary.- References.- 10 The Bounded Queue.- 10.1 Queue Enumerations.- 10.2 Bounded Queue Interface.- 10.2.1 Type Declarations.- 10.2.2 Exceptions.- 10.2.3 Constructors.- 10.2.4 Selectors.- 10.2.5 Iterators.- 10.3 Bounded Queue Implementation.- 10.3.1 Internal Bounded Queue Representation.- 10.3.2 Exceptions.- 10.3.3 Constructors.- 10.3.4 Selectors.- 10.3.5 Iterators.- 10.3.6 Module Initialization.- 10.4 The Bounded Balking Queue.- 10.4.1 Bounded Balking Queue Interface.- 10.4.2 Bounded Balking Queue Implementation.- References.- 11 The Unbounded Queue.- 11.1 Unbounded Queue Interface.- 11.1.1 Type Declarations.- 11.1.2 Exceptions.- 11.1.3 Constructors.- 11.1.4 Selectors.- 11.1.5 Iterators.- 11.2 Unbounded Queue Implementation.- 11.2.1 Internal Unbounded Queue Representation.- 11.2.2 Exceptions.- 11.2.3 Constructors.- 11.2.4 Selectors.- 11.2.5 Iterators.- 11.2.6 Module Initialization.- 11.3 The Unbounded Balking Queue.- 11.3.1 Unbounded Balking Queue Interface.- 11.3.2 Unbounded Balking Queue Implementation.- References.- 12 The Bounded Priority Queue.- 12.1 Bounded Balking Priority Queue Interface.- 12.1.1 Type Declarations.- 12.1.2 Exceptions.- 12.1.3 Constructors.- 12.1.4 Selectors.- 12.1.5 Iterators.- 12.2 Bounded Balking Priority Queue Implementation.- 12.2.1 Internal Bounded Priority Queue Representation.- 12.2.2 Exceptions.- 12.2.3 Constructors.- 12.2.4 Selectors.- 12.2.5 Iterators.- 12.2.6 Module Initialization.- 12.3 Bounded Priority Queue Implementation Using Heaps.- 12.3.1 Internal Bounded Priority Queue Representation.- References.- 13 The Unbounded Priority Queue.- 13.1 Unbounded Balking Priority Queue Interface.- 13.1.1 Type Declarations.- 13.1.2 Exceptions.- 13.1.3 Constructors.- 13.1.4 Selectors.- 13.1.5 Iterators.- 13.2 Unbounded Balking Priority Queue Implementation.- 13.2.1 Internal Unbounded Priority Queue Representation.- 13.2.2 Exceptions.- 13.2.3 Constructors.- 13.2.4 Selectors.- 13.2.5 Iterators.- 13.2.6 Module Initialization.- References.- 14 The Bounded Deque.- 14.1 Bounded Deque Interface.- 14.1.1 Type Declarations.- 14.1.2 Exceptions.- 14.1.3 Constructors.- 14.1.4 Selectors.- 14.1.5 Iterators.- 14.2 Bounded Deque Implementation.- 14.2.1 Internal Bounded Deque Representation.- 14.2.2 Exceptions.- 14.2.3 Constructors.- 14.2.4 Selectors.- 14.2.5 Iterators.- 14.2.6 Module Initialization.- 14.3 The Balking Bounded Deque.- 14.3.1 Constructors.- 14.3.2 Selectors.- 14.3.3 Balking Bounded Deque Implementation.- References.- 15 The Unbounded Deque.- 15.1 Unbounded Deque Interface.- 15.2 Unbounded Deque Implementation.- 15.2.1 Internal Unbounded Deque Representation.- 15.2.2 Exceptions.- 15.2.3 Constructors.- 15.2.4 Selectors.- 15.2.5 Iterators.- 15.2.6 Module Initialization.- 15.3 Unbounded Balking Deque Implementation.- References.- 16 The Bounded Priority Deque.- 16.1 Bounded Priority Deque Interface.- 16.1.1 Type Declarations.- 16.1.2 Exceptions.- 16.1.3 Constructors.- 16.1.4 Selectors.- 16.1.5 Iterators.- 16.2 Bounded Priority Deque Implementation.- 16.2.1 Internal Bounded Priority Balking Deque Representation.- 16.2.2 Exceptions.- 16.2.3 Constructors.- 16.2.4 Selectors.- 16.2.5 Iterators.- 16.2.6 Module Initialization.- References.- 17 The Unbounded Priority Balking Deque.- 17.1 Unbounded Priority Balking Deque Interface.- 17.1.1 Type Declarations.- 17.1.2 Exceptions.- 17.1.3 Constructors.- 17.1.4 Selectors.- 17.1.5 Iterators.- 17.2 Unbounded Priority Balking Deque Implementation.- 17.2.1 Internal Unbounded Balking Priority Deque Representation.- 17.2.2 Exceptions.- 17.2.3 Constructors.- 17.2.4 Selectors.- 17.2.5 Iterators.- 17.2.6 Module Initialization.- References.- Appendices.- A Modula-2 Syntax Diagrams.- B Module Import Graph Diagrams.- C Module Index.