00001
00004 template<class T> inline
00005 void _binary_sort(T *_P, T *_Q, T s)
00006 {
00007 T *P = _P, *Q = _Q;
00008 T p, q;
00009 while(P != Q)
00010 {
00011 if(((p = P[0]) & s) != 0) break;
00012 P++;
00013 }
00014 while(P != Q)
00015 {
00016 if(((q = Q[-1]) & s) == 0) break;
00017 Q--;
00018 }
00019 while(P != Q)
00020 {
00021 *P++ = q;
00022 *--Q = p;
00023 while(((p = P[0]) & s) == 0) P++;
00024 while(((q = Q[-1]) & s) != 0) Q--;
00025 }
00026 s >>= 1;
00027 if(s)
00028 {
00029 if(Q - _P > 1) _binary_sort(_P, Q, s);
00030 if(_Q - P > 1) _binary_sort(P, _Q, s);
00031 }
00032 }
00033
00037 template<class T, class S> inline
00038 void _binary_sort_copy(T *_P, T *_Q, S *_U, S* _V, T s)
00039 {
00040 T *P = _P, *Q = _Q;
00041 S *U = _U, *V = _V;
00042 T p, q;
00043 while(P != Q)
00044 {
00045 if(((p = P[0]) & s) != 0) break;
00046 P++;
00047 U++;
00048 }
00049 while(P != Q)
00050 {
00051 if(((q = Q[-1]) & s) == 0) break;
00052 Q--;
00053 V--;
00054 }
00055 while(P != Q)
00056 {
00057 *P++ = q;
00058 *--Q = p;
00059 S u, v;
00060 u = *U;
00061 v = *--V;
00062 *U++ = v;
00063 *V = u;
00064 while(((p = P[0]) & s) == 0) P++, U++;
00065 while(((q = Q[-1]) & s) != 0) Q--, V--;
00066 }
00067 s >>= 1;
00068 if(s)
00069 {
00070 if(Q - _P > 1) _binary_sort_copy(_P, Q, _U, V, s);
00071 if(_Q - P > 1) _binary_sort_copy(P, _Q, U, _V, s);
00072 }
00073 }
00074
00078 template<class T> inline
00079 void _binary_sort_sort(T *_P, T *_Q, T *_A, T *_B, T s, T t)
00080 {
00081 T *P = _P, *Q = _Q, *A = _A, *B = _B;
00082 T p, q;
00083 while(P != Q)
00084 {
00085 if(((p = P[0]) & s) != 0) break;
00086 P++;
00087 A++;
00088 }
00089 while(P != Q)
00090 {
00091 if(((q = Q[-1]) & s) == 0) break;
00092 Q--;
00093 B--;
00094 }
00095 while(P != Q)
00096 {
00097 *P++ = q;
00098 *--Q = p;
00099 T a, b;
00100 a = *A;
00101 b = *--B;
00102 *A++ = b;
00103 *B = a;
00104 while(((p = P[0]) & s) == 0) P++, A++;
00105 while(((q = Q[-1]) & s) != 0) Q--, B--;
00106 }
00107 s >>= 1;
00108 if(s)
00109 {
00110 if(Q - _P > 1) _binary_sort_sort(_P, Q, _A, B, s, t);
00111 if(_Q - P > 1) _binary_sort_sort(P, _Q, A, _B, s, t);
00112 }
00113 else if(t)
00114 {
00115 if(Q - _P > 1) _binary_sort_sort(_A, B, _P, Q, t, s);
00116 if(_Q - P > 1) _binary_sort_sort(A, _B, P, _Q, t, s);
00117 }
00118 }
00119
00123 template<class T, class S> inline
00124 void _binary_sort_sort_copy(T *_P, T *_Q, T *_A, T *_B, S *_U, S* _V, T s, T t)
00125 {
00126 T *P = _P, *Q = _Q, *A = _A, *B = _B;
00127 S *U = _U, *V = _V;
00128 T p, q;
00129 while(P != Q)
00130 {
00131 if(((p = P[0]) & s) != 0) break;
00132 P++;
00133 A++;
00134 U++;
00135 }
00136 while(P != Q)
00137 {
00138 if(((q = Q[-1]) & s) == 0) break;
00139 Q--;
00140 B--;
00141 V--;
00142 }
00143 while(P != Q)
00144 {
00145 *P++ = q;
00146 *--Q = p;
00147 T a, b;
00148 a = *A;
00149 b = *--B;
00150 *A++ = b;
00151 *B = a;
00152 S u, v;
00153 u = *U;
00154 v = *--V;
00155 *U++ = v;
00156 *V = u;
00157 while(((p = P[0]) & s) == 0) P++, A++, U++;
00158 while(((q = Q[-1]) & s) != 0) Q--, B--, V--;
00159 }
00160 s >>= 1;
00161 if(s)
00162 {
00163 if(Q - _P > 1) _binary_sort_sort_copy(_P, Q, _A, B, _U, V, s, t);
00164 if(_Q - P > 1) _binary_sort_sort_copy(P, _Q, A, _B, U, _V, s, t);
00165 }
00166 else if(t)
00167 {
00168 if(Q - _P > 1) _binary_sort_sort_copy(_A, B, _P, Q, _U, V, t, s);
00169 if(_Q - P > 1) _binary_sort_sort_copy(A, _B, P, _Q, U, _V, t, s);
00170 }
00171 }
00172
00176 template<class T, class S> inline
00177 void _fractal_sort_sort_copy(T *_P, T *_Q, T *_A, T *_B, S *_U, S* _V, T s, T t)
00178 {
00179 T *P = _P, *Q = _Q, *A = _A, *B = _B;
00180 S *U = _U, *V = _V;
00181 T p, q;
00182 while(P != Q)
00183 {
00184 if(((p = P[0]) & s) != 0) break;
00185 P++;
00186 A++;
00187 U++;
00188 }
00189 while(P != Q)
00190 {
00191 if(((q = Q[-1]) & s) == 0) break;
00192 Q--;
00193 B--;
00194 V--;
00195 }
00196 while(P != Q)
00197 {
00198 *P++ = q;
00199 *--Q = p;
00200 T a, b;
00201 a = *A;
00202 b = *--B;
00203 *A++ = b;
00204 *B = a;
00205 S u, v;
00206 u = *U;
00207 v = *--V;
00208 *U++ = v;
00209 *V = u;
00210 while(((p = P[0]) & s) == 0) P++, A++, U++;
00211 while(((q = Q[-1]) & s) != 0) Q--, B--, V--;
00212 }
00213 s >>= 1;
00214 if(t != 0)
00215 {
00216 if(Q - _P > 1) _fractal_sort_sort_copy(_A, B, _P, Q, _U, V, t, s);
00217 if(_Q - P > 1) _fractal_sort_sort_copy(A, _B, P, _Q, U, _V, t, s);
00218 }
00219 }
00220
00224 template<class T> inline
00225 T _binary_log(const T *P, const T *Q)
00226 {
00227 T s = 0;
00228 while(P != Q)
00229 {
00230 s |= *P++;
00231 }
00232 T t = ~0;
00233 while(s & t)
00234 {
00235 s &= t;
00236 t <<= 1;
00237 }
00238 return s;
00239 }
00240
00245 template<class T> inline
00246 void binary_sort(vector<T> &_V)
00247 {
00248 if(_V.size() < 2) return;
00249 _binary_sort(&_V[0], &_V[0]+_V.size(), _binary_log(&_V[0], &_V[0]+_V.size()));
00250 }
00251
00257 template<class T, class S> inline
00258 void binary_sort_copy(vector<T> &_V, vector<S> &_W)
00259 {
00260 if(_V.size() < 2) return;
00261 _binary_sort_copy(&_V[0], &_V[0]+_V.size(), &_W[0], &_W[0]+_W.size(), _binary_log(&_V[0], &_V[0]+_V.size()));
00262 }
00263
00269 template<class T> inline
00270 void binary_sort_sort(vector<T> &_V, vector<T> &_W)
00271 {
00272 if(_V.size() < 2) return;
00273 _binary_sort_sort(&_V[0], &_V[0]+_V.size(), &_W[0], &_W[0]+_W.size(),
00274 _binary_log(&_V[0], &_V[0]+_V.size()), _binary_log(&_W[0], &_W[0]+_W.size()));
00275 }
00276
00283 template<class T, class S> inline
00284 void binary_sort_sort_copy(vector<T> &_V, vector<T> &_W, vector<S> &_A)
00285 {
00286 if(_V.size() < 2) return;
00287 _binary_sort_sort_copy(&_V[0], &_V[0]+_V.size(), &_W[0], &_W[0]+_W.size(), &_A[0], &_A[0]+_A.size(),
00288 _binary_log(&_V[0], &_V[0]+_V.size()), _binary_log(&_W[0], &_W[0]+_W.size()));
00289 }
00290
00297 template<class T, class S> inline
00298 void fractal_sort_sort_copy(vector<T> &_V, vector<T> &_W, vector<S> &_A)
00299 {
00300 if(_V.size() < 2) return;
00301 T log = max(_binary_log(&_V[0], &_V[0]+_V.size()), _binary_log(&_W[0], &_W[0]+_W.size()));
00302 _fractal_sort_sort_copy(&_V[0], &_V[0]+_V.size(), &_W[0], &_W[0]+_W.size(), &_A[0], &_A[0]+_A.size(), log, log);
00303 }
00304
00310 template<class T, class S> inline
00311 void bucket_sort_count(const vector<T> &_U, vector<S> &_W)
00312 {
00313 const T *U = &_U[0], *V = &_U[0] + _U.size();
00314 S *W = &_W[0];
00315
00316 while(U != V)
00317 {
00318 W[*U++]++;
00319 }
00320 }
00321
00327 template<class T> inline
00328 T bucket_sort_size(const vector<T> &_U)
00329 {
00330 const T *U = &_U[0], *V = &_U[0] + _U.size();
00331
00332 T t = 0;
00333 while(U != V)
00334 {
00335 t += *U++;
00336 }
00337 return t;
00338 }
00339
00345 template<class T> inline
00346 void bucket_sort_offset(const vector<T> &_U, vector<T> &_W)
00347 {
00348 const T *U = &_U[0], *V = &_U[0] + _U.size();
00349 T *W = &_W[0];
00350
00351 T t = 0;
00352 while(U != V)
00353 {
00354 T s = *U++;
00355 *W++ = t;
00356 t += s;
00357 }
00358 }
00359
00368 template<class T, class S, class C> inline
00369 void bucket_sort_copy(const vector<T> &_U, const vector<C> &_A, vector<C> &_B, vector<S> _W, int _n)
00370 {
00371 const T *U = &_U[0], *V = &_U[0] + _U.size();
00372 const C *A = &_A[0];
00373 C *B = &_B[0];
00374 S *W = &_W[0];
00375
00376 while(U != V)
00377 {
00378 T t = *U++;
00379 S s = W[t];
00380 W[t]++;
00381 B = &_B[_n * s];
00382 for(int i = 0; i < _n; i++)
00383 {
00384 *B++ = *A++;
00385 }
00386 }
00387 }
00388
00393 template<class T> inline
00394 void unique(vector<T> &_P)
00395 {
00396 if(_P.size() < 2) return;
00397 T *P = &_P[0], *Q = &_P[0] + _P.size();
00398
00399 if(P != Q)
00400 {
00401 T* R = P;
00402 ++P;
00403 while(P != Q)
00404 {
00405 if ((*R != *P))
00406 {
00407 *++R = *P;
00408 }
00409 ++P;
00410 }
00411 ++R;
00412 _P.resize(R - &_P[0]);
00413 }
00414 }
00415
00421 template<class T, class S> inline
00422 void unique_accumulate(vector<T> &_P, vector<S> &_A)
00423 {
00424 if(_P.size() < 2) return;
00425 T *P = &_P[0], *Q = &_P[0] + _P.size();
00426 S *A = &_A[0];
00427
00428 if(P != Q)
00429 {
00430 T* R = P;
00431 S* C = A;
00432 ++P; ++A;
00433 while(P != Q)
00434 {
00435 if (*R == *P)
00436 {
00437 *C += *A;
00438 }
00439 else
00440 {
00441 *++R = *P;
00442 *++C = *A;
00443 }
00444 ++P; ++A;
00445 }
00446 ++R;
00447 ++C;
00448 _P.resize(R - &_P[0]);
00449 _A.resize(C - &_A[0]);
00450 }
00451 }
00452
00459 template<class T, class S> inline
00460 void unique_accumulate(vector<T> &_P, vector<T> &_U, vector<S> &_A)
00461 {
00462 if(_P.size() < 2) return;
00463 T *P = &_P[0], *Q = &_P[0] + _P.size();
00464 T *U = &_U[0];
00465 S *A = &_A[0];
00466
00467 if(P != Q)
00468 {
00469 T* R = P;
00470 T* W = U;
00471 S* C = A;
00472 ++P; ++U; ++A;
00473 while(P != Q)
00474 {
00475 if ((*R == *P) && (*W == *U))
00476 {
00477 *C += *A;
00478 }
00479 else
00480 {
00481 *++R = *P;
00482 *++W = *U;
00483 *++C = *A;
00484 }
00485 ++P; ++U; ++A;
00486 }
00487 ++R;
00488 ++W;
00489 ++C;
00490 _P.resize(R - &_P[0]);
00491 _U.resize(W - &_U[0]);
00492 _A.resize(C - &_A[0]);
00493 }
00494 }
00495
00496
00507 template<class T> inline
00508 void global_intersection(const int _size, const int _rank, const vector<T> &_P, const vector<T> &_U, vector<T> &_A, vector<T> &_C, vector<T> &_D)
00509 {
00510 const T *P = &_P[0], *U = &_U[0];
00511 T *A = &_A[0], *C = &_C[0], *D = &_D[0];
00512
00513 int j = 0, k, l;
00514 int m = (int)_P.size(), n;
00515 for(int i = 0; i < _size; i++)
00516 {
00517 k = 0, l = D[i], n = l + C[i];
00518
00519 D[i] = j;
00520 if(_rank != i)
00521 {
00522 while((k < m) && (l < n))
00523 {
00524 if (P[k] < A[l])
00525 {
00526 k++;
00527 }
00528 else if (A[l] < P[k])
00529 {
00530 l++;
00531 }
00532 else
00533 {
00534 A[j] = U[k];
00535 j++;
00536 k++;
00537 l++;
00538 }
00539 }
00540 }
00541 C[i] = j - D[i];
00542 }
00543 _A.resize(j);
00544 }
00545
