Design Problem
===============
Would appreciate any help or suggestion on this design issue. I have
spent a great deal of time and effort for an elegant solution but it
seems I am not getting anywhere...
I have simplified my design problem to the following:
Consider the following classes:
Entity, Point, Polygon, Shape
Entity is the base class of Point, Polygon and Shape
Point is obvious
Polygon is defined using a set of points
Shape is a "set" of polygons BUT it will have one outside polygon and
zero or more inside polygons (ie. holes)
If I apply the composite pattern, I can make Entity to be the component
and Point will be a leaf. [There are other leaves in my original
design. Remember this is a simple example]
Then Polygon will be a composite and so will Shape.
The datastructure to use for the polygon could be an array or a list.
However, the datastructure to use for Shape is debatable. Unlike a
polygon where its points can happily reside side by side in an array or
a list, the polygons in a shape have a hierarchial relationship. The
outside polygon is the parent of the inside polygons. It therefore
seems reasonable to use a tree data structure in Shape to store the
polygons. GOF suggest using different data structure to store the
children of a composite and Shape seems to offer an object where a tree
would be appropriate.
If the above solution is OK so far then a number of questions arise.
1) the parent pointer for a composite pattern that is declared in the
Entity(component) can be set for points of a polygon when we add them
to a polygon. So each point of a polygon knows its parent(polygon). But
what about the parent of a polygon in a shape. Will this pointer point
to the Shape? Ie all the polygons of a shape (outside and inside) will
know their parent in the composite? Or should this pointer be used to
indicate the relationship between the polygons. In other words an
inside polygon(hole) will have its parent pointer set to the outside
polygon of the shape. Equally the parent pointer of the outside polygon
of a shape will point to the shape(its parent). Is the parent pointer
confined to the tree defined by the composite pattern and not the tree
inside a shape? Can we traverse up from a hole to the outside polygon
and then to the shape?
2) Should we have an abstract base class named say Composite for
Polygon and Shape and if so what will be its interface? The interface
for a Composite in GOF pattern suggests methods such as Add, Remove and
GetChild. Will these be enough for the Shape which has a tree data
structure? Or perhaps we will ahve two sets of interfaces one for
Polygon(list) and one for Shape(tree)?
3) It may be the case that a shape (an outside polygon and some inside
polygon(holes)) could have another shape inside one of the holes.
Should we create a new class for such a composite named NestedShape or
just use Shape. What will be the datastructure to store shape in
NestedShape? Tree again? I like to be able to ask a NestedShape to give
me all the holes for example...
4) If I do use a tree data structure for shape whats the best option?
Implement the tree or use a library? My tree has to be general (not
binary etc) and most libraries out there implement Binary trees, Avl,
etc. Does anyone know a good implementation of a general tree data
structure in c++?
5) Are there examples of the use of the Composite Pattern with tree
data structure used to store the children? All examples I have seen use
a list or an array.
Many thanks in advance for suggestions...
Merlin
