Actual source code: sorti.c

petsc-master 2019-06-15
Report Typos and Errors

  2: /*
  3:    This file contains routines for sorting integers. Values are sorted in place.
  4:  */
  5:  #include <petsc/private/petscimpl.h>

  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: /* -----------------------------------------------------------------------*/

 22: /*
 23:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
 24:    Assumes 0 origin for v, number of elements = right+1 (right is index of
 25:    right-most member).
 26: */
 27: static void PetscSortInt_Private(PetscInt *v,PetscInt right)
 28: {
 29:   PetscInt i,j,pivot,tmp;

 31:   if (right <= 1) {
 32:     if (right == 1) {
 33:       if (v[0] > v[1]) SWAP(v[0],v[1],tmp);
 34:     }
 35:     return;
 36:   }
 37:   i = MEDIAN(v,right);          /* Choose a pivot */
 38:   SWAP(v[0],v[i],tmp);          /* Move it out of the way */
 39:   pivot = v[0];
 40:   for (i=0,j=right+1;; ) {
 41:     while (++i < j && v[i] <= pivot) ; /* Scan from the left */
 42:     while (v[--j] > pivot) ;           /* Scan from the right */
 43:     if (i >= j) break;
 44:     SWAP(v[i],v[j],tmp);
 45:   }
 46:   SWAP(v[0],v[j],tmp);          /* Put pivot back in place. */
 47:   PetscSortInt_Private(v,j-1);
 48:   PetscSortInt_Private(v+j+1,right-(j+1));
 49: }

 51: /*@
 52:    PetscSortInt - Sorts an array of integers in place in increasing order.

 54:    Not Collective

 56:    Input Parameters:
 57: +  n  - number of values
 58: -  i  - array of integers

 60:    Level: intermediate

 62: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
 63: @*/
 64: PetscErrorCode  PetscSortInt(PetscInt n,PetscInt i[])
 65: {
 66:   PetscInt j,k,tmp,ik;

 69:   if (n<8) {
 70:     for (k=0; k<n; k++) {
 71:       ik = i[k];
 72:       for (j=k+1; j<n; j++) {
 73:         if (ik > i[j]) {
 74:           SWAP(i[k],i[j],tmp);
 75:           ik = i[k];
 76:         }
 77:       }
 78:     }
 79:   } else PetscSortInt_Private(i,n-1);
 80:   return(0);
 81: }

 83: /*@
 84:    PetscSortedRemoveDupsInt - Removes all duplicate entries of a sorted input array

 86:    Not Collective

 88:    Input Parameters:
 89: +  n  - number of values
 90: -  ii  - sorted array of integers

 92:    Output Parameter:
 93: .  n - number of non-redundant values

 95:    Level: intermediate

 97: .seealso: PetscSortInt()
 98: @*/
 99: PetscErrorCode  PetscSortedRemoveDupsInt(PetscInt *n,PetscInt ii[])
100: {
101:   PetscInt i,s = 0,N = *n, b = 0;

104:   for (i=0; i<N-1; i++) {
105:     if (PetscUnlikely(ii[b+s+1] < ii[b])) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_WRONG,"Input array is not sorted");
106:     if (ii[b+s+1] != ii[b]) {
107:       ii[b+1] = ii[b+s+1]; b++;
108:     } else s++;
109:   }
110:   *n = N - s;
111:   return(0);
112: }

114: /*@
115:    PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries

117:    Not Collective

119:    Input Parameters:
120: +  n  - number of values
121: -  ii  - array of integers

123:    Output Parameter:
124: .  n - number of non-redundant values

126:    Level: intermediate

128: .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt(), PetscSortedRemoveDupsInt()
129: @*/
130: PetscErrorCode  PetscSortRemoveDupsInt(PetscInt *n,PetscInt ii[])
131: {

135:   PetscSortInt(*n,ii);
136:   PetscSortedRemoveDupsInt(n,ii);
137:   return(0);
138: }

