Okay, here's the design problem (this is related to the other design problem I posted on recently): I currently want to support two different classes in my class library that should have a common interface design. The two classes are Pixel and Voxel. The only real difference between them is the dimensionality of the coordinate data they store, which will affect computations that process pixels or voxels and the return type of the coordinate data, unless I return a pointer to the coordinate array. I had originally chosen to use a template class, but I was wondering if it would be better to use an abstract base class to define the interface and then write the rest of the library using polymorphism and base class pointers? In particular, pixels or voxels will be stored in a container class attribute of a Image class and reference by that class. I was thinking that polymorphism would be a good way to handle them in the Image class rather than using template parameters and typedef typename designs... Thoughts, comments, suggestions? Thanks, Timkin

From a quick read it seems like Pixel and Voxel computation process might be rather frequent. It almost seem like calling process in a loop is a common operation in your case.

As such, I advise AGAINST an abstract polymorphic base class. Instead, I would go for a compile time policy driven template class, with two policies, Pixel and Voxel, and a template class Interface, passing Pixel and Voxel as template policy parameter.

This is a classic problem .. where the classes are the same in 1 of 2 of their primary attributes (the functional unit they represent), but are different in the other (the family of technology they belong to).

Much like the SAT questions where:
Point2D is to Square
as
Point3D is to ? (answer - Cube)

and you want to retain ALL of the possible usefull elements of the abstraction ...

but the problem is, in C+ (and all normal compiled OO langauges), the "interface" of a base class, ie, it's "signature" includes a specification of the contract it provides to the client in terms of BOTH the data it expects and receives, and the function it fullfills.

You cannot easily make such frameworks be embodied in base classes and polymorphics, because although a Point2D and Point3D could both derive from "Point" or "IPoint" ... almost no usefull work could be done on just "IPoint"s .. IE, you could not write function that took 2 Points and computed their distance, cause the function is different for 2D and 3D points.

So naturally, since the exact types differ, then you want to use templates ... or so it seems. Following that route you will find that in many cases you can write an interface in a usefull way, just like before, except now you can often even write the interfaces to functions generically - such as:

// to ignore additional complexity, the code below assumes all frameworks prefer "double" as the scalar unit of choice.
typedef double ScalarType;
template <typename PointType>
ScalarType Distance(PointType point1, PointType point2);

but as you quickly see, you have correctly imbodied 1 part of the abstraction, but still you cannot implement it once and reuse that implementation. You will need to write both point version as specializations.

BUT you do get something ... once written, client code has an identical interface that functions with either point type.

Functionality wise, this is no different than just implementing:
ScalarType Distance(Point2D point1, Point2D point2);
ScalarType Distance(Point3D point1, Point3D point2);

but it does retain the fact that both specializations are implementations of the same generic function, where the "overload" version does not really embody that idea anywhere.

Through a combination of using base interfaces for the purely functional elements

IE, use a base interface for "public virtual void Draw()" type functiosn, and generics for things which differ based on families of related data ... you can build fairly complex heirarchies, fairly well.

Xai: I appreciate the reply, but I'm not quite seeing your point. Are you saying 'avoid polymorphism' for this sort of problem and 'use templates' or are you saying 'avoid both' and write overloaded functions?

janus: That doesn't seem to me to be a particularly good use of polymorphism, since you could simply access DoStuff() through a pointer to type Impl.

dot: yes, there are occasions when Pixels or Voxels are referenced, but only through a container interface (so the container stores one type of data, Pixel or Voxel, depending on the dimensionality of the data stored in a netcdf file). Why do you say that using a lot of loop computations on polymorphic objects suggests NOT using polymorphism?


Thanks,

Timkin

Quote:Original post by Timkin
Xai: I appreciate the reply, but I'm not quite seeing your point. Are you saying 'avoid polymorphism' for this sort of problem and 'use templates' or are you saying 'avoid both' and write overloaded functions?

janus: That doesn't seem to me to be a particularly good use of polymorphism, since you could simply access DoStuff() through a pointer to type Impl.

dot: yes, there are occasions when Pixels or Voxels are referenced, but only through a container interface (so the container stores one type of data, Pixel or Voxel, depending on the dimensionality of the data stored in a netcdf file). Why do you say that using a lot of loop computations on polymorphic objects suggests NOT using polymorphism?


Thanks,

Timkin

Its not avoiding polymorphism its just another form of polymorphism there is more than one form polymorphism, using templates/generics is a form of parametric polymorphism where as class hierarchies is a form sub-type polymorphism.

templates gives you static polymorphism because its bound at compile time.

class hierarchies gives you dynamic polymorphism bound at run-time.

You can achieve the same thing in both but you have various trade-offs between the two. Here is an example of doing the same thing using both forms of polymorphism:

templates:


inheritance:

Quote:Original post by antareus
From the tone of the post it sounds as if you will know this at compile-time.

No. The use of Pixel or Voxel depends on the data read from a file, so it is run-time information. Obviously I could provide compile time functionality for the possible types in a template design... I was thinking though that using inheritance and polymorphism might make extensibility easier, particularly since I want to give users of the library the ability to provide certain functions of their own (to replace some inbuilt computational functions). Thus, being able to define their own element types (that conform to the interface) would also be nice.

