Actual source code: sortip.c

petsc-master 2019-12-10
Report Typos and Errors

  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 <petscsys.h>

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

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

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

 37: /*@
 38:    PetscSortIntWithPermutation - Computes the permutation of values that gives
 39:    a sorted sequence.

 41:    Not Collective

 43:    Input Parameters:
 44: +  n  - number of values to sort
 45: .  i  - values to sort
 46: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

 48:    Level: intermediate

 50:    Notes:
 51:    On output i is unchanged and idx[i] is the position of the i-th smallest index in i.

 53: .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
 54:  @*/
 55: PetscErrorCode  PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
 56: {
 58:   PetscInt       j,k,tmp,ik;

 61:   if (n<8) {
 62:     for (k=0; k<n; k++) {
 63:       ik = i[idx[k]];
 64:       for (j=k+1; j<n; j++) {
 65:         if (ik > i[idx[j]]) {
 66:           SWAP(idx[k],idx[j],tmp);
 67:           ik = i[idx[k]];
 68:         }
 69:       }
 70:     }
 71:   } else {
 72:     PetscSortIntWithPermutation_Private(i,idx,n-1);
 73:   }
 74:   return(0);
 75: }

 77: /* ---------------------------------------------------------------------- */

 79: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
 80: {
 81:   PetscReal      vl;
 83:   PetscInt       tmp,i,last;

 86:   if (right <= 1) {
 87:     if (right == 1) {
 88:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
 89:     }
 90:     return(0);
 91:   }
 92:   SWAP(vdx[0],vdx[right/2],tmp);
 93:   vl   = v[vdx[0]];
 94:   last = 0;
 95:   for (i=1; i<=right; i++) {
 96:     if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
 97:   }
 98:   SWAP(vdx[0],vdx[last],tmp);
 99:   PetscSortRealWithPermutation_Private(v,vdx,last-1);
100:   PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
101:   return(0);
102: }

104: /*@
105:    PetscSortRealWithPermutation - Computes the permutation of values that gives
106:    a sorted sequence.

108:    Not Collective

110:    Input Parameters:
111: +  n  - number of values to sort
112: .  i  - values to sort
113: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

115:    Level: intermediate

117:    Notes:
118:    i is unchanged on output.

120: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
121:  @*/
122: PetscErrorCode  PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
123: {
125:   PetscInt       j,k,tmp;
126:   PetscReal      ik;

129:   if (n<8) {
130:     for (k=0; k<n; k++) {
131:       ik = i[idx[k]];
132:       for (j=k+1; j<n; j++) {
133:         if (ik > i[idx[j]]) {
134:           SWAP(idx[k],idx[j],tmp);
135:           ik = i[idx[k]];
136:         }
137:       }
138:     }
139:   } else {
140:     PetscSortRealWithPermutation_Private(i,idx,n-1);
141:   }
142:   return(0);
143: }

145: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
146: {
148:   PetscInt       tmp,i,last;
149:   PetscBool      gt;
150:   const char     *vl;

153:   if (right <= 1) {
154:     if (right == 1) {
155:       PetscStrgrt(v[vdx[0]],v[vdx[1]],&gt);
156:       if (gt) SWAP(vdx[0],vdx[1],tmp);
157:     }
158:     return(0);
159:   }
160:   SWAP(vdx[0],vdx[right/2],tmp);
161:   vl   = v[vdx[0]];
162:   last = 0;
163:   for (i=1; i<=right; i++) {
164:     PetscStrgrt(vl,v[vdx[i]],&gt);
165:     if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
166:   }
167:   SWAP(vdx[0],vdx[last],tmp);
168:   PetscSortStrWithPermutation_Private(v,vdx,last-1);
169:   PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
170:   return(0);
171: }

173: /*@C
174:    PetscSortStrWithPermutation - Computes the permutation of values that gives
175:    a sorted sequence.

177:    Not Collective

179:    Input Parameters:
180: +  n  - number of values to sort
181: .  i  - values to sort
182: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

184:    Level: intermediate

186:    Notes:
187:    i is unchanged on output.

189: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
190:  @*/
191: PetscErrorCode  PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
192: {
194:   PetscInt       j,k,tmp;
195:   const char     *ik;
196:   PetscBool      gt;

199:   if (n<8) {
200:     for (k=0; k<n; k++) {
201:       ik = i[idx[k]];
202:       for (j=k+1; j<n; j++) {
203:         PetscStrgrt(ik,i[idx[j]],&gt);
204:         if (gt) {
205:           SWAP(idx[k],idx[j],tmp);
206:           ik = i[idx[k]];
207:         }
208:       }
209:     }
210:   } else {
211:     PetscSortStrWithPermutation_Private(i,idx,n-1);
212:   }
213:   return(0);
214: }