Actual source code: sortip.c

      1: #define PETSC_DLL
      2: /*
      3:    This file contains routines for sorting integers and doubles with a permutation array.

      5:    The word "register"  in this code is used to identify data that is not
      6:    aliased.  For some compilers, this can cause the compiler to fail to
      7:    place inner-loop variables into registers.
      8:  */
     9:  #include petsc.h
     10:  #include petscsys.h

     12: #define SWAP(a,b,t) {t=a;a=b;b=t;}

     16: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)
     17: {
     19:   PetscInt       tmp,i,vl,last;

     22:   if (right <= 1) {
     23:     if (right == 1) {
     24:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
     25:     }
     26:     return(0);
     27:   }
     28:   SWAP(vdx[0],vdx[right/2],tmp);
     29:   vl   = v[vdx[0]];
     30:   last = 0;
     31:   for (i=1; i<=right; i++) {
     32:     if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
     33:   }
     34:   SWAP(vdx[0],vdx[last],tmp);
     35:   PetscSortIntWithPermutation_Private(v,vdx,last-1);
     36:   PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));
     37:   return(0);
     38: }

     42: /*@
     43:    PetscSortIntWithPermutation - Computes the permutation of values that gives
     44:    a sorted sequence.

     46:    Not Collective

     48:    Input Parameters:
     49: +  n  - number of values to sort
     50: .  i  - values to sort
     51: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

     53:    Level: intermediate

     55:    Notes:
     56:    i is unchanged on output.

     58:    Concepts: sorting^ints with permutation

     60: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
     61:  @*/
     62: PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
     63: {
     65:   PetscInt       j,k,tmp,ik;

     68:   if (n<8) {
     69:     for (k=0; k<n; k++) {
     70:       ik = i[idx[k]];
     71:       for (j=k+1; j<n; j++) {
     72:         if (ik > i[idx[j]]) {
     73:           SWAP(idx[k],idx[j],tmp);
     74:           ik = i[idx[k]];
     75:         }
     76:       }
     77:     }
     78:   } else {
     79:     PetscSortIntWithPermutation_Private(i,idx,n-1);
     80:   }
     81:   return(0);
     82: }

     84: /* ---------------------------------------------------------------------- */

     88: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
     89: {
     90:   PetscReal      vl;
     92:   PetscInt       tmp,i,last;

     95:   if (right <= 1) {
     96:     if (right == 1) {
     97:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
     98:     }
     99:     return(0);
    100:   }
    101:   SWAP(vdx[0],vdx[right/2],tmp);
    102:   vl   = v[vdx[0]];
    103:   last = 0;
    104:   for (i=1; i<=right; i++) {
    105:     if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
    106:   }
    107:   SWAP(vdx[0],vdx[last],tmp);
    108:   PetscSortRealWithPermutation_Private(v,vdx,last-1);
    109:   PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
    110:   return(0);
    111: }

    115: /*@
    116:    PetscSortRealWithPermutation - Computes the permutation of values that gives
    117:    a sorted sequence.

    119:    Not Collective

    121:    Input Parameters:
    122: +  n  - number of values to sort
    123: .  i  - values to sort
    124: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

    126:    Level: intermediate

    128:    Notes:
    129:    i is unchanged on output.

    131:    Concepts: sorting^doubles with permutation

    133: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
    134:  @*/
    135: PetscErrorCode PETSC_DLLEXPORT PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
    136: {
    138:   PetscInt       j,k,tmp;
    139:   PetscReal      ik;

    142:   if (n<8) {
    143:     for (k=0; k<n; k++) {
    144:       ik = i[idx[k]];
    145:       for (j=k+1; j<n; j++) {
    146:         if (ik > i[idx[j]]) {
    147:           SWAP(idx[k],idx[j],tmp);
    148:           ik = i[idx[k]];
    149:         }
    150:       }
    151:     }
    152:   } else {
    153:     PetscSortRealWithPermutation_Private(i,idx,n-1);
    154:   }
    155:   return(0);
    156: }

    160: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
    161: {
    163:   PetscInt       tmp,i,last;
    164:   PetscTruth     gt;
    165:   const char     *vl;

    168:   if (right <= 1) {
    169:     if (right == 1) {
    170:       PetscStrgrt(v[vdx[0]],v[vdx[1]],&gt);
    171:       if (gt) SWAP(vdx[0],vdx[1],tmp);
    172:     }
    173:     return(0);
    174:   }
    175:   SWAP(vdx[0],vdx[right/2],tmp);
    176:   vl   = v[vdx[0]];
    177:   last = 0;
    178:   for (i=1; i<=right; i++) {
    179:     PetscStrgrt(vl,v[vdx[i]],&gt);
    180:     if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
    181:   }
    182:   SWAP(vdx[0],vdx[last],tmp);
    183:   PetscSortStrWithPermutation_Private(v,vdx,last-1);
    184:   PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
    185:   return(0);
    186: }

    190: /*@C
    191:    PetscSortStrWithPermutation - Computes the permutation of values that gives
    192:    a sorted sequence.

    194:    Not Collective

    196:    Input Parameters:
    197: +  n  - number of values to sort
    198: .  i  - values to sort
    199: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

    201:    Level: intermediate

    203:    Notes:
    204:    i is unchanged on output.

    206:    Concepts: sorting^ints with permutation

    208: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
    209:  @*/
    210: PetscErrorCode PETSC_DLLEXPORT PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
    211: {
    213:   PetscInt       j,k,tmp;
    214:   const char     *ik;
    215:   PetscTruth     gt;

    218:   if (n<8) {
    219:     for (k=0; k<n; k++) {
    220:       ik = i[idx[k]];
    221:       for (j=k+1; j<n; j++) {
    222:         PetscStrgrt(ik,i[idx[j]],&gt);
    223:         if (gt) {
    224:           SWAP(idx[k],idx[j],tmp);
    225:           ik = i[idx[k]];
    226:         }
    227:       }
    228:     }
    229:   } else {
    230:     PetscSortStrWithPermutation_Private(i,idx,n-1);
    231:   }
    232:   return(0);
    233: }