OS/2 Professional Developers Kit 1992 November/Disc01/Disc01.mdf/cppbeta/help/dde4ccl.in_/DDE4CCL.INF

OS/2 Help File | 1992-10-27 | 182.1 KB | 7,245 lines

ΓòÉΓòÉΓòÉ 1. Version Notice ΓòÉΓòÉΓòÉ

This document contains User's Guide and Reference Manual for the IBM Class
Library: Collection Classes

November 1992 - External Beta The main purpose of this driver of the IBM Class
Library: Collection Classes is to provide material that can be used in
conjunction with the external beta test driver of the Toronto OS/2 C++ compiler
package.

Current restrictions.  are described in a separate section.

A form for readers' comments is provided at the back of this publication. If
the form has been removed, address your comments to:

IBM Canada Ltd. Laboratory
Information Development
21/986/844/TOR
844 Don Mills Road
North York, Ontario, Canada. M3C 1V7

You can also send your comments by facsimile to [phone] addressed to the
attention of the RCF Coordinator. If you have access to Internet, you can send
your comments electronically to [e-mail]; IBMLINK, to
toribm(torrcf); IBM/PROFS, to torolab4(torrcf)

If you choose to respond through Internet, please include either your entire
Internet network address, or a postal address.

When you send information to IBM, you grant IBM a nonexclusive right to use or
distribute the information in any way it believes appropriate without incurring
any obligation to you.


ΓòÉΓòÉΓòÉ 1.1. 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 licensed program in this publication is not
intended to state or imply that only IBM's licensed program 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, except those expressly designated by IBM, is 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.


ΓòÉΓòÉΓòÉ 2. User's Guide ΓòÉΓòÉΓòÉ


ΓòÉΓòÉΓòÉ 2.1. Introduction ΓòÉΓòÉΓòÉ

This document contains the information required to use the IBM Class Library:
Collection Classes (or Collection Classes for short). The Collection Classes
are generic C++ classes designed to be used in system or application programs
written in the object-oriented language C++. Each Class implements an abstract
data type of the collection variety such as list, tree, or set.


ΓòÉΓòÉΓòÉ 2.1.1. Who Should Read This Document ΓòÉΓòÉΓòÉ

The User's Guide and Reference Manual is intended for C++ programmers and
program designers who wish to make use of one or more C++ BBs in developing an
application. As such, it presupposes some familiarity with C++ and, in
particular, with the C++ class concept.


ΓòÉΓòÉΓòÉ 2.1.2. How This Document Is Organized ΓòÉΓòÉΓòÉ

User's Guide contains the following chapters:

What the Library Offers introduces the motivation for having such a library.

Library Overview explains the general structure of the library.

Basic Concepts describes in detail the concepts and techniques used.

Reference Manual - Flat Collections contains an introductory chapter, which
includes a synopsis of all functions of the flat collections, and a chapter for
each class, which describes its semantics and interfaces in detail, including
coding examples.

subj='Tree Classes'.Reference Manual - Tree Classes is organized the same and
describes the tree classes.

subj='Auxiliary Classes'.Reference Manual - Auxiliary Classes describes a few
auxiliary classe.

subj='Abstract Classes'.Reference Manual - Abstract Classes describes the
abstract classes.


ΓòÉΓòÉΓòÉ 2.1.3. Related Documentation ΓòÉΓòÉΓòÉ

to be completed ....


ΓòÉΓòÉΓòÉ 2.1.4. Current restrictions ΓòÉΓòÉΓòÉ

Implementation Restrictions:

o Trees are not available
o IBounded is not implemented
o Multi level implementation chains (like set based on key sorted set based on
  linked sequence) lead to (mangled) names longer than 255 which are not
  accepted by the linker
o Diluted arrays and b*trees are not yet implemented


ΓòÉΓòÉΓòÉ 2.2. What the Library Offers ΓòÉΓòÉΓòÉ

The IBM Class Library: Collection Classes implements commonly used data
abstractions such as sets, maps, sequences, relations, trees, and stacks, in
the C++ programming language.

The major focus of the library design is on high performance. The library's
collection classes are designed to be not only for prototypes or smaller
applications, but also for production- quality high-performance systems. The
library achieves high-performance on two levels:

o By using appropriate C++ concepts for its implementation
o By providing you with a function for tailoring collection class
  implementations to the specific needs of your software system.

Although C++ is a high performance system programming language, several of the
programming techniques it enables can cause your programs to be inefficient.
For example, virtual functions can never be  inlined, and calling overhead may
increase as a result. Templates may cause large amounts of code to be generated
through template  instantiations. The library is designed to circumvent such
inefficiencies while still offering C++ benefits such as polymorphism and
strong typing.

Each data abstraction has several implementations. For example, you can
implement sets through hash tables, search trees, or sequences. Your choice of
implementation depends on the context in which you apply the data abstraction
Hash tables are a good solution, but if the maximum number of elements is known
in advance and if sets are often copied, binary search arrays may provide
superior performance. In other contexts, AVL trees may be the best solution.

Even within a given project context, you can often only decide on a concrete
implementation after you conduct prototyping experiments with the systems and
you gather initial figures about the usage of collection functions
Nonfunctional system requirements often change, especially when you are reusing
system components in other contexts. The ability to replace an implementation
that was well-suited to one context with one that is well-suited to a new
context is essential for system development, maintenance, and reuse. The
library therefore strictly distinguishes between abstract data types, such as
sets or sequences, and their concrete implementations, such as AVL trees, hash
tables, linked lists, or arrays.

The library incorporates a common interface for the abstract data types through
which the different concrete implementations can be accessed. The main
challenge in this approach is to avoid losing the capabilities of concrete
implementations by hiding them through an abstract interface. For example, you
can implement sequences without knowing whether they are implemented by linked
nodes or by arrays. The concept of cursors, however, which are an abstraction
of node pointers and array indices, retain the critical capabilities at the
abstract sequence interface.

The library enables you to choose the right data abstraction by providing
collection classes that are a complete, systematic, and consistent combination
of basic properties. These properties are explained in the following section.
Properties lead to questions you can ask and these questions lead you to select
the appropriate data type. These questions also prevent you from using data
types that are on a lower abstraction level than necessary. You may think of a
sorted tree when you only need a set (with fast element access) or you may
think of a sequence when you only need an unordered collection of elements.


ΓòÉΓòÉΓòÉ 2.3. Library Overview ΓòÉΓòÉΓòÉ

Instead of just providing common abstractions such as sets, maps, sorted
collections, and sequences, the library offers a systematic, orthogonal
framework of concepts that can be used to determine the data abstraction that
is needed in a given situation.

The framework does not include implementation decisions, such as the choice for
implementing a set through a hash table, an AVL tree, or a binary search array.
You should defer this decision until it can be made on a more solid basis.
However, you can use a basic understanding of the implementation choices to do
some early worst case performance analysis. Implementation issues are presented
in section Tailoring a Collection Implementation.

The main classes that the library provides are flat collections. There are also
trees and several auxiliary classes to handle garbage collection by reference
counting, or to build recursive collections:

Flat Collections.
          Flat collections are, for example, sequences, sets, bags or maps. As
          opposed to trees, graphs or recursive collections there is no
          hierarchy of elements or recursive structure of collections.

          Flat collections and their properties are described in detail in Flat
          Collections.

Flat Collections with Restricted Access
          Restricted access collections are, for example, stacks or priority
          queues. They are based on flat collections and restrict the set of
          applicable functions.

          You will find more information in Flat Collection with Restricted
          Access.

Trees
          Trees are not flat. They can be described either as a structure where
          their elements have a hierarchy or as a special form of recursive
          structures. I.e. a tree can be recursively described as a node with
          references to other nodes.

          The library offers two kinds of trees:

    1. binary trees

    2. n-ary trees Please refer to Binary Tree and N-ary Tree for a full
          explanation.

Auxiliary Classes
          In order to use the collection classes you need also a cursor and an
          iterator class.

          Both are further described in Cursors and Using Iterators.

          The reference classes provides the means to manage objects and
          garbage collection.

          Values vs. (Managed) Objects and Garbage Collection explain the
          concepts and usage in detail.

A general property of the library's collection classes is that all collections
are implemented without structure sharing. This means that a collection
referred to by variable A cannot be part of another collection referred to by
variable B. This prevents changes performed on B from having side effects on A
and vice versa. Such side effects complicate program understanding and
validation and should in general be avoided. You can still use C++ references
or pointers to share whole collection objects or pass them as arguments.


ΓòÉΓòÉΓòÉ 2.3.1. Flat Collections ΓòÉΓòÉΓòÉ

There are four basic properties that are used to describe the characteristics
of flat collections:

Ordering
          is there a next or previous relationship between the elements.

Availability of equality for elements
          is the value of the whole element relevant.

Access by key
          is the value of a part of the element (a key) relevant.

Uniqueness of entries.
          are the only unique or multiple occurrences of the same element
          allowed.
The properties for flat collections are summarized in "Figure: Combination of
collection properties". Subsequent sections describe them in more detail.


Combination of collection properties


ΓòÉΓòÉΓòÉ 2.3.1.1. Ordering of Collection Elements ΓòÉΓòÉΓòÉ

There are three kinds of orderings:

o Unordered collections have no ordering of their elements at all.
o Sorted collections have their elements sorted by an ordering relation defined
  for the element type. For example integers can be sorted ascending or strings
  alphabetically The ordering relation is determined by instantiating the
  collection class.
o Sequential collections have their ordering determined by an explicit
  qualifier to the Add function, for example AddAsFirst.

While sorted collections allow fast element access through the ordering
relation, unordered collections may be implemented in a way that also allows
fast access to the elements, for example by using a hash table or a sorted
representation. A fast locate function which can make use of this structure is
provided for unordered and sorted collections. Even though unordered
collections are often implemented by sorting the elements, you should never
make this (implicit) assumption for an unordered collection. For each of the
following collection categories, the library provides both unordered and sorted
abstractions, such as sets and sorted sets, so the choice for unordered or
sorted is independent of other selection criteria.


ΓòÉΓòÉΓòÉ 2.3.1.2. Elements, Keys and Equality ΓòÉΓòÉΓòÉ

The collection structure may depend on an ordering relation, or a hash function
that is defined on the element type itself, or it may be defined on a key of
the element. A key is usually a data member of the element but can be some
arbitrary function from the element type to some given key type.

Equality or ordering for the key type may be different from equality or
ordering for the element type. 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 a fast access
via the task ID and no (particular) access via the priority; in the second case
you have fast access via the priority but not via the task ID. The ordering
relation on the priority key in the second case is not compatible with the task
equality, since two tasks can have equal priorities without being equal.

These considerations show that equality for the element and equality/ordering
for the key must be distinguished. For collections with key, equality must
always be provided for at least the key type. Functions like
locateElementWithKey use this key equality for locating elements. Element
equality may optionally be provided, in addition to key equality. Functions
that are based on equality (such as locate) are only provided for collections
that have an element equality defined. Non-equality, non-key collections (Heaps
and Sequences) provide no functions for locating elements by their values or
testing for containment. They are containers which elements can be added to and
retrieved from by iteration or, for Sequences, by position.

For sorted collections without a key there is always an ordering relation for
the element type This relation implicitly defines element equality. Sorted
collections with no key and no element equality do not make sense.

In addition to acting as a 'carrier' for structuring information, the key
concept is mainly used for accessing an element by providing its key as
argument to functions such as elementWithKey. The alternative to defining
equality of elements as equality of their keys (in the task 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:

  TaskId const& key (Task const& t) {return t.id;}
  KeySet < Task, int > tasks;
  ...
  tasks.locateElementWithKey (1);
and

  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) is not free.

The library offers the abstractions of (possibly sorted) Maps and Relations
where both key and element equality must be provided. These abstractions are
similar to KeySets and KeyBags but, in addition, the functions based on element
equality are defined in particular, union and intersection. Furthermore, the
add function behaves differently toward the corresponding classes without
element equality with respect to uniqueness of elements. This is discussed in
the following section.

In mathematics, maps and relations are mostly defined as sets of pairs of
components: a key component and an information component. Maps and Relations as
the library defines them do not make the pairing explicit; they expect the
element type to be the pair, with the key given by some access function.
Pairing can easily be put on top of this implementation but a given
key/information pair type on top of a map that requires the two components to
be separated is not possible.


ΓòÉΓòÉΓòÉ 2.3.1.3. Unique vs. Multiple Occurrences ΓòÉΓòÉΓòÉ

The same element or key may be added several times to the same collection. If
the programmer is interested in the number of occurrences of the element, an
element can be added once or multiple times. According to this distinction we
say that collections have unique or multiple elements or keys.

For collections with a key uniqueness is always with respect to the key (this
means uniqueness for the element, because unequal keys mean unequal elements).
For non-unique collections with key and element equality (Relations), elements
are always unique (while keys can occur multiple times). A collection with
multiple elements and keys together with element equality is not provided; the
corresponding collection without element equality may be used instead, but the
element dependent functions (such as remove) must be implemented by the
programmer, for example, by iterating over the elements associated with the
given key. For collections without key and with no element equality there is no
unique variant because containment is not defined.

Unique and multiple collections are established by defining the behavior of the
add function, according to whether it adds the element or not. The add function
has, in general, two properties:

o All elements that have been contained in the collection before will be
  contained afterwards
o The given element will be contained afterwards.
This property could not be fulfilled for Map, if an element is added to that
which another element with the same key is already contained. In this case, an
exception will be thrown. For KeySet which does not know about element
equality, the element is not added if an element with the same key already
exists. This may violate the condition stated before, that element equality is
different from key equality for a KeySet; the alternative to always raising an
exception would, however, be less desirable. There are the functions
locateOrAddElementWithKey and addOrReplaceElementWithKey which explicitly state
what shall happen in case an element with the same key is already contained in
the collection.

"Figure: Behavior of add for unique and multiple collections" illustrates the
concept of keys, element equality and uniqueness. Consider elements which are
pairs of integers, the first being the key. Element equality, if defined, is
equality of both integers. Adding the following (pair-)elements will yield the
corresponding results so the ordering of the elements is irrelevant.

ΓöîΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÉ
Γöé add        Γöé Map        Γöé Relation   Γöé KeySet     Γöé KeyBag     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé <1,1>      Γöé <1,1>      Γöé <1,1>      Γöé <1,1>      Γöé <1,1>      Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé <2,1>      Γöé <1,1>,     Γöé <1,1>,     Γöé <1,1>,     Γöé <1,1>,     Γöé
Γöé            Γöé <2,1>      Γöé <2,1>      Γöé <2,1>      Γöé <2,1>      Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé <1,1>      Γöé <1,1>,     Γöé <1,1>,     Γöé <1,1>,     Γöé <1,1>,     Γöé
Γöé            Γöé <2,1>      Γöé <2,1>      Γöé <2,1>      Γöé <2,1>,     Γöé
Γöé            Γöé            Γöé            Γöé            Γöé <1,1>      Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé <1,2>      Γöé exception: Γöé <1,1>,     Γöé <1,1>,     Γöé <1,1>,     Γöé
Γöé            Γöé KeyAlreadyEΓöéi<2,1>,     Γöé <2,1>      Γöé <2,1>,     Γöé
Γöé            Γöé            Γöé <1,2>      Γöé            Γöé <1,1>,     Γöé
Γöé            Γöé            Γöé            Γöé            Γöé <1,2>      Γöé
ΓööΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÿ

Behavior of add for unique and multiple collections


ΓòÉΓòÉΓòÉ 2.3.2. Flat Collection with Restricted Access ΓòÉΓòÉΓòÉ

Restricted access collections are, for example, stacks or priority queues. They
are based on flat collections and restrict the set of applicable functions.
These restrictions are present for two reasons:

 1. They allow certain assumptions to be made when validating and inspecting
    the code; a stack, for example, does not allow the removal of any element
    except the top one.
 2. Functionality restrictions open up new implementation alternatives. With
    stacks, for example, a linked implementation that shares common front nodes
    is possible, whereas sequence functions that change other than the top
    element prohibit this implementation.
Currently you will find restricted access classes for sequences and key sorted
bags:

o Stacks, deques and queues are all based on sequence.
o Priority Queues are based on key sorted bags.


ΓòÉΓòÉΓòÉ 2.3.3. Trees ΓòÉΓòÉΓòÉ

Trees are not flat. They can be described either as a structure where their
elements have a hierarchy or as a special form of recursive structures. I.e. a
tree can be recursively described as a node with references to other nodes.

The library offers two kinds of trees:

 1. binary trees

 2. n-ary trees
Please refer to Binary Tree and N-ary Tree for a full explanation.


ΓòÉΓòÉΓòÉ 2.3.4. Auxilitary Classes ΓòÉΓòÉΓòÉ

In order to use the collection classes you need also a cursor and an iterator
class.

They are further described in Cursors and Using Iterators.

The reference classes provides the means to manage objects and garbage
collection.

Values vs. (Managed) Objects and hdref refid=garb. explain the concepts and
usage in detail.


ΓòÉΓòÉΓòÉ 2.3.5. The Overall Implementation Structure ΓòÉΓòÉΓòÉ

It is a major design issue of the library, to achieve maximum efficiency
together with ease of use. This goal has lead to a class structure that
combines the common features of object-orientation, such as class hierarchies,
polymorphism and late binding, with a more efficiency-oriented class structure
using inline functions. This section gives a brief overview of the library
structure which is sketched in "Figure: Overall library structure". A more
detailed explanation of the particular concepts is found in subsequent
sections.

You do not have to understand the whole implementation structure right from the
start. There are three levels of complexity that you can approach step by step:

use the defaults only
          in this case you only worry about the default classes.

use different implementations
          using techniques that are described in Tailoring a Collection
          Implementation you use the concrete classes to replace the default
          implementation.

make use of polymorphism
          abstract classes and reference classes provide the means for that.
The categories of classes are shown in "Figure: Overall library structure". and
are introduced briefly below.


Overall library structure

Default Classes
          The easiest way to use the library's collection classes is through
          the provided default classes. Two default classes are provided for
          each data abstraction, one that is instantiated only with the element
          (and possibly key) type (ISet), and one that, in addition, takes
          element specific functions (IGSet, see section Defining Element
          Functions).

Concrete Classes
          For each abstraction there exist several concrete representations;
          sets may, for example, be implemented based on sorted maps or on hash
          tables, or sorted maps may be implemented on AVL trees or on
          sequences. Concrete classes are grouped according to the data
          abstraction which they implement. They all have the same interface.

          Based on relationships in "Figure: Overall library structure"
          indicate that the based class is a template that needs to be
          instantiated with a class that implements the interface of the
          class(es) to which the arrow points. This mechanism is used for
          reference classes and for concrete implementations that are based on
          other classes. Names of concrete classes based on other concrete
          classes start with IW, for example IWSetOnSortedMap. These classes
          are instantiated to compose a specific implementation, such as a set
          being based on a sorted map again being based on a sequence. This
          mechanism is further explained in section Tailoring a Collection
          Implementation.

Abstract Classes
          Object-orientation ordinarily represents this grouping by a class
          hierarchy. The library defines this hierarchy by the abstract
          classes. Names of abstract classes start with IA. The leaves of the
          abstract class hierarchy define the data abstractions for which
          concrete implementations are provided. The full abstract class
          hierarchy is shown in "Figure: The abstract class hierarchy".


                    The abstract class hierarchy

Reference Classes
          The concrete classes are not derived from the abstract classes
          because this would cause inevitable virtual function call overhead
          (see footnote  (**) in section Introduction). Programmers who do not
          want to make use of the polymorphism for collections, do not want to
          pay the function call penalty. Abstract and concrete classes are
          linked through so-called reference classes. These classes are derived
          from the abstract classes and implement the functions based on a
          given, corresponding concrete class. Names of reference classes start
          with IR. This mechanism is further described in section Polymorphic
          Use of Collections.

