DSU pattern (was Re: Trouble sorting lists (unicode/locale related?))

[Duncan Booth]

Peter Otten <__peter__ at web.de> wrote in
news:bkn12v$tns$06$1 at news.t-online.com: 

> My first idea was to add a .dsu(mapping) where the tuples in the
> decoration phase would be generated as (mapping(item), item). 

Note that if anyone proposes this seriously, it should generate a 3-tuple 
(mapping(item), index, item) rather than the 2-tuple you suggest.

This is because the mapping function could reasonably be used to impose an 
ordering on objects that have no natural order, so you need to be sure that 
the comparison never falls through the the original object even where the 
mapping compares equal. It also has the side effect of making the sort 
stable (although if stability is a goal you might want another option to 
reverse the sort which would use '-index' as the second element and call 
.reverse() on the result).

FWIW, I think something like this belongs in the standard library rather 
than as a method on lists or a new builtin.

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?