ginac/utils.h

   1 /** @file utils.h
   2  *
   3  *  Interface to several small and furry utilities. */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  */
  22
  23 #ifndef __GINAC_UTILS_H__
  24 #define __GINAC_UTILS_H__
  25
  26 #include <strstream>
  27 #include <string>
  28 #include "config.h"
  29 #include "assertion.h"
  30
  31 #ifndef NO_GINAC_NAMESPACE
  32 namespace GiNaC {
  33 #endif // ndef NO_GINAC_NAMESPACE
  34
  35 template<class T>
  36 string ToString(T const & t)
  37 {
  38     char buf[256];
  39     ostrstream(buf,sizeof(buf)) << t << ends;
  40     return buf;
  41 }
  42
  43 unsigned log2(unsigned n);
  44
  45 int compare_pointers(void const * a, void const * b);
  46
  47 /** Rotate lower 31 bits of unsigned value by one bit to the left
  48  *  (upper bits get cleared). */
  49 inline unsigned rotate_left_31(unsigned n)
  50 {
  51     // clear highest bit and shift 1 bit to the left
  52     n=(n & 0x7FFFFFFFU) << 1;
  53
  54     // overflow? clear highest bit and set lowest bit
  55     if (n & 0x80000000U) {
  56         n=(n & 0x7FFFFFFFU) | 0x00000001U;
  57     }
  58     GINAC_ASSERT(n<0x80000000U);
  59
  60     return n;
  61 }
  62
  63 /** Golden ratio hash function. */
  64 inline unsigned golden_ratio_hash(unsigned n)
  65 {
  66         // This function requires arithmetic with at least 64 significant bits
  67 #if SIZEOF_LONG_DOUBLE > 8
  68         // If "long double" is bigger than 64 bits, we assume that the mantissa
  69         // has at least 64 bits. This is not guaranteed but it's a good guess.
  70     const static long double golden_ratio = .618033988749894848204586834370;
  71     long double m = golden_ratio * n;
  72     return unsigned((m - int(m)) * 0x80000000);
  73 #elif SIZEOF_LONG >= 8
  74         // "long" has 64 bits, so we prefer it because it might be more efficient
  75         // than "long long"
  76         unsigned long l = n * 0x4f1bbcddL;
  77         return (l & 0x7fffffffU) ^ (l >> 32);
  78 #elif SIZEOF_LONG_LONG >= 8
  79         // This requires ´long long´ (or an equivalent 64 bit type)---which is,
  80     // unfortunately, not ANSI-compliant:
  81         unsigned long long l = n * 0x4f1bbcddLL;
  82         return (l & 0x7fffffffU) ^ (l >> 32);
  83 #else
  84 #error "No 64 bit data type. You lose."
  85 #endif
  86 }
  87
  88 // modified from stl_algo.h: always do com(*first1,*first2) instead of comp(*first2,*first1)
  89 template <class InputIterator1, class InputIterator2, class OutputIterator,
  90           class Compare>
  91 OutputIterator mymerge(InputIterator1 first1, InputIterator1 last1,
  92                        InputIterator2 first2, InputIterator2 last2,
  93                        OutputIterator result, Compare comp) {
  94   while (first1 != last1 && first2 != last2) {
  95     if (comp(*first1, *first2)) {
  96       *result = *first1;
  97       ++first1;
  98     }
  99     else {
 100       *result = *first2;
 101       ++first2;
 102     }
 103     ++result;
 104   }
 105   return copy(first2, last2, copy(first1, last1, result));
 106 }
 107
 108 // like merge(), but three lists with *last2<*first3
 109 template <class InputIterator1, class InputIterator2, class InputIterator3,
 110           class OutputIterator, class Compare>
 111 OutputIterator mymerge3(InputIterator1 first1, InputIterator1 last1,
 112                         InputIterator2 first2, InputIterator2 last2,
 113                         InputIterator3 first3, InputIterator3 last3,
 114                         OutputIterator result, Compare comp) {
 115   while (first1 != last1 && first2 != last2) {
 116     if (comp(*first1, *first2)) {
 117       *result = *first1;
 118       ++first1;
 119     }
 120     else {
 121       *result = *first2;
 122       ++first2;
 123     }
 124     ++result;
 125   }
 126
 127   if (first1==last1) {
 128     // list1 empty, copy rest of list2, then list3
 129     return copy(first3, last3, copy(first2, last2, result));
 130   } else {
 131     // list2 empty, merge rest of list1 with list3
 132     return mymerge(first1,last1,first3,last3,result,comp);
 133   }
 134 }
 135
 136 #ifndef NO_GINAC_NAMESPACE
 137 } // namespace GiNaC
 138 #endif // ndef NO_GINAC_NAMESPACE
 139
 140 #endif // ndef __GINAC_UTILS_H__