ceph/src/boost/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     template<class I, class T, class ALLOC>
 199     class map_std : public std::map<I, T, std::less<I>, ALLOC> {
 200     public:
 201          // Serialization
 202         template<class Archive>
 203         void serialize(Archive & ar, const unsigned int /* file_version */){
 204             ar & serialization::make_nvp("base", boost::serialization::base_object< std::map<I, T, std::less<I>, ALLOC> >(*this));
 205         }
 206     };
 207
 208
 209
 210
 211     // Map array
 212     //  Implementation requires pair<I, T> allocator definition (without const)
 213     template<class I, class T, class ALLOC>
 214     class map_array {
 215     public:
 216         typedef ALLOC allocator_type;
 217         typedef typename ALLOC::size_type size_type;
 218         typedef typename ALLOC::difference_type difference_type;
 219         typedef std::pair<I,T> value_type;
 220         typedef I key_type;
 221         typedef T mapped_type;
 222         typedef const value_type &const_reference;
 223         typedef value_type &reference;
 224         typedef const value_type *const_pointer;
 225         typedef value_type *pointer;
 226         // Iterators simply are pointers.
 227         typedef const_pointer const_iterator;
 228         typedef pointer iterator;
 229
 230         typedef const T &data_const_reference;
 231 #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
 232         typedef T &data_reference;
 233 #else
 234         typedef sparse_storage_element<map_array> data_reference;
 235 #endif
 236
 237         // Construction and destruction
 238         BOOST_UBLAS_INLINE
 239         map_array (const ALLOC &a = ALLOC()):
 240             alloc_(a), capacity_ (0), size_ (0) {
 241                 data_ = 0;
 242         }
 243         BOOST_UBLAS_INLINE
 244         map_array (const map_array &c):
 245             alloc_ (c.alloc_), capacity_ (c.size_), size_ (c.size_) {
 246             if (capacity_) {
 247                 data_ = alloc_.allocate (capacity_);
 248                 std::uninitialized_copy (data_, data_ + capacity_, c.data_);
 249                 // capacity != size_ requires uninitialized_fill (size_ to capacity_)
 250             }
 251             else
 252                 data_ = 0;
 253         }
 254         BOOST_UBLAS_INLINE
 255         ~map_array () {
 256             if (capacity_) {
 257                 std::for_each (data_, data_ + capacity_, static_destroy);
 258                 alloc_.deallocate (data_, capacity_);
 259             }
 260         }
 261
 262     private:
 263         // Resizing - implicitly exposses uninitialized (but default constructed) mapped_type
 264         BOOST_UBLAS_INLINE
 265         void resize (size_type size) {
 266             BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
 267             if (size > capacity_) {
 268                 const size_type capacity = size << 1;
 269                 BOOST_UBLAS_CHECK (capacity, internal_logic ());
 270                 pointer data = alloc_.allocate (capacity);
 271                 std::uninitialized_copy (data_, data_ + (std::min) (size, size_), data);
 272                 std::uninitialized_fill (data + (std::min) (size, size_), data + capacity, value_type ());
 273
 274                 if (capacity_) {
 275                     std::for_each (data_, data_ + capacity_, static_destroy);
 276                     alloc_.deallocate (data_, capacity_);
 277                 }
 278                 capacity_ = capacity;
 279                 data_ = data;
 280             }
 281             size_ = size;
 282             BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
 283         }
 284     public:
 285
 286         // Reserving
 287         BOOST_UBLAS_INLINE
 288         void reserve (size_type capacity) {
 289             BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
 290             // Reduce capacity_ if size_ allows
 291             BOOST_UBLAS_CHECK (capacity >= size_, bad_size ());
 292             pointer data;
 293             if (capacity) {
 294                 data = alloc_.allocate (capacity);
 295                 std::uninitialized_copy (data_, data_ + size_, data);
 296                 std::uninitialized_fill (data + size_, data + capacity, value_type ());
 297             }
 298             else
 299                 data = 0;
 300
 301             if (capacity_) {
 302                 std::for_each (data_, data_ + capacity_, static_destroy);
 303                 alloc_.deallocate (data_, capacity_);
 304             }
 305             capacity_ = capacity;
 306             data_ = data;
 307             BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
 308         }
 309
 310         // Random Access Container
 311         BOOST_UBLAS_INLINE
 312         size_type size () const {
 313             return size_;
 314         }
 315         BOOST_UBLAS_INLINE
 316         size_type capacity () const {
 317             return capacity_;
 318         }
 319         BOOST_UBLAS_INLINE
 320         size_type max_size () const {
 321             return 0; //TODO
 322         }
 323
 324         BOOST_UBLAS_INLINE
 325         bool empty () const {
 326             return size_ == 0;
 327         }
 328
 329         // Element access
 330         BOOST_UBLAS_INLINE
 331         data_reference operator [] (key_type i) {
 332 #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
 333             pointer it = find (i);
 334             if (it == end ())
 335                 it = insert (end (), value_type (i, mapped_type (0)));
 336             BOOST_UBLAS_CHECK (it != end (), internal_logic ());
 337             return it->second;
 338 #else
 339             return data_reference (*this, i);
 340 #endif
 341         }
 342
 343         // Assignment
 344         BOOST_UBLAS_INLINE
 345         map_array &operator = (const map_array &a) {
 346             if (this != &a) {
 347                 resize (a.size_);
 348                 std::copy (a.data_, a.data_ + a.size_, data_);
 349             }
 350             return *this;
 351         }
 352         BOOST_UBLAS_INLINE
 353         map_array &assign_temporary (map_array &a) {
 354             swap (a);
 355             return *this;
 356         }
 357
 358         // Swapping
 359         BOOST_UBLAS_INLINE
 360         void swap (map_array &a) {
 361             if (this != &a) {
 362                 std::swap (capacity_, a.capacity_);
 363                 std::swap (data_, a.data_);
 364                 std::swap (size_, a.size_);
 365             }
 366         }
 367         BOOST_UBLAS_INLINE
 368         friend void swap (map_array &a1, map_array &a2) {
 369             a1.swap (a2);
 370         }
 371
 372         // Element insertion and deletion
 373
 374         // From Back Insertion Sequence concept
 375         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 376         iterator push_back (iterator it, const value_type &p) {
 377             if (size () == 0 || (it = end () - 1)->first < p.first) {
 378                 resize (size () + 1);
 379                 *(it = end () - 1) = p;
 380                 return it;
 381             }
 382             external_logic ().raise ();
 383             return it;
 384         }
 385         // Form Unique Associative Container concept
 386         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 387         std::pair<iterator,bool> insert (const value_type &p) {
 388             iterator it = detail::lower_bound (begin (), end (), p, detail::less_pair<value_type> ());
 389             if (it != end () && it->first == p.first)
 390                 return std::make_pair (it, false);
 391             difference_type n = it - begin ();
 392             resize (size () + 1);
 393             it = begin () + n;    // allow for invalidation
 394             std::copy_backward (it, end () - 1, end ());
 395             *it = p;
 396             return std::make_pair (it, true);
 397         }
 398         // Form Sorted Associative Container concept
 399         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 400                                 iterator insert (iterator /*hint*/, const value_type &p) {
 401             return insert (p).first;
 402         }
 403         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 404         void erase (iterator it) {
 405             BOOST_UBLAS_CHECK (begin () <= it && it < end (), bad_index ());
 406             std::copy (it + 1, end (), it);
 407             resize (size () - 1);
 408         }
 409         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 410         void erase (iterator it1, iterator it2) {
 411             if (it1 == it2) return /* nothing to erase */;
 412             BOOST_UBLAS_CHECK (begin () <= it1 && it1 < it2 && it2 <= end (), bad_index ());
 413             std::copy (it2, end (), it1);
 414             resize (size () - (it2 - it1));
 415         }
 416         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 417         void clear () {
 418             resize (0);
 419         }
 420
 421         // Element lookup
 422         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 423         const_iterator find (key_type i) const {
 424             const_iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
 425             if (it == end () || it->first != i)
 426                 it = end ();
 427             return it;
 428         }
 429         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 430         iterator find (key_type i) {
 431             iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
 432             if (it == end () || it->first != i)
 433                 it = end ();
 434             return it;
 435         }
 436         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 437         const_iterator lower_bound (key_type i) const {
 438             return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
 439         }
 440         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
 441         iterator lower_bound (key_type i) {
 442             return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
 443         }
 444
 445         BOOST_UBLAS_INLINE
 446         const_iterator begin () const {
 447             return data_;
 448         }
 449         BOOST_UBLAS_INLINE
 450         const_iterator cbegin () const {
 451             return begin ();
 452         }
 453         BOOST_UBLAS_INLINE
 454         const_iterator end () const {
 455             return data_ + size_;
 456         }
 457         BOOST_UBLAS_INLINE
 458         const_iterator cend () const {
 459             return end ();
 460         }
 461
 462         BOOST_UBLAS_INLINE
 463         iterator begin () {
 464             return data_;
 465         }
 466         BOOST_UBLAS_INLINE
 467         iterator end () {
 468             return data_ + size_;
 469         }
 470
 471         // Reverse iterators
 472         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 473         typedef std::reverse_iterator<iterator> reverse_iterator;
 474
 475         BOOST_UBLAS_INLINE
 476         const_reverse_iterator rbegin () const {
 477             return const_reverse_iterator (end ());
 478         }
 479         BOOST_UBLAS_INLINE
 480         const_reverse_iterator crbegin () const {
 481             return rbegin ();
 482         }
 483         BOOST_UBLAS_INLINE
 484         const_reverse_iterator rend () const {
 485             return const_reverse_iterator (begin ());
 486         }
 487         BOOST_UBLAS_INLINE
 488         const_reverse_iterator crend () const {
 489             return rend ();
 490         }
 491
 492         BOOST_UBLAS_INLINE
 493         reverse_iterator rbegin () {
 494             return reverse_iterator (end ());
 495         }
 496         BOOST_UBLAS_INLINE
 497         reverse_iterator rend () {
 498             return reverse_iterator (begin ());
 499         }
 500
 501         // Allocator
 502         allocator_type get_allocator () {
 503             return alloc_;
 504         }
 505
 506          // Serialization
 507         template<class Archive>
 508         void serialize(Archive & ar, const unsigned int /* file_version */){
 509             serialization::collection_size_type s (size_);
 510             ar & serialization::make_nvp("size",s);
 511             if (Archive::is_loading::value) {
 512                 resize(s);
 513             }
 514             ar & serialization::make_array(data_, s);
 515         }
 516
 517     private:
 518         // Provide destroy as a non member function
 519         BOOST_UBLAS_INLINE
 520         static void static_destroy (reference p) {
 521             (&p) -> ~value_type ();
 522         }
 523         ALLOC alloc_;
 524         size_type capacity_;
 525         pointer data_;
 526         size_type size_;
 527     };
 528
 529
 530     namespace detail {
 531         template<class A, class T>
 532         struct map_traits {
 533             typedef typename A::mapped_type &reference;
 534         };
 535         template<class I, class T, class ALLOC>
 536         struct map_traits<map_array<I, T, ALLOC>, T > {
 537             typedef typename map_array<I, T, ALLOC>::data_reference reference;
 538         };
 539
 540         // reserve helpers for map_array and generic maps
 541         // ISSUE should be in map_traits but want to use on all compilers
 542
 543         template<class M>
 544         BOOST_UBLAS_INLINE
 545         void map_reserve (M &/* m */, typename M::size_type /* capacity */) {
 546         }
 547         template<class I, class T, class ALLOC>
 548         BOOST_UBLAS_INLINE
 549         void map_reserve (map_array<I, T, ALLOC> &m, typename map_array<I, T, ALLOC>::size_type capacity) {
 550             m.reserve (capacity);
 551         }
 552
 553         template<class M>
 554         struct map_capacity_traits {
 555             typedef typename M::size_type type ;
 556             type operator() ( M const& m ) const {
 557                return m.size ();
 558             }
 559         } ;
 560
 561         template<class I, class T, class ALLOC>
 562         struct map_capacity_traits< map_array<I, T, ALLOC> > {
 563             typedef typename map_array<I, T, ALLOC>::size_type type ;
 564             type operator() ( map_array<I, T, ALLOC> const& m ) const {
 565                return m.capacity ();
 566             }
 567         } ;
 568
 569         template<class M>
 570         BOOST_UBLAS_INLINE
 571         typename map_capacity_traits<M>::type map_capacity (M const& m) {
 572             return map_capacity_traits<M>() ( m );
 573         }
 574     }
 575
 576 }}}
 577
 578 #endif