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 #undef __FUNCT__ 163 #define __FUNCT__ "PetscSortMPIIntWithArray_Private" 164 /* 165 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 166 Assumes 0 origin for v, number of elements = right+1 (right is index of 167 right-most member). 168 */ 169 static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right) 170 { 171 PetscErrorCode ierr; 172 PetscMPIInt i,vl,last,tmp; 173 174 PetscFunctionBegin; 175 if (right <= 1) { 176 if (right == 1) { 177 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 178 } 179 PetscFunctionReturn(0); 180 } 181 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 182 vl = v[0]; 183 last = 0; 184 for (i=1; i<=right; i++) { 185 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 186 } 187 SWAP2(v[0],v[last],V[0],V[last],tmp); 188 ierr = PetscSortMPIIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 189 ierr = PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 190 PetscFunctionReturn(0); 191 } 192 193 #undef __FUNCT__ 194 #define __FUNCT__ "PetscSortMPIIntWithArray" 195 /*@ 196 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 197 changes a second array to match the sorted first array. 198 199 Not Collective 200 201 Input Parameters: 202 + n - number of values 203 . i - array of integers 204 - I - second array of integers 205 206 Level: intermediate 207 208 Concepts: sorting^ints with array 209 210 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 211 @*/ 212 PetscErrorCode PETSC_DLLEXPORT PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[]) 213 { 214 PetscErrorCode ierr; 215 PetscMPIInt j,k,tmp,ik; 216 217 PetscFunctionBegin; 218 if (n<8) { 219 for (k=0; k<n; k++) { 220 ik = i[k]; 221 for (j=k+1; j<n; j++) { 222 if (ik > i[j]) { 223 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 224 ik = i[k]; 225 } 226 } 227 } 228 } else { 229 ierr = PetscSortMPIIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 230 } 231 PetscFunctionReturn(0); 232 } 233 234 /* -----------------------------------------------------------------------*/ 235 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 236 237 #undef __FUNCT__ 238 #define __FUNCT__ "PetscSortIntWithScalarArray_Private" 239 /* 240 Modified from PetscSortIntWithArray_Private(). 241 */ 242 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 243 { 244 PetscErrorCode ierr; 245 PetscInt i,vl,last,tmp; 246 PetscScalar stmp; 247 248 PetscFunctionBegin; 249 if (right <= 1) { 250 if (right == 1) { 251 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 252 } 253 PetscFunctionReturn(0); 254 } 255 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 256 vl = v[0]; 257 last = 0; 258 for (i=1; i<=right; i++) { 259 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 260 } 261 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 262 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 263 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 264 PetscFunctionReturn(0); 265 } 266 267 #undef __FUNCT__ 268 #define __FUNCT__ "PetscSortIntWithScalarArray" 269 /*@ 270 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 271 changes a second SCALAR array to match the sorted first INTEGER array. 272 273 Not Collective 274 275 Input Parameters: 276 + n - number of values 277 . i - array of integers 278 - I - second array of scalars 279 280 Level: intermediate 281 282 Concepts: sorting^ints with array 283 284 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 285 @*/ 286 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 287 { 288 PetscErrorCode ierr; 289 PetscInt j,k,tmp,ik; 290 PetscScalar stmp; 291 292 PetscFunctionBegin; 293 if (n<8) { 294 for (k=0; k<n; k++) { 295 ik = i[k]; 296 for (j=k+1; j<n; j++) { 297 if (ik > i[j]) { 298 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 299 ik = i[k]; 300 } 301 } 302 } 303 } else { 304 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 305 } 306 PetscFunctionReturn(0); 307 } 308 309 310