nowlin@ihuxy.UUCP (01/12/88)
Group,
I sent an example sorting procedure out a couple days ago in
response to a message about sorting routines. I mentioned in the
accompanying note that the procedure could be extended to sort on multiple
keys with just a little modification. I then decided to go ahead and make
it sort on multiple keys on my own. The modified routine follows. I also
commented the procedure this time so it would be easier to follow.
There is one final modification I'd like to see and I'd like some help from
you Icon gurus out there. How could I pass a list of sorting keys that
consist of strings corresponding to the labels used to reference the fields
in a record instead of numeric indexes for the record that is being sorted
to the recsort() procedure? If you didn't follow that question here is an
example of what I mean. Given the program that follows, If I want to sort
the password file by the uid field I have to invoke the program with "3" as
the sorting key. I'd like to be able to invoke it with "uid" as the
sorting key.
Any suggestions are welcome. The real trick is to do this in a record
definition independent way. This means that recsort() can't know ahead of
time about the definition of the record type it's sorting. I don't think
it can be done given the current Icon. Please prove me wrong.
Jerry Nowlin
(...!ihnp4!ihuxy!nowlin)
# This example program is to illustrate the recsort() procedure. It sorts
# a UNIX style password file. The arguments to the program should be the
# fields in each password entry to sort on in order of precedence. The
# program has a built-in limit of the first 20 entries in the password file
# but it can be removed to test the program on the whole password file.
# Notice that the UID and GID fields are now forced to be numeric. Sorts
# on these fields will work accordingly.
record passwd(name,pass,uid,gid,info,logdir,shell)
procedure main(args)
if *args = 0 then stop("I need a numeric record index to sort on")
users := []
in := open("/etc/passwd","r")
every line := !in\20 do line ? {
user := passwd()
user.name := tab(upto(':')) & move(1)
user.pass := tab(upto(':')) & move(1)
user.uid := numeric(tab(upto(':'))) & move(1)
user.gid := numeric(tab(upto(':'))) & move(1)
user.info := tab(upto(':')) & move(1)
user.logdir := tab(upto(':')) & move(1)
user.shell := tab(0)
put(users,user)
}
close(in)
write("UNSORTED: ",image(users)," ",image(users[1]))
every user := !users do write( user.name,":",
user.pass,":",
user.uid,":",
user.gid,":",
user.info,":",
user.logdir,":",
user.shell)
stuff := recsort(users,args)
write("\nSORTED: ",image(stuff)," ",image(stuff[1]))
every user := !stuff do write( user.name,":",
user.pass,":",
user.uid,":",
user.gid,":",
user.info,":",
user.logdir,":",
user.shell)
end
# Sort a list of records by the fields given in keys. These fields must
# be numeric indexes to one or more of the fields in the record type being
# sorted. A sorted list of records is returned.
procedure recsort(recs,keys)
# Initialize a temporary table.
tempt := table()
# Get a sorting key.
key := get(keys)
# Take every record in the recs list and add it to the table.
every rec := !recs do
# Each index to the table is a different sorting key. To
# avoid losing records which have identical sorting keys
# each value in the table must be a list of the records
# that are indexed by a given sorting key.
(/tempt[rec[key]] := [ rec ]) | put(tempt[rec[key]],rec)
# Sort the table by the indexes (sorting keys).
templ := sort(tempt,1)
# Initialize a new records list.
newrecs := []
# Take apart the pairs of lists generated by the sort.
every pair := !templ do {
# If there is more than one record in this value list and
# there are additional keys to sort on recursively sort this
# value list with the remaining keys.
if *pair[2] > 1 & *keys > 0 then
pair[2] := recsort(pair[2],copy(keys))
# Add each record from the value list to the temporary list.
every put(newrecs,!pair[2])
}
# Return the new sorted list of records.
return newrecs
endgudeman@ARIZONA.EDU ("David Gudeman") (01/14/88)
From: ihnp4!ihuxy!nowlin ...How could I pass a list of sorting keys that consist of strings corresponding to the labels used to reference the fields in a record instead of numeric indexes for the record that is being sorted to the recsort() procedure? If you didn't follow that question here is an example of what I mean. Given the program that follows, If I want to sort the password file by the uid field I have to invoke the program with "3" as the sorting key. I'd like to be able to invoke it with "uid" as the sorting key. You can't reference records by string name anyway, so getting a string corresponding to a field name wouldn't do you any good. You probably should be using tables if you want to do this. Table references are a little uglier than record references, e.g.: foo["name"] vs. foo.name, but tables are a lot more flexible.