Actual source code: sorti.c


  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>
  7: #include <petsc/private/hashseti.h>

  9: #define MEDIAN3(v, a, b, c) (v[a] < v[b] ? (v[b] < v[c] ? (b) : (v[a] < v[c] ? (c) : (a))) : (v[c] < v[b] ? (b) : (v[a] < v[c] ? (a) : (c))))

 11: #define MEDIAN(v, right) MEDIAN3(v, right / 4, right / 2, right / 4 * 3)

 13: /* Swap one, two or three pairs. Each pair can have its own type */
 14: #define SWAP1(a, b, t1) \
 15:   do { \
 16:     t1 = a; \
 17:     a  = b; \
 18:     b  = t1; \
 19:   } while (0)
 20: #define SWAP2(a, b, c, d, t1, t2) \
 21:   do { \
 22:     t1 = a; \
 23:     a  = b; \
 24:     b  = t1; \
 25:     t2 = c; \
 26:     c  = d; \
 27:     d  = t2; \
 28:   } while (0)
 29: #define SWAP3(a, b, c, d, e, f, t1, t2, t3) \
 30:   do { \
 31:     t1 = a; \
 32:     a  = b; \
 33:     b  = t1; \
 34:     t2 = c; \
 35:     c  = d; \
 36:     d  = t2; \
 37:     t3 = e; \
 38:     e  = f; \
 39:     f  = t3; \
 40:   } while (0)

 42: /* Swap a & b, *c & *d. c, d, t2 are pointers to a type of size <siz> */
 43: #define SWAP2Data(a, b, c, d, t1, t2, siz) \
 44:   do { \
 45:     t1 = a; \
 46:     a  = b; \
 47:     b  = t1; \
 48:     PetscMemcpy(t2, c, siz); \
 49:     PetscMemcpy(c, d, siz); \
 50:     PetscMemcpy(d, t2, siz); \
 51:   } while (0)

 53: /*
 54:    Partition X[lo,hi] into two parts: X[lo,l) <= pivot; X[r,hi] > pivot

 56:    Input Parameters:
 57:     + X         - array to partition
 58:     . pivot     - a pivot of X[]
 59:     . t1        - temp variable for X
 60:     - lo,hi     - lower and upper bound of the array

 62:    Output Parameters:
 63:     + l,r       - of type PetscInt

 65:    Note:
 66:     The TwoWayPartition2/3 variants also partition other arrays along with X.
 67:     These arrays can have different types, so they provide their own temp t2,t3
 68:  */
 69: #define TwoWayPartition1(X, pivot, t1, lo, hi, l, r) \
 70:   do { \
 71:     l = lo; \
 72:     r = hi; \
 73:     while (1) { \
 74:       while (X[l] < pivot) l++; \
 75:       while (X[r] > pivot) r--; \
 76:       if (l >= r) { \
 77:         r++; \
 78:         break; \
 79:       } \
 80:       SWAP1(X[l], X[r], t1); \
 81:       l++; \
 82:       r--; \
 83:     } \
 84:   } while (0)

 86: /*
 87:    Partition X[lo,hi] into two parts: X[lo,l) >= pivot; X[r,hi] < pivot

 89:    Input Parameters:
 90:     + X         - array to partition
 91:     . pivot     - a pivot of X[]
 92:     . t1        - temp variable for X
 93:     - lo,hi     - lower and upper bound of the array

 95:    Output Parameters:
 96:     + l,r       - of type PetscInt

 98:    Note:
 99:     The TwoWayPartition2/3 variants also partition other arrays along with X.
100:     These arrays can have different types, so they provide their own temp t2,t3
101:  */
102: #define TwoWayPartitionReverse1(X, pivot, t1, lo, hi, l, r) \
103:   do { \
104:     l = lo; \
105:     r = hi; \
106:     while (1) { \
107:       while (X[l] > pivot) l++; \
108:       while (X[r] < pivot) r--; \
109:       if (l >= r) { \
110:         r++; \
111:         break; \
112:       } \
113:       SWAP1(X[l], X[r], t1); \
114:       l++; \
115:       r--; \
116:     } \
117:   } while (0)

119: #define TwoWayPartition2(X, Y, pivot, t1, t2, lo, hi, l, r) \
120:   do { \
121:     l = lo; \
122:     r = hi; \
123:     while (1) { \
124:       while (X[l] < pivot) l++; \
125:       while (X[r] > pivot) r--; \
126:       if (l >= r) { \
127:         r++; \
128:         break; \
129:       } \
130:       SWAP2(X[l], X[r], Y[l], Y[r], t1, t2); \
131:       l++; \
132:       r--; \
133:     } \
134:   } while (0)

