category-group: containers
layer(s): 1, 2, 3 header file(s): z_array.h classes in this group: alist_o <T>, aordlist_o <T>, aordset_o <T>, array_o <T>, aset_o <T>, cnode_o <T>, cursor_o <T>, linkedlist_o <T>, list_axiom_o <T>, list_o <T>, llist_o <T>, llnode_o <T>, llonode_o <T>, llordlist_o <T>, llordset_o <T>, llpnode_o <T>, llset_o <T>, onode_o <T>, ordlist_o <T>, ordset_o <T>, pnode_o <T>, set_o <T> function groups:
layer 02 functions group description.
Containers constitute an integral part of the Z Directory. There are many types of Z Directory containers. They are all template-based (similar to STL). Access to objects in any Z Directory container is done via a cursor. Usage of a cursor is the same, regardless of the type of container. This means that all container types support the same operations: add(), insert(), fetch(), remove(), get(), and put(). These can be done for both linked lists and arrays (*). Containers have been evolving and (in this century) have some new features added. Sometimes a container operation can be expensive (in computer science context: ie, requiring many search steps or move operations), and hence, sub-optimal, for the given type of container. For example, get() can result in a long linear search for linked lists, when the cursor is far from the desired node. Also, insert() can be expensive if it results in an insertion of an object in an array, since this requires relocation of all successor objects. An advantage to having all container types conform to a common API is that the container can be swapped from one type to another - even dynamically. It is then possible to implement a higher-level class ("vlist") that can have a pointer to the container. The client code, e.g., the end-user, might not even know or care about what kind of container is in use. The interface classes of containers are abstract, and present the user with a choice of types of data to be stored: list, ordered list, set, ordered set, etc. A mixin methodology is used to bind the interface classes to the implementation classes:
One does need to know what type of container is needed in advance - whether it is to be a list or set; ordered or not, etc. The class hierarchy is a straightforward implementation of this idea:
If no information is available about the data to be stored
in a container, one should use "vlist_o" - a 'virtual list'.
Container nodes.
Each object in a container is assigned a "node". The node contains data needed specifically to link the item to the container. Linked list nodes contain pointers to the 'next' and 'previous' nodes, for example. Tree nodes contain pointers to "child" objects. There is another classification of nodes - whether a node points to its data object (a "pnode") or contains it (an "onode"). This [relatively new] feature allows a node to hold a pointer, instead of embedding the object. This has the advantage of allowing an object to be passed around by simply moving its pointer. In the case of embedded objects within an array, deletion of an object would require calling the copy constructor for each object that had to relocate - a very expensive operation. Also, using pointers facilitates the "take()" operation, which allows one container to "take" the contents of another, leaving the "taken" container empty. Node hierarchy:
You may notice that multiple inheritance ("MI") is used here.
This is a very specialized use of MI, not commonly found in the Z
Directory. MI is generally discouraged; its usage here is a special
case. The overall relationships of the container classes is described
by this schematic:
How to use containers.
The easiest way to start with containers is by adding objects to a vlist_o container. A "vlist" is defined simply as an alist object:
#define vlist_o alist_o
This is in the header file z_simplist.h. The next question is,
"what is an 'alist'?". This is also found in the same include file,
and it is the [multiple-inheritance] marriage of an array and the
list class:
template <class T>
class alist_o : virtual public array_o<T>, virtual public list_o<T>
The array (array_o) provides the implementation, and the list
(list_o) indicates that the objects contained are a simple
list: unordered, and there can be multiple occurances of the "same"
object - that is, it is not a "set". So the default container is an
array. It need not be: if you prefer, say, a linked list, you can use
the (llist_o) container object:
template <class T>
class llist_o : virtual public linkedlist_o<T>, virtual public list_o<T>
There are many combinations available to choose from:
No matter what is chosen, the usage is the same. Here is an example of adding objects to an aset_o, then iterating through the collection, and finally deleting an object from the set:
name header file description alist_o z_simplist.h a list, stored as an array llist_o z_simplist.h a list, stored as a linked list aset_o z_hardlist.h a set, stored as an array llset_o z_hardlist.h a set, stored as a linked list aordlist_o z_hardlist.h an ordered list, stored as a linked list llordlist_o z_hardlist.h an ordered list, stored as a linked list aordset_o z_hardlist.h an ordered set, stored as an array llordset_o z_hardlist.h an ordered set, stored as alinked list
#include <iostream>
#include "z_hardlist.h"
class MyNum
{
public:
MyNum () { i = 0; }
MyNum (int j) { i = j; }
int operator == (const MyNum &rhs) const { return (i == rhs.i) ? 1 : 0; }
int operator != (const MyNum &rhs) const { return (i == rhs.i) ? 0 : 1; }
int get () const { return i; }
int reset () { i = 0; return 0; }
static const MyNum &bad_reference ();
private:
int i;
};
int main (int argc, char **argv)
{
int i, ie;
MyNum x5(5), x6(6), x9(9), x9_again(9);
aset_o<MyNum> numbers;
cursor_o<MyNum> cunum(numbers);
// [1] populate the set
numbers.put (x5); // don't use add for sets,
numbers.put (x6); // lists, ordered sets, etc
numbers.put (x9); // add() is for array_o/list_o
numbers.put (x9_again); // fails, '9' already in the set
// [2] iterate thru the set
for (i = 0, cunum.first(); cunum.ok(); i++, cunum++)
{
const MyNum &currno = cunum.fetch();
std::cout << "MyNum object " << i << ":" << currno.get() << std::endl;
}
count_t idx = 2; // [3] remove 2nd member
numbers.remove (idx, &ie);
return 0;
}
const MyNum &MyNum::bad_reference ()
{
static MyNum *badref = NULL;
if (badref == NULL)
{
badref = new MyNum;
if (badref == NULL)
{ std::cout << "can't 'new' a \"MyNum\"!!\n"; }
}
return *badref;
}
Irregardless of the type of container - whether llist_o,
aset_o, llset_o, aordlist_o, llordset_o,
or other - the code will be almost identical. The only changes may be
in the include file name, and wherever 'aset_o' appears, you would
substitute in the desired class. Note that for ordered containers,
the ">" and ">=" operators must be defined in your class, and
for sets, the "==" and "!=" member function operators must be defined.
For lists (alist_o and llist_o), there are no
requirements. If you don't care about how the items are contained,
and order or uniqueness is not relevant, we suggest you use the
vlist_o object.
using containers: the "bad reference".
Finally, any class that is to be used in a container must have the static member function bad_reference(). You may notice this function in many Z Directory header files. They exist whenever a class was used in a container. This function returns a reference handle to a singleton global instance of your class. The object instance need not be different, or be special. Its sole purpose is to provide a pointer to itself. Since functions like "fetch()" return a reference to an object, and references are basically pointers in disguise, there is no immediate way to check the return value to see if an error occured. Even if the retrieval function has an output error indicator parameter [such as cursor_o<T>::fetch (count_t, int *)], the function must nevertheless return a reference to an object. One can't return NULL since a reference must refer to an object. In our example, class MyNum needs to include this line in its public area:
static const MyNum &bad_reference ();
The actual code definition can look like this:
const MyNum &MyNum::bad_reference ()
{
static MyNum global_ugh;
return global_ugh;
}
This approach is not recommended, as creating any global variables
in C++ is generally full of pitfalls. A better approach:
const MyNum &MyNum::bad_reference ()
{
static MyNum *badref = NULL;
if (badref == NULL)
{
badref = new badref;
if (badref == NULL)
{
std::cout << "ouch! can't new a \"MyNum\"!!\n";
exit(1);
}
}
return *badref;
}
You would use this by comparing the address of the object retrieved
(or returned from a non-fetch type function) to the address of the
"bad reference" - eg, compare pointers, like so:
const MyNum &ref_num = cunum.fetch();
const MyNum &ref_bad = MyNum::bad_reference();
if (&ref_num == &ref_bad)
{
// the fetch failed; probably because there was
// no match in the container (object not found)
}
note. binary trees are expected to join the Z Directory containers soon. in regard to the list of classes, the following classes names are simple aliases:
vlist_o - alist_o vordlist_o - aordlist_o vordset_o - aordset_o vset_o - aset_oFor example, a "vlist" object is actually a "alist" object. The actual definitions for these names are as follows:
#define vlist_o alist_o #define vordlist_o aordlist_o #define vordset_o aordset_o #define vset_o aset_owarnings.
Unfortunately, simple built-in types cannot be the recipients of containers. You cannot do this:
aset_o<int> my_intbox;Because the member function bad_reference() is required. Hence, Z Directory containers are resticted to holding class objects. This can be resolved by building "shells" around the simple types (int, long int, float, double, etc.). We have chosen not to do this, as the vast majority of the time it seems that the containers are used on objects.