Design/Inheritance Question

[bfeist]

I'm working on a maze generation program which works with MazeCell
objects describing the geometry and topology of individual cells of a
maze -- how they connect and how to draw them. MazeCell itself is an
abstract class, which will have concrete classes of IsoscelesTriangle,
Hexagon, RightTriangle, and Square (for instance). Now, it turns out
that there is a subclass of RightTriangle which is topologically
equivalent to IsoscelesTriangle, meaning that the "neighbors" of each
cell are identical: if the triangle points upward, its neighbors are to
the left, to the right, and down in the same way for both of them; this
is not true for other subclasses of right triangle.

I'd like to reuse code for the RightTriangle subclass and
IsoscelesTriangle subclasses, but it's not clear to me what the best
way of doing so is. Certainly neither IS-A the other. I suppose I
could stick the method in MazeCell itself, or in an intermediate new
class called TriangleCell which extends to both RightTriangle and
IsoscelesTriangle, but since the method really isn't general for all
subclasses in the sub-hierarchy that doesn't seem appropriate.

The cleanest alternative might be to separate out classes defining
geometry (how it's drawn) from topology (how they're connected), but
that seems complicated.

Any suggestions?

Thanks,
Bruce Feist

 

[Robert Klemme]

I'm working on a maze generation program which works with MazeCell
objects describing the geometry and topology of individual cells of a
maze -- how they connect and how to draw them. MazeCell itself is an
abstract class, which will have concrete classes of IsoscelesTriangle,
Hexagon, RightTriangle, and Square (for instance). Now, it turns out
that there is a subclass of RightTriangle which is topologically
equivalent to IsoscelesTriangle, meaning that the "neighbors" of each
cell are identical: if the triangle points upward, its neighbors are to
the left, to the right, and down in the same way for both of them; this
is not true for other subclasses of right triangle.

I'd like to reuse code for the RightTriangle subclass and
IsoscelesTriangle subclasses, but it's not clear to me what the best
way of doing so is. Certainly neither IS-A the other. I suppose I
could stick the method in MazeCell itself, or in an intermediate new
class called TriangleCell which extends to both RightTriangle and
IsoscelesTriangle, but since the method really isn't general for all
subclasses in the sub-hierarchy that doesn't seem appropriate.

Huh? Didn't you just say that TriangleCell just has sub classes
RightTriangle and IsoscelesTriangle? If you want to create other sub
classes of TriangleCell later you can refactor and create a base class
for RightTriangle and IsoscelesTriangle only.

The cleanest alternative might be to separate out classes defining
geometry (how it's drawn) from topology (how they're connected), but
that seems complicated.

It depends on how complex your whole app is. If your classes reach a
certain degree of complexity (i.e. LOC) it is certainly worthwhile to
think about refactoring aspects (geometry, topology) out of them.

Kind regards

robert

 

[Bruce Feist]

bfeist wrote:

Huh? Didn't you just say that TriangleCell just has sub classes
RightTriangle and IsoscelesTriangle? If you want to create other sub
classes of TriangleCell later you can refactor and create a base class
for RightTriangle and IsoscelesTriangle only.

Only one subclass of RightTriangle is topologically equivalent to
IsoscelesTriangle. There are at least two others which do not.

Here are some ASCII pictures of some of the grids involved, with numbers
indicating the row number for the first triangle in each row:

IsoscelesTriangle:
____________
\0 /\ /\ /\
\/1_\/__\/__\
/\2 /\ /\ /
/3_\/__\/__\/

RightTriangle1 (topology like IsoscelesTriangle)
___________
|1 /| /| /|
| / | / | / |
|/_2|/__|/__|
|\ 3|\ |\ |
| \ | \ | \ |
|4_\|__\|__\|

RightTriangle2 (different topology -- note that the triangle marked '3'
has three neighbors in the above two examples, but only two in the one
below)
___________
|1 /| /| /|
| / | / | / |
|/_2|/__|/__|
|3 /| /| /|
| / | / | / |
|/_4|/__|/__|

