myfaces-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Leonardo Uribe <>
Subject Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is broken
Date Thu, 04 Feb 2010 16:06:08 GMT

I did the algorithm proposed there. For me it is ok if we can find a simpler
one, as long as all tests proposed pass.

Anyway, I'll check why it is failing.


Leonardo Uribe

2010/2/4 Curtiss Howard <>

> Hi,
> Our testers are currently running against Sun's CTS tests and the
> relative ordering algorithm in
> FacesConfigurator.sortRelativeOrderingList() is failing on a rather
> simple case:
> A after B
> B before C
> C before A
> The expected faces-config ordering is B-C-A, but instead
> sortRelativeOrderingList() is detecting a circularity.
> I've looked at the code, and it seems like a very complicated
> algorithm that attempts to sort the list elements in-place using
> weighting.  Honestly I'm not even sure where to begin modifying that
> code.
> Looking through the history, I can't determine who the original author
> is, so if you're reading this, please let me know your thoughts.  I'd
> like to fix this problem, but instead I'd prefer to rewrite it using a
> simpler and more reliable algorithm, which involves creating a tree
> out of the "before/after" rules and using a bottom-up level order
> traversal to trim duplicate nodes and finally reversing the resulting
> list.  Circularities can also be detected in the same pass.  Is that a
> less efficient algorithm?  Most likely, but I'd argue its simplicity
> and reliability, coupled with the fact that the data set should always
> stay fairly small (after all, how many faces-configs can someone
> possible use in an application...) would make up for that.
> Thoughts?
> Thanks,
> Curtiss Howard

View raw message