myfaces-dev mailing list archives

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

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.

regards,

Leonardo Uribe

2010/2/4 Curtiss Howard <curtiss.howard@gmail.com>

> 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
>

Mime
View raw message