Online document
___________________________________________________________________________
The container class libraries
CONTENTS
1 The container class libraries 1 Member functions . . . . . . . 38
What's new since version 1.0? . . 1 Friends . . . . . . . . . . . . 40
Why two sets of libraries? . . . . 3 Array . . . . . . . . . . . . . . 41
Container basics . . . . . . . . . 4 Example . . . . . . . . . . . . 41
Object-based and other Member functions . . . . . . . 42
classes . . . . . . . . . . . 6 ArrayIterator . . . . . . . . . . 43
Class categories . . . . . . . . 6 Member functions . . . . . . . 43
Non-container classes . . . . . 7 Association . . . . . . . . . . . 44
Error class . . . . . . . . . 7 Member functions . . . . . . . 44
Sortable class . . . . . . . . 7 Example . . . . . . . . . . . . 45
Association class . . . . . . 8 Bag . . . . . . . . . . . . . . . 47
Container classes . . . . . . . 8 Member functions . . . . . . . 47
Containers and ownership . . . . 9 BaseDate . . . . . . . . . . . . 49
Container iterators . . . . . 11 Member functions . . . . . . . 49
Sequence classes . . . . . . . 12 BaseTime . . . . . . . . . . . . 51
Collections . . . . . . . . . 12 Member functions . . . . . . . 51
Unordered collections . . . 13 Btree . . . . . . . . . . . . . . 53
Ordered collections . . . . 13 Member functions . . . . . . . 53
The BIDS template library . . . 13 Friends . . . . . . . . . . . . 55
Templates, classes, and BtreeIterator . . . . . . . . . . 55
containers . . . . . . . . . . 14 Member functions . . . . . . . 56
Container implementation . . . 14 Collection . . . . . . . . . . . 57
The template solution . . . . 15 Member functions . . . . . . . 58
ADTs and FDSs . . . . . . . 16 Container . . . . . . . . . . . . 59
Class templates . . . . . . 17 Member functions . . . . . . . 60
Container class compatibility . 20 Friends . . . . . . . . . . . . 63
Header files . . . . . . . . . 22 ContainerIterator . . . . . . . . 64
Tuning an application . . . . 23 Member functions . . . . . . . 64
FDS implementation . . . . . . 24 Date . . . . . . . . . . . . . . 65
ADT implementation . . . . . . 27 Member functions . . . . . . . 65
The class library directory . . 31 Deque . . . . . . . . . . . . . . 66
The INCLUDE directory . . . . 32 Example . . . . . . . . . . . . 67
The OBJS directory . . . . . . 32 Member functions . . . . . . . 68
The SOURCE directory . . . . . 32 Dictionary . . . . . . . . . . . 69
Creating a library . . . . . 33 Member functions . . . . . . . 69
The LIB directory . . . . . . 34 DoubleList . . . . . . . . . . . 70
The EXAMPLES directory . . . . 34 Member functions . . . . . . . 71
Preconditions and checks . . . . 35 Friends . . . . . . . . . . . . 73
Container class reference . . . 36 DoubleListIterator . . . . . . . 73
AbstractArray . . . . . . . . . 37 Member functions . . . . . . . 73
Data members . . . . . . . . . 37 Error . . . . . . . . . . . . . . 74
i

Member functions . . . . . . . 75 Member functions . . . . . . . 92
HashTable . . . . . . . . . . . 75 Set . . . . . . . . . . . . . . . 92
Member functions . . . . . . . 76 Member functions . . . . . . . 92
Friends . . . . . . . . . . . 78 Sortable . . . . . . . . . . . . 93
HashTableIterator . . . . . . . 78 Member functions . . . . . . . 95
Member functions . . . . . . . 78 Related functions . . . . . . . 96
List . . . . . . . . . . . . . . 79 SortedArray . . . . . . . . . . . 97
Member functions . . . . . . . 79 Stack . . . . . . . . . . . . . . 97
Friends . . . . . . . . . . . 80 Example . . . . . . . . . . . . 98
ListIterator . . . . . . . . . . 81 Member functions . . . . . . . 99
Member functions . . . . . . . 81 String . . . . . . . . . . . . 100
MemBlocks . . . . . . . . . . . 82 Member functions . . . . . . 100
MemStack . . . . . . . . . . . . 83 Example . . . . . . . . . . . 101
Object . . . . . . . . . . . . . 84 Time . . . . . . . . . . . . . 102
Data member . . . . . . . . . 84 Member functions . . . . . . 103
Member functions . . . . . . . 84 Timer . . . . . . . . . . . . . 104
Friends . . . . . . . . . . . 87 Member functions . . . . . . 104
Related functions . . . . . . 87 TShouldDelete . . . . . . . . . 105
PriorityQueue . . . . . . . . . 88 Member functions . . . . . . 105
Member functions . . . . . . . 89
Queue . . . . . . . . . . . . . 90 Index 107
Example . . . . . . . . . . . 91

ii

Online document
___________________________________________________________________________
The container class libraries
For more Turbo C++ version 3.0 includes two complete container
information about class libraries: an enhanced version of the Object-
templates, see based library supplied with version 1.0, plus a brand-
Chapter 13, "C++ new implementation based on templates. This chapter
specifics." describes both libraries. We assume that you are
familiar with the syntax and semantics of C++ and with
the basic concepts of object-oriented programming
(OOP). To understand the template-based version (called
BIDS, for Borland International Data Structures), you
should be acquainted with C++'s new template mechanism.
The chapter is divided into seven parts:
o A review of the difference between versions 1.0 and
3.0 of the class libraries
o An overview of the Object- and template-based
libraries
o A survey of the Object container classes, introducing
the basic concepts and terminology
o An overview of the BIDS library
o The CLASSLIB directory and how to use it
o Debugging tools
o An alphabetic reference guide to the Object container
library, listing each class and its members
===========================================================================
What's new since version 1.0?
===========================================================================
The version 1.0 container library is an Object-based
implementation. Both container objects and the elements
stored in them are all ultimately derived from the
- 1 -

class Object. Further, the data structures used to
implement each container class were fixed and (usually)
hidden from the programmer. This provides a simple,
effective model for most container applications.
Version 3.0 therefore offers an enhanced, code-
compatible version of the previous Object-based
container library. We call this the Object container
class library. In addition, a more flexible (but more
complex), template-based container library, called BIDS
(Borland International Data Structures), is supplied
with version 3.0. Through the power of templates, BIDS
lets you vary the underpinning data structure for a
container and lets you store arbitrary objects in a
container. With the appropriate template parameters,
BIDS can actually emulate the Object container library.
Before we review the differences between the Object and
BIDS models, we'll list the changes to the Object
container library since version 1.0:
o New Btree and PriorityQueue classes.
o New TShouldDelete class gives the programmer control
over container/element ownership. You can control the
fate of objects when they are detached from a
container and when the container is flushed (using
the new flush method) or destroyed.
o New memory management classes, MemBlocks and
MemStack, for efficient memory block and memory stack
(mark-and-release) allocations.
o New PRECONDITION and CHECK macros provide sophisti-
cated assert mechanisms to speed application develop-
ment and debugging.
o New Timer class gives you a stopwatch for timing
program execution.
When you choose Existing Turbo C++ version 1.01 container class code
Container Class will still run with the version 3.0 libraries. The new
Library in the Object container class libraries, in directory
IDE's Options| \CLASSLIB, are distinguished by the prefix TC:
Linker|Libraries TCLASSx.LIB and TCLASDBx.LIB where x specifies the
dialog box, the memory model, and DB indicates the special debug
Object-based version. To reduce verbiage, we will often refer to
libraries will be this container implementation as the Object or TC
automatically version.
linked in.

- 2 -

To use the The corresponding libraries for the new template-based
template-based container classes are distinguished by the prefix BIDS:
libraries, you BIDSx.LIB and BIDSDBx.LIB. Let's review the reasons for
must explicitly having two sets of container libraries. The use of all
add the these libraries is covered on page 31.
appropriate
BIDS[DB]x.LIB
library to your
project or
makefile.
===========================================================================
Why two sets of libraries?
===========================================================================
The Object container classes have been retained and
enhanced to provide code compatibility with the version
1.0 library. They provide a gentler learning curve than
the template-based BIDS library. The Object container
code offers faster compilation but slightly slower
execution than the template version. The project files
for the example and demo programs are set up to use the
Object version of the container libraries.
BIDS exploits the new exciting templates feature of C++
2.1. It offers you considerable flexibility in choosing
the best underlying data structure for a given
container application. With the Object version, each
container is implemented with a fixed data structure,
chosen to meet the space/speed requirements of most
container applications. For example, a Bag object is
implemented with a hash table, and a Deque object with
a double list. With BIDS you can fine-tune your
application by varying the container implementation
with the minimum recoding--often a single typedef will
suffice. You can switch easily from StackAsList to
StackAsVector and test the results. In fact, you'll see
that by setting appropriate values for <T>, a generic
class parameter, you can implement the Object model
exactly. With BIDS, you can even choose between
polymorphic and non-polymorphic implementations of the
Object container model. Such choices between execution
speed (non-polymorphic) and future flexibility
(polymorphic) can be tested without major recoding.

- 3 -