Implementation Classes
          Implementation classes are used for handling the problem of
          (unnecessary) code expansion (see footnote  (**) in section
          Introduction). They provide an untyped (void*) interface which is
          used by the concrete class implementations. Programmers will never
          use the implementation classes directly.


ΓòÉΓòÉΓòÉ 2.4. Basic Concepts ΓòÉΓòÉΓòÉ


ΓòÉΓòÉΓòÉ 2.4.1. Instantiating and Using the Collection Classes ΓòÉΓòÉΓòÉ

Using a collection class generally proceeds in three steps:

 1. Instantiating a collection class template, and providing arguments for the
    formal template arguments

 2. Defining one or more objects of this instantiated class, possibly providing
    constructor argument(s)

 3. Applying functions to these objects.

Section The Based-On Concept will introduce another step before class
instantiation, namely the composition of several class templates to a new one
(for example, implementing a set based on a sorted collection which is again
based on a sequence for which, finally, a tabular sequence implementation is
chosen). For each abstraction there is at least one predefined, default
implementation choice.


ΓòÉΓòÉΓòÉ 2.4.1.1. Instantiation and Object Definition ΓòÉΓòÉΓòÉ

This section describes instantiation for the default implementation. For a
given class, say ISet, and a given element type, say Task, an instantiation for
a new class that represents sets of tasks is written as:

   typedef ISet < Task > TaskSet;
or

   class TaskSet : public ISet < Task > {
   public:
     TaskSet (INumber n = 100) : ISet < Task > (n) {}
   }
The second form defines a new class type which is upward, but not downward
compatible with ISet < Task >, and does not inherit any constructor with
default arguments, which would have to be redefined as shown. The first form
introduces a shorthand for this name.

Objects, such as toBeDone, pending, and delayed of this class can now be
defined by:

   TaskSet toBeDone, pending, delayed;

Both steps might technically also have to be done in one:

   ISet < Task > toBeDone, pending, delayed;
It is recommended to explicitly define or derive a named class which is used
for the intended purpose (here, sets of tasks) and which can later on be
redefined using an implementation more suitable than the default (see Tailoring
a Collection Implementation).


ΓòÉΓòÉΓòÉ 2.4.1.2. Bounded and Unbounded Collections ΓòÉΓòÉΓòÉ

If a collection is bounded it can contain a certain maximum number of elements.
This decision can be made independent of the choice of collection
implementation; all implementations allow an arbitrary number of elements
(until the memory is exceeded) which may, involve restructuring or reallocation
of space.

A collection should only be made bounded if the number of elements is bounded
by some other criterion. Sets, for example, may be bounded by a known number of
elements that are in the set; a set of states may be bounded by the number of
different states. It is generally not a good idea to impose a size restriction
by choosing an upper bound for the size of a collection.

The primary collection constructor has two arguments: the number of elements
and an indication of whether the collection shall be bounded or unbounded.

   enum IBoundIndicator {IBounded, IUnbounded};
   ...
   class <AnyCollection> {
     ...
     <AnyCollection> (INumber = 100, IBoundIndicator = IUnbounded);
   };

If the BoundIndicator is IUnbounded the number specifies an estimate for the
number of elements in the collection which is not upper bound. If the
BoundIndicator is IBounded the number specifies an upper bound for the number
of elements in the collection. If this bound is exceeded, the exception
IFullException will be raised. The function isFull can be used to check (in
advance) whether the collection is full.

The function isBounded can be used to test whether a collection is bounded and,
if it is, the function maxNumberOfElements tells its maximum element number.


ΓòÉΓòÉΓòÉ 2.4.1.3. Adding, Removing, and Replacing Elements ΓòÉΓòÉΓòÉ

The main functions for constructing collections are (different variations of)
add, remove, and replace.

The function add adds the given element to the collection. According to the
collection properties this function behaves differently for different
collections: with unique collections the element is not added if it is already
contained; for sorted collections it is added according to its ordering
relation; for sequential collections, it is added last. A general rule for the
behavior of add is that iterating over a given collection and adding each
element to a new collection that is initially empty yields a copy of the given
collection in the new collection. In particular, for a sequential collection
add must add the element as last, because iteration iterates from the first
towards the last element.

For sequential collections, elements can be added at a given position. Elements
before and including this position will be 'shifted'. Positions can be
specified by a number, where counting starts with 1 for the first element, or
relative to some other element occurrence (asNext, asPrevious), or relative to
the collection (asFirst, asLast).

Removal of an element can in general be done for the element occurrence
referred to by a given cursor (see section Cursors). All other removal
functions can be reduced to this function by 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 non-unique collections, occur
more than once. The basic remove function always removes only one occurrence of
an element.

For collections with keys or element equality, there are removal functions that
remove one or all occurrence(s) of a given key or element, ( remove,
removeElementWithKey, removeAllOccurrences, and removeAllElementsWithKey).
Ordered (sorted as well as sequential) collections provide functions for
removing an element at a given position given by a number or as First or Last.

After an element has been added or removed, all cursors of the collection
become undefined (see section Cursors). Therefore, removing all elements with a
given property from a collection cannot be done efficiently, because after
removing one element with the property, the collection would have to be
searched 'from the beginning' for the next element with the property. For this
purpose, the function removeAll (predicate) is provided. Predicate is a
function that, for a given element and an optional additional argument, returns
a boolean result, indicating whether the element shall be removed or not. The
following example removes all even elements from an integer collection:

  Boolean isEven (int const& i, void*)
  { return i % 2 == 0;
  }
  ...
    intSet.removeAll (isEven);
The purpose and usage of the additional argument will be explained in section
Using Iterators.

Collections can be modified by replacing the value of an element occurrence.
Adding and removing elements usually involves the creation or deletion of
'nodes' or the shifting of elements within a tabular implementation, replacing
an element leaves the internal representation of collections unchanged.
Therefore, cursors of the collection do not become undefined.

For collections that are organized according to some 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 old key; for non-key collections with element equality the new element must
be equal to the old element, both as defined by the equality or comparison
function provided for the key or element type, respectively. This key or
element value is called the positioning property of the element with respect to
the given collection type. As an alternative to replacing the value of an
element occurrence you can remove the old and add the new element value; this
must be done if the element's positioning property is being changed. For
sequential collections and heaps, there is no such property; element values in
sequences and heaps can be changed freely. Replacing element values involves
copying of 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 that is
described in section Locating and Accessing Elements. While the replace
function checks the validity of the position property as a precondition, the
elementAt function leaves this responsibility to the programmer.


ΓòÉΓòÉΓòÉ 2.4.1.4. Cursors ΓòÉΓòÉΓòÉ

A cursor  is a handle to an element in a collection. It is used for several
purposes, for example to access the result of the locate function, and to
indicate the current working point for iterating over the elements of a
collection. A cursor is always associated with a collection. The collection is
specified at construction time and can not be changed later on. The association
of the collection to the cursor is used for two reasons:

o Simple functions, in particular advancing the cursor, can be functions of the
  cursor instead of being collection functions that take the cursor as an
  argument.
o Collections that take a cursor argument can have as a precondition, that the
  cursor actually belongs to this collection; the association of the collection
  to the cursor makes the check effectively executable. Errors of using a
  cursor with a collection to which it does not belong and for which it might
  not work as expected, are otherwise hard to detect.

Cursors are only temporarily defined: as soon as elements are being added to,
or removed from the collection, existing cursors are no longer defined.
Remember that cursors can be implemented as C++ pointers (to nodes that carry
the elements) in case of implementations that are called linked or as indices
to an array in case of implementations that are called tabular. For tabular
implementations, cursors may no longer refer to the original element occurrence
if this element is shifted with adding or removing. For this reason, if you
wish to leave the choice for a linked and a tabular implementation open, you
should not make use of a cursor after elements have been added to, or removed
from the corresponding collection. The reference manual states that, for such
functions all cursors will be undefined. If you restrict yourself to linked
implementations, this decision must be specified (documented by a comment) with
the class instantiation, so that:

o All who use the collection class know whether they may assume this property
  or not.

o Tailoring only chooses appropriate implementations.

Cursors and iteration by cursors can be used with any collection. This
provides:

o An iteration scheme that is simpler than using iterators (see Using
  Iterators).
o The ability to define functions that have cursors as output argument and
  thereby either grant fast access to an element if it exists, or indicate the
  non-existence by an invalid cursor.

Different collection implementations use different cursor classes; linked
implementations use pointers to nodes; array implementations use numeric
indices; hash tables use an index into the hash table and a pointer to the node
in the collision list; bags based on dictionaries use the dictionary cursor and
a count for equal elements.

Each concrete collection class, for example C, has an inner definition of a
class Cursor which can be accessed as C::Cursor.

Since abstract classes will 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, there is a virtual member
function newCursor for all abstract collection classes, creating an appropriate
cursor for the given collection object.


ΓòÉΓòÉΓòÉ 2.4.1.5. Locating and Accessing Elements ΓòÉΓòÉΓòÉ

Cursors provide a basic mechanism for accessing elements; all other access
mechanism can be reduced to first finding an appropriate cursor and then
accessing the element via this cursor. Two functions are provided for accessing
an element through a cursor:

  const Element& elementAt (Cursor const&) const;
        Element& elementAt (Cursor const&);
which return a reference to an element and thereby avoid the actual element
copying within the function. Assume an element with a size of some KBytes and a
situation where you want to access a 2 Byte data member of an element pointed
to by a given cursor; you would not want to copy the element to some local
variable and then access the data member but instead, use a pointer or
reference to the element.

There are several other functions, such as firstElement, or elementWithKey that
yield 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 via the cursor. It is necessary to assert the
existence of the element before accessing it. If this is not known from the
context it must first be checked; in order to save the extra effort of locating
the desired element twice (once for checking whether it exists and then for
actually retrieving its reference), the cursor that results from the locate
function can be used for fast element access like this:

  if (locateElementWithKey (key, cursor))
    ... elementAt (cursor) ...

The elementAt function can also be used to replace the value of the referenced
element occurrence. The programmer is responsible for not changing the
positioning property of the element (with respect to the given collection; see
section Adding, Removing, and Replacing Elements).

  class Task
  { ...
    TaskId ivId;
    State ivState;
    ...
  };
  ...
  elementWithKey (tid).ivState = RUNNING;

The distinction of a constant and a non-constant elementAt function guarantees
that for a constant collection no elements can be changed via this function;
still, the constant function can be used (that means it is automatically
selected by the compiler) to gain read access to the element.


ΓòÉΓòÉΓòÉ 2.4.1.6. Iterating over Collections ΓòÉΓòÉΓòÉ

Iterating over all or some elements of a collection is a common pattern. The
library provides two iteration concepts: iteration by cursors and iteration 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 will be visited. However, it is guaranteed that each element will be
visited exactly once.

While iterating over a collection no elements may be added to or removed from
the collection. Otherwise it is not guaranteed that all elements will be
visited once. Cursor iteration can be used to relax this rule in order to
iteratively remove all elements from the collection that have a certain
property.


Cursor Iteration

Cursor iteration can be done with a for loop, for example:

  XYCollection collection;
  XYCollection::Cursor current (collection);
  for (current.setToFirst (); current.isValid (); current.setToNext ())
  { ... collection.elementAt (current) ...
  }

One of the challenges with iteration is the removal of elements while
iterating; removing or adding elements changes the collections and implicitly
makes all cursors to the collection undefined. One could not 'remember' the
cursor of the next element, remove the current, and then proceed iteration with
the remembered cursor (think of array implementations). Therefore, the remove
function that gets as an argument a cursor pointing to the element that is to
be removed, also sets this cursor to the next element. So, an iteration
removing all elements with a certain property from an arbitrary collection
could work as follows:

  Cursor current (collection);
  for (current.setToFirst (); current.isValid ();)
  { ...
    if (... collection.elementAt (current) ...)
      collection.removeAt (current);
    else
      current.setToNext ();
  }

Using Iterators

Cursor iteration may have two 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 as with
  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 library provides the functions allElementsDo which address both drawbacks
by taking a function that is applied to all elements. The function returns a
boolean value which 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 applied in each iteration step can be given in two ways: as a C++
function, or as an object of a so-called iterator class. The advantage of the
iterator class is that additional arguments that are needed by the iteration
function can be better encapsulated. The C++ function has an additional
argument which may be used for this purpose. In addition, for both of these
possibilities, it is distinguished whether the function leaves the element
constant or not. This gives the following four cases:

   template < class Element >
   class IIterator {
   public:
     virtual Boolean applyTo (Element&) = 0;
   };

   template < class Element >
   class IConstantIterator {
   public:
     virtual Boolean applyTo (Element const&) = 0;
   };

   template < class Element, ... >
   class <AnyCollection> {
     ...
     Boolean allElementsDo (Boolean (*) (Element&, void*),
                            void*);
     Boolean allElementsDo (Boolean (*) (Element const&, void*),
                            void*) const;
     Boolean allElementsDo (IIterator < Element >);
     Boolean allElementsDo (IConstantIterator < Element >);
   }

Using the iterator class, the programmer derives the class IIterator or
IContsantIterator, respectively, and defines the applyTo function for the
derived class. Additional arguments needed for the iteration can, for example,
be passed as constructor arguments of the derived iterator class. The
programmer defines the function with the given argument and result types. For
additional arguments it might be necessary to define a separate class or
structure. The following example adds all integers in a set, showing the usage
of both mechanisms in the case of additional arguments required.

   typedef ISet < int > IntSet;

   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 sumUsingIterator (ISet const& set) {
     SumIterator sumUp;
     set.allElementsDo (sumUp);
     return sumUp.sum ();
   }

   Boolean sumUpFunction (int &const i, void* sum) {
     *(int*)sum += i;
     return True;
   };

   int sumUsingFunction (ISet const& set) {
     int sum = 0;
     set.allElementsDo (sumUpFunction, &sum);
     sum;
   }


ΓòÉΓòÉΓòÉ 2.4.1.7. Copying and Referencing Collections ΓòÉΓòÉΓòÉ

As mentioned in section Flat Collections, the library's collections implement
no structure sharing. 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. This should be noted when using collection
types as arguments to functions: If the argument type is not a reference or
pointer type, the collection will be copied and, in particular, changes made to
the collection within the function will not 'write through' to the actual
argument; in most cases collections should therefore be passed by reference:

   void removePrimes (ISet < int > set) { ... // wrong!
   void removePrimes (ISet < int >& set) { ... // right
For the same reason it is not advisable to have collection types being result
types of functions. For example:

   ISet < int > f () {
      ISet < int > result;
      ...
      result result;
   }
   ...
   intSet = f ();
In this program the situation would be worse: the result of f would be copied
in a temporary which would be taken as (reference) argument to the assignment
operation which would again copy the set. The above program should therefore
look like this:

   void f (ISet < int > &result) {
      ...
   }
   ...
   f (intSet);

The rationale for using collection types as argument rather than result types
will be discussed in section Polymorphic Use of Collections.


ΓòÉΓòÉΓòÉ 2.4.2. Exception Handling ΓòÉΓòÉΓòÉ

The C++ exception handling mechanism enables a program to recover from an
'exceptional' situation. An exceptional situation occurs within a function
which the programmer did not or could not explicitly consider when writing a
call to this function.

There is some ambiguity in the notion of exceptional and it is left to the
design of a class interface to define which situations are considered
exceptional and which are considered regular.

Exceptional situations can result from two major sources:

o The violation of a precondition

o The occurrence of an internal system failure or system restriction.

A precondition of a function is a condition that the function requires to be
true when being called. It is the caller's responsibility to assure this
condition. The function implementation may assert that the condition holds
without further checking it; in the case of a precondition violation, the
function may behave in an arbitrarily negative manner, for example, overwriting
foreign storage areas.

In order to make programs more robust and to locate errors in the test phase,
preconditions must be checked by the function. Since this checking may require
significant overhead, it is helpful to turn it off after the system has been
tested or even systematically verified with respect to the preconditions. The
programmer does not 'expect' a function call to violate the function's
precondition, so this is a typically exceptional situation. In the checked
case, the function would throw an exception in case of a violated precondition;
in the unchecked case, the behavior would be unpredictable.

System failures and restrictions are different from preconditions. They are
usually not anticipated by the programmer and are therefore exceptional.
However, the programmer has no chance of verifying that such a situation, like
storage overflow, does not occur. These exceptions should therefore be checked
for and thrown as an exception if they occur.


ΓòÉΓòÉΓòÉ 2.4.2.1. Precondition vs. Defined Behavior ΓòÉΓòÉΓòÉ

Exceptions are not generally used for 'regular' programming. For example, the
exit from an iteration through a collection should not be implemented using an
exception which is raised when accessing elements through an invalid cursor. It
should, explicitly test for the cursor being valid.  In order to make this
possible, there must be a function that efficiently tests this condition.

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 and
return the condition as a boolean result. Consider a function that first tests
whether an element exists with a given key and, if so, accesses it, for
example:

   if (c.containsElementWithKey (key)) {
     ...
     ... c.elementWithKey (key) ...
     ...
   } else {
     <else-part>
   }
This solution is inefficient because it does the locating twice. Consider the
following example:

   try {
     ...
     ... c.elementWithKey (key) ...
     ...
   } catch (INotContainsKeyException) {
     <else-part>
   }
This solution is undesirable because it violates the mentioned programming
practice. The correct solution is to first obtain a cursor together with the
containment test, and then use the cursor for a fast element access:

   if (c.locateElementWithKey (key, cursor)) {
     ...
     ... elementAt (cursor) ...
     ...
   } else {
     <else-part>
   }


ΓòÉΓòÉΓòÉ 2.4.2.2. Levels of Checking ΓòÉΓòÉΓòÉ

There are different levels of cost versus expected benefit ratios for different
kinds of preconditions; the precondition that a cursor for a linked collection
implementation actually (still) points to an element of a given collection is
rather costly (iterating over the complete collection) and would probably only
be turned on in cases where the programmer is rather desperate; checking for an
empty collection, however, is rather inexpensive and could be done in the
production version.

The library provides three levels of precondition checking which are selected
by the following macro variable definitions (use, for example, compile flag
-DINO_CHECKS):

INO_CHECKS       Skip all checks except memory overflow

default          Perform those checks only where the ratio of safety through
                 checking versus its cost is high

IALL_CHECKS      Perform all checks


ΓòÉΓòÉΓòÉ 2.4.2.3. List of Exceptions ΓòÉΓòÉΓòÉ

Currently, the library defines the following exceptions.  Exceptions that are
checked with IALL_CHECKS only are marked as 'optional'.
IChildAlreadyExistsException A tree must not already contain a child at the
position specified for the function addAsChild.
ICursorInvalidException

There are three cursor properties that may be checked for different functions
and lead to the ICursorInvalidException:

o A given cursor must always belong to the collection to which the function is
  applied; this means it must be defined with this collection as its
  constructor argument. This applies to every function that has a cursor as in-
  or out-argument (add, setToFirst, locate, ...).

o For functions that have a cursor as in-argument (elementAt, removeAt,
  replaceAt, isValid function and means that the cursor actually refers to some
  element within the collection. Invalid cursors are well-defined and are, for
  example, the result of unsuccessful location functions.

o If a cursor must be valid, the programmer can check that the cursor actually
  points to an element that is

     in the collection (see cursor function
  isValid). This check is effective and may be costly only for linked and
  diluted implementations.

IEmptyException The collection must not be empty with any function that
accesses the first or last element (firstElement, removeFirstElement, ...).
IFullException A bounded collection must not be full already with any function
that adds an element (add, addAsFirst, ...).
IIdenticalCollectionException The receiving collection must not be the same as
the From-collection  with function addAllFrom.
IKeyAlreadyExistsException A unique key collection must not already contain a
different element with the same key, with any function that adds an element
(add, addAllFrom, ...).
INotBoundedException The collection must be bounded for the function
maxNumberOfElements.
INotContainsKeyException The element with the specified key must be contained
in the collection, for the function elementWithKey.  .
IOutOfMemory IOutOfMemory exceptions are not the result of a precondition
violation. They can occur during any function that adds something  (add,
addAsFirst, ...).
IPositionInvalidException That the position specified is valid in the
collection, is a precondition for any function that specifies a position  (
elementAtPosition, removeAtPosition, setToPosition, ...).
IRootAlreadyExistsException A tree must not already have a root when the
function addAsRoot is called.  This is equivalent to the precondition that the
tree must be empty.


ΓòÉΓòÉΓòÉ 2.4.2.4. The Hierarchy of Exceptions ΓòÉΓòÉΓòÉ


IException
  |
.
.
.
  |
  |-- IPreconditionViolation
  |     |-- IChildAlreadyExistsException
  |     |-- ICursorInvalidException
  |     |-- IEmptyException
  |     |-- IFullException
  |     |-- IIdenticalCollectionException
  |     |-- IKeyAlreadyExistsException
  |     |-- INotBoundedException
  |     |-- INotContainsKeyException
  |     |-- IPositionInvalidException
  |     |-- IRootAlreadyExistsException
  |
.
.
.
  |
  |-- IResourceExhausted
  |     |
  |     |-- IOutOfMemory
  |     |
.
.
.

IException offers the following functions that return information on the
exception:
unsigned long  errorId() The ID of the error is returned.
unsigned int  isRecoverable() 1 is returned, if the exception is deemed to be
recoverable, 0 if it is not.
const char*  name() The name of the exception class is returned.
const char*  text(unsigned long indexFromTop = 0) A text string with additional
information about the exception is returned.  There is a stack of text strings.
Index 0, the top of the stack, is the default for argument indexFromTop.
unsigned long  textCount() The number of levels of message text in the
exception message stack is returned.


ΓòÉΓòÉΓòÉ 2.4.3. Required Functions of Elements and Keys ΓòÉΓòÉΓòÉ


ΓòÉΓòÉΓòÉ 2.4.3.1. Defining Element Functions ΓòÉΓòÉΓòÉ

Functions of the collection classes call other functions to determine their
element and key types. For example, they use the element's assignment or copy
constructors for adding an element, or they use the element's equality operator
for locating an element in the collection. In addition, they use memory
management functions for the allocation and deallocation of dynamically created
internal objects (nodes).

Element functions that may be required are:

o default and copy constructor,
o destructor,
o assignment,
o equality test,
o ordering relation,
o key access, and
o hash function.
Key functions that may be required are:

o equality test,
o ordering relation, and
o hash function.
Memory management functions are:

o allocation
o deallocation
The element/key functions can be provided in three different ways, allowing
three different levels of flexibility and tailoring.


Using Standard Operators

The easiest way is to use the element/key's standard operators. This is the
only way for constructors and destructors. For assignment, equality and
ordering relation, the operators =, ==, and < are used, respectively. This
function is not applicable for key access, hash function and memory management.
It is important that the argument types are defined as const except for the
first assignment argument, or in case of class member functions, that the
functions are defined to be const for the class; missing consts will result in
compile errors.

   void          operator=  (Element&, Element const&);
   Boolean       operator== (Element const&, Element const&);
   long          operator<  (Element const&, Element const&);
or

   class Element
   { void          operator=  (Element const&);
     Boolean       operator== (Element const&) const;
     long          operator<  (Element const&) const;
   };


Using Separate Functions

The second level uses the following functions, which may be defined by the
programmer; the previously described function works by providing a default
(template) definition for these functions:

   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&);
   Boolean       equal   (Key const&, Key const&);
   long          compare (Key const&, Key const&);
   unsigned long hash    (Key const&);
as well as the standard memory management functions

   void*         operator new (size_t);
   void          operator delete (void*);
The default definition for the compare function uses two comparisons with
operator<. It is therefore advisable to (re-)define the 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
being used.

The second level will be used, in particular, if the programmer who
instantiates the collection class has no control over the element class and the
element class does not define the appropriate functions. It is also the most
convenient way for providing key access and hash function:

  typedef unsigned long TaskId;
  typedef int Priority;
  class Task
  { TaskId ivId;
    Priority ivPriority;
  public:
    TaskId   id ()       { return ivId; }
    Priority priority () { return ivPriority; }
    ...
  };
  ...
  TaskId key (Task const& t)
  { return t.id (); }
  ...
  IKeySet <Task, TaskId> runningTasks;


Using Element Operation Classes

For each collection class there is an argument that takes a class defining all
required element/key operations. By default, a class is used that defines these
operations via the corresponding element/key functions. The advantage of
passing the arguments via an extra class instead of passing them as function
pointers is that the class solution allows, (and mostly in fact uses) inlining.
Collection classes with the operation class argument are called IG..., for
example, IGSequence. Programmers may define such classes themselves and pass
them to the IG... templates. This may, in particular, be useful in cases where,
for two different instantiations of (maybe different) collections with the same
element or key type, two different key or hash functions shall be used.

Operation classes look as follows, where 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&);

    class KeyOps
    { Boolean       equal        (Key const&, Key const&);
      long          compare      (Key const&, Key const&);
      unsigned long hash         (Key const&);
    } keyOps;
  };
