Actual source code: sorti.c

      1: /*
      2:    This file contains routines for sorting integers. Values are sorted in place.
      3:    One can use src/sys/tests/ex52.c for benchmarking.
      4:  */
      5: #include <petsc/private/petscimpl.h>
      6: #include <petsc/private/hashseti.h>

      8: #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))))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    245:   Not Collective

    247:   Input Parameters:
    248: + n - number of values
    249: - X - array of `PetscInt`

    251:   Output Parameter:
    252: . sorted - flag whether the array is sorted

    254:   Level: intermediate

    256: .seealso: `PetscSortInt()`, `PetscSortedMPIInt()`, `PetscSortedReal()`
    257: @*/
    258: PetscErrorCode PetscSortedInt(PetscCount n, const PetscInt X[], PetscBool *sorted)
    259: {
    260:   PetscFunctionBegin;
    261:   if (n) PetscAssertPointer(X, 2);
    262:   PetscAssertPointer(sorted, 3);
    263:   PetscSorted(n, X, *sorted);
    264:   PetscFunctionReturn(PETSC_SUCCESS);
    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 `PetscInt64`

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

    279:   Level: intermediate

    281: .seealso: `PetscSortInt64()`, `PetscSortInt()`, `PetscSortedMPIInt()`, `PetscSortedReal()`
    282: @*/
    283: PetscErrorCode PetscSortedInt64(PetscCount n, const PetscInt64 X[], PetscBool *sorted)
    284: {
    285:   PetscFunctionBegin;
    286:   if (n) PetscAssertPointer(X, 2);
    287:   PetscAssertPointer(sorted, 3);
    288:   PetscSorted(n, X, *sorted);
    289:   PetscFunctionReturn(PETSC_SUCCESS);
    290: }

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

    295:   Not Collective

    297:   Input Parameters:
    298: + n - number of values
    299: - X - array of `PetscInt`

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

    306:   Level: intermediate

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

    314:   PetscFunctionBegin;
    315:   if (n) PetscAssertPointer(X, 2);
    316:   PetscCall(PetscIntCast(n, &N));
    317:   QuickSort1(PetscSortInt, X, N, pivot, t1);
    318:   PetscFunctionReturn(PETSC_SUCCESS);
    319: }

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

    324:   Not Collective

    326:   Input Parameters:
    327: + n - number of values
    328: - X - array of `PetscInt64`

    330:   Notes:
    331:   This function sorts `PetscInt64`s assumed to be in completely random order

    333:   Level: intermediate

    335: .seealso: `PetscSortInt()`
    336: @*/
    337: PetscErrorCode PetscSortInt64(PetscCount n, PetscInt64 X[])
    338: {
    339:   PetscCount pivot, t1;

    341:   PetscFunctionBegin;
    342:   if (n) PetscAssertPointer(X, 2);
    343:   QuickSort1(PetscSortInt64, X, n, pivot, t1);
    344:   PetscFunctionReturn(PETSC_SUCCESS);
    345: }

    347: /*@
    348:   PetscSortCount - Sorts an array of `PetscCount` in place in increasing order.

    350:   Not Collective

    352:   Input Parameters:
    353: + n - number of values
    354: - X - array of `PetscCount`

    356:   Notes:
    357:   This function sorts `PetscCount`s assumed to be in completely random order

    359:   Level: intermediate

    361: .seealso: `PetscSortInt()`
    362: @*/
    363: PetscErrorCode PetscSortCount(PetscCount n, PetscCount X[])
    364: {
    365:   PetscCount pivot, t1;

    367:   PetscFunctionBegin;
    368:   if (n) PetscAssertPointer(X, 2);
    369:   QuickSort1(PetscSortCount, X, n, pivot, t1);
    370:   PetscFunctionReturn(PETSC_SUCCESS);
    371: }

    373: /*@
    374:   PetscSortReverseInt - Sorts an array of `PetscInt` in place in decreasing order.

    376:   Not Collective

    378:   Input Parameters:
    379: + n - number of values
    380: - X - array of `PetscInt`

    382:   Level: intermediate

    384: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithPermutation()`
    385: @*/
    386: PetscErrorCode PetscSortReverseInt(PetscCount n, PetscInt X[])
    387: {
    388:   PetscInt pivot, t1;

    390:   PetscFunctionBegin;
    391:   if (n) PetscAssertPointer(X, 2);
    392:   QuickSortReverse1(PetscSortReverseInt, X, n, pivot, t1);
    393:   PetscFunctionReturn(PETSC_SUCCESS);
    394: }

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

    399:   Not Collective

    401:   Input Parameters:
    402: + n - number of values
    403: - X - sorted array of `PetscInt`

    405:   Output Parameter:
    406: . n - number of non-redundant values

    408:   Level: intermediate

    410: .seealso: `PetscSortInt()`
    411: @*/
    412: PetscErrorCode PetscSortedRemoveDupsInt(PetscInt *n, PetscInt X[])
    413: {
    414:   PetscInt i, s = 0, N = *n, b = 0;

    416:   PetscFunctionBegin;
    417:   PetscAssertPointer(n, 1);
    418:   PetscCheckSorted(*n, X);
    419:   for (i = 0; i < N - 1; i++) {
    420:     if (X[b + s + 1] != X[b]) {
    421:       X[b + 1] = X[b + s + 1];
    422:       b++;
    423:     } else s++;
    424:   }
    425:   *n = N - s;
    426:   PetscFunctionReturn(PETSC_SUCCESS);
    427: }

    429: /*@
    430:   PetscSortedCheckDupsInt - Checks if a sorted `PetscInt` array has duplicates

    432:   Not Collective

    434:   Input Parameters:
    435: + n - number of values
    436: - X - sorted array of `PetscInt`

    438:   Output Parameter:
    439: . flg - True if the array has duplications, otherwise false

    441:   Level: intermediate

    443: .seealso: `PetscSortInt()`, `PetscCheckDupsInt()`, `PetscSortRemoveDupsInt()`, `PetscSortedRemoveDupsInt()`
    444: @*/
    445: PetscErrorCode PetscSortedCheckDupsInt(PetscCount n, const PetscInt X[], PetscBool *flg)
    446: {
    447:   PetscInt i;

    449:   PetscFunctionBegin;
    450:   PetscCheckSorted(n, X);
    451:   *flg = PETSC_FALSE;
    452:   for (i = 0; i < n - 1; i++) {
    453:     if (X[i + 1] == X[i]) {
    454:       *flg = PETSC_TRUE;
    455:       break;
    456:     }
    457:   }
    458:   PetscFunctionReturn(PETSC_SUCCESS);
    459: }

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

    464:   Not Collective

    466:   Input Parameters:
    467: + n - number of values
    468: - X - array of `PetscInt`

    470:   Output Parameter:
    471: . n - number of non-redundant values

    473:   Level: intermediate

    475: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortedRemoveDupsInt()`
    476: @*/
    477: PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n, PetscInt X[])
    478: {
    479:   PetscFunctionBegin;
    480:   PetscAssertPointer(n, 1);
    481:   PetscCall(PetscSortInt(*n, X));
    482:   PetscCall(PetscSortedRemoveDupsInt(n, X));
    483:   PetscFunctionReturn(PETSC_SUCCESS);
    484: }

    486: /*@
    487:   PetscFindInt - Finds the location of a `PetscInt` key in a sorted array of `PetscInt`

    489:   Not Collective

    491:   Input Parameters:
    492: + key - the `PetscInt` key to locate
    493: . n   - number of values in the array
    494: - X   - array of `PetscInt`

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

    499:   Level: intermediate

    501: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithArray()`, `PetscSortRemoveDupsInt()`
    502: @*/
    503: PetscErrorCode PetscFindInt(PetscInt key, PetscCount n, const PetscInt X[], PetscInt *loc)
    504: {
    505:   PetscInt lo = 0, hi;

    507:   PetscFunctionBegin;
    508:   PetscAssertPointer(loc, 4);
    509:   if (!n) {
    510:     *loc = -1;
    511:     PetscFunctionReturn(PETSC_SUCCESS);
    512:   }
    513:   PetscAssertPointer(X, 3);
    514:   PetscCall(PetscIntCast(n, &hi));
    515:   while (hi - lo > 1) {
    516:     PetscInt mid = lo + (hi - lo) / 2;
    517:     PetscAssert(X[lo] <= X[mid] && X[mid] <= X[hi - 1], PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array was not sorted: (%" PetscInt_FMT ", %" PetscInt_FMT ", %" PetscInt_FMT ")", X[lo], X[mid], X[hi - 1]);
    518:     if (key < X[mid]) hi = mid;
    519:     else lo = mid;
    520:   }
    521:   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);
    522:   PetscFunctionReturn(PETSC_SUCCESS);
    523: }

    525: /*@
    526:   PetscCheckDupsInt - Checks if an `PetscInt` array has duplicates

    528:   Not Collective

    530:   Input Parameters:
    531: + n - number of values in the array
    532: - X - array of `PetscInt`

    534:   Output Parameter:
    535: . dups - True if the array has dups, otherwise false

    537:   Level: intermediate

    539: .seealso: `PetscSortRemoveDupsInt()`, `PetscSortedCheckDupsInt()`
    540: @*/
    541: PetscErrorCode PetscCheckDupsInt(PetscInt n, const PetscInt X[], PetscBool *dups)
    542: {
    543:   PetscInt   i;
    544:   PetscHSetI ht;
    545:   PetscBool  missing;

    547:   PetscFunctionBegin;
    548:   if (n) PetscAssertPointer(X, 2);
    549:   PetscAssertPointer(dups, 3);
    550:   *dups = PETSC_FALSE;
    551:   if (n > 1) {
    552:     PetscCall(PetscHSetICreate(&ht));
    553:     PetscCall(PetscHSetIResize(ht, n));
    554:     for (i = 0; i < n; i++) {
    555:       PetscCall(PetscHSetIQueryAdd(ht, X[i], &missing));
    556:       if (!missing) {
    557:         *dups = PETSC_TRUE;
    558:         break;
    559:       }
    560:     }
    561:     PetscCall(PetscHSetIDestroy(&ht));
    562:   }
    563:   PetscFunctionReturn(PETSC_SUCCESS);
    564: }

    566: /*@
    567:   PetscFindMPIInt - Finds `PetscMPIInt` in a sorted array of `PetscMPIInt`

    569:   Not Collective

    571:   Input Parameters:
    572: + key - the integer to locate
    573: . n   - number of values in the array
    574: - X   - array of `PetscMPIInt`

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

    579:   Level: intermediate

    581: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortInt()`, `PetscSortIntWithArray()`, `PetscSortRemoveDupsInt()`
    582: @*/
    583: PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscCount n, const PetscMPIInt X[], PetscInt *loc)
    584: {
    585:   PetscCount lo = 0, hi = n;

    587:   PetscFunctionBegin;
    588:   PetscAssertPointer(loc, 4);
    589:   if (!n) {
    590:     *loc = -1;
    591:     PetscFunctionReturn(PETSC_SUCCESS);
    592:   }
    593:   PetscAssertPointer(X, 3);
    594:   while (hi - lo > 1) {
    595:     PetscCount mid = lo + (hi - lo) / 2;
    596:     PetscAssert(X[lo] <= X[mid] && X[mid] <= X[hi - 1], PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array was not sorted: (%d, %d, %d)", X[lo], X[mid], X[hi - 1]);
    597:     if (key < X[mid]) hi = mid;
    598:     else lo = mid;
    599:   }
    600:   PetscCall(PetscIntCast(key == X[lo] ? lo : -(lo + (key > X[lo]) + 1), loc));
    601:   PetscFunctionReturn(PETSC_SUCCESS);
    602: }

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

    608:   Not Collective

    610:   Input Parameters:
    611: + n - number of values
    612: . X - array of `PetscInt`
    613: - Y - second array of `PetscInt`

    615:   Level: intermediate

    617: .seealso: `PetscIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithCountArray()`
    618: @*/
    619: PetscErrorCode PetscSortIntWithArray(PetscCount n, PetscInt X[], PetscInt Y[])
    620: {
    621:   PetscInt pivot, t1, t2;

    623:   PetscFunctionBegin;
    624:   QuickSort2(PetscSortIntWithArray, X, Y, n, pivot, t1, t2);
    625:   PetscFunctionReturn(PETSC_SUCCESS);
    626: }

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

    632:   Not Collective

    634:   Input Parameters:
    635: + n - number of values
    636: . X - array of `PestcInt`
    637: . Y - second array of `PestcInt` (first array of the pair)
    638: - Z - third array of `PestcInt` (second array of the pair)

    640:   Level: intermediate

    642: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortIntWithArray()`, `PetscIntSortSemiOrdered()`, `PetscSortIntWithIntCountArrayPair()`
    643: @*/
    644: PetscErrorCode PetscSortIntWithArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscInt Z[])
    645: {
    646:   PetscInt pivot, t1, t2, t3;

    648:   PetscFunctionBegin;
    649:   QuickSort3(PetscSortIntWithArrayPair, X, Y, Z, n, pivot, t1, t2, t3);
    650:   PetscFunctionReturn(PETSC_SUCCESS);
    651: }

    653: /*@
    654:   PetscSortIntWithMPIIntArray - Sorts an array of `PetscInt` in place in increasing order;
    655:   changes a second array of `PetscMPI` to match the sorted first array.

    657:   Not Collective

    659:   Input Parameters:
    660: + n - number of values
    661: . X - array of `PetscInt`
    662: - Y - second array of `PetscMPIInt`

    664:   Level: intermediate

    666: .seealso: `PetscIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    667: @*/
    668: PetscErrorCode PetscSortIntWithMPIIntArray(PetscCount n, PetscInt X[], PetscMPIInt Y[])
    669: {
    670:   PetscInt    pivot, t1;
    671:   PetscMPIInt t2;

    673:   PetscFunctionBegin;
    674:   QuickSort2(PetscSortIntWithMPIIntArray, X, Y, n, pivot, t1, t2);
    675:   PetscFunctionReturn(PETSC_SUCCESS);
    676: }

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

    682:   Not Collective

    684:   Input Parameters:
    685: + n - number of values
    686: . X - array of `PetscInt`
    687: - Y - second array of `PetscCount`

    689:   Level: intermediate

    691: .seealso: `PetscIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    692: @*/
    693: PetscErrorCode PetscSortIntWithCountArray(PetscCount n, PetscInt X[], PetscCount Y[])
    694: {
    695:   PetscInt   pivot, t1;
    696:   PetscCount t2;

    698:   PetscFunctionBegin;
    699:   QuickSort2(PetscSortIntWithCountArray, X, Y, n, pivot, t1, t2);
    700:   PetscFunctionReturn(PETSC_SUCCESS);
    701: }

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

    707:   Not Collective

    709:   Input Parameters:
    710: + n - number of values
    711: . X - array of `PetscInt`
    712: . Y - second array of `PetscInt` (first array of the pair)
    713: - Z - third array of `PetscCount` (second array of the pair)

    715:   Level: intermediate

    717:   Note:
    718:   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.

    720: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortIntWithArray()`, `PetscIntSortSemiOrdered()`, `PetscSortIntWithArrayPair()`
    721: @*/
    722: PetscErrorCode PetscSortIntWithIntCountArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscCount Z[])
    723: {
    724:   PetscInt   pivot, t1, t2; /* pivot is take from X[], so its type is still PetscInt */
    725:   PetscCount t3;            /* temp for Z[] */

    727:   PetscFunctionBegin;
    728:   QuickSort3(PetscSortIntWithIntCountArrayPair, X, Y, Z, n, pivot, t1, t2, t3);
    729:   PetscFunctionReturn(PETSC_SUCCESS);
    730: }

    732: /*@
    733:   PetscSortedMPIInt - Determines whether the `PetscMPIInt` array is sorted.

    735:   Not Collective

    737:   Input Parameters:
    738: + n - number of values
    739: - X - array of `PetscMPIInt`

    741:   Output Parameter:
    742: . sorted - flag whether the array is sorted

    744:   Level: intermediate

    746: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortMPIInt()`, `PetscSortedInt()`, `PetscSortedReal()`
    747: @*/
    748: PetscErrorCode PetscSortedMPIInt(PetscCount n, const PetscMPIInt X[], PetscBool *sorted)
    749: {
    750:   PetscFunctionBegin;
    751:   PetscSorted(n, X, *sorted);
    752:   PetscFunctionReturn(PETSC_SUCCESS);
    753: }

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

    758:   Not Collective

    760:   Input Parameters:
    761: + n - number of values
    762: - X - array of `PetscMPIInt`

    764:   Level: intermediate

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

    771: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`
    772: @*/
    773: PetscErrorCode PetscSortMPIInt(PetscCount n, PetscMPIInt X[])
    774: {
    775:   PetscMPIInt pivot, t1;

    777:   PetscFunctionBegin;
    778:   QuickSort1(PetscSortMPIInt, X, n, pivot, t1);
    779:   PetscFunctionReturn(PETSC_SUCCESS);
    780: }

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

    785:   Not Collective

    787:   Input Parameters:
    788: + n - number of values
    789: - X - array of `PetscMPIInt`

    791:   Output Parameter:
    792: . n - number of non-redundant values

    794:   Level: intermediate

    796: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
    797: @*/
    798: PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n, PetscMPIInt X[])
    799: {
    800:   PetscInt s = 0, N = *n, b = 0;

    802:   PetscFunctionBegin;
    803:   PetscCall(PetscSortMPIInt(N, X));
    804:   for (PetscInt i = 0; i < N - 1; i++) {
    805:     if (X[b + s + 1] != X[b]) {
    806:       X[b + 1] = X[b + s + 1];
    807:       b++;
    808:     } else s++;
    809:   }
    810:   *n = N - s;
    811:   PetscFunctionReturn(PETSC_SUCCESS);
    812: }

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

    818:   Not Collective

    820:   Input Parameters:
    821: + n - number of values
    822: . X - array of `PetscMPIInt`
    823: - Y - second array of `PetscMPIInt`

    825:   Level: intermediate

    827: .seealso: `PetscMPIIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
    828: @*/
    829: PetscErrorCode PetscSortMPIIntWithArray(PetscCount n, PetscMPIInt X[], PetscMPIInt Y[])
    830: {
    831:   PetscMPIInt pivot, t1, t2;

    833:   PetscFunctionBegin;
    834:   QuickSort2(PetscSortMPIIntWithArray, X, Y, n, pivot, t1, t2);
    835:   PetscFunctionReturn(PETSC_SUCCESS);
    836: }

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

    842:   Not Collective

    844:   Input Parameters:
    845: + n - number of values
    846: . X - array of `PetscMPIInt`
    847: - Y - second array of `PetscInt`

    849:   Level: intermediate

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

    854: .seealso: `PetscSortMPIIntWithArray()`, `PetscIntSortSemiOrderedWithArray()`, `PetscTimSortWithArray()`
    855: @*/
    856: PetscErrorCode PetscSortMPIIntWithIntArray(PetscCount n, PetscMPIInt X[], PetscInt Y[])
    857: {
    858:   PetscMPIInt pivot, t1;
    859:   PetscInt    t2;

    861:   PetscFunctionBegin;
    862:   QuickSort2(PetscSortMPIIntWithIntArray, X, Y, n, pivot, t1, t2);
    863:   PetscFunctionReturn(PETSC_SUCCESS);
    864: }

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

    870:   Not Collective

    872:   Input Parameters:
    873: + n - number of values
    874: . X - array of `PetscInt`
    875: - Y - second array of `PetscScalar`

    877:   Level: intermediate

    879: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    880: @*/
    881: PetscErrorCode PetscSortIntWithScalarArray(PetscCount n, PetscInt X[], PetscScalar Y[])
    882: {
    883:   PetscInt    pivot, t1;
    884:   PetscScalar t2;

    886:   PetscFunctionBegin;
    887:   QuickSort2(PetscSortIntWithScalarArray, X, Y, n, pivot, t1, t2);
    888:   PetscFunctionReturn(PETSC_SUCCESS);
    889: }

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

    896:   Not Collective, No Fortran Support

    898:   Input Parameters:
    899: + n    - number of values
    900: . X    - array of `PetscInt`
    901: . Y    - second array of data
    902: . size - sizeof elements in the data array in bytes
    903: - t2   - workspace of "size" bytes used when sorting

    905:   Level: intermediate

    907: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    908: @*/
    909: PetscErrorCode PetscSortIntWithDataArray(PetscCount n, PetscInt X[], void *Y, size_t size, void *t2)
    910: {
    911:   char      *YY = (char *)Y;
    912:   PetscCount hi = n - 1;
    913:   PetscInt   pivot, t1;

    915:   PetscFunctionBegin;
    916:   if (n < 8) {
    917:     for (PetscCount i = 0; i < n; i++) {
    918:       pivot = X[i];
    919:       for (PetscCount j = i + 1; j < n; j++) {
    920:         if (pivot > X[j]) {
    921:           SWAP2Data(X[i], X[j], YY + size * i, YY + size * j, t1, t2, size);
    922:           pivot = X[i];
    923:         }
    924:       }
    925:     }
    926:   } else {
    927:     /* Two way partition */
    928:     PetscCount l = 0, r = hi;

    930:     pivot = X[MEDIAN(X, hi)];
    931:     while (1) {
    932:       while (X[l] < pivot) l++;
    933:       while (X[r] > pivot) r--;
    934:       if (l >= r) {
    935:         r++;
    936:         break;
    937:       }
    938:       SWAP2Data(X[l], X[r], YY + size * l, YY + size * r, t1, t2, size);
    939:       l++;
    940:       r--;
    941:     }
    942:     PetscCall(PetscSortIntWithDataArray(l, X, Y, size, t2));
    943:     PetscCall(PetscSortIntWithDataArray(hi - r + 1, X + r, YY + size * r, size, t2));
    944:   }
    945:   PetscFunctionReturn(PETSC_SUCCESS);
    946: }

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

    951:   Not Collective

    953:   Input Parameters:
    954: + an - number of values in the first array
    955: . aI - first sorted array of `PetscInt`
    956: . bn - number of values in the second array
    957: - bI - second array of `PetscInt`

    959:   Output Parameters:
    960: + n - number of values in the merged array
    961: - L - merged sorted array, this is allocated if an array is not provided

    963:   Level: intermediate

    965: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    966: @*/
    967: PetscErrorCode PetscMergeIntArray(PetscInt an, const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L)
    968: {
    969:   PetscInt *L_ = *L, ak, bk, k;

    971:   PetscFunctionBegin;
    972:   if (!L_) {
    973:     PetscCall(PetscMalloc1(an + bn, L));
    974:     L_ = *L;
    975:   }
    976:   k = ak = bk = 0;
    977:   while (ak < an && bk < bn) {
    978:     if (aI[ak] == bI[bk]) {
    979:       L_[k] = aI[ak];
    980:       ++ak;
    981:       ++bk;
    982:       ++k;
    983:     } else if (aI[ak] < bI[bk]) {
    984:       L_[k] = aI[ak];
    985:       ++ak;
    986:       ++k;
    987:     } else {
    988:       L_[k] = bI[bk];
    989:       ++bk;
    990:       ++k;
    991:     }
    992:   }
    993:   if (ak < an) {
    994:     PetscCall(PetscArraycpy(L_ + k, aI + ak, an - ak));
    995:     k += (an - ak);
    996:   }
    997:   if (bk < bn) {
    998:     PetscCall(PetscArraycpy(L_ + k, bI + bk, bn - bk));
    999:     k += (bn - bk);
    1000:   }
    1001:   *n = k;
    1002:   PetscFunctionReturn(PETSC_SUCCESS);
    1003: }

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

    1010:   Not Collective

    1012:   Input Parameters:
    1013: + an - number of values in the first array
    1014: . aI - first sorted array of `PetscInt`
    1015: . aJ - first additional array of `PetscInt`
    1016: . bn - number of values in the second array
    1017: . bI - second array of `PetscInt`
    1018: - bJ - second additional of `PetscInt`

    1020:   Output Parameters:
    1021: + n - number of values in the merged array (== an + bn)
    1022: . L - merged sorted array
    1023: - J - merged additional array

    1025:   Note:
    1026:   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

    1028:   Level: intermediate

    1030: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    1031: @*/
    1032: PetscErrorCode PetscMergeIntArrayPair(PetscInt an, const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J)
    1033: {
    1034:   PetscInt n_, *L_, *J_, ak, bk, k;

    1036:   PetscFunctionBegin;
    1037:   PetscAssertPointer(L, 8);
    1038:   PetscAssertPointer(J, 9);
    1039:   n_ = an + bn;
    1040:   *n = n_;
    1041:   if (!*L) PetscCall(PetscMalloc1(n_, L));
    1042:   L_ = *L;
    1043:   if (!*J) PetscCall(PetscMalloc1(n_, J));
    1044:   J_ = *J;
    1045:   k = ak = bk = 0;
    1046:   while (ak < an && bk < bn) {
    1047:     if (aI[ak] <= bI[bk]) {
    1048:       L_[k] = aI[ak];
    1049:       J_[k] = aJ[ak];
    1050:       ++ak;
    1051:       ++k;
    1052:     } else {
    1053:       L_[k] = bI[bk];
    1054:       J_[k] = bJ[bk];
    1055:       ++bk;
    1056:       ++k;
    1057:     }
    1058:   }
    1059:   if (ak < an) {
    1060:     PetscCall(PetscArraycpy(L_ + k, aI + ak, an - ak));
    1061:     PetscCall(PetscArraycpy(J_ + k, aJ + ak, an - ak));
    1062:     k += (an - ak);
    1063:   }
    1064:   if (bk < bn) {
    1065:     PetscCall(PetscArraycpy(L_ + k, bI + bk, bn - bk));
    1066:     PetscCall(PetscArraycpy(J_ + k, bJ + bk, bn - bk));
    1067:   }
    1068:   PetscFunctionReturn(PETSC_SUCCESS);
    1069: }

    1071: /*@
    1072:   PetscMergeMPIIntArray -     Merges two SORTED `PetscMPIInt` arrays.

    1074:   Not Collective

    1076:   Input Parameters:
    1077: + an - number of values in the first array
    1078: . aI - first sorted array of `PetscMPIInt`
    1079: . bn - number of values in the second array
    1080: - bI - second array of `PetscMPIInt`

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

    1086:   Level: intermediate

    1088: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
    1089: @*/
    1090: PetscErrorCode PetscMergeMPIIntArray(PetscInt an, const PetscMPIInt aI[], PetscInt bn, const PetscMPIInt bI[], PetscInt *n, PetscMPIInt **L)
    1091: {
    1092:   PetscInt ai, bi, k;

    1094:   PetscFunctionBegin;
    1095:   if (!*L) PetscCall(PetscMalloc1(an + bn, L));
    1096:   for (ai = 0, bi = 0, k = 0; ai < an || bi < bn;) {
    1097:     PetscInt t = -1;
    1098:     for (; ai < an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai];
    1099:     for (; bi < bn && bI[bi] == t; bi++);
    1100:     for (; bi < bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi];
    1101:     for (; ai < an && aI[ai] == t; ai++);
    1102:   }
    1103:   *n = k;
    1104:   PetscFunctionReturn(PETSC_SUCCESS);
    1105: }

    1107: /*@C
    1108:   PetscProcessTree - Prepares tree data to be displayed graphically

    1110:   Not Collective, No Fortran Support

    1112:   Input Parameters:
    1113: + n        - number of values
    1114: . mask     - indicates those entries in the tree, location 0 is always masked
    1115: - parentid - indicates the parent of each entry

    1117:   Output Parameters:
    1118: + Nlevels   - the number of levels
    1119: . Level     - for each node tells its level
    1120: . Levelcnt  - the number of nodes on each level
    1121: . Idbylevel - a list of ids on each of the levels, first level followed by second etc
    1122: - Column    - for each id tells its column index

    1124:   Level: developer

    1126:   Note:
    1127:   This code is not currently used

    1129: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
    1130: @*/
    1131: PetscErrorCode PetscProcessTree(PetscInt n, const PetscBool mask[], const PetscInt parentid[], PetscInt *Nlevels, PetscInt **Level, PetscInt **Levelcnt, PetscInt **Idbylevel, PetscInt **Column)
    1132: {
    1133:   PetscInt  i, j, cnt, nmask = 0, nlevels = 0, *level, *levelcnt, levelmax = 0, *workid, *workparentid, tcnt = 0, *idbylevel, *column;
    1134:   PetscBool done = PETSC_FALSE;

    1136:   PetscFunctionBegin;
    1137:   PetscCheck(mask[0], PETSC_COMM_SELF, PETSC_ERR_SUP, "Mask of 0th location must be set");
    1138:   for (i = 0; i < n; i++) {
    1139:     if (mask[i]) continue;
    1140:     PetscCheck(parentid[i] != i, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Node labeled as own parent");
    1141:     PetscCheck(!parentid[i] || !mask[parentid[i]], PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Parent is masked");
    1142:   }

    1144:   for (i = 0; i < n; i++) {
    1145:     if (!mask[i]) nmask++;
    1146:   }

    1148:   /* determine the level in the tree of each node */
    1149:   PetscCall(PetscCalloc1(n, &level));

    1151:   level[0] = 1;
    1152:   while (!done) {
    1153:     done = PETSC_TRUE;
    1154:     for (i = 0; i < n; i++) {
    1155:       if (mask[i]) continue;
    1156:       if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1;
    1157:       else if (!level[i]) done = PETSC_FALSE;
    1158:     }
    1159:   }
    1160:   for (i = 0; i < n; i++) {
    1161:     level[i]--;
    1162:     nlevels = PetscMax(nlevels, level[i]);
    1163:   }

    1165:   /* count the number of nodes on each level and its max */
    1166:   PetscCall(PetscCalloc1(nlevels, &levelcnt));
    1167:   for (i = 0; i < n; i++) {
    1168:     if (mask[i]) continue;
    1169:     levelcnt[level[i] - 1]++;
    1170:   }
    1171:   for (i = 0; i < nlevels; i++) levelmax = PetscMax(levelmax, levelcnt[i]);

    1173:   /* for each level sort the ids by the parent id */
    1174:   PetscCall(PetscMalloc2(levelmax, &workid, levelmax, &workparentid));
    1175:   PetscCall(PetscMalloc1(nmask, &idbylevel));
    1176:   for (j = 1; j <= nlevels; j++) {
    1177:     cnt = 0;
    1178:     for (i = 0; i < n; i++) {
    1179:       if (mask[i]) continue;
    1180:       if (level[i] != j) continue;
    1181:       workid[cnt]         = i;
    1182:       workparentid[cnt++] = parentid[i];
    1183:     }
    1184:     /*  PetscIntView(cnt,workparentid,0);
    1185:     PetscIntView(cnt,workid,0);
    1186:     PetscCall(PetscSortIntWithArray(cnt,workparentid,workid));
    1187:     PetscIntView(cnt,workparentid,0);
    1188:     PetscIntView(cnt,workid,0);*/
    1189:     PetscCall(PetscArraycpy(idbylevel + tcnt, workid, cnt));
    1190:     tcnt += cnt;
    1191:   }
    1192:   PetscCheck(tcnt == nmask, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Inconsistent count of unmasked nodes");
    1193:   PetscCall(PetscFree2(workid, workparentid));

    1195:   /* for each node list its column */
    1196:   PetscCall(PetscMalloc1(n, &column));
    1197:   cnt = 0;
    1198:   for (j = 0; j < nlevels; j++) {
    1199:     for (i = 0; i < levelcnt[j]; i++) column[idbylevel[cnt++]] = i;
    1200:   }

    1202:   *Nlevels   = nlevels;
    1203:   *Level     = level;
    1204:   *Levelcnt  = levelcnt;
    1205:   *Idbylevel = idbylevel;
    1206:   *Column    = column;
    1207:   PetscFunctionReturn(PETSC_SUCCESS);
    1208: }

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

    1213:   Collective

    1215:   Input Parameters:
    1216: + comm - the MPI communicator
    1217: . n    - the local number of `PetscInt`
    1218: - keys - the local array of `PetscInt`

    1220:   Output Parameters:
    1221: . is_sorted - whether the array is globally sorted

    1223:   Level: developer

    1225: .seealso: `PetscParallelSortInt()`
    1226: @*/
    1227: PetscErrorCode PetscParallelSortedInt(MPI_Comm comm, PetscInt n, const PetscInt keys[], PetscBool *is_sorted)
    1228: {
    1229:   PetscBool   sorted;
    1230:   PetscInt    i, min, max, prevmax;
    1231:   PetscMPIInt rank;

    1233:   PetscFunctionBegin;
    1234:   sorted = PETSC_TRUE;
    1235:   min    = PETSC_INT_MAX;
    1236:   max    = PETSC_INT_MIN;
    1237:   if (n) {
    1238:     min = keys[0];
    1239:     max = keys[0];
    1240:   }
    1241:   for (i = 1; i < n; i++) {
    1242:     if (keys[i] < keys[i - 1]) break;
    1243:     min = PetscMin(min, keys[i]);
    1244:     max = PetscMax(max, keys[i]);
    1245:   }
    1246:   if (i < n) sorted = PETSC_FALSE;
    1247:   prevmax = PETSC_INT_MIN;
    1248:   PetscCallMPI(MPI_Exscan(&max, &prevmax, 1, MPIU_INT, MPI_MAX, comm));
    1249:   PetscCallMPI(MPI_Comm_rank(comm, &rank));
    1250:   if (rank == 0) prevmax = PETSC_INT_MIN;
    1251:   if (prevmax > min) sorted = PETSC_FALSE;
    1252:   PetscCallMPI(MPIU_Allreduce(&sorted, is_sorted, 1, MPIU_BOOL, MPI_LAND, comm));
    1253:   PetscFunctionReturn(PETSC_SUCCESS);
    1254: }