1 2 /* 3 This file contains routines for sorting integers. Values are sorted in place. 4 */ 5 #include <petsc/private/petscimpl.h> /*I "petscsys.h" I*/ 6 7 #define SWAP(a,b,t) {t=a;a=b;b=t;} 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 /* -----------------------------------------------------------------------*/ 21 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 /*@ 52 PetscSortInt - Sorts an array of integers in place in increasing order. 53 54 Not Collective 55 56 Input Parameters: 57 + n - number of values 58 - i - array of integers 59 60 Level: intermediate 61 62 Concepts: sorting^ints 63 64 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 65 @*/ 66 PetscErrorCode PetscSortInt(PetscInt n,PetscInt i[]) 67 { 68 PetscInt j,k,tmp,ik; 69 70 PetscFunctionBegin; 71 if (n<8) { 72 for (k=0; k<n; k++) { 73 ik = i[k]; 74 for (j=k+1; j<n; j++) { 75 if (ik > i[j]) { 76 SWAP(i[k],i[j],tmp); 77 ik = i[k]; 78 } 79 } 80 } 81 } else PetscSortInt_Private(i,n-1); 82 PetscFunctionReturn(0); 83 } 84 85 /*@ 86 PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries 87 88 Not Collective 89 90 Input Parameters: 91 + n - number of values 92 - ii - array of integers 93 94 Output Parameter: 95 . n - number of non-redundant values 96 97 Level: intermediate 98 99 Concepts: sorting^ints 100 101 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 102 @*/ 103 PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n,PetscInt ii[]) 104 { 105 PetscErrorCode ierr; 106 PetscInt i,s = 0,N = *n, b = 0; 107 108 PetscFunctionBegin; 109 ierr = PetscSortInt(N,ii);CHKERRQ(ierr); 110 for (i=0; i<N-1; i++) { 111 if (ii[b+s+1] != ii[b]) { 112 ii[b+1] = ii[b+s+1]; b++; 113 } else s++; 114 } 115 *n = N - s; 116 PetscFunctionReturn(0); 117 } 118 119 /*@ 120 PetscFindInt - Finds integer in a sorted array of integers 121 122 Not Collective 123 124 Input Parameters: 125 + key - the integer to locate 126 . n - number of values in the array 127 - ii - array of integers 128 129 Output Parameter: 130 . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go 131 132 Level: intermediate 133 134 Concepts: sorting^ints 135 136 .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt() 137 @*/ 138 PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt ii[], PetscInt *loc) 139 { 140 PetscInt lo = 0,hi = n; 141 142 PetscFunctionBegin; 143 PetscValidPointer(loc,4); 144 if (!n) {*loc = -1; PetscFunctionReturn(0);} 145 PetscValidPointer(ii,3); 146 while (hi - lo > 1) { 147 PetscInt mid = lo + (hi - lo)/2; 148 if (key < ii[mid]) hi = mid; 149 else lo = mid; 150 } 151 *loc = key == ii[lo] ? lo : -(lo + (key > ii[lo]) + 1); 152 PetscFunctionReturn(0); 153 } 154 155 156 /* -----------------------------------------------------------------------*/ 157 #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;} 158 159 /* 160 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 161 Assumes 0 origin for v, number of elements = right+1 (right is index of 162 right-most member). 163 */ 164 static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right) 165 { 166 PetscErrorCode ierr; 167 PetscInt i,vl,last,tmp; 168 169 PetscFunctionBegin; 170 if (right <= 1) { 171 if (right == 1) { 172 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 173 } 174 PetscFunctionReturn(0); 175 } 176 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 177 vl = v[0]; 178 last = 0; 179 for (i=1; i<=right; i++) { 180 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 181 } 182 SWAP2(v[0],v[last],V[0],V[last],tmp); 183 ierr = PetscSortIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 184 ierr = PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 185 PetscFunctionReturn(0); 186 } 187 188 /*@ 189 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 190 changes a second array to match the sorted first array. 191 192 Not Collective 193 194 Input Parameters: 195 + n - number of values 196 . i - array of integers 197 - I - second array of integers 198 199 Level: intermediate 200 201 Concepts: sorting^ints with array 202 203 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 204 @*/ 205 PetscErrorCode PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[]) 206 { 207 PetscErrorCode ierr; 208 PetscInt j,k,tmp,ik; 209 210 PetscFunctionBegin; 211 if (n<8) { 212 for (k=0; k<n; k++) { 213 ik = i[k]; 214 for (j=k+1; j<n; j++) { 215 if (ik > i[j]) { 216 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 217 ik = i[k]; 218 } 219 } 220 } 221 } else { 222 ierr = PetscSortIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 223 } 224 PetscFunctionReturn(0); 225 } 226 227 228 #define SWAP3(a,b,c,d,e,f,t) {t=a;a=b;b=t;t=c;c=d;d=t;t=e;e=f;f=t;} 229 230 /* 231 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 232 Assumes 0 origin for v, number of elements = right+1 (right is index of 233 right-most member). 234 */ 235 static PetscErrorCode PetscSortIntWithArrayPair_Private(PetscInt *L,PetscInt *J, PetscInt *K, PetscInt right) 236 { 237 PetscErrorCode ierr; 238 PetscInt i,vl,last,tmp; 239 240 PetscFunctionBegin; 241 if (right <= 1) { 242 if (right == 1) { 243 if (L[0] > L[1]) SWAP3(L[0],L[1],J[0],J[1],K[0],K[1],tmp); 244 } 245 PetscFunctionReturn(0); 246 } 247 SWAP3(L[0],L[right/2],J[0],J[right/2],K[0],K[right/2],tmp); 248 vl = L[0]; 249 last = 0; 250 for (i=1; i<=right; i++) { 251 if (L[i] < vl) {last++; SWAP3(L[last],L[i],J[last],J[i],K[last],K[i],tmp);} 252 } 253 SWAP3(L[0],L[last],J[0],J[last],K[0],K[last],tmp); 254 ierr = PetscSortIntWithArrayPair_Private(L,J,K,last-1);CHKERRQ(ierr); 255 ierr = PetscSortIntWithArrayPair_Private(L+last+1,J+last+1,K+last+1,right-(last+1));CHKERRQ(ierr); 256 PetscFunctionReturn(0); 257 } 258 259 /*@ 260 PetscSortIntWithArrayPair - Sorts an array of integers in place in increasing order; 261 changes a pair of integer arrays to match the sorted first array. 262 263 Not Collective 264 265 Input Parameters: 266 + n - number of values 267 . I - array of integers 268 . J - second array of integers (first array of the pair) 269 - K - third array of integers (second array of the pair) 270 271 Level: intermediate 272 273 Concepts: sorting^ints with array pair 274 275 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortIntWithArray() 276 @*/ 277 PetscErrorCode PetscSortIntWithArrayPair(PetscInt n,PetscInt L[],PetscInt J[], PetscInt K[]) 278 { 279 PetscErrorCode ierr; 280 PetscInt j,k,tmp,ik; 281 282 PetscFunctionBegin; 283 if (n<8) { 284 for (k=0; k<n; k++) { 285 ik = L[k]; 286 for (j=k+1; j<n; j++) { 287 if (ik > L[j]) { 288 SWAP3(L[k],L[j],J[k],J[j],K[k],K[j],tmp); 289 ik = L[k]; 290 } 291 } 292 } 293 } else { 294 ierr = PetscSortIntWithArrayPair_Private(L,J,K,n-1);CHKERRQ(ierr); 295 } 296 PetscFunctionReturn(0); 297 } 298 299 /* 300 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 301 Assumes 0 origin for v, number of elements = right+1 (right is index of 302 right-most member). 303 */ 304 static void PetscSortMPIInt_Private(PetscMPIInt *v,PetscInt right) 305 { 306 PetscInt i,j; 307 PetscMPIInt pivot,tmp; 308 309 if (right <= 1) { 310 if (right == 1) { 311 if (v[0] > v[1]) SWAP(v[0],v[1],tmp); 312 } 313 return; 314 } 315 i = MEDIAN(v,right); /* Choose a pivot */ 316 SWAP(v[0],v[i],tmp); /* Move it out of the way */ 317 pivot = v[0]; 318 for (i=0,j=right+1;; ) { 319 while (++i < j && v[i] <= pivot) ; /* Scan from the left */ 320 while (v[--j] > pivot) ; /* Scan from the right */ 321 if (i >= j) break; 322 SWAP(v[i],v[j],tmp); 323 } 324 SWAP(v[0],v[j],tmp); /* Put pivot back in place. */ 325 PetscSortMPIInt_Private(v,j-1); 326 PetscSortMPIInt_Private(v+j+1,right-(j+1)); 327 } 328 329 /*@ 330 PetscSortMPIInt - Sorts an array of MPI integers in place in increasing order. 331 332 Not Collective 333 334 Input Parameters: 335 + n - number of values 336 - i - array of integers 337 338 Level: intermediate 339 340 Concepts: sorting^ints 341 342 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 343 @*/ 344 PetscErrorCode PetscSortMPIInt(PetscInt n,PetscMPIInt i[]) 345 { 346 PetscInt j,k; 347 PetscMPIInt tmp,ik; 348 349 PetscFunctionBegin; 350 if (n<8) { 351 for (k=0; k<n; k++) { 352 ik = i[k]; 353 for (j=k+1; j<n; j++) { 354 if (ik > i[j]) { 355 SWAP(i[k],i[j],tmp); 356 ik = i[k]; 357 } 358 } 359 } 360 } else PetscSortMPIInt_Private(i,n-1); 361 PetscFunctionReturn(0); 362 } 363 364 /*@ 365 PetscSortRemoveDupsMPIInt - Sorts an array of MPI integers in place in increasing order removes all duplicate entries 366 367 Not Collective 368 369 Input Parameters: 370 + n - number of values 371 - ii - array of integers 372 373 Output Parameter: 374 . n - number of non-redundant values 375 376 Level: intermediate 377 378 Concepts: sorting^ints 379 380 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 381 @*/ 382 PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n,PetscMPIInt ii[]) 383 { 384 PetscErrorCode ierr; 385 PetscInt i,s = 0,N = *n, b = 0; 386 387 PetscFunctionBegin; 388 ierr = PetscSortMPIInt(N,ii);CHKERRQ(ierr); 389 for (i=0; i<N-1; i++) { 390 if (ii[b+s+1] != ii[b]) { 391 ii[b+1] = ii[b+s+1]; b++; 392 } else s++; 393 } 394 *n = N - s; 395 PetscFunctionReturn(0); 396 } 397 398 /* 399 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 400 Assumes 0 origin for v, number of elements = right+1 (right is index of 401 right-most member). 402 */ 403 static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right) 404 { 405 PetscErrorCode ierr; 406 PetscMPIInt i,vl,last,tmp; 407 408 PetscFunctionBegin; 409 if (right <= 1) { 410 if (right == 1) { 411 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 412 } 413 PetscFunctionReturn(0); 414 } 415 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 416 vl = v[0]; 417 last = 0; 418 for (i=1; i<=right; i++) { 419 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 420 } 421 SWAP2(v[0],v[last],V[0],V[last],tmp); 422 ierr = PetscSortMPIIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 423 ierr = PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 424 PetscFunctionReturn(0); 425 } 426 427 /*@ 428 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 429 changes a second array to match the sorted first array. 430 431 Not Collective 432 433 Input Parameters: 434 + n - number of values 435 . i - array of integers 436 - I - second array of integers 437 438 Level: intermediate 439 440 Concepts: sorting^ints with array 441 442 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 443 @*/ 444 PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[]) 445 { 446 PetscErrorCode ierr; 447 PetscMPIInt j,k,tmp,ik; 448 449 PetscFunctionBegin; 450 if (n<8) { 451 for (k=0; k<n; k++) { 452 ik = i[k]; 453 for (j=k+1; j<n; j++) { 454 if (ik > i[j]) { 455 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 456 ik = i[k]; 457 } 458 } 459 } 460 } else { 461 ierr = PetscSortMPIIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 462 } 463 PetscFunctionReturn(0); 464 } 465 466 /* -----------------------------------------------------------------------*/ 467 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 468 469 /* 470 Modified from PetscSortIntWithArray_Private(). 471 */ 472 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 473 { 474 PetscErrorCode ierr; 475 PetscInt i,vl,last,tmp; 476 PetscScalar stmp; 477 478 PetscFunctionBegin; 479 if (right <= 1) { 480 if (right == 1) { 481 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 482 } 483 PetscFunctionReturn(0); 484 } 485 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 486 vl = v[0]; 487 last = 0; 488 for (i=1; i<=right; i++) { 489 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 490 } 491 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 492 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 493 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 494 PetscFunctionReturn(0); 495 } 496 497 /*@ 498 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 499 changes a second SCALAR array to match the sorted first INTEGER array. 500 501 Not Collective 502 503 Input Parameters: 504 + n - number of values 505 . i - array of integers 506 - I - second array of scalars 507 508 Level: intermediate 509 510 Concepts: sorting^ints with array 511 512 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 513 @*/ 514 PetscErrorCode PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 515 { 516 PetscErrorCode ierr; 517 PetscInt j,k,tmp,ik; 518 PetscScalar stmp; 519 520 PetscFunctionBegin; 521 if (n<8) { 522 for (k=0; k<n; k++) { 523 ik = i[k]; 524 for (j=k+1; j<n; j++) { 525 if (ik > i[j]) { 526 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 527 ik = i[k]; 528 } 529 } 530 } 531 } else { 532 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 533 } 534 PetscFunctionReturn(0); 535 } 536 537 #define SWAP2IntData(a,b,c,d,t,td,siz) \ 538 do { \ 539 PetscErrorCode _ierr; \ 540 t=a;a=b;b=t; \ 541 _ierr = PetscMemcpy(td,c,siz);CHKERRQ(_ierr); \ 542 _ierr = PetscMemcpy(c,d,siz);CHKERRQ(_ierr); \ 543 _ierr = PetscMemcpy(d,td,siz);CHKERRQ(_ierr); \ 544 } while(0) 545 546 /* 547 Modified from PetscSortIntWithArray_Private(). 548 */ 549 static PetscErrorCode PetscSortIntWithDataArray_Private(PetscInt *v,char *V,PetscInt right,size_t size,void *work) 550 { 551 PetscErrorCode ierr; 552 PetscInt i,vl,last,tmp; 553 554 PetscFunctionBegin; 555 if (right <= 1) { 556 if (right == 1) { 557 if (v[0] > v[1]) SWAP2IntData(v[0],v[1],V,V+size,tmp,work,size); 558 } 559 PetscFunctionReturn(0); 560 } 561 SWAP2IntData(v[0],v[right/2],V,V+size*(right/2),tmp,work,size); 562 vl = v[0]; 563 last = 0; 564 for (i=1; i<=right; i++) { 565 if (v[i] < vl) {last++; SWAP2IntData(v[last],v[i],V+size*last,V+size*i,tmp,work,size);} 566 } 567 SWAP2IntData(v[0],v[last],V,V + size*last,tmp,work,size); 568 ierr = PetscSortIntWithDataArray_Private(v,V,last-1,size,work);CHKERRQ(ierr); 569 ierr = PetscSortIntWithDataArray_Private(v+last+1,V+size*(last+1),right-(last+1),size,work);CHKERRQ(ierr); 570 PetscFunctionReturn(0); 571 } 572 573 /*@C 574 PetscSortIntWithDataArray - Sorts an array of integers in place in increasing order; 575 changes a second array to match the sorted first INTEGER array. Unlike other sort routines, the user must 576 provide workspace (the size of an element in the data array) to use when sorting. 577 578 Not Collective 579 580 Input Parameters: 581 + n - number of values 582 . i - array of integers 583 . Ii - second array of data 584 . size - sizeof elements in the data array in bytes 585 - work - workspace of "size" bytes used when sorting 586 587 Level: intermediate 588 589 Concepts: sorting^ints with array 590 591 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 592 @*/ 593 PetscErrorCode PetscSortIntWithDataArray(PetscInt n,PetscInt i[],void *Ii,size_t size,void *work) 594 { 595 char *V = (char *) Ii; 596 PetscErrorCode ierr; 597 PetscInt j,k,tmp,ik; 598 599 PetscFunctionBegin; 600 if (n<8) { 601 for (k=0; k<n; k++) { 602 ik = i[k]; 603 for (j=k+1; j<n; j++) { 604 if (ik > i[j]) { 605 SWAP2IntData(i[k],i[j],V+size*k,V+size*j,tmp,work,size); 606 ik = i[k]; 607 } 608 } 609 } 610 } else { 611 ierr = PetscSortIntWithDataArray_Private(i,V,n-1,size,work);CHKERRQ(ierr); 612 } 613 PetscFunctionReturn(0); 614 } 615 616 617 /*@ 618 PetscMergeIntArray - Merges two SORTED integer arrays, removes duplicate elements. 619 620 Not Collective 621 622 Input Parameters: 623 + an - number of values in the first array 624 . aI - first sorted array of integers 625 . bn - number of values in the second array 626 - bI - second array of integers 627 628 Output Parameters: 629 + n - number of values in the merged array 630 - L - merged sorted array, this is allocated if an array is not provided 631 632 Level: intermediate 633 634 Concepts: merging^arrays 635 636 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 637 @*/ 638 PetscErrorCode PetscMergeIntArray(PetscInt an,const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L) 639 { 640 PetscErrorCode ierr; 641 PetscInt *L_ = *L, ak, bk, k; 642 643 if (!L_) { 644 ierr = PetscMalloc1(an+bn, L);CHKERRQ(ierr); 645 L_ = *L; 646 } 647 k = ak = bk = 0; 648 while (ak < an && bk < bn) { 649 if (aI[ak] == bI[bk]) { 650 L_[k] = aI[ak]; 651 ++ak; 652 ++bk; 653 ++k; 654 } else if (aI[ak] < bI[bk]) { 655 L_[k] = aI[ak]; 656 ++ak; 657 ++k; 658 } else { 659 L_[k] = bI[bk]; 660 ++bk; 661 ++k; 662 } 663 } 664 if (ak < an) { 665 ierr = PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));CHKERRQ(ierr); 666 k += (an-ak); 667 } 668 if (bk < bn) { 669 ierr = PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));CHKERRQ(ierr); 670 k += (bn-bk); 671 } 672 *n = k; 673 PetscFunctionReturn(0); 674 } 675 676 /*@ 677 PetscMergeIntArrayPair - Merges two SORTED integer arrays that share NO common values along with an additional array of integers. 678 The additional arrays are the same length as sorted arrays and are merged 679 in the order determined by the merging of the sorted pair. 680 681 Not Collective 682 683 Input Parameters: 684 + an - number of values in the first array 685 . aI - first sorted array of integers 686 . aJ - first additional array of integers 687 . bn - number of values in the second array 688 . bI - second array of integers 689 - bJ - second additional of integers 690 691 Output Parameters: 692 + n - number of values in the merged array (== an + bn) 693 . L - merged sorted array 694 - J - merged additional array 695 696 Notes: 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 697 Level: intermediate 698 699 Concepts: merging^arrays 700 701 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 702 @*/ 703 PetscErrorCode PetscMergeIntArrayPair(PetscInt an,const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J) 704 { 705 PetscErrorCode ierr; 706 PetscInt n_, *L_, *J_, ak, bk, k; 707 708 PetscFunctionBegin; 709 PetscValidIntPointer(L,8); 710 PetscValidIntPointer(J,9); 711 n_ = an + bn; 712 *n = n_; 713 if (!*L) { 714 ierr = PetscMalloc1(n_, L);CHKERRQ(ierr); 715 } 716 L_ = *L; 717 if (!*J) { 718 ierr = PetscMalloc1(n_, J);CHKERRQ(ierr); 719 } 720 J_ = *J; 721 k = ak = bk = 0; 722 while (ak < an && bk < bn) { 723 if (aI[ak] <= bI[bk]) { 724 L_[k] = aI[ak]; 725 J_[k] = aJ[ak]; 726 ++ak; 727 ++k; 728 } else { 729 L_[k] = bI[bk]; 730 J_[k] = bJ[bk]; 731 ++bk; 732 ++k; 733 } 734 } 735 if (ak < an) { 736 ierr = PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));CHKERRQ(ierr); 737 ierr = PetscMemcpy(J_+k,aJ+ak,(an-ak)*sizeof(PetscInt));CHKERRQ(ierr); 738 k += (an-ak); 739 } 740 if (bk < bn) { 741 ierr = PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));CHKERRQ(ierr); 742 ierr = PetscMemcpy(J_+k,bJ+bk,(bn-bk)*sizeof(PetscInt));CHKERRQ(ierr); 743 } 744 PetscFunctionReturn(0); 745 } 746 747 /*@ 748 PetscMergeMPIIntArray - Merges two SORTED integer arrays. 749 750 Not Collective 751 752 Input Parameters: 753 + an - number of values in the first array 754 . aI - first sorted array of integers 755 . bn - number of values in the second array 756 - bI - second array of integers 757 758 Output Parameters: 759 + n - number of values in the merged array (<= an + bn) 760 - L - merged sorted array, allocated if address of NULL pointer is passed 761 762 Level: intermediate 763 764 Concepts: merging^arrays 765 766 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 767 @*/ 768 PetscErrorCode PetscMergeMPIIntArray(PetscInt an,const PetscMPIInt aI[],PetscInt bn,const PetscMPIInt bI[],PetscInt *n,PetscMPIInt **L) 769 { 770 PetscErrorCode ierr; 771 PetscInt ai,bi,k; 772 773 PetscFunctionBegin; 774 if (!*L) {ierr = PetscMalloc1((an+bn),L);CHKERRQ(ierr);} 775 for (ai=0,bi=0,k=0; ai<an || bi<bn; ) { 776 PetscInt t = -1; 777 for ( ; ai<an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai]; 778 for ( ; bi<bn && bI[bi] == t; bi++); 779 for ( ; bi<bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi]; 780 for ( ; ai<an && aI[ai] == t; ai++); 781 } 782 *n = k; 783 PetscFunctionReturn(0); 784 } 785 786 /*@C 787 PetscProcessTree - Prepares tree data to be displayed graphically 788 789 Not Collective 790 791 Input Parameters: 792 + n - number of values 793 . mask - indicates those entries in the tree, location 0 is always masked 794 - parentid - indicates the parent of each entry 795 796 Output Parameters: 797 + Nlevels - the number of levels 798 . Level - for each node tells its level 799 . Levelcnts - the number of nodes on each level 800 . Idbylevel - a list of ids on each of the levels, first level followed by second etc 801 - Column - for each id tells its column index 802 803 Level: developer 804 805 Notes: This code is not currently used 806 807 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 808 @*/ 809 PetscErrorCode PetscProcessTree(PetscInt n,const PetscBool mask[],const PetscInt parentid[],PetscInt *Nlevels,PetscInt **Level,PetscInt **Levelcnt,PetscInt **Idbylevel,PetscInt **Column) 810 { 811 PetscInt i,j,cnt,nmask = 0,nlevels = 0,*level,*levelcnt,levelmax = 0,*workid,*workparentid,tcnt = 0,*idbylevel,*column; 812 PetscErrorCode ierr; 813 PetscBool done = PETSC_FALSE; 814 815 PetscFunctionBegin; 816 if (!mask[0]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Mask of 0th location must be set"); 817 for (i=0; i<n; i++) { 818 if (mask[i]) continue; 819 if (parentid[i] == i) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Node labeled as own parent"); 820 if (parentid[i] && mask[parentid[i]]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Parent is masked"); 821 } 822 823 for (i=0; i<n; i++) { 824 if (!mask[i]) nmask++; 825 } 826 827 /* determine the level in the tree of each node */ 828 ierr = PetscCalloc1(n,&level);CHKERRQ(ierr); 829 830 level[0] = 1; 831 while (!done) { 832 done = PETSC_TRUE; 833 for (i=0; i<n; i++) { 834 if (mask[i]) continue; 835 if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1; 836 else if (!level[i]) done = PETSC_FALSE; 837 } 838 } 839 for (i=0; i<n; i++) { 840 level[i]--; 841 nlevels = PetscMax(nlevels,level[i]); 842 } 843 844 /* count the number of nodes on each level and its max */ 845 ierr = PetscCalloc1(nlevels,&levelcnt);CHKERRQ(ierr); 846 for (i=0; i<n; i++) { 847 if (mask[i]) continue; 848 levelcnt[level[i]-1]++; 849 } 850 for (i=0; i<nlevels;i++) levelmax = PetscMax(levelmax,levelcnt[i]); 851 852 /* for each level sort the ids by the parent id */ 853 ierr = PetscMalloc2(levelmax,&workid,levelmax,&workparentid);CHKERRQ(ierr); 854 ierr = PetscMalloc1(nmask,&idbylevel);CHKERRQ(ierr); 855 for (j=1; j<=nlevels;j++) { 856 cnt = 0; 857 for (i=0; i<n; i++) { 858 if (mask[i]) continue; 859 if (level[i] != j) continue; 860 workid[cnt] = i; 861 workparentid[cnt++] = parentid[i]; 862 } 863 /* PetscIntView(cnt,workparentid,0); 864 PetscIntView(cnt,workid,0); 865 ierr = PetscSortIntWithArray(cnt,workparentid,workid);CHKERRQ(ierr); 866 PetscIntView(cnt,workparentid,0); 867 PetscIntView(cnt,workid,0);*/ 868 ierr = PetscMemcpy(idbylevel+tcnt,workid,cnt*sizeof(PetscInt));CHKERRQ(ierr); 869 tcnt += cnt; 870 } 871 if (tcnt != nmask) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Inconsistent count of unmasked nodes"); 872 ierr = PetscFree2(workid,workparentid);CHKERRQ(ierr); 873 874 /* for each node list its column */ 875 ierr = PetscMalloc1(n,&column);CHKERRQ(ierr); 876 cnt = 0; 877 for (j=0; j<nlevels; j++) { 878 for (i=0; i<levelcnt[j]; i++) { 879 column[idbylevel[cnt++]] = i; 880 } 881 } 882 883 *Nlevels = nlevels; 884 *Level = level; 885 *Levelcnt = levelcnt; 886 *Idbylevel = idbylevel; 887 *Column = column; 888 PetscFunctionReturn(0); 889 } 890