Actual source code: sortip.c

petsc-3.9.2 2018-05-20
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: }
```