1 //---------------------------------------------------------------------------// 2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com> 3 // 4 // Distributed under the Boost Software License, Version 1.0 5 // See accompanying file LICENSE_1_0.txt or copy at 6 // http://www.boost.org/LICENSE_1_0.txt 7 // 8 // See http://boostorg.github.com/compute for more information. 9 //---------------------------------------------------------------------------// 10 11 #ifndef BOOST_COMPUTE_CONTAINER_FLAT_SET_HPP 12 #define BOOST_COMPUTE_CONTAINER_FLAT_SET_HPP 13 14 #include <cstddef> 15 #include <utility> 16 17 #include <boost/compute/algorithm/find.hpp> 18 #include <boost/compute/algorithm/lower_bound.hpp> 19 #include <boost/compute/algorithm/upper_bound.hpp> 20 #include <boost/compute/container/vector.hpp> 21 22 namespace boost { 23 namespace compute { 24 25 template<class T> 26 class flat_set 27 { 28 public: 29 typedef T key_type; 30 typedef typename vector<T>::value_type value_type; 31 typedef typename vector<T>::size_type size_type; 32 typedef typename vector<T>::difference_type difference_type; 33 typedef typename vector<T>::reference reference; 34 typedef typename vector<T>::const_reference const_reference; 35 typedef typename vector<T>::pointer pointer; 36 typedef typename vector<T>::const_pointer const_pointer; 37 typedef typename vector<T>::iterator iterator; 38 typedef typename vector<T>::const_iterator const_iterator; 39 typedef typename vector<T>::reverse_iterator reverse_iterator; 40 typedef typename vector<T>::const_reverse_iterator const_reverse_iterator; 41 flat_set(const context & context=system::default_context ())42 explicit flat_set(const context &context = system::default_context()) 43 : m_vector(context) 44 { 45 } 46 flat_set(const flat_set<T> & other)47 flat_set(const flat_set<T> &other) 48 : m_vector(other.m_vector) 49 { 50 } 51 operator =(const flat_set<T> & other)52 flat_set<T>& operator=(const flat_set<T> &other) 53 { 54 if(this != &other){ 55 m_vector = other.m_vector; 56 } 57 58 return *this; 59 } 60 ~flat_set()61 ~flat_set() 62 { 63 } 64 begin()65 iterator begin() 66 { 67 return m_vector.begin(); 68 } 69 begin() const70 const_iterator begin() const 71 { 72 return m_vector.begin(); 73 } 74 cbegin() const75 const_iterator cbegin() const 76 { 77 return m_vector.cbegin(); 78 } 79 end()80 iterator end() 81 { 82 return m_vector.end(); 83 } 84 end() const85 const_iterator end() const 86 { 87 return m_vector.end(); 88 } 89 cend() const90 const_iterator cend() const 91 { 92 return m_vector.cend(); 93 } 94 rbegin()95 reverse_iterator rbegin() 96 { 97 return m_vector.rbegin(); 98 } 99 rbegin() const100 const_reverse_iterator rbegin() const 101 { 102 return m_vector.rbegin(); 103 } 104 crbegin() const105 const_reverse_iterator crbegin() const 106 { 107 return m_vector.crbegin(); 108 } 109 rend()110 reverse_iterator rend() 111 { 112 return m_vector.rend(); 113 } 114 rend() const115 const_reverse_iterator rend() const 116 { 117 return m_vector.rend(); 118 } 119 crend() const120 const_reverse_iterator crend() const 121 { 122 return m_vector.crend(); 123 } 124 size() const125 size_type size() const 126 { 127 return m_vector.size(); 128 } 129 max_size() const130 size_type max_size() const 131 { 132 return m_vector.max_size(); 133 } 134 empty() const135 bool empty() const 136 { 137 return m_vector.empty(); 138 } 139 capacity() const140 size_type capacity() const 141 { 142 return m_vector.capacity(); 143 } 144 reserve(size_type size,command_queue & queue)145 void reserve(size_type size, command_queue &queue) 146 { 147 m_vector.reserve(size, queue); 148 } 149 reserve(size_type size)150 void reserve(size_type size) 151 { 152 command_queue queue = m_vector.default_queue(); 153 reserve(size, queue); 154 queue.finish(); 155 } 156 shrink_to_fit()157 void shrink_to_fit() 158 { 159 m_vector.shrink_to_fit(); 160 } 161 clear()162 void clear() 163 { 164 m_vector.clear(); 165 } 166 167 std::pair<iterator, bool> insert(const value_type & value,command_queue & queue)168 insert(const value_type &value, command_queue &queue) 169 { 170 iterator location = upper_bound(value, queue); 171 172 if(location != begin()){ 173 value_type current_value; 174 ::boost::compute::copy_n(location - 1, 1, ¤t_value, queue); 175 if(value == current_value){ 176 return std::make_pair(location - 1, false); 177 } 178 } 179 180 m_vector.insert(location, value, queue); 181 return std::make_pair(location, true); 182 } 183 insert(const value_type & value)184 std::pair<iterator, bool> insert(const value_type &value) 185 { 186 command_queue queue = m_vector.default_queue(); 187 std::pair<iterator, bool> result = insert(value, queue); 188 queue.finish(); 189 return result; 190 } 191 erase(const const_iterator & position,command_queue & queue)192 iterator erase(const const_iterator &position, command_queue &queue) 193 { 194 return erase(position, position + 1, queue); 195 } 196 erase(const const_iterator & position)197 iterator erase(const const_iterator &position) 198 { 199 command_queue queue = m_vector.default_queue(); 200 iterator iter = erase(position, queue); 201 queue.finish(); 202 return iter; 203 } 204 erase(const const_iterator & first,const const_iterator & last,command_queue & queue)205 iterator erase(const const_iterator &first, 206 const const_iterator &last, 207 command_queue &queue) 208 { 209 return m_vector.erase(first, last, queue); 210 } 211 erase(const const_iterator & first,const const_iterator & last)212 iterator erase(const const_iterator &first, const const_iterator &last) 213 { 214 command_queue queue = m_vector.default_queue(); 215 iterator iter = erase(first, last, queue); 216 queue.finish(); 217 return iter; 218 } 219 erase(const key_type & value,command_queue & queue)220 size_type erase(const key_type &value, command_queue &queue) 221 { 222 iterator position = find(value, queue); 223 224 if(position == end()){ 225 return 0; 226 } 227 else { 228 erase(position, queue); 229 return 1; 230 } 231 } 232 erase(const key_type & value)233 size_type erase(const key_type &value) 234 { 235 command_queue queue = m_vector.default_queue(); 236 size_type result = erase(value, queue); 237 queue.finish(); 238 return result; 239 } 240 find(const key_type & value,command_queue & queue)241 iterator find(const key_type &value, command_queue &queue) 242 { 243 return ::boost::compute::find(begin(), end(), value, queue); 244 } 245 find(const key_type & value)246 iterator find(const key_type &value) 247 { 248 command_queue queue = m_vector.default_queue(); 249 iterator iter = find(value, queue); 250 queue.finish(); 251 return iter; 252 } 253 find(const key_type & value,command_queue & queue) const254 const_iterator find(const key_type &value, command_queue &queue) const 255 { 256 return ::boost::compute::find(begin(), end(), value, queue); 257 } 258 find(const key_type & value) const259 const_iterator find(const key_type &value) const 260 { 261 command_queue queue = m_vector.default_queue(); 262 const_iterator iter = find(value, queue); 263 queue.finish(); 264 return iter; 265 } 266 count(const key_type & value,command_queue & queue) const267 size_type count(const key_type &value, command_queue &queue) const 268 { 269 return find(value, queue) != end() ? 1 : 0; 270 } 271 count(const key_type & value) const272 size_type count(const key_type &value) const 273 { 274 command_queue queue = m_vector.default_queue(); 275 size_type result = count(value, queue); 276 queue.finish(); 277 return result; 278 } 279 lower_bound(const key_type & value,command_queue & queue)280 iterator lower_bound(const key_type &value, command_queue &queue) 281 { 282 return ::boost::compute::lower_bound(begin(), end(), value, queue); 283 } 284 lower_bound(const key_type & value)285 iterator lower_bound(const key_type &value) 286 { 287 command_queue queue = m_vector.default_queue(); 288 iterator iter = lower_bound(value, queue); 289 queue.finish(); 290 return iter; 291 } 292 lower_bound(const key_type & value,command_queue & queue) const293 const_iterator lower_bound(const key_type &value, command_queue &queue) const 294 { 295 return ::boost::compute::lower_bound(begin(), end(), value, queue); 296 } 297 lower_bound(const key_type & value) const298 const_iterator lower_bound(const key_type &value) const 299 { 300 command_queue queue = m_vector.default_queue(); 301 const_iterator iter = lower_bound(value, queue); 302 queue.finish(); 303 return iter; 304 } 305 upper_bound(const key_type & value,command_queue & queue)306 iterator upper_bound(const key_type &value, command_queue &queue) 307 { 308 return ::boost::compute::upper_bound(begin(), end(), value, queue); 309 } 310 upper_bound(const key_type & value)311 iterator upper_bound(const key_type &value) 312 { 313 command_queue queue = m_vector.default_queue(); 314 iterator iter = upper_bound(value, queue); 315 queue.finish(); 316 return iter; 317 } 318 upper_bound(const key_type & value,command_queue & queue) const319 const_iterator upper_bound(const key_type &value, command_queue &queue) const 320 { 321 return ::boost::compute::upper_bound(begin(), end(), value, queue); 322 } 323 upper_bound(const key_type & value) const324 const_iterator upper_bound(const key_type &value) const 325 { 326 command_queue queue = m_vector.default_queue(); 327 const_iterator iter = upper_bound(value, queue); 328 queue.finish(); 329 return iter; 330 } 331 332 private: 333 vector<T> m_vector; 334 }; 335 336 } // end compute namespace 337 } // end boost namespace 338 339 #endif // BOOST_COMPUTE_CONTAINER_FLAT_SET_HPP 340