CLRX  1
An unofficial OpenCL extensions designed for Radeon GPUs
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
Containers.h
Go to the documentation of this file.
1 /*
2  * CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3  * Copyright (C) 2014-2016 Mateusz Szpakowski
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18  */
23 #ifndef __CLRX_CONTAINERS_H__
24 #define __CLRX_CONTAINERS_H__
25 
26 #include <CLRX/Config.h>
27 #include <cstddef>
28 #include <iterator>
29 #include <algorithm>
30 #include <initializer_list>
31 
33 namespace CLRX
34 {
35 
37 template<typename T>
38 class Array
39 {
40 public:
41  typedef T* iterator;
42  typedef const T* const_iterator;
43  typedef T element_type;
44 private:
45  T* ptr, *ptrEnd;
46 public:
48  Array(): ptr(nullptr), ptrEnd(nullptr)
49  { }
50 
52  explicit Array(size_t N)
53  {
54  ptr = nullptr;
55  if (N != 0)
56  ptr = new T[N];
57  ptrEnd = ptr+N;
58  }
59 
61  template<typename It>
62  Array(It b, It e)
63  try
64  {
65  ptr = nullptr;
66  const size_t N = e-b;
67  if (N != 0)
68  ptr = new T[N];
69  ptrEnd = ptr+N;
70  std::copy(b, e, ptr);
71  }
72  catch(...)
73  {
74  delete[] ptr;
75  throw;
76  }
77 
79  Array(const Array& cp)
80  try
81  {
82  ptr = ptrEnd = nullptr;
83  const size_t N = cp.size();
84  if (N != 0)
85  ptr = new T[N];
86  ptrEnd = ptr+N;
87  std::copy(cp.ptr, cp.ptrEnd, ptr);
88  }
89  catch(...)
90  {
91  delete[] ptr;
92  throw;
93  }
94 
96  Array(Array&& cp) noexcept
97  {
98  ptr = cp.ptr;
99  ptrEnd = cp.ptrEnd;
100  cp.ptr = cp.ptrEnd = nullptr;
101  }
102 
104  Array(std::initializer_list<T> list)
105  try
106  {
107  ptr = nullptr;
108  const size_t N = list.size();
109  if (N != 0)
110  ptr = new T[N];
111  ptrEnd = ptr+N;
112  std::copy(list.begin(), list.end(), ptr);
113  }
114  catch(...)
115  {
116  delete[] ptr;
117  throw;
118  }
119 
122  { delete[] ptr; }
123 
125  Array& operator=(const Array& cp)
126  {
127  if (this == &cp)
128  return *this;
129  assign(cp.begin(), cp.end());
130  return *this;
131  }
133  Array& operator=(Array&& cp) noexcept
134  {
135  if (this == &cp)
136  return *this;
137  delete[] ptr;
138  ptr = cp.ptr;
139  ptrEnd = cp.ptrEnd;
140  cp.ptr = cp.ptrEnd = nullptr;
141  return *this;
142  }
143 
145  Array& operator=(std::initializer_list<T> list)
146  {
147  assign(list.begin(), list.end());
148  return *this;
149  }
150 
152  const T& operator[] (size_t i) const
153  { return ptr[i]; }
155  T& operator[] (size_t i)
156  { return ptr[i]; }
157 
159  bool empty() const
160  { return ptrEnd==ptr; }
161 
163  size_t size() const
164  { return ptrEnd-ptr; }
165 
167  void allocate(size_t N)
168  {
169  if (N == size())
170  return;
171  delete[] ptr;
172  ptr = nullptr;
173  if (N != 0)
174  ptr = new T[N];
175  ptrEnd = ptr + N;
176  }
177 
179  void resize(size_t N)
180  {
181  if (N == size())
182  return;
183  T* newPtr = nullptr;
184  if (N != 0)
185  newPtr = new T[N];
186  try
187  { /* move only if move constructor doesn't throw exceptions */
188  const size_t toMove = std::min(N, size());
189  for (size_t k = 0; k < toMove; k++)
190  newPtr[k] = std::move_if_noexcept(ptr[k]);
191  }
192  catch(...)
193  {
194  delete[] newPtr;
195  throw;
196  }
197  delete[] ptr;
198  ptr = newPtr;
199  ptrEnd = ptr + N;
200  }
201 
203  void clear()
204  {
205  delete[] ptr;
206  ptr = ptrEnd = nullptr;
207  }
208 
210  template<typename It>
211  Array& assign(It b, It e)
212  {
213  const size_t N = e-b;
214  if (N != size())
215  {
216  T* newPtr = nullptr;
217  if (N != 0)
218  newPtr = new T[N];
219  try
220  { std::copy(b, e, newPtr); }
221  catch(...)
222  {
223  delete[] newPtr;
224  throw;
225  }
226  delete[] ptr;
227  ptr = newPtr;
228  ptrEnd = ptr+N;
229  }
230  else // no size changed only copy
231  std::copy(b, e, ptr);
232  return *this;
233  }
234 
236  const T* data() const
237  { return ptr; }
239  T* data()
240  { return ptr; }
241 
243  const T* begin() const
244  { return ptr; }
246  T* begin()
247  { return ptr; }
248 
250  const T* end() const
251  { return ptrEnd; }
253  T* end()
254  { return ptrEnd; }
255 
257  const T& front() const
258  { return *ptr; }
260  T& front()
261  { return *ptr; }
263  const T& back() const
264  { return ptrEnd[-1]; }
266  T& back()
267  { return ptrEnd[-1]; }
268 
270  void swap(Array& array)
271  {
272  std::swap(ptr, array.ptr);
273  std::swap(ptrEnd, array.ptrEnd);
274  }
275 };
276 
278 
284 template<typename Iter>
285 Iter binaryFind(Iter begin, Iter end, const
286  typename std::iterator_traits<Iter>::value_type& v);
287 
289 
296 template<typename Iter, typename Comp =
297  std::less<typename std::iterator_traits<Iter>::value_type> >
298 Iter binaryFind(Iter begin, Iter end, const
299  typename std::iterator_traits<Iter>::value_type& v, Comp comp);
300 
302 
308 template<typename Iter>
309 Iter binaryMapFind(Iter begin, Iter end, const
310  typename std::iterator_traits<Iter>::value_type::first_type& k);
311 
313 
320 template<typename Iter, typename Comp =
321  std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
322 Iter binaryMapFind(Iter begin, Iter end, const
323  typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp);
324 
326 
330 template<typename Iter>
331 void mapSort(Iter begin, Iter end);
332 
334 
338 template<typename Iter, typename Comp =
339  std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
340 void mapSort(Iter begin, Iter end, Comp comp);
341 
343 
349 template<typename Iter>
350 Iter binaryFind(Iter begin, Iter end,
351  const typename std::iterator_traits<Iter>::value_type& v)
352 {
353  auto it = std::lower_bound(begin, end, v);
354  if (it == end || v < *it)
355  return end;
356  return it;
357 }
358 
360 
367 template<typename Iter, typename Comp>
368 Iter binaryFind(Iter begin, Iter end,
369  const typename std::iterator_traits<Iter>::value_type& v, Comp comp)
370 {
371  auto it = std::lower_bound(begin, end, v, comp);
372  if (it == end || comp(v, *it))
373  return end;
374  return it;
375 }
376 
378 template<typename Iter>
379 Iter binaryMapFind(Iter begin, Iter end, const
380  typename std::iterator_traits<Iter>::value_type::first_type& k)
381 {
382  typedef typename std::iterator_traits<Iter>::value_type::first_type K;
383  typedef typename std::iterator_traits<Iter>::value_type::second_type V;
384  auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
385  [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
386  return e1.first < e2.first; });
387  if (it == end || k < it->first)
388  return end;
389  return it;
390 }
391 
393 template<typename Iter, typename Comp>
394 Iter binaryMapFind(Iter begin, Iter end, const
395  typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp)
396 {
397  typedef typename std::iterator_traits<Iter>::value_type::first_type K;
398  typedef typename std::iterator_traits<Iter>::value_type::second_type V;
399  auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
400  [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
401  return comp(e1.first, e2.first); });
402  if (it == end || comp(k, it->first))
403  return end;
404  return it;
405 }
406 
408 
412 template<typename Iter>
413 void mapSort(Iter begin, Iter end)
414 {
415  typedef typename std::iterator_traits<Iter>::value_type::first_type K;
416  typedef typename std::iterator_traits<Iter>::value_type::second_type V;
417  std::sort(begin, end, [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
418  return e1.first < e2.first; });
419 }
420 
422 
427 template<typename Iter, typename Comp>
428 void mapSort(Iter begin, Iter end, Comp comp)
429 {
430  typedef typename std::iterator_traits<Iter>::value_type::first_type K;
431  typedef typename std::iterator_traits<Iter>::value_type::second_type V;
432  std::sort(begin, end, [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
433  return comp(e1.first, e2.first); });
434 }
435 
436 };
437 
438 namespace std
439 {
440 
442 template<typename T>
443 void swap(CLRX::Array<T>& a1, CLRX::Array<T>& a2)
444 { a1.swap(a2); }
445 
446 }
447 
448 #endif
const T * begin() const
get iterator to first element
Definition: Containers.h:243
T element_type
element type
Definition: Containers.h:43
Iter binaryMapFind(Iter begin, Iter end, const typename std::iterator_traits< Iter >::value_type::first_type &k)
binary find helper for array-map
Definition: Containers.h:379
void swap(Array &array)
swap two arrays
Definition: Containers.h:270
void allocate(size_t N)
only allocating space without keeping previous content
Definition: Containers.h:167
const T & operator[](size_t i) const
operator of indexing
Definition: Containers.h:152
const T & front() const
get first element
Definition: Containers.h:257
an array class
Definition: Containers.h:38
void resize(size_t N)
resize space with keeping old content
Definition: Containers.h:179
const T * const_iterator
type of constant iterator
Definition: Containers.h:42
Array()
empty constructor
Definition: Containers.h:48
Array(size_t N)
construct array of N elements
Definition: Containers.h:52
Array & operator=(Array &&cp) noexcept
move assignment
Definition: Containers.h:133
T & back()
get last element
Definition: Containers.h:266
Array & operator=(std::initializer_list< T > list)
assignment from initializer list
Definition: Containers.h:145
Array(std::initializer_list< T > list)
constructor with initializer list
Definition: Containers.h:104
T * end()
get iterator to after last element
Definition: Containers.h:253
Array & operator=(const Array &cp)
copy assignment
Definition: Containers.h:125
T * data()
get data
Definition: Containers.h:239
T & front()
get first element
Definition: Containers.h:260
void mapSort(Iter begin, Iter end)
map range of iterators
Definition: Containers.h:413
Array & assign(It b, It e)
assign from range of iterators
Definition: Containers.h:211
T * iterator
type of iterator
Definition: Containers.h:41
~Array()
destructor
Definition: Containers.h:121
Array(It b, It e)
construct array of elements in begin and end
Definition: Containers.h:62
T * begin()
get iterator to first element
Definition: Containers.h:246
Array(const Array &cp)
copy constructor
Definition: Containers.h:79
Iter binaryFind(Iter begin, Iter end, const typename std::iterator_traits< Iter >::value_type &v)
binary find helper
Definition: Containers.h:350
size_t size() const
returns number of elements
Definition: Containers.h:163
const T * data() const
get data
Definition: Containers.h:236
void clear()
clear array
Definition: Containers.h:203
bool empty() const
returns true if empty
Definition: Containers.h:159
Array(Array &&cp) noexcept
move constructor
Definition: Containers.h:96
const T & back() const
get last element
Definition: Containers.h:263
const T * end() const
get iterator to after last element
Definition: Containers.h:250