/* MSORT.I Multiple key sort routine. $Id$ */ /* Copyright (c) 1994. The Regents of the University of California. All rights reserved. */ func msort (x, ..) /* DOCUMENT msort(x1, x2, x3, ...) returns an index list which sorts the array X1 into increasing order. Where X1 values are equal, the list will sort X2 into increasing order. Where both X1 and X2 are equal, X3 will be in increasing order, and so on. Finally, where all of the keys are equal, the returned list will leave the order unchanged from the input keys. The Xi may be numbers or strings (e.g.- X1 could be an integer while X2 was a string, and X3 was a real). The Xi must all be conformable, and each dimension of X1 must be as large as the corresponding dimension of any otehr Xi. Hence, msort(x) will return the same list as sort(x), except where the values of x are equal, in which case msort leaves the order unchanged, while sort non-deterministically permutes equal elements. This feature may cost a factor of two in speed, so don't use it unless you really need it. In general, msort will call sort up to twice per input argument. SEE ALSO: sort, msort_rank */ { mxrank= numberof(x)-1; local list; rank= msort_rank(x, list); if (max(rank)==mxrank) return list; norm= 1.0/(mxrank+1.0); if (1.0+norm == 1.0) error, pr1(mxrank+1)+" is too large an array"; n= more_args(); while (n--) { x= next_arg(); rank+= msort_rank(x)*norm; /* adjust rank for next key */ rank= msort_rank(rank, list); /* renormalize adjusted rank */ if (max(rank)==mxrank) return list; } /* use indgen as final key guaranteed to break up any remaining equal values */ return sort(rank+indgen(0:mxrank)*norm); } func msort_rank (x, &list) /* DOCUMENT msort_rank(x) msort_rank(x, list) returns a list of longs the same size and shape as X, whose values are the "rank" of the corresponding element of X among all the elements of X -- the smallest element has rank 0 and the largest has the largest rank, which is equal to one less than the number of distinct values in the array X. If LIST is present, it is set to the order list returned by sort(x(*)). SEE ALSO: msort, sort */ { rank= array(0, dimsof(x)); if (numberof(x)<2) return rank; void= use_origins(0); list= sort(x(*)); x= x(list); x= (x(1:-1)!=x(2:0))(cum); /* NOT dif -- x may be strings */ rank(list)= x; return rank; }