4.7 Dynamic Aggregation

The distinguishing feature of a dynamic aggregation is that at least some of the objects encapsulated within such an aggregation are dynamically created (via the new operator) at run-time. Dynamic aggregations are needed when the type of the encapsulated subobjects is known when the class is defined but the number of such objects is not. At run-time the dynamic aggregation must allocate and manage new subobjects.

The subobjects in a dynamic aggregation are not automatically destructed when the object is destructed because the subobjects are dynamically allocated. The responsibility for properly destructing the subobjects, thus preventing memory leaks, lies with the programmer. Failure to manage the dynamic subobjects properly is a common source of errors; usually these errors are difficult to identify due to the dynamic nature of the subobjects.

An abstraction that must be represented as a dynamic aggregation is a closed polygon-like shape that has an arbitrary number of sides. To illustrate the mechanics of a dynamic aggregation, a class for a polygon-like shape will be defined and implemented. This class will allow the vertices of the shape to be defined dynamically at run-time. The class must maintain a list of vertices whose length is not known in advance. When required to draw itself on a canvas, the class is responsible for drawing lines between each successive pair of points, treating the last vertex and the first vertex as adjacent. Thus, if there are n vertices, n lines will be drawn: the first line is drawn from vertex 0 to vertex 1, the second line from vertex 1 to vertex 2, and so on, with the last line being drawn from the vertex n-1 to vertex 0.

The interface of the PolyShape class is shown below.

PolyShape Class Interface
class PolyShape
        LocationNode *head;
        LocationNode *tail;
        int currentX, currentY;
        int length;
        PolyShape(int x, int y); 
        void Up   (int n);       
        void Down (int n);
        void Left (int n);
        void Right(int n);
        void Mark();
        void Draw(Canvas& canvas);

A PolyShape object is constructed with the Location, the x and y coordinates, of its first vertex. These coordinates are used to initialize the current location of the PolyShape, represented by the state variables currentX and currentY. The other parts of the constructor will be explained later. The Up, Down, Left, and Right methods change the current location by the amount of the method's parameter. The name of the method suggests which coordinate of the current location is affected and in what manner. For example, if the current location is (100, 100) then the method Up(10) changes the Y coordinate so that the current location becomes (100, 90), a location "up" in the sense that it is closer to the top of the canvas area. Similarly, the call Right(20) would change the current location (100, 100) to become (120, 100), a location 20 pixels toward the right edge of the canvas. The implementation of these methods is shown below. The Mark() method adds the current location to the linked list of Locations maintained by the PolyShape object. The Draw method draws the PolyShape on the canvas. The implementation of the Mark () and Draw () methods is discussed further below.

Linked List Animation

This interactive animation illustrates the operation of the dynamic aggregation used in the PolyShape class. At the top of the display is a set of four arrowed controls surrounding the coordinates of the "current" point (the logical cursor) maintained by a PolyShape object. The arrowed controls move the current point in the direction indicated by the arrows. The button labelled "Mark" simulates the action of the PolyShape's mark method. When the "Mark" button is pressed a new point is added to the internal dynamic aggregation maintained by the PolyShape. The coordinates of each point in the dynamic aggregation are stored in a Location object. The Location objects are linked together using paired LocationNode objects. While the animation only allows a small number of list elements, the actual list in the PolyShape object is unbounded.


Basic Methods of the PolyShape Class
PolyShape::PolyShape (int x, int y) 
{ currentX = x; currentY = y;
  Location *start = new Location(x,y);
  head = tail = new LocationNode(start);
  length = 1; } 
void PolyShape::Up(int n) 
{ currentY = currentY - n; } 
void PolyShape::Down(int n) 
{ currentY = currentY + n; } 
void PolyShape::Left(int n) 
{ currentX = currentX - n; } 
void PolyShape::Right(int n) 
{ currentX = currentX + n; } 

A significant issue for the designer of the PolyShape class is how to maintain the ordered list giving the Locations of its vertices. Because the number of vertices is unknown (at least unknown at design-time and compile-time), some form of dynamic aggregation is used.

The first solution to implementing the PolyShape data structure uses a linked-list technique. The Location class provides a convenient means to maintain an (x,y) coordinate pair but it does not provide a capability for Location objects to be members of a list. While the Location class could be changed to add the necessary data and methods to provide a linked-list capability, this approach is not followed. Three reasons argue against modifying the Location class in this way:

  • There is nothing inherent in the abstration of a Location to suggest that it is a member of a list of Locations. Thus, modifying the Location class would weaken the abstraction on which the class is based.
  • The additional methods and data are costs incurred by all Location objects regardless of whether they are needed. Thus, modifying the Location class lessens the efficiency of Location objects in many situations. In the worst case, applications that do not use a list of Locations receive no benefit from the list mechanisms added to the Location class.
  • This approach may not always be possible. In some situations, the objects to put on a list are instances of classes that cannot be changed. This occurs when the class is a library class provided by a vendor and the source code is not available to be changed.

