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 "petscsys.h" /*I "petscsys.h" I*/ 11 12 #define SWAP(a,b,t) {t=a;a=b;b=t;} 13 14 /* -----------------------------------------------------------------------*/ 15 16 #undef __FUNCT__ 17 #define __FUNCT__ "PetscSortInt_Private" 18 /* 19 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 20 Assumes 0 origin for v, number of elements = right+1 (right is index of 21 right-most member). 22 */ 23 static PetscErrorCode PetscSortInt_Private(PetscInt *v,PetscInt right) 24 { 25 PetscErrorCode ierr; 26 PetscInt i,vl,last,tmp; 27 28 PetscFunctionBegin; 29 if (right <= 1) { 30 if (right == 1) { 31 if (v[0] > v[1]) SWAP(v[0],v[1],tmp); 32 } 33 PetscFunctionReturn(0); 34 } 35 SWAP(v[0],v[right/2],tmp); 36 vl = v[0]; 37 last = 0; 38 for (i=1; i<=right; i++) { 39 if (v[i] < vl) {last++; SWAP(v[last],v[i],tmp);} 40 } 41 SWAP(v[0],v[last],tmp); 42 ierr = PetscSortInt_Private(v,last-1);CHKERRQ(ierr); 43 ierr = PetscSortInt_Private(v+last+1,right-(last+1));CHKERRQ(ierr); 44 PetscFunctionReturn(0); 45 } 46 47 #undef __FUNCT__ 48 #define __FUNCT__ "PetscSortInt" 49 /*@ 50 PetscSortInt - Sorts an array of integers in place in increasing order. 51 52 Not Collective 53 54 Input Parameters: 55 + n - number of values 56 - i - array of integers 57 58 Level: intermediate 59 60 Concepts: sorting^ints 61 62 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 63 @*/ 64 PetscErrorCode PETSC_DLLEXPORT PetscSortInt(PetscInt n,PetscInt i[]) 65 { 66 PetscErrorCode ierr; 67 PetscInt j,k,tmp,ik; 68 69 PetscFunctionBegin; 70 if (n<8) { 71 for (k=0; k<n; k++) { 72 ik = i[k]; 73 for (j=k+1; j<n; j++) { 74 if (ik > i[j]) { 75 SWAP(i[k],i[j],tmp); 76 ik = i[k]; 77 } 78 } 79 } 80 } else { 81 ierr = PetscSortInt_Private(i,n-1);CHKERRQ(ierr); 82 } 83 PetscFunctionReturn(0); 84 } 85 86 #undef __FUNCT__ 87 #define __FUNCT__ "PetscSortRemoveDupsInt" 88 /*@ 89 PetscSortRemoveDupsInt - Sorts an array of integers in place in increasing order removes all duplicate entries 90 91 Not Collective 92 93 Input Parameters: 94 + n - number of values 95 - ii - array of integers 96 97 Output Parameter: 98 . n - number of non-redundant values 99 100 Level: intermediate 101 102 Concepts: sorting^ints 103 104 .seealso: PetscSortReal(), PetscSortIntWithPermutation(), PetscSortInt() 105 @*/ 106 PetscErrorCode PETSC_DLLEXPORT PetscSortRemoveDupsInt(PetscInt *n,PetscInt ii[]) 107 { 108 PetscErrorCode ierr; 109 PetscInt i,s = 0,N = *n, b = 0; 110 111 PetscFunctionBegin; 112 ierr = PetscSortInt(N,ii);CHKERRQ(ierr); 113 for (i=0; i<N-1; i++) { 114 if (ii[b+s+1] == ii[b]) {ii[b+1] = ii[b+s+2]; s++;} 115 else b++; 116 } 117 *n = N - s; 118 PetscFunctionReturn(0); 119 } 120 121 122 /* -----------------------------------------------------------------------*/ 123 #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;} 124 125 #undef __FUNCT__ 126 #define __FUNCT__ "PetscSortIntWithArray_Private" 127 /* 128 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 129 Assumes 0 origin for v, number of elements = right+1 (right is index of 130 right-most member). 131 */ 132 static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right) 133 { 134 PetscErrorCode ierr; 135 PetscInt i,vl,last,tmp; 136 137 PetscFunctionBegin; 138 if (right <= 1) { 139 if (right == 1) { 140 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 141 } 142 PetscFunctionReturn(0); 143 } 144 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 145 vl = v[0]; 146 last = 0; 147 for (i=1; i<=right; i++) { 148 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 149 } 150 SWAP2(v[0],v[last],V[0],V[last],tmp); 151 ierr = PetscSortIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 152 ierr = PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 153 PetscFunctionReturn(0); 154 } 155 156 #undef __FUNCT__ 157 #define __FUNCT__ "PetscSortIntWithArray" 158 /*@ 159 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 160 changes a second array to match the sorted first array. 161 162 Not Collective 163 164 Input Parameters: 165 + n - number of values 166 . i - array of integers 167 - I - second array of integers 168 169 Level: intermediate 170 171 Concepts: sorting^ints with array 172 173 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 174 @*/ 175 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[]) 176 { 177 PetscErrorCode ierr; 178 PetscInt j,k,tmp,ik; 179 180 PetscFunctionBegin; 181 if (n<8) { 182 for (k=0; k<n; k++) { 183 ik = i[k]; 184 for (j=k+1; j<n; j++) { 185 if (ik > i[j]) { 186 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 187 ik = i[k]; 188 } 189 } 190 } 191 } else { 192 ierr = PetscSortIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 193 } 194 PetscFunctionReturn(0); 195 } 196 197 #undef __FUNCT__ 198 #define __FUNCT__ "PetscSortMPIIntWithArray_Private" 199 /* 200 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 201 Assumes 0 origin for v, number of elements = right+1 (right is index of 202 right-most member). 203 */ 204 static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right) 205 { 206 PetscErrorCode ierr; 207 PetscMPIInt i,vl,last,tmp; 208 209 PetscFunctionBegin; 210 if (right <= 1) { 211 if (right == 1) { 212 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 213 } 214 PetscFunctionReturn(0); 215 } 216 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 217 vl = v[0]; 218 last = 0; 219 for (i=1; i<=right; i++) { 220 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 221 } 222 SWAP2(v[0],v[last],V[0],V[last],tmp); 223 ierr = PetscSortMPIIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 224 ierr = PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 225 PetscFunctionReturn(0); 226 } 227 228 #undef __FUNCT__ 229 #define __FUNCT__ "PetscSortMPIIntWithArray" 230 /*@ 231 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 232 changes a second array to match the sorted first array. 233 234 Not Collective 235 236 Input Parameters: 237 + n - number of values 238 . i - array of integers 239 - I - second array of integers 240 241 Level: intermediate 242 243 Concepts: sorting^ints with array 244 245 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 246 @*/ 247 PetscErrorCode PETSC_DLLEXPORT PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[]) 248 { 249 PetscErrorCode ierr; 250 PetscMPIInt j,k,tmp,ik; 251 252 PetscFunctionBegin; 253 if (n<8) { 254 for (k=0; k<n; k++) { 255 ik = i[k]; 256 for (j=k+1; j<n; j++) { 257 if (ik > i[j]) { 258 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 259 ik = i[k]; 260 } 261 } 262 } 263 } else { 264 ierr = PetscSortMPIIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 265 } 266 PetscFunctionReturn(0); 267 } 268 269 /* -----------------------------------------------------------------------*/ 270 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 271 272 #undef __FUNCT__ 273 #define __FUNCT__ "PetscSortIntWithScalarArray_Private" 274 /* 275 Modified from PetscSortIntWithArray_Private(). 276 */ 277 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 278 { 279 PetscErrorCode ierr; 280 PetscInt i,vl,last,tmp; 281 PetscScalar stmp; 282 283 PetscFunctionBegin; 284 if (right <= 1) { 285 if (right == 1) { 286 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 287 } 288 PetscFunctionReturn(0); 289 } 290 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 291 vl = v[0]; 292 last = 0; 293 for (i=1; i<=right; i++) { 294 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 295 } 296 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 297 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 298 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 299 PetscFunctionReturn(0); 300 } 301 302 #undef __FUNCT__ 303 #define __FUNCT__ "PetscSortIntWithScalarArray" 304 /*@ 305 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 306 changes a second SCALAR array to match the sorted first INTEGER array. 307 308 Not Collective 309 310 Input Parameters: 311 + n - number of values 312 . i - array of integers 313 - I - second array of scalars 314 315 Level: intermediate 316 317 Concepts: sorting^ints with array 318 319 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 320 @*/ 321 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 322 { 323 PetscErrorCode ierr; 324 PetscInt j,k,tmp,ik; 325 PetscScalar stmp; 326 327 PetscFunctionBegin; 328 if (n<8) { 329 for (k=0; k<n; k++) { 330 ik = i[k]; 331 for (j=k+1; j<n; j++) { 332 if (ik > i[j]) { 333 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 334 ik = i[k]; 335 } 336 } 337 } 338 } else { 339 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 340 } 341 PetscFunctionReturn(0); 342 } 343 344 345