Jump to content
  • Advertisement
Sign in to follow this  
tmarques4

Polymorphism with Linked Lists

This topic is 2594 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm testing an implementation which comprises a linked list of objects, each called Geometry, which stores information about vertices, UVcoordinates and normals in a GeometryData array.
The problem is that a geometry object can be either one of the primitive types: points, lines, triangles and quads so; in essence, the data structure is a list of objects which contain one of the aforementioned types, not following any precondition to linking objects.

The workaround implemented by me for this would have generic pointers and a type variable which specifies what type it is so proper cast is done.


struct point{...};
struct line{...};
struct triangle{...};
struct quad{...};
class Geometry
{
short type; //POINT, LINE, TRIANGLE OR QUAD
void *geometryData; //Pointer to structure of type specified.
Geometry *next;
}


Is this a good approach or is there a better one for working with polymorphism, maybe using templates?

Appreciate all help given.
Best regards!

Share this post


Link to post
Share on other sites
Advertisement
You could inherit all your geometric objects from a base struct

Struct Geometry
{}

Struct Point : public Geometriy
{}

Struct Line : public Geometry
{}

...

Then you can use Geometry as type for the linked list and store eg lines without having to cast anything.

Share this post


Link to post
Share on other sites
@The King2

I've just tried one simple code which doesn't seem to work.


#include <stdio.h>

struct Object
{
int object;
};

struct Point : public Object
{
int point;
};
struct Quad : public Object
{
int quad;
};
int main()
{
Object *hum = new Quad;
hum->quad = 10;
return 0;
}



However, if I try to access quad int by casting ((Quad *)hum)->quad, the above example works.
Is there anything wrong?

Share this post


Link to post
Share on other sites
hum is an Object*. When you access it, you can only access members which are defined in Object. If hum were to be a Quad*, your code would work as shown. However, that kind of defeats the purpose of polymorphism!


Unfortunately, the situation as we know it is too simple to actually offer a real solution. Typically when you use this sort of design, you will write virtual functions which are defined in Object and then implemented in Quad/etc. Those functions will do the actual work of processing the various types of geometry. However, it can be tricky to set things up that way, and it depends a lot on the sort of work your program is trying to do.

Moreover, there may be better alternatives, but they are only useful in certain situations. Without knowing a lot more about your program's purpose it's hard to suggest options.

Share this post


Link to post
Share on other sites

@The King2

I've just tried one simple code which doesn't seem to work.


#include <stdio.h>

struct Object
{
int object;
};

struct Point : public Object
{
int point;
};
struct Quad : public Object
{
int quad;
};
int main()
{
Object *hum = new Quad;
hum->quad = 10;
return 0;
}



However, if I try to access quad int by casting ((Quad *)hum)->quad, the above example works.
Is there anything wrong?


I don't think you really understand the concept of polymorphism. Object doesn't know anything about Quads.
You can only access the Object members though the Object pointer.

What do you want to do with all your different geometry types that they have in common?

Share this post


Link to post
Share on other sites
The above example is broken anyway, it's the canonical case of how inheritance is taught incorrectly.

Line, Point, Quad, etc. are all geometric shapes, but are not descendants. One possible definition is:
typedef std::vector<Point> GeometricShape;

bool is_triangle(GeometricShape s);
bool is_equilateral_triangle(GeometricShape s);
bool is_rectangle(...
Then, classify them based on how many points they contain and other properties. Which is exactly what the geometric definitions are.

Example of a problem: Take triangle with coordinates: (1,1)(1,1)(1,1) and another with (1,1),(2,1),(3,1).

Its class will say: "Triangle". But the first is a point and second is a line. And it's a degenerate triangle at best, if it's a triangle at all. The type system is ok, it actually says: this doesn't work.

And there's the problem of covariance: every square is a rectangle and a polygon, but not vice versa. So asking for type of (0,0)(0,1)(1,1)(1,0), would need to return (Square, Rectangle, Polygon, maybe_a_few_other_things), yet such typing systems only allow single type association.

A geometric shape is a composition of points with implied order. What shape they represent depends and is not statically typed, especially with such simple typing systems that C family languages offer, where type is unrelated to values. Even the most trivial examples quickly lead to exceptions, where a line is suddenly being called a triangle, just because.

Share this post


Link to post
Share on other sites

Line, Point, Quad, etc. are all geometric shapes, but are not descendants. One possible definition is:
typedef std::vector<Point> GeometricShape;

bool is_triangle(GeometricShape s);
bool is_equilateral_triangle(GeometricShape s);
bool is_rectangle(...


Then, classify them based on how many points they contain and other properties. Which is exactly what the geometric definitions are.


The problem is that a "GeometricShape" have other variants, mainly UVcoordinates and normals, so they differ from each other, so problem can't be solved just by adding a Point data type.

-------------------------------------------------------------------

@Apoch

The problem is fairly simple to understand but not so easy to implement.

The data structure is as follows.


struct point
{
float vertex[3];
}
struct line
{
float vertex[2][3];
}
struct triangle
{
float vertex[3][3];
float UVcoord[3][2];
float normal[3][3];
}
struct quad
{
float vertex[4][3];
float UVcoord[4][2];
float normal[4][3];
}


As you can see, points and lines differ from triangles and quads. Off course, vertex is common to all of them so a proper hierarchy can be designed but, it does not solve the problem of having a generic linked list, which is a linked list that can link to any of the geometry above.

What I basically want is a linked list like the following:

quad->point->point->triangle->quad->line->point->quad->NULL

Since The King2 proposition is not the proper one, the problem doesn't have anything to do with OOD, I may be wrong and, what I want to implement is a polymorphic linked list I suppose.

Share this post


Link to post
Share on other sites
The question isn't about what form the data takes. The question is, what do you do with the data? That really changes the best approach.

I guess what I'm getting at is, why do you want all of these different objects in a single linked list? What will that gain you that alternatives will not? What sort of processing are you doing on the list?

Share this post


Link to post
Share on other sites
If you can put enough methods in Object to make it a useful interface, polymorphism might work for you. Geometric figures might have a method to draw themselves in a window, they might be able to return a bounding box... Perhaps then you can have a linked list of your objects, but it needs to be the case that most of the code can handle objects just using the Object interface. The sample of code you posted where you tried to set hum->quad is an example of code that needs to know more than the Object interface.

I use polymorphism in very few places. I do it when I can have a factory function that returns a pointer to the base class and no other part of the code needs to know what exact type was returned. If I ever find the need to use dynamic_cast (which is what would allow you to get a more specific pointer from a pointer to Object), I reconsider my design, because the abstraction is not working.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!