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 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right) 14 { 15 PetscErrorCode ierr; 16 PetscInt tmp,i,vl,last; 17 18 PetscFunctionBegin; 19 if (right <= 1) { 20 if (right == 1) { 21 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 22 } 23 PetscFunctionReturn(0); 24 } 25 SWAP(vdx[0],vdx[right/2],tmp); 26 vl = v[vdx[0]]; 27 last = 0; 28 for (i=1; i<=right; i++) { 29 if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);} 30 } 31 SWAP(vdx[0],vdx[last],tmp); 32 ierr = PetscSortIntWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 33 ierr = PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 34 PetscFunctionReturn(0); 35 } 36 37 /*@ 38 PetscSortIntWithPermutation - Computes the permutation of values that gives 39 a sorted sequence. 40 41 Not Collective 42 43 Input Parameters: 44 + n - number of values to sort 45 . i - values to sort 46 - idx - permutation array. Must be initialized to 0:n-1 on input. 47 48 Level: intermediate 49 50 Notes: 51 On output i is unchanged and idx[i] is the position of the i-th smallest index in i. 52 53 .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray() 54 @*/ 55 PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[]) 56 { 57 PetscErrorCode ierr; 58 PetscInt j,k,tmp,ik; 59 60 PetscFunctionBegin; 61 if (n<8) { 62 for (k=0; k<n; k++) { 63 ik = i[idx[k]]; 64 for (j=k+1; j<n; j++) { 65 if (ik > i[idx[j]]) { 66 SWAP(idx[k],idx[j],tmp); 67 ik = i[idx[k]]; 68 } 69 } 70 } 71 } else { 72 ierr = PetscSortIntWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 73 } 74 PetscFunctionReturn(0); 75 } 76 77 /* ---------------------------------------------------------------------- */ 78 79 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right) 80 { 81 PetscReal vl; 82 PetscErrorCode ierr; 83 PetscInt tmp,i,last; 84 85 PetscFunctionBegin; 86 if (right <= 1) { 87 if (right == 1) { 88 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 89 } 90 PetscFunctionReturn(0); 91 } 92 SWAP(vdx[0],vdx[right/2],tmp); 93 vl = v[vdx[0]]; 94 last = 0; 95 for (i=1; i<=right; i++) { 96 if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);} 97 } 98 SWAP(vdx[0],vdx[last],tmp); 99 ierr = PetscSortRealWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 100 ierr = PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 101 PetscFunctionReturn(0); 102 } 103 104 /*@ 105 PetscSortRealWithPermutation - Computes the permutation of values that gives 106 a sorted sequence. 107 108 Not Collective 109 110 Input Parameters: 111 + n - number of values to sort 112 . i - values to sort 113 - idx - permutation array. Must be initialized to 0:n-1 on input. 114 115 Level: intermediate 116 117 Notes: 118 i is unchanged on output. 119 120 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 121 @*/ 122 PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[]) 123 { 124 PetscErrorCode ierr; 125 PetscInt j,k,tmp; 126 PetscReal ik; 127 128 PetscFunctionBegin; 129 if (n<8) { 130 for (k=0; k<n; k++) { 131 ik = i[idx[k]]; 132 for (j=k+1; j<n; j++) { 133 if (ik > i[idx[j]]) { 134 SWAP(idx[k],idx[j],tmp); 135 ik = i[idx[k]]; 136 } 137 } 138 } 139 } else { 140 ierr = PetscSortRealWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 141 } 142 PetscFunctionReturn(0); 143 } 144 145 static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right) 146 { 147 PetscErrorCode ierr; 148 PetscInt tmp,i,last; 149 PetscBool gt; 150 const char *vl; 151 152 PetscFunctionBegin; 153 if (right <= 1) { 154 if (right == 1) { 155 ierr = PetscStrgrt(v[vdx[0]],v[vdx[1]],>);CHKERRQ(ierr); 156 if (gt) SWAP(vdx[0],vdx[1],tmp); 157 } 158 PetscFunctionReturn(0); 159 } 160 SWAP(vdx[0],vdx[right/2],tmp); 161 vl = v[vdx[0]]; 162 last = 0; 163 for (i=1; i<=right; i++) { 164 ierr = PetscStrgrt(vl,v[vdx[i]],>);CHKERRQ(ierr); 165 if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);} 166 } 167 SWAP(vdx[0],vdx[last],tmp); 168 ierr = PetscSortStrWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 169 ierr = PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 170 PetscFunctionReturn(0); 171 } 172 173 /*@C 174 PetscSortStrWithPermutation - Computes the permutation of values that gives 175 a sorted sequence. 176 177 Not Collective 178 179 Input Parameters: 180 + n - number of values to sort 181 . i - values to sort 182 - idx - permutation array. Must be initialized to 0:n-1 on input. 183 184 Level: intermediate 185 186 Notes: 187 i is unchanged on output. 188 189 .seealso: PetscSortInt(), PetscSortRealWithPermutation() 190 @*/ 191 PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[]) 192 { 193 PetscErrorCode ierr; 194 PetscInt j,k,tmp; 195 const char *ik; 196 PetscBool gt; 197 198 PetscFunctionBegin; 199 if (n<8) { 200 for (k=0; k<n; k++) { 201 ik = i[idx[k]]; 202 for (j=k+1; j<n; j++) { 203 ierr = PetscStrgrt(ik,i[idx[j]],>);CHKERRQ(ierr); 204 if (gt) { 205 SWAP(idx[k],idx[j],tmp); 206 ik = i[idx[k]]; 207 } 208 } 209 } 210 } else { 211 ierr = PetscSortStrWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 212 } 213 PetscFunctionReturn(0); 214 } 215