Debian Codegraph @

ipl/packs/ibpag2/sortff.icn

raw
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