Terris is a software engineer for Sagent Technology Inc. and can be contacted at terris@rahul.net.
Understanding relationships between objects is crucial to the success of any object-oriented software project. Relationships express real-world facts about objects without delving into computer terminology. For example, "companies" and "employees" can be related by the statement "an employee works for a company." Programmers have a much better chance of implementing a design correctly if relationships are documented in a clear and concise manner, free of any implementation details.
Relationships are known as "associations" in the Object Modeling Technique (OMT). Associations that relate two classes are known as "binary associations." Three, four, and even more classes can participate in associations. However, binary associations are the easiest to conceptualize, and they tend to be the most common. Associations have additional semantics--multiplicity, bidirectionality, properties, and association objects. (For more on associations, see Object-Oriented Modeling and Design, by James Rumbaugh et al., Prentice Hall, 1991.)
Associations can express one-to-one, one-to-many, and many-to-many relationships between classes; this is known as "multiplicity." Consider a simple one-to-one relationship (like Figure 1) between a company and its board of directors, where the board has performed its duties for a particular duration. A company and a board of directors participate in a simple association called "has," as in "a company has a board of directors." In this example, a path exists from a particular company to its board of directors and from the board of directors to the company. This type of association is called "bidirectional" since both participants can locate each other.
"Properties" describe aspects of the association. Without the association, properties are meaningless. In the aforementioned example, "duration" is an association property--it describes the amount of time that the board has performed its duties.
Associations can be modeled and implemented as separate objects. An association "object" in this example would contain a duration field, a pointer to a company object, and another pointer to a board of directors object.
Associations allow projects to leverage the power of various classes without intermixing their implementations and creating unplanned dependencies. Associations thus promote modularity. Instead of building one monolithic class that does everything under the sun, classes can enlist other classes to store specific information and carry out specific tasks.
The degree of effort required to implement associations depends on the target language. SQL, for example, requires a properly prepared join between tables. In C++, programmers typically implement associations using pointers.
A pointer-based implementation of Figure 1 might look like Example 1. There is a flaw in this implementation, however. Although a board object can locate its company, the company object cannot locate its board. This is a common oversight. The fact may well be that the existing code base does not need to find a board of directors object given a company object. In many cases, this is just a coincidence and is not a true reflection of the project's needs. Some programmers take the point of view "this will get us by--we can add the other pointer later when we need it." However, adding the pointer later means that the class implementation will change, and depending on the code base, client code may need to be changed. You should not allow existing code to bias class implementations. Large systems should implement associations correctly up front; otherwise, the hasty decision to implement half of the association may result in extra effort later.
In a one-to-one association, both objects must point to each other. Pointers do not enforce this constraint. At run time, this rule is easy to circumvent, and doing so can lead to code with hidden bugs. Pointer management is even more important in one-to-many associations.
Dangling pointers can crop up easily at run time. Pointers can point to deleted objects. Sometimes, pointers should be NULL when they aren't (these bugs are difficult to track down).Properties should be shared by both the forward and backward pointers in an association.
Some methodologies include support for "unidirectional" relationships, which map directly to pointers in C++. However, if your design includes bidirectional associations, C++ programmers will face challenges. The extra effort required to fully implement associations must be justified, so implementers should use their best judgment. In short, don't do it unless you really have to.
In this article, I'll present a design for implementing binary associations. The design consists of both OMT object-model and dynamic-model diagrams. I'll then implement the design in C++ (using templates to promote code reuse) and provide examples that use it. All of the code associated with this article is available electronically (see "Availability," page 3) and at ftp.rahul.net, in the pub/terris directory. The source code is freely distributable.
I tried to create a design that would do the following:
Another approach is described in chapter 15 of Object-Oriented Analysis and Design by Rumbaugh et al. Private methods, such as add_item() and remove_ item(), are defined on the classes that participate in an association. These functions maintain the backward and forward pointers. However, code reuse is not optimal and the chapter glosses over the details.
The approach I propose is illustrated in Figure 2 through Figure 5. Figure 2 and Figure 3 illustrate the object models, while Figure 4 and Figure 5 show the dynamic models. Table1 describes the classes and methods of the association objects ASToOne, ASToOneProp, ASToMany, and ASToManyProp. DetachMe() is called on destruction to minimize "dangling pointers."
Notice that the ASToOneBase and ASToManyBase classes are indirectly associated. ASToOneBase has a one-to-zero-or-one relationship with ASAssn, and ASToManyBase has a one-to-many relationship with ASAssn. This means that:
Figure 4 shows the behavior for the one-to-one case. First, the object (call it "A") starts in the "unattached" state. Association objects are linked by sending one of the objects an Attach event. Sending the object an Attach event has two results: First, B is sent an iAttach event; then, A points to B. This ensures that the two objects point to each other.
When A receives a DetachMe event, B is sent an iDetach message. This ensures that A and B are no longer linked.
Finally, consider the case where A is attached to B, and A receives another Attach event. Since A is a one-to-one association object, A's left-hand side (LHS) object cannot be linked to more than one object. So, A sends B an iDetach message.
The one-to-many dynamic model (Figure 5) is similar to Figure 4. The Attach and Detach events have the same "message forwarding" behavior. Attach sends an iAttach event and Detach sends an iDetach event.
In the following discussion, I'll use the terms "left-hand-side" (LHS) and "right-hand-side" (RHS) to identify the objects in an association. The left-hand-side is the point of reference; there is only one object on the left-hand-side of an association. The right-hand-side of the association is what the left-hand-side object "sees" as it "looks out" through the association, as if it were a sailor looking through a periscope. In a one-to-many relationship, the left-hand-side object sees many objects through the periscope. In a one-to-one relationship, the left-hand-side sees only one object.
Also note that I'll actually be implementing pseudoassociation objects, because one association object in this design only tells half of the story; two pseudoassociation objects are needed to express one association. In other words, I use the term "association object" when I mean "pseudoassociation object."
In Figure 1, both sides of the association are implemented with ASToOneProp data members. Figure 6 is an instance diagram of the participants. The Corporation class has its own ASToOneProp object that contains:
Note that there is only one instance that holds the association properties. This ensures consistency and may conserve memory.
One-to-zero-or-one relationships are fairly easy to implement using the template classes. Two template classes exist for this purpose, ASToOne and ASToOneProp. ASToOne accepts two parameters, which are the classes that are involved in the association. ASToOneProp accepts an additional parameter, which is the class that contains the association properties; see Listing One. Listing Two links a company to a board of directors. By default, the properties object is deleted when the link is broken. This can be overridden.
A board can locate its company using board.CompanyBoardAssn.GetRhsObject() and a company can locate its board using company.CompanyBoardAssn.GetRhsObject(). The properties for the association can be located starting from the company object using company.CompanyBoardAssn.GetProperties().m_duration and also starting from the board of directors object using board.CompanyBoardAssn.GetProperties().m_duration.
Notice that the Attach() method accepts an ASAssn object. The code that calls Attach() accesses a data member in board. Clearly, this violates encapsulation. All other association implementations have this encapsulation problem. Some object-oriented practitioners even argue against associations entirely because of the encapsulation problem. Creating association object "getters" on company and board is a trivial task, but this is not a complete solution. The objects are tightly bound by a member name in either case.
Other proposed solutions refer only to entire objects, as in Link( objectA, objectB ), so they don't need to access data members; however, this violates one of our design goals, which is to allow one class to participate in many associations with other classes.
The encapsulation problem is not as detrimental as it seems. First, associations can be implemented without adding data members to a class, because ASAssn objects can be declared anywhere in a program. The following section shows how. However, this approach carries with it the problem of cataloging association objects and finding them when you need them.
Secondly, subclassing can be used to isolate classes. First, a stand-alone class is built, free from any associations. Then, a subclass is created that has association objects as data members. Any class that is reusable without a particular association should be implemented in this manner. Listing Three demonstrates this approach.
Instead of embedding data members in the Company and BoardOfDirectors classes, association objects can be declared as local or global variables; see Example 3(a). Example 3(b) declares local variables for the company and board objects, while Example 3(c) declares an association object for the company called company_link. Finally, Example 3(d) declares an association object for the board called board_link. The company and board are then linked using Example 3(e).
Is this approach best, or should data members be used? I'm not recommending one method or the other. Both schemes are valid and have their own strengths and weaknesses.
Consider the simple one-to-many relationship between a car and its accessories in Figure 7. The "car" side of the implementation uses an association of type ASToManyProp, and the "accessory" side of the implementation uses an object of type ASToOneProp. In Figure 8, the Car object has its own ASToManyProp object that contains:
Implementing one-to-many associations requires more work than implementing one-to-one associations. First, list and iterator classes must be implemented. The list class inherits from ASListAdapter and the iterator class inherits from ASIteratorAdapter. These are abstract template classes. Adapters define an interface. They have no implementation details. Adapter interfaces are typically implemented by forwarding messages to other objects. See Design Patterns: Elements of Reusable Object-Oriented Software, by Erich Gamma et al., Addison-Wesley 1995.
Lists contain different types of items, depending on whether the association has properties. In the ASToMany case, the list contains ASAssn objects. In the ASToManyProp case, the list contains ASAssnPropTuple objects. Each ASAssnPropTuple (Figure 3) object contains a pointer to an ASAssn object and a pointer to an association properties object. The same list and iterator implementations can store both types of objects.
The sample code (available electronically) implements two classes, ListTempl and IteratorTempl. Listing Four is an example of the car and accessory classes. In Example 4(a), one car is declared along with three accessories. The car and accessories are then linked together in Example 4(b). Given a car object, Example 4(c) steps through all of its accessories. Iterate() is a factory method and returns a pointer to an object that must be deleted. The code acc1.m_installedIn.GetProperties().m_installationCost demonstrates how to access the properties, given an accessory object. Example 5 shows code that iterates through a list of associations depending upon whether associations have properties. Example 5(a) is code without properties, while 5(b) is code with properties. Note that the call to GetLhsObject is missing in Example 5(a).
Ordered associations can be implemented in two ways. First, the list itself can be ordered: Items can be traversed in the order that they were added to the list; or, a list can be built to sort items based on a key generated from RHS objects. Secondly, traversal order can be specified explicitly when items are attached; the iOrder parameter sent to the Attach() method can specify relative order.
Many-to-many relationships can also be implemented. The difference is that ASToMany (or ASToManyProp) objects appear as data members in both classes.
Implementing associations is not a trivial task. Programmers should take the time to design a standard approach for implementing associations; otherwise, individual programmers will code unique solutions that require their own debugging and documentation. In this article, I've described an approach for implementing associations via OMT diagrams and working C++ code. Combining OMT diagrams with real code can be an effective approach for documenting designs. Unfortunately, the design does not solve the encapsulation violation problem, but it does improve your chances of producing reusable code.
class Company
{
public:
string name;
};
class Board
{
public:
Company *pCorporation;
};
(a)
template <class parentClass, class linkClass>
class Association : public parentClass
{
linkClass *pLinkedObject;
public:
link( linkClass * );
getAssociatiedObject();
};
(b)
class CompanyBase
{
public:
string name;
};
(c)
class Company : public Association< CompanyBase,
BoardOfDirectors >
{
};
(a)
class Company
{
public:
string name;
};
class BoardOfDirectors
{
};
(b)
Company company;
BoardOfDirectors board;
(c)
ASToOneProp< Company,
BoardOfDirectors,
CompanyBoardProperties
> company_link(company);
(d)
ASToOneProp< BoardOfDirectors,
Company,
CompanyBoardProperties
>board_link(board);
(e)
company_link.Attach(board_link,
*new Properties(1));
(a)
Car car;
Accessory acc1;
Accessory acc2;
Accessory acc3;
(b)
car.m_hasAccessories.Attach( acc1.m_installedIn,
*new CarAccessoryProperties( 500 ) );
acc2.m_installedIn.Attach( car.m_hasAccessories,
*new CarAccessoryProperties( 1000 ) );
acc3.m_installedIn.Attach( car.m_hasAccessories,
*new CarAccessoryProperties( 7000 ) );
(c)
typedef AS_ITER_ADAPTER_PROP( Car, Accessory,
CarAccessoryProperties ) Iterator;
Iterator *pIterator =
car.m_hasAccessories.GetRhsObjects().Iterate();
for ( ; !pIterator -> AtEnd(); pIterator -> Next())
{
printf( "Cost %d\n",
pIterator->GetCurrent().GetProperties()
.m_installationCost
);
}
delete pIterator;
(a)
for ( ; !pIterator -> AtEnd(); pIterator -> Next())
{
printf( "Many link: %d\n",
pIterator->GetCurrent().i
);
}
(b)
for ( ; !pIterator -> AtEnd(); pIterator -> Next())
{
printf( "Many link: %d\n",
pIterator->GetCurrent().GetLhsObject().i
);
}
Method ASToOne/ASToOneProp ASToMany/ASToManyProp
Attach(object) Attaches the LHS object to Attaches the LHS object to
passed-in object. the passed-in object.
If either object is already
attached, the previous
attachments are revoked.
DetachMe() Detaches the LHS and RHS Detaches the LHS object
objects. from all of the objects
it is attached to.
Detach(object) <<Not present>> Detaches the LHS object
from a specific RHS
object.
GetLhsObject() Returns the LHS object. Returns the LHS object.
GetRhsObject() Returns the object that is <<Not present>>
associated with the
LHS object.
// Forward
class Company;
class BoardOfDirectors;
class CompanyBoardProperties;
class Company
{
public:
Company() : CompanyBoardAssn ( *this )
{
}
string name;
ASToOneProp< Company, BoardOfDirectors, CompanyBoardProperties >
CompanyBoardAssn;
};
class BoardOfDirectors
{
public:
BoardOfDirectors() : CompanyBoardAssn ( *this )
{}
ASToOneProp<BoardOfDirectors, Company, CompanyBoardProperties>
CompanyBoardAssn;
};
class CompanyBoardProperties
{
public:
CompanyBoardProperties( const long duration )
: m_duration( duration )
{}
long m_duration;
};
Company company;
BoardOfDirectors board;
// Attach the board and the company - the board has served for 5 months
company.CompanyBoardAssn.Attach( board.CompanyBoardAssn,
*new CompanyBoardProperties( 5 ) );
Class CompanyPure
{
public:
string name;
};
class BoardOfDirectorsPure
{
};
class Company : public CompanyPure
{
public:
Company() : CompanyBoardAssn ( *this )
{
}
ASToOneProp< Company, BoardOfDirectors, CompanyBoardProperties >
CompanyBoardAssn; // You can use any name you want
};
class BoardOfDirectors : public BoardOfDirectorsPure
{
public:
BoardOfDirectors() : CompanyBoardAssn ( *this )
{}
ASToOneProp<BoardOfDirectors, Company, CompanyBoardProperties>
CompanyBoardAssn; // You use any name you want
}
// Forward
class Car;
class Accessory;
class CarAccessoryProperties;
typedef AS_LIST_PROP( ListTempl,
Car, Accessory, CarAccessoryProperties ) List;
class Car
{
public:
Car() : m_hasAccessories( *this, *new List )
{
}
ASToManyProp< Car, Accessory, CarAccessoryProperties >
m_hasAccessories;
};
class Accessory
{
public:
Accessory() : m_installedIn( *this )
{}
ASToOneProp<Accessory, Car, CarAccessoryProperties> m_installedIn;
};
class CarAccessoryProperties
{
public:
CarAccessoryProperties( long cost )
: m_installationCost( cost )
{}
long m_installationCost;
};