Instead of modifying the Location class to add linked-list features, another approach that allows lists of Location objects, but does not modify the Location class, will be used.

The linked-list technique used in the PolyShape class depends on an auxiliary class, the LocationNode class. The LocationNode class provides the ability to form a linked list of Location objects. The relationship between a PolyShape object, the LocationNode objects, and the Location objects is shown in the figure below. As illustrated, each LocationNode object contains a pointer (contents) that identifies the Location object with which the LocationNode is paired. The LocationNode also contains a pointer (next) that identifies the next LocationNode (if any) in the list of LocationNodes. The two pointers in each LocationNode provide the abilities to form a list, by using the next pointer, and to represent a Location object, by using the contents pointer.

Relationships Among PolyShape, LocationNode, and Location Objects

As illustrated in the figure and shown in the PolyShape class definition, a PolyShape object maintains two pointers, head and tail, that indicate the first and last elements in the linked list of LocationNodes.

The code for the LocationNode class is given below. Notice that no changes are needed in the Location class in order to implement the LocationNode class. Thus, the three problems noted earlier are avoided by the design of the LocationNode class.

LocationNode Class
class LocationNode
   LocationNode *next;
   Location *location;
    LocationNode(Location *loc);
        LocationNode* Next();
        void Next(LocationNode* nxt);
        Location& Contents();
LocationNode::LocationNode(Location *loc)
{ location = loc;
  next = (LocationNode*)0; }
LocationNode* LocationNode::Next()
{ return next; }
void LocationNode::Next(LocationNode* nxt)
{ next = nxt; }
Location& LocationNode::Contents()
{ return *location; }
{ delete location; }

Notice that the destructor in the LocationNode class deletes the Location object to which the LocationNode points with its contents pointer. Also notice that no action is taken regarding the next pointer in the LocationNode.

The Mark and Draw methods of the PolyShape class operate on the linked list of LocationNodes as shown in the code below. The Mark method creates a new Location object using the current location of the PolyShape and creates a new LocationNode object whose contents points to the Location object just created, then adds the just-created LocationNode to the tail of the linked list of LocationNodes.

The Draw method uses the DrawLine method of the Canvas class to draw a sequence of lines. Each line is drawn between a pair of consecutive Location objects extracted from the linked list of LocationNodes. The code for the Mark and Draw methods is shown below.

Code for the Mark and Draw Methods
void PolyShape::Mark()
{ Location *newPoint   = new Location(currentX, currentY);
  LocationNode *newNode = new LocationNode(newPoint);
  tail = newNode;
  length = length + 1;
void PolyShape::Draw(Canvas& canvas)
{ if (length == 1) return;
  LocationNode *node, *next;
  node = head;
  for(int i=0; i<length-1; i++)
  { next = node->Next();
    node = next;

The destructor in a dynamic aggregation plays a key role in ensuring the proper reclamation of the subobjects dynamically created during the lifetime of the containing (aggregating) object. The destructor for a PolyShape object must destruct all of the dynamically created LocationNode and Location objects that are part of the linked list of the PolyShape object. The destructor for the PolyShape class is shown below.

PolyShape Class Destructor
{ LocationNode *next = head;
  while (next)
  { LocationNode *node = next->Next();
    delete next;
    next = node;

The PolyShape destructor performs a list traversal, destructing each LocationNode in sequence. Recall that, when destructed, a LocationNode object will destruct the Location object to which it points. Thus, the PolyShape directly destructs all LocationNode objects and indirectly causes the destruction of all Location objects.



  1. Change the destructors of the LocationNode and the PolyShape classes to what is shown below. Explain why this code correctly destructs all LocationNode and Location objects in the PolyShape.
    { delete contents;
      delete next;
    { delete head;
  2. Use the linked list technique developed in this section to define and implement a linked list of Message objects without changing the Message class. A partial specification of the MessageList class interface is given below. The MessageList::Draw method should invoke the Message::Draw method in each Message object on its list. Similarly for the MessageList::Clear method. The MessageList destructor should not destruct the Message objects but should destruct all dynamic structures created by the MessageList class.
    class MessageList
       void Add(Message& msg);
       void Draw();
       void Clear();


©1998 Prentice-Hall, Inc.
A Simon & Schuster Company
Upper Saddle River, New Jersey 07458

Legal Statement