Existing code Both the Object and BIDS versions provide the same
based on the functional interface. For example, the push and pop
Object container member functions work the same for all Stack objects.
classes will This makes the new template-based libraries highly
compile and run compatible with existing code written for the Object
perfectly using library.
the new BIDS
classes, just by The objects stored in Object library containers must be
linking in the derived from the class Object. To store ints, say, you
appropriate would have to derive an Integer class from Object
library. (you'll see how later). With BIDS you have complete
freedom and direct control over the types of objects
stored in a container. The stored data type is simply a
value passed as a template parameter. For instance,
BI_ListImp<int> gives you a list of ints.
Regardless of which container class model you elect to
use, you should be familiar with container terminology,
the Object class hierarchy, and the functionality
provided for each container type. Although the classes
in the BIDS library have different naming conventions
and special template parameters, the prototypes and
functionality of each class member are the same as
those in the Object library.
===========================================================================
Container basics
===========================================================================
If you are fully We start by describing the Object container class
versed in the hierarchy as enhanced for Turbo C++ version 3.0. This
Turbo C++ 1.0 hierarchy offers a high degree of modularity through
version of the inheritance and polymorphism. You can use these classes
container library, as they are, or you can extend and expand them to pro-
you should first duce an object-oriented software package specific to
check out the your needs.
Object library
enhancements At the top of the class hierarchy is the Object class
before moving to (see Figure 1), an abstract class that cannot be
the templates instantiated (no objects of its type can be declared).
section on page An abstract class serves as an umbrella for related
14. classes. As such, it has few if any data members, and
some or all of its member functions are pure virtual
functions. Pure virtual functions serve as placeholders
for functions of the same name and signature intended
- 4 -

to be defined eventually in derived classes. In fact,
any class with at least one pure virtual function is,
by definition, an abstract class.
Figure 1: Class hierarchies in CLASSLIB
ObjectÄÂÄError
ÃÄSortableÄÄÄÄÂÄString
³ ÃÄBaseDateÄÄÄÄÄDate
³ ÀÄBaseTimeÄÄÄÄÄTime
ÃÄAssociation
ÀÄContainerÄÄÄÂÄCollectionÄÂÄAbstractArrayÄÂÄArray
³ ³ ÀÄSortedArray
³ ÃÄHashTable
³ ÃÄBagÄÄSetÄÄDictionary
³ ÃÄList
³ ÃÄBtree
³ ÀÄDoubleList
ÃÄStack
ÃÄDequeÄÄQueue
ÀÄPriorityQueue
ContainerIteratorÄÄÄÄÂÄHashTableIterator
ÃÄListIterator
ÃÄDoubleListIterator
ÃÄBtreeIterator
ÀÄArrayIterator
Memblocks
MemStack
Note that TShouldDelete provides a second base
(multiple inheritance) for both Container and
Association.
A class derived from an abstract class can provide a
body defining the inherited pure virtual function. If
it doesn't, the derived class remains abstract,
providing a base for further derivations. When you
reach a derived class with no pure virtual functions,
the class is called a non-abstract or instance class.
As the name implies, instance classes can be
instantiated to provide usable objects.
An abstract class can be the base for both abstract and
instance classes. For example, you'll see that
Container, an abstract class derived from the abstract
class Object, is the base for both Collection
(abstract) and Stack (instance).

- 5 -

To enhance your As you read this chapter, bear in mind that a derived
understanding of class inherits and can access all non-private data
the classes, you members and member functions from all its ancestral
can review their base classes. For example, the Array class does not
declarations in need to explicitly define a function to print an array,
the source code because its immediate parent class AbstractArray does
files in the so. The Container class, an ancestor further up the
CLASSLIB class tree, defines a different print function that can
directory. also be used with an array, because an array is a
container. To determine all the member functions
available to an object, you will have to ascend the
class hierarchy tree. Because the public interface is
intended to be sufficient for applications, object-
oriented programming makes a knowledge of private data
members unnecessary; therefore, private members (with a
few exceptions) are not documented in this chapter.
------------------ The Object-based hierarchy contains classes derived
Object-based and from the class Object (together with some other utility
other classes classes). Object provides a minimal set of members
------------------ representing what every derived object must do; these
are described in the reference section under Object
(page 84). Both the containers-as-objects and the
objects they store are objects derived (ultimately)
from Object. Later you'll see that the template-based
containers can contain objects of any data type, not
just those derived from Object.
Class categories =======================================================
The classes in or near the Object hierarchy can be
divided into three groups:
o The non-container classes include Object itself, and
those classes derived from Object, such as String and
Date, which cannot store other objects.
o The container classes (also derived from Object),
such as Array and List, which can store objects of
other, usually non-container, class types.
o The helper and utility classes not derived from
Object, such as TShouldDelete, ListIterator and
MemStack.
Let's look at each category in more detail, although as
with most OOP topics, they are closely related.

- 6 -

Non-container =======================================================
classes
The basic non-container classes provided are Object and
its three children: Error (instance), Sortable
(abstract), and Association (instance). Recall that the
main purpose of these classes is to provide objects
that can be stored as data elements in containers. To
this end, all Object-derived classes provide a hashing
function allowing any of their objects to be stored in
a hash table.
------------------ Error is not a normal class; it exists solely to define
Error class a unique, special object called theErrorObject. A
------------------ pointer to theErrorObject carries the mnemonic
Error see page 74 NOOBJECT. NOOBJECT is rather like a null pointer, but
in the reference serves the vital function of occupying empty slots in a
section. container. For example, when an Array object is created
(not to be confused with a traditional C array), each
of its elements will initially contain NOOBJECT.
------------------ Sortable is an abstract class from which sortable
Sortable class classes must be derived. Some containers, known as
------------------ ordered collections, need to maintain their elements in
a particular sequence. Collections such as SortedArray
and PriorityQueue, for example, must have consistent
methods for comparing the "magnitude" of objects.
Sortable adds the pure virtual function isLessThan to
its base, Object. Classes derived from Sortable need to
define IsLessThan and IsEqual (inherited from Object)
for their particular objects. Using these members, the
relational operators <, ==, >, >=, and so on, can be
overloaded for sortable objects. Typical sortable
classes are String, Date, and Time, the objects of
which are ordered in the natural way. Of course, string
ordering may depend on your locale, but you can always
override the comparison functions (another plus for
C++).
For more details Distinguish between the container object and the
on Sortable see objects it contains: Sortable is the base for non-
page 93 in the container objects; it is not a base for ordered
reference section. collections. Every class derived from Object inherits
the isSortable member function so that objects can be
queried as to their "sortability."

- 7 -

------------------ Association is a non-container, instance class
Association class providing special objects to be stored (typically) in
------------------ Dictionary collections. An Association object, known as
Association see an association, is a pair of objects known as the key
page 44 in the and the value. The key (which is unique in the
reference section. dictionary) can be used to retrieve the value. Every
class derived from Object inherits the isAssociation
member function so that objects can report whether they
are associations or not.
Container classes =======================================================
In the Object-based library, all the container storage
and access methods assume that the stored elements are
derived from Object. They are actually stored as
references or pointers to Object offering the
advantages and disadvantages of polymorphism. Most of
the container access member functions are virtual, so a
container does not need to "know" how its contained
elements were derived. A container can, in theory,
contain mixed objects of different class types, so
proper care is needed to maintain type-safe linkage.
Every class has member functions called IsA and nameOf,
which allow objects to announce their class ID and
name. As you've seen, there are also isSortable and
isAssociation member functions for testing object
types.
All the container classes are derived from the abstract
Container class, a child of Object. Container
encapsulates just a few simple properties upon which
more specialized containers can be built. The basic
container provides the following functionality:
o Displays its elements
o Calculates its hash value
o Pure virtual slot for counting the number of items
with getItemsInContainer
o Pure virtual slot for flushing (emptying) the
container with flush
o Performs iterations over its elements
o Reports and changes the ownership of its elements
(inherited from TShouldDelete)
So far, our containers have no store, access, or detach
methods. (We can flush the container but we cannot
detach individual elements.) Nor is there a hasMember
- 8 -

member function, that is, a general way of determining
whether a given object is an element of the container.
This is a deliberate design decision. As we move up the
hierarchy, you'll see that what distinguishes the
various derived container classes are the storage and
access rules that actually define each container's
underlying data structure. Thus push and pop member
functions are added for Stack, indexing operators are
added for Array, and so on. There is not enough in
common to warrant having generic add and retrieve
methods at the Container level. There is no one perfect
way of extracting common properties from groups of
containers, and therefore no perfect container class
hierarchy. The Object-based container hierarchy is just
one possible design based on reasonable compromises.
The BIDS version, as you'll see, offers a different
perspective.
The first three Container functions listed previously
are fairly self-explanatory. We'll discuss the
important subjects of ownership and iteration in the
next two sections.
Containers and =======================================================
ownership
Before you use the Container family, you must
understand the concept of ownership. As in real life, a
C++ container starts out empty and must be filled with
objects before the objects can be said to be in the
container. Unlike the real world, however, when objects
are placed in the container, they are, by default,
owned by the container. The basic idea is that when a
container owns its objects, the objects are destroyed
when the container is destroyed.
Recall that containers are themselves objects subject
to the usual C++ scoping rules, so local containers
come and go as they move in and out of scope. Care is
needed, therefore, to prevent unwanted destruction of a
container's contents, so provision is made for changing
ownership. A container can, throughout its lifetime,
relinquish and regain ownership of its objects as often
as it likes by calling the ownsElements member function
(inherited from TShouldDelete). The fate of its objects
when the container disappears is determined by the
ownership status ruling at the time of death. Consider
the following:
- 9 -

void test()
{
Array a1( 10 ); // construct an array
Array a2( 10 ); // and another
a1.ownsElements( 1 ); // array a1 owns its objects
(the default)
a2.ownsElements( 0 ); // array a2 relinquishes
ownership
// load and manipulate the arrays here
}
When test exits, a1 will destroy its objects, but the
objects in a2 will survive (subject, of course, to
their own scope). The a1.ownsElements( 1 ) call is not
really needed since, by default, containers own their
contents.
Ownership also plays a role when an object is removed
from a container. The pure virtual function
Container::flush is declared as
virtual void flush( DeleteType dt = DefDelete ) = 0;
flush empties the container but whether the flushed
objects are destroyed or not is controlled by the dt
argument. DeleteType is an enum defined in
TShouldDelete. A value of NoDelete means preserve the
flushed objects regardless of ownership; Delete means
destroy the objects regardless of ownership; DefDelete,
the default value, means destroy the objects only if
owned by the container. Similarly Collection (derived
from Container) has a detach member function, declared
as
virtual void detach( Object& obj, DeleteType dt =
NoDelete ) = 0;
which looks for obj in the collection and removes it if
found. Again, the fate of the detached object is
determined by the value dt. Here, the default is not to
destroy the detached object. Collection::destroy is a
variant that calls detach with DefDelete.
A related problem occurs if you destroy an object that
resides in a container without "notifying" the
- 10 -

container. The safest approach is to use the
container's methods to detach and destroy its contents.
Important! If you declare an automatic object (an object that's
local to your routine) and place that object in a
global container, your local object will be destroyed
when the routine leaves the scope in which it was
declared. To prevent this, you must only add heap
objects (objects that aren't local to the current
scope) to global containers. Similarly, when you remove
an object from a global container, you are responsible
for destroying it and freeing the space in which it
resides.
Container =======================================================
iterators
You saw earlier that Container, the base for all
containers in the Object-based library, supports
iteration. Iteration means traversing or scanning a
container, accessing each stored object in turn to
perform some test or action. The separate
ContainerIterator-based hierarchy provides this
functionality. Iterator classes are derived from this
base to provide iterators for particular groups of
containers, so you'll find HashTableIterator,
ListIterator, BtreeIterator, and so on.
Under There are two flavors of iterators: internal and
ContainerIterator external. Each container inherits the three member
on page 64 in the functions: firstThat, lastThat, and forEach, via the
reference section, Object and Container classes. As the names indicate,
you see how the these let you scan through a container either testing
pre- and post- each element for a condition or performing an action on
increment each of the container's elements. When you invoke one
operators ++ are of these three member functions, the appropriate
overloaded to iterator object is created for you internally to
simplify your support the iteration. Most iterations can be performed
iterator programs. in this way since the three iterating functions are
very flexible. They take a pointer-to-function argument
together with an arbitrary parameter list, so you can
do almost anything. For even more flexibility, there
are external iterators that you can build via the
initIterator member function. With these, you have to
set up your own loops and test for the end-of-
container.

- 11 -

Returning to the container class hierarchy, we look at
three classes derived directly from Container: Stack,
Deque, and PriorityQueue.
Sequence classes =======================================================
The instance classes Stack, Deque (and its offspring
Queue), and PriorityQueue are containers collectively
known as sequence classes. A sequence class is
characterized by the following properties:
1. Objects can be inserted and removed.
2. The order of insertions and deletions is
significant.
3. Insertions and extractions can occur only at
specific points, as defined by the individual class.
In other words, access is nonrandom and restricted.
Sequences (like all containers) know how many elements
they have (using getItemsInContainer) and if they are
empty or not (using isEmpty). However, they cannot
usually determine if a given object is a member or not
(there is still no general hasMember or findMember
member function). Stacks, queues, priority queues, and
deques vary in their access methods as explained in
more detail in the reference section.
Sequence is not itself a class because sequences do not
share enough in common to warrant a separate base
class. However, you might find it helpful to consider
the classes together when reviewing the container
hierarchy.
Collections =======================================================
The next level of specialization is the abstract class
Collection, derived from Container, and poised to
provide a slew of widely used data structures. The key
difference between collections and containers is that
we now have general hasMember and findMember member
functions.
From Collection we derive the unordered collections
Bag, HashTable, List, DoubleList, and AbstractArray,
- 12 -

and the ordered collection Btree. In turn,
AbstractArray spawns the unordered Array and the
ordered SortedArray. Bag serves as the base for Set
which in turn is the base for Dictionary. These
collections all refine the storage and retrieval
methods in their own fashions.
------------------ With unordered collections, any objects derived from
Unordered Object can be stored, retrieved, and detached. The
collections objects do not have to be sortable because the access
------------------ methods do not depend on the relative "magnitude" of
the elements. Classes that fall into this category are
o HashTable
o Bag, Set, and Dictionary
o List and DoubleList
o Array
------------------ An ordered collection depends on relative "magnitude"
Ordered when adding or retrieving its elements. Hence these
collections elements must be objects for which the isLessThan
------------------ member function is defined. In other words, the
elements in an ordered collection must be derived from
the class Sortable. The following are ordered
collections:
o Btree
o SortedArray
===========================================================================
The BIDS template library
===========================================================================
The BIDS container class library can be used as a
springboard for creating useful classes for your
individual needs. Unlike the Object container library,
BIDS lets you fine-tune your applications by varying
the underlying data structures for different containers
with minimum reprogramming. This extends the power of
encapsulation: the implementor can change the internals
of a class with little recoding and the user can easily
replace a class with one that provides a more
appropriate algorithm. The BIDS class library achieves
this flexibility by using the C++ template mechanism.
- 13 -

For a basic With BIDS, the container is considered as an ADT
description of C++ (abstract data type), and its underlying data structure
templates see is independently treated as an FDS (fundamental data
Chapter 13. structure). BIDS also allows separate selections of the
type of objects to be stored, and whether to store the
objects themselves or pointers to objects.
Templates, =======================================================
classes, and
containers Computer science has devoted much attention to devising
suitable data structures for different applications.
Recall Wirth's equation, Programs = Algorithms + Data
Structures, which stresses the equal importance of data
structures and their access methods.
As used in current OOP terminology, a container is
simply an object that implements a particular data
structure, offering member functions for adding and
accessing its data elements (usually other objects)
while hiding from the user as much of the inner detail
as possible. There are no simple rules to determine the
best data structure for a given program. Often, the
choice is a compromise between competing space (RAM)
and time (accessibility) considerations, and even here
the balance can shift suddenly if the number of
elements or the frequency of access grows or falls
beyond a certain number.
Container =======================================================
implementation
Often, you can implement the desired container
properties in many ways using different underlying data
structures. For example, a stack, characterized by its
Last-In-First-Out (LIFO) access, can be implemented as
a vector, a linked list, or perhaps some other
structure. The vector-based stack is appropriate when
the maximum number of elements to be stored on the
stack is known in advance. A vector allocates space for
all its elements when it is created. The stack as a
list is needed when there is no reasonable upper bound
to the size of the stack. The list is a slower imple-
mentation than the vector, but it doesn't use any more
memory than it needs for the current state of the
stack.

- 14 -

The way objects are stored in the container also
affects size and performance: they can be stored
directly by copying the object into the data structure,
or stored indirectly via pointers. The type of data to
be stored is a key factor. A stack of ints, for
example, would probably be stored directly, where large
structs would call for indirect storage to reduce
copying time. For "in-between" cases, however, choosing
strategies is not always so easy. Performance tuning
requires the comparison of different container
implementations, yet traditionally this entails drastic
recoding.
The template =======================================================
solution
The template approach lets you develop a stack-based
application, say, using vectors as the underlying
structure. You can change this to a list implementation
without major recoding (a single typedef change, in
fact). The BIDS library also lets you experiment with
object-storage strategies late in the development
cycle. Each container-data structure combination is
implemented with both direct and indirect object
storage, and the template approach allows a switch of
strategy with minimal rewriting. The data type of the
stored elements is also easy to change using template
parameters, and you are free to use any data type you
want.
As you'll see, BIDS offers container/data structure
combinations that match those of the Object-based
version. For example, the Object library implements
Stack using lists, so Stack can be simulated exactly
with the template class BI_TCStackAsList. Let's look at
the template approach in more detail.

- 15 -

------------------ We discussed earlier the stack and its possible
ADTs and FDSs implementations as a linked list or as a vector. The
------------------ potential for confusion is that stacks, lists, and
vectors are all commonly referred to as data
structures. However, there is a difference. We can
define a stack abstractly in terms of its LIFO
accessibility, but it's difficult to envision a list
without thinking of specifics such as nodes and
pointers. Likewise, we picture a vector as a concrete
sequence of adjacent memory locations. So we call the
stack an ADT (abstract data type) and we call the list
and vector FDSs (fundamental data structures). The BIDS
container library offers each of the standard ADTs
implemented with a choice of appropriate FDSs. Table 1
indicates the combinations provided:
ADTs as
fundamental data -------------------------------------------------------
structures ADT Sorted
FDS Stack Queue Deque Bag Set Array Array
-------------------------------------------------------
Vector x x x x x x x
List x
DoubleList x x
-------------------------------------------------------
The abstract data types involved are Stacks, Queues,
Deques, Bags, Sets, and Arrays. Each ADT can be
implemented several different ways using the
fundamental data structures Vector, List, and
DoubleList as indicated by a bullet ( x ) in the table.
Thus, all ADTs are implemented as vectors. In addition,
Stacks are implemented as a list; Queues and Deques
implemented as doubly-linked lists. (Not shown in the
table are the sorted and counted FDSs from which
various ADTs can be developed.)
There is nothing sacred about these combinations; you
can use the template classes to develop your own
ADT/FDS implementations.

- 16 -

------------------ ADTs are implemented in both direct and indirect
Class templates versions. The direct versions store the objects
------------------ themselves, while the indirect versions store pointers
to objects. You can store whatever objects you want as
elements in these FDSs using the power of templates.
Here are the ADT and FDS templates we provide:
---------------------------------------------------------------------------
Table 2: FDS class templates
Class template Description
---------------------------------------------------------------------------
BI_VectorImp<T> vector of Ts
BI_VectorIteratorImp<T> iterator for a vector of Ts
BI_CVectorImp<T> counted vector of Ts
BI_SVectorImp<T> sorted vector of Ts
BI_IVectorImp<T> vector of pointers to T
BI_IVectorIteratorImp<T> iterator for a vector of pointers to T
BI_ICVectorImp<T> counted vector of pointers to T
BI_ISVectorImp<T> sorted vector of pointers to T
BI_ListImp<T> list of Ts
BI_SListImp<T> sorted list of Ts
BI_IListImp<T> list of pointers to T
BI_ISListImp<T> sorted list of pointers to T
BI_DoubleListImp<T> double-linked list of Ts
BI_SDoubleListImp<T> sorted double-linked list of Ts
BI_IDoubleListImp<T> double-linked list of pointers to T
BI_ISDoubleListImp<T> sorted double-linked list of pointers to T
---------------------------------------------------------------------------
Each basic FDT has a direct and indirect iterator; to
save space we have shown only the Vector iterators.
The BI_ prefix stands for Borland International and the
suffix Imp for implementation. The indirect versions
have the prefix BI_I with the extra I for Indirect. The
extra prefixes S and C mean Sorted and Counted
respectively. The template parameter T in <T>
represents the data type of the objects to be stored.
You instantiate the template by supplying this data
type. For example, BI_ListImp<double> gives you a list
of doubles. See Table 3 on page 19 for a summary of
these abbreviations. For direct object storage, the

- 17 -

type T must have meaningful copy semantics and a
default constructor. Indirect containers, however, hold
pointers to T, and pointers always have

- 18 -

good copy semantics. This means that indirect
containers can contain objects of any type.
Abbreviations in
CLASSLIB names -----------------------------------------------------------------
Abbreviation Description
-----------------------------------------------------------------
I Indirect
C Counted
S Sorted
O Object-based, non-polymorphic
TC Object-based, polymorphic (compatible with
original Turbo C++ library)
-----------------------------------------------------------------
For details see For the sorted FDSs (BI_SVectorImp, BI_ISVectorImp, and
the discussion so on), T must have valid == and < operators to define
under Sortable on the ordering of the elements. It should be clear that
page 94. the IS variants refer to the objects being sorted, not
that the pointers to the objects are sorted.
Each implementation of an ADT with an FDS is named
using the convention (ADT)As(FDS)<T>, as follows:
----------------------------------------------------------------------------
Table 4: ADT class templates
Class name Description
----------------------------------------------------------------------------
BI_StackAsVector<T> Stack of Ts as a vector
BI_QueueAsVector<T> Queue of Ts as a vector
BI_DequeAsVector<T> Deque of Ts as a vector
BI_BagAsVector<T> Bag of Ts as a vector
BI_SetAsVector<T> Set of Ts as a vector
BI_ArrayAsVector<T> Array of Ts as a vector
BI_SArrayAsVector<T> Sorted array of Ts as a vector
BI_IStackAsVector<T> Stack of pointers to T as a vector
BI_IQueueAsVector<T> Queue of pointers to T as a vector
... and so on
BI_StackAsList<T> Stack of Ts as a list
BI_IStackAsList<T> Stack of pointers to T as a list
- 19 -

Table 4: ADT class templates (continued)___________________________________
BI_QueueAsDoubleList<T> Queue of Ts as a double list
BI_DequeAsDoubleList<T> Deque of Ts as a double list
BI_IQueueAsDoubleList<T> Queue of pointers to T as a double list
BI_IDequeAsDoubleList<T> Deque of pointers to T as a double list
----------------------------------------------------------------------------
There are also Again, the <T> argument, either a class or predefined
BI_Oxxx and data type, provides the data type for the contained
BI_TCxxx variants elements. Each of the bulleted items ( x ) in Table 1
discussed soon. can be mapped to two templates (direct and indirect
versions) with names following this convention.
Container class ========================================================
compatibility
Each template must be instantiated with a particular
data type as the type of the element that it will hold.
This allows the compiler to generate the correct code
for dealing with any possible type of element without
restricting the elements to just those derived from
Object.
Each ADT is also used to instantiate two classes that
imitate the behavior of the Object class libraries. Here
is a list of them:
--------------------------------------------------------
Object-based FDS Class name Description
classes --------------------------------------------------------
BI_OStackAsVector Stack of pointers to Object,
as a vector
BI_OQueueAsVector Queue of pointers to Object,
as a vector
BI_ODequeAsVector Deque of pointers to Object,
as a vector
BI_OBagAsVector Bag of pointers to Object, as
a vector
BI_OSetAsVector Set of pointers to Object, as
a vector
BI_OArrayAsVector Array of pointers to Object,
as a vector
BI_OSArrayAsVector Sorted array of pointers to
Object, as a vector
- 20 -

Table 5: Object-based FDS classes (continued)__________
BI_TCStackAsVector Polymorphic stack of pointers
to Object, as a vector
BI_TCQueueAsVector Polymorphic queue of pointers
to Object, as a vector
BI_TCDequeAsVector Polymorphic deque of pointers
to Object, as a vector
BI_TCBagAsVector Polymorphic bag of pointers to
Object, as a vector
BI_TCSetAsVector Polymorphic set of pointers to
Object, as a vector
BI_TCArrayAsVector Polymorphic array of pointers
to Object, as a vector
BI_TCSArrayAsVector Polymorphic sorted array of
pointers to Object, as a
vector
BI_OStackAsList Stack of pointers to Object,
as a list
BI_TCStackAsList Polymorphic stack of pointers
to Object, as a list
BI_OQueueAsDoubleList Queue of pointers to Object,
as a double list
BI_ODequeAsDoubleList Deque of pointers to Object,
as a double list
BI_TCQueueAsDoubleList Polymorphic queue of pointers
to Object, as a double list
BI_TCDequeAsDoubleList Polymorphic deque of pointers
to Object, as a double list
--------------------------------------------------------
Note that these versions have no explicit <T>
parameters; they use the fixed data types shown
The TCxxx versions (pointers to Object). The BI_Oxxx (O for Object library)
offer the same versions of these classes have no virtual functions.
behavior and This makes it easier for the compiler to generate inline
interfaces as the function expansions, which in turn makes the BI_Oxxx
Object library. versions of the containers somewhat faster than the
corresponding polymorphic BI_TCxxx (TC for Turbo C++)
versions. The obverse of the coin is that the BI_Oxxx
versions do not share the polymorphic behavior of the
Object container library.

- 21 -

In the Object container library, Stack implements a
stack as a polymorphic list of pointers to Object. The
BIDS class BI_TCStackAsList therefore mirrors the
Object-based class Stack. Even with BI_TCStackAsVector,
the public interface and semantics are the same as for
the Object-based Stack. The user "sees" the ADT while
the FDS is "hidden." For these reasons, we will not
repeat the alphabetic list of Object-based classes and
member functions for the BIDS library.
Consider your many choices when writing container code
with the BIDS model. You can gain speed over future
flexibility by using the non-polymorphic classes, such
as BI_OStackAsList or BI_OStackAsVector. Or you can
retain the polymorphism of the Object-based hierarchy by
using the BI_TCxxx classes.
Header files ========================================================
Each group of FDSs is defined in its own header file,
which contains templates for both the direct and the
indirect versions. The names of the headers are as
follows:
vectimp.h
listimp.h
dlistimp.h
In vectimp.h, for example, you'll find declarations for
all the vector, counted vector, and sorted vector
templates, together those for a direct and indirect
vector iterator.
Note also the stdtempl.h file that defines the useful
template functions min, max, and range. If you are new
to templates, this file offers a useful, gentle
introduction to the subject.
Each ADT family is defined in its own header file, named
as follows:
stacks.h
queues.h
deques.h
bags.h
sets.h
arrays.h
- 22 -

Note the plural The file stacks.h, for example, defines the following
form that templates:
distinguishes the
BIDS include files BI_StackAsVector<T>
from the Object- BI_IStackAsVector<T>
based include file BI_OStackAsVector
BI_TCStackAsVector
BI_StackAsList<T>
BI_IStackAsList<T>
BI_OStackAsList
BI_TCStackAsList
Tuning an ========================================================
application
Consider the following example:
typedef BI_StackAsVector<int> intStack;
int main()
{
intStack is;
for( int i = 0; i < 10; i++ )
is.push( i );
for( i = 0; i < 10; i++ )
cout << is.pop() << endl;
return(0);
}
Here we are implementing a stack of ints using a vector
as the underlying data structure. If you later determine
that a list would be a more suitable implementation for
the stack, you can simply replace the typedef with the
following:
typedef BI_StackAsList<int> intStack;
After recompilation, the stack implementation is changed
from vector to list. Similarly, you can try a stack of
pointers to int, with:
typedef BI_IStackAsList<int> intStack;

- 23 -

FDS implementation ========================================================
Each FDS is implemented as two templates, one that
provides the direct version, and one that provides the
indirect version. The indirect version makes use of an
InternalIxxxImp class. The following simplified extract
from listimp.h will give you an idea how the different
list FDSs are implemented. Note that BI_ListElement<T>
is an internal template class used to implement the node
(data of type T and pointer to next node) of a list. The
direct list of objects of type T is implemented by the
template class BI_ListImp<T>, which also provides the
base for BI_SListImp<T> (sorted lists). The example
shows how the add member function is implemented in the
direct, indirect, sorted and unsorted lists.
template <class T> class BI_ListElement
{
public:
BI_ListElement( T t, BI_ListElement<T> *p ) : data(t)
{ next = p->next; p->next = this; }
// constructor
...
BI_ListElement<T> *next; // pointer to next node
T data; // object at node
...
};
template <class T> class BI_ListImp
// linked list (unsorted) of type T objects; assumes T
has meaningful // copy semantics and a default
constructor
{
public:
...
void add( T t ) { new BI_ListElement<T>( t, &head );
}
// adds objects at head of list (shown inline here to
save space)
T peekHead() const { return head.next->data; }
...
};
template <class T> class BI_SListImp : public
BI_ListImp<T>
// sorted list; assumes T has meaningful copy

