Sierra Toolkit Version of the Day
algorithm_rdestl.h
00001 #ifndef RDESTL_ALGORITHM_H
00002 #define RDESTL_ALGORITHM_H
00003 
00004 #include <stk_util/util/int_to_type_rdestl.h>
00005 #include <stk_util/util/iterator_rdestl.h>
00006 #include <stk_util/util/type_traits_rdestl.h>
00007 #include <stk_util/util/utility_rdestl.h>
00008 
00009 namespace rde
00010 {
00011 
00012 //-----------------------------------------------------------------------------
00013 template<typename T> RDE_FORCEINLINE
00014 void copy_construct(T* mem, const T& orig)
00015 {
00016   //new (mem) T(orig);
00017   internal::copy_construct(mem, orig, int_to_type<has_trivial_copy<T>::value>());
00018 }
00019 
00020 //-----------------------------------------------------------------------------
00021 template<typename T> RDE_FORCEINLINE
00022 void construct(T* mem)
00023 {
00024   internal::construct(mem, int_to_type<has_trivial_constructor<T>::value>());
00025 }
00026 
00027 //-----------------------------------------------------------------------------
00028 template<typename T> RDE_FORCEINLINE
00029 void destruct(T* mem)
00030 {
00031   internal::destruct(mem, int_to_type<has_trivial_destructor<T>::value>());
00032 }
00033 
00034 //-----------------------------------------------------------------------------
00035 template<typename T>
00036 void copy_n(const T* first, size_t n, T* result)
00037 {
00038   internal::copy_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
00039 }
00040 
00041 //-----------------------------------------------------------------------------
00042 template<typename T>
00043 void copy(const T* first, const T* last, T* result)
00044 {
00045   internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
00046 }
00047 
00048 //-----------------------------------------------------------------------------
00049 template<typename T>
00050 void copy_construct_n(T* first, size_t n, T* result)
00051 {
00052   internal::copy_construct_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
00053 }
00054 //-----------------------------------------------------------------------------
00055 template<typename T>
00056 void move_n(const T* from, size_t n, T* result)
00057 {
00058   RDE_ASSERT(from != result || n == 0);
00059   // Overlap?
00060   if (result > from && result < from + n)
00061   {
00062     internal::move_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
00063   }
00064   else
00065   {
00066     internal::copy_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
00067   }
00068 }
00069 
00070 //-----------------------------------------------------------------------------
00071 template<typename T>
00072 void move(const T* first, const T* last, T* result)
00073 {
00074   RDE_ASSERT(first != result || first == last);
00075   if (result > first && result < last)
00076   {
00077     internal::move(first, last, result, int_to_type<has_trivial_copy<T>::value>());
00078   }
00079   else
00080   {
00081     internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
00082   }
00083 }
00084 
00085 //-----------------------------------------------------------------------------
00086 template<typename T>
00087 void construct_n(T* first, size_t n)
00088 {
00089   internal::construct_n(first, n, int_to_type<has_trivial_constructor<T>::value>());
00090 }
00091 
00092 //-----------------------------------------------------------------------------
00093 template<typename T>
00094 void destruct_n(T* first, size_t n)
00095 {
00096   internal::destruct_n(first, n, int_to_type<has_trivial_destructor<T>::value>());
00097 }
00098 
00099 //-----------------------------------------------------------------------------
00100 template<typename T> RDE_FORCEINLINE
00101 void fill_n(T* first, size_t n, const T& val)
00102 {
00103   //for (size_t i = 0; i < n; ++i)
00104   //  first[i] = val;
00105   // Loop unrolling with Duff's Device.
00106   T* last = first + n;
00107   switch (n & 0x7)
00108   {
00109   case 0:
00110     while (first != last)
00111     {
00112       *first = val; ++first;
00113   case 7: *first = val; ++first;
00114   case 6: *first = val; ++first;
00115   case 5: *first = val; ++first;
00116   case 4: *first = val; ++first;
00117   case 3: *first = val; ++first;
00118   case 2: *first = val; ++first;
00119   case 1: *first = val; ++first;
00120     }
00121   }
00122 }
00123 
00124 //-----------------------------------------------------------------------------
00125 template<typename TIter, typename TDist> inline
00126 void distance(TIter first, TIter last, TDist& dist)
00127 {
00128   internal::distance(first, last, dist, typename iterator_traits<TIter>::iterator_category());
00129 }
00130 
00131 //-----------------------------------------------------------------------------
00132 template<typename TIter, typename TDist> inline
00133 void advance(TIter& iter, TDist off)
00134 {
00135   internal::advance(iter, off, typename iterator_traits<TIter>::iterator_category());
00136 }
00137 
00138 //-----------------------------------------------------------------------------
00139 template<class TIter, typename T, class TPred> inline
00140 TIter lower_bound(TIter first, TIter last, const T& val, const TPred& pred)
00141 {
00142   internal::test_ordering(first, last, pred);
00143   int dist(0);
00144   distance(first, last, dist);
00145   while (dist > 0)
00146   {
00147     const int halfDist = dist >> 1;
00148     TIter mid = first;
00149     advance(mid, halfDist);
00150     if (internal::debug_pred(pred, *mid, val))
00151       first = ++mid, dist -= halfDist + 1;
00152     else
00153       dist = halfDist;
00154   }
00155   return first;
00156 }
00157 
00158 //-----------------------------------------------------------------------------
00159 template<class TIter, typename T, class TPred> inline
00160 TIter upper_bound(TIter first, TIter last, const T& val, const TPred& pred)
00161 {
00162   internal::test_ordering(first, last, pred);
00163   int dist(0);
00164   distance(first, last, dist);
00165   while (dist > 0)
00166   {
00167     const int halfDist = dist >> 1;
00168     TIter mid = first;
00169     advance(mid, halfDist);
00170     if (!internal::debug_pred(pred, val, *mid))
00171       first = ++mid, dist -= halfDist + 1;
00172     else
00173       dist = halfDist;
00174   }
00175   return first;
00176 }
00177 
00178 //-----------------------------------------------------------------------------
00179 template<class TIter, typename T>
00180 TIter find(TIter first, TIter last, const T& val)
00181 {
00182   while (first != last)
00183   {
00184     if ((*first) == val)
00185       return first;
00186     ++first;
00187   }
00188   return last;
00189 }
00190 
00191 //-----------------------------------------------------------------------------
00192 template<class TIter, typename T, class TPred>
00193 TIter find_if(TIter first, TIter last, const T& val, const TPred& pred)
00194 {
00195   while (first != last)
00196   {
00197     if (pred(*first, val))
00198       return first;
00199     ++first;
00200   }
00201   return last;
00202 }
00203 
00204 //-----------------------------------------------------------------------------
00205 template<class TIter, typename T>
00206 void accumulate(TIter first, TIter last, T& result)
00207 {
00208   while (first != last)
00209   {
00210     result += *first;
00211     ++first;
00212   }
00213 }
00214 
00215 //-----------------------------------------------------------------------------
00216 template<typename T>
00217 T abs(const T& t)
00218 {
00219   return t >= T(0) ? t : -t;
00220 }
00221 // No branches, Hacker's Delight way.
00222 RDE_FORCEINLINE int abs(int x)
00223 {
00224   const int y = x >> 31;
00225   return (x ^ y) - y;
00226 }
00227 RDE_FORCEINLINE short abs(short x)
00228 {
00229   const short y = x >> 15;
00230   return (x ^ y) - y;
00231 }
00232 
00233 //-----------------------------------------------------------------------------
00234 template<typename T> inline
00235 T max(const T& x, const T& y)
00236 {
00237     return x > y ? x : y;
00238 }
00239 
00240 //-----------------------------------------------------------------------------
00241 template<typename T> inline
00242 T min(const T& x, const T& y)
00243 {
00244   return x < y ? x : y;
00245 }
00246 // @TODO: determine if it REALLY is quicker than version with branches.
00247 /*RDE_FORCEINLINE float min(float x, float y)
00248 {
00249   float result;
00250   __asm
00251   {
00252     fld   [x]
00253     fld   [y]
00254     fcomi st(0), st(1)
00255     fcmovnb st(0), st(1)
00256     fstp  [result]
00257     fcomp
00258   }
00259   return result;
00260 }*/
00261 
00262 //-----------------------------------------------------------------------------
00263 template<typename TAssignable>
00264 void swap(TAssignable& a, TAssignable& b)
00265 {
00266   TAssignable tmp(a);
00267   a = b;
00268   b = tmp;
00269 }
00270 
00271 } // namespace rde
00272 //-----------------------------------------------------------------------------
00273 #endif // #ifndef RDESTL_ALGORITHM_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends