Triple linked lists

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

colin - 06 Jan 2008 15:42 GMT

Hi,
I have 3 object of interest wich are objects in 3d space,
surface,wire,point.

they are all interconnected,
and they all contain lists of objects they are connected to,
eg each surface will have a list of wires, points, and adjacent surfaces.
same for the others.

building the lists so they all the references are two way is fairly easy to
start with.
ie if a point references a surface then that surface also references that
point,
however it becomes rather difficult to do complicated operations like
combining 1 point onto another wire etc.
particularly dealing with combining overlapping wires,
and making sure all the adjacent objects all reference eachother as
necessary.

I seem to occasionaly find the lists are out of sync,
theres lots of code, and its quite complicated it seems to have got into a
bit of a mess,
so im thinking I need to examine easier ways of doing this and re write it,
are there any good references ?

I also have a seperate class for each list to implement functions like
FindOrAdd,AddUnique etc ...
I had difficulty trying to combine into one generic class, as I was wanting
to constrain the type to one of 3 classes but I couldnt :s
the search term can be several different types too, again I can only
constrain to one clas with generics functions wich makes it hard to do
again are there any good references for making versatile lists like this ?

Im still relativly new to c# and I have a feeling theres prob some good
stuff that would make this easy wich im not aware of.

thanks
Colin =^.^=

Reply to this Message

Peter Duniho - 07 Jan 2008 02:00 GMT

> [...]
> I seem to occasionaly find the lists are out of sync,
[quoted text clipped - 4 lines]
> it,
> are there any good references ?

I don't know about "easy", but...

I think I mentioned, early on, when you were describing your difficulty
with respect to the UI for editing these data, that the data structures
you were describing seemed unwieldy. If not, I meant to...sorry if I
neglected that.

Basically, you seem to have created an overly complex design. Of
particular concern to me would be the repetition of information. There
obviously is some, because your concern now is that information that
should be identical in multiple places is not.

Assuming your 3D data is typical, then it seems to me that what you've
really got are a bunch of vertices that define a bunch of surfaces, where
the edges of each surface is a "wire". If so, it seems to me that what
you really want to be storing is a collection of the surfaces, with the
vertices of each surface being references into a collection of vertices.
The surfaces themselves would not contain any vertex information
directly...it would all be relative to the collection of vertices, and
multiple surfaces could reference any given vertex. The "wires" would be
inherent in the information presented by each surface.

If you really want a collection of wires as well, I'd define each surface
by the wires at the edges, and each wire by the vertices. An advantage of
this, other than being more similar to what you've apparently already got,
is that just as you can share vertices for surfaces or wires, you can
share wires for surfaces (which would not be as easy if the wires were
simply implied by each surface).

In either case, the collections aren't peers, but rather a definite
hierarchy of composition. Vertices being the smallest building block,
composing wires, which in turn compose surfaces. Or just have the
vertices compose surfaces, with the wires being an inherent characteristic
of each surface.

Either way, there is no duplicated information and thus no need to worry
about any of the information being in sync.

> [...]
> Im still relativly new to c# and I have a feeling theres prob some good
> stuff that would make this easy wich im not aware of.

C# will make it easier to write the code for a given design. But you have
to start with a good design in the first place. I wouldn't say that
having multiple data structures that all represent the same basic
information, just in different ways, is all that good a design.

As an added benefit, simpler designs generally are actually _less_ work.
You have to type less, there's less code interactions to deal with, and of
course less debugging. :)

Pete

Reply to this Message

colin - 07 Jan 2008 11:51 GMT

>> [...]
>> I seem to occasionaly find the lists are out of sync,
[quoted text clipped - 11 lines]
> you were describing seemed unwieldy. If not, I meant to...sorry if I
> neglected that.

yes you did mention it or at least I remember someone did.

> Basically, you seem to have created an overly complex design. Of
> particular concern to me would be the repetition of information. There
> obviously is some, because your concern now is that information that
> should be identical in multiple places is not.

Yes I sort of agree and that aspect was in my mind
when I was thinking of re writing it.

however Im sure youl apreciate I dont just write complicated code for the
fun of it,
but it does seem complicated so im trying to evaluate if its unecessary,
so I at need to look at ways of simplifieg not only the implmentation,
but also the design.

> Assuming your 3D data is typical, then it seems to me that what you've
> really got are a bunch of vertices that define a bunch of surfaces, where
[quoted text clipped - 5 lines]
> multiple surfaces could reference any given vertex. The "wires" would be
> inherent in the information presented by each surface.

yes the surfaces start of as just a collection of vertices stored in a file.
and the same will be used to save the information.

> If you really want a collection of wires as well, I'd define each surface
> by the wires at the edges, and each wire by the vertices. An advantage of
> this, other than being more similar to what you've apparently already got,
> is that just as you can share vertices for surfaces or wires, you can
> share wires for surfaces (which would not be as easy if the wires were
> simply implied by each surface).

