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 PetscInt 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 PetscInt 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 PetscInt 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 PetscInt 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 Level: intermediate 246 247 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 248 @*/ 249 PetscErrorCode PetscSortInt(PetscInt n,PetscInt X[]) 250 { 251 PetscErrorCode ierr; 252 PetscInt pivot,t1; 253 254 PetscFunctionBegin; 255 QuickSort1(PetscSortInt,X,n,pivot,t1,ierr); 256 PetscFunctionReturn(0); 257 } 258 259 /*@ 260 PetscSortReverseInt - Sorts an array of integers in place in decreasing order. 261 262 Not Collective 263 264 Input Parameters: 265 + n - number of values 266 - X - array of integers 267 268 Level: intermediate 269 270 .seealso: PetscSortInt(), PetscSortIntWithPermutation() 271 @*/ 272 PetscErrorCode PetscSortReverseInt(PetscInt n,PetscInt X[]) 273 { 274 PetscErrorCode ierr; 275 PetscInt pivot,t1; 276 277 PetscFunctionBegin; 278 QuickSortReverse1(PetscSortReverseInt,X,n,pivot,t1,ierr); 279 PetscFunctionReturn(0); 280 } 281 282 /*@ 283 PetscSortedRemoveDupsInt - Removes all duplicate entries of a sorted input array 284 285 Not Collective 286 287 Input Parameters: 288 + n - number of values 289 - X - sorted array of integers 290 291 Output Parameter: 292 . n - number of non-redundant values 293 294 Level: intermediate 295 296 .seealso: PetscSortInt() 297 @*/ 298 PetscErrorCode PetscSortedRemoveDupsInt(PetscInt *n,PetscInt X[]) 299 { 300 PetscInt i,s = 0,N = *n, b = 0; 301 302 PetscFunctionBegin; 303 PetscCheckSorted(*n,X); 304 for (i=0; i<N-1; i++) { 305 if (X[b+s+1] != X[b]) { 306 X[b+1] = X[b+s+1]; b++; 307 } else s++; 308 } 309 *n = N - s; 310 PetscFunctionReturn(0); 311 } 312 313 /*@ 314 PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries 315 316 Not Collective 317 318 Input Parameters: 319 + n - number of values 320 - X - array of integers 321 322 Output Parameter: 323 . n - number of non-redundant values 324 325 Level: intermediate 326 327 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortedRemoveDupsInt() 328 @*/ 329 PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n,PetscInt X[]) 330 { 331 PetscErrorCode ierr; 332 333 PetscFunctionBegin; 334 ierr = PetscSortInt(*n,X);CHKERRQ(ierr); 335 ierr = PetscSortedRemoveDupsInt(n,X);CHKERRQ(ierr); 336 PetscFunctionReturn(0); 337 } 338 339 /*@ 340 PetscFindInt - Finds integer in a sorted array of integers 341 342 Not Collective 343 344 Input Parameters: 345 + key - the integer to locate 346 . n - number of values in the array 347 - X - array of integers 348 349 Output Parameter: 350 . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go 351 352 Level: intermediate 353 354 .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt() 355 @*/ 356 PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt X[], PetscInt *loc) 357 { 358 PetscInt lo = 0,hi = n; 359 360 PetscFunctionBegin; 361 PetscValidPointer(loc,4); 362 if (!n) {*loc = -1; PetscFunctionReturn(0);} 363 PetscValidPointer(X,3); 364 PetscCheckSorted(n,X); 365 while (hi - lo > 1) { 366 PetscInt mid = lo + (hi - lo)/2; 367 if (key < X[mid]) hi = mid; 368 else lo = mid; 369 } 370 *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1); 371 PetscFunctionReturn(0); 372 } 373 374 /*@ 375 PetscCheckDupsInt - Checks if an integer array has duplicates 376 377 Not Collective 378 379 Input Parameters: 380 + n - number of values in the array 381 - X - array of integers 382 383 384 Output Parameter: 385 . dups - True if the array has dups, otherwise false 386 387 Level: intermediate 388 389 .seealso: PetscSortRemoveDupsInt() 390 @*/ 391 PetscErrorCode PetscCheckDupsInt(PetscInt n,const PetscInt X[],PetscBool *dups) 392 { 393 PetscErrorCode ierr; 394 PetscInt i; 395 PetscHSetI ht; 396 PetscBool missing; 397 398 PetscFunctionBegin; 399 PetscValidPointer(dups,3); 400 *dups = PETSC_FALSE; 401 if (n > 1) { 402 ierr = PetscHSetICreate(&ht);CHKERRQ(ierr); 403 ierr = PetscHSetIResize(ht,n);CHKERRQ(ierr); 404 for (i=0; i<n; i++) { 405 ierr = PetscHSetIQueryAdd(ht,X[i],&missing);CHKERRQ(ierr); 406 if (!missing) {*dups = PETSC_TRUE; break;} 407 } 408 ierr = PetscHSetIDestroy(&ht);CHKERRQ(ierr); 409 } 410 PetscFunctionReturn(0); 411 } 412 413 /*@ 414 PetscFindMPIInt - Finds MPI integer in a sorted array of integers 415 416 Not Collective 417 418 Input Parameters: 419 + key - the integer to locate 420 . n - number of values in the array 421 - X - array of integers 422 423 Output Parameter: 424 . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go 425 426 Level: intermediate 427 428 .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt() 429 @*/ 430 PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscInt n, const PetscMPIInt X[], PetscInt *loc) 431 { 432 PetscInt lo = 0,hi = n; 433 434 PetscFunctionBegin; 435 PetscValidPointer(loc,4); 436 if (!n) {*loc = -1; PetscFunctionReturn(0);} 437 PetscValidPointer(X,3); 438 PetscCheckSorted(n,X); 439 while (hi - lo > 1) { 440 PetscInt mid = lo + (hi - lo)/2; 441 if (key < X[mid]) hi = mid; 442 else lo = mid; 443 } 444 *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1); 445 PetscFunctionReturn(0); 446 } 447 448 /*@ 449 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 450 changes a second array to match the sorted first array. 451 452 Not Collective 453 454 Input Parameters: 455 + n - number of values 456 . X - array of integers 457 - Y - second array of integers 458 459 Level: intermediate 460 461 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 462 @*/ 463 PetscErrorCode PetscSortIntWithArray(PetscInt n,PetscInt X[],PetscInt Y[]) 464 { 465 PetscErrorCode ierr; 466 PetscInt pivot,t1,t2; 467 468 PetscFunctionBegin; 469 QuickSort2(PetscSortIntWithArray,X,Y,n,pivot,t1,t2,ierr); 470 PetscFunctionReturn(0); 471 } 472 473 /*@ 474 PetscSortIntWithArrayPair - Sorts an array of integers in place in increasing order; 475 changes a pair of integer arrays to match the sorted first array. 476 477 Not Collective 478 479 Input Parameters: 480 + n - number of values 481 . X - array of integers 482 . Y - second array of integers (first array of the pair) 483 - Z - third array of integers (second array of the pair) 484 485 Level: intermediate 486 487 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortIntWithArray() 488 @*/ 489 PetscErrorCode PetscSortIntWithArrayPair(PetscInt n,PetscInt X[],PetscInt Y[],PetscInt Z[]) 490 { 491 PetscErrorCode ierr; 492 PetscInt pivot,t1,t2,t3; 493 494 PetscFunctionBegin; 495 QuickSort3(PetscSortIntWithArrayPair,X,Y,Z,n,pivot,t1,t2,t3,ierr); 496 PetscFunctionReturn(0); 497 } 498 499 /*@ 500 PetscSortedMPIInt - Determines whether the array is sorted. 501 502 Not Collective 503 504 Input Parameters: 505 + n - number of values 506 - X - array of integers 507 508 Output Parameters: 509 . sorted - flag whether the array is sorted 510 511 Level: intermediate 512 513 .seealso: PetscSortMPIInt(), PetscSortedInt(), PetscSortedReal() 514 @*/ 515 PetscErrorCode PetscSortedMPIInt(PetscInt n,const PetscMPIInt X[],PetscBool *sorted) 516 { 517 PetscFunctionBegin; 518 PetscSorted(n,X,*sorted); 519 PetscFunctionReturn(0); 520 } 521 522 /*@ 523 PetscSortMPIInt - Sorts an array of MPI integers in place in increasing order. 524 525 Not Collective 526 527 Input Parameters: 528 + n - number of values 529 - X - array of integers 530 531 Level: intermediate 532 533 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 534 @*/ 535 PetscErrorCode PetscSortMPIInt(PetscInt n,PetscMPIInt X[]) 536 { 537 PetscErrorCode ierr; 538 PetscMPIInt pivot,t1; 539 540 PetscFunctionBegin; 541 QuickSort1(PetscSortMPIInt,X,n,pivot,t1,ierr); 542 PetscFunctionReturn(0); 543 } 544 545 /*@ 546 PetscSortRemoveDupsMPIInt - Sorts an array of MPI integers in place in increasing order removes all duplicate entries 547 548 Not Collective 549 550 Input Parameters: 551 + n - number of values 552 - X - array of integers 553 554 Output Parameter: 555 . n - number of non-redundant values 556 557 Level: intermediate 558 559 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 560 @*/ 561 PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n,PetscMPIInt X[]) 562 { 563 PetscErrorCode ierr; 564 PetscInt i,s = 0,N = *n, b = 0; 565 566 PetscFunctionBegin; 567 ierr = PetscSortMPIInt(N,X);CHKERRQ(ierr); 568 for (i=0; i<N-1; i++) { 569 if (X[b+s+1] != X[b]) { 570 X[b+1] = X[b+s+1]; b++; 571 } else s++; 572 } 573 *n = N - s; 574 PetscFunctionReturn(0); 575 } 576 577 /*@ 578 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 579 changes a second array to match the sorted first array. 580 581 Not Collective 582 583 Input Parameters: 584 + n - number of values 585 . X - array of integers 586 - Y - second array of integers 587 588 Level: intermediate 589 590 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 591 @*/ 592 PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt X[],PetscMPIInt Y[]) 593 { 594 PetscErrorCode ierr; 595 PetscMPIInt pivot,t1,t2; 596 597 PetscFunctionBegin; 598 QuickSort2(PetscSortMPIIntWithArray,X,Y,n,pivot,t1,t2,ierr); 599 PetscFunctionReturn(0); 600 } 601 602 /*@ 603 PetscSortMPIIntWithIntArray - Sorts an array of MPI integers in place in increasing order; 604 changes a second array of Petsc intergers to match the sorted first array. 605 606 Not Collective 607 608 Input Parameters: 609 + n - number of values 610 . X - array of MPI integers 611 - Y - second array of Petsc integers 612 613 Level: intermediate 614 615 Notes: this routine is useful when one needs to sort MPI ranks with other integer arrays. 616 617 .seealso: PetscSortMPIIntWithArray() 618 @*/ 619 PetscErrorCode PetscSortMPIIntWithIntArray(PetscMPIInt n,PetscMPIInt X[],PetscInt Y[]) 620 { 621 PetscErrorCode ierr; 622 PetscMPIInt pivot,t1; 623 PetscInt t2; 624 625 PetscFunctionBegin; 626 QuickSort2(PetscSortMPIIntWithIntArray,X,Y,n,pivot,t1,t2,ierr); 627 PetscFunctionReturn(0); 628 } 629 630 /*@ 631 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 632 changes a second SCALAR array to match the sorted first INTEGER array. 633 634 Not Collective 635 636 Input Parameters: 637 + n - number of values 638 . X - array of integers 639 - Y - second array of scalars 640 641 Level: intermediate 642 643 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 644 @*/ 645 PetscErrorCode PetscSortIntWithScalarArray(PetscInt n,PetscInt X[],PetscScalar Y[]) 646 { 647 PetscErrorCode ierr; 648 PetscInt pivot,t1; 649 PetscScalar t2; 650 651 PetscFunctionBegin; 652 QuickSort2(PetscSortIntWithScalarArray,X,Y,n,pivot,t1,t2,ierr); 653 PetscFunctionReturn(0); 654 } 655 656 /*@C 657 PetscSortIntWithDataArray - Sorts an array of integers in place in increasing order; 658 changes a second array to match the sorted first INTEGER array. Unlike other sort routines, the user must 659 provide workspace (the size of an element in the data array) to use when sorting. 660 661 Not Collective 662 663 Input Parameters: 664 + n - number of values 665 . X - array of integers 666 . Y - second array of data 667 . size - sizeof elements in the data array in bytes 668 - t2 - workspace of "size" bytes used when sorting 669 670 Level: intermediate 671 672 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 673 @*/ 674 PetscErrorCode PetscSortIntWithDataArray(PetscInt n,PetscInt X[],void *Y,size_t size,void *t2) 675 { 676 PetscErrorCode ierr; 677 char *YY = (char*)Y; 678 PetscInt i,j,p,t1,pivot,hi=n-1,l,r; 679 680 PetscFunctionBegin; 681 if (n<8) { 682 for (i=0; i<n; i++) { 683 pivot = X[i]; 684 for (j=i+1; j<n; j++) { 685 if (pivot > X[j]) { 686 SWAP2Data(X[i],X[j],YY+size*i,YY+size*j,t1,t2,size); 687 pivot = X[i]; 688 } 689 } 690 } 691 } else { 692 /* Two way partition */ 693 p = MEDIAN(X,hi); 694 pivot = X[p]; 695 l = 0; 696 r = hi; 697 while (1) { 698 while (X[l] < pivot) l++; 699 while (X[r] > pivot) r--; 700 if (l >= r) {r++; break;} 701 SWAP2Data(X[l],X[r],YY+size*l,YY+size*r,t1,t2,size); 702 l++; 703 r--; 704 } 705 ierr = PetscSortIntWithDataArray(l,X,Y,size,t2);CHKERRQ(ierr); 706 ierr = PetscSortIntWithDataArray(hi-r+1,X+r,YY+size*r,size,t2);CHKERRQ(ierr); 707 } 708 PetscFunctionReturn(0); 709 } 710 711 /*@ 712 PetscMergeIntArray - Merges two SORTED integer arrays, removes duplicate elements. 713 714 Not Collective 715 716 Input Parameters: 717 + an - number of values in the first array 718 . aI - first sorted array of integers 719 . bn - number of values in the second array 720 - bI - second array of integers 721 722 Output Parameters: 723 + n - number of values in the merged array 724 - L - merged sorted array, this is allocated if an array is not provided 725 726 Level: intermediate 727 728 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 729 @*/ 730 PetscErrorCode PetscMergeIntArray(PetscInt an,const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L) 731 { 732 PetscErrorCode ierr; 733 PetscInt *L_ = *L, ak, bk, k; 734 735 if (!L_) { 736 ierr = PetscMalloc1(an+bn, L);CHKERRQ(ierr); 737 L_ = *L; 738 } 739 k = ak = bk = 0; 740 while (ak < an && bk < bn) { 741 if (aI[ak] == bI[bk]) { 742 L_[k] = aI[ak]; 743 ++ak; 744 ++bk; 745 ++k; 746 } else if (aI[ak] < bI[bk]) { 747 L_[k] = aI[ak]; 748 ++ak; 749 ++k; 750 } else { 751 L_[k] = bI[bk]; 752 ++bk; 753 ++k; 754 } 755 } 756 if (ak < an) { 757 ierr = PetscArraycpy(L_+k,aI+ak,an-ak);CHKERRQ(ierr); 758 k += (an-ak); 759 } 760 if (bk < bn) { 761 ierr = PetscArraycpy(L_+k,bI+bk,bn-bk);CHKERRQ(ierr); 762 k += (bn-bk); 763 } 764 *n = k; 765 PetscFunctionReturn(0); 766 } 767 768 /*@ 769 PetscMergeIntArrayPair - Merges two SORTED integer arrays that share NO common values along with an additional array of integers. 770 The additional arrays are the same length as sorted arrays and are merged 771 in the order determined by the merging of the sorted pair. 772 773 Not Collective 774 775 Input Parameters: 776 + an - number of values in the first array 777 . aI - first sorted array of integers 778 . aJ - first additional array of integers 779 . bn - number of values in the second array 780 . bI - second array of integers 781 - bJ - second additional of integers 782 783 Output Parameters: 784 + n - number of values in the merged array (== an + bn) 785 . L - merged sorted array 786 - J - merged additional array 787 788 Notes: 789 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 790 Level: intermediate 791 792 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 793 @*/ 794 PetscErrorCode PetscMergeIntArrayPair(PetscInt an,const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J) 795 { 796 PetscErrorCode ierr; 797 PetscInt n_, *L_, *J_, ak, bk, k; 798 799 PetscFunctionBegin; 800 PetscValidIntPointer(L,8); 801 PetscValidIntPointer(J,9); 802 n_ = an + bn; 803 *n = n_; 804 if (!*L) { 805 ierr = PetscMalloc1(n_, L);CHKERRQ(ierr); 806 } 807 L_ = *L; 808 if (!*J) { 809 ierr = PetscMalloc1(n_, J);CHKERRQ(ierr); 810 } 811 J_ = *J; 812 k = ak = bk = 0; 813 while (ak < an && bk < bn) { 814 if (aI[ak] <= bI[bk]) { 815 L_[k] = aI[ak]; 816 J_[k] = aJ[ak]; 817 ++ak; 818 ++k; 819 } else { 820 L_[k] = bI[bk]; 821 J_[k] = bJ[bk]; 822 ++bk; 823 ++k; 824 } 825 } 826 if (ak < an) { 827 ierr = PetscArraycpy(L_+k,aI+ak,an-ak);CHKERRQ(ierr); 828 ierr = PetscArraycpy(J_+k,aJ+ak,an-ak);CHKERRQ(ierr); 829 k += (an-ak); 830 } 831 if (bk < bn) { 832 ierr = PetscArraycpy(L_+k,bI+bk,bn-bk);CHKERRQ(ierr); 833 ierr = PetscArraycpy(J_+k,bJ+bk,bn-bk);CHKERRQ(ierr); 834 } 835 PetscFunctionReturn(0); 836 } 837 838 /*@ 839 PetscMergeMPIIntArray - Merges two SORTED integer arrays. 840 841 Not Collective 842 843 Input Parameters: 844 + an - number of values in the first array 845 . aI - first sorted array of integers 846 . bn - number of values in the second array 847 - bI - second array of integers 848 849 Output Parameters: 850 + n - number of values in the merged array (<= an + bn) 851 - L - merged sorted array, allocated if address of NULL pointer is passed 852 853 Level: intermediate 854 855 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 856 @*/ 857 PetscErrorCode PetscMergeMPIIntArray(PetscInt an,const PetscMPIInt aI[],PetscInt bn,const PetscMPIInt bI[],PetscInt *n,PetscMPIInt **L) 858 { 859 PetscErrorCode ierr; 860 PetscInt ai,bi,k; 861 862 PetscFunctionBegin; 863 if (!*L) {ierr = PetscMalloc1((an+bn),L);CHKERRQ(ierr);} 864 for (ai=0,bi=0,k=0; ai<an || bi<bn;) { 865 PetscInt t = -1; 866 for (; ai<an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai]; 867 for (; bi<bn && bI[bi] == t; bi++); 868 for (; bi<bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi]; 869 for (; ai<an && aI[ai] == t; ai++); 870 } 871 *n = k; 872 PetscFunctionReturn(0); 873 } 874 875 /*@C 876 PetscProcessTree - Prepares tree data to be displayed graphically 877 878 Not Collective 879 880 Input Parameters: 881 + n - number of values 882 . mask - indicates those entries in the tree, location 0 is always masked 883 - parentid - indicates the parent of each entry 884 885 Output Parameters: 886 + Nlevels - the number of levels 887 . Level - for each node tells its level 888 . Levelcnts - the number of nodes on each level 889 . Idbylevel - a list of ids on each of the levels, first level followed by second etc 890 - Column - for each id tells its column index 891 892 Level: developer 893 894 Notes: 895 This code is not currently used 896 897 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 898 @*/ 899 PetscErrorCode PetscProcessTree(PetscInt n,const PetscBool mask[],const PetscInt parentid[],PetscInt *Nlevels,PetscInt **Level,PetscInt **Levelcnt,PetscInt **Idbylevel,PetscInt **Column) 900 { 901 PetscInt i,j,cnt,nmask = 0,nlevels = 0,*level,*levelcnt,levelmax = 0,*workid,*workparentid,tcnt = 0,*idbylevel,*column; 902 PetscErrorCode ierr; 903 PetscBool done = PETSC_FALSE; 904 905 PetscFunctionBegin; 906 if (!mask[0]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Mask of 0th location must be set"); 907 for (i=0; i<n; i++) { 908 if (mask[i]) continue; 909 if (parentid[i] == i) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Node labeled as own parent"); 910 if (parentid[i] && mask[parentid[i]]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Parent is masked"); 911 } 912 913 for (i=0; i<n; i++) { 914 if (!mask[i]) nmask++; 915 } 916 917 /* determine the level in the tree of each node */ 918 ierr = PetscCalloc1(n,&level);CHKERRQ(ierr); 919 920 level[0] = 1; 921 while (!done) { 922 done = PETSC_TRUE; 923 for (i=0; i<n; i++) { 924 if (mask[i]) continue; 925 if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1; 926 else if (!level[i]) done = PETSC_FALSE; 927 } 928 } 929 for (i=0; i<n; i++) { 930 level[i]--; 931 nlevels = PetscMax(nlevels,level[i]); 932 } 933 934 /* count the number of nodes on each level and its max */ 935 ierr = PetscCalloc1(nlevels,&levelcnt);CHKERRQ(ierr); 936 for (i=0; i<n; i++) { 937 if (mask[i]) continue; 938 levelcnt[level[i]-1]++; 939 } 940 for (i=0; i<nlevels;i++) levelmax = PetscMax(levelmax,levelcnt[i]); 941 942 /* for each level sort the ids by the parent id */ 943 ierr = PetscMalloc2(levelmax,&workid,levelmax,&workparentid);CHKERRQ(ierr); 944 ierr = PetscMalloc1(nmask,&idbylevel);CHKERRQ(ierr); 945 for (j=1; j<=nlevels;j++) { 946 cnt = 0; 947 for (i=0; i<n; i++) { 948 if (mask[i]) continue; 949 if (level[i] != j) continue; 950 workid[cnt] = i; 951 workparentid[cnt++] = parentid[i]; 952 } 953 /* PetscIntView(cnt,workparentid,0); 954 PetscIntView(cnt,workid,0); 955 ierr = PetscSortIntWithArray(cnt,workparentid,workid);CHKERRQ(ierr); 956 PetscIntView(cnt,workparentid,0); 957 PetscIntView(cnt,workid,0);*/ 958 ierr = PetscArraycpy(idbylevel+tcnt,workid,cnt);CHKERRQ(ierr); 959 tcnt += cnt; 960 } 961 if (tcnt != nmask) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Inconsistent count of unmasked nodes"); 962 ierr = PetscFree2(workid,workparentid);CHKERRQ(ierr); 963 964 /* for each node list its column */ 965 ierr = PetscMalloc1(n,&column);CHKERRQ(ierr); 966 cnt = 0; 967 for (j=0; j<nlevels; j++) { 968 for (i=0; i<levelcnt[j]; i++) { 969 column[idbylevel[cnt++]] = i; 970 } 971 } 972 973 *Nlevels = nlevels; 974 *Level = level; 975 *Levelcnt = levelcnt; 976 *Idbylevel = idbylevel; 977 *Column = column; 978 PetscFunctionReturn(0); 979 } 980 981 /*@ 982 PetscParallelSortedInt - Check whether an integer array, distributed over a communicator, is globally sorted. 983 984 Collective 985 986 Input Parameters: 987 + comm - the MPI communicator 988 . n - the local number of integers 989 - keys - the local array of integers 990 991 Output Parameters: 992 . is_sorted - whether the array is globally sorted 993 994 Level: developer 995 996 .seealso: PetscParallelSortInt() 997 @*/ 998 PetscErrorCode PetscParallelSortedInt(MPI_Comm comm, PetscInt n, const PetscInt keys[], PetscBool *is_sorted) 999 { 1000 PetscBool sorted; 1001 PetscInt i, min, max, prevmax; 1002 PetscMPIInt rank; 1003 PetscErrorCode ierr; 1004 1005 PetscFunctionBegin; 1006 sorted = PETSC_TRUE; 1007 min = PETSC_MAX_INT; 1008 max = PETSC_MIN_INT; 1009 if (n) { 1010 min = keys[0]; 1011 max = keys[0]; 1012 } 1013 for (i = 1; i < n; i++) { 1014 if (keys[i] < keys[i - 1]) break; 1015 min = PetscMin(min,keys[i]); 1016 max = PetscMax(max,keys[i]); 1017 } 1018 if (i < n) sorted = PETSC_FALSE; 1019 prevmax = PETSC_MIN_INT; 1020 ierr = MPI_Exscan(&max, &prevmax, 1, MPIU_INT, MPI_MAX, comm);CHKERRQ(ierr); 1021 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr); 1022 if (!rank) prevmax = PETSC_MIN_INT; 1023 if (prevmax > min) sorted = PETSC_FALSE; 1024 ierr = MPI_Allreduce(&sorted, is_sorted, 1, MPIU_BOOL, MPI_LAND, comm);CHKERRQ(ierr); 1025 PetscFunctionReturn(0); 1026 } 1027 1028