Path: utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!grand.UUCP!day
From: day@grand.UUCP
Newsgroups: comp.lang.icon
Subject: Re: complicated sorting
Message-ID: <8801090133.AA25745@grand.COM>
Date: 9 Jan 88 01:33:06 GMT
References: <8801032038.AA13538@megaron.arizona.edu>
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: inet
Organization: Grand Software, Inc., makers of "The Grand Editor"
Lines: 166


    Date: Sun, 3 Jan 88 13:38:47 MST
    From: "Kenneth Walker" <arizona.edu!kwalker@uunet.UUCP>
    In-Reply-To: <397@grand.UUCP>
    To: day@grand.UUCP, icon-group@arizona.edu
    Subject: Re:  complicated sorting

    The comparison routine used by the Icon sort function is built
    into the run-time system and cannot be overriden without
    modifying Icon.

Right.

    Sometimes a comlicated sort criterion can be handled by constructing
    artifical keys for records such that a key sorts the corrosponding
    record where it needs to go in the sequence. The records can then
    be put in a table using the keys and the table can be sorted to
    produce the desired sequence of records. The artifical keys would
    typically be strings.

This is exactly what I am doing, and it's cumbersome.

    If such keys are not easy to produce, your best bet is probably
    to write a sort procedure in Icon specific to your application.

I believe the best solution is a more powerful sort function
to which the user supplies the comparison procedure, like qsort
in the C library.

The problem I am solving in icon (thank God and you people I'm
not trying to do it in C!) is the preparation of a book index.
The index is a list of entries consisting of a list of subentries
consisting of a list of page numbers.

A built-in function a la the C library qsort, would help.
It might look like this:

sortx(a, p)

    Sortlist is a stable sort which sorts list a and
    produces a new, sorted list.  Procedure p is called each
    time sortx needs to compare two list entries.  It takes
    two arguments and returns -1, 0, or 1 when the first
    argument is less than, equal to, or greater than the
    second argument, respectively.  If p is omitted, the
    standard icon sort order is used.

Since I wrote my first message on this subject, I now see
that even this proposed sortx doesn't really cut it for my
present problem.  It turns out to be the trivial case of what
I really need:

sortlist(a, p, depth)

    Sortlist is a stable sort which sorts list a and
    produces a new, sorted tree of lists of the specified
    depth.  In the simplest case, when the depth argument is
    1 or not specified, sortlist returns a simple sorted
    list.  If depth is 2, then a list of lists is returned,
    and so on for greater values of depth.

    Procedure p is called each time sortlist needs to
    compare two list entries.  If p is not specified, the
    standard icon sort order is used.

    When depth is not specified or is 1, procedure p must be
    in this form:

	procedure p(x1, x2)
	   return relation_result
	end

    where relation_result return value is -1, 0, or 1 when
    x1 is less than, equal to, or greater than x2,
    respectively.

    When depth is specified and is > 1, procedure p must be
    in this form:

	record sortcompare(relation, depth)

	procedure p(x1, x2)
	   return sortcompare(relation_result, depth_result)
	end

    The relation_result return value is -1, 0, or 1 when x1
    is less than, equal to, or greater than x2, respectively.

    The depth_result return value specifies how deep p had
    to go in making the comparison before deciding on the
    value for the relation field.  For efficiency, it is
    advisable to write procedure p so that it never bothers
    to compare to a depth greater than needed by its caller.

    For example, the list [ "aa", "ba", "bb", "c" ] sorted to
    a depth of 2 with the aid of a suitable comparison routine
    could yield: [ [ "aa" ], [ "ba", "bb" ], [ "c" ] ]

Such a function would be perfect for my application, and I
bet it would be a useful and powerful tool for other sorting
problems.

I don't have an algorithm to implement this.
I wish I did.  Any takers?

To be sure what I'm getting at is clear, here's an example:

procedure
cmp(x1, x2)
    if x2[1] ~== x1[1] then return sortcompare(x2[1] - x2[1], 1)
    if x2[2] ~== x1[2] then return sortcompare(x2[2] - x2[2], 2)
    return sortcompare(x2[3] - x2[3], 3)
end

Input:  ["aaa", "baa", "bba", "caa", "cab" ]

Call:   sortlist(Input, p, 1)
Output: [ "aaa", "baa", "bba", "caa", "cab" ]

Call:   sortlist(Input, cmp, 2)
Output: [
	  [ "aaa" ],
	  [ "baa", "bba" ],
	  [ "caa", "cab" ]
	]

Call:   sortlist(Input, cmp, 3)
Output: [
	  [
	    [ "aaa" ]
	  ],
	  [
	    [ "baa" ],
	    [ "bba" ]
	  ],
	  [
	    [ "caa", "cab" ]
	  ]
	]

Call:   sortlist(Input, cmp, 4)
Output: [
	  [
	    [
	      [ "aaa" ]
	    ]
	  ],
	  [
	    [
	      [ "baa" ]
	    ],
	    [
	      [ "bba" ]
	    ]
	  ],
	  [
	    [
	      [ "caa" ],
	      [ "cab" ]
	    ]
	  ]
	]

etc.

 --dave yost