140: /*@
141:   PetscFindInt - Finds integer in a sorted array of integers

143:    Not Collective

145:    Input Parameters:
146: +  key - the integer to locate
147: .  n   - number of values in the array
148: -  ii  - array of integers

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

153:    Level: intermediate

155: .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt()
156: @*/
157: PetscErrorCode PetscFindInt(PetscInt key, PetscInt n, const PetscInt ii[], PetscInt *loc)
158: {
159:   PetscInt lo = 0,hi = n;

163:   if (!n) {*loc = -1; return(0);}
165:   while (hi - lo > 1) {
166:     PetscInt mid = lo + (hi - lo)/2;
167:     if (key < ii[mid]) hi = mid;
168:     else               lo = mid;
169:   }
170:   *loc = key == ii[lo] ? lo : -(lo + (key > ii[lo]) + 1);
171:   return(0);
172: }

174: /*@
175:   PetscFindMPIInt - Finds MPI integer in a sorted array of integers

177:    Not Collective

179:    Input Parameters:
180: +  key - the integer to locate
181: .  n   - number of values in the array
182: -  ii  - array of integers

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

187:    Level: intermediate

189: .seealso: PetscSortInt(), PetscSortIntWithArray(), PetscSortRemoveDupsInt()
190: @*/
191: PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscInt n, const PetscMPIInt ii[], PetscInt *loc)
192: {
193:   PetscInt lo = 0,hi = n;

197:   if (!n) {*loc = -1; return(0);}
199:   while (hi - lo > 1) {
200:     PetscInt mid = lo + (hi - lo)/2;
201:     if (key < ii[mid]) hi = mid;
202:     else               lo = mid;
203:   }
204:   *loc = key == ii[lo] ? lo : -(lo + (key > ii[lo]) + 1);
205:   return(0);
206: }

208: /* -----------------------------------------------------------------------*/
209: #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;}

211: /*
212:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
213:    Assumes 0 origin for v, number of elements = right+1 (right is index of
214:    right-most member).
215: */
216: static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right)
217: {
219:   PetscInt       i,vl,last,tmp;

222:   if (right <= 1) {
223:     if (right == 1) {
224:       if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp);
225:     }
226:     return(0);
227:   }
228:   SWAP2(v[0],v[right/2],V[0],V[right/2],tmp);
229:   vl   = v[0];
230:   last = 0;
231:   for (i=1; i<=right; i++) {
232:     if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);}
233:   }
234:   SWAP2(v[0],v[last],V[0],V[last],tmp);
235:   PetscSortIntWithArray_Private(v,V,last-1);
236:   PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));
237:   return(0);
238: }

240: /*@
241:    PetscSortIntWithArray - Sorts an array of integers in place in increasing order;
242:        changes a second array to match the sorted first array.

244:    Not Collective

246:    Input Parameters:
247: +  n  - number of values
248: .  i  - array of integers
249: -  I - second array of integers

251:    Level: intermediate

253: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
254: @*/
255: PetscErrorCode  PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[])
256: {
258:   PetscInt       j,k,tmp,ik;

261:   if (n<8) {
262:     for (k=0; k<n; k++) {
263:       ik = i[k];
264:       for (j=k+1; j<n; j++) {
265:         if (ik > i[j]) {
266:           SWAP2(i[k],i[j],Ii[k],Ii[j],tmp);
267:           ik = i[k];
268:         }
269:       }
270:     }
271:   } else {
272:     PetscSortIntWithArray_Private(i,Ii,n-1);
273:   }
274:   return(0);
275: }


278: #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;}

