1 #define PETSC_DLL 2 /* 3 This file contains routines for sorting integers. Values are sorted in place. 4 5 6 The word "register" in this code is used to identify data that is not 7 aliased. For some compilers, marking variables as register can improve 8 the compiler optimizations. 9 */ 10 #include "petsc.h" /*I "petsc.h" I*/ 11 #include "petscsys.h" /*I "petscsys.h" I*/ 12 13 #define SWAP(a,b,t) {t=a;a=b;b=t;} 14 15 /* -----------------------------------------------------------------------*/ 16 17 #undef __FUNCT__ 18 #define __FUNCT__ "PetscSortInt_Private" 19 /* 20 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 21 Assumes 0 origin for v, number of elements = right+1 (right is index of 22 right-most member). 23 */ 24 static PetscErrorCode PetscSortInt_Private(PetscInt *v,PetscInt right) 25 { 26 PetscErrorCode ierr; 27 PetscInt i,vl,last,tmp; 28 29 PetscFunctionBegin; 30 if (right <= 1) { 31 if (right == 1) { 32 if (v[0] > v[1]) SWAP(v[0],v[1],tmp); 33 } 34 PetscFunctionReturn(0); 35 } 36 SWAP(v[0],v[right/2],tmp); 37 vl = v[0]; 38 last = 0; 39 for (i=1; i<=right; i++) { 40 if (v[i] < vl) {last++; SWAP(v[last],v[i],tmp);} 41 } 42 SWAP(v[0],v[last],tmp); 43 ierr = PetscSortInt_Private(v,last-1);CHKERRQ(ierr); 44 ierr = PetscSortInt_Private(v+last+1,right-(last+1));CHKERRQ(ierr); 45 PetscFunctionReturn(0); 46 } 47 48 #undef __FUNCT__ 49 #define __FUNCT__ "PetscSortInt" 50 /*@ 51 PetscSortInt - Sorts an array of integers in place in increasing order. 52 53 Not Collective 54 55 Input Parameters: 56 + n - number of values 57 - i - array of integers 58 59 Level: intermediate 60 61 Concepts: sorting^ints 62 63 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 64 @*/ 65 PetscErrorCode PETSC_DLLEXPORT PetscSortInt(PetscInt n,PetscInt i[]) 66 { 67 PetscErrorCode ierr; 68 PetscInt j,k,tmp,ik; 69 70 PetscFunctionBegin; 71 if (n<8) { 72 for (k=0; k<n; k++) { 73 ik = i[k]; 74 for (j=k+1; j<n; j++) { 75 if (ik > i[j]) { 76 SWAP(i[k],i[j],tmp); 77 ik = i[k]; 78 } 79 } 80 } 81 } else { 82 ierr = PetscSortInt_Private(i,n-1);CHKERRQ(ierr); 83 } 84 PetscFunctionReturn(0); 85 } 86 87 /* -----------------------------------------------------------------------*/ 88 #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;} 89 90 #undef __FUNCT__ 91 #define __FUNCT__ "PetscSortIntWithArray_Private" 92 /* 93 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 94 Assumes 0 origin for v, number of elements = right+1 (right is index of 95 right-most member). 96 */ 97 static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right) 98 { 99 PetscErrorCode ierr; 100 PetscInt i,vl,last,tmp; 101 102 PetscFunctionBegin; 103 if (right <= 1) { 104 if (right == 1) { 105 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 106 } 107 PetscFunctionReturn(0); 108 } 109 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 110 vl = v[0]; 111 last = 0; 112 for (i=1; i<=right; i++) { 113 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 114 } 115 SWAP2(v[0],v[last],V[0],V[last],tmp); 116 ierr = PetscSortIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 117 ierr = PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 118 PetscFunctionReturn(0); 119 } 120 121 #undef __FUNCT__ 122 #define __FUNCT__ "PetscSortIntWithArray" 123 /*@ 124 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 125 changes a second array to match the sorted first array. 126 127 Not Collective 128 129 Input Parameters: 130 + n - number of values 131 . i - array of integers 132 - I - second array of integers 133 134 Level: intermediate 135 136 Concepts: sorting^ints with array 137 138 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 139 @*/ 140 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[]) 141 { 142 PetscErrorCode ierr; 143 PetscInt j,k,tmp,ik; 144 145 PetscFunctionBegin; 146 if (n<8) { 147 for (k=0; k<n; k++) { 148 ik = i[k]; 149 for (j=k+1; j<n; j++) { 150 if (ik > i[j]) { 151 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 152 ik = i[k]; 153 } 154 } 155 } 156 } else { 157 ierr = PetscSortIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 158 } 159 PetscFunctionReturn(0); 160 } 161 162 /* -----------------------------------------------------------------------*/ 163 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 164 165 #undef __FUNCT__ 166 #define __FUNCT__ "PetscSortIntWithScalarArray_Private" 167 /* 168 Modified from PetscSortIntWithArray_Private(). 169 */ 170 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 171 { 172 PetscErrorCode ierr; 173 PetscInt i,vl,last,tmp; 174 PetscScalar stmp; 175 176 PetscFunctionBegin; 177 if (right <= 1) { 178 if (right == 1) { 179 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 180 } 181 PetscFunctionReturn(0); 182 } 183 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 184 vl = v[0]; 185 last = 0; 186 for (i=1; i<=right; i++) { 187 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 188 } 189 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 190 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 191 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 192 PetscFunctionReturn(0); 193 } 194 195 #undef __FUNCT__ 196 #define __FUNCT__ "PetscSortIntWithScalarArray" 197 /*@ 198 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 199 changes a second SCALAR array to match the sorted first INTEGER array. 200 201 Not Collective 202 203 Input Parameters: 204 + n - number of values 205 . i - array of integers 206 - I - second array of scalars 207 208 Level: intermediate 209 210 Concepts: sorting^ints with array 211 212 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 213 @*/ 214 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 215 { 216 PetscErrorCode ierr; 217 PetscInt j,k,tmp,ik; 218 PetscScalar stmp; 219 220 PetscFunctionBegin; 221 if (n<8) { 222 for (k=0; k<n; k++) { 223 ik = i[k]; 224 for (j=k+1; j<n; j++) { 225 if (ik > i[j]) { 226 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 227 ik = i[k]; 228 } 229 } 230 } 231 } else { 232 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 233 } 234 PetscFunctionReturn(0); 235 } 236 237 238