1 2 /* 3 This file contains routines for sorting integers. Values are sorted in place. 4 One can use src/sys/tests/ex52.c for benchmarking. 5 */ 6 #include <petsc/private/petscimpl.h> /*I "petscsys.h" I*/ 7 #include <petsc/private/hashseti.h> 8 9 #define MEDIAN3(v,a,b,c) \ 10 (v[a]<v[b] \ 11 ? (v[b]<v[c] \ 12 ? (b) \ 13 : (v[a]<v[c] ? (c) : (a))) \ 14 : (v[c]<v[b] \ 15 ? (b) \ 16 : (v[a]<v[c] ? (a) : (c)))) 17 18 #define MEDIAN(v,right) MEDIAN3(v,right/4,right/2,right/4*3) 19 20 /* Swap one, two or three pairs. Each pair can have its own type */ 21 #define SWAP1(a,b,t1) do {t1=a;a=b;b=t1;} while (0) 22 #define SWAP2(a,b,c,d,t1,t2) do {t1=a;a=b;b=t1; t2=c;c=d;d=t2;} while (0) 23 #define SWAP3(a,b,c,d,e,f,t1,t2,t3) do {t1=a;a=b;b=t1; t2=c;c=d;d=t2; t3=e;e=f;f=t3;} while (0) 24 25 /* Swap a & b, *c & *d. c, d, t2 are pointers to a type of size <siz> */ 26 #define SWAP2Data(a,b,c,d,t1,t2,siz) \ 27 do { \ 28 PetscErrorCode ierr; \ 29 t1=a; a=b; b=t1; \ 30 ierr = PetscMemcpy(t2,c,siz);CHKERRQ(ierr); \ 31 ierr = PetscMemcpy(c,d,siz);CHKERRQ(ierr); \ 32 ierr = PetscMemcpy(d,t2,siz);CHKERRQ(ierr); \ 33 } while (0) 34 35 /* 36 Partition X[lo,hi] into two parts: X[lo,l) <= pivot; X[r,hi] > pivot 37 38 Input Parameters: 39 + X - array to partition 40 . pivot - a pivot of X[] 41 . t1 - temp variable for X 42 - lo,hi - lower and upper bound of the array 43 44 Output Parameters: 45 + l,r - of type PetscInt 46 47 Notes: 48 The TwoWayPartition2/3 variants also partition other arrays along with X. 49 These arrays can have different types, so they provide their own temp t2,t3 50 */ 51 #define TwoWayPartition1(X,pivot,t1,lo,hi,l,r) \ 52 do { \ 53 l = lo; \ 54 r = hi; \ 55 while (1) { \ 56 while (X[l] < pivot) l++; \ 57 while (X[r] > pivot) r--; \ 58 if (l >= r) {r++; break;} \ 59 SWAP1(X[l],X[r],t1); \ 60 l++; \ 61 r--; \ 62 } \ 63 } while (0) 64 65 /* 66 Partition X[lo,hi] into two parts: X[lo,l) >= pivot; X[r,hi] < pivot 67 68 Input Parameters: 69 + X - array to partition 70 . pivot - a pivot of X[] 71 . t1 - temp variable for X 72 - lo,hi - lower and upper bound of the array 73 74 Output Parameters: 75 + l,r - of type PetscInt 76 77 Notes: 78 The TwoWayPartition2/3 variants also partition other arrays along with X. 79 These arrays can have different types, so they provide their own temp t2,t3 80 */ 81 #define TwoWayPartitionReverse1(X,pivot,t1,lo,hi,l,r) \ 82 do { \ 83 l = lo; \ 84 r = hi; \ 85 while (1) { \ 86 while (X[l] > pivot) l++; \ 87 while (X[r] < pivot) r--; \ 88 if (l >= r) {r++; break;} \ 89 SWAP1(X[l],X[r],t1); \ 90 l++; \ 91 r--; \ 92 } \ 93 } while (0) 94 95 #define TwoWayPartition2(X,Y,pivot,t1,t2,lo,hi,l,r) \ 96 do { \ 97 l = lo; \ 98 r = hi; \ 99 while (1) { \ 100 while (X[l] < pivot) l++; \ 101 while (X[r] > pivot) r--; \ 102 if (l >= r) {r++; break;} \ 103 SWAP2(X[l],X[r],Y[l],Y[r],t1,t2); \ 104 l++; \ 105 r--; \ 106 } \ 107 } while (0) 108 109 #define TwoWayPartition3(X,Y,Z,pivot,t1,t2,t3,lo,hi,l,r) \ 110 do { \ 111 l = lo; \ 112 r = hi; \ 113 while (1) { \ 114 while (X[l] < pivot) l++; \ 115 while (X[r] > pivot) r--; \ 116 if (l >= r) {r++; break;} \ 117 SWAP3(X[l],X[r],Y[l],Y[r],Z[l],Z[r],t1,t2,t3); \ 118 l++; \ 119 r--; \ 120 } \ 121 } while (0) 122 123 /* Templates for similar functions used below */ 124 #define QuickSort1(FuncName,X,n,pivot,t1,ierr) \ 125 do { \ 126 PetscCount i,j,p,l,r,hi=n-1; \ 127 if (n < 8) { \ 128 for (i=0; i<n; i++) { \ 129 pivot = X[i]; \ 130 for (j=i+1; j<n; j++) { \ 131 if (pivot > X[j]) { \ 132 SWAP1(X[i],X[j],t1); \ 133 pivot = X[i]; \ 134 } \ 135 } \ 136 } \ 137 } else { \ 138 p = MEDIAN(X,hi); \ 139 pivot = X[p]; \ 140 TwoWayPartition1(X,pivot,t1,0,hi,l,r); \ 141 ierr = FuncName(l,X);CHKERRQ(ierr); \ 142 ierr = FuncName(hi-r+1,X+r);CHKERRQ(ierr); \ 143 } \ 144 } while (0) 145 146 /* Templates for similar functions used below */ 147 #define QuickSortReverse1(FuncName,X,n,pivot,t1,ierr) \ 148 do { \ 149 PetscCount i,j,p,l,r,hi=n-1; \ 150 if (n < 8) { \ 151 for (i=0; i<n; i++) { \ 152 pivot = X[i]; \ 153 for (j=i+1; j<n; j++) { \ 154 if (pivot < X[j]) { \ 155 SWAP1(X[i],X[j],t1); \ 156 pivot = X[i]; \ 157 } \ 158 } \ 159 } \ 160 } else { \ 161 p = MEDIAN(X,hi); \ 162 pivot = X[p]; \ 163 TwoWayPartitionReverse1(X,pivot,t1,0,hi,l,r); \ 164 ierr = FuncName(l,X);CHKERRQ(ierr); \ 165 ierr = FuncName(hi-r+1,X+r);CHKERRQ(ierr); \ 166 } \ 167 } while (0) 168 169 #define QuickSort2(FuncName,X,Y,n,pivot,t1,t2,ierr) \ 170 do { \ 171 PetscCount i,j,p,l,r,hi=n-1; \ 172 if (n < 8) { \ 173 for (i=0; i<n; i++) { \ 174 pivot = X[i]; \ 175 for (j=i+1; j<n; j++) { \ 176 if (pivot > X[j]) { \ 177 SWAP2(X[i],X[j],Y[i],Y[j],t1,t2); \ 178 pivot = X[i]; \ 179 } \ 180 } \ 181 } \ 182 } else { \ 183 p = MEDIAN(X,hi); \ 184 pivot = X[p]; \ 185 TwoWayPartition2(X,Y,pivot,t1,t2,0,hi,l,r); \ 186 ierr = FuncName(l,X,Y);CHKERRQ(ierr); \ 187 ierr = FuncName(hi-r+1,X+r,Y+r);CHKERRQ(ierr); \ 188 } \ 189 } while (0) 190 191 #define QuickSort3(FuncName,X,Y,Z,n,pivot,t1,t2,t3,ierr) \ 192 do { \ 193 PetscCount i,j,p,l,r,hi=n-1; \ 194 if (n < 8) { \ 195 for (i=0; i<n; i++) { \ 196 pivot = X[i]; \ 197 for (j=i+1; j<n; j++) { \ 198 if (pivot > X[j]) { \ 199 SWAP3(X[i],X[j],Y[i],Y[j],Z[i],Z[j],t1,t2,t3); \ 200 pivot = X[i]; \ 201 } \ 202 } \ 203 } \ 204 } else { \ 205 p = MEDIAN(X,hi); \ 206 pivot = X[p]; \ 207 TwoWayPartition3(X,Y,Z,pivot,t1,t2,t3,0,hi,l,r); \ 208 ierr = FuncName(l,X,Y,Z);CHKERRQ(ierr); \ 209 ierr = FuncName(hi-r+1,X+r,Y+r,Z+r);CHKERRQ(ierr); \ 210 } \ 211 } while (0) 212 213 /*@ 214 PetscSortedInt - Determines whether the array is sorted. 215 216 Not Collective 217 218 Input Parameters: 219 + n - number of values 220 - X - array of integers 221 222 Output Parameters: 223 . sorted - flag whether the array is sorted 224 225 Level: intermediate 226 227 .seealso: PetscSortInt(), PetscSortedMPIInt(), PetscSortedReal() 228 @*/ 229 PetscErrorCode PetscSortedInt(PetscInt n,const PetscInt X[],PetscBool *sorted) 230 { 231 PetscFunctionBegin; 232 PetscSorted(n,X,*sorted); 233 PetscFunctionReturn(0); 234 } 235 236 /*@ 237 PetscSortInt - Sorts an array of integers in place in increasing order. 238 239 Not Collective 240 241 Input Parameters: 242 + n - number of values 243 - X - array of integers 244 245 Notes: 246 This function serves as an alternative to PetscIntSortSemiOrdered(), and may perform faster especially if the array 247 is completely random. There are exceptions to this and so it is __highly__ recommended that the user benchmark their 248 code to see which routine is fastest. 249 250 Level: intermediate 251 252 .seealso: PetscIntSortSemiOrdered(), PetscSortReal(), PetscSortIntWithPermutation() 253 @*/ 254 PetscErrorCode PetscSortInt(PetscInt n,PetscInt X[]) 255 { 256 PetscErrorCode ierr; 257 PetscInt pivot,t1; 258 259 PetscFunctionBegin; 260 QuickSort1(PetscSortInt,X,n,pivot,t1,ierr); 261 PetscFunctionReturn(0); 262 } 263 264 /*@ 265 PetscSortReverseInt - Sorts an array of integers in place in decreasing order. 266 267 Not Collective 268 269 Input Parameters: 270 + n - number of values 271 - X - array of integers 272 273 Level: intermediate 274 275 .seealso: PetscIntSortSemiOrdered(), PetscSortInt(), PetscSortIntWithPermutation() 276 @*/ 277 PetscErrorCode PetscSortReverseInt(PetscInt n,PetscInt X[]) 278 { 279 PetscErrorCode ierr; 280 PetscInt pivot,t1; 281 282 PetscFunctionBegin; 283 QuickSortReverse1(PetscSortReverseInt,X,n,pivot,t1,ierr); 284 PetscFunctionReturn(0); 285 } 286 287 /*@ 288 PetscSortedRemoveDupsInt - Removes all duplicate entries of a sorted input array 289 290 Not Collective 291 292 Input Parameters: 293 + n - number of values 294 - X - sorted array of integers 295 296 Output Parameter: 297 . n - number of non-redundant values 298 299 Level: intermediate 300 301 .seealso: PetscSortInt() 302 @*/ 303 PetscErrorCode PetscSortedRemoveDupsInt(PetscInt *n,PetscInt X[]) 304 { 305 PetscInt i,s = 0,N = *n, b = 0; 306 307 PetscFunctionBegin; 308 PetscCheckSorted(*n,X); 309 for (i=0; i<N-1; i++) { 310 if (X[b+s+1] != X[b]) { 311 X[b+1] = X[b+s+1]; b++; 312 } else s++; 313 } 314 *n = N - s; 315 PetscFunctionReturn(0); 316 } 317 318 /*@ 319 PetscSortedCheckDupsInt - Checks if a sorted integer array has duplicates 320 321 Not Collective 322 323 Input Parameters: 324 + n - number of values 325 - X - sorted array of integers 326 327 Output Parameter: 328 . dups - True if the array has dups, otherwise false 329 330 Level: intermediate 331 332 .seealso: PetscSortInt(), PetscCheckDupsInt(), PetscSortRemoveDupsInt(), PetscSortedRemoveDupsInt() 333 @*/ 334 PetscErrorCode PetscSortedCheckDupsInt(PetscInt n,const PetscInt X[],PetscBool *flg) 335 { 336 PetscInt i; 337 338 PetscFunctionBegin; 339 PetscCheckSorted(n,X); 340 *flg = PETSC_FALSE; 341 for (i=0; i<n-1; i++) { 342 if (X[i+1] == X[i]) { 343 *flg = PETSC_TRUE; 344 break; 345 } 346 } 347 PetscFunctionReturn(0); 348 } 349 350 /*@ 351 PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries 352 353 Not Collective 354 355 Input Parameters: 356 + n - number of values 357 - X - array of integers 358 359 Output Parameter: 360 . n - number of non-redundant values 361 362 Level: intermediate 363 364 .seealso: PetscIntSortSemiOrdered(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortedRemoveDupsInt() 365 @*/ 366 PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n,PetscInt X[]) 367 { 368 PetscErrorCode ierr; 369 370 PetscFunctionBegin; 371 ierr = PetscSortInt(*n,X);CHKERRQ(ierr); 372 ierr = PetscSortedRemoveDupsInt(n,X);CHKERRQ(ierr); 373 PetscFunctionReturn(0); 374 } 375 376 /*@ 377 PetscFindInt - Finds integer in a sorted array of integers 378 379 Not Collective 380 381 Input Parameters: 382 + key - the integer to locate 383 . n - number of values in the array 384 - X - array of integers 385 386 Output Parameter: 387 . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go 388 389 Level: intermediate 390 391 .seealso: PetscIntSortSemiOrdered(), PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt() 392 @*/ 393 PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt X[], PetscInt *loc) 394 { 395 PetscInt lo = 0,hi = n; 396 397 PetscFunctionBegin; 398 PetscValidPointer(loc,4); 399 if (!n) {*loc = -1; PetscFunctionReturn(0);} 400 PetscValidPointer(X,3); 401 PetscCheckSorted(n,X); 402 while (hi - lo > 1) { 403 PetscInt mid = lo + (hi - lo)/2; 404 if (key < X[mid]) hi = mid; 405 else lo = mid; 406 } 407 *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1); 408 PetscFunctionReturn(0); 409 } 410 411 /*@ 412 PetscCheckDupsInt - Checks if an integer array has duplicates 413 414 Not Collective 415 416 Input Parameters: 417 + n - number of values in the array 418 - X - array of integers 419 420 Output Parameter: 421 . dups - True if the array has dups, otherwise false 422 423 Level: intermediate 424 425 .seealso: PetscSortRemoveDupsInt(), PetscSortedCheckDupsInt() 426 @*/ 427 PetscErrorCode PetscCheckDupsInt(PetscInt n,const PetscInt X[],PetscBool *dups) 428 { 429 PetscErrorCode ierr; 430 PetscInt i; 431 PetscHSetI ht; 432 PetscBool missing; 433 434 PetscFunctionBegin; 435 PetscValidPointer(dups,3); 436 *dups = PETSC_FALSE; 437 if (n > 1) { 438 ierr = PetscHSetICreate(&ht);CHKERRQ(ierr); 439 ierr = PetscHSetIResize(ht,n);CHKERRQ(ierr); 440 for (i=0; i<n; i++) { 441 ierr = PetscHSetIQueryAdd(ht,X[i],&missing);CHKERRQ(ierr); 442 if (!missing) {*dups = PETSC_TRUE; break;} 443 } 444 ierr = PetscHSetIDestroy(&ht);CHKERRQ(ierr); 445 } 446 PetscFunctionReturn(0); 447 } 448 449 /*@ 450 PetscFindMPIInt - Finds MPI integer in a sorted array of integers 451 452 Not Collective 453 454 Input Parameters: 455 + key - the integer to locate 456 . n - number of values in the array 457 - X - array of integers 458 459 Output Parameter: 460 . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go 461 462 Level: intermediate 463 464 .seealso: PetscMPIIntSortSemiOrdered(), PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt() 465 @*/ 466 PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscInt n, const PetscMPIInt X[], PetscInt *loc) 467 { 468 PetscInt lo = 0,hi = n; 469 470 PetscFunctionBegin; 471 PetscValidPointer(loc,4); 472 if (!n) {*loc = -1; PetscFunctionReturn(0);} 473 PetscValidPointer(X,3); 474 PetscCheckSorted(n,X); 475 while (hi - lo > 1) { 476 PetscInt mid = lo + (hi - lo)/2; 477 if (key < X[mid]) hi = mid; 478 else lo = mid; 479 } 480 *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1); 481 PetscFunctionReturn(0); 482 } 483 484 /*@ 485 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 486 changes a second array to match the sorted first array. 487 488 Not Collective 489 490 Input Parameters: 491 + n - number of values 492 . X - array of integers 493 - Y - second array of integers 494 495 Level: intermediate 496 497 .seealso: PetscIntSortSemiOrderedWithArray(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithCountArray() 498 @*/ 499 PetscErrorCode PetscSortIntWithArray(PetscInt n,PetscInt X[],PetscInt Y[]) 500 { 501 PetscErrorCode ierr; 502 PetscInt pivot,t1,t2; 503 504 PetscFunctionBegin; 505 QuickSort2(PetscSortIntWithArray,X,Y,n,pivot,t1,t2,ierr); 506 PetscFunctionReturn(0); 507 } 508 509 /*@ 510 PetscSortIntWithArrayPair - Sorts an array of integers in place in increasing order; 511 changes a pair of integer arrays to match the sorted first array. 512 513 Not Collective 514 515 Input Parameters: 516 + n - number of values 517 . X - array of integers 518 . Y - second array of integers (first array of the pair) 519 - Z - third array of integers (second array of the pair) 520 521 Level: intermediate 522 523 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortIntWithArray(), PetscIntSortSemiOrdered(), PetscSortIntWithIntCountArrayPair() 524 @*/ 525 PetscErrorCode PetscSortIntWithArrayPair(PetscInt n,PetscInt X[],PetscInt Y[],PetscInt Z[]) 526 { 527 PetscErrorCode ierr; 528 PetscInt pivot,t1,t2,t3; 529 530 PetscFunctionBegin; 531 QuickSort3(PetscSortIntWithArrayPair,X,Y,Z,n,pivot,t1,t2,t3,ierr); 532 PetscFunctionReturn(0); 533 } 534 535 /*@ 536 PetscSortIntWithCountArray - Sorts an array of integers in place in increasing order; 537 changes a second array to match the sorted first array. 538 539 Not Collective 540 541 Input Parameters: 542 + n - number of values 543 . X - array of integers 544 - Y - second array of PetscCounts (signed integers) 545 546 Level: intermediate 547 548 .seealso: PetscIntSortSemiOrderedWithArray(), PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 549 @*/ 550 PetscErrorCode PetscSortIntWithCountArray(PetscCount n,PetscInt X[],PetscCount Y[]) 551 { 552 PetscErrorCode ierr; 553 PetscInt pivot,t1; 554 PetscCount t2; 555 556 PetscFunctionBegin; 557 QuickSort2(PetscSortIntWithCountArray,X,Y,n,pivot,t1,t2,ierr); 558 PetscFunctionReturn(0); 559 } 560 561 /*@ 562 PetscSortIntWithIntCountArrayPair - Sorts an array of integers in place in increasing order; 563 changes an integer array and a PetscCount array to match the sorted first array. 564 565 Not Collective 566 567 Input Parameters: 568 + n - number of values 569 . X - array of integers 570 . Y - second array of integers (first array of the pair) 571 - Z - third array of PetscCounts (second array of the pair) 572 573 Level: intermediate 574 575 Notes: 576 Usually X, Y are matrix row/column indices, and Z is a permutation array and therefore Z's type is PetscCount to allow 2B+ nonzeros even with 32-bit PetscInt. 577 578 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortIntWithArray(), PetscIntSortSemiOrdered(), PetscSortIntWithArrayPair() 579 @*/ 580 PetscErrorCode PetscSortIntWithIntCountArrayPair(PetscCount n,PetscInt X[],PetscInt Y[],PetscCount Z[]) 581 { 582 PetscErrorCode ierr; 583 PetscInt pivot,t1,t2; /* pivot is take from X[], so its type is still PetscInt */ 584 PetscCount t3; /* temp for Z[] */ 585 586 PetscFunctionBegin; 587 QuickSort3(PetscSortIntWithIntCountArrayPair,X,Y,Z,n,pivot,t1,t2,t3,ierr); 588 PetscFunctionReturn(0); 589 } 590 591 /*@ 592 PetscSortedMPIInt - Determines whether the array is sorted. 593 594 Not Collective 595 596 Input Parameters: 597 + n - number of values 598 - X - array of integers 599 600 Output Parameters: 601 . sorted - flag whether the array is sorted 602 603 Level: intermediate 604 605 .seealso: PetscMPIIntSortSemiOrdered(), PetscSortMPIInt(), PetscSortedInt(), PetscSortedReal() 606 @*/ 607 PetscErrorCode PetscSortedMPIInt(PetscInt n,const PetscMPIInt X[],PetscBool *sorted) 608 { 609 PetscFunctionBegin; 610 PetscSorted(n,X,*sorted); 611 PetscFunctionReturn(0); 612 } 613 614 /*@ 615 PetscSortMPIInt - Sorts an array of MPI integers in place in increasing order. 616 617 Not Collective 618 619 Input Parameters: 620 + n - number of values 621 - X - array of integers 622 623 Level: intermediate 624 625 Notes: 626 This function serves as an alternative to PetscMPIIntSortSemiOrdered(), and may perform faster especially if the array 627 is completely random. There are exceptions to this and so it is __highly__ recommended that the user benchmark their 628 code to see which routine is fastest. 629 630 .seealso: PetscMPIIntSortSemiOrdered(), PetscSortReal(), PetscSortIntWithPermutation() 631 @*/ 632 PetscErrorCode PetscSortMPIInt(PetscInt n,PetscMPIInt X[]) 633 { 634 PetscErrorCode ierr; 635 PetscMPIInt pivot,t1; 636 637 PetscFunctionBegin; 638 QuickSort1(PetscSortMPIInt,X,n,pivot,t1,ierr); 639 PetscFunctionReturn(0); 640 } 641 642 /*@ 643 PetscSortRemoveDupsMPIInt - Sorts an array of MPI integers in place in increasing order removes all duplicate entries 644 645 Not Collective 646 647 Input Parameters: 648 + n - number of values 649 - X - array of integers 650 651 Output Parameter: 652 . n - number of non-redundant values 653 654 Level: intermediate 655 656 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 657 @*/ 658 PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n,PetscMPIInt X[]) 659 { 660 PetscErrorCode ierr; 661 PetscInt i,s = 0,N = *n, b = 0; 662 663 PetscFunctionBegin; 664 ierr = PetscSortMPIInt(N,X);CHKERRQ(ierr); 665 for (i=0; i<N-1; i++) { 666 if (X[b+s+1] != X[b]) { 667 X[b+1] = X[b+s+1]; b++; 668 } else s++; 669 } 670 *n = N - s; 671 PetscFunctionReturn(0); 672 } 673 674 /*@ 675 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 676 changes a second array to match the sorted first array. 677 678 Not Collective 679 680 Input Parameters: 681 + n - number of values 682 . X - array of integers 683 - Y - second array of integers 684 685 Level: intermediate 686 687 .seealso: PetscMPIIntSortSemiOrderedWithArray(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 688 @*/ 689 PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt X[],PetscMPIInt Y[]) 690 { 691 PetscErrorCode ierr; 692 PetscMPIInt pivot,t1,t2; 693 694 PetscFunctionBegin; 695 QuickSort2(PetscSortMPIIntWithArray,X,Y,n,pivot,t1,t2,ierr); 696 PetscFunctionReturn(0); 697 } 698 699 /*@ 700 PetscSortMPIIntWithIntArray - Sorts an array of MPI integers in place in increasing order; 701 changes a second array of Petsc intergers to match the sorted first array. 702 703 Not Collective 704 705 Input Parameters: 706 + n - number of values 707 . X - array of MPI integers 708 - Y - second array of Petsc integers 709 710 Level: intermediate 711 712 Notes: this routine is useful when one needs to sort MPI ranks with other integer arrays. 713 714 .seealso: PetscSortMPIIntWithArray(), PetscIntSortSemiOrderedWithArray(), PetscTimSortWithArray() 715 @*/ 716 PetscErrorCode PetscSortMPIIntWithIntArray(PetscMPIInt n,PetscMPIInt X[],PetscInt Y[]) 717 { 718 PetscErrorCode ierr; 719 PetscMPIInt pivot,t1; 720 PetscInt t2; 721 722 PetscFunctionBegin; 723 QuickSort2(PetscSortMPIIntWithIntArray,X,Y,n,pivot,t1,t2,ierr); 724 PetscFunctionReturn(0); 725 } 726 727 /*@ 728 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 729 changes a second SCALAR array to match the sorted first INTEGER array. 730 731 Not Collective 732 733 Input Parameters: 734 + n - number of values 735 . X - array of integers 736 - Y - second array of scalars 737 738 Level: intermediate 739 740 .seealso: PetscTimSortWithArray(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithArray() 741 @*/ 742 PetscErrorCode PetscSortIntWithScalarArray(PetscInt n,PetscInt X[],PetscScalar Y[]) 743 { 744 PetscErrorCode ierr; 745 PetscInt pivot,t1; 746 PetscScalar t2; 747 748 PetscFunctionBegin; 749 QuickSort2(PetscSortIntWithScalarArray,X,Y,n,pivot,t1,t2,ierr); 750 PetscFunctionReturn(0); 751 } 752 753 /*@C 754 PetscSortIntWithDataArray - Sorts an array of integers in place in increasing order; 755 changes a second array to match the sorted first INTEGER array. Unlike other sort routines, the user must 756 provide workspace (the size of an element in the data array) to use when sorting. 757 758 Not Collective 759 760 Input Parameters: 761 + n - number of values 762 . X - array of integers 763 . Y - second array of data 764 . size - sizeof elements in the data array in bytes 765 - t2 - workspace of "size" bytes used when sorting 766 767 Level: intermediate 768 769 .seealso: PetscTimSortWithArray(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithArray() 770 @*/ 771 PetscErrorCode PetscSortIntWithDataArray(PetscInt n,PetscInt X[],void *Y,size_t size,void *t2) 772 { 773 PetscErrorCode ierr; 774 char *YY = (char*)Y; 775 PetscInt i,j,p,t1,pivot,hi=n-1,l,r; 776 777 PetscFunctionBegin; 778 if (n<8) { 779 for (i=0; i<n; i++) { 780 pivot = X[i]; 781 for (j=i+1; j<n; j++) { 782 if (pivot > X[j]) { 783 SWAP2Data(X[i],X[j],YY+size*i,YY+size*j,t1,t2,size); 784 pivot = X[i]; 785 } 786 } 787 } 788 } else { 789 /* Two way partition */ 790 p = MEDIAN(X,hi); 791 pivot = X[p]; 792 l = 0; 793 r = hi; 794 while (1) { 795 while (X[l] < pivot) l++; 796 while (X[r] > pivot) r--; 797 if (l >= r) {r++; break;} 798 SWAP2Data(X[l],X[r],YY+size*l,YY+size*r,t1,t2,size); 799 l++; 800 r--; 801 } 802 ierr = PetscSortIntWithDataArray(l,X,Y,size,t2);CHKERRQ(ierr); 803 ierr = PetscSortIntWithDataArray(hi-r+1,X+r,YY+size*r,size,t2);CHKERRQ(ierr); 804 } 805 PetscFunctionReturn(0); 806 } 807 808 /*@ 809 PetscMergeIntArray - Merges two SORTED integer arrays, removes duplicate elements. 810 811 Not Collective 812 813 Input Parameters: 814 + an - number of values in the first array 815 . aI - first sorted array of integers 816 . bn - number of values in the second array 817 - bI - second array of integers 818 819 Output Parameters: 820 + n - number of values in the merged array 821 - L - merged sorted array, this is allocated if an array is not provided 822 823 Level: intermediate 824 825 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithArray() 826 @*/ 827 PetscErrorCode PetscMergeIntArray(PetscInt an,const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L) 828 { 829 PetscErrorCode ierr; 830 PetscInt *L_ = *L, ak, bk, k; 831 832 PetscFunctionBegin; 833 if (!L_) { 834 ierr = PetscMalloc1(an+bn, L);CHKERRQ(ierr); 835 L_ = *L; 836 } 837 k = ak = bk = 0; 838 while (ak < an && bk < bn) { 839 if (aI[ak] == bI[bk]) { 840 L_[k] = aI[ak]; 841 ++ak; 842 ++bk; 843 ++k; 844 } else if (aI[ak] < bI[bk]) { 845 L_[k] = aI[ak]; 846 ++ak; 847 ++k; 848 } else { 849 L_[k] = bI[bk]; 850 ++bk; 851 ++k; 852 } 853 } 854 if (ak < an) { 855 ierr = PetscArraycpy(L_+k,aI+ak,an-ak);CHKERRQ(ierr); 856 k += (an-ak); 857 } 858 if (bk < bn) { 859 ierr = PetscArraycpy(L_+k,bI+bk,bn-bk);CHKERRQ(ierr); 860 k += (bn-bk); 861 } 862 *n = k; 863 PetscFunctionReturn(0); 864 } 865 866 /*@ 867 PetscMergeIntArrayPair - Merges two SORTED integer arrays that share NO common values along with an additional array of integers. 868 The additional arrays are the same length as sorted arrays and are merged 869 in the order determined by the merging of the sorted pair. 870 871 Not Collective 872 873 Input Parameters: 874 + an - number of values in the first array 875 . aI - first sorted array of integers 876 . aJ - first additional array of integers 877 . bn - number of values in the second array 878 . bI - second array of integers 879 - bJ - second additional of integers 880 881 Output Parameters: 882 + n - number of values in the merged array (== an + bn) 883 . L - merged sorted array 884 - J - merged additional array 885 886 Notes: 887 if L or J point to non-null arrays then this routine will assume they are of the approproate size and use them, otherwise this routine will allocate space for them 888 Level: intermediate 889 890 .seealso: PetscIntSortSemiOrdered(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithArray() 891 @*/ 892 PetscErrorCode PetscMergeIntArrayPair(PetscInt an,const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J) 893 { 894 PetscErrorCode ierr; 895 PetscInt n_, *L_, *J_, ak, bk, k; 896 897 PetscFunctionBegin; 898 PetscValidIntPointer(L,8); 899 PetscValidIntPointer(J,9); 900 n_ = an + bn; 901 *n = n_; 902 if (!*L) { 903 ierr = PetscMalloc1(n_, L);CHKERRQ(ierr); 904 } 905 L_ = *L; 906 if (!*J) { 907 ierr = PetscMalloc1(n_, J);CHKERRQ(ierr); 908 } 909 J_ = *J; 910 k = ak = bk = 0; 911 while (ak < an && bk < bn) { 912 if (aI[ak] <= bI[bk]) { 913 L_[k] = aI[ak]; 914 J_[k] = aJ[ak]; 915 ++ak; 916 ++k; 917 } else { 918 L_[k] = bI[bk]; 919 J_[k] = bJ[bk]; 920 ++bk; 921 ++k; 922 } 923 } 924 if (ak < an) { 925 ierr = PetscArraycpy(L_+k,aI+ak,an-ak);CHKERRQ(ierr); 926 ierr = PetscArraycpy(J_+k,aJ+ak,an-ak);CHKERRQ(ierr); 927 k += (an-ak); 928 } 929 if (bk < bn) { 930 ierr = PetscArraycpy(L_+k,bI+bk,bn-bk);CHKERRQ(ierr); 931 ierr = PetscArraycpy(J_+k,bJ+bk,bn-bk);CHKERRQ(ierr); 932 } 933 PetscFunctionReturn(0); 934 } 935 936 /*@ 937 PetscMergeMPIIntArray - Merges two SORTED integer arrays. 938 939 Not Collective 940 941 Input Parameters: 942 + an - number of values in the first array 943 . aI - first sorted array of integers 944 . bn - number of values in the second array 945 - bI - second array of integers 946 947 Output Parameters: 948 + n - number of values in the merged array (<= an + bn) 949 - L - merged sorted array, allocated if address of NULL pointer is passed 950 951 Level: intermediate 952 953 .seealso: PetscIntSortSemiOrdered(), PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortIntWithArray() 954 @*/ 955 PetscErrorCode PetscMergeMPIIntArray(PetscInt an,const PetscMPIInt aI[],PetscInt bn,const PetscMPIInt bI[],PetscInt *n,PetscMPIInt **L) 956 { 957 PetscErrorCode ierr; 958 PetscInt ai,bi,k; 959 960 PetscFunctionBegin; 961 if (!*L) {ierr = PetscMalloc1((an+bn),L);CHKERRQ(ierr);} 962 for (ai=0,bi=0,k=0; ai<an || bi<bn;) { 963 PetscInt t = -1; 964 for (; ai<an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai]; 965 for (; bi<bn && bI[bi] == t; bi++); 966 for (; bi<bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi]; 967 for (; ai<an && aI[ai] == t; ai++); 968 } 969 *n = k; 970 PetscFunctionReturn(0); 971 } 972 973 /*@C 974 PetscProcessTree - Prepares tree data to be displayed graphically 975 976 Not Collective 977 978 Input Parameters: 979 + n - number of values 980 . mask - indicates those entries in the tree, location 0 is always masked 981 - parentid - indicates the parent of each entry 982 983 Output Parameters: 984 + Nlevels - the number of levels 985 . Level - for each node tells its level 986 . Levelcnts - the number of nodes on each level 987 . Idbylevel - a list of ids on each of the levels, first level followed by second etc 988 - Column - for each id tells its column index 989 990 Level: developer 991 992 Notes: 993 This code is not currently used 994 995 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 996 @*/ 997 PetscErrorCode PetscProcessTree(PetscInt n,const PetscBool mask[],const PetscInt parentid[],PetscInt *Nlevels,PetscInt **Level,PetscInt **Levelcnt,PetscInt **Idbylevel,PetscInt **Column) 998 { 999 PetscInt i,j,cnt,nmask = 0,nlevels = 0,*level,*levelcnt,levelmax = 0,*workid,*workparentid,tcnt = 0,*idbylevel,*column; 1000 PetscErrorCode ierr; 1001 PetscBool done = PETSC_FALSE; 1002 1003 PetscFunctionBegin; 1004 PetscCheckFalse(!mask[0],PETSC_COMM_SELF,PETSC_ERR_SUP,"Mask of 0th location must be set"); 1005 for (i=0; i<n; i++) { 1006 if (mask[i]) continue; 1007 PetscCheckFalse(parentid[i] == i,PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Node labeled as own parent"); 1008 PetscCheckFalse(parentid[i] && mask[parentid[i]],PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Parent is masked"); 1009 } 1010 1011 for (i=0; i<n; i++) { 1012 if (!mask[i]) nmask++; 1013 } 1014 1015 /* determine the level in the tree of each node */ 1016 ierr = PetscCalloc1(n,&level);CHKERRQ(ierr); 1017 1018 level[0] = 1; 1019 while (!done) { 1020 done = PETSC_TRUE; 1021 for (i=0; i<n; i++) { 1022 if (mask[i]) continue; 1023 if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1; 1024 else if (!level[i]) done = PETSC_FALSE; 1025 } 1026 } 1027 for (i=0; i<n; i++) { 1028 level[i]--; 1029 nlevels = PetscMax(nlevels,level[i]); 1030 } 1031 1032 /* count the number of nodes on each level and its max */ 1033 ierr = PetscCalloc1(nlevels,&levelcnt);CHKERRQ(ierr); 1034 for (i=0; i<n; i++) { 1035 if (mask[i]) continue; 1036 levelcnt[level[i]-1]++; 1037 } 1038 for (i=0; i<nlevels;i++) levelmax = PetscMax(levelmax,levelcnt[i]); 1039 1040 /* for each level sort the ids by the parent id */ 1041 ierr = PetscMalloc2(levelmax,&workid,levelmax,&workparentid);CHKERRQ(ierr); 1042 ierr = PetscMalloc1(nmask,&idbylevel);CHKERRQ(ierr); 1043 for (j=1; j<=nlevels;j++) { 1044 cnt = 0; 1045 for (i=0; i<n; i++) { 1046 if (mask[i]) continue; 1047 if (level[i] != j) continue; 1048 workid[cnt] = i; 1049 workparentid[cnt++] = parentid[i]; 1050 } 1051 /* PetscIntView(cnt,workparentid,0); 1052 PetscIntView(cnt,workid,0); 1053 ierr = PetscSortIntWithArray(cnt,workparentid,workid);CHKERRQ(ierr); 1054 PetscIntView(cnt,workparentid,0); 1055 PetscIntView(cnt,workid,0);*/ 1056 ierr = PetscArraycpy(idbylevel+tcnt,workid,cnt);CHKERRQ(ierr); 1057 tcnt += cnt; 1058 } 1059 PetscCheckFalse(tcnt != nmask,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Inconsistent count of unmasked nodes"); 1060 ierr = PetscFree2(workid,workparentid);CHKERRQ(ierr); 1061 1062 /* for each node list its column */ 1063 ierr = PetscMalloc1(n,&column);CHKERRQ(ierr); 1064 cnt = 0; 1065 for (j=0; j<nlevels; j++) { 1066 for (i=0; i<levelcnt[j]; i++) { 1067 column[idbylevel[cnt++]] = i; 1068 } 1069 } 1070 1071 *Nlevels = nlevels; 1072 *Level = level; 1073 *Levelcnt = levelcnt; 1074 *Idbylevel = idbylevel; 1075 *Column = column; 1076 PetscFunctionReturn(0); 1077 } 1078 1079 /*@ 1080 PetscParallelSortedInt - Check whether an integer array, distributed over a communicator, is globally sorted. 1081 1082 Collective 1083 1084 Input Parameters: 1085 + comm - the MPI communicator 1086 . n - the local number of integers 1087 - keys - the local array of integers 1088 1089 Output Parameters: 1090 . is_sorted - whether the array is globally sorted 1091 1092 Level: developer 1093 1094 .seealso: PetscParallelSortInt() 1095 @*/ 1096 PetscErrorCode PetscParallelSortedInt(MPI_Comm comm, PetscInt n, const PetscInt keys[], PetscBool *is_sorted) 1097 { 1098 PetscBool sorted; 1099 PetscInt i, min, max, prevmax; 1100 PetscMPIInt rank; 1101 PetscErrorCode ierr; 1102 1103 PetscFunctionBegin; 1104 sorted = PETSC_TRUE; 1105 min = PETSC_MAX_INT; 1106 max = PETSC_MIN_INT; 1107 if (n) { 1108 min = keys[0]; 1109 max = keys[0]; 1110 } 1111 for (i = 1; i < n; i++) { 1112 if (keys[i] < keys[i - 1]) break; 1113 min = PetscMin(min,keys[i]); 1114 max = PetscMax(max,keys[i]); 1115 } 1116 if (i < n) sorted = PETSC_FALSE; 1117 prevmax = PETSC_MIN_INT; 1118 ierr = MPI_Exscan(&max, &prevmax, 1, MPIU_INT, MPI_MAX, comm);CHKERRMPI(ierr); 1119 ierr = MPI_Comm_rank(comm, &rank);CHKERRMPI(ierr); 1120 if (rank == 0) prevmax = PETSC_MIN_INT; 1121 if (prevmax > min) sorted = PETSC_FALSE; 1122 ierr = MPI_Allreduce(&sorted, is_sorted, 1, MPIU_BOOL, MPI_LAND, comm);CHKERRMPI(ierr); 1123 PetscFunctionReturn(0); 1124 } 1125