- 24 -

// semantics and a default constructor
{
public:
...
void add( T t ) { new BI_ListElement<T>( t,
findPred(t) ); }
// adds object in sorted position
...
};
template <class T, class List> class
BI_InternalIListImp : public List
{
...
void add( T *t ) { List::add ( t ); }
};
// The work is done in this intermediate class
// used as base for BI_IListImp; list is
// unsorted so we use List::add
template <class T> class BI_IListImp :
public BI_InternalIListImp<T, BI_ListImp< void * > >
{ ... };
/* unsorted list of pointers to objects of type T;
since pointers always have meaningful copy
semantics, this class can handle any object type;
add comes straight from BI_InternalIListImp
*/
template <class T> class BI_ISListImp :
public BI_InternalIListImp<T>, BSListImp< void * >> {
... };
/* sorted list of pointers to objects of type T; since
pointers always have meaningful copy semantics, this
class can handle any object type
*/
In addition to the template classes shown here,
listimp.h also declares BI_ListIteratorImp<T> and
BI_IListIteratorImp<T>, the iterators for direct and
indirect lists.
In the next section on ADTs, you'll see how the
different stack implementations in stacks.h pull in the
vector and list FDSs declared in vectimp.h and
listimp.h.

- 25 -

The double list templates, in dlistimp.h, follows the
same pattern. The sorted versions of list and double
list provide exactly the same interface as the non-
sorted ones, except that the add member function adds
new elements in sorted order. This speeds up subsequent
access and also makes it easier to implement priority
queues.
vectimp.h also follows a similar pattern to listimp.h,
implementing BI_VectorImp<T> (direct) and
BI_IVectorImp<T> (indirect). These are low-level vectors
with no notion of add or detach. To support more
sophisticated ADTs, the counted vector,
BI_CVectorImp<T>, derived from BI_VectorImp<T>, is
provided. This maintains a pointer to the last valid
entry in the underlying Vector. It has an add member
function that inserts its argument at the top (the next
available slot), and a detach member function that
removes its argument and compresses the array.
BI_CVectorImp<T> provides the base for the sorted vector
template BI_SVectorImp<T>. With a sorted vector, you can
run through the indices from 0 to the last valid entry,
and the objects will emerge in sort order. Here's a
simplified extract from vectimp.h:
// extract from vectimp.h
template <class T> class BI_VectorImp { ... };
// direct uncounted, unsorted vector
template <class T> class BI_CVectorImp : public
BI_VectorImp<T>
// direct counted, unsorted vector
{
public:
...
void add( T t );
// add at top of array; inc count; resize array if
necessary
void detach( T t, int del = 0 );
void detach( unsigned loc, int del = 0 );
// detach given object or object at loc
...
};
template <class T> class BI_SVectorImp : public
BI_CVectorImp<T>
// direct counted, sorted vector
- 26 -

{
public:
void add( T t );
// add at position that maintains sort
};
template <class T, class Vect> class
BI_InternalIVectorImp :
public Vect {...};
// interdiate base for BI_IVectorImp: no add
template <class T> class BI_IVectorImp :
public BI_InternalIVectorImp<T, BI_VectorImp<void *> >
{...};
// indirect uncounted, unsorted vector: no add
template <class T, class Vect> class
BI_InternalICVectorImp :
public BI_InternalIVectorImp<T, Vect>
// intermediate base for BI_ICVector
{
public:
void add( T *t) { Vect::add(t); }
...
};
template <class T> class BI_ICVectorImp :
public BI_InternalICVectorImp<T, BI_CVectorImp<void *>
>
{ ... };
// indirect counted vector; can contain any object type
template <class T> class BI_ISVectorImp :
public BI_InternalICVectorImp<T, BI_SVectorImp<void *>
>
{ ... };
// indirect sorted vector
ADT implementation ========================================================
Each ADT is implemented as several templates. For
example, the following provides an implementation of a
stack of objects of type T using vectors as the FDS:
// simplified extract from stacks.h

- 27 -

template <class Vect, class T> class
BI_StackAsVectorImp
{
public:
...
void push( T t ) { data[current++] = t; }
...
protected:
Vect data;
unsigned current;
};
The first parameter, class Vect, is either a direct
vector or an indirect vector, depending on whether the
stack being created is direct or indirect, so Vect will
be either BI_VectorImp<T0> or BI_IVectorImp<T0>. The
type T represents the type of objects to be stored in
the stack. For a direct Vect, T should be the same as
T0; for an indirect Vect, T must be of type pointer to
T0. A direct stack implemented as a vector looks like
this:
template <class T> class BI_StackAsVector :
public BI_StackAsVectorImp< BI_VectorImp<T>, T >
{
public:
friend class BI_StackAsVectorIterator<T>;
...
};
template <class T> class BI_StackAsVectorIterator :
public BI_VectorIteratorImp<T> {...};
That is, a BI_StackAsVector is implemented by using a
BI_StackAsVectorImp, whose "implementation" is of type
BI_VectorImp<T>, and whose elements are of type T.
BI_StackAsVector has its own iterator, derived from
underpinning FDS iterator with the contained-object type
T as parameter.
An indirect stack implemented as a vector looks like
this:
template <class T> class BI_IStackAsVector :
public BI_StackAsVectorImp< BI_IVectorImp<T>, T* >,
public virtual TShouldDelete
{...};
- 28 -

That is, an BI_IStackAsVector is implemented by using a
BI_StackAsVectorImp, whose "implementation" is of type
BI_IVectorImp<T>, and whose elements are of type pointer
to T. The TShouldDelete base provides the ownership
control discussed in the Object-based class reference
section. TShouldDelete also serves as a second base for
the following classes.
Figure 2: TShouldDelete hierarchy
TShouldDelete*ÄÄÄÄÄÄÂÄÄAssociation*
ÃÄÄContainer
ÃÄÄBI_IArrayAsVector+
ÃÄÄBI_IBagAsVector+
ÃÄÄBI_IDequeAsDoubleList+
ÃÄÄBI_IDequeAsVector+ *Instance classes
ÃÄÄBI_ISArrayAsVector+
ÃÄÄBI_ISObjectArray+
ÃÄÄBI_IStackAsList+ +Template classes
ÀÄÄBI_IStackAsVector+
The BI_OStackAsVector and BI_TCStackAsVector versions
(stacks of pointers to Objects, emulating the Object
container library) now follow easily:
class BI_OStackAsVector
// non-polymorphic stack with vector of pointers to
Objects
{
public:
...
void push( Object *t ) { ostack.push(t); }
// ostack is type BI_IStackAsVector<Object>
// so we are pushing pointers to Object
...
private:
BI_IStackAsVector<Object> ostack;
};
class BI_TCStackAsVector : public Container
// polymorphic stack with vector of pointers to
Objects
// inherits from the Object-based Container class
// Provides identical interface and functionality as
Object-based Stack // class but underlying data
structure is Vector not List
- 29 -

{
public:
...
void push( Object& o ) { stk.push( &o ); }
// stk is type BI_OStackAsVector
// so we are pushing Objects
...
private:
BI_OStackAsVector stk;
};
We end the section with some short examples using the
BIDS classes.
Source #include <iostream.h>
#include <strstream.h>
Uses the template #include <arrays.h>
facility to pick a #include <strng.h>
specific FDS for
the array ADT. int main()
{
typedef BI_SArrayAsVector<String> lArray;
In the "sorted lArray a(2);
array" FDS, the for (int i = a.arraySize(); i; i--)
index of a {
particular array ostrstream os;
element depends on os << "string " << i << ends;
its value, not on a.add( *(new String(os.str())));
the order in which }
it was entered. cout << "array elements;\n";
for (i = 0; i < a.arraySize(); ++i)
{
If the ADT used cout<< a[i] << endl;
BI_ArrayAsVector }
<String>, the return(0);
elements would }
appear in the
order they were
added to the
array.
Output string 1
string 2
string 3
Source
- 30 -

Doubly-linked list #include <iostream.h>
with indirect #include <strstream.h>
storage as FDS. #include <deques.h>
#include <strng.h>
Pointers to String typedef BI_IDequeAsDoubleList<String> lDeque;
objects in the
deque container int main()
must be {
dereferenced when lDeque d;
extracting from for (int i = 1; i < 5; i++)
the deque. {
ostrstream os;
os << "string " << i << ends;
// use alternating left, right insertions
if(i&1)
d.putLeft(new String(os.str()));
else
d.putRight(new String(os.str()));
}
cout << "Deque Contents:" << endl;
while (!d.isEmpty())
{
cout << *d.getLeft() << endl;
}
return(0);
}
Output Deque Contents:
string 3
string 1
string 2
string 4
===========================================================================
The class library directory
===========================================================================
The files in the class library are set up in the
following directory structure:

- 31 -

ÉÍÍÍÍÍÍÍÍÍÍÍ»
º CLASSLIB\ º
ÈÍÍÍÍÍÑÍÍÍÍÍ¼
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÉÍÍÍÍÏÍÍÍÍÍ» ÉÍÍÍÍÏÍÍÍÍ» ÚÄÄÄÄÄÁÄÄÄÄ¿ ÉÍÍÏÍÍÍ» ÉÍÍÍÍÏÍÍÍÍÍÍ»
º INCLUDE\ º º SOURCE\ º ³ OBJS ³ º LIB\ º º EXAMPLES\ º
ÈÍÍÍÍÍÍÍÍÍÍ¼ ÈÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍ¼ ÈÍÍÍÍÍÍÍÍÍÍÍ¼
The CLASSLIB directory is under the TC directory. The
contents of the directories in the class library are
discussed in more detail in the following sections.
The INCLUDE =======================================================
directory
The INCLUDE directory contains the header files
necessary to compile a program that uses the class
library. You must put this directory on the include
search path when you compile your program. Modify
Options|Directories|Include Directories if you changed
the default setup.
For each BIDS ADT (abstract data type), such as Stack,
there is a header file called stacks.h. The Object-
based class Stack is declared in stack.h. If the
identifier TEMPLATES is #defined, either in an .h file
or via the command line _D option, then when stack.h is
preprocessed, the Object-based declarations for Stack
are bypassed and the template versions are included. In
particular, if TEMPLATES is #defined, Stack is #defined
as BI_TCStackAsList, so any code written for the
Object-based Stack will be compiled with the BIDS
version.
The OBJS directory =======================================================
Subdirectories of the OBJS directory contain .PRJ file
samples.
The SOURCE =======================================================
directory
The SOURCE directory contains the source files that
implement many of the member functions of the classes
in the library. These source files are provided as a
guide for implementing new classes.
- 32 -

You also need these source files if you want to build a
library. There are project files for small and large
models, debug and non-debug versions, and template and
non-template versions.
------------------ To create a new library using the small memory model,
Creating a library proceed as follows:
------------------
1. Open the CLASSLIBS\OBJS\S (for standard or BIDS) or
CLASSLIBS\OBJS\DBS (for debug) directory.
2. Create a directory for the new library.
3. Copy the project file that's closest to the one you
want to create to that directory (use TCLASSS.PRJ to
create a standard classlib, TCLASDBS.PRJ to create a
debug version, or BIDSS.PRJ to create a templatized
version).
4. Rename the project file to TCLASSS.PRJ.
5. Run TC and select Project|Open TCLASSS.PRJ.
6. Set Options|Compiler|Code Generation to the small
memory model.
7. Select Compile|Build all.
8. Copy the resultant .LIB file to the CLASSLIB\LIB
directory.
For a large memory model, in step 2 copy a xL.PRJ file
and in step 3 rename it to TCLASSL.PRJ.
Important! When you take a library that you have built and use it
in one of the sample projects, you must update the
project. See Chapter 7, "Managing multi-file projects"
for more information. You must also be sure to compile
your project with precisely the same switches and op-
tions you used to build the library. If you don't have
the same options, you will get warnings from the linker
when the executable file is built.

- 33 -

The LIB directory =======================================================
The LIB directory contains the compiled source modules
archived into a library. You must put this directory on
the library search path when you link your program. For
information about modifying the library search path,
see Chapter 8, "The command-line compiler" (for
command-line options).
The Object-based container classes are in TCLASSx.LIB,
where x is the memory-model designation (S for small, C
for compact, M for medium, L for large, and H for
huge). For each of these there are debugging versions
TCLASDBx.LIB.
The EXAMPLES =======================================================
directory
The CLASSLIB\EXAMPLES directory contains the example
programs and their project files. You can compile these
programs to see how the parts of the class library are
put together to form an application. Most of the
examples use one or two of the classes in the
hierarchy; other examples are more complex. Here is a
list of the example programs and the classes that they
use:
1. STRNGMAX: A very simple example using String.
2. REVERSE: An intermediate example using Stack and
String.
3. LOOKUP: An intermediate example using Dictionary and
Association.
4. QUEUETST: An intermediate example using Queue and
introducing a non-hierarchical class, Time.
5. DIRECTRY: An advanced example illustrating derived
user classes with SortedArray.

- 34 -

===========================================================================
Preconditions and checks
===========================================================================
Version 3.0 offers some new debugging tools. The class
libraries TCLASDBx.LIB and BIDSDBx.LIB (where x
represents the memory model, S, C, L, M, or H) provide
the debugging versions of TCLASSx.LIB and BIDSx.LIB.
checks.h defines two macros, PRECONDITION( arg ) and
CHECK( arg ). Each macro takes an arbitrary expression
as an argument, just like assert. At runtime, if the
expression evaluates to 0, an error message is
displayed and execution terminates. If the expression
evaluates to a nonzero value, execution continues in
the normal fashion.
Use PRECONDITION on entry to a function to check the
validity of the arguments and to do any other checking
to determine that the function has been invoked
correctly.
Use CHECK for internal checking during the course of
execution of the function.
Compilation of PRECONDITION and CHECK is controlled by
the value of a manifest constant named __DEBUG. If
__DEBUG has the value 0, PRECONDITION and CHECK are set
to empty macros. In other words, setting __DEBUG to 0
removes all debugging. If __DEBUG has the value 1,
PRECONDITION macros are expanded into the tests
described above, but CHECK macros are empty. So,
setting __DEBUG to 1 enables PRECONDITIONs and disables
CHECKs. Setting __DEBUG to 2 or more, or not defining
it at all, enables both forms of testing. Table 6
summarizes the available debugging modes:
-----------------------------------------------------------------
Class debugging __DEBUG PRECONDITION CHECK
modes -----------------------------------------------------------------
0 Off Off
1 On Off
>1 On On
undefined On On

