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:     PetscCall(PetscMemcpy(t2, c, siz)); \
 49:     PetscCall(PetscMemcpy(c, d, siz)); \
 50:     PetscCall(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:       PetscCall(FuncName(l, X)); \
172:       PetscCall(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:       PetscCall(FuncName(l, X)); \
195:       PetscCall(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:       PetscCall(FuncName(l, X, Y)); \
217:       PetscCall(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:       PetscCall(FuncName(l, X, Y, Z)); \
239:       PetscCall(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 Parameter:
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: {
261:   PetscFunctionBegin;
264:   PetscSorted(n, X, *sorted);
265:   PetscFunctionReturn(PETSC_SUCCESS);
266: }

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

271:    Not Collective

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

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

280:    Level: intermediate

282: .seealso: `PetscSortInt64()`, `PetscSortInt()`, `PetscSortedMPIInt()`, `PetscSortedReal()`
283: @*/
284: PetscErrorCode PetscSortedInt64(PetscInt n, const PetscInt64 X[], PetscBool *sorted)
285: {
286:   PetscFunctionBegin;
289:   PetscSorted(n, X, *sorted);
290:   PetscFunctionReturn(PETSC_SUCCESS);
291: }

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

296:    Not Collective

298:    Input Parameters:
299: +  n  - number of values
300: -  X  - array of integers

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

307:    Level: intermediate

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

315:   PetscFunctionBegin;
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 integers

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

333:    Level: intermediate

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

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

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

350:    Not Collective

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

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(PetscInt n, PetscCount X[])
364: {
365:   PetscCount pivot, t1;

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

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

376:    Not Collective

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

382:    Level: intermediate

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

390:   PetscFunctionBegin;
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 integers

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;
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 integers

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

441:    Level: intermediate

443: .seealso: `PetscSortInt()`, `PetscCheckDupsInt()`, `PetscSortRemoveDupsInt()`, `PetscSortedRemoveDupsInt()`
444: @*/
445: PetscErrorCode PetscSortedCheckDupsInt(PetscInt 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 integers

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;
481:   PetscCall(PetscSortInt(*n, X));
482:   PetscCall(PetscSortedRemoveDupsInt(n, X));
483:   PetscFunctionReturn(PETSC_SUCCESS);
484: }

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

489:    Not Collective

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

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, PetscInt n, const PetscInt X[], PetscInt *loc)
504: {
505:   PetscInt lo = 0, hi = n;

507:   PetscFunctionBegin;
509:   if (!n) {
510:     *loc = -1;
511:     PetscFunctionReturn(PETSC_SUCCESS);
512:   }
514:   PetscCheckSorted(n, X);
515:   while (hi - lo > 1) {
516:     PetscInt mid = lo + (hi - lo) / 2;
517:     if (key < X[mid]) hi = mid;
518:     else lo = mid;
519:   }
520:   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);
521:   PetscFunctionReturn(PETSC_SUCCESS);
522: }

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

527:    Not Collective

529:    Input Parameters:
530: +  n  - number of values in the array
531: -  X  - array of integers

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

536:    Level: intermediate

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

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

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

568:    Not Collective

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

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

578:    Level: intermediate

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

586:   PetscFunctionBegin;
588:   if (!n) {
589:     *loc = -1;
590:     PetscFunctionReturn(PETSC_SUCCESS);
591:   }
593:   PetscCheckSorted(n, X);
594:   while (hi - lo > 1) {
595:     PetscInt mid = lo + (hi - lo) / 2;
596:     if (key < X[mid]) hi = mid;
597:     else lo = mid;
598:   }
599:   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);
600:   PetscFunctionReturn(PETSC_SUCCESS);
601: }

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

607:    Not Collective

609:    Input Parameters:
610: +  n  - number of values
611: .  X  - array of integers
612: -  Y  - second array of integers

614:    Level: intermediate

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

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

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

631:    Not Collective

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

639:    Level: intermediate

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

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

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

656:    Not Collective

658:    Input Parameters:
659: +  n  - number of values
660: .  X  - array of integers
661: -  Y  - second array of PetscCounts (signed integers)

663:    Level: intermediate

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

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

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

681:    Not Collective

683:    Input Parameters:
684: +  n  - number of values
685: .  X  - array of integers
686: .  Y  - second array of integers (first array of the pair)
687: -  Z  - third array of PetscCounts  (second array of the pair)

689:    Level: intermediate

691:    Note:
692:     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.

694: .seealso: `PetscSortReal()`, `PetscSortIntPermutation()`, `PetscSortIntWithArray()`, `PetscIntSortSemiOrdered()`, `PetscSortIntWithArrayPair()`
695: @*/
696: PetscErrorCode PetscSortIntWithIntCountArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscCount Z[])
697: {
698:   PetscInt   pivot, t1, t2; /* pivot is take from X[], so its type is still PetscInt */
699:   PetscCount t3;            /* temp for Z[] */

701:   PetscFunctionBegin;
702:   QuickSort3(PetscSortIntWithIntCountArrayPair, X, Y, Z, n, pivot, t1, t2, t3);
703:   PetscFunctionReturn(PETSC_SUCCESS);
704: }

706: /*@
707:   PetscSortedMPIInt - Determines whether the `PetscMPIInt` array is sorted.

709:    Not Collective

711:    Input Parameters:
712: +  n  - number of values
713: -  X  - array of integers

715:    Output Parameter:
716: .  sorted - flag whether the array is sorted

718:    Level: intermediate

720: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortMPIInt()`, `PetscSortedInt()`, `PetscSortedReal()`
721: @*/
722: PetscErrorCode PetscSortedMPIInt(PetscInt n, const PetscMPIInt X[], PetscBool *sorted)
723: {
724:   PetscFunctionBegin;
725:   PetscSorted(n, X, *sorted);
726:   PetscFunctionReturn(PETSC_SUCCESS);
727: }

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

732:    Not Collective

734:    Input Parameters:
735: +  n  - number of values
736: -  X  - array of integers

738:    Level: intermediate

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

745: .seealso: `PetscMPIIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`
746: @*/
747: PetscErrorCode PetscSortMPIInt(PetscInt n, PetscMPIInt X[])
748: {
749:   PetscMPIInt pivot, t1;

751:   PetscFunctionBegin;
752:   QuickSort1(PetscSortMPIInt, X, n, pivot, t1);
753:   PetscFunctionReturn(PETSC_SUCCESS);
754: }

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

759:    Not Collective

761:    Input Parameters:
762: +  n  - number of values
763: -  X  - array of integers

765:    Output Parameter:
766: .  n - number of non-redundant values

768:    Level: intermediate

770: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
771: @*/
772: PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n, PetscMPIInt X[])
773: {
774:   PetscInt s = 0, N = *n, b = 0;

776:   PetscFunctionBegin;
777:   PetscCall(PetscSortMPIInt(N, X));
778:   for (PetscInt i = 0; i < N - 1; i++) {
779:     if (X[b + s + 1] != X[b]) {
780:       X[b + 1] = X[b + s + 1];
781:       b++;
782:     } else s++;
783:   }
784:   *n = N - s;
785:   PetscFunctionReturn(PETSC_SUCCESS);
786: }

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