For defining operation classes, the following class templates may be used which
define a single function that calls the corresponding non-member function.
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&);
  };

In order to define an operation class, use the predefined templates for
standard functions and define the specific functions 'by hand'. As an example,
consider 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.
Since the key function is already defined to yield the task identifier, the
priority queue would have to be instantiated like this:

  class TaskPrioOps : public IStdMemOps,
                      public IStdAsOps < Task >,
  { Priority key (Task const& t)
    { returnt.priority (); }

    IStdCmpOps < int > keyOps;
  };
  ...
IGPriorityQueue < Task, Priority, TaskPrioOps > taskPriorityQueue;

The functions that are required for a certain collection class depends 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 logic of the
collection interface; The reference manual defines which functions must be
provided for keys and elements for each implementation choice; for the default
implementation (for example IGSet), a default operation class is provided
(IGSetOps). This class may be used as a base class for deriving a specific
class with non-standard element or key functions. The following example uses
the standard sequence operations but provides a non-standard memory manager:

  class MySeqOps : public ISequenceOps < MyElement >
  { void* allocate   (size_t s) {...}
    void  deallocate (void* p)  {...}
  };

  class MyElementSeq : public IGSequence < MyElement, MySeqOps >
  {...};

Note that the instantiation of the default collection operations will cause the
standard key and element functions to be instantiated; these functions or
operators must be defined even though they are redefined in the derived class.


ΓòÉΓòÉΓòÉ 2.4.3.2. Values vs. (Managed) Objects ΓòÉΓòÉΓòÉ

C++ is a 'value-oriented' language due to its origination and compatibility
with C. This means that unless otherwise stated, variables, and function
arguments and results have their value (contents) copied when assigned.
Pointers or references are used for the common object semantics, which means
copying just a pointer or reference to the object, thus enabling polymorphic
applications through virtual functions. Pointers to elements can be used as
collection element types in such cases, because references are not allowed as
collection element types. For KeySets, this procedure works fine (note that the
key function is defined with argument type Task*):

  class Task
  { ...
  };
  TaskId const& key (Task* const& t) { return t.ivId; }
  IKeySet < Task*, int > tasks;

For collections with element equality, the situation is not as simple.
Instantiating the collection template with the element pointer type will result
in applying pointer assignment and comparison for the elements which is, in
general, not intended. In the following example, adding, locating and other
functions would be based on pointer equality and, possible, ordering, and not
the equality defined for the Task type.

  class Task
  { TaskId ivId;
    ...
    Boolean operator== (Task const& t)
    { return ivId == t.ivId; }
  };
  ISet < Task* > tasks;

For the 'simulation' of references to elements, the library has the template
class IRef, which is instantiated with the element type. IRefs are constructed
(or converted) from an element pointer and can be converted to element
references.

  typedef IRef < Task > TaskRef;
  ISet < TaskRef > taskSet;
  TaskRef t1 (new Task);
  taskSet.add (t1);
  ...
  taskSet.remove (t1);
  delete &t1;

Note that the dynamically created elements are not automatically deleted when
they are removed from the collection. For managed references that provide
automatic garbage collection see section Garbage Collection.


ΓòÉΓòÉΓòÉ 2.4.3.3. Garbage Collection ΓòÉΓòÉΓòÉ

The class IMgRef implements a reference class as defined in the previous
section together with garbage collection for the referenced element. Garbage
collection is implemented by reference counting; its proper behaviour requires
that the pointer to the element from which the reference is initially
constructed is no longer used.

  typedef IMgRef < Task > TaskRef;
  ISet < TaskRef > tasks;
  TaskRef t1 (new Task);
  tasks.add (t1);
  ...
  tasks.remove (t1);
In the example, the allocated task will automatically be deleted within the
remove function unless it is referenced through another TaskRef; in this case
it will be removed when it is referenced by no other TaskRef.

Garbage collection 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 IMgRef can
also be used for this purpose.


ΓòÉΓòÉΓòÉ 2.4.3.4. Functions for Derived Element Classes ΓòÉΓòÉΓòÉ

Due to the C++ language rule that states function template instantiations to be
considered before conversions, element functions like equal or compare defined
for some classes will not be considered for a derived class; 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 B which uses the
operator< of B, if defined, or otherwise reports it as an error. To get the
intended behavior, standard functions like equal or compare must be
(re-)defined for the actual element type.

IRef classes cope with this problem by using an extra indirection, to make an
instantiation like ISet < IRef < Task > > use the right functions. This
indirection is, in general, transparent to the programmer, but must be
considered when deriving from the IRef 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 IRef (and similar classes) this function is defined to yield the referenced
element instead. Note, that if a class derived from IRef < E > is used as
collection element type, the default template functions must be instantiated
before a conversion will be considered; a derived class will therefore have to
explicitly redefine the elementForOps function:

  class TaskRef : public IRef < Task >
  { Task& elementForOps ()
    { return IRef < Task >::elementForOps (); }
    Task const& elementForOps () const
    { return IRef < Task >::elementForOps (); }
  };
  Set < TaskRef > taskSet;


ΓòÉΓòÉΓòÉ 2.4.4. Tailoring a Collection Implementation ΓòÉΓòÉΓòÉ

Section Instantiation and Object Definition introduced the instantiation of the
collections' default implementations. The library suggests a development
methodology that starts with the default implementation for all (or most)
collections, and ends with a final tuning or tailoring phase where
implementations are chosen, according to the actual needs. These needs can, for
example, be derived with profiling or other measurement tools. This section
will describe how to choose and possibly compose implementation classes.

As described in section The Overall Implementation Structure, each data
abstraction has several possible implementations. Some of these concrete
classes are basic, like the AVL trees, hash tables, or linked and tabular
sequences, others are based on other collection classes, like the bag.
Exchanging the default implementation with a basic implementation is simple. If
you want to use an AVL tree for the implementation of a particular class, say
MyType that is a map and has been defined with a default implementation IKeySet
you can just replace

   typedef IKeySet < Element, Key > MyType;
by

   typedef IAvlKeySet < Element, Key > MyType;

If the implementation that you choose is based on some other collection, you
must first choose this collection and then use it to instantiate the based
collection. This mechanism will be outlined in the following section.


ΓòÉΓòÉΓòÉ 2.4.4.1. The Based-On Concept ΓòÉΓòÉΓòÉ

In order to achieve a high degree of implementation choice flexibility, several
collection class implementations are based on another abstract class, rather
than implemented directly by a concrete implementation variant of this class.

For choosing a concrete implementation, like a Set based on a KeySorted Set
based on a Tabular Sequence, these class templates have to be 'plugged
together'.  The plug mechanism requires class templates being used as template
arguments; unfortunately, C++ does not allow this.  Therefore, the library
simulates the plug mechanism by macros.  Two macros are needed: one for
defining a template with an additional function class argument (see section
Defining Element Functions), and one for defining a template with just the
element and, possibly, key types as arguments.

The element functions that are needed by a particular implementation may 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 will require the element type to provide a
comparison function, and a hash table implementation will require the element
type to have a hash function. Standard function class templates are predefined
which can be used for defining particular collection implementations. Their
names are systematically derived from the operations they define. The name
structure is: I<elem-ops>[K<key-ops>]Ops, where <elem-ops> and <key-ops> 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, and key
equality and hashing.

  IDefineSetOnKeySortedSet (IGAvlKeySortedSet, IGAvlSet)
  IDefineCollectionWithOps (IGAvlSet, IECOps, IAvlSet)
The first of these defines a Set class template named IGAvlSet as based on a
KeySorted Set class template IGAvlKeySortedSet.  The second defines a Set class
template named IAvlSet as the Set class template IGAvlSet with the element and
key functions specified with IECOps.


Together with the definition of IECOps this expands to:

  template < class Element, class ElementOps >
  class IGAvlSet :
    public IGAvlKeySortedSet < Element, Element,
                               IOpsWithKey < Element, ElementOps > >
  { ... constructor redefinition
  };
  template < class Element >
  class IECOps : public IStdMemOps,
                 public IStdAsOps < Element >,
                 public IStdEqOps < Element >,
                 public IStdCmpOps < Element >
  {
  };
  template < class Element >
  class IAvlSet : public IGAvlSet < Element, IECOps < Element > >
  { ... constructor redefinition
  };
For multilevel based-on implementations, the same mechanism is applied as
follows:

  IDefineGKeySortedSetOnGSequence
    (IGLinkedSequence, IGKeySortedSetOnLnkSeq)
  IDefineGSetOnGKeySortedSet
    (IGKeySortedSetOnLnkSeq, IGSetOnSortedLnkSeq)
  IDefineCollectionWithOps
    (IGSetOnSortedLnkSeq, IECOps, ISetOnSortedLnkSeq)


ΓòÉΓòÉΓòÉ 2.4.4.2. Provided Implementation Variants ΓòÉΓòÉΓòÉ

 reftype=hd."Figure: Possible Implementation Paths" contains the basic and
based implementations provided by the library. The upper left corner of each
entry contains the name of the (abstract) collection class; basic
implementations are written in bold letters while based implementations are
described by arrows starting from the class which 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 implementation path which ultimately leads to a basic implementation.
For ease of use, and for the avoidance of very long (mangled) names, the based
implementations denoted by non-bold arrows are provided as shortcuts.

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 is
inserted keeping the elements sorted.


PossibleImplementationPaths


ΓòÉΓòÉΓòÉ 2.4.5. Implementation Classes and Include Files ΓòÉΓòÉΓòÉ


Following is the list of provided abstract classes and their implementations.
The first mentioned implementation for each abstract class is the current
default. The default implementation is defined as a template with the given
name and can be accessed through the include files specified for each abstract
class; the corresponding template with additional operation class argument is
called IG... instead of I..., for example template classes IMap and IGMap are
defined in include file imap.h as based on KeySortedSet. Knowledge about the
implementation classes, their names and their include files is only necessary
for selecting alternative implementations as described in section The Based-On
Concept.



ΓöîΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö¼ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÉ
Γöé CLASS NAME       Γöé INCLUDE     Γöé DESCRIPTION                   Γöé
Γöé                  Γöé FILE        Γöé                               Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé 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               Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IKeySet          Γöé ikeyset.h   Γöé based on AVL KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWKeySetOnKSSet Γöé ikskss.h    Γöé based on KeySortedSet         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IGHashKeySet    Γöé ihshks.h    Γöé Hash table for KeySet (basic) Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IKeyBag          Γöé ikeybag.h   Γöé Hash table for KeyBag         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IGHashKeyBag    Γöé ihshkb.h    Γöé Hash table for KeyBag (basic) Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé ISet             Γöé iset.h      Γöé based on AVL KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWSetOnKSSet    Γöé isetkss.h   Γöé based on KeySortedSet         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWSetOnKeySet   Γöé isetks.h    Γöé based on KeySet               Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IBag             Γöé ibag.h      Γöé based on AVL KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWBagOnKSSet    Γöé ibagkss.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         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IKeySortedSet    Γöé iksset.h    Γöé AVL tree for KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé                  Γöé iavlkss.h   Γöé AVL tree for KeySortedSet     Γöé
Γöé IGAvlKeySortedSetΓöé             Γöé (basic)                       Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IKeySortedBag    Γöé iksbag.h    Γöé based on LinkedSequence       Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWKSBagOnSeq    Γöé iksbseq.h   Γöé based on Sequence             Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé ISortedSet       Γöé isrtset.h   Γöé based on AVL KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWSSetOnKSSet   Γöé isskss.h    Γöé based on KeySortedSet         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé ISortedBag       Γöé isrtbag.h   Γöé based on AVL KeySortedSet     Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWSrtBagOnKSSet Γöé isbkss.h    Γöé based on KeySortedSet         Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé IEqualitySequenceΓöé ieqseq.h    Γöé based on LinkedSequence       Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  IWEqSeqOnSeq    Γöé iesseq.h    Γöé based on Sequence             Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé ISequence        Γöé iseq.h      Γöé linked sequence               Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé  ILinkedSequence Γöé ilnseq.h    Γöé linked sequence (basic)       Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé                  Γöé itbseq.h    Γöé tabular sequence (basic)      Γöé
Γöé ITabularSequence Γöé             Γöé                               Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö╝ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
Γöé                  Γöé itdseq.h    Γöé tabular diluted sequence      Γöé
Γöé IDilutedSequence Γöé             Γöé (basic)                       Γöé
Γö£ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöñ
ΓööΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓö┤ΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÇΓöÿ


ΓòÉΓòÉΓòÉ 2.4.6. Polymorphic Use of Collections ΓòÉΓòÉΓòÉ

Polymorphism allows the programmer to take an abstract view on an object or
function argument and accept any concrete objects or arguments that are
specialized (derived) from this abstract view. The collection properties
defined in section Flat Collections serve to define such abstract views. They
are represented in the form of a class hierarchy that is illustrated in
"Figure: The abstract class hierarchy".

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. A heap is a concrete implementation of just
this abstract view. Elements can be added to a collection and a collection can
be iterated over. 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 so-called multiple inheritance: the
abstract collection class IEqualitySortedCollection, for example, combines the
abstract concepts of element equality and of being sorted which implies being
ordered.

