az_sort.c

并行解法器,功能强大

  length:          The length of a[].

  type_length:     This is the size of each element in a[]. Normally, if we are
                   sorting integers ... type_length = 4.

  ind_length:      Number of sublists to be sorted.

*******************************************************************************/

{

  /* local variables */

  char *abuffer = 0;
  int   next_ind = 0;
  int   i, midpoint, real_lists, the_first, buf_len;

  /**************************** execution begins ******************************/

  type_size = type_length;

  /*
   * Divider is the indices of the first sublist in sequence 2.  In the example
   * above, divider = 4.
   */

  divider = -1;
  for (i = 0; i < ind_length; i++) {
    if (indices[i] != next_ind) {
      divider = indices[i];
      break;
    }

    next_ind++;
  }

  if (divider != -1) {

    /* allocate a temporary buffer ... try and make it as big as possible */

    buf_len = type_length * length/2;
    while (abuffer == 0) {
      buf_len = buf_len / 2;
      abuffer = (char *) AZ_allocate(buf_len*sizeof(char));
    }

    /*
     * Effectively merge together lists that are already in the correct order.
     * That is, two consecutive lists which are also to appear consecutively on
     * output are grouped together. This grouping is accomplished by changing
     * the arrays: indices and b.
     */

    AZ_change_it(indices, ind_length, &the_first, &real_lists, b);

    /* now sort the merged sublists */

    if (type_length == 4)
      AZ_sort_ints(a, indices, 0, type_length*length-1, b, &midpoint, real_lists,
                   abuffer, buf_len, the_first, 0);
    else if (type_length == 8)
      AZ_sort_dble(a, indices, 0, type_length*length-1, b, &midpoint, real_lists,
                   abuffer, buf_len, the_first, 0);
    else
      (void) fprintf(stderr, "ERROR: unknown type size in AZ_sortqlists\n");

    AZ_free(abuffer);

    /*
     * Reverse the changes made by AZ_change_it() so that the arrays: indices and
     * b have the same values that they had before AZ_change_it()
     */

    AZ_reverse_it(indices, ind_length, the_first, real_lists, b);
  }

} /* AZ_sortqlists */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void move_dble(double first[], double second[], unsigned int first_length,
               unsigned int second_length)

/*******************************************************************************

  Swap the contents of the arrays 'first' and 'second'. NOTE: THE ARRAY 'second'
  FOLLOWS IMMEDIATELY AFTER THE ARRAY 'first' IN STORAGE. For example,

          ----------------------------------------------
          |first                             |second   |
          ----------------------------------------------

  On output, the two arrays are swapped.

          ----------------------------------------------
          |second   |first                             |
          ----------------------------------------------

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  first:           Pointer to first array (as illustrated above).

  second:          Pointer to second array (as illustrated above).

  first_length:    Length of array 'first'.

  second_length:   Length of array 'second'.

*******************************************************************************/

{

  /* local variables */

  int    working = 1, tlength, i;
  double temp;

  /**************************** execution begins ******************************/

  if ((first_length == 0) || (second_length == 0)) working = 0;
  while (working) {
    if (first_length < second_length) tlength = first_length;
    else                              tlength = second_length;

    for (i = 0; i < tlength; i++) {
      temp      = first[i];
      first[i]  = second[i];
      second[i] = temp;
    }

    if (first_length  > second_length) {
      first         = &(first[second_length]);
      first_length -= second_length;
    }
    else if (first_length < second_length) {
      first          = &(first[first_length]);
      second         = &(second[first_length]);
      second_length -= first_length;
    }
    else
      working = 0;
  }

} /* move_dble */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void move_ints(int first[], int second[], unsigned int first_length, 
               unsigned int second_length)