280: /*
281:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
282:    Assumes 0 origin for v, number of elements = right+1 (right is index of
283:    right-most member).
284: */
285: static PetscErrorCode PetscSortIntWithArrayPair_Private(PetscInt *L,PetscInt *J, PetscInt *K, PetscInt right)
286: {
288:   PetscInt       i,vl,last,tmp;

291:   if (right <= 1) {
292:     if (right == 1) {
293:       if (L[0] > L[1]) SWAP3(L[0],L[1],J[0],J[1],K[0],K[1],tmp);
294:     }
295:     return(0);
296:   }
297:   SWAP3(L[0],L[right/2],J[0],J[right/2],K[0],K[right/2],tmp);
298:   vl   = L[0];
299:   last = 0;
300:   for (i=1; i<=right; i++) {
301:     if (L[i] < vl) {last++; SWAP3(L[last],L[i],J[last],J[i],K[last],K[i],tmp);}
302:   }
303:   SWAP3(L[0],L[last],J[0],J[last],K[0],K[last],tmp);
304:   PetscSortIntWithArrayPair_Private(L,J,K,last-1);
305:   PetscSortIntWithArrayPair_Private(L+last+1,J+last+1,K+last+1,right-(last+1));
306:   return(0);
307: }

309: /*@
310:    PetscSortIntWithArrayPair - Sorts an array of integers in place in increasing order;
311:        changes a pair of integer arrays to match the sorted first array.

313:    Not Collective

315:    Input Parameters:
316: +  n  - number of values
317: .  I  - array of integers
318: .  J  - second array of integers (first array of the pair)
319: -  K  - third array of integers  (second array of the pair)

321:    Level: intermediate

323: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortIntWithArray()
324: @*/
325: PetscErrorCode  PetscSortIntWithArrayPair(PetscInt n,PetscInt L[],PetscInt J[], PetscInt K[])
326: {
328:   PetscInt       j,k,tmp,ik;

331:   if (n<8) {
332:     for (k=0; k<n; k++) {
333:       ik = L[k];
334:       for (j=k+1; j<n; j++) {
335:         if (ik > L[j]) {
336:           SWAP3(L[k],L[j],J[k],J[j],K[k],K[j],tmp);
337:           ik = L[k];
338:         }
339:       }
340:     }
341:   } else {
342:     PetscSortIntWithArrayPair_Private(L,J,K,n-1);
343:   }
344:   return(0);
345: }

347: /*
348:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
349:    Assumes 0 origin for v, number of elements = right+1 (right is index of
350:    right-most member).
351: */
352: static void PetscSortMPIInt_Private(PetscMPIInt *v,PetscInt right)
353: {
354:   PetscInt          i,j;
355:   PetscMPIInt       pivot,tmp;

357:   if (right <= 1) {
358:     if (right == 1) {
359:       if (v[0] > v[1]) SWAP(v[0],v[1],tmp);
360:     }
361:     return;
362:   }
363:   i = MEDIAN(v,right);          /* Choose a pivot */
364:   SWAP(v[0],v[i],tmp);          /* Move it out of the way */
365:   pivot = v[0];
366:   for (i=0,j=right+1;; ) {
367:     while (++i < j && v[i] <= pivot) ; /* Scan from the left */
368:     while (v[--j] > pivot) ;           /* Scan from the right */
369:     if (i >= j) break;
370:     SWAP(v[i],v[j],tmp);
371:   }
372:   SWAP(v[0],v[j],tmp);          /* Put pivot back in place. */
373:   PetscSortMPIInt_Private(v,j-1);
374:   PetscSortMPIInt_Private(v+j+1,right-(j+1));
375: }

377: /*@
378:    PetscSortMPIInt - Sorts an array of MPI integers in place in increasing order.

380:    Not Collective

382:    Input Parameters:
383: +  n  - number of values
384: -  i  - array of integers

386:    Level: intermediate

388: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
389: @*/
390: PetscErrorCode  PetscSortMPIInt(PetscInt n,PetscMPIInt i[])
391: {
392:   PetscInt    j,k;
393:   PetscMPIInt tmp,ik;

396:   if (n<8) {
397:     for (k=0; k<n; k++) {
398:       ik = i[k];
399:       for (j=k+1; j<n; j++) {
400:         if (ik > i[j]) {
401:           SWAP(i[k],i[j],tmp);
402:           ik = i[k];
403:         }
404:       }
405:     }
406:   } else PetscSortMPIInt_Private(i,n-1);
407:   return(0);
408: }

