Actual source code: sortip.c

petsc-3.8.2 2017-11-09
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:    Concepts: sorting^ints with permutation

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

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

 79: /* ---------------------------------------------------------------------- */

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

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

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

110:    Not Collective

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

117:    Level: intermediate

119:    Notes:
120:    i is unchanged on output.

122:    Concepts: sorting^doubles with permutation

124: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
125:  @*/
126: PetscErrorCode  PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
127: {
129:   PetscInt       j,k,tmp;
130:   PetscReal      ik;

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

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

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

177: /*@C
178:    PetscSortStrWithPermutation - Computes the permutation of values that gives
179:    a sorted sequence.

181:    Not Collective

183:    Input Parameters:
184: +  n  - number of values to sort
185: .  i  - values to sort
186: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

188:    Level: intermediate

190:    Notes:
191:    i is unchanged on output.

193:    Concepts: sorting^ints with permutation

195: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
196:  @*/
197: PetscErrorCode  PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
198: {
200:   PetscInt       j,k,tmp;
201:   const char     *ik;
202:   PetscBool      gt;

205:   if (n<8) {
206:     for (k=0; k<n; k++) {
207:       ik = i[idx[k]];
208:       for (j=k+1; j<n; j++) {
209:         PetscStrgrt(ik,i[idx[j]],&gt);
210:         if (gt) {
211:           SWAP(idx[k],idx[j],tmp);
212:           ik = i[idx[k]];
213:         }
214:       }
215:     }
216:   } else {
217:     PetscSortStrWithPermutation_Private(i,idx,n-1);
218:   }
219:   return(0);
220: }