- 35 -

-----------------------------------------------------------------
When developing a class, set __DEBUG to 2 or leave it
undefined. This gives you maximum checking when the
code is still being worked on. When the class works
properly, but the application that is going to use the
class hasn't been completed, set __DEBUG to 1, so that
incorrect calls from the application can be caught,
without the additional overhead of the internal
checking within the class. Once everything is working,
set __DEBUG to 0 to remove all checking. Two versions
of the .LIB file are provided that contain the class
library code: one with PRECONDITIONs enabled, and one
with no debugging. These are named TCLASDBX.LIB and
TCLASSX.LIB, where X is replaced with the letter for
the appropriate memory model: s, c, m, l, or h. The
.LIB with DB in its name is the one with PRECONDITIONs
enabled.
===========================================================================
Container class reference
===========================================================================
This section describes each class in the library as
follows. We give the include file where it is defined,
a diagram showing the parent of each class and
immediate offspring, some introductory remarks, data
members and member functions (with protoypes) listed
alphabetically, what friendly relations exist, and,
where appropriate, an example of the class's use. The
members listed in the See also section belong to the
class under discussion unless scope-qualified. Thus in
the section on class X, you could find See also foo,
Y::foo, and so on. The first foo refers to X::foo.
Class derivations and class members are public unless
otherwise noted as protected. We do not document
destructors since they all perform the usual way. Most
container classes have virtual destructors.

- 36 -

AbstractArray
===========================================================================
AbstractArray abstarry.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Collection ÃÄÄ¶AbstractArrayÇÄÂÄ´ Array ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´SortedArray ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
The abstract class AbstractArray offers random access
to the elements of the collection via an indexing
mechanism that maps a range of integers to the array
elements. Indexes can be positive or negative integers
with arbitrary lower and upper bounds (within the range
of int). Arrays derived from AbstractArray can be
dynamically resized as elements are added to them. The
data member delta determines how many additional
elements are assigned to the array when overflow
occurs. AbstractArray exists because the derived
classes SortedArray and Array have enough in common to
warrant combining the common properties into an
abstract base class. Since the derived classes differ
only in the implementation of the member functions
detach and the subscript operator, the remaining
functions can be encapsulated in AbstractArray.
Data members =======================================================
delta sizeType delta; protected
delta represents the additional number of elements that
will be assigned to the array if overflow occurs. If
delta is zero, the array will not be resized following
overflow.
lastElementIndex int lastElementIndex; protected
The index value of the last element added to the array.
For an empty array this data member has the value
(lowerbound - 1).
lowerbound int lowerbound; protected

- 37 -

AbstractArray
The lower bound of the array index, returned by the
lowerBound member function. lowerbound is the minimum
legal value of the absolute index.
See also: lowerBound
upperbound int upperbound; protected
The current upper bound of the array index, returned by
the upperBound member function. upperbound is the
maximum legal value of the absolute index.
See also: upperBound
Member functions =======================================================
destroy void destroy( int atIndex );
Removes the object at the given index. Whether the
object itself is destroyed or not depends on the
array's ownership status. If the array currently owns
the object, the object will be destroyed, otherwise the
object survives. destroy is implemented with detach(
atIndex, DefDelete ).
arraySize sizeType arraySize() const;
Returns the current number of cells allocated
(upperbound - lowerbound + 1).
constructor AbstractArray( int anUpper, int aLower = 0, sizeType
aDelta = 0 );
Constructs and "zeroes" an array, given the upper and
lower index bounds. The default lower bound is 0, the
traditional origin for C arrays. The default delta is
also zero, giving a fixed, nonresizable array. If delta
is nonzero, run-time array overflow invokes the
reallocate member function to provide more space (in
increments of delta). A PRECONDITION is set to test if
the lower bound is greater than or equal to the lower
bound.
detach virtual void detach( int atIndex, DeleteType dt =
NoDelete );
- 38 -

AbstractArray
virtual void detach( Object& toDetach, DeleteType dt =
NoDelete );
The first version removes the object at atIndex; the
second version removes the object toDetach. The value
of dt and the current ownership setting determine
whether the object itself will be deleted. DeleteType
is defined in the base class TShouldDelete as enum {
NoDelete, DefDelete, Delete }. The default value of dt,
NoDelete, means that the object will not be deleted
regardless of ownership. With dt set to Delete, the
object will be deleted regardless of ownership. If dt
is set to DefDelete, the object will only be deleted if
the array owns its elements.
See also: TShouldDelete::ownsElements
initIterator virtual ContainerIterator& initIterator() const;
Creates an external iterator for this array.
See also: ContainerIterator class
isEqual int isEqual( const Object& testObject ) const;
Returns 1 if the testObject array is equal to the
calling array. Equal means that the two arrays have the
same object ID, the arrays' dimensions are equal, and
that their components are equal in each index position.
Otherwise, isEqual returns 0.
lowerBound int lowerBound() const;
Returns the array's lowerbound.
objectAt Object& objectAt( int atIndex ) const; protected
Returns a reference to the element at the given index.
See also: operator []
operator [] Object& operator []( int atIndex ) const;
Returns a reference to the object at the given array
index.
printContentsOn void printContentsOn( ostream& outputStream ) const;
- 39 -

AbstractArray
Prints an array, with header and trailer, to the given
stream.
ptrAt Object *ptrAt( int atIndex ) const; protected
Returns a pointer to the element at the given index.
reallocate void reallocate( sizeType newSize ); protected
If delta is zero, reallocate gives an __EEXPANDFS
error. Otherwise, reallocate tries to create a new
array of size newSize (adjusted upwards to the nearest
multiple of delta). The existing array is copied to the
expanded array and then deleted. Unused elements in the
new array are zeroed. An __ENOMEM error is invoked if
there is insufficient memory for the reallocation.
removeEntry void removeEntry( int loc ); protected
Reduces the array by one element. Elements from index
(loc + 1) upwards are copied to positions loc, (loc +
1), and so on. The original element at loc is lost.
setData void setData( int loc, Object *data ); protected
The given data replaces the existing element at the
index loc.
squeezeEntry void squeezeEntry( int squeezePoint ); protected
Reduces the array by one element. As for removeEntry
but squeezePoint is an index relative to the lower
bound
upperBound int upperBound() const;
Returns the array's current upperbound.
Friends =======================================================
ArrayIterator is a friend of AbstractArray

- 40 -

Array
===========================================================================
Array array.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³AbstractArrayÃÄÄ¶ Array º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class Array is derived from class
AbstractArray. An Array object defines an array in
which the ordering of the elements is arbitrary. That
is, the element at index i of the array need have no
relationship to the element at index i + 1.
Array adds the functions add and addAt. While add
stores a given object at the next free place in the
array (expanding the array if necessary), addAt stores
the object at a specified index.
Example =======================================================
Source #include <iostream.h>
#include <array.h>
#include <strng.h>
#include <assoc.h>
int main()
{
Array a(2);
String *s1 = new String("a string");
String *s2 = new String("another string");
Association *a1 = new Association(*s1,*s2);
// Put some objects in the array
a.add(*s1);
a.add(*s2);
a.add(*a1);
// Print as a Container
cout << "As a container:\n" << a << endl << endl;
// Print as an Array
cout << "As an array:\n";
a.printContentsOn(cout);
// Print as elements
- 41 -

Array
cout << "\nAs elements:\n";
for (int i = 0; i < a.arraySize(); ++i)
cout << a[i] << endl;
return(0);
}
Output As a container:
Array { a string,
another atring,
Association { a string, another string }
}
As an array:
Array { a string,
another atring,
Association { a string, another string }
}
As elements:
a string
another string
Association { a string, another string}
Member functions =======================================================
add virtual void add( Object& toAdd );
Adds the given object at the next available index at
the end of an array. Adding an element beyond the upper
bound leads to an overflow condition. If overflow
occurs and delta is nonzero, the array is expanded (by
sufficient multiples of delta bytes) to accommodate the
addition. If delta is zero, overflow gives an error.
addAt void addAt( Object& toAdd, int atIndex );
Writes the given object at the specified index. If that
index is occupied, the previous object is deleted. If
atIndex is beyond the upper bound, the array is
expanded if delta is nonzero. If delta is zero,
attempting to addAt beyond the upper bound gives an
error.
constructor Array( int anUpper, int aLower = 0, sizeType Delta = 0
);
- 42 -

Array
Constructs and "zeroes" an array by calling the base
AbstractArray constructor.
See also: AbstractArray::AbstractArray
isA virtual classType isA() const;
Returns arrayClass, the Arrays type ID.
nameOf virtual char *nameOf() const;
Returns "Array", the Array type ID string.
===========================================================================
ArrayIterator abstarry.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ContainerIteratorÃÄÄ¶ ArrayIterator º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
Provides iterator functions to traverse objects of the
class AbstractArray and its derived classes.
ArrayIterator is a friend class of AbstractArray
Member functions =======================================================
constructor ArrayIterator( const AbstractArray& toIterate );
Creates an iterator object for the given array.
See also: restart
current virtual Object& current();
Returns the object at the current index of the
iterator. If the current index doesn't refer to a valid
object, NOOBJECT is returned.
operator ++ virtual Object& operator ++ ();
virtual Object& operator ++ ( int );
See ContainerIterator operator ++
operator int() virtual operator int();
- 43 -

ArrayIterator
Conversion operator to test for end of iterator
position.
restart virtual void restart();
Sets the current index of the iterator to the first
nonempty object in the array.
===========================================================================
Association assoc.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Object ÃÄÄ¶Association º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The Association class provides a simple mechanism for
associating two objects, known as the value object and
the key object, in one Association type object. These
combined objects are typically stored in a Dictionary
type object, which provides member functions to
retrieve the value when given the key, providing the
basic tools for many data-retrieval applications.
Member functions =======================================================
constructor Association( Object& key, Object& value );
Constructs an association object from the given key and
value objects.
constructor Association( const Association& a );
Copy constructor.
hashValue virtual hashValueType hashValue() const;
Returns the hash value of the association's key. See
HashTable::hashValue for more details.
isA virtual classType isA() const;
Returns associationClass, the Association type ID.
- 44 -

Association
isAssociation virtual int isAssociation() const;
Returns 1 for association objects (and 0 for other
object types).
isEqual virtual int isEqual( const Object& toObject ) const;
Returns 1 if toObject and the calling association have
equal keys, otherwise returns 0.
key Object& key() const;
Returns the key object of the association.
nameOf virtual char *nameOf() const;
Returns "Association", the Association type ID string.
printOn virtual void printOn( ostream& outputStream ) const;
operator << is a Prints the association on the given output stream.
friend of Object. printOn is really for internal use by the overloaded
See page 87. operator <<.
value Object& value() const;
Returns the value object of the association.
Example =======================================================
Source // File TASSOC.CPP: Illustrates the Association class
#include <string.h> // For strlen()
#include <strng.h>
#include <assoc.h>
#include <iostream.h>
void identify(Object&);
main()
{
char s1[21], s2[81];
// Read a key
cout << "Enter a key: ";
cin >> s1;
cin.get(); // Eat newline
- 45 -

Association
String str1(s1);
identify(str1);
// Read a value
cout << "Enter a value: ";
cin.getline(s2,81);
s2[strlen(s2) - 1] = '\0';
String str2(s2);
identify(str2);
Association a1(str1,str2);
identify(a1);
Association a2 = a1;
identify(a2);
cout << "Equal: " << a1.isEqual(a2) << endl;
}
void identify(Object& o)
{
// Echo an object and its type
cout << "Value: " << o
<< ", Object type: " << o.nameOf()
<< endl << endl;
}
Output Enter a key: class
Value: class, Object type: String
Enter a value: A group of related objects
Value: A group of related objects, Object type: String
Value: Association { class, A group of related
objects }
, Object type: Association
Value: Association { class, A group of related
objects }
, Object type: Association
Equal: 1

- 46 -

Bag
===========================================================================
Bag bag.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Collection ÃÄÄ¶ Bag ÇÄÄ´ Set ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
A Bag is an unordered collection that may contain more
than one of the same object. Bag also provides the base
class for Set. Unlike Bags, Sets can contain only one
copy of a any given object.
Member functions =======================================================
add virtual void add( Object& toAdd );
Adds the given object at the next available index at
the end of an array. Adding an element beyond the upper
bound leads to an overflow condition. If overflow
occurs and delta is nonzero, the array is expanded (by
sufficient multiples of delta bytes) to accommodate the
addition. If delta is zero, overflow gives an error.
constructor Bag( sizeType bagSize = DEFAULT_BAG_SIZE );
Constructs an empty bag. bagSize represents the initial
number of slots allocated.
detach virtual void detach( Object& toDetach, DeleteType dt =
NoDelete );
See Array::detach.
findMember virtual Object& findMember( Object& toFind ) const;
Returns the given object if found, otherwise returns
NOOBJECT.
firstThat virtual Object& firstThat( condFuncType testFuncPtr,
void *paramList ) const;
See also: Container::firstThat, Object::firstThat
flush void flush( DeleteType dt = DefDelete );

- 47 -

Bag
Removes all the elements from the bag without
destroying the bag. The value of dt determines whether
the elements themselves are destroyed. By default, the
ownership status of the bag determines their fate, as
explained in the detach member function. You can also
set dt to Delete and NoDelete.
See also: detach
forEach void forEach( void ( *actionFuncPtr)(Object& o, void
*), void *args );
See also: Container::forEach
getItemsInContainer countType getItemsInContainer() const;
Returns the number of items in the bag.
hasMember virtual int hasMember( const Object& obj ) const;
Returns 1 if the given object is found in the bag,
otherwise returns 0.
initIterator ContainerIterator& initIterator() const;
Creates and returns an iterator for this bag.
See also: ContainerIterator class
isA virtual classType isA() const;
Returns bagClass the Bag type ID.
isEmpty int isEmpty() const;
Returns 1 if a container has no elements; otherwise
returns 0.
lastThat virtual Object& lastThat( condFuncType testFuncPtr,
void *paramList ) const;
Returns a reference to the last object in the container
that satisfies a given condition. You supply a
testFuncPtr that returns true for a certain condition.
You can pass arbitrary arguments via the paramList
argument. NOOBJECT is returned if no object in the
container meets the condition. Note that you are not
involved directly with iterators: firstThat and
- 48 -

Bag
lastThat create their own internal iterators, so you
can simply treat them as "search" functions.
See also: firstThat, Object::firstThat,
Container::lastThat
nameOf virtual char *nameOf() const;
Returns "Bag", the Bag type ID string.
ownsElements int ownsElements();
void ownsElements( int del );
See TShouldDelete::ownsElements
===========================================================================
BaseDate ldate.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Sortable ÃÄÄ¶ BaseDate ÇÄÄ´ Date ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
BaseDate is an abstract class derived from Sortable
that provides basic date manipulation functions.
Member functions =======================================================
constructor BaseDate(); protected
Creates a BaseDate object with the current system date.
constructor BaseDate( unsigned char M, unsigned char D, unsigned Y
); protected
Creates a BaseDate object with the given month, day,
and year.
constructor BaseDate( const BaseDate& BD ); protected
Copy constructor.
Day unsigned Day() const;
Returns the day of the month.
- 49 -

BaseDate
hashValue virtual hashValueType hashValue() const;
Returns the hash value of the date object. See
HashTable::hashValue for more details.
isA virtual classType isA() const = 0;
A pure virtual function to return a classtype ID (to be
defined in derived classes).
isEqual virtual int isEqual( const Object& testDate ) const;
Returns 1 if the object represents the same date as
testDate. Otherwise returns 0.
isLessThan virtual int isLessThan( const Object& testDate ) const;
Returns 1 if the object precedes testDate on the
calendar.
Month unsigned Month() const;
Returns the month.
nameOf virtual char *nameOf() const = 0;
Pure virtual function to be defined by derived classes
to return their object ID string.
printOn virtual void printOn( ostream& outputStream ) const =
0;
operator << is a Pure virtual function to be defined in derived classes
friend of Object. to print the date object on the given stream. printOn
See page 87. is for internal use by the overloaded operator <<.
SetDay void SetDay( unsigned char D );
Sets the day to D.
SetMonth void SetMonth( unsigned char M );
Sets the month to M.
SetYear void SetYear( unsigned Y );
Sets the year to Y.
- 50 -

BaseDate
Year unsigned Year() const;
Returns the year.
===========================================================================
BaseTime ltime.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Sortable ÃÄÄ¶ BaseTime ÇÄÄ´ Time ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
BaseTime is an abstract class derived from Sortable
that provides basic time manipulation functions.
Member functions =======================================================
constructor BaseTime(); protected
Creates a BaseTime object with the current system time.
constructor BaseTime( const BaseTime& BT ); protected
Copy constructor.
constructor BaseTime( unsigned char H, unsigned char M = 0,
unsigned char S = 0, unsigned char HD = 0
); protected
Creates a BaseTime object with the given hour, minutes,
seconds, and hundredths of seconds.
hashValue virtual hashValueType hashValue() const;
Returns the hash value of the BaseTime object. See
HashTable::hashValue for more details.
hour unsigned hour() const;
Returns the hour.
hundredths unsigned hundredths() const;

- 51 -

