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 /* -----------------------------------------------------------------------*/ 87 #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;} 88 89 #undef __FUNCT__ 90 #define __FUNCT__ "PetscSortIntWithArray_Private" 91 /* 92 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 93 Assumes 0 origin for v, number of elements = right+1 (right is index of 94 right-most member). 95 */ 96 static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right) 97 { 98 PetscErrorCode ierr; 99 PetscInt i,vl,last,tmp; 100 101 PetscFunctionBegin; 102 if (right <= 1) { 103 if (right == 1) { 104 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 105 } 106 PetscFunctionReturn(0); 107 } 108 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 109 vl = v[0]; 110 last = 0; 111 for (i=1; i<=right; i++) { 112 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 113 } 114 SWAP2(v[0],v[last],V[0],V[last],tmp); 115 ierr = PetscSortIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 116 ierr = PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 117 PetscFunctionReturn(0); 118 } 119 120 #undef __FUNCT__ 121 #define __FUNCT__ "PetscSortIntWithArray" 122 /*@ 123 PetscSortIntWithArray - Sorts an array of integers in place in increasing order; 124 changes a second array to match the sorted first array. 125 126 Not Collective 127 128 Input Parameters: 129 + n - number of values 130 . i - array of integers 131 - I - second array of integers 132 133 Level: intermediate 134 135 Concepts: sorting^ints with array 136 137 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 138 @*/ 139 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[]) 140 { 141 PetscErrorCode ierr; 142 PetscInt j,k,tmp,ik; 143 144 PetscFunctionBegin; 145 if (n<8) { 146 for (k=0; k<n; k++) { 147 ik = i[k]; 148 for (j=k+1; j<n; j++) { 149 if (ik > i[j]) { 150 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 151 ik = i[k]; 152 } 153 } 154 } 155 } else { 156 ierr = PetscSortIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 157 } 158 PetscFunctionReturn(0); 159 } 160 161 #undef __FUNCT__ 162 #define __FUNCT__ "PetscSortMPIIntWithArray_Private" 163 /* 164 A simple version of quicksort; taken from Kernighan and Ritchie, page 87. 165 Assumes 0 origin for v, number of elements = right+1 (right is index of 166 right-most member). 167 */ 168 static PetscErrorCode PetscSortMPIIntWithArray_Private(PetscMPIInt *v,PetscMPIInt *V,PetscMPIInt right) 169 { 170 PetscErrorCode ierr; 171 PetscMPIInt i,vl,last,tmp; 172 173 PetscFunctionBegin; 174 if (right <= 1) { 175 if (right == 1) { 176 if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp); 177 } 178 PetscFunctionReturn(0); 179 } 180 SWAP2(v[0],v[right/2],V[0],V[right/2],tmp); 181 vl = v[0]; 182 last = 0; 183 for (i=1; i<=right; i++) { 184 if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);} 185 } 186 SWAP2(v[0],v[last],V[0],V[last],tmp); 187 ierr = PetscSortMPIIntWithArray_Private(v,V,last-1);CHKERRQ(ierr); 188 ierr = PetscSortMPIIntWithArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 189 PetscFunctionReturn(0); 190 } 191 192 #undef __FUNCT__ 193 #define __FUNCT__ "PetscSortMPIIntWithArray" 194 /*@ 195 PetscSortMPIIntWithArray - Sorts an array of integers in place in increasing order; 196 changes a second array to match the sorted first array. 197 198 Not Collective 199 200 Input Parameters: 201 + n - number of values 202 . i - array of integers 203 - I - second array of integers 204 205 Level: intermediate 206 207 Concepts: sorting^ints with array 208 209 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt() 210 @*/ 211 PetscErrorCode PETSC_DLLEXPORT PetscSortMPIIntWithArray(PetscMPIInt n,PetscMPIInt i[],PetscMPIInt Ii[]) 212 { 213 PetscErrorCode ierr; 214 PetscMPIInt j,k,tmp,ik; 215 216 PetscFunctionBegin; 217 if (n<8) { 218 for (k=0; k<n; k++) { 219 ik = i[k]; 220 for (j=k+1; j<n; j++) { 221 if (ik > i[j]) { 222 SWAP2(i[k],i[j],Ii[k],Ii[j],tmp); 223 ik = i[k]; 224 } 225 } 226 } 227 } else { 228 ierr = PetscSortMPIIntWithArray_Private(i,Ii,n-1);CHKERRQ(ierr); 229 } 230 PetscFunctionReturn(0); 231 } 232 233 /* -----------------------------------------------------------------------*/ 234 #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;} 235 236 #undef __FUNCT__ 237 #define __FUNCT__ "PetscSortIntWithScalarArray_Private" 238 /* 239 Modified from PetscSortIntWithArray_Private(). 240 */ 241 static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right) 242 { 243 PetscErrorCode ierr; 244 PetscInt i,vl,last,tmp; 245 PetscScalar stmp; 246 247 PetscFunctionBegin; 248 if (right <= 1) { 249 if (right == 1) { 250 if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp); 251 } 252 PetscFunctionReturn(0); 253 } 254 SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp); 255 vl = v[0]; 256 last = 0; 257 for (i=1; i<=right; i++) { 258 if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);} 259 } 260 SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp); 261 ierr = PetscSortIntWithScalarArray_Private(v,V,last-1);CHKERRQ(ierr); 262 ierr = PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));CHKERRQ(ierr); 263 PetscFunctionReturn(0); 264 } 265 266 #undef __FUNCT__ 267 #define __FUNCT__ "PetscSortIntWithScalarArray" 268 /*@ 269 PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order; 270 changes a second SCALAR array to match the sorted first INTEGER array. 271 272 Not Collective 273 274 Input Parameters: 275 + n - number of values 276 . i - array of integers 277 - I - second array of scalars 278 279 Level: intermediate 280 281 Concepts: sorting^ints with array 282 283 .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray() 284 @*/ 285 PetscErrorCode PETSC_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[]) 286 { 287 PetscErrorCode ierr; 288 PetscInt j,k,tmp,ik; 289 PetscScalar stmp; 290 291 PetscFunctionBegin; 292 if (n<8) { 293 for (k=0; k<n; k++) { 294 ik = i[k]; 295 for (j=k+1; j<n; j++) { 296 if (ik > i[j]) { 297 SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp); 298 ik = i[k]; 299 } 300 } 301 } 302 } else { 303 ierr = PetscSortIntWithScalarArray_Private(i,Ii,n-1);CHKERRQ(ierr); 304 } 305 PetscFunctionReturn(0); 306 } 307 308 309