Sierra Toolkit  Version of the Day
algorithm_rdestl.h
1 #ifndef RDESTL_ALGORITHM_H
2 #define RDESTL_ALGORITHM_H
3 
4 #include <stk_util/util/int_to_type_rdestl.h>
5 #include <stk_util/util/iterator_rdestl.h>
6 #include <stk_util/util/type_traits_rdestl.h>
7 #include <stk_util/util/utility_rdestl.h>
8 
9 namespace rde
10 {
11 
12 //-----------------------------------------------------------------------------
13 template<typename T> RDE_FORCEINLINE
14 void copy_construct(T* mem, const T& orig)
15 {
16  //new (mem) T(orig);
17  internal::copy_construct(mem, orig, int_to_type<has_trivial_copy<T>::value>());
18 }
19 
20 //-----------------------------------------------------------------------------
21 template<typename T> RDE_FORCEINLINE
22 void construct(T* mem)
23 {
24  internal::construct(mem, int_to_type<has_trivial_constructor<T>::value>());
25 }
26 
27 //-----------------------------------------------------------------------------
28 template<typename T> RDE_FORCEINLINE
29 void destruct(T* mem)
30 {
31  internal::destruct(mem, int_to_type<has_trivial_destructor<T>::value>());
32 }
33 
34 //-----------------------------------------------------------------------------
35 template<typename T>
36 void copy_n(const T* first, size_t n, T* result)
37 {
38  internal::copy_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
39 }
40 
41 //-----------------------------------------------------------------------------
42 template<typename T>
43 void copy(const T* first, const T* last, T* result)
44 {
45  internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
46 }
47 
48 //-----------------------------------------------------------------------------
49 template<typename T>
50 void copy_construct_n(T* first, size_t n, T* result)
51 {
52  internal::copy_construct_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
53 }
54 //-----------------------------------------------------------------------------
55 template<typename T>
56 void move_n(const T* from, size_t n, T* result)
57 {
58  RDE_ASSERT(from != result || n == 0);
59  // Overlap?
60  if (result > from && result < from + n)
61  {
62  internal::move_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
63  }
64  else
65  {
66  internal::copy_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
67  }
68 }
69 
70 //-----------------------------------------------------------------------------
71 template<typename T>
72 void move(const T* first, const T* last, T* result)
73 {
74  RDE_ASSERT(first != result || first == last);
75  if (result > first && result < last)
76  {
77  internal::move(first, last, result, int_to_type<has_trivial_copy<T>::value>());
78  }
79  else
80  {
81  internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
82  }
83 }
84 
85 //-----------------------------------------------------------------------------
86 template<typename T>
87 void construct_n(T* first, size_t n)
88 {
89  internal::construct_n(first, n, int_to_type<has_trivial_constructor<T>::value>());
90 }
91 
92 //-----------------------------------------------------------------------------
93 template<typename T>
94 void destruct_n(T* first, size_t n)
95 {
96  internal::destruct_n(first, n, int_to_type<has_trivial_destructor<T>::value>());
97 }
98 
99 //-----------------------------------------------------------------------------
100 template<typename T> RDE_FORCEINLINE
101 void fill_n(T* first, size_t n, const T& val)
102 {
103  //for (size_t i = 0; i < n; ++i)
104  // first[i] = val;
105  // Loop unrolling with Duff's Device.
106  T* last = first + n;
107  switch (n & 0x7)
108  {
109  case 0:
110  while (first != last)
111  {
112  *first = val; ++first;
113  case 7: *first = val; ++first;
114  case 6: *first = val; ++first;
115  case 5: *first = val; ++first;
116  case 4: *first = val; ++first;
117  case 3: *first = val; ++first;
118  case 2: *first = val; ++first;
119  case 1: *first = val; ++first;
120  }
121  }
122 }
123 
124 //-----------------------------------------------------------------------------
125 template<typename TIter, typename TDist> inline
126 void distance(TIter first, TIter last, TDist& dist)
127 {
128  internal::distance(first, last, dist, typename iterator_traits<TIter>::iterator_category());
129 }
130 
131 //-----------------------------------------------------------------------------
132 template<typename TIter, typename TDist> inline
133 void advance(TIter& iter, TDist off)
134 {
135  internal::advance(iter, off, typename iterator_traits<TIter>::iterator_category());
136 }
137 
138 //-----------------------------------------------------------------------------
139 template<class TIter, typename T, class TPred> inline
140 TIter lower_bound(TIter first, TIter last, const T& val, const TPred& pred)
141 {
142  internal::test_ordering(first, last, pred);
143  int dist(0);
144  distance(first, last, dist);
145  while (dist > 0)
146  {
147  const int halfDist = dist >> 1;
148  TIter mid = first;
149  advance(mid, halfDist);
150  if (internal::debug_pred(pred, *mid, val))
151  first = ++mid, dist -= halfDist + 1;
152  else
153  dist = halfDist;
154  }
155  return first;
156 }
157 
158 //-----------------------------------------------------------------------------
159 template<class TIter, typename T, class TPred> inline
160 TIter upper_bound(TIter first, TIter last, const T& val, const TPred& pred)
161 {
162  internal::test_ordering(first, last, pred);
163  int dist(0);
164  distance(first, last, dist);
165  while (dist > 0)
166  {
167  const int halfDist = dist >> 1;
168  TIter mid = first;
169  advance(mid, halfDist);
170  if (!internal::debug_pred(pred, val, *mid))
171  first = ++mid, dist -= halfDist + 1;
172  else
173  dist = halfDist;
174  }
175  return first;
176 }
177 
178 //-----------------------------------------------------------------------------
179 template<class TIter, typename T>
180 TIter find(TIter first, TIter last, const T& val)
181 {
182  while (first != last)
183  {
184  if ((*first) == val)
185  return first;
186  ++first;
187  }
188  return last;
189 }
190 
191 //-----------------------------------------------------------------------------
192 template<class TIter, typename T, class TPred>
193 TIter find_if(TIter first, TIter last, const T& val, const TPred& pred)
194 {
195  while (first != last)
196  {
197  if (pred(*first, val))
198  return first;
199  ++first;
200  }
201  return last;
202 }
203 
204 //-----------------------------------------------------------------------------
205 template<class TIter, typename T>
206 void accumulate(TIter first, TIter last, T& result)
207 {
208  while (first != last)
209  {
210  result += *first;
211  ++first;
212  }
213 }
214 
215 //-----------------------------------------------------------------------------
216 template<typename T>
217 T abs(const T& t)
218 {
219  return t >= T(0) ? t : -t;
220 }
221 // No branches, Hacker's Delight way.
222 RDE_FORCEINLINE int abs(int x)
223 {
224  const int y = x >> 31;
225  return (x ^ y) - y;
226 }
227 RDE_FORCEINLINE short abs(short x)
228 {
229  const short y = x >> 15;
230  return (x ^ y) - y;
231 }
232 
233 //-----------------------------------------------------------------------------
234 template<typename T> inline
235 T max(const T& x, const T& y)
236 {
237  return x > y ? x : y;
238 }
239 
240 //-----------------------------------------------------------------------------
241 template<typename T> inline
242 T min(const T& x, const T& y)
243 {
244  return x < y ? x : y;
245 }
246 // @TODO: determine if it REALLY is quicker than version with branches.
247 /*RDE_FORCEINLINE float min(float x, float y)
248 {
249  float result;
250  __asm
251  {
252  fld [x]
253  fld [y]
254  fcomi st(0), st(1)
255  fcmovnb st(0), st(1)
256  fstp [result]
257  fcomp
258  }
259  return result;
260 }*/
261 
262 //-----------------------------------------------------------------------------
263 template<typename TAssignable>
264 void swap(TAssignable& a, TAssignable& b)
265 {
266  TAssignable tmp(a);
267  a = b;
268  b = tmp;
269 }
270 
271 } // namespace rde
272 //-----------------------------------------------------------------------------
273 #endif // #ifndef RDESTL_ALGORITHM_H
InputIterator find_if(InputIterator first, InputIterator last, Predicate predicate)
OutputIterator fill_n(OutputIterator first, Size n, const T &value)
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
Definition: Part.cpp:22