BaseTime
Returns the hundredths of a second.
isA virtual classType isA() const = 0;
Pure virtual function for a derived class to return its
class ID.
isEqual virtual int isEqual( const Object& testTime ) const;
Returns 1 if this object equals testTime; otherwise
returns 0.
isLessThan virtual int isLessThan( const Object& testTime ) const;
Returns 1 if this object is less than testTime;
otherwise returns 0 .
minute unsigned minute() const;
Returns the minute.
nameOf virtual char *nameOf() const = 0;
Pure virtual function to be defined by derived classes
to return their object ID string.
printOn virtual void printOn( ostream& outStream ) const = 0;
operator << is a Pure virtual function to be defined in derived classes
friend of Object. to print the time object on the given stream. printOn
See page 87. is for internal use by the overloaded operator <<.
second unsigned second() const;
Returns the seconds.
setHour void setHour( unsigned char H );
Sets the hour to H.
setHundredths void setHundredths( unsigned char HD );
Sets the hundredths of a second to HD.
setMinute void setMinute( unsigned char M );
Sets the minutes.
- 52 -

BaseTime
setSecond void setSecond( unsigned char S );
Sets the seconds.
===========================================================================
Btree btree.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Collection ÃÄÄ¶ Btree º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The class Btree, derived from Collection, implements
the B-tree, a popular data structure offering efficient
storage and retrieval with large, dynamic volumes of
data. (A detailed account of Turbo C++ development of
B-tree theory is beyond the scope of this manual: see
BTREE.CPP and D. E Knuth's The Art of Computer
Programming, Volume 3, 6.2.3.). Btree makes use of
several auxiliary, noncontainer friend classes: Node,
Item, InnerNode, and LeafNode (the last two being
derived from Node). You can study these in btree.h.
Here, we will just outline the members of the Btree
class, which should suffice for most applications.
Member functions =======================================================
add void add( Object& );
Add the given object to the B-tree.
constructor Btree( int ordern = 3 );
Creates a B-tree of order ordern (default order is 3).
decrNofKeys void decrNofKeys(); protected
Decrements the itemsInContainer data member
detach void detach( Object& toDetach, DeleteType dt = NoDelete
);

- 53 -

Btree
Removes the given object from the B-tree. The fate of
the removed object depends on the argument dt. See
TShouldDelete for details.
findMember virtual Object& findMember( const Object& toFind )
const;
Returns the given object if found, otherwise returns
NOOBJECT.
flush void flush( DeleteType dt = DefDelete );
Flushes (empties) the B-tree. The fate of the removed
objects depends on the argument dt. See TShouldDelete
for details.
hasMember virtual int hasMember( const Object& obj ) const;
Returns 1 if the given object is found in the B-tree,
otherwise returns 0.
hashValue virtual hashValueType hashValue() const;
Returns the hash value of this B-tree. See
HashTable::hashValue for more details.
i_add long i_add( const Object& obj ); protected
Adds the given object to the tree and returns the index
in the tree at which the object was inserted.
incrNofKeys void incrNofKeys(); protected
Increments the itemsInContainer data member
initIterator virtual ContainerIterator& initIterator() const;
Creates an iterator for this B-tree.
See also: Container::initIterator
isA virtual classType isA() const;
Returns btreeClass, the Btree class ID
isEqual virtual int isEqual( const Object& testObject ) const;
Returns 1 if testObject is the same as this object.
- 54 -

Btree
nameOf virtual char *nameOf() const;
Returns "Btree", the Btree class ID string
operator [] Object& operator[]( long i ) const;
Returns the root at index i
order int order();
Returns the order of the B-tree.
printOn virtual void printOn( ostream& outputStream ) const;
operator << is a Sends the formatted B-tree data to the given output
friend of Object. stream. printOn is for internal use by the overloaded
See page 87. operator <<.
rank long rank( const Object& obj ) const;
Returns the rank of the given object in the B-tree.
Friends =======================================================
Node, InnerNode, and LeafNode are friends of Btree.
===========================================================================
BtreeIterator btree.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ContainerIteratorÃÄÄ¶ BtreeIterator º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
The class BtreeIterator is derived from
ContainerIterator. Its members follow the same scheme
as those for the other container iterators.

- 55 -

BtreeIterator
Member functions =======================================================
constructor BtreeIterator( const Btree& toIterate );
See ContainerIterator constructor
current virtual Object& current();
See ContainerIterator::current
operator ++ virtual Object& operator ++();
virtual Object& operator ++( int );
See ContainerIterator::operator ++
operator int virtual operator int();
Conversion operator to test for end of iterator
position.
restart virtual void restart();
See ContainerIterator::restart

- 56 -

Collection
===========================================================================
Collection collect.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄ´AbstractArray³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´ HashTable ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Container ÃÄÄ¶ Collection ÇÄÅÄ´ List ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´ DoubleList ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´ Bag ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´ Btree ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
Collection is an abstract class derived from the
abstract class Container. This means that although
Collection is more specialized than Container, it still
cannot be used directly for creating useful objects but
exists only as a further stepping stone towards usable,
derived instance classes.
Collection inherits five pure virtual functions (flush,
initIterator, isA, nameOf and getItemsInContainer),
that simply await definitions down the road by derived
instance classes.
Collection extends the functionality of Container in
several areas by adding both virtual and pure virtual
member functions. The extra pure virtual functions are
add and detach. Instance classes ultimately derived
from Collection, therefore, will need to provide
appropriate member functions for adding and removing
elements.
The other (non-pure) virtual member functions added by
Collection are destroy, hasMember, and findMember. The
last two provide the key difference between Collection
and Container. A Collection-derived object can
determine if any given object is a member (with
- 57 -

Collection
hasMember) and, by using an iterator, can locate a
member object within the collection (with findMember).
The offspring of Collection refine these access methods
in various ways, and add other functions. In most
applications, you will be dealing directly with a
particular derived class of Collection, chosen to match
your needs: sorted and unsorted arrays, hash tables,
bags, sets, dictionaries, and single and double lists.
However, it is useful to have a feel for how these
instance classes build up from abstract classes, and
why it is useful to have intermediate abstract classes.
Member functions =======================================================
add virtual void add( Object& o ) = 0;
Pure virtual function to be defined in derived classes
to add an object to a collection.
constructor Uses the Container base constructor.
destroy void destroy( const Object& o );
Removes an object from a Collection. Whether the object
itself is destroyed or not depends on the ownership
status of the collection. If the collection currently
owns the object, the object will be destroyed,
otherwise the object survives. destroy is implemented
with detach( o, DefDelete );
See also: TShouldDelete::ownsElements
detach virtual void detach( Object& o, DeleteType dt =
NoDelete) = 0;
Pure virtual function to be defined in derived classes
to remove an object from a collection. The destruction
of the object depends both on the ownership status and
the value (Delete, NoDelete, or DefDelete) passed via
the dt argument.
See also: destroy, TShouldDelete::ownsElements
findMember virtual Object& findMember( const Object& testObject )
const;
- 58 -

Collection
Returns the test object if it is in the collection,
otherwise returns NOOBJECT.
hasMember virtual int hasMember( const Object& o ) const;
Returns 1 if the collection contains the given object.
===========================================================================
Container contain.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄ´ Collection ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Object ÃÄÄ¶ Container ÇÄÅÄ´ Stack ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´ PriorityQueue ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´ Deque ÃÄ´ Queue ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ

The abstract class Container, derived directly from
Object, is the base for all the container classes.
Container has a second pure virtual base class (not
shown) called TShouldDelete. Container provides the
following functionality:
1. A container can store objects of other classes,
known as elements or items. (The objects in a
container are sometimes called "members" of the
container, but this usage can lead to ambiguities in
C++.) A container can flush itself by removing all
its elements.
2. A container can determine the number of objects it
holds. Empty containers are allowed.
3. Container is also derived from TShouldDelete
(multiple inheritance), which lets you control the
ownership of a container's elements. By default, a
container owns its elements, meaning that it will
- 59 -

Container
destroy them when its destructor is called or when
it is flushed.
4. A container can create external iterators, objects
of type ContainerIterator, which can be used to
traverse the container, element by element. With
external iterators, you need to handle the scanning
of the elements yourself. Other iterators, known as
internal iterators, are generated automatically by
certain member functions. These do their own loop
tests and can perform arbitrary actions on each
element (forEach). Member functions are also
available for scanning the container until a certain
condition is satisfied (firstThat, lastThat).
5. A container can test if it is equal to another
container.
6. A container can display its elements on streams in a
formatted way. A printOn function is provided from
which the usual overloaded << output operator can be
obtained.
Strictly speaking, some of the above member functions
are pure virtual functions that need to be defined in
derived classes. See Collection class for a more
detailed discussion.
Specialized containers are derived to two ways:
directly derived are the classes Stack, PriorityQueue,
and Deque (from which Queue is derived). Derived
indirectly via another abstract class, Collection, are
AbstractArray, HashTable, Bag, Btree, List, and
DoubleList.
itemsInContainer countType itemsInContainer; protected
Holds the current number of elements in the container.
See also: getItemsInContainer
Member functions =======================================================
constructor Container();
Creates an empty container.
- 60 -

Container
firstThat virtual Object& firstThat( condFuncType testFuncPtr,
void *paramList ) const;
Returns a reference to the first object in the
container that satisfies a given condition. You supply
a testFuncPtr that returns true for a certain
condition. You can pass arbitrary arguments via the
paramList argument. NOOBJECT is returned if no object
in the container meets the condition. Note that you are
not involved directly with iterators: firstThat and
lastThat create their own internal iterators, so you
can simply treat them as "search" functions.
See also: lastThat, Object::firstThat
flush virtual void flush( DeleteType dt = DefDelete ) = 0;
A pure virtual function to be defined in derived
classes. Flushing means removing all the elements from
the container without destroying it. The value of dt
determines whether the elements themselves are
destroyed. By default, the ownership status of the
container determines their fate. You can also set dt to
Delete and NoDelete.
See also: TShouldDelete::ownsElements
forEach virtual void forEach( iterFuncType actionFuncPtr, void
*args );
forEach creates an internal iterator to execute the
given action function for each element in the
container. The args argument lets you pass arbitrary
data to the action function.
getItemsInContainer virtual countType getItemsInContainer() const = 0;
Pure virtual function to be defined by derived classes
to return the number of elements in a container.
hashValue virtual hashValueType hashValue() const = 0;
A pure virtual function to be defined by derived
classes to return the hash value of an object. See
HashTable::hashValue for more details.
initIterator virtual ContainerIterator& initIterator() const = 0;
- 61 -

Container
Pure virtual function to be defined in derived classes
to initialize an external container iterator.
isA virtual classType isA() const = 0;
Pure virtual function to be defined in derived classes
to return their class ID.
isEmpty virtual int isEmpty() const = 0;
Pure virtual function to be defined in derived classes.
Returns 1 if a container has no elements; otherwise
returns 0.
isEqual virtual int isEqual( const Object& testObject ) const;
Returns 1 if the testObject is a container of the same
type and size as this container, and with the same
objects in the same order. Otherwise returns 0.
lastThat virtual Object& lastThat( condFuncType testFuncPtr,
void *paramList ) const;
Returns a reference to the last object in the container
that satisfies a given condition. You supply a
testFuncPtr that returns true for a certain condition.
You can pass arbitrary arguments via the paramList
argument. NOOBJECT is returned if no object in the
container meets the condition. Note that you are not
involved directly with iterators: firstThat and
lastThat create their own internal iterators, so you
can simply treat them as "search" functions.
See also: firstThat, Object::firstThat
nameOf virtual char *nameOf() const = 0;
Pure virtual function to be defined by derived classes
to return their object type ID string (usually the
unique class name).
printHeader virtual void printHeader( ostream& outputStream )
const;
Sends a standard header for containers to the output
stream (called by printOn).
See also: printOn, printSeparator, printTrailer
- 62 -

Container
printOn virtual void printOn( ostream& outputStream ) const;
operator << is a Sends a formatted representation of the container to
friend of Object. the given output stream. printOn is for internal use by
See page 87. the overloaded operator <<.
See also: printHeader, printSeparator, printTrailer
printSeparator virtual void printSeparator( ostream& outputStream )
const;
Sends to the output stream a separator (comma) between
elements in a container (called by printOn).
See also: printOn, printHeader, printTrailer
printTrailer virtual void printTrailer( ostream& outputStream )
const;
Sends to the output stream a standard trailer (a
closing brace) for a container (called by printOn).
See also: printOn, printHeader, printSeparator
Friends =======================================================
ContainerIterator is a friend of Container.

- 63 -

ContainerIterator
===========================================================================
ContainerIterator contain.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄ´HashTableIterator ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ºContainerIteratorÇÄÅÄ´ ListIterator ³
ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´DoubleListIterator³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´ BtreeIterator ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´ ArrayIterator ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ContainerIterator is an abstract class declared as a
friend of Container. Container classes have
initIterator member functions that create
ContainerIterator-derived objects. These provide the
basic mechanisms for traversing the elements in a
container: incrementing through the container;
returning positional information; testing for
conditions, and so on. The member functions for
ContainerIterator are all pure virtual and are defined
in derived classes. See page 11 for more on the
ContainerIterator hierarchy.
Member functions =======================================================
current virtual Object& current() = 0;
Pure virtual function to be defined in derived classes
to return the current element. If the current element
is empty or invalid, NOOBJECT is returned.
operator int virtual operator int() = 0;
Pure virtual function to be defined by derived classes
to provide a conversion operator to test for end of
iteration condition.
- 64 -

ContainerIterator
operator ++ virtual Object& operator ++() = 0;
virtual Object& operator ++( int ) = 0;
Advances the iterator one position in the container.
The first version returns the object referred to before
incrementing; the second version returns the object
referred to after incrementing. The int argument is a
dummy used to distinguish the two operators (see the
section on Operator Overloading in the Programmer's
Guide).
restart virtual void restart() = 0;
Pure virtual function to be refined in derived classes
to set the current index of the iterator to the first
nonempty element in the container.
===========================================================================
Date ldate.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ BaseDate ÃÄÄ¶ Date º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The Date instance class is a direct descendant of the
abstract class BaseDate, defining a printOn function.
You can vary Date for different national conventions
without disturbing BaseDate.
Member functions =======================================================
constructor Date();
Calls the BaseDate constructor to create a date object
with today's date.
constructor Date( unsigned char M, unsigned char D, unsigned Y );
Calls the BaseDate constructor to create a date object
with the given date.
constructor Date( const Date& aDate );

- 65 -

Date
Copy constructor.
isA virtual classType isA() const;
Returns dateClass, the Date class ID.
nameOf virtual char *nameOf() const;
Returns "Date", the Date class ID string.
printOn virtual void printOn( ostream& outputStream ) const;
operator << is a Sends a formatted date to the given output stream. The
friend of Object. format is full month name, day, year, for example
See page 87. January 1, 1990. printOn is really for internal use by
the overloaded operator <<.
===========================================================================
Deque deque.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Container ÃÄÄ¶ Deque ÇÄ´ Queue ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
The instance class Deque (pronounced "deck"), derived
from Container, implements a double-ended queue so it
is one of the sequence classes. Objects can be
examined, inserted, and removed at both the left and
the right ends but nowhere else. You can use the member
functions peekLeft and peekRight to examine the objects
currently at the left and the right ends. putLeft and
putRight insert objects at the ends. The getLeft and
getRight members also access the end objects but detach
them from the deque. The fate of the objects removed
from the deque is determined by the same ownership and
DeleteType considerations discussed in the
TShouldDelete class (recall that TShouldDelete is a
virtual base class for Container). Deque also acts as
the base class for Queue.

- 66 -

Deque
Example =======================================================
Source #include <deque.h>
#include <strng.h>
main()
{
Deque d;
String *s1 = new String("one");
String *s2 = new String("two");
String *s3 = new String("three");
String *s4 = new String("four");
// Populate the deque
d.putLeft(*s1);
d.putRight(*s2);
d.putLeft(*s3);
d.putRight(*s4);
// Print to cout
cout << "As a container:\n" << d << endl;
// Empty to cout
cout << "As a Deque:\n";
while (!d.isEmpty())
{
cout << d.getLeft() << endl;
}
// Should be empty
cout << "\nShould be empty:\n" << d;
}
Output As a container:
Deque { three,
one,
two,
four }
As a Deque:
three
one
two
four
Should be empty:

- 67 -

Deque
Deque { }
Member functions =======================================================
flush virtual void flush( DeleteType dt = DefDefault );
Flushes (empties) the deque without destroying it. The
fate of any objects thus removed depends on the current
ownership status and the value of the dt argument.
See also: TShouldDelete::ownsElements
getItemsInContainer virtual countType getItemsInContainer() const;
Returns the number of items in the deque.
getLeft Object& getLeft();
Returns the object at the left end and removes it from
the deque. Returns NOOBJECT if the deque is empty.
See also: TShouldDelete class
getRight Object& getRight();
As for getLeft, except that the right end of the deque
is returned.
See also: getLeft
initIterator virtual ContainerIterator& initIterator() const;
Initializes an iterator for the deque.
See also: Container::initIterator
isA virtual classType isA() const;
Returns dequeClass, the Deque class ID.
isEmpty virtual int isEmpty() const;
Returns 1 if a container has no elements; otherwise
returns 0.
nameOf virtual char *nameOf() const;
- 68 -

