Actual source code: sorti.c
petsc-3.7.5 2017-01-01
2: /*
3: This file contains routines for sorting integers. Values are sorted in place.
4: */
5: #include <petsc/private/petscimpl.h> /*I "petscsys.h" I*/
7: #define SWAP(a,b,t) {t=a;a=b;b=t;}
9: #define MEDIAN3(v,a,b,c) \
10: (v[a]<v[b] \
11: ? (v[b]<v[c] \
12: ? b \
13: : (v[a]<v[c] ? c : a)) \
14: : (v[c]<v[b] \
15: ? b \
16: : (v[a]<v[c] ? a : c)))
18: #define MEDIAN(v,right) MEDIAN3(v,right/4,right/2,right/4*3)
20: /* -----------------------------------------------------------------------*/
24: /*
25: A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
26: Assumes 0 origin for v, number of elements = right+1 (right is index of
27: right-most member).
28: */
29: static void PetscSortInt_Private(PetscInt *v,PetscInt right)
30: {
31: PetscInt i,j,pivot,tmp;
33: if (right <= 1) {
34: if (right == 1) {
35: if (v[0] > v[1]) SWAP(v[0],v[1],tmp);
36: }
37: return;
38: }
39: i = MEDIAN(v,right); /* Choose a pivot */
40: SWAP(v[0],v[i],tmp); /* Move it out of the way */
41: pivot = v[0];
42: for (i=0,j=right+1;; ) {
43: while (++i < j && v[i] <= pivot) ; /* Scan from the left */
44: while (v[--j] > pivot) ; /* Scan from the right */
45: if (i >= j) break;
46: SWAP(v[i],v[j],tmp);
47: }
48: SWAP(v[0],v[j],tmp); /* Put pivot back in place. */
49: PetscSortInt_Private(v,j-1);
50: PetscSortInt_Private(v+j+1,right-(j+1));
51: }
55: /*@
56: PetscSortInt - Sorts an array of integers in place in increasing order.
58: Not Collective
60: Input Parameters:
61: + n - number of values
62: - i - array of integers
64: Level: intermediate
66: Concepts: sorting^ints
68: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
69: @*/
70: PetscErrorCode PetscSortInt(PetscInt n,PetscInt i[])
71: {
72: PetscInt j,k,tmp,ik;
75: if (n<8) {
76: for (k=0; k<n; k++) {
77: ik = i[k];
78: for (j=k+1; j<n; j++) {
79: if (ik > i[j]) {
80: SWAP(i[k],i[j],tmp);
81: ik = i[k];
82: }
83: }
84: }
85: } else PetscSortInt_Private(i,n-1);
86: return(0);
87: }
91: /*@
92: PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries
94: Not Collective
96: Input Parameters:
97: + n - number of values
98: - ii - array of integers
100: Output Parameter:
101: . n - number of non-redundant values
103: Level: intermediate
105: Concepts: sorting^ints
107: .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt()
108: @*/
109: PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n,PetscInt ii[])
110: {
112: PetscInt i,s = 0,N = *n, b = 0;
115: PetscSortInt(N,ii);
116: for (i=0; i<N-1; i++) {
117: if (ii[b+s+1] != ii[b]) {
118: ii[b+1] = ii[b+s+1]; b++;
119: } else s++;
120: }
121: *n = N - s;
122: return(0);
123: }
127: /*@
128: PetscFindInt - Finds integer in a sorted array of integers
130: Not Collective
132: Input Parameters:
133: + key - the integer to locate
134: . n - number of values in the array
135: - ii - array of integers
137: Output Parameter:
138: . loc - the location if found, otherwise -(slot+1) where slot is the place the value would go
140: Level: intermediate
142: Concepts: sorting^ints
144: .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt()
145: @*/
146: PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt ii[], PetscInt *loc)
147: {
148: PetscInt lo = 0,hi = n;
152: if (!n) {*loc = -1; return(0);}
154: while (hi - lo > 1) {
155: PetscInt mid = lo + (hi - lo)/2;
156: if (key < ii[mid]) hi = mid;
157: else lo = mid;
158: }
159: *loc = key == ii[lo] ? lo : -(lo + (key > ii[lo]) + 1);
160: return(0);
161: }
164: /* -----------------------------------------------------------------------*/
165: #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;}
169: /*
170: A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
171: Assumes 0 origin for v, number of elements = right+1 (right is index of
172: right-most member).
173: */
174: static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right)
175: {
177: PetscInt i,vl,last,tmp;
180: if (right <= 1) {
181: if (right == 1) {
182: if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp);
183: }
184: return(0);
185: }
186: SWAP2(v[0],v[right/2],V[0],V[right/2],tmp);
187: vl = v[0];
188: last = 0;
189: for (i=1; i<=right; i++) {
190: if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);}
191: }
192: SWAP2(v[0],v[last],V[0],V[last],tmp);
193: PetscSortIntWithArray_Private(v,V,last-1);
194: PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));
195: return(0);
196: }
200: /*@
201: PetscSortIntWithArray - Sorts an array of integers in place in increasing order;
202: changes a second array to match the sorted first array.
204: Not Collective
206: Input Parameters:
207: + n - number of values
208: . i - array of integers
209: - I - second array of integers
211: Level: intermediate
213: Concepts: sorting^ints with array
215: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
216: @*/
217: PetscErrorCode PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[])
218: {
220: PetscInt j,k,tmp,ik;
223: if (n<8) {
224: for (k=0; k<n; k++) {
225: ik = i[k];
226: for (j=k+1; j<n; j++) {
227: if (ik > i[j]) {
228: SWAP2(i[k],i[j],Ii[k],Ii[j],tmp);
229: ik = i[k];
230: }
231: }
232: }
233: } else {
234: PetscSortIntWithArray_Private(i,Ii,n-1);
235: }
236: return(0);
237: }
240: #define SWAP3(a,b,c,d,e,f,t) {t=a;a=b;b=t;t=c;c=d;d=t;t=e;e=f;f=t;}
244: /*
245: A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
246: Assumes 0 origin for v, number of elements = right+1 (right is index of
247: right-most member).
248: */
249: static PetscErrorCode PetscSortIntWithArrayPair_Private(PetscInt *L,PetscInt *J, PetscInt *K, PetscInt right)
250: {
252: PetscInt i,vl,last,tmp;
255: if (right <= 1) {
256: if (right == 1) {
257: if (L[0] > L[1]) SWAP3(L[0],L[1],J[0],J[1],K[0],K[1],tmp);
258: }
259: return(0);
260: }
261: SWAP3(L[0],L[right/2],J[0],J[right/2],K[0],K[right/2],tmp);
262: vl = L[0];
263: last = 0;
264: for (i=1; i<=right; i++) {
265: if (L[i] < vl) {last++; SWAP3(L[last],L[i],J[last],J[i],K[last],K[i],tmp);}
266: }
267: SWAP3(L[0],L[last],J[0],J[last],K[0],K[last],tmp);
268: PetscSortIntWithArrayPair_Private(L,J,K,last-1);
269: PetscSortIntWithArrayPair_Private(L+last+1,J+last+1,K+last+1,right-(last+1));
270: return(0);
271: }
275: /*@
276: PetscSortIntWithArrayPair - Sorts an array of integers in place in increasing order;
277: changes a pair of integer arrays to match the sorted first array.
279: Not Collective
281: Input Parameters:
282: + n - number of values
283: . I - array of integers
284: . J - second array of integers (first array of the pair)
285: - K - third array of integers (second array of the pair)
287: Level: intermediate
289: Concepts: sorting^ints with array pair
291: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortIntWithArray()
292: @*/
293: PetscErrorCode PetscSortIntWithArrayPair(PetscInt n,PetscInt *L,PetscInt *J, PetscInt *K)
294: {
296: PetscInt j,k,tmp,ik;
299: if (n<8) {
300: for (k=0; k<n; k++) {
301: ik = L[k];
302: for (j=k+1; j<n; j++) {
303: if (ik > L[j]) {
304: SWAP3(L[k],L[j],J[k],J[j],K[k],K[j],tmp);
305: ik = L[k];
306: }
307: }
308: }
309: } else {
310: PetscSortIntWithArrayPair_Private(L,J,K,n-1);
311: }
312: return(0);
313: }
317: /*
318: A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
319: Assumes 0 origin for v, number of elements = right+1 (right is index of
320: right-most member).
321: */
322: static void PetscSortMPIInt_Private(PetscMPIInt *v,PetscInt right)
323: {
324: PetscInt i,j;
325: PetscMPIInt pivot,tmp;
327: if (right <= 1) {
328: if (right == 1) {
329: if (v[0] > v[1]) SWAP(v[0],v[1],tmp);
330: }
331: return;
332: }
333: i = MEDIAN(v,right); /* Choose a pivot */
334: SWAP(v[0],v[i],tmp); /* Move it out of the way */
335: pivot = v[0];
336: for (i=0,j=right+1;; ) {
337: while (++i < j && v[i] <= pivot) ; /* Scan from the left */
338: while (v[--j] > pivot) ; /* Scan from the right */
339: if (i >= j) break;
340: SWAP(v[i],v[j],tmp);
341: }
342: SWAP(v[0],v[j],tmp); /* Put pivot back in place. */
343: PetscSortMPIInt_Private(v,j-1);
344: PetscSortMPIInt_Private(v+j+1,right-(j+1));
345: }
349: /*@
350: PetscSortMPIInt - Sorts an array of MPI integers in place in increasing order.
352: Not Collective
354: Input Parameters:
355: + n - number of values
356: - i - array of integers
358: Level: intermediate
360: Concepts: sorting^ints
362: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
363: @*/
364: PetscErrorCode PetscSortMPIInt(PetscInt n,PetscMPIInt i[])
365: {
366: PetscInt j,k;
367: PetscMPIInt tmp,ik;
370: if (n<8) {
371: for (k=0; k<n; k++) {
372: ik = i[k];
373: for (j=k+1; j<n; j++) {
374: if (ik > i[j]) {
375: SWAP(i[k],i[j],tmp);
376: ik = i[k];
377: }
378: }
379: }
380: } else PetscSortMPIInt_Private(i,n-1);
381: return(0);
382: }
386: /*@
387: PetscSortRemoveDupsMPIInt - Sorts an array of MPI integers in place in increasing order removes all duplicate entries
389: Not Collective
391: Input Parameters:
392: + n - number of values
393: - ii - array of integers
395: Output Parameter:
396: . n - number of non-redundant values
398: Level: intermediate
400: Concepts: sorting^ints
402: .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt()
403: @*/
404: PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n,PetscMPIInt ii[])
405: {
407: PetscInt i,s = 0,N = *n, b = 0;
410: PetscSortMPIInt(N,ii);
411: for (i=0; i<N-1; i++) {
412: if (ii[b+s+1] != ii[b]) {
413: ii[b+1] = ii[b+s+1]; b++;
414: } else s++;
415: }
416: *n = N - s;
417: return(0);
418: }
422: /*
423: A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
424: Assumes 0 origin for v, number of elements = right+1 (right is index of
425: right-most member).
426: */
427: static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right)
428: {
430: PetscMPIInt i,vl,last,tmp;
433: if (right <= 1) {
434: if (right == 1) {
435: if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp);
436: }
437: return(0);
438: }
439: SWAP2(v[0],v[right/2],V[0],V[right/2],tmp);
440: vl = v[0];
441: last = 0;
442: for (i=1; i<=right; i++) {
443: if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);}
444: }
445: SWAP2(v[0],v[last],V[0],V[last],tmp);
446: PetscSortMPIIntWithArray_Private(v,V,last-1);
447: PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));
448: return(0);
449: }
453: /*@
454: PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order;
455: changes a second array to match the sorted first array.
457: Not Collective
459: Input Parameters:
460: + n - number of values
461: . i - array of integers
462: - I - second array of integers
464: Level: intermediate
466: Concepts: sorting^ints with array
468: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
469: @*/
470: PetscErrorCode PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[])
471: {
473: PetscMPIInt j,k,tmp,ik;
476: if (n<8) {
477: for (k=0; k<n; k++) {
478: ik = i[k];
479: for (j=k+1; j<n; j++) {
480: if (ik > i[j]) {
481: SWAP2(i[k],i[j],Ii[k],Ii[j],tmp);
482: ik = i[k];
483: }
484: }
485: }
486: } else {
487: PetscSortMPIIntWithArray_Private(i,Ii,n-1);
488: }
489: return(0);
490: }
492: /* -----------------------------------------------------------------------*/
493: #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;}
497: /*
498: Modified from PetscSortIntWithArray_Private().
499: */
500: static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right)
501: {
503: PetscInt i,vl,last,tmp;
504: PetscScalar stmp;
507: if (right <= 1) {
508: if (right == 1) {
509: if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp);
510: }
511: return(0);
512: }
513: SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp);
514: vl = v[0];
515: last = 0;
516: for (i=1; i<=right; i++) {
517: if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);}
518: }
519: SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp);
520: PetscSortIntWithScalarArray_Private(v,V,last-1);
521: PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));
522: return(0);
523: }
527: /*@
528: PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order;
529: changes a second SCALAR array to match the sorted first INTEGER array.
531: Not Collective
533: Input Parameters:
534: + n - number of values
535: . i - array of integers
536: - I - second array of scalars
538: Level: intermediate
540: Concepts: sorting^ints with array
542: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
543: @*/
544: PetscErrorCode PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[])
545: {
547: PetscInt j,k,tmp,ik;
548: PetscScalar stmp;
551: if (n<8) {
552: for (k=0; k<n; k++) {
553: ik = i[k];
554: for (j=k+1; j<n; j++) {
555: if (ik > i[j]) {
556: SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp);
557: ik = i[k];
558: }
559: }
560: }
561: } else {
562: PetscSortIntWithScalarArray_Private(i,Ii,n-1);
563: }
564: return(0);
565: }
567: #define SWAP2IntData(a,b,c,d,t,td,siz) \
568: do { \
569: PetscErrorCode _ierr; \
570: t=a;a=b;b=t; \
571: _PetscMemcpy(td,c,siz);CHKERRQ(_ierr); \
572: _PetscMemcpy(c,d,siz);CHKERRQ(_ierr); \
573: _PetscMemcpy(d,td,siz);CHKERRQ(_ierr); \
574: } while(0)
578: /*
579: Modified from PetscSortIntWithArray_Private().
580: */
581: static PetscErrorCode PetscSortIntWithDataArray_Private(PetscInt *v,char *V,PetscInt right,size_t size,void *work)
582: {
584: PetscInt i,vl,last,tmp;
587: if (right <= 1) {
588: if (right == 1) {
589: if (v[0] > v[1]) SWAP2IntData(v[0],v[1],V,V+size,tmp,work,size);
590: }
591: return(0);
592: }
593: SWAP2IntData(v[0],v[right/2],V,V+size*(right/2),tmp,work,size);
594: vl = v[0];
595: last = 0;
596: for (i=1; i<=right; i++) {
597: if (v[i] < vl) {last++; SWAP2IntData(v[last],v[i],V+size*last,V+size*i,tmp,work,size);}
598: }
599: SWAP2IntData(v[0],v[last],V,V + size*last,tmp,work,size);
600: PetscSortIntWithDataArray_Private(v,V,last-1,size,work);
601: PetscSortIntWithDataArray_Private(v+last+1,V+size*(last+1),right-(last+1),size,work);
602: return(0);
603: }
607: /*@
608: PetscSortIntWithDataArray - Sorts an array of integers in place in increasing order;
609: changes a second array to match the sorted first INTEGER array. Unlike other sort routines, the user must
610: provide workspace (the size of an element in the data array) to use when sorting.
612: Not Collective
614: Input Parameters:
615: + n - number of values
616: . i - array of integers
617: . Ii - second array of data
618: . size - sizeof elements in the data array in bytes
619: - work - workspace of "size" bytes used when sorting
621: Level: intermediate
623: Concepts: sorting^ints with array
625: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
626: @*/
627: PetscErrorCode PetscSortIntWithDataArray(PetscInt n,PetscInt i[],void *Ii,size_t size,void *work)
628: {
629: char *V = (char *) Ii;
631: PetscInt j,k,tmp,ik;
634: if (n<8) {
635: for (k=0; k<n; k++) {
636: ik = i[k];
637: for (j=k+1; j<n; j++) {
638: if (ik > i[j]) {
639: SWAP2IntData(i[k],i[j],V+size*k,V+size*j,tmp,work,size);
640: ik = i[k];
641: }
642: }
643: }
644: } else {
645: PetscSortIntWithDataArray_Private(i,V,n-1,size,work);
646: }
647: return(0);
648: }
653: /*@
654: PetscMergeIntArray - Merges two SORTED integer arrays, removes duplicate elements.
656: Not Collective
658: Input Parameters:
659: + an - number of values in the first array
660: . aI - first sorted array of integers
661: . bn - number of values in the second array
662: - bI - second array of integers
664: Output Parameters:
665: + n - number of values in the merged array
666: - I - merged sorted array, this is allocated if an array is not provided
668: Level: intermediate
670: Concepts: merging^arrays
672: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
673: @*/
674: PetscErrorCode PetscMergeIntArray(PetscInt an,const PetscInt *aI, PetscInt bn, const PetscInt *bI, PetscInt *n, PetscInt **L)
675: {
677: PetscInt *L_ = *L, ak, bk, k;
679: if (!L_) {
680: PetscMalloc1(an+bn, L);
681: L_ = *L;
682: }
683: k = ak = bk = 0;
684: while (ak < an && bk < bn) {
685: if (aI[ak] == bI[bk]) {
686: L_[k] = aI[ak];
687: ++ak;
688: ++bk;
689: ++k;
690: } else if (aI[ak] < bI[bk]) {
691: L_[k] = aI[ak];
692: ++ak;
693: ++k;
694: } else {
695: L_[k] = bI[bk];
696: ++bk;
697: ++k;
698: }
699: }
700: if (ak < an) {
701: PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));
702: k += (an-ak);
703: }
704: if (bk < bn) {
705: PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));
706: k += (bn-bk);
707: }
708: *n = k;
709: return(0);
710: }
714: /*@
715: PetscMergeIntArrayPair - Merges two SORTED integer arrays that share NO common values along with an additional array of integers.
716: The additional arrays are the same length as sorted arrays and are merged
717: in the order determined by the merging of the sorted pair.
719: Not Collective
721: Input Parameters:
722: + an - number of values in the first array
723: . aI - first sorted array of integers
724: . aJ - first additional array of integers
725: . bn - number of values in the second array
726: . bI - second array of integers
727: - bJ - second additional of integers
729: Output Parameters:
730: + n - number of values in the merged array (== an + bn)
731: . L - merged sorted array
732: - J - merged additional array
734: Notes: if L or J point to non-null arrays then this routine will assume they are of the approproate size and use them, otherwise this routine will allocate space for them
735: Level: intermediate
737: Concepts: merging^arrays
739: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
740: @*/
741: PetscErrorCode PetscMergeIntArrayPair(PetscInt an,const PetscInt *aI, const PetscInt *aJ, PetscInt bn, const PetscInt *bI, const PetscInt *bJ, PetscInt *n, PetscInt **L, PetscInt **J)
742: {
744: PetscInt n_, *L_, *J_, ak, bk, k;
749: n_ = an + bn;
750: *n = n_;
751: if (!*L) {
752: PetscMalloc1(n_, L);
753: }
754: L_ = *L;
755: if (!*J) {
756: PetscMalloc1(n_, J);
757: }
758: J_ = *J;
759: k = ak = bk = 0;
760: while (ak < an && bk < bn) {
761: if (aI[ak] <= bI[bk]) {
762: L_[k] = aI[ak];
763: J_[k] = aJ[ak];
764: ++ak;
765: ++k;
766: } else {
767: L_[k] = bI[bk];
768: J_[k] = bJ[bk];
769: ++bk;
770: ++k;
771: }
772: }
773: if (ak < an) {
774: PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));
775: PetscMemcpy(J_+k,aJ+ak,(an-ak)*sizeof(PetscInt));
776: k += (an-ak);
777: }
778: if (bk < bn) {
779: PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));
780: PetscMemcpy(J_+k,bJ+bk,(bn-bk)*sizeof(PetscInt));
781: }
782: return(0);
783: }
787: /*@
788: PetscMergeMPIIntArray - Merges two SORTED integer arrays.
790: Not Collective
792: Input Parameters:
793: + an - number of values in the first array
794: . aI - first sorted array of integers
795: . bn - number of values in the second array
796: - bI - second array of integers
798: Output Parameters:
799: + n - number of values in the merged array (<= an + bn)
800: - L - merged sorted array, allocated if address of NULL pointer is passed
802: Level: intermediate
804: Concepts: merging^arrays
806: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
807: @*/
808: PetscErrorCode PetscMergeMPIIntArray(PetscInt an,const PetscMPIInt aI[],PetscInt bn,const PetscMPIInt bI[],PetscInt *n,PetscMPIInt **L)
809: {
811: PetscInt ai,bi,k;
814: if (!*L) {PetscMalloc1((an+bn),L);}
815: for (ai=0,bi=0,k=0; ai<an || bi<bn; ) {
816: PetscInt t = -1;
817: for ( ; ai<an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai];
818: for ( ; bi<bn && bI[bi] == t; bi++);
819: for ( ; bi<bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi];
820: for ( ; ai<an && aI[ai] == t; ai++);
821: }
822: *n = k;
823: return(0);
824: }
828: /*@
829: PetscProcessTree - Prepares tree data to be displayed graphically
831: Not Collective
833: Input Parameters:
834: + n - number of values
835: . mask - indicates those entries in the tree, location 0 is always masked
836: - parentid - indicates the parent of each entry
838: Output Parameters:
839: + Nlevels - the number of levels
840: . Level - for each node tells its level
841: . Levelcnts - the number of nodes on each level
842: . Idbylevel - a list of ids on each of the levels, first level followed by second etc
843: - Column - for each id tells its column index
845: Level: intermediate
848: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
849: @*/
850: PetscErrorCode PetscProcessTree(PetscInt n,const PetscBool mask[],const PetscInt parentid[],PetscInt *Nlevels,PetscInt **Level,PetscInt **Levelcnt,PetscInt **Idbylevel,PetscInt **Column)
851: {
852: PetscInt i,j,cnt,nmask = 0,nlevels = 0,*level,*levelcnt,levelmax = 0,*workid,*workparentid,tcnt = 0,*idbylevel,*column;
854: PetscBool done = PETSC_FALSE;
857: if (!mask[0]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Mask of 0th location must be set");
858: for (i=0; i<n; i++) {
859: if (mask[i]) continue;
860: if (parentid[i] == i) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Node labeled as own parent");
861: if (parentid[i] && mask[parentid[i]]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Parent is masked");
862: }
864: for (i=0; i<n; i++) {
865: if (!mask[i]) nmask++;
866: }
868: /* determine the level in the tree of each node */
869: PetscCalloc1(n,&level);
871: level[0] = 1;
872: while (!done) {
873: done = PETSC_TRUE;
874: for (i=0; i<n; i++) {
875: if (mask[i]) continue;
876: if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1;
877: else if (!level[i]) done = PETSC_FALSE;
878: }
879: }
880: for (i=0; i<n; i++) {
881: level[i]--;
882: nlevels = PetscMax(nlevels,level[i]);
883: }
885: /* count the number of nodes on each level and its max */
886: PetscCalloc1(nlevels,&levelcnt);
887: for (i=0; i<n; i++) {
888: if (mask[i]) continue;
889: levelcnt[level[i]-1]++;
890: }
891: for (i=0; i<nlevels;i++) levelmax = PetscMax(levelmax,levelcnt[i]);
893: /* for each level sort the ids by the parent id */
894: PetscMalloc2(levelmax,&workid,levelmax,&workparentid);
895: PetscMalloc1(nmask,&idbylevel);
896: for (j=1; j<=nlevels;j++) {
897: cnt = 0;
898: for (i=0; i<n; i++) {
899: if (mask[i]) continue;
900: if (level[i] != j) continue;
901: workid[cnt] = i;
902: workparentid[cnt++] = parentid[i];
903: }
904: /* PetscIntView(cnt,workparentid,0);
905: PetscIntView(cnt,workid,0);
906: PetscSortIntWithArray(cnt,workparentid,workid);
907: PetscIntView(cnt,workparentid,0);
908: PetscIntView(cnt,workid,0);*/
909: PetscMemcpy(idbylevel+tcnt,workid,cnt*sizeof(PetscInt));
910: tcnt += cnt;
911: }
912: if (tcnt != nmask) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Inconsistent count of unmasked nodes");
913: PetscFree2(workid,workparentid);
915: /* for each node list its column */
916: PetscMalloc1(n,&column);
917: cnt = 0;
918: for (j=0; j<nlevels; j++) {
919: for (i=0; i<levelcnt[j]; i++) {
920: column[idbylevel[cnt++]] = i;
921: }
922: }
924: *Nlevels = nlevels;
925: *Level = level;
926: *Levelcnt = levelcnt;
927: *Idbylevel = idbylevel;
928: *Column = column;
929: return(0);
930: }