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.
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.
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:
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.
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.
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 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.
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.