Deque
Returns "Deque", the Deque class ID string.
peekLeft Object& peekLeft() const;
Returns the object at the left end (head) of the deque.
The object stays in the deque.
peekRight Object& peekRight()
Returns the object at the right end (tail) of the
deque. The object stays in the deque.
putLeft void putLeft( Object& obj );
Adds (pushes) the given object at the left end (head)
of the deque.
putRight void putRight(Object& obj)
Adds (pushes) the given object at the right end (tail)
of the deque.
===========================================================================
Dictionary dict.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Set ÃÄÄ¶ Dictionary º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
A dictionary is a special collection of Association
type objects. The instance class Dictionary is derived
from Collection via Bag and Set, implying that no
duplicate association objects are allowed in a
dictionary. Dictionary overrides the add function and
adds a lookup function to the members inherited from
Set. lookup allows you to retrieve the value object of
an association stored in the dictionary if you supply
the key.
Member functions =======================================================
add virtual void add( Object& assoc );

- 69 -

Dictionary
Adds the given association (assoc) to the dictionary.
If the given argument is not of type Association, a
runtime error occurs.
constructor Dictionary( unsigned sz = DEFAULT_HASH_TABLE_SIZE );
Invokes the base Set constructor to create an empty
dictionary of size sz.
isA virtual classType isA() const;
Returns dictionaryClass, the Dictionary class ID.
lookup Association& lookup( const Object& toLookUp ) const;
Returns the association matching the toLookUp key. If
no match is found, NOOBJECT is returned.
nameOf virtual char *nameOf() const;
Returns "Dictionary", the Dictionary class ID string.
===========================================================================
DoubleList dbllist.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Collection ÃÄÄ¶ DoubleList º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class DoubleList, derived from Collection,
implements the classical doubly-linked list data
structure (see D. E Knuth's The Art of Computer
Programming, Volume 1, 2.2.5). Briefly, each node
object of a doubly-linked list has two links, one
pointing to the next node and one pointing to the
previous node. The extreme nodes are called the head
and the tail. As with the Deque class, you can examine,
add, and remove objects at either end of the list.

- 70 -

DoubleList
Member functions =======================================================
add virtual void add( Object& toAdd );
Add the given object at the beginning of the list.
addAtHead void addAtHead( Object& toAdd );
Adds the given object at the beginning (head) of the
list.
addAtTail void addAtTail( Object& toAdd );
Adds the given object at the end (tail) the list.
constructor DoubleList();
Creates a new, empty doubly-linked list.
destroyFromHead void destroyFromHead( const Object& toDestroy );
Detaches the first occurrence of the given object
encountered by searching from the beginning of the
list. The object is destroyed only if it is owned by
the list.
destroyFromTail void destroyFromTail( const Object& toDestroy );
Detaches the first occurrence of the given object
encountered by searching from the tail of the list
towards the head. The object is destroyed only if it is
owned by the list.
detach virtual void detach( Object& toDetach, DeleteType dt =
NoDelete );
Calls detachFromHead( toDetach, dt);
detachFromHead void detachFromHead( const Object& toDetach, DeleteType
dt = NoDelete );
Removes the first occurrence of the given object
encountered by searching from the beginning of the
list. The dt argument determines if the detached object
is itself destroyed. See TShouldDelete for details.

- 71 -

DoubleList
detachFromTail void detachFromTail( const Object& toDetach, DeleteType
dt = NoDelete );
Removes the first occurrence of the object starting at
the tail of the list and scanning towards the head. The
dt argument determines if the detached object is itself
destroyed. See TShouldDelete for details.
flush virtual void flush( DeleteType dt = DefDelete);
Flushes (empties) the list without destroying it. The
fate of the objects thus removed is determined by the
dt argument as explained at TShouldDelete. The default
value of dt means that the removed objects will be
destroyed only if the list owns these objects.
See also: TShouldDelete::ownsElements
initIterator virtual ContainerIterator& initIterator() const;
Creates and returns a forward (from head to tail)
iterator for the list.
isA virtual classType isA() const;
Returns doubleListClass, the DoubleList class ID.
nameOf virtual char *nameOf() const;
Returns "DoubleList", the DoubleList class ID string.
peekAtHead Object& peekAtHead() const;
Returns the object at the head of the list (without
removing it).
peekAtTail Object& peekAtTail() const;
Returns the object at the tail of the list (without
removing it).

- 72 -

DoubleList
Friends =======================================================
DoubleListIterator is a friend of DoubleList
===========================================================================
DoubleListIterator dbllist.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ContainerIteratorÃÄÄ¶DoubleListIteratorº
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
DoubleListIterator, derived from ContainerIterator,
implements the special iterators for traversing
doubly-linked lists in either direction. This class
adds overloading of the pre- and postdecrement operator
- - to allow reverse iteration. For more details on
iterators, see ContainerIterator, and
DoubleList::initIterator.
Member functions =======================================================
constructor DoubleListIterator(const DoubleList& toIterate, int
atHead = 1);
Creates an iterator for the given list. The iterator
will begin at the head of the list if atHead is 1 ,
otherwise it starts at the tail.
current virtual Object& current();
Returns the object at the current index of the
iterator. If the current index exceeds the upper bound,
NOOBJECT is returned.
operator ++ virtual Object& operator ++ ( int );
virtual Object& operator ++ ();
See ContainerIterator operator ++
operator - - Object& operator - - ( int );
Object& operator - - ();

- 73 -

DoubleListIterator
Moves the iterator back one position in the list. The
object returned is either the current object
(postdecrement) or the object at the new position
(predecrement), or NOOBJECT if no valid object at the
relevant position. The first version gives
postdecrement, the second gives predecrement. The int
argument is a dummy serving only to distinguish the two
operators.
operator int virtual operator int();
Conversion operator to test for the end of an iteration
condition.
restart virtual void restart();
Moves the iterator back to its starting position at the
head of the list.
See also: DoubleListIterator constructor
===========================================================================
Error object.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Object ÃÄÄ¶ Error º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The class Error is a special instance class derived
from Object. There is just one instance of class Error,
namely theErrorObject. Pointing to this global object
is the static object pointer Object::ZERO. NOOBJECT is
defined as *(Object::ZERO) in object.h. The operator
Object::operator new returns a pointer to
theErrorObject if an attempt to allocate an object
fails. You may test the return value of the new
operator against Object::ZERO to see whether the
allocation failed.
NOOBJECT is rather like a null pointer, but serves the
vital function of occupying empty slots in a container.
For example, when an Array object is created (not to be
confused with a traditional C array), each of its
elements will initially contain NOOBJECT.

- 74 -

Error
Member functions =======================================================
delete void operator delete(void *);
Invokes a runtime error if an attempt to delete the
Error object is detected.
isA virtual classtype isA() const;
Returns errorClass, the Error class ID.
isEqual virtual int isEqual( const Object& testObject const );
Returns 1 if the test object is the Error object.
nameOf virtual char *nameOf() const;
Returns the Error class ID string.
printOn virtual void printOn(ostream& outputStream ) const;
operator << is a Prints the string "Error\n" on the given stream.
friend of Object. printOn is for internal use by the overloaded operator
See page 87. <<.
===========================================================================
HashTable hashtbl.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Collection ÃÄÄ¶ HashTable º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class HashTable provides an implementation
of an unordered collection in which objects are added
and retrieved via a hashing function. A hash table
provides a fixed array with size slots (usually a prime
number), one for each possible hash value modulo size.
A hashing function computes the hash value for each
object (or a key part of that object) to be added, and
this determines the slot to which the new object is
assigned.

- 75 -

HashTable
For each containable object of class X, the member
function X::HashValue returns a value (of type
hashValueType) between 0 and 65535, which is as
"unique" as possible. This "raw" hash value is reduced
modulo size. We'll use the term hash value to refer to
this reduced value in the range 0 to size - 1. This
hash value serves as an index into the hash table. The
internal organization of the table is hidden, but it
may help you to consider the slots as pointers to
lists.
It should be clear that if you want to store more than
size objects, the hash value cannot be unique for each
object. So two cases arise when an object is added: if
the slot is empty, a new list is assigned to the slot
and the object is stored in the list; if the slot is
already occupied by an object with the same hash value
(known as a collision), the new object is stored in the
existing list attached to the slot. When it comes to
locating an object, the hashing function computes its
hash value to access the appropriate slot. If the slot
is empty, NOOBJECT is returned, otherwise a
List::findMember call locates the object.
Choosing the best HashValue function and table size is
a delicate compromise between avoiding too many
collisions and taking up too much memory. (Other
hashing techniques are available, but the modulo prime
method is the most common. For more on hash table
theory, see D. E. Knuth's The Art of Computer
Programming, Volume 3, 6.4.). Hashing is widely used by
compilers to maintain symbol tables.
Member functions =======================================================
add virtual void add( Object& objectToAdd );
Adds the given object to the hash table.
constructor HashTable( sizeType aPrime = DEFAULT_HASH_TABLE_SIZE );
Creates an empty table. The aPrime argument is a prime
number used in the hashing function (the default is
defined in resource.h).
detach
- 76 -

HashTable
virtual void detach( Object& objectToDetach, DeleteType
dt = NoDelete );
Removes the given object from the hash table. Whether
the object itself is destroyed or not depends on the dt
argument, as explained in TShouldDelete::ownsElements.
findMember virtual Object& findMember( const Object& testObject )
const;
Returns the target object if found, otherwise returns
NOOBJECT.
flush virtual void flush( DeleteType dt = DefDelete );
Removes all the elements from the table without
destroying it. The value of dt determines whether the
elements themselves are destroyed. By default (dt =
DefDelete), the ownership status of the table
determines the fate of all its elements, as explained
in TShouldDelete::ownsElements. You can set dt to
Delete to force destruction of the flushed elements
regardless of ownership. If dt is set to NoDelete, the
flushed elements will survive regardless of ownership.
See also: TShouldDelete::ownsElements
hashValue virtual hashValueType hashValue() const;
Returns the raw hash value of this table. This must not
be confused with the hash values calculated by the hash
table for each of the objects it stores. When an object
x of class X is added or retrieved from a hash table h,
the raw hash value used is x.hashValue(). The true hash
value (usually modulo size) is obtained from the hash
table object via h.getHashValue( x ). Only classes with
a proper hashValue member function can provide objects
for storage in a hash table. All standard Object-
derived classes in the library have meaningful hashing
functions provided. For example, BaseDate::hashValue
(unless overridden) returns the value YY + MM + DD from
which the (private) member function
HashTable::getHashValue computes a hash value (using
mod size). It is this value that governs the hash
table's add, findMember, and detach operations.
initIterator virtual ContainerIterator& initIterator() const;
- 77 -

HashTable
Creates and returns an iterator for the hash table. See
Container::initIterator for more details.
isA virtual classType isA() const;
Returns hashTableClass, the HashTable class ID.
nameOf virtual char *nameOf() const;
Returns "HashTable", the HashTable class ID string.
Friends =======================================================
HashTableIterator is a friend of HashTable
===========================================================================
HashTableIterator hashtbl.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ContainerIteratorÃÄÄ¶HashTableIterator º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
HashTableIterator is an instance class providing
iterator functions for HashTable objects. Since hash
values are stored in an array, hash table iterators use
the array iterator mechanism. See ContainerIterator for
a detailed discussion of iterators.
Member functions =======================================================
constructor HashTableIterator( const Array& toIterate );
See ContainerIterator constructor
current virtual operator Object& current();
See ContainerIterator::current
operator int virtual operator int();
Conversion operator to test for end of iterator
position.
- 78 -

HashTableIterator
operator ++ virtual Object& operator ++ ( int );
virtual Object& operator ++ ();
See ContainerIterator::operator ++
restart virtual void restart()
See ContainerIterator::restart
===========================================================================
List list.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Collection ÃÄÄ¶ List º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class List, derived from Collection,
implements a linear, linked list. Lists are unordered
collections in which objects are linked in one
direction only to form a chain. You can usually add
objects only at the start of a list but any object can
be removed from a list. You can traverse a list (from
head to tail) with an iterator to access the objects
sequentially. List has an internal private class
ListElement providing memory management and other
functions for the pairs of pointers (to object and to
next element) that constitute the elements of a List
object. (For more on list theory, see Sedgwick's
Algorithms and Knuth's The Art of Computer Programming,
Volume 1, 2.2).
Member functions =======================================================
add void add( Object& toAdd );
Adds the given object at the head of the list. The
added object becomes the new head.
constructor List();
Creates an empty list.
detach
- 79 -

List
virtual void detach( Object& toDetach, DeleteType dt =
NoDelete );
Removes the given object from the list. Whether the
object itself is destroyed or not depends on the dt
argument, as explained in TShouldDelete::ownsElements.
flush virtual void flush( DeleteType dt = DefDelete );
Removes all the objects from the list without
destroying it. The value of dt determines whether the
objects themselves are destroyed. By default (dt =
DefDelete), the ownership status of the list determines
the fate of its elements, as explained in
TShouldDelete::ownsElements. You can set dt to Delete
to force destruction of the flushed objects regardless
of ownership. If dt is set to NoDelete, the flushed
objects will survive regardless of ownership.
See also: TShouldDelete::ownsElements
hashValue virtual hashValueType hashValue() const;
Returns the hash value of this list. See
HashTable::hashValue for more details.
initIterator virtual ContainerIterator& initIterator() const;
See Container::initIterator
isA virtual classType isA() const;
Returns listClass the List class ID.
nameOf virtual char *nameOf() const;
Returns "List", the List class ID string.
peekHead Object& peekHead() const;
Returns the object at the head of the list.
Friends =======================================================
ListIterator is a friend of List and ListElement.

- 80 -

ListIterator
===========================================================================
ListIterator list.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ContainerIteratorÃÄÄ¶ ListIterator º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
ListIterator is an instance class derived from
ContainerIterator providing iterator functions for List
objects. See ContainerIterator for a discussion of
iterators.
Member functions =======================================================
constructor ListIterator( const List& toIterate );
Creates an iterator for the given list. The starting
and current elements are set to the first element of
the list. See ContainerIterator constructor for
details.
current virtual Object& current();
See ContainerIterator::current
operator ++ virtual Object& operator ++ ( int );
virtual Object& operator ++ ();
See ContainerIterator::operator ++
operator int virtual operator int();
Conversion operator to test for end of iterator
position.
restart virtual void restart()
See ContainerIterator::restart

- 81 -

MemBlocks
===========================================================================
MemBlocks memmgr.h
===========================================================================
ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
º MemBlocks Ç
ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The classes MemBlocks and MemStack in memmgr.h offer
specialized memory management not only for the
container classes but for other applications. Detailed
knowledge of their operations is not needed for normal
container applications. If you are planning your own
advanced memory management schemes, you should first
study memmgr.h and MEMMGR.CPP.
MemBlocks is a noncontainer, instance class, providing
fixed-block memory allocations. Large, dynamic lists
and trees need to allocate and free their node blocks
as quickly as possible. MemBlocks offers more efficient
memory management than the standard heap manager for
this kind of operation. The MemBlock constructor takes
two arguments: block size and number of blocks. These
determine the size of the internal blocks that are
allocated as needed using the normal run-time library
allocation functions. A free list of blocks is
maintained and the internal blocks are not released
until the MemBlock object is destroyed. The following
example illustrates the use of MemBlocks with a
simplified Node class:
class Node
{
Node *next;
Object *obj;
static MemBlocks memBlocks;
void *operator new( size_t sz ) { return
memBlocks.allocate ( sz); }
void operator delete( void * blk ) { memBlocks.free
( blk ); }
...
};
CAUTION: If you derive a class from a class that does
its own memory management as in the Node example
above, then either the derived class must be the same
size as the base class or you must override the new and
delete operators.
- 82 -

MemBlocks
See also: MemStack class.
allocate void allocate( size_t sz, unsigned blks = 100 );
Allocates blks blocks each of size sz
free void free( void * ptr );
Frees the memory blocks at ptr.
===========================================================================
MemStack memmgr.h
===========================================================================
ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
º MemStack º
ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
MemStack is a noncontainer, instance class, providing
fast mark-and-release style memory management. Although
used internally by various container classes, MemStack
is also available for general use. Memory allocations
and deallocations are extremely fast since they
"popped" and "pushed" on a stack of available blocks.
Marking and releasing blocks is handled by objects of a
helper marker class. When a marker is created it
records the current location in the memory stack; when
a marker is destroyed, the stack is returned to its
original state, freeing any allocations made since the
marker was created. For example:
MemStack symbols;
void handleLocals()
{
Marker locals( symbols ); // marks current
state of symbols
Sym *symbol1 = new(symbols)Sym; // add a Sym to the
table
Sym *symbol2 = new(symbols)Sym; // and another
}
When the function exits, the Marker destructor releases
the memory allocated by the new(symbols) calls made in
handleLocal and restores the memory stack.
- 83 -

Object
See also: MemBlocks
===========================================================================
Object object.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄ´ Error ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
º Object ÇÄÅÄ´ Sortable ³
ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄ´Association ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´ Container ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
Object is an abstract class providing the primordial
base for the whole Object-based container hierarchy
(with the exception of the iterator classes). The
member functions provide the basic essentials for all
derived classes and the objects they contain. Object
has four immediate children: Error, Sortable,
Association, and Container.
Data member =======================================================
ZERO static Object *ZERO;
A static pointer to the unique instance of class Error.
ZERO is used to define NOOBJECT.
See also: Error class
Member functions =======================================================
constructors Object();
Object( Object& obj );
Creates or copies an object.
- 84 -

