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

[Wolfgang Huber]

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.

I was surprised that nobody seems yet to have made an R version of this 
[and probably I should ask R-help?], since it seems easy enough, but 
perhaps we'll just have to do it.

	Best wishes	
	Wolfgang

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


> Hi Wolfgang --
> 
> I guess these are S4 objects. One way might be, for a list l of
> objects with slots x, y
> 
>> s1 <- sapply(l, slot, "x")
>> s2 <- sapply(l, slot, "y")
>> sorted <- l[order(s1, s2)]
> 
> slot access might be replaced by 'order_keygen' to generate whatever
> the comparison value should be.
> 
> Here's a complete example:
> 
>> ## setup
>> n <- 100
>> l <- list(n)
>> xi <- sample(1:10, n, replace=TRUE)
>> yi <- sample(letters, n, replace=TRUE)
>> setClass("A",
> +          representation=representation(
> +            x="numeric",
> +            y="character"))
> [1] "A"
>> l <- mapply(new, Class="A", x=xi, y=yi)
>> ## unorderd
>> head(unlist(lapply(l, slot, "x"), use.names=FALSE))
> [1] 10  1  5 10  7  7
>> head(unlist(lapply(l, slot, "y"), use.names=FALSE))
> [1] "k" "d" "z" "y" "z" "k"
>> ## sort
>> s1 <- sapply(l, slot, "x")
>> s2 <- sapply(l, slot, "y")
>> sorted <- l[order(s1, s2)]
>>
>> ## how'd we do?
>> head(unlist(lapply(sorted, slot, "x"), use.names=FALSE))
> [1] 1 1 1 1 1 1
>> head(unlist(lapply(sorted, slot, "y"), use.names=FALSE))
> [1] "d" "j" "k" "n" "q" "r"
> 
> Martin (with input from Seth)
> 
> Wolfgang Huber <huber at ebi.ac.uk> writes:
> 
>> Hi all,
>>
>> I hope I have not missed the obvious...: does anyone know a function in
>> R (or in a package) that sorts the elements of a list based on a
>> user-defined comparison function?
>> -- 
>> Best wishes
>>  Wolfgang
>>
>> ------------------------------------------------------------------
>> Wolfgang Huber  EBI/EMBL  Cambridge UK  http://www.ebi.ac.uk/huber
>>