136: #define TwoWayPartition3(X, Y, Z, pivot, t1, t2, t3, lo, hi, l, r) \
137:   do { \
138:     l = lo; \
139:     r = hi; \
140:     while (1) { \
141:       while (X[l] < pivot) l++; \
142:       while (X[r] > pivot) r--; \
143:       if (l >= r) { \
144:         r++; \
145:         break; \
146:       } \
147:       SWAP3(X[l], X[r], Y[l], Y[r], Z[l], Z[r], t1, t2, t3); \
148:       l++; \
149:       r--; \
150:     } \
151:   } while (0)

153: /* Templates for similar functions used below */
154: #define QuickSort1(FuncName, X, n, pivot, t1) \
155:   do { \
156:     PetscCount i, j, p, l, r, hi = n - 1; \
157:     if (n < 8) { \
158:       for (i = 0; i < n; i++) { \
159:         pivot = X[i]; \
160:         for (j = i + 1; j < n; j++) { \
161:           if (pivot > X[j]) { \
162:             SWAP1(X[i], X[j], t1); \
163:             pivot = X[i]; \
164:           } \
165:         } \
166:       } \
167:     } else { \
168:       p     = MEDIAN(X, hi); \
169:       pivot = X[p]; \
170:       TwoWayPartition1(X, pivot, t1, 0, hi, l, r); \
171:       FuncName(l, X); \
172:       FuncName(hi - r + 1, X + r); \
173:     } \
174:   } while (0)

176: /* Templates for similar functions used below */
177: #define QuickSortReverse1(FuncName, X, n, pivot, t1) \
178:   do { \
179:     PetscCount i, j, p, l, r, hi = n - 1; \
180:     if (n < 8) { \
181:       for (i = 0; i < n; i++) { \
182:         pivot = X[i]; \
183:         for (j = i + 1; j < n; j++) { \
184:           if (pivot < X[j]) { \
185:             SWAP1(X[i], X[j], t1); \
186:             pivot = X[i]; \
187:           } \
188:         } \
189:       } \
190:     } else { \
191:       p     = MEDIAN(X, hi); \
192:       pivot = X[p]; \
193:       TwoWayPartitionReverse1(X, pivot, t1, 0, hi, l, r); \
194:       FuncName(l, X); \
195:       FuncName(hi - r + 1, X + r); \
196:     } \
197:   } while (0)

199: #define QuickSort2(FuncName, X, Y, n, pivot, t1, t2) \
200:   do { \
201:     PetscCount i, j, p, l, r, hi = n - 1; \
202:     if (n < 8) { \
203:       for (i = 0; i < n; i++) { \
204:         pivot = X[i]; \
205:         for (j = i + 1; j < n; j++) { \
206:           if (pivot > X[j]) { \
207:             SWAP2(X[i], X[j], Y[i], Y[j], t1, t2); \
208:             pivot = X[i]; \
209:           } \
210:         } \
211:       } \
212:     } else { \
213:       p     = MEDIAN(X, hi); \
214:       pivot = X[p]; \
215:       TwoWayPartition2(X, Y, pivot, t1, t2, 0, hi, l, r); \
216:       FuncName(l, X, Y); \
217:       FuncName(hi - r + 1, X + r, Y + r); \
218:     } \
219:   } while (0)

221: #define QuickSort3(FuncName, X, Y, Z, n, pivot, t1, t2, t3) \
222:   do { \
223:     PetscCount i, j, p, l, r, hi = n - 1; \
224:     if (n < 8) { \
225:       for (i = 0; i < n; i++) { \
226:         pivot = X[i]; \
227:         for (j = i + 1; j < n; j++) { \
228:           if (pivot > X[j]) { \
229:             SWAP3(X[i], X[j], Y[i], Y[j], Z[i], Z[j], t1, t2, t3); \
230:             pivot = X[i]; \
231:           } \
232:         } \
233:       } \
234:     } else { \
235:       p     = MEDIAN(X, hi); \
236:       pivot = X[p]; \
237:       TwoWayPartition3(X, Y, Z, pivot, t1, t2, t3, 0, hi, l, r); \
238:       FuncName(l, X, Y, Z); \
239:       FuncName(hi - r + 1, X + r, Y + r, Z + r); \
240:     } \
241:   } while (0)

243: /*@
244:    PetscSortedInt - Determines whether the `PetscInt` array is sorted.

246:    Not Collective

248:    Input Parameters:
249: +  n  - number of values
250: -  X  - array of integers

252:    Output Parameters:
253: .  sorted - flag whether the array is sorted

255:    Level: intermediate

257: .seealso: `PetscSortInt()`, `PetscSortedMPIInt()`, `PetscSortedReal()`
258: @*/
259: PetscErrorCode PetscSortedInt(PetscInt n, const PetscInt X[], PetscBool *sorted)
260: {
263:   PetscSorted(n, X, *sorted);
264:   return 0;
265: }

267: /*@
268:    PetscSortedInt64 - Determines whether the `PetscInt64` array is sorted.

270:    Not Collective

272:    Input Parameters:
273: +  n  - number of values
274: -  X  - array of integers

276:    Output Parameters:
277: .  sorted - flag whether the array is sorted

279:    Level: intermediate

281: .seealso: `PetscSortInt64()`, `PetscSortInt()`, `PetscSortedMPIInt()`, `PetscSortedReal()`
282: @*/
283: PetscErrorCode PetscSortedInt64(PetscInt n, const PetscInt64 X[], PetscBool *sorted)
284: {
287:   PetscSorted(n, X, *sorted);
288:   return 0;
289: }

291: /*@
292:    PetscSortInt - Sorts an array of `PetscInt` in place in increasing order.

294:    Not Collective

296:    Input Parameters:
297: +  n  - number of values
298: -  X  - array of integers

300:    Note:
301:    This function serves as an alternative to `PetscIntSortSemiOrdered()`, and may perform faster especially if the array
302:    is completely random. There are exceptions to this and so it is __highly__ recommended that the user benchmark their
303:    code to see which routine is fastest.

305:    Level: intermediate

307: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`
308: @*/
309: PetscErrorCode PetscSortInt(PetscInt n, PetscInt X[])
310: {
311:   PetscInt pivot, t1;

314:   QuickSort1(PetscSortInt, X, n, pivot, t1);
315:   return 0;
316: }

318: /*@
319:    PetscSortInt64 - Sorts an array of `PetscInt64` in place in increasing order.

321:    Not Collective

323:    Input Parameters:
324: +  n  - number of values
325: -  X  - array of integers

327:    Notes:
328:    This function sorts `PetscCount`s assumed to be in completely random order

330:    Level: intermediate

332: .seealso: `PetscSortInt()`
333: @*/
334: PetscErrorCode PetscSortInt64(PetscInt n, PetscInt64 X[])
335: {
336:   PetscCount pivot, t1;

339:   QuickSort1(PetscSortInt64, X, n, pivot, t1);
340:   return 0;
341: }

343: /*@
344:    PetscSortCount - Sorts an array of integers in place in increasing order.

346:    Not Collective

348:    Input Parameters:
349: +  n  - number of values
350: -  X  - array of integers

352:    Notes:
353:    This function sorts `PetscCount`s assumed to be in completely random order

355:    Level: intermediate

357: .seealso: `PetscSortInt()`
358: @*/
359: PetscErrorCode PetscSortCount(PetscInt n, PetscCount X[])
360: {
361:   PetscCount pivot, t1;

364:   QuickSort1(PetscSortCount, X, n, pivot, t1);
365:   return 0;
366: }

368: /*@
369:    PetscSortReverseInt - Sorts an array of integers in place in decreasing order.

371:    Not Collective

373:    Input Parameters:
374: +  n  - number of values
375: -  X  - array of integers

377:    Level: intermediate

379: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithPermutation()`
380: @*/
381: PetscErrorCode PetscSortReverseInt(PetscInt n, PetscInt X[])
382: {
383:   PetscInt pivot, t1;

386:   QuickSortReverse1(PetscSortReverseInt, X, n, pivot, t1);
387:   return 0;
388: }

390: /*@
391:    PetscSortedRemoveDupsInt - Removes all duplicate entries of a sorted `PetscInt` array

393:    Not Collective

395:    Input Parameters:
396: +  n  - number of values
397: -  X  - sorted array of integers

399:    Output Parameter:
400: .  n - number of non-redundant values

402:    Level: intermediate

404: .seealso: `PetscSortInt()`
405: @*/
406: PetscErrorCode PetscSortedRemoveDupsInt(PetscInt *n, PetscInt X[])
407: {
408:   PetscInt i, s = 0, N = *n, b = 0;

412:   for (i = 0; i < N - 1; i++) {
413:     if (X[b + s + 1] != X[b]) {
414:       X[b + 1] = X[b + s + 1];
415:       b++;
416:     } else s++;
417:   }
418:   *n = N - s;
419:   return 0;
420: }

422: /*@
423:    PetscSortedCheckDupsInt - Checks if a sorted `PetscInt` array has duplicates

425:    Not Collective

427:    Input Parameters:
428: +  n  - number of values
429: -  X  - sorted array of integers

431:    Output Parameter:
432: .  dups - True if the array has dups, otherwise false

434:    Level: intermediate

437: @*/
438: PetscErrorCode PetscSortedCheckDupsInt(PetscInt n, const PetscInt X[], PetscBool *flg)
439: {
440:   PetscInt i;

443:   *flg = PETSC_FALSE;
444:   for (i = 0; i < n - 1; i++) {
445:     if (X[i + 1] == X[i]) {
446:       *flg = PETSC_TRUE;
447:       break;
448:     }
449:   }
450:   return 0;
451: }

453: /*@
454:    PetscSortRemoveDupsInt - Sorts an array of `PetscInt` in place in increasing order removes all duplicate entries

456:    Not Collective

458:    Input Parameters:
459: +  n  - number of values
460: -  X  - array of integers

462:    Output Parameter:
463: .  n - number of non-redundant values

465:    Level: intermediate

467: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortedRemoveDupsInt()`
468: @*/
469: PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n, PetscInt X[])
470: {
472:   PetscSortInt(*n, X);
473:   PetscSortedRemoveDupsInt(n, X);
474:   return 0;
475: }

477: /*@
478:  PetscFindInt - Finds `PetscInt` in a sorted array of `PetscInt`

480:    Not Collective

482:    Input Parameters:
483: +  key - the integer to locate
484: .  n   - number of values in the array
485: -  X  - array of integers

487:    Output Parameter:
488: .  loc - the location if found, otherwise -(slot+1) where slot is the place the value would go

490:    Level: intermediate

492: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithArray()`, `PetscSortRemoveDupsInt()`
493: @*/
494: PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt X[], PetscInt *loc)
495: {
496:   PetscInt lo = 0, hi = n;

499:   if (!n) {
500:     *loc = -1;
501:     return 0;
502:   }
505:   while (hi - lo > 1) {
506:     PetscInt mid = lo + (hi - lo) / 2;
507:     if (key < X[mid]) hi = mid;
508:     else lo = mid;
509:   }
510:   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);
511:   return 0;
512: }

514: /*@

517:    Not Collective

519:    Input Parameters:
520: +  n  - number of values in the array
521: -  X  - array of integers

523:    Output Parameter:
524: .  dups - True if the array has dups, otherwise false

526:    Level: intermediate

528: .seealso: `PetscSortRemoveDupsInt()`, `PetscSortedCheckDupsInt()`
529: @*/
531: {
532:   PetscInt   i;
533:   PetscHSetI ht;
534:   PetscBool  missing;

538:   *dups = PETSC_FALSE;
539:   if (n > 1) {
540:     PetscHSetICreate(&ht);
541:     PetscHSetIResize(ht, n);
542:     for (i = 0; i < n; i++) {
543:       PetscHSetIQueryAdd(ht, X[i], &missing);
544:       if (!missing) {
545:         *dups = PETSC_TRUE;
546:         break;
547:       }
548:     }
549:     PetscHSetIDestroy(&ht);
550:   }
551:   return 0;
552: }

554: /*@
555:   PetscFindMPIInt - Finds `PetscMPIInt` in a sorted array of `PetscMPIInt`

557:    Not Collective

559:    Input Parameters:
560: +  key - the integer to locate
561: .  n   - number of values in the array
562: -  X   - array of integers

564:    Output Parameter:
565: .  loc - the location if found, otherwise -(slot+1) where slot is the place the value would go

567:    Level: intermediate

569: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithArray()`, `PetscSortRemoveDupsInt()`
570: @*/
571: PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscInt n, const PetscMPIInt X[], PetscInt *loc)
572: {
573:   PetscInt lo = 0, hi = n;

576:   if (!n) {
577:     *loc = -1;
578:     return 0;
579:   }
582:   while (hi - lo > 1) {
583:     PetscInt mid = lo + (hi - lo) / 2;
584:     if (key < X[mid]) hi = mid;
585:     else lo = mid;
586:   }
587:   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);
588:   return 0;
589: }

591: /*@
592:    PetscSortIntWithArray - Sorts an array of `PetscInt` in place in increasing order;
593:        changes a second array of `PetscInt` to match the sorted first array.

595:    Not Collective

597:    Input Parameters:
598: +  n  - number of values
599: .  X  - array of integers
600: -  Y  - second array of integers

602:    Level: intermediate

604: .seealso: `PetscIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithCountArray()`
605: @*/
606: PetscErrorCode PetscSortIntWithArray(PetscInt n, PetscInt X[], PetscInt Y[])
607: {
608:   PetscInt pivot, t1, t2;

610:   QuickSort2(PetscSortIntWithArray, X, Y, n, pivot, t1, t2);
611:   return 0;
612: }

614: /*@
615:    PetscSortIntWithArrayPair - Sorts an array of `PetscInt` in place in increasing order;
616:        changes a pair of `PetscInt` arrays to match the sorted first array.

618:    Not Collective

620:    Input Parameters:
621: +  n  - number of values
622: .  X  - array of integers
623: .  Y  - second array of integers (first array of the pair)
624: -  Z  - third array of integers  (second array of the pair)

626:    Level: intermediate

628: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortIntWithArray()`, `PetscIntSortSemiOrdered()`, `PetscSortIntWithIntCountArrayPair()`
629: @*/
630: PetscErrorCode PetscSortIntWithArrayPair(PetscInt n, PetscInt X[], PetscInt Y[], PetscInt Z[])
631: {
632:   PetscInt pivot, t1, t2, t3;

634:   QuickSort3(PetscSortIntWithArrayPair, X, Y, Z, n, pivot, t1, t2, t3);
635:   return 0;
636: }

638: /*@
639:    PetscSortIntWithCountArray - Sorts an array of `PetscInt` in place in increasing order;
640:        changes a second array of `PetscCount` to match the sorted first array.

642:    Not Collective

644:    Input Parameters:
645: +  n  - number of values
646: .  X  - array of integers
647: -  Y  - second array of PetscCounts (signed integers)

649:    Level: intermediate

651: .seealso: `PetscIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
652: @*/
653: PetscErrorCode PetscSortIntWithCountArray(PetscCount n, PetscInt X[], PetscCount Y[])
654: {
655:   PetscInt   pivot, t1;
656:   PetscCount t2;

658:   QuickSort2(PetscSortIntWithCountArray, X, Y, n, pivot, t1, t2);
659:   return 0;
660: }

662: /*@
663:    PetscSortIntWithIntCountArrayPair - Sorts an array of `PetscInt` in place in increasing order;
664:        changes a `PetscInt`  array and a `PetscCount` array to match the sorted first array.

666:    Not Collective

668:    Input Parameters:
669: +  n  - number of values
670: .  X  - array of integers
671: .  Y  - second array of integers (first array of the pair)
672: -  Z  - third array of PetscCounts  (second array of the pair)

674:    Level: intermediate

676:    Note:
677:     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.

679: .seealso: `PetscSortReal()`, `PetscSortIntPermutation()`, `PetscSortIntWithArray()`, `PetscIntSortSemiOrdered()`, `PetscSortIntWithArrayPair()`
680: @*/
681: PetscErrorCode PetscSortIntWithIntCountArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscCount Z[])
682: {
683:   PetscInt   pivot, t1, t2; /* pivot is take from X[], so its type is still PetscInt */
684:   PetscCount t3;            /* temp for Z[] */

686:   QuickSort3(PetscSortIntWithIntCountArrayPair, X, Y, Z, n, pivot, t1, t2, t3);
687:   return 0;
688: }

690: /*@
691:   PetscSortedMPIInt - Determines whether the `PetscMPIInt` array is sorted.

693:    Not Collective

695:    Input Parameters:
696: +  n  - number of values
697: -  X  - array of integers

699:    Output Parameters:
700: .  sorted - flag whether the array is sorted

702:    Level: intermediate

704: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortMPIInt()`, `PetscSortedInt()`, `PetscSortedReal()`
705: @*/
706: PetscErrorCode PetscSortedMPIInt(PetscInt n, const PetscMPIInt X[], PetscBool *sorted)
707: {
708:   PetscSorted(n, X, *sorted);
709:   return 0;
710: }

712: /*@
713:    PetscSortMPIInt - Sorts an array of `PetscMPIInt` in place in increasing order.

715:    Not Collective

717:    Input Parameters:
718: +  n  - number of values
719: -  X  - array of integers

721:    Level: intermediate

723:    Note:
724:    This function serves as an alternative to PetscMPIIntSortSemiOrdered(), and may perform faster especially if the array
725:    is completely random. There are exceptions to this and so it is __highly__ recommended that the user benchmark their
726:    code to see which routine is fastest.

728: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`
729: @*/
730: PetscErrorCode PetscSortMPIInt(PetscInt n, PetscMPIInt X[])
731: {
732:   PetscMPIInt pivot, t1;

734:   QuickSort1(PetscSortMPIInt, X, n, pivot, t1);
735:   return 0;
736: }

738: /*@
739:    PetscSortRemoveDupsMPIInt - Sorts an array of `PetscMPIInt` in place in increasing order removes all duplicate entries

741:    Not Collective

743:    Input Parameters:
744: +  n  - number of values
745: -  X  - array of integers

747:    Output Parameter:
748: .  n - number of non-redundant values

750:    Level: intermediate

752: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
753: @*/
754: PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n, PetscMPIInt X[])
755: {
756:   PetscInt s = 0, N = *n, b = 0;

758:   PetscSortMPIInt(N, X);
759:   for (PetscInt i = 0; i < N - 1; i++) {
760:     if (X[b + s + 1] != X[b]) {
761:       X[b + 1] = X[b + s + 1];
762:       b++;
763:     } else s++;
764:   }
765:   *n = N - s;
766:   return 0;
767: }

769: /*@
770:    PetscSortMPIIntWithArray - Sorts an array of `PetscMPIInt` in place in increasing order;
771:        changes a second `PetscMPIInt` array to match the sorted first array.

773:    Not Collective

775:    Input Parameters:
776: +  n  - number of values
777: .  X  - array of integers
778: -  Y  - second array of integers

780:    Level: intermediate

782: .seealso: `PetscMPIIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
783: @*/
784: PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n, PetscMPIInt X[], PetscMPIInt Y[])
785: {
786:   PetscMPIInt pivot, t1, t2;

788:   QuickSort2(PetscSortMPIIntWithArray, X, Y, n, pivot, t1, t2);
789:   return 0;
790: }

