1 2 /* 3 This file contains routines for sorting integers and doubles with a permutation array. 4 5 The word "register" in this code is used to identify data that is not 6 aliased. For some compilers, this can cause the compiler to fail to 7 place inner-loop variables into registers. 8 */ 9 #include <petscsys.h> /*I "petscsys.h" I*/ 10 11 #define SWAP(a,b,t) {t=a;a=b;b=t;} 12 13 #undef __FUNCT__ 14 #define __FUNCT__ "PetscSortIntWithPermutation_Private" 15 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right) 16 { 17 PetscErrorCode ierr; 18 PetscInt tmp,i,vl,last; 19 20 PetscFunctionBegin; 21 if (right <= 1) { 22 if (right == 1) { 23 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 24 } 25 PetscFunctionReturn(0); 26 } 27 SWAP(vdx[0],vdx[right/2],tmp); 28 vl = v[vdx[0]]; 29 last = 0; 30 for (i=1; i<=right; i++) { 31 if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);} 32 } 33 SWAP(vdx[0],vdx[last],tmp); 34 ierr = PetscSortIntWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 35 ierr = PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 36 PetscFunctionReturn(0); 37 } 38 39 #undef __FUNCT__ 40 #define __FUNCT__ "PetscSortIntWithPermutation" 41 /*@ 42 PetscSortIntWithPermutation - Computes the permutation of values that gives 43 a sorted sequence. 44 45 Not Collective 46 47 Input Parameters: 48 + n - number of values to sort 49 . i - values to sort 50 - idx - permutation array. Must be initialized to 0:n-1 on input. 51 52 Level: intermediate 53 54 Notes: 55 i is unchanged on output. 56 57 Concepts: sorting^ints with permutation 58 59 .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray() 60 @*/ 61 PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[]) 62 { 63 PetscErrorCode ierr; 64 PetscInt j,k,tmp,ik; 65 66 PetscFunctionBegin; 67 if (n<8) { 68 for (k=0; k<n; k++) { 69 ik = i[idx[k]]; 70 for (j=k+1; j<n; j++) { 71 if (ik > i[idx[j]]) { 72 SWAP(idx[k],idx[j],tmp); 73 ik = i[idx[k]]; 74 } 75 } 76 } 77 } else { 78 ierr = PetscSortIntWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 79 } 80 PetscFunctionReturn(0); 81 } 82 83 /* ---------------------------------------------------------------------- */ 84 85 #undef __FUNCT__ 86 #define __FUNCT__ "PetscSortRealWithPermutation_Private" 87 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right) 88 { 89 PetscReal vl; 90 PetscErrorCode ierr; 91 PetscInt tmp,i,last; 92 93 PetscFunctionBegin; 94 if (right <= 1) { 95 if (right == 1) { 96 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 97 } 98 PetscFunctionReturn(0); 99 } 100 SWAP(vdx[0],vdx[right/2],tmp); 101 vl = v[vdx[0]]; 102 last = 0; 103 for (i=1; i<=right; i++) { 104 if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);} 105 } 106 SWAP(vdx[0],vdx[last],tmp); 107 ierr = PetscSortRealWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 108 ierr = PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 109 PetscFunctionReturn(0); 110 } 111 112 #undef __FUNCT__ 113 #define __FUNCT__ "PetscSortRealWithPermutation" 114 /*@ 115 PetscSortRealWithPermutation - Computes the permutation of values that gives 116 a sorted sequence. 117 118 Not Collective 119 120 Input Parameters: 121 + n - number of values to sort 122 . i - values to sort 123 - idx - permutation array. Must be initialized to 0:n-1 on input. 124 125 Level: intermediate 126 127 Notes: 128 i is unchanged on output. 129 130 Concepts: sorting^doubles with permutation 131 132 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 133 @*/ 134 PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[]) 135 { 136 PetscErrorCode ierr; 137 PetscInt j,k,tmp; 138 PetscReal ik; 139 140 PetscFunctionBegin; 141 if (n<8) { 142 for (k=0; k<n; k++) { 143 ik = i[idx[k]]; 144 for (j=k+1; j<n; j++) { 145 if (ik > i[idx[j]]) { 146 SWAP(idx[k],idx[j],tmp); 147 ik = i[idx[k]]; 148 } 149 } 150 } 151 } else { 152 ierr = PetscSortRealWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 153 } 154 PetscFunctionReturn(0); 155 } 156 157 #undef __FUNCT__ 158 #define __FUNCT__ "PetscSortStrWithPermutation_Private" 159 static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right) 160 { 161 PetscErrorCode ierr; 162 PetscInt tmp,i,last; 163 PetscBool gt; 164 const char *vl; 165 166 PetscFunctionBegin; 167 if (right <= 1) { 168 if (right == 1) { 169 ierr = PetscStrgrt(v[vdx[0]],v[vdx[1]],>);CHKERRQ(ierr); 170 if (gt) SWAP(vdx[0],vdx[1],tmp); 171 } 172 PetscFunctionReturn(0); 173 } 174 SWAP(vdx[0],vdx[right/2],tmp); 175 vl = v[vdx[0]]; 176 last = 0; 177 for (i=1; i<=right; i++) { 178 ierr = PetscStrgrt(vl,v[vdx[i]],>);CHKERRQ(ierr); 179 if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);} 180 } 181 SWAP(vdx[0],vdx[last],tmp); 182 ierr = PetscSortStrWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 183 ierr = PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 184 PetscFunctionReturn(0); 185 } 186 187 #undef __FUNCT__ 188 #define __FUNCT__ "PetscSortStrWithPermutation" 189 /*@C 190 PetscSortStrWithPermutation - Computes the permutation of values that gives 191 a sorted sequence. 192 193 Not Collective 194 195 Input Parameters: 196 + n - number of values to sort 197 . i - values to sort 198 - idx - permutation array. Must be initialized to 0:n-1 on input. 199 200 Level: intermediate 201 202 Notes: 203 i is unchanged on output. 204 205 Concepts: sorting^ints with permutation 206 207 .seealso: PetscSortInt(), PetscSortRealWithPermutation() 208 @*/ 209 PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[]) 210 { 211 PetscErrorCode ierr; 212 PetscInt j,k,tmp; 213 const char *ik; 214 PetscBool gt; 215 216 PetscFunctionBegin; 217 if (n<8) { 218 for (k=0; k<n; k++) { 219 ik = i[idx[k]]; 220 for (j=k+1; j<n; j++) { 221 ierr = PetscStrgrt(ik,i[idx[j]],>);CHKERRQ(ierr); 222 if (gt) { 223 SWAP(idx[k],idx[j],tmp); 224 ik = i[idx[k]]; 225 } 226 } 227 } 228 } else { 229 ierr = PetscSortStrWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 230 } 231 PetscFunctionReturn(0); 232 } 233