Reusable Associations

The best way to explain this problem is with a real-world example. We chose the computer-aided design of silicon chips (VLSI circuits) because it involves complex data organization with only a few classes. A fully functional computer can be on a single chip, and the data to store and traverse are huge—millions of objects. Figure 1 explains the engineering concepts of building these chips.

If you use standard class libraries, the initial code may look like Listing One, where ChipLib is a library storing both complete chips and partially designed blocks. ChipLib also keeps frequently needed basic geometries such as contacts. Associations among classes in Listing One are represented by collections, pointers, or by a combination of both—one relation may possibly require members in several classes. For example, the relation between Block and Terminal requires the two members shown in red.

[Click image to view at full size]

Figure 1: A silicon chip is designed from blocks, which are hierarchically composed from smaller blocks and so on. This is a conceptual diagram, not a real circuit. Pins are points to which the outside signal nets may be attached. A set of pins connected together inside a block is a logical entity called "terminal" (shown as a dashed line). A terminal often has only one pin. The nets are formed by wires (rectangles assigned to one of the layers; here blue or red) and by contacts (geometries that connect several layers). The two parts of net1 are connected through one of the BLK blocks.

class ChipLib {     
  Collection<Master> masters;
  Master *chip;    
  Collection<Geometry> geometries;
};
class Master {    
  String name;
  int xWidth,yWidth; 
  <font color="00CC33">Collection<Block> blocks;</font> 
  <font color="#FF00CC">Collection<Net> nets; </font>   
};
class Block {
  String name;
  int x,y;             
  int orientation;     
  <font color="#00CC33">Master *master;</font>      
  <font color="#FF0000">Collection<Terminal> termsByBlock;</font> 
};
class Net {
  String name;
  Collection<Connector> connectors;   
  <font color="#0099FF">Collection<Terminal> termsByNet;</font>  
  Collection<Pin> pins; 
  <font color="#FF00CC">Master *master;</font>           
};
class Terminal {
  <font color="#FF0000">Block *block;</font>   
  <font color="#0099FF">Net *net;</font>       
  Net *masterNet; 
};
 ... and so on

The problem with this code is that the associations are buried inside the class definitions; and when reading the code, the purpose of these members is obscured. Worse, in spite of the formal similarity to how associations are implemented, the green members in classes Master and Block do not belong to the same relation. Member Block::master points to the master of the block, not to the master in which the block is used. This style of implementing associations, in some situations, prohibits derivation of the UML class diagram from the code automatically—additional information such as variable names, written documentation, or comments would have to be included.

Today, you typically start with a UML class diagram describing classes and the associations among them (Figure 2). UML class diagrams are popular because they provide a network representation of a problem, which is difficult to understand without a picture, and because associations used in the UML diagram are more powerful than collections in existing class libraries. UML works with a number of different views, each using a different style of diagram. When we say "UML diagram" in this article, we refer to the most popular of these—the class diagram.

[Click image to view at full size]

Figure 2: UML class diagram of the data supporting the hierarchical VLSI chip design. Compare with Listing One where each association is implemented in a different color with the exception of green (blocks and master here).

If we could expand existing libraries such as STL or Java Collections to include associations, it would improve the existing software design methodology in several ways:

• It would force us to think in more general terms—in associations instead of collections and individual references/pointers.
• MDD code generators would be simpler because there would be a one-to-one match between the associations in the diagram and those in the code.
• For the same reason, UML diagram generators would be easy to code and always safe to use.

Collections deal with only two classes where one of them controls the other, while associations involve two or more cooperating classes that may know (and access) each other. Adding a collection requires an addition to the controlling class only but adding an association may require additions to several participating classes (Listing Two). The Java implementation would be identical, except for references instead of pointers.

// LIBRARY OF ASSOCIATIONS:
 template<class Parent,class Child> class <font color="#FF00CC">ParentAggregate</font> {
     Collection<Child> children;
 };
  template<class Parent,class Child> class <font color="#FF00CC">ChildAggregate</font> {
     Parent *parent;
 };
 template<class Source,class Link,class Target> class <font color="#0099FF">SourceXtoX</font> {
     Collection<Link> links;
 };
 template< class Source,class Link,class Target > class <font color="#0099FF">LinkXtoX</font> {
     Source *source;
     Target *target;
 };
 template<class Source,class Link,class Target> class <font color="#0099FF">TargetXtoX</font> {
     Collection<Link> links;
 };
 // APPLICATION CODE
 class Master {
     <font color="#FF00CC">ParentAggregate</font><Master,Net> <font color="#FF0000">nets</font>;
     ...
 };
 class Net {
     <font color="#FF00CC">ChildAggregate</font><Master,Net> <font color="#FF0000">nets</font>;
     <font color="#0099FF">TargetXtoX</font><Block,Terminal,Net> <font color="#FF0000">blockNets</font>;
     ...
 };
 class Block {
     <font color="#0099FF">SourceXtoX</font><Block,Terminal,Net> <font color="#FF0000">blockNets</font>;
     ...
 };
 class Terminal {
     <font color="#0099FF">LinkXtoX</font><Block,Terminal,Net> <font color="#FF0000">blockNets</font>;
     ...
 };

We find it logical and convenient to use the association names, such as nets or blockNets, for the inserted member. When an application class participates in several associations (such as Net in Listing Two), several members are inserted, one for each association.

Once popular, pointer-based data structures have been neglected and are completely missing from existing class libraries. Like associations, intrusive data structures (IDS) require coordinated insertion of members into participating classes. For example, collection masters in Listing One may be implemented as an intrusive linked list:

class ChipLib {
    Master *masters;
    ...
};
class Master {
    Master *next;
    ...
};    

Besides being more efficient than array-based collections (faster to traverse, smaller footprint), when such lists are implemented with rings instead of NULL ending lists, they provide effective runtime protection of data integrity. As demonstrated by the IN_CODE library (www.codefarms.com/products.htm), one-to-one, one-to-many, and many-to-many associations can be implemented in the intrusive style. On the other hand, all the IDS the authors know implement one association or another. Perhaps there are some IDS that are not associations, but for a library of generic associations, we should use a mechanism that would support any IDS as well.

Structural design patterns are data structures that combine associations with inheritance. In Figure 2, classes Connector, Geometry, Wire, and Contact form a pattern Composite that allows complex hierarchical designs from several different types.

This pattern is different from the commonly used association called "composition aggregate," which is simply a specific implementation of OneToMany. An example of a composition aggregate is the relation between Master and Block. Each block belongs to only one master and ceases to exist if its master is destroyed.