410: /*@
411:    PetscSortRemoveDupsMPIInt - Sorts an array of MPI integers in place in increasing order removes all duplicate entries

413:    Not Collective

415:    Input Parameters:
416: +  n  - number of values
417: -  ii  - array of integers

419:    Output Parameter:
420: .  n - number of non-redundant values

422:    Level: intermediate

424: .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt()
425: @*/
426: PetscErrorCode  PetscSortRemoveDupsMPIInt(PetscInt *n,PetscMPIInt ii[])
427: {
429:   PetscInt       i,s = 0,N = *n, b = 0;

432:   PetscSortMPIInt(N,ii);
433:   for (i=0; i<N-1; i++) {
434:     if (ii[b+s+1] != ii[b]) {
435:       ii[b+1] = ii[b+s+1]; b++;
436:     } else s++;
437:   }
438:   *n = N - s;
439:   return(0);
440: }

442: /*
443:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
444:    Assumes 0 origin for v, number of elements = right+1 (right is index of
445:    right-most member).
446: */
447: static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right)
448: {
450:   PetscMPIInt    i,vl,last,tmp;

453:   if (right <= 1) {
454:     if (right == 1) {
455:       if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp);
456:     }
457:     return(0);
458:   }
459:   SWAP2(v[0],v[right/2],V[0],V[right/2],tmp);
460:   vl   = v[0];
461:   last = 0;
462:   for (i=1; i<=right; i++) {
463:     if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);}
464:   }
465:   SWAP2(v[0],v[last],V[0],V[last],tmp);
466:   PetscSortMPIIntWithArray_Private(v,V,last-1);
467:   PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));
468:   return(0);
469: }

471: /*@
472:    PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order;
473:        changes a second array to match the sorted first array.

475:    Not Collective

477:    Input Parameters:
478: +  n  - number of values
479: .  i  - array of integers
480: -  I - second array of integers

482:    Level: intermediate

484: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
485: @*/
486: PetscErrorCode  PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[])
487: {
489:   PetscMPIInt    j,k,tmp,ik;

492:   if (n<8) {
493:     for (k=0; k<n; k++) {
494:       ik = i[k];
495:       for (j=k+1; j<n; j++) {
496:         if (ik > i[j]) {
497:           SWAP2(i[k],i[j],Ii[k],Ii[j],tmp);
498:           ik = i[k];
499:         }
500:       }
501:     }
502:   } else {
503:     PetscSortMPIIntWithArray_Private(i,Ii,n-1);
504:   }
505:   return(0);
506: }

508: /* -----------------------------------------------------------------------*/
509: #define SWAP2MPIIntInt(a,b,c,d,t1,t2) {t1=a;a=b;b=t1;t2=c;c=d;d=t2;}

511: /*
512:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
513:    Assumes 0 origin for v, number of elements = right+1 (right is index of
514:    right-most member).
515: */
516: static PetscErrorCode PetscSortMPIIntWithIntArray_Private(PetscMPIInt *v,PetscInt *V,PetscMPIInt right)
517: {
519:   PetscMPIInt    i,vl,last,t1;
520:   PetscInt       t2;

523:   if (right <= 1) {
524:     if (right == 1) {
525:       if (v[0] > v[1]) SWAP2MPIIntInt(v[0],v[1],V[0],V[1],t1,t2);
526:     }
527:     return(0);
528:   }
529:   SWAP2MPIIntInt(v[0],v[right/2],V[0],V[right/2],t1,t2);
530:   vl   = v[0];
531:   last = 0;
532:   for (i=1; i<=right; i++) {
533:     if (v[i] < vl) {last++; SWAP2MPIIntInt(v[last],v[i],V[last],V[i],t1,t2);}
534:   }
535:   SWAP2MPIIntInt(v[0],v[last],V[0],V[last],t1,t2);
536:   PetscSortMPIIntWithIntArray_Private(v,V,last-1);
537:   PetscSortMPIIntWithIntArray_Private(v+last+1,V+last+1,right-(last+1));
538:   return(0);
539: }

