az_sort.c

并行解法器,功能强大

/*====================================================================
 * ------------------------
 * | CVS File Information |
 * ------------------------
 *
 * $RCSfile: az_sort.c,v $
 *
 * $Author: tuminaro $
 *
 * $Date: 1999/10/07 00:07:43 $
 *
 * $Revision: 1.15 $
 *
 * $Name:  $
 *====================================================================*/
#ifndef lint
static char rcsid[] = "$Id: az_sort.c,v 1.15 1999/10/07 00:07:43 tuminaro Exp $";
#endif


/*******************************************************************************
 * Copyright 1995, Sandia Corporation.  The United States Government retains a *
 * nonexclusive license in this software as prescribed in AL 88-1 and AL 91-7. *
 * Export of this program may require a license from the United States         *
 * Government.                                                                 *
 ******************************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include "az_aztec.h"
#include <string.h>

int divider;
int type_size;

/* ----------------- External Definitions ---------------------------------*/

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

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

/* ------------------------------------------------------------------------*/

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

int AZ_quick_find(int key, int list[], int length, int shift, int bins[])

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

  Find 'key' in 'list' and return the indices number. On exit, AZ_find_index()
  returns:
            -1 ==> key not found
             i ==> list[i] = key

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

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

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

  key:             Element to be search for in list.

  list:            List (assumed to be in ascending order) to be searched.

  length:          Length of list.

  shift:           Integer used to compute an indices into bins[]. Computed by
                   AZ_init_quick_find().

  bins:            Used to obtain a sublist where should contain 'key'. In
                   particular, list[bins[k] ... bins[k+1]-1] should contain
                   'key'. Computed by AZ_init_quick_find().

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

{

  /* local variables */

  int i, loc, oldkey;

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

  if (length == 0)            return -1;
  if (key > list[length - 1]) return -1;

  oldkey = key;
  key   -= list[0];

  if (key < 0) return -1;

  loc = key >> shift;

  i = AZ_find_index(oldkey, &(list[bins[loc]]), bins[loc + 1] - bins[loc]);

  if (i == -1) return -1;

  return (i + bins[loc]);

} /* AZ_quick_find */

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

void AZ_init_quick_find(int list[], int length, int *shift, int *bins)

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

  The value 'shift' and the array 'bins' are initialized so that subsequent
  calls to AZ_quick_find() will work properly. In particular, the array 'bins'
  and which should be 1/4 the size of list is set so that

    1)  range>>shift     > length/4
              and
        range>>(shift+1) < length/4

    where range = list[length-1] - list[0].

    2)  list[j] = value  ==> bins[k] <= j < bins[k+1]
                             where k = (value-list[0]) >> shift

 Note: list[] is sorted in ascending order. This routine is used in conjunction
 with AZ_quick_find(). The idea is to use bins[] to get a good initial guess as
 to the location of 'value' in list[].

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

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

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

  list:            List (assumed to be in ascending order) to be searched.

  length:          Length of list.

  shift:           Integer used to compute an indices into bins[]. Computed by
                   AZ_init_quick_find().

  bins:            Used to obtain a sublist where should contain 'key'. In
                   particular, list[bins[k] ... bins[k+1]-1] should contain
                   'key'. Computed by AZ_init_quick_find().

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

{

  /* local variables */

  register int i, j = 0;
  int          range, temp;

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

  if (length == 0) return;

  range  = list[length - 1] - list[0];
  *shift = 0;

  while ((range >> (*shift)) > length / 4)
    (*shift)++;

  bins[j++] = 0;

  for (i = 0; i < length; i++) {
    temp = list[i] - list[0];

    while ((temp >> (*shift)) >= j)
      bins[j++] = i;
  }

  bins[j] = length;

} /* AZ_init_quick_find */

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

void AZ_sort(int list[], int N, int list2[], double list3[])

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

  This routine was taken from Knuth: Sorting and Searching. It puts the input
  data list into a heap and then sorts it.

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

  Return code:     double, maximum value in vector 'vec'
  ============

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

  list:            On input, values to be sorted. On output, sorted values
                   (i.e., list[i] <= list[i+1]).

  N:               length of vector 'vec'.

  list2:           If on input,
                   a) list2 = NULL: it is unchanged on output,
                   b) list2 is a list associated with 'list':
                   on output, if list[k] on input is now element 'j' on output,
                   list2[j] on output is list2[k].

  list3:           If on input,
                   a) list3 = NULL: it is unchanged on output,
                   b) list3 is a list associated with 'list':
                   on output, list3[j] is assigned the input value of list3[k],
                   if list[j] has been assigned the input value of list[k].

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