/*******************************************************************************

  Swap the contents of the arrays 'first' and 'second'. NOTE: THE ARRAY 'second'
  FOLLOWS IMMEDIATELY AFTER THE ARRAY 'first' IN STORAGE. For example,

          ----------------------------------------------
          |first                             |second   |
          ----------------------------------------------

  On output, the two arrays are swapped.

          ----------------------------------------------
          |second   |first                             |
          ----------------------------------------------

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  first:           Pointer to first array (as illustrated above).

  second:          Pointer to second array (as illustrated above).

  first_length:    Length of array 'first'.

  second_length:   Length of array 'second'.

*******************************************************************************/

{

  /* local variables */

  int i, tlength, temp, working = 1;

  /**************************** execution begins ******************************/

  if ((first_length == 0) || (second_length == 0)) working = 0;
  while (working) {
    if (first_length < second_length) tlength = first_length;
    else                              tlength = second_length;

    for (i = 0; i < tlength; i++) {
      temp      = first[i];
      first[i]  = second[i];
      second[i] = temp;
    }

    if (first_length  > second_length) {
      first         = &(first[second_length]);
      first_length -= second_length;
    }
    else if (first_length < second_length) {
      first          = &(first[first_length]);
      second         = &(second[first_length]);
      second_length -= first_length;
    }
    else
      working = 0;
  }

} /* move_ints */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void AZ_change_it(int indx[], int length, int *first, int *total, int b[])

/*******************************************************************************

  Modify indx[] and b[] to effectively merge the lists found in indx[]. That is,
  indx[] and b[] will correspond to a set of merged lists where all consecutive
  elements belonging to the same subsequence (see AZ_sortqlists() comments) are
  grouped together.

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  indx:            On input, indx[] contains the numbers 0 --> 'length'-1. It is
                   assumed that indices[] contains 2 sequencies of numbers that
                   are ordered but intertwined as discussed in the comments for
                   AZ_sortqlists(). After AZ_sortqlists() reorders list j on
                   input will become list indices[j].
                   On output to AZ_change_it(),
                     indx[i] - indx[i-1] i > 0
                     indx[i]             i = 0
                   gives the length of the ith merged list.

  length:          The length of indx[].

  first:           Indicates if the first merged list belongs to the first
                   subsequence or the second subsequence. In particular ...
                   On output,
                     first = 0   ==> the first merged list will be the first
                                     list after sorting.
                     first = 1   ==> the first merged list will appear
                                     immediately after the first subsequence
                                     when the sorting is finished.
                   NOTE: IT IS ASSUMED THAT THE MERGED LISTS ALTERNATE. That is,
                   if the first merged lists belongs to the first subsequence,
                   then all the even merged lists belong to the second
                   subsequence and all the odd merged lists belong to the first
                   subsequence.

  total:           On output, number of merged lists.

  b:               On input, b[i] indicates the length of list i.
                   On output,
                       b[indx[i-1]]     i > 0
                       b[i]             i = 0
                  gives the length of merged list i.

*******************************************************************************/

{

  /* local variables */

  int i, ii = 0, count = 0;

  /**************************** execution begins ******************************/

  if (indx[0] == 0) *first = 0;
  else              *first = 1;

  for (i = 1; i < length; i++) {
    if (indx[i-1] < divider) {
      if (indx[i] >= divider)
        indx[ii++] = i;
    }
    else if (indx[i] < divider)
      indx[ii++] = i;
  }

  *total         = ii + 1;
  indx[*total-1] = length;

  if (b != 0) {
    for (i = 1; i < *total; i++) {
      count = 0;

      for (ii = indx[i-1]; ii < indx[i]; ii++)
        count += b[ii];

      count       *= type_size;
      b[indx[i-1]] = count;
    }

    count = 0;
    for (ii = 0; ii < indx[0]; ii++)
      count += b[ii];

    count *= type_size;
    b[0]   = count;
  }

} /* AZ_change_it */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void AZ_reverse_it(int indx[], int length, int first, int total, int b[])