541: /*@
542:    PetscSortMPIIntWithIntArray - Sorts an array of MPI integers in place in increasing order;
543:        changes a second array of Petsc intergers to match the sorted first array.

545:    Not Collective

547:    Input Parameters:
548: +  n  - number of values
549: .  i  - array of MPI integers
550: -  I - second array of Petsc integers

552:    Level: intermediate

554:    Notes: this routine is useful when one needs to sort MPI ranks with other integer arrays.

556: .seealso: PetscSortMPIIntWithArray()
557: @*/
558: PetscErrorCode PetscSortMPIIntWithIntArray(PetscMPIInt n,PetscMPIInt i[],PetscInt Ii[])
559: {
561:   PetscMPIInt    j,k,t1,ik;
562:   PetscInt       t2;

565:   if (n<8) {
566:     for (k=0; k<n; k++) {
567:       ik = i[k];
568:       for (j=k+1; j<n; j++) {
569:         if (ik > i[j]) {
570:           SWAP2MPIIntInt(i[k],i[j],Ii[k],Ii[j],t1,t2);
571:           ik = i[k];
572:         }
573:       }
574:     }
575:   } else {
576:     PetscSortMPIIntWithIntArray_Private(i,Ii,n-1);
577:   }
578:   return(0);
579: }

581: /* -----------------------------------------------------------------------*/
582: #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;}

584: /*
585:    Modified from PetscSortIntWithArray_Private().
586: */
587: static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right)
588: {
590:   PetscInt       i,vl,last,tmp;
591:   PetscScalar    stmp;

594:   if (right <= 1) {
595:     if (right == 1) {
596:       if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp);
597:     }
598:     return(0);
599:   }
600:   SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp);
601:   vl   = v[0];
602:   last = 0;
603:   for (i=1; i<=right; i++) {
604:     if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);}
605:   }
606:   SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp);
607:   PetscSortIntWithScalarArray_Private(v,V,last-1);
608:   PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));
609:   return(0);
610: }

612: /*@
613:    PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order;
614:        changes a second SCALAR array to match the sorted first INTEGER array.

616:    Not Collective

618:    Input Parameters:
619: +  n  - number of values
620: .  i  - array of integers
621: -  I - second array of scalars

623:    Level: intermediate

625: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
626: @*/
627: PetscErrorCode  PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[])
628: {
630:   PetscInt       j,k,tmp,ik;
631:   PetscScalar    stmp;

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:           SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp);
640:           ik = i[k];
641:         }
642:       }
643:     }
644:   } else {
645:     PetscSortIntWithScalarArray_Private(i,Ii,n-1);
646:   }
647:   return(0);
648: }

650: #define SWAP2IntData(a,b,c,d,t,td,siz)          \
651:   do {                                          \
652:   PetscErrorCode _ierr;                         \
653:   t=a;a=b;b=t;                                  \
654:   _PetscMemcpy(td,c,siz);CHKERRQ(_ierr); \
655:   _PetscMemcpy(c,d,siz);CHKERRQ(_ierr);  \
656:   _PetscMemcpy(d,td,siz);CHKERRQ(_ierr); \
657: } while(0)