For performance reasons that were explained in section The Overall
Implementation Structure the concrete collection classes are not directly
derived from the abstract classes. Instead, the programmer must use an
indirection that 'couples' a concrete collection with an abstract class. Users
of concrete classes need not pay the runtime (and partly even codesize)
overhead that comes with abstract class hierarchies. For each leaf in the
collection class hierarchy, for example, ISet there is such an indirection
class template called IRSet (see "Figure: 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.

  class TaskPrinter {
  public:
    print (IACollection < Task* > const& tasks)
    { cout << "ID     ..."
      ICursor *cursor = tasks.newCursor ();
      forCursor (*cursor)
      { Task* task = tasks.elementAt (*cursor);
        cout << task->id() << ...
      }
    }
  };
  ...
  typedef IKeySet < Task*, int > TaskSet;
  TaskSet running;
  ...
  IRKeySet < Task*, TaskSet > refRunning (running);
  TaskPrinter.print (refRunning);


ΓòÉΓòÉΓòÉ 3. Reference Manual - Flat Collections ΓòÉΓòÉΓòÉ

This part contains detailed descriptions of the flat collections of the  IBM
Class Library: Collection Classes for reference.

It starts with a chapter containing a list of all functions available in
alphabetical order. This chapter contains all information relevant for each
function.

You will notice that the classes have many member functions in common. For
example most classes have an addElement and  removeElement function.
So instead of describing the same function over and over again for each class
you will find each function described in detail in All Functions.

For each class you will find

o ... an abstract. E.g. what is a set or what is a tree.

o ...

o ...

o ... a summary of all functions.

o ... an example.


ΓòÉΓòÉΓòÉ 3.1. All Functions ΓòÉΓòÉΓòÉ

This chapter lists all functions in alphabetical order.

At the beginning, you will find an explanation of some of the terms used.


ΓòÉΓòÉΓòÉ 3.1.1. Terms Used ΓòÉΓòÉΓòÉ

this collection     is the collection on which a function is applied. As
                    opposed to the given collection.

given collection    is a collection given as a function argument.

given element       is an element given as a function argument.

returned element    is an element returned as a function return value.

positioning property the property of an element which is used to poition the
                    element in a collection. E.g. the value of the whole
                    element or the value of the key.

iteration order     the order in which elements are visited in allElementsDo
                    and setToNext or setToPrevious.
                    In SORTED collections elements are visited following there
                    positioning property.
                    In ORDERED collections the element at position 1 will be
                    visited first, then element at postion 2, etc.. (ORDERED
                    collection are not necessarily SORTED!).
                    In collections that are not ORDERED the ELEMENTS are
                    visited in an arbitrary order. Each element is visited
                    exactly once.


ΓòÉΓòÉΓòÉ 3.1.2. List of Functions ΓòÉΓòÉΓòÉ


ΓòÉΓòÉΓòÉ 3.1.2.1. add ΓòÉΓòÉΓòÉ

 Boolean add (Element const&);
 Boolean add (Element const&,ICursor&);
If the collection has UNIQUE ELEMENTS and the element is already contained in
the collection, set the cursor to the existing element in the collection and do
not add the element. Otherwise, add the element to the collection and set 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.
ReturnValue: True if the element was added.
Side Effect: If an element was added all cursors of this collection, except the
given cursor, become undefined.
Precondition:

o The cursor must belong to the collection..
o If BOUNDED and UNIQUE:
  Element exists or numberOfElements < maxNumberOfElements
o If BOUNDED and NON UNIQUE:
  NumberOfElements < maxNumberOfElements.
o If UNIQUE KEY:
  If the collection contains some element with the same key as the given
  element, then this element must be equal to the given element.
o If MAPPING:
  If the collection contains some element with the same key as the given
  element, then this element must be equal to the given element.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.2. addAllFrom ΓòÉΓòÉΓòÉ

 void addAllFrom (CLASS_NAME const&);
 void addAllFrom (IACollection <Element> const&);
Add (copy) all elements of the given collection to the collection. The sequence
in which the elements are copied is according to the definition off
allElementsDo of the given collection. The elements are added according to the
definition of add for this collection.
Side Effect: If some elements were actually added all cursors of this
collection would become undefined.
Precondition: See preconditions of add.

The collection may not be the same as the given collection. I.e. you can't copy
a collection to itself.
Exceptions:

o IMemoryExhaustedException
o IIdenticalCollectionException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.3. addAsFirst ΓòÉΓòÉΓòÉ

 void addAsFirst (Element const&);
 void addAsFirst (Element const&,ICursor&);
Add the element to the collection as the first element in sequential order. Set
the cursor to the added element.
Side Effect: All cursors of this collection, except the given cursor, become
undefined.
Precondition: The cursor must belong to the collection.
If BOUNDED:
numberOfElements < maxNumberOfElements.
Exceptions:

o ICursorInvalidException
o IMemoryExhaustedException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.4. addAsLast ΓòÉΓòÉΓòÉ

 void addAsLast (Element const&);
 void addAsLast (Element const&,ICursor&);
Add the element to the collection as the last element in sequential order. Set
the cursor to the added element.
Side Effect: All cursors of this collection, except the given cursor, become
undefined.
Precondition: The cursor must belong to the collection.
If BOUNDED:
numberOfElements < maxNumberOfElements.
Exceptions:

o ICursorInvalidException
o IMemoryExhaustedException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.5. addAsNext ΓòÉΓòÉΓòÉ

 void addAsNext (Element const&,ICursor&);
Add the element to the collection as the element which is in sequential order
next to the element pointed to by the cursor. Set the cursor to the added
element.
Side Effect: If the element was actually added all cursors of this collection,
except the given cursor, become undefined.
Precondition: If BOUNDED: The cursor must belong to the collection.
numberOfElements < maxNumberOfElements.
Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.6. addAsPrevious ΓòÉΓòÉΓòÉ

 void addAsPrevious (Element const&,ICursor&);
Add the element to the collection as the element which, in sequential order is
previous to the element pointed to by the cursor. Set the cursor to the added
element.
Side Effect: If the element was actually added all cursors of this collection,
except the given cursor, would become undefined.
Precondition: The cursor must belong to the collection.
If BOUNDED:
numberOfElements < maxNumberOfElements.
Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.7. addAtPosition ΓòÉΓòÉΓòÉ

 void addAtPosition (IPosition,Element const&);
 void addAtPosition (IPosition,Element const&,ICursor&);
Add 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 previous element to
the existing element. Set the cursor to the added element.
Position 1 specifies the first element.
Side Effect: All cursors of this collection become undefined.
Precondition:

o The cursor must belong to the collection.
o 1 <= position <= numberOfElements + 1
o If BOUNDED: numberOfElements < maxNumberOfElements

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o IPositionInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.8. addDifference ΓòÉΓòÉΓòÉ

 void addDifference (CLASS_NAME const&,CLASS_NAME const&);
Create the difference between the two given collections and add this difference
to the collection.
(See definition of difference at differenceWith.)
Side Effect: If some elements are added all cursors of this collection become
undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.9. addIntersection ΓòÉΓòÉΓòÉ

 void addIntersection (CLASS_NAME const&,CLASS_NAME const&);
Create the intersection of the two given collections and add this intersection
to the collection.
(See definition of intersection at intersectionWith.)
Side Effect: If some elements were added all cursors of this collection become
undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.10. addOrReplaceElementWithKey ΓòÉΓòÉΓòÉ

 Boolean addOrReplaceElementWithKey (Element const&);
 Boolean addOrReplaceElementWithKey (Element const&,ICursor&);
If there is an element contained in the collection where the key is equal to
the key of the given element, set the cursor to this element in the collection
and replace it with the given element. Otherwise, add the given element to the
collection and set the cursor to the added or replaced element.
ReturnValue: True if the element was added.
Side Effect: If the element was added all cursors of this collection, except
the given cursor, would become undefined.
Precondition: The cursor must belong to the collection.
If BOUNDED:
an element with the given key is contained in the collection or
numberOfElements < maxNumberOfElements.
Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.11. addUnion ΓòÉΓòÉΓòÉ

 void addUnion (CLASS_NAME const&,CLASS_NAME const&);
Create the union of the two given collections and add this union to the
collection.
(See definition of union at unionWith.)
Side Effect: If some elements were actually added all cursors of this
collection become undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.12. allElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (IConstantIterator <Element>&) const;
Call 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.
Note: The applyTo function must not remove or add elements of the collection.
ReturnValue: True if the applyTo function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 3.1.2.13. allElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (Boolean (*function) (Element const&, void*),
                        void* additionalArgument)const;
Call 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.
Note: The given function may not remove or add elements to the collection.
ReturnValue: True if the given function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 3.1.2.14. allElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (IIterator <Element>&);
Call 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 can be passed to the applyTo function using the
additionalArgument.
Note: The applyTo function may not remove or add elements from or to the
collection.
The applyTo must not manipulate the element in the collection in a way, that
changes the positioning property of the element.
ReturnValue: True if the applyTo function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 3.1.2.15. allElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (Boolean (*function) (Element&, void*),
                        void* additionalArgument);
Call the given function to 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 the additionalArgument.
Note: The given function may not remove or add elements to or from the
collection.
The given function must not manipulate the element in the collection in a way
that changes the positioning property of the element.
ReturnValue: True if the given function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 3.1.2.16. anyElement ΓòÉΓòÉΓòÉ

 Element const& anyElement () const;
Returns (a constant reference to) any element of the collection.
Precondition: The collection must not be empty.
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.17. compare ΓòÉΓòÉΓòÉ

 long compare (CLASS_NAME const&, long (*comparisonFunction)
                              ( Element const&,Element const&)) const;
Lexicographically compare 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
no such pair exists, the collection with more elements is the greater one;
otherwise the collection with the greater element of the pair is the greater
one.
Note: The comparisonFunction must deliver: >0 if element1 > element2, 0 if
element1 == element2, <0 if element1 < element2.
ReturnValue: Result of the comparison.


ΓòÉΓòÉΓòÉ 3.1.2.18. Constructor ΓòÉΓòÉΓòÉ

 CLASS_BASE_NAME (INumber numberOfElements = 100, IBoundIndicator = IUnbounded);
Construct a collection. The boundIndicator determines whether the collection is
bounded or unbounded. NumberOfElements is the estimated or maximum number of
elements contained in the collection, depending on whether the collection is
bounded or unbounded, respectively. The collection is initially empty.
Note: It is undefined whether any elements are constructed with the collection
constructor. For some classes the element's default constructor may be invoked.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 3.1.2.19. contains ΓòÉΓòÉΓòÉ

 Boolean contains (Element const&) const;
Return true if the given element is contained in the collection.


ΓòÉΓòÉΓòÉ 3.1.2.20. containsAllFrom ΓòÉΓòÉΓòÉ

 Boolean containsAllFrom (CLASS_NAME const&) const;
 Boolean containsAllFrom (IACollection <Element> const&) const;
Return true if all the elements of the given collection are contained in the
collection.


ΓòÉΓòÉΓòÉ 3.1.2.21. containsAllKeysFrom ΓòÉΓòÉΓòÉ

 Boolean containsAllKeysFrom (CLASS_NAME const&) const;
 Boolean containsAllKeysFrom (IACollection <Element> const&) const;
Return true if all the keys of the given collection are contained in the
collection.


ΓòÉΓòÉΓòÉ 3.1.2.22. containsElementWithKey ΓòÉΓòÉΓòÉ

 Boolean containsElementWithKey (Key const&) const;
Return true if the given key is contained in the collection.


ΓòÉΓòÉΓòÉ 3.1.2.23. copy ΓòÉΓòÉΓòÉ

 void copy (IACollection <Element> const&);
Copy the given collection to the collection (that means reset the collection
and add the elements from the given collection).
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.
Side Effect: All cursors of this collection become undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException
o If UNIQUE KEYS: IKeyAlreadyExistsException
  This exception may be thrown, for example, when copying a bag into a set.


ΓòÉΓòÉΓòÉ 3.1.2.24. Copy Constructor ΓòÉΓòÉΓòÉ

 CLASS_BASE_NAME (CLASS_NAME const&);
Construct the collection and copy all elements from the given collection into
the collection.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 3.1.2.25. dequeue ΓòÉΓòÉΓòÉ

 void dequeue ();
 void dequeue (Element&);
Copy the first element of the collection to the given element, if any, and
remove it from the collection.
Side Effect: All cursors of this collection become undefined.
Precondition: The collection must not be empty
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.26. Destructor ΓòÉΓòÉΓòÉ

 ~CLASS_BASE_NAME ();
Remove all elements from the collection.
Side Effect: All cursors of the collection become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.27. differenceWith ΓòÉΓòÉΓòÉ

 void differenceWith (CLASS_NAME const&);
Make the collection the difference of the collection and the given collection.
Note: The difference of A and B (A minus B) is the set of elements which are
members of A but not of B.

The following rules apply for Bags with duplicate elements: If bag P contains
the element el-x m times and bag Q contains the element el-x n times, then the
difference of P and Q contains the element el-x m-n times if m is greater than
n, and zero times if m is equal to or smaller than n.
Side Effect: If some elements were actually removed, all cursors of this
collection become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.28. elementAt ΓòÉΓòÉΓòÉ

 Element& elementAt (ICursor const&);
Returns (a reference to) the element pointed to by the given cursor.
Note: Do not manipulate the element in the collection in a way that may change
the positioning property of the element (e.g. do not manipulate the key of an
element).
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.29. elementAt ΓòÉΓòÉΓòÉ

 Element const& elementAt (ICursor const&) const;
Returns (a constant reference to) the element pointed to by the given cursor.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.30. elementAtPosition ΓòÉΓòÉΓòÉ

 Element const& elementAtPosition (IPosition) const;
Returns (a constant reference to) the element at the given position in the
collection. Position 1 specifies the first element.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: IPositionInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.31. elementWithKey ΓòÉΓòÉΓòÉ

 Element& elementWithKey (Key const&);
Returns (a reference to) an element specified by the key.
Note: Do not manipulate the element in the collection in a way that changes the
positioning property of the element (example: do not change the key of an
element).
If there are several elements with the given key, an arbitrary one is returned.
Precondition: The given key is contained in the collection.
Exceptions: IKeyNotContainedException


ΓòÉΓòÉΓòÉ 3.1.2.32. elementWithKey ΓòÉΓòÉΓòÉ

 Element const& elementWithKey (Key const&) const;
Returns (a constant reference to) an element specified by the key.
Note If there are several elements with the given key, an arbitrary one is
returned.
Precondition: The given key is contained in the collection.
Exceptions: IKeyNotContainedException


ΓòÉΓòÉΓòÉ 3.1.2.33. enqueue ΓòÉΓòÉΓòÉ

 void enqueue (Element const&);
 void enqueue (Element const&,ICursor&);
Add the element to the collection and set the cursor to the added element. For
ordinary QUEUES the given element is added as the last element. For PRIORITY
QUEUES the element is added at a position determined by the element or key
value.
Side Effect: All cursors of this collection, except the given cursor, would
become undefined.
Precondition:

o The cursor must belong to the collection..
o If BOUNDED:
  numberOfElements < maxNumberOfElements.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.34. firstElement ΓòÉΓòÉΓòÉ

 Element const& firstElement () const;
Returns (a constant reference to) the first element of the collection.
Precondition: The collection must not be empty.
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.35. intersectionWith ΓòÉΓòÉΓòÉ

 void intersectionWith (CLASS_NAME const&);
Make the collection the intersection of the collection and the given
collection.
Note: The intersection of A and B is the set of elements which are members of
both A and B.

The following rules apply for Bags with duplicate elements: If bag P contains
the element el-x m times and bag Q contains the element el-x n times, then the
intersection of P and Q contains the element el-x MIN(m,n) times.
Side Effect: If some elements are actually removed, all cursors of this
collection would become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.36. isBounded ΓòÉΓòÉΓòÉ

 Boolean isBounded () const;
Return true if the collection is bounded.


ΓòÉΓòÉΓòÉ 3.1.2.37. isEmpty ΓòÉΓòÉΓòÉ

 Boolean isEmpty () const;
Return true if the collection is empty.


ΓòÉΓòÉΓòÉ 3.1.2.38. isFirst ΓòÉΓòÉΓòÉ

 Boolean isFirst (ICursor const&) const;
Return true if the element pointed to by cursor is the first element of the
collection.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.39. isFull ΓòÉΓòÉΓòÉ

 Boolean isFull () const;
Return true if the collection is bounded and contains the maximum number of
elements, i.e. if numberOfElements == maxNumberOfElements.


ΓòÉΓòÉΓòÉ 3.1.2.40. isLast ΓòÉΓòÉΓòÉ

 Boolean isLast (ICursor const&) const;
Return true if the element pointed to by cursor is the last element of the
collection.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.41. lastElement ΓòÉΓòÉΓòÉ

 Element const& lastElement () const;
Returns (a constant reference to) the last element of the collection.
Precondition: The collection must not be empty
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.42. locate ΓòÉΓòÉΓòÉ

 Boolean locate (Element const&, ICursor&) const;
Locate an element in the collection which is equal to the given element. Set
the cursor to point to the element in the collection, or invalidate the cursor
if no such element exists.
ReturnValue: True if an element was found.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.43. locateElementWithKey ΓòÉΓòÉΓòÉ

 Boolean locateElementWithKey (Key const&, ICursor&) const;
Locate an element in the collection with the given key. Set the cursor to point
to the element in the collection. or invalidate the cursor if no such element
exists.
ReturnValue: True if an element was found.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.44. locateFirst ΓòÉΓòÉΓòÉ

 Boolean locateFirst (Element const&, ICursor&) const;
Locate the first element in iteration order in the collection which is equal to
the given element. Set the cursor to the located element, or invalidate the
cursor if no such element exists.
ReturnValue: True if an element was found.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.45. locateLast ΓòÉΓòÉΓòÉ

 Boolean locateLast (Element const&, ICursor&) const;
Locate the last element in iteration order in the collection which is equal to
the given element. Set the cursor to the located element, or invalidate the
cursor if no such element exists.
ReturnValue: True if an element was found.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.46. locateNext ΓòÉΓòÉΓòÉ

 Boolean locateNext (Element const&, ICursor&) const;
Locate the next element in iteration order in the collection which is equal to
the given element starting at the element pointed to by the given cursor. Set
the cursor to point to the element in the collection. The cursor is invalidated
if no more occurrences of the given element are left to be visited.
Note: For unordered collections, the elements are visited in some order that is
not further defined.
ReturnValue: True if the cursor is valid.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.47. locateNextElementWithKey ΓòÉΓòÉΓòÉ

 Boolean locateNextElementWithKey (Key const&, ICursor&) const;
Locate the next element in iteration order in the collection with the given key
starting at the element pointed to by the given cursor. Set the cursor to point
to the element in the collection. The cursor is invalidated if no more
occurrences of such an element are left to be visited.
Note: For unordered collections, the elements are visited in some order that is
not further defined.
ReturnValue: True if the cursor is valid.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.48. locateOrAdd ΓòÉΓòÉΓòÉ

 Boolean locateOrAdd (Element const&);
 Boolean locateOrAdd (Element const&, ICursor&);
Locate an element in the collection which is equal to the given element. If
such an element is not contained add it. The cursor is set to the located or,
respectively, added element.
Note: This method is more efficient then using a locate followed by a
conditional add.
ReturnValue: True if the element was located (was already there).
Side Effect: If the element was actually added, all cursors of this collection
except the given cursor become undefined.
Precondition: See preconditions of add, if the element is to be added.
The cursor must belong to the collection.
Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.1.2.49. locateOrAddElementWithKey ΓòÉΓòÉΓòÉ

 Boolean locateOrAddElementWithKey (Element const&);
 Boolean locateOrAddElementWithKey (Element const&, ICursor&);
Locate any element in the collection with the given key. If such an element is
not contained add it. The cursor is set to the located or, respectively, added
element.
ReturnValue: True if an element with the given key was contained and could be
located
Side Effect: If the element was added, all cursors of this collection except
the given cursor become undefined.
Precondition: If BOUNDED and an element with the given key is not already
contained then numberOfElements < maxNumberOfElements.
The cursor must belong to the collection.
Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.50. locatePrevious ΓòÉΓòÉΓòÉ

 Boolean locatePrevious (Element const&, ICursor&) const;
Locate the previous element in iteration order in the collection which is equal
to the given element starting at the element previous to the one specified by
the given cursor. Set the cursor to the located element. The cursor is
invalidated if no such element was found.
ReturnValue: True if an element was found.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.51. maxNumberOfElements ΓòÉΓòÉΓòÉ

 INumber maxNumberOfElements () const;
Return the number of elements the collection can contain at most.
Precondition: The collection is bounded.
Exceptions: INotBoundedException


ΓòÉΓòÉΓòÉ 3.1.2.52. newCursor ΓòÉΓòÉΓòÉ

 ICursor* newCursor () const;
Create a cursor for the collection. The cursor is initially invalid.
ReturnValue: Pointer to the cursor.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 3.1.2.53. numberOfDifferentElements ΓòÉΓòÉΓòÉ

 INumber numberOfDifferentElements () const;
Return the number of different elements in the collection.


ΓòÉΓòÉΓòÉ 3.1.2.54. numberOfDifferentKeys ΓòÉΓòÉΓòÉ

 INumber numberOfDifferentKeys () const;
Return the number of different keys in the collection.


ΓòÉΓòÉΓòÉ 3.1.2.55. numberOfElements ΓòÉΓòÉΓòÉ

 INumber numberOfElements () const;
Return the number of elements the collection contains.


ΓòÉΓòÉΓòÉ 3.1.2.56. numberOfElementsWithKey ΓòÉΓòÉΓòÉ

 INumber numberOfElementsWithKey (Key const&) const;
Return the number of elements in the collection with the given key. collection.


ΓòÉΓòÉΓòÉ 3.1.2.57. numberOfOccurrences ΓòÉΓòÉΓòÉ

 INumber numberOfOccurrences (Element const&) const;
Return the number of occurrences of the given element in the collection.


ΓòÉΓòÉΓòÉ 3.1.2.58. operator != ΓòÉΓòÉΓòÉ

 Boolean operator != (CLASS_NAME const&) const;
Return true if the given collection is not equal to the collection. (See
description of operator ==)


ΓòÉΓòÉΓòÉ 3.1.2.59. operator = ΓòÉΓòÉΓòÉ

 CLASS_NAME& operator = (CLASS_NAME const&);
Copy the given collection to the collection (that means reset the collection
and add the elements from the given collection).
ReturnValue: (A reference to) the collection.
Side Effect: All cursors of this collection become undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.60. operator == ΓòÉΓòÉΓòÉ

 Boolean operator == (CLASS_NAME const&) const;
Return true if the given collection is equal to the collection. Two collections
are equal:

If the number of elements in the collections are the same and ...

If UNIQUE ELEMENTS: If an element occurs in the collection it must occur in the
               given collection and vice versa.
If NON UNIQUE ELEMENTS: If an element has N occurrences in the collection it
               must have exactly N occurrences in the given collection and vice
               versa.
If SEQUENTIAL: the ordering of the elements is the same for both collections.


ΓòÉΓòÉΓòÉ 3.1.2.61. pop ΓòÉΓòÉΓòÉ

 void pop ();
 void pop (Element&);
Copies the last element of the collection to the given element, if any, and
removes it from the collection.
Side Effect: All cursors of this collection become undefined.
Precondition: The collection must not be empty
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.62. push ΓòÉΓòÉΓòÉ

 void push (Element const&);
 void push (Element const&, ICursor&);
Add the element to the collection as the last element and set the cursor to the
added element.
Side Effect: All cursors of this collection except the given cursor become
undefined.
Precondition:

o The cursor must belong to the collection..
o If BOUNDED:
  numberOfElements < maxNumberOfElements.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o If BOUNDED: IFullException


ΓòÉΓòÉΓòÉ 3.1.2.63. remove ΓòÉΓòÉΓòÉ

 Boolean remove (Element const&);
Remove an element in the collection which is equal to the given element. In
collections with NON UNIQUE ELEMENTS and arbitrary occurrence of the given
element will be removed.
ReturnValue: True if an element was actually removed
Side Effect: If an element was actually removed, all cursors of this collection
become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.64. removeAll ΓòÉΓòÉΓòÉ

 void removeAll ();
Removes all elements from the collection.
Side Effect: All cursors of this collection become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.65. removeAll ΓòÉΓòÉΓòÉ

 INumber removeAll (Boolean (*property) (Element const&));
Removes all elements from this collection for which the given property function
return True.
ReturnValue: The number of actually removed elements.
Side Effect: All cursors of this collection become undefined.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.66. removeAllElementsWithKey ΓòÉΓòÉΓòÉ

 INumber removeAllElementsWithKey (Key const&);
Removes all elements from the collection with the given key.
ReturnValue: Number of elements removed
Side Effect: If an element was actually removed all cursors of this collection
become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.67. removeAllOccurrences ΓòÉΓòÉΓòÉ

 INumber removeAllOccurrences (Element const&);
Remove all occurrences of the given element in the collection.
ReturnValue: Number of elements removed
Side Effect: If an element was actually removed, all cursors of this collection
become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.68. removeAt ΓòÉΓòÉΓòÉ

 void removeAt (ICursor const&);
Removes the element pointed to by the cursor.
Side Effect: All cursors of this collection become undefined.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.69. removeAtPosition ΓòÉΓòÉΓòÉ

 void removeAtPosition (IPosition);
Removes the element from the collection, which is at the given position. The
first element of the collection has position 1.
Side Effect: All cursors of this collection become undefined.
Precondition: Position must be a valid position in the collection,
i.e. 1 <= position <= numberOfElements.
Exceptions: IPositionInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.70. removeElementWithKey ΓòÉΓòÉΓòÉ

 Boolean removeElementWithKey (Key const&);
Removes an element from the collection with the given key. In collections with
NON UNIQUE ELEMENTS and arbitrary occurrence of such an element will be
removed.
ReturnValue: True if an element was actually removed.
Side Effect: If an element was actually removed, all cursors of this collection
become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.71. removeFirst ΓòÉΓòÉΓòÉ

 void removeFirst ();
Removes the first element from the collection.
Side Effect: All cursors of this collection become undefined.
Precondition: The collection must not be empty
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.72. removeLast ΓòÉΓòÉΓòÉ

 void removeLast ();
Removes the last element from the collection.
Side Effect: All cursors of this collection become undefined.
Precondition: The collection must not be empty
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.73. replaceAt ΓòÉΓòÉΓòÉ

 void replaceAt (ICursor const&, Element const&);
Replaces the element pointed to by the cursor with the given element.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions:

o ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.74. replaceElementWithKey ΓòÉΓòÉΓòÉ

 Boolean replaceElementWithKey (Element const&);
 Boolean replaceElementWithKey (Element const&, ICursor&);
If there is no element where the key is equal to the key of the given element
in the collection invalidate the cursor. Otherwise replace the element and set
the cursor to this element. In collections with NON UNIQUE ELEMENTS and
arbitrary occurrence of such an element will be replaced.
ReturnValue: True if an element was replaced.
Precondition: The cursor must belong to the collection.
Exceptions: IMemoryExhaustedException
ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.75. setToFirst ΓòÉΓòÉΓòÉ

 Boolean setToFirst (ICursor&) const;
Set the cursor to the first element of the collection in iteration order. If
the collection is empty (i.e. if no first element exists) the given cursor will
become invalid.
ReturnValue: True if the collection is not empty.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.76. setToLast ΓòÉΓòÉΓòÉ

 Boolean setToLast (ICursor&) const;
Set the cursor to the last element of the collection in iteration order. If the
collection is empty (i.e. no last element exists) the given cursor will become
invalid.
ReturnValue: True if the collection was not empty.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.77. setToNext ΓòÉΓòÉΓòÉ

 Boolean setToNext (ICursor&) const;
Set the cursor to the next element in the collection in iteration order. If no
more elements are left to be visited the given cursor will become invalid.
ReturnValue: True if there was a next element.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.78. setToNextDifferentElement ΓòÉΓòÉΓòÉ

 Boolean setToNextDifferentElement (ICursor&) const;
Set the cursor to the next element in iteration order in the collection which
is different to the given element. If no more elements are left to be visited.
the given cursor will become invalid.
ReturnValue: True if there was a next different element.
Precondition: The cursor must belong to the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.79. setToNextWithDifferentKey ΓòÉΓòÉΓòÉ

 Boolean setToNextWithDifferentKey (ICursor&) const;
Set the cursor to the next element in the collection in iteration order with a
different key. If there is no such element the given cursor will become
invalid.
ReturnValue: True if there was a next element with different key.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.80. setToPosition ΓòÉΓòÉΓòÉ

 void setToPosition (IPosition, ICursor&) const;
Set the cursor to the element at the given position. If the given position does
not exist in the collection the given cursor will become invalid.
ReturnValue: True if position was a valid position.
Precondition: The cursor must belong to the collection.
Position must be a valid position in the collection,
i.e. 1 <= position <= numberOfElements.
Exceptions: ICursorInvalidException
IPositionInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.81. setToPrevious ΓòÉΓòÉΓòÉ

 Boolean setToPrevious (ICursor&) const;
Set the cursor to the previous (opposite of next) element in iteration order.
If no such element exists, the given cursor will become invalid.
ReturnValue: True if a previous element exists.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 3.1.2.82. sort ΓòÉΓòÉΓòÉ

 void sort (long (*comparisonFunction) (Element const&, Element const&));
Sort the collection. The relation of two elements is described by the
comparisonFunction.
Note: The comparisonFunction must deliver: >0 if element1 > element2, 0 if
element1 == element2, <0 if element1 < element2.
Side Effect: All cursors of this collection become undefined.


ΓòÉΓòÉΓòÉ 3.1.2.83. top ΓòÉΓòÉΓòÉ

 Element const& top () const;
Returns (a constant reference to) the last element of the collection.
Exceptions: IEmptyException


ΓòÉΓòÉΓòÉ 3.1.2.84. unionWith ΓòÉΓòÉΓòÉ

 void unionWith (CLASS_NAME const&);
Make the collection the union of the collection and the given collection.
Note: The union of A and B is the set of elements which are members of A or B
or both.

The following rules apply for Bags with duplicate elements: If bag P contains
the element el-x m times and bag Q contains the element el-x n times, then the
union of P and Q contains the element el-x m+n times.
Side Effect: If some elements were added to the collection all cursors of this
collection become undefined.
Precondition: See preconditions of add.
Exceptions:

o IMemoryExhaustedException
o If BOUNDED: IFullException
o If MAPPING: IKeyAlreadyExistsException


ΓòÉΓòÉΓòÉ 3.2. Heap ΓòÉΓòÉΓòÉ

A heap is an unordered collection of zero or more elements.

The type and value of the heap elements are irrelevant and have no effect on
the behavior of the heap.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a heap in respect to other flat collections.


ΓòÉΓòÉΓòÉ 3.2.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.2.2. Declaration ΓòÉΓòÉΓòÉ

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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) const;
};


