11.2 COLLECTION

Purpose:

An ordered or unordered COLLECTION occurs when one object type (TOP) contains a whole set of objects of another type (BOT).

This organization can also be used as a RING with an encapsulated entry point. If the ring is singly linked it is a single collection(SINGLE_COLLECT), if it is doubly linked it is a double collection (DOUBLE_COLLECT).

Note the difference between a COLLECTION and a TREE. A TREE is composed of objects that all have the same type; a COLLECTION works with two different object types. Also, a COLLECTION requires only about 50% of the memory required by a tree because the child and parent pointers on the bottom objects are missing.

You can also look at the COLLECTION as being a TRIANGLE (see Chap.11.3) where the parent pointer is missing, or as a combination of singly-linked RINGS (Chap.11.1) with a single LINK (Chap. 11.6).

ADD and DELETE:

These commands add/delete objects to/from the bottom level. In order to make a COLLECTION empty, delete all its bottom objects. del() can be used while traversing the set with the iterator.

Order of objects:

The objects at the bottom level are handled as a ring. If objects ABCD have been added to a COLLECTION, the iterator returns them in the reverse order: DCBA. The child pointer of the top object works as the start pointer of the RING. set() allows you to reset this pointer. Therefore, for example, the following sequence results in the bottom objects being ordered in the same sequence as they were loaded:

ZZ_HYPER_SINGLE_COLLECT(myCol,ParType,ChiType);
ParType *p; ChiType *c1,*c2;
...
myCol.add(p,c1);
myCol.set(p,c1);
...
myCol.add(p,c2);
myCol.set(p,c2);
...

sort() sorts all the children using a user supplied compare function similar to the one needed for qsort().

Moving around the COLLECTION:

The iterator traverses the bottom elements of the COLLECTION.

myCol_iterator it(p);
while(c1= ++it){
...
}
fwd() returns the next object in the bottom ring;
child() returns the starting bottom object.

Merging or Splitting Collections

Because all the children of a collection form a ring, collections can be merged or split just like a ring (see the illustration in Chap.11.1).

The merge command must be given two children and one parent object. If the two children are in the same collection, the operation results in splitting the collection in two. If the two children are in different collections, the operation merges them into one.

id.merge(c,c,par) results in no action. In order to extract a single object into a new COLLECTION, proceed as for the RING.

In the case of merging, the given parent must be the parent of the second child. In the case of splitting, an empty parent must be given to receive the second part of the set.

ZZ_HYPER_SINGLE_COLLECT(myCol,ParType,ChiType);
ParType *p1,*p2; 
ChiType *c1,*c2 // given two children
    ....
// p1 and p2 are parents of two collections
// c1 is child of p1, c2 is child of p2
if(p1==p2){ // case of splitting
    p2=new ParType;
    c1=myCol.merge(c1,c2,p2);
    // p1 and p2 now hold the two collections
}
else { // case of merging, p2 must be parent of c2
    c1=myCol.merge(c1,c2,p2);
    // p1 contains the result, p2 is empty
}

Syntax:

ZZ_HYPER_SINGLE_COLLECT(id,TOP,BOT); Declares a singly-linked collection.
void id.add(TOP *parent,BOT *newChild); Adds newChild to the given parent.
void id.del(TOP *parent,BOT *oldChild); Deletes oldChild from this parent.
BOT* id.fwd(BOT *child); Returns next child (fwd=FORWARD) under the same parent.
BOT* id.child(TOP *parent); Returns the first child under this parent.
void id.set(TOP *parent,BOT *newFirstChild); Sets already existing child as the new first child of this parent

Warning: Using an improper parent will cause an un-detectable error.

void id.merge(BOT *child1,BOT *child2,TOP *parent); If the two children are from the same collection, this splits it into two parts, and parent will be the second collection.
If the two children are from different collections, the collections will merge.
void id.switchParents(TOP *parent1,TOP *parent2); Exchanges parents of two collections. When one collection is empty, this effectively moves a collection under a new parent.
void id.sort(int (*sortFun)(const void*,const void*),TOP *parent); Sorts the elements of the collection, using sortFun() to compare the objects.
TOP *parent; BOT *obj;
id_iterator it(parent);
while(obj= ++it){ ... }		 This loop traverses all the elements of the collection. The value of obj should not be changed from within the loop. Upon exit from the loop, obj=NULL.
it.start(parent); Restarts the same loop.

Available only for the DOUBLE_COLLECT:

ZZ_HYPER_DOUBLE_COLLECT(id,TOP,BOT); Declares a doubly-linked collection.
BOT* id.bwd(BOT *child); For a given child returns the previous (bwd=BACKWARD) child in the ring that forms the collection.
void id.ins(BOT *child,BOT *newChild); Inserts the new child before the given child.
TOP *parent; BOT *obj;
id_iterator it(parent);
while(obj=it--){ ... }		 This loop is just like the one above, except that it traverses the data in reverse order.
it.start(parent); Restarts the same loop

Most new C++ compilers for DOS issue warnings when using the while() statement in this situation. You can use the iterator in a different form which is not as easy to read, but it does not generate any warnings:

id_iterator it(parent);
for(child= ++it; child; child= ++it){ ... };

Examples:

Netlist in electrical circuits, storing pins by block and by signal net (test0i.c).

 

Previous Section 11.1 RING Next Section: 11.3 AGGREGATION