659: /*
660:    Modified from PetscSortIntWithArray_Private().
661: */
662: static PetscErrorCode PetscSortIntWithDataArray_Private(PetscInt *v,char *V,PetscInt right,size_t size,void *work)
663: {
665:   PetscInt       i,vl,last,tmp;

668:   if (right <= 1) {
669:     if (right == 1) {
670:       if (v[0] > v[1]) SWAP2IntData(v[0],v[1],V,V+size,tmp,work,size);
671:     }
672:     return(0);
673:   }
674:   SWAP2IntData(v[0],v[right/2],V,V+size*(right/2),tmp,work,size);
675:   vl   = v[0];
676:   last = 0;
677:   for (i=1; i<=right; i++) {
678:     if (v[i] < vl) {last++; SWAP2IntData(v[last],v[i],V+size*last,V+size*i,tmp,work,size);}
679:   }
680:   SWAP2IntData(v[0],v[last],V,V + size*last,tmp,work,size);
681:   PetscSortIntWithDataArray_Private(v,V,last-1,size,work);
682:   PetscSortIntWithDataArray_Private(v+last+1,V+size*(last+1),right-(last+1),size,work);
683:   return(0);
684: }

686: /*@C
687:    PetscSortIntWithDataArray - Sorts an array of integers in place in increasing order;
688:        changes a second array to match the sorted first INTEGER array.  Unlike other sort routines, the user must
689:        provide workspace (the size of an element in the data array) to use when sorting.

691:    Not Collective

693:    Input Parameters:
694: +  n  - number of values
695: .  i  - array of integers
696: .  Ii - second array of data
697: .  size - sizeof elements in the data array in bytes
698: -  work - workspace of "size" bytes used when sorting

700:    Level: intermediate

702: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
703: @*/
704: PetscErrorCode  PetscSortIntWithDataArray(PetscInt n,PetscInt i[],void *Ii,size_t size,void *work)
705: {
706:   char           *V = (char *) Ii;
708:   PetscInt       j,k,tmp,ik;

711:   if (n<8) {
712:     for (k=0; k<n; k++) {
713:       ik = i[k];
714:       for (j=k+1; j<n; j++) {
715:         if (ik > i[j]) {
716:           SWAP2IntData(i[k],i[j],V+size*k,V+size*j,tmp,work,size);
717:           ik = i[k];
718:         }
719:       }
720:     }
721:   } else {
722:     PetscSortIntWithDataArray_Private(i,V,n-1,size,work);
723:   }
724:   return(0);
725: }


728: /*@
729:    PetscMergeIntArray -     Merges two SORTED integer arrays, removes duplicate elements.

731:    Not Collective

733:    Input Parameters:
734: +  an  - number of values in the first array
735: .  aI  - first sorted array of integers
736: .  bn  - number of values in the second array
737: -  bI  - second array of integers

739:    Output Parameters:
740: +  n   - number of values in the merged array
741: -  L   - merged sorted array, this is allocated if an array is not provided

743:    Level: intermediate

745: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
746: @*/
747: PetscErrorCode  PetscMergeIntArray(PetscInt an,const PetscInt aI[], PetscInt bn, const PetscInt bI[],  PetscInt *n, PetscInt **L)
748: {
750:   PetscInt       *L_ = *L, ak, bk, k;

752:   if (!L_) {
753:     PetscMalloc1(an+bn, L);
754:     L_   = *L;
755:   }
756:   k = ak = bk = 0;
757:   while (ak < an && bk < bn) {
758:     if (aI[ak] == bI[bk]) {
759:       L_[k] = aI[ak];
760:       ++ak;
761:       ++bk;
762:       ++k;
763:     } else if (aI[ak] < bI[bk]) {
764:       L_[k] = aI[ak];
765:       ++ak;
766:       ++k;
767:     } else {
768:       L_[k] = bI[bk];
769:       ++bk;
770:       ++k;
771:     }
772:   }
773:   if (ak < an) {
774:     PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));
775:     k   += (an-ak);
776:   }
777:   if (bk < bn) {
778:     PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));
779:     k   += (bn-bk);
780:   }
781:   *n = k;
782:   return(0);
783: }