For those that didn't read my thread last week, I'm writing an class library that provides data structures for image segmentation problems. There are three fundamental classes used for any given problem:

1) Voxel/Pixel class: basic data type. Contains a coordinate and a vector of intensity values (for multi-spectral segmentation);
2) Image class: an aggregated container class holding Voxels/Pixels that also provides computational functions for obtaining information about the set of Voxels/Pixels: e.g., computing the value of some cost function; and,
3) Tree class: performs segmentation of initial Image into a heirarchy of images, according to one of several available algorithms (or a user supplemented algorithm).

There will also (eventually) be functionality to display the segmentation in various formats, but I'm not at the design phase for that yet.

Thanks for the help. Given the above information, if anyone has any more ideas, please let me know.

Thanks,

Timkin

Quote:Original post by Xai
So naturally, since the exact types differ, then you want to use templates ... or so it seems. Following that route you will find that in many cases you can write an interface in a usefull way, just like before, except now you can often even write the interfaces to functions generically - such as:

// to ignore additional complexity, the code below assumes all frameworks prefer "double" as the scalar unit of choice.
typedef double ScalarType;
template <typename PointType>
ScalarType Distance(PointType point1, PointType point2);

but as you quickly see, you have correctly imbodied 1 part of the abstraction, but still you cannot implement it once and reuse that implementation. You will need to write both point version as specializations.

BUT you do get something ... once written, client code has an identical interface that functions with either point type.

Functionality wise, this is no different than just implementing:
ScalarType Distance(Point2D point1, Point2D point2);
ScalarType Distance(Point3D point1, Point3D point2);

but it does retain the fact that both specializations are implementations of the same generic function, where the "overload" version does not really embody that idea anywhere.

You do not need to specialize the distance function for points of different dimensions (nor any other algorithm based around the general abstraction of points, vectors, or matrices when properly metaprogrammed). All core point operations can simply and efficiently be implemented as metafunctions operating off of the compile time dimension information from integral template parameters, such as subtraction of points, addition of vectors, magnitude of vectors, dot product, even the more complex cross product, etc. without any theoretical extra runtime cost. For instance, in this case, one quick and simple implementation (though not necessarily the fastest) for distance between two points is to implement it as:



(where magnitude is a metaprogrammed member function that computes the magnitude of a vector and the nested component_type typedef is the component type of the points).

If you want to make a fully modular system based on number of dimensions and find yourself having to specialize for every single type which varies by number of dimensions, then you are missing a relationship between the concepts. There is nothing stopping you from making a point or vector class templated with both component type and number of dimensions that allows you to create a point with any number of components that works with properly coded generic algorithms. In fact, this is exactly what I personally do and I have yet to come across a situation where a truely generic algorithm that should work with points, vectors, or matrices of a general number of dimensions couldn't be implemented with one series of metafunctions in C++.

So, to Timkin -- if you know templating pretty well, by all means, use it instead of polymorphism as long as it subtracts nothing from your application's requirements (IE as long as the type only varies at compile time, you have no reason to use runtime polymorpism so use templating). The only time you really should use polymorphism is if you know that the type is going to vary at runtime, or if you are dealing with interfaces whose object implementation can change between versions but must be interfaced with the same way across DLL boundaries, and even then, you should most-likely use a combination, or even avoid polymorphism in the object altogether and just box a reference to the point in an object which has a virtual interface when you need to so that it can be passed safely between modules without forcing all points to suffer from vtable pointer bloat and initialization costs (which can be very considerable considering the polymorphism is ultimately unecessary in most cases and you will most-likely have a lot of pixels and/or voxels in whatever you're doing).

So again, prefer strictly templating. If you absolutely MUST have runtime polymorpism between pixels and voxels (which I'm currently doubting, but it is possible), then first look to see if you can just box a reference to the object for those specific situations. Finally, if you consistently need runtime polymorphism (which is probably very unlikely, but again possible), then go for an integrated runtime polymorphism approach. This, again, should be a last resort, and even then I'd recommend having the type templated for the sake of modularity and genericity.

Edit: you posted your reply as I wrote this -- remember that even though the use of pixels and voxels may vary from input information at runtime, this doesn't mean that those classes have to be runtime polymorphic. Instead, only your absolute outermost abstraction has to be. Try to abstract away as much runtime polymorpism as much as possible to the highest level encapsulating objects you can. Use of templating internally instead of a runtime solution will not only produce generally faster code, but will also make it easier for you to write as it forces errors to compile-time rather than runtime IE if you were working with points, two templated points subtracted is much simpler than subtracting two abstract types via a base pointer, since conceptually the latter can be either a pixel or voxel or some other type. If you use completely templating at that level of abstraction, this type of mistake would be caught at compile time and would save you a lot of trouble, whereas a polymorphic solution will push those errors to when the program is run.

Thanks for the responses everyone... I think the general suggestion is to stick with my original design - that of template classes. I'll go with that advice.

Thanks,

Timkin