[857] | 1 | //
|
---|
| 2 | // Copyright (c) 2000-2002
|
---|
| 3 | // Joerg Walter, Mathias Koch
|
---|
| 4 | //
|
---|
| 5 | // Permission to use, copy, modify, distribute and sell this software
|
---|
| 6 | // and its documentation for any purpose is hereby granted without fee,
|
---|
| 7 | // provided that the above copyright notice appear in all copies and
|
---|
| 8 | // that both that copyright notice and this permission notice appear
|
---|
| 9 | // in supporting documentation. The authors make no representations
|
---|
| 10 | // about the suitability of this software for any purpose.
|
---|
| 11 | // It is provided "as is" without express or implied warranty.
|
---|
| 12 | //
|
---|
| 13 | // The authors gratefully acknowledge the support of
|
---|
| 14 | // GeNeSys mbH & Co. KG in producing this work.
|
---|
| 15 | //
|
---|
| 16 |
|
---|
| 17 | #ifndef _BOOST_UBLAS_STORAGE_SPARSE_
|
---|
| 18 | #define _BOOST_UBLAS_STORAGE_SPARSE_
|
---|
| 19 |
|
---|
| 20 | #include <map>
|
---|
| 21 |
|
---|
| 22 | #include <boost/numeric/ublas/storage.hpp>
|
---|
| 23 |
|
---|
| 24 |
|
---|
| 25 | namespace boost { namespace numeric { namespace ublas {
|
---|
| 26 |
|
---|
| 27 | namespace detail {
|
---|
| 28 |
|
---|
| 29 | template<class I, class T, class C>
|
---|
| 30 | BOOST_UBLAS_INLINE
|
---|
| 31 | I lower_bound (const I &begin, const I &end, const T &t, C compare) {
|
---|
| 32 | // t <= *begin <=> ! (*begin < t)
|
---|
| 33 | if (begin == end || ! compare (*begin, t))
|
---|
| 34 | return begin;
|
---|
| 35 | if (compare (*(end - 1), t))
|
---|
| 36 | return end;
|
---|
| 37 | return std::lower_bound (begin, end, t, compare);
|
---|
| 38 | }
|
---|
| 39 | template<class I, class T, class C>
|
---|
| 40 | BOOST_UBLAS_INLINE
|
---|
| 41 | I upper_bound (const I &begin, const I &end, const T &t, C compare) {
|
---|
| 42 | if (begin == end || compare (t, *begin))
|
---|
| 43 | return begin;
|
---|
| 44 | // (*end - 1) <= t <=> ! (t < *end)
|
---|
| 45 | if (! compare (t, *(end - 1)))
|
---|
| 46 | return end;
|
---|
| 47 | return std::upper_bound (begin, end, t, compare);
|
---|
| 48 | }
|
---|
| 49 |
|
---|
| 50 | template<class P>
|
---|
| 51 | struct less_pair {
|
---|
| 52 | BOOST_UBLAS_INLINE
|
---|
| 53 | bool operator () (const P &p1, const P &p2) {
|
---|
| 54 | return p1.first < p2.first;
|
---|
| 55 | }
|
---|
| 56 | };
|
---|
| 57 | template<class T>
|
---|
| 58 | struct less_triple {
|
---|
| 59 | BOOST_UBLAS_INLINE
|
---|
| 60 | bool operator () (const T &t1, const T &t2) {
|
---|
| 61 | return t1.first.first < t2.first.first ||
|
---|
| 62 | (t1.first.first == t2.first.first && t1.first.second < t2.first.second);
|
---|
| 63 | }
|
---|
| 64 | };
|
---|
| 65 |
|
---|
| 66 | }
|
---|
| 67 |
|
---|
| 68 | #ifdef BOOST_UBLAS_STRICT_MAP_ARRAY
|
---|
| 69 | template<class A>
|
---|
| 70 | class sparse_storage_element:
|
---|
| 71 | public container_reference<A> {
|
---|
| 72 | public:
|
---|
| 73 | typedef A array_type;
|
---|
| 74 | typedef typename A::key_type index_type;
|
---|
| 75 | typedef typename A::mapped_type data_value_type;
|
---|
| 76 | // typedef const data_value_type &data_const_reference;
|
---|
| 77 | typedef typename type_traits<data_value_type>::const_reference data_const_reference;
|
---|
| 78 | typedef data_value_type &data_reference;
|
---|
| 79 | typedef typename A::value_type value_type;
|
---|
| 80 | typedef value_type *pointer;
|
---|
| 81 |
|
---|
| 82 | // Construction and destruction
|
---|
| 83 | BOOST_UBLAS_INLINE
|
---|
| 84 | sparse_storage_element (array_type &a, pointer it):
|
---|
| 85 | container_reference<array_type> (a), it_ (it), i_ (it->first), d_ (it->second), dirty_ (false) {}
|
---|
| 86 | BOOST_UBLAS_INLINE
|
---|
| 87 | sparse_storage_element (array_type &a, index_type i):
|
---|
| 88 | container_reference<array_type> (a), it_ (), i_ (i), d_ (), dirty_ (false) {
|
---|
| 89 | pointer it = (*this) ().find (i_);
|
---|
| 90 | if (it == (*this) ().end ())
|
---|
| 91 | it = (*this) ().insert ((*this) ().end (), value_type (i_, d_));
|
---|
| 92 | d_ = it->second;
|
---|
| 93 | }
|
---|
| 94 | BOOST_UBLAS_INLINE
|
---|
| 95 | ~sparse_storage_element () {
|
---|
| 96 | if (dirty_) {
|
---|
| 97 | if (! it_)
|
---|
| 98 | it_ = (*this) ().find (i_);
|
---|
| 99 | BOOST_UBLAS_CHECK (it_ != (*this) ().end (), internal_logic ());
|
---|
| 100 | it_->second = d_;
|
---|
| 101 | }
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | // Element access - only if data_const_reference is defined
|
---|
| 105 | BOOST_UBLAS_INLINE
|
---|
| 106 | typename data_value_type::data_const_reference
|
---|
| 107 | operator [] (index_type i) const {
|
---|
| 108 | return d_ [i];
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | // Assignment
|
---|
| 112 | BOOST_UBLAS_INLINE
|
---|
| 113 | sparse_storage_element &operator = (const sparse_storage_element &p) {
|
---|
| 114 | // Overide the implict copy assignment
|
---|
| 115 | d_ = p.d_;
|
---|
| 116 | dirty_ = true;
|
---|
| 117 | return *this;
|
---|
| 118 | }
|
---|
| 119 | template<class D>
|
---|
| 120 | BOOST_UBLAS_INLINE
|
---|
| 121 | sparse_storage_element &operator = (const D &d) {
|
---|
| 122 | d_ = d;
|
---|
| 123 | dirty_ = true;
|
---|
| 124 | return *this;
|
---|
| 125 | }
|
---|
| 126 | template<class D>
|
---|
| 127 | BOOST_UBLAS_INLINE
|
---|
| 128 | sparse_storage_element &operator += (const D &d) {
|
---|
| 129 | d_ += d;
|
---|
| 130 | dirty_ = true;
|
---|
| 131 | return *this;
|
---|
| 132 | }
|
---|
| 133 | template<class D>
|
---|
| 134 | BOOST_UBLAS_INLINE
|
---|
| 135 | sparse_storage_element &operator -= (const D &d) {
|
---|
| 136 | d_ -= d;
|
---|
| 137 | dirty_ = true;
|
---|
| 138 | return *this;
|
---|
| 139 | }
|
---|
| 140 | template<class D>
|
---|
| 141 | BOOST_UBLAS_INLINE
|
---|
| 142 | sparse_storage_element &operator *= (const D &d) {
|
---|
| 143 | d_ *= d;
|
---|
| 144 | dirty_ = true;
|
---|
| 145 | return *this;
|
---|
| 146 | }
|
---|
| 147 | template<class D>
|
---|
| 148 | BOOST_UBLAS_INLINE
|
---|
| 149 | sparse_storage_element &operator /= (const D &d) {
|
---|
| 150 | d_ /= d;
|
---|
| 151 | dirty_ = true;
|
---|
| 152 | return *this;
|
---|
| 153 | }
|
---|
| 154 |
|
---|
| 155 | // Comparison
|
---|
| 156 | template<class D>
|
---|
| 157 | BOOST_UBLAS_INLINE
|
---|
| 158 | bool operator == (const D &d) const {
|
---|
| 159 | return d_ == d;
|
---|
| 160 | }
|
---|
| 161 | template<class D>
|
---|
| 162 | BOOST_UBLAS_INLINE
|
---|
| 163 | bool operator != (const D &d) const {
|
---|
| 164 | return d_ != d;
|
---|
| 165 | }
|
---|
| 166 |
|
---|
| 167 | // Conversion
|
---|
| 168 | BOOST_UBLAS_INLINE
|
---|
| 169 | operator data_const_reference () const {
|
---|
| 170 | return d_;
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | // Swapping
|
---|
| 174 | BOOST_UBLAS_INLINE
|
---|
| 175 | void swap (sparse_storage_element p) {
|
---|
| 176 | if (this != &p) {
|
---|
| 177 | dirty_ = true;
|
---|
| 178 | p.dirty_ = true;
|
---|
| 179 | std::swap (d_, p.d_);
|
---|
| 180 | }
|
---|
| 181 | }
|
---|
| 182 | BOOST_UBLAS_INLINE
|
---|
| 183 | friend void swap (sparse_storage_element p1, sparse_storage_element p2) {
|
---|
| 184 | p1.swap (p2);
|
---|
| 185 | }
|
---|
| 186 |
|
---|
| 187 | private:
|
---|
| 188 | pointer it_;
|
---|
| 189 | index_type i_;
|
---|
| 190 | data_value_type d_;
|
---|
| 191 | bool dirty_;
|
---|
| 192 | };
|
---|
| 193 | #endif
|
---|
| 194 |
|
---|
| 195 |
|
---|
| 196 | // Default map type is simply forwarded to std::map
|
---|
| 197 | // FIXME should use ALLOC for map but std::allocator of std::pair<const I, T> and std::pair<I,T> fail to compile
|
---|
| 198 | template<class I, class T, class ALLOC>
|
---|
| 199 | class map_std : public std::map<I, T /*, ALLOC */> {
|
---|
| 200 | };
|
---|
| 201 |
|
---|
| 202 |
|
---|
| 203 | // Map array
|
---|
| 204 | // Implementation requires pair<I, T> allocator definition (without const)
|
---|
| 205 | template<class I, class T, class ALLOC>
|
---|
| 206 | class map_array {
|
---|
| 207 | public:
|
---|
| 208 | typedef ALLOC allocator_type;
|
---|
| 209 | typedef typename ALLOC::size_type size_type;
|
---|
| 210 | typedef typename ALLOC::difference_type difference_type;
|
---|
| 211 | typedef std::pair<I,T> value_type;
|
---|
| 212 | typedef I key_type;
|
---|
| 213 | typedef T mapped_type;
|
---|
| 214 | typedef const value_type &const_reference;
|
---|
| 215 | typedef value_type &reference;
|
---|
| 216 | typedef const value_type *const_pointer;
|
---|
| 217 | typedef value_type *pointer;
|
---|
| 218 | // Iterators simply are pointers.
|
---|
| 219 | typedef const_pointer const_iterator;
|
---|
| 220 | typedef pointer iterator;
|
---|
| 221 |
|
---|
| 222 | typedef const T &data_const_reference;
|
---|
| 223 | #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
|
---|
| 224 | typedef T &data_reference;
|
---|
| 225 | #else
|
---|
| 226 | typedef sparse_storage_element<map_array> data_reference;
|
---|
| 227 | #endif
|
---|
| 228 |
|
---|
| 229 | // Construction and destruction
|
---|
| 230 | BOOST_UBLAS_INLINE
|
---|
| 231 | map_array (const ALLOC &a = ALLOC()):
|
---|
| 232 | alloc_(a), capacity_ (0), size_ (0) {
|
---|
| 233 | data_ = 0;
|
---|
| 234 | }
|
---|
| 235 | BOOST_UBLAS_INLINE
|
---|
| 236 | map_array (const map_array &c):
|
---|
| 237 | alloc_ (c.alloc_), capacity_ (c.size_), size_ (c.size_) {
|
---|
| 238 | if (capacity_) {
|
---|
| 239 | data_ = alloc_.allocate (capacity_);
|
---|
| 240 | std::uninitialized_copy (data_, data_ + capacity_, c.data_);
|
---|
| 241 | // capacity != size_ requires uninitialized_fill (size_ to capacity_)
|
---|
| 242 | }
|
---|
| 243 | else
|
---|
| 244 | data_ = 0;
|
---|
| 245 | }
|
---|
| 246 | BOOST_UBLAS_INLINE
|
---|
| 247 | ~map_array () {
|
---|
| 248 | if (capacity_) {
|
---|
| 249 | std::for_each (data_, data_ + capacity_, static_destroy);
|
---|
| 250 | alloc_.deallocate (data_, capacity_);
|
---|
| 251 | }
|
---|
| 252 | }
|
---|
| 253 |
|
---|
| 254 | private:
|
---|
| 255 | // Resizing - implicitly exposses uninitialized (but default constructed) mapped_type
|
---|
| 256 | BOOST_UBLAS_INLINE
|
---|
| 257 | void resize (size_type size) {
|
---|
| 258 | BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
|
---|
| 259 | if (size > capacity_) {
|
---|
| 260 | const size_type capacity = size << 1;
|
---|
| 261 | BOOST_UBLAS_CHECK (capacity, internal_logic ());
|
---|
| 262 | pointer data = alloc_.allocate (capacity);
|
---|
| 263 | std::uninitialized_copy (data_, data_ + (std::min) (size, size_), data);
|
---|
| 264 | std::uninitialized_fill (data + (std::min) (size, size_), data + capacity, value_type ());
|
---|
| 265 |
|
---|
| 266 | if (capacity_) {
|
---|
| 267 | std::for_each (data_, data_ + capacity_, static_destroy);
|
---|
| 268 | alloc_.deallocate (data_, capacity_);
|
---|
| 269 | }
|
---|
| 270 | capacity_ = capacity;
|
---|
| 271 | data_ = data;
|
---|
| 272 | }
|
---|
| 273 | size_ = size;
|
---|
| 274 | BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
|
---|
| 275 | }
|
---|
| 276 | public:
|
---|
| 277 |
|
---|
| 278 | // Reserving
|
---|
| 279 | BOOST_UBLAS_INLINE
|
---|
| 280 | void reserve (size_type capacity) {
|
---|
| 281 | BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
|
---|
| 282 | // Reduce capacity_ if size_ allows
|
---|
| 283 | BOOST_UBLAS_CHECK (capacity >= size_, bad_size ());
|
---|
| 284 | pointer data;
|
---|
| 285 | if (capacity) {
|
---|
| 286 | data = alloc_.allocate (capacity);
|
---|
| 287 | std::uninitialized_copy (data_, data_ + size_, data);
|
---|
| 288 | std::uninitialized_fill (data + size_, data + capacity, value_type ());
|
---|
| 289 | }
|
---|
| 290 | else
|
---|
| 291 | data = 0;
|
---|
| 292 |
|
---|
| 293 | if (capacity_) {
|
---|
| 294 | std::for_each (data_, data_ + capacity_, static_destroy);
|
---|
| 295 | alloc_.deallocate (data_, capacity_);
|
---|
| 296 | }
|
---|
| 297 | capacity_ = capacity;
|
---|
| 298 | data_ = data;
|
---|
| 299 | BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
|
---|
| 300 | }
|
---|
| 301 |
|
---|
| 302 | BOOST_UBLAS_INLINE
|
---|
| 303 | size_type size () const {
|
---|
| 304 | return size_;
|
---|
| 305 | }
|
---|
| 306 | BOOST_UBLAS_INLINE
|
---|
| 307 | size_type capacity () const {
|
---|
| 308 | return capacity_;
|
---|
| 309 | }
|
---|
| 310 |
|
---|
| 311 | // Element access
|
---|
| 312 | BOOST_UBLAS_INLINE
|
---|
| 313 | data_reference operator [] (key_type i) {
|
---|
| 314 | #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
|
---|
| 315 | pointer it = find (i);
|
---|
| 316 | if (it == end ())
|
---|
| 317 | it = insert (end (), value_type (i, mapped_type (0)));
|
---|
| 318 | BOOST_UBLAS_CHECK (it != end (), internal_logic ());
|
---|
| 319 | return it->second;
|
---|
| 320 | #else
|
---|
| 321 | return data_reference (*this, i);
|
---|
| 322 | #endif
|
---|
| 323 | }
|
---|
| 324 |
|
---|
| 325 | // Assignment
|
---|
| 326 | BOOST_UBLAS_INLINE
|
---|
| 327 | map_array &operator = (const map_array &a) {
|
---|
| 328 | if (this != &a) {
|
---|
| 329 | resize (a.size_);
|
---|
| 330 | std::copy (a.data_, a.data_ + a.size_, data_);
|
---|
| 331 | }
|
---|
| 332 | return *this;
|
---|
| 333 | }
|
---|
| 334 | BOOST_UBLAS_INLINE
|
---|
| 335 | map_array &assign_temporary (map_array &a) {
|
---|
| 336 | swap (a);
|
---|
| 337 | return *this;
|
---|
| 338 | }
|
---|
| 339 |
|
---|
| 340 | // Swapping
|
---|
| 341 | BOOST_UBLAS_INLINE
|
---|
| 342 | void swap (map_array &a) {
|
---|
| 343 | if (this != &a) {
|
---|
| 344 | std::swap (capacity_, a.capacity_);
|
---|
| 345 | std::swap (data_, a.data_);
|
---|
| 346 | std::swap (size_, a.size_);
|
---|
| 347 | }
|
---|
| 348 | }
|
---|
| 349 | BOOST_UBLAS_INLINE
|
---|
| 350 | friend void swap (map_array &a1, map_array &a2) {
|
---|
| 351 | a1.swap (a2);
|
---|
| 352 | }
|
---|
| 353 |
|
---|
| 354 | // Element insertion and deletion
|
---|
| 355 |
|
---|
| 356 | // From Back Insertion Sequence concept
|
---|
| 357 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 358 | iterator push_back (iterator it, const value_type &p) {
|
---|
| 359 | if (size () == 0 || (it = end () - 1)->first < p.first) {
|
---|
| 360 | resize (size () + 1);
|
---|
| 361 | *(it = end () - 1) = p;
|
---|
| 362 | return it;
|
---|
| 363 | }
|
---|
| 364 | external_logic ().raise ();
|
---|
| 365 | return it;
|
---|
| 366 | }
|
---|
| 367 | // Form Unique Associative Container concept
|
---|
| 368 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 369 | std::pair<iterator,bool> insert (const value_type &p) {
|
---|
| 370 | iterator it = detail::lower_bound (begin (), end (), p, detail::less_pair<value_type> ());
|
---|
| 371 | if (it->first == p.first)
|
---|
| 372 | return std::make_pair (it, false);
|
---|
| 373 | difference_type n = it - begin ();
|
---|
| 374 | BOOST_UBLAS_CHECK (size () == 0 || size () == size_type (n), external_logic ());
|
---|
| 375 | resize (size () + 1);
|
---|
| 376 | it = begin () + n; // allow for invalidation
|
---|
| 377 | std::copy_backward (it, end () - 1, end ());
|
---|
| 378 | *it = p;
|
---|
| 379 | return std::make_pair (it, true);
|
---|
| 380 | }
|
---|
| 381 | // Form Sorted Associative Container concept
|
---|
| 382 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 383 | iterator insert (iterator hint, const value_type &p) {
|
---|
| 384 | return insert (p).first;
|
---|
| 385 | }
|
---|
| 386 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 387 | void erase (iterator it) {
|
---|
| 388 | BOOST_UBLAS_CHECK (begin () <= it && it < end (), bad_index ());
|
---|
| 389 | std::copy (it + 1, end (), it);
|
---|
| 390 | resize (size () - 1);
|
---|
| 391 | }
|
---|
| 392 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 393 | void erase (iterator it1, iterator it2) {
|
---|
| 394 | BOOST_UBLAS_CHECK (begin () <= it1 && it1 < it2 && it2 <= end (), bad_index ());
|
---|
| 395 | std::copy (it2, end (), it1);
|
---|
| 396 | resize (size () - (it2 - it1));
|
---|
| 397 | }
|
---|
| 398 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 399 | void clear () {
|
---|
| 400 | resize (0);
|
---|
| 401 | }
|
---|
| 402 |
|
---|
| 403 | // Element lookup
|
---|
| 404 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 405 | const_iterator find (key_type i) const {
|
---|
| 406 | const_iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
|
---|
| 407 | if (it == end () || it->first != i)
|
---|
| 408 | it = end ();
|
---|
| 409 | return it;
|
---|
| 410 | }
|
---|
| 411 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 412 | iterator find (key_type i) {
|
---|
| 413 | iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
|
---|
| 414 | if (it == end () || it->first != i)
|
---|
| 415 | it = end ();
|
---|
| 416 | return it;
|
---|
| 417 | }
|
---|
| 418 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 419 | const_iterator lower_bound (key_type i) const {
|
---|
| 420 | return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
|
---|
| 421 | }
|
---|
| 422 | // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
|
---|
| 423 | iterator lower_bound (key_type i) {
|
---|
| 424 | return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
|
---|
| 425 | }
|
---|
| 426 |
|
---|
| 427 | BOOST_UBLAS_INLINE
|
---|
| 428 | const_iterator begin () const {
|
---|
| 429 | return data_;
|
---|
| 430 | }
|
---|
| 431 | BOOST_UBLAS_INLINE
|
---|
| 432 | const_iterator end () const {
|
---|
| 433 | return data_ + size_;
|
---|
| 434 | }
|
---|
| 435 |
|
---|
| 436 | BOOST_UBLAS_INLINE
|
---|
| 437 | iterator begin () {
|
---|
| 438 | return data_;
|
---|
| 439 | }
|
---|
| 440 | BOOST_UBLAS_INLINE
|
---|
| 441 | iterator end () {
|
---|
| 442 | return data_ + size_;
|
---|
| 443 | }
|
---|
| 444 |
|
---|
| 445 | // Reverse iterators
|
---|
| 446 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
|
---|
| 447 | typedef std::reverse_iterator<iterator> reverse_iterator;
|
---|
| 448 |
|
---|
| 449 | BOOST_UBLAS_INLINE
|
---|
| 450 | const_reverse_iterator rbegin () const {
|
---|
| 451 | return const_reverse_iterator (end ());
|
---|
| 452 | }
|
---|
| 453 | BOOST_UBLAS_INLINE
|
---|
| 454 | const_reverse_iterator rend () const {
|
---|
| 455 | return const_reverse_iterator (begin ());
|
---|
| 456 | }
|
---|
| 457 | BOOST_UBLAS_INLINE
|
---|
| 458 | reverse_iterator rbegin () {
|
---|
| 459 | return reverse_iterator (end ());
|
---|
| 460 | }
|
---|
| 461 | BOOST_UBLAS_INLINE
|
---|
| 462 | reverse_iterator rend () {
|
---|
| 463 | return reverse_iterator (begin ());
|
---|
| 464 | }
|
---|
| 465 |
|
---|
| 466 | // Allocator
|
---|
| 467 | allocator_type get_allocator () {
|
---|
| 468 | return alloc_;
|
---|
| 469 | }
|
---|
| 470 |
|
---|
| 471 | private:
|
---|
| 472 | // Provide destroy as a non member function
|
---|
| 473 | BOOST_UBLAS_INLINE
|
---|
| 474 | static void static_destroy (reference p) {
|
---|
| 475 | (&p) -> ~value_type ();
|
---|
| 476 | }
|
---|
| 477 | ALLOC alloc_;
|
---|
| 478 | size_type capacity_;
|
---|
| 479 | pointer data_;
|
---|
| 480 | size_type size_;
|
---|
| 481 | };
|
---|
| 482 |
|
---|
| 483 |
|
---|
| 484 | namespace detail {
|
---|
| 485 | template<class A, class T>
|
---|
| 486 | struct map_traits {
|
---|
| 487 | typedef typename A::mapped_type &reference;
|
---|
| 488 | };
|
---|
| 489 | template<class I, class T, class ALLOC>
|
---|
| 490 | struct map_traits<map_array<I, T, ALLOC>, T > {
|
---|
| 491 | typedef typename map_array<I, T, ALLOC>::data_reference reference;
|
---|
| 492 | };
|
---|
| 493 |
|
---|
| 494 | // reserve helpers for map_array and generic maps
|
---|
| 495 | // ISSUE should be in map_traits but want to use on all compilers
|
---|
| 496 |
|
---|
| 497 | template<class M>
|
---|
| 498 | BOOST_UBLAS_INLINE
|
---|
| 499 | void map_reserve (M &/* m */, typename M::size_type /* capacity */) {
|
---|
| 500 | }
|
---|
| 501 | template<class I, class T, class ALLOC>
|
---|
| 502 | BOOST_UBLAS_INLINE
|
---|
| 503 | void map_reserve (map_array<I, T, ALLOC> &m, typename map_array<I, T, ALLOC>::size_type capacity) {
|
---|
| 504 | m.reserve (capacity);
|
---|
| 505 | }
|
---|
| 506 |
|
---|
| 507 | template<class M>
|
---|
| 508 | struct map_capacity_traits {
|
---|
| 509 | typedef typename M::size_type type ;
|
---|
| 510 | type operator() ( M const& m ) const {
|
---|
| 511 | return m.size ();
|
---|
| 512 | }
|
---|
| 513 | } ;
|
---|
| 514 |
|
---|
| 515 | template<class I, class T, class ALLOC>
|
---|
| 516 | struct map_capacity_traits< map_array<I, T, ALLOC> > {
|
---|
| 517 | typedef typename map_array<I, T, ALLOC>::size_type type ;
|
---|
| 518 | type operator() ( map_array<I, T, ALLOC> const& m ) const {
|
---|
| 519 | return m.capacity ();
|
---|
| 520 | }
|
---|
| 521 | } ;
|
---|
| 522 |
|
---|
| 523 | template<class M>
|
---|
| 524 | BOOST_UBLAS_INLINE
|
---|
| 525 | typename map_capacity_traits<M>::type map_capacity (M const& m) {
|
---|
| 526 | return map_capacity_traits<M>() ( m );
|
---|
| 527 | }
|
---|
| 528 | }
|
---|
| 529 |
|
---|
| 530 | }}}
|
---|
| 531 |
|
---|
| 532 | #endif
|
---|