Craig,
Since I am leaving the country in less than 36 hours, I will not be able to
review all the stuff right now, but this will be a good mental exercise on
the plane :-).
I think once we figured out the algorithm and created more unit tests, we
can optimize the implementation by caching connected graphs (though I need
to take a closer look to make sure I am making sense at all).
Andrus
Craig Miskell writes:
> Hi,
> Just a heads up that I have completed and committed the new technique
> for resolving the order of inserts. That was one nasty bit of work
> (rather complicated unfortunately). My alarm bells have been going off
> because it is complicated (I've seen too many things that were
> unnecessariliy complicated), but the more I look at it the more I'm
> convinced it needs to be.
>
> For reference, I have included the algorithm below (psuedo-coded). This
> pseudo code is also in the OperationSorter.java file as well, for
> completeness.
>
> Some points:
> 1) It works for the unit tests (they've always worked, more by goodluck
> than anything else)
> 2) It seems to work so far in our particular case here (where it was
> failing before)
> 3) I'm almost certain there will be some borderline cases that it
> doesn't handle, but for now, it's more robust than what was there before
> (IMHO). That sounds quite uppity, doesn't it? I assure you that's not
> the intention.
> 4) It is obviously slower than the original sorting, but necessarily
> so. However, I'm pretty sure that the OperationSorter can be made
> better, mostly be changing the static methods to instance methods (and
> presorting the entities once at startup). That said, it currently has
> no noticeable effect on the unit tests (a reasonable initial case), but
> larger sets of DbEntities may cause problems. It also uses a fair bit
> of temporary objects, which may cause problems with memory usage.
>
> So, all that's left is the algorithm:
>
> Partition the entities into sets of connected entities.
> While there are unassigned entities:
> Create a new set and put the first unassigned entity in it.
> Follow relationships of entities in the set and add entities that
> aren't already in the set, until all relationships have been checked.
> end while
> For each set:
> Pick an entity, create a Structure entityDeps {entity,
> afterEntities, beforeEntities, dontCareEntities} and populate for that
> entity.
> Put this structure into a "main" list (one object only to start with)
> While there exists a structure in the main list that has
> after/before/dontcare entities do
> Pick one such "current" structure
> From its beforeEntities list, pick one of the entities and create its
> structure, only using other entities from the current before list in the
> new before/after/dontcare lists.
> Insert this new structure into the main list directly before the
> current structure
> Do the same for the afterEntities, but insert the resulting structure
> directly after the current structure in the main list
> Do the same for the dontCareEntities list, and place the result
> directly after the current structure (before or after is an arbitrary
> choice and doesn't matter. However, it must be between the current and
> the newly inserted after or before structure (the previous two steps)
> for consistency.
> End while
>
> Finally, take the lists from each set and concatenate the top level
> entities into one big list. The order of sets doesn't matter as by
> creation they are disjoint
>
>
> Craig
>
This archive was generated by hypermail 2.0.0 : Wed Nov 20 2002 - 18:27:23 EST