RightTriangle3 (also a different topology)
___________
|1 /|\ | /|
| / | \ | / |
|/_2|__\|/__|
|\ 3| /|\ |
| \ | / | \ |
|4_\|/__|__\|

It depends on how complex your whole app is. If your classes reach a
certain degree of complexity (i.e. LOC)

What's LOC?

it is certainly worthwhile to
think about refactoring aspects (geometry, topology) out of them.

Thanks for your response!

Bruce Feist

 

[Chris Uppal]

I'd like to reuse code for the RightTriangle subclass and
IsoscelesTriangle subclasses, but it's not clear to me what the best
way of doing so is. Certainly neither IS-A the other. I suppose I
could stick the method in MazeCell itself, or in an intermediate new
class called TriangleCell which extends to both RightTriangle and
IsoscelesTriangle, but since the method really isn't general for all
subclasses in the sub-hierarchy that doesn't seem appropriate.

First an observation: OO isn't about reducing code duplication, it's about
maximising clarity and comprehensibility. So it's not only OK, it's actually
/better/, to have duplicate code in two places if there is no underlying
logical reason why it /must/ be the same in both. I.e. if it wouldn't
necessarily be an error to change one without changing the other, then
duplication is preferable to a misleading attempt to reuse the "shared" code.
Of course if it /would/ be an error, then the duplication is bad for precisely
that reason.

You triangles sound as if they might be one of those cases.

If not (and it may not be) then it suggests that your hierarchy is focussed on
the wrong aspects of a cell. Presumably, for a maze, the /most/ important fact
is its topology -- not the geometrical shape -- so I'd expect the class
hierarchy to follow that. And then geometry /might/ be expressed in the same
hierarchy (by further subclassing), but I suspect that factoring it out into a
separate object which knows how to handle representational issues would be
better. As you say:

The cleanest alternative might be to separate out classes defining
geometry (how it's drawn) from topology (how they're connected), but
that seems complicated.

And, indeed, it might /be/ complicated. But, on the other hand, it might
simplify things quite a lot. There's a lot to be said for just trying out
different design alternatives, and see how the code fits together. You may
like the results, if not then just throw the experiment away...

BTW, on the subject of complication: it isn't too clear to me that you actually
need different classes for each kind of cell. You /may/ need it (I don't know
what your code does), but it might be simpler if things like number-of-doors,
number-of-walls, etc, were just fields with different values in different
instances of Cell. The key here is to ask whether the differently-shaped cells
/behave/ differently -- if not then a class hierarchy is probably
overcomplicating things.

