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>                /*I  "petscsys.h"  I*/

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

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

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

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

 45:    Not Collective

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

 52:    Level: intermediate

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

 57:    Concepts: sorting^ints with permutation

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

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

 83: /* ---------------------------------------------------------------------- */

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

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

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

118:    Not Collective

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

125:    Level: intermediate

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

130:    Concepts: sorting^doubles with permutation

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

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

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

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

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

193:    Not Collective

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

200:    Level: intermediate

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

205:    Concepts: sorting^ints with permutation

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

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