boost/numeric/ublas/storage_sparse.hpp

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