Jump to content

  • Log In with Google      Sign In   
  • Create Account


Polymorphism with Linked Lists


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 26 October 2011 - 01:08 PM

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!
Tiago.MWeb Developer - Aspiring CG Programmer

Sponsor:

#2 Juliean   GDNet+   -  Reputation: 2350

Like
0Likes
Like

Posted 26 October 2011 - 01:20 PM

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.

#3 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 26 October 2011 - 02:01 PM

@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?
Tiago.MWeb Developer - Aspiring CG Programmer

#4 ApochPiQ   Moderators   -  Reputation: 14623

Like
0Likes
Like

Posted 26 October 2011 - 03:11 PM

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.

#5 ChaosEngine   Crossbones+   -  Reputation: 2219

Like
0Likes
Like

Posted 26 October 2011 - 03:18 PM

@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?
if you think programming is like sex, you probably haven't done much of either.-------------- - capn_midnight

#6 Antheus   Members   -  Reputation: 2397

Like
2Likes
Like

Posted 26 October 2011 - 03:21 PM

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.

#7 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 26 October 2011 - 05:17 PM

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.
Tiago.MWeb Developer - Aspiring CG Programmer

#8 rip-off   Moderators   -  Reputation: 7964

Like
1Likes
Like

Posted 26 October 2011 - 05:26 PM

You don't have to use inheritance. Why not store them in four different containers?

#9 ApochPiQ   Moderators   -  Reputation: 14623

Like
2Likes
Like

Posted 26 October 2011 - 06:08 PM

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?

#10 Álvaro   Crossbones+   -  Reputation: 12383

Like
0Likes
Like

Posted 26 October 2011 - 07:19 PM

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.

#11 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 27 October 2011 - 01:14 PM

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.


All geometric shapes must be derived from a base class "Object", which will have only virtual functions that operates on the geometric shapes, just as you mentioned: Draw(), Rotate(), Translate() etc... This Object will describe a "protocol" that all those derived geometric shapes must follow. Is it a proper data structure for considering polymorphism? Or is it recommended to create separate linked list for those, I'm trying to avoid this since I was looking at a single volatile structure, in which I just have to add geometry without the need to be concerned about what they actually represent.
Tiago.MWeb Developer - Aspiring CG Programmer

#12 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 27 October 2011 - 01:22 PM

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?


Convenience I guess.

It's "easier" to handle a single data structure than having to handle multiple ones if you have a good implemented polymorphic structure. Polymorphism is not a must to implement the code but would be a nice approach.
Tiago.MWeb Developer - Aspiring CG Programmer

#13 FLeBlanc   Crossbones+   -  Reputation: 3085

Like
0Likes
Like

Posted 27 October 2011 - 01:40 PM

If it really were easier and more convenient, you wouldn't need this thread to help you figure it out. In the modern world of data-oriented architectures, where cache coherence and rapid batching of data are far more important than whatever meager convenience benefits polymorphism offers, I would think that this approach might be a step backward. Any time you have to hop out of a contiguous chunk of memory and follow a pointer off to somewhere else, you risk stepping out of cache unnecessarily. As clunky as interleaved, fixed-format vertices might be to work with, at least they offer the benefit of being very cacheable without virtualized interfaces or pointer indirections to access the individual components.

#14 ApochPiQ   Moderators   -  Reputation: 14623

Like
0Likes
Like

Posted 27 October 2011 - 01:53 PM

Convenience I guess.

It's "easier" to handle a single data structure than having to handle multiple ones if you have a good implemented polymorphic structure. Polymorphism is not a must to implement the code but would be a nice approach.




I'm honestly a little confused here. You sound comfortable enough with the idea of polymorphism to identify it as a useful solution for your current situation, but you're missing some of the most basic concepts behind how it works, as evidenced by the Object*-vs-Quad* confusion earlier.

I'm not sure exactly how to help at this point...?

#15 Madhed   Crossbones+   -  Reputation: 2648

Like
0Likes
Like

Posted 27 October 2011 - 07:00 PM

I think before being able to help you we need to know what exactly you want to do with this code. Is it for a render engine? A 3D modelling tool? Do you use Direct3D, OpenGL or even software rendering?
Generally I try to avoid polymorphism whenever possible. (Composition over inheritance) With such small structures virtual methods are better avoided as stated before. It is better to operate on a whole bunch of them at once.

When I started learning OOP I was, like many, under the impression that everything has to be a class and that inheritance was the best way to extend classes.
Doing relational database design and normalizing DB models has really helped me think more in terms of data and algorithms vs. single object manipulation.

#16 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 31 October 2011 - 05:58 PM

