1
2 /*
3 This file contains routines for sorting integers and doubles with a permutation array.
4
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*/
10
11 #define SWAP(a,b,t) {t=a;a=b;b=t;}
12
PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)13 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)
14 {
15 PetscErrorCode ierr;
16 PetscInt tmp,i,vl,last;
17
18 PetscFunctionBegin;
19 if (right <= 1) {
20 if (right == 1) {
21 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
22 }
23 PetscFunctionReturn(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 ierr = PetscSortIntWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr);
33 ierr = PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr);
34 PetscFunctionReturn(0);
35 }
36
37 /*@
38 PetscSortIntWithPermutation - Computes the permutation of values that gives
39 a sorted sequence.
40
41 Not Collective
42
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.
47
48 Level: intermediate
49
50 Notes:
51 On output i is unchanged and idx[i] is the position of the i-th smallest index in i.
52
53 .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
54 @*/
PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])55 PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
56 {
57 PetscErrorCode ierr;
58 PetscInt j,k,tmp,ik;
59
60 PetscFunctionBegin;
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 ierr = PetscSortIntWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr);
73 }
74 PetscFunctionReturn(0);
75 }
76
77 /* ---------------------------------------------------------------------- */
78
PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)79 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
80 {
81 PetscReal vl;
82 PetscErrorCode ierr;
83 PetscInt tmp,i,last;
84
85 PetscFunctionBegin;
86 if (right <= 1) {
87 if (right == 1) {
88 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
89 }
90 PetscFunctionReturn(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 ierr = PetscSortRealWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr);
100 ierr = PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr);
101 PetscFunctionReturn(0);
102 }
103
104 /*@
105 PetscSortRealWithPermutation - Computes the permutation of values that gives
106 a sorted sequence.
107
108 Not Collective
109
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.
114
115 Level: intermediate
116
117 Notes:
118 i is unchanged on output.
119
120 .seealso: PetscSortReal(), PetscSortIntWithPermutation()
121 @*/
PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])122 PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
123 {
124 PetscErrorCode ierr;
125 PetscInt j,k,tmp;
126 PetscReal ik;
127
128 PetscFunctionBegin;
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 ierr = PetscSortRealWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr);
141 }
142 PetscFunctionReturn(0);
143 }
144
PetscSortStrWithPermutation_Private(const char * v[],PetscInt vdx[],PetscInt right)145 static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
146 {
147 PetscErrorCode ierr;
148 PetscInt tmp,i,last;
149 PetscBool gt;
150 const char *vl;
151
152 PetscFunctionBegin;
153 if (right <= 1) {
154 if (right == 1) {
155 ierr = PetscStrgrt(v[vdx[0]],v[vdx[1]],>);CHKERRQ(ierr);
156 if (gt) SWAP(vdx[0],vdx[1],tmp);
157 }
158 PetscFunctionReturn(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 ierr = PetscStrgrt(vl,v[vdx[i]],>);CHKERRQ(ierr);
165 if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
166 }
167 SWAP(vdx[0],vdx[last],tmp);
168 ierr = PetscSortStrWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr);
169 ierr = PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr);
170 PetscFunctionReturn(0);
171 }
172
173 /*@C
174 PetscSortStrWithPermutation - Computes the permutation of values that gives
175 a sorted sequence.
176
177 Not Collective
178
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.
183
184 Level: intermediate
185
186 Notes:
187 i is unchanged on output.
188
189 .seealso: PetscSortInt(), PetscSortRealWithPermutation()
190 @*/
PetscSortStrWithPermutation(PetscInt n,const char * i[],PetscInt idx[])191 PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
192 {
193 PetscErrorCode ierr;
194 PetscInt j,k,tmp;
195 const char *ik;
196 PetscBool gt;
197
198 PetscFunctionBegin;
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 ierr = PetscStrgrt(ik,i[idx[j]],>);CHKERRQ(ierr);
204 if (gt) {
205 SWAP(idx[k],idx[j],tmp);
206 ik = i[idx[k]];
207 }
208 }
209 }
210 } else {
211 ierr = PetscSortStrWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr);
212 }
213 PetscFunctionReturn(0);
214 }
215