Sign in to follow this  
Timkin

Abstract base class... or a better way?

Recommended Posts

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

Share this post


Link to post
Share on other sites
Why not use both?

class Base
{
virtual void DoStuff() =0;
};

template<typename T>
class Impl : public Base
{
void DoStuff()
{
// do stuff templated to T
}
};

// somewhere over the voxel rainbow....
Base* base = new Impl<PixelData>;
//or...
Base* base = new Impl<VoxelData>;



Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Template the Image class on what is stored inside of there. From the tone of the post it sounds as if you will know this at compile-time. I only use polymorphism for run-time dispatching, usually I can get by on compile-time dispatching for a great deal of things.

It sounds like template specialization will be useful for you. You may be able to get away with specializing only the functions that actually use Pixel/Voxel classes. If this isn't the case, then partially specialize the classes.

Share this post


Link to post
Share on other sites
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:

#include <iostream>

struct alien {

void draw() const {
std::cout << "alien\n";
}

};


struct window {

void draw() const {
std::cout << "window\n";
}

};

template< typename Entity >
void draw(const Entity& e) {
e.draw();
}


int main() {

alien a;

window h;

draw(h);

draw(a);

return 0;

}



inheritance:

#include <iostream>

struct entity {

virtual void draw() const = 0;
virtual ~entity() {}
};

struct alien : entity {

void draw() const {
std::cout << "alien\n";
}

};

struct window : entity {

void draw() const {
std::cout << "window\n";
}

};


void draw(const entity& e) {
e.draw();
}


int main() {

alien a;

window h;

draw(h);

draw(a);

return 0;

}

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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:


const typename PointType::component_type result = (Point1 - Point2).magnitude(); // hello, NRVO
return result;




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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Why not just code two plain separate classes?

Those classes should be relatively simple, and provide few functionalities... I would personally just code the two separately. Its not because they are somewhat similar in a way that they *have* to be united somehow. In this particular scenario, you don't really have a complex hierarchy where a pixel and a voxel belong to a common set of objects which belongs to another set of objects. You just have two partly similar classes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Xai
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.

You could use Alexandrescu's multimethods...

Share this post


Link to post
Share on other sites
Quote:
Original post by Max_Payne
Why not just code two plain separate classes?


Because then I would have to write overloaded methods of other classes that utilise pixels/voxels in computations. That's the whole point of templating... to save work down the track (somewhat).

Timkin

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Quote:
Original post by Max_Payne
Why not just code two plain separate classes?


Because then I would have to write overloaded methods of other classes that utilise pixels/voxels in computations. That's the whole point of templating... to save work down the track (somewhat).

Timkin


How much work have you saved so far :P ?

Share this post


Link to post
Share on other sites
Quote:
Original post by Max_Payne
How much work have you saved so far :P ?


By templating... quite a lot actually. Having to write two versions of every computational function (there are lots of them and they are LONG) would be a HUGE pain in the arse and a waste of time. Given the similarities of Pixels and Voxels, it takes little effort to hide the differences in a template class.

Anyway, I appreciate the point of view, I just don't agree that it's the correct way to go in this situation.

Cheers,

Timkin

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this