ΓòÉΓòÉΓòÉ 3.3. Sequence ΓòÉΓòÉΓòÉ

A sequence is a collection of zero or more elements in which a linear order of
succession is maintained, with a first and a last element. Each element but the
first one has a predecessor, and each element but the last one has a successor.

The type and value of the sequence elements are irrelevant and have no effect
on the behavior of the sequence. Elements can be added and deleted from any
position of the sequence. Elements can be retrieved, and they can be replaced.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a sequence in respect to other flat collections.


ΓòÉΓòÉΓòÉ 3.3.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Sequence
Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.3.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The basic selections of implementation variants are :

doubly linked  and  unbounded or
tabular  and  bounded
If tabular and bounded is selected, further selections for implementation
variants might be done with:

wrapped  or  unwrapped and
pointered  or  pointerless and
undiluted  or  flag diluted  or  value diluted

The implementation variants for the Sequence are independent from other Classs,
i.e. it can not be based on other Classs.

Time complexity for element lookup is O( N ), where N is the total number of
elements in the list. This goes for both tabular and doubly linked lists.


ΓòÉΓòÉΓòÉ 3.3.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Sequence Class is illustrated in a  reftype=hd.coding example
provided with the IBM Class Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.3.3. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <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                     (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.3.4. Coding Example ΓòÉΓòÉΓòÉ

#include "iseq.h"
#include "xlist.h"

typedef ISequence <Word> WordSeq;
typedef IIterator <Word> WordIter;

long compare ( Word const& w1, Word const& w2) {
    return(strcmp(w1.GetElement(), w2.GetElement()));
}


/*--------------------------------------------------------------------------*\
* Test variables                                                             *
\*--------------------------------------------------------------------------*/

char *String[9] = {
   "the",
   "quick",
   "brown",
   "fox",
   "jumps",
   "over",
   "a",
   "lazy",
   "dog"
};

class PrintClass : public WordIter
{
public:
   Boolean applyTo(Word &w)
      {
      printf("%s\n",w.GetElement());    // Print the string
      return(True);
      }
};




/*--------------------------------------------------------------------------*\
* Main program                                                               *
\*--------------------------------------------------------------------------*/
int main()
{
   WordSeq WL;
   Word     aWord;
   WordSeq:: Cursor cursor(WL);
   PrintClass Print;

   int i;

   printf("\n*** Example of Sequence use ***\n");

   for (i = 0; i < 9; i ++) {                // Put all strings in the list
      aWord.Fill(String[i]);                 // Fill object with right value
      WL.addAsFirst(aWord);                  // Add it as first in the list
      }
   printf("\nList initial order:\n");        // Print the list in this order
   WL.allElementsDo(Print);

   WL.sort(compare);                       // Sort the list ascending
   printf("\nList sorted order:\n");         // Print the list in this order
   WL.allElementsDo(Print);

   /**/
   /**/

   printf("\nLook for \"fox\" in the list\n");
   aWord.Fill("fox");
   for (cursor.setToFirst();
      cursor.isValid(), (WL.elementAt(cursor) != aWord.GetElement());
      cursor.setToNext());
   if (WL.elementAt(cursor)==aWord.GetElement()) {
    printf("\n found Element \n");
    }
   else {
    printf("\n Element not found \n");
   }
   /**/
   /**/

   /**/
   /**/


   printf("\n*** End of example ***\n");

   return(0);
}

Header File:

#include "iseq.h"
#include "xlist.h"

typedef ISequence <Word> WordSeq;
typedef IIterator <Word> WordIter;

long compare ( Word const& w1, Word const& w2) {
    return(strcmp(w1.GetElement(), w2.GetElement()));
}


/*--------------------------------------------------------------------------*\
* Test variables                                                             *
\*--------------------------------------------------------------------------*/

char *String[9] = {
   "the",
   "quick",
   "brown",
   "fox",
   "jumps",
   "over",
   "a",
   "lazy",
   "dog"
};

class PrintClass : public WordIter
{
public:
   Boolean applyTo(Word &w)
      {
      printf("%s\n",w.GetElement());    // Print the string
      return(True);
      }
};




/*--------------------------------------------------------------------------*\
* Main program                                                               *
\*--------------------------------------------------------------------------*/
int main()
{
   WordSeq WL;
   Word     aWord;
   WordSeq:: Cursor cursor(WL);
   PrintClass Print;

   int i;

   printf("\n*** Example of Sequence use ***\n");

   for (i = 0; i < 9; i ++) {                // Put all strings in the list
      aWord.Fill(String[i]);                 // Fill object with right value
      WL.addAsFirst(aWord);                  // Add it as first in the list
      }
   printf("\nList initial order:\n");        // Print the list in this order
   WL.allElementsDo(Print);

   WL.sort(compare);                       // Sort the list ascending
   printf("\nList sorted order:\n");         // Print the list in this order
   WL.allElementsDo(Print);

   /**/
   /**/

   printf("\nLook for \"fox\" in the list\n");
   aWord.Fill("fox");
   for (cursor.setToFirst();
      cursor.isValid(), (WL.elementAt(cursor) != aWord.GetElement());
      cursor.setToNext());
   if (WL.elementAt(cursor)==aWord.GetElement()) {
    printf("\n found Element \n");
    }
   else {
    printf("\n Element not found \n");
   }
   /**/
   /**/

   /**/
   /**/


   printf("\n*** End of example ***\n");

   return(0);
}


ΓòÉΓòÉΓòÉ 3.3.5. Coding Example ΓòÉΓòÉΓòÉ

/*--------------------------------------------------------------------------*\
*                                                                            *
| Example program of Building Block SEQUENCE.                               |
*                                                                            *
\*--------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <iseq.h>

typedef ISequence <char> CharSeq;

typedef IIterator <char> CharIterator;

class PrintClass : public CharIterator
{
public:
   Boolean applyTo(char &c)
      {
      printf("%c",c);    // Print the character
      return(True);
      }
};


char * String = "BuildingBlocks";

/*--------------------------------------------------------------------------*\
* Main program                                                               *
\*--------------------------------------------------------------------------*/
int main() {
   CharSeq CS;
   CharSeq::Cursor cursor(CS);

   PrintClass Print;
   int i;

   printf("\n*** Example of SEQUENCE use ***\n");

   for (i = 0; String[i] != 0; i++)          // Put all characters in the
      {                                      // sequence.
      CS.add(String[i]);
      }

   printf("\nSequence contains:\n");         // Print the contents
   CS.allElementsDo(Print);
   printf("\nNumber of elements = %ld\n",CS.numberOfElements());

   while (CS.numberOfElements () >= 5) {
     CS.setToPosition(5, cursor);
     CS.allElementsDo(Print);
     printf("\n");
     CS.removeAt(cursor);
   }

   printf("\nSequence without the tail:\n"); // Print the contents again
   CS.allElementsDo(Print);
   printf("\nNumber of elements = %ld\n",CS.numberOfElements());

   printf("\n*** End of example ***\n");

   return(0);
}


ΓòÉΓòÉΓòÉ 3.3.6. Coding Example ΓòÉΓòÉΓòÉ


#include <iostream.h>

#include "people.h"
#include "iseq.h"


typedef ISequence <Person> People;


main() {

    People people;
    People::Cursor p_cursor(people);

    people.add(Person("M. Gorbatschow", True));
    people.add(Person("G. Bush", False));
    people.add(Person("R. Perot", True));
    people.add(Person("B. Jeltsin", False));
    people.add(Person("J. Major", False));
    people.add(Person("F. Castro", False));
    people.add(Person("Kojak", True));
    people.add(Person("A. Schwarzenegger", False));
    people.add(Person("H. Kohl", True));
    people.add(Person("F. Mitterand", True));
    people.add(Person("Magic Johnson", True));
    people.add(Person("B. Becker", False));
    people.add(Person("E. Presley", False));
    people.add(Person("Heino", True));
    people.add(Person("M. Gandhi", True));
    people.add(Person("Lenin", True));

    cout<<"\n";

    for(p_cursor.setToFirst(); p_cursor.isValid(); p_cursor.setToNext()) {
        cout<<"\n"<<people.elementAt(p_cursor).get_name();
    }
    cout<<"\n\nNumber of people : "<< people.numberOfElements()<<"\n";

    People bald;
    People::Cursor b_cursor(bald);
    for (p_cursor.setToFirst(); p_cursor.isValid(); p_cursor.setToNext()) {
        if(people.elementAt(p_cursor).is_bald()) {
            bald.add(people.elementAt(p_cursor));
        }
    }
    cout<<"\nBald people : \n";
    for (b_cursor.setToFirst(); b_cursor.isValid(); b_cursor.setToNext()) {
        cout<<"\n"<<bald.elementAt(b_cursor).get_name();
    }
    cout<<"\n\nNumber of bald people : "<<bald.numberOfElements()<<"\n";

    return 0;
}
Header File:


#include <iostream.h>

#include "people.h"
#include "iseq.h"


typedef ISequence <Person> People;


main() {

    People people;
    People::Cursor p_cursor(people);

    people.add(Person("M. Gorbatschow", True));
    people.add(Person("G. Bush", False));
    people.add(Person("R. Perot", True));
    people.add(Person("B. Jeltsin", False));
    people.add(Person("J. Major", False));
    people.add(Person("F. Castro", False));
    people.add(Person("Kojak", True));
    people.add(Person("A. Schwarzenegger", False));
    people.add(Person("H. Kohl", True));
    people.add(Person("F. Mitterand", True));
    people.add(Person("Magic Johnson", True));
    people.add(Person("B. Becker", False));
    people.add(Person("E. Presley", False));
    people.add(Person("Heino", True));
    people.add(Person("M. Gandhi", True));
    people.add(Person("Lenin", True));

    cout<<"\n";

    for(p_cursor.setToFirst(); p_cursor.isValid(); p_cursor.setToNext()) {
        cout<<"\n"<<people.elementAt(p_cursor).get_name();
    }
    cout<<"\n\nNumber of people : "<< people.numberOfElements()<<"\n";

    People bald;
    People::Cursor b_cursor(bald);
    for (p_cursor.setToFirst(); p_cursor.isValid(); p_cursor.setToNext()) {
        if(people.elementAt(p_cursor).is_bald()) {
            bald.add(people.elementAt(p_cursor));
        }
    }
    cout<<"\nBald people : \n";
    for (b_cursor.setToFirst(); b_cursor.isValid(); b_cursor.setToNext()) {
        cout<<"\n"<<bald.elementAt(b_cursor).get_name();
    }
    cout<<"\n\nNumber of bald people : "<<bald.numberOfElements()<<"\n";

    return 0;
}


ΓòÉΓòÉΓòÉ 3.4. Equality Sequence ΓòÉΓòÉΓòÉ

A equality sequence is similar to a sequence. But unlike a sequence which has
no knowledge of the value of its elements a equality sequence supports element
equality as well.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a equality sequence in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.4.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.4.2. Declarations ΓòÉΓòÉΓòÉ

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);
  };
                  IREqualitySequence             (INumber
                                               numberOfElements = 100,
                                               IBoundIndicator =
                                               IUnbounded);
                  IREqualitySequence             (IREqualitySequence < Element > const&);
   IREqualitySequence < Element >&    operator =   (IREqualitySequence < Element > const&);
                 ~IREqualitySequence             ();
   Boolean        add                         (Element const&);
   Boolean        add                         (Element const&,
                                               ICursor&);
   void           addAllFrom                  (IREqualitySequence < 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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) const;
   Boolean        contains                    (Element const&) const;
   Boolean        containsAllFrom             (IREqualitySequence < 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 ==                 (IREqualitySequence < Element > const&) const;
   Boolean        operator !=                 (IREqualitySequence < Element > const&) const;
   void           unionWith                   (IREqualitySequence < Element > const&);
   void           intersectionWith            (IREqualitySequence < Element > const&);
   void           differenceWith              (IREqualitySequence < Element > const&);
   void           addUnion                    (IREqualitySequence < Element > const&,
                                               IREqualitySequence < Element > const&);
   void           addIntersection             (IREqualitySequence < Element > const&,
                                               IREqualitySequence < Element > const&);
   void           addDifference               (IREqualitySequence < Element > const&,
                                               IREqualitySequence < 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                     (IREqualitySequence < 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.5. Deque ΓòÉΓòÉΓòÉ

A deque is a collection of zero or more elements in which a linear order of
succession is maintained, with a first and a last element. Each element but the
first one has a predecessor, and each element but the last one has a successor.

The type and value of the deque elements are irrelevant and have no effect on
the behavior of the deque. Elements can be added at and deleted from either end
of the queue.


ΓòÉΓòÉΓòÉ 3.5.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Deque Class
and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.5.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The implementation variants that can be chosen for the Deque are depending on
the Building Block on which the Deque is based on, i.e.:

Sequence

A Deque has the same performance behavior as the Sequence in terms of time
complexities because it is based on it.


ΓòÉΓòÉΓòÉ 3.5.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Deque Class is illustrated in a  reftype=hd.coding example
provided with the IBM Class Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.5.3. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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&       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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <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                     (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&);
   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.5.4. Coding Example ΓòÉΓòÉΓòÉ

/*--------------------------------------------------------------------------*\
*                                                                            *
| Example program of Building Block dequeue
*                                                                            *
\*--------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <ideqseq.h>
#include <ideque.h>

/*---------------------- Building Block specification ----------------------*\
*                                                                            *
| A deque is specified,                                                      |
| It is to hold characters.                                                  |
*                                                                            *
\*--------------------------------------------------------------------------*/

typedef IDeque <char> Deque;
typedef IIterator <char> CharIterator;

class Print : public CharIterator
{
public:
   Boolean applyTo(char &c)
      {
      printf("Char in Deque == %c\n",c);
      return True;
      }
};

/*--------------------------------------------------------------------------*\
* Test variables                                                             *
\*--------------------------------------------------------------------------*/

char *String = "teqikbonfxjme vralz ogdya  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 the Deque, switching from one side of
   // the Deque to the other side of the Deque.


   printf("\n*** Example of deque use ***\n");

   for (i = 0; String[i] != 0; i ++) {          // For all characters:
      D.addAsLast(String[i]);                   //    - put it in the deque
      printf("Add as Last [%c]\n",String[i]);   //    - and give feedback
      }

   Print Aprinter;

   D.allElementsDo(Aprinter);

   printf("Current number of elements in the deque: %lu\n",
           D.numberOfElements());


   while (!D.isEmpty())            // As long as deque not empty
      {
      if (ReadFront)             // Read from front of Deque
         {
         C=D.firstElement();          // Get the character
         D.removeFirst();        // Delete it from the deque
         }
      else
         {
         D.lastElement();           // Get the character
         D.removeLast();         // Delete it from the deque
         }
      printf("%c",C);
      ReadFront = !ReadFront;    // Switch to other end of Deque
      }

   printf("\n*** End of example ***\n");

   return(0);
}


ΓòÉΓòÉΓòÉ 3.6. Queue ΓòÉΓòÉΓòÉ

A queue is a collection of zero or more elements in which a linear order of
succession is maintained, with a first and a last element. Each element but the
first one has a predecessor, and each element but the last one has a successor.

The type and value of the queue elements are irrelevant and have no effect on
the behavior of the queue.

Elements are added at one end (called back end or bottom).  Elements are
deleted from the other end (called the front end or top).  Consequently, the
elements of a queue are in chronological order.

A queue is characterized by a "first-in, first-out" (FIFO) behavior.


ΓòÉΓòÉΓòÉ 3.6.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Queue Class
and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.6.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The Queue implementation bases on another Class:

Deque

The performance characteristics of the Queue are the same as those of the
Deque.


ΓòÉΓòÉΓòÉ 3.6.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Queue Class is illustrated in a -- Link Reference QueueX not
found -- reftype=hd.coding example provided with the IBM Class Library:
Collection Classes.


ΓòÉΓòÉΓòÉ 3.6.3. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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&       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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) const;
   void           removeFirst                 ();
   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                     (IQueue < Element > const&,
                                               long (*comparisonFunction)
                                                  (Element const&,
                                                  Element const&)) const;
   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&));
   void           enqueue                     (Element const&);
   void           enqueue                     (Element const&,
                                               ICursor&);
   void           dequeue                     ();
   void           dequeue                     (Element&);
};