@ApochPiQ

I'm not sure exactly how to help at this point...?


Well, I have worked out a solution based on alvaro's reply that does what I wanted in the first place. That helped me a lot to understand polymorphism and I think I have a clearer idea now as I did one week ago. If someone could give me a tip or two as to how right or wrong this implementation is I'd appreciate it.

#include <stdio.h>

class generic
{
public:
	virtual void imprime(){printf("this is generic...\n");}
};

class point : public generic
{
public:
	char *nome;
	point(){nome = "point";}
	void imprime(){printf("this is %s...\n", nome);}
};

class line : public generic
{
public:
	char *nome;
	line(){nome = "line";}
	void imprime(){printf("this is %s...\n", nome);}
};

class triangle : public generic
{
public:
	char *nome;
	triangle(){nome = "triangle";}
	void imprime(){printf("this is %s...\n", nome);}
};

class quad : public generic
{
public:
	char *nome;
	quad(){nome = "quad";}
	void imprime(){printf("this is %s...\n", nome);}
};

int main()
{
	void *hum[5];
	hum[0] = new generic();
	hum[1] = new point();
	hum[2] = new line();
	hum[3] = new triangle();
	hum[4] = new quad();

	((generic *)hum[0])->imprime();
	((generic *)hum[1])->imprime();
	((generic *)hum[2])->imprime();
	((generic *)hum[3])->imprime();
	((generic *)hum[4])->imprime();
}

Here I just create and set a bunch of void pointers to different data types and can test what objects they represent by the printf function, each one of the "imprime" at main have a different output on the terminal and, even though they are different types, the program doesn't need to know about this.

Now, think of those "imprime" functions as being a "render" function. This render function is part of generic class and is virtual, each geometry that derives from this generic class will have this "render" function behaving differently according to each geometry's "private variables", like render needing to set normals for tris and quads and not for points and lines, etc...

This way I can have a linked list of different geometries like I stated before and, when I need to render them all I just need to pass through each node and cast render() recursively:

void Render(void *linkedList)
{
  ((generic *)linkedList)->render();
  Render((((generic *)linkedList)->next()));
}

Also, one other reason for me to want to have a single linked list with different data types is that I want a history of recently created objects, not mattering their types, and I want to switch between objects on the fly, forward or backward. Linked list is a good alternative. I think if I can design such a structure there are lots of benefits.
Tiago.MWeb Developer - Aspiring CG Programmer

#17 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 31 October 2011 - 06:17 PM

I think before being able to help you we need to know what exactly you want to do with this code. Is it for a render engine? A 3D modelling tool? Do you use Direct3D, OpenGL or even software rendering?
Generally I try to avoid polymorphism whenever possible. (Composition over inheritance) With such small structures virtual methods are better avoided as stated before. It is better to operate on a whole bunch of them at once.

When I started learning OOP I was, like many, under the impression that everything has to be a class and that inheritance was the best way to extend classes.
Doing relational database design and normalizing DB models has really helped me think more in terms of data and algorithms vs. single object manipulation.


I haven't thought about graphics engines yet, I'm just implementing a data structure for 3d models. It should not depend on the engine used, being rather a generic structure.

Polymorphism works when you have many classes that share the same methods, as stated by alvaro, and is exactly what happens in my case, not?

Classes help organizing code and having a clearer view of what the program does and how it's going to do it. I don't think inheritance is the best way to extend classes though, every problem has a unique solution.

I must admit I don't handle relational databases, aside from SGBD's. I appreciate and will take your advice.
Tiago.MWeb Developer - Aspiring CG Programmer

#18 ApochPiQ   Moderators   -  Reputation: 14623

Like
0Likes
Like

Posted 31 October 2011 - 06:19 PM

There is no need for using a void* here. Just use a generic* directly and skip all the icky casting ;-)

#19 TMarques   Members   -  Reputation: 189

Like
0Likes
Like

Posted 02 November 2011 - 08:48 AM

Everything sorted them.
Thanks everyone very much for the help!
Tiago.MWeb Developer - Aspiring CG Programmer

#20 Codarki   Members   -  Reputation: 462

Like
0Likes
Like

Posted 03 November 2011 - 06:50 AM

For other future readers of this thread:

Usually your primitives for the geometry are of the same type, all triangles, all lines, etc.. You don't want to make the primitive to be a polymorphic, but rather the collection of them. The solution is seen in post #2, but renaming the derived classes as PointGeometry and LineGeometry would make the case more clear, as is seen from the misunderstanding in post #3.

If you really want a single geometry to have different types of primitives, just add a collection for each type.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS