|
GiNaC
1.6.2
|
00001 00006 /* 00007 * GiNaC Copyright (C) 1999-2011 Johannes Gutenberg University Mainz, Germany 00008 * 00009 * This program is free software; you can redistribute it and/or modify 00010 * it under the terms of the GNU General Public License as published by 00011 * the Free Software Foundation; either version 2 of the License, or 00012 * (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 * GNU General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU General Public License 00020 * along with this program; if not, write to the Free Software 00021 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00022 */ 00023 00024 #ifndef GINAC_UTILS_H 00025 #define GINAC_UTILS_H 00026 00027 #include "assertion.h" 00028 #ifdef HAVE_CONFIG_H 00029 #include "config.h" 00030 #endif 00031 00032 #include <functional> 00033 #ifdef HAVE_STDINT_H 00034 #include <stdint.h> // for uintptr_t 00035 #endif 00036 #include <string> 00037 00038 namespace GiNaC { 00039 00042 class dunno {}; 00043 00044 // some compilers (e.g. cygwin) define a macro log2, causing confusion 00045 #ifdef log2 00046 #undef log2 00047 #endif 00048 00049 unsigned log2(unsigned n); 00050 00053 inline unsigned rotate_left(unsigned n) 00054 { 00055 return (n & 0x80000000U) ? (n << 1 | 0x00000001U) : (n << 1); 00056 } 00057 00060 template <class T> 00061 inline int compare_pointers(const T * a, const T * b) 00062 { 00063 // '<' is not defined for pointers that don't point to the same array, 00064 // but std::less is. 00065 if (std::less<const T *>()(a, b)) 00066 return -1; 00067 else if (std::less<const T *>()(b, a)) 00068 return 1; 00069 return 0; 00070 } 00071 00072 #ifdef HAVE_STDINT_H 00073 typedef uintptr_t p_int; 00074 #else 00075 typedef unsigned long p_int; 00076 #endif 00077 00079 inline unsigned golden_ratio_hash(p_int n) 00080 { 00081 // This function works much better when fast arithmetic with at 00082 // least 64 significant bits is available. 00083 if (sizeof(long) >= 8) { 00084 // So 'long' has 64 bits. Excellent! We prefer it because it might be 00085 // more efficient than 'long long'. 00086 unsigned long l = n * 0x4f1bbcddUL; 00087 return (unsigned)l; 00088 } 00089 #ifdef HAVE_LONG_LONG 00090 else if (sizeof(long long) >= 8) { 00091 // This requires 'long long' (or an equivalent 64 bit type)---which is, 00092 // unfortunately, not ANSI-C++-compliant. 00093 // (Yet C99 demands it, which is reason for hope.) 00094 unsigned long long l = n * 0x4f1bbcddULL; 00095 return (unsigned)l; 00096 } 00097 #endif 00098 // Without a type with 64 significant bits do the multiplication manually 00099 // by splitting n up into the lower and upper two bytes. 00100 const unsigned n0 = (n & 0x0000ffffU); 00101 const unsigned n1 = (n & 0xffff0000U) >> 16; 00102 return (n0 * 0x0000bcddU) + ((n1 * 0x0000bcddU + n0 * 0x00004f1bU) << 16); 00103 } 00104 00105 /* Compute the sign of a permutation of a container, with and without an 00106 explicitly supplied comparison function. If the sign returned is 1 or -1, 00107 the container is sorted after the operation. */ 00108 template <class It> 00109 int permutation_sign(It first, It last) 00110 { 00111 if (first == last) 00112 return 0; 00113 --last; 00114 if (first == last) 00115 return 0; 00116 It flag = first; 00117 int sign = 1; 00118 00119 do { 00120 It i = last, other = last; 00121 --other; 00122 bool swapped = false; 00123 while (i != first) { 00124 if (*i < *other) { 00125 std::iter_swap(other, i); 00126 flag = other; 00127 swapped = true; 00128 sign = -sign; 00129 } else if (!(*other < *i)) 00130 return 0; 00131 --i; 00132 if (i != first) 00133 --other; 00134 } 00135 if (!swapped) 00136 return sign; 00137 ++flag; 00138 if (flag == last) 00139 return sign; 00140 first = flag; 00141 i = first; other = first; 00142 ++other; 00143 swapped = false; 00144 while (i != last) { 00145 if (*other < *i) { 00146 std::iter_swap(i, other); 00147 flag = other; 00148 swapped = true; 00149 sign = -sign; 00150 } else if (!(*i < *other)) 00151 return 0; 00152 ++i; 00153 if (i != last) 00154 ++other; 00155 } 00156 if (!swapped) 00157 return sign; 00158 last = flag; 00159 --last; 00160 } while (first != last); 00161 00162 return sign; 00163 } 00164 00165 template <class It, class Cmp, class Swap> 00166 int permutation_sign(It first, It last, Cmp comp, Swap swapit) 00167 { 00168 if (first == last) 00169 return 0; 00170 --last; 00171 if (first == last) 00172 return 0; 00173 It flag = first; 00174 int sign = 1; 00175 00176 do { 00177 It i = last, other = last; 00178 --other; 00179 bool swapped = false; 00180 while (i != first) { 00181 if (comp(*i, *other)) { 00182 swapit(*other, *i); 00183 flag = other; 00184 swapped = true; 00185 sign = -sign; 00186 } else if (!comp(*other, *i)) 00187 return 0; 00188 --i; 00189 if (i != first) 00190 --other; 00191 } 00192 if (!swapped) 00193 return sign; 00194 ++flag; 00195 if (flag == last) 00196 return sign; 00197 first = flag; 00198 i = first; other = first; 00199 ++other; 00200 swapped = false; 00201 while (i != last) { 00202 if (comp(*other, *i)) { 00203 swapit(*i, *other); 00204 flag = other; 00205 swapped = true; 00206 sign = -sign; 00207 } else if (!comp(*i, *other)) 00208 return 0; 00209 ++i; 00210 if (i != last) 00211 ++other; 00212 } 00213 if (!swapped) 00214 return sign; 00215 last = flag; 00216 --last; 00217 } while (first != last); 00218 00219 return sign; 00220 } 00221 00222 /* Implementation of shaker sort, only compares adjacent elements. */ 00223 template <class It, class Cmp, class Swap> 00224 void shaker_sort(It first, It last, Cmp comp, Swap swapit) 00225 { 00226 if (first == last) 00227 return; 00228 --last; 00229 if (first == last) 00230 return; 00231 It flag = first; 00232 00233 do { 00234 It i = last, other = last; 00235 --other; 00236 bool swapped = false; 00237 while (i != first) { 00238 if (comp(*i, *other)) { 00239 swapit(*other, *i); 00240 flag = other; 00241 swapped = true; 00242 } 00243 --i; 00244 if (i != first) 00245 --other; 00246 } 00247 if (!swapped) 00248 return; 00249 ++flag; 00250 if (flag == last) 00251 return; 00252 first = flag; 00253 i = first; other = first; 00254 ++other; 00255 swapped = false; 00256 while (i != last) { 00257 if (comp(*other, *i)) { 00258 swapit(*i, *other); 00259 flag = other; 00260 swapped = true; 00261 } 00262 ++i; 00263 if (i != last) 00264 ++other; 00265 } 00266 if (!swapped) 00267 return; 00268 last = flag; 00269 --last; 00270 } while (first != last); 00271 } 00272 00273 /* In-place cyclic permutation of a container (no copying, only swapping). */ 00274 template <class It, class Swap> 00275 void cyclic_permutation(It first, It last, It new_first, Swap swapit) 00276 { 00277 unsigned num = last - first; 00278 again: 00279 if (first == new_first || num < 2) 00280 return; 00281 00282 unsigned num1 = new_first - first, num2 = last - new_first; 00283 if (num1 >= num2) { 00284 It a = first, b = new_first; 00285 while (b != last) { 00286 swapit(*a, *b); 00287 ++a; ++b; 00288 } 00289 if (num1 > num2) { 00290 first += num2; 00291 num = num1; 00292 goto again; 00293 } 00294 } else { 00295 It a = new_first, b = last; 00296 do { 00297 --a; --b; 00298 swapit(*a, *b); 00299 } while (a != first); 00300 last -= num1; 00301 num = num2; 00302 goto again; 00303 } 00304 } 00305 00306 00307 // Collection of `construct on first use' wrappers for safely avoiding 00308 // internal object replication without running into the `static 00309 // initialization order fiasco'. This chest of numbers helps speed up 00310 // the library but should not be used outside it since it is 00311 // potentially confusing. 00312 00313 class ex; 00314 00315 extern const numeric *_num_120_p; 00316 extern const ex _ex_120; 00317 extern const numeric *_num_60_p; 00318 extern const ex _ex_60; 00319 extern const numeric *_num_48_p; 00320 extern const ex _ex_48; 00321 extern const numeric *_num_30_p; 00322 extern const ex _ex_30; 00323 extern const numeric *_num_25_p; 00324 extern const ex _ex_25; 00325 extern const numeric *_num_24_p; 00326 extern const ex _ex_24; 00327 extern const numeric *_num_20_p; 00328 extern const ex _ex_20; 00329 extern const numeric *_num_18_p; 00330 extern const ex _ex_18; 00331 extern const numeric *_num_15_p; 00332 extern const ex _ex_15; 00333 extern const numeric *_num_12_p; 00334 extern const ex _ex_12; 00335 extern const numeric *_num_11_p; 00336 extern const ex _ex_11; 00337 extern const numeric *_num_10_p; 00338 extern const ex _ex_10; 00339 extern const numeric *_num_9_p; 00340 extern const ex _ex_9; 00341 extern const numeric *_num_8_p; 00342 extern const ex _ex_8; 00343 extern const numeric *_num_7_p; 00344 extern const ex _ex_7; 00345 extern const numeric *_num_6_p; 00346 extern const ex _ex_6; 00347 extern const numeric *_num_5_p; 00348 extern const ex _ex_5; 00349 extern const numeric *_num_4_p; 00350 extern const ex _ex_4; 00351 extern const numeric *_num_3_p; 00352 extern const ex _ex_3; 00353 extern const numeric *_num_2_p; 00354 extern const ex _ex_2; 00355 extern const numeric *_num_1_p; 00356 extern const ex _ex_1; 00357 extern const numeric *_num_1_2_p; 00358 extern const ex _ex_1_2; 00359 extern const numeric *_num_1_3_p; 00360 extern const ex _ex_1_3; 00361 extern const numeric *_num_1_4_p; 00362 extern const ex _ex_1_4; 00363 extern const numeric *_num0_p; 00364 extern const basic *_num0_bp; 00365 extern const ex _ex0; 00366 extern const numeric *_num1_4_p; 00367 extern const ex _ex1_4; 00368 extern const numeric *_num1_3_p; 00369 extern const ex _ex1_3; 00370 extern const numeric *_num1_2_p; 00371 extern const ex _ex1_2; 00372 extern const numeric *_num1_p; 00373 extern const ex _ex1; 00374 extern const numeric *_num2_p; 00375 extern const ex _ex2; 00376 extern const numeric *_num3_p; 00377 extern const ex _ex3; 00378 extern const numeric *_num4_p; 00379 extern const ex _ex4; 00380 extern const numeric *_num5_p; 00381 extern const ex _ex5; 00382 extern const numeric *_num6_p; 00383 extern const ex _ex6; 00384 extern const numeric *_num7_p; 00385 extern const ex _ex7; 00386 extern const numeric *_num8_p; 00387 extern const ex _ex8; 00388 extern const numeric *_num9_p; 00389 extern const ex _ex9; 00390 extern const numeric *_num10_p; 00391 extern const ex _ex10; 00392 extern const numeric *_num11_p; 00393 extern const ex _ex11; 00394 extern const numeric *_num12_p; 00395 extern const ex _ex12; 00396 extern const numeric *_num15_p; 00397 extern const ex _ex15; 00398 extern const numeric *_num18_p; 00399 extern const ex _ex18; 00400 extern const numeric *_num20_p; 00401 extern const ex _ex20; 00402 extern const numeric *_num24_p; 00403 extern const ex _ex24; 00404 extern const numeric *_num25_p; 00405 extern const ex _ex25; 00406 extern const numeric *_num30_p; 00407 extern const ex _ex30; 00408 extern const numeric *_num48_p; 00409 extern const ex _ex48; 00410 extern const numeric *_num60_p; 00411 extern const ex _ex60; 00412 extern const numeric *_num120_p; 00413 extern const ex _ex120; 00414 00415 00416 // Helper macros for class implementations (mostly useful for trivial classes) 00417 00418 #define DEFAULT_CTOR(classname) \ 00419 classname::classname() { setflag(status_flags::evaluated | status_flags::expanded); } 00420 00421 #define DEFAULT_COMPARE(classname) \ 00422 int classname::compare_same_type(const basic & other) const \ 00423 { \ 00424 /* by default, the objects are always identical */ \ 00425 return 0; \ 00426 } 00427 00428 #define DEFAULT_PRINT(classname, text) \ 00429 void classname::do_print(const print_context & c, unsigned level) const \ 00430 { \ 00431 c.s << text; \ 00432 } 00433 00434 #define DEFAULT_PRINT_LATEX(classname, text, latex) \ 00435 DEFAULT_PRINT(classname, text) \ 00436 void classname::do_print_latex(const print_latex & c, unsigned level) const \ 00437 { \ 00438 c.s << latex; \ 00439 } 00440 00441 } // namespace GiNaC 00442 00443 #endif // ndef GINAC_UTILS_H