Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell
From: rockwell@socrates.umd.edu (Raul Rockwell)
Newsgroups: comp.object
Subject: Re: generic sort orders
Message-ID: <ROCKWELL.91May23210411@socrates.umd.edu>
Date: 24 May 91 02:04:11 GMT
References: <1991May22.012821.12048@tkou02.enet.dec.com> <1991May22.183044.5634@Think.COM>
	<1991May22.203058.15452@ccs.carleton.ca>
	<1991May23.043349.24754@Think.COM>
Sender: rockwell@socrates.umd.edu (Raul Rockwell)
Organization: Traveller
Lines: 46
In-Reply-To: barmar@think.com's message of 23 May 91 04: 33:49 GMT

Barry Margolin:
[on using function arguments for generic sorting]

   Yes, of course the "object that represents the style of comparison
   being done" could be a function.  I was trying to suggest a more
   "object-oriented" approach to thinking about this problem.  As I
   said, I hadn't really designed the details; were I to try, I would
   probably give up and just use a function.  Or perhaps a hybrid,
   e.g. an object that contains some pretty generic options, along
   with a function that implements the more domain-specific behavior.

My personal favorite object for sorting is a "list of strings" (where
the strings are anything that the builtin ">" works for).  The trick
is DON'T SORT THE DATA.  Create a "sort message" (e.g. permute this
way...) which can be passed to whatever you like.

Now if you want to sort something that is nasty (like Japanese phone
book entries :-) you can implement it by "sorting" a representation of
the data which has been processed to so that sort will "do the right
thing".  (e.g. re-arrange first and last names, double each letter so
that the first letter of each pair is monocase and likewise preceed
every non-alpha character with one which indicates which "bucket" to
sort with, ...)

Most people, when they see this, can't figure out why you'd want to do
such a thing.  It's very handy though...

If anyone needs a diagram, here's a general case:

           A                  B               C
   object --> representation --> permutation --> sorted object
                                              ^
                                              |
                                            object

B is the "sorting function".  

Note that you don't need to incur the O(n log n) time penalty of
sorting when building your representation, so you can get an
efficiency gain too.  Er.. it's more efficient in time, you do need
space for your intermediate results.

(Incidentally, you'll find it much nicer if the sort guarantees that
"equal" strings maintain their order with respect to each other.)

Raul Rockwell