11.3 AGGREGATION (TRIANGLE)

Purpose:

A triangle represents one level of a general hierarchy, with one object type at the top (TOP), and another object type at the bottom (BOT).

Note the difference between a TRIANGLE and a TREE. A TREE is composed of objects that all have the same type; a TRIANGLE works with two different object types. Also, a TRIANGLE requires about 30% less memory than a TREE because the child pointer on the bottom objects is absent.

ADD and DELETE:

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

Order of objects:

The objects on the bottom level are handled as a ring. If objects ABCD have been added to a TRIANGLE, the iterator returns them in reverse order: DCBA. The child pointer of the top object works as the start pointer of the RING. Function 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:

...
id.add(par,obj1);
id.set(obj1);
...
id.add(par,obj2);
id.set(obj2);
...

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

Moving around the TRIANGLE:

The iterator traverses the bottom elements of the TRIANGLE.

id_iterator it(parent);
while(obj= ++it){
...
};

fwd() returns the next object in the bottom ring;
par() returns the parent object for a given bottom object;
child() returns the starting child object.

Merging or Splitting Triangles

Because all the children of a triangle form a ring, triangles 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 triangle, the operation results in splitting the triangle in two. If the two children are in different triangles, 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 TRIANGLE, proceed as shown for the RING.

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

ZZ_HYPER_SINGLE_TRIANGLE (myTriangle,parType,chiType);
parType *p1,*p2;
chiType *c1,*c2;
    ....
p1=myTriangle.par(c1);
p2=myTriangle.par(c2); 
if(p1==p2){ // case of splitting
    p2=new parType;
    myTriangle.merge(c1,c2,p2);
    // p1 and p2 now hold the two triangles
}
else { // case of merging
    myTriangle.merge(c1,c2,p2);
    // p1 contains the result, p2 is empty
}

Syntax:

ZZ_HYPER_SINGLE_TRIANGLE(id,TOP,BOT);
ZZ_HYPER_SINGLE_AGGREGATE(id,TOP,BOT);		 Both statements declare identical organizations (both names are acceptable).
void id.add(TOP *parent,BOT *newChild); Adds new child under the given parent.
void id.del(BOT *childToRemove); Removes the given child from the aggregation.
BOT* id.fwd(BOT *child); Returns the next child under the same aggregation (fwd=FORWARD)
TOP* id.par(BOT *obj); Returns the parent of the given object.
BOT* id.child(TOP *obj); Returns the first child of the given object.
void id.set(newFirstChild); Sets the given object as the first child under the same aggregation.
void id.merge(BOT *child1,BOT *child2,TOP *parent); If the two children are in the same aggregation, the aggregation will split, and parent will be the parent of the new section, which will contain child2. If the two children are in different aggregations, the two aggregations will merge, and the parent of child1 will be its parent.
void id.switchParents(TOP *parent1,TOP *parent2); Exchanges parents of two aggregates. If one aggregate is empty, it effectively moves an aggregate under a new parent.
void id.sort(int (*sortFun)(const void*,const void*),TOP *parent); Will sort children under the given parent, using the given function to compare them.
TOP *parent; BOT *obj;
id_iterator it(parent); while(obj= ++it){ ... };		 Will traverse all children of the given parent. obj must not be modified from within the loop, but objects can be deleted using id.del(). You can break from the loop as usual.

Comment: id.sort() does not work for the ZORTECH compiler.

Examples:

  1. Netlist in electrical circuits, storing pins by block and by signal net (test0a.c, test2.c).
  2. Storing a list of towns under the state to which they belong (test 14a.c).
  3. Loading Pins by Blocks and by Nets into netlist, without reversing their order (test0a.c).

 

Previous Section 11.2 COLLECTION Next Section 11.4 TREE