792:    Not Collective

794:    Input Parameters:
795: +  n  - number of values
796: .  X  - array of integers
797: -  Y  - second array of integers

799:    Level: intermediate

801: .seealso: `PetscMPIIntSortSemiOrderedWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`
802: @*/
803: PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n, PetscMPIInt X[], PetscMPIInt Y[])
804: {
805:   PetscMPIInt pivot, t1, t2;

807:   PetscFunctionBegin;
808:   QuickSort2(PetscSortMPIIntWithArray, X, Y, n, pivot, t1, t2);
809:   PetscFunctionReturn(PETSC_SUCCESS);
810: }

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

816:    Not Collective

818:    Input Parameters:
819: +  n  - number of values
820: .  X  - array of MPI integers
821: -  Y  - second array of Petsc integers

823:    Level: intermediate

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

828: .seealso: `PetscSortMPIIntWithArray()`, `PetscIntSortSemiOrderedWithArray()`, `PetscTimSortWithArray()`
829: @*/
830: PetscErrorCode PetscSortMPIIntWithIntArray(PetscMPIInt n, PetscMPIInt X[], PetscInt Y[])
831: {
832:   PetscMPIInt pivot, t1;
833:   PetscInt    t2;

835:   PetscFunctionBegin;
836:   QuickSort2(PetscSortMPIIntWithIntArray, X, Y, n, pivot, t1, t2);
837:   PetscFunctionReturn(PETSC_SUCCESS);
838: }

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

844:    Not Collective

846:    Input Parameters:
847: +  n  - number of values
848: .  X  - array of integers
849: -  Y  - second array of scalars

851:    Level: intermediate

