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  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  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  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: }