792: /*@
793:    PetscSortMPIIntWithIntArray - Sorts an array of `PetscMPIInt` in place in increasing order;
794:        changes a second array of `PetscInt` to match the sorted first array.

796:    Not Collective

798:    Input Parameters:
799: +  n  - number of values
800: .  X  - array of MPI integers
801: -  Y  - second array of Petsc integers

803:    Level: intermediate

805:    Note:
806:    This routine is useful when one needs to sort MPI ranks with other integer arrays.

808: .seealso: `PetscSortMPIIntWithArray()`, `PetscIntSortSemiOrderedWithArray()`, `PetscTimSortWithArray()`
809: @*/
810: PetscErrorCode PetscSortMPIIntWithIntArray(PetscMPIInt n, PetscMPIInt X[], PetscInt Y[])
811: {
812:   PetscMPIInt pivot, t1;
813:   PetscInt    t2;

815:   QuickSort2(PetscSortMPIIntWithIntArray, X, Y, n, pivot, t1, t2);
816:   return 0;
817: }

819: /*@
820:    PetscSortIntWithScalarArray - Sorts an array of `PetscInt` in place in increasing order;
821:        changes a second `PetscScalar` array to match the sorted first array.

823:    Not Collective

825:    Input Parameters:
826: +  n  - number of values
827: .  X  - array of integers
828: -  Y  - second array of scalars

830:    Level: intermediate

832: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
833: @*/
834: PetscErrorCode PetscSortIntWithScalarArray(PetscInt n, PetscInt X[], PetscScalar Y[])
835: {
836:   PetscInt    pivot, t1;
837:   PetscScalar t2;

839:   QuickSort2(PetscSortIntWithScalarArray, X, Y, n, pivot, t1, t2);
840:   return 0;
841: }

843: /*@C
844:    PetscSortIntWithDataArray - Sorts an array of `PetscInt` in place in increasing order;
845:        changes a second array to match the sorted first INTEGER array.  Unlike other sort routines, the user must
846:        provide workspace (the size of an element in the data array) to use when sorting.

848:    Not Collective

850:    Input Parameters:
851: +  n  - number of values
852: .  X  - array of integers
853: .  Y  - second array of data
854: .  size - sizeof elements in the data array in bytes
855: -  t2   - workspace of "size" bytes used when sorting

857:    Level: intermediate

859: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
860: @*/
861: PetscErrorCode PetscSortIntWithDataArray(PetscInt n, PetscInt X[], void *Y, size_t size, void *t2)
862: {
863:   char    *YY = (char *)Y;
864:   PetscInt t1, pivot, hi = n - 1;

866:   if (n < 8) {
867:     for (PetscInt i = 0; i < n; i++) {
868:       pivot = X[i];
869:       for (PetscInt j = i + 1; j < n; j++) {
870:         if (pivot > X[j]) {
871:           SWAP2Data(X[i], X[j], YY + size * i, YY + size * j, t1, t2, size);
872:           pivot = X[i];
873:         }
874:       }
875:     }
876:   } else {
877:     /* Two way partition */
878:     PetscInt l = 0, r = hi;

880:     pivot = X[MEDIAN(X, hi)];
881:     while (1) {
882:       while (X[l] < pivot) l++;
883:       while (X[r] > pivot) r--;
884:       if (l >= r) {
885:         r++;
886:         break;
887:       }
888:       SWAP2Data(X[l], X[r], YY + size * l, YY + size * r, t1, t2, size);
889:       l++;
890:       r--;
891:     }
892:     PetscSortIntWithDataArray(l, X, Y, size, t2);
893:     PetscSortIntWithDataArray(hi - r + 1, X + r, YY + size * r, size, t2);
894:   }
895:   return 0;
896: }

898: /*@
899:    PetscMergeIntArray -     Merges two SORTED `PetscInt` arrays, removes duplicate elements.

901:    Not Collective

903:    Input Parameters:
904: +  an  - number of values in the first array
905: .  aI  - first sorted array of integers
906: .  bn  - number of values in the second array
907: -  bI  - second array of integers

909:    Output Parameters:
910: +  n   - number of values in the merged array
911: -  L   - merged sorted array, this is allocated if an array is not provided

913:    Level: intermediate

915: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
916: @*/
917: PetscErrorCode PetscMergeIntArray(PetscInt an, const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L)
918: {
919:   PetscInt *L_ = *L, ak, bk, k;

921:   if (!L_) {
922:     PetscMalloc1(an + bn, L);
923:     L_ = *L;
924:   }
925:   k = ak = bk = 0;
926:   while (ak < an && bk < bn) {
927:     if (aI[ak] == bI[bk]) {
928:       L_[k] = aI[ak];
929:       ++ak;
930:       ++bk;
931:       ++k;
932:     } else if (aI[ak] < bI[bk]) {
933:       L_[k] = aI[ak];
934:       ++ak;
935:       ++k;
936:     } else {
937:       L_[k] = bI[bk];
938:       ++bk;
939:       ++k;
940:     }
941:   }
942:   if (ak < an) {
943:     PetscArraycpy(L_ + k, aI + ak, an - ak);
944:     k += (an - ak);
945:   }
946:   if (bk < bn) {
947:     PetscArraycpy(L_ + k, bI + bk, bn - bk);
948:     k += (bn - bk);
949:   }
950:   *n = k;
951:   return 0;
952: }