ΓòÉΓòÉΓòÉ 3.7. Stack ΓòÉΓòÉΓòÉ

A stack is a collection of zero or more elements in which a linear order of
succession is maintained, with a first and a last element. Each element but the
first one has a predecessor, and each element but the last one has a successor.
The type and value of the stack elements are irrelevant and have no effect on
the behavior of the stack.

Elements are added at and deleted from the same end, which is called 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.


ΓòÉΓòÉΓòÉ 3.7.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Stack Class
and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.7.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The Stack implementation bases on another Class:

Deque

The performance characteristics of the Stack are the same as those of the
Deque.


ΓòÉΓòÉΓòÉ 3.7.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Stack Class is illustrated in a  reftype=hd.coding example
provided with the IBM Class Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.7.3. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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&       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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) const;
   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                     (IStack < Element > const&,
                                               long (*comparisonFunction)
                                                  (Element const&,
                                                  Element const&)) const;
   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&));
   void           push                        (Element const&);
   void           push                        (Element const&,
                                               ICursor&);
   void           pop                         ();
   void           pop                         (Element&);
   Element const& top                         () const;
};


ΓòÉΓòÉΓòÉ 3.7.4. Coding Example ΓòÉΓòÉΓòÉ

/*--------------------------------------------------------------------------*\
*                                                                            *
| Example program of Building Block STACK.                                  |
*                                                                            *
\*--------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <istack.h>
#include <istkseq.h>

/*---------------------- Building Block specification ----------------------*\
*                                                                            *
| A stack is specified,                                                      |
| It is to be linked, unbouded and contains pointers to character strings.   |
*                                                                            *
\*--------------------------------------------------------------------------*/


/*--------------------------------------------------------------------------*\
* Test variables                                                             *
\*--------------------------------------------------------------------------*/

char *String[9] = {
   "the",
   "quick",
   "brown",
   "fox",
   "jumps",
   "over",
   "a",
   "lazy",
   "dog"
};

typedef IStack <char*> SimpleStack;
typedef IIterator <char*> StackIterator;
class PrintClass : public StackIterator
{
public:
   Boolean applyTo(char *&w)
      {
      printf("%s\n",w);
      return(True);
      }
};

/*--------------------------------------------------------------------------*\
* Main program                                                               *
\*--------------------------------------------------------------------------*/
int main()
{
   SimpleStack Stack1, Stack2;
   char *S;
   PrintClass Print;

   // We specify two stacks.
   // First all the strings are pushed on the first stack,
   // Next, they are popped from the first and pushed on the second,
   // Finally they are popped from the second and printed
   // This results are the strings printed in the original order.

   int i;

   printf("\n*** Example of STACK use ***\n");

   for (i = 0; i < 9; i ++) {                // Put all strings in the stack
      Stack1.push(String[i]);                // Add it as top of the stack
      }

   while (!Stack1.isEmpty()) {
      Stack1.pop(S);                         // Pop from stack 1
      Stack2.push(S);                        // Add it on top of stack 2
      }
   printf("Output using AllElementsDo():\n");
   Stack2.allElementsDo(Print);

   printf("----------------------------\n");

   while (!Stack2.isEmpty()) {
      Stack2.pop(S);
      printf("Popped from Stack 2: [%s]\n",S);
      }

   printf("\n*** End of example ***\n");

   return(0);
}


ΓòÉΓòÉΓòÉ 3.8. Set ΓòÉΓòÉΓòÉ

A set is an unordered collection of zero or more elements. The values of the
elements are relevant.

Any two elements are equal if they have the same value, otherwise they are not
equal (equal relation).  The elements of a set are unique, i.e. they are all of
different values, that is, there are no duplicates.  A request to add an
element which already exists, is ignored.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a set in respect to other flat collections.

The elements of a set are also called the members of the set.

If A and B are two sets, then B is called a subset of A or A a superset of B if
and only if all members of B are also members of A.  The union of A and B is
the set of elements which are members of A or B or both.  The intersection of A
and B is the set of elements which are members of both A and B.  The difference
of A and B (A minus B) is the set of elements which are members of A but not of
B.

Usually, elements are added to a set by means of the union operation.  Elements
are deleted from a set by using the intersection or difference operation.

It is convenient to offer additional operations, which allow adding a single
element to a set and deleting a specified element from a set.


ΓòÉΓòÉΓòÉ 3.8.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Set Class
and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.8.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The implementation variants that can be chosen for the Set are depending on the
Class on which the Set is based on, i.e.:

KeySet

A Set has the same performance characteristic as the KeySet it is based on.


ΓòÉΓòÉΓòÉ 3.8.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Set Class is illustrated in a  reftype=hd.coding example
provided with the IBM Class Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.8.3. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.8.4. Coding Example ΓòÉΓòÉΓòÉ

/*--------------------------------------------------------------------------*\
*                                                                            *
| Example of using the Building Block ISet.                                  |
*                                                                            *
\*--------------------------------------------------------------------------*/

#include <iostream.h>

/*---------------------- Building Block specification ----------------------*\
*                                                                            *
| A Set is specified.                                                        |
| It is based on a Sorted Mapping.                                           |
| The Sorted Mapping is based on a Linked Sequence.                          |
| The elements stored in the Set are integers.                               |
*                                                                            *
\*--------------------------------------------------------------------------*/

#include <iset.h>              //  ISetOnSortedMapping

typedef ISet <int> IntSet;

/*--------------------------------------------------------------------------*\
* Iterator                                                                   *
\*--------------------------------------------------------------------------*/
class PrintClass : public IIterator<int>
{
  public:
    virtual Boolean applyTo(int& i)
      { cout << " " << i << " "; return True;}
};


/*--------------------------------------------------------------------------*\
* Local prototype                                                            *
\*--------------------------------------------------------------------------*/
void    List(char *, IntSet &);

/*--------------------------------------------------------------------------*\
* Main program                                                               *
\*--------------------------------------------------------------------------*/
int main ()
{
   IntSet odd, prime;
   IntSet oddPrime, evenPrime;

   int One = 1, Two = 2, Three = 3, Five = 5, Seven = 7, Nine = 9;

   cout << "\n*** Example of ISet use ***\n";

// 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' giving 'EvenPrime'
   evenPrime.addDifference( prime, oddPrime);
   List("Even primes less than 10:", evenPrime);

   cout << "\n*** End of example ***\n";

   return(0);
}

/*--------------------------------------------------------------------------*\
* Local function                                                             *
\*--------------------------------------------------------------------------*/

void List(char *Message, IntSet &anIntSet)
{
   PrintClass Print;

   cout << Message;
   anIntSet.allElementsDo(Print);
   cout << "\n";
}


ΓòÉΓòÉΓòÉ 3.8.5. Coding Example ΓòÉΓòÉΓòÉ

#include <iset.h>

#include "cocktail.h"
#include <iostream.h>

typedef ISet <Cocktail> Cocktails;

void list_ingredients(Cocktails const&);