Object
firstThat virtual Object& firstThat( condFuncType testFuncPtr,
void *paramList ) const;
Returns *this if the object satisfies the condition
specified by the BOOLEAN testFunc function, otherwise
NOOBJECT is returned. You can pass arbitrary arguments
via the paramList argument. Note that firstThat,
lastThat, and forEach work for all Object-derived
objects, both container and non-container objects,
whether they are in containers or not. With container
objects, you can get iteration through the contained
objects. When used with objects outside containers, the
three functions act only on the calling object, so
firstThat and lastThat are equivalent. condFuncType is
defined in clstypes.h as
#typdef int ( *condFuncType )( const class Object&,
void *);
firstThat calls ( *testFuncPtr )( *this, paramList ).
If 1 is returned, firstThat returns (Object &) *this,
otherwise NOOBJECT is returned.
See also: Container::firstThat
forEach virtual void forEach( iterFuncType actionFuncPtr, void
*args );
forEach executes the given action function on *this.
The args argument lets you pass arbitrary data to the
action function.
See also: firstThat
hashValue virtual hashValueType hashValue() const = 0;
A pure virtual function to be defined by derived
classes to return the hash value of an object. See
HashTable::hashValue for more details.
isA virtual classType isA() const = 0;
Pure virtual function for derived classes to return a
class ID.
isAssociation virtual int isAssociation() const;

- 85 -

Object
Returns 1 if the calling object is part of an
Association object, otherwise returns 0. Must be
overridden in classes providing associations.
See also: Association class.
isEqual virtual int isEqual( const Object& testObject ) const =
0;
Pure virtual function to be defined in derived classes
to test for equality between testObject and the calling
object (assumed to be of the same type). isEqual is
really for internal use by the operator == which first
applies isA to see if the compared objects are of the
same type. If they are, == then uses isEqual.
See also: operator ==
isSorttable virtual int isSortable() const;
Returns 1 if the calling object can be sorted; that
is, if the class Sortable is an ancestor. Otherwise
returns 0. Object::isSortable returns 0. Sortable
classes must override isSortable to return true.
See also: Sortable class
lastThat virtual Object& lastThat( condFuncType testFuncPtr,
void *paramList ) const;
Returns *this if the object satisfies the condition
specified by the BOOLEAN testFuncPtr function,
otherwise NOOBJECT is returned. You can pass arbitrary
arguments via the paramList argument. Note that
firstThat, lastThat, and forEach work for all Object-
derived objects, both container and non-container
objects, whether they are in containers or not. With
container objects, you get iteration through the
contained objects. When used with objects outside
containers, the three functions act only on the calling
object, so firstThat and lastThat are equivalent.
See also: firstThat, Container::lastThat
nameOf virtual char *nameOf() const = 0;
Pure virtual function to be defined by derived classes
to return their object ID string.
- 86 -

Object
new void *operator new( size_t size );
Overrides the C++ operator new. Allocates size bytes
for an object. Returns ZERO if the allocation fails,
otherwise returns a pointer to the new object.
printOn virtual void printOn( ostream& outputStream ) const =
0;
Pure virtual function to be defined in derived classes
to provide formatted output of objects on the given
output stream. printOn is really for internal use by
the overloaded operator <<.
See also: operator <<
ptrToRef static Object ptrToRef( Object *p );
Returns *ZERO is p is 0, else returns *p
Friends =======================================================
operator << ostream& operator <<( ostream& outputStream, const
Object& anObject );
Uses printOn to send a formatted representation of
anObject to the given output stream. The stream is
returned, allowing the usual chaining of the <<
operator.
operator << is a friend of Object.
Related functions =======================================================
The following overloaded operators are related to
Object but are not member functions:
operator == int operator ==( const Object& test1, const Object&
test2 );
Returns 1 if the two objects are equal, otherwise
returns 0. Equal means that isA and isEqual each return
the same values for the two objects.

- 87 -

Object
Note that for sortable objects (derived from the class
Sortable) there are also overloaded nonmember operators
<, >, <=, and >=.
See also: Object::isA, Object::isEqual, operator !=,
Sortable class.
operator != int operator !=( const Object& test1, const Object&
test2 );
Returns 1 if the two objects are unequal, otherwise
returns 0. Unequal means that either isA or isEqual
each return the different values for the two objects.
See also: Object::isA, Object::isEqual, operator ==
===========================================================================
PriorityQueue priortyq.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Container ÃÄÄ¶ PriorityQueue º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class Priority Queue, derived from
Container, implements the traditional priority queue
data structure. The objects in a priority queue must be
sortable (see Sortable class for details). A priority
queue is either a GIFO (greatest-in-first-out) or SIFO
(smallest-in-first-out) container widely used in
scheduling algorithms. The difference really depends on
your ordering definition. In explaining this
implementation, we'll assume a GIFO. You can picture
sortable objects being added at the right, but each
extraction from the left gives the "greatest" object in
the queue. (For applications where you need to extract
the smallest item, you need to adjust your definition
of "less than.") A detailed discussion of priority
queues can be found in Knuth's The Art of Computer
Programming, Volume 3, 5.2.3.
The member function put adds objects to the queue;
peekLeft lets you examine the largest element in the
queue; get removes and returns the largest element; you
can also detach this item with detachLeft without
- 88 -

PriorityQueue
"getting" it. PriorityQueue is implemented internally
using a private Btree object called tree.
Member functions =======================================================
detachLeft void detachLeft( Container::DeleteType dt =
Container::DefDelete );
Removes the smallest object from the priority queue.
Whether this object is destroyed or not depends on the
value of dt as explained in
TShouldDelete::ownsElements.
flush void flush( Container::DeleteType dt =
Container::DefDelete );
Flushes (empties) the priority queue. The fate of the
removes objects depends on the value of dt as explained
in TShouldDelete::ownsElements.
get Object& get();
Detaches the smallest object from the priority queue
and returns it. The detached object is not itself
destroyed.
getItemsInContainer countType getItemsInContainer() const ;
Returns the number of items in the priority queue.
hashValue virtual hashValueType hashValue() const;
Returns the hash value of the priority queue. See
HashTable::hashValue for more details.
hasMember int hasMember( const Object& obj ) const;
Returns 1 if obj belongs to the priority queue,
otherwise returns 0.
initIterator virtual void ContainerIterator& initIterator() const;
Creates and returns an iterator for this queue.
See also: ContainerIterator
- 89 -

PriorityQueue
isA virtual classType isA() const;
Returns priorityQueueClass, the PriorityQueue type ID.
isEmpty int isEmpty();
Returns 1 if the priority queue is empty, otherwise
returns 0.
nameOf virtual char *nameOf() const;
Returns "PriorityQueue", the PriorityQueue type ID
string.
peekLeft Object& peekLeft();
Returns the smallest object in the priority queue
without removing it.
put void put( Object& o );
Add the given object to the priority queue.
===========================================================================
Queue queue.h
===========================================================================
ÚÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Deque ÃÄÄ¶ Queue º
ÀÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class Queue, derived from Deque,
implements the traditional queue data structure. A
queue is a FIFO (first-in-first-out) container where
objects are inserted at the left (head) and removed
from the right (tail). For a detailed discussion of
queues, see Knuth's The Art of Computer Programming,
Volume 1, 2.2.1.
The member functions put and get insert and remove
objects.
Queue is implemented as a restricted-access version of
Deque.

- 90 -

Queue
Example =======================================================
Source #include <queue.h>
#include <strng.h>
#include <assoc.h>
main()
{
Queue q;
String *s1 = new String("a string");
String *s2 = new String("another string");
Association *a1 = new Association(*s1,*s2);
// Populate the queue
q.put(*s1);
q.put(*s2);
q.put(*a1);
// Print to cout as a Container
cout << "As a container:\n" << q << endl;
// Empty the queue to cout
cout << "As a queue:\n";
while (!q.isEmpty())
{
cout << q << endl;
}
cout << endl;
// Queue should be empty
cout << "Should be empty:\n" << q;
}
Output As a container:
Queue { Association { a string, another a string }
,
another string,
a string }
As a queue:
a string
another string
Association { a string, another string }
Should be empty:
Queue { }

- 91 -

Queue
Member functions =======================================================
get Object& get();
Removes the object from the end (tail) of the queue. By
default the removed object will not be destroyed. If
the queue is empty, NOOBJECT is returned. Otherwise the
removed object is returned.
See also: TShouldDelete class
isA virtual classType isA() const;
Returns queueClass, the Queue type ID.
put void put( Object& o );
Add an object to (the tail of) a queue.
===========================================================================
Set set.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Bag ÃÄÄ¶ Set ÇÄÄ´ Dictionary ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
The instance class Set is a collection that allows only
one instance of any object. This restriction calls for
a specialized add member function to trap any
duplicates. Apart from this difference, the Set and Bag
classes are essentially the same.
Member functions =======================================================
add virtual void add( Object& objectToAdd );
Adds the given object to the set only if it is not
already a member. If objectToAdd is found in the set,
add does nothing.

- 92 -

Set
See also: Collection::hasMember
constructor Set( sizeType setSize = DEFAULT_SET_SIZE );
Creates a set with the given size by calling the base
Bag constructor.
See also: Bag::Bag
isA virtual classType isA() const;
Returns setClass, the Set class ID.
nameOf virtual char *nameOf() const;
Returns "Set", the Set class ID string.
===========================================================================
Sortable sortable.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄ´ String ³
³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ» ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Object ÃÄÄ¶ Sortable ÇÄÅÄ´ BaseDate ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
³ ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄ´ BaseTime ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ
Sortable is an abstract class derived from Object. You
can use it to build classes of sortable objects.
Objects are said to be sortable when they can be placed
in an order based on some useful and consistent
definition of "less than", "equal", and "greater than."
Any two of these conditions will suffice, in fact,
since the remaining condition can be constructed with
logical operators. Sortable uses the two primitives
"less than" and "equal" via the pure virtual functions
(pure virtual functions) isLessThan and isEqual. Both
of these member functions are applicable only to
objects of the same type (see operators == and < for
more details). The isEqual member function is a pure
virtual function inherited from Object (since unordered
objects also need a test for equality), whereas
- 93 -

Sortable
isLessThan is a new pure virtual function for Sortable.
Your derived classes must define these two member
functions to provide an appropriate ordering of their
objects.
Once isLessThan and isEqual are defined, you can use
the overloaded operators ==, !=, <, <=, >, >= in the
obvious way (see Related Functions section below). The
< operator tests the objects' types first with isA and
returns 0 if the objects are of different types. Then
if the objects are of the same type, the isLessThan
member is called, returning 0 or 1. If your application
calls for the ordering of objects of different types,
you would have to define your own comparison operators.
The elements stored in ordered containers must clearly
be sortable. For example, when adding elements to a
SortedArray object, the add member function must
compare the "size" of the incoming object against that
of the existing elements. Similarly, Btree objects make
use of magnitude for storage and access methods. Note,
however, that an unordered container can hold either
unsortable or sortable objects.
The type of sortable objects available differs between
the Object-based containers and the template-based
containers. In the Object-based hierarchy you must use
objects ultimately derived from Sortable, whereas the
template containers let you store any object or
predefined data type for which == and < is defined. If
you want to store ints in an Object-based container,
for example, you must invent a suitable class:
class Integer : public Sortable
{
int data;
...
public:
virtual char *nameOf() const { return "Integer"; }
virtual classType isA() const { return
integerClass; }
virtual int isLessThan( const Object& i ) const
{ return data < ((Integer&)i).data; }
...
}

- 94 -

Sortable
The Object-based container library already provides
three useful instance classes derived from Sortable:
String, Date, and Time with the natural ordering you
would expect. Remember, though, that you are free to
define your own orderings in derived classes to suit
your application. You must make sure that your
comparisons are logically consistent. For instance, >
must be transitive: A > B and B > C must imply A > C.
Member functions =======================================================
hashValue virtual hashValueType hashValue() const = 0;
A pure virtual function to be defined by derived
classes to return the hash value of a sortable object.
See HashTable::hashValue for more details.
isA virtual classType isA() const = 0;
Pure virtual function to be defined in derived classes
to return their class ID.
isEqual virtual int isEqual( const Object& testObject ) const =
0;
Pure virtual function to be defined in derived classes
to test for equality. Equality means that the calling
object is the same type as testObject and that their
values (as defined by this member function) are equal.
Returns 1 for equality, otherwise 0.
isLessThan virtual int isLessThan( const Object& testObject )
const = 0;
Pure virtual function to be defined in derived classes
to test for "less than." Returns 1 for "less than",
otherwise 0.
isSortable virtual int isSortable() const;
Returns 1 for all objects derived from Sortable
(overrides Object::isSortable).
nameOf virtual char *nameOf() const = 0;

- 95 -

Sortable
Pure virtual function to be defined by derived classes
to return their object ID string.
printOn virtual void printOn( ostream& outputStream ) const =
0;
operator << is a Pure virtual function to be defined in derived classes
friend of Object. to output the object on the given stream. printOn is
See page 87. for internal use by the overloaded operator <<.
Related functions =======================================================
The following overloaded operators are related to
Sortable but are not member functions:
operator < int operator <( const Sortable& test1, const Sortable&
test2 );
Returns 1 if the two objects are of the same type X,
and test1 is "less than" test2 (as defined by
X::isLessThan). Otherwise returns 0.
See also: Sortable::isLessThan, Sortable::isA
operator <= int operator <=( const Sortable& test1, const Sortable&
test2 );
As for operator <, but also tests true for equality.
operator > int operator >( const Sortable& test1, const Sortable&
test2 );
Returns 1 if the two objects are of the same type X,
and test1 is not "less than" and not "equal" to test2
(as defined by X::isLessThan and X::isEqual). Otherwise
returns 0.
operator >= int operator >=( const Sortable& test1, const Sortable&
test2 );
As for operator >, but also tests true for equality.
Note that >= returns !( test1<( test2) ), so it returns
1 if test1 and test2 are of different types.

- 96 -

SortedArray
===========================================================================
SortedArray sortarry.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³AbstractArrayÃÄÄ¶SortedArray º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class SortedArray, derived from
AbstractArray, defines an array that maintains its
elements in ascending order (according to the ordering
defined for the elements). That is, the element at
index n is less than or equal to the element at index n
+ 1. Note that the operator <=, used when adding new
elements to the array, must be defined for comparing
any objects in the array. This will be the case for
objects ultimately derived from Sortable (see the
Related Functions section of the Sortable class
reference) as well as for the standard C integral
types.
Array and SortedArray are identical in many areas (they
have the same base, AbstractArray). One difference is
that SortedArray::detach "squeezes" the array to
maintain ascending order, while Array::detach leaves
"holes" in the array.
===========================================================================
Stack stack.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Container ÃÄÄ¶ Stack º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
The instance class Stack, derived from Container, is
one of the sequence classes like Queue and Deque. A
stack is a LIFO (last-in-first-out) linear list for
which all insertions (pushes) and removals (pops) take
place at one end (the top or head) of the list (see D.
E Knuth's The Art of Computer Programming, Volume 1,
2.2). In addition to the traditional pop and push
member functions, Stack provides top, a member function
for examining the object at the top of the stack
without affecting the stack's contents. top must be
- 97 -

Stack
used with care since it returns a reference to an
object that may be owned by the stack. Destroying the
object returned by top can disrupt the internal
mechanism for storing the stack. The correct way to
dispose of the top element is to use pop followed by
delete. Stack is implemented internally as a List via a
private data member theStack of type List.
See also: Stacks templates and classes
Example =======================================================
Source #include <stack.h>
#include <strng.h>
#include <assoc.h>
main()
{
Stack s;
String *s1 = new String("a string");
String *s2 = new String("another string");
Association *a1 = new Association(*s1,*s2);
s.push(*s1);
s.push(*s2);
s.push(*a1);
// Print the Stack
cout << "As a Container:\n" << s << endl;
// Empty the stack to cout
cout << "As a Stack:\n";
while (!s.isEmpty())
{
Object& obj = s.pop();
cout << obj << endl;
delete &obj;
}
}
Output As a Container:
Stack { Association { a string, another string }
,
another string,
a string }
As a Stack:
- 98 -

Stack
Association { a string, another string }
another string
a string
Member functions =======================================================
flush virtual void flush( DeleteType dt = DefDelete );
Flushes (empties) the stack. The fate of the removed
objects depends on the argument dt. See TShouldDelete
for details.
getItemsInContainer virtual countType getItemsInContainer() const;
Returns the number of items in the stack.
initIterator virtual ContainerIterator& initIterator() const;
Creates and returns a stack iterator for the stack.
See also: ContainerIterator class
isA virtual classType isA() const;
Returns stackClass, the Stack type ID.
isEmpty virtual int isEmpty() const;
Returns 1 if the stack is empty, otherwise returns 0.
nameOf virtual char *nameOf() const;
Returns "Stack", the Stack type ID string.
pop Object& pop();
Removes the object from the top of the stack and
returns the object. The fate of the popped object is
determined by ownership as explained in TShouldDelete.
push void push( Object& toPush );
Adds (pushes) the object toPush to the top of the
stack.
- 99 -

Stack
top Object& top();
Returns but does not remove the object at the top of
the stack.
===========================================================================
String strng.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ Sortable ÃÄÄ¶ String º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
String is an instance class, derived from Sortable, to
implement null-terminated, character strings. String
objects are ordered in the usual lexicographic way
using strcmp from the standard C string.h. Note that
the String class include file is spelled strng.h. See
Sortable for a discussion on ordered classes.
Member functions =======================================================
constructor String( const char *aPtr = "" );
Constructs a String object from the given C string.
constructor String(const String& sourceString );
Copy constructor.
hashValue virtual hashValueType hashValue() const;
Returns the hash value of this string. See
HashTable::hashValue for more details.
isA virtual classType isA() const;
Returns stringClass, the Stack type ID.
isEqual virtual int isEqual( const Object& testString ) const;
Returns 1 if the calling string is equal to testString,
otherwise returns 0. You can also use the overloaded
- 100 -