/*******************************************************************************

  Reverse the changes performed in AZ_change_it(). That is, the arrays 'indx'
  and 'b' should be identical before and after the following code sequence:

        AZ_change_it(indx, b)
        AZ_reverse_it(indx, b)

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  indx:            On input, indx[] contains the numbers 0 --> 'length'-1. It is
                   assumed that indices[] contains 2 sequencies of numbers that
                   are ordered but intertwined as discussed in the comments for
                   AZ_sortqlists(). After AZ_sortqlists() reorders list j on
                   input will become list indices[j].
                   On output to AZ_change_it(),
                     indx[i] - indx[i-1] i > 0
                     indx[i]             i = 0
                   gives the length of the ith merged list.

  length:          The length of indx[].

  first:           Indicates if the first merged list belongs to the first
                   subsequence or the second subsequence. In particular ...
                   On output,
                     first = 0   ==> the first merged list will be the first
                                     list after sorting.
                     first = 1   ==> the first merged list will appear
                                     immediately after the first subsequence
                                     when the sorting is finished.
                   NOTE: IT IS ASSUMED THAT THE MERGED LISTS ALTERNATE. That is,
                   if the first merged lists belongs to the first subsequence,
                   then all the even merged lists belong to the second
                   subsequence and all the odd merged lists belong to the first
                   subsequence.

  total:           On output, number of merged lists.

  b:               On input, b[i] indicates the length of list i.
                   On output,
                       b[indx[i-1]]     i > 0
                       b[i]             i = 0
                  gives the length of merged list i.

*******************************************************************************/

{

  /* local variables */

  int i, j, ii, count;
  int seq1, seq2;
  int cur, toggle, sub_length;

  /**************************** execution begins ******************************/

  if (b != 0) {
    count = 0;
    for (ii = 1; ii < indx[0]; ii++)
      count += b[ii];
    count *= type_size;

    b[0] = (b[0] - count) / type_size;

    for (i = 1; i < total; i++) {
      count = 0;
      for (ii = indx[i-1]+1; ii < indx[i]; ii++)
        count += b[ii];
      count *= type_size;

      b[indx[i-1]] = (b[indx[i-1]] - count) / type_size;
    }
  }

  seq1 = divider - 1;
  seq2 = cur = length - 1;

  if (first == 0) {
    if (total%2 == 0) toggle = 1;
    else              toggle = 0;
  }
  else {
    if (total%2 == 0) toggle = 0;
    else              toggle = 1;
  }

  for (i = total-1; i > 0; i--) {
    sub_length = indx[i] - indx[i-1];

    if (toggle)
      for (j = 0; j < sub_length; j++)
        indx[cur--] = seq2--;
    else
      for (j = 0; j < sub_length; j++)
        indx[cur--] = seq1--;

    toggle = 1 - toggle;
  }

  sub_length = indx[0];

  if (toggle)
    for (j = 0; j < sub_length; j++)
      indx[cur--] = seq2--;
  else
    for (j = 0; j < sub_length; j++ )
      indx[cur--] = seq1--;

} /* AZ_reverse_it */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void AZ_sort_dble(char a[], int indx[], int start, int end, int b[], int *mid,
               int real_lists, char buffer[], int buf_len, int the_first,
               int ind_indices)

/*******************************************************************************

  Sort the set of merged lists in a[]. In particular a[] contains a sequence
  of 'real_lists' merged lists of the form
        list 0   list 1  list 2   list 3
  Each merged list is in fact comprised of a bunch of sublists which consist
  of double precision numbers.  On output, AZ_sort_dble will put all the even
  lists first followed by all the odd lists (e.g. list 0, list 2, list4, ...
  list1, list3, list 5, ...) if 'the_first' == 0. Otherwise, the odd lists are
  first followed by the even lists.

  The algorithm proceeds as follows:
      1) sort as many merged lists as we can using a buffer (of size buf_len)
         and simply copy what does not belong in the first subsequence
         (either even or odd depending on 'the_first') into the buffer.
      2) split the remaining merged lists into 2 sublists.
      3) use AZ_sort_dble() recursively for each of the 2 sublists.
      4) merge the results of the 2 recursive calls so that the entire
         list is sorted.

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============