Actual source code: sortip.c


  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: {
 15:   PetscInt       tmp,i,vl,last;

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

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

 39:    Not Collective

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

 46:    Level: intermediate

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

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

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

 73: /* ---------------------------------------------------------------------- */

 75: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
 76: {
 77:   PetscReal      vl;
 78:   PetscInt       tmp,i,last;

 80:   if (right <= 1) {
 81:     if (right == 1) {
 82:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
 83:     }
 84:     return 0;
 85:   }
 86:   SWAP(vdx[0],vdx[right/2],tmp);
 87:   vl   = v[vdx[0]];
 88:   last = 0;
 89:   for (i=1; i<=right; i++) {
 90:     if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
 91:   }
 92:   SWAP(vdx[0],vdx[last],tmp);
 93:   PetscSortRealWithPermutation_Private(v,vdx,last-1);
 94:   PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
 95:   return 0;
 96: }

 98: /*@
 99:    PetscSortRealWithPermutation - Computes the permutation of values that gives
100:    a sorted sequence.

102:    Not Collective

104:    Input Parameters:
105: +  n  - number of values to sort
106: .  i  - values to sort
107: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

109:    Level: intermediate

111:    Notes:
112:    i is unchanged on output.

114: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
115:  @*/
116: PetscErrorCode  PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
117: {
118:   PetscInt       j,k,tmp;
119:   PetscReal      ik;

121:   if (n<8) {
122:     for (k=0; k<n; k++) {
123:       ik = i[idx[k]];
124:       for (j=k+1; j<n; j++) {
125:         if (ik > i[idx[j]]) {
126:           SWAP(idx[k],idx[j],tmp);
127:           ik = i[idx[k]];
128:         }
129:       }
130:     }
131:   } else {
132:     PetscSortRealWithPermutation_Private(i,idx,n-1);
133:   }
134:   return 0;
135: }

137: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
138: {
139:   PetscInt       tmp,i,last;
140:   PetscBool      gt;
141:   const char     *vl;

143:   if (right <= 1) {
144:     if (right == 1) {
145:       PetscStrgrt(v[vdx[0]],v[vdx[1]],&gt);
146:       if (gt) SWAP(vdx[0],vdx[1],tmp);
147:     }
148:     return 0;
149:   }
150:   SWAP(vdx[0],vdx[right/2],tmp);
151:   vl   = v[vdx[0]];
152:   last = 0;
153:   for (i=1; i<=right; i++) {
154:     PetscStrgrt(vl,v[vdx[i]],&gt);
155:     if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
156:   }
157:   SWAP(vdx[0],vdx[last],tmp);
158:   PetscSortStrWithPermutation_Private(v,vdx,last-1);
159:   PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
160:   return 0;
161: }

163: /*@C
164:    PetscSortStrWithPermutation - Computes the permutation of values that gives
165:    a sorted sequence.

167:    Not Collective

169:    Input Parameters:
170: +  n  - number of values to sort
171: .  i  - values to sort
172: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

174:    Level: intermediate

176:    Notes:
177:    i is unchanged on output.

179: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
180:  @*/
181: PetscErrorCode  PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
182: {
183:   PetscInt       j,k,tmp;
184:   const char     *ik;
185:   PetscBool      gt;

187:   if (n<8) {
188:     for (k=0; k<n; k++) {
189:       ik = i[idx[k]];
190:       for (j=k+1; j<n; j++) {
191:         PetscStrgrt(ik,i[idx[j]],&gt);
192:         if (gt) {
193:           SWAP(idx[k],idx[j],tmp);
194:           ik = i[idx[k]];
195:         }
196:       }
197:     }
198:   } else {
199:     PetscSortStrWithPermutation_Private(i,idx,n-1);
200:   }
201:   return 0;
202: }