Springer Compass International Series Editors Steven S. Muchnick Peter Schnupp c. Lins The Modula-2 Software Component Library Volume 2 With 35 Illustrations Springer-Verlag New York Berlin Heidelberg London Paris Tokyo Charles Lins, Apple Computer, Inc., Cupertino, CA 95014, USA Editors Steven S. Muchnick, SUN Microsystems, Inc., Mountain View, CA 94043, USA Peter Schnupp, InterFace Computer GmbH, D-8000 Miinchen 81, West Germany All of the Modula-2 software in this book was written by C. Lins. Copyright © 1988 by Charles A. Lins, 20525 Mariani Ave., Mail Stop 41K, Cupertino, CA 95014, USA. MacMETH, by Werner Heiz, Neugasse 71, CH-8005, Ziirich, Switzerland. Copyright © 1986, Institut fUr Informatik Eidgenossische Technische Hochschule (ETH) Ziirich, Clausiusstr. 55, CH-8096 Ziirich, Switzerland. TML Modula-2 Compiler, by Robert R. Campbell. Copyright © 1987, Robert R. Campbell. Ada is a registered trademark of the U.S. Government (Ada Joint Program Office). Apple, the Apple logo, AppleTalk, LaserWriter, and Lisa are registered trademarks of Apple Computer, Inc. ImageWriter, MacDraw, Macintosh, MacPaint, and MacWrite are trademarks of Apple Computer, Inc. Motorola is a trademark of Motorola, Inc. UNIX is a trademark of AT&T Bell Laboratories. Cover: Pastel on paper (1984), John Pearson. Library of Congress Cataloging-in-Publication Data (Revised for volume 2) Lins, C. (Charles) The Modula-2 software component library. (Springer compass international) Includes bibliographies and index. I. Modula-2 (Computer program language) I. Title. II. Series. QA76.73.M63L56 1988 005.13'3 88-24956 © 1989 by Springer-Verlag New York Inc. Printed on acid-free paper. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag, 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc. in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Camera-ready copy provided by the author. 9 8 765 4 3 2 1 ISBN-13: 978-1-4684-6398-9 e-ISBN-13: 978-1-4684-6396-5 DOl: 10.1 007/978-1-4684-6396-5 To Doris Regina whose love made this possible Volume 2 Table of Contents o Introduction to Volume 2 1 1 Specification 3 1.1 Specification of Procedure Abstractions 3 1.2 Specifying Data Abstractions 4 1.3 Special Symbols 5 References 5 2 Module Guide 7 2.1 Purpose 7 2.2 Lists 7 2.2.1 List Enumerations 7 2.2.2 Doubly-Linked List 8 2.2.3 Singly-Linked Lists 10 2.2.4 Singly-Linked List Utilities 11 2.3 Queues 12 2.3.1 Queue Enumerations 13 2.3.2 Non-Priority Balking Sequential Queue 13 2.3.3 Non-Priority Non-Balking Sequential Queue 14 2.3.4 Priority Balking Sequential Queue 16 2.4 Deques 18 2.4.1 Deque Enumerations 18 2.4.2 Non-Priority Balking Sequential Deque 19 2.4.3 Non-Priority Non-Balking Sequential Deque 20 2.4.4 Priority Balking Sequential Deque 22 2.5 Module Names 23 References 24 viii Table of Contents 3 The List Abstraction 25 3.1 Lists: Concept and Defmitions 25 3.2 Selected Summary of List Applications and Uses 26 3.3 List Constructor Operations 27 3.3.1 Create 27 3.3.2 Destroy 27 3.3.3 Clear 28 3.3.4 Assign 28 3.3.5 Insert 28 3.3.6 SetList 29 3.3.7 SetItem 29 3.3.8 SetNext 29 3.3.9 SetPrev 29 3.4 List Selector Operations 30 3.4.1 IsDefined 30 3.4.2 IsEmpty 30 3.4.3 IsEqual 30 3.4.4 LengthOf 30 3.4.5 GetItem 31 3.4.6 GetNext 31 3.4.7 GetPrev 31 3.5 List Exceptions 31 3.5.1 InitFailed 31 3.5.2 Overflow 32 3.5.3 List Is Null 32 3.5.4 Undefined 32 3.6 Summary 33 3.6.1 Operations Summary 33 3.6.2 Exceptions Summary 34 References 35 4 Singly-Linked Unbounded List 37 4.1 List Enumerations 37 4.2 Singly-Linked Unbounded List Interface 38 4.2.1 Type Declarations 39 4.2.2 Exceptions 39 4.2.3 Constructors 39 4.2.4 Selectors 40 Table of Contents ix 4.3 Singly-Linked Unbounded List Implementation 42 4.3.1 Internal Singly-Linked Unbounded List Representation 42 4.3.2 Exceptions 43 4.3.3 Constructors 44 4.3.4 Selectors 48 4.3.5 Module Initialization 50 References 50 5 The Doubly-Linked Unbounded List 51 5.1 Doubly-Linked Unbounded List Interface 51 5.1.1 Type Declarations 52 5.1.2 Exceptions 52 5.1.3 Constructors 52 5.1.4 Selectors 53 5.2 Doubly-Linked Unbounded List Implementation 55 5.2.1 Internal Doubly-Linked Unbounded List Representation 55 5.2.2 Exceptions 56 5.2.3 Constructors 57 5.2.4 Selectors 61 5.2.5 Module Initialization 63 References 64 6 The Singly-Linked Bounded List 65 6.1 Singly-Linked Bounded List Interface 65 6.1.1 Type Declarations 66 6.1.2 Exceptions 67 6.1. 3 Constructors 68 6.1.4 Selectors 69 6.2 Singly-Linked Bounded List Implementation 71 6.2.1 Internal Singly-Linked Bounded List Representation 71 6.2.2 Exceptions 73 6.2.3 Pool Constructors 74 6.2.4 List Constuctors 75 6.2.5 Selectors 79 6.2.6 Module Initialization 82 References 83 x Table of Contents 7 The Doubly-Linked Bounded List 85 7.1 Doubly-Linked Bounded List Interface 85 7.1.1 Type Declarations 85 7.1.2 Exceptions 86 7.1.3 Constructors 86 7.1.4 Selectors 87 7.2 Doubly-Linked Bounded List Implementation 89 7.2.1 Internal Doubly-Linked Bounded List Representation 90 7.2.2 Exceptions 91 7.2.3 Pool Constructors 92 7.2.4 List Constructors 93 7.2.5 Selectors 98 7.2.6 Module Initialization 101 References 102 8 List Utilities 103 8.1 Sequential Search Utilities - Interface 103 8.1.1 PrimarySearch 104 8.1.2 SecondarySearch 105 8.1.3 Self-Organizing Sequential Search - MoveToFront 105 8.1.4 Self-Organizing Sequential Search - Transpose 105 8.2 Sequential Search Utilities - Implementation 106 8.2.1 PrimarySearch 107 8.2.2 SecondarySearch 107 8.2.3 Self-Organizing Sequential Search - MoveToFront 108 8.2.4 Self-Organizing Sequential Search - Transpose 109 8.3 List Utilities - Interface 110 8.3.1 Type Declarations 111 8.3.2 Constructors 111 8.3.3 Selectors 112 8.4 List Utilites - Implementation 113 8.4.1 Constructors 114 8.4.2 Selectors 116 References 118 Table of Contents Xl 9 The Queue and Deque Abstractions 119 9.1 Queues and Deques: Concept and Definitions 119 9.1.1 Queue 119 9.1.2 Deque 120 9.1.3 Priority Queue/Deque 120 9.1.4 Balking Queue/Deque 121 9.2 Summary of Queue!Deque Applications and Uses 121 9.3 Queue Constructor Operations 122 9.3.1 Create 122 9.3.2 Destroy 122 9.3.3 Clear 122 9.3.4 Assign 123 9.3.5 Arrive 123 9.3.6 Depart 124 9.4 Queue Selector Operations 125 9.4.1 IsDefined 125 9.4.2 IsEmpty 125 9.4.3 IsEqual 125 9.4.4 LengthOf 125 9.4.5 FrontOf 126 9.5 Queue Iterator Operations 126 9.5.1 LoopOver 126 9.5.2 Traverse 126 9.6 Deque Operations 127 9.6.1 Arrive 127 9.6.2 Depart 128 9.6.3 BackOf 129 9.6.4 EndOf 129 9.6.5 LoopOver 129 9.6.6 Traverse 130 9.7 Priority Queue/Deque Operations 130 9.7.1 Create (Queue) 130 9.7.2 Create (Deque) 131 9.8 Balking Queue/Deque Operations 131 9.8.1 Leave (Queue) 131 9.8.2 Leave (Deque) 132 9.9 Queue/Deque Exceptions 133 9.9.1 InitFailed 133 9.9.2 Not Found 133 9.9.3 Overflow 133 9.9.4 Underflow 133 9.9.5 Undefined 134 xii Table of Contents 9.10 Summary 134 9.10.1 Queue Operations Summary 134 9.10.2 Queue Exceptions Summary 135 9.10.3 Deque Operations Summary 136 9.10.4 Deque Exceptions Summary 136 9.10.5 Priority Queue Operations Summary 137 9.10.6 Balking Queue Operations Summary 138 9.10.7 Balking Queue Exceptions Summary 139 References 140 10 The Bounded Queue 141 10.1 Queue Enumerations 141 10.2 Bounded Queue Interface 142 10.2.1 Type Declarations 144 10.2.2 Exceptions 144 10.2.3 Constructors 145 10.2.4 Selectors 145 10.2.5 Iterators 146 10.3 Bounded Queue Implementation 146 10.3.1 Internal Bounded Queue Representation 147 10.3.2 Exceptions 148 10.3.3 Constructors 149 10.3.4 Selectors 153 10.3.5 Iterators 156 10.3.6 Module Initialization 157 10.4 The Bounded Balking Queue 157 10.4.1 Bounded Balking Queue Interface 158 10.4.2 Bounded Balking Queue Implementation 158 References 160 11 The Unbounded Queue 161 11.1 Unbounded Queue Interface 161 11.1.1 Type Declarations 163 11.1.2 Exceptions 163 11.1.3 Constructors 163 11.1.4 Selectors 164 11.1.5 Iterators 164