02/02/84  sort_items_indirect_

Function: provides a facility for sorting a group of data items, based
upon the value of an information field that is logically associated
with each item but resides at a varying offset from the beginning of
each item.


Notes: This procedure differs from that used in the sort_items_
subroutine in that an array of indices into the vector is sorted
rather than the vector itself.  This allows the caller to create two
vectors of pointers: one containing pointers to the data items to be
sorted and one containing pointers to the particular data field within
each item on which the item is to be sorted.  There is a one-to-one
correspondence between the elements of the data items vector and the
elements of the data field within each item vector.  This
correspondence is maintained across the reordering of the index array.
Thus, the index array provides indices into the sorted list of data
fields and also into the sorted list of data items containing these
fields.


Only indices are moved or copied into temporary storage.  Vector
elements and data items remain where they were when
sort_items_indirect_ was invoked.

If the information field upon which the sort is based is located at a
known offset from the beginning of each item, then the calling program
can avoid creating the index array and the item vector by using the
sort_items_ subroutine.  (This subroutine cannot process adjustable
length fields.)  The field vector is passed to the sort_items_
subroutine, and then the elements of the item vector are computed by
applying the appropriate offset to the corresponding field vector
elements.


Entry points in sort_items_indirect_:
   (List is generated by the help command)


:Entry:  adj_char:  02/02/84 sort_items_indirect_$adj_char


Function: sorts a group of information fields, which are unaligned
adjustable length character strings, into ASCII collating sequence
order by reordering an index array.  The elements in this index array
are indices into an array of unaligned pointers to the character
strings in the group.


Syntax:
declare sort_items_indirect_$adj_char (ptr, ptr, ptr);
call sort_items_indirect_$adj_char (v_ptr, i_ptr, l_ptr);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the aligned fixed binary (35,0) numbers to be sorted.  (Input).
   The structure is to be declared as follows, where n is the number
   of elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin(18)
   indices into the unaligned pointer array.  (Input).  The structure
   is to be declared as follows, where n is the number of elements to
   be sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);


l_ptr
   points to a structure containing an array of lengths of the
   unaligned adjustable length character strings to be sorted.
   (Input).  The structure is declared as follows, where n is the
   number of elements to be sorted.

      dcl 1 l aligned,
            2 n fixed bin (18),
            2 vector (n) fixed bin (21);


:Entry:  bit:  02/02/84 sort_items_indirect_$bit


Function: sorts a group of information fields, which are fixed-length
unaligned bit strings into bit string order by reordering an index
array.  The elements of this index array are indices into an array of
pointers to the bit strings in the group.  Bit string ordering
guarantees that, if each ordered bit string is converted to a binary
natural number, the binary value is less than or equal to the value of
each of its successors.


Syntax:
declare sort_items_indirect_$bit entry (ptr, ptr, fixed bin (24));
call sort_items_indirect_$bit (v_ptr, i_ptr, length);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the fixed-length unaligned bit strings to be sorted.  (Input) The
   structure is to be declared as follows, where n is the number of
   elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin(18)
   indices into the unaligned pointer array.  (Input) The structure is
   to be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);

length
   is the number of bits in each string.  (Input)


:Entry:  char:  02/02/84 sort_items_indirect_$char


Function: sorts fixed-length unaligned character strings into ASCII
collating sequence by reordering an index array whose elements are
indices into a pointer array that points to the strings.  All the
strings must be the same length.


Syntax:
declare sort_items_indirect_$char entry (ptr, ptr, fixed bin (21));
call sort_items_indirect_$char (v_ptr, i_ptr, string_lth);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the fixed-length unaligned character string to be sorted.  (Input)
   The structure is to be declared as follows, where n is the number
   of elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure of fixed bin (18) indices into the unaligned
   pointer array.  (Input) The structure is to be declared as follows,
   where n is the number of elements to be sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);

string_lth
   indicates the length of each character string.  (Input)


:Entry:  fixed_bin:  02/02/84 sort_items_indirect_$fixed_bin


Function: sorts a group of information fields, which are aligned fixed
binary (35,0) numbers, into numerical order by reordering an index
array.  The elements of this index array are indices into an array of
unaligned pointers to the numbers in the group.


Syntax:
declare sort_items_indirect_$fixed_bin entry (ptr, ptr);
call sort_items_indirect_$fixed_bin (v_ptr, i_ptr);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the unaligned adjustable length character strings to be sorted.
   (Input) The structure is to be declared as follows, where n is the
   number of elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin(18)
   indices into the unaligned pointer array.  (Input) The structure is
   to be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);


