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 - 17:13:51 EST