785: /*@
786:    PetscMergeIntArrayPair -     Merges two SORTED integer arrays that share NO common values along with an additional array of integers.
787:                                 The additional arrays are the same length as sorted arrays and are merged
788:                                 in the order determined by the merging of the sorted pair.

790:    Not Collective

792:    Input Parameters:
793: +  an  - number of values in the first array
794: .  aI  - first sorted array of integers
795: .  aJ  - first additional array of integers
796: .  bn  - number of values in the second array
797: .  bI  - second array of integers
798: -  bJ  - second additional of integers

800:    Output Parameters:
801: +  n   - number of values in the merged array (== an + bn)
802: .  L   - merged sorted array 
803: -  J   - merged additional array

805:    Notes:
806:     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 
807:    Level: intermediate

809: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
810: @*/
811: PetscErrorCode  PetscMergeIntArrayPair(PetscInt an,const PetscInt aI[], const PetscInt aJ[], PetscInt bn, const PetscInt bI[], const PetscInt bJ[], PetscInt *n, PetscInt **L, PetscInt **J)
812: {
814:   PetscInt       n_, *L_, *J_, ak, bk, k;

819:   n_ = an + bn;
820:   *n = n_;
821:   if (!*L) {
822:     PetscMalloc1(n_, L);
823:   }
824:   L_ = *L;
825:   if (!*J) {
826:     PetscMalloc1(n_, J);
827:   }
828:   J_   = *J;
829:   k = ak = bk = 0;
830:   while (ak < an && bk < bn) {
831:     if (aI[ak] <= bI[bk]) {
832:       L_[k] = aI[ak];
833:       J_[k] = aJ[ak];
834:       ++ak;
835:       ++k;
836:     } else {
837:       L_[k] = bI[bk];
838:       J_[k] = bJ[bk];
839:       ++bk;
840:       ++k;
841:     }
842:   }
843:   if (ak < an) {
844:     PetscMemcpy(L_+k,aI+ak,(an-ak)*sizeof(PetscInt));
845:     PetscMemcpy(J_+k,aJ+ak,(an-ak)*sizeof(PetscInt));
846:     k   += (an-ak);
847:   }
848:   if (bk < bn) {
849:     PetscMemcpy(L_+k,bI+bk,(bn-bk)*sizeof(PetscInt));
850:     PetscMemcpy(J_+k,bJ+bk,(bn-bk)*sizeof(PetscInt));
851:   }
852:   return(0);
853: }

855: /*@
856:    PetscMergeMPIIntArray -     Merges two SORTED integer arrays.

858:    Not Collective

860:    Input Parameters:
861: +  an  - number of values in the first array
862: .  aI  - first sorted array of integers
863: .  bn  - number of values in the second array
864: -  bI  - second array of integers

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

870:    Level: intermediate

872: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
873: @*/
874: PetscErrorCode PetscMergeMPIIntArray(PetscInt an,const PetscMPIInt aI[],PetscInt bn,const PetscMPIInt bI[],PetscInt *n,PetscMPIInt **L)
875: {
877:   PetscInt       ai,bi,k;

880:   if (!*L) {PetscMalloc1((an+bn),L);}
881:   for (ai=0,bi=0,k=0; ai<an || bi<bn; ) {
882:     PetscInt t = -1;
883:     for ( ; ai<an && (!bn || aI[ai] <= bI[bi]); ai++) (*L)[k++] = t = aI[ai];
884:     for ( ; bi<bn && bI[bi] == t; bi++);
885:     for ( ; bi<bn && (!an || bI[bi] <= aI[ai]); bi++) (*L)[k++] = t = bI[bi];
886:     for ( ; ai<an && aI[ai] == t; ai++);
887:   }
888:   *n = k;
889:   return(0);
890: }

