On Aug 14, 2009, at 2:23 PM, Krzysztof Kosiński wrote:
Jon A. Cruz wrote:
=================== Q: *Why* do you want to iterate over references to an object? A: Umm.... I dunno. Just some things. ===================
I don't understand you. I explicitly said why it's needed, at the very beginning. I'll repeat that list for you. 1 means the task would be simplified by "find hrefs to object", and 2 by "find hrefs in an object".
No.
To clarify, you did not really explicitly say the "why" of the ends, just the "how" of the means you were looking at.
As you say "the task" is an *implicit* reference to the "why", but did not really address what that was.
And to be clear, "find hrefs to object" and "find hrefs in an object" are not high-level "why" items, but low-level "how" items.
- Generic clipboard code that does not require updates whenever a
new type of SPObject that can refer to something is added (2). 2. Robust ID collision resolution (1). 3. Deleting objects that are referred to - currently deleting a gradient in the XML editor causes junk to be displayed and usually a crash (1). 4. Better vacuum defs (something like mark-and-sweep could be used instead of the current simple refcounting scheme) (2). 5. Editing a clipping path or mask that is applied to several objects - the outline should be shown over each item the mask is applied to (1). 6. Not having to redraw everything when a gradient, pattern, etc. is changed (1).
Ooh. Good list.
#1 is a good problem. #2 is an "interesting" problem that might be much smaller than expected. This definitely does not require a high-performance structure. #3 is a very large and complicated problem. For this I can see that some UI work and such would be required. #4 is another large problem that is more than just "who is referred to". That would be part of the solution, but more work is needed. Things like "not referenced but still desired" is critical but hard to implement without some thought. #5 is technically not solved by just that simple structure. It could be *part* of the solution, but there really is a lot more to the problem. #6 is not nearly as simple as you might guess. Using the simple structure chain to try to determine that one will fall down pretty quickly. Among other things that involves bounding boxes, transformations, intersections of bounding boxes, etc.
Often different structures are appropriate for solving different problems. I've personally seen where an array of pointers one walks and compares vastly outperforms "smarter" structures (I can go into that separately if you're interested). If you're trying to solve several different problems with one single structure then that's a red-flag.
There are only 2 problems to solve, and there are 2 separate but identical data structures that happen to have their data in the same object.
Ah, and this is where you're missing things. There are more than two problems. There are many many problems, but 2 proposed implementations to address those problems.
If you can't see more than 2 problems, then you really need to take a step back and think about it. From an architectural viewpoint those two are both "means" and not "ends". Thus they themselves are not the problems but only the means you are looking at to be able to solve some problems.
I was thinking that the best thing to move forward would be to do a simple wiki page to list out specific use cases where this structure would be helpful.
See above. I may put this on the wiki if you want, but I'm not sure it would get more exposure than here.
I'll get that going, and include a breakdown. The wiki and chat rooms are much better communication channels to hash out such details as these. (Emails tend to get fragmented and hard to follow, etc.)
Just for an example, I'll start discussion on one point (look for it in the wiki soon): Problem: avoid ID collision When does this occur? * when a user pastes content from another SVG document * when a user changes an object's ID via the XML editor or object properties
These are two different use cases. The second use case is quite simple to address. A *highly* efficient structure to address this would be a map of IDs used in the document. Upon attempting to commit the ID change in the UI, a simple check for presence in the map would result in an immediate pass or fail. If, on the other hand, the three way pointer was relied upon then in order to detect if another object had the same ID the could would have to walk the *entire* document tree visiting each node and checking its ID.
So the tri-pointer really is not a solution for the "avoid ID collision" problem in that second use case.
For the first use case I believe we need to define what the requirement actually is. Here is a first cut:
"When pasting content from the clipboard, modify any colliding ID's to be new unique ID's"
Sounds good. But then we still have the first half of the problem where we need to walk *both* the existing document tree and also the clipboard tree to find each ID. If it were implemented with no other structures that would even lead to an exponential slowdown, so we can't do that. Ok.
So we'll assume that we have a set that contains the existing IDs in a document. Now we can walk the pasted in clipboard tree and check for any conflicts. So we'll just do a complete tree walk of that new subset (probably will be smaller than that of the main document, so that will help) checking each node for an ID and if it has a conflicting one just add it to a set of ID's to be changed.
Interesting. So now we have a set of IDs that are in the incoming tree that need to be changed. For each one we'll have to come up for a replacement that does not collide with the existing tree *or* the new replacements. We also will need to find each object with that id, etc. So perhaps instead of a set of IDs we should have built a set of SPObjects that need ID changes. Hmmm... and to properly avoid new collisions we'll need to create and update a list of *all* IDs in the incoming tree. So we can check any proposed replacement for presence in both the main tree and the incoming tree. Once we have that, we can visit the list of objects to be updated and change their IDs before merging into the main tree. Voila! then we're done.
Oop! no we're not. What if some of the things that were copied are dangling references! Hmmmm... what should we do about that? Oh, and what if we're copying from the same document we might want a half- copy that will keep references to gradients, etc, and have those gradients also just in case we're pasting into a different document. And what if we have a "just in case" gradient with the same ID as in the destination document... and that gradient has the same properties? Should we assume it is the same and not change the ID???
eeek
But... as I come to the end of this first pass analysis, I notice something quite interesting. The tri-pointer would only ever help with "ID changing" and not really with "clash prevention" itself.
Hmmm... and while we're at it, the proposed class does seem a bit heavyweight for the problem it wants to solve. Also I don't see anything addressing the problem of pinning. I would think we would need weak references in here. That's another thing to add to the consideration.
Bottom line... this is definitely a problem to hash out online in the chat room and/or on the wiki. Just looking at that one sub-section I typed out really let's me see email will not be the best medium for the discussion.