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]],>);
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]],>);
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]],>);
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: }