892: /*@C
893:    PetscProcessTree - Prepares tree data to be displayed graphically

895:    Not Collective

897:    Input Parameters:
898: +  n  - number of values
899: .  mask - indicates those entries in the tree, location 0 is always masked
900: -  parentid - indicates the parent of each entry

902:    Output Parameters:
903: +  Nlevels - the number of levels
904: .  Level - for each node tells its level
905: .  Levelcnts - the number of nodes on each level
906: .  Idbylevel - a list of ids on each of the levels, first level followed by second etc
907: -  Column - for each id tells its column index

909:    Level: developer

911:    Notes:
912:     This code is not currently used

914: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
915: @*/
916: PetscErrorCode  PetscProcessTree(PetscInt n,const PetscBool mask[],const PetscInt parentid[],PetscInt *Nlevels,PetscInt **Level,PetscInt **Levelcnt,PetscInt **Idbylevel,PetscInt **Column)
917: {
918:   PetscInt       i,j,cnt,nmask = 0,nlevels = 0,*level,*levelcnt,levelmax = 0,*workid,*workparentid,tcnt = 0,*idbylevel,*column;
920:   PetscBool      done = PETSC_FALSE;

923:   if (!mask[0]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Mask of 0th location must be set");
924:   for (i=0; i<n; i++) {
925:     if (mask[i]) continue;
926:     if (parentid[i]  == i) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Node labeled as own parent");
927:     if (parentid[i] && mask[parentid[i]]) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Parent is masked");
928:   }

930:   for (i=0; i<n; i++) {
931:     if (!mask[i]) nmask++;
932:   }

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

937:   level[0] = 1;
938:   while (!done) {
939:     done = PETSC_TRUE;
940:     for (i=0; i<n; i++) {
941:       if (mask[i]) continue;
942:       if (!level[i] && level[parentid[i]]) level[i] = level[parentid[i]] + 1;
943:       else if (!level[i]) done = PETSC_FALSE;
944:     }
945:   }
946:   for (i=0; i<n; i++) {
947:     level[i]--;
948:     nlevels = PetscMax(nlevels,level[i]);
949:   }

951:   /* count the number of nodes on each level and its max */
952:   PetscCalloc1(nlevels,&levelcnt);
953:   for (i=0; i<n; i++) {
954:     if (mask[i]) continue;
955:     levelcnt[level[i]-1]++;
956:   }
957:   for (i=0; i<nlevels;i++) levelmax = PetscMax(levelmax,levelcnt[i]);

959:   /* for each level sort the ids by the parent id */
960:   PetscMalloc2(levelmax,&workid,levelmax,&workparentid);
961:   PetscMalloc1(nmask,&idbylevel);
962:   for (j=1; j<=nlevels;j++) {
963:     cnt = 0;
964:     for (i=0; i<n; i++) {
965:       if (mask[i]) continue;
966:       if (level[i] != j) continue;
967:       workid[cnt]         = i;
968:       workparentid[cnt++] = parentid[i];
969:     }
970:     /*  PetscIntView(cnt,workparentid,0);
971:     PetscIntView(cnt,workid,0);
972:     PetscSortIntWithArray(cnt,workparentid,workid);
973:     PetscIntView(cnt,workparentid,0);
974:     PetscIntView(cnt,workid,0);*/
975:     PetscMemcpy(idbylevel+tcnt,workid,cnt*sizeof(PetscInt));
976:     tcnt += cnt;
977:   }
978:   if (tcnt != nmask) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Inconsistent count of unmasked nodes");
979:   PetscFree2(workid,workparentid);

981:   /* for each node list its column */
982:   PetscMalloc1(n,&column);
983:   cnt = 0;
984:   for (j=0; j<nlevels; j++) {
985:     for (i=0; i<levelcnt[j]; i++) {
986:       column[idbylevel[cnt++]] = i;
987:     }
988:   }

990:   *Nlevels   = nlevels;
991:   *Level     = level;
992:   *Levelcnt  = levelcnt;
993:   *Idbylevel = idbylevel;
994:   *Column    = column;
995:   return(0);
996: }