util.h

   1 #ifndef UTIL_HEADER_
   2 #define UTIL_HEADER_
   3
   4 #include "headers.h"
   5 #include "debug.h"
   6
   7 /// \file
   8
   9 /** Field containing 2^i on i-th position, defined in modules.cpp */
  10 extern const int powers[31];
  11
  12 /** Helper template function computing the square of a number */
  13 template<typename T> inline T sqr(T i)
  14         { return i*i; }
  15 /** Helper template function computing the cube of a number */
  16 template<typename T> inline T cube(T i)
  17         { return i*i*i; }
  18
  19 /** Returns i*2^bits */
  20 template<typename T> inline T lShift(T i,T bits)
  21         { ASSERT(bits>=0); return i<<bits; }
  22
  23 /** Returns i/2^bits */
  24 template<typename T> inline T rShift(T i,T bits)
  25         { ASSERT(bits>=0 && i>=0); return i>>bits; }
  26
  27 /** Returns ceil(log2(i)) */
  28 inline int log2ceil(int i) {
  29         ASSERT(i>0);
  30         --i;
  31         int result= 0;
  32         while (i) {
  33                 i/= 2;
  34                 ++result;
  35         }
  36         return result;
  37 }
  38
  39 /** A wrapper around isnan() because of compiler support */
  40 template<class T> inline bool isNaN(T num) {
  41 #ifndef __ICC
  42         return isnan(num);
  43 #else
  44         return num!=num;
  45 #endif
  46 }
  47
  48 /** How many short intervals (shifted by density) can fit into a long interval (discrete) */
  49 inline int getCountForDensity(int longLength,int density,int shortLength)
  50         { return (longLength-shortLength)/density +1; }
  51
  52 /** The same as above, but in 2D for squares fitting into a rectangle */
  53 inline int getCountForDensity2D(int width,int height,int density,int sideSize) {
  54         return getCountForDensity(width,density,sideSize)
  55         *       getCountForDensity(height,density,sideSize);
  56 }
  57
  58 /** General bounds-checking template routine - returns max(low,min(value,high)) */
  59 template<class T> inline T checkBoundsFunc(T low,T value,T high) {
  60         if (value<low)
  61                 return low;
  62         if (value>high)
  63                 return high;
  64         return value;
  65 }
  66
  67 /** Struct for conversion between 0-1 Real and 0-(2^power-1) integer */
  68 template<int power,class R> struct Float2int {
  69         static R convert(int i)
  70                 { return std::ldexp( i+R(0.5), -power ); }
  71
  72         static int convert(R r)
  73                 { return (int)trunc(std::ldexp( r, power )); }
  74         static int convertCheck(R r)
  75                 { return checkBoundsFunc( 0, convert(r), powers[power]-1 ); }
  76 };
  77
  78 /** Counts the number of '\n' characters in a C-string */
  79 inline int countEOLs(const char *s) {
  80         int result= 0;
  81         for (; *s; ++s)
  82                 if (*s=='\n')
  83                         ++result;
  84         return result;
  85 }
  86
  87 /** Converts any type to std::string via std::stringstream */
  88 template<class T> inline std::string toString(const T &what) {
  89         std::stringstream stream;
  90         stream << what;
  91         std::string result;
  92         stream >> result;
  93         return result;
  94 }
  95
  96 /** Type convertor - NonConstType<T>::Result is a non-const variant of T or T itself if N/A */
  97 template<class T> struct NonConstType                   { typedef T Result; };
  98 template<class T> struct NonConstType<const T>  { typedef T Result; };
  99
 100 /** Automatic version of const_cast for pointers */
 101 template <class T> inline T* constCast(const T* toCast) { return const_cast<T*>(toCast); }
 102 /** Automatic version of const_cast for references */
 103 template <class T> inline T& constCast(const T& toCast) { return const_cast<T&>(toCast); }
 104
 105 /** Checking a condition - throws std::exception if false */
 106 inline void checkThrow(bool check) { if (!check) throw std::exception(); }
 107
 108
 109 /** Template object for automated deletion of pointers (useful in for_each) */
 110 struct SingleDeleter {
 111         template <class T> void operator()(T *toDelete) const { delete toDelete; }
 112 };
 113 /** Template object for automated deletion of field pointers (useful in for_each) */
 114 struct MultiDeleter {
 115         template <class T> void operator()(T *toDelete) const { delete[] toDelete; }
 116 };
 117
 118
 119 /** Deletes all pointers in a container (it has to support \c begin and \c end methods) */
 120 template<class C> void clearContainer(const C &container)
 121         { for_each( container.begin(), container.end(), SingleDeleter() ); }
 122
 123
 124 template <class T,int bulkKb=64>
 125 class BulkAllocator {
 126         enum { bulkCount=(bulkKb*1024)/sizeof(T) };
 127
 128         std::vector<T*> pools;
 129         PtrInt nextIndex;
 130
 131 public:
 132         BulkAllocator()
 133         : nextIndex(bulkCount) {}
 134         BulkAllocator(const BulkAllocator &DEBUG_ONLY(copy))
 135                 { nextIndex=bulkCount; ASSERT(copy.pools.empty()); }
 136         ~BulkAllocator()
 137                 { for_each( pools.begin(), pools.end(), MultiDeleter() ); }
 138
 139         T* make() {
 140         //      check for errors
 141                 ASSERT(nextIndex<=bulkCount);
 142         //      allocate a new bulk if needed
 143                 if (nextIndex==bulkCount) {
 144                         nextIndex= 0;
 145                         pools.push_back( new T[bulkCount] );
 146                 }
 147                 return & (pools.back()[nextIndex++]);
 148         }
 149         T* makeField(PtrInt count) {
 150         //      check for errors
 151                 ASSERT(nextIndex<=bulkCount);
 152
 153                 if (count>bulkCount/2) {
 154                         T *result=new T[count];
 155                         if (pools.empty())
 156                                 pools.push_back(result);
 157                         else {
 158                                 pools.push_back(pools.back());
 159                                 *(pools.end()-2)=result;
 160                         }
 161                         return result;
 162                 }
 163
 164                 if (nextIndex+count>bulkCount) {
 165                 //      some space will be wasted
 166                         nextIndex=0;
 167                         pools.push_back(new T[bulkCount]);
 168                 }
 169                 T *result=&pools.back()[nextIndex];
 170                 nextIndex+=count;
 171                 return result;
 172         }
 173 }; // BulkAllocator class
 174
 175 /** Structure providing support for progress update and interruption (used for encoding) */
 176 struct UpdateInfo {
 177         typedef void (*IncInt)(int increment); ///< Type for used functions -> more readable code
 178
 179         static void emptyFunction(int) {}               ///< does nothing, default for IncInt functions
 180         static const bool noTerminate= false;   ///< default for #terminate, defined in modules.cpp
 181         static const UpdateInfo none;                   ///< empty UpdateInfo instance, in modules.cpp
 182
 183         volatile const bool *terminate; ///< true if the action should be terminated
 184         IncInt incMaxProgress                   ///  function for increasing the maximum progress (100%)
 185         , incProgress;                                  ///< function for increasing the current progress
 186
 187         /** Initializes the structure from supplied parametres */
 188         UpdateInfo( const bool &terminate_, IncInt incMaxProgress_, IncInt incProgress_ )
 189         : terminate(&terminate_), incMaxProgress(incMaxProgress_), incProgress(incProgress_)
 190                 { ASSERT(isValid()); }
 191
 192         bool isValid() const { return terminate && incMaxProgress && incProgress; }
 193 };
 194
 195 #endif // UTIL_HEADER_