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: }