1 #define PETSC_DLL 2 /* 3 This file contains routines for sorting integers. Values are sorted in place. 4 */ 5 #include "petscsys.h" /*I "petscsys.h" I*/ 6 7 #define SWAP(a,b,t) {t=a;a=b;b=t;} 8 9 #define MEDIAN(v,right) \ 10 (v[0]<v[right/2] \ 11 ? (v[right/2]<v[right] \ 12 ? right/2 \ 13 : (v[0]<v[right] ? right : 0)) \ 14 : (v[right]<v[right/2] \ 15 ? right/2 \ 16 : (v[0]<v[right] ? 0 : right))) 17 18 /* -----------------------------------------------------------------------*/ 19 20 #undef __FUNCT__ 21 #define __FUNCT__ "PetscSortInt_Private" 22 /* 23 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 24 Assumes 0 origin for v, number of elements = right+1 (right is index of 25 right-most member). 26 */ 27 static void PetscSortInt_Private(PetscInt *v,PetscInt right) 28 { 29 PetscInt i,j,pivot,tmp; 30 31 if (right <= 1) { 32 if (right == 1) { 33 if (v[0] > v[1]) SWAP(v[0],v[1],tmp); 34 } 35 return; 36 } 37 i = MEDIAN(v,right); /* Choose a pivot */ 38 SWAP(v[0],v[i],tmp); /* Move it out of the way */ 39 pivot = v[0]; 40 for (i=0,j=right+1;;) { 41 while (++i < j && v[i] <= pivot); /* Scan from the left */ 42 while (v[--j] > pivot); /* Scan from the right */ 43 if (i >= j) break; 44 SWAP(v[i],v[j],tmp); 45 } 46 SWAP(v[0],v[j],tmp); /* Put pivot back in place. */ 47 PetscSortInt_Private(v,j-1); 48 PetscSortInt_Private(v+j+1,right-(j+1)); 49 } 50 51 #undef __FUNCT__ 52 #define __FUNCT__ "PetscSortInt" 53 /*@ 54 PetscSortInt - Sorts an array of integers in place in increasing order. 55 56 Not Collective 57 58 Input Parameters: 59 + n - number of values 60 - i - array of integers 61 62 Level: intermediate 63 64 Concepts: sorting^ints 65 66 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 67 @*/ 68 PetscErrorCode PETSCSYS_DLLEXPORT PetscSortInt(PetscInt n,PetscInt i[]) 69 { 70 PetscInt j,k,tmp,ik; 71 72 PetscFunctionBegin; 73 if (n<8) { 74 for (k=0; k<n; k++) { 75 ik = i[k]; 76 for (j=k+1; j<n; j++) { 77 if (ik > i[j]) { 78 SWAP(i[k],i[j],tmp); 79 ik = i[k]; 80 } 81 } 82 } 83 } else { 84 PetscSortInt_Private(i,n-1); 85 } 86 PetscFunctionReturn(0); 87 } 88 89 #undef __FUNCT__ 90 #define __FUNCT__ "PetscSortRemoveDupsInt" 91 /*@ 92 PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries 93 94 Not Collective 95 96 Input Parameters: 97 + n - number of values 98 - ii - array of integers 99 100 Output Parameter: 101 . n - number of non-redundant values 102 103 Level: intermediate 104 105 Concepts: sorting^ints 106 107 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 108 @*/ 109 PetscErrorCode PETSCSYS_DLLEXPORT PetscSortRemoveDupsInt(PetscInt *n,PetscInt ii[]) 110 { 111 PetscErrorCode ierr; 112 PetscInt i,s = 0,N = *n, b = 0; 113 114 PetscFunctionBegin; 115 ierr = PetscSortInt(N,ii);CHKERRQ(ierr); 116 for (i=0; i<N-1; i++) { 117 if (ii[b+s+1] == ii[b]) {ii[b+1] = ii[b+s+2]; s++;} 118 else b++; 119 } 120 *n = N - s; 121 PetscFunctionReturn(0); 122 } 123 124 125 /* -----------------------------------------------------------------------*/ 126 #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;} 127 128 #undef __FUNCT__ 129 #define __FUNCT__ "PetscSortIntWithArray_Private" 130 /* 131 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 132 Assumes 0 origin for v, number of elements = right+1 (right is index of 133 right-most member). 134 */ 135 static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right) 136 { 137 PetscErrorCode ierr; 138 PetscInt i,vl,last,tmp; 139 140 PetscFunctionBegin; 141 if (right <= 1) { 142 if (right == 1) { 143 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 144 } 145 PetscFunctionReturn(0); 146 } 147 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 148 vl = v[0]; 149 last = 0; 150 for (i=1; i<=right; i++) { 151 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 152 } 153 SWAP2(v[0],v[last],V[0],V[last],tmp); 154 ierr = PetscSortIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 155 ierr = PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 156 PetscFunctionReturn(0); 157 } 158 159 #undef __FUNCT__ 160 #define __FUNCT__ "PetscSortIntWithArray" 161 /*@ 162 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 163 changes a second array to match the sorted first array. 164 165 Not Collective 166 167 Input Parameters: 168 + n - number of values 169 . i - array of integers 170 - I - second array of integers 171 172 Level: intermediate 173 174 Concepts: sorting^ints with array 175 176 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 177 @*/ 178 PetscErrorCode PETSCSYS_DLLEXPORT PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[]) 179 { 180 PetscErrorCode ierr; 181 PetscInt j,k,tmp,ik; 182 183 PetscFunctionBegin; 184 if (n<8) { 185 for (k=0; k<n; k++) { 186 ik = i[k]; 187 for (j=k+1; j<n; j++) { 188 if (ik > i[j]) { 189 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 190 ik = i[k]; 191 } 192 } 193 } 194 } else { 195 ierr = PetscSortIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 196 } 197 PetscFunctionReturn(0); 198 } 199 200 #undef __FUNCT__ 201 #define __FUNCT__ "PetscSortMPIIntWithArray_Private" 202 /* 203 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 204 Assumes 0 origin for v, number of elements = right+1 (right is index of 205 right-most member). 206 */ 207 static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right) 208 { 209 PetscErrorCode ierr; 210 PetscMPIInt i,vl,last,tmp; 211 212 PetscFunctionBegin; 213 if (right <= 1) { 214 if (right == 1) { 215 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 216 } 217 PetscFunctionReturn(0); 218 } 219 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 220 vl = v[0]; 221 last = 0; 222 for (i=1; i<=right; i++) { 223 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 224 } 225 SWAP2(v[0],v[last],V[0],V[last],tmp); 226 ierr = PetscSortMPIIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 227 ierr = PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 228 PetscFunctionReturn(0); 229 } 230 231 #undef __FUNCT__ 232 #define __FUNCT__ "PetscSortMPIIntWithArray" 233 /*@ 234 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 235 changes a second array to match the sorted first array. 236 237 Not Collective 238 239 Input Parameters: 240 + n - number of values 241 . i - array of integers 242 - I - second array of integers 243 244 Level: intermediate 245 246 Concepts: sorting^ints with array 247 248 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 249 @*/ 250 PetscErrorCode PETSCSYS_DLLEXPORT PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[]) 251 { 252 PetscErrorCode ierr; 253 PetscMPIInt j,k,tmp,ik; 254 255 PetscFunctionBegin; 256 if (n<8) { 257 for (k=0; k<n; k++) { 258 ik = i[k]; 259 for (j=k+1; j<n; j++) { 260 if (ik > i[j]) { 261 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 262 ik = i[k]; 263 } 264 } 265 } 266 } else { 267 ierr = PetscSortMPIIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 268 } 269 PetscFunctionReturn(0); 270 } 271 272 /* -----------------------------------------------------------------------*/ 273 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 274 275 #undef __FUNCT__ 276 #define __FUNCT__ "PetscSortIntWithScalarArray_Private" 277 /* 278 Modified from PetscSortIntWithArray_Private(). 279 */ 280 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 281 { 282 PetscErrorCode ierr; 283 PetscInt i,vl,last,tmp; 284 PetscScalar stmp; 285 286 PetscFunctionBegin; 287 if (right <= 1) { 288 if (right == 1) { 289 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 290 } 291 PetscFunctionReturn(0); 292 } 293 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 294 vl = v[0]; 295 last = 0; 296 for (i=1; i<=right; i++) { 297 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 298 } 299 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 300 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 301 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 302 PetscFunctionReturn(0); 303 } 304 305 #undef __FUNCT__ 306 #define __FUNCT__ "PetscSortIntWithScalarArray" 307 /*@ 308 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 309 changes a second SCALAR array to match the sorted first INTEGER array. 310 311 Not Collective 312 313 Input Parameters: 314 + n - number of values 315 . i - array of integers 316 - I - second array of scalars 317 318 Level: intermediate 319 320 Concepts: sorting^ints with array 321 322 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 323 @*/ 324 PetscErrorCode PETSCSYS_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 325 { 326 PetscErrorCode ierr; 327 PetscInt j,k,tmp,ik; 328 PetscScalar stmp; 329 330 PetscFunctionBegin; 331 if (n<8) { 332 for (k=0; k<n; k++) { 333 ik = i[k]; 334 for (j=k+1; j<n; j++) { 335 if (ik > i[j]) { 336 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 337 ik = i[k]; 338 } 339 } 340 } 341 } else { 342 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 343 } 344 PetscFunctionReturn(0); 345 } 346 347 348