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_MAP_HPP 12 #define BOOST_COMPUTE_CONTAINER_FLAT_MAP_HPP 13 14 #include <cstddef> 15 #include <utility> 16 #include <exception> 17 18 #include <boost/config.hpp> 19 #include <boost/throw_exception.hpp> 20 21 #include <boost/compute/exception.hpp> 22 #include <boost/compute/algorithm/find.hpp> 23 #include <boost/compute/algorithm/lower_bound.hpp> 24 #include <boost/compute/algorithm/upper_bound.hpp> 25 #include <boost/compute/container/vector.hpp> 26 #include <boost/compute/functional/get.hpp> 27 #include <boost/compute/iterator/transform_iterator.hpp> 28 #include <boost/compute/types/pair.hpp> 29 #include <boost/compute/detail/buffer_value.hpp> 30 31 namespace boost { 32 namespace compute { 33 34 template<class Key, class T> 35 class flat_map 36 { 37 public: 38 typedef Key key_type; 39 typedef T mapped_type; 40 typedef typename ::boost::compute::vector<std::pair<Key, T> > vector_type; 41 typedef typename vector_type::value_type value_type; 42 typedef typename vector_type::size_type size_type; 43 typedef typename vector_type::difference_type difference_type; 44 typedef typename vector_type::reference reference; 45 typedef typename vector_type::const_reference const_reference; 46 typedef typename vector_type::pointer pointer; 47 typedef typename vector_type::const_pointer const_pointer; 48 typedef typename vector_type::iterator iterator; 49 typedef typename vector_type::const_iterator const_iterator; 50 typedef typename vector_type::reverse_iterator reverse_iterator; 51 typedef typename vector_type::const_reverse_iterator const_reverse_iterator; 52 flat_map(const context & context=system::default_context ())53 explicit flat_map(const context &context = system::default_context()) 54 : m_vector(context) 55 { 56 } 57 flat_map(const flat_map<Key,T> & other)58 flat_map(const flat_map<Key, T> &other) 59 : m_vector(other.m_vector) 60 { 61 } 62 operator =(const flat_map<Key,T> & other)63 flat_map<Key, T>& operator=(const flat_map<Key, T> &other) 64 { 65 if(this != &other){ 66 m_vector = other.m_vector; 67 } 68 69 return *this; 70 } 71 ~flat_map()72 ~flat_map() 73 { 74 } 75 begin()76 iterator begin() 77 { 78 return m_vector.begin(); 79 } 80 begin() const81 const_iterator begin() const 82 { 83 return m_vector.begin(); 84 } 85 cbegin() const86 const_iterator cbegin() const 87 { 88 return m_vector.cbegin(); 89 } 90 end()91 iterator end() 92 { 93 return m_vector.end(); 94 } 95 end() const96 const_iterator end() const 97 { 98 return m_vector.end(); 99 } 100 cend() const101 const_iterator cend() const 102 { 103 return m_vector.cend(); 104 } 105 rbegin()106 reverse_iterator rbegin() 107 { 108 return m_vector.rbegin(); 109 } 110 rbegin() const111 const_reverse_iterator rbegin() const 112 { 113 return m_vector.rbegin(); 114 } 115 crbegin() const116 const_reverse_iterator crbegin() const 117 { 118 return m_vector.crbegin(); 119 } 120 rend()121 reverse_iterator rend() 122 { 123 return m_vector.rend(); 124 } 125 rend() const126 const_reverse_iterator rend() const 127 { 128 return m_vector.rend(); 129 } 130 crend() const131 const_reverse_iterator crend() const 132 { 133 return m_vector.crend(); 134 } 135 size() const136 size_type size() const 137 { 138 return m_vector.size(); 139 } 140 max_size() const141 size_type max_size() const 142 { 143 return m_vector.max_size(); 144 } 145 empty() const146 bool empty() const 147 { 148 return m_vector.empty(); 149 } 150 capacity() const151 size_type capacity() const 152 { 153 return m_vector.capacity(); 154 } 155 reserve(size_type size,command_queue & queue)156 void reserve(size_type size, command_queue &queue) 157 { 158 m_vector.reserve(size, queue); 159 } 160 reserve(size_type size)161 void reserve(size_type size) 162 { 163 command_queue queue = m_vector.default_queue(); 164 reserve(size, queue); 165 queue.finish(); 166 } 167 shrink_to_fit()168 void shrink_to_fit() 169 { 170 m_vector.shrink_to_fit(); 171 } 172 clear()173 void clear() 174 { 175 m_vector.clear(); 176 } 177 178 std::pair<iterator, bool> insert(const value_type & value,command_queue & queue)179 insert(const value_type &value, command_queue &queue) 180 { 181 iterator location = upper_bound(value.first, queue); 182 183 if(location != begin()){ 184 value_type current_value; 185 ::boost::compute::copy_n(location - 1, 1, ¤t_value, queue); 186 if(value.first == current_value.first){ 187 return std::make_pair(location - 1, false); 188 } 189 } 190 191 m_vector.insert(location, value); 192 return std::make_pair(location, true); 193 } 194 insert(const value_type & value)195 std::pair<iterator, bool> insert(const value_type &value) 196 { 197 command_queue queue = m_vector.default_queue(); 198 std::pair<iterator, bool> result = insert(value, queue); 199 queue.finish(); 200 return result; 201 } 202 erase(const const_iterator & position,command_queue & queue)203 iterator erase(const const_iterator &position, command_queue &queue) 204 { 205 return erase(position, position + 1, queue); 206 } 207 erase(const const_iterator & position)208 iterator erase(const const_iterator &position) 209 { 210 command_queue queue = m_vector.default_queue(); 211 iterator iter = erase(position, queue); 212 queue.finish(); 213 return iter; 214 } 215 erase(const const_iterator & first,const const_iterator & last,command_queue & queue)216 iterator erase(const const_iterator &first, 217 const const_iterator &last, 218 command_queue &queue) 219 { 220 return m_vector.erase(first, last, queue); 221 } 222 erase(const const_iterator & first,const const_iterator & last)223 iterator erase(const const_iterator &first, const const_iterator &last) 224 { 225 command_queue queue = m_vector.default_queue(); 226 iterator iter = erase(first, last, queue); 227 queue.finish(); 228 return iter; 229 } 230 erase(const key_type & value,command_queue & queue)231 size_type erase(const key_type &value, command_queue &queue) 232 { 233 iterator position = find(value, queue); 234 235 if(position == end()){ 236 return 0; 237 } 238 else { 239 erase(position, queue); 240 return 1; 241 } 242 } 243 find(const key_type & value,command_queue & queue)244 iterator find(const key_type &value, command_queue &queue) 245 { 246 ::boost::compute::get<0> get_key; 247 248 return ::boost::compute::find( 249 ::boost::compute::make_transform_iterator(begin(), get_key), 250 ::boost::compute::make_transform_iterator(end(), get_key), 251 value, 252 queue 253 ).base(); 254 } 255 find(const key_type & value)256 iterator find(const key_type &value) 257 { 258 command_queue queue = m_vector.default_queue(); 259 iterator iter = find(value, queue); 260 queue.finish(); 261 return iter; 262 } 263 find(const key_type & value,command_queue & queue) const264 const_iterator find(const key_type &value, command_queue &queue) const 265 { 266 ::boost::compute::get<0> get_key; 267 268 return ::boost::compute::find( 269 ::boost::compute::make_transform_iterator(begin(), get_key), 270 ::boost::compute::make_transform_iterator(end(), get_key), 271 value, 272 queue 273 ).base(); 274 } 275 find(const key_type & value) const276 const_iterator find(const key_type &value) const 277 { 278 command_queue queue = m_vector.default_queue(); 279 const_iterator iter = find(value, queue); 280 queue.finish(); 281 return iter; 282 } 283 count(const key_type & value,command_queue & queue) const284 size_type count(const key_type &value, command_queue &queue) const 285 { 286 return find(value, queue) != end() ? 1 : 0; 287 } 288 count(const key_type & value) const289 size_type count(const key_type &value) const 290 { 291 command_queue queue = m_vector.default_queue(); 292 size_type result = count(value, queue); 293 queue.finish(); 294 return result; 295 } 296 lower_bound(const key_type & value,command_queue & queue)297 iterator lower_bound(const key_type &value, command_queue &queue) 298 { 299 ::boost::compute::get<0> get_key; 300 301 return ::boost::compute::lower_bound( 302 ::boost::compute::make_transform_iterator(begin(), get_key), 303 ::boost::compute::make_transform_iterator(end(), get_key), 304 value, 305 queue 306 ).base(); 307 } 308 lower_bound(const key_type & value)309 iterator lower_bound(const key_type &value) 310 { 311 command_queue queue = m_vector.default_queue(); 312 iterator iter = lower_bound(value, queue); 313 queue.finish(); 314 return iter; 315 } 316 lower_bound(const key_type & value,command_queue & queue) const317 const_iterator lower_bound(const key_type &value, command_queue &queue) const 318 { 319 ::boost::compute::get<0> get_key; 320 321 return ::boost::compute::lower_bound( 322 ::boost::compute::make_transform_iterator(begin(), get_key), 323 ::boost::compute::make_transform_iterator(end(), get_key), 324 value, 325 queue 326 ).base(); 327 } 328 lower_bound(const key_type & value) const329 const_iterator lower_bound(const key_type &value) const 330 { 331 command_queue queue = m_vector.default_queue(); 332 const_iterator iter = lower_bound(value, queue); 333 queue.finish(); 334 return iter; 335 } 336 upper_bound(const key_type & value,command_queue & queue)337 iterator upper_bound(const key_type &value, command_queue &queue) 338 { 339 ::boost::compute::get<0> get_key; 340 341 return ::boost::compute::upper_bound( 342 ::boost::compute::make_transform_iterator(begin(), get_key), 343 ::boost::compute::make_transform_iterator(end(), get_key), 344 value, 345 queue 346 ).base(); 347 } 348 upper_bound(const key_type & value)349 iterator upper_bound(const key_type &value) 350 { 351 command_queue queue = m_vector.default_queue(); 352 iterator iter = upper_bound(value, queue); 353 queue.finish(); 354 return iter; 355 } 356 upper_bound(const key_type & value,command_queue & queue) const357 const_iterator upper_bound(const key_type &value, command_queue &queue) const 358 { 359 ::boost::compute::get<0> get_key; 360 361 return ::boost::compute::upper_bound( 362 ::boost::compute::make_transform_iterator(begin(), get_key), 363 ::boost::compute::make_transform_iterator(end(), get_key), 364 value, 365 queue 366 ).base(); 367 } 368 upper_bound(const key_type & value) const369 const_iterator upper_bound(const key_type &value) const 370 { 371 command_queue queue = m_vector.default_queue(); 372 const_iterator iter = upper_bound(value, queue); 373 queue.finish(); 374 return iter; 375 } 376 at(const key_type & key) const377 const mapped_type at(const key_type &key) const 378 { 379 const_iterator iter = find(key); 380 if(iter == end()){ 381 BOOST_THROW_EXCEPTION(std::out_of_range("key not found")); 382 } 383 384 return value_type(*iter).second; 385 } 386 operator [](const key_type & key)387 detail::buffer_value<mapped_type> operator[](const key_type &key) 388 { 389 iterator iter = find(key); 390 if(iter == end()){ 391 iter = insert(std::make_pair(key, mapped_type())).first; 392 } 393 394 size_t index = iter.get_index() * sizeof(value_type) + sizeof(key_type); 395 396 return detail::buffer_value<mapped_type>(m_vector.get_buffer(), index); 397 } 398 399 private: 400 ::boost::compute::vector<std::pair<Key, T> > m_vector; 401 }; 402 403 } // end compute namespace 404 } // end boost namespace 405 406 #endif // BOOST_COMPUTE_CONTAINER_FLAT_MAP_HPP 407