main() {
    Cocktails cocktail;

    Cocktail TS("Tequila Sunrise");
    TS.add_ingredient(Ingdt("Tequila"));
    TS.add_ingredient(Ingdt("Grenadine Sirup"));
    TS.add_ingredient(Ingdt("Orange Juice"));
    cocktail.add(TS);
    Cocktail SD("Screw Driver");
    SD.add_ingredient(Ingdt("Wodka"));
    SD.add_ingredient(Ingdt("Orange Juice"));
    cocktail.add(SD);
    Cocktail BD("Bull Dog");
    BD.add_ingredient(Ingdt("Rum"));
    BD.add_ingredient(Ingdt("Wodka"));
    BD.add_ingredient(Ingdt("Bitter Lemon"));
    cocktail.add(BD);

    list_ingredients(cocktail);

    Cocktails::Cursor ctailcursor(cocktail);

    cocktail.locate(BD, ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(False);
    list_ingredients(cocktail);

    cocktail.locate(BD,ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(True);
    cocktail.locate(TS, ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(False);
    list_ingredients(cocktail);


    return 0;
}

void list_ingredients(Cocktails const& cocktail) {
    Cocktails::Cursor ctailcursor(cocktail);
    IngSet neededIngdt;
    IngSet::Cursor ingcursor(neededIngdt);
    cout<<"\n\nTo make  : ";
    for(ctailcursor.setToFirst(); ctailcursor.isValid(); ctailcursor.setToNext()) {
        if (cocktail.elementAt(ctailcursor).get_make()) {
            cout<<"   "<<cocktail.elementAt(ctailcursor).get_name();
            neededIngdt.unionWith(cocktail.elementAt(ctailcursor).get_ingredients());
        }
    }
    cout<<"\nyou need : ";
    for (ingcursor.setToFirst(); ingcursor.isValid(); ingcursor.setToNext()) {
        cout<<"   "<<neededIngdt.elementAt(ingcursor).get_name();
    }
    cout<<"\n\n\n";
}

Header File:

#include <iset.h>

#include "cocktail.h"
#include <iostream.h>

typedef ISet <Cocktail> Cocktails;

void list_ingredients(Cocktails const&);

main() {
    Cocktails cocktail;

    Cocktail TS("Tequila Sunrise");
    TS.add_ingredient(Ingdt("Tequila"));
    TS.add_ingredient(Ingdt("Grenadine Sirup"));
    TS.add_ingredient(Ingdt("Orange Juice"));
    cocktail.add(TS);
    Cocktail SD("Screw Driver");
    SD.add_ingredient(Ingdt("Wodka"));
    SD.add_ingredient(Ingdt("Orange Juice"));
    cocktail.add(SD);
    Cocktail BD("Bull Dog");
    BD.add_ingredient(Ingdt("Rum"));
    BD.add_ingredient(Ingdt("Wodka"));
    BD.add_ingredient(Ingdt("Bitter Lemon"));
    cocktail.add(BD);

    list_ingredients(cocktail);

    Cocktails::Cursor ctailcursor(cocktail);

    cocktail.locate(BD, ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(False);
    list_ingredients(cocktail);

    cocktail.locate(BD,ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(True);
    cocktail.locate(TS, ctailcursor);
    cocktail.elementAt(ctailcursor).set_make(False);
    list_ingredients(cocktail);


    return 0;
}

void list_ingredients(Cocktails const& cocktail) {
    Cocktails::Cursor ctailcursor(cocktail);
    IngSet neededIngdt;
    IngSet::Cursor ingcursor(neededIngdt);
    cout<<"\n\nTo make  : ";
    for(ctailcursor.setToFirst(); ctailcursor.isValid(); ctailcursor.setToNext()) {
        if (cocktail.elementAt(ctailcursor).get_make()) {
            cout<<"   "<<cocktail.elementAt(ctailcursor).get_name();
            neededIngdt.unionWith(cocktail.elementAt(ctailcursor).get_ingredients());
        }
    }
    cout<<"\nyou need : ";
    for (ingcursor.setToFirst(); ingcursor.isValid(); ingcursor.setToNext()) {
        cout<<"   "<<neededIngdt.elementAt(ingcursor).get_name();
    }
    cout<<"\n\n\n";
}


ΓòÉΓòÉΓòÉ 3.9. KeySet ΓòÉΓòÉΓòÉ

KeySet is similar to a set, except that the elements can be accessed by key.

A KeySet is an unordered collection of zero or more elements which have a key.
The values of the elements are relevant. The value of the element is defined as
the value of its key. Any two elements are equal if they have the same key,
otherwise they are not equal.  The keys of a KeySet are unique, i.e. they are
all of different values, that is, there are no duplicates.  A request to add an
element whose key already exists, is rejected. "Figure: Behavior of add for
unique and multiple collections" illustrates the different behaviour for map,
relation, key set, and key bag when adding identical elements and elements with
the same key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a KeySet in respect to other flat collections.

The key can be any part of the element, but must be the same part for all
elements of a KeySet.  The remainder of the element is called the element body.
The element body is not relevant for the behavior of the KeySet. Nevertheless,
it can be replaced with new information.  The key of an element can not be
changed.

The set terminology applies to KeySets as well.

Besides the set operations a KeySet allows addition, retrieval, replacement and
deletion of single elements using the key, and it is possible to check whether
an element with a specified key is contained in the KeySet.


ΓòÉΓòÉΓòÉ 3.9.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the KeySet
Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.9.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The KeySet implementation can base on one of the following Classs:

AVL Tree  This is the default.

B* Tree

Hash Table

Key-Sorted Set

The performance characteristics of the KeySet depend on the Class on which the
KeySet is based.


ΓòÉΓòÉΓòÉ 3.9.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the KeySet Class is illustrated in a -- Link Reference DictX not
found -- reftype=hd.coding example provided with the IBM Class Library:
Collection Classes.


ΓòÉΓòÉΓòÉ 3.9.3. Declarations ΓòÉΓòÉΓòÉ

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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.10. Sorted Set ΓòÉΓòÉΓòÉ

A sorted set is a collection of zero or more elements in which a linear order
of succession is maintained, with a first and a last element. Each element but
the first one has a predecessor, and each element but the last one has a
successor. The values of the elements are relevant.

The elements appear in an order in such a way that the value of each element is
less than or equal to the value of its successor, if any.

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.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a sorted set in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.10.1. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.11. Key-Sorted Set ΓòÉΓòÉΓòÉ

A key-sorted set is a collection of zero or more elements with key. in which a
linear order of succession is maintained, with a first and a last element. Each
element but the first one has a predecessor, and each element but the last one
has a successor. The values of the elements are relevant. The value of the
element is defined as the value of its key.

The elements have a key, which can be used to access the elements, and there is
an ordering relation defined on the set of key values. The elements appear in
an order in such a way that the key of each element is less than or equal to
the key of its successor, if any.

The element with the smallest key currently in a key-sorted set, is called the
first element.  The element with the largest key is called the last element.

The key can be any part of the element, but must be the same part for all
elements of a key-sorted set.  The remainder of the element is called the
element body. The element body is not relevant for the behavior of the
key-sorted set. Nevertheless, it can be replaced with new information.  The key
of an element can not be changed.

When an element is added, it is placed in the key-sorted set according to the
defined ordering relation.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a key-sorted set in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.11.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Key-Sorted
Set Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.11.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The implementation variants for the Key-Sorted Set are depending on the Class
on which the Key-Sorted Set is based.

The Key-Sorted Set implementation can base on one of the following Classs:

AVL Tree

B* Tree

Sequence

The performance characteristics of the Key-Sorted Set depend on the Class on
which the Key-Sorted Set is based.


ΓòÉΓòÉΓòÉ 3.11.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Key-Sorted Set Class is illustrated in a -- Link Reference
KslistX not found -- reftype=hd.coding example provided with the IBM Class
Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.11.3. Declarations ΓòÉΓòÉΓòÉ

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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.12. Priority Queue ΓòÉΓòÉΓòÉ

A priority queue is a collection of zero or more elements in which a linear
order of succession is maintained, with a first and a last element. The
priority of the elements is relevant. The priority is any part of the element,
but it must be the same part for all elements.

When an element is added, it is placed in the queue according to its priority.
For access or deletion, the element with the largest priority is identified and
deleted from the queue.

A priority queue has a "largest-in, first-out" behavior.

A variant of the priority queue is obtained by replacing the term "largest" by
the term "smallest".


ΓòÉΓòÉΓòÉ 3.12.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Priority
Queue Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 3.12.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The implementation variants that can be chosen for the Priority Queue are
depending on the Class on which the Priority Queue is based on, i.e.:

Key-Sorted Set

A Priority Queue has the same performance characteristic as the Key-Sorted Set
it is based on.


ΓòÉΓòÉΓòÉ 3.12.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Priority Queue Class is illustrated in a -- Link Reference
PrtyqX not found -- reftype=hd.coding example provided with the IBM Class
Library: Collection Classes.


ΓòÉΓòÉΓòÉ 3.12.3. Declarations ΓòÉΓòÉΓòÉ



to be completed


ΓòÉΓòÉΓòÉ 3.13. Bag ΓòÉΓòÉΓòÉ

A bag is similar to a set, except that the collection of elements may contain
duplicates.  A request to add an element which already exists is not ignored.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a bag in respect to other flat collections.

The set terminology applies to bags as well.

The following rules apply for duplicates: If bag P contains the element el-x m
times and bag Q contains the element el-x n times, then the union of P and Q
contains the element el-x m+n times, the intersection of P and Q contains the
element el-x MIN(m,n) times, and the difference of P and Q contains the element
el-x m-n times if m is greater than n, and zero times if m is equal to or
smaller than n.

Usually elements are added to a bag by means of the union operation.  Elements
are deleted from a bag using the intersection or difference operation.
However, it is convenient to offer operations which allow adding a single
element to a bag, or deleting a specified element from a bag.


ΓòÉΓòÉΓòÉ 3.13.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.13.2. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.14. Key Bag ΓòÉΓòÉΓòÉ

A key bag is similar to a bag except that all elements have a key.

"Figure: Behavior of add for unique and multiple collections" illustrates the
different behaviour for map, relation, key set, and key bag when adding
identical elements and elements with the same key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a key bag in respect to other flat collections.


ΓòÉΓòÉΓòÉ 3.14.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.14.2. Declarations ΓòÉΓòÉΓòÉ

template  <class Element, class Key >
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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.15. Sorted Bag ΓòÉΓòÉΓòÉ

A sorted bag is similar to a bag except that all elements are sorted.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a sorted bag in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.15.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.15.2. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.16. Key Sorted Bag ΓòÉΓòÉΓòÉ

A key sorted bag is similar to a sorted bag except that all elements have a
key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a key sorted bag in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.16.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.16.2. Declarations ΓòÉΓòÉΓòÉ

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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.17. Map ΓòÉΓòÉΓòÉ

A map is an unordered collection of zero or more elements which have a key. The
values of the elements are relevant.

The keys of the elements are unique. That is you can't add an element if there
is already an element in the map with the same key. "Figure: Behavior of add
for unique and multiple collections" illustrates the different behaviour for
map, relation, key set, and key bag when adding identical elements and elements
with the same key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a map in respect to other flat collections.


ΓòÉΓòÉΓòÉ 3.17.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.17.2. Declarations ΓòÉΓòÉΓòÉ

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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.18. Sorted Map ΓòÉΓòÉΓòÉ

A sorted map is similar to a map except that all elements are sorted by the
value of the key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a sorted map in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.18.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.18.2. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.18.3. Coding Example ΓòÉΓòÉΓòÉ

#include "parcel.h"

#include <isrtmap.h>
#include <iostream.h>

ostream& operator<<(ostream& s, Parcel p) {
    if (p.now().getPlace()!=p.dest().getPlace()) {
        return s<< p.getID()<<": From "<<p.orig().getPlace()<<"("
         <<p.orig().getTime()<<") to "<<p.dest().getPlace()<<" is now at "
         <<p.now().getPlace()<<"("<<p.now().getTime()<<")";
    }
    else {
        return s<<p.getID()<<": From "<<p.orig().getPlace()<<"("
         <<p.orig().getTime()<<") to "<<p.now().getPlace()<<"("
         <<p.now().getTime()<<") delivered.";
    }
}

typedef ISortedMap<Parcel, char*> ParcelService;

void list(ParcelService const& p);

void update(ParcelService const& p, ParcelService& d);

main() {

    ParcelService ps;
    ParcelService delivered;

    ps.add(Parcel("Lobito", "Athen", 26.02, "26LoAt"));
    ps.add(Parcel("Angusta", "Canberra", 27.02, "27AnCa"));
    ps.add(Parcel("Wassenaar", "Shinagawa", 25.02, "25WaSh"));
    ps.add(Parcel("Kanpur", "Uster", 25.03, "25KaUs"));
    update(ps, delivered);
    list(ps);

    ps.elementWithKey("26LoAt").arrivedAt("Luanda", 28.02);
    ps.elementWithKey("27AnCa").arrivedAt("Atlanta", 28.02);
    ps.elementWithKey("25WaSh").arrivedAt("Amsterdam", 25.02);
    ps.elementWithKey("25KaUs").arrivedAt("Delhi", 25.03);
    update(ps, delivered);
    list(ps);

    ps.elementWithKey("26LoAt").arrivedAt("Athen", 28.02);
    ps.elementWithKey("25KaUs").arrivedAt("Zuerich", 26.03);
    update(ps, delivered);
    list(ps);
    list(delivered);

    ps.removeElementWithKey("26LoAt");

    ps.add(Parcel("Kanpur", "Uster", 27.04, "27KaUs"));
    ps.add(Parcel("Wassenaar","Shinagawa", 15.02, "25WaSh"));
    ps.elementWithKey("25KaUs").arrivedAt("Uster", 29.03);
    update(ps, delivered);
    list(ps);


    ParcelService::Cursor pscursor(ps);

    for (pscursor.setToFirst(); pscursor.isValid(); pscursor.setToNext()) {
        ps.elementAt(pscursor).arrivedAt(ps.elementAt(pscursor).dest().getPlace(), 30.02);
    }
    update(ps, delivered);
    list(ps);
    if (delivered.containsAllFrom(ps)) {
        cout<<"All delivered \n";
    }
    else {
        cout<<"Something very wrong is happening here \n";
    }
        return 0;
}


void list(ParcelService const& p) {
    ParcelService::Cursor pcursor(p);
    for(pcursor.setToFirst(); pcursor.isValid(); pcursor.setToNext()) {
        cout<<p.elementAt(pcursor)<<"\n";
    }
    cout<<"\n";
}

void update(ParcelService const& p, ParcelService& d) {
    ParcelService::Cursor pc(p);

    for (pc.setToFirst(); pc.isValid(); pc.setToNext()) {
        if (!d.contains(p.elementAt(pc))) {
            if (p.elementAt(pc).now().getPlace()==p.elementAt(pc).dest().getPlace()) {
                d.add(p.elementAt(pc));
            }
        }
    }
}
Header File:

#include "parcel.h"

#include <isrtmap.h>
#include <iostream.h>

ostream& operator<<(ostream& s, Parcel p) {
    if (p.now().getPlace()!=p.dest().getPlace()) {
        return s<< p.getID()<<": From "<<p.orig().getPlace()<<"("
         <<p.orig().getTime()<<") to "<<p.dest().getPlace()<<" is now at "
         <<p.now().getPlace()<<"("<<p.now().getTime()<<")";
    }
    else {
        return s<<p.getID()<<": From "<<p.orig().getPlace()<<"("
         <<p.orig().getTime()<<") to "<<p.now().getPlace()<<"("
         <<p.now().getTime()<<") delivered.";
    }
}

typedef ISortedMap<Parcel, char*> ParcelService;

void list(ParcelService const& p);

void update(ParcelService const& p, ParcelService& d);

main() {

    ParcelService ps;
    ParcelService delivered;

    ps.add(Parcel("Lobito", "Athen", 26.02, "26LoAt"));
    ps.add(Parcel("Angusta", "Canberra", 27.02, "27AnCa"));
    ps.add(Parcel("Wassenaar", "Shinagawa", 25.02, "25WaSh"));
    ps.add(Parcel("Kanpur", "Uster", 25.03, "25KaUs"));
    update(ps, delivered);
    list(ps);

    ps.elementWithKey("26LoAt").arrivedAt("Luanda", 28.02);
    ps.elementWithKey("27AnCa").arrivedAt("Atlanta", 28.02);
    ps.elementWithKey("25WaSh").arrivedAt("Amsterdam", 25.02);
    ps.elementWithKey("25KaUs").arrivedAt("Delhi", 25.03);
    update(ps, delivered);
    list(ps);

    ps.elementWithKey("26LoAt").arrivedAt("Athen", 28.02);
    ps.elementWithKey("25KaUs").arrivedAt("Zuerich", 26.03);
    update(ps, delivered);
    list(ps);
    list(delivered);

    ps.removeElementWithKey("26LoAt");

    ps.add(Parcel("Kanpur", "Uster", 27.04, "27KaUs"));
    ps.add(Parcel("Wassenaar","Shinagawa", 15.02, "25WaSh"));
    ps.elementWithKey("25KaUs").arrivedAt("Uster", 29.03);
    update(ps, delivered);
    list(ps);


    ParcelService::Cursor pscursor(ps);

    for (pscursor.setToFirst(); pscursor.isValid(); pscursor.setToNext()) {
        ps.elementAt(pscursor).arrivedAt(ps.elementAt(pscursor).dest().getPlace(), 30.02);
    }
    update(ps, delivered);
    list(ps);
    if (delivered.containsAllFrom(ps)) {
        cout<<"All delivered \n";
    }
    else {
        cout<<"Something very wrong is happening here \n";
    }
        return 0;
}


void list(ParcelService const& p) {
    ParcelService::Cursor pcursor(p);
    for(pcursor.setToFirst(); pcursor.isValid(); pcursor.setToNext()) {
        cout<<p.elementAt(pcursor)<<"\n";
    }
    cout<<"\n";
}

void update(ParcelService const& p, ParcelService& d) {
    ParcelService::Cursor pc(p);

    for (pc.setToFirst(); pc.isValid(); pc.setToNext()) {
        if (!d.contains(p.elementAt(pc))) {
            if (p.elementAt(pc).now().getPlace()==p.elementAt(pc).dest().getPlace()) {
                d.add(p.elementAt(pc));
            }
        }
    }
}


ΓòÉΓòÉΓòÉ 3.19. Relation ΓòÉΓòÉΓòÉ

A relation is an unordered collection of zero or more elements which have a
key. The values of the elements are relevant.

The keys of the elements are non unique. That is you can add an element if
there is already an element in the relation with the same key. "Figure:
Behavior of add for unique and multiple collections" illustrates the different
behaviour for map, relation, key set, and key bag when adding identical
elements and elements with the same key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a relation in respect to other flat collections.


ΓòÉΓòÉΓòÉ 3.19.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.19.2. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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.20. Sorted Relation ΓòÉΓòÉΓòÉ

A sorted relation is similar to a relation except that all elements are sorted
by the value of the key.

"Figure: Combination of collection properties" gives an overview of the
properties and the position of a sorted relation in respect to other flat
collections.


ΓòÉΓòÉΓòÉ 3.20.1. Customizing ΓòÉΓòÉΓòÉ

     To be completed ..........


ΓòÉΓòÉΓòÉ 3.20.2. Declarations ΓòÉΓòÉΓòÉ

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,
                                               IBoundIndicator =
                                               IUnbounded);
                  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 <Element>&);
   Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const;
   Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) 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;
};


ΓòÉΓòÉΓòÉ 4. subj='Tree Classes'.Reference Manual - Tree Classes ΓòÉΓòÉΓòÉ

The following chapters describe the tree classes of the library.

As for flat collections you will find all function described in a separate
chapter (List of Functions) separeted from the decsriptions for the tree
classes.


ΓòÉΓòÉΓòÉ 4.1. List of Functions ΓòÉΓòÉΓòÉ


ΓòÉΓòÉΓòÉ 4.1.1. addAsChild ΓòÉΓòÉΓòÉ

 void addAsChild (ITreeCursor const&
                      IPosition,
                      Element const&) = 0;

Add the given element as child with the given position of the node (of this
tree) denoted by the given cursor.
Precondition:

o The cursor must belong to the collection and the cursor must point to an
  element of the collection..
o 1 <= position <= children.
o The node denoted by the given cursor (of this tree) must not have a child at
  the given position.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o IPositionInvalidException
o IChildAlreadyExistsException


ΓòÉΓòÉΓòÉ 4.1.2. addAsRoot ΓòÉΓòÉΓòÉ

 void addAsRoot (Element const&) = 0;

Add the given element as root of the tree.
Precondition: The tree must not have a root, that means it must be empty.
Exceptions:

o IMemoryExhaustedException
o IRootAlreadyExistsException


ΓòÉΓòÉΓòÉ 4.1.3. allElementsDo, allSubtreeElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (IConstantIterator <Element>&,
                     ITreeIterationOrder) const = 0;

 Boolean allSubtreeElementsDo (ITreeCursor const&,
                     IConstantIterator <Element>&,                      ITreeIterationOrder) const = 0;

Call 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 or add elements of the tree.
ReturnValue: True if the applyTo function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 4.1.4. allElementsDo, allSubtreeElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (Boolean (*function)
                         (Element const&, void*),                      ITreeIterationOrder, void*
additionalArgument = 0)                          const = 0;

 Boolean allSubtreeElementsDo (ITreeCursor const&,
                     Boolean (*function)                          (Element const&, void*),
ITreeIterationOrder, void* additionalArgument = 0)                          const = 0;

Call 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 allElementsDo function (without a
subtree cursor argument) iterates over all elements of the tree.
Note: The given function may not remove or add elements to the tree.
ReturnValue: True if the given function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 4.1.5. allElementsDo, allSubtreeElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (IIterator <Element>&,
                     ITreeIterationOrder) = 0;

 Boolean allSubtreeElementsDo (ITreeCursor const&,
                     IIterator <Element>&,                      ITreeIterationOrder) = 0;

Call 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.
Additional arguments can be passed to the applyTo function using the
additionalArgument.
Note: The applyTo function may not remove or add elements from or to the tree.
ReturnValue: True if the applyTo function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 4.1.6. allElementsDo, allSubtreeElementsDo ΓòÉΓòÉΓòÉ

 Boolean allElementsDo (Boolean (*function)
(Element&, void*),                      ITreeIterationOrder, void* additionalArgument = 0) =
0;

 Boolean allSubtreeElementsDo (ITreeCursor const&,
                     Boolean (*function) (Element&, void*),                      ITreeIterationOrder, void*
additionalArgument = 0) = 0;

Call 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 the additionalArgument. The allElementsDo function
(without a subtree cursor argument) iterates over all elements of the tree.
Note: The given function may not remove or add elements from or to the tree.
ReturnValue: True if the given function returns true for every element it is
applied to.


ΓòÉΓòÉΓòÉ 4.1.7. attachAsChild, attachSubtreeAsChild ΓòÉΓòÉΓòÉ

 void attachAsChild (ITreeCursor const&,
                     IPosition,                      ITree < Element,                          children >&) = 0;

 void attachSubtreeAsChild (ITreeCursor const&,
                     IPosition,                      ITree < Element,                          children >&                      ITreeCursor
const& subtree) = 0;

Copy the subtree denoted by the given subtree cursor of the given tree as child
with the given position of the node (of this tree) denoted by the given cursor
and remove this subtree from the given tree. The attachAsChild function
(without a subtree cursor argument) copies and removes the whole given tree.
Precondition:

o The cursor must belong to the collection and the cursor must point to an
  element of the collection..
o The subtree cursor must point to an element of the given tree.
o 1 <= position <= children.
o The node denoted by the given cursor (of this tree) must not have a child at
  the given position.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o IPositionInvalidException
o IChildAlreadyExistsException


ΓòÉΓòÉΓòÉ 4.1.8. attachAsRoot, attachSubtreeAsRoot ΓòÉΓòÉΓòÉ

 void attachAsRoot (ITree < Element,
                         children >&) = 0;

 void attachSubtreeAsRoot (ITree < Element,
                         children >&                      ITreeCursor const&) = 0;

Copy the subtree denoted by the given cursor of the given tree to (the root of)
this tree and remove this subtree from the given tree. The attachAsRoot
function (without a cursor argument) copies and removes the whole given tree.
Precondition:

o The cursor must belong to the collection and the cursor must point to an
  element of the collection..
o The tree must not have a root, that means it must be empty.

Exceptions:

o IMemoryExhaustedException
o ICursorInvalidException
o IRootAlreadyExistsException


ΓòÉΓòÉΓòÉ 4.1.9. Constructor ΓòÉΓòÉΓòÉ

 ITree ();

Construct a tree. The tree is initially empty, that means it contains no node.


ΓòÉΓòÉΓòÉ 4.1.10. Copy Constructor ΓòÉΓòÉΓòÉ

 ITree (ITree < Element, children > const&);

Construct a tree by copying all elements from the given tree.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 4.1.11. copy, copySubtree ΓòÉΓòÉΓòÉ

 void copy (ITree < Element,
                         children > const&) = 0;

 void copySubtree (ITree < Element,
                         children > const&                      ITreeCursor const&) = 0;

Remove all elements from this tree and copy 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.
Precondition: The cursor must point to an element of the given tree.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 4.1.12. Destructor ΓòÉΓòÉΓòÉ

 ~ITree ();

Remove all elements from this tree.
Side Effect: All cursors of the tree become undefined.


ΓòÉΓòÉΓòÉ 4.1.13. elementAt ΓòÉΓòÉΓòÉ

 Element& elementAt (ITreeCursor const&) = 0;

Returns (a reference to) the element pointed to by the given cursor.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.14. elementAt ΓòÉΓòÉΓòÉ

 Element const& elementAt (ITreeCursor const&) const = 0;

Returns (a constant reference to) the element pointed to by the given cursor.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.15. hasChild ΓòÉΓòÉΓòÉ

 Boolean hasChild (IPosition,
                     ITreeCursor const&) const = 0;

Return true if the node pointed to by the given cursor has a child child at the
given position.
Precondition:

o The cursor must belong to the collection and the cursor must point to an
  element of the collection..
o 1 <= position <= children.

Exceptions:

o ICursorInvalidException
o IPositionInvalidException


ΓòÉΓòÉΓòÉ 4.1.16. isEmpty ΓòÉΓòÉΓòÉ

 Boolean isEmpty () const = 0;

Return true if the tree is empty.


ΓòÉΓòÉΓòÉ 4.1.17. isLeaf ΓòÉΓòÉΓòÉ

 Boolean isLeaf (ITreeCursor const&) const = 0;

Return true if the node pointed to by the given cursor is a leaf node of the
tree, that means it has no children.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.18. isRoot ΓòÉΓòÉΓòÉ

 Boolean isRoot (ITreeCursor const&) const = 0;

Return true if the node pointed to by the given cursor is the root node of the
tree.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.19. newCursor ΓòÉΓòÉΓòÉ

 ITreeCursor* newCursor () const = 0;

Create a cursor for the tree. The cursor is initially invalid.
ReturnValue: Pointer to the cursor.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 4.1.20. numberOfChildren ΓòÉΓòÉΓòÉ

 INumber numberOfChildren () const = 0;

Return the number of children a node can possibly have. The actual number of
children of any node will always be less or equal to this number.


ΓòÉΓòÉΓòÉ 4.1.21. numberOfElements, numberOfSubtreeElements ΓòÉΓòÉΓòÉ

 INumber numberOfElements () const = 0;
 INumber numberOfSubtreeElements (ITreeCursor const&) const = 0;

Return the number of elements which the subtree denoted by the given cursor
contains. The subtree root and inner as well as leaf nodes are counted. The
numberOfElements function (without a cursor argument) counts the number of
elements in the whole tree.


ΓòÉΓòÉΓòÉ 4.1.22. numberOfLeaves, numberOfSubtreeLeaves ΓòÉΓòÉΓòÉ

 INumber numberOfLeaves () const = 0;
 INumber numberOfSubtreeLeaves (ITreeCursor const&) const = 0;

Return the number of leaf elements which 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.


ΓòÉΓòÉΓòÉ 4.1.23. operator = ΓòÉΓòÉΓòÉ

 ITree < Element, children >&
operator = (ITree < Element,                          children > const&);

Remove all elements from this tree and copy the given tree to (the root of)
this tree.
ReturnValue: (A reference to) this tree.
Side Effect: All cursors of this tree become undefined.
Precondition: none.
Exceptions: IMemoryExhaustedException


ΓòÉΓòÉΓòÉ 4.1.24. position ΓòÉΓòÉΓòÉ

 INumber position (ITreeCursor const&) const = 0;

Return the position of the node pointed to by the given cursor as child with
respect to its parent node. The position of the root node is 1.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.25. removeAll, removeSubtree ΓòÉΓòÉΓòÉ

 void removeAll () = 0;
 void removeSubtree (ITreeCursor const&) = 0;

Remove 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 belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.26. replaceAt ΓòÉΓòÉΓòÉ

 void replaceAt (ITreeCursor const&,
Element const&) = 0;

Replaces the element pointed to by the cursor with the given element.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.27. setToChild ΓòÉΓòÉΓòÉ

 Boolean setToChild (IPosition,
                     ITreeCursor&) const = 0;

Set the cursor to the child with the given position of the node denoted by the
given cursor (of this tree). If this child does not exist, the given cursor
will become invalid.
ReturnValue: True if the child exists.
Precondition:

o The cursor must belong to the collection and the cursor must point to an
  element of the collection..
o 1 <= position <= children.

Exceptions:

o ICursorInvalidException
o IPositionInvalidException


ΓòÉΓòÉΓòÉ 4.1.28. setToFirst ΓòÉΓòÉΓòÉ

 Boolean setToFirst (ITreeCursor&,
                     ITreeIterationOrder) const = 0;

Set the cursor to the first node in the given iteration order. If the tree is
empty, the given cursor will become invalid.
ReturnValue: True if the tree is not empty.
Precondition: The cursor must belong to this tree.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.29. setToFirstExistingChild ΓòÉΓòÉΓòÉ

 Boolean setToFirstExistingChild (ITreeCursor&) const = 0;

Set the cursor to the first child of the node denoted by the given cursor (of
this tree). If the node has no child (that means the node denotes a leaf node
of this tree), the given cursor will become invalid.
ReturnValue: True if the node has a child.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.30. setToLast ΓòÉΓòÉΓòÉ

 Boolean setToLast (ITreeCursor&,
                     ITreeIterationOrder) const = 0;

Set the cursor to the last node in the given iteration order. If the tree is
empty, the given cursor will become invalid.
ReturnValue: True if the tree is not empty.
Precondition: The cursor must belong to this tree.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.31. setToLastExistingChild ΓòÉΓòÉΓòÉ

 Boolean setToLastExistingChild (ITreeCursor&) const = 0;

Set the cursor to the last child of the node denoted by the given cursor (of
this tree). If the node has no child (that means the node denotes a leaf node
of this tree), the given cursor will become invalid.
ReturnValue: True if the node has a child.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.32. setToNext ΓòÉΓòÉΓòÉ

 Boolean setToNext (ITreeCursor&,
                     ITreeIterationOrder) const = 0;

Set the cursor to the next node in the given iteration order. If there is no
next node, the given cursor will become invalid.
ReturnValue: True if the given cursor does not point to the last node (in
iteration order).
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.33. setToNextExistingChild ΓòÉΓòÉΓòÉ

 Boolean setToNextExistingChild (ITreeCursor&) const = 0;

Set the cursor to the next existing sibling of the node denoted by the given
cursor (of this tree). If the node has no next sibling (that means the node is
the last existing child of its parent), the given cursor will become invalid.
ReturnValue: True if the node has a next sibling.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.34. setToParent ΓòÉΓòÉΓòÉ

 Boolean setToParent (ITreeCursor&) const = 0;

Set the cursor to the parent of the node denoted by the given cursor (of this
tree). If the node has no parent (that means the node denotes the root node of
this tree), the given cursor will become invalid.
ReturnValue: True if the node has a parent.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.35. setToPrevious ΓòÉΓòÉΓòÉ

 Boolean setToPrevious (ITreeCursor&,
                     ITreeIterationOrder) const = 0;

Set the cursor to the previous node in the given iteration order. If there is
no previous node, the given cursor will become invalid.
ReturnValue: True if the given cursor does not point to the first node (in
iteration order).
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.36. setToPreviousExistingChild ΓòÉΓòÉΓòÉ

 Boolean setToPreviousExistingChild (ITreeCursor&) const = 0;

Set the cursor to the previous existing sibling of the node denoted by the
given cursor (of this tree). If the node has no previous sibling (that means
the node is the first existing child of its parent), the given cursor will
become invalid.
ReturnValue: True if the node has a previous sibling.
Precondition: The cursor must belong to the collection and the cursor must
point to an element of the collection..
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.1.37. setToRoot ΓòÉΓòÉΓòÉ

 Boolean setToRoot (ITreeCursor&) const = 0;

Set the cursor to the root node of the tree. If the tree is empty (i.e. if no
root node exists) the given cursor will become invalid.
ReturnValue: True if the tree is not empty.
Precondition: The cursor must belong to this tree.
Exceptions: ICursorInvalidException


ΓòÉΓòÉΓòÉ 4.2. N-ary Tree ΓòÉΓòÉΓòÉ

An n-ary tree is a special tree where each node can have up to n children.

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.
For every two nodes there exists a unique path connecting them.  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. Suppose N is a node and T-1, T-2, R-2, ..., R-k, respectively.  We can
    construct a new tree 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, N.

Associated with each node is a data item called element.

Nodes without children are called leaves or terminals.  The number of children
of 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.

Each node of an n-ary tree can have up to "n" children.

For most trees used in practice, the children of a node are ordered from
"left-to-right".  If two siblings in such a tree exchange their place, the tree
as it was before is different from the tree as it is after the exchange,
because the children of that node appear in a different order.


ΓòÉΓòÉΓòÉ 4.2.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the N-ary Tree
Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 4.2.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The N-ary Tree Class implements a linked and unbounded data structure  (also
known as Arbitrary Tree) or a tabular and bounded data structure. No other
implementation variants can be selected.


ΓòÉΓòÉΓòÉ 4.2.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the N-ary Tree Class is illustrated in a -- Link Reference NarytrX
not found -- reftype=hd.coding example provided with the IBM Class Library:
Collection Classes.


ΓòÉΓòÉΓòÉ 4.2.3. Declarations ΓòÉΓòÉΓòÉ




to be completed ......



ΓòÉΓòÉΓòÉ 4.3. Binary Tree ΓòÉΓòÉΓòÉ

A binary tree is a special tree where each node can have at most two children.

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.
For every two nodes there exists a unique path connecting them.  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. Suppose N is a node and T-1, T-2 are trees with roots R-1, R-2,
    respectively.  We can construct a new tree by making N the parent of the
    nodes R-1, R-2.  In this new tree, N is the root and T-1, T-2 are the
    subtrees of the root N.  Nodes R-1, R-2 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
of 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.

Each node of a binary tree can have at most "two" children.

For most trees used in practice, the children of a node are ordered from
"left-to-right". The children of a node are called the left and the right
child.  If the left and the right child exchange their place, the tree after
the exchange is different from the tree as it was before, because the children
of that node appear in a different order.


ΓòÉΓòÉΓòÉ 4.3.1. Customizing ΓòÉΓòÉΓòÉ

This section describes the implementation variants supported by the Binary Tree
Class and the generic parameters available for selecting these variants.


ΓòÉΓòÉΓòÉ 4.3.1.1. Implementation Variants ΓòÉΓòÉΓòÉ

The Binary Tree Class always implements a linked and unbounded data structure.
No other implementation variants can be selected.

Time complexity for element lookup is O( N ), where N is the total number of
elements in the tree.


ΓòÉΓòÉΓòÉ 4.3.2. Usage Notes ΓòÉΓòÉΓòÉ

The use of the Binary Tree Class is illustrated in a -- Link Reference BintreX
not found -- reftype=hd.coding example provided with the IBM Class Library:
Collection Classes.


ΓòÉΓòÉΓòÉ 4.3.3. Declarations ΓòÉΓòÉΓòÉ




to be completed ......



ΓòÉΓòÉΓòÉ 5. subj='Auxiliary Classes'.Reference Manual - Auxiliary Classes ΓòÉΓòÉΓòÉ

The following chapters describe the auxiliary classes of the library.


ΓòÉΓòÉΓòÉ 5.1. Cursor ΓòÉΓòÉΓòÉ

The cursor class is the base class for the cursor classes in each collection.

Cursors explains the concepts and usage of cursors.


ΓòÉΓòÉΓòÉ 5.1.1. Declarations ΓòÉΓòÉΓòÉ

class ICursor {
public:
  virtual        Boolean setToFirst () = 0;
  virtual        Boolean setToNext  () = 0;
  virtual        Boolean isValid    () const = 0;
  virtual        void    invalidate () = 0;
};


ΓòÉΓòÉΓòÉ 5.2. Iterator Class ΓòÉΓòÉΓòÉ

The &iter. provides one possibility to iterate over all elements in a
collection.

Using Iterators explains the concepts and usage of iterations.


ΓòÉΓòÉΓòÉ 5.2.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element >
class IIterator {
public:
  virtual Boolean applyTo (Element&) = 0;
};
template < class Element >
class IConstantIterator {
public:
  virtual Boolean applyTo (Element const&) = 0;
};


ΓòÉΓòÉΓòÉ 5.3. Reference Class ΓòÉΓòÉΓòÉ

The reference class provides the means to manage objects and garbage
collection.

Values vs. (Managed) Objects and hdref refid=garb. explain the concepts and
usage in detail.


ΓòÉΓòÉΓòÉ 5.3.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element >
class IRef {
protected:
  Element *ivPtr;
public:
  IRef () : ivPtr (0) {}
  IRef (Element *ptr) : ivPtr (ptr) {}
  operator Element&       ()       { return *ivPtr; }
  operator Element const& () const { return *ivPtr; }
  Element*       operator & ()       { return ivPtr; }
  Element const* operator & () const { return ivPtr; }
  friend inline Element&       elementForOps (IRef < Element > &     ref)
  { return *ref.ivPtr; }
  friend inline Element const& elementForOps (IRef < Element > const&ref)
  { return *ref.ivPtr; }
};
template < class Element >
class IMgRef {
protected:
  struct PtrRc {
    Element *ivPtr;
    unsigned int ivRc;
    PtrRc (Element *ptr) : ivPtr (ptr), ivRc (1) {}
    ~PtrRc () { delete ivPtr; }
  } *ivPtrRc;
public:
  IMgRef () : ivPtrRc (0) {}
  IMgRef (Element *ptr) {
    ivPtrRc = new PtrRc (ptr);
  }
  IMgRef (Element const& e) {
    ivPtrRc = new PtrRc (new Element (e));
  }
  IMgRef (IMgRef < Element > const& ref) {
    ivPtrRc = ref.ivPtrRc;
    ivPtrRc->ivRc++;
  }
  ~IMgRef () {
    if (ivPtrRc && --ivPtrRc->ivRc == 0) delete ivPtrRc;
  }
  IMgRef < Element >& operator= (IMgRef < Element > const& ref) {
    if (ivPtrRc == ref.ivPtrRc) return *this;
    if (ivPtrRc && --ivPtrRc->ivRc == 0) delete ivPtrRc;
    ivPtrRc = ref.ivPtrRc;
    ivPtrRc->ivRc++;
    return *this;
  }
  operator Element&       ()       { return *ivPtrRc->ivPtr; }
  operator Element const& () const { return *ivPtrRc->ivPtr; }
  friend inline Element&       elementForOps (IMgRef < Element > &     ref)
  { return *ref.ivPtrRc->ivPtr; }
  friend inline Element const& elementForOps (IMgRef < Element > const&ref)
  { return *ref.ivPtrRc->ivPtr; }
};


ΓòÉΓòÉΓòÉ 6. subj='Abstract Classes'.Reference Manual - Abstract Classes ΓòÉΓòÉΓòÉ

The following chapters describe the abstract classes of the library.


ΓòÉΓòÉΓòÉ 6.1. Collection ΓòÉΓòÉΓòÉ

The collection is an abstract class. I.e. 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 following concrete classes are defined by collection:

o heap
"Figure: The abstract class hierarchy" shows the position of collection in
respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.1.1. Declarations ΓòÉΓòÉΓòÉ

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 <Element> const&);
  virtual void           copy                        (IACollection
                                                  <Element> 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 <Element>&) = 0;
  virtual Boolean        allElementsDo               (Boolean (*function)
                                               (Element const&, void*),
                                               void* additionalArgument = 0)
                                               const = 0;
  virtual Boolean        allElementsDo               (IConstantIterator
                                                  <Element>&) const = 0;
};