954: /*@
955:    PetscMergeIntArrayPair -     Merges two SORTED `PetscInt` arrays that share NO common values along with an additional array of `PetscInt`.
956:                                 The additional arrays are the same length as sorted arrays and are merged
957:                                 in the order determined by the merging of the sorted pair.

959:    Not Collective

961:    Input Parameters:
962: +  an  - number of values in the first array
963: .  aI  - first sorted array of integers
964: .  aJ  - first additional array of integers
965: .  bn  - number of values in the second array
966: .  bI  - second array of integers
967: -  bJ  - second additional of integers

969:    Output Parameters:
970: +  n   - number of values in the merged array (== an + bn)
971: .  L   - merged sorted array
972: -  J   - merged additional array

974:    Note:
975:     if L or J point to non-null arrays then this routine will assume they are of the appropriate size and use them, otherwise this routine will allocate space for them

977:    Level: intermediate

979: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
980: @*/
981: PetscErrorCode PetscMergeIntArrayPair(PetscInt an, const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J)
982: {
983:   PetscInt n_, *L_, *J_, ak, bk, k;

987:   n_ = an + bn;
988:   *n = n_;
989:   if (!*L) PetscMalloc1(n_, L);
990:   L_ = *L;
991:   if (!*J) PetscMalloc1(n_, J);
992:   J_ = *J;
993:   k = ak = bk = 0;
994:   while (ak < an && bk < bn) {
995:     if (aI[ak] <= bI[bk]) {
996:       L_[k] = aI[ak];
997:       J_[k] = aJ[ak];
998:       ++ak;
999:       ++k;
1000:     } else {
1001:       L_[k] = bI[bk];
1002:       J_[k] = bJ[bk];
1003:       ++bk;
1004:       ++k;
1005:     }
1006:   }
1007:   if (ak < an) {
1008:     PetscArraycpy(L_ + k, aI + ak, an - ak);
1009:     PetscArraycpy(J_ + k, aJ + ak, an - ak);
1010:     k += (an - ak);
1011:   }
1012:   if (bk < bn) {
1013:     PetscArraycpy(L_ + k, bI + bk, bn - bk);
1014:     PetscArraycpy(J_ + k, bJ + bk, bn - bk);
1015:   }
1016:   return 0;
1017: }

1019: /*@
1020:    PetscMergeMPIIntArray -     Merges two SORTED `PetscMPIInt` arrays.

1022:    Not Collective

1024:    Input Parameters:
1025: +  an  - number of values in the first array
1026: .  aI  - first sorted array of integers
1027: .  bn  - number of values in the second array
1028: -  bI  - second array of integers

1030:    Output Parameters:
1031: +  n   - number of values in the merged array (<= an + bn)
1032: -  L   - merged sorted array, allocated if address of NULL pointer is passed

1034:    Level: intermediate

1036: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
1037: @*/
1038: PetscErrorCode PetscMergeMPIIntArray(PetscInt an, const PetscMPIInt aI[], PetscInt bn, const PetscMPIInt bI[], PetscInt *n, PetscMPIInt **L)
1039: {
1040:   PetscInt ai, bi, k;

1042:   if (!*L) PetscMalloc1((an + bn), L);
1043:   for (ai = 0, bi = 0, k = 0; ai < an || bi < bn;) {
1044:     PetscInt t = -1;
1045:     for (; ai < an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai];
1046:     for (; bi < bn && bI[bi] == t; bi++)
1047:       ;
1048:     for (; bi < bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi];
1049:     for (; ai < an && aI[ai] == t; ai++)
1050:       ;
1051:   }
1052:   *n = k;
1053:   return 0;
1054: }

