On 06/22/2010 11:24 AM, Steve Schveighoffer wrote:
Hm... this is turning out to be quite an interesting problem.
I'm thinking a full cycle detection algorithm might be required, like
Floyd-Warshall, but that's O(n^3), so it would be painful to run on
the start of every thread. 100 modules == 1,000,000 iterations.
I agree with saving the result of the ordering!
Wouldn't a topological sort suffice for our needs?
For all modules with constructors:
1. Assign r=0 to all modules
2. Assign r=1 to modules that don't depend on other modules. If no such
modules, fail.
3. For each child of parent modules, assign r+1 to its rank if it's
zero. If it's not zero and is not r+1, cycle detected.
Then constructor execution will be in increasing order of rank. For
modules of the same rank the order is not important.
I might be way off :o).
Andrei
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