Another possibility, suggested by the diagrams in your later post, is that the
topology and cell shape are both aspects of the maze itself, rather than of the
cells that make it up. So the Maze "knows" what shape all its cells are (and
maybe that shape is expressed as a Shape object and/or a Grid object), whereas
each Cell only "knows" its containing Maze, its location in that Maze (which it
doesn't interpret itself), and what Cells it is directly connected to.

-- chris

 

[Bruce Feist]

First an observation: OO isn't about reducing code duplication, it's about
maximising clarity and comprehensibility. So it's not only OK, it's actually
/better/, to have duplicate code in two places if there is no underlying
logical reason why it /must/ be the same in both.

I agree. In this case, it must be the same because the topology for
IsoscelesTriangle and the RightTriangle subclass are the same. By
reusing the code, I'm achieving better stability for the final program
and avoiding future bugs (which I'd include with your clarity and
comprehensibility goals as the point of OO).

it suggests that your hierarchy is focussed on
the wrong aspects of a cell. Presumably, for a maze, the /most/ important fact
is its topology -- not the geometrical shape -- so I'd expect the class
hierarchy to follow that.

That makes sense, although I'm frankly not sure how to do that.
Geometric categorization is easy; I have convenient names and concepts
for most of the shapes involved. Topological categorization is more
difficult for me, because each topology for the cell seems independent,
and I don't have language to describe them -- I don't want to end up
with obscure names that I cannot mentally associate with the meanings of
the classes. I suppose I could manufacture meaningful names somehow out
of the connectivity information... tricky.

And then geometry /might/ be expressed in the same
hierarchy (by further subclassing), but I suspect that factoring it out into a
separate object which knows how to handle representational issues would be
better.

I think that I reluctantly agree with both of us. That's the "right"
way to do it, at least if I stick with this approach.

see how the code fits together. You may
like the results, if not then just throw the experiment away...

BTW, on the subject of complication: it isn't too clear to me that you actually
need different classes for each kind of cell. You /may/ need it (I don't know
what your code does), but it might be simpler if things like number-of-doors,
number-of-walls, etc, were just fields with different values in different
instances of Cell. The key here is to ask whether the differently-shaped cells
/behave/ differently -- if not then a class hierarchy is probably
overcomplicating things.

That's attractive. My main background is with database analysis, and in
fact I'm biased towards data-driven, parametric approaches rather than
implementing functionality through subclasses. In this case, I think
it's initially easier to use subclasses, but in the long term the
analysis needed to come up with a solution such as you describe might be
worth it. Certainly encoding the shapes of the cells is straightforward
enough; I don't plan to use cells more complex than polygons (although
that could change). I'd need to represent several variations of cell;
for instance, for right triangles, there are four different cell
variations that can show up:
___ __
|\ /| | / \ |
|_\ /_| |/ \|

And I'd need a way of representing which variation is at each cell in
the maze.

Another possibility, suggested by the diagrams in your later post, is that the
topology and cell shape are both aspects of the maze itself, rather than of the
cells that make it up. So the Maze "knows" what shape all its cells are (and
maybe that shape is expressed as a Shape object and/or a Grid object), whereas
each Cell only "knows" its containing Maze, its location in that Maze (which it
doesn't interpret itself), and what Cells it is directly connected to.

That's basically the way the program works now, with most of the logic
in the Maze class. MazeCell deals primarily with sides, directions, and
neighbors of a cell. There are only five methods which are polymorphed
in subclasses:
public int nSides()
public int nDirections()
public int sideToDirection(int side)
public MazeCell directionToNeighbor(int direction)
public void drawSide (Graphics g, Dimension d, int side, boolean visible);

Thank you for a most insightful and thought-provoking reply. You've
given me much to think about.

Bruce Feist

 

[Patricia Shanahan]

Chris Uppal wrote: ....

That makes sense, although I'm frankly not sure how to do that.
Geometric categorization is easy; I have convenient names and concepts
for most of the shapes involved. Topological categorization is more
difficult for me, because each topology for the cell seems independent,
and I don't have language to describe them -- I don't want to end up
with obscure names that I cannot mentally associate with the meanings of
the classes. I suppose I could manufacture meaningful names somehow out
of the connectivity information... tricky.

....

Here's a possible compromise. Define an interface Topology with methods
that return things like lists of neighbors.

Add to the abstract base class for the cells a method:

public abstract Topology getTopology();

For any cell type where there is a single topology that applies, make
the cell class implement Topology, and return itself:

public Topology getTopology(){
return this;
}

For a cell type where you want to use a separate Topology, for example
one shared with some cases of another cell type, have a non-trivial
getTopology method:

public Topology getTopology(){
if(conditions for special case){
return new SomeTopologyClass(parameters);
}else{
return this;
}
}

Within the cell hierarchy, you can vary the extent to which Topology is
merged with cell type or separate, without affecting any other code.

Patricia

 

[Bruce Feist]

Here's a possible compromise. Define an interface Topology with methods
that return things like lists of neighbors.

For a cell type where you want to use a separate Topology, for example
one shared with some cases of another cell type, have a non-trivial
getTopology method:

Whee! More to think about... this sounds like a good possibility too.
Thank you!

Bruce Feist