Another Class Library! Why?
Most class libraries are large, complex entities. To use one
effectively can require a long apprenticeship. Unfortunately, there is no one
library in general use that every programmer can be expected to be familiar
with.
A programmer faced with an unfamiliar library often encounters
dozens of classes, each of which may have dozens of methods.
Understanding the use of just
one method in one class may require looking up many other methods in many
other classes. This seriously hinders the study and use of examples.
The AGCLIB1 library was designed to avoid this difficulty. Instead
of generality and completeness, it strives for specificity and minimality.
Any method in any of the classes can be understood without reference to
other methods or classes. Each user level class in the library
stands completely alone and requires no other user level class for support.
The result is that a programmer can acquire an adequate working familiarity
with the AGCLIB1 library in a very short time.
|
AGCLIB1
A Template Class Library for AnaGram Examples
AGCLIB1 is a small C++ template class library originally designed to
support examples of the use of the AnaGram parser generator.
The library was designed to implement absolutely minimal functionality, in
order to be easy to learn and compatible with a great variety of users'
systems and requirements. Moreover, the library was designed to scale well
so that it can be used effectively in real applications as well as in
examples.
The idea is to provide for easy manipulation of collections of data of
various types, without obscuring the presentation of examples. At the same
time, AGCLIB1 aims to require only the smallest possible investment of time
and effort on the part of the user.
Where appropriate, AGCLIB1 can support the extension and conversion of
examples into a developer's own projects. And it can be profitably used in
many circumstances where a small, easy-to-learn container library is
needed.
This software is provided 'as-is', without any express or implied
warranty. In no event will Parsifal Software be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
-
The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
-
Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
-
This notice may not be removed or altered from any source distribution.
* This license conforms to the zlib/libpng license.
See the listing of
approved licenses maintained by the Open Source Initiative. The
zlib/libpng license was chosen for its simplicity and because it allows
commercial use.
The AGCLIB1 template class library comprises five container classes,
implemented as template classes, and a string class. These classes provide
facilities for handling collections of objects using such familiar concepts
such as stacks and sets without having to deal with the mechanics of
managing the memory used for storing them. The classes handle all the
routine tasks of allocating memory when it is required and freeing it when
it is no longer needed.
All of the classes are implemented using value
semantics. This means, in a nutshell, that container objects can be
passed to and from functions and assigned to variables just like native
programming types such as int or double.
The container classes and their essential functions are as follows:
- AgStack<Object>
-
This class provides pushdown stack functionality. It implements
push(), pop() and top()
operators. The push() operator allocates storage as
necessary as the stack grows. The pop() operator frees
unused storage as the stack shrinks. There is no intrinsic limit
to the number of elements a stack may contain.
- AgSet<Element>
-
This class uses an aleatory binary tree to provide
elementary set theoretic functionality. The basic data management
operators are add() and remove(). The predicate
operator contains() determines whether a given object is
contained in the set. Use of the AgSet<Element> class requires
prior definition of an appropriate hash function.
Hash functions for predefined types and tools for creating hash functions
for more complex types have been provided.
- AgMap<Key, Value>
-
The AgMap class provides a mechanism for creating simple associations.
The value() function returns a reference to the value
associated with a given key. The pValue() function is
similar but returns a pointer rather than a reference and provides
a means of determining whether any value at all has been associated
with a given key. The remove() function provides for
removing an association from the map. Like the AgSet class, AgMap
is based on an aleatory binary tree and
requires that a hash function be defined
for the Key class.
- AgDictionary<Object>
-
The AgDictionary class is similar to the AgMap class. Instead of
mapping a key to a value, though, it maps a collection of objects
to a compact set of integers. The AgDictionary class implements
the intern() function, which is used to add an object to the dictionary,
and the lookup() function, which is used to determine whether an object
can be found in the dictionary. There is no provision for removing
an item from the dictionary. The dictionary class, like the set and
map classes, uses an aleatory binary tree and thus
requires that an appropriate hash function be
defined.
- AgArray<Object>
-
The AgArray class simply provides safe handling of arrays. The principal
method is resize(), which provides for changing the size of the
array.
In addition, all five container classes implement some common functionality:
- Iteration
-
All the container classes implement a size() function and all
override the subscript operator. Thus it is possible to scan the contents
of any container without having to master the intricacies of an iterator
class. Since, in all cases, the subscript operator checks bounds, it is
not possible to inadvertently access memory outside the container.
- The contents() function
-
All of the container classes define a function, contents(),
which returns an instance of a nested class, Contents, which
derives from AgContainerContents<Object>. Here, in its entirety,
is the definition of AgContainerContents:
template <class Object>
class AgContainerContents {
protected:
virtual ~AgContainerContents() {};
public:
virtual int size() const = 0;
virtual const Object &operator [] (int) const = 0;
};
All of the container classes implement a constructor which takes a
reference to an instance of AgContainerContents, so that any
container can be initialized with the contents of another. All of
the container classes also override the assignment operator to enable
assigning the contents of any container to any other container.
The AgMap class provides the functions keys()
and values()
which also inherit from AgContainerContents. Thus, they too can be used to
initialize any container or can be assigned to any container.
- Assignment operator override
-
All the template classes override the assignment operator, using
value semantics.
- Relational operators
-
Equality and inequality operators are implemented for each class.
Other relational operators are defined only for the AgSet class.
The string class, AgString, exists largely for
convenience. Any other string class could be used just as well. For those
users who would prefer to use another, implementations of AgString have
been provided in terms of the MFC class CString
(agstr_mfc.h) and in
terms of the Standard Template Library string class
(agstr_stl.h). These
classes allow for interoperation of AgString with CString and std::string
respectively.
All of the user level classes in AGCLIB1 are reference counted and
implement "value semantics" using a copy on write technique. The basic idea
of copy on write is that two or more objects may share the same storage
until such time as one of the objects is changed.
The assignment operator is overloaded and simply increments the reference
count on the actual data. Similarly, the copy constructor only increments
the reference count. Only when one of the objects is modified, i.e., there
is a non-constant reference to the data, is the data actually copied.
In many cases, such as returning an object from a function, one of the
objects is deleted before the other is ever modified, so no copy is ever
needed.
Note that for several of the methods defined on the classes, there are two
implementations: one a constant function returning a constant value, the
other a non-constant function returning a non-constant value. Since the
constant version cannot alter the contents of the data belonging to an
object, the constant version will never cause a physical copy of data. The
non-constant version, however, will, if there is more than one object
referring to the data, make a separate copy of the data for each object.
Your C++ compiler will select the correct implementation depending on
whether the object you are using has been declared const or not. To
minimize unnecessary copying, make it a practice to declare values as
const if you have no intention of modifying them.
Further information about copy on write implementations may be found in
section 16.21 of the C++ FAQ:
http://www.faqs.org/faqs/C++-faq/part6
Also relevant is the discussion of value semantics in section 28
http://www.faqs.org/faqs/C++-faq/part8
Another benefit of the copy on write implementation is that when the last
reference to an object is deleted, the object itself is deleted. Thus these
classes can be used without the risk of creating memory leaks.
The container classes all support a size() method which returns the number
of items in the container and a subscript operator to return the k'th item
in the container. Iterators are therefore unnecessary, since it is possible
to step through the contents of any container using ordinary indexing.
It is tempting to attempt to formalize this homogeneity by creating
an abstract class from which the classes would inherit. In
practice, however, doing so adds substantial complexity and overhead
with little tangible benefit.
In fact, it turns out that it is quite easy and unconstraining to write
a few template functions that provide most of the benefit and of such
an abstract class without the attendant costs. A number of such functions
are defined for each class in the library. These are documented under the
heading "Externally Defined Functions" for each particular class. Since
these functions are defined externally to the classes, the user can safely
ignore their existence unless they are useful to him.
The library also contains, in agsort.h,
externally defined functions to sort the contents of a container. These
functions all return an integer permutation array rather than rearranging
the contents of the container. There are four basic sort functions,
depending on how the comparison of elements is to be carried out.
template <class Container>
AgArray<int> agSort(const Container &, int ascending = 1);
-
This function sorts the contents of the Container using the operator <()
function defined for the objects in the container.
template <class Container, class Object>
AgArray<int> agSort(const Container &, int (*)(const Object &, const Object &), int ascending = 1);
-
This function allows the user to supply a pointer to a comparison function.
Unfortunately, at least one popular C++ compiler has troubles recognizing
template functions that have such a complicated signature. Programmers who
use such a compiler should use the function object version of agSort
described below.
template <class Container, class SortKey>
AgArray<int> agSort(const Container &c, const SortKey &(Object::*sortKey)() const, int ascending = 1);
-
This version of the agSort function can be used when a collection of records
is to be sorted by some key belonging to the records. The argument to the
sort function is a method pointer which identifies a function which returns
a reference to the desired sort key. Some C++ compilers have difficulties
with this form, so, again, the function object version of AgSort provides
a workaround for broken compilers.
template <class Container, class Object>
AgArray<int> agSort(const Container &, const AgSortCompare<Object> &, int ascending = 1);
-
In this version of agSort, a function object is used to specify the
comparison operation. AgSortCompare<Object> is a template class that
contains nothing but a pure virtual override of the function call object.
Here is the complete definition:
template <class Object>
struct AgSortCompare {
virtual int operator ()
(const Object &, const Object &) const = 0;
};
Instead of writing a special compare function and passing a pointer to it,
you derive a class from AgSortCompare and overload the function call
operator. Here for example, is a function object used to sort strings
by length, with strings of equal length sorted alphabetically:
struct Compare : public AgSortCompare<AgString> {
int operator ()
(const AgString &x, const AgString &y) const {
int flag = x.size() - y.size();
if (flag) return flag;
return strcmp((const char *) x, (const char *) y);
}
} compare;
Here is a function object used to sort according to a key in
a record.
struct Compare : public AgSortCompare<Record> {
int operator ()
(const Record &x, const Record &y) const {
return x.sortKey() - y.sortKey();
} compare;
In all these functions, the ascending parameter can be set to 0
if it is wished to sort in descending order. Note that, since template
functions cannot have default argument values, the effect has actually been
accomplished by defining a total of eight template functions, with and
without the "default argument".
To print a sorted list of the contents of a dictionary containing
strings, one would code the following:
void printSorted
(const AgDictionary<AgString> &dictionary) {
AgArray<int> permutation = agSort(dictionary);
for (int i = 0; i < dictionary.size(); i++) {
printf("%4d: %s\n", i,
(const char *) dictionary[permutation[i]]);
}
}
Note the use here of the cast operator to extract a string pointer
for the use of printf().
Three of the container classes, AgSet, AgMap and AgDictionary,
require the existence of a hash function, agABTHash() defined on
the objects stored in the containers. There are no particular requirements
on the hash function except that if two objects are equal, their hash
values must be equal. If two objects are not equal, the probability
that their hash values are not equal should be as high as possible.
The following functions are predefined:
int agABTHash(const int, int startValue = 0);
int agABTHash(const double, int startValue = 0);
int agABTHash(const char *, int startValue = 0);
int agABTHash(const AgString &, int startValue = 0);
In addition, an agABTHash function is defined for each container, in
terms of the agABTHash function defined for the elements it contains.
The startValue parameter is convenient
for calculating a hash code for an object that consists of several components.
For example, if we have a class Foobar with member fields foo and bar, we
can define the hash code for a Foobar object in terms of the already
defined hash codes for foo and bar:
int agABTHash(const Foobar &f, int startValue = 0) {
startValue = agABTHash(f.foo, startValue);
return agABTHash(f.bar, startValue);
}
Finally, the following function has been provided for use when writing a hash function
for a struct or array of known size.
int agABTHash(const void *array, int size, int startValue = 0);
For example, consider the following definitions of a struct and
a corresponding instance of agABTHash():
struct Widget {int x, y, z; double u;};
int agABTHash(const Widget &widget, startValue = 0) {
return agABTHash(&widget, sizeof(Widget), startValue);
}
#include "agstk.h"
AgStack<Object> is a template class that can be used to provide an
efficient stack of objects of any type. It can also be used as a dynamic
array. The subscript operator has been implemented to allow efficient
access to any element of the array. Since storage allocation is completely
dynamic, AgStack<Object> can accommodate a stack of arbitrary depth. As
objects are popped off the stack, storage is recovered.
AgStack<Object> maintains an active buffer capable of holding
bufferSize objects. bufferSize defaults to 64. When
this buffer fills up, a pointer to the buffer is stacked on a pointer stack
(implemented recursively with AgStack<void *>) and a new active buffer
is allocated. Note that the active buffer of the pointer stack will fill up
in turn, requiring a second level of nesting, only when the active buffer
of the primary stack has been filled up bufferSize times. For
the default value of bufferSize, this occurs only when 64*64 =
4096 objects have been pushed onto the main stack.
Storage overhead for an AgStack<Object> is minimal. An empty
AgStack<Object> object requires only 24 bytes of overhead in
addition to the storage required for the active buffer. By setting
the size of the active buffer to 8 or 16 elements, an
AgStack<Object> can handle even small lists with less computational and
storage overhead than many implementations of linked lists.
The stack algorithm does not require moving objects when resizing.
Therefore once an object has been pushed onto an AgStack<Object>,
it is never moved. Thus it is safe to use a pointer to an object
on an AgStack<Object> so long as it has not been popped off.
AgStack<Object>(unsigned bufferSize = 64);
-
The bufferSize parameter may take on any positive integer value.
It sets the size of the active stack buffer. If you know that a stack is
unlikely to have more than a dozen entries, you might want to set this
parameter to 10 or 12. On the other hand, if you know that a stack might
have thousands of entries you might want to increase the value to
500 or 1000.
AgStack<Object>(const AgContainerContents<Object> &, int bufferSize = 64);
-
Creates a stack and pushes the elements of the container contents onto it.
Elements of the container contents are taken in numerical order, beginning with
zero, so the data will be in the reverse order on the stack.
As with the previous constructor, the bufferSize parameter sets
the size of the active stack buffer.
AgStack<Object>(const AgStack<Object> &);
-
Creates a new stack object with the same data as the argument stack. No data
is actually copied until there is an attempt to modify data. In that case, if
there is still more than one reference to the data, the data will be copied.
~AgStack<Object>();
-
Decrements the use count and, if there are no other references, deletes
all the data in the stack.
AgStack<Object> &push(const Object &t);
-
If multiple stack objects are sharing the stack data, a private copy is
made. Then a copy of the specified object is pushed onto the stack. The
function returns a reference to the stack.
Object pop();
-
If multiple stack objects are sharing the stack data, a private copy is
made. The top object on the stack is then popped off and returned as the
value of the function.
Object &top();
const Object &top() const;
-
These two implementations of
top() allow for read-only
access or read-write access to the top element of the stack. If the stack
data is shared by two different stack objects, the non-constant version
will cause the data to be copied.
int size() const;
-
Returns the number of objects on the stack.
AgStack<Object> &reset();
-
If there are multiple references to the data on the stack, the reference
count is decremented and a new empty stack is created. Otherwise, the
stack is emptied and its contents are deleted. The function returns a
reference to the stack.
const AgStack<Object>::Contents contents() const;
-
The Contents class is derived from AgContainerContents<Object>. The
contents() function can be used to initialize any class in the class
library or can be used to copy the contents of any container class to any
other container class.
AgStack<Object> &operator =(const AgStack<Object> &);
-
Assigns a new value to a stack object.
AgStack<Object> &operator =(const
AgContainerContents<Object> &);
-
This function discards the entire stack contents and then pushes the
elements of the specified container contents onto the stack. As with the corresponding
constuctor, the elements of the container contents are pushed in numerical order,
beginning with zero, so that indices are reversed on the stack.
Object &operator[] (int k);
const Object &operator[] (int k) const;
-
These two implementations of the subscript operator provide separate
implementations for read-only access and read-write access. The
non-constant operator will induce a physical copy of the data if two or
more objects are sharing the same data. The const operator will not cause a
copy.
Stack elements are indexed from the beginning of the stack, not, as is
sometimes done, from the top of the stack. Thus stack[0]
returns the first item pushed onto the stack, not the last. The justification
for this approach is that, when indexing is done this way, the index of a
particular item is invariant and does not change as items are pushed onto,
or popped off, a stack.
int operator == (const AgStack<Object> &x) const;
int operator != (const AgStack<Object> &x) const;
-
These operators can be used to determine if two stacks are the same or
different. Two stacks are equal if and only if they have the same
number of elements and correspondingly indexed elements are equal.
The following function definitions should be understood as template functions
with template parameters Object and Container, as appropriate.
AgStack<Object> &operator += (AgStack<Object> &a, const Container &c);
-
The contents of the specified container are pushed onto the stack.
This operator can be used on any container class which implements a size() operator
and overloads the subscript operator to provide an instance of the Object class.
int agABTHash(const AgStack<Object> &c, int startValue = 0);
-
This template function creates a hashcode for the specified stack as a
whole, thus ensuring that AgStack instances may be used as elements of AgSet, AgMap or AgDictionary instances. This function requires
that agABTHash(const Object &, int startValue) be previously defined.
#include "agset.h"
AgSet<Object> is a template class that can be used to provide the
functionality of mathematical sets. The elements of the set are stored
using an "aleatory binary tree", which does not require any comparison
function for the elements of the set other than the equality operator,
"==".
In order to define an AgSet class for a specified Object class, there must
be a hash function defined for the Object
class. Versions of agABTHash() are predefined in the library for
the types int, double, null terminated character strings, and
all the classes defined in the library. The definitions for the container
classes are all in terms of the definition of agABTHash() for
the elements contained within the container.
AgSet<Object>();
-
Creates an empty set object.
AgSet<Object>(const AgContainerContents<Object> &);
-
Creates an set which contains all of the distinct elements of the
container contents. Note that unless all the elements of the aggregate are distinct,
the size of the set will be less than the size of the container contents.
AgSet<Object>(const AgSet<Object> &);
-
Creates a new set object with the same value as the argument. No physical
copy takes place until the value is changed.
~AgSet<Object>();
-
Decrements the reference count and deletes the stored data if the
reference count becomes zero.
Object *add(const Object &);
-
Adds the object to the set if it is not already a member of the set and
returns a pointer to the object contained in the set.
int remove(const Object &);
-
Removes the matching object, if any, from the set and returns zero if no
matching object was found, non-zero if an object was removed.
Object *contains(const Object &);
const Object *contains(const Object &) const;
-
These functions return a pointer to the matching object in the set,
if it exists, NULL otherwise. These functions can be used to determine
if a set contains a matching object.
These two implementations of the contains() function provide
separate implementations for read-only access and read-write access. The
non-constant variant will induce a physical copy of the data if two or
more objects are sharing the same data. The const variant will not cause
a copy. Note that the compiler will determine which implementation to use
by checking to see whether the set is or is not declared
const, not by what is done with the pointer that is returned.
int size() const;
-
Returns the number of elements in the set;
AgSet<Object> reset();
-
If the set data is being shared with another set, a new, empty set
is created. Otherwise, the existing contents of the set are deleted,
leaving it empty.
const AgSet<Object>::Contents contents() const;
-
The Contents class is derived from AgContainerContents. The contents()
function can be used to initialize any class in the class library or
can be used to copy the contents of any container class to any other
container class.
AgSet<Object> &operator =(const AgSet<Object> &);
-
Assigns a new value to an AgSet object.
AgSet<Object> &operator =(const
AgContainerContents<Object> &);
-
Replaces the contents of the set with the distinct elements of the
specified container contents.
Object &operator[] (int k);
const Object &operator[] (int k) const;
-
The subscript operator can be used to step through the elements of a set.
There are two versions of the function, a constant and a non-constant
version. Note that if you change the value of the object it could
adversely affect subsequent lookups. The rule is that you can modify any
field that is not checked by the equality operator (or involved in
the calculation of the hash code). If you need to change the value of an
element in such a way that the new value is no longer equal to the old
value (in the sense of the "==" operator), remove the element, change it,
and then add it back to the set.
int operator <= (const AgSet<Object> &, const AgSet<Object> &);
-
Returns 1 if the left hand operand is a subset of the right hand
operand, 0 otherwise.
int operator < (const AgSet<Object> &, const AgSet<Object> &);
-
Returns 1 if the left hand operand is a proper subset of the
right hand operand, 0 otherwise.
int operator >= (const AgSet<Object> &, const AgSet<Object> &);
-
Returns 1 if the right hand operand is a subset of the left hand
operand, 0 otherwise.
int operator > (const AgSet<Object> &, const AgSet<Object> &);
-
Returns 1 if the right hand operand is a proper subset of the
left hand operand, 0 otherwise.
int operator == (const AgSet<Object> &, const AgSet<Object> &);
int operator != (const AgSet<Object> &, const AgSet<Object> &);
-
These operators can be used to determine if two sets are the same or
different. Two sets are equal if and only if they contain
exactly the same elements. Note that the order of the elements, as
accessed by the subscript operator, may be different in the two sets.
The following template functions are defined externally to the AgSet class, and are
thus not part of the class itself. They provide the capability to write
conventional set theoretic expressions involving unions, differences and
intersections. Notice that in all cases, the
right hand operand can be any container which supports the size() method
and a subscript operator that returns an object of the same sort that is
stored in the set.
The following function definitions should be understood as template functions
with template parameters Object and Container, as appropriate.
AgSet<Object> operator +(const AgSet<Object> &, const Container &);
-
Returns a new set which contains all the objects in both the set
and the container operands. This is the set-theoretic union of the set and
the set of objects in the container.
AgSet<Object> &operator +=(const AgSet<Object> &, const Container &);
-
Adds all objects in the specified container to the set. This results in the
set-theoretic union of the set and the set of objects in the container.
AgSet<Object> operator -(const AgSet<Object> &, const Container &);
-
Returns a new set which contains all objects of the set operand that
cannot be found in the specified container operand.
AgSet<Object> &operator -=(const AgSet<Object> &, const Container &);
-
Removes all objects in the container operand from the set operand.
AgSet<Object> operator *(const AgSet<Object> &, const Container &);
-
Returns a new set object which contains all Objects of the set which can also be found in the
specified container. This is the set-theoretic intersection of the set and the set
of elements in the container.
AgSet<Object> &operator *=(const AgSet<Object> &, const Container &);
-
Removes all objects from the set operand that cannot be found in
the container operand. This operation results in the set-theoretic intersection
of the set operand and the contents of the container operand.
-
int operator >=(const AgSet<Object> &, const Container &);
-
Returns non-zero if the contents of the container are a subset of the set, i.e., if
all elements of the container are also to be found in the set.
int agABTHash(const AgSet<Object> &c, int hash = 0);
-
This template function creates a hashcode for the specified set, thus
ensuring that AgSet instances may be used as elements of AgSet, AgMap or AgDictionary instances.
#include "agmap.h"
AgMap<Key, Value> is a template class that can be used to associate
value objects with key objects. The AgMap class is implemented as an aleatory binary tree of AgKVPair<Key, Value> objects, using the same
technique that is used for the AgSet class.
In order to define an AgMap class for a specified Key-Value pair, there
must be a hash function defined for the Key
class. Versions of agABTHash() are predefined in the library for
the types int, double, null terminated character strings, and
all the classes defined in the library.
The AgKVPair<Key, Value> class is a helper class used to implement
the AgMap class. It consists of a key-value pair and the minimal
functionality to support such a pair:
- Constructors
- AgKVPair(const Key & = Key();, const Value & = Value());
- AgKVPair(const AgKVPair<Key, Value> &);
- Access Methods
- const Key &key() const;
- Value &value();
- const Value &value() const;
- Comparison Operators
- int operator == (const AgKVPair<Key, Value> &);
- int operator != (const AgKVPair<Key, Value> &);
The key() and value() functions simply return the
key and value elements respectively. Note that the key()
function can only be used to return a constant reference to the key, since
if a key internal to an AgMap were to be modified, subsequent behavior of
the AgMap object would be indeterminate.
Two nested classes are defined in AgMap: Keys and
Values. These classes allow ready access to the
domain and range of the mapping. AgMap contains methods,
keys() and values(), which may be used to obtain an
instance of either.
AgMap<Key, Value>();
-
Creates an empty AgMap object.
AgMap<Key, Value>(const AgContainerContents<AgKVPair<Key, Value> > &);
-
Creates a map from the array of key, value pairs.
AgMap<Key, Value>(const AgMap<Key, Value> &);
-
Creates a new AgMap object with contents initially equal to the contents
of the argument.
~AgMap<Key, Value>();
-
Decrements the use count and, if there are no other references, deletes
all the data in the stack.
Value &value(const Key &key);
-
The value function looks up a key in the map and returns a reference to
the value associated with the key. If no value has previously been
associated with the key, a new one is created using the null constructor
for the Value class. Use the value function to assign a value to a key:
map.value(key) = valueAssociatedWithKey;
Value *pValue(const Key &key);
const Value *pValue(const Key &key) const;
-
Both versions of the pValue method return a pointer to the value
associated with the specified key, if it exists. Otherwise, they return
NULL. pValue() can be used either to determine the value for a
given key, or to modify the value of a key already entered in the map.
The nonconstant version of the operator will trigger a copy of the
data in the map if the data is being shared by two or more maps.
int remove(const Key &key);
-
Removes the key and its associated value from the map. If there are
multiple references to the stack, a private copy is made before the key
is removed. The return value is 1 if the key was found and removed, 0 if
the key was not found.
int size() const;
-
Returns the number of key-value pairs in the map.
AgMap<Key, Value> &reset();
-
Releases the data belonging to the map. Returns a reference to the map
object.
AgMap<Key, Value>::Contents contents() const;
-
Returns an instance of the nested class Contents which contains
all key, value pairs in the map. The Contents class inherits from
the AgContainerContents<Key, Value> class and provides a mechanism
for copying the contents of the map to any other kind of container class.
Keys keys() const;
-
Returns an instance of the nested class Keys which contains
the keys for all the items in the map. The Keys class inherits from
the AgContainerContents<Key> class and provides a mechanism
for copying the key fields defined by the map to any other kind of container class.
Values values() const;
-
Returns an instance of the nested class Values which contains
the keys for all the items in the map. The Values class inherits from
the AgContainerContents<Value> class and provides a mechanism
for copying the value fields defined by the map to any other kind of container class.
AgMap<Key, Value> &operator =(const AgMap<Key, Value> &);
-
Deletes the entire content of the map and sets its value to that of the argument.
No actual data is copied until one or the other of the two map objects is
altered.
AgMap<Key, Value> &operator =
(const AgContainerContents< AgKVPair<Key, Value> > &);
-
Deletes the current content of the map and replaces it with key-value
pairs from the specified container contents.
AgKVPair<Key, Value> &operator[] (int k);
const AgKVPair<Key, Value> &operator[] (int k) const;
-
Provide access to the k'th element of the map. If this map object is
sharing data with another map object and the access is not a constant
access, the contents of the map object will be copied.
AgMap<Key, Value> &operator += (AgMap<Key, Value> &m, const Container &c);
-
The contents of the Container, which must be elements of the AgKVPair<Key, Value>
class, are added to the map.
int agABTHash(const AgMap<Key, Value> &m, int startValue = 0);
-
This template function creates a hashcode for the specified map, thus
ensuring that AgMap instances may be used as elements of AgSet, AgMap or AgDictionary instances.
#include "agdict.h"
The AgDictionary class provides a simple mechanism for identifying
and storing objects, as might be used, for example, in the implementation of a symbol
table. The intern() function adds an object to the dictionary and
returns an integer index that identifies the object uniquely. The
lookup() function returns the index of an object if it is found
in the dictionary and -1 otherwise.
Note that there is no provision for deleting a single object from a
dictionary.
AgDictionary<Object>();
-
Creates an empty dictionary object.
AgDictionary<Object>(const AgContainerContents<Object> &);
-
Creates a dictionary and enters the elements of the argument into it.
Elements of the specified container contents are taken in numerical order, beginning with
zero. Notice that any element is occurs more than one time in the
argument will only occur once in the dictionary, so it cannot be
assumed that index values in the dictionary correspond directly to index
values in the argument.
AgDictionary<Object(const AgDictionary<Object> &);
-
Copy constructor creates a new dictionary object. Data will only be
copied if there is an attempt to modify the dictionary and the
use count is greater than one.
~AgDictionary<Object>();
-
Deletes the dictionary object. If there is no other dictionary object
that refers to the actual content of the dictionary, the contents are
deleted.
int intern(const Object &s);
-
Enters the object into the dictionary, if it is not already there, and
returns the index associated with the Object.
int lookup(const Object &s) const;
-
Returns the index associated with the object if it has been
previously entered into the dictionary. Otherwise, the function returns -1.
int size() const;
-
Returns the number of entries in the dictionary.
AgDictionary<Object> reset();
-
Deletes the entire contents of the dictionary, leaving it empty.
const AgDictionary<Object>::Contents contents() const;
-
The Contents class is derived from AgContainerContents. The contents()
function can be used to initialize any class in the class library with
the contents of the dictionary or
can be used to copy the contents of the dictionary to any container class
object.
AgDictionary &operator = (const AgDictionary<Object> &s);
-
Assigns a new value to an AgDictionary object. If there are no other
AgDictionary objects that refer to the contents of the dictionary, the
contents are deleted.
const Object &operator [] (int k) const;
-
Provide a reference to the k'th object in the dictionary. Note that the
value is a constant reference, so the object contained in the dictionary
cannot be modified.
The following function definitions should be understood as template functions
with template parameters Object and Container, as appropriate.
AgStack<Object> &operator += (AgDictionary<Object> &a, const Container &c);
-
The contents of the specified container are added to the dictionary using
the intern() function. This operator can be used on any
container class which implements a size() operator and
overloads the subscript operator to provide an instance of the Object
class.
int agABTHash(const AgDictionary<Object> &c, int hash = 0);
-
This template function creates a hashcode for the specified dictionary, thus
ensuring that AgDictionary instances may be used as elements of AgSet, AgMap or AgDictionary instances.
#include "agarray.h"
AgArray<Object> is a template class that can be used to provide simple
resizable arrays that use copy on write, making it easy to return arrays
from functions without undue overhead.
AgArray<Object>();
-
Creates an empty array object.
AgArray<Object>(int n);
-
Creates an array of n Objects.
AgArray<Object>(const Object *d, int n);
-
Creates an array of n Objects and initializes it with the contents of the
specified array.
AgArray<Object>(const AgContainerContents<Object> &);
-
Creates an array and populates it with the contents of the specified
container contents.
AgArray<Object>(const AgArray<Object> &);
-
The copy constructor creates a new AgArray object that contains the same data as
the argument object. Note that the data is not physically copied, if at all, until
one or the other of the two array objects is modified.
~AgArray<Object>();
-
Decrements the reference count and deletes the stored data if the
reference count becomes zero.
int size() const;
-
Returns the size of the array.
AgArray<Object> &resize(int newSize);
-
Resizes the array to the specified size.
const AgArray<Object>::Contents contents() const;
-
The Contents class is derived from AgContainerContents. The contents()
function can be used to initialize any class in the class library or
can be used to copy the contents of any container class to any other
container class.
AgArray<Object> &operator =(const
AgArray<Object> &);
-
Assigns a new value to an AgArray object.
AgArray<Object> &operator =(const
AgContainerContents<Object> &);
-
Replaces the contents of the array with the specified
container contents.
Object &operator[] (int k);
const Object &operator[] (int k) const;
-
These two implementations of the subscript operator provide separate
implementations for read-only access and read-write access. The
non-constant operator will induce a physical copy of the data if two or
more objects are sharing the same data. The const operator will not cause
a copy. Note that when an array is subscripted, the compiler will determined
which implementation to use by checking to see whether the array is or is
not declared const, not by what is done with the reference
returned.
operator Object *();
operator const Object *() const;
-
These cast operators provide direct access to the data in the array. Note
that when the data is accessed via these operators, there is no bounds
checking on subscripts, so these operators should be used with extreme
care. As with the subscript operator, the compiler chooses the operator
overload by checking whether the array is or is not declared
const.
int operator == (const AgArray<Object> &x) const;
int operator != (const AgArray<Object> &x) const;
-
These operators can be used to determine if two arrays are the same or
different. Two arrays are equal if and only if they have the same
number of elements and correspondingly indexed elements are equal.
The following function definitions should be understood as template functions
with template parameters Object and Container, as appropriate.
AgArray<Object> &operator += (AgArray<Object> &a, const Container &c);
-
The array is resized to provide room for the contents of the specified container.
This operator can be used on any container class which implements a size() operator
and overloads the subscript operator to provide an instance of the Object class.
int agABTHash(const AgArray<Object> &c, int hash = 0);
-
This template function creates a hashcode for the specified array, thus
ensuring that AgArray instances may be used as elements of AgSet, AgMap or AgDictionary instances.
#include "agstr.h"
The AgString class provides a simple mechanism for handling string objects.
In particular, it takes care of allocating and freeing memory. The class
uses the "copy on write" technique to minimize unnecessary copies. See Value Semantics above.
Since there already exists a surfeit of string classes, care was taken to
make AgString simple enough to be easily replaced with another class. To
facilitate this task, two alternative definitions of the class can be
found in agstr_mfc.h and
agstr_stl.h which implement AgString
in terms of the Microsoft Foundation Class CString and the standard
template library string class respectively.
AgString();
-
Creates a null string object.
AgString(int count);
-
Creates a string object with room for a string of
count bytes.
AgString(const char *s);
-
Creates a string object with the specified text.
AgString(const AgString &string);
-
Creates a new string object which points to the same text as
string. A subsequent attempt to modify the contents of
either the copy or the original will cause a new copy of the actual text
string to be made prior to the modification. If the destructor for one
string is called before any attempt to modify the contents of the other,
no copy will be necessary and none will be made.
~AgString();
-
If no copies of the string have been made, the object is deleted. If a
copy exists, the reference count is simply decremented.
AgString &operator = (const AgString &s);
-
Assigns a new value to an AgString object.
operator const char *() const;
-
Provides a pointer to the string value. Note that access to the data is
read only. If the string is empty, this function returns a null pointer.
char &operator [] (int k);
const char &operator [] (int k) const;
-
Provide a reference to the k'th character of the string. Subscripting
begins with the 0'th character of the string.
int operator < (const char *s) const;
int operator > (const char *s) const;
int operator <= (const char *s) const;
int operator >= (const char *s) const;
int operator != (const char *s) const;
int operator == (const char *s) const;
-
These operators return non-zero for true or zero for false. Note that these functions
can be used to compare two AgString objects.
AgString &append(int c) const;
-
Appends the specified character to the string.
AgString &append(const char *s) const;
-
Appends the specified character string to the string. Note that this
function can be used to concatenate two AgString objects.
AgString &append(const char *s, n) const;
-
Appends no more than n characters from the specified character string to
the string.
int size() const;
-
Returns the length of the string. Note that the size does not include
the null byte at the end of the string.
- AgString &reset();
-
Creates a new null string if the reference count is greater than one.
Otherwise, it discards the content of the string and resets it to have
zero length.
All of the user level classes are
implemented as pointers to reference counted base class objects. The actual
implementation is to be found, then, in these classes:
The AgMapBase and AgSetBase classes are both derived from the
AgAleatoryBinaryTree<Object> class. The tree nodes are instances of the
AgAleatoryBinaryNode<Object> class. These classes are declared in agabt.h.
The value semantics or copy on write feature
is implemented by the joint operation of the AgReferenceCounter and the
AgCopyControl classes. These classes are defined in agref.h
Make files have been provided for users of six different compilers:
|
Directory |
|
Compiler |
|
Make Command |
|
msvc |
|
Miscrosoft Visual C++ |
|
nmake |
|
borland |
|
Borland C++ |
|
make |
|
watcom |
|
Watcom C++ |
|
wmake |
|
vacpp |
|
IBM Visual Age for C++ |
|
nmake |
|
gcc |
|
gcc on *nix Systems |
|
make |
|
intel |
|
Intel C++ Compiler 5.0 for Linux |
|
make |
If you are using some other compiler, here are the modules you need to
compile and link to form the library:
Although they are slightly slower, binary trees are generally more versatile
devices than hash tables for identifying objects. Hash tables are cumbersome
and difficult to extend. The main trouble with binary trees is the need for
keeping them balanced. If the objects are not entered into the tree in a
completely random way, a tree with no balancing could, in the extreme case,
degenerate into a simple linked list. Access time then would be proportional
to the number of entries in the tree rather than the logarithm of the number
of entries.
There are a number of ways to keep a tree balanced, but all are moderately
tedious to code and are consequently error prone. Furthermore, binary
trees can only be used to store objects that are members of a well ordered
set.
Aleatory binary trees combine the benefits of hash tables with the neatness
of binary trees. The idea is to use a hash code to determine whether, when
creating subnodes, a subnode is to go on the left or on the right. Rather
than compare the objects themselves, the comparison is made on hash codes
derived from the objects. If the hash code produces reasonably random
results, the outcome is a binary tree that doesn't need balancing when new
items are inserted or when items are removed. Of course, the trees are
usually not balanced within a single level, as is the case with
conventional balanced binary trees, since the degree of balance is a matter of
probabilities. Nevertheless, actual experience shows that average access time
increases logarithmically with the number of entries in the tree, although
at a slightly greater rate than would be the case with a conventional
balanced tree.
The downside to the use of aleatory binary trees is that it is not
possible at this time to automate the creation of hash functions for tree
objects. To do so properly requires the use of template restrictions in C++,
a feature of the ISO/ANSI standard that is not yet widely available. As a result,
anyone wishing to use an aleatory binary tree has to explicitly write a
hash function. A number of appropriate hash functions have been provided as
part of the AGCLIB1 library.
|
