| 1 |
############################################################################ |
| 2 |
# |
| 3 |
# Name: sortff.icn |
| 4 |
# |
| 5 |
# Title: sortf with multiple field arguments |
| 6 |
# |
| 7 |
# Author: Bob Alexander and Richard L. Goerwitz |
| 8 |
# |
| 9 |
# Date: July 14, 1993 |
| 10 |
# |
| 11 |
############################################################################ |
| 12 |
# |
| 13 |
# Sortff is like sortf(), except takes an unlimited number of field |
| 14 |
# arguments. E.g. if you want to sort a list of structures on field |
| 15 |
# 5, and (for those objects that have the same field 5) do a sub-sort |
| 16 |
# on field 2, you would use "sortff(list_of_objects, 5, 2)." |
| 17 |
# |
| 18 |
############################################################################ |
| 19 |
|
| 20 |
# |
| 21 |
# sortff: structure [x integer [x integer...]] -> structure |
| 22 |
# (L, [fields ...]) -> new_L |
| 23 |
# |
| 24 |
# Where L is any subscriptable structure, and fields are any |
| 25 |
# number of integer subscripts in any desired order. Returns |
| 26 |
# a copy of structure L with its elements sorted on field 1, |
| 27 |
# and, for those elements having an identical field 1, sub- |
| 28 |
# sorted on field 2, etc. |
| 29 |
# |
| 30 |
procedure sortff(L, fields[]) |
| 31 |
*L <= 1 & { return copy(L) } |
| 32 |
return sortff_1(L, fields, 1, []) |
| 33 |
end |
| 34 |
|
| 35 |
procedure sortff_1(L, fields, k, uniqueObject) |
| 36 |
|
| 37 |
local sortField, cachedKeyValue, i, startOfRun, thisKey |
| 38 |
|
| 39 |
sortField := fields[k] |
| 40 |
L := sortf(L, sortField) # initial sort using fields[k] |
| 41 |
# |
| 42 |
# If more than one sort field is given, use each field successively |
| 43 |
# as the current key, and, where members in L have the same value for |
| 44 |
# this key, do a subsort using fields[k+1]. |
| 45 |
# |
| 46 |
if fields[k +:= 1] then { |
| 47 |
# |
| 48 |
# Set the equal-key-run pointer to the start of the list and |
| 49 |
# save the value of the first key in the run. |
| 50 |
# |
| 51 |
startOfRun := 1 |
| 52 |
cachedKeyValue := L[startOfRun][sortField] | uniqueObject |
| 53 |
every i := 2 to *L do { |
| 54 |
thisKey := L[i][sortField] | uniqueObject |
| 55 |
if not (thisKey === cachedKeyValue) then { |
| 56 |
# |
| 57 |
# We have an element with a sort key different from the |
| 58 |
# previous. If there's a run of more than one equal keys, |
| 59 |
# sort the sublist. |
| 60 |
# |
| 61 |
if i - startOfRun > 1 then { |
| 62 |
L := L[1:startOfRun] ||| |
| 63 |
sortff_1(L[startOfRun:i], fields, k, uniqueObject) ||| |
| 64 |
L[i:0] |
| 65 |
} |
| 66 |
# Reset the equal-key-run pointer to this key and cache. |
| 67 |
startOfRun := i |
| 68 |
cachedKeyValue := L[startOfRun][sortField] | uniqueObject |
| 69 |
} |
| 70 |
} |
| 71 |
# |
| 72 |
# Sort a final run if it exists. |
| 73 |
# |
| 74 |
if i - startOfRun > 1 then { |
| 75 |
L := L[1:startOfRun] ||| |
| 76 |
sortff_1(L[startOfRun:0], fields, k, uniqueObject) |
| 77 |
} |
| 78 |
} |
| 79 |
|
| 80 |
return L |
| 81 |
|
| 82 |
end |