7 #if ((defined (__GNUC__) && (__GNUC__ > 2)) && !defined(__APPLE__)) 8 #include <ext/algorithm> 9 #if __cplusplus <= 199711L 12 using __gnu_cxx::copy_n;
34 inline void copy(
const T& a, T* out,
int n)
36 std::fill(out,out+n,a);
40 inline void copy(
const T* a, T* out,
int n)
42 #if defined(__APPLE__) 47 #endif //defined(__APPLE__) 50 template <
typename T,
typename ftype>
51 inline void foreach(T* a, ftype f,
int n)
53 std::for_each(a,a+n,f);
57 inline void reverse (T *a,
int n)
63 template <
typename t1,
typename t2,
typename ftype>
64 inline void transform(
const t1* a, t2* out, ftype f,
int n)
66 std::transform(a,a+n,out,f);
69 template <
typename t1,
typename t2,
typename t3,
typename ftype>
70 inline void binary_transform(
const t1* a,
const t2* b, t3* out, ftype f,
int n)
72 std::transform(a,a+n,b,out,f);
76 inline void add(
const T* a,
const T* b, T* out,
int n)
78 binary_transform(a,b,out,std::plus<T>(),n);
82 inline void sub(
const T* a,
const T* b, T* out,
int n)
84 binary_transform(a,b,out,std::minus<T>(),n);
88 inline void mul(
const T* a,
const T* b, T* out,
int n)
90 binary_transform(a,b,out,std::multiplies<T>(),n);
94 inline void div(
const T* a,
const T* b, T* out,
int n)
96 binary_transform(a,b,out,std::divides<T>(),n);
100 template <
typename T>
103 assert(n < S.size());
104 size_t i=rand()%S.size();
109 for(i=0;i<S.size();i++) {
110 if(S[i] < m) S1.push_back(S[i]);
111 else if(m < S[i]) S2.push_back(S[i]);
114 else if(S.size()-S2.size()>=n)
return m;
115 else return nth_element(S2,n-(S.size()-S2.size()));
119 template <
typename T,
typename fless>
120 inline T
nth_element (
const std::vector<T>& S,
size_t n, fless less)
122 assert(n < S.size());
123 size_t i=rand()%S.size();
128 for(i=0;i<S.size();i++) {
129 if(less(S[i],m)) S1.push_back(S[i]);
130 else if(less(m,S[i])) S2.push_back(S[i]);
133 else if(S.size()-S2.size()>=n)
return m;
134 else return nth_element(S2,n-(S.size()-S2.size()),less);
137 template <
typename T>
138 inline bool is_sorted(T* a,
int n)
141 if(a[i]<a[i-1])
return false;
146 template <
typename T,
typename fless>
147 inline bool is_sorted(T* a,
int n, fless f)
150 if(f(a[i],a[i-1]))
return false;
155 template <
typename T>
156 inline void quicksort(T* a,
int p,
int r)
166 temp=a[j];a[j]=a[i];a[i]=temp;
170 temp=a[p];a[p]=a[i];a[i]=temp;
177 template <
typename T,
typename fless>
178 inline void quicksort(T* a,
int p,
int r,fless f)
188 temp=a[j];a[j]=a[i];a[i]=temp;
192 temp=a[p];a[p]=a[i];a[i]=temp;
194 quicksort(a,p,i-1,f);
195 quicksort(a,i+1,r,f);
199 template <
typename T>
200 inline void sort(T* a,
int n)
205 template <
typename T,
typename fless>
206 inline void sort(T* a,
int n, fless f)
208 quicksort(a,0,n-1,f);
213 inline void concat(std::vector<T>& a,
const std::vector<T>& b)
215 size_t aorig=a.size();
216 a.resize(a.size()+b.size());
217 copy(b.begin(),b.end(),a.begin()+aorig);
T nth_element(const std::vector< T > &S, size_t n, fless less)
returns the nth largest element in the array a
Definition: arrayutils.h:120
Definition: rayprimitives.h:132
void copy(const T &a, T *out, int n)
Definition: arrayutils.h:34
Convenience routines for C arrays and STL vectors.
Definition: arrayutils.h:28
void concat(std::vector< T > &a, const std::vector< T > &b)
Concatenates b onto the end of a.
Definition: arrayutils.h:213