Actual source code: sortip.c

petsc-master 2020-09-19
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: }
```