1056: /*@C
1057:    PetscProcessTree - Prepares tree data to be displayed graphically

1059:    Not Collective

1061:    Input Parameters:
1062: +  n  - number of values
1063: .  mask - indicates those entries in the tree, location 0 is always masked
1064: -  parentid - indicates the parent of each entry

1066:    Output Parameters:
1067: +  Nlevels - the number of levels
1068: .  Level - for each node tells its level
1069: .  Levelcnts - the number of nodes on each level
1070: .  Idbylevel - a list of ids on each of the levels, first level followed by second etc
1071: -  Column - for each id tells its column index

1073:    Level: developer

1075:    Note:
1076:     This code is not currently used

1078: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
1079: @*/
1080: PetscErrorCode PetscProcessTree(PetscInt n, const PetscBool mask[], const PetscInt parentid[], PetscInt *Nlevels, PetscInt **Level, PetscInt **Levelcnt, PetscInt **Idbylevel, PetscInt **Column)
1081: {
1082:   PetscInt  i, j, cnt, nmask = 0, nlevels = 0, *level, *levelcnt, levelmax = 0, *workid, *workparentid, tcnt = 0, *idbylevel, *column;
1083:   PetscBool done = PETSC_FALSE;

1086:   for (i = 0; i < n; i++) {
1087:     if (mask[i]) continue;
1090:   }

1092:   for (i = 0; i < n; i++) {
1093:     if (!mask[i]) nmask++;
1094:   }

1096:   /* determine the level in the tree of each node */
1097:   PetscCalloc1(n, &level);

1099:   level[0] = 1;
1100:   while (!done) {
1101:     done = PETSC_TRUE;
1102:     for (i = 0; i < n; i++) {
1103:       if (mask[i]) continue;
1104:       if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1;
1105:       else if (!level[i]) done = PETSC_FALSE;
1106:     }
1107:   }
1108:   for (i = 0; i < n; i++) {
1109:     level[i]--;
1110:     nlevels = PetscMax(nlevels, level[i]);
1111:   }

1113:   /* count the number of nodes on each level and its max */
1114:   PetscCalloc1(nlevels, &levelcnt);
1115:   for (i = 0; i < n; i++) {
1116:     if (mask[i]) continue;
1117:     levelcnt[level[i] - 1]++;
1118:   }
1119:   for (i = 0; i < nlevels; i++) levelmax = PetscMax(levelmax, levelcnt[i]);

1121:   /* for each level sort the ids by the parent id */
1122:   PetscMalloc2(levelmax, &workid, levelmax, &workparentid);
1123:   PetscMalloc1(nmask, &idbylevel);
1124:   for (j = 1; j <= nlevels; j++) {
1125:     cnt = 0;
1126:     for (i = 0; i < n; i++) {
1127:       if (mask[i]) continue;
1128:       if (level[i] != j) continue;
1129:       workid[cnt]         = i;
1130:       workparentid[cnt++] = parentid[i];
1131:     }
1132:     /*  PetscIntView(cnt,workparentid,0);
1133:     PetscIntView(cnt,workid,0);
1134:     PetscSortIntWithArray(cnt,workparentid,workid);
1135:     PetscIntView(cnt,workparentid,0);
1136:     PetscIntView(cnt,workid,0);*/
1137:     PetscArraycpy(idbylevel + tcnt, workid, cnt);
1138:     tcnt += cnt;
1139:   }
1141:   PetscFree2(workid, workparentid);

1143:   /* for each node list its column */
1144:   PetscMalloc1(n, &column);
1145:   cnt = 0;
1146:   for (j = 0; j < nlevels; j++) {
1147:     for (i = 0; i < levelcnt[j]; i++) column[idbylevel[cnt++]] = i;
1148:   }

1150:   *Nlevels   = nlevels;
1151:   *Level     = level;
1152:   *Levelcnt  = levelcnt;
1153:   *Idbylevel = idbylevel;
1154:   *Column    = column;
1155:   return 0;
1156: }

1158: /*@
1159:   PetscParallelSortedInt - Check whether a `PetscInt` array, distributed over a communicator, is globally sorted.

1161:   Collective

1163:   Input Parameters:
1164: + comm - the MPI communicator
1165: . n - the local number of integers
1166: - keys - the local array of integers

1168:   Output Parameters:
1169: . is_sorted - whether the array is globally sorted

1171:   Level: developer

1173: .seealso: `PetscParallelSortInt()`
1174: @*/
1175: PetscErrorCode PetscParallelSortedInt(MPI_Comm comm, PetscInt n, const PetscInt keys[], PetscBool *is_sorted)
1176: {
1177:   PetscBool   sorted;
1178:   PetscInt    i, min, max, prevmax;
1179:   PetscMPIInt rank;

1181:   sorted = PETSC_TRUE;
1182:   min    = PETSC_MAX_INT;
1183:   max    = PETSC_MIN_INT;
1184:   if (n) {
1185:     min = keys[0];
1186:     max = keys[0];
1187:   }
1188:   for (i = 1; i < n; i++) {
1189:     if (keys[i] < keys[i - 1]) break;
1190:     min = PetscMin(min, keys[i]);
1191:     max = PetscMax(max, keys[i]);
1192:   }
1193:   if (i < n) sorted = PETSC_FALSE;
1194:   prevmax = PETSC_MIN_INT;
1195:   MPI_Exscan(&max, &prevmax, 1, MPIU_INT, MPI_MAX, comm);
1196:   MPI_Comm_rank(comm, &rank);
1197:   if (rank == 0) prevmax = PETSC_MIN_INT;
1198:   if (prevmax > min) sorted = PETSC_FALSE;
1199:   MPI_Allreduce(&sorted, is_sorted, 1, MPIU_BOOL, MPI_LAND, comm);
1200:   return 0;
1201: }