ΓòÉΓòÉΓòÉ 6.2. Equality Collection ΓòÉΓòÉΓòÉ

The equality collection is an abstract class. I.e. it cannot be used to create
any objects. The equality collection inherits from collection. It defines the
interfaces for the following properties:

o 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.
"Figure: The abstract class hierarchy" shows the position of equality
collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.2.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element >
class IAEqualityCollection : public virtual IACollection < Element > {
public:
  virtual Boolean        contains                    (Element const&) const = 0;
  virtual Boolean        containsAllFrom             (IACollection <Element>
                                               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;
protected:
  static Boolean isContained (Element const&, void* env);
  static Boolean isNotContained (Element const&, void* env);
};


ΓòÉΓòÉΓòÉ 6.3. Key Collection ΓòÉΓòÉΓòÉ

The key collection is an abstract class. I.e. it cannot be used to create any
objects. The key collection inherits from collection. It defines the interfaces
for the following properties:

o key
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
"Figure: The abstract class hierarchy" shows the position of key collection in
respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.3.1. Declarations ΓòÉΓòÉΓòÉ

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 <Element>
                                               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 ΓòÉΓòÉΓòÉ

The ordered collection is an abstract class. I.e. it cannot be used to create
any objects. The ordered collection inherits from collection. It defines the
interfaces for the following properties:

o ordered elements
The following abstract classes are derived from ordered collection:

o sorted collection

o sequential collection
"Figure: The abstract class hierarchy" shows the position of ordered collection
in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.4.1. Declarations ΓòÉΓòÉΓòÉ

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 ΓòÉΓòÉΓòÉ

The sorted collection is an abstract class. I.e. it cannot be used to create
any objects. The sorted collection inherits from ordered collection. It defines
the interfaces for the following properties:

o sorted elements
The following abstract classes are derived from sorted collection:

o equality sorted collection

o key sorted collection
"Figure: The abstract class hierarchy" shows the position of sorted collection
in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.5.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element >
class IASortedCollection :
  public virtual IAOrderedCollection < Element > {
public:
};


ΓòÉΓòÉΓòÉ 6.6. Sequential Collection ΓòÉΓòÉΓòÉ

The equality key sorted collection is an abstract class. I.e. it cannot be used
to create any objects. The equality key sorted collection inherits from ordered
collection. It defines the interfaces for the following properties:

o orderd elements
The following concrete classes are defined by equality key sorted collection:

o sequence

o equality sequence
"Figure: The abstract class hierarchy" shows the position of equality key
sorted collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.6.1. Declarations ΓòÉΓòÉΓòÉ

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 ΓòÉΓòÉΓòÉ

The equality key collection is an abstract class. I.e. 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 following abstract classes are derived from equality key collection:

o equality key sorted collection
The following concrete classes are defined by equality key collection:

o map

o relation
"Figure: The abstract class hierarchy" shows the position of equality key
collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.7.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element, class Key >
class IAEqualityKeyCollection :
  public virtual IAEqualityCollection < Element >,
  public virtual IAKeyCollection < Element, Key > {
public:
};


ΓòÉΓòÉΓòÉ 6.8. Equality Key Collection ΓòÉΓòÉΓòÉ

The equality key collection is an abstract class. I.e. 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 following abstract classes are derived from equality key collection:

o equality key sorted collection
The following concrete classes are defined by equality key collection:

o map

o relation
"Figure: The abstract class hierarchy" shows the position of equality key
collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.8.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element, class Key >
class IAEqualityKeyCollection :
  public virtual IAEqualityCollection < Element >,
  public virtual IAKeyCollection < Element, Key > {
public:
};


ΓòÉΓòÉΓòÉ 6.9. Key Sorted Collection ΓòÉΓòÉΓòÉ

The key sorted collection is an abstract class. I.e. 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 following abstract classes are derived from key sorted collection:

o equality key sorted collection
The following concrete classes are defined by key sorted collection:

o key sorted set

o key sorted bag
"Figure: The abstract class hierarchy" shows the position of key sorted
collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.9.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element, class Key >
class IAKeySortedCollection :
  public virtual IASortedCollection < Element >,
  public virtual IAKeyCollection < Element, Key > {
public:
};


ΓòÉΓòÉΓòÉ 6.10. Equality Sorted Collection ΓòÉΓòÉΓòÉ

The equality sorted collection is an abstract class. I.e. 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 following abstract classes are derived from equality sorted collection:

o equality key sorted collection
The following concrete classes are defined by equality sorted collection:

o sorted set

o sorted bag
"Figure: The abstract class hierarchy" shows the position of equality sorted
collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.10.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element >
class IAEqualitySortedCollection :
  public virtual IAEqualityCollection < Element >,
  public virtual IASortedCollection < Element > {
public:
};


ΓòÉΓòÉΓòÉ 6.11. Equality Key Sorted Collection ΓòÉΓòÉΓòÉ

The equality key sorted collection is an abstract class. I.e. 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
"Figure: The abstract class hierarchy" shows the position of equality key
sorted collection in respect to the whole class hierarchie.


ΓòÉΓòÉΓòÉ 6.11.1. Declarations ΓòÉΓòÉΓòÉ

template < class Element, class Key >
class IAEqualityKeySortedCollection :
  public virtual IAEqualityKeyCollection < Element, Key >,
  public virtual IAEqualitySortedCollection < Element >,
  public virtual IAKeySortedCollection < Element, Key > {
public:
};


ΓòÉΓòÉΓòÉ <hidden>  ΓòÉΓòÉΓòÉ

Usually the compiler can optimize function calls when it knows the exact type
of the object. Because collections are mostly passed by reference, this would
not be possible.


ΓòÉΓòÉΓòÉ <hidden>  ΓòÉΓòÉΓòÉ

The general technique to avoid such expansions is to use untyped (void*)
implementations for functions. Collections, however, make use of element type
specific functions which complicates the situation.