═══ Selection copy ═══ This function exists for both a flat collection and a tree. Please select: o copy if you are using a flat collection. o copy, copySubtree if you are using a tree. ═══ Selection newCursor ═══ This function exists for both a flat collection and a tree. Please select: o newCursor if you are using a flat collection. o newCursor if you are using a tree. ═══ Selection replaceAt ═══ This function exists for both a flat collection and a tree. Please select: o replaceAt if you are using a flat collection. o replaceAt if you are using a tree. ═══ Selection setToFirst ═══ This function exists for a flat collection, a tree and a cursor. Please select: o setToFirst if you are using a flat collection. o setToFirst if you are using a tree. o setToFirst if you are using the cursor class. ═══ Selection setToLast ═══ This function exists for a flat collection, a tree and a cursor. Please select: o setToLast if you are using a flat collection. o setToLast if you are using a tree. o setToLast if you are using the cursor. ═══ Selection setToNext ═══ This function exists for a flat collection, a tree and a cursor. Please select: o setToNext if you are using a flat collection. o setToNext if you are using a tree. o setToNext if you are using the cursor. ═══ Selection setToPrevious ═══ This function exists for a flat collection, a tree and a cursor. Please select: o setToPrevious if you are using a flat collection. o setToPrevious if you are using a tree. o setToPrevious if you are using the cursor. ═══ Selection operator = ═══ This function exists for both a flat collection and a tree. Please select: o operator= if you are using a flat collection. o operator= if you are using a tree. ═══ Selection operator != ═══ This function exists for both a flat collection and a cursor. Please select: o operator!= if you are using a flat collection. o operator!= if you are using a cursor. ═══ Selection operator == ═══ This function exists for both a flat collection and a cursor. Please select: o operator== if you are using a flat collection. o operator== if you are using a cursor. ═══ Selection allElementsDo ═══ For both flat and tree collections, there are multiple versions of the allElementsDo function. For an explanation of the differences, see Iterating over Collections. For flat collections: o With an iteration function see allElementsDo o With an iterator class see allElementsDo For tree collections: o With an iteration function see allElementsDo, allSubtreeElementsDo o With an iterator class see allElementsDo, allSubtreeElementsDo ═══ Selection allSubtreeElementsDo ═══ There are multiple versions of the allSubtreeElementsDo function. For an explanation of the differences, see Iterating over Collections. See the following sections: o With an iteration function see allElementsDo, allSubtreeElementsDo o With an iterator class see allElementsDo, allSubtreeElementsDo ═══ Selection elementAt ═══ The elementAt is offered both for a flat collection and a tree: o For a flat collection see elementAt o For a tree see elementAt ═══ Selection removeAll ═══ The removeAll in its normal form (removing all elements) is available for both flat and tree collections. For a flat collection you can also specify a property function that allows you to specify a property under which an element is to be removed: o For a flat collection see removeAll o For a flat collection with a property function see removeAll o For a tree see removeAll, removeSubtree ═══ 1. How to Use the Online Collection Class Library Guide ═══ The IBM C/C++ Tools Online Collection Class Library Guide is a guide for C++ programmers. It provides information about the Collection Class Library, a set of C++ classes that implement commonly used data structures such as stacks, heaps and queues. This document is a reference rather than a tutorial. It assumes you are already familiar with C++ programming concepts. Before you begin to use this information, it would be helpful to understand how you can: o Expand the Contents to see all available topics o Obtain additional information for a highlighted word or phrase o Use action bar choices How to Use the Contents When the Contents window first appears, some topics have a plus (+) sign beside them. The plus sign indicates that additional topics are available. To expand the Contents if you are using a mouse, click on the plus sign. If you are using the keyboard, use the Up or Down Arrow key to highlight the topic, and press the plus (+) key. To see additional topics for those headings, click on the plus sign or highlight that topic and press the plus (+) key. To view a topic, double-click on the topic (or press the Up or Down Arrow key to highlight the topic, and then press the Enter key). How to Obtain Additional Information After you select a topic, the information for that topic appears in a window. Highlighted words or phrases indicate that additional information is available. You will notice that certain words and phrases are highlighted in green letters, or in white letters on a black background. These are called hypertext terms. If you are using a mouse, double-click on the highlighted word. If you are using a keyboard, press the Tab key to move to the highlighted word, and then press the Enter key. Additional information then appears in a window. How to Use Action Bar Choices Several choices are available for managing information presented in the C/C++ Tools Online Standard Class Library Guide. There are three pull-down menus on the action bar: the Services menu, the Options menu, and the Help menu. The actions that are selectable from the Services menu operate on the active window currently displayed on the screen. These actions include the following: Bookmark Allows you to set a placeholder so you can retrieve information of interest to you. When you place a bookmark on a topic, it is added to a list of bookmarks you have previously set. You can view the list, and you can remove one or all bookmarks from the list. If you have not set any bookmarks, the list is empty. To set a bookmark, do the following: 1. Select a topic from the Contents. 2. When that topic appears, choose the Bookmark option from the Services pull-down. 3. If you want to change the name used for the bookmark, type the new name in the field. 4. Click on the Place radio button (or press the Up or Down Arrow key to select it). 5. Click on OK (or select it and press Enter). The bookmark is then added to the bookmark list. Search Allows you to find occurrences of a word or phrase in the current topic, selected topics, or all topics. You can specify a word or phrase to be searched. You can also limit the search to a set of topics by first marking the topics in the Contents list. To search for a word or phrase in all topics, do the following: 1. Choose the Search option from the Services pull-down. 2. Type the word or words to be searched for. 3. Click on All sections (or press the Up or Down Arrow keys to select it). 4. Click on Search (or select it and press Enter) to begin the search. 5. The list of topics where the word or phrase appears is displayed. Print Allows you to print one or more topics. You can also print a set of topics by first marking the topics in the Contents list. To print the document Contents list, do the following: 1. Choose Print from the Services pull-down. 2. Click on Contents (or press the Up or Down Arrow key to select it). 3. Click on Print (or select it and press Enter). 4. The Contents list is printed on your printer. Copy Allows you to copy a topic that you are viewing to the System Clipboard or to a file that you can edit. This is particularly useful for copying program samples into the application that you are developing. You can copy a topic that you are viewing in two ways: o Copy copies the topic that you are viewing into the System Clipboard. If you are using a Presentation Manager* (PM) editor (for example, the Enhanced Editor) that copies or cuts (or both) to the System Clipboard, and pastes to the System Clipboard, you can easily add the copied information to your program source module. o Copy to file copies the topic that you are viewing into a temporary file named TEXT.TMP. You can later edit that file by using any editor. TEXT.TMP is placed in the directory where your viewable document resides. To copy a topic, do the following: 1. Expand the Contents list and select a topic. 2. When the topic appears, choose Copy to file from the Services pull-down. 3. The system puts the text pertaining to that topic into the temporary file TEXT.TMP. For information on any of the choices in the Services pull-down, highlight the choice and press the F1 key. The actions that are selectable from the Options menu allow you to change the way your Contents list is displayed. To expand the Contents and show all levels for all topics, choose Expand all from the Options pull-down. You can also press the Ctrl and * keys together. For information on any of the choices in the Options pull-down, highlight the choice and press the F1 key. The actions that are selectable from the Help menu allow you to select different types of help information. You can also press the F1 key for help information about the Information Presentation Facility (IPF). ═══ Related Information ═══ o Copyright o Edition Notice o Notices o Trademarks and Service Marks ═══ 1.1. Copyright ═══ Copyright International Business Machines Corporation, 1993. All rights reserved. Note to U.S. Government Users - Documentation related to restricted rights - Use, duplication, or disclosure is subject to restrictions set forth in GSA ADP Schedule Contract with IBM* Corp. ═══ 1.2. Edition Notice ═══ Second Edition, November 1993. This edition applies to Version 2.01 of IBM C/C++ Tools (82G3745, 82G3746, 82G3747) and to all subsequent releases and modifications until otherwise indicated in new editions. This publication could include technical inaccuracies or typographical errors. Changes are periodically made to the information herein; any such changes will be reported in subsequent revisions. Requests for publications and for technical information about IBM* products should be made to your IBM Authorized Dealer or your IBM Marketing Representative. When you send information to IBM, you grant IBM a nonexclusive right to use or distribute the information in any ways it believes appropriate without incurring any obligation to you. ═══ 1.3. Notices ═══ References in this publication to IBM* products, programs, or services do not imply that IBM intends to make these available in all countries in which IBM operates. Any reference to an IBM product, program, or service is not intended to state or imply that only IBM's product, program, or service may be used. Any functionally equivalent product, program, or service that does not infringe any of IBM's intellectual property rights may be used instead of the IBM product, program, or service. Evaluation and verification of operation in conjunction with other products, programs, or services, except those expressly designated by IBM, are the user's responsibility. IBM may have patents or pending patent applications covering subject matter in this document. The furnishing of this document does not give you any license to these patents. You can send license inquiries, in writing, to the IBM Director of Commercial Relations, IBM Corporation, Purchase, NY 10577. This online information may contain coding examples of programs used in daily business operations. To illustrate them as completely as possible, the examples may include the names of individuals, companies, brands, and products. Any such names are fictitious and any similarity to the names and addresses used by an actual business enterprise is entirely coincidental. ═══ 1.4. Trademarks and Service Marks ═══ The following terms, denoted by an asterisk (*) in this publication, are trademarks or service marks of IBM* Corporation in the United States or other countries: IBM OS/2 C/C++ Tools C Set ++ ═══ IBM Trademark ═══ Trademark of the IBM Corporation. ═══ Non-IBM Trademarks ═══ AT&T is a trademark of ATTrue Corporation. ═══ 2. User's Guide ═══ This section gives general information about the Collection Classes and defines the terms that are used in the rest of the book. It contains the following chapters: Overview of the Collection Classes Provides an overview of the Collection Classes and describes the different kinds of collections. Instantiating and Using the Collection Classes Provides an overview of how you can instantiate and use the Collection Classes. Element Functions and Key Functions Describes the functions that manipulate elements and keys. Tailoring a Collection Implementation Describes how you can customize a collection implementation for your specific requirements. Polymorphic Use of Collections Describes the polymorphic use of collection classes. Exception Handling Describes the exception-handling facilities of the Collection Classes. Use this chapter to build exception recovery into your applications that use the Collection Classes. Implementation Classes and Header Files Lists the implementation classes and their header files. Tutorials Provides information on how to use the tutorials provided with the Collection Classes. These tutorials are exercises that you can follow to learn about the Collection Classes. Understanding the Reference Chapters Describes the format of member function descriptions, and the format of the Reference Manual chapters that describe individual abstract data types. ═══ 2.1. Introduction ═══ This book describes the Collection Classes, a set of C++ classes included with C/C++ Tools, that implement commonly used abstract data types, including: o Sets o Maps o Sequences o Relations o Trees o Stacks o Bags o Queues o Priority queues o Sorted collections o Keyed collections The Collection Classes do not limit you to a single implementation of the above abstract data types. For each type, you can tailor the implementation to the specific needs of your application. ═══ 2.1.1. Who Should Use This Book ═══ This book is meant for programmers who are skilled in programming in the C++ language, who understand the concept of classes, and who have experience with using C++ templates. You should use this book if you want to use the Collection Classes to implement data structures in your programs. ═══ 2.1.2. How to Use This Book ═══ Introduction tells you how to use this book, which is divided into five parts: o User's Guide, gives general information about the Collection Classes and defines the terms that are used in the rest of the book. Read this part to become familiar with the basic concepts of the collection classes. o Reference Manual - Flat Collections, describes the flat collections. Its first chapter, Flat Collection Member Functions, describes member functions that are common to all flat collections. Each subsequent chapter describes a particular flat collection class. o Reference Manual - Tree Classes, describes the tree classes. o Reference Manual - Auxiliary Classes, describes the auxiliary classes that are associated with each collection class. o Reference Manual - Abstract Classes, describes the abstract classes. These classes define the data abstractions for which concrete implementations are provided. ═══ 2.1.2.1. Fonts Used in This Book ═══ In this book, C++ code and code fragments, and Collection Classes class and member function names, appear in special font. Variables that are not used in actual examples, and for which other variable names can be substituted, appear in italics. ═══ 2.1.3. A Note About Examples ═══ The examples in this book explain how to use the Collection Classes. They are coded in a simple style. They do not try to conserve storage, check for errors, achieve fast run times, or demonstrate all possible uses of a particular class or function. ═══ 2.1.4. Related Documentation ═══ You might want to refer to the following publications for additional information: IBM Publications: IBM C/C++ Tools: C++ Language Reference, S61G-1185, describes the C++ language. IBM C/C++ Tools: Standard Class Library Reference, S61G-1180, describes the Complex, I/O Stream, and Task Libraries. IBM C/C++ Tools: User Interface Class Library Reference, S61G-1179, describes the C++ User Interface classes, a set of C++ classes that can be used to create C++ applications with a graphical user interface that conforms to the Common User Access (CUA) interface design. IBM C/C++ Tools: Class Libraries Reference Summary, S61G-1186, lists the member functions of the Standard, Collection, and User Interface class libraries. For each member function, the declaration is provided and the class the function belongs to is indicated. IBM C/C++ Tools: Programming Guide, S61G-1181, describes the C++ component of the common programming interface. The following is a sample of some non-IBM publications that are generally available. It is not an exhaustive list. IBM does not specifically recommend any of these books, and other publications may be available in your locality. o These books contain information about the C++ language: The Annotated C++ Reference Manual by Margaret A. Ellis and Bjarne Stroustrup, Addison-Wesley Publishing Company. The C++ Programming Language (Second Edition) by Bjarne Stroustrup, Addison-Wesley Publishing Company. C++ Primer (Second Edition) by Stanley B. Lippman, Addison-Wesley Publishing Company. o These books contain explanations of data structures that may help you understand the data structures in the Collection Class Library: Data Structures and Algorithms by Aho, Hopcroft and Ullman, Addison-Wesley Publishing Company. The Art of Computer Programming, Vol.3: Sorting and Searching, D.E. Knuth, Addison-Wesley Publishing Company. C++ Components and Algorithms by Scott Robert Ladd, M&T Publishing Inc. A Systematic Catalogue of Reusable Abstract Data Types by Juergen Uhl and Hans Albrecht Schmid, Springer Verlag. ═══ 2.2. Overview of the Collection Classes ═══ A C++ collection is an abstract concept that allows you to manipulate objects in a group. Collections are used to store and manage elements (or objects ) of a user-defined type. Different collections have different internal structures, and different access methods for storage and retrieval of objects. This chapter briefly introduces the classes that make up the Collection Classes, and explains some of the key concepts that are used throughout this book. This chapter describes the following topics: o Benefits of the Collection Classes o Types of classes in the Collection Classes o Flat collections o Trees o Auxiliary classes o Overall implementation structure of the Collection Classes o Class template naming conventions o Linking to the Collection Class library ═══ 2.2.1. Benefits of the Collection Classes ═══ In addition to implementing the common abstract data types efficiently and reliably, the Collection Classes give you the following benefits: o A framework of properties to help you to decide which abstract data type is appropriate in a given situation. o A choice about how the abstract data type you have chosen is implemented by the Collection Classes. The Collection Classes let you choose the appropriate abstract data type for a given situation by providing collection classes that are a complete, systematic, and consistent combination of basic properties. These properties, which are explained in Flat Collections, help you to select abstract data types that are at the appropriate level of abstraction. In a particular application, for example, you may have the choice between using a bag and a key sorted set. The properties of these two collections will help you to decide which one is more appropriate. Once you have chosen the appropriate abstract data type, the Collection Classes offer you a choice of implementations for it. Each abstract data type has a common interface with all of its possible implementations. It is easy to replace one implementation with another for performance reasons or if the requirements of your application change. ═══ 2.2.2. Types of Classes in the Collection Classes ═══ The classes that make up the Collection Classes are divided into three types: Flat Collections Flat collections include abstractions like sequence, set, bag, and map. Unlike trees, flat collections have no hierarchy of elements or recursive structure. See Flat Collections for more information on flat collections and their properties. Trees Trees are recursive collections of nodes, where each node holds an element and has a given number of nodes as children. See Trees for more details on trees. Auxiliary Classes The auxiliary classes include classes for cursors, iterators, and simple and managed pointers. Cursors and iterators give you convenient methods for accessing the elements stored in the collections. See Cursors for more details on cursor classes. See Iteration Using Iterators for more details on iterator classes. The pointer classes provide the means to store in collections a pointer to an object instead of the object itself. The managed pointer class offers this object management together with automatic storage management. See Values and Objects and Automatic Storage Management for more details on pointer classes. ═══ 2.2.3. Flat Collections ═══ Four basic properties are used to differentiate between different flat collections: Ordering Whether a next or previous relationship exists between elements. Access by key Whether a part of the element (a key) is relevant for accessing an element in the collection. When keys are used, they are compared using relational operators. Equality for elements Whether equality is defined for the element. Uniqueness of entries Whether any given element or key is unique, or whether multiple occurrences of the same element or key are allowed. Combination of Flat Collection Properties shows the flat collection that results from each combination of properties. For example, map appears in the unique, unordered column for the key, element equality row. This means that a Map is unordered, each element is unique, keys are defined, and element equality is defined. The figure contains NA where no flat collection corresponds to the combination of properties. For example, the NA in the first two rows of the rightmost column indicates that an ordered collection that is sequential instead of sorted and offers access by key is not available. There are no flat collections that have all of the following properties: o The collection is ordered. o The collection is sequential. o The collection allows an element to appear more than once. o Keys are defined for elements in the collection. The rationale for not implementing collections with these combinations of properties is that there is no reason to choose them over another collection that is already available. Consider the case mentioned above of an ordered collection that is sequential and offers access by key. Access by key would only have advantages if the elements are stored in a position depending on their key. Because they are not, there is no flat collection with key access that maintains a sequential order. Combination of Flat Collection Properties ┌─────────────────┬─────────────────┬──────────────────────────┐ │ │ Unordered │ Ordered │ │ │ ├─────────────────┬────────┤ │ │ │ Sorted │Sequen- │ │ │ │ │tial │ │ ├────────┬────────┼────────┬────────┼────────┤ │ │ Unique │Multiple│ Unique │Multiple│Multiple│ ├────────┬────────┼────────┼────────┼────────┼────────┼────────┤ │ │Element │ Map │Relation│ Sorted │ Sorted │ NA │ │ │Equality│ │ │ Map │Relation│ │ │ Key │────────┼────────┼────────┼────────┼────────┼────────┤ │ │ No │ │ │ Key │ Key │ │ │ │Element │Key Set │Key Bag │ Sorted │ Sorted │ NA │ │ │Equality│ │ │ Set │ Bag │ │ ├────────┼────────┼────────┼────────┼────────┼────────┼────────┤ │ │Element │ Set │ Bag │ Sorted │ Sorted │Equality│ │ │Equality│ │ │ Set │ Bag │Sequence│ │ No │────────┼────────┼────────┼────────┼────────┼────────┤ │ Key │ No │ │ │ │ │ │ │ │Element │ NA │ Heap │ NA │ NA │Sequence│ │ │Equality│ │ │ │ │ │ └────────┴────────┴────────┴────────┴────────┴────────┴────────┘ ═══ 2.2.3.1. Ordering of Collection Elements ═══ The elements of a flat collection class can be ordered in three ways: o Unordered collections have elements that are not ordered. o Sorted collections have their elements sorted by an ordering relation defined for the element type. For example, integers can be sorted in ascending order, and strings can be ordered alphabetically. The ordering relation is determined by the instantiations for the collection class. o Sequential collections have their ordering determined by an explicit qualifier to the add function, for example, addAtPosition. A particular element in a sorted collection can be accessed quickly by using the ordering relation to determine its position. Unordered collections can also be implemented to allow fast access to the elements, by using, for example, a hash table or a sorted representation. The Collection Classes provide a fast locate function that uses this structure for unordered and sorted collections. Even though unordered collections are often implemented by sorting the elements, do not assume that all unordered collections are implemented in this way. If your program requires this assumption to be true, use a sorted collection instead. For each flat collection, the Collection Classes provide both unordered and sorted abstractions. For example, the Collection Classes support both a set and a sorted set. The ordering property is independent of the other properties of flat collections: you have the choice of making a given flat collection unordered or sorted regardless of the choices that you make for the other properties. ═══ 2.2.3.2. Access by Key ═══ A given flat collection can have a key defined for its elements. A key is usually a data member of the element but it can also be calculated from the data members of the element by some arbitrary function. Keys let you: o Organize the elements in a collection o Access a particular element in a collection For collections that have a key defined, an equality relation must be defined for the key type. Thus, a collection with a key is said to have key equality. ═══ 2.2.3.3. Equality for Keys and Elements ═══ A flat collection can have an equality relation defined for its elements. This relation is based on the element as a whole, not just on one or more of its data members (for example, the key). For two elements to be equal, all data members of both elements must be equal. The equality relation is needed for functions such as those that locate or remove a given element. A flat collection that has an equality relation has element equality. The equality relation for keys may be different than the equality relation for elements. Consider, for example, a task control block that has a priority and a task identifier that defines equality for tasks. You could choose to implement a task collection as unordered with the task ID as key, or as sorted with the priority as key. In the first case, you have fast access through the task ID but not through the priority; in the second case, you have fast access through the priority but not through the task ID. The ordering relation on the priority key in the second case does not yield a task equality, because two tasks can have equal priorities without being the same. Functions like locateElementWithKey (see Flat Collection Member Functions) use the equality relation on keys to locate elements within a collection. A collection that defines key equality may also define element equality. Functions that are based on equality (such as locate) are only provided for collections that define element equality. Collections that define neither key equality nor element equality, such as heaps and sequences, provide no functions for locating elements by their values or testing for containment. Elements can be added and retrieved from such collections by iteration. For sequences, elements can also be added and retrieved by position. A sorted collection must define either key equality or element equality. A sorted collection that does not have a key defined must have an ordering relation defined for the element type. This relation implicitly defines element equality. Keys can be used to access a particular element in a collection. The alternative to defining equality of elements as equality of their keys (in the task control block example: defining task equality as equality of the task ID) and then locating collection entries by providing an equal element, causes performance problems when the element is large or difficult to construct compared to the key alone. Consider the two alternatives in the following example. Note that the Task type defined in these examples is not related to the Task Library described in the Standard Class Library Reference. // First solution TaskId const& key (Task const& t) {return t.id;} KeySet < Task, int > tasks; // ... tasks.locateElementWithKey (1); // Second solution Boolean operator== (Task const& t1, Task const& t2) {return t1.id == t2.id;} Set < Task > tasks; // ... Task t1; t1.id = 1; tasks.locate (t1); The first solution is superior, if task construction (Task t1) requires a significant proportion of the total system resources used by the program. The Collection Classes provide sorted and unsorted versions of maps and relations, for which both key and element equality must be defined. These collections are similar to key set and key bag, except that they define functions based on element equality, namely union and intersection. The add function behaves differently toward maps and relations than towards key set and key bag. ═══ 2.2.3.4. Uniqueness of Entries ═══ The terms unique and multiple relate to the key, in the case of collections with a key. For collections with no key, unique and multiple relate to the element. In some flat collections, such as map, key set, and set, no two elements are the same or have the same key. Such collections are called unique collections. Other collections, including relation, key bag, bag, and heap, can have two equal elements or elements with the same key. Such collections are called multiple collections. For those multiple collections with key that have an element equality (relation and sorted relation), elements are always unique while keys can occur multiple times. In other words, if element equality is defined for a multiple collection with key, element equality is tested for before inserting a new element. A unique collection with no keys and no element equality is not provided because a containment function cannot be defined for such a collection. A containment function determines whether a collection contains a given element. The behavior during element insertion (add, ...) distinguishes unique and multiple collections. In unique collections, the add function does not add an element that is equal to an element that is already in the collection. In multiple collections, the add function does add the elements. The add function has two general properties: o All elements that are contained in the collection before an element is added are still contained in the collection after the element is added. o The element that is added will be contained in the collection after it is added. Operations that contradict these properties are not valid. You cannot add an element to a map or sorted map that has the same key as an element that is already contained in the collection, but is not equal to this element (as a whole). In the case of a map and sorted map, an exception is thrown. Note that both map and sorted map are unique collections. The functions locateOrAddElementWithKey and addOrReplaceElementWithKey specify what happens if you try to add an element to a collection that already contains an element with the same key. Behavior of add for Unique and Multiple Collections shows the result of adding a series of four elements to a map, a relation, a key set, and a key bag. The first row shows what each collection looks like after the element is added to each collection. Each following row shows what the collections look like after the element in the leftmost column is added to each. The elements are pairs of a character and an integer. The character in the pair is the key. An element equality relation, if defined, holds between two elements if both the character and the integer in each pair are equal. ┌───────────┬───────────┬───────────┬───────────┬──────────┐ │ │Map or │Relation or│Key Set or │Key Bag or│ │ add │Sorted Map │Sorted │Key Sorted │Key Sorted│ │ │ │Relation │Set │Bag │ ├───────────┼───────────┼───────────┼───────────┼──────────┤ │ │ ├───────────┼───────────┼───────────┼───────────┼──────────┤ │ , │ , │ , │ , │ │ │ │ ├───────────┼───────────┼───────────┼───────────┼──────────┤ │ , │ , │ , │ , │ │ │ , │ │ │ │ │ │ │ ├───────────┼───────────┼───────────┼───────────┼──────────┤ │ │Exception: │ , │ , │ , │ │ │KeyAlready-│ , │ , │ │ │Exists │ │ │ , │ │ │ │ │ │ │ └───────────┴───────────┴───────────┴───────────┴──────────┘ Behavior of add for Unique and Multiple Collections ═══ 2.2.4. Restricted Access ═══ Flat collections with restricted access have a restricted set of functions that can be applied to them, that is, only a subset of the functions listed in Flat Collection Functions can be applied. Examples of such flat collections are stack and priority queue. You may want to restrict the set of functions for reasons such as: 1. You can simplify the interface to the collection. 2. The normal rules for restricted flat collections apply, so certain assumptions can be made when validating and inspecting the code. A stack, for example, does not allow the removal of any element except the top one. 3. You can create new implementation options. The Collection Classes provide the following flat collections with restricted access: o Stack, deque, and queue, which are all based on sequence o Priority queue, which is based on key sorted bag See Reference Manual - Flat Collections for descriptions of collections with restricted access. These descriptions are alphabetically merged with descriptions for other collections. You can use Properties for Collections with Restricted Access to select the appropriate flat collection with restricted access for a given set of properties. ┌──────────────────────────────────────────────────────────────────────────────┐ │ Properties for Collections with Restricted Access │ ├───────────────┬───────────────┬───────────────────────┬──────────────────────┤ │ ADD │ REMOVE │ SORTED (WITH KEY) │ UNSORTED (NO KEY) │ ├───────────────┼───────────────┼───────────────────────┼──────────────────────┤ │ According to │ First │ Priority queue │ N/A │ │ key │ │ │ │ ├───────────────┼───────────────┼───────────────────────┼──────────────────────┤ │ Last │ Last │ N/A │ Stack │ ├───────────────┼───────────────┼───────────────────────┼──────────────────────┤ │ Last │ First │ N/A │ Queue │ ├───────────────┼───────────────┼───────────────────────┼──────────────────────┤ │ First or last │ First or last │ N/A │ Deque │ └───────────────┴───────────────┴───────────────────────┴──────────────────────┘ ═══ 2.2.5. Trees ═══ Trees can be described either as structures where the elements have a hierarchy or as a special form of recursive structures. Recursively a tree can be described as a node (parent) with pointers to other nodes (children). Every node has a fixed number of pointers, which are set to null at initialization time. Insertion of a new node involves setting a pointer in the parent so that it points to the inserted child. The Structure of N-ary Trees illustrates the structure of an n-ary tree. The Structure of N-ary Trees Similarly, you can obtain tree-like or recursive structures by implementing the array of children of a node as a flat collection of nodes. This will give you different functionality for the children, for example the ability to locate a child with a given value. ═══ 2.2.6. Auxiliary Classes ═══ To use the collection classes, you also need a cursor and an iterator class. These are described in Cursors and Iteration Using Iterators. The Pointer and Managed Pointer Classes allow you to manage objects, and they enable automatic storage management. Values and Objects and Automatic Storage Management explain the concepts and usage in detail. ═══ 2.2.7. The Overall Implementation Structure ═══ To achieve maximum runtime efficiency and ease of use, the Collection Classes combine the common features of object-oriented techniques, such as class hierarchies, polymorphism and late binding, with an efficient class structure that uses advanced optimization techniques. This section gives a brief overview of the library structure that is shown in Overall Library Structure. A more detailed explanation of the particular concepts is found in subsequent sections. You need not understand the entire implementation structure to begin using the collections in their basic forms. The following is a list of the implementation strategies offered by the Collection Classes, in order of increasing complexity: Use the defaults Default implementations are provided for every collection. If you do not want to be concerned with choosing an implementation for an abstract data type, you can use the default classes provided by the Collection Classes. In chapters on particular collections, the default implementation is the first implementation in the "Class Implementation Variants" table for that chapter, if a table is present. If no table is present, the default implementation is stated in the chapter's "Class Implementation Variants" section. Use variants If you want to choose a particular implementation variant for a collection, you can use variant classes to replace the default implementation. See Tailoring a Collection Implementation for details on how to use the variant classes. Use polymorphism If you want to have a more generalized collection class than those offered by the concrete classes, you can take advantage of polymorphism. For example, when working with a set, instead of using the concrete class ISetOnAVLKeySortedSet, you can use the abstract class IASet or, for more generic behavior, the abstract class IAEqualityCollection. Abstract classes, which are accessed using reference classes let you program to a more generalized interface, without necessarily knowing what abstract data types (collections), your code will operate on. You can leave the implementation details for later. The following figure illustrates the relationships between the categories of classes for the collection set. Each class falls within one of five categories: default, concrete, typeless implementation, abstract, and reference classes. Arrows indicate a relationship between classes. Text beside each arrow indicates the relationship between the two classes. The relationships are: o Based on o Partially instantiates o Is a o Uses In this figure, you will notice certain naming conventions. For information on naming conventions, see Class Template Naming Conventions. Overall Library Structure The following sections describe the categories of classes in the Collection Classes. ═══ 2.2.7.1. Default Classes ═══ The default classes provide the easiest way to use the collection classes. Two default classes are provided for each abstract data type: o A class that is instantiated only with the element type, and possibly the key type. ISet is an example of this type of default class. o A class that takes element-specific functions. IGSet is an example of this type of default class. See Using Element Operation Classes for information on element-specific functions. ═══ 2.2.7.2. Abstract Classes ═══ The classes in the Collection Classes are all related through the hierarchy of abstract classes shown in The Abstract Class Hierarchy. The leaves of the abstract class hierarchy (that is, those classes that have no derived classes within abstract class hierarchy tree) define the collection for which concrete implementations are provided. The arrows in the figure represent an is a relationship. For example, a set is an equality collection which is a collection. The library names of abstract classes start with IA. Note: The Abstract Class Hierarchy does not show the N-ary Tree class nor the flat collections with restricted access because thess classes are not derived from the abstract class IACollection. The Abstract Class Hierarchy ═══ 2.2.8. Class Template Naming Conventions ═══ All class templates begin with an uppercase I. Class template naming conventions shows the naming conventions used to distinguish between different types of class templates, given a default class template of ISet. Underscored letters in each class template name are those that indicate the stated convention: ┌────────────────────┬──────────────────────────────────────────────────┐ │ CLASS NAME │ MEANING OF LETTERS │ ├────────────────────┼──────────────────────────────────────────────────┤ │ "ISet" │ Default class template │ ├────────────────────┼──────────────────────────────────────────────────┤ │ "IGSet" │ Default generic class template. The element │ │ │ operations class can be specified as template │ │ │ argument. │ ├────────────────────┼──────────────────────────────────────────────────┤ │ ISetOn... │ Variant class template │ ├────────────────────┼──────────────────────────────────────────────────┤ │ IWSetOn... │ Typed implementation based on another typed │ │ │ implementation. You can think of the "W" as a │ │ │ shorthand for "wrapping another implementation │ │ │ with a new interface." │ ├────────────────────┼──────────────────────────────────────────────────┤ │ IASet │ Abstract class template │ ├────────────────────┼──────────────────────────────────────────────────┤ │ IRSet │ Reference class template │ └────────────────────┴──────────────────────────────────────────────────┘ Table 2. Class template naming conventions ═══ 2.2.8.1. Concrete Classes ═══ Each abstract data type can be instantiated by one of several concrete classes. Sets, for example, may be implemented as key sorted sets or as hash tables. Key sorted sets may be implemented as sequences. Concrete classes are grouped according to the abstract data type that they implement. All of the concrete classes for an abstract data type have the same interface. This guide refers to the concrete class templates that are not default class template as variant class templates. ═══ 2.2.8.2. Reference Classes ═══ To avoid the overhead of virtual function calls, the Collection Classes do not allow concrete classes to be derived directly from abstract classes. The compiler can usually optimize function calls when it knows the exact type of the object, but because collections are mostly passed by reference, such an optimization is not possible with the collection classes. If you do not want to take advantage of polymorphism, you do not have to deal with the overhead of virtual function calls. Abstract and concrete classes are linked through reference classes. These classes are derived from the abstract classes, and implement the member functions using one of the corresponding concrete classes. Names of reference classes start with IR. See Polymorphic Use of Collections for more details on the use of polymorphism in the Collection Classes. ═══ 2.2.8.3. Typed and Typeless Implementation Classes ═══ Typed implementation classes implement the concrete classes. They provide an interface that is specific to a given element type; this type-interface enables the C++ compiler to verify, for example, that an integer cannot be added to a set of strings. Typed implementation classes may be basic or based on another implementation. Basic classes have names that start with I or IG. Based-on classes have names that start with IW. For further details see The Based-On Concept. Typeless implementation classes are used for handling the problem of unnecessary code expansion. Giving member functions a return type of void* is a simple way to avoid this problem. The collection classes, however, use functions that return specific types. The implementation classes provide an untyped (void*) interface that the concrete class implementations use. Programmers never use the implementation classes directly. ═══ 2.2.9. Linking to the Collection Class Library ═══ You must specify the following library names when compiling or linking programs that use the Collection Class Library: o DDE4CC.LIB - for static linking o DDE4CCI.LIB - for dynamic linking. ═══ 2.3. Instantiating and Using the Collection Classes ═══ This chapter describes how to instantiate and use collection classes. The following topics are described in this chapter: o Instantiation and object definition o Bounded and unbounded collections o Adding, removing, and replacing elements o Cursors o Iterating over collections o Copying and referencing collections To use a collection class, you normally follow these three steps: 1. Instantiate a collection class template and provide arguments for the formal template arguments 2. Define one or more objects of this instantiated class, possibly providing constructor arguments 3. Apply functions to these objects. ═══ 2.3.1. Instantiation and Object Definition ═══ This section describes instantiation for the default implementation. For a given class, such as ISet, and a given element type, such as Task, the instantiation for a new class that represents sets of tasks could look like this: class Task { /* ... */ }; typedef ISet < Task > TaskSet; The instantiation could also look like this: class TaskSet : public ISet < Task > { public: TaskSet (INumber n = 100) : ISet < Task > (n) {} } The second form defines a new class called TaskSet that has a constructor that takes a single argument. The definition of the constructor is necessary if TaskSets with different estimates for the number of elements will be created. C++ language rules determine that TaskSet does not inherit the constructor of ISet < Task >. You can now define TaskSet objects toBeDone, pending, and delayed as follows: TaskSet toBeDone, pending, delayed; You can also define the objects without introducing a new type name (TaskSet): ISet < Task > toBeDone, pending, delayed; However, you should begin by explicitly defining a named class, such as TaskSet, that uses the default implementation. It is then easier to replace the default implementation with a better implementation later on. See Tailoring a Collection Implementation for more details on replacing default implementations. Note: The Task element type used in the above example is not related to the C++ Task Library described in Standard Class Library Reference. ═══ 2.3.2. Bounded and Unbounded Collections ═══ A bounded collection limits the number of elements it can contain. There are no bounded collections in the Collection Class Library. The concept of bounded collections is provided so that you can create your own bounded collection implementations. When a bounded collection contains the maximum number of elements (its bound), the collection is said to be full. This condition can be tested by the function isFull. If elements are added to a full collection, the exception IFullException is thrown. This behavior is useful for collections that are to have their storage allocated completely on the runtime stack. You can determine the maximum number of elements in a bounded collection by calling the function maxNumberOfElements. You can only call this function if the collection is bounded. You can determine whether a collection is bounded by calling the function isBounded. In the current implementation of the Collection Class Library, all collections are unbounded. The functions isBounded and isFull always return False. The function maxNumberOfElements throws the exception INotBoundedException. ═══ 2.3.3. Adding, Removing, and Replacing Elements ═══ You can perform three operations to modify a collection: o Adding elements. Use the add function and its variants. o Removing elements. Use the remove function and its variants. o Replacing elements. Use the replace function and its variants. ═══ 2.3.3.1. Adding Elements ═══ The function add places the element identified by its argument into the collection. add behaves differently depending on the properties of the collection: o In unique collections, an element is not added if it is already contained in the collection. o In sorted collections, an element is added according to the ordering relation of the collection. o In sequential collections, an element is added to the end of the collection. In general, you can copy one collection to another collection that is initially empty by iterating through the elements of the first collection and calling add with each element as an argument. In particular, for a sequential collection, add must add the element last, because iteration iterates from the first toward the last element. For sequential collections, elements can be added at a given position using add functions other than add, such as addAtPosition, addAsFirst, and addAsNext. Elements after and including the given position are shifted. Positions can be specified by a number, where counting starts with 1 for the first element, by using the addAtPosition function. Positions can also be specified relative to another element by using the addAsNext or addAsPrevious functions, or relative to the collection as a whole by using the addAsFirst or addAsLast functions. ═══ 2.3.3.2. Removing Elements ═══ In the Collection Classes, you can remove an element that is pointed to by a given cursor, by using the removeAt function. All other removal functions operate on the model of first generating a cursor that refers to the desired position and then removing the element to which the cursor refers. There is an important difference between element values and element occurrences. An element value may, for nonunique collections, occur more than once. The basic remove function always removes only one occurrence of an element. For collections with keys or element equality, removal functions remove one or all occurrences of a given key or element. These functions include remove, removeElementWithKey, removeAllOccurrences, and removeAllElementsWithKey. Ordered collections provide functions for removing an element at a given numbered position. Ordered collections also allow you to remove the first or last elements of a collection using the removeFirst or removeLast functions. After an element has been added or removed, all cursors of the collection become undefined. Therefore, removing all elements with a given property from a collection cannot be done efficiently using cursors. After you have removed one element with the property, the entire collection would have to be searched for the next element with the property. If you want to remove all of the elements in a collection that have a given property, you should use the function removeAll and provide a predicate function as its argument. This predicate function has an element as argument and returns a Boolean value. The Boolean result tells whether the element will be removed. Sometimes you may want to pass more information to the predicate function. You can use an additional argument of type void*. The pointer then can be used to access a structure containing further information. The following example removes all even elements from an integer collection: Boolean isEven (int const& i, void*) { return i % 2 == 0; } // ... intSet.removeAll (isEven); In the above example function isEven, the additional argument of type void* was not used. See the last example under Iteration Using Iterators for information on how to use the additional argument. ═══ 2.3.3.3. Replacing Elements ═══ It is possible to modify collections by replacing the value of an element occurrence. Adding and removing elements usually changes the internal structure of the collection. Replacing an element leaves the internal structure unchanged. If an element of a collection is replaced, the cursors in the collection do not become undefined. For collections that are organized according to element properties, such as an ordering relation or a hash function, the replace function must not change this element property. For key collections, the new key must be equal to the key that is replaced. For nonkey collections with element equality, the new element must be equal to the old element as defined by the element equality relation. The key or element value that must be preserved is called the positioning property of the element in the given collection type. Sequential collections and heaps do not have a positioning property. Element values in sequences and heaps can be changed freely. Replacing element values involves copying the whole value. If only a small part of the element is to be changed, it is more efficient to use the elementAt access function described in Using Cursors for Locating and Accessing Elements. The replaceAt function checks the validity of the positioning property as a precondition. (See Exception Handling for more details on preconditions.) When you use the elementAt function to replace part of the element value, this check is not performed. ═══ 2.3.4. Cursors ═══ A cursor is a reference to an element in a collection. If the position of the element changes, the cursor is invalidated. This occurs because the cursor refers only to the position of the element and not to the element itself. A cursor is always associated with a collection. The collection is specified when the cursor is created, and cannot be changed. Each collection function that takes a cursor argument has a precondition that the cursor actually belong to the collection. Simple functions, such as advancing the cursor, are also functions of the cursor itself. For example: Set::Cursor cursor(collection); cursor.setToNext(); is the same as: collection.setToNext(cursor); Cursors and iteration by cursors can be used with any collection. With cursors the Collection Classes provide: o An iteration scheme that is simpler than using iterators. (see Iteration Using Iterators.) o The ability to define functions that return cursors. Such functions can give you fast access to an element if it exists, or indicate the non-existence of an element by returning an invalid cursor. ═══ 2.3.4.1. Cursors in Linked and Tabular Implementations ═══ Cursors are only temporarily defined. As soon as elements are added to or removed from the collection, existing cursors become undefined. This leads to one of the three following situations: 1. The cursor is invalidated (isValid will return False). 2. The cursor remains valid and points to an element of the collection; however, it may point to a different element than before. 3. The cursor remains valid but no longer points to an element of the collection. Do not use an undefined cursor as an argument to a function that requires that the cursor point to an element of the collection. Cursors can be implemented as C++ pointers (to nodes that carry the elements) in linked implementations or as indices to an array in tabular implementations. A linked implementation is accessed using pointer chains, while a tabular implementation is accessed using indices into arrays. If an element is added or removed from a collection that has a tabular implementation, the other elements may be shifted. A cursor that is defined for this collection may no longer refer to the same element after elements have been shifted. For this reason, if you want to be able to choose between a linked or tabular implementation for a particular collection, you should not use a cursor after elements have been added to or removed from the collection. One of the properties of linked implementations is that elements are not shifted. If you exploit this property, the cursors might still be used. You should document the decision to use a linked implementation so that: o All those who use the collection class know whether the implementation is linked. o All those who tailor the collection class only choose appropriate implementations. See Tailoring a Collection Implementation for more details on tailoring. ═══ 2.3.4.2. Cursor Implementations ═══ Different collection implementations use different cursor classes. For example: o Linked implementations use pointers to nodes. o Array implementations use numeric indices. o Hash tables use an index into the hash table and a pointer to the node in the collision list. o Bags use the key set cursor and a count for equal elements. Each concrete collection class, such as ISet, has an inner definition of a class Cursor that can be accessed as ISet::Cursor. Because abstract classes also declare functions on cursors, there is a base class ICursor for these specific cursor classes. To allow the creation of specific cursors for all kinds of collections, every abstract class has a virtual member function newCursor. newCursor creates an appropriate cursor for the given collection object. ═══ 2.3.4.3. Using Cursors for Locating and Accessing Elements ═══ Cursors provide a basic mechanism for accessing elements of objects of collection classes. All other access mechanisms begin with finding an appropriate cursor and then accessing the element using this cursor. The member function elementAt lets you access an element using a cursor. elementAt returns a reference to an element, thereby avoiding copying the elements. Suppose that an element had a size of 20 KBytes and you want to access a 2-byte data member of that element. If you use elementAt to return a reference to this element, you avoid having to copy the entire element to a local variable. There are several other functions, such as firstElement or elementWithKey that return a reference to an element. They can be thought of as first executing a corresponding cursor function, such as setToFirst or locateElementWithKey, and then accessing the element using the cursor. You must determine if the element exists before accessing it. If its existence is not known from the context, it must first be checked. To save the extra effort of locating the desired element twice (once for checking whether it exists and then for actually retrieving its reference), use the cursor that is returned by the locate function for fast element access: if (locateElementWithKey (key, cursor)) { // ... elementAt (cursor); // ... } The elementAt function can also be used to replace the value of the referenced element. You must ensure that the positioning property of the element is not changed with respect to the given collection. See Adding, Removing, and Replacing Elements for more details. There are two versions of elementAt: Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); The first version of elementAt guarantees that no elements in the collection can be changed by this function. ═══ 2.3.5. Iterating over Collections ═══ Iterating over all or some elements of a collection is a common operation. The Collection Classes provide two methods of iteration: o By cursors o By iterators or iteration functions Ordered (including sorted) collections have a well-defined ordering of their elements, while unordered collections have no defined order in which the elements are visited in an iteration. However, each element is visited exactly once. You cannot add or remove elements from a collection while you are iterating over a collection, or all elements may not be visited once. You cannot use any of the iterations described in this section if you want to remove all of the elements of a collection that have a certain property. Use the function removeAll (described in Flat Collection Member Functions), using a predicate function as argument. See Removing Elements for details on removing elements. ═══ 2.3.5.1. Iteration Using Cursors ═══ Cursor iteration can be done with a for loop. Consider the following example: ISet collection; ISet::Cursor current (collection); for (current.setToFirst (); current.isValid (); current.setToNext ()) { // ... collection.elementAt (current) ; // ... } ISet::Cursor is the class Cursor that is defined within the class ISet. This is referred to as a nested class. current is the name of the cursor object. Its constructor takes collection as argument. The Collection Classes define a macro forCursor that lets you write a cursor iteration even more elegantly: #define forCursor(c) \ for ((c).setToFirst(); \ (c).isValid(); \ (c).setToNext()) // collection and current are the same as before. forCursor(current) { // ... collection.elementAt (current) // ... } If the element is used read-only, a function of the cursor can be used instead of elementAt(current): // collection and current are the same as before. // current's construction associated it to collection. forCursor(current) { // ... current.element () //... } Note: You should remove multiple elements from a collection using the removeAll function, with a predicate function as an argument. See Adding, Removing, and Replacing Elements for further details. ═══ 2.3.5.2. Iteration Using Iterators ═══ Cursor iteration has two possible drawbacks: o For unordered collections, the explicit notion of an (arbitrary) ordering may be undesirable for stylistic reasons. o Iteration in an arbitrary order might be done more efficiently using something other than cursors. For example, with tree representations, a recursive descent iteration may be faster than the cursor navigation, even though the time for extra function calls must be considered. The Collection Classes provides the allElementsDo function that addresses both drawbacks by calling a function that is applied to all elements. The function returns a Boolean value that tells whether the iteration should be continued or not. For ordered collections, the function is applied in this order. Otherwise the order is unspecified. The function that is applied in each iteration step can be given in two ways: o As a C++ function o As an object of an iterator class. The advantage of applying the function as an object of an iterator class is that additional arguments that are needed by the iteration function can be better encapsulated. The C++ function accepts an additional argument for the same purpose. For both these possibilities (the C++ function and the object of an iterator class), an additional distinction is made whether the function leaves the element constant or not. This means that four definitions of the function allElementsDo are offered by every collection. The following example shows the definition of allElementsDo for ISet: template < class Element, ... > class ISet { // ... // Iteration applying a C++ function: Boolean allElementsDo (Boolean (*function)(Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (Boolean (*function)(Element const&, void*), void* additionalArgument = 0) const; // Iteration applying an iterator object: Boolean allElementsDo (IIterator < Element > &); Boolean allElementsDo (IConstantIterator < Element > &) const ; } If you use an object of an iterator class, this class must offer an applyTo function. It also must be derived from the abstract base class IIterator or IConstantIterator. These abstract iterator base classes are defined in the following way: template < class Element > class IIterator { public: virtual Boolean applyTo (Element&) = 0; }; template < class Element > class IConstantIterator { public: virtual Boolean applyTo (Element const&) = 0; }; Additional arguments that are needed for the iteration can, for example, be passed as arguments to the constructor of the derived iterator class. You can define the function with the given argument and return types. For additional arguments, you may have to define a separate class or structure. The following example shows the use of iterators. The example adds all integers in a bag using two methods: by iterating the applied function as an object of an iterator class, or as a function. // sumup.C - An example of using Iterators #include #include typedef IBag < int > IntBag; class SumIterator : public IConstantIterator < int > { int ivSum; public: SumIterator () : ivSum (0) {} Boolean applyTo (int const& i) { ivSum += i; return True; } int sum () { return ivSum; } }; int sumUsingIteratorObject (IntBag const& bag) { SumIterator sumUp; bag.allElementsDo (sumUp); return sumUp.sum (); } Boolean sumUpFunction (int const& i, void* sum) { *(int*)sum += i; return True; }; int sumUsingIteratorFunction (IntBag const& bag) { int sum = 0; bag.allElementsDo (sumUpFunction, &sum); return sum; } int main (int argc, char* argv[]) { IntBag intbag; for (int cnt=1; cnt < argc; cnt++) intbag.add(atoi(argv[cnt])); cout << "Sum obtained using an Iterator Object = " << sumUsingIteratorObject(intbag) << "\n"; cout << "Sum obtained using an Iterator Function = " << sumUsingIteratorFunction(intbag) << "\n"; return 0; } ═══ 2.3.6. Copying and Referencing Collections ═══ The Collection Classes implement no structure sharing between different collection objects. The assignment operator and the copy constructor for collections are defined to copy all elements of the given collection into the assigned or constructed collection. You should remember this if you are using collection types as arguments to functions. If the argument type is not a reference or pointer type, the collection is passed by value, and changes made to the collection within the function do not affect the collection in the calling function. If you want a function to modify a collection, you should pass the collection as a reference: void removePrimes (ISet < int > set) { /* ... */ } // wrong void removePrimes (ISet < int >& set) { /* ... */ } // right For the sake of efficiency you should avoid having a collection type as the return type of a function: ISet < int > f () { ISet < int > result; // ... return result; } // ... intSet = f (); // inefficient In this program intSet becomes a reference argument to the assignment operation, which would again copy the set. A better approach is: void f (ISet < int > &result) { /* ... */ } // ... f (intSet); ═══ 2.4. Element Functions and Key Functions ═══ This chapter describes the functions that are required by member functions of the collection classes to manipulate elements and keys. The following topics are discussed: o Element Functions and Key Functions o Using standard operators to provide element and key functions o Using separate functions o Using element operation classes o Functions for derived element classes. o Values and managed objects ═══ 2.4.1. Introduction to Element Functions and Key Functions ═══ The member functions of the collection classes call other functions to manipulate elements and keys. These functions are called element functions and key functions, respectively. Member functions of the collection classes may, for example, use the element's assignment or copy constructors for adding an element, or may use the element's equality operator for locating an element in the collection. In addition, collection class functions use memory management functions for the allocation and deallocation of dynamically created internal objects (nodes). The element functions that may be required by the Collection Classes are: o Default and copy constructor o Destructor o Assignment o Equality test o Ordering relation o Key access o Hash function The key functions that may be required by the Collection Classes are: o Equality test o Ordering relation o Hash function The memory management functions that may be required by the Collection Classes are: o Allocation o Deallocation The lists above are the superset of all element functions and key functions that a collection class may ever require. For example, a collection without keys does not require a key function and a collection without element equality does not require an equality test. Element functions and key functions required for a certain collection are listed with the description of each collection in the reference parts of this manual. Where possible, these functions are already defined by the Collection Classes. Default memory management functions are provided for usage with any element and key type. For the standard C++ data types int and char*, defaults are offered for all element and key functions. For all other element and key types you must provide these functions. There are three different methods of providing element functions and key functions, each of which offers a different level of flexibility and tailoring. The methods are: 1. Using member functions 2. Using separate functions in the global name space 3. Using element operation classes. The second and third methods can also be used to replace the default memory management functions for some of the collections. ═══ 2.4.2. Using Member Functions to Provide Element and Key Functions ═══ The easiest way to provide the required element or key functions is to use the member functions. For assignment, equality, and ordering relation, operator=, operator==, and operator< are used, respectively. You must define these functions using member functions: o Constructors o Destructors. You cannot define these functions using member functions: o Functions for key access o Functions for hashing o Functions for memory management. Except for assignment, you must define member functions of a class as const. You will get a compile-time error if you do not include const in these definitions. The following example shows how member functions must be defined as const: class Element { public: Element& operator= (Element const&); Boolean operator== (Element const&) const; Boolean operator< (Element const&) const; }; The result type of the assignment operator is irrelevant to the Collection Classes. The result type of equality and ordering relation must be compatible with type Boolean. For some element functions, if they are not defined in any of the three methods, the compiler will generate default element member functions according to C++ language rules. ═══ 2.4.3. Using Separate Functions ═══ You can use separate functions to provide the required element and key functions. Use separate functions when, in instantiating the collection class, you have no control over the element class, and the element class does not define the appropriate functions. You can also use separate functions to provide key access and hash function. The following shows what the declarations for these separate functions must look like: void assign (Element&, Element const&); Boolean equal (Element const&, Element const&); long compare (Element const&, Element const&); Key const& key (Element const&); unsigned long hash (Element const&, unsigned long); Boolean equal (Key const&, Key const&); long compare (Key const&, Key const&); unsigned long hash (Key const&, unsigned long); You can also use separate functions for the standard memory management functions, as defined by the C++ language: void* operator new (size_t); void operator delete (void*); The compare function must return a value that is less than, equal to, or greater than zero, depending on whether the first argument is less than, equal to, or greater than the second argument. The hash function must return a value that is less than the second argument; this may, for example, be achieved by computing the remainder (operator%) with the second argument. The hash function should evenly distribute over the range between zero and the second argument. For equal elements or keys the hash element must yield equal results. For assign, equal, and compare, template functions are defined that will be instantiated unless otherwise defined. The default for assign uses the assignment operator, the default for equal uses the equality operator, and the default for compare uses two comparisons with operator<. It is therefore advisable to define your own compare function if the given element type has a more efficient implementation available. Such definitions are already provided for integer types using operator- and for char* using strcmp. By default, the standard memory management functions are used. The following example demonstrates the use of a separate function for the definition of the key access. The element class is Task, its member data TaskId are the key, and its member function id is used to access the key: typedef unsigned long TaskId; typedef int Priority; class Task { TaskId ivId; Priority ivPriority; public: TaskId id () const { return ivId; } Priority priority () { return ivPriority; } // ... }; // ... TaskId key (Task const& t) // key access { return t.id (); } // ... IKeySet runningTasks; ═══ 2.4.4. Using Element Operation Classes ═══ For each collection, there is one class template that takes a template argument ElementOps. ElementOps is itself a template class that defines all required element/key operations. By default, a standard class template is used that defines these operations by the corresponding element and key functions. For example, these are the definitions of the class templates ILinkedSequence and IGLinkedSequence: template < class Element, class ElementOps > class IGLinkedSequence { /* ... */ }; template < class Element > class ILinkedSequence : public IGLinkedSequence < Element, IStdOps < Element > > { /* ... */ }; The advantage of passing the arguments by an extra class instead of passing them as function pointers is that the class solution allows inlining. Collection classes with the operation class argument have names that begin with IG. IGSequence is an example of a collection class with the operation class argument. You can define such classes and pass them to the IG templates. Use this method in cases where, for two instantiations of collections with the same element or key type, two different key or hash functions are used. The following is a skeleton for operation classes. The keyOps member must only be present for key collections: class ...Ops { void* allocate (size_t); void deallocate (void*); void assign (Element&, Element const&); Boolean equal (Element const&, Element const&); long compare (Element const&, Element const&); Key const& key (Element const&); unsigned long hash (Element const&, unsigned long); class KeyOps { Boolean equal (Key const&, Key const&); long compare (Key const&, Key const&); unsigned long hash (Key const&, unsigned long); } keyOps; }; You can inherit from the following class templates when you define your own operation classes. Templates with argument type T may be used for both the element and the key type. class IStdMemOps { void* allocate (size_t); void deallocate (void*); }; template < class T > class IStdAsOps { void assign (T&, T const&); }; template < class T > class IStdEqOps { Boolean equal (T const&, T const&); }; template < class T > class IStdCmpOps { long compare (T const&, T const&); }; template < class Element, class Key > class IStdKeyOps { Key const& key (Element const&); }; template < class T > class IStdHshOps { unsigned long hash (T const&, unsigned long); }; To define an operation class, use the predefined templates for standard functions, and define the specific functions individually. Consider, for example, tasks that have an identifier and a priority. The identifier might serve as the key in a collection that keeps track of all active tasks, while the priority might be used for implementing priority controlled task queues. Because the key function is already defined to yield the task identifier, the priority queue has to be instantiated in the following way: class TaskPrioOps : public IStdMemOps, public IStdAsOps < Task > { public: Priority key (Task const& t) { return t.priority (); } IStdCmpOps < Priority > keyOps; }; // ... IGPriorityQueue < Task, Priority, TaskPrioOps > taskPriorityQueue; The functions that are required for a particular collection class depend not only on the abstract class but also on the concrete implementation choice. If you choose a set to be implemented through a hash table, the elements require a hash function. If you choose a (sorted) AVL tree implementation, elements need a comparison function. Even the default implementations may require more functions to be provided than would be necessary for the collection interface. Each chapter that describes a particular collection defines which functions must be provided for keys and elements for each implementation of that collection. ═══ 2.4.5. Values and Objects ═══ In C++, variables and function arguments have their values copied when they are assigned. This copying can decrease a program's efficiency, especially when the objects are large. Therefore it is common to use pointers or references for common object semantics. This use includes copying a pointer or reference to the object and enabling polymorphic applications through virtual functions. Pointers to elements can be used as collection element types in such cases. References are not allowed as collection element types. For KeySets, this procedure is illustrated in the following example: (Note that the key function is defined with argument type Task*.) class Task { Task id () const; Priority priority () const; }; TaskId const& key (Task* const& t) { return t->ivId; } IKeySet < Task*, Taskid > tasks; If you have already defined the key function for type Task, you may find it inconvenient to add the extra definition of a pointer to Task, using dereferencing. For collections with element equality, the inconvenience is even greater. Instantiating the collection template with the element pointer type will result in applying pointer comparison for the elements. In general, this result is not intended. Equality and ordering relation could also be provided for Task*. The compiler would not produce an error if these functions were missing, as it would for the key function, but would instantiate the default templates. In the following example, adding, locating, and other functions are based on pointer equality and ordering, and not on the equality defined for the Task type. class Task { TaskId ivId; //... Boolean operator== (Task const& t) { return ivId == t.ivId; } }; ISet < Task* > tasks; // equality refers to pointers For the handling of pointers to elements, the Collection Classes offer a class template IPtr, which is instantiated with the element type. Objects of this class automatically apply all element functions, except for assignment, to the referenced object. IPtr objects are constructed (or converted) from an element pointer. The C++ dereferencing operators * and -> are defined, for IPtr, to refer to the referenced objects. typedef IPtr < Task > TaskPtr; ISet < TaskPtr > taskSet; Task* t = new Task; TaskPtr t1 (t); taskSet.add (t1); //... taskSet.elementAt (cursor)->priority(); //... taskSet.remove (t1); delete t; The dynamically created elements are not automatically deleted when they are removed from the collection. Note: The IPtr class will not work with standard data types such as int, long, and char. ═══ 2.4.5.1. Automatic Storage Management ═══ The class IMgPtr implements a managed pointer class, which is a pointer class as defined in Values and Objects, together with automatic storage management for the referenced element. Automatic storage management is implemented by counting the managed pointers that reference an object. The object is automatically deleted when no more managed pointers refer to it. Its proper behavior requires that the pointer to the element from which the managed pointer is initially constructed is no longer used. For example: typedef IMgPtr < Task > TaskPtr; ISet < TaskPtr > tasks; TaskPtr t1 (new Task); tasks.add (t1); // ... tasks.remove (t1); In the example, the allocated task will automatically be deleted by the remove function unless it is referenced through another TaskPtr. Automatic storage management is particularly useful when functions return pointers or references to objects that they have created (dynamically allocated), and the last user of the object is responsible for cleaning up. The class IMgPtr can also be used for this purpose. Note: The IMgPtr class will not work with standard data types such as int, long, and char ═══ 2.4.6. Functions for Derived Element Classes ═══ One of the C++ language rules states that function template instantiations are considered before conversions. Because the Collection Classes define default templates for element functions, functions such as equal or compare, defined for a class, will not be considered for that class's derived classes; the default template functions will be instantiated instead: class A { /* ... */ }; long compare (A const&, A const&); class B : public A { /* ... */ }; ISortedSet < B > BSet; The example will instantiate the default compare function for class B which uses the operator< of B, if defined. Otherwise, a compilation error occurs, because a member function operator< is not found for class B. You must define standard functions such as equal or compare for the actual element type to prevent the template instantiation of those functions. The classes IPtr and IMgPtr (see Values and Objects) use an extra indirection to ensure that an instantiation such as ISet> uses the correct functions. This indirection is usually transparent but you must consider it when you derive classes from the IPtr class. The standard operation classes first apply a function elementForOps to the element before they apply the corresponding non-member (equal, ...) function. By default, a corresponding template function is instantiated for elementForOps which yields the identity. For IPtr (and similar classes) this function is defined to yield the referenced element instead. If a class derived from IPtr is used as collection element type, the default template functions must be instantiated before a conversion will be considered. A derived class must therefore explicitly redefine the elementForOps function, as shown in the following example: class TaskPtr : public IPtr < Task > { friend Task& elementForOps ( TaskPtr & t ) { return ( Task & ) elementForOps ( t ); } friend Task const & elementForOps ( TaskPtr const & t ) { return ( Task const & ) elementForOps ( t ); } }; ISet < TaskPtr > taskSet; ═══ 2.5. Tailoring a Collection Implementation ═══ This chapter describes how to tailor a collection implementation for your specific applications. It describes the based-on concept and predefined implementation variants. The following topics are discussed: o Introduction to tailoring o Replacing the default implementation o The based-on concept o Provided implementation variants ═══ 2.5.1. Introduction ═══ When you are developing a program that uses a collection, you should begin by using the default implementation and go on to a final tuning phase where you choose implementations according to the actual requirements of your application. You can determine these requirements by profiling or by using other measurement tools. This section describes how to choose between a variety of implementations provided by the Collection Classes as well as how to create your own implementation classes. As described in The Overall Implementation Structure, each abstract data type has several possible implementations. Some of these implementations are basic; that is, the collection class is implemented directly as a concrete class. These basic implementations include: o AVL trees o Hash tables o Linked sequences o Tabular sequences. Other implementations, including bags, are based on other collection classes. The based-on concept provides a systematic framework for choosing the most appropriate implementations. It is also useful for extending the Collection Classes with other basic implementations, such as specific kinds of search trees, and for using these implementations as the basis for other data abstractions such as sets, maps, and bags. ═══ 2.5.2. Replacing the Default Implementation ═══ You can easily replace the default implementation with another implementation. Suppose that you have a key set class called MyType that has been defined with the default implementation IKeySet. The definition of this class would look like this: typedef IKeySet < Element, Key > MyType; If you want to replace the default implementation, which uses an AVL tree, with a hash table implementation, you can replace the above implementation with the following definition: typedef IHashKeySet < Element, Key > MyType; Implementation variants are predefined for basic implementations, like IHashKeySet, as well as for based-on implementations, like ISetOnHashKeySet. ═══ 2.5.3. The Based-On Concept ═══ The Collection Classes achieve a high degree of implementation flexibility by basing several collection class implementations on other abstract classes, rather than by implementing them directly through a concrete implementation variant of the class. This design feature results in an implementation path rather than the selection of an implementation in a single step. The Collection Classes contain type definitions for the most common implementation paths; they are described in the corresponding sections of the Reference Manual. See Possible Implementation Paths for an illustration of implementation paths. The figure is explained in Provided Implementation Variants. The element functions that are needed by a particular implementation depend on all collection class templates that participate in the implementation. While ISet requires at least element equality to be defined, an AVL tree implementation of this set also requires the element type to provide a comparison function. A hash table implementation requires the element type to have an additional hash function. The required element functions for all predefined implementation variants are listed in the chapters for individual collection types in the Reference Manual. For a concrete implementation, such as a Set based on a KeySorted Set that is in turn based on a Tabular Sequence, these class templates have to be plugged together. The plug mechanism requires class templates to be used as template arguments. Because C++ does not allow class templates as template arguments, the Collection Classes implement the plug mechanism using macros. Two macros are provided: o One for defining a template with an additional operation class argument, for example IDefineGSetOnGKeySortedSet. See Using Element Operation Classes. o One for defining a template with only the element type, or the element and key types, as arguments, for example IDefineCollectionWithOps and IDefineKeyCollectionWithOps. The second macro needs, as an element operation class, an argument as is described in section Using Element Operation Classes. Standard operation class templates are predefined that can be used for this purpose. Their names are systematically derived from the operations they define. The name structure is: I[K]Ops where and are a sequence of letters: E for equality, C for comparison, and H for hashing. IEKEHOps, for example, is an operation template providing, besides the basic memory management and element assignment operations, element equality, key equality, and hashing on keys. For the following example, assume you have a specific form of a sorted tree called IGMySortedTree, which is a new implementation for a KeySorted Set. It must exactly implement the interface provided for a KeySortedSet: o It must have three template arguments, the element type, the key type, and an element operations class. o It must implement all of the member functions defined for KeySortedSet A set implementation IGMySet which is based on this new sorted tree is defined like this: IDefineGSetOnGKeySortedSet (IGMySortedTree, IGMySet) IGMySet is defined as a template with the element type and an element operation class as arguments. A template which only takes the element type as argument and which uses the standard element operations for equality and comparison is then defined like this: IDefineCollectionWithOps (IGMySet, IECOps, IMySet) This expands to the code shown below. The expansion is not intended to give you an in-depth understanding of how the mechanism works internally. It merely illustrates the value of the macros. template < class Element, class ElementOps > class IGMySet : IWSetOnKeySortedSet < Element, ElementOps, IGMySortedTree < Element, Element, IOpsWithKey < Element, ElementOps > > > { /* ... constructor redefinition ... */ }; template < class Element > class IMySet : public IGMySet < Element, IECOps < Element > > { /* ... constructor redefinition ... */ }; ═══ 2.5.4. Provided Implementation Variants ═══ Possible Implementation Paths lists the basic and based-on implementations provided by the library. The upper left corner of each cell contains the name of the (abstract) collection class; basic implementations are written in bold letters, while based-on implementations are described by arrows starting from the class that they implement and ending in the (abstract) class on which they are based. An implementation choice for a given class must use either a basic implementation for this class or follow a based-on implementation path that ultimately leads to a basic implementation. The nonbold arrow denote the shortcuts to the basic implementations. Take the example of the Bag abstraction. The Bag is not implemented directly. It can only be based on the KeySet abstraction, which itself is either implemented directly with a HashTable or can be based on the KeySorted Set. The KeySorted Set is either directly implemented as Avl Tree or B* Tree or can be based on the Sequence abstraction. The Sequence is implemented directly as a linked or tabular undiluted or tabular diluted data structure, into which elements are inserted. The insertions preserve the sorting order. Possible Implementation Paths The following table lists the based-on implementations of Collection Classes and the header files that provide the IDefine... macros. Usually, you do not need to use the IDefine... macros. You can use them, however, to define your own implementation variant for a collection class and to integerate it into the scheme of implementation paths shown in Possible Implementation Paths. Macro Name Header File IDefineGBagOnGKeySet ibagks.h IDefineGBagOnGKeySortedSet ibagkss.h IDefineGDequeOnSequence ideqseq.h IDefineGEqualitySequenceOnGSequence iesseq.h IDefineGHeapOnGSequence iheapseq.h IDefineGKeySetOnGKeySortedSet ikskss.h IDefineGKeySortedBagOnGSequence iksbseq.h IDefineGKeySortedSetOnGSequence ikssseq.h IDefineGMapOnGKeySet imapks.h IDefineGMapOnGKeySortedSet imapkss.h IDefineGPriorityQueueOnGKeySortedBag ipquksb.h IDefineGQueueOnSequence iqueseq.h IDefineGRelationOnGKeyBag imapks.h IDefineGSetOnGKeySet isetks.h IDefineGSetOnGKeySortedSet isetkss.h IDefineGSortedBagOnGKeySortedSet isbkss.h IDefineGSortedMapOnGKeySortedSet ismkss.h IDefineGSortedRelationOnGKeySortedBag isrksb.h IDefineGSortedSetOnGKeySortedSet isskss.h IDefineGStackOnSequence istkseq.h ═══ 2.6. Polymorphic Use of Collections ═══ This chapter describes how you can use polymorphism in the Collection Classes. The following topics are discussed: o Introduction to polymorphism o Using reference classes. ═══ 2.6.1. Introduction to Polymorphism ═══ Polymorphism allows you to take an abstract view of an object or function argument and use any concrete objects or arguments that are derived from this abstract view. The collection properties defined in Flat Collections define such abstract views. They are represented in the form of the class hierarchy in The Abstract Class Hierarchy. Polymorphic use of collections differs from polymorphism of the element type. Element polymorphism means that you can use the collections with any elements that provide basic operations like assignment and equality; this kind of polymorphism is implemented by the use of the C++ template concept. This chapter, however, deals with the polymorphic use of collections which means that a function may specify an abstract collection type for its argument, like IACollection, and then accept any concrete collections given as its actual argument. Each abstract class is defined by its functions and their behavior. The most abstract view of a collection is a container without any ordering or any specific element or key properties. Elements can be added to a collection, and a collection can be iterated over. A polymorphic function on collections might be to print all elements; such a function is given as an example in Using Reference Classes. Collections whose elements define equality or key equality provide, in addition to the common collection functions, functions for retrieving element occurrences by a given element or key value. Ordered collections provide the notion of a well-defined ordering of the element occurrences, either by an element ordering relation or by explicit positioning of elements within a sequence. They define operations for positional element access. Sorted collections provide no further functions, but define a more specific behavior, namely that the elements or their keys are sorted. These properties are combined through multiple inheritance: the abstract collection class IEqualitySortedCollection, for example, combines the abstract concepts of element equality and of being sorted, which implies being ordered. If a polymorphic function uses this class as its argument type, the arguments will be sorted, and the function can use functions like contains that are only defined for collections with element equality. Class libraries often make use of polymorphism to implement their functions. For equality collections, for example, a common union operator could be implemented that could be used for all concrete implementations of equality collections. For performance reasons, the Collection Classes do not make use of this mechanism. ═══ 2.6.2. Using Reference Classes ═══ For performance reasons explained in The Overall Implementation Structure, concrete collection classes are not directly derived from abstract classes. Instead, you must use an indirection that "couples" a concrete collection with an abstract class. For each leaf in the collection class hierarchy, IASet, for example, there is an indirection class template called IRSet (see Overall Library Structure). It takes as template arguments the element type and, for key collections, the key type and a concrete collection class that has been instantiated with this element and key type. Instances of this indirection class refer to instances of the concrete collection class. (The R in IRSet stands for reference). The IR classes are derived from the corresponding abstract IA classes and are therefore part of the C++ class hierarchy. Instances of this class can be used wherever an instance (pointer or reference) of an abstract base class is required. The following example defines a universal printer class that accepts an arbitrary collection of tasks and prints their IDs. The elements are printed in the iteration order that is defined for the given collection. The concrete key set running cannot be used as an argument to the printer directly, because IKeySet is not derived from the abstract collection classes. The reference class IRKeySet is used for this purpose. It is instantiated with the element and key type, and with the concrete collection class TaskSet. An instance of this class refRunning is defined by providing running as a constructor argument. refRunning can finally be used as argument to the universal printer. class TaskPrinter { public: print (IACollection < Task* > const& tasks) { cout << "ID ..." ICursor *cursor = tasks.newCursor (); cout << "{ "; forCursor (*cursor) cout << cursor->element ()->id() << ' '; cout << "}\n"; } }; // ... typedef IKeySet < Task*, TaskId > TaskSet; TaskSet running; // ... IRKeySet < Task*, TaskId, TaskSet > refRunning (running); TaskPrinter.print (refRunning); ═══ 2.7. Exception Handling ═══ This chapter describes the exception-handling facilities provided by member functions of the Collection Classes. This chapter includes the following topics: o Introduction to exception handling o Preconditions and defined behavior o Levels of exception checking o List of Collection Classes exceptions o The hierarchy of exceptions ═══ 2.7.1. Introduction to Exception Handling ═══ The C++ exception-handling facilities allow a program to recover from an exception. An exception is a user, logic, or system error that is detected by a function that does not itself deal with the error, but passes the error to a handling function. Exceptions can result from two major sources: o The violation of a precondition o The occurrence of an internal system failure or system restriction. In this chapter, two kinds of functions are discussed. A called function is a Collection Classes function that may throw an exception. A calling function is a function that calls a Collection Classes function. The calling function may be a Collection Classes function or a function you have defined. ═══ 2.7.1.1. Exceptions Caused by Violated Preconditions ═══ A precondition of a called function is a condition that the function requires to be true when it is called. The calling function must assure that this condition holds. The called function implementation may assume that the condition holds without further checking it. If a precondition does not hold, the called function's behavior is undefined. If you want to make your programs more robust and to locate errors in the test phase, the functions your program calls should check to ensure that their preconditions hold. The Collection Class Library enables this checking to be enabled through macro definitions. Because this checking often requires significant overhead, it is turned off by default, and you need only use it while you are testing the system and verifying that preconditions are always met. A call to a function that violates the function's preconditions has two possible results: o If the called function checks its preconditions, the function will throw an exception. o If the function does not check its preconditions, the behavior of the function is undefined. ═══ 2.7.1.2. Exceptions Caused by System Failures and Restrictions ═══ System failures and restrictions are different from precondition violations. You cannot usually anticipate them, and you have no opportunity to verify that such situations, for example storage overflow, will not occur. These exceptions need to be checked for, and an exception should be thrown if they occur. ═══ 2.7.2. Precondition and Defined Behavior ═══ Exceptions are not generally used to change the flow of control of a program under normal circumstances. An example of using exceptions under normal circumstances is a function that iterates through a collection, and exits from the iteration by checking for the exception that is thrown when an invalid cursor is used to access elements. When the iteration is complete, the cursor will no longer be valid, and this exception will be thrown. This is not a good programming practice. A function should explicitly test for the cursor being valid. To make this possible, a function must efficiently test this condition (isValid, for the cursor example). There are situations where the test for a condition can be done more efficiently in combination with performing the actual function. In such cases, it is appropriate, for performance reasons, to make the situation regular (that is, not exceptional) and return the condition as a Boolean result. Consider a function that first tests whether an element exists with a given key, and then accesses it if it exits: if (c.containsElementWithKey (key)) { // ... /* ... */ c.elementWithKey (key) /* ... */ // inefficient // ... } else { // ... } This solution is inefficient because the element is located twice, once to determine if it is in the collection and once to access it. Consider the following example: try { // ... /* ... */ c.elementWithKey (key) /* ... */ // bad: exception expected // ... } catch (INotContainsKeyException) { // ... } This solution is undesirable because an exception is used to change the flow of control of the program. The correct solution is to obtain a cursor together with the containment test, and then to use the cursor for a fast element access: if (c.locateElementWithKey (key, cursor)) { // ... /* ... */ elementAt (cursor) /* ... */ // most efficient // ... } else { //... } ═══ 2.7.3. Levels of Exception Checking ═══ Some preconditions are more difficult to check than others. Consider the following possible preconditions: 1. A cursor for a linked collection implementation still points to an element of a given collection. 2. A collection is not empty. It may be less efficient to check the first precondition in the production version of a program than to check the second precondition. The Collection Classes provide three levels of precondition checking. They are selected by the following macro variable definitions (use, for example, compile flag -DINO_CHECKS): INO_CHECKS Check for memory overflow. Other checks may be eliminated to improve performance. Default Perform all precondition checks, except the check that a cursor actually points to an element of the collection. IALL_CHECKS Perform all precondition checks, including the (costly) check that a cursor actually points to an element of the collection. This extra check can only fail for undefined cursors. ═══ 2.7.4. List of Exceptions ═══ The Collection Classes define the following exceptions: IChildAlreadyExistsException Occurs when you try to add a child to a tree using addAsChild at a position that already contains a child. ICursorInvalidException Two cursor properties may lead to the ICursorInvalidException: o Every time a cursor is created, you must specify the collection that it belongs to. If a function takes a cursor as an argument (such as add, setToFirst, and locate), the function can only be applied to the collection that the cursor belongs to. If the function is applied to another collection, the ICursorInvalidException results. o If a function takes a cursor as an input argument (such as elementAt, removeAt, and replaceAt), the cursor must be valid. A cursor is valid if it actually refers to some element contained in the collection. You can use the isValid function to determine if a cursor is valid. IEmptyException Occurs when a function tries to access an element of an empty collection. Functions that might cause this exception include firstElement and removeFirstElement. IFullException Occurs when a function tries to add an element to a bounded collection that is already full. Functions that might cause this exception include add and addAsFirst. IIdenticalCollectionException Occurs when the function addAllFrom is called with the source collection being the same as the target collection. IInvalidReplacementException Occurs when, during a replaceAt function, the replacing element has different positioning properties (see Replacing Elements) than the positioning properties of the element to be replaced. IKeyAlreadyExistsException Occurs when a function attempts to add an element to a map or sorted map that already has a different element with the same key. Functions that might cause this exception include add and addAllFrom. INotBoundedException Occurs when the function maxNumberOfElements is applied to a collection that is not bounded. INotContainsKeyException Occurs when the function elementWithKey is applied to a collection that does not contain an element with the specified key. IOutOfMemory Occurs when a function cannot obtain the space that it requires. This exception is not the result of a precondition violation. Functions that add an element to a collection, including add and addAsFirst, can cause this exception. IPositionInvalidException Occurs when a function specifies a position that is not valid in a collection. The functions that might cause this exception include elementAtPosition, removeAtPosition, and setToPosition. IRootAlreadyExistsException Occurs when the function addAsRoot is called for a tree that already has a root. ═══ 2.7.5. The Hierarchy of Exceptions ═══ In the Collection Classes, all exceptions are derived from IException. It provides common functions to access information about an exception that has occurred. The direct subclasses of IException used in the Collection Classes are IPreconditionViolation and IResourceExhausted. The following figure shows the hierarchy of exceptions: IException . . │ ├── IPreconditionViolation . . . . │ ├── IChildAlreadyExistsException │ ├── ICursorInvalidException │ ├── IEmptyException │ ├── IFullException │ ├── IIdenticalCollectionException │ ├── InvalidReplacementException │ ├── IKeyAlreadyExistsException │ ├── INotBoundedException │ ├── INotContainsKeyException │ ├── IPositionInvalidException │ └── IRootAlreadyExistsException . . │ │── IResourceExhausted │ . │ ├── IOutOfMemory . . . . Hierarchy of Exceptions ═══ 2.8. Implementation Classes and Header Files ═══ Use this chapter to determine what header files to include in your program when you use a particular implementation class. The following table lists the concrete classes provided by the Collection Classes and their implementations. The first mentioned implementation for each abstract class is the default. Default implementations for an abstract class are not indented in the table, while variant implementations are indented. The default implementation is defined as a template with the given name and can be accessed through the header files specified for each abstract class. The name of the corresponding template with additional operation class argument begins with IG instead of I. For example, template classes IMap and IGMap are defined in the header file imap.h as based on KeySortedSet. Information about the implementation classes, their names and their header files is only necessary for selecting alternative implementations as described in section The Based-On Concept. Class Name Header File Description IBag ibag.h Based on AVL KeySortedSet IWBagOnKSSet ibagkss.h Based on KeySortedSet IEqualitySequence ieqseq.h Based on LinkedSequence IWEqSeqOnSeq iesseq.h Based on Sequence IKeyBag ikeybag.h Hash table for KeyBag IHashKeyBag ihshkb.h Hash table for KeyBag (basic) IKeySet ikeyset.h Based on AVL KeySortedSet IWKeySetOnKSSet ikskss.h Based on KeySortedSet IHashKeySet ihshks.h Hash table for KeySet (basic) IKeySortedBag iksbag.h Based on LinkedSequence IWKSBagOnSeq iksbseq.h Based on Sequence IKeySortedSet iksset.h AVL tree for KeySortedSet IAvlKeySortedSet iavlkss.h AVL tree for KeySortedSet (basic) IMap imap.h Based on AVL KeySortedSet IWMapOnKSSet imapkss.h Based on KeySortedSet IWMapOnKeySet imapks.h Based on KeySet IRelation irel.h Based on Hash table KeyBag IWRelOnKeyBag imapks.h Based on KeyBag ISequence iseq.h Linked sequence ILinkedSequence ilnseq.h Linked sequence (basic) ITabularSequence itbseq.h Tabular sequence (basic) IDilutedSequence itdseq.h Tabular diluted sequence (basic) ISet iset.h Based on AVL KeySortedSet IWSetOnKSSet isetkss.h Based on KeySortedSet IWSetOnKeySet isetks.h Based on KeySet ISortedBag isrtbag.h Based on AVL KeySortedSet IWSrtBagOnKSSet isbkss.h Based on KeySortedSet ISortedMap isrtmap.h Based on AVL KeySortedSet IWSrtMapOnKSSet ismkss.h Based on KeySortedSet ISortedRelation isrtrel.h Based on KeySortedBag on LinkedSequence IWSrtRelOnKSBag isrksb.h Based on KeySortedBag ISortedSet isrtset.h Based on AVL KeySortedSet IWSSetOnKSSet isskss.h Based on KeySortedSet ITabularTree itbtree.h Tabular tree IWDequeOnSeq ideqseq.h Based on Sequence IWPQueOnKSBag ipquksb.h Based on KeySortedBag IWQueueOnSeq iqueseq.h Based on Sequence IWStackOnSeq istkseq.h Based on Sequence ═══ 2.9. Tutorials ═══ The tutorials provided with the IBM Class Library: Collection Classes can help you to learn the concepts of the Collection Classes. They are presented in the same order as the topics in Part 1 of this book. You should be familiar with the information in the first three chapters of this book before beginning the tutorials. The following topics are discussed: o Tutorials for using the default classes o Tutorials that make more advanced use of the classes o Source files for the tutorials o Examples ═══ 2.9.1. Using the Default Classes ═══ When you are learning to use a particular collection, you should first use the default class of that collection, so that you can gain a fundamental understanding of the collection before you approach the implementation variants of the collection. You need to understand the topics covered in the following sections in order to successfully complete the tutorials: Tutorial 1 Use of default implementations (Instantiation and Object Definition) Tutorial 2 Adding, removing and replacing elements in a collection (Adding, Removing, and Replacing Elements) Tutorial 3 Use of a cursor, locating and accessing elements, and the use of iterators (Cursors, Using Cursors for Locating and Accessing Elements, Iterating over Collections) Tutorial 4 Use of exceptions (Exception Handling). After completing the above tutorials, you should be acquainted with the basic features of the Collection Classes. For a more thorough understanding of the Collection Classes, use the tutorials described in Advanced Use. ═══ 2.9.2. Advanced Use ═══ If you want to understand more advanced uses of the classes, use tutorials 5 and 6. You need to understand the topics covered in the following sections in order to successfully complete the tutorials: Tutorial 5 Exchanging implementation variants (Tailoring a Collection Implementation) Tutorial 6 Using abstract base classes to write polymorphic functions (Polymorphic Use of Collections). ═══ 2.9.3. Source Files for the Tutorials ═══ Each tutorial's files are stored in a separate directory. The tutorials are contained in subdirectories with the name ...\tutorial\iclcc\tutor? where ? corresponds to the number of the tutorial (1-6). Every directory contains the following files: read.me Read this to understand the purpose of the tutorial. instruct.txt Instructions to follow. makefile Prepared makefile to compile the example. solution Directory containing a possible solution. You will find prepared .c and .h files, where certain parts are missing. The objective of the tutorials is to apply the information you have learned about the Collection Classes by adding the missing parts for each file. Complete the prepared files following the instructions in instruct.txt. You can compare your solutions to the solutions found in the solution directory. ═══ 2.9.4. Source Files for Examples ═══ The examples contained in this book can get you started on particular classes. Source code and makefiles for the examples are located in ...\ibmclass\samples\iclcc. If you want to understand the examples in more detail, you can read through the .c and .h files. ═══ 2.10. Understanding the Reference Chapters ═══ The reference chapters in this book, with the exception of Flat Collection Functions and Introduction to Trees, follow a standard format. This chapter describes the format for both function and class descriptions. It also lists special types defined by the library that you will need to know about to use the Collection Classes. This chapter discusses the following: o Format of member function descriptions o Format of class descriptions o Types defined for the library ═══ 2.10.1. Format of Member Function Descriptions ═══ This section describes the member function descriptions found in the following chapters: o Flat Collection Functions o N-ary Tree o Cursor o Pointer and Managed Pointer Classes ═══ 2.10.1.1. Order of Functions ═══ In each chapter that describes member functions, the functions are ordered as follows: 1. Constructors 2. Copy constructors 3. Destructors 4. Operators 5. Member functions, arranged alphabetically ═══ 2.10.1.2. Format of Each Function ═══ Each member function consists of the following components: 1. A heading that identifies the name of the function. 2. The function's declaration. This declaration contains the following information: a. The return type, if any. b. The function name, in bold special font. c. The argument list, if any. Tokens that appear in italics are variable names. You can use other names instead if you are calling the function. Tokens that appear in special font are keywords, types, or other tokens that should not be changed, although they may be omitted where the C++ language rules permit. d. The const suffix, if any. 3. An explanation of the action the function performs. 4. Any preconditions the function requires to be met before it is called. 5. Any side effects the function may have on the collection or the cursors associated with it. 6. The return value of the function, unless the function has a return type of void (for example, constructors and destructors). 7. Any exceptions the function may throw, if a precondition is violated or if a system failure or restriction occurs. In the sample member function likeElements below, highlighted numbers and letters correspond to the items in the list and sublist above. The function is not an actual or realistic function of the Collection Class Library, but shows all components of actual member functions. Note that actual member functions may have only some of the headings identified in the example. likeElements1 Boolean2a likeElements2b ( Element elementA, Element elementB)2c const2d ; Performs a subjective comparison of the contents of element elementA and the contents of element elementB.3 Preconditions Both elements must already be contained in the collection.4 Side Effects All cursors of the collection become undefined.5 Return Value Returns True if the elements are sufficiently similar. Otherwise returns False.6 Exceptions o IOutOfMemory o ICursorInvalid7 ═══ 2.10.2. Format of Class Descriptions ═══ This section describes the format of chapters that deal with individual classes or groups of classes. Each such chapter consists of the following components: o The chapter title, which usually refers to the kind of collection being discussed. o A description of the collection's characteristics, such as whether the collection is sorted or unsorted, or whether the type and value of the elements are relevant. o A section on class implementation variants, which provides some or all of the following information: - The default implementation, and the classes that you can use to alter the way the collection is implemented. These variant classes are based on other abstract data types within the Collection Classes. For example, in the chapter on heap collections, the class IHeapOnTabularSequence is a heap collection based on TabularSequence. - The names of the header files that correspond to particular implementation variants, so that you can include those files in your source code to make use of the implementation variants. o A section on template arguments and required parameters, which provides the following information: - Template arguments, which identify what parameters you must supply when you instantiate a particular implementation variant. - Required functions, which are functions that must be provided by the element- or key type you use for any implementation variant. For further information, see Required Functions. o A section on the reference class. The reference class allows you to make use of polymorphism. This section contains information on include files, template arguments and required functions similar to the information provided for the implementation variants described above. In general, reference classes do not put any additional requirements on the element- and key type. The requirements are those of the implementation variant used with the reference class. o An extract from the declarations file that shows the interface for an abstraction, its member functions and data members. The name of the default implementation is used in this extract to represent any of the implementation variants. The extracts have been edited for clarity and brevity. You should include the appropriate implementation variant header file, rather than this declarations file, in any programs you develop that use any implementation variant of the abstract data type. For this reason, the name of the declarations file is not given. o Optionally, a coding example to show you how to use the collection. ═══ 2.10.2.1. Required Functions ═══ As described in Element Functions and Key Functions, the Collection Classes require that you provide certain functions for the element- and key type. These functions are required by member functions of the Collection Classes to manipulate elements and keys. The functions you must provide depend on the abstraction you use and on the implementation variant you choose. For example, you will usually need to provide a key access for all keyed abstractions, and for a hash table implementation you will need to provide a hash function. ═══ 2.10.3. Types Defined for the Collection Classes Library ═══ In the header file iglobals.h, the following types are defined for using the library: typedef int IBoolean; const IBoolean False = 0; const IBoolean True = 1; typedef IBoolean Boolean; typedef unsigned long INumber; typedef unsigned long IPosition; enum ITreeIterationOrder {IPreorder, IPostorder}; // for N-ary tree only Note: If your environment defines another Boolean, do the following: 1. Erase the line typedef IBoolean Boolean from your iglobals.h file. 2. Use IBoolean wherever you want to refer to Boolean in the context of the Collection Classes. ═══ 3. Reference Manual - Flat Collections ═══ This part contains detailed descriptions of the flat collections of the IBM Class Library: Collection Classes. Flat Collection Functions describes the common member functions for flat collections. Subsequent chapters describe individual collection classes. For information on the organization of chapters that describe individual abstract data types, see Format of Class Descriptions. The following flat collections are described in this part: o Bag o Deque o Equality sequence o Heap o Key bag o Key set o Key sorted bag o Key sorted set o Map o Priority queue o Queue o Relation o Sequence o Set o Sorted bag o Sorted map o Sorted relation o Sorted set o Stack ═══ 3.1. Flat Collection Functions ═══ Some of the terms used in this chapter are defined below. You can also use the Glossary to look up terms you are unfamiliar with. This chapter lists all the functions of flat collections and defines some of the terms used. ═══ 3.1.1. Terms Used ═══ CLASS_BASE_NAME Represents the name of the class without any template arguments, of which the function is a member. CLASS_NAME Represents the name of the class with template arguments of which the function is a member. equal element Refers to equality of elements as defined by the equality operation or ordering relation provided for the element type (see Element Functions and Key Functions). It is not defined whether the equality operation or the ordering relation is used to determine element equality in cases where both are provided. given ... Refers to an argument of the described function, such as given element, given key, or given collection. iteration order The order in which elements are visited in allElementsDo and setToNext or setToPrevious. In ordered collections the element at position 1 will be visited first, then the element at position 2, and so on. Sorted collections, in particular, are visited following the ordering relation provided for the element type. In collections that are not ordered the elements are visited in an arbitrary order. Each element is visited exactly once. positioning property The property of an element that is used to position the element in a collection. For key collections, the positioning property is key equality. For non-sequential collections with element equality the positioning property is element equality. Other collections have no positioning property. same key Refers to equality of keys as defined by the equality operation or ordering relation provided for the key type (see Element Functions and Key Functions). It is not defined whether the equality operation or the ordering relation will be used to determine key equality in case where both are provided. this collection The collection to which a function is applied. Contrast with the given collection, which is an argument supplied to a function. The collection is used synonymously with this collection. undefined cursor Indicates that it is undefined whether the cursor is invalidated or remains valid. Even if it remains valid, it may refer to a different element than before, or even to no element of the collection. You should not use cursors, once they become undefined, in functions that require the cursor to point to an element of the collection. ═══ 3.1.2. Flat Collection Member Functions ═══ Each flat collection implements some or all of the member functions described in this chapter. You can tell which functions a particular flat collection implements by looking at the declarations in the header file for that class. The following member functions are described: Constructor Copy Constructor Destructor operator!= operator= operator== add addAllFrom addAsFirst addAsLast addAsNext addAsPrevious addAtPosition addDifference addIntersection addOrReplaceElementWithKey addUnion allElementsDo allElementsDo anyElement compare contains containsAllFrom containsAllKeysFrom containsElementWithKey copy dequeue differenceWith elementAt elementAtPosition elementWithKey enqueue firstElement intersectionWith isbounded isEmpty isFirst isFull isLast key lastElement locate locateElementWithKey locateFirst locateLast locateNext locateNextElementWithKey locateOrAdd locateOrAddElementWithKey locatePrevious maxNumberOfElements newCursor numberOfDifferentElements numberOfDifferentKeys numberOfElements numberOfElementsWithKey numberOfOccurrences pop push remove removeAllElementsWithKey removeAllOccurrences removeAll removeAll removeAt removeAtPosition removeElementWithKey removeFirst removeLast replaceAt replaceElementWithKey setToFirst setToLast setToNext setToNextDifferentElement setToNextWithDifferentKey setToPosition setToPrevious sort top unionWith ═══ 3.1.2.1. Constructor ═══ CLASS_BASE_NAME ( INumber numberOfElements = 100 ) ; Constructs a collection. numberOfElments is the estimated maximum number of elements contained in the collection. The collection is unbounded and is initially empty. If the estimated maximum is exceeded, the collection is automatically enlarged. Note: The collection constructor does not define whether any elements are constructed when the collection is constructed. For some classes, the element's default constructor may be invoked when the collection's constructor is invoked. This is done, for example, when initializing empty elements in advance in a tabular implementation. Exception IOutOfMemory ═══ 3.1.2.2. Copy Constructor ═══ CLASS_BASE_NAME ( CLASS_NAME const& collection ) ; Constructs a collection and copies all elements from the given collection into the collection as described for addAllFrom. Exception IOutOfMemory ═══ 3.1.2.3. Destructor ═══ ~CLASS_BASE_NAME ( ) ; Removes all elements from the collection. Destructors are called for all elements contained in the collection and for elements that have been constructed in advance (see Constructor). Side Effects All cursors of the collection become undefined. ═══ 3.1.2.4. operator!= ═══ Boolean operator != ( CLASS_NAME const& collection ) const; Returns True if the given collection is not equal to the collection. For a definition of equality for collections, see operator==. ═══ 3.1.2.5. operator= ═══ CLASS_NAME& operator= ( CLASS_NAME const& collection ) ; Copies the given collection to the collection. Removes all elements from the collection and adds the elements from the given collection as described for addAllFrom. Preconditions o If the collection is bounded then numberOfElements of the given colelction must be less than maxNumberOfElements of this collection. Side Effects All cursors of this collection become undefined. Return Value Returns a reference to the collection. Exceptions o IOutOfMemory o IFullException, if the collection is bounded ═══ 3.1.2.6. operator== ═══ Boolean operator== ( CLASS_NAME const& collection ) const; Returns True if the given collection is equal to the collection. Two collections are equal if the number of elements in each collection is the same, and if the condition for the collection is described in the following list: Type of Collection Condition Unique Elements If the collections have unique elements, any element that occurs in one collection must occur in the other collection. Non-Unique Elements If an element has N occurrences in one collection it must have exactly N occurrences in the other collection. Sequential The ordering of the elements is the same for both collections. ═══ 3.1.2.7. add ═══ Boolean add ( Element const& element ) ; Boolean add ( Element const& element, ICursor& cursor ) ; If the collection is unique (with respect to elements or keys) and the element or key is already contained in the collection, sets the cursor to the existing element in the collection without adding the element. Otherwise, it adds the element to the collection and sets the cursor to the added element. In sequential collections, the given element is added as the last element. In sorted collections, the element is added at a position determined by the element or key value. Adding an element will either use the element's copy constructor or the assignment operator provided for the element type, depending on the implementation variant you choose. See contains for the definition of element or key containment. Preconditions o The cursor must belong to the collection. o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If an element was added, all cursors of this collection, except the given cursor, become undefined. Return Value Returns True if the element was added. Exceptions o IOutOfMemory o ICursorInvalidException o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map ═══ 3.1.2.8. addAllFrom ═══ void addAllFrom ( CLASS_NAME const& collection ) ; void addAllFrom ( IACollection const& collection ) ; Adds (copies) all elements of the given collection to the collection. The elements are added in the iteration order of the given collection. The contents of the elements, as opposed to the pointers to the elements, are copied. The elements are added according to the definition of add for this collection. The given collection is not changed. Preconditions Since the elements are added one by one, the following preconditions are tested for each individual add operation: o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If any elements were added, all cursors of this collection become undefined. Exceptions o IOutOfMemory o IIdenticalCollectionException o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map ═══ 3.1.2.9. addAsFirst ═══ void addAsFirst ( Element const& element ) ; void addAsFirst ( Element const& element, ICursor& cursor ) ; Adds the element to the collection as the first element in sequential order. Sets the cursor to the added element. Preconditions o The cursor must belong to the collection. o If the collection is bounded, Side Effects All cursors of this collection, except the given cursor, become undefined. (numberOfElements < maxNumberOfElements). Exceptions o ICursorInvalidException o IOutOfMemory o IFullException, if the collection is bounded ═══ 3.1.2.10. addAsLast ═══ void addAsLast ( Element const& element ) ; void addAsLast ( Element const& element, ICursor& cursor ) ; Adds the element to the collection as the last element in sequential order. Sets the cursor to the added element. Preconditions o The cursor must belong to the collection. o If the collection is bounded, (numberOfElements < maxNumberOfElements). Side Effects All cursors of this collection, except the given cursor, become undefined. Exceptions o ICursorInvalidException o IOutOfMemory o IFullException, if the collection is bounded ═══ 3.1.2.11. addAsNext ═══ void addAsNext ( Element const& element, ICursor& cursor ) ; Adds the element to the collection as the element following element pointed to by the cursor. Sets the cursor to the added element. Preconditions o The cursor must belong to the collection and must point to an element of the collection. o If the collection is bounded, (numberOfElements < maxNumberOfElements). Side Effects All cursors of this collection, except the given cursor, become undefined. Exceptions o IOutOfMemory o ICursorInvalidException o IFullException, if the collection is bounded ═══ 3.1.2.12. addAsPrevious ═══ void addAsPrevious ( Element const& element, ICursor& cursor ) ; Adds the element to the collection as the element preceding the element pointed to by the cursor. Sets the cursor to the added element. Preconditions o The cursor must belong to the collection and must point to an element of the collection. o If the collection is bounded, (numberOfElements < maxNumberOfElements). Side Effects All cursors of this collection, except the given cursor, become undefined. Exceptions o IOutOfMemory o ICursorInvalidException o IFullException, if the collection is bounded ═══ 3.1.2.13. addAtPosition ═══ void addAtPosition ( IPosition position, Element const& element ) ; void addAtPosition ( IPosition position, Element const& element, ICursor& cursor ) ; Adds the element at the given position to the collection. If an element exists at the given position, the new element will be added as the element preceding the existing element. Sets the cursor to the added element. Position 1 specifies the first element. Preconditions o The cursor must belong to the collection. o (1 =< position =< numberOfElements + 1). o If the collection is bounded, (numberOfElements < maxNumberOfElements). Side Effects All cursors of this collection become undefined except the given cursor. Exceptions o IOutOfMemory.exmp. o ICursorInvalidException o IPositionInvalidException o IFullException, if the collection is bounded ═══ 3.1.2.14. addDifference ═══ void addDifference ( CLASS_NAME const& collection1, CLASS_NAME const& collection2 ) ; Creates the difference between the two given collections, and adds this difference to the collection. The contents of the added elements, as opposed to the pointers to those elements, are copied. For a definition of the difference between two collections, see differenceWith. Preconditions Since the elements are added one by one, the following preconditions are tested for each individual addition. o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If any elements were added, all cursors of this collection become undefined. Exceptions o IOutOfMemory o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map ═══ 3.1.2.15. addIntersection ═══ void addIntersection ( CLASS_NAME const& collection1, CLASS_NAME const& collection2 ) ; Creates the intersection of the two given collections, and adds this intersection to the collection. The contents of the added elements, as opposed to the pointers to those elements, are copied. For a definition of the intersection of two collections, see intersectionWith. Preconditions Since the elements are added one by one, the following preconditions are tested for each individual addition. o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If any elements were added, all cursors of this collection become undefined. Exceptions o IOutOfMemory o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map ═══ 3.1.2.16. addOrReplaceElementWithKey ═══ Boolean addOrReplaceElementWithKey ( Element const& element ) const; Boolean addOrReplaceElementWithKey ( Element const& element, ICursor& cursor ) ; If an element is contained in the collection where the key is equal to the key of the given element, sets the cursor to this element in the collection and replaces it with the given element. Otherwise, it adds the given element to the collection, and sets the cursor to the added element. If the given element is added, the contents of the element, as opposed to a pointer to it, is added. Preconditions o The cursor must belong to the collection. o If the collection is bounded, an element with the given key must be contained in the collection, or (numberOfElements < maxNumberOfElements). Side Effects If the element was added, all cursors of this collection, except the given cursor, become undefined. Return Value Returns True if the element was added. cp 3 Exceptions o IOutOfMemory o ICursorInvalidException o IFullException, if the collection is bounded ═══ 3.1.2.17. addUnion ═══ void addUnion ( CLASS_NAME const& collection1, CLASS_NAME const& collection2 ) ; Creates the union of the two given collections, and adds this union to the collection. The contents of the added elements, as opposed to the pointers to those elements, are copied. For a definition of the union of two collections, see unionWith. Preconditions Since the elements are added one by one, the following preconditions are tested for each individual addition. o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If any elements were added, all cursors of this collection become undefined. Exceptions o IOutOfMemory o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map ═══ 3.1.2.18. allElementsDo ═══ Boolean allElementsDo ( Boolean (*function) (Element&, void*), void* additionalArgument = 0 ) ; Boolean allElementsDo ( Boolean (*function) (Element const&, void*), void* additionalArgument = 0 ) const; Calls the given function for all elements in the collection until the given function returns False. The elements are visited in iteration order. Additional arguments can be passed to the given function using additionalArgument. The additional argument defaults to zero if no additional argument is given. Note: 1. The given function must not remove elements from or add them to the collection. If you want to remove elements, you can use the removeAll function with a property argument. For further information see removeAll. 2. For the non-const version of allElementsDo, the given function must not manipulate the element in the collection in a way that changes the positioning property of the element. Return Value Returns True if the given function returns True for every element it is applied to. ═══ 3.1.2.19. allElementsDo ═══ Boolean allElementsDo ( IIterator & iterator ) ; Boolean allElementsDo ( IConstantIterator & iterator ) const; Calls the applyTo function of the given iterator for all elements of the collection until the applyTo function returns False. The elements are visited in iteration order. Additional arguments may be passed as arguments to the constructor of the derived iterator class (for further details see Iteration Using Iterators). Note: 1. The applyTo function must not remove elements from or add elements to the collection. If you want to remove elements, you can use the removeAll function with a property argument. For further information see removeAll. 2. For the non-const version of allElementsDo, the applyTo function must not manipulate the element in the collection in a way that changes the positioning property of the element. Return Value Returns True if the applyTo function returns True for every element it is applied to. ═══ 3.1.2.20. anyElement ═══ Element const& anyElement ( ) const; Returns a reference to an arbitrary element of the collection. Precondition The collection must not be empty. Exception IEmptyException ═══ 3.1.2.21. compare ═══ long compare ( CLASS_NAME const& collection, long (*comparisonFunction) (Element const& element1,Element const& element2) ) const; Lexicographically compares the collection with the given collection. Comparison yields <0 if the collection is less than the given collection, 0 if the collection is equal to the given collection, and >0 if the collection is greater than the given collection. Lexicographic comparison is defined by the first pair of corresponding elements, in both collections, that are not equal. If such a pair exists, the collection with the greater element is the greater one. Otherwise, the collection with more elements is the greater one. Note: The given comparison function must return a result according to the following rules: >0 if element1 > element2, 0 if element1 == element2, <0 if element1 < element2. Return Value Returns the result of the collection comparison. ═══ 3.1.2.22. contains ═══ Boolean contains ( Element const& element ) const; Returns True if the collection contains an element equal to the given element. ═══ 3.1.2.23. containsAllFrom ═══ Boolean containsAllFrom ( CLASS_NAME const& collection ) const; Boolean containsAllFrom ( IACollection const& collection ) const; Returns True if all the elements of the given collection are contained in the collection. The definition of containment is described in contains. ═══ 3.1.2.24. containsAllKeysFrom ═══ Boolean containsAllKeysFrom ( CLASS_NAME const& collection ) const; Boolean containsAllKeysFrom ( IACollection const& collection ) const; Returns True if all of the keys of the given collection are contained in the collection. ═══ 3.1.2.25. containsElementWithKey ═══ Boolean containsElementWithKey ( Key const& key ) const; Returns True if the collection contains an element with the same key as the given key. ═══ 3.1.2.26. copy ═══ void copy ( IACollection const& collection ) ; Copies the given collection to this collection. copy removes all elements from this collection, and adds the elements from the given collection. For information on how adding is done see addAllFrom. Note: The given collection may be of another concrete type than the collection itself. In this case, copying implicitly performs a conversion. If, for example, the given collection is a bag and the collection itself is a set, elements with multiple occurrences in the copied bag will only occur once in the resulting set. Preconditions Since the elements are copied one by one, the following preconditions are tested for each individual copy operation: o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects All cursors of this collection become undefined. Exceptions o IOutOfMemory o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection has unique keys. This exception may be thrown, for example, when copying a bag into a map.) ═══ 3.1.2.27. dequeue ═══ void dequeue ( ) ; void dequeue ( Element& element ) ; Copies the first element of the collection to the given element, and removes it from the collection. Precondition The collection must not be empty. Side Effects All cursors of this collection become undefined. Exception IEmptyException ═══ 3.1.2.28. differenceWith ═══ void differenceWith ( CLASS_NAME const& collection ) ; Makes the collection the difference between the collection and the given collection. The difference of A and B (A minus B) is the set of elements that are contained in A but not in B. The following rule applies for bags with duplicate elements: If bag P contains the element X m times and bag Q contains the element X n times, then the difference of P and Q contains the element X m-n times if m > n, and zero times if m=0 if (element1 > element2) 0 if (element1 == element2) <0 if (element1 < element2) Side Effects All cursors of this collection become undefined. ═══ 3.1.2.80. top ═══ Element const& top ( ) const; Returns a reference to the last element of the collection. Precondition The collection must not be empty. Exception IEmptyException ═══ 3.1.2.81. unionWith ═══ void unionWith ( CLASS_NAME const& collection ) ; Makes the collection the union of the collection and the given collection. The union of A and B is the set of elements which are members of A or B or both. The following rule applies for bags with duplicate elements: If bag P contains the element X m times and bag Q contains the element X n times, the union of P and Q contains the element X m+n times. Preconditions Since the elements from the given collection are added to the collection one by one, the following preconditions are tested for each individual add operation : o If the collection is bounded and unique, the element or key must exist or (numberOfElements < maxNumberOfElements). o If the collection is bounded and nonunique, then (numberOfElements < maxNumberOfElements). o If the collection is a map and contains an element with the same key as the given element, then this element must be equal to the given element. Side Effects If any elements were added to the collection, all cursors of this collection become undefined. Exceptions o IOutOfMemory o IFullException, if the collection is bounded o IKeyAlreadyExistsException, if the collection is a map Note: This function is not provided for equality sequences. ═══ 3.2. Bag ═══ A bag is an unordered collection of zero or more elements with no key. Multiple elements are supported. A request to add an element that already exists is not ignored. Combination of Flat Collection Properties gives an overview of the properties of a bag and its relationship to other flat collections. The following rule applies for duplicates: If bag P contains the element X m times and bag Q contains the element X n times, then the union of P and Q contains the element X m+n times, the intersection of P and Q contains the element X MIN(m,n) times, and the difference of P and Q contains the element X m-n times if m is > n, and zero times if m is =< n. Note: All member functions of bag are described under "List of Functions". ═══ 3.2.1. Class Implementation Variants ═══ IBag, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IBag ibag.h AVL KeySortedSet IGBag ibag.h AVL KeySortedSet IBagOnBSTKeySortedSet ibagbst.h B* KeySortedSet IGBagOnBSTKeySortedSet ibagbst.h B* KeySortedSet IBagOnSortedLinkedSequence ibagsls.h Linked Sequence IGBagOnSortedLinkedSequence ibagsls.h Linked Sequence IBagOnSortedTabularSequence ibagsts.h TabularSequence IGBagOnSortedTabularSequence ibagsts.h TabularSequence IBagOnSortedDilutedSequence ibagsds.h DilutedSequence IGBagOnSortedDilutedSequence ibagsds.h DilutedSequence IBagOnHashKeySet ibaghks.h HashKeySet IGBagOnHashKeySet ibaghks.h HashKeySet ═══ 3.2.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for bags: o Bag o Bag on B* Key Sorted Set o Bag on Sorted Linked Sequence o Bag on Sorted Tabular Sequence o Bag on Sorted Diluted Sequence o Bag on Hash Key Set ═══ 3.2.2.1. Bag ═══ IBag IGBag The default implementation of the class IBag requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.2.2.2. Bag on B* Key Sorted Set ═══ IBagOnBSTKeySortedSet IGBagOnBSTKeySortedSet The default implementation of the class IBagOnBSTKeySortedSet requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.2.2.3. Bag on Sorted Linked Sequence ═══ IBagOnSortedLinkedSequence IGBagOnSortedLinkedSequence The implementation of the class IBagOnSortedLinkedSequence requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.2.2.4. Bag on Sorted Tabular Sequence ═══ IBagOnSortedTabularSequence IGBagOnSortedTabularSequence The implementation of the class IBagOnSortedTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.2.2.5. Bag on Sorted Diluted Sequence ═══ IBagOnSortedDilutedSequence IGBagOnSortedDilutedSequence The implementation of the class IBagOnSortedDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.2.2.6. Bag on Hash Key Set ═══ IBagOnHashKeySet IGBagOnHashKeySet The implementation of the class IBagOnHashKeySet requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Hash function ═══ 3.2.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IABag, which is found in the iabag.h header file, or the corresponding reference class, IRBag, which is found in the irbag.h header file. See Polymorphic Use of Collections for further information. ═══ 3.2.3.1. Template Arguments and Required Functions ═══ IABag IRBag The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.2.4. Declarations for Bag ═══ template < class Element > class IBag { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IBag (INumber numberOfElements = 100); IBag (IBag < Element > const&); IBag < Element >& operator = (IBag < Element > const&); ~IBag (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IBag < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (IBag < Element > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); INumber numberOfOccurrences (Element const&) const; Boolean locateNext (Element const&, ICursor&) const; INumber removeAllOccurrences(Element const&); INumber numberOfDifferentElements () const; Boolean setToNextDifferentElement (ICursor&) const; Boolean operator == (IBag < Element > const&) const; Boolean operator != (IBag < Element > const&) const; void unionWith (IBag < Element > const&); void intersectionWith (IBag < Element > const&); void differenceWith (IBag < Element > const&); void addUnion (IBag < Element > const&, IBag < Element > const&); void addIntersection (IBag < Element > const&, IBag < Element > const&); void addDifference (IBag < Element > const&, IBag < Element > const&); }; ═══ 3.3. Deque ═══ A deque or double-ended queue is a sequence with restricted access. It is an ordered collection of elements with no key and no element equality. The elements are arranged so that each collection has a first and a last element, each element except the last has a next element, and each element but the first has a previous element. You can only add or remove the first or last element. The type and value of the elements are irrelevant, and have no effect on the behavior of the collection. Note: All member functions of deque are described under "List of Functions". ═══ 3.3.1. Class Implementation Variants ═══ IDeque, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IDeque ideque.h LinkedSequence IGDeque ideque.h LinkedSequence IDequeOnTabularSequence idquts.h TabularSequence IGDequeOnTabularSequence idquts.h TabularSequence IDequeOnDilutedSequence idquds.h DilutedSequence IGDequeOnDilutedSequence idquds.h DilutedSequence ═══ 3.3.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for deques: o Deque o Deque on Tabular Sequence o Deque on Diluted Sequence ═══ 3.3.2.1. Deque ═══ IDeque IGDeque The default implementation of the class IDeque requires the following element functions: Element Type o Copy constructor o Destructor o Assignment ═══ 3.3.2.2. Deque on Tabular Sequence ═══ IDequeOnTabularSequence IGDequeOnTabularSequence The implementation of the class IDequeOnTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment ═══ 3.3.2.3. Deque on Diluted Sequence ═══ IDequeOnDilutedSequence IGDequeOnDilutedSequence The implementation of the class IDequeOnDilutedSequence requires the following element functions: Element Type o Default constructor o copy constructor o Assignment ═══ 3.3.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IADeque, which is found in the iadeque.h header file, or the corresponding reference class, IRDeque, which is found in the irdeque.h header file. See Polymorphic Use of Collections for further information. ═══ 3.3.3.1. Template Arguments and Required Functions ═══ IADeque IRDeque The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.3.4. Declarations for Deque ═══ template < class Element > class IDeque { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IDeque (INumber numberOfElements = 100); IDeque (IDeque < Element > const&); IDeque < Element >& operator = (IDeque < Element > const&); ~IDeque (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IDeque < Element > const&); Element const& elementAt (ICursor const&) const; Element const& anyElement () const; void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; void removeFirst (); void removeLast (); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IDeque < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void addAsFirst (Element const&); void addAsFirst (Element const&, ICursor&); void addAsLast (Element const&); void addAsLast (Element const&, ICursor&); }; ═══ 3.3.5. Coding Example for Deque ═══ The following program uses the default deque class, IDeque, to create a deque. It fills the deque with characters by adding them to the back end. The program then removes the characters from alternating ends of the deque (beginning with the front end) until the deque is empty. The program uses the constant iterator class, IConstantIterator, when printing the collection. It uses the addAsLast function to fill the deque and the numberOfElements function to determine the deque's size. It uses the functions firstElement, removeFirst, lastElement, and removeLast to empty the deque. // letterdq.C - An example of using a Deque. #include #include #include // Let's use the default deque typedef IDeque Deque; // The deque requires iteration to be const typedef IConstantIterator CharIterator; class Print : public CharIterator { public: Boolean applyTo(char const&c) { cout << c; return True; } }; // Test variables char *String = "Teqikbonfxjme vralz o.gdya eospu o wr cu h"; // Main program int main() { Deque D; char C; Boolean ReadFront = True; int i; // Put all characters in the deque. // Then read it, changing the end to read from // with every character read. cout << "\nAdding characters to the back end of the deque:\n"; for (i = 0; String[i] != 0; i ++) { D.addAsLast(String[i]); cout << String[i]; } cout << "\n\nCurrent number of elements in the deque: " << D.numberOfElements() << "\n"; cout << "\nContents of the deque:\n"; Print Aprinter; D.allElementsDo(Aprinter); cout << "\n\nReading from the deque one element from front, one " "from back, and so on:\n"; while (!D.isEmpty()) { if (ReadFront) // Read from front of Deque { C = D.firstElement(); // Get the character D.removeFirst(); // Delete it from the Deque } else { C = D.lastElement(); D.removeLast(); } cout << C; ReadFront = !ReadFront; // Switch to other end of Deque } return(0); } The program produces the following output: Adding characters to the back end of the deque: Teqikbonfxjme vralz o.gdya eospu o wr cu h Current number of elements in the deque: 43 Contents of the deque: Teqikbonfxjme vralz o.gdya eospu o wr cu h Reading from the deque one element from front, one from back, and so on: The quick brown fox jumpes over a lazy dog. ═══ 3.4. Equality Sequence ═══ An equality sequence is an ordered collection of elements. The elements are arranged so that each collection has a first and a last element, each element except the last has a next element, and each element but the first has a previous element. An equality sequence supports element equality, which gives you the ability, for example, to search for particular elements. Combination of Flat Collection Properties gives an overview of the properties of an equality sequence and of its relationship to other flat collections. Note: All member functions of equality sequence are described under "List of Functions". ═══ 3.4.1. Class Implementation Variants ═══ IEqualitySequence, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IEqualitySequence ieqseq.h LinkedSequence IGEqualitySequence ieqseq.h LinkedSequence IEqualitySequence- ieqts.h TabularSequence OnTabularSequence IGEqualitySequence ieqts.h TabularSequence IEqualitySequence- ieqds.h DilutedSequence OnDilutedSequence IGEqualitySequence ieqds.h DilutedSequence ═══ 3.4.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for equality sequences: o Equality Sequence o Equality Sequence on Tabular Sequence o Equality Sequence on Diluted Sequence ═══ 3.4.2.1. Equality Sequence ═══ IEqualitySequence IGEqualitySequence The default implementation of IEqualitySequence requires the following element functions: Element Type o Assignment o Equality test ═══ 3.4.2.2. Equality Sequence on Tabular Sequence ═══ IEqualitySequenceOnTabularSequence IGEqualitySequenceOnTabularSequence The implementation of the class IEqualitySequenceOnTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test ═══ 3.4.2.3. Equality Sequence on Diluted Sequence ═══ IEqualitySequenceOnDilutedSequence IGEqualitySequenceOnDilutedSequence The implementation of the class IEqualitySequenceOnDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test ═══ 3.4.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAEqSeq, which is found in the iaeqseq.h header file, or the corresponding reference class, IREqSeq, which is found in the ireqseq.h header file. See Polymorphic Use of Collections for further information. ═══ 3.4.3.1. Template Arguments and Required Functions ═══ IAEqSequ IREqSequ The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.4.4. Declarations for Equality Sequence ═══ template < class Element > class IEqualitySequence { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IEqualitySequence (INumber numberOfElements = 100); IEqualitySequence (IEqualitySequence < Element > const&); IEqualitySequence < Element >& operator = (IEqualitySequence < Element > const&); ~IEqualitySequence (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IEqualitySequence < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (IEqualitySequence < Element > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); INumber numberOfOccurrences (Element const&) const; Boolean locateNext (Element const&, ICursor&) const; INumber removeAllOccurrences (Element const&); Boolean operator == (IEqualitySequence < Element > const&) const; Boolean operator != (IEqualitySequence < Element > const&) const; void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IEqualitySequence < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void addAsFirst (Element const&); void addAsFirst (Element const&, ICursor&); void addAsLast (Element const&); void addAsLast (Element const&, ICursor&); void addAsNext (Element const&, ICursor&); void addAsPrevious (Element const&, ICursor&); void addAtPosition (IPosition, Element const&); void addAtPosition (IPosition, Element const&, ICursor&); void sort (long (*comparisonFunction) (Element const&, Element const&)); Boolean locateFirst (Element const&, ICursor&) const; Boolean locateLast (Element const&, ICursor&) const; Boolean locatePrevious (Element const&, ICursor&) const; }; ═══ 3.5. Heap ═══ A heap is an unordered collection of zero or more elements with no key. Element equality is not supported. Multiple elements are supported. The type and value of the elements are irrelevant, and have no effect on the behavior of the heap. Combination of Flat Collection Properties illustrates the properties of a heap and of its relationship to other flat collections. Note: All member functions of heap are described under "List of Functions". ═══ 3.5.1. Class Implementation Variants ═══ IHeap, the first class in the table below, is the default implementation variant. If you need to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IHeap iheap.h LinkedSequence IGHeap iheap.h LinkedSequence IHeapOnTabularSequence iheapts.h TabularSequence IGHeapOnTabularSequence iheapts.h TabularSequence IHeapOnDilutedSequence iheapds.h DilutedSequence IGHeapOnDilutedSequence iheapds.h DilutedSequence ═══ 3.5.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for heaps: o Heap o Heap on Tabular Sequence o Heap on Diluted Sequence ═══ 3.5.2.1. Heap ═══ IHeap IGHeap The default implementation of IHeap requires the following element functions: Element Type o Copy constructor o Assignment ═══ 3.5.2.2. Heap on Tabular Sequence ═══ IHeapOnTabularSequence IGHeapOnTabularSequence The implementation of the class IHeapOnTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Assignment ═══ 3.5.2.3. Heap on Diluted Sequence ═══ IHeapOnDilutedSequence IGHeapOnDilutedSequence The implementation of the class IHeapOnDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor ═══ 3.5.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAHeap, which is found in the iaheap.h header file, or the corresponding reference class, IRHeap, which is found in the irheap.h header file. ═══ 3.5.3.1. Template Arguments and Required Functions ═══ IAHeap IRHeap The concrete base class is one of the heap classes. The required functions are the same as the required functions of the concrete base class. ═══ 3.5.4. Declarations for Heap ═══ template < class Element > class IHeap { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IHeap (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IHeap (IHeap < Element > const&); IHeap < Element >& operator = (IHeap < Element > const&); ~IHeap (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IHeap < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; }; ═══ 3.5.5. Coding Example for Heap ═══ See Coding Example for Key Sorted Set for an example of using a heap. ═══ 3.6. Key Bag ═══ A key bag is an unordered collection of zero or more elements that have a key. Multiple elements are supported. Behavior of add for Unique and Multiple Collections illustrates the differences in behavior between map, relation, key set, and key bag when adding identical elements and elements with the same key. Combination of Flat Collection Properties gives an overview of the properties of a key bag and its relationship to other flat collections. Note: All member functions of key bag are described under "List of Functions". ═══ 3.6.1. Class Implementation Variants ═══ IKeyBag, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IKeyBag ikeybag.h Hash Table IGKeyBag ikeybag.h Hash Table IHashKeyBag ihshkb.h Hash Table IGHashKeyBag ihshkb.h Hash Table (basic) ═══ 3.6.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for key bags: o Key Bag o Hash Key Bag ═══ 3.6.2.1. Key Bag ═══ IKeyBag IGKeyBag The default implementation of the class IKeyBag requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type o Equality test o Hash function ═══ 3.6.2.2. Hash Key Bag ═══ IHashKeyBag IGHashKeyBag The implementation of the class IHashKeyBag requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type o Equality test o Hash function ═══ 3.6.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAKeyBag, which is found in the iakeybag.h header file, or the corresponding reference class, IRKeyBag, which is found in the irkeybag.h header file. See Polymorphic Use of Collections for further information. ═══ 3.6.3.1. Template Arguments and Required Functions ═══ IAKeyBag IRKeyBag The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.6.4. Declarations for Key Bag ═══ template class IKeyBag { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IKeyBag (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IKeyBag (IKeyBag < Element, Key > const&); IKeyBag < Element, Key >& operator = (IKeyBag < Element, Key > const&); ~IKeyBag (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IKeyBag < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IKeyBag < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); INumber numberOfElementsWithKey (Key const&) const; Boolean locateNextElementWithKey (Key const&, ICursor&) const; INumber removeAllElementsWithKey (Key const&); INumber numberOfDifferentKeys () const; Boolean setToNextWithDifferentKey (ICursor&) const; }; ═══ 3.6.5. Coding Example for Key Bag ═══ The following program uses the default key bag class, IKeyBag to create a key bag for storing observations made on animals. The key of the class is the name of the animal. The program produces various reports regarding the observations. Then it removes all the extinct animals, which are stored in a sequence, from the key bag. The program uses the add function to fill the key bag and the forCursor macro to display the observations. It uses the following functions to produce the reports: o numberOfElements o numberOfDifferentKeys o numberOfElementsWithKey o locateElementWithKey o setToNextElementWithKey o removeAllElementsWithKey // animals.C - An example of using a Key Bag #include // Class Animal: #include "animal.h" // Let's use the default Key Bag: #include typedef IKeyBag Animals; // For keys let's use the default Sequence: #include typedef ISequence Names; main() { Animals animals; Animals::Cursor animalsCur1(animals), animalsCur2(animals); animals.add(Animal("bear", "heavy")); animals.add(Animal("bear", "strong")); animals.add(Animal("dinosaur", "heavy")); animals.add(Animal("dinosaur", "huge")); animals.add(Animal("dinosaur", "extinct")); animals.add(Animal("eagle", "black")); animals.add(Animal("eagle", "strong")); animals.add(Animal("lion", "dangerous")); animals.add(Animal("lion", "strong")); animals.add(Animal("mammoth", "long haired")); animals.add(Animal("mammoth", "extinct")); animals.add(Animal("sabre tooth tiger", "extinct")); animals.add(Animal("zebra", "striped")); // Display all elements in animals: cout << "\nAll our observations on animals:\n"; forCursor(animalsCur1) cout << " " << animalsCur1.element(); cout << "\n\nNumber of observations on animals: " << animals.numberOfElements() << "\n"; cout << "\nNumber of different animals: " << animals.numberOfDifferentKeys() << "\n"; Names namesOfExtinct(animals.numberOfDifferentKeys()); Names::Cursor extinctCur1(namesOfExtinct); animalsCur1.setToFirst(); do { ToyString name = animalsCur1.element().name(); cout << "\nWe have " << animals.numberOfElementsWithKey(name) << " observations on " << name.text() << ":\n"; // We need to use a separate cursor here // because otherwise animalsCur1 would become // invalid after last locateNextElement...() animals.locateElementWithKey(name, animalsCur2); do { ToyString attribute = animalsCur2.element().attribute(); cout << " " << attribute << "\n"; if (attribute == "extinct") namesOfExtinct.add(name); } while (animals.locateNextElementWithKey(name, animalsCur2)); } while (animals.setToNextWithDifferentKey(animalsCur1)); // Remove all observations on extinct animals: forCursor(extinctCur1) animals.removeAllElementsWithKey(extinctCur1.element()); // Display all elements in animals: cout << "\n\nAfter removing all observations on extinct animals:\n"; forCursor(animalsCur1) cout << " " << animalsCur1.element(); cout << "\nNumber of observations on animals: " << animals.numberOfElements() << "\n"; cout << "\nNumber of different animals: " << animals.numberOfDifferentKeys() << "\n"; return 0; } The program produces the following output: All our observations on animals: The eagle is strong. The eagle is black. The bear is strong. The bear is heavy. The zebra is striped. The mammoth is extinct. The mammoth is long haired. The lion is strong. The lion is dangerous. The dinosaur is extinct. The dinosaur is huge. The dinosaur is heavy. The sabre tooth tiger is extinct. Number of observations on animals: 13 Number of different animals: 7 We have 2 observations on eagle: strong black We have 2 observations on bear: strong heavy We have 1 observations on zebra: striped We have 2 observations on mammoth: extinct long haired We have 2 observations on lion: strong dangerous We have 3 observations on dinosaur: extinct huge heavy We have 1 observations on sabre tooth tiger: extinct After removing all observations on extinct animals: The eagle is strong. The eagle is black. The bear is strong. The bear is heavy. The zebra is striped. The lion is strong. The lion is dangerous. Number of observations on animals: 7 Number of different animals: 4 ═══ 3.7. Key Set ═══ A key set is an unordered collection of zero or more elements that have a key. Element equality is not supported. Only unique elements are supported, in terms of their key. Behavior of add for Unique and Multiple Collections illustrates the differences in behavior between map, relation, key set, and key bag when adding identical elements and elements with the same key. Combination of Flat Collection Properties gives an overview of the properties of a key set and its relationship to other flat collections. Note: All member functions of key set are described under "List of Functions". ═══ 3.7.1. Class Implementation Variants ═══ IKeySet, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IKeySet ikeyset.h AVL KeySortedSet IGKeySet ikeyset.h AVL KeySortedSet IKeySetOnBSTKeySortedSet iksbst.h B* KeySortedSet IGKeySetOnBSTKeySortedSet iksbst.h B* KeySortedSet IHashKeySet ihshks.h Hash table for KeySet (basic) IGHashKeySet ihshks.h Hash table for KeySet (basic) IKeySetOnSortedLinkedSequence ikssls.h LinkedSequence IGKeySetOnSortedLinkedSequence ikssls.h LinkedSequence IKeySetOnSortedTabularSequence ikssts.h TabularSequence IGKeySetOnSortedTabularSequence ikssts.h TabularSequence IKeySetOnSortedDilutedSequence ikssds.h Diluted Sequence IGKeySetOnSortedDilutedSequence ikssds.h DilutedSequence ═══ 3.7.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for key sets: o Key Set o Key Set on B* Key Sorted Set o Hash Key Set o Key Set on Sorted Linked Sequence o Key Set on Sorted Tabular Sequence o Key Set on Sorted Diluted Sequence ═══ 3.7.2.1. Key Set ═══ IKeySet IGKeySet The default implementation of the class IKeySet requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.7.2.2. Key Set on B* Key Sorted Set ═══ IKeySetOnBSTKeySortedSet IGKeySetOnBSTKeySortedSet The default implementation of the class IKeySetOnBSTKeySortedSet requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.7.2.3. Hash Key Set ═══ IHashKeySet IGHashKeySet The implementation class IGHashKeySet requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type o Equality test o Hash function ═══ 3.7.2.4. Key Set on Sorted Linked Sequence ═══ IKeySetOnSortedLinkedSequence IGKeySetOnSortedLinkedSequence The default implementation of the class IKeySetOnSortedLinkedSequence requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.7.2.5. Key Set on Sorted Tabular Sequence ═══ IKeySetOnSortedTabularSequence IGKeySetOnSortedTabularSequence The default implementation of the class IKeySetOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.7.2.6. Key Set on Sorted Diluted Sequence ═══ IKeySetOnSortedDilutedSequence IGKeySetOnSortedDilutedSequence The default implementation of the class IKeySetOnSortedDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.7.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAKeySet, which is found in the iakeyset.h header file, or the corresponding reference class, IRKeySet, which is found in the irkeyset.h header file. See Polymorphic Use of Collections for further information. ═══ 3.7.3.1. Template Arguments and Required Functions ═══ IAKeySet IRKeySet The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.7.4. Declarations for Key Set ═══ template < class Element, class Key > class IKeySet { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IKeySet (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IKeySet (IKeySet < Element, Key > const&); IKeySet < Element, Key >& operator = (IKeySet < Element, Key > const&); ~IKeySet (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IKeySet < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IKeySet < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); }; ═══ 3.7.5. Coding Example for Key Set ═══ The following program implements a key set using the default class, IKeySet. The program adds four elements to the key set and then removes one element by looking for a key. If an exception occurs, it displays the exception name and description. The program uses cursor iteration (the forCursor macro) to display the contents of the collection. To add and remove elements, it uses the add function and the removeElementWithKey function. // intkyset.C - An example of using a Key Set #include #include #include #include // Class DemoElement: #include "demoelem.h" typedef IKeySet < DemoElement,int > TestKeySet; ostream & operator << ( ostream & sout, TestKeySet const & t){ sout << t.numberOfElements() << " elements are in the set:\n"; TestKeySet::Cursor cursor (t); // forCursor(c) // expands to // for ((c).setToFirst (); (c).isValid (); (c).setToNext ()) forCursor (cursor) sout << " " << cursor.element() << "\n"; return sout << "\n"; } main(){ TestKeySet t; try { t.add(DemoElement(1,1)); t.add(DemoElement(2,4711)); t.add(DemoElement(3,1)); t.add(DemoElement(4,443)); cout << t; t.removeElementWithKey (3); cout << t; } catch (IException & exception) { cout << exception.name() << " : " << exception.text(); } return 0; } The program produces the following output: 4 elements are in the set: 1,1 2,4711 3,1 4,443 3 elements are in the set: 1,1 2,4711 4,443 ═══ 3.8. Key Sorted Bag ═══ A key sorted bag is an ordered collection of zero or more elements that have a key. Elements are sorted according to the value of their key field. Element equality is not supported. Multiple elements are supported. Combination of Flat Collection Properties gives an overview of the properties of a key sorted bag and its relationship to other flat collections. Note: All member functions of key sorted bag are described under "List of Functions". ═══ 3.8.1. Class Implementation Variants ═══ IKeySortedBag, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IKeySortedBag iksbag.h LinkedSequence IGKeySortedBag iksbag.h LinkedSequence IKeySortedBagOnSortedTabularSequence iksbsts.h TabularSequence IGKeySortedBagOnSortedTabularSequence iksbsts.h TabularSequence IKeySortedBagOnSortedDilutedSequence iksbsds.h DilutedSequence IGKeySortedBagOnSortedDilutedSequence iksbsds.h DilutedSequence ═══ 3.8.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for key sorted bags: o Key Sorted Bag o Key Sorted Bag on Tabular Sequence o Key Sorted Bag on Diluted Sequence ═══ 3.8.2.1. Key Sorted Bag ═══ IKeySortedBag IGKeySortedBag The implementation of the class IKeySortedBag requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.8.2.2. Key Sorted Bag on Tabular Sequence ═══ IKeySortedBagOnTabularSequence IGKeySortedBagOnTabularSequence The implementation of the class IKeySortedBagOnTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.8.2.3. Key Sorted Bag on Diluted Sequence ═══ IKeySortedBagOnDilutedSequence IGKeySortedBagOnDilutedSequence The implementation of the class IKeySortedBagOnDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.8.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAKeySortedBag, which is found in the iaksbag.h header file, or the corresponding reference class, IRKeySortedBag, which is found in the irksbag.h header file. See Polymorphic Use of Collections for further information. ═══ 3.8.3.1. Template Arguments and Required Functions ═══ IAKSBag IRKSBag The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.8.4. Declarations for Key Sorted Bag ═══ template < class Element, class Key > class IKeySortedBag { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IKeySortedBag (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IKeySortedBag (IKeySortedBag < Element, Key > const&); IKeySortedBag < Element, Key >& operator = (IKeySortedBag < Element, Key > const&); ~IKeySortedBag (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IKeySortedBag < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IKeySortedBag < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); INumber numberOfElementsWithKey (Key const&) const; Boolean locateNextElementWithKey(Key const&, ICursor&) const; INumber removeAllElementsWithKey (Key const&); INumber numberOfDifferentKeys () const; Boolean setToNextWithDifferentKey (ICursor&) const; void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IKeySortedBag < Element, Key > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.8.5. Coding Example for Key Sorted Bag ═══ The following program illustrates the use of a key bag. The program determines the number of words that have the same length in a phrase. It stores the words of the phrase in a key sorted bag that it implements using the default class, IKeySortedBag. The program makes the key the length of the word. Because of the properties of a key sorted bag, it sorts the words by their length (the key), and it stores all duplicate words. The program determines the number of different word lengths using the numberOfDifferentKeys function. It uses the numberOfElementsWithKey function and the setToNextWithDifferentKey function to iterate through the collection and count the number of words with the same length. // wordbag.C - An exampe for using a Key Sorted Bag #include // Class Word: #include "toyword.h" // Let's use the defaults: #include typedef IKeySortedBag WordBag; int main() { Word phrase[] = {"people", "who", "live", "in", "glass", "houses", "should", "not", "throw", "stones"}; const int phraseWords = sizeof(phrase) / sizeof(Word); WordBag wordbag(phraseWords); for (int cnt=0; cnt < phraseWords; cnt++) { wordbag.add(phrase[cnt]); } cout << "Contents of our WordBag sorted by number of letters:\n"; WordBag::Cursor wordBagCursor(wordbag); forCursor(wordBagCursor) cout << "WB: " << wordBagCursor.element().text() << "\n"; cout << "\nOur phrase has " << phraseWords << " words.\n"; cout << "In our WordBag are " << wordbag.numberOfElements() << " words.\n\n"; cout << "There are " << wordbag.numberOfDifferentKeys() << " different word lengths.\n\n"; wordBagCursor.setToFirst(); do { int letters = wordbag.key(wordBagCursor.element()); cout << "There are " << wordbag.numberOfElementsWithKey(letters) << " words with " << letters << " letters.\n"; } while (wordbag.setToNextWithDifferentKey(wordBagCursor)); return 0; } ═══ 3.9. Key Sorted Set ═══ A key sorted set is an ordered collection of zero or more elements that have a key. Elements are sorted according to the value of their key field. Element equality is not supported. Only elements with unique keys are supported. A request to add an element whose key already exists is ignored. Combination of Flat Collection Properties gives an overview of the properties of a key sorted set and its relationship to other flat collections. Note: All member functions of key sorted set are described under "List of Functions". ═══ 3.9.1. Class Implementation Variants ═══ IKeySortedSet, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Description IKeySortedSet iksset.h AVL tree for KeySortedSet IGKeySortedSet iksset.h AVL tree for KeySortedSet IAvlKeySortedSet iavlkss.h AVL tree for KeySortedSet IGAvlKeySortedSet iavlkss.h AVL tree for KeySortedSet IBSTKeySortedSet ibstkss.h B* tree for KeySortedSet IGBSTKeySortedSet ibstkss.h B* tree for KeySortedSet IKeySortedSetOn- iksssls.h Based on LinkedSequence SortedLinkedSequence IGKeySortedSetOn- iksssls.h Based on LinkedSequence SortedLinkedSequence IKeySortedSetOn- iksssts.h Based on TabularSequence SortedTabularSequence IGKeySortedSetOn- iksssts.h Based on TabularSequence SortedTabularSequence IKeySortedSetOn- iksssds.h Based on DilutedSequence SortedDilutedSequence IGKeySortedSetOn- iksssds.h Based on DilutedSequence SortedDilutedSequence ═══ 3.9.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for key sorted sets: o Key Sorted Set o AVL Key Sorted Set o B* Key Sorted Set o Key Sorted Set on Sorted Linked Sequence o Key Sorted Set on Sorted Tabular Sequence o Key Sorted Set on Sorted Diluted Sequence ═══ 3.9.2.1. Key Sorted Set ═══ IKeySortedSet IGKeySortedSet The implementation of the class IKeySortedSet requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.9.2.2. AVL Key Sorted Set ═══ IAvlKeySortedSet IGAvlKeySortedSet The implementation of the class IGAvlKeySortedSet requires the following element and key functions: Element Type o Copy constructor o Assignment o Destructor o Key access Key Type Ordering relation ═══ 3.9.2.3. B* Key Sorted Set ═══ IBSTKeySortedSet IGBSTKeySortedSet The implementation of the class IBSTKeySortedSet requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.9.2.4. Key Sorted Set on Sorted Linked Sequence ═══ IKeySortedSetOnSortedLinkedSequence IGKeySortedSetOnSortedLinkedSequence The implementation of the class IKeySortedSetOnSortedLinkedSequence requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.9.2.5. Key Sorted Set on Sorted Tabular Sequence ═══ IKeySortedSetOnSortedTabularSequence IGKeySortedSetOnSortedTabularSequence The implementation of the class IKeySortedSetOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.9.2.6. Key Sorted Set on Sorted Diluted Sequence ═══ IKeySortedSetOnSortedDilutedSequence IGKeySortedSetOnSortedDilutedSequence The implementation of the class IKeySortedSetOnSortedDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.9.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAKeySortedSet, which is found in the iaksset.h header file, or the corresponding reference class, IRKeySortedSet, which is found in the irksset.h header file. See Polymorphic Use of Collections for further information. ═══ 3.9.3.1. Template Arguments and Required Functions ═══ IAKeySortedSet IRKeySortedSet The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.9.4. Declarations for Key Sorted Set ═══ template < class Element, class Key > class IKeySortedSet { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IKeySortedSet (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IKeySortedSet (IKeySortedSet < Element, Key > const&); IKeySortedSet < Element, Key >& operator = (IKeySortedSet < Element, Key > const&); ~IKeySortedSet (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IKeySortedSet < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Key const& key (Element const&) const; Boolean containsElementWithKey(Key const&) const; Boolean containsAllKeysFrom (IKeySortedSet < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IKeySortedSet < Element, Key > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.9.5. Coding Example for Key Sorted Set ═══ The following program uses the default classes for a key sorted set and a heap, IKeySortedSet and IHeap, to track parcels for a delivery service. It uses a key sorted set to record the parcels that are currently in circulation. The fast access of a sorted collection is not necessary to keep track of the delivered parcels, so the program uses a heap to keep track of them. The parcel element contains three data members: one of type PlaceTime that stores the origin time and place of the parcel, another of type PlaceTime that stores the current time and place of the parcel, and one of type ToyString that stores the destination. The function update adds parcels that have arrived at their destinations to the heap of delivered parcels, and removes them from the key sorted set for circulating parcels. The program uses the add function to update and the removeAll function to remove elements from the key sorted set. // parcel.C - An example for using a Key Sorted Set and a Heap #include #include "parcel.h" // Let's use the default KeySorted Set: #include // Let's use the default Heap: #include typedef IKeySortedSet ParcelSet; typedef IHeap ParcelHeap; ostream& operator<<(ostream&, ParcelSet const&); ostream& operator<<(ostream&, ParcelHeap const&); void update(ParcelSet&, ParcelHeap&); main() { ParcelSet circulating; ParcelHeap delivered; int today = 8; circulating.add(Parcel("London", "Athens", today, "26LoAt")); circulating.add(Parcel("Amsterdam", "Toronto", today += 2, "27AmTo")); circulating.add(Parcel("Washington", "Stockholm", today += 5, "25WaSt")); circulating.add(Parcel("Dublin", "Kairo", today += 1, "25DuKa")); update(circulating, delivered); cout << "\nThe situation at start:\n"; cout << "Parcels in circulation:\n" << circulating; today ++; circulating.elementWithKey("27AmTo").arrivedAt( "Atlanta", today); circulating.elementWithKey("25WaSt").arrivedAt( "Amsterdam", today); circulating.elementWithKey("25DuKa").arrivedAt( "Paris", today); update(circulating, delivered); cout << "\n\nThe situation at day " << today << ":\n"; cout << "Parcels in circulation:\n" << circulating; today ++; // One day later ... circulating.elementWithKey("27AmTo").arrivedAt("Chicago", today); // As in real life, one parcel gets lost: circulating.removeElementWithKey("26LoAt"); update(circulating, delivered); cout << "\n\nThe situation at day " << today << ":\n"; cout << "Parcels in circulation:\n" << circulating; today ++; circulating.elementWithKey("25WaSt").arrivedAt("Oslo", today); circulating.elementWithKey("25DuKa").arrivedAt("Kairo", today); // New parcels are shipped. circulating.add(Parcel("Dublin", "Rome", today, "27DuRo")); // Let's try to add one with a key already there. // The KeySsorted Set should ignore it: circulating.add(Parcel("Nowhere", "Nirvana", today, "25WaSt")); update(circulating, delivered); cout << "\n\nThe situation at day " << today << ":\n"; cout << "Parcels in circulation:\n" << circulating; cout << "Parcels delivered:\n" << delivered; // Now we make all parcels arrive today: today ++; ParcelSet::Cursor circulatingcursor(circulating); forCursor(circulatingcursor) { circulating.elementAt(circulatingcursor).wasDelivered(today); } update(circulating, delivered); cout << "\n\nThe situation at day " << today << ":\n"; cout << "Parcels in circulation:\n" << circulating; cout << "Parcels delivered:\n" << delivered; if (circulating.isEmpty()) cout << "\nAll parcels were delivered.\n"; else cout << "\nSomething very strange happened here.\n"; return 0; } ostream& operator<<(ostream& os, ParcelSet const& parcels) { ParcelSet::Cursor pcursor(parcels); forCursor(pcursor) { os << pcursor.element() << "\n"; } return os; } ostream& operator<<(ostream& os, ParcelHeap const& parcels) { ParcelHeap::Cursor pcursor(parcels); forCursor(pcursor) { os << pcursor.element() << "\n"; } return os; } Boolean wasDelivered(Parcel const& p, void* dp) { if ( p.lastArrival().city() == p.destination() ) { ((ParcelHeap*)dp)->add(p); return True; } else return False; } void update(ParcelSet& p, ParcelHeap& d) { p.removeAll(wasDelivered, &d); } The program produces the following output: The situation at start: Parcels in circulation: 25DuKa: From Dublin(day 16) to Kairo is at Dublin since day 16. 25WaSt: From Washington(day 15) to Stockholm is at Washington since day 15. 26LoAt: From London(day 8) to Athens is at London since day 8. 27AmTo: From Amsterdam(day 10) to Toronto is at Amsterdam since day 10. The situation at day 17: Parcels in circulation: 25DuKa: From Dublin(day 16) to Kairo is at Paris since day 17. 25WaSt: From Washington(day 15) to Stockholm is at Amsterdam since day 17. 26LoAt: From London(day 8) to Athens is at London since day 8. 27AmTo: From Amsterdam(day 10) to Toronto is at Atlanta since day 17. The situation at day 18: Parcels in circulation: 25DuKa: From Dublin(day 16) to Kairo is at Paris since day 17. 25WaSt: From Washington(day 15) to Stockholm is at Amsterdam since day 17. 27AmTo: From Amsterdam(day 10) to Toronto is at Chicago since day 18. The situation at day 19: Parcels in circulation: 25WaSt: From Washington(day 15) to Stockholm is at Oslo since day 19. 27AmTo: From Amsterdam(day 10) to Toronto is at Chicago since day 18. 27DuRo: From Dublin(day 19) to Rome is at Dublin since day 19. Parcels delivered: 25DuKa: From Dublin(day 16) to Kairo was delivered on day 19. The situation at day 20: Parcels in circulation: Parcels delivered: 25DuKa: From Dublin(day 16) to Kairo was delivered on day 19. 25WaSt: From Washington(day 15) to Stockholm was delivered on day 20. 27AmTo: From Amsterdam(day 10) to Toronto was delivered on day 20. 27DuRo: From Dublin(day 19) to Rome was delivered on day 20. All parcels were delivered. ═══ 3.10. Map ═══ A map is an unordered collection of zero or more elements that have a key. Element equality is supported and the values of the elements are relevant. Only elements with unique keys are supported. A request to add an element whose key already exists in another element of the collection is ignored. Behavior of add for Unique and Multiple Collections illustrates the differences in behavior between map, relation, key set, and key bag when adding identical elements and elements with the same key. Combination of Flat Collection Properties gives an overview of the properties of a map and its relationship to other flat collections. Note: All member functions of map are described under "List of Functions". ═══ 3.10.1. Class Implementation Variants ═══ IMap, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IMap imap.h AVL KeySortedSet IGMap imap.h AVL KeySortedSet IMapOnBSTKeySortedSet imapbst.h B* KeySortedSet IGMapOnBSTKeySortedSet imapbst.h B* KeySortedSet IMapOnSortedLinkedSequence imapsls.h Linked Sequence IGMapOnSortedLinkedSequence imapsls.h LinkedSequence IMapOnSortedTabularSequence imapsts.h TabularSequence IGMapOnSortedTabularSequence imapsts.h TabularSequence IMapOnSortedDilutedSequence imapsds.h DilutedSequence IGMapOnSortedDilutedSequence imapsds.h DilutedSequence IMapOnHashKeySet imaphks.h Hash KeySet IGMapOnHashKeySet imaphks.h Hash KeySet ═══ 3.10.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for maps: o Map o Map on B* Key Sorted Set o Map on Sorted Linked Sequence o Map on Sorted Tabular Sequence o Map on Sorted Diluted Sequence o Map on Hash Key Set ═══ 3.10.2.1. Map ═══ IMap IGMap The implementation of the class IMap requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type Ordering relation ═══ 3.10.2.2. Map on B* Key Sorted Set ═══ IMapOnBSTKeySortedSet IGMapOnBSTKeySortedSet The default implementation of the class IMapOnBSTKeySortedSet requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type Ordering relation ═══ 3.10.2.3. Map on Sorted Linked Sequence ═══ IMapOnSortedLinkedSequence IGMapOnSortedLinkedSequence The implementation of the class IMapOnSortedLinkedSequence requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type Ordering relation ═══ 3.10.2.4. Map on Sorted Tabular Sequence ═══ IMapOnSortedTabularSequence IGMapOnSortedTabularSequence The implementation of the class IMapOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type Ordering relation ═══ 3.10.2.5. Map on Sorted Diluted Sequence ═══ IMapOnSortedDilutedSequence IGMapOnSortedDilutedSequence The implementation of the class IMapOnSortedDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type Ordering relation ═══ 3.10.2.6. Map on Hash Key Set ═══ IMapOnHashKeySet IGMapOnHashKeySet The implementation of the class IMapOnHashKeySet requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Key access Key Type o Equality test o Hash function ═══ 3.10.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAMap, which is found in the iamap.h header file, or the corresponding reference class, IRMap, which is found in the irmap.h header file. See Polymorphic Use of Collections for further information. ═══ 3.10.3.1. Template Arguments and Required Functions ═══ IAMap IRMap The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.10.4. Declarations for Map ═══ template < class Element, class Key > class IMap { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IMap (INumber numberOfElements = 100, IBoundIndicator = IUnbounded); IMap (IMap < Element, Key > const&); IMap < Element, Key >& operator = (IMap < Element, Key > const&); ~IMap (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IMap < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean contains (Element const&) const; Boolean containsAllFrom (IMap < Element, Key > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (IMap < Element, Key > const&) const; Boolean operator != (IMap < Element, Key > const&) const; void unionWith (IMap < Element, Key > const&); void intersectionWith (IMap < Element, Key > const&); void differenceWith (IMap < Element, Key > const&); void addUnion (IMap < Element, Key > const&, IMap < Element, Key > const&); void addIntersection (IMap < Element, Key > const&, IMap < Element, Key > const&); void addDifference (IMap < Element, Key > const&, IMap < Element, Key > const&); Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IMap < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); }; ═══ 3.10.5. Coding Example for Map ═══ The following program allows EBCDIC to ASCII and ASCII to EBCDIC translation of a string. It uses two maps, one with the EBCDIC code as key (E2AMap) and one with the ASCII code as key (A2EMap). It converts from EBCDIC to ASCII by finding the element whose key matches the EBCDIC code in E2AMap (which has the EBCDIC code as key) and taking the ASCII code information from that element. It converts from ASCII to EBCDIC by finding the key that matches the ASCII code in A2EMap (which has the ASCII code as key) and taking the EBCDIC code information for that element. The program uses the add function to build the maps and the elementWithKey function to convert the characters. // transtab.C - An example of using a Map #include "transelm.h" // Get the standard operation classes: #include #include "trmapops.h" // Now we define the two Map templates and two maps // We want both of them to be based on the Hashtable KeySet #include typedef IGMapOnHashKeySet < TranslationElement, char, KeyOpsTransE2A > TransE2AMap; typedef IGMapOnHashKeySet < TranslationElement, char, KeyOpsTransA2E > TransA2EMap; void display(char*, char*); int main(int argc, char* argv[]) { TransA2EMap A2EMap; TransE2AMap E2AMap; // char translationtable[256] = .... #include // Load the translation table into both maps. for (int i=0; i < 256; i++) { /* asc_code ebc_code */ TranslationElement te(translationtable[i], i ); E2AMap.add(te); A2EMap.add(te); } // What do we want to convert now? char* to_convert; if (argc > 1) to_convert = argv[1]; else to_convert = "$7 (=Dollar seven)"; size_t text_length = strlen(to_convert) +1; char* converted_to_asc = new char[text_length]; char* converted_to_ebc = new char[text_length]; // Convert the strings in place, character by character for (i=0; to_convert[i] != 0x00; i++) { converted_to_asc[i] = E2AMap.elementWithKey(to_convert[i]).asc_code; converted_to_ebc[i] = A2EMap.elementWithKey(to_convert[i]).ebc_code; } display("To convert", to_convert); display("After EBCDIC-ASCII conversion", converted_to_asc); display("After ASCII-EBCDIC conversion", converted_to_ebc); delete[] converted_to_asc; delete[] converted_to_ebc; return 0; } #include #include void display(char* title, char* text) { cout << "\n" << title <<": \n"; cout << " Hex: " << hex; for (int i=0; text[i] != 0x00; i++) { cout << (int)text[i] << " "; } cout << dec << endl; } The program produces the following output: To convert: Hex: 24 37 20 20 28 3d 44 6f 6c 6c 61 72 20 73 65 76 65 6e 29 After EBCDIC-ASCII conversion: Hex: 86 4 81 81 89 15 eb 3f 25 25 2f 94 81 b0 dd fc dd 3e 91 After ASCII-EBCDIC conversion: Hex: 5b f7 40 40 4d 7e c4 96 93 93 81 99 40 a2 85 a5 85 95 5d ═══ 3.11. Priority Queue ═══ A priority queue is a key sorted bag with restricted access. It is an ordered collection of zero or more elements. Keys and multiple elements are supported. Element equality is not supported. When an element is added, it is placed in the queue according to its key value or priority. You can only remove the element with the highest key value. A priority queue has a largest-in, first-out behavior. Note: All member functions of priority queue are described under "List of Functions". ═══ 3.11.1. Class Implementation Variants ═══ IPriorityQueue, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IPriorityQueue iprioqu.h KeySortedBag on LinkedSequence IGPriorityQueue iprioqu.h KeySortedBag on LinkedSequence IPriorityQueueOn- ipqusts.h KeySortedBag on TabularSequence SortedTabularSequence IGPriorityQueueOn- ipqusts.h KeySortedBag on TabularSequence SortedTabularSequence IPriorityQueueOn- ipqusds.h KeySortedBag on DilutedSequence SortedDilutedSequence IGPriorityQueueOn- ipqusds.h KeySortedBag on DilutedSequence SortedDilutedSequence ═══ 3.11.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for priority queues: o Priority Queue o Priority Queue on Sorted Tabular Sequence o Priority Queue on Sorted Diluted Sequence ═══ 3.11.2.1. Priority Queue ═══ IPriorityQueue IGPriorityQueue The implementation of the class IPriorityQueue requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.11.2.2. Priority Queue on Sorted Tabular Sequence ═══ IPriorityQueueOnSortedTabularSequence IGPriorityQueueOnSortedTabularSequence The implementation of the class IPriorityQueueOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.11.2.3. Priority Queue on Sorted Diluted Sequence ═══ IPriorityQueueOnSortedDilutedSequence IGPriorityQueueOnSortedDilutedSequence The implementation of the class IPriorityQueueOnSortedDilutedSequence requires the following element/key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access Key Type Ordering relation ═══ 3.11.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAPriorityQueue, which is found in the iaprioqu.h header file, or the corresponding reference class, IRPriorityQueue, which is found in the irprioqu.h header file. See Polymorphic Use of Collections for further information. ═══ 3.11.3.1. Template Arguments and Required Functions ═══ IAPriorityQueue IRPriorityQueue The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.11.4. Declarations for Priority Queue ═══ template < class Element, class Key > class IPriorityQueue { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IPriorityQueue (INumber numberOfElements = 100); IPriorityQueue (IPriorityQueue < Element, Key > const&); IPriorityQueue < Element, Key >& operator = (IPriorityQueue < Element, Key > const&); ~IPriorityQueue (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IPriorityQueue < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element const& anyElement () const; void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IPriorityQueue < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Element const& elementWithKey (Key const&) const; INumber numberOfElementsWithKey (Key const&) const; Boolean locateNextElementWithKey (Key const&, ICursor&) const; INumber numberOfDifferentKeys () const; Boolean setToNextWithDifferentKey (ICursor&) const; void removeFirst (); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IPriorityQueue < Element, Key > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void enqueue (Element const&); void enqueue (Element const&, ICursor&); void dequeue (); void dequeue (Element&); }; ═══ 3.12. Queue ═══ A queue is a sequence with restricted access. It is an ordered collection of elements with no key and no element equality. The elements are arranged so that each collection has a first and a last element, each element except the last has a next element, and each element but the first has a previous element. The type and value of the elements are irrelevant, and have no effect on the behavior of the collection. You can only add an element as the last element, and you can only remove the first element. Consequently, the elements of a queue are in chronological order. A queue is characterized by a first-in, first-out (FIFO) behavior. Note: All member functions of queue are described under "List of Functions". ═══ 3.12.1. Class Implementation Variants ═══ IQueue, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On IQueue iqueue.h LinkedSequence IGQueue iqueue.h LinkedSequence IQueueOnTabularSequence iquets.h TabularSequence IGQueueOnTabularSequence iquets.h TabularSequence IQueueOnDilutedSequence iqueds.h DilutedSequence IGQueueOnDilutedSequence iqueds.h DilutedSequence ═══ 3.12.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for queues: o Queue o Queue on Tabular Sequence o Queue on Diluted Sequence ═══ 3.12.2.1. Queue ═══ IQueue IGQueue The default implementation of the class IQueue requires the following element functions: Element Type o Copy constructor o Destructor o Assignment ═══ 3.12.2.2. Queue on Tabular Sequence ═══ IQueueOnTabularSequence IGQueueOnTabularSequence The implementation of the class IDequeOnTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment ═══ 3.12.2.3. Queue on Diluted Sequence ═══ IQueueOnDilutedSequence IGQueueOnDilutedSequence The implementation of the class IQueueOnDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment ═══ 3.12.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAQueue, which is found in the iaqueue.h header file, or the corresponding reference class, IRQueue, which is found in the irqueue.h header file. See Polymorphic Use of Collections for further information. ═══ 3.12.3.1. Template Arguments and Required Functions ═══ IAQueue IRQueue The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.12.4. Declarations for Queue ═══ template < class Element > class IQueue { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IQueue (INumber numberOfElements = 100); IQueue (IQueue < Element > const&); IQueue < Element >& operator = (IQueue < Element > const&); ~IQueue (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IQueue < Element > const&); Element const& elementAt (ICursor const&) const; Element const& anyElement () const; void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; void removeFirst (); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IQueue < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void addAsLast (Element const&); void addAsLast (Element const&, ICursor&); void enqueue (Element const&); void enqueue (Element const&, ICursor&); void dequeue (); void dequeue (Element&); }; ═══ 3.13. Relation ═══ A relation is an unordered collection of zero or more elements that have a key. Element equality is supported and the values of the elements are relevant. The keys of the elements are not unique. You can add an element whether or not there is already an element in the collection with the same key. Behavior of add for Unique and Multiple Collections illustrates the differences in behavior between map, relation, key set, and key bag when adding identical elements and elements with the same key. Combination of Flat Collection Properties gives an overview of the properties of a relation and its relationship to other flat collections. Note: All member functions of relation are described under "List of Functions". ═══ 3.13.1. Class Implementation Variants ═══ IRelation is the default implementation variant. IGRelation is the default implementation with generic operations class. Both variants are declared in the header file irel.h. If you want to use polymorphism, you can replace these class implementation variants by the reference class. ═══ 3.13.2. Template Arguments and Required Functions for Relation ═══ IRelation IGRelation The default implementation of the class IRelation requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type o Equality test o Hash function ═══ 3.13.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IARelation, which is found in the iarel.h header file, or the corresponding reference class, IRRelation, which is found in the irrel.h header file. See Polymorphic Use of Collections for further information. ═══ 3.13.3.1. Template Arguments and Required Functions ═══ IARel IRRel The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.13.4. Declarations for Relation ═══ template < class Element, class Key > class IRelation { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IRelation (INumber numberOfElements = 100); IRelation (IRelation < Element, Key > const&); IRelation < Element, Key >& operator = (IRelation < Element, Key > const&); ~IRelation (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IRelation < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements() const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (IRelation < Element, Key > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (IRelation < Element, Key > const&) const; Boolean operator != (IRelation < Element, Key > const&) const; void unionWith (IRelation < Element, Key > const&); void intersectionWith(IRelation < Element, Key > const&); void differenceWith (IRelation < Element, Key > const&); void addUnion (IRelation < Element, Key > const&, IRelation < Element, Key > const&); void addIntersection (IRelation < Element, Key > const&, IRelation < Element, Key > const&); void addDifference (IRelation < Element, Key > const&, IRelation < Element, Key > const&); Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (IRelation < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); INumber numberOfElementsWithKey (Key const&) const; Boolean locateNextElementWithKey (Key const&, ICursor&) const; INumber removeAllElementsWithKey (Key const&); INumber numberOfDifferentKeys () const; Boolean setToNextWithDifferentKey (ICursor&) const; }; ═══ 3.14. Sequence ═══ A sequence is an ordered collection of elements. The elements are arranged so that each collection has a first and a last element, each element except the last has a next element, and each element but the first has a previous element. The type and value of the elements are irrelevant, and have no effect on the behavior of the collection. Elements can be added and deleted from any position in the collection. Elements can be retrieved or replaced. A sequence does not support element equality or a key. Combination of Flat Collection Properties illustrates the properties of a sequence and its relationship to other flat collections. Note: All member functions of sequence are described under "List of Functions". ═══ 3.14.1. Class Implementation Variants ═══ ISequence, the first class in the table below, is the default implementation variant. If you need to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Description ISequence iseq.h Linked Sequence IGSequence iseq.h Linked Sequence ILinkedSequence ilnseq.h Linked Sequence IGLinkedSequence ilnseq.h Linked Sequence ITabularSequence itbseq.h Tabular Sequence IGTabularSequence itbseq.h Tabular Sequence IDilutedSequence itdseq.h Tabular Diluted Sequence IGDilutedSequence itdseq.h Tabular Diluted Sequence ═══ 3.14.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sequences: o Sequence o Linked Sequence o Tabular Sequence o Diluted Sequence ═══ 3.14.2.1. Sequence ═══ ISequence IGSequence The default implementation of ISequence requires the following element functions: Element Type o Copy constructor. o Destructor o Assignment. ═══ 3.14.2.2. Linked Sequence ═══ ILinkedSequence IGLinkedSequence The implementation of the class ILinkedSequence requires the following element functions: Element Type o Copy constructor. o Destructor o Assignment. ═══ 3.14.2.3. Tabular Sequence ═══ ITabularSequence IGTabularSequence The implementation of the class ITabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor. o Destructor o Assignment. ═══ 3.14.2.4. Diluted Sequence ═══ IDilutedSequence IGDilutedSequence The implementation of the class IDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor. o Destructor o Assignment. ═══ 3.14.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASequence, which is found in the iaseq.h header file, or the corresponding reference class, IRSequence, which is found in the irseq.h header file. See Polymorphic Use of Collections for further information. ═══ 3.14.3.1. Template Arguments and Required Functions ═══ IASequence IRSequence The concrete base class is one of the sequence classes. The required functions are the same as the required functions of the concrete base class. ═══ 3.14.4. Declarations for Sequence ═══ template < class Element > class ISequence { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISequence (INumber numberOfElements = 100); ISequence (ISequence < Element > const&); ISequence < Element >& operator = (ISequence < Element > const&); ~ISequence (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISequence < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (ISequence < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void addAsFirst (Element const&); void addAsFirst (Element const&, ICursor&); void addAsLast (Element const&); void addAsLast (Element const&, ICursor&); void addAsNext (Element const&, ICursor&); void addAsPrevious (Element const&, ICursor&); void addAtPosition (IPosition, Element const&); void addAtPosition (IPosition, Element const&, ICursor&); void sort (long (*comparisonFunction) (Element const&, Element const&)); }; ═══ 3.14.5. Coding Example for Sequence ═══ The following program creates a sequence using the default sequence class, ISequence, and adds a number of words to it. The program sorts the words in ascending order and searches the sequence for the word "fox". Finally, it prints the word that is in position 9. The program uses two types of iteration. It uses the iterator class, IIterator, when printing the sequence, and it uses cursor iteration when searching for a word. With the iterator object, the program uses the allElementsDo function. With cursor iteration, it uses the setToFirst, isValid, and setToNext functions. It uses the elementAt and elementAtPosition functions to find words in the sequence. // wordseq.C - An example of using a Sequence #include // Get definition and declaration of class Word: #include "toyword.h" // Define a compare function to be used for sort: inline long wordCompare ( Word const& w1, Word const& w2) { return compare (w1.text(), w2.text()); } // We want to use the default Sequence called ISequence #include typedef ISequence WordSeq; typedef IIterator WordIter; // Test variables to put into the Sequence char *String[9] = { "the", "quick", "brown", "fox", "jumps", "over", "a", "lazy", "dog" }; // Our Iterator class for use with allElementsDo() class PrintClass : public WordIter { public: Boolean applyTo(Word &w) { cout << "\n" << w.text(); // Print the string return(True); } }; int main() { WordSeq WL; WordSeq::Cursor cursor(WL); PrintClass Print; int i; for (i = 0; i < 9; i ++) { // Put all strings into Sequence Word aWord(String[i]); // Fill object with right value WL.addAsLast(aWord); // Add it to the Sequence at end } cout << "\nSequence in initial order:\n"; WL.allElementsDo(Print); WL.sort(wordCompare); // Sort the Sequence ascending cout << "\n\nSequnce in sorted order:\n"; WL.allElementsDo(Print); // Use iteration via cursor now: cout << "\n\nLook for \"fox\" in the Sequence:\n"; for (cursor.setToFirst(); cursor.isValid() && (WL.elementAt(cursor) != "fox"); cursor.setToNext()); if (WL.elementAt(cursor) != "fox") { cout << "\n The element was not found.\n"; } else { cout << "\n The element was found.\n"; } cout << "\n\nThe element at position 9: " << WL.elementAtPosition(9).text(); return(0); } The program produces the following output: Sequence in initial order: the quick brown fox jumps over a lazy dog Sequence in sorted order: a brown dog fox jumps lazy over quick the Look for "fox" in the Sequence: The element was found. The element at position 9: the ═══ 3.15. Set ═══ A set is an unordered collection of zero or more elements with no key. Element equality is supported and the values of the elements are relevant. Only unique elements are supported. A request to add an element that already exists is ignored. Combination of Flat Collection Properties gives an overview of the properties of a set and its relationship to other flat collections. The set also offers typical set functions such as union, intersection, and difference. Note: All member functions of set are described under "List of Functions". ═══ 3.15.1. Class Implementation Variants ═══ ISet, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On ISet iset.h AVL KeySortedSet IGSet iset.h AVL KeySortedSet ISetOnBSTKeySortedSet isetbst.h B* KeySortedSet IGSetOnBSTKeySortedSet isetbst.h B* KeySortedSet ISetOnSortedLinkedSequence isetsls.h LinkedSequence IGSetOnSortedLinkedSequence isetsls.h LinkedSequence ISetOnSortedTabularSequence isetsts.h TabularSequence IGSetOnSortedTabularSequence isetsts.h TabularSequence ISetOnSortedDilutedSequence isetsds.h DilutedSequence IGSetOnSortedDilutedSequence isetsds.h DilutedSequence ISetOnHashKeySet isethks.h Hash KeySet IGSetOnHashKeySet isethks.h Hash KeySet ═══ 3.15.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sets: o Set o Set on B* Key Sorted Set o Set on Sorted linked Sequence o Set on Sorted Tabular Sequence o Set on Sorted Diluted Sequence o Set on Hash Key Set ═══ 3.15.2.1. Set ═══ ISet IGSet The default implementation of the class ISet requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.15.2.2. Set on B* Key Sorted Set ═══ ISetOnBSTKeySortedSet IGSetOnBSTKeySortedSet The default implementation of the class ISetOnBSTKeySortedSet requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.15.2.3. Set on Sorted linked Sequence ═══ ISetOnSortedLinkedSequence IGSetOnSortedLinkedSequence The implementation of the class ISetOnSortedLinkedSequence requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.15.2.4. Set on Sorted Tabular Sequence ═══ ISetOnSortedTabularSequence IGSetOnSortedTabularSequence The implementation of the class ISetOnSortedTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.15.2.5. Set on Sorted Diluted Sequence ═══ ISetOnSortedDilutedSequence IGSetOnSortedDilutedSequence The implementation of the class ISetOnSortedDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.15.2.6. Set on Hash Key Set ═══ ISetOnHashKeySet IGSetOnHashKeySet The implementation of the classISetOnHashKeySet requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Hash function ═══ 3.15.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASet, which is found in the iaset.h header file, or the corresponding reference class, IRSet, which is found in the irset.h header file. See Polymorphic Use of Collections for further information. ═══ 3.15.3.1. Template Arguments and Required Functions ═══ IASet IRSet The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.15.4. Declarations for Set ═══ template < class Element > class ISet { public: class Cursor : ICursor { Element& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISet (INumber numberOfElements = 100); ISet (ISet < Element > const&); ISet < Element >& operator = (ISet < Element > const&); ~ISet (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISet < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (ISet < Element > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (ISet < Element > const&) const; Boolean operator != (ISet < Element > const&) const; void unionWith (ISet < Element > const&); void intersectionWith (ISet < Element > const&); void differenceWith (ISet < Element > const&); void addUnion (ISet < Element > const&, ISet < Element > const&); void addIntersection (ISet < Element > const&, ISet < Element > const&); void addDifference (ISet < Element > const&, ISet < Element > const&); }; ═══ 3.15.5. Coding Example for Set ═══ The follow program creates sets using the default class, ISet. The odd set contains all odd numbers less than ten. The prime set contains all prime numbers less than ten. The program creates a set, oddPrime, that contains all the prime numbers less than ten that are odd, by using the intersection of odd and prime. It creates another set, evenPrime, that contains all the prime numbers less than ten that are even, by using the difference of prime and oddPrime. When printing the sets, the program uses the iterator class, IIterator. It uses the add function to build the odd and prime sets. It uses the addIntersection and addDifference functions to create the oddPrime and evenPrime sets, respectively. // evenodd.C - An example of using a Set #include #include // Take the defaults for the Set and for // the required functions for integer typedef ISet IntSet; // For iteration we want to use an object of an iterator class z class PrintClass : public IIterator { public: virtual Boolean applyTo(int& i) { cout << " " << i << " "; return True;} }; // Local prototype for the function to display an IntSet void List(char *, IntSet &); int main () { IntSet odd, prime; IntSet oddPrime, evenPrime; int One = 1, Two = 2, Three = 3, Five = 5, Seven = 7, Nine = 9; // Fill odd set with odd integers < 10 odd.add( One ); odd.add( Three ); odd.add( Five ); odd.add( Seven ); odd.add( Nine ); List("Odds less than 10: ", odd); // Fill prime set with primes < 10 prime.add( Two ); prime.add( Three ); prime.add( Five ); prime.add( Seven ); List("Primes less than 10: ", prime); // Intersect 'Odd' and 'Prime' to give 'OddPrime' oddPrime.addIntersection( odd, prime); List("Odd primes less than 10: ", oddPrime); // Subtract all 'Odd' from 'Prime' to give 'EvenPrime' evenPrime.addDifference( prime, oddPrime); List("Even primes less than 10: ", evenPrime); return(0); } // Local function to display an IntSet void List(char *Message, IntSet &anIntSet) { PrintClass Print; cout << Message; anIntSet.allElementsDo(Print); cout << "\n"; } The program produces the following output: Odds less than 10: 1 3 5 7 9 Primes less than 10: 2 3 5 7 Odd primes less than 10: 3 5 7 Even primes less than 10: 2 ═══ 3.16. Sorted Bag ═══ A sorted bag is an ordered collection of zero or more elements with no key. Both element equality and multiple elements are supported. Combination of Flat Collection Properties gives an overview of the properties of a sorted bag and its relationship to other flat collections. Note: All member functions are described in Flat Collection Member Functions. ═══ 3.16.1. Class Implementation Variants ═══ ISortedBag, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On ISortedBag isrtbag.h AVL KeySortedSet IGSortedBag isrtbag.h AVL KeySortedSet ISortedBagOnBSTKeySortedSet isbbst.h B* KeySortedSet IGSortedBagOnBSTKeySortedSet isbbst.h B* KeySortedSet ISortedBagOn- isbsls.h LinkedSequence SortedLinkedSequence IGSortedBagOn isbsls.h LinkedSequence SortedLinkedSequence ISortedBagOn- isbsts.h TabularSequence SortedTabularSequence IGSortedBagOn- isbsts.h TabularSequence SortedTabularSequence ISortedBagOn- isbsds.h DilutedSequence SortedDilutedSequence IGSortedBagOn- isbsds.h DilutedSequence SortedDilutedSequence ═══ 3.16.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sorted bags: o Sorted Bag o Sorted Bag on B* Key Sorted Set o Sorted Bag on Sorted Linked Sequence o Sorted Bag on Sorted Tabular Sequence o Sorted Bag on Sorted Diluted Sequence ═══ 3.16.2.1. Sorted Bag ═══ ISortedBag IGSortedBag The default implementation of the class ISortedBag requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.16.2.2. Sorted Bag on B* Key Sorted Set ═══ ISortedBagOnBSTKeySortedSet IGSortedBagOnBSTKeySortedSet The default implementation of the class ISortedBagOnBSTKeySortedSet requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.16.2.3. Sorted Bag on Sorted Linked Sequence ═══ ISortedBagOnSortedLinkedSequence IGSortedBagOnSortedLinkedSequence The default implementation of the class ISortedBagOnSortedLinkedSequence requires the following element functions: Element Type o Constructor o Assignment o Equality test o Ordering relation ═══ 3.16.2.4. Sorted Bag on Sorted Tabular Sequence ═══ ISortedBagOnSortedTabularSequence IGSortedBagOnSortedTabularSequence The default implementation of the class ISortedBagOnSortedTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.16.2.5. Sorted Bag on Sorted Diluted Sequence ═══ ISortedBagOnSortedDilutedSequence IGSortedBagOnSortedDilutedSequence The default implementation of the class ISortedBagOnSortedDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.16.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASBag, which is found in the iasbag.h header file, or the corresponding reference class, IRSBag, which is found in the irsbag.h header file. See Polymorphic Use of Collections for further information. ═══ 3.16.3.1. Template Arguments and Required Functions ═══ IASBag IRSBag The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.16.4. Declarations for Sorted Bag ═══ template < class Element > class ISortedBag { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISortedBag (INumber numberOfElements = 100); ISortedBag (ISortedBag < Element > const&); ISortedBag < Element >& operator = (ISortedBag < Element > const&); ~ISortedBag (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISortedBag < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (ISortedBag < Element > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); INumber numberOfOccurrences(Element const&) const; Boolean locateNext (Element const&, ICursor&) const; INumber removeAllOccurrences (Element const&); INumber numberOfDifferentElements () const; Boolean setToNextDifferentElement (ICursor&) const; Boolean operator == (ISortedBag < Element > const&) const; Boolean operator != (ISortedBag < Element > const&) const; void unionWith (ISortedBag < Element > const&); void intersectionWith (ISortedBag < Element > const&); void differenceWith (ISortedBag < Element > const&); void addUnion (ISortedBag < Element > const&, ISortedBag < Element > const&); void addIntersection (ISortedBag < Element > const&, ISortedBag < Element > const&); void addDifference (ISortedBag < Element > const&, ISortedBag < Element > const&); void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (ISortedBag < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.17. Sorted Map ═══ A sorted map is an ordered collection of zero or more elements that have a key. Element equality is supported and the values of the elements are relevant. Elements are sorted by the value of their keys. Only elements with unique keys are supported. A request to add an element whose key already exists in another element of the collection is ignored. Combination of Flat Collection Properties gives an overview of the properties of a sorted map and its relationship to other flat collections. Note: All member functions of sorted map are described under "List of Functions". ═══ 3.17.1. Class Implementation Variants ═══ ISortedMap, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On ISortedMap isrtmap.h AVL KeySortedSet IGSortedMap isrtmap.h AVL KeySortedSet ISortedMapOnBSTKeySortedSet ismbst.h B* KeySortedSet IGSortedMapOnBSTKeySortedSet ismbst.h B* KeySortedSet ISortedMapOn- ismsls.h LinkedSequence SortedLinkedSequence IGSortedMapOn- ismsls.h LinkedSequence SortedLinkedSequence ISortedMapOn- ismsts.h TabularSequence SortedTabularSequence IGSortedMapOn- ismsts.h TabularSequence SortedTabularSequence ISortedMapOn- ismsds.h DilutedSequence SortedDilutedSequence IGSortedMapOn- ismsds.h DilutedSequence SortedDilutedSequence ═══ 3.17.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sorted maps: o Sorted Map o Sorted Map on B* Key Sorted Set o Sorted Map on Sorted Linked Sequence o Sorted Map on Sorted Tabular Sequence o Sorted Map on Sorted Diluted Sequence ═══ 3.17.2.1. Sorted Map ═══ ISortedMap IGSortedMap The implementation of the class ISortedMap requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.17.2.2. Sorted Map on B* Key Sorted Set ═══ ISortedMapOnBSTKeySortedSet IGSortedMapOnBSTKeySortedSet The implementation of the class ISortedMapOnBSTKeySortedSet requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.17.2.3. Sorted Map on Sorted Linked Sequence ═══ ISortedMapOnSortedLinkedSequence IGSortedMapOnSortedLinkedSequence The implementation of the class ISortedMapOnSortedLinkedSequence requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.17.2.4. Sorted Map on Sorted Tabular Sequence ═══ ISortedMapOnSortedTabularSequence IGSortedMapOnSortedTabularSequence The implementation of the class ISortedMapOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.17.2.5. Sorted Map on Sorted Diluted Sequence ═══ ISortedMapOnSortedDilutedSequence IGSortedMapOnSortedDilutedSequence The implementation of the class ISortedMapOnSortedDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.17.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASortedMap, which is found in the iasrtmap.h header file, or the corresponding reference class, IRSortedMap, which is found in the irsrtmap.h header file. See Polymorphic Use of Collections for further information. ═══ 3.17.3.1. Template Arguments and Required Functions ═══ IASortedMap IRSortedMap The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.17.4. Declarations for Sorted Map ═══ template < class Element, class Key > class ISortedMap { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISortedMap (INumber numberOfElements = 100); ISortedMap (ISortedMap < Element, Key > const&); ISortedMap < Element, Key >& operator = (ISortedMap < Element, Key > const&); ~ISortedMap (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISortedMap < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (ISortedMap < Element, Key > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (ISortedMap < Element, Key > const&) const; Boolean operator != (ISortedMap < Element, Key > const&) const; void unionWith (ISortedMap < Element, Key > const&); void intersectionWith (ISortedMap < Element, Key > const&); void differenceWith (ISortedMap < Element, Key > const&); void addUnion (ISortedMap < Element, Key > const&, ISortedMap < Element, Key > const&); void addIntersection (ISortedMap < Element, Key > const&, ISortedMap < Element, Key > const&); void addDifference (ISortedMap < Element, Key > const&, ISortedMap < Element, Key > const&); Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (ISortedMap < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey(Element const&); Boolean addOrReplaceElementWithKey(Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (ISortedMap < Element, Key > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.17.5. Coding Example for Sorted Map ═══ The following program uses a sorted map and a sorted relation to display sorted lists of the name and size of files contained on a disk. It uses the default classes, ISortedMap and ISortedRelation, to implement the collections. The program uses the sorted map to store the name of the file because all elements in a sorted map are unique and all names on a disk are unique. It uses a sorted relation for the file size because there may be identical file sizes, and identical values are permissible in sorted relations. The program uses the add function to fill both collections. To print the collections, it uses the forCursor macro and the allElementsDo function. The program produces a list of files sorted by name (in ascending order) and a list of the same files sorted by file size (in descending order). Because the output varies depending on the file system in use when it is run, no output is shown here. // dskusage.C - An example of using a Sorted Map and a Sorted Relation #include "dsur.h" // Our own common exit for all errors: void errorExit(int, char*, char* = ""); // Use the default Sorted Map as is: #include // Use the default Sorted Relation as is: #include int main (int argc, char* argv[]) { char* fspec = "dsu.dat"; // Default for input file if (argc > 1) fspec = argv[1]; ifstream inputfile(fspec); if (!inputfile) errorExit(20, "Unable to open input file", fspec); ISortedMap dsurByName; ISortedMap ::Cursor curByName(dsurByName); IGSortedRelation dsurBySpace; IGSortedRelation ::Cursor curBySpace(dsurBySpace); // Read all records into dsurByName while (inputfile.good()) { DiskSpaceUR dsur(inputfile); if (dsur.isValid()) { dsurByName.add(dsur); dsurBySpace.add(dsur); } } if (! inputfile.eof()) errorExit(39, "Error during read of", fspec); cout << "\n\nAll Disk Space Usage records " << "sorted (ascending) by name:\n\n"; forCursor(curByName) cout << " " << dsurByName.elementAt(curByName) << "\n"; cout << "\n\nAll Disk Space Usage records " << "sorted (descending) by space:\n\n"; forCursor(curBySpace) cout << " " << dsurBySpace.elementAt(curBySpace) << "\n"; return 0; } #include // for exit() definition void errorExit (int rc, char* s1, char* s2) { cerr << s1 << " " << s2 << "\n"; exit(rc); } ═══ 3.18. Sorted Relation ═══ A sorted relation is an unordered collection of zero or more elements that have a key. The elements are sorted by the value of their key. Element equality is supported and the values of the elements are relevant. The keys of the elements are not unique. You can add an element whether or not there is already an element in the collection with the same key. Combination of Flat Collection Properties gives an overview of the properties of a sorted relation and its relationship to other flat collections. Note: All member functions of sorted relation are described under "List of Functions". ═══ 3.18.1. Class Implementation Variants ═══ ISortedRelation, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Note: In the table, some class names have been hyphenated to fit in their column. In your code you should not include these hyphens in the class names. Class Name Header File Based On ISortedRelation isrtrel.h KeySortedBag on LinkedSequence IGSortedRelation isrtrel.h KeySortedBag on LinkedSequence ISortedRelationOn- isrsts.h KeySortedBag on TabularSequence SortedTabularSequence IGSortedRelationOn- isrsts.h KeySortedBag on TabularSequence SortedTabularSequence ISortedRelationOn- isrsds.h KeySortedBag on DilutedSequence SortedDilutedSequence IGSortedRelationOn- isrsds.h KeySortedBag on DilutedSequence SortedDilutedSequence ═══ 3.18.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sorted relations: o Sorted Relation o Sorted Relation on Sorted Tabular Sequence o Sorted Relation on Sorted Diluted Sequence ═══ 3.18.2.1. Sorted Relation ═══ ISortedRelation IGSortedRelation The default implementation of the class ISortedRelation requires the following element and key functions: Element Type o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.18.2.2. Sorted Relation on Sorted Tabular Sequence ═══ ISortedRelationOnSortedTabularSequence IGSortedRelationOnSortedTabularSequence The implementation of ISortedRelationOnSortedTabularSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.18.2.3. Sorted Relation on Sorted Diluted Sequence ═══ ISortedRelationOnSortedDilutedSequence IGSortedRelationOnSortedDilutedSequence The implementation of ISortedRelationOnSortedDilutedSequence requires the following element and key functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Key access o Equality test Key Type Ordering relation ═══ 3.18.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASortedRelation, which is found in the iasrtrel.h header file, or the corresponding reference class, IRSortedRelation, which is found in the irsrtrel.h header file. See Polymorphic Use of Collections for further information. ═══ 3.18.3.1. Template Arguments and Required Functions ═══ IASortedRelation IRSortedRelation The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.18.4. Declarations for Sorted Relation ═══ template < class Element, class Key > class ISortedRelation { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISortedRelation (INumber numberOfElements = 100); ISortedRelation (ISortedRelation < Element, Key > const&); ISortedRelation < Element, Key >& operator = (ISortedRelation < Element, Key > const&); ~ISortedRelation (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISortedRelation < Element, Key > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function)(Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (ISortedRelation < Element, Key > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (ISortedRelation < Element, Key > const&) const; Boolean operator != (ISortedRelation < Element, Key > const&) const; void unionWith (ISortedRelation < Element, Key > const&); void intersectionWith (ISortedRelation < Element, Key > const&); void differenceWith (ISortedRelation < Element, Key > const&); void addUnion (ISortedRelation < Element, Key > const&, ISortedRelation < Element, Key > const&); void addIntersection (ISortedRelation < Element, Key > const&, ISortedRelation < Element, Key > const&); void addDifference (ISortedRelation < Element, Key > const&, ISortedRelation < Element, Key > const&); Key const& key (Element const&) const; Boolean containsElementWithKey (Key const&) const; Boolean containsAllKeysFrom (ISortedRelation < Element, Key > const&) const; Boolean locateElementWithKey (Key const&, ICursor&) const; Boolean replaceElementWithKey (Element const&); Boolean replaceElementWithKey (Element const&, ICursor&); Boolean locateOrAddElementWithKey (Element const&); Boolean locateOrAddElementWithKey (Element const&, ICursor&); Boolean addOrReplaceElementWithKey (Element const&); Boolean addOrReplaceElementWithKey (Element const&, ICursor&); Boolean removeElementWithKey (Key const&); Element const& elementWithKey (Key const&) const; Element& elementWithKey (Key const&); INumber numberOfElementsWithKey (Key const&) const; Boolean locateNextElementWithKey (Key const&, ICursor&) const; INumber removeAllElementsWithKey (Key const&); INumber numberOfDifferentKeys () const; Boolean setToNextWithDifferentKey (ICursor&) const; void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (ISortedRelation < Element, Key > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.18.5. Coding Example for Sorted Relation ═══ See Coding Example for Sorted Map for an example of a sorted relation. ═══ 3.19. Sorted Set ═══ A sorted set is an ordered collection of zero or more elements with element equality but no key. Only unique elements are supported. A request to add an element that already exists is ignored. The value of the elements is relevant. The elements of a sorted set are ordered such that the value of each element is less than or equal to the value of its successor. The element with the smallest value currently in a sorted set is called the first element. The element with the largest value is called the last element. When an element is added, it is placed in the sorted set according to the defined ordering relation. Combination of Flat Collection Properties gives an overview of the properties of a sorted set and its relationship to other flat collections. Note: All member functions of sorted set are described under "List of Functions". ═══ 3.19.1. Class Implementation Variants ═══ ISortedSet, the first class in the table below, is the default implementation variant. If you want to use polymorphism, you can replace the following class implementation variants by the reference class. Class Name Header File Based On ISortedSet isrtset.h AVL KeySortedSet IGSortedSet isrtset.h AVL KeySortedSet ISortedSetOn- issbst.h B* KeySortedSet BSTKeySortedSet IGSortedSetOn- issbst.h B* KeySortedSet BSTKeySortedSet ISortedSetOn- isssls.h LinkedSequence SortedLinkedSequence IGSortedSetOn- isssls.h LinkedSequence SortedLinkedSequence ISortedSetOn- isssts.h TabularSequence SortedTabularSequence IGSortedSetOn- isssts.h TabularSequence SortedTabularSequence ISortedSetOn- isssds.h DilutedSequence SortedDilutedSequence IGSortedSetOn- isssds.h DilutedSequence SortedDilutedSequence ═══ 3.19.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for sorted sets: o Sorted Set o Sorted Set on B* Key Sorted Set o Sorted Set on Sorted Linked Sequence o Sorted Set on Sorted Tabular Sequence o Sorted Set on Sorted Diluted Sequence ═══ 3.19.2.1. Sorted Set ═══ ISortedSet IGSortedSet The default implementation of the class ISortedSet requires the following element functions: Element Type o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.19.2.2. Sorted Set on B* Key Sorted Set ═══ ISortedSetOnBSTKeySortedSet IGSortedSetOnBSTKeySortedSet The default implementation of the class ISortedSetOnBSTKeySortedSet requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.19.2.3. Sorted Set on Sorted Linked Sequence ═══ ISortedSetOnSortedLinkedSequence IGSortedSetOnSortedLinkedSequence The implementation of the class ISortedSetOnSortedLinkedSequence requires the following element functions: Element Type o Copy constructor o Assignment o Destructor o Equality test o Ordering relation ═══ 3.19.2.4. Sorted Set on Sorted Tabular Sequence ═══ ISortedSetOnSortedTabularSequence IGSortedSetOnSortedTabularSequence The implementation of the class ISortedSetOnSortedTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.19.2.5. Sorted Set on Sorted Diluted Sequence ═══ ISortedSetOnSortedDilutedSequence IGSortedSetOnSortedDilutedSequence The implementation of the class ISortedSetOnSortedDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment o Equality test o Ordering relation ═══ 3.19.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IASortedSet, which is found in the iasrtset.h header file, or the corresponding reference class, IRSortedSet, which is found in the irsrtset.h header file. See Polymorphic Use of Collections for further information. ═══ 3.19.3.1. Template Arguments and Required Functions ═══ IASortedSet IRSortedSet The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.19.4. Declarations for Sorted Set ═══ template < class Element > class ISortedSet { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; ISortedSet (INumber numberOfElements = 100); ISortedSet (ISortedSet < Element > const&); ISortedSet < Element >& operator = (ISortedSet < Element > const&); ~ISortedSet (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (ISortedSet < Element > const&); Element const& elementAt (ICursor const&) const; Element& elementAt (ICursor const&); Element const& anyElement () const; void removeAt (ICursor const&); INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0); void replaceAt (ICursor const&, Element const&); void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements() const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0); Boolean allElementsDo (IIterator &); Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; Boolean contains (Element const&) const; Boolean containsAllFrom (ISortedSet < Element > const&) const; Boolean locate (Element const&, ICursor&) const; Boolean locateOrAdd (Element const&); Boolean locateOrAdd (Element const&, ICursor&); Boolean remove (Element const&); Boolean operator == (ISortedSet < Element > const&) const; Boolean operator != (ISortedSet < Element > const&) const; void unionWith (ISortedSet < Element > const&); void intersectionWith (ISortedSet < Element > const&); void differenceWith (ISortedSet < Element > const&); void addUnion (ISortedSet < Element > const&, ISortedSet < Element > const&); void addIntersection (ISortedSet < Element > const&, ISortedSet < Element > const&); void addDifference (ISortedSet < Element > const&, ISortedSet < Element > const&); void removeFirst (); void removeLast (); void removeAtPosition (IPosition); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (ISortedSet < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; }; ═══ 3.19.5. Coding Example for Sorted Set ═══ The following program uses the default class, ISortedSet, to create sorted lists of planets with different properties. The program stores all planets in our solar system, all heavy planets in our solar system, all bright planets in our solar system, and all heavy or bright planets in our solar system in a number of sorted sets. Each set sorts the planets by its distance from the sun. The program uses the forCursor macro to create the heavyPlanets and the brightPlanets collections. It uses the allElementsDo function to display the planets in each collection and the unionWith function when creating the bright-or-heavy planets category. // planets.C - An example of using a Sorted Set #include // Let's use the Sorted Set Default Variant: #include // Get Class Planet: #include "planet.h" int main() { ISortedSet allPlanets, heavyPlanets, brightPlanets; // A cursor to cursor through allPlanets: ISortedSet::Cursor aPCursor(allPlanets); SayPlanetName showPlanet; allPlanets.add( Planet("Earth", 149.60f, 1.0000f, 99.9f)); allPlanets.add( Planet("Jupiter", 778.3f, 317.818f, -2.4f)); allPlanets.add( Planet("Mars", 227.9f, 0.1078f, -1.9f)); allPlanets.add( Planet("Mercury", 57.91f, 0.0558f, -0.2f)); allPlanets.add( Planet("Neptune", 4498.f, 17.216f, +7.6f)); allPlanets.add( Planet("Pluto", 5910.f, 0.18f, +14.7f)); allPlanets.add( Planet("Saturn", 1428.f, 95.112f, +0.8f)); allPlanets.add( Planet("Uranus", 2872.f, 14.517f, +5.8f)); allPlanets.add( Planet("Venus", 108.21f, 0.8148f, -4.1f)); forCursor(aPCursor) { if (allPlanets.elementAt(aPCursor).isHeavy()) heavyPlanets.add(allPlanets.elementAt(aPCursor)); if (allPlanets.elementAt(aPCursor).isBright()) brightPlanets.add(allPlanets.elementAt(aPCursor)); } cout << "\n\n" << "All Planets: \n"; allPlanets.allElementsDo(showPlanet); cout << "\n\n" << "Heavy Planets: \n"; heavyPlanets.allElementsDo(showPlanet); cout << "\n\n" << "Bright Planets: \n"; brightPlanets.allElementsDo(showPlanet); cout << "\n\n" << "Bright-or-Heavy Planets: \n"; brightPlanets.unionWith(heavyPlanets); brightPlanets.allElementsDo(showPlanet); cout << "\n\nDid you notice that all these Sets are sorted" << " in the same order\n" << " (distance of planet from sun) ? \n"; return 0; } The program produces the following output: All Planets: Mercury Venus Earth Mars Jupiter Saturn Uranus Neptune Pluto Heavy Planets: Jupiter Saturn Uranus Neptune Bright Planets: Mercury Venus Mars Jupiter Bright-or-Heavy Planets: Mercury Venus Mars Jupiter Saturn Uranus Neptune Did you notice that all these Sets are sorted in the same order (distance of planet from sun) ? ═══ 3.20. Stack ═══ A stack is a sequence with restricted access. It is an ordered collection of elements with no key and no element equality. The elements are arranged so that each collection has a first and a last element, each element except the last has a next element, and each element but the first has a previous element. The type and value of the elements are irrelevant and have no effect on the behavior of the stack. Elements are added to and deleted from the top of the stack. Consequently, the elements of a stack are in reverse chronological order. A stack is characterized by a last-in, first-out (LIFO) behavior. Note: All member functions of stack are described under "List of Functions". ═══ 3.20.1. Class Implementation Variants ═══ IStack, the first class in the table below, is the default implementation variant. If you need polymorphism you can replace the following class implementation variants by the reference class. Class Name Header File Based On IStack istack.h LinkedSequence IGStack istack.h LinkedSequence IStackOnTabularSequence istkts.h TabularSequence IGStackOnTabularSequence istkts.h TabularSequence IStackOnDilutedSequence istkds.h DilutedSequence IGStackOnDilutedSequence istkds.h DilutedSequence ═══ 3.20.2. Template Arguments and Required Functions ═══ The following implementation variants are defined for stacks: o Stack o Stack on Tabular Sequence o Stack on Diluted Sequence ═══ 3.20.2.1. Stack ═══ IStack IGStack The default implementation of the class IStack requires the following element functions: Element Type o Copy constructor o Destructor o Assignment ═══ 3.20.2.2. Stack on Tabular Sequence ═══ IStackOnTabularSequence IGStackOnTabularSequence The implementation of the class IStackOnTabularSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment ═══ 3.20.2.3. Stack on Diluted Sequence ═══ IStackOnDilutedSequence IGStackOnDilutedSequence The implementation of the class IStackOnDilutedSequence requires the following element functions: Element Type o Default constructor o Copy constructor o Destructor o Assignment ═══ 3.20.3. Abstract Class and Reference Class ═══ For polymorphism, you can use the corresponding abstract class, IAStack, which is found in the iastack.h header file, or the corresponding reference class, IRStack, which is found in the irstack.h header file. See Polymorphic Use of Collections for further information. ═══ 3.20.3.1. Template Arguments and Required Functions ═══ IRStack IAStack The concrete base class is one of the classes defined above. The required functions are the same as the required functions of the concrete base class. ═══ 3.20.4. Declarations for Stack ═══ template < class Element > class IStack { public: class Cursor : ICursor { Element& element (); void setToLast (); void setToPrevious (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IStack (INumber numberOfElements = 100); IStack (IStack < Element > const&); IStack < Element >& operator = (IStack < Element > const&); ~IStack (); Boolean add (Element const&); Boolean add (Element const&, ICursor&); void addAllFrom (IStack < Element > const&); Element const& elementAt (ICursor const&) const; Element const& anyElement () const; void removeAll (); Boolean isBounded () const; INumber maxNumberOfElements () const; INumber numberOfElements () const; Boolean isEmpty () const; Boolean isFull () const; ICursor* newCursor () const; Boolean setToFirst (ICursor&) const; Boolean setToNext (ICursor&) const; Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &) const; Boolean isConsistent () const; void removeLast (); Element const& firstElement () const; Element const& lastElement () const; Element const& elementAtPosition (IPosition) const; Boolean setToLast (ICursor&) const; Boolean setToPrevious (ICursor&) const; void setToPosition (IPosition, ICursor&) const; Boolean isFirst (ICursor const&) const; Boolean isLast (ICursor const&) const; long compare (IStack < Element > const&, long (*comparisonFunction) (Element const&, Element const&)) const; void addAsLast (Element const&); void addAsLast (Element const&, ICursor&); void push (Element const&); void push (Element const&, ICursor&); void pop (); void pop (Element&); Element const& top () const; }; ═══ 3.20.5. Coding Example for Stack ═══ The following program creates two stacks (Stack1 and Stack2) using the default class, IStack. It adds a number of words to Stack1, removes them from Stack1, adds them to Stack2, and finally removes them from Stack2 so that they can be printed. We use the push and pop functions for adding and removing elements, respectively. Between these stack operations the stacks are printed. During printing we do not want to change the stack. Therefore we use the constant version of the iterator class, IConstantIterator with the allElementsDo function. In the end, the words will print in the same order as they were originally added to Stack1. Because of the nature of the stack class, the program must use the constant iterator class, IConstantIterator, when printing the stacks. It uses the push and pop functions for adding and removing elements, respectively. The allElementsDo function is used when the collection is printed. // pushpop.C - An example of using a Stack #include #include // Let's use the default stack: IStack #include typedef IStack SimpleStack; // The stack requires iteration to be const. typedef IConstantIterator StackIterator; // Test variables to put into our Stack: char *String[9] = { "The", "quick", "brown", "fox", "jumps", "over", "a", "lazy", "dog." }; // A class to display the contents of our Stack: class PrintClass : public StackIterator { public: Boolean applyTo(char* const& w) { cout << w << "\n"; return(True); } }; int main() { SimpleStack Stack1, Stack2; char *S; PrintClass Print; int i; for (i = 0; i < 9; i ++) { Stack1.push(String[i]); } cout << "Contents of Stack1:\n"; Stack1.allElementsDo(Print); cout << "----------------------------\n"; while (!Stack1.isEmpty()) { Stack1.pop(S); // Pop from stack 1 Stack2.push(S); // Add it on top of stack 2 } cout << "Contents of Stack2:\n"; Stack2.allElementsDo(Print); cout << "----------------------------\n"; while (!Stack2.isEmpty()) { Stack2.pop(S); cout << "Popped from Stack 2: " << S << "\n"; } return(0); } This program produces the following output: Contents of Stack1: The quick brown fox jumps over a lazy dog. ---------------------------- Contents of Stack2: dog. lazy a over jumps fox brown quick The ---------------------------- Popped from Stack 2: The Popped from Stack 2: quick Popped from Stack 2: brown Popped from Stack 2: fox Popped from Stack 2: jumps Popped from Stack 2: over Popped from Stack 2: a Popped from Stack 2: lazy Popped from Stack 2: dog. ═══ 4. Reference Manual - Tree Classes ═══ This section contains the following chapters: Introduction to Trees Introduces the concept of trees. N-ary Tree Describes N-ary tree, the tree collection of the Collection Classes. Defines the class implementation variants, template arguments and required functions for N-ary tree. Declarations for N-ary tree are provided, terms are defined, and the public member functions of N-ary tree are described. ═══ 4.1. Introduction to Trees ═══ A tree is a collection of nodes that can have an arbitrary number of references to other nodes. There can be no cycles or short-circuit references. A unique path connects every two nodes. One node is designated as the root of the tree. Formally, a tree can be defined recursively in the following manner: 1. A single node by itself is a tree. This node is also the root of the tree. 2. If N is a node and T-1, T-2, ..., T-k are trees with roots R-1, R-2, ..., R-k, respectively, then a new tree can be constructed by making N the parent of the nodes R-1, R-2, ..., R-k. In this new tree, N is the root and T-1, T-2, ..., T-k are the subtrees of the root N. Nodes R-1, R-2, ..., R-k are called children of node N. Associated with each node is a data item called element. Nodes without children are called leaves or terminals. The number of children in a node is called the degree of that node. The level of a given node is the number of steps in the path from the root to the given node. The root is at level 0 by definition. The height of a tree is the length of the longest path from the root to any node. ═══ 4.1.1. Defining the Traversal Order of Tree Elements ═══ You can define the order in which nodes of a tree are traversed by specifying a parameter of type ITreeIterationOrder in calls to the following member functions: o setToFirst o setToLast o setToNext o setToPrevious o allElementsDo, allSubtreeElementsDo These functions are described in N-ary Tree. The ITreeIterationOrder parameter can have one of two values: IPreorder or IPostorder. The effect of each of these values is explained below. ═══ 4.1.1.1. IPreorder ═══ The search begins at the root of the tree, and continues with the leftmost child of the root. If the child is the root of a subtree, the search continues with the leftmost child of the subtree, and so on, until a terminal node is detected. The search continues with all siblings of the terminal node, from left to right. If any of these siblings is the root of a subtree, the subtree is searched the same way as described above for the tree. The preorder method can be summarized by the following recursive rules: 1. Visit the root. 2. Traverse the subtrees from left to right in preorder. ═══ 4.1.1.2. IPostorder ═══ The IPostorder method is the opposite of IPreorder. The search begins with the leftmost terminal node in the tree. Then that node's siblings are searched from left to right. If any of these siblings is the root of a subtree, the subtree is searched for its leftmost terminal node. The postorder method can be sumarized by the following recursive rules: 1. Traverse the subtrees from left to right in postorder. 2. Visit the root. The following figure shows a tree with 12 nodes, and the order of traversal for both preorder and postorder methods. Numbers indicate the preorder method (node 1 is searched before node 2) while letters indicate the postorder method (node A is searched before node B). Preorder and Postorder Iteration Methods for Trees ┌───────┐ │1 M│ └───┬───┘ ┌───────────┼──────────┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ │2 D│ │6 G│ │9 L│ └───┬───┘ └───┬───┘ └───┬───┘ ┌───┴───┐ │ ├───────────┬───────────┐ │3 C│ │ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ └───┬───┘ │ │10 H│ │11 J│ │13 K│ ┌─────────────┴───┐ │ └───────┘ └───┬───┘ └───────┘ │ │ └──┬─────────┐ │ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ │4 A│ │5 B│ │7 E│ │8 F│ │12 I│ └───────┘ └───────┘ └───────┘ └───────┘ └───────┘ ═══ 4.2. N-ary Tree ═══ An n-ary tree is a special tree where each node can have up to n children. n must be greater than one. If n is one, the tree is a list. If n is zero, the structure loses its meaning. ═══ 4.2.1. Class Implementation Variants ═══ ITree is the default implementation variant based on tabular tree. IGTree is the default implementation variant with generic operations class. Both classes are declared in itree.h. No reference class exists for tree classes. ═══ 4.2.1.1. Template Arguments and Required Functions ═══ ITree IGTree The default implementation of ITree requires the following element functions: ═══ 4.2.1.1.1. Element Type ═══ o Copy constructor o Destructor o Assignment The argument value of numberOfElements specifies the maximum number of children for each node. ═══ 4.2.2. Declarations for N-ary Tree ═══ template < class Element, class ElementOps, INumber pNumberOfChildren > class IGTree { public : class Cursor : public ITreeCursor { public: Cursor (IGTree < Element, ElementOps, pNumberOfChildren > const& collection); Boolean setToRoot (); Boolean setToChild (IPosition); Boolean setToFirstExistingChild (); Boolean setToNextExistingChild (); Boolean setToLastExistingChild (); Boolean setToPreviousExistingChild (); Boolean isValid () const; void invalidate (); Element const& element (); Boolean operator== (Cursor const& cursor); Boolean operator!= (Cursor const& cursor); }; IGTree (); IGTree (IGTree < Element, ElementOps, pNumberOfChildren > const&); ~IGTree (); IGTree < Element, ElementOps, pNumberOfChildren >& operator= (IGTree < Element, ElementOps, pNumberOfChildren > const&); void copy (IGTree < Element, ElementOps, pNumberOfChildren > const&); void copySubtree (IGTree < Element, ElementOps, pNumberOfChildren > const&, ITreeCursor const&); void addAsRoot (Element const&); void addAsChild (ITreeCursor const&, IPosition, Element const&); void attachAsRoot (IGTree < Element, ElementOps, pNumberOfChildren >&); void attachAsChild (ITreeCursor const&, IPosition, IGTree < Element, ElementOps, pNumberOfChildren >&); void attachSubtreeAsRoot (IGTree < Element, ElementOps, pNumberOfChildren >&, ITreeCursor const&); void attachSubtreeAsChild (ITreeCursor const&, IPosition, IGTree < Element, ElementOps, pNumberOfChildren >&, ITreeCursor const&); INumber removeAll (); INumber removeSubtree (ITreeCursor const&); Element const& elementAt (ITreeCursor const&) const; Element& elementAt (ITreeCursor const&); void replaceAt (ITreeCursor const&, Element const&); INumber numberOfChildren () const; INumber numberOfElements () const; INumber numberOfSubtreeElements (ITreeCursor const&) const; INumber numberOfLeaves () const; INumber numberOfSubtreeLeaves (ITreeCursor const&) const; Boolean isEmpty () const; ITreeCursor* newCursor () const; Boolean isRoot (ITreeCursor const&) const; Boolean isLeaf (ITreeCursor const&) const; INumber position (ITreeCursor const&) const; Boolean hasChild (IPosition, ITreeCursor const&) const; Boolean setToRoot (ITreeCursor&) const; Boolean setToChild (IPosition, ITreeCursor&) const; Boolean setToParent (ITreeCursor&) const; Boolean setToFirstExistingChild (ITreeCursor&) const; Boolean setToNextExistingChild (ITreeCursor&) const; Boolean setToLastExistingChild (ITreeCursor&) const; Boolean setToPreviousExistingChild (ITreeCursor&) const; Boolean setToFirst (ITreeCursor&, ITreeIterationOrder) const; Boolean setToNext (ITreeCursor&, ITreeIterationOrder) const; Boolean setToLast (ITreeCursor&, ITreeIterationOrder) const; Boolean setToPrevious (ITreeCursor&, ITreeIterationOrder) const; Boolean allElementsDo (Boolean (*function) (Element&, void*), ITreeIterationOrder, void* additionalArgument = 0); Boolean allElementsDo (IIterator &, ITreeIterationOrder); Boolean allElementsDo (Boolean (*function) (Element const&, void*), ITreeIterationOrder, void* additionalArgument = 0) const; Boolean allElementsDo (IConstantIterator &, ITreeIterationOrder) const; Boolean allSubtreeElementsDo (ITreeCursor const&, Boolean (*function) (Element&, void*), ITreeIterationOrder, void* additionalArgument = 0); Boolean allSubtreeElementsDo (ITreeCursor const&, IIterator &, ITreeIterationOrder); Boolean allSubtreeElementsDo (ITreeCursor const&, Boolean (*function) (Element const&, void*), ITreeIterationOrder, void* additionalArgument = 0) const; Boolean allSubtreeElementsDo (ITreeCursor const&, IConstantIterator &, ITreeIterationOrder) const; }; ═══ 4.2.3. Terms Used ═══ Some of the terms used in this chapter are defined below. You can also use the Glossary to look up terms you are unfamiliar with. this tree The tree to which a function is applied, in contrast to the given tree. given ... Referring to a tree, element, or function that is given as a function argument. returned element An element returned as a function return value. iteration order The order in which elements are visited in functions allElementsDo, allSubtreeElementsDo, setToNext, and setToPrevious. ═══ 4.2.4. Tree Functions ═══ This section lists the public member functions of n-ary trees. The following member functions are described: Constructor Copy Constructor Destructor operator= addAsChild addAsRoot allElementsDo allElementsDo allSubtreeElementsDo allSubtreeElementsDo attachAsChild attachSubtreeAsChild attachAsRoot attachSubtreeAsRoot copy copySubtree elementAt hasChild isEmpty isLeaf isRoot newCursor numberOfChildren numberOfElements numberOfSubtreeElements numberOfLeaves numberOfSubtreeLeaves position removeAll removeSubtree replaceAt setToChild setToFirst setToFirstExistingChild setToLast setToLastExistingChild setToNext setToNextExistingChild setToParent setToPrevious setToPreviousExistingChild setToRoot ═══ 4.2.4.1. Constructor ═══ ITree ( ) ; Constructs a tree. The tree is initially empty; that is, it contains no node. ═══ 4.2.4.2. Copy Constructor ═══ ITree ( ITree const& tree ) ; Constructs a tree by copying all elements from the given tree. Exception IOutOfMemory ═══ 4.2.4.3. Destructor ═══ ~ITree ( ) ; Removes all elements from this tree. Side Effects All cursors of the tree become undefined. ═══ 4.2.4.4. operator= ═══ ITree & operator= ( ITree const& tree ) ; Copies all elements of the given tree to this tree. Return Value A reference to this tree. Side Effects All cursors of this tree become undefined. Exception IOutOfMemory ═══ 4.2.4.5. addAsChild ═══ void addAsChild ( ITreeCursor const& cursor, IPosition position, Element const& element ) ; Adds the given element as a child with the given position to the node of this tree denoted by the given cursor. Preconditions o The cursor must point to an element of this tree. o (1 =< position =< numberOfChildren) o The node denoted by the given cursor (of this tree) must not have a child at the given position. Exceptions o IOutOfMemory o ICursorInvalidException o IPositionInvalidException o IChildAlreadyExistsException ═══ 4.2.4.6. addAsRoot ═══ void addAsRoot ( Element const& element ) ; Adds the given element as root of the tree. Precondition The tree must not have a root; that is, it must be empty. Exceptions o IOutOfMemory o IRootAlreadyExistsException ═══ 4.2.4.7. allElementsDo, allSubtreeElementsDo ═══ Boolean allElementsDo ( Boolean (*function) (Element&, void*), ITreeIterationOrder iterationOrder, void* additionalArgument = 0 ) ; Boolean allElementsDo ( Boolean (*function) (Element const&, void*), ITreeIterationOrder iterationOrder, void* additionalArgument = 0 ) const; Boolean allSubtreeElementsDo ( ITreeCursor const& cursor, Boolean (*function) (Element const&, void*), ITreeIterationOrder iterationOrder, void* additionalArgument = 0 ) const; Boolean allSubtreeElementsDo ( ITreeCursor const& cursor, Boolean (*function) (Element&, void*), ITreeIterationOrder iterationOrder, void* additionalArgument = 0 ) ; Calls the given function for all elements of the subtree denoted by the given cursor (of this tree) until the given function returns False. The elements are visited in the given iteration order. Additional arguments can be passed to the given function using additionalArgument. The additional argument defaults to zero if no additional argument is given. The allElementsDo function (without a subtree cursor argument) iterates over all elements of the tree. Note: The given function must not remove elements from or add elements to the tree. Return Value Returns True if the given function returns True for every element it is applied to. Preconditions o The cursor must belong to this tree o The cursor must point to an element of this tree Exception IInvalidCursorException ═══ 4.2.4.8. allElementsDo, allSubtreeElementsDo ═══ Boolean allElementsDo ( IIterator & iterator, ITreeIterationOrder iterationOrder ) ; Boolean allElementsDo ( IConstantIterator & iterator, ITreeIterationOrder iterationOrder ) const; Boolean allSubtreeElementsDo ( ITreeCursor const& cursor, IIterator & iterator, ITreeIterationOrder iterationOrder ) ; Boolean allSubtreeElementsDo ( ITreeCursor const& cursor, IConstantIterator & iterator, ITreeIterationOrder iterationOrder ) const; Calls the applyTo function of the given iterator for all elements of the subtree denoted by the given cursor (of this tree) until the applyTo function returns False. The elements are visited in the given iteration order. The allElementsDo function (without a subtree cursor argument) iterates over all elements of the tree. Note: The applyTo function must not remove elements from or add elements to the tree. Preconditions o The cursor must belong to this tree o The cursor must point to an element of this tree Return Value Returns True if the applyTo function returns True for every element it is applied to. Exceptions IInvalidCursorException ═══ 4.2.4.9. attachAsChild, attachSubtreeAsChild ═══ void attachAsChild ( ITreeCursor const& cursor, IPosition position, ITree & tree ) ; void attachSubtreeAsChild ( ITreeCursor const& cursor, IPosition position, ITree & tree, ITreeCursor const& subTreeCursor ) ; Copies the subtree denoted by the given subtree cursor as a child with the given position of the node (of this tree) denoted by the given cursor. Removes this subtree from the given tree. The attachAsChild function (without a subtree cursor argument) copies and removes the whole given tree. Note: These functions are implemented by copying a pointer to the subtree, rather than by copying all elements in the subtree. Preconditions o The cursor must point to an element of this tree. o The subtree cursor must point to an element of the given tree. o (1 =< position =< numberOfChildren) o The node denoted by the given cursor (of this tree) must not have a child at the given position. Exceptions o ICursorInvalidException o IPositionInvalidException o IChildAlreadyExistsException ═══ 4.2.4.10. attachAsRoot, attachSubtreeAsRoot ═══ void attachAsRoot ( ITree & tree ) ; void attachSubtreeAsRoot ( ITree & tree, ITreeCursor const& cursor ) ; Copies the subtree denoted by the cursor of the given tree to (the root of) this tree, and removes this subtree from the given tree. The attachAsRoot function (without a cursor argument) copies and removes the whole given tree. Note: These functions are implemented by copying a pointer to the subtree, rather than by copying all elements in the subtree. Preconditions o The cursor must point to an element of this tree. o The tree must not have a root; that is, it must be empty. Exceptions o ICursorInvalidException o IRootAlreadyExistsException ═══ 4.2.4.11. copy, copySubtree ═══ void copy ( (ITree const& tree ) ; void copySubtree ( ITree const& tree, ITreeCursor const& cursor ) ; Removes all elements from this tree, and copies the subtree denoted by the given cursor of the given tree to (the root of) this tree. The copy function (without a cursor argument) copies the whole given tree. Preconditions The cursor must point to an element of the given tree. Exceptions o IOutOfMemory o ICursorInvalidException ═══ 4.2.4.12. elementAt ═══ Element const& elementAt ( ITreeCursor const& cursor ) const; Element& elementAt ( ITreeCursor const& cursor ) ; Returns a reference to the element pointed to by the given cursor. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.13. hasChild ═══ Boolean hasChild ( IPosition position, ITreeCursor const& cursor ) const; Returns True if the node pointed to by the given cursor has a child at the given position. Preconditions o The cursor must point to an element of this tree. o (1 =< position =< numberOfChildren) Exceptions o ICursorInvalidException o IPositionInvalidException ═══ 4.2.4.14. isEmpty ═══ Boolean isEmpty ( ) const; Returns True if the tree is empty. ═══ 4.2.4.15. isLeaf ═══ Boolean isLeaf ( ITreeCursor const& cursor ) const; Returns True if the node pointed to by the given cursor is a leaf node of the tree; that is, it has no children. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.16. isRoot ═══ Boolean isRoot ( ITreeCursor const& cursor ) const; Returns True if the node pointed to by the given cursor is the root node of the tree. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.17. newCursor ═══ ITreeCursor* newCursor ( ) const; Creates a cursor for the tree. The cursor is initially invalid. Return Value Pointer to the cursor. Exception IOutOfMemory ═══ 4.2.4.18. numberOfChildren ═══ INumber numberOfChildren ( ) const; Returns the number of children a node can possibly have. The actual number of children of any node will always be less than or equal to this number. ═══ 4.2.4.19. numberOfElements, numberOfSubtreeElements ═══ INumber numberOfElements ( ) const; INumber numberOfSubtreeElements ( ITreeCursor const& cursor ) const; Returns the number of elements that the subtree denoted by the given cursor contains. The subtree root, inner, and leaf nodes are counted. The numberOfElements function (without a cursor argument) counts the number of elements in the whole tree. Preconditions The cursor must belong to the tree and must point to an element in the tree. Exception ICursorInvalidException ═══ 4.2.4.20. numberOfLeaves, numberOfSubtreeLeaves ═══ INumber numberOfLeaves ( ) const; INumber numberOfSubtreeLeaves ( ITreeCursor const& cursor ) const; Returns the number of leaf elements that the subtree denoted by the given cursor contains. Leaves are nodes that have no children. The numberOfLeaves function (without a cursor argument) counts the number of leaves in the whole tree. Preconditions The cursor must belong to the tree and must point to an element in the tree. Exception ICursorInvalidException ═══ 4.2.4.21. position ═══ INumber position ( ITreeCursor const& cursor ) const; Returns the position of the node pointed to by the given cursor as a child with respect to its parent node. The position of the root node is 1. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.22. removeAll, removeSubtree ═══ void removeAll ( ) ; void removeSubtree ( ITreeCursor const& cursor ) ; Removes the subtree denoted by the given cursor (of this tree). The removeAll function (without a cursor argument) removes all elements from this tree. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.23. replaceAt ═══ void replaceAt ( ITreeCursor const& cursor, Element const& element ) ; Replaces the element pointed to by the cursor with the given element. Precondition The cursor must point to an element of this tree. Exception ICursorInvalidException ═══ 4.2.4.24. setToChild ═══ Boolean setToChild ( IPosition position, ITreeCursor& cursor ) const; Sets the cursor to the child with the given position of the node denoted by the given cursor (of this tree). Invalidates the cursor if this child does not exist. Preconditions o The cursor must point to an element of this tree o (1 =< position =< numberOfChildren) Return Value Returns True if the child exists. Exceptions o ICursorInvalidException o IPositionInvalidException ═══ 4.2.4.25. setToFirst ═══ Boolean setToFirst ( ITreeCursor& cursor, ITreeIterationOrder iterationOrder ) const; Sets the cursor to the first node in the given iteration order. Invalidates the cursor if the tree is empty. Precondition The cursor must belong to this tree. Return Value Returns True if the tree is not empty. Exception ICursorInvalidException ═══ 4.2.4.26. setToFirstExistingChild ═══ Boolean setToFirstExistingChild ( ITreeCursor& cursor ) const; Sets the cursor to the first child of the node denoted by the given cursor (of this tree). Invalidates the cursor if the node has no child (that is, the node denotes a leaf node of this tree). Preconditions The cursor must point to an element of this tree. Return Value Returns True if the node has a child. Exception ICursorInvalidException ═══ 4.2.4.27. setToLast ═══ Boolean setToLast ( ITreeCursor& cursor, ITreeIterationOrder iterationOrder ) const; Sets the cursor to the last node in the given iteration order. Invalidates the cursor if the tree is empty. Precondition The cursor must belong to this tree. Return Value Returns True if the tree is not empty. Exception ICursorInvalidException ═══ 4.2.4.28. setToLastExistingChild ═══ Boolean setToLastExistingChild ( ITreeCursor& cursor ) const; Sets the cursor to the last child of the node denoted by the given cursor (of this tree). Invalidates the cursor if the node has no child (that is, the node denotes a leaf node of this tree). Precondition The cursor must point to an element of this tree. Return Value Returns True if the node has a child. Exception ICursorInvalidException ═══ 4.2.4.29. setToNext ═══ Boolean setToNext ( ITreeCursor& cursor, ITreeIterationOrder iterationOrder ) const; Sets the cursor to the next node in the given iteration order. Invalidates the cursor if there is no next node. Precondition The cursor must point to an element of this tree. Return Value Returns True if the given cursor does not point to the last node (in iteration order). Exception ICursorInvalidException ═══ 4.2.4.30. setToNextExistingChild ═══ Boolean setToNextExistingChild ( ITreeCursor& cursor ) const; Sets the cursor to the next existing sibling of the node denoted by the given cursor (of this tree). Invalidates the cursor if the node has no next sibling (that is, the node is the last existing child of its parent). Precondition The cursor must point to an element of this tree. Return Value Returns True if the node has a next sibling. Exception ICursorInvalidException ═══ 4.2.4.31. setToParent ═══ Boolean setToParent ( ITreeCursor& cursor ) const; Sets the cursor to the parent of the node denoted by the given cursor (of this tree). Invalidates the cursor if the node has no parent (that is, the node denotes the root node of this tree). Precondition The cursor must point to an element of this tree. Return Value Returns True if the node has a parent. Exception ICursorInvalidException ═══ 4.2.4.32. setToPrevious ═══ Boolean setToPrevious ( ITreeCursor& cursor, ITreeIterationOrder iterationOrder ) const; Sets the cursor to the previous node in the given iteration order. Invalidates the cursor if there is no previous node. Precondition The cursor must point to an element of this tree. Return Value Returns True if the given cursor does not point to the first node (in iteration order). Exception ICursorInvalidException ═══ 4.2.4.33. setToPreviousExistingChild ═══ Boolean setToPreviousExistingChild ( ITreeCursor& cursor ) const; Sets the cursor to the previous existing sibling of the node denoted by the given cursor (of this tree). Invalidates the cursor if the node has no previous sibling (that is, the node is the first existing child of its parent). Precondition The cursor must point to an element of this tree. Return Value Returns True if the node has a previous sibling. Exception ICursorInvalidException ═══ 4.2.4.34. setToRoot ═══ Boolean setToRoot ( ITreeCursor& cursor ) const; Sets the cursor to the root node of the tree. Invalidates the cursor if the tree is empty (that is, if no root node exists). Precondition The cursor must belong to this tree. Return Value Returns True if the tree is not empty. Exception ICursorInvalidException ═══ 5. Reference Manual - Auxiliary Classes ═══ This section contains the following chapters: Cursor Describes the declarations and public member functions for the cursor classes. Tree Cursor Describes the declarations and public member functions for the tree cursor classes. Iterator and Constant Iterator Classes Describes the declarations and public member functions for the classes that define the interface for iterator objects. Pointer and Managed Pointer Classes Describes the declarations and public member functions for the classes that allow you to access collection classes through pointers. ═══ 5.1. Cursor ═══ Each collection class defines its own nested cursor class. All of these classes are derived from the common base class ICursor. This chapter describes the general methods of the ICursor class as well as the specific methods provided for specific collections. Because ICursor is an abstract class, no objects of type ICursor can be declared. ICursor objects can only be obtained by using the collection method newCursor, which returns a pointer to a newly created cursor object. Each cursor instance is associated with a collection instance; cursor functions just call the corresponding function for this collection. For example, cursor.setToFirst() is the same as collection.setToFirst(cursor) , where collection is the instance associated with cursor. See Cursors for more information on cursors. ═══ 5.1.1. Declarations for Cursor ═══ class ICursor { public: virtual Boolean setToFirst () = 0; virtual Boolean setToNext () = 0; virtual Boolean isValid () const = 0; virtual void invalidate () = 0; }; ═══ 5.1.2. Public Member Functions for Cursor ═══ The following member functions are described: o Constructor o isValid o invalidate o element o operator!= o operator== o setToFirst o setToLast o setToNext o setToPrevious ═══ 5.1.2.1. Constructor ═══ ICursor ( Collection const& ) ; Constructs the cursor and associates it with the given collection. The cursor is initially invalid. The name of the constructor is that of the nested cursor class, not ICursor. ═══ 5.1.2.2. isValid ═══ Boolean isValid ( ) const; Returns True if the cursor points to an element of the associated collection. ═══ 5.1.2.3. invalidate ═══ void invalidate ( ) ; Invalidates the cursor; that is, it no longer points to an element of the associated collection. ═══ 5.1.2.4. element ═══ Element const& element ( ) const; Returns a constant reference to the element of the associated collection to which the cursor points. Precondition The cursor must point to an element of the associated collection. Exception ICursorInvalidException ═══ 5.1.2.5. operator!= ═══ Boolean operator!= ( Cursor const& cursor ) const; Returns True if the cursor does not point to the same element (of the same collection) as the given cursor. ═══ 5.1.2.6. operator== ═══ Boolean operator== ( Cursor const& cursor ) const; Returns True if the cursor points to the same element (of the same collection) as the given cursor. ═══ 5.1.2.7. setToFirst ═══ Boolean setToFirst ( ) ; Sets the cursor to the first element of the associated collection in iteration order. Invalidates the cursor if the collection is empty (if no first element exists). Return Value Returns True if the associated collection is not empty. ═══ 5.1.2.8. setToLast ═══ Boolean setToLast ( ) ; Sets the cursor to the last element of the associated collection in iteration order. Invalidates the cursor if the collection is empty (no last element exists). Returns True if the associated collection was not empty. ═══ 5.1.2.9. setToNext ═══ Boolean setToNext ( ) ; Sets the cursor to the next element in the associated collection in iteration order. Invalidates the cursor if no more elements are left to be visited. Returns True if there was a next element. Precondition The cursor must point to an element of the associated collection. Exception ICursorInvalidException ═══ 5.1.2.10. setToPrevious ═══ Boolean setToPrevious ( ) ; Sets the cursor to the previous element of the associated collection in iteration order. Invalidates the cursor if no such element exists. Return Value Returns True if a previous element exists. Precondition The cursor must point to an element of the associated collection. Exception ICursorInvalidException ═══ 5.2. Tree Cursor ═══ For n-ary trees, cursors are used to point to nodes in the tree. Unlike cursors of flat collections, tree cursors stay defined when elements are added to the tree, or when elements other than the one pointed to are removed. Cursors are used in operations to access the element information stored in a node. They are also used to designate a subtree of the tree, namely the subtree whose root node the cursor points to. As for flat collections, a distinction is made between the abstract base class ITreeCursor, and Cursor classes local to the tree classes themselves. The local, or nested, cursor classes are derived from the abstract base class. ═══ 5.2.1. Declarations for Tree Cursor ═══ class ITreeCursor { public: virtual Boolean setToRoot () = 0; virtual Boolean setToChild (IPosition) = 0; virtual Boolean setToParent () = 0; virtual Boolean setToFirstExistingChild () = 0; virtual Boolean setToNextExistingChild () = 0; virtual Boolean setToLastExistingChild () = 0; virtual Boolean setToPreviousExistingChild () = 0; virtual Boolean isValid () const = 0; virtual void invalidate () = 0; }; ═══ 5.2.2. Public Member Functions of Tree Cursor ═══ The following member functions are described: o Constructor o isValid o invalidate o element o operator!= o operator== o setToChild o setToFirstExistingChild o setToLastExistingChild o setToNextExistingChild o setToParent o setToPreviousExistingChild o setToRoot ═══ 5.2.2.1. Constructor ═══ Cursor ( Tree const& tree ) ; Constructs the cursor and associates it with the given tree. The cursor is initially invalid. ═══ 5.2.2.2. isValid ═══ Boolean isValid ( ) ; Returns True if the cursor points to a node of the associated tree. ═══ 5.2.2.3. invalidate ═══ void invalidate ( ) ; Invalidates the cursor so that it no longer points to a node of the associated tree. ═══ 5.2.2.4. element ═══ Element const& element ( ) ; Returns a reference to the element of the associated tree to which the cursor points. Preconditions The cursor must point to a node of the associated tree. Exception ICursorInvalidException ═══ 5.2.2.5. operator!= ═══ Boolean operator!= ( Cursor const& cursor ) ; Returns True if the cursor does not point to the same node of the same tree as the given cursor. ═══ 5.2.2.6. operator== ═══ Boolean operator== ( Cursor const& cursor ) ; Returns True if the cursor points to the same node of the same tree as the given cursor. ═══ 5.2.2.7. setToChild ═══ Boolean setToChild ( IPosition position ) ; Sets the cursor to the child node with the given position. If the child does not exist, the cursor is invalidated. If the child at the given position exists, setToChild returns True. Preconditions o (1 =< position =< numberOfChildren) o The cursor must point to a node of the associated tree. Exceptions o IPositionInvalidException o ICursorInvalidException ═══ 5.2.2.8. setToFirstExistingChild ═══ Boolean setToFirstExistingChild ( ) ; Sets the cursor to the first existing child of the associated tree. If the node pointed to by the cursor has no children (that is, if the node is a leaf) the cursor is invalidated. If the node pointed to by the cursor has a child, setToFirstExistingChild returns True. ═══ 5.2.2.9. setToLastExistingChild ═══ Boolean setToLastExistingChild ( ) ; Sets the cursor to the last existing child of the associated tree. If the node pointed to by the cursor has no children (that is, if the node is a leaf) the cursor is invalidated. If the node pointed to by the cursor has a child, setToLastExistingChild returns True. ═══ 5.2.2.10. setToNextExistingChild ═══ Boolean setToNextExistingChild ( ) ; Sets the cursor to the next existing sibling of the node to which the cursor points. If the node to which the cursor points is the last child of its parent, no next existing child exists and the cursor is invalidated. Return Value Returns False if a next existing child exists. Preconditions The cursor must point to a node of the associated tree. Exception ICursorInvalidException ═══ 5.2.2.11. setToParent ═══ Boolean setToParent ( ) ; Sets the cursor to the parent of the node pointed to by the cursor. If the cursor points to the root, the node has no parent, and the cursor is invalidated. Return Value Returns True if the node has a parent. Preconditions The cursor must point to a node of the associated tree. Exception ICursorInvalidException ═══ 5.2.2.12. setToPreviousExistingChild ═══ Boolean setToPreviousExistingChild ( ) ; Sets the cursor to the previous existing sibling of the node to which the cursor points. If the node to which the cursor points is the last child of its parent, no more children exist and the cursor is invalidated. Return Value Returns True if there was a previous child. Precondition The cursor must point to a node of the associated tree. Exception ICursorInvalidException ═══ 5.2.2.13. setToRoot ═══ Boolean setToRoot ( ) ; Sets the cursor to the root of the associated tree. If the collection is empty (if no root element exists), the cursor is invalidated. Otherwise, setToRoot returns True. ═══ 5.3. Iterator and Constant Iterator Classes ═══ The classes IIterator and IConstantIterator define the interface for iterator objects. The redefinition of the function applyTo defines the actions that are performed with the allElementsDo. (See allElementsDo.) Iteration is terminated when applyTo returns False. Iteration Using Iterators explains the concepts and usage of iterations. ═══ 5.3.1. Declarations for Iterator and Constant Iterator ═══ template < class Element > class IIterator { public: virtual Boolean applyTo (Element&) = 0; }; template < class Element > class IConstantIterator { public: virtual Boolean applyTo (Element const&) = 0; }; ═══ 5.4. Pointer and Managed Pointer Classes ═══ These classes are declared in the header file iptr.h. The classes IPtr and IMgPtr implement C++ pointers for which element operations that are used by the collection classes, like element equality or comparison, are evaluated for the dereferenced pointers instead for the pointers themselves. This allows the use of a pointer to E as element type of a collection where E defines what equality or comparison mean. Managed pointers (IMgPtr) implement an automatic storage management mechanism that deletes the referenced object when no more managed pointers refer to it. Managed pointers are implemented using reference counting. Values and Objects and Automatic Storage Management explain the concepts and usage in detail. ═══ 5.4.1. Declarations for Pointer and Managed Pointer ═══ template < class Element > class IPtr { public: IPtr (); IPtr (Element *ptr); Element& operator * () const; Element* operator-> () const; friend inline Element& elementForOps (IPtr < Element >& ptr); friend inline Element const& elementForOps (IPtr < Element > const& ptr); }; template < class Element > class IMgPtr { public: IMgPtr (); IMgPtr (Element *ptr); IMgPtr (Element const& e); IMgPtr (IMgPtr < Element > const& ptr); ~IMgPtr (); IMgPtr < Element >& operator= (IMgPtr < Element > const& ptr); Element& operator * () const; Element* operator-> () const; friend inline Element& elementForOps (IMgPtr < Element >& ptr); friend inline Element const& elementForOps (IMgPtr < Element > const& ptr); }; ═══ 5.4.2. Public Member Functions for Pointer and Managed Pointer ═══ The following member functions are described: o Constructor o Constructor o Default Constructor o Destructor o operator* o operator-> o operator= ═══ 5.4.2.1. Constructor ═══ IPtr ( Element* element ) ; IMgPtr ( Element* element ) ; Constructs an IPtr or IMgPtr that refers to the element referred to by the given element pointer. ═══ 5.4.2.2. Copy Constructor ═══ IMgPtr ( Element const& element ) ; Constructs an IMgPtr that refers to a new object that is constructed from the given element. ═══ 5.4.2.3. Default Constructor ═══ IPtr ( ) ; IMgPtr ( ) ; Construct an IPtr or IMgPtr that refers to no object. ═══ 5.4.2.4. Destructor ═══ ~IMgPtr ( ) ; Deletes the object to which the IMgPtr refers, unless other IMgPtrs refer to this object. ═══ 5.4.2.5. operator* ═══ Element& operator* ( ) ; Returns a reference to the object to which the IPtr or IMgPtr refers. ═══ 5.4.2.6. operator-> ═══ Element* operator-> ( ) ; Returns a pointer to the object to which the IPtr or IMgPtr refers. ═══ 5.4.2.7. operator= ═══ operator= IMgPtr & operator= (IMgPtr const& ptr); Assigns the managed pointer to point to the object to which the given IMgPtr refers. ═══ 6. Reference Manual - Abstract Classes ═══ This part describes the abstract classes of the library. The following classes are described: o Collection o Equality collection o Key collection o Ordered collection o Sorted collection o Sequential collection o Equality key collection o Key sorted collection o Equality sorted collection o Equality key sorted collection ═══ 6.1. Collection ═══ Because collection is an abstract class, it cannot be used to create any objects. The following abstract classes are derived from collection: o Key collection o Equality collection o Ordered collection The concrete class Heap is defined by collection. The Abstract Class Hierarchy shows the relationship of collection to the class hierarchy. Collection is declared in the header file iacllct.h. ═══ 6.1.1. Declarations for Collection ═══ template < class Element > class IACollection { public: virtual ~IACollection (); virtual Boolean add (Element const&) = 0; virtual Boolean add (Element const&, ICursor&) = 0; virtual void addAllFrom (IACollection const&); virtual void copy (IACollection const&); virtual Element const& elementAt (ICursor const&) const = 0; virtual Element& elementAt (ICursor const&) = 0; virtual Element const& anyElement () const = 0; virtual void removeAt (ICursor const&) = 0; virtual INumber removeAll (Boolean (*property) (Element const&, void*), void* additionalArgument = 0) = 0; virtual void replaceAt (ICursor const&, Element const&) = 0; virtual void removeAll () = 0; virtual Boolean isBounded () const = 0; virtual INumber maxNumberOfElements() const = 0; virtual INumber numberOfElements () const = 0; virtual Boolean isEmpty () const = 0; virtual Boolean isFull () const = 0; virtual ICursor* newCursor () const = 0; virtual Boolean setToFirst (ICursor&) const = 0; virtual Boolean setToNext (ICursor&) const = 0; virtual Boolean allElementsDo (Boolean (*function) (Element&, void*), void* additionalArgument = 0) = 0; virtual Boolean allElementsDo (IIterator &) = 0; virtual Boolean allElementsDo (Boolean (*function) (Element const&, void*), void* additionalArgument = 0) const = 0; virtual Boolean allElementsDo (IConstantIterator &) const = 0; virtual Boolean isConsistent () const = 0; }; ═══ 6.2. Equality Collection ═══ Because equality collection is an abstract class, it cannot be used to create any objects. The equality collection inherits from collection. It defines the interfaces for the property of element equality. The following abstract classes are derived from equality collection: o Equality key collection o Equality sorted collection The following concrete classes are defined by equality collection: o Set o Bag o Equality Sequence The Abstract Class Hierarchy shows the relationship of equality collection to the whole class hierarchy. The equality collection class is declared in the header file iaequal.h. ═══ 6.2.1. Declarations for Equality Collection ═══ template < class Element > class IAEqualityCollection : public virtual IACollection < Element > { public: virtual Boolean contains (Element const&) const = 0; virtual Boolean containsAllFrom (IACollection const&) const; virtual Boolean locate (Element const&, ICursor&) const = 0; virtual Boolean locateOrAdd (Element const&) = 0; virtual Boolean locateOrAdd (Element const&, ICursor&) = 0; virtual Boolean remove (Element const&) = 0; virtual INumber numberOfOccurrences (Element const&) const = 0; virtual Boolean locateNext (Element const&, ICursor&) const = 0; virtual INumber removeAllOccurrences (Element const&) = 0; }; ═══ 6.3. Key Collection ═══ Because key collection is an abstract class, it cannot be used to create any objects. The key collection inherits from collection and defines the interfaces for the key property. The following abstract classes are derived from key collection: o Equality key collection o Key sorted collection The following concrete classes are defined by key collection: o Key set o Key bag The Abstract Class Hierarchy shows the relationship of key collection to the class hierarchy. The key collection class is declared in the header file iakey.h. ═══ 6.3.1. Declarations for Key Collection ═══ template < class Element, class Key > class IAKeyCollection : public virtual IACollection < Element > { public: virtual Key const& key (Element const&) const = 0; virtual Boolean containsElementWithKey (Key const&) const = 0; virtual Boolean containsAllKeysFrom (IACollection const&) const; virtual Boolean locateElementWithKey (Key const&, ICursor&) const = 0; virtual Boolean replaceElementWithKey (Element const&) = 0; virtual Boolean replaceElementWithKey (Element const&, ICursor&) = 0; virtual Boolean locateOrAddElementWithKey (Element const&) = 0; virtual Boolean locateOrAddElementWithKey (Element const&, ICursor&) = 0; virtual Boolean addOrReplaceElementWithKey (Element const&) = 0; virtual Boolean addOrReplaceElementWithKey (Element const&, ICursor&) = 0; virtual Boolean removeElementWithKey (Key const&) = 0; virtual Element const& elementWithKey (Key const&) const = 0; virtual Element& elementWithKey (Key const&) = 0; virtual INumber numberOfElementsWithKey (Key const&) const = 0; virtual Boolean locateNextElementWithKey (Key const&, ICursor&) const = 0; virtual INumber removeAllElementsWithKey (Key const&) = 0; virtual INumber numberOfDifferentKeys () const = 0; virtual Boolean setToNextWithDifferentKey (ICursor&) const = 0; }; ═══ 6.4. Ordered Collection ═══ Because ordered collection is an abstract class, it cannot be used to create any objects. The ordered collection inherits from collection and defines the interfaces for the property of ordered elements. The following abstract classes are derived from ordered collection: o Sorted collection o Sequential collection The Abstract Class Hierarchy shows the relationship of ordered collection to the whole class hierarchy. The ordered collection class is declared in the header file iaorder.h. ═══ 6.4.1. Declarations for Ordered Collection ═══ template < class Element > class IAOrderedCollection : public virtual IACollection < Element > { public: virtual void removeFirst () = 0; virtual void removeLast () = 0; virtual void removeAtPosition (IPosition) = 0; virtual Element const& firstElement () const = 0; virtual Element const& lastElement () const = 0; virtual Element const& elementAtPosition (IPosition) const = 0; virtual Boolean setToLast (ICursor&) const = 0; virtual Boolean setToPrevious (ICursor&) const = 0; virtual void setToPosition (IPosition, ICursor&) const = 0; virtual Boolean isFirst (ICursor const&) const = 0; virtual Boolean isLast (ICursor const&) const = 0; }; ═══ 6.5. Sorted Collection ═══ Because sorted collection is an abstract class, it cannot be used to create any objects. The sorted collection inherits from ordered collection and defines the interfaces for the properties of sorted elements. The following abstract classes are derived from sorted collection: o Equality sorted collection o Key sorted collection The Abstract Class Hierarchy shows the relationship of sorted collection to the class hierarchy. The sorted collection class is declared in the header file iasrt.h. ═══ 6.5.1. Declarations for Sorted Collection ═══ template < class Element > class IASortedCollection : public virtual IAOrderedCollection < Element > { public: }; ═══ 6.6. Sequential Collection ═══ Because sequential collection is an abstract class, it cannot be used to create any objects. The sequential collection inherits from ordered collection and defines the interfaces for the properties of ordered elements. The following concrete classes are defined by sequential collection: o Sequence o Equality sequence The Abstract Class Hierarchy shows the relationship of sequential collection to the class hierarchy. The sequential collection class is declared in the header file iasqntl.h. ═══ 6.6.1. Declarations for Sequential Collection ═══ template < class Element > class IASequentialCollection : public virtual IAOrderedCollection < Element > { public: virtual void addAsFirst (Element const&) = 0; virtual void addAsFirst (Element const&, ICursor&) = 0; virtual void addAsLast (Element const&) = 0; virtual void addAsLast (Element const&, ICursor&) = 0; virtual void addAsNext (Element const&, ICursor&) = 0; virtual void addAsPrevious (Element const&, ICursor&) = 0; virtual void addAtPosition (IPosition, Element const&) = 0; virtual void addAtPosition (IPosition, Element const&, ICursor&) = 0; virtual void sort (long (*comparisonFunction) (Element const&, Element const&)) = 0; }; ═══ 6.7. Equality Key Collection ═══ Because equality key collection is an abstract class, it cannot be used to create any objects. The equality key collection inherits from equality collection, and key collection. It defines the interfaces for the following properties: o Element equality o Key equality The equality key sorted collection abstract class is derived from equality key collection. The following concrete classes are defined by equality key collection: o Map o Relation The Abstract Class Hierarchy shows the relationship of equality key collection to the whole class hierarchy. The equality key collection class is declared in the header file iaeqey.h. ═══ 6.7.1. Declarations for Equality Key Collection ═══ template < class Element, class Key > class IAEqualityKeyCollection : public virtual IAEqualityCollection < Element >, public virtual IAKeyCollection < Element, Key > { public: }; ═══ 6.8. Key Sorted Collection ═══ Because key sorted collection is an abstract class, it cannot be used to create any objects. The key sorted collection inherits from sorted collection and key collection. It defines the interfaces for the following properties: o Key equality o Sorted elements The equality key sorted collection abstract class is derived from key sorted collection. The following concrete classes are defined by key sorted collection: o Key sorted set o Key sorted bag The Abstract Class Hierarchy shows the relationship of key sorted collection to the whole class hierarchy. The key sorted collection class is declared in the header file iaksrt.h. ═══ 6.8.1. Declarations for Key Sorted Collection ═══ template < class Element, class Key > class IAKeySortedCollection : public virtual IASortedCollection < Element >, public virtual IAKeyCollection < Element, Key > { public: }; ═══ 6.9. Equality Sorted Collection ═══ Because equality sorted collection is an abstract class, it cannot be used to create any objects. The equality sorted collection inherits from equality collection and sorted collection. It defines the interfaces for the following properties: o Element equality o Sorted elements The equality key sorted collection abstract class is derived from equality sorted collection. The following concrete classes are defined by equality sorted collection: o Sorted set o Sorted bag The Abstract Class Hierarchy shows the relationship of equality sorted collection to the whole class hierarchy. The equality sorted collection class is declared in the header file iaeqsrt.h. ═══ 6.9.1. Declarations for Equality Sorted Collection ═══ template < class Element > class IAEqualitySortedCollection : public virtual IAEqualityCollection < Element >, public virtual IASortedCollection < Element > { public: }; ═══ 6.10. Equality Key Sorted Collection ═══ Because equality key sorted collection is an abstract class, it cannot be used to create any objects. The equality key sorted collection inherits from equality key collection, key sorted collection, and equality sorted collection. It defines the interfaces for the following properties: o Element equality o Key equality o Sorted elements The following concrete classes are defined by equality key sorted collection: o Sorted map o Sorted relation The Abstract Class Hierarchy shows the relationship of equality key sorted collection to the whole class hierarchy. The equality key sorted collection class is declared in the header file iaeqksrt.h. ═══ 6.10.1. Declarations for Equality Key Sorted Collection ═══ template < class Element, class Key > class IAEqualityKeySortedCollection : public virtual IAEqualityKeyCollection < Element, Key >, public virtual IAEqualitySortedCollection < Element >, public virtual IAKeySortedCollection < Element, Key > { public: }; ═══ 7. Problem Determination ═══ This appendix helps you solve problems that you may encounter when you use the Collection Classes. The following table provides a short summary of each problem, and directs you to a section containing hints for a solution. ┌────────────────────────────────┬─────────────────────────────────────────────┐ │ PROBLEM AREA │ PROBLEM EFFECT │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Cursor Usage │ Unexpected results when using cursors │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Element Functions and Key │ Error messages indicating a problem in │ │ Functions │ istdops.h │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Key Access Function - How to │ Error messages indicating a problem in │ │ Return the Key (1) │ istdops.h: a local variable or compiler │ │ │ temporary is being used in a return │ │ │ expression │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Key Access Function - How to │ Unexpected results when adding an element │ │ Return the Key (2) │ to a unique key collection │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Definition of Key Functions │ Link step returns error message EDC3013 │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Exception Tracing │ Unexpected exception tracing output on │ │ │ standard error │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Declaration of Template Argu- │ Compiler messages (when templates are being │ │ ments and Element Functions │ processed) indicating that an element type │ │ (1) │ or one of its required element functions is │ │ │ not declared │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Declaration of Template Argu- │ Compilation errors from symbols being │ │ ments and Element Functions │ defined multiple times │ │ (2) │ │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Declaration of Template Argu- │ Link errors from symbols being defined mul- │ │ ments and Element Functions │ tiple times │ │ (3) │ │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Default Constructor │ Compiler error messages indicating a │ │ │ problem with constructors │ ├────────────────────────────────┼─────────────────────────────────────────────┤ │ Considerations when Linking │ Unresolved external references during │ │ with Templates │ linking │ └────────────────────────────────┴─────────────────────────────────────────────┘ ═══ 7.1. Cursor Usage ═══ Effect You get unexpected results when using cursors. For example, the elementAt function fails for the given cursor or returns an unexpected element. Reason You have used an undefined cursor. Cursors become undefined when an element is added to or removed from the collection. Solution Cursors that become undefined must be rebuilt with an appropriate operation (for example, locateElement) before they are used again. Rebuilding is especially important for removing all elements with a given property from a collection. Elements cannot be removed by coding a cursor iteration. Use the removeAll function that takes a predicate function as its argument. For more information about cursors, see Cursors and Removing Elements. ═══ 7.2. Element Functions and Key Functions ═══ Effect When compiled, your program causes a compiler error indicating a problem in istdops.h. The following are examples of such errors: Message if key is missing: j:\...\ibmclass\istdops.h(166:1) : (E) EDC3013: "key" is undefined. j:\...\ibmclass\istdops.h(160:1) : informational EDC3207: The previous message applies to the definition of template "IStdKeyOps::key(const Parcel&) const". Message if hash is missing: j:\...\ibmclass\istdops.h(152:1) : (E) EDC3070: Call does not match any argument list for "::hash". j:\...\ibmclass\istdops.h(146:1) : informational EDC3207: The previous message applies to the definition of template "IStdHshOps::hash(const ToyString&,unsigned long) const". Message if == is missing: j:\...\ibmclass\istdops.h(81:1) : (E) EDC3054: The "==" operator is not allowed between "const ToyString" and "const ToyString". j:\...\ibmclass\istdops.h(80:1) : informational EDC3207: The previous message applies to the definition of template "equal(const ToyString&,const ToyString&)". Message if < is missing: j:\...\ibmclass\istdops.h(105:1) : (E) EDC3054: The "<" operator is not allowed between "const ToyString" and "const ToString". j:\...\ibmclass\istdops.h(103:1) : informational EDC3206: The previous 2 messages apply to the definition of template "compare(const ToyString&,const ToyString&)". Reason Compiler error messages indicating a problem in istdops.h are always related to the element and key functions that you must define for your elements. These functions depend on the collection and implementation variant you are using. The compilation errors listed above occur when the key function, the hash function, the operator ==, or the operator < are required for your elements, but are defined with the wrong interface or not defined at all. Whether arguments are defined as const is significant. Compiler messages do not always point directly to the incorrect function. For example, a compare function with non-const arguments results in the compilation error: The "<" operator is not allowed between "const ..". Solution Verify which element and key functions are required for the implementation variant of the collection you are using. You can find this information for each collection in the section pertaining to the collection under the heading "Template Arguments and Required Functions". For more information about element and key functions, see Element Functions and Key Functions. Note that the same problem may be produced if function declarations and definitions are not properly separated between .h files and .cpp files. This situation is described in detail in Declaration of Template Arguments and Element Functions (1). ═══ 7.3. Key Access Function - How to Return the Key (1) ═══ Effect You get a compiler warning similar to: Message if key is passed by value: j:\...\ibmclass\istdops.h(166:1) : warning EDC3285: The address of a local variable or compiler temporary is being used in a return expression. j:\...\ibmclass\istdops.h(160:1) : informational EDC3207: The previous message applies to the definition of template "IStdKeyOps::key(const Word&) const". Reason Compiler error messages indicating a problem in istdops.h are always related to the element and key functions that you must define for your elements. These functions depend on the collection and implementation variant you are using. Your global name space function key returns the key by value instead of by reference. A temporary variable is created for the key within the operator-class function key. The operator class function key returns the key by reference. Returning a reference to a temporary variable causes unpredictable results. Solution Verify that the global name-space function key correctly returns a key const& instead of key. For more information on element and key functions, see Element Functions and Key Functions. ═══ 7.4. Key Access Function - How to Return the Key (2) ═══ Effect You are adding an element into a unique key collection such as a key set or a map, and you are sure that the collection does not yet contain an element with the same key. Nevertheless, you get unexpected results: IKeyAlreadyExistsException, or the element is not added and the cursor is positioned to a different element. Reason This problem has the same cause as the problem described in Key Access Function - How to Return the Key (1). However, you did not get the warning message described above, because you compiled with a lower warning level. Solution The solution for this problem is the same as described in Key Access Function - How to Return the Key (1). ═══ 7.5. Definition of Key Functions ═══ Effect You are using a collection class with a key and you get an error message during the link step indicating a problem in istdops.h. The following are examples of such errors: Message if key function is undefined istdops.h(176): (E) EDC3013: "key" function is undefined. Reason You are using a collection class that requires the element class to provide a key and you chose to use the method of using a global key function. You are using collection class methods in a .cpp file but the .h file with the same name as the .cpp file does not contain a declaration (prototype) of the global key function. While compiling the .cpp file, which uses methods of the collection class, the C++ compiler has created or modified a temporary .cpp file in the tempinc directory. During the link step, this .cpp file is compiled in order to resolve references to template code. The error message you encounter refers to this compilation. The .cpp file in the tempinc directory contains include directives for the collection class template code. It also contains include directives for a .h file of the same name as the .cpp file that uses the collection class methods. The template code in istdops.h requires that the global key function be known at compilation time. The only file that gets included at this time is the .h file with the same name as your .cpp file. The problem is that the .cpp file is not included at this time, so a definition or declaration of the global key function in this file is not recognized by the compiler. Solution You must declare the global key function in the .h file with the same name as the .cpp file that uses the collection class methods. The definition of the global key function should be in the .cpp file. If you are not sure which .h file is meant by the message, look in the .cpp file found in the tempinc directory. ═══ 7.6. Exception Tracing ═══ Effect You get unexpected exception tracing output on standard error even though the related exception causing the output is caught. Reason For each exception raised, the trace function write of class IException::TraceFn is called and writes information about the raised exception to standard error. This trace function write is called whether the related exception is caught or not. Solution To suppress the trace output, provide your own IException::TraceFn write tracing function by subclassing IException::TraceFn and register the subclass with setTraceFunction. For more information about exception tracing, see the User Interface Class Library Reference. ═══ 7.7. Declaration of Template Arguments and Element Functions (1) ═══ Effect You get compiler messages when processing templates indicating that an element type or one of its required element functions is not declared. Reason The element type or element function is defined locally to the .cpp file that contains the template instantiation with the element type as its argument. The pre-link phase is executed only by using the header files. Therefore, your declaration local to a .cpp file is not recognized and causes these compilation errors. Solution Move the corresponding declarations to a separate header file and include the header file from the .cpp file. ═══ 7.8. Declaration of Template Arguments and Element Functions (2) ═══ Effect You get compilation errors from symbols being defined multiple times. Reason The template instantiation needs to include the type declarations it received as arguments. Your header files containing type declarations used in template classes may automatically be included several times. Solution Protect your header files against multiple inclusion by using the following preprocessor macros at the beginning and end of your header files: #ifndef _MYHEADER_H_ #define _MYHEADER_H_ 1 . . . #endif Where _MYHEADER_H_ is a string, unique to each header file, representing the header file's name. ═══ 7.9. Declaration of Template Arguments and Element Functions (3) ═══ Effect You get link errors from symbols being defined multiple times. Reason The template instantiation needs to include the type declarations it received as arguments. Your header files containing type declarations used in template classes might automatically be included several times. Solution Verify that you did not define functions in the header files that declare types used in templates. If you did, you must move them from the header file into a separate .cpp file or make them inline. ═══ 7.10. Default Constructor ═══ Effect You get a compiler error similar to the following: Message for missing default constructor: itbseq.h(25:1) : (E) EDC3222: "IGTabularSequence >::Node" needs a constructor because class member "ivElement" needs a constructor initializer. Names namesOfExtinct(animals.numberOfDifferentKeys()); ANIMALS.C(55:57) : informational EDC3207: The previous message applies to the definition of template "ITabularSequence". Reason Compiler error messages indicating a problem with constructors for a collection are typically related to the constructors defined for your element. Here the default constructor for the element is missing. Solution Define the default constructor for the element class. For more information about element and key functions see Element Functions and Key Functions. The element and key functions required for each collection are listed for each collection type in sections entitled "Template Arguments and Required Functions". ═══ 7.11. Considerations when Linking with Templates ═══ Effect You get unresolved external references during linking that refer to symbols you cannot explain. Reason A possible reason for unresolved external references during linking is that template code cannot be correctly resolved. Solution 1. Use ICC for linking. ICC knows it has to process templates, LINK386 does not. 2. Use the -Tdp for linking. This tells ICC it is processing C++ code that might have templates, so ICC may have to process these templates. ═══ 8. Glossary ═══ ═══ 8.1. abstract class ═══ abstract class A class that allows polymorphism. There can be no objects of an abstract class; they are only used to derive new classes. ═══ 8.2. abstract data type ═══ abstract data type A mathematical model that includes a structure for storing data and operations that can be performed on that data. Common abstract data types include sets, trees, and heaps. ═══ 8.3. array implementation ═══ array implementation Implementation of an abstract data type using an array. Also called a tabular implementation. ═══ 8.4. automatic storage management ═══ automatic storage management The process that automatically allocates and deallocates objects in order to use memory efficiently. ═══ 8.5. auxiliary classes ═══ auxiliary classes Classes that support other classes. The auxiliary classes include classes for cursors, pointers and iterators. ═══ 8.6. AVL tree ═══ AVL tree A balanced binary search tree that does not allow the height of two siblings to differ by more than one. ═══ 8.7. bag ═══ bag An unordered flat collection that allows duplicate elements and has element equality. ═══ 8.8. base class ═══ base class A class from which other classes are derived. ═══ 8.9. based on ═══ based on The use of existing classes for implementing new classes. ═══ 8.10. bounded collection ═══ bounded collection A collection that has an upper limit on the number of elements it can contain. ═══ 8.11. B*-tree (B star tree) ═══ B*-tree (B star tree) A tree in which only the leaves contain whole elements. All other nodes contain keys. ═══ 8.12. child ═══ child A node that is subordinate to another node in a tree structure. Only the root node is not a child. ═══ 8.13. class ═══ class A user-defined data type that contains both data representations and functions. ═══ 8.14. class template ═══ class template A blueprint describing how a set of related classes can be constructed. ═══ 8.15. collection ═══ collection 1. An abstract class without any ordering, element properties, or key properties. All abstract classes are derived from collection. 2. In a general sense, an implementation of an abstract data type for storing elements. ═══ 8.16. concrete class ═══ concrete class A class that implements an abstract data type but does not allow polymorphism. ═══ 8.17. constructor ═══ constructor A member function that is used to construct class objects. The constructor function has the same name as the class. ═══ 8.18. containment function ═══ containment function A function that determines whether a collection contains a given element. ═══ 8.19. copy constructor ═══ copy constructor A constructor that copies a class object of the same class type. ═══ 8.20. cursor ═══ cursor A reference to an element at a specific position in a data structure. ═══ 8.21. cursor iteration ═══ cursor iteration The process of repeatedly moving the cursor to the next element in a collection until some condition is satisfied. ═══ 8.22. data member ═══ data member The smallest possible piece of complete data. Elements are composed of data members. ═══ 8.23. data structure ═══ data structure The internal data representation of an implementation. ═══ 8.24. data type ═══ data type A category that specifies the interpretation of a data object such as its mathematical qualities and internal representation. ═══ 8.25. default class ═══ default class A class with preprogrammed definitions that can be used for simple implementations. ═══ 8.26. default constructor ═══ default constructor A constructor that takes no arguments, or, if it takes arguments, all its arguments have default values. ═══ 8.27. default implementation ═══ default implementation One of several possible implementation variants offered as the default for a specific abstract data type. ═══ 8.28. default operation class ═══ default operation class A class with preprogrammed definitions for all required element and key operations for a particular implementation. ═══ 8.29. degree ═══ degree The number of children of a node. ═══ 8.30. deque ═══ deque A queue that can have elements added and removed at both ends. A double-ended queue. ═══ 8.31. dequeue ═══ dequeue An operation that removes the first element of a queue. ═══ 8.32. derived class ═══ derived class A class that inherits the properties of a base class. A derived has the data members and member functions of the base class but new data and operations can be defined. ═══ 8.33. destructor ═══ destructor A member function that destroys an object and frees up storage. The destructor of a class has the same name of the class preceded by a ~ (tilde). ═══ 8.34. difference ═══ difference Given two sets A and B, the difference (A-B) is the set of all elements contained in A but not in B.. For bags, there is an additional rule for duplicates: If bag P contains an element m times and bag Q contains the same element n times, then, if m>n, the difference contains that element m-n times. If m=