Path: utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!ARIZONA.EDU!kwalker
From: kwalker@ARIZONA.EDU ("Kenneth Walker")
Newsgroups: comp.lang.icon
Subject: Re:  complicated sorting
Message-ID: <8801121935.AA14573@megaron.arizona.edu>
Date: 12 Jan 88 19:35:38 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: inet
Organization: The ARPA Internet
Lines: 95


	From: grand!day@uunet.UU.NET
	Date: Fri, 08 Jan 88 17:33:06 PST

        ...
	
	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.

This suggestion sounds to me like something worth putting on the list
of possible future enhancements to Icon. There is an actual list.
Inclusion in the list doesn't insure a feature will every get put in
the language, but it does mean that it will get consideration when (and if)
the next round of enhancements are implemented.
	
	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:
	
        [details omitted - essentially a routine to sort on multiple
         keys producing a tree structure]

I can beleive that such a routine is usefull occationally, but its need
doesn't seem to me to be wide spread enough to burden the language
with such a complex feature.

When I need to sort on multiple keys, I sometimes use multi-level tables.
Perhaps a modification of the following routine could be used for your
purposes.

#
# Sort records on 3 keys. The result is a list of lists of lists (that is,
#  a 3 level tree - one level for each key). The intermediate data structure
#  is a table of tables of tables; each level of tables is keyed on the
#  corrosponding record key.
#
record info(key1, key2, key3)

procedure main()
   local s, w_sp
   local rec
   local tbl, x
   local lst

   #
   # 1st level table
   #
   tbl := table()

   #
   # read records and store in intermediate table structure
   #
   while s := read() do {
      s ? rec := info(tab(many(&lcase)),
                      tab(upto(&lcase)) & tab(many(&lcase)),
                      tab(upto(&lcase)) & tab(many(&lcase)))
      #
      # put the record in the correct table, making sure the required 2nd
      # and 3rd level tables exist
      #
      /tbl[rec.key1] := table()
      x := tbl[rec.key1]
      /x[rec.key2] := table()
      x := x[rec.key2]
      x[rec.key3] := rec
      }

   #
   # convert each level of table into a sorted list
   #
   lst := sort_tbl(tbl)

   do_whatever(lst)
end

procedure sort_tbl(tbl)
   local l1, l2

   l1 := sort(tbl, 3)

   #
   # remove keys from list, sorting entries if they are tables
   #
   l2 := list()
   get(l1)
   if type(l1[1]) == "table" then
      while put(l2, sort_tbl(get(l1))) do
         get(l1)
   else
      while put(l2, get(l1)) do
         get(l1)
   return l2
end