source: CLRX/CLRadeonExtender/trunk/CLRX/utils/Containers.h @ 3876

Last change on this file since 3876 was 3876, checked in by matszpk, 17 months ago

CLRadeonExtender: Small doxygen update.

File size: 12.8 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 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 */
19/*! \file Containers.h
20 * \brief containers and other utils for other libraries and programs
21 */
22
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 <vector>
31#include <initializer_list>
32
33/// main namespace
34namespace CLRX
35{
36
37/// an array class
38template<typename T>
39class Array
40{
41public:
42    typedef T* iterator;    ///< type of iterator
43    typedef const T* const_iterator;    ///< type of constant iterator
44    typedef T element_type; ///< element type
45private:
46    T* ptr, *ptrEnd;
47public:
48    /// empty constructor
49    Array(): ptr(nullptr), ptrEnd(nullptr)
50    { }
51   
52    /// construct array of N elements
53    explicit Array(size_t N)
54    {
55        ptr = nullptr;
56        if (N != 0)
57            ptr = new T[N];
58        ptrEnd = ptr+N;
59    }
60   
61    /// construct array of elements in begin and end
62    template<typename It>
63    Array(It b, It e)
64    {
65        try
66        {
67            ptr = nullptr;
68            const size_t N = e-b;
69            if (N != 0)
70                ptr = new T[N];
71            ptrEnd = ptr+N;
72            std::copy(b, e, ptr);
73        }
74        catch(...)
75        {
76            delete[] ptr;
77            throw;
78        }
79    }
80   
81    /// copy constructor
82    Array(const Array& cp)
83    {
84        try
85        {
86            ptr = ptrEnd = nullptr;
87            const size_t N = cp.size();
88            if (N != 0)
89                ptr = new T[N];
90            ptrEnd = ptr+N;
91            std::copy(cp.ptr, cp.ptrEnd, ptr);
92        }
93        catch(...)
94        {
95            delete[] ptr;
96            throw;
97        }
98    }
99   
100    /// move constructor
101    Array(Array&& cp) noexcept
102    {
103        ptr = cp.ptr;
104        ptrEnd = cp.ptrEnd;
105        cp.ptr = cp.ptrEnd = nullptr;
106    }
107   
108    /// constructor with initializer list
109    Array(std::initializer_list<T> list)
110    {
111        try
112        {
113            ptr = nullptr;
114            const size_t N = list.size();
115            if (N != 0)
116                ptr = new T[N];
117            ptrEnd = ptr+N;
118            std::copy(list.begin(), list.end(), ptr);
119        }
120        catch(...)
121        {
122            delete[] ptr;
123            throw;
124        }
125    }
126   
127    /// destructor
128    ~Array()
129    { delete[] ptr; }
130   
131    /// copy assignment
132    Array& operator=(const Array& cp)
133    {
134        if (this == &cp)
135            return *this;
136        assign(cp.begin(), cp.end());
137        return *this;
138    }
139    /// move assignment
140    Array& operator=(Array&& cp) noexcept
141    {
142        if (this == &cp)
143            return *this;
144        delete[] ptr;
145        ptr = cp.ptr;
146        ptrEnd = cp.ptrEnd;
147        cp.ptr = cp.ptrEnd = nullptr;
148        return *this;
149    }
150   
151    /// assignment from initializer list
152    Array& operator=(std::initializer_list<T> list)
153    {
154        assign(list.begin(), list.end());
155        return *this;
156    }
157   
158    /// operator of indexing
159    const T& operator[] (size_t i) const
160    { return ptr[i]; }
161    /// operator of indexing
162    T& operator[] (size_t i)
163    { return ptr[i]; }
164   
165    /// returns true if empty
166    bool empty() const
167    { return ptrEnd==ptr; }
168   
169    /// returns number of elements
170    size_t size() const
171    { return ptrEnd-ptr; }
172   
173    /// only allocating space without keeping previous content
174    void allocate(size_t N)
175    {
176        if (N == size())
177            return;
178        delete[] ptr;
179        ptr = nullptr;
180        if (N != 0)
181            ptr = new T[N];
182        ptrEnd = ptr + N;
183    }
184   
185    /// resize space with keeping old content
186    void resize(size_t N)
187    {
188        if (N == size())
189            return;
190        T* newPtr = nullptr;
191        if (N != 0)
192            newPtr = new T[N];
193        try
194        {
195            /* move only if move constructor doesn't throw exceptions */
196            const size_t toMove = std::min(N, size());
197            for (size_t k = 0; k < toMove; k++)
198                newPtr[k] = std::move_if_noexcept(ptr[k]);
199        }
200        catch(...)
201        {
202            delete[] newPtr;
203            throw;
204        }
205        delete[] ptr;
206        ptr = newPtr;
207        ptrEnd = ptr + N;
208    }
209   
210    /// clear array
211    void clear()
212    {
213        delete[] ptr;
214        ptr = ptrEnd = nullptr;
215    }
216   
217    /// assign from range of iterators
218    template<typename It>
219    Array& assign(It b, It e)
220    {
221        const size_t N = e-b;
222        if (N != size())
223        {
224            T* newPtr = nullptr;
225            if (N != 0)
226                newPtr = new T[N];
227            try
228            { std::copy(b, e, newPtr); }
229            catch(...)
230            {
231                delete[] newPtr;
232                throw;
233            }
234            delete[] ptr;
235            ptr = newPtr;
236            ptrEnd = ptr+N;
237        }
238        else // no size changed only copy
239            std::copy(b, e, ptr);
240        return *this;
241    }
242   
243    /// get data
244    const T* data() const
245    { return ptr; }
246    /// get data
247    T* data()
248    { return ptr; }
249   
250    /// get iterator to first element
251    const T* begin() const
252    { return ptr; }
253    /// get iterator to first element
254    T* begin()
255    { return ptr; }
256   
257    /// get iterator to after last element
258    const T* end() const
259    { return ptrEnd; }
260    /// get iterator to after last element
261    T* end()
262    { return ptrEnd; }
263   
264    /// get first element
265    const T& front() const
266    { return *ptr; }
267    /// get first element
268    T& front()
269    { return *ptr; }
270    /// get last element
271    const T& back() const
272    { return ptrEnd[-1]; }
273    /// get last element
274    T& back()
275    { return ptrEnd[-1]; }
276   
277    /// swap two arrays
278    void swap(Array& array)
279    {
280        std::swap(ptr, array.ptr);
281        std::swap(ptrEnd, array.ptrEnd);
282    }
283};
284
285/// VectorSet
286template<typename T>
287class VectorSet: public std::vector<T>
288{
289public:
290    /// constructor
291    VectorSet()
292    { }
293   
294    /// constructor
295    VectorSet(size_t n) : std::vector<T>(n)
296    { }
297   
298    /// constructor
299    VectorSet(size_t n, const T& v) : std::vector<T>(n, v)
300    { }
301   
302    /// constructor
303    VectorSet(std::initializer_list<T> l): std::vector<T>(l)
304    { }
305   
306    /// insert new value if doesn't exists
307    void insertValue(const T& v)
308    {
309        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
310        if (fit == std::vector<T>::end())
311            std::vector<T>::push_back(v);
312    }
313   
314    /// erase value if exists
315    void eraseValue(const T& v)
316    {
317        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
318        if (fit != std::vector<T>::end())
319            std::vector<T>::erase(fit);
320    }
321   
322    /// return true if value present in vector set
323    bool hasValue(const T& v) const
324    {
325        return std::find(std::vector<T>::begin(), std::vector<T>::end(), v) !=
326                std::vector<T>::end();
327    }
328};
329
330
331/// binary find helper
332/**
333 * \param begin iterator to first element
334 * \param end iterator to after last element
335 * \param v value to find
336 * \return iterator to value or end
337 */
338template<typename Iter>
339Iter binaryFind(Iter begin, Iter end, const
340            typename std::iterator_traits<Iter>::value_type& v);
341
342/// binary find helper
343/**
344 * \param begin iterator to first element
345 * \param end iterator to after last element
346 * \param v value to find
347 * \param comp comparator
348 * \return iterator to value or end
349 */
350template<typename Iter, typename Comp =
351        std::less<typename std::iterator_traits<Iter>::value_type> >
352Iter binaryFind(Iter begin, Iter end, const
353        typename std::iterator_traits<Iter>::value_type& v, Comp comp);
354
355/// binary find helper for array-map
356/**
357 * \param begin iterator to first element
358 * \param end iterator to after last element
359 * \param k key to find
360 * \return iterator to value or end
361 */
362template<typename Iter>
363Iter binaryMapFind(Iter begin, Iter end, const 
364        typename std::iterator_traits<Iter>::value_type::first_type& k);
365
366/// binary find helper for array-map
367/**
368 * \param begin iterator to first element
369 * \param end iterator to after last element
370 * \param k key to find
371 * \param comp comparator
372 * \return iterator to value or end
373 */
374template<typename Iter, typename Comp =
375    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
376Iter binaryMapFind(Iter begin, Iter end, const
377        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp);
378
379/// map range of iterators
380/**
381 * \param begin iterator to first element
382 * \param end iterator to after last element
383 */
384template<typename Iter>
385void mapSort(Iter begin, Iter end);
386
387/// map range of iterators
388/**
389 * \param begin iterator to first element
390 * \param end iterator to after last element
391 */
392template<typename Iter, typename Comp =
393    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
394void mapSort(Iter begin, Iter end, Comp comp);
395
396/// binary find
397/**
398 * \param begin iterator to first element
399 * \param end iterator to after last element
400 * \param v value to find
401 * \return iterator to value or end
402 */
403template<typename Iter>
404Iter binaryFind(Iter begin, Iter end,
405        const typename std::iterator_traits<Iter>::value_type& v)
406{
407    auto it = std::lower_bound(begin, end, v);
408    if (it == end || v < *it)
409        return end;
410    return it;
411}
412
413/// binary find
414/**
415 * \param begin iterator to first element
416 * \param end iterator to after last element
417 * \param v value to find
418 * \param comp comparator
419 * \return iterator to value or end
420 */
421template<typename Iter, typename Comp>
422Iter binaryFind(Iter begin, Iter end,
423        const typename std::iterator_traits<Iter>::value_type& v, Comp comp)
424{
425    auto it = std::lower_bound(begin, end, v, comp);
426    if (it == end || comp(v, *it))
427        return end;
428    return it;
429}
430
431/// binary find of map (array)
432template<typename Iter>
433Iter binaryMapFind(Iter begin, Iter end, const
434            typename std::iterator_traits<Iter>::value_type::first_type& k)
435{
436    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
437    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
438    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
439               [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
440        return e1.first < e2.first; });
441    if (it == end || k < it->first)
442        return end;
443    return it;
444}
445
446/// binary find of map (array)
447template<typename Iter, typename Comp>
448Iter binaryMapFind(Iter begin, Iter end, const
449        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp)
450{
451    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
452    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
453    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
454               [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
455        return comp(e1.first, e2.first); });
456    if (it == end || comp(k, it->first))
457        return end;
458    return it;
459}
460
461/// sort map (array)
462/**
463 * \param begin iterator to first element
464 * \param end iterator to after last element
465 */
466template<typename Iter>
467void mapSort(Iter begin, Iter end)
468{
469    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
470    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
471    std::sort(begin, end, [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
472        return e1.first < e2.first; });
473}
474
475/// sort map (array)
476/**
477 * \param begin iterator to first element
478 * \param end iterator to after last element
479 * \param comp comparator
480 */
481template<typename Iter, typename Comp>
482void mapSort(Iter begin, Iter end, Comp comp)
483{
484    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
485    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
486    std::sort(begin, end, [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
487       return comp(e1.first, e2.first); });
488}
489
490};
491
492namespace std
493{
494
495/// std::swap specialization for CLRX::Array
496template<typename T>
497void swap(CLRX::Array<T>& a1, CLRX::Array<T>& a2)
498{ a1.swap(a2); }
499
500}
501
502#endif
Note: See TracBrowser for help on using the repository browser.