1 07/26/82 sort_items_
  2 
  3 
  4 The sort_items_ subroutine provides a generalized, yet highly
  5 efficient, sorting facility.  Entry points are provided for sorting
  6 fixed binary (35) numbers, float binary (63) numbers, fixed-length
  7 character strings, varying character strings, and fixed-length bit
  8 strings.  A generalized entry point is provided for sorting other data
  9 types (including data structures and data aggregates) and for sorting
 10 data into a user-defined order.
 11 
 12 The procedure implements the QUICKSORT algorithm of M.  H.  van Emden,
 13 including the Wheeler modification to detect ordered sequences.
 14 
 15 
 16 The subroutine takes a vector of unaligned pointers to the data items
 17 to be sorted and rearranges the elements of this vector to point to the
 18 data items in correct order.  Only the pointers are moved or copied
 19 into temporary storage; the data items remain where they were when
 20 sort_items_ was invoked.
 21 
 22 
 23 Entry points in sort_items_:
 24    (List is generated by the help command)
 25 
 26 
 27 :Entry:  fixed_bin:  07/26/82 sort_items_$fixed_bin
 28 
 29 
 30 Function:  This entry point sorts a group of aligned fixed binary
 31 (35,0) numbers into numerical order by reordering a pointer array whose
 32 elements point to the numbers in the group.
 33 
 34 
 35 Syntax:
 36 declare sort_items_$fixed_bin entry (ptr);
 37 call sort_items_$fixed_bin (v_ptr);
 38 
 39 
 40 Arguments:
 41 v_ptr
 42    points to a structure containing an array of unaligned pointers to
 43    the aligned fixed binary (35,0) numbers to be sorted.  (Input)
 44 
 45 
 46 Notes:  The structure pointed to by v_ptr is to be declared as follows,
 47 where n is the value of v.n:
 48 
 49 dcl 1 v             aligned,
 50       2 n           fixed bin (18),
 51       2 vector (n)  ptr unaligned;
 52 
 53 
 54 :Entry: float_bin:  07/26/82  sort_items_$float_bin
 55 
 56 
 57 Function: This entry point sorts a group of aligned float binary (63)
 58 numbers into numerical order by reordering a pointer array whose
 59 elements point to the numbers in the group.
 60 
 61 
 62 Syntax:
 63 declare sort_items_$float_bin entry (ptr);
 64 call sort_items_$float_bin (v_ptr);
 65 
 66 
 67 Arguments:
 68 v_ptr
 69    points to the above structure containing an array of unaligned
 70    pointers to the aligned float binary (63) numbers to be sorted.
 71    (Input)
 72 
 73 
 74 :Entry:  char:  07/26/82 sort_items_$char
 75 
 76 
 77 Function:  This entry point sorts a group of fixed-length unaligned
 78 character strings into ASCII collating sequence by reordering a pointer
 79 array whose elements point to the character strings in the group.
 80 
 81 
 82 Syntax:
 83 declare sort_items_$char entry (ptr, fixed bin (24));
 84 call sort_items_$char (v_ptr, string_lth);
 85 
 86 
 87 Arguments:
 88 v_ptr
 89    points to the structure (described in "Notes" above) containing an
 90    array of unaligned pointers to the varying character strings to be
 91    sorted.  (Input)
 92 string_lth
 93    is the length of each character string.  (Input)
 94 
 95 
 96 :Entry:  varying_char:  07/26/82 sort_items_$varying_char
 97 
 98 
 99 Function:  This entry point sorts a group of varying character strings
100 into ASCII collating sequence by reordering a pointer array whose
101 elements point to the character strings in the group.
102 
103 
104 Syntax:
105 declare sort_items_$varying_char entry (ptr);
106 call sort_items_$varying_char (v_ptr);
107 
108 
109 Arguments:
110 v_ptr
111    points to the structure (described in "Notes" above) containing an
112    array of unaligned pointers to the varying character strings to be
113    sorted.  (Input)
114 
115 
116 :Entry:  bit:  07/26/82 sort_items_$bit
117 
118 
119 Function:  This entry point sorts a group of fixed-length unaligned bit
120 strings into bit string order by reordering a pointer array whose
121 elements point to the bit strings in the group.  Bit string ordering
122 guarantees that, if each ordered bit string were converted to a binary
123 natural number, the binary value would be less than or equal to the
124 value of its successors.
125 
126 
127 Syntax:
128 declare sort_items_$bit entry (ptr, fixed bin (24));
129 call sort_items_$bit (v_ptr, length);
130 
131 
132 Arguments:
133 v_ptr
134    points the structure (described in "Notes" above) containing an array
135    of unaligned pointers to the fixed-length unaligned bit strings to
136    be sorted.  (Input)
137 length
138    is the number of bits in each string.  (Input)
139 
140 
141 :Entry:  general:  07/26/82 sort_items_$general
142 
143 
144 Function:  This entry point sorts a group of arbitrary data elements,
145 structures, or other aggregates into a user-defined order by reordering
146 a pointer array whose elements point to the data items in the group.
147 The structure of data items, the information field or fields within
148 each item by which items are sorted, and the data ordering principle
149 are all decoupled from the sorting algorithm by calling a user-supplied
150 function to order pairs of data items.  The function is called with
151 pointers to a pair of items.  It must compare the items and return a
152 value that indicates whether the first item of the pair is less than,
153 equal to, or greater than the second item.  The sorting algorithm
154 reorders the elements of the pointer array based upon the results of
155 the item comparisons.
156 
157 
158 Syntax:
159 declare sort_items_$general entry (ptr, entry);
160 call sort_items_$general (v_ptr, function);
161 
162 
163 Arguments:
164 v_ptr
165    points the structure (described in "Notes" above) containing an array
166    of unaligned pointers to the data items to be sorted.  (Input)
167 function
168    is a user-supplied ordering function.  (Input) Its calling sequence
169    is shown under "Notes" below.
170 
171 
172 Notes:  The sort_items_$general entry point calls a user-supplied
173 function to compare pairs of data items.  This function must know the
174 structure of the data items being compared, the field or fields within
175 each item that are to be compared, and the ordering principle to be
176 used in performing the comparisons.  The function returns a
177 relationship code as its value.  The calling sequence of the function
178 is shown below.
179 
180      declare function entry (ptr unaligned, ptr unaligned)
181              returns (fixed bin(1));
182      value = function (ptr_first_item, ptr_second_item);
183 
184 
185 Structure elements:
186    ptr_first_item
187       is an unaligned pointer to the first data item.  (Input)
188    ptr_second_item
189       is an unaligned pointer to a data item to be compared with the
190       first data item.  (Input)
191    value
192       is the value of the first data item compared to the second data
193       item.  (Output) It can be:
194       -1   the first data item is less than the second.
195        0   the first data item is equal to the second.
196       +1   the first data item is greater than the second.