the wires are a difficult thing to use to describe a surface,
as all the surfaces are clockwise wich means the direction of the wires is
oposite for
adjacent surfaces. the vertices describe the surface well,
infact I tend to use the vertex list to generate a list of lines when im
testing for
PointInsideSurface() rather than use the list of wires as the direction
matters in the calculations.

> In either case, the collections aren't peers, but rather a definite
> hierarchy of composition. Vertices being the smallest building block,
[quoted text clipped - 17 lines]
> You have to type less, there's less code interactions to deal with, and of
> course less debugging. :)

Yes I agree with what you said, and if it was just a simple case of
displaying surfaces
that would be fine.

the list of wires and vertices are there becuase its an editor and the user
can do operations
on any of the visible aspects such as surfaces, wires, points.

if the user moves a point it needs to move the same point on all the
surfaces,
this wil hapen anyway if the surfaces store a reference into a list of
points.
but it needs to make sure all the surfaces connected to that point stay
coplaner,
or take some action.
it would be possible to go through all the surfaces to see wich one contains
that point
instead of duplicating information but it is more time consuming,

the same for moving a wire and when a surface is moved its quite complicated
to
make sure all the points move so that all surfaces are still coplaner but
ive got it to work.

there are restraints to keep surfaces or any object moving together as a set
or to only allow movement in
the plane of the surface etc.. wires can be moved to keep each end within
the plane of the surface at each end etc.

theres lots of checking too wich alone takes several minutes,
If i were to search the list of surfaces every time I looked at a point it
might take hours.
A typical input data set is 100mb of text consiting of 8 digit floats for
each vertex.

Ive also recently added another list wich stores the plane of the line just
to speed things up a bit,
as this was hitting very high in the profiler, and reduced the run time
considerably.
however this is self contained and cuases no problems.

it does give me an idea to regenerate the other lists from scratch rather
than try and manipulate them
when the data is changed wich is cuasing the problems of being in sync.
thus the extra lists would become realy only a speed up cache.

however one tricky problem is when it is found one of the points on
one surface is sitting on a line of another surface but is not included in
that surface.
this not only makes the CSG think it has a hole, but cuases problems when
moving stuff.
this is what was giving me headache with the lists when I tried to join them
up.

however I think ive fixed the remaining issues with that.

doubly linked lists although a bit complicated work well with a handfull of
routines needed to manipulate them.
actually mine is more of a many to many database type scenario rather than a
doubly linked list.

However Im so used to C++ and I keep thinking I could do it this way but
then find I cant,
Im not sure how long you have to spend with C# before you know how
to do the equivalent of all the things you leanred how to do well in C++
over 10 years or so lol.

I just saw 'provider' being mentioned in relation to interfaces
in another post, wich seemed to offer some benefits, Im not sure if this is
a general or c# term or
but i intend to investigate.

many thanks
Colin =^.^=

Reply to this Message

Peter Duniho - 07 Jan 2008 18:15 GMT

> [...]
> However Im so used to C++ and I keep thinking I could do it this way but
> then find I cant,
> Im not sure how long you have to spend with C# before you know how
> to do the equivalent of all the things you leanred how to do well in C++
> over 10 years or so lol.

IMHO, it's a mistake to think that the language affects how you can design
your code. Different languages may complicate the implementation of a
design, but you don't really need language support if you're willing to
put more effort in. The first binary tree I ever wrote, I did in BASIC.
That is, regular old-school BASIC with no pointers, using parallel arrays
to store the data structure.

As far as C++ vs C# goes, my experience was that my C++ experience
translated almost immediately to C#. From an architectural point of view,
I've found the languages very similar. Where they differ, mostly what
I've found has been that C# simplifies and refines techniques that may be
used in C++.

There are lots of little differences and the languages are in some ways
very different, some times fundamentally. But from a design point of
view, I've found all of my old design skills translate directly.

Now, as far as your actual issue goes...because of the UI requirements,
you seem to not be able to get away from this reflexively-related data
structure. If that's the case, then all I can suggest is to be more
careful implementing management of the data structures. Why your data
structures are getting out of sync, I can't say. I can say that if you
keep code that manages the data structures isolated, so that a specific
kind of change to the data structure always only goes through a specific
block of code, you should fewer problems or none at all. In that
scenario, if the updates work for any data they should work for all data.

Why this doesn't seem to apply in your case, I can't say. Without a
specific example of your implementation, I can't offer specific advice.
But whatever the problem is, I doubt it has anything to do with using C#
versus C++. There's not any magic bullet in the language that will just
fix your data structure management woes.

Pete

Reply to this Message

Triple linked lists

Free Magazines