853: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
854: @*/
855: PetscErrorCode PetscSortIntWithScalarArray(PetscInt n, PetscInt X[], PetscScalar Y[])
856: {
857:   PetscInt    pivot, t1;
858:   PetscScalar t2;

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

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

870:    Not Collective

872:    Input Parameters:
873: +  n  - number of values
874: .  X  - array of integers
875: .  Y  - second array of data
876: .  size - sizeof elements in the data array in bytes
877: -  t2   - workspace of "size" bytes used when sorting

879:    Level: intermediate

881: .seealso: `PetscTimSortWithArray()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
882: @*/
883: PetscErrorCode PetscSortIntWithDataArray(PetscInt n, PetscInt X[], void *Y, size_t size, void *t2)
884: {
885:   char    *YY = (char *)Y;
886:   PetscInt t1, pivot, hi = n - 1;

888:   PetscFunctionBegin;
889:   if (n < 8) {
890:     for (PetscInt i = 0; i < n; i++) {
891:       pivot = X[i];
892:       for (PetscInt j = i + 1; j < n; j++) {
893:         if (pivot > X[j]) {
894:           SWAP2Data(X[i], X[j], YY + size * i, YY + size * j, t1, t2, size);
895:           pivot = X[i];
896:         }
897:       }
898:     }
899:   } else {
900:     /* Two way partition */
901:     PetscInt l = 0, r = hi;

903:     pivot = X[MEDIAN(X, hi)];
904:     while (1) {
905:       while (X[l] < pivot) l++;
906:       while (X[r] > pivot) r--;
907:       if (l >= r) {
908:         r++;
909:         break;
910:       }
911:       SWAP2Data(X[l], X[r], YY + size * l, YY + size * r, t1, t2, size);
912:       l++;
913:       r--;
914:     }
915:     PetscCall(PetscSortIntWithDataArray(l, X, Y, size, t2));
916:     PetscCall(PetscSortIntWithDataArray(hi - r + 1, X + r, YY + size * r, size, t2));
917:   }
918:   PetscFunctionReturn(PETSC_SUCCESS);
919: }

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

924:    Not Collective

926:    Input Parameters:
927: +  an  - number of values in the first array
928: .  aI  - first sorted array of integers
929: .  bn  - number of values in the second array
930: -  bI  - second array of integers

932:    Output Parameters:
933: +  n   - number of values in the merged array
934: -  L   - merged sorted array, this is allocated if an array is not provided

936:    Level: intermediate

938: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
939: @*/
940: PetscErrorCode PetscMergeIntArray(PetscInt an, const PetscInt aI[], PetscInt bn, const PetscInt bI[], PetscInt *n, PetscInt **L)
941: {
942:   PetscInt *L_ = *L, ak, bk, k;

944:   PetscFunctionBegin;
945:   if (!L_) {
946:     PetscCall(PetscMalloc1(an + bn, L));
947:     L_ = *L;
948:   }
949:   k = ak = bk = 0;
950:   while (ak < an && bk < bn) {
951:     if (aI[ak] == bI[bk]) {
952:       L_[k] = aI[ak];
953:       ++ak;
954:       ++bk;
955:       ++k;
956:     } else if (aI[ak] < bI[bk]) {
957:       L_[k] = aI[ak];
958:       ++ak;
959:       ++k;
960:     } else {
961:       L_[k] = bI[bk];
962:       ++bk;
963:       ++k;
964:     }
965:   }
966:   if (ak < an) {
967:     PetscCall(PetscArraycpy(L_ + k, aI + ak, an - ak));
968:     k += (an - ak);
969:   }
970:   if (bk < bn) {
971:     PetscCall(PetscArraycpy(L_ + k, bI + bk, bn - bk));
972:     k += (bn - bk);
973:   }
974:   *n = k;
975:   PetscFunctionReturn(PETSC_SUCCESS);
976: }

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

983:    Not Collective

985:    Input Parameters:
986: +  an  - number of values in the first array
987: .  aI  - first sorted array of integers
988: .  aJ  - first additional array of integers
989: .  bn  - number of values in the second array
990: .  bI  - second array of integers
991: -  bJ  - second additional of integers

993:    Output Parameters:
994: +  n   - number of values in the merged array (== an + bn)
995: .  L   - merged sorted array
996: -  J   - merged additional array

998:    Note:
999:     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

1001:    Level: intermediate

1003: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
1004: @*/
1005: PetscErrorCode PetscMergeIntArrayPair(PetscInt an, const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J)
1006: {
1007:   PetscInt n_, *L_, *J_, ak, bk, k;

1009:   PetscFunctionBegin;
1012:   n_ = an + bn;
1013:   *n = n_;
1014:   if (!*L) PetscCall(PetscMalloc1(n_, L));
1015:   L_ = *L;
1016:   if (!*J) PetscCall(PetscMalloc1(n_, J));
1017:   J_ = *J;
1018:   k = ak = bk = 0;
1019:   while (ak < an && bk < bn) {
1020:     if (aI[ak] <= bI[bk]) {
1021:       L_[k] = aI[ak];
1022:       J_[k] = aJ[ak];
1023:       ++ak;
1024:       ++k;
1025:     } else {
1026:       L_[k] = bI[bk];
1027:       J_[k] = bJ[bk];
1028:       ++bk;
1029:       ++k;
1030:     }
1031:   }
1032:   if (ak < an) {
1033:     PetscCall(PetscArraycpy(L_ + k, aI + ak, an - ak));
1034:     PetscCall(PetscArraycpy(J_ + k, aJ + ak, an - ak));
1035:     k += (an - ak);
1036:   }
1037:   if (bk < bn) {
1038:     PetscCall(PetscArraycpy(L_ + k, bI + bk, bn - bk));
1039:     PetscCall(PetscArraycpy(J_ + k, bJ + bk, bn - bk));
1040:   }
1041:   PetscFunctionReturn(PETSC_SUCCESS);
1042: }

1044: /*@
1045:    PetscMergeMPIIntArray -     Merges two SORTED `PetscMPIInt` arrays.

1047:    Not Collective

1049:    Input Parameters:
1050: +  an  - number of values in the first array
1051: .  aI  - first sorted array of integers
1052: .  bn  - number of values in the second array
1053: -  bI  - second array of integers

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

1059:    Level: intermediate

1061: .seealso: `PetscIntSortSemiOrdered()`, `PetscSortReal()`, `PetscSortIntWithPermutation()`, `PetscSortInt()`, `PetscSortIntWithArray()`
1062: @*/
1063: PetscErrorCode PetscMergeMPIIntArray(PetscInt an, const PetscMPIInt aI[], PetscInt bn, const PetscMPIInt bI[], PetscInt *n, PetscMPIInt **L)
1064: {
1065:   PetscInt ai, bi, k;

1067:   PetscFunctionBegin;
1068:   if (!*L) PetscCall(PetscMalloc1((an + bn), L));
1069:   for (ai = 0, bi = 0, k = 0; ai < an || bi < bn;) {
1070:     PetscInt t = -1;
1071:     for (; ai < an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai];
1072:     for (; bi < bn && bI[bi] == t; bi++)
1073:       ;
1074:     for (; bi < bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi];
1075:     for (; ai < an && aI[ai] == t; ai++)
1076:       ;
1077:   }
1078:   *n = k;
1079:   PetscFunctionReturn(PETSC_SUCCESS);
1080: }

1082: /*@C
1083:    PetscProcessTree - Prepares tree data to be displayed graphically

1085:    Not Collective

1087:    Input Parameters:
1088: +  n  - number of values
1089: .  mask - indicates those entries in the tree, location 0 is always masked
1090: -  parentid - indicates the parent of each entry

1092:    Output Parameters:
1093: +  Nlevels - the number of levels
1094: .  Level - for each node tells its level
1095: .  Levelcnts - the number of nodes on each level
1096: .  Idbylevel - a list of ids on each of the levels, first level followed by second etc
1097: -  Column - for each id tells its column index

1099:    Level: developer

1101:    Note:
1102:     This code is not currently used

1104: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
1105: @*/
1106: PetscErrorCode PetscProcessTree(PetscInt n, const PetscBool mask[], const PetscInt parentid[], PetscInt *Nlevels, PetscInt **Level, PetscInt **Levelcnt, PetscInt **Idbylevel, PetscInt **Column)
1107: {
1108:   PetscInt  i, j, cnt, nmask = 0, nlevels = 0, *level, *levelcnt, levelmax = 0, *workid, *workparentid, tcnt = 0, *idbylevel, *column;
1109:   PetscBool done = PETSC_FALSE;

1111:   PetscFunctionBegin;
1112:   PetscCheck(mask[0], PETSC_COMM_SELF, PETSC_ERR_SUP, "Mask of 0th location must be set");
1113:   for (i = 0; i < n; i++) {
1114:     if (mask[i]) continue;
1115:     PetscCheck(parentid[i] != i, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Node labeled as own parent");
1116:     PetscCheck(!parentid[i] || !mask[parentid[i]], PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Parent is masked");
1117:   }

1119:   for (i = 0; i < n; i++) {
1120:     if (!mask[i]) nmask++;
1121:   }

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

1126:   level[0] = 1;
1127:   while (!done) {
1128:     done = PETSC_TRUE;
1129:     for (i = 0; i < n; i++) {
1130:       if (mask[i]) continue;
1131:       if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1;
1132:       else if (!level[i]) done = PETSC_FALSE;
1133:     }
1134:   }
1135:   for (i = 0; i < n; i++) {
1136:     level[i]--;
1137:     nlevels = PetscMax(nlevels, level[i]);
1138:   }

1140:   /* count the number of nodes on each level and its max */
1141:   PetscCall(PetscCalloc1(nlevels, &levelcnt));
1142:   for (i = 0; i < n; i++) {
1143:     if (mask[i]) continue;
1144:     levelcnt[level[i] - 1]++;
1145:   }
1146:   for (i = 0; i < nlevels; i++) levelmax = PetscMax(levelmax, levelcnt[i]);

1148:   /* for each level sort the ids by the parent id */
1149:   PetscCall(PetscMalloc2(levelmax, &workid, levelmax, &workparentid));
1150:   PetscCall(PetscMalloc1(nmask, &idbylevel));
1151:   for (j = 1; j <= nlevels; j++) {
1152:     cnt = 0;
1153:     for (i = 0; i < n; i++) {
1154:       if (mask[i]) continue;
1155:       if (level[i] != j) continue;
1156:       workid[cnt]         = i;
1157:       workparentid[cnt++] = parentid[i];
1158:     }
1159:     /*  PetscIntView(cnt,workparentid,0);
1160:     PetscIntView(cnt,workid,0);
1161:     PetscCall(PetscSortIntWithArray(cnt,workparentid,workid));
1162:     PetscIntView(cnt,workparentid,0);
1163:     PetscIntView(cnt,workid,0);*/
1164:     PetscCall(PetscArraycpy(idbylevel + tcnt, workid, cnt));
1165:     tcnt += cnt;
1166:   }
1167:   PetscCheck(tcnt == nmask, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Inconsistent count of unmasked nodes");
1168:   PetscCall(PetscFree2(workid, workparentid));

1170:   /* for each node list its column */
1171:   PetscCall(PetscMalloc1(n, &column));
1172:   cnt = 0;
1173:   for (j = 0; j < nlevels; j++) {
1174:     for (i = 0; i < levelcnt[j]; i++) column[idbylevel[cnt++]] = i;
1175:   }

1177:   *Nlevels   = nlevels;
1178:   *Level     = level;
1179:   *Levelcnt  = levelcnt;
1180:   *Idbylevel = idbylevel;
1181:   *Column    = column;
1182:   PetscFunctionReturn(PETSC_SUCCESS);
1183: }

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

1188:   Collective

1190:   Input Parameters:
1191: + comm - the MPI communicator
1192: . n - the local number of integers
1193: - keys - the local array of integers

1195:   Output Parameters:
1196: . is_sorted - whether the array is globally sorted

1198:   Level: developer

1200: .seealso: `PetscParallelSortInt()`
1201: @*/
1202: PetscErrorCode PetscParallelSortedInt(MPI_Comm comm, PetscInt n, const PetscInt keys[], PetscBool *is_sorted)
1203: {
1204:   PetscBool   sorted;
1205:   PetscInt    i, min, max, prevmax;
1206:   PetscMPIInt rank;

1208:   PetscFunctionBegin;
1209:   sorted = PETSC_TRUE;
1210:   min    = PETSC_MAX_INT;
1211:   max    = PETSC_MIN_INT;
1212:   if (n) {
1213:     min = keys[0];
1214:     max = keys[0];
1215:   }
1216:   for (i = 1; i < n; i++) {
1217:     if (keys[i] < keys[i - 1]) break;
1218:     min = PetscMin(min, keys[i]);
1219:     max = PetscMax(max, keys[i]);
1220:   }
1221:   if (i < n) sorted = PETSC_FALSE;
1222:   prevmax = PETSC_MIN_INT;
1223:   PetscCallMPI(MPI_Exscan(&max, &prevmax, 1, MPIU_INT, MPI_MAX, comm));
1224:   PetscCallMPI(MPI_Comm_rank(comm, &rank));
1225:   if (rank == 0) prevmax = PETSC_MIN_INT;
1226:   if (prevmax > min) sorted = PETSC_FALSE;
1227:   PetscCall(MPIU_Allreduce(&sorted, is_sorted, 1, MPIU_BOOL, MPI_LAND, comm));
1228:   PetscFunctionReturn(PETSC_SUCCESS);
1229: }