{

  /* local variables */

  int    l, r, RR, K, j, i, flag;
  int    RR2;
  double RR3;

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

  if (N <= 1) return;

  l   = N / 2 + 1;
  r   = N - 1;
  l   = l - 1;
  RR  = list[l - 1];
  K   = list[l - 1];

  if ((list2 != NULL) && (list3 != NULL)) {
    RR2 = list2[l - 1];
    RR3 = list3[l - 1];
    while (r != 0) {
      j = l;
      flag = 1;

      while (flag == 1) {
        i = j;
        j = j + j;

        if (j > r + 1)
          flag = 0;
        else {
          if (j < r + 1)
            if (list[j] > list[j - 1]) j = j + 1;

          if (list[j - 1] > K) {
            list[ i - 1] = list[ j - 1];
            list2[i - 1] = list2[j - 1];
            list3[i - 1] = list3[j - 1];
          }
          else {
            flag = 0;
          }
        }
      }

      list[ i - 1] = RR;
      list2[i - 1] = RR2;
      list3[i - 1] = RR3;

      if (l == 1) {
        RR  = list [r];
        RR2 = list2[r];
        RR3 = list3[r];

        K = list[r];
        list[r ] = list[0];
        list2[r] = list2[0];
        list3[r] = list3[0];
        r = r - 1;
      }
      else {
        l   = l - 1;
        RR  = list[ l - 1];
        RR2 = list2[l - 1];
        RR3 = list3[l - 1];
        K   = list[l - 1];
      }
    }

    list[ 0] = RR;
    list2[0] = RR2;
    list3[0] = RR3;
  }
  else if (list2 != NULL) {
    RR2 = list2[l - 1];
    while (r != 0) {
      j = l;
      flag = 1;

      while (flag == 1) {
        i = j;
        j = j + j;

        if (j > r + 1)
          flag = 0;
        else {
          if (j < r + 1)
            if (list[j] > list[j - 1]) j = j + 1;

          if (list[j - 1] > K) {
            list[ i - 1] = list[ j - 1];
            list2[i - 1] = list2[j - 1];
          }
          else {
            flag = 0;
          }
        }
      }

      list[ i - 1] = RR;
      list2[i - 1] = RR2;

      if (l == 1) {
        RR  = list [r];
        RR2 = list2[r];

        K = list[r];
        list[r ] = list[0];
        list2[r] = list2[0];
        r = r - 1;
      }
      else {
        l   = l - 1;
        RR  = list[ l - 1];
        RR2 = list2[l - 1];
        K   = list[l - 1];
      }
    }

    list[ 0] = RR;
    list2[0] = RR2;
  }
  else if (list3 != NULL) {
    RR3 = list3[l - 1];
    while (r != 0) {
      j = l;
      flag = 1;

      while (flag == 1) {
        i = j;
        j = j + j;

        if (j > r + 1)
          flag = 0;
        else {
          if (j < r + 1)
            if (list[j] > list[j - 1]) j = j + 1;

          if (list[j - 1] > K) {
            list[ i - 1] = list[ j - 1];
            list3[i - 1] = list3[j - 1];
          }
          else {
            flag = 0;
          }
        }
      }

      list[ i - 1] = RR;
      list3[i - 1] = RR3;

      if (l == 1) {
        RR  = list [r];
        RR3 = list3[r];

        K = list[r];
        list[r ] = list[0];
        list3[r] = list3[0];
        r = r - 1;
      }
      else {
        l   = l - 1;
        RR  = list[ l - 1];
        RR3 = list3[l - 1];
        K   = list[l - 1];
      }
    }

    list[ 0] = RR;
    list3[0] = RR3;

  }
  else {
    while (r != 0) {
      j = l;
      flag = 1;

      while (flag == 1) {
        i = j;
        j = j + j;

        if (j > r + 1)
          flag = 0;
        else {
          if (j < r + 1)
            if (list[j] > list[j - 1]) j = j + 1;

          if (list[j - 1] > K) {
            list[ i - 1] = list[ j - 1];
          }
          else {
            flag = 0;
          }
        }
      }

      list[ i - 1] = RR;

      if (l == 1) {
        RR  = list [r];

        K = list[r];
        list[r ] = list[0];
        r = r - 1;
      }
      else {
        l   = l - 1;
        RR  = list[ l - 1];
        K   = list[l - 1];
      }
    }

    list[ 0] = RR;
  }

} /* AZ_sort */

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

void AZ_sortqlists(char a[], int b[], int indices[], int length, int type_length,
                int ind_length)

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

  Sort the set of sublists in a[]. In particular a[] contains a sequence of k
  sublists (the length of sublist j is given by b[j] unless b=0 then the list is
  of size 1). The array indices[] contains the numbers 0 to k-1. On output, the
  sublists in a[] are ordered such that the jth list on input becomes the
  indices[j]th list on output.

  IMPORTANT: This routine assumes that indices[] contains 2 sequencies of numbers
  that are ordered but intertwined. For example,

         indices:   4 5 0 6 1 2 3 7
         seq 1 =>     0   1 2 3
         seq 2 => 4 5   6       7

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

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

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

  a:               Set of lists to be sorted.
                   List 0 consists of a[0-->b[0]-1], list 1 consists of
                   a[b[0]-->b[0]+b[1]-1], list 2 consists of
                   a[b[0]+b[1]-->b[0]+b[1]+b[2]-1], etc.
                   On output, a[] is reordered such that list j on input
                   becomes list indices[j].

  b:               b[i] is the length of list i in a[]. If b = 0 then all the
                   sublists are of length 1.

  indices:           Contains the numbers 0 --> number of lists. It is assumed
                   that indices[] contains 2 sequencies of numbers that are
                   ordered but intertwined as discussed in the comments above.
                   On output, list j on input becomes list indices[j].