Need guidance on data structure
Need guidance on data structure
- Subject: Need guidance on data structure
- From: Graham Cox <email@hidden>
- Date: Tue, 28 Apr 2009 11:47:53 +1000
Not directly a Cocoa question - apologies if that's inappropriate, but
I could do with some brain power to bear on this design problem and
there are lots of smart people here...
I have an object that represents a road, say. It has a path that gets
drawn to show the road. Typically there are several parts to the
rendering of this path, for example a black stroke of say 8 points,
overlaid with a grey stroke of say 7 points. This gives a 0.5 point
"casement" to the drawn road.
A road can be connected to other roads. Currently each road keeps a
list of the "subroads" that are connected to it, which is a parent-
child relationship. A parent road can have any number of child roads,
but a child road can only have a maximum of two parents - one for each
end. (The parent could also be the same for each end, or it could have
an unconnected end which is a nil parent for that end). Roads can
connect to each other in any way you like, so in some cases a child
road could be the parent of its own parent, and obviously there are
many other kinds of cycles possible. The only thing currently not
permitted is that a road can't loop back and connect to itself.
When a connected network of roads is drawn, the junctions of a parent
and child road needs to be carefully handled so that the appearance is
right. The casements are drawn first, then the overlaid stroke for the
child road, then the overlaid stroke for the parent road which then
covers the overlap of the child road stroke to give a clean join.
(Child roads might have a different overlay colour from their parent
road). To handle this, each junction is drawn by the parent road,
including a minimal short length of the child road, with various
clippings applied to limit the extent of drawing to the vicinity of
the junction. The drawing of each stroke is carefully phased to ensure
the desired order. This means that the overall road network can be
drawn by simply iterating the list of roads and drawing each one - the
order of overall drawing doesn't affect the correct drawing of
junctions, because they are effectively re-ordered into the local
parent-child ordering on the fly as each one is drawn.
Add to this the fact that each road can be directly moved/edited by
the user, which recalculates the path, repositions the junctions as
needed to remain attached and cascades the path changes to the
subroads as needed, and so on.
This does all, somehow, manage to work quite well. The problem I'm
running into is that once the number of roads multiplies up, the
cascading effect becomes too slow to be usable, especially for
interactive movement. I also require a couple of cycle-breaking locks
to prevent infinite loops, which strikes me as indicative of an
awkward design.
Something tells me I'm missing a trick here. A data structure that is
intended to manage exactly this sort of interconnected network of
objects without the awkwardness I'm running into with this ad-hoc
approach. The problem is I don't know what sort of thing I should be
looking for, or what the right technical terms would be. Or there may
be some completely obvious way to do this that I'm missing. The key
requirement is that the connections between the parents and children
are drawn properly, which requires that children are always drawn
before their parents. Because of the cyclic nature of the network
though, there isn't a way I can see to simply sort the objects into
the right order.
Any insight or pointers would be gratefully received at this point -
I'm tying myself in knots trying to make this function with any
scalability.
--Graham
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden