[Bioc-devel] sorting objects with user-defined comparison function

[Seth Falcon]

Hi Wolfgang,

Wolfgang Huber <huber at ebi.ac.uk> writes:
> Dear Martin + Seth,
>
> thanks a lot! I was however thinking more of something like an R pendant 
> to the "qsort" function in libc (the algorithm doesn't matter, but the 
> interface):
>
> void qsort (void *array,
>     size_t count, size_t size, comparison_fn_t compare)
>
> where comparison_fn_t is a user-defined function that takes two 
> (pointers to) objects in array[] (these could themselves be references 
> to more complicated, arbitrary objects somewhere else) and returns -1, 0 
> or 1 depending on the value of the comparison. Sometimes such a 
> comparison can be mapped to comparisons between (tuples) of 
> representative numbers or character strings and the usual ordering 
> relation in these domains, but it need not: it could be an arbitrarily 
> complicated function.

Martin and I actually discussed a bit along these lines.  What gets
tricky rather quickly is how to handle dispatch.  Things are sane if
you have a list where each element is the same class.  In this case,
one could imagine determining the comparator method up front and
pass it to the sort code.  If you do full dispatch for each comparison
call, I suspect the performance will not be what is desired (I could
be wrong, and that could certainly change in the future).  If you
don't do full dispatch for each call, things are essentially broken
from the start for non (completely) homogeneous object lists.

> PS what is "order_keygen"? Googling it only let me to various Harry 
> Potter sites.

ha!  That was just an example name.  The idea is that you could define
a method for your classes that would return a string or integer that
could be used for sorting.  Your method could be complex, but by
returning a simple type you can reuse existing (fast) sorting
routines.

I have to go now or I'll be late for quidditch practice.

+ seth

-- 
Seth Falcon | Computational Biology | Fred Hutchinson Cancer Research Center
BioC: http://bioconductor.org/
Blog: http://userprimary.net/user/