:Entry:  float_bin:  02/02/84 sort_items_indirect_$float_bin


Function: sorts a group of information fields, which are aligned float
binary (63,0) numbers, into numerical order by reordering an index
array.  The elements of this index array are indices into an array of
unaligned pointers to the numbers in the group.


Syntax:
declare sort_items_indirect_$float_bin entry (ptr, ptr);
call sort_items_indirect_$float_bin (v_ptr, i_ptr);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the aligned float binary (63,0) numbers to be sorted.  (Input) The
   structure is to be declared as follows, where n is the number of
   elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin(18)
   indices into the unaligned pointer array.  (Input) The structure is
   to be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);


:Entry:  general:  02/02/84 sort_items_indirect_$general


Function: sorts a group of information fields (which are arbitrary
data elements, structures, or other aggregates) into a user-defined
order.  It does this by reordering an array of indices into a pointer
array.  The elements of this index array point to the sort information
field within the data items of the group.  The structure and data type
of the information field and the data ordering principle are decoupled
from the sorting algorithm by calling a user-supplied function to
order pairs of information fields.  The function is called with
pointers to a pair of fields.  It must compare the fields and return a
value that indicates whether the first field of the pair is less than,
equal to, or greater than the second field.  The sorting algorithm
reorders the elements of the index array based upon the results of the
information field comparisons.


Syntax:
declare sort_items_indirect_$general entry (ptr, ptr, entry);
call sort_items_indirect_$general (v_ptr, i_ptr, function):


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the information fields to be sorted.  (Input) The structure is to
   be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin (18)
   indices into the unaligned pointer array.  (Input) The structure is
   to be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);

function
   is a user-supplied ordering function. (Input) (See "Notes" below.)


Notes:
The sort_items_indirect_$general entry point calls a user-supplied
function to compare pairs of data items.  This function must know the
structure and data type of the information fields, and it must know the
ordering principle to be used to compare a pair of information fields.
The function returns a relationship code as its value.  The calling
sequence of the function is as follows:

   declare function entry (ptr unaligned, ptr unaligned)
        returns (fixed bin(1));
   value = function (ptr_1st_field, ptr_2nd_field);


ptr_1st_field
   is an unaligned pointer to the first information field.  (Input)
ptr_2nd_field
   is an unaligned pointer to an information field to be compared with
   the first information field.  (Input)
value
   is the value of the first information field compared to the second
   information field.  (Output).  It can be:
   -1   first information field is less than the second.
    0   first information field is equal to the second.
   +1   first information field is greater than the second.

A simple example of a user-supplied ordering function is shown in the
Subroutines manual under the sort_items_ subroutine.


:Entry:  varying_char:  02/02/84 sort_items_indirect_$varying_char


Function: sorts a group of information fields, which are varying
unaligned character strings, into ASCII collating sequence by
reordering an index array.  The elements of this index array are
indices into an array of pointers to the character strings in the
group.


Syntax:
declare sort_items_indirect_$varying_char entry (ptr, ptr);
call sort_items_indirect_$varying_char (v_ptr, i_ptr);


Arguments:
v_ptr
   points to a structure containing an array of unaligned pointers to
   the varying fixed-length character strings to be sorted.  (Input)
   The structure is to be declared as follows, where n is the number
   of elements to be sorted.

      dcl 1 v aligned,
            2 n fixed bin (18),
            2 vector (n) ptr unaligned;


i_ptr
   points to a structure containing an ordered array of fixed bin(18)
   indices into the unaligned pointer array.  (Input) The structure is
   to be declared as follows, where n is the number of elements to be
   sorted.

      dcl 1 i aligned,
            2 n fixed bin (18),
            2 array (n) fixed bin (18);


                                          -----------------------------------------------------------


Historical Background

This edition of the Multics software materials and documentation is provided and donated
to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. 
as a contribution to computer science knowledge.  
This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology,
Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL
and BULL HN Information Systems Inc. to the development of this operating system. 
Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970),
renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership
of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture 
for managing computer hardware properly and for executing programs. Many subsequent operating systems 
incorporated Multics principles.
Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., 
as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. .

                                          -----------------------------------------------------------

Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without
fee is hereby granted,provided that the below copyright notice and historical background appear in all copies
and that both the copyright notice and historical background and this permission notice appear in supporting
documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining
to distribution of the programs without specific prior written permission.
    Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc.
    Copyright 2006 by BULL HN Information Systems Inc.
    Copyright 2006 by Bull SAS
    All Rights Reserved