String
operators == and != as explained in the Related
functions section of the Object class.
isLessThan virtual int isLessThan( const Object& testString )
const;
Returns 1 if the calling string lexically precedes
testString, otherwise returns 0. You can also use the
overloaded operators <, <=, >, and >=, as explained in
the Related functions section of the Storable class.
nameOf virtual char *nameOf() const;
Returns the Stack type ID string.
printOn virtual void printOn( ostream& outputString ) const;
operator << is a Prints this string on the given stream. printOn is
friend of Object. really for internal use by the overloaded operator <<.
See page 87.
operator = String& operator =( const String& sourceString );
Overloads the assignment operator for string objects.
operator char * operator const char *() const;
Returns a pointer to this string.
Example =======================================================
Source // File TSTRNG.CPP: Test the String class
#include <strng.h>
void identify(String&);
main()
{
char s1[21], s2[21];
cout << "Enter a string: "; // Read a
string
cin >> s1;
String str1(s1);
identify(str1);
- 101 -

String
cout << "Enter another string: "; // Read
another
cin >> s2;
String str2(s2);
identify(str2);
// Do some relational tests:
cout << "Equal: " << str1.isEqual(str2) << endl
<< "Less than: " << str1.isLessThan(str2) <<
endl;
// String assignment:
str2 = str1;
cout << "After assignment:\n" << "Equal: "
<< str1.isEqual(str2);
}
void identify(String& str)
{
// Echo a String's value and type
cout << "Value: " << str
<< ", Object type: " << str.nameOf() << endl
<< endl;
}
Output Enter a string: hello
Value: hello, Object type: String
Enter another string: goodbye
Value: goodbye, Object type: String
Equal: 0
Less than: 0
After assignment:
Equal: 1
===========================================================================
Time ltime.h
===========================================================================
ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
³ BaseTime ÃÄÄ¶ Time º
ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
Time is a sortable instance class derived from
BaseTime. Time adds a printOn member. You can override
- 102 -

Time
this in derived classes to cope with international
formatting variations.
Member functions =======================================================
constructor Time();
Calls the BaseTime constructor to create a Time object
with the current time.
See also: BaseTime constructor
constructor Time( const Time& T );
Copy constructor.
constructor Time( unsigned char H, unsigned char M = 0, unsigned
char S = 0, unsigned char D = 0 );
Creates a Time object with the given hour, minutes,
seconds, and hundredths of seconds.
isA virtual classType isA() const;
Returns timeClass, the Time class ID.
nameOf virtual char *nameOf() const;
Returns "Time", the Time class ID string.
printOn virtual void printOn( ostream& outputStream ) const;
operator << is a Sends a formatted Time object to the given output
friend of Object. stream. The default format is hh:mm:ss:dd a/pm with
See page 87. nonmilitary hours. printOn is for internal use by the
overloaded operator <<.

- 103 -

Timer
===========================================================================
Timer timer.h
===========================================================================
ÉÍÍÍÍÍÍÍÍÍÍÍÍ»
º Timer Ç
ÈÍÍÍÍÍÍÍÍÍÍÍÍ¼
Timer is an instance class implementing a stop watch.
You can use Timer objects to time program execution by
calling the member functions start and stop within your
program, and then using time to return the elapsed
time. The reset member function resets the elapsed time
to zero. Successive starts and stops will accumulate
elapsed time until a reset.
Member functions =======================================================
constructor Timer();
Creates a Timer object.
reset void reset();
Clears the elapsed time accumulated from previous
start/stop sequences.
resolution static double resolution();
Determines the timer resolution for all timer objects.
This value is hardware and OS dependent. For example:
if( elapsedTime < timer.resolution() )
cout << "Measured time not meaningful." << endl;
start void start();
Ignored if the timer is running, otherwise starts the
timer. The elapsed times from any previous start/stop
sequences are accumulated until reset is called.
status int status();
Returns 1 if the timer is running, otherwise 0.
stop void stop();
- 104 -

Timer
Stops the timer. The accumulated elapsed time is
preserved until a reset call.
time double time();
Returns the elapsed time. The precision is given by the
value returned by the member function resolution.
===========================================================================
TShouldDelete shddel.h
===========================================================================
Figure 3: Class hierarchies in CLASSLIB

TShouldDeleteÄÄÄÄÄÄÄÂÄÄAssociation
ÀÄÄContainer
TShouldDelete maintains the ownership state of a
container. The fate of objects that are removed from a
container can be made to depend on whether the
container owns its elements or not. Similarly, when a
container is destroyed, ownership can dictate the fate
of contained objects that are still in scope. As a
virtual base class for Container and Association,
TShouldDelete provides ownership control for all
containers and associations. The member function
ownsElements can be used either to report or to change
the ownership status of a container. delObj is used to
determine if objects in containers or associations
should be deleted or not.
Member functions =======================================================
constructor TShouldDelete( DeleteType dt = Delete );
Creates a TShouldDelete object. By default, containers
and associations own their elements. DeleteType is an
enumeration declared within the class as follows:
enum DeleteType { NoDelete, DefDelete, Delete };
ownsElements int ownsElements();
void ownsElements( int del );
- 105 -

TShouldDelete
The first form returns 1 if the container owns its
elements, otherwise it returns 0. The second form
changes the ownership status as follows: if del is 0,
ownership is turned off; otherwise ownership is turned
on.
delObj int delObj( DeleteType dt );
Tests the state of ownership and returns 1 if the
contained objects should be deleted or 0 if the
contained elements should not be deleted. The factors
determining this are (i) the current ownership state
and (ii) the value of dt, as shown in the following
table.
delObj returns 1 if (dt is Delete) or (dt is DefDelete
and the container currently owns its elements). Thus a
dt of NoDelete returns 0 (don't delete) regardless of
ownership; a dt of Delete return 1 (do delete)
regardless of ownership; and a dt of DefDelete returns
1 (do delete) if the elements are owned, but a 0 (don't
delete) if the objects are not owned.
-------------------------------------------------------
delObj
ownsElements no yes
-------------------------------------------------------
NoDelete no no
DefDelete no yes
Delete yes yes
-------------------------------------------------------

- 106 -

INDEX
___________________________________________________________________________

A B
abbreviations Bag class 47
CLASSLIB names and 19 BaseDate class 49
abstract classes 4 BaseTime class 51
abstract data types BI_ prefix
BIDS class names 19 class names 19
class library and 13 BIDS template library 13
AbstractArray class 37 Borland International Data
add Structures (BIDS) 13
Array member function 42 Btree class 53
Bag member function 47 BtreeIterator class 55
Btree member function 53
Collection member function 58
Dictionary member function 69 C
DoubleList member function 71 C prefix
HashTable member function 76 class names 19
List member function 79 CHECK macro 35
Sets member function 92 class templates 17
addAt classes
Array member function 42 abstract vs instance 4
addAtHead arrays
DoubleList member function 71 sorted 97
addAtTail collections 12
DoubleList member function 71 date and time 65, 102
ADT debugging modes 35
header files 22 hierarchies 4
ADT (abstract data types) 13 object-based 6
Array class 41 traversing 43
ArrayInterator lists 70
AbstractArray friend 40 priority queues 88
ArrayIterator class 43 queue 90
arrays queues
classes for 37, 41 double-ended 66
classes for sorted 97 sequence 12, 66, 90, 97
arraySize rules for 12
AbstractArray member function 38 sortable objects 93
ascending sort 97 stack 97
assertion macros 35 string 100
Association class 7, 44 CLASSLIB naming conventions 19
example program 34 Collection class 12, 57
Index 107

collections reference section 36
ordered 13 container classes 6, 8, 59
random access to 37 functions of 59
unordered 13 container hierarchy
Bag class 47 object-based 4
Dictionary class 69 ContainerIterator class 64
DoubleList class 70 containers and 64
HashTable class 75 hierarchy 11
List class 79 containers
Set class 92 basics 4
condFuncType definition 84 ContainerIterator class and 64
constructors direct 19
AbstractArray member function 38 elements of 59
Array member function 42 equality testing 60
ArrayIterator member function 43 flushing 10, 59
Association member function 44 implementation 14
Bag member function 47 indirect 19
Basedate member function 49 current
Basetime member function 51 ArrayIterator member function 43
Btree member function 53 BtreeIterator member function 56
BtreeIterator member function 56 ContainerIterator member function
Collection member function 58 64
Container member function 60 DoubleListIterator member
Date member function 65 function 73
Dictionary member function 70 HashTableIterator member function
DoubleList member function 71 78
DoubleListIterator member ListIterator member function 81
function 73
HashTable member function 76
HashTableIterator member function D
78 Date class 65
List member function 79 dates
ListIterator member function 81 class 65
Object member function 84 Day
Sets member function 93 Basedate member function 49
String member function 100 __DEBUG macro 35
Time member function 103 decrNofKeys
Timer member function 104 Btree member function 53
TShouldDelete member function 105 delete
container class library Error member function 75
directories 31 delObj
examples 34 TShouldDelete member function 106
INCLUDE 32 delta
lib 34 AbstractArray data member 37
source 32 Deque class 66
example programs 34 destroy
memory models and 32 AbstractArray member function 38
project files and 32 Collection member function 58
- 108 -

destroyFromHead HashTable member function 77
DoubleList member function 71 firstThat
destroyFromTail Bag member function 47
DoubleList member function 71 Container member function 60
detach Object member function 84
AbstractArray member function 38 flush
Bag member function 47 Bag member function 47
Btree member function 53 Btree member function 54
Collection member function 58 Container member function 61
DoubleList member function 71 Deque member function 68
HashTable member function 76 DoubleList member function 72
List member function 79 HashTable member function 77
SortedArray member function 97 List member function 80
detachFromHead PriorityQueue member function 89
DoubleList member function 71 Stacks member function 99
detachFromTail forEach
DoubleList member function 71 Bag member function 48
detachLeft Container member function 61
PriorityQueue member function 89 Object member function 85
Dictionary class 69 free
example program 34 MemBlocks member function 83
direct and indirect data structures fundamental data structure
14 class templates 17
directories fundamental data structures
container class library 31 class library and 13
DIRECTRY (container class library Object-based classes 20
example program) 34
DoubleList class 70
DoubleListIterator class 73 G
get
PriorityQueue member function 89
E Queue member function 92
elements getItemsInContainer
ordering definition 19 Bag member function 48
Error class 7, 74 Container member function 61
examples directory Deques member function 68
container class library 34 PriorityQueue member function 89
Stacks member function 99
getLeft
F Deque member function 68
FDS getRight
header files 22 Deque member function 68
FDS (fundamental data structures)
13
findmember H
Bag member function 47 hash table
Btree member function 54 iterators 78
Collection member function 58 HashTable class 75
Index 109

HashTableIterator class 78 instance classes 4
hashValue isA
Association member function 44 Array member function 43
Basedate member function 49 Association member function 44
Basetime member function 51 Bag member function 48
Btree member function 54 Basedate member function 50
Container member function 61 Basetime member function 52
HashTable member function 77 Btree member function 54
List member function 80 Container member function 62
Object member function 85 Date member function 66
PriorityQueue member function 89 Deque member function 68
Sortable member function 95 Dictionary member function 70
String member function 100 DoubleList member function 72
hasMember Error member function 75
Bag member function 48 HashTable member function 78
Btree member function 54 List member function 80
Collection member function 59 Object member function 85
PriorityQueue member function 89 PriorityQueue member function 89
hour Queue member function 92
Basetime member function 51 Set member function 93
hundredths Sortable member function 95
Basetime member function 51 Stack member function 99
String member function 100
Time member function 103
I isAssociation
i_add Association member function 44
Btree member function 54 Object member function 85
I prefix isEmpty
class names 19 Bag member function 48
Imp suffix Container member function 62
class names 19 Deques member function 68
INCLUDE directory PriorityQueue member function 90
container class library 32 Stack member function 99
incrNofKeys isEqual
Btree member function 54 AbstractArray member function 39
initIterator Association member function 45
AbstractArray member function 39 Basedate member function 50
Bag member function 48 Basetime member function 52
Btree member function 54 Btree member function 54
Container member function 61 Container member function 62
Deque member function 68 Error member function 75
DoubleList member function 72 Object member function 86
HashTable member function 77 Sortable member function 95
List member function 80 String member function 100
PriorityQueue member function 89 isLessThan
Stacks member function 99 Basedate member function 50
InnerNode Basetime member function 52
Btree friend class 53 Sortable member function 95
- 110 -

String member function 101 M
isSortable member functions
Object member function 86 virtual
Sortable member function 95 pure 4
Item MemBlocks class 82
Btree friend class 53 memory models
itemsInContainer container class library and 32
Container data member 60 MemStack class 83
iterators minute
DoubleList 73 Basetime member function 52
internal and external 11 Month
iterFuncType definition 61 Basedate member function 50
K N
key nameOf
Association class 44 Arrays member function 43
Association member function 45 Association member function 45
Bag member function 49
Basedate member function 50
L Basetime member function 52
Last-In-First-Out (LIFO) 14 Btree member function 54
lastElementIndex Container member function 62
AbstractArray data member 37 Date member function 66
lastThat Deque member function 68
Bag member function 48 Dictionary member function 70
Container member function 62 DoubleList member function 72
Object member function 86 Error member function 75
LeafNode HashTable member function 78
Btree friend class 53 List member function 80
lib directory Object member function 86
container class library 34 PriorityQueue member function 90
List class 79 Set member function 93
iterators 81 Sortable member function 95
ListElement class 79 Stacks member function 99
ListIterator class 81 String member function 101
lists Time member function 103
classes for 70 new
linked Object member function 86
traversing 81 Node
lookup Btree friend 55
Dictionary member function 70 Btree friend class 53
LOOKUP (container class library non-container classes 6
example program) 34
lowerBound
AbstractArray member function 39 O
lowerbound O prefix 21
AbstractArray data member 37 class names 19
Index 111

Object class 4, 84 operator char *
Object container class library String member function 101
version 3.0 changes to 1 operator int
objectAt ArrayIterator member function 43
AbstractArray member function 39 BtreeIterator member function 56
objects ContainerIterator member function
automatic 11 64
detaching 10 DoubleListIterator member
heap 11 function 74
in containers HashTableIterator member function
counting 59 78
displaying 60 ListIterator member function 81
iterating 60 order
ownership 59 Btree member function 55
ownership 9 ordered collections 7, 13
sortable 93 ownsElements 9
operator < Bag member function 49
overloaded 96 TShouldDelete member function 105
operator =
String member function 101
operator > P
overloaded 96 peekAtHead
operator != DoubleList member function 72
overloaded 88 peekAtTail
operator ++ DoubleList member function 72
ArrayIterator member function 43 peekHead
BtreeIterator member function 56 List member function 80
ContainerIterator member function peekLeft
64 Deque member function 69
DoubleListIterator member PriorityQueue member function 90
function 73 peekRight
HashTableIterator member function Deque member function 69
79 pop
ListIterator member function 81 Stacks member function 99
operator << PRECONDITION macro 35
Object friends 87 printContentsOn
operator <= AbstractArray member function 39
overloaded 96 printHeader
operator == Container member function 62
overloaded 87 printOn
operator >= Association member function 45
overloaded 96 Basedate member function 50
operator [] Basetime member function 52
AbstractArray member function 39 Btree member function 55
Btree member function 55 Container member function 62
operator - - Date member function 66
DoubleListIterator member Error member function 75
function 73 Object member function 87
- 112 -

Sortable member function 96 restart
String member function 101 ArrayIterator member function 44
Time member function 103 BtreeIterator member function 56
printSeparator ContainerIterator member function
Container member function 63 65
printTrailer DoubleListIterator member
Container member function 63 function 74
priority queues 88 HashTableIterator member function
PriorityQueue class 88 79
project files ListIterator member function 81
container class libraries and 32 REVERSE (container class library
ptrAt example program) 34
AbstractArray member function 40
ptrToRef
Object member function 87 S
push S prefix
Stacks member function 99 class names 19
put second
PriorityQueue member function 90 Basetime member function 52
Queue member function 92 Set class 92
putLeft setData
Deque member function 69 AbstractArray member function 40
putRight SetDay
Deque member function 69 Basedate member function 50
setHour
Basetime member function 52
Q setHundredths
Queue class 90 Basetime member function 52
example program 34 setMinute
queues 90 Basetime member function 52
double-ended 66 SetMonth
QUEUETST (container class library Basedate member function 50
example program) 34 setSecond
Basetime member function 52
SetYear
R Basedate member function 50
rank Sortable class 7, 93
Btree member function 55 ordered collections 13
reallocate SortedArray class 97
AbstractArray member function 40 example program 34
MemBlocks member function 83 sorts
removeEntry ascending 97
AbstractArray member function 40 source directory
reset container class library 32
Timer member function 104 squeezeEntry
resolution AbstractArray member function 40
Timer member function 104 Stack class 97
example program 34
Index 113

start top
Timer member function 104 Stacks member function 99
status TShouldDelete class 105
Timer member function 104
stdtempl.h 22
stop U
Timer member function 104 unordered collections 13
String class 100 Bag class 47
example program 34 Dictionary class 69
strings DoubleList class 70
classes for 100 HashTable class 75
STRNGMAX (container class library List class 79
example program) 34 Set class 92
upperBound
AbstractArray member function 40
T upperbound
TC prefix 21 AbstractArray data member 38
class names 19
template-based container library 13
TEMPLATES V
conditional compilation 32 value
Templates Association class 44
Arrays example 30 Association member function 45
Deques example 30
templates
approach to class library 3, 15 Y
container classes and 14 Year
instantiating 19 Basedate member function 50
time
Timer member function 105
Time class 102 Z
example program 34 ZERO
Timer class 104 Object data member 84

- 114 -