- Main Page
- Related Pages
- Classes
- Files

- File List

# vector_sparse.hpp

    00001 //
    00002 //  Copyright (c) 2000-2002
    00003 //  Joerg Walter, Mathias Koch
    00004 //
    00005 //  Distributed under the Boost Software License, Version 1.0. (See
    00006 //  accompanying file LICENSE_1_0.txt or copy at
    00007 //  http://www.boost.org/LICENSE_1_0.txt)
    00008 //
    00009 //  The authors gratefully acknowledge the support of
    00010 //  GeNeSys mbH & Co. KG in producing this work.
    00011 //
    00012
    00013 #ifndef _BOOST_UBLAS_VECTOR_SPARSE_
    00014 #define _BOOST_UBLAS_VECTOR_SPARSE_
    00015
    00016 #include <boost/numeric/ublas/storage_sparse.hpp>
    00017 #include <boost/numeric/ublas/vector_expression.hpp>
    00018 #include <boost/numeric/ublas/detail/vector_assign.hpp>
    00019 #if BOOST_UBLAS_TYPE_CHECK
    00020 #include <boost/numeric/ublas/vector.hpp>
    00021 #endif
    00022
    00023 // Iterators based on ideas of Jeremy Siek
    00024
    00025 namespace boost { namespace numeric { namespace ublas {
    00026
    00027 #ifdef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    00028
    00029     template<class V>
    00030     class sparse_vector_element:
    00031        public container_reference<V> {
    00032     public:
    00033         typedef V vector_type;
    00034         typedef typename V::size_type size_type;
    00035         typedef typename V::value_type value_type;
    00036         typedef const value_type &const_reference;
    00037         typedef value_type *pointer;
    00038
    00039     private:
    00040         // Proxied element operations
    00041         void get_d () const {
    00042             pointer p = (*this) ().find_element (i_);
    00043             if (p)
    00044                 d_ = *p;
    00045             else
    00046                 d_ = value_type/*zero*/();
    00047         }
    00048
    00049         void set (const value_type &s) const {
    00050             pointer p = (*this) ().find_element (i_);
    00051             if (!p)
    00052                 (*this) ().insert_element (i_, s);
    00053             else
    00054                 *p = s;
    00055         }
    00056
    00057     public:
    00058         // Construction and destruction
    00059         sparse_vector_element (vector_type &v, size_type i):
    00060             container_reference<vector_type> (v), i_ (i) {
    00061         }
    00062         BOOST_UBLAS_INLINE
    00063         sparse_vector_element (const sparse_vector_element &p):
    00064             container_reference<vector_type> (p), i_ (p.i_) {}
    00065         BOOST_UBLAS_INLINE
    00066         ~sparse_vector_element () {
    00067         }
    00068
    00069         // Assignment
    00070         BOOST_UBLAS_INLINE
    00071         sparse_vector_element &operator = (const sparse_vector_element &p) {
    00072             // Overide the implict copy assignment
    00073             p.get_d ();
    00074             set (p.d_);
    00075             return *this;
    00076         }
    00077         template<class D>
    00078         BOOST_UBLAS_INLINE
    00079         sparse_vector_element &operator = (const D &d) {
    00080             set (d);
    00081             return *this;
    00082         }
    00083         template<class D>
    00084         BOOST_UBLAS_INLINE
    00085         sparse_vector_element &operator += (const D &d) {
    00086             get_d ();
    00087             d_ += d;
    00088             set (d_);
    00089             return *this;
    00090         }
    00091         template<class D>
    00092         BOOST_UBLAS_INLINE
    00093         sparse_vector_element &operator -= (const D &d) {
    00094             get_d ();
    00095             d_ -= d;
    00096             set (d_);
    00097             return *this;
    00098         }
    00099         template<class D>
    00100         BOOST_UBLAS_INLINE
    00101         sparse_vector_element &operator *= (const D &d) {
    00102             get_d ();
    00103             d_ *= d;
    00104             set (d_);
    00105             return *this;
    00106         }
    00107         template<class D>
    00108         BOOST_UBLAS_INLINE
    00109         sparse_vector_element &operator /= (const D &d) {
    00110             get_d ();
    00111             d_ /= d;
    00112             set (d_);
    00113             return *this;
    00114         }
    00115
    00116         // Comparison
    00117         template<class D>
    00118         BOOST_UBLAS_INLINE
    00119         bool operator == (const D &d) const {
    00120             get_d ();
    00121             return d_ == d;
    00122         }
    00123         template<class D>
    00124         BOOST_UBLAS_INLINE
    00125         bool operator != (const D &d) const {
    00126             get_d ();
    00127             return d_ != d;
    00128         }
    00129
    00130         // Conversion - weak link in proxy as d_ is not a perfect alias for the element
    00131         BOOST_UBLAS_INLINE
    00132         operator const_reference () const {
    00133             get_d ();
    00134             return d_;
    00135         }
    00136
    00137         // Conversion to reference - may be invalidated
    00138         BOOST_UBLAS_INLINE
    00139         value_type& ref () const {
    00140             const pointer p = (*this) ().find_element (i_);
    00141             if (!p)
    00142                 return (*this) ().insert_element (i_, value_type/*zero*/());
    00143             else
    00144                 return *p;
    00145         }
    00146
    00147     private:
    00148         size_type i_;
    00149         mutable value_type d_;
    00150     };
    00151
    00152     /*
    00153      * Generalise explicit reference access
    00154      */
    00155     namespace detail {
    00156         template <class R>
    00157         struct element_reference {
    00158             typedef R& reference;
    00159             static reference get_reference (reference r)
    00160             {
    00161                 return r;
    00162             }
    00163         };
    00164         template <class V>
    00165         struct element_reference<sparse_vector_element<V> > {
    00166             typedef typename V::value_type& reference;
    00167             static reference get_reference (const sparse_vector_element<V>& sve)
    00168             {
    00169                 return sve.ref ();
    00170             }
    00171         };
    00172     }
    00173     template <class VER>
    00174     typename detail::element_reference<VER>::reference ref (VER& ver) {
    00175         return detail::element_reference<VER>::get_reference (ver);
    00176     }
    00177     template <class VER>
    00178     typename detail::element_reference<VER>::reference ref (const VER& ver) {
    00179         return detail::element_reference<VER>::get_reference (ver);
    00180     }
    00181
    00182
    00183     template<class V>
    00184     struct type_traits<sparse_vector_element<V> > {
    00185         typedef typename V::value_type element_type;
    00186         typedef type_traits<sparse_vector_element<V> > self_type;
    00187         typedef typename type_traits<element_type>::value_type value_type;
    00188         typedef typename type_traits<element_type>::const_reference const_reference;
    00189         typedef sparse_vector_element<V> reference;
    00190         typedef typename type_traits<element_type>::real_type real_type;
    00191         typedef typename type_traits<element_type>::precision_type precision_type;
    00192
    00193         static const unsigned plus_complexity = type_traits<element_type>::plus_complexity;
    00194         static const unsigned multiplies_complexity = type_traits<element_type>::multiplies_complexity;
    00195
    00196         static
    00197         BOOST_UBLAS_INLINE
    00198         real_type real (const_reference t) {
    00199             return type_traits<element_type>::real (t);
    00200         }
    00201         static
    00202         BOOST_UBLAS_INLINE
    00203         real_type imag (const_reference t) {
    00204             return type_traits<element_type>::imag (t);
    00205         }
    00206         static
    00207         BOOST_UBLAS_INLINE
    00208         value_type conj (const_reference t) {
    00209             return type_traits<element_type>::conj (t);
    00210         }
    00211
    00212         static
    00213         BOOST_UBLAS_INLINE
    00214         real_type type_abs (const_reference t) {
    00215             return type_traits<element_type>::type_abs (t);
    00216         }
    00217         static
    00218         BOOST_UBLAS_INLINE
    00219         value_type type_sqrt (const_reference t) {
    00220             return type_traits<element_type>::type_sqrt (t);
    00221         }
    00222
    00223         static
    00224         BOOST_UBLAS_INLINE
    00225         real_type norm_1 (const_reference t) {
    00226             return type_traits<element_type>::norm_1 (t);
    00227         }
    00228         static
    00229         BOOST_UBLAS_INLINE
    00230         real_type norm_2 (const_reference t) {
    00231             return type_traits<element_type>::norm_2 (t);
    00232         }
    00233         static
    00234         BOOST_UBLAS_INLINE
    00235         real_type norm_inf (const_reference t) {
    00236             return type_traits<element_type>::norm_inf (t);
    00237         }
    00238
    00239         static
    00240         BOOST_UBLAS_INLINE
    00241         bool equals (const_reference t1, const_reference t2) {
    00242             return type_traits<element_type>::equals (t1, t2);
    00243         }
    00244     };
    00245
    00246     template<class V1, class T2>
    00247     struct promote_traits<sparse_vector_element<V1>, T2> {
    00248         typedef typename promote_traits<typename sparse_vector_element<V1>::value_type, T2>::promote_type promote_type;
    00249     };
    00250     template<class T1, class V2>
    00251     struct promote_traits<T1, sparse_vector_element<V2> > {
    00252         typedef typename promote_traits<T1, typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
    00253     };
    00254     template<class V1, class V2>
    00255     struct promote_traits<sparse_vector_element<V1>, sparse_vector_element<V2> > {
    00256         typedef typename promote_traits<typename sparse_vector_element<V1>::value_type,
    00257                                         typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
    00258     };
    00259
    00260 #endif
    00261
    00262
    00279     template<class T, class A>
    00280     class mapped_vector:
    00281         public vector_container<mapped_vector<T, A> > {
    00282
    00283         typedef T &true_reference;
    00284         typedef T *pointer;
    00285         typedef const T *const_pointer;
    00286         typedef mapped_vector<T, A> self_type;
    00287     public:
    00288 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
    00289         using vector_container<self_type>::operator ();
    00290 #endif
    00291         typedef typename A::size_type size_type;
    00292         typedef typename A::difference_type difference_type;
    00293         typedef T value_type;
    00294         typedef A array_type;
    00295         typedef const value_type &const_reference;
    00296 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    00297         typedef typename detail::map_traits<A,T>::reference reference;
    00298 #else
    00299         typedef sparse_vector_element<self_type> reference;
    00300 #endif
    00301         typedef const vector_reference<const self_type> const_closure_type;
    00302         typedef vector_reference<self_type> closure_type;
    00303         typedef self_type vector_temporary_type;
    00304         typedef sparse_tag storage_category;
    00305
    00306         // Construction and destruction
    00307         BOOST_UBLAS_INLINE
    00308         mapped_vector ():
    00309             vector_container<self_type> (),
    00310             size_ (0), data_ () {}
    00311         BOOST_UBLAS_INLINE
    00312         mapped_vector (size_type size, size_type non_zeros = 0):
    00313             vector_container<self_type> (),
    00314             size_ (size), data_ () {
    00315             detail::map_reserve (data(), restrict_capacity (non_zeros));
    00316         }
    00317         BOOST_UBLAS_INLINE
    00318         mapped_vector (const mapped_vector &v):
    00319             vector_container<self_type> (),
    00320             size_ (v.size_), data_ (v.data_) {}
    00321         template<class AE>
    00322         BOOST_UBLAS_INLINE
    00323         mapped_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
    00324             vector_container<self_type> (),
    00325             size_ (ae ().size ()), data_ () {
    00326             detail::map_reserve (data(), restrict_capacity (non_zeros));
    00327             vector_assign<scalar_assign> (*this, ae);
    00328         }
    00329
    00330         // Accessors
    00331         BOOST_UBLAS_INLINE
    00332         size_type size () const {
    00333             return size_;
    00334         }
    00335         BOOST_UBLAS_INLINE
    00336         size_type nnz_capacity () const {
    00337             return detail::map_capacity (data ());
    00338         }
    00339         BOOST_UBLAS_INLINE
    00340         size_type nnz () const {
    00341             return data (). size ();
    00342         }
    00343
    00344         // Storage accessors
    00345         BOOST_UBLAS_INLINE
    00346         const array_type &data () const {
    00347             return data_;
    00348         }
    00349         BOOST_UBLAS_INLINE
    00350         array_type &data () {
    00351             return data_;
    00352         }
    00353
    00354         // Resizing
    00355     private:
    00356         BOOST_UBLAS_INLINE
    00357         size_type restrict_capacity (size_type non_zeros) const {
    00358             non_zeros = (std::min) (non_zeros, size_);
    00359             return non_zeros;
    00360         }
    00361     public:
    00362         BOOST_UBLAS_INLINE
    00363         void resize (size_type size, bool preserve = true) {
    00364             size_ = size;
    00365             if (preserve) {
    00366                 data ().erase (data ().lower_bound(size_), data ().end());
    00367             }
    00368             else {
    00369                 data ().clear ();
    00370             }
    00371         }
    00372
    00373         // Reserving
    00374         BOOST_UBLAS_INLINE
    00375         void reserve (size_type non_zeros = 0, bool preserve = true) {
    00376             detail::map_reserve (data (), restrict_capacity (non_zeros));
    00377         }
    00378
    00379         // Element support
    00380         BOOST_UBLAS_INLINE
    00381         pointer find_element (size_type i) {
    00382             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
    00383         }
    00384         BOOST_UBLAS_INLINE
    00385         const_pointer find_element (size_type i) const {
    00386             const_subiterator_type it (data ().find (i));
    00387             if (it == data ().end ())
    00388                 return 0;
    00389             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
    00390             return &(*it).second;
    00391         }
    00392
    00393         // Element access
    00394         BOOST_UBLAS_INLINE
    00395         const_reference operator () (size_type i) const {
    00396             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00397             const_subiterator_type it (data ().find (i));
    00398             if (it == data ().end ())
    00399                 return zero_;
    00400             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
    00401             return (*it).second;
    00402         }
    00403         BOOST_UBLAS_INLINE
    00404         true_reference ref (size_type i) {
    00405             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00406             std::pair<subiterator_type, bool> ii (data ().insert (typename array_type::value_type (i, value_type/*zero*/())));
    00407             BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ());   // broken map
    00408             return (ii.first)->second;
    00409         }
    00410         BOOST_UBLAS_INLINE
    00411         reference operator () (size_type i) {
    00412 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    00413             return ref (i);
    00414 #else
    00415             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00416             return reference (*this, i);
    00417 #endif
    00418         }
    00419
    00420         BOOST_UBLAS_INLINE
    00421         const_reference operator [] (size_type i) const {
    00422             return (*this) (i);
    00423         }
    00424         BOOST_UBLAS_INLINE
    00425         reference operator [] (size_type i) {
    00426             return (*this) (i);
    00427         }
    00428
    00429         // Element assignment
    00430         BOOST_UBLAS_INLINE
    00431         true_reference insert_element (size_type i, const_reference t) {
    00432             std::pair<subiterator_type, bool> ii = data ().insert (typename array_type::value_type (i, t));
    00433             BOOST_UBLAS_CHECK (ii.second, bad_index ());        // duplicate element
    00434             BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ());   // broken map
    00435             if (!ii.second)     // existing element
    00436                 (ii.first)->second = t;
    00437             return (ii.first)->second;
    00438         }
    00439         BOOST_UBLAS_INLINE
    00440         void erase_element (size_type i) {
    00441             subiterator_type it = data ().find (i);
    00442             if (it == data ().end ())
    00443                 return;
    00444             data ().erase (it);
    00445         }
    00446
    00447         // Zeroing
    00448         BOOST_UBLAS_INLINE
    00449         void clear () {
    00450             data ().clear ();
    00451         }
    00452
    00453         // Assignment
    00454         BOOST_UBLAS_INLINE
    00455         mapped_vector &operator = (const mapped_vector &v) {
    00456             if (this != &v) {
    00457                 size_ = v.size_;
    00458                 data () = v.data ();
    00459             }
    00460             return *this;
    00461         }
    00462         template<class C>          // Container assignment without temporary
    00463         BOOST_UBLAS_INLINE
    00464         mapped_vector &operator = (const vector_container<C> &v) {
    00465             resize (v ().size (), false);
    00466             assign (v);
    00467             return *this;
    00468         }
    00469         BOOST_UBLAS_INLINE
    00470         mapped_vector &assign_temporary (mapped_vector &v) {
    00471             swap (v);
    00472             return *this;
    00473         }
    00474         template<class AE>
    00475         BOOST_UBLAS_INLINE
    00476         mapped_vector &operator = (const vector_expression<AE> &ae) {
    00477             self_type temporary (ae, detail::map_capacity (data()));
    00478             return assign_temporary (temporary);
    00479         }
    00480         template<class AE>
    00481         BOOST_UBLAS_INLINE
    00482         mapped_vector &assign (const vector_expression<AE> &ae) {
    00483             vector_assign<scalar_assign> (*this, ae);
    00484             return *this;
    00485         }
    00486
    00487         // Computed assignment
    00488         template<class AE>
    00489         BOOST_UBLAS_INLINE
    00490         mapped_vector &operator += (const vector_expression<AE> &ae) {
    00491             self_type temporary (*this + ae, detail::map_capacity (data()));
    00492             return assign_temporary (temporary);
    00493         }
    00494         template<class C>          // Container assignment without temporary
    00495         BOOST_UBLAS_INLINE
    00496         mapped_vector &operator += (const vector_container<C> &v) {
    00497             plus_assign (v);
    00498             return *this;
    00499         }
    00500         template<class AE>
    00501         BOOST_UBLAS_INLINE
    00502         mapped_vector &plus_assign (const vector_expression<AE> &ae) {
    00503             vector_assign<scalar_plus_assign> (*this, ae);
    00504             return *this;
    00505         }
    00506         template<class AE>
    00507         BOOST_UBLAS_INLINE
    00508         mapped_vector &operator -= (const vector_expression<AE> &ae) {
    00509             self_type temporary (*this - ae, detail::map_capacity (data()));
    00510             return assign_temporary (temporary);
    00511         }
    00512         template<class C>          // Container assignment without temporary
    00513         BOOST_UBLAS_INLINE
    00514         mapped_vector &operator -= (const vector_container<C> &v) {
    00515             minus_assign (v);
    00516             return *this;
    00517         }
    00518         template<class AE>
    00519         BOOST_UBLAS_INLINE
    00520         mapped_vector &minus_assign (const vector_expression<AE> &ae) {
    00521             vector_assign<scalar_minus_assign> (*this, ae);
    00522             return *this;
    00523         }
    00524         template<class AT>
    00525         BOOST_UBLAS_INLINE
    00526         mapped_vector &operator *= (const AT &at) {
    00527             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
    00528             return *this;
    00529         }
    00530         template<class AT>
    00531         BOOST_UBLAS_INLINE
    00532         mapped_vector &operator /= (const AT &at) {
    00533             vector_assign_scalar<scalar_divides_assign> (*this, at);
    00534             return *this;
    00535         }
    00536
    00537         // Swapping
    00538         BOOST_UBLAS_INLINE
    00539         void swap (mapped_vector &v) {
    00540             if (this != &v) {
    00541                 std::swap (size_, v.size_);
    00542                 data ().swap (v.data ());
    00543             }
    00544         }
    00545         BOOST_UBLAS_INLINE
    00546         friend void swap (mapped_vector &v1, mapped_vector &v2) {
    00547             v1.swap (v2);
    00548         }
    00549
    00550         // Iterator types
    00551     private:
    00552         // Use storage iterator
    00553         typedef typename A::const_iterator const_subiterator_type;
    00554         typedef typename A::iterator subiterator_type;
    00555
    00556         BOOST_UBLAS_INLINE
    00557         true_reference at_element (size_type i) {
    00558             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00559             subiterator_type it (data ().find (i));
    00560             BOOST_UBLAS_CHECK (it != data ().end(), bad_index ());
    00561             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
    00562             return it->second;
    00563         }
    00564
    00565     public:
    00566         class const_iterator;
    00567         class iterator;
    00568
    00569         // Element lookup
    00570         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    00571         const_iterator find (size_type i) const {
    00572             return const_iterator (*this, data ().lower_bound (i));
    00573         }
    00574         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    00575         iterator find (size_type i) {
    00576             return iterator (*this, data ().lower_bound (i));
    00577         }
    00578
    00579
    00580         class const_iterator:
    00581             public container_const_reference<mapped_vector>,
    00582             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    00583                                                const_iterator, value_type> {
    00584         public:
    00585             typedef typename mapped_vector::value_type value_type;
    00586             typedef typename mapped_vector::difference_type difference_type;
    00587             typedef typename mapped_vector::const_reference reference;
    00588             typedef const typename mapped_vector::pointer pointer;
    00589
    00590             // Construction and destruction
    00591             BOOST_UBLAS_INLINE
    00592             const_iterator ():
    00593                 container_const_reference<self_type> (), it_ () {}
    00594             BOOST_UBLAS_INLINE
    00595             const_iterator (const self_type &v, const const_subiterator_type &it):
    00596                 container_const_reference<self_type> (v), it_ (it) {}
    00597             BOOST_UBLAS_INLINE
    00598             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
    00599                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
    00600
    00601             // Arithmetic
    00602             BOOST_UBLAS_INLINE
    00603             const_iterator &operator ++ () {
    00604                 ++ it_;
    00605                 return *this;
    00606             }
    00607             BOOST_UBLAS_INLINE
    00608             const_iterator &operator -- () {
    00609                 -- it_;
    00610                 return *this;
    00611             }
    00612
    00613             // Dereference
    00614             BOOST_UBLAS_INLINE
    00615             const_reference operator * () const {
    00616                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    00617                 return (*it_).second;
    00618             }
    00619
    00620             // Index
    00621             BOOST_UBLAS_INLINE
    00622             size_type index () const {
    00623                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    00624                 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
    00625                 return (*it_).first;
    00626             }
    00627
    00628             // Assignment
    00629             BOOST_UBLAS_INLINE
    00630             const_iterator &operator = (const const_iterator &it) {
    00631                 container_const_reference<self_type>::assign (&it ());
    00632                 it_ = it.it_;
    00633                 return *this;
    00634             }
    00635
    00636             // Comparison
    00637             BOOST_UBLAS_INLINE
    00638             bool operator == (const const_iterator &it) const {
    00639                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    00640                 return it_ == it.it_;
    00641             }
    00642
    00643         private:
    00644             const_subiterator_type it_;
    00645         };
    00646
    00647         BOOST_UBLAS_INLINE
    00648         const_iterator begin () const {
    00649             return const_iterator (*this, data ().begin ());
    00650         }
    00651         BOOST_UBLAS_INLINE
    00652         const_iterator end () const {
    00653             return const_iterator (*this, data ().end ());
    00654         }
    00655
    00656         class iterator:
    00657             public container_reference<mapped_vector>,
    00658             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    00659                                                iterator, value_type> {
    00660         public:
    00661             typedef typename mapped_vector::value_type value_type;
    00662             typedef typename mapped_vector::difference_type difference_type;
    00663             typedef typename mapped_vector::true_reference reference;
    00664             typedef typename mapped_vector::pointer pointer;
    00665
    00666             // Construction and destruction
    00667             BOOST_UBLAS_INLINE
    00668             iterator ():
    00669                 container_reference<self_type> (), it_ () {}
    00670             BOOST_UBLAS_INLINE
    00671             iterator (self_type &v, const subiterator_type &it):
    00672                 container_reference<self_type> (v), it_ (it) {}
    00673
    00674             // Arithmetic
    00675             BOOST_UBLAS_INLINE
    00676             iterator &operator ++ () {
    00677                 ++ it_;
    00678                 return *this;
    00679             }
    00680             BOOST_UBLAS_INLINE
    00681             iterator &operator -- () {
    00682                 -- it_;
    00683                 return *this;
    00684             }
    00685
    00686             // Dereference
    00687             BOOST_UBLAS_INLINE
    00688             reference operator * () const {
    00689                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    00690                 return (*it_).second;
    00691             }
    00692
    00693             // Index
    00694             BOOST_UBLAS_INLINE
    00695             size_type index () const {
    00696                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    00697                 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
    00698                 return (*it_).first;
    00699             }
    00700
    00701             // Assignment
    00702             BOOST_UBLAS_INLINE
    00703             iterator &operator = (const iterator &it) {
    00704                 container_reference<self_type>::assign (&it ());
    00705                 it_ = it.it_;
    00706                 return *this;
    00707             }
    00708
    00709             // Comparison
    00710             BOOST_UBLAS_INLINE
    00711             bool operator == (const iterator &it) const {
    00712                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    00713                 return it_ == it.it_;
    00714             }
    00715
    00716         private:
    00717             subiterator_type it_;
    00718
    00719             friend class const_iterator;
    00720         };
    00721
    00722         BOOST_UBLAS_INLINE
    00723         iterator begin () {
    00724             return iterator (*this, data ().begin ());
    00725         }
    00726         BOOST_UBLAS_INLINE
    00727         iterator end () {
    00728             return iterator (*this, data ().end ());
    00729         }
    00730
    00731         // Reverse iterator
    00732         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
    00733         typedef reverse_iterator_base<iterator> reverse_iterator;
    00734
    00735         BOOST_UBLAS_INLINE
    00736         const_reverse_iterator rbegin () const {
    00737             return const_reverse_iterator (end ());
    00738         }
    00739         BOOST_UBLAS_INLINE
    00740         const_reverse_iterator rend () const {
    00741             return const_reverse_iterator (begin ());
    00742         }
    00743         BOOST_UBLAS_INLINE
    00744         reverse_iterator rbegin () {
    00745             return reverse_iterator (end ());
    00746         }
    00747         BOOST_UBLAS_INLINE
    00748         reverse_iterator rend () {
    00749             return reverse_iterator (begin ());
    00750         }
    00751
    00752          // Serialization
    00753         template<class Archive>
    00754         void serialize(Archive & ar, const unsigned int /* file_version */){
    00755             serialization::collection_size_type s (size_);
    00756             ar & serialization::make_nvp("size",s);
    00757             if (Archive::is_loading::value) {
    00758                 size_ = s;
    00759             }
    00760             ar & serialization::make_nvp("data", data_);
    00761         }
    00762
    00763     private:
    00764         size_type size_;
    00765         array_type data_;
    00766         static const value_type zero_;
    00767     };
    00768
    00769     template<class T, class A>
    00770     const typename mapped_vector<T, A>::value_type mapped_vector<T, A>::zero_ = value_type/*zero*/();
    00771
    00772
    00773     // Thanks to Kresimir Fresl for extending this to cover different index bases.
    00774
    00796     template<class T, std::size_t IB, class IA, class TA>
    00797     class compressed_vector:
    00798         public vector_container<compressed_vector<T, IB, IA, TA> > {
    00799
    00800         typedef T &true_reference;
    00801         typedef T *pointer;
    00802         typedef const T *const_pointer;
    00803         typedef compressed_vector<T, IB, IA, TA> self_type;
    00804     public:
    00805 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
    00806         using vector_container<self_type>::operator ();
    00807 #endif
    00808         // ISSUE require type consistency check
    00809         // is_convertable (IA::size_type, TA::size_type)
    00810         typedef typename IA::value_type size_type;
    00811         typedef typename IA::difference_type difference_type;
    00812         typedef T value_type;
    00813         typedef const T &const_reference;
    00814 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    00815         typedef T &reference;
    00816 #else
    00817         typedef sparse_vector_element<self_type> reference;
    00818 #endif
    00819         typedef IA index_array_type;
    00820         typedef TA value_array_type;
    00821         typedef const vector_reference<const self_type> const_closure_type;
    00822         typedef vector_reference<self_type> closure_type;
    00823         typedef self_type vector_temporary_type;
    00824         typedef sparse_tag storage_category;
    00825
    00826         // Construction and destruction
    00827         BOOST_UBLAS_INLINE
    00828         compressed_vector ():
    00829             vector_container<self_type> (),
    00830             size_ (0), capacity_ (restrict_capacity (0)), filled_ (0),
    00831             index_data_ (capacity_), value_data_ (capacity_) {
    00832             storage_invariants ();
    00833         }
    00834         explicit BOOST_UBLAS_INLINE
    00835         compressed_vector (size_type size, size_type non_zeros = 0):
    00836             vector_container<self_type> (),
    00837             size_ (size), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
    00838             index_data_ (capacity_), value_data_ (capacity_) {
    00839         storage_invariants ();
    00840         }
    00841         BOOST_UBLAS_INLINE
    00842         compressed_vector (const compressed_vector &v):
    00843             vector_container<self_type> (),
    00844             size_ (v.size_), capacity_ (v.capacity_), filled_ (v.filled_),
    00845             index_data_ (v.index_data_), value_data_ (v.value_data_) {
    00846             storage_invariants ();
    00847         }
    00848         template<class AE>
    00849         BOOST_UBLAS_INLINE
    00850         compressed_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
    00851             vector_container<self_type> (),
    00852             size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
    00853             index_data_ (capacity_), value_data_ (capacity_) {
    00854             storage_invariants ();
    00855             vector_assign<scalar_assign> (*this, ae);
    00856         }
    00857
    00858         // Accessors
    00859         BOOST_UBLAS_INLINE
    00860         size_type size () const {
    00861             return size_;
    00862         }
    00863         BOOST_UBLAS_INLINE
    00864         size_type nnz_capacity () const {
    00865             return capacity_;
    00866         }
    00867         BOOST_UBLAS_INLINE
    00868         size_type nnz () const {
    00869             return filled_;
    00870         }
    00871
    00872         // Storage accessors
    00873         BOOST_UBLAS_INLINE
    00874         static size_type index_base () {
    00875             return IB;
    00876         }
    00877         BOOST_UBLAS_INLINE
    00878         typename index_array_type::size_type filled () const {
    00879             return filled_;
    00880         }
    00881         BOOST_UBLAS_INLINE
    00882         const index_array_type &index_data () const {
    00883             return index_data_;
    00884         }
    00885         BOOST_UBLAS_INLINE
    00886         const value_array_type &value_data () const {
    00887             return value_data_;
    00888         }
    00889         BOOST_UBLAS_INLINE
    00890         void set_filled (const typename index_array_type::size_type & filled) {
    00891             filled_ = filled;
    00892             storage_invariants ();
    00893         }
    00894         BOOST_UBLAS_INLINE
    00895         index_array_type &index_data () {
    00896             return index_data_;
    00897         }
    00898         BOOST_UBLAS_INLINE
    00899         value_array_type &value_data () {
    00900             return value_data_;
    00901         }
    00902
    00903         // Resizing
    00904     private:
    00905         BOOST_UBLAS_INLINE
    00906         size_type restrict_capacity (size_type non_zeros) const {
    00907             non_zeros = (std::max) (non_zeros, size_type (1));
    00908             non_zeros = (std::min) (non_zeros, size_);
    00909             return non_zeros;
    00910         }
    00911     public:
    00912         BOOST_UBLAS_INLINE
    00913         void resize (size_type size, bool preserve = true) {
    00914             size_ = size;
    00915             capacity_ = restrict_capacity (capacity_);
    00916             if (preserve) {
    00917                 index_data_. resize (capacity_, size_type ());
    00918                 value_data_. resize (capacity_, value_type ());
    00919                 filled_ = (std::min) (capacity_, filled_);
    00920                 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
    00921                     --filled_;
    00922                 }
    00923             }
    00924             else {
    00925                 index_data_. resize (capacity_);
    00926                 value_data_. resize (capacity_);
    00927                 filled_ = 0;
    00928             }
    00929             storage_invariants ();
    00930         }
    00931
    00932         // Reserving
    00933         BOOST_UBLAS_INLINE
    00934         void reserve (size_type non_zeros, bool preserve = true) {
    00935             capacity_ = restrict_capacity (non_zeros);
    00936             if (preserve) {
    00937                 index_data_. resize (capacity_, size_type ());
    00938                 value_data_. resize (capacity_, value_type ());
    00939                 filled_ = (std::min) (capacity_, filled_);
    00940             }
    00941             else {
    00942                 index_data_. resize (capacity_);
    00943                 value_data_. resize (capacity_);
    00944                 filled_ = 0;
    00945             }
    00946             storage_invariants ();
    00947         }
    00948
    00949         // Element support
    00950         BOOST_UBLAS_INLINE
    00951         pointer find_element (size_type i) {
    00952             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
    00953         }
    00954         BOOST_UBLAS_INLINE
    00955         const_pointer find_element (size_type i) const {
    00956             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    00957             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    00958                 return 0;
    00959             return &value_data_ [it - index_data_.begin ()];
    00960         }
    00961
    00962         // Element access
    00963         BOOST_UBLAS_INLINE
    00964         const_reference operator () (size_type i) const {
    00965             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00966             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    00967             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    00968                 return zero_;
    00969             return value_data_ [it - index_data_.begin ()];
    00970         }
    00971         BOOST_UBLAS_INLINE
    00972         true_reference ref (size_type i) {
    00973             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00974             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    00975             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    00976                 return insert_element (i, value_type/*zero*/());
    00977             else
    00978                 return value_data_ [it - index_data_.begin ()];
    00979         }
    00980         BOOST_UBLAS_INLINE
    00981         reference operator () (size_type i) {
    00982 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    00983             return ref (i) ;
    00984 #else
    00985             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    00986             return reference (*this, i);
    00987 #endif
    00988         }
    00989
    00990         BOOST_UBLAS_INLINE
    00991         const_reference operator [] (size_type i) const {
    00992             return (*this) (i);
    00993         }
    00994         BOOST_UBLAS_INLINE
    00995         reference operator [] (size_type i) {
    00996             return (*this) (i);
    00997         }
    00998
    00999         // Element assignment
    01000         BOOST_UBLAS_INLINE
    01001         true_reference insert_element (size_type i, const_reference t) {
    01002             BOOST_UBLAS_CHECK (!find_element (i), bad_index ());        // duplicate element
    01003             if (filled_ >= capacity_)
    01004                 reserve (2 * capacity_, true);
    01005             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01006             // ISSUE max_capacity limit due to difference_type
    01007             typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
    01008             BOOST_UBLAS_CHECK (filled_ == 0 || filled_ == typename index_array_type::size_type (n) || *it != k_based (i), internal_logic ());   // duplicate found by lower_bound
    01009             ++ filled_;
    01010             it = index_data_.begin () + n;
    01011             std::copy_backward (it, index_data_.begin () + filled_ - 1, index_data_.begin () + filled_);
    01012             *it = k_based (i);
    01013             typename value_array_type::iterator itt (value_data_.begin () + n);
    01014             std::copy_backward (itt, value_data_.begin () + filled_ - 1, value_data_.begin () + filled_);
    01015             *itt = t;
    01016             storage_invariants ();
    01017             return *itt;
    01018         }
    01019         BOOST_UBLAS_INLINE
    01020         void erase_element (size_type i) {
    01021             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01022             typename std::iterator_traits<subiterator_type>::difference_type  n = it - index_data_.begin ();
    01023             if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
    01024                 std::copy (it + 1, index_data_.begin () + filled_, it);
    01025                 typename value_array_type::iterator itt (value_data_.begin () + n);
    01026                 std::copy (itt + 1, value_data_.begin () + filled_, itt);
    01027                 -- filled_;
    01028             }
    01029             storage_invariants ();
    01030         }
    01031
    01032         // Zeroing
    01033         BOOST_UBLAS_INLINE
    01034         void clear () {
    01035             filled_ = 0;
    01036             storage_invariants ();
    01037         }
    01038
    01039         // Assignment
    01040         BOOST_UBLAS_INLINE
    01041         compressed_vector &operator = (const compressed_vector &v) {
    01042             if (this != &v) {
    01043                 size_ = v.size_;
    01044                 capacity_ = v.capacity_;
    01045                 filled_ = v.filled_;
    01046                 index_data_ = v.index_data_;
    01047                 value_data_ = v.value_data_;
    01048             }
    01049             storage_invariants ();
    01050             return *this;
    01051         }
    01052         template<class C>          // Container assignment without temporary
    01053         BOOST_UBLAS_INLINE
    01054         compressed_vector &operator = (const vector_container<C> &v) {
    01055             resize (v ().size (), false);
    01056             assign (v);
    01057             return *this;
    01058         }
    01059         BOOST_UBLAS_INLINE
    01060         compressed_vector &assign_temporary (compressed_vector &v) {
    01061             swap (v);
    01062             return *this;
    01063         }
    01064         template<class AE>
    01065         BOOST_UBLAS_INLINE
    01066         compressed_vector &operator = (const vector_expression<AE> &ae) {
    01067             self_type temporary (ae, capacity_);
    01068             return assign_temporary (temporary);
    01069         }
    01070         template<class AE>
    01071         BOOST_UBLAS_INLINE
    01072         compressed_vector &assign (const vector_expression<AE> &ae) {
    01073             vector_assign<scalar_assign> (*this, ae);
    01074             return *this;
    01075         }
    01076
    01077         // Computed assignment
    01078         template<class AE>
    01079         BOOST_UBLAS_INLINE
    01080         compressed_vector &operator += (const vector_expression<AE> &ae) {
    01081             self_type temporary (*this + ae, capacity_);
    01082             return assign_temporary (temporary);
    01083         }
    01084         template<class C>          // Container assignment without temporary
    01085         BOOST_UBLAS_INLINE
    01086         compressed_vector &operator += (const vector_container<C> &v) {
    01087             plus_assign (v);
    01088             return *this;
    01089         }
    01090         template<class AE>
    01091         BOOST_UBLAS_INLINE
    01092         compressed_vector &plus_assign (const vector_expression<AE> &ae) {
    01093             vector_assign<scalar_plus_assign> (*this, ae);
    01094             return *this;
    01095         }
    01096         template<class AE>
    01097         BOOST_UBLAS_INLINE
    01098         compressed_vector &operator -= (const vector_expression<AE> &ae) {
    01099             self_type temporary (*this - ae, capacity_);
    01100             return assign_temporary (temporary);
    01101         }
    01102         template<class C>          // Container assignment without temporary
    01103         BOOST_UBLAS_INLINE
    01104         compressed_vector &operator -= (const vector_container<C> &v) {
    01105             minus_assign (v);
    01106             return *this;
    01107         }
    01108         template<class AE>
    01109         BOOST_UBLAS_INLINE
    01110         compressed_vector &minus_assign (const vector_expression<AE> &ae) {
    01111             vector_assign<scalar_minus_assign> (*this, ae);
    01112             return *this;
    01113         }
    01114         template<class AT>
    01115         BOOST_UBLAS_INLINE
    01116         compressed_vector &operator *= (const AT &at) {
    01117             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
    01118             return *this;
    01119         }
    01120         template<class AT>
    01121         BOOST_UBLAS_INLINE
    01122         compressed_vector &operator /= (const AT &at) {
    01123             vector_assign_scalar<scalar_divides_assign> (*this, at);
    01124             return *this;
    01125         }
    01126
    01127         // Swapping
    01128         BOOST_UBLAS_INLINE
    01129         void swap (compressed_vector &v) {
    01130             if (this != &v) {
    01131                 std::swap (size_, v.size_);
    01132                 std::swap (capacity_, v.capacity_);
    01133                 std::swap (filled_, v.filled_);
    01134                 index_data_.swap (v.index_data_);
    01135                 value_data_.swap (v.value_data_);
    01136             }
    01137             storage_invariants ();
    01138         }
    01139         BOOST_UBLAS_INLINE
    01140         friend void swap (compressed_vector &v1, compressed_vector &v2) {
    01141             v1.swap (v2);
    01142         }
    01143
    01144         // Back element insertion and erasure
    01145         BOOST_UBLAS_INLINE
    01146         void push_back (size_type i, const_reference t) {
    01147             BOOST_UBLAS_CHECK (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i), external_logic ());
    01148             if (filled_ >= capacity_)
    01149                 reserve (2 * capacity_, true);
    01150             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
    01151             index_data_ [filled_] = k_based (i);
    01152             value_data_ [filled_] = t;
    01153             ++ filled_;
    01154             storage_invariants ();
    01155         }
    01156         BOOST_UBLAS_INLINE
    01157         void pop_back () {
    01158             BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
    01159             -- filled_;
    01160             storage_invariants ();
    01161         }
    01162
    01163         // Iterator types
    01164     private:
    01165         // Use index array iterator
    01166         typedef typename IA::const_iterator const_subiterator_type;
    01167         typedef typename IA::iterator subiterator_type;
    01168
    01169         BOOST_UBLAS_INLINE
    01170         true_reference at_element (size_type i) {
    01171             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    01172             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01173             BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
    01174             return value_data_ [it - index_data_.begin ()];
    01175         }
    01176
    01177     public:
    01178         class const_iterator;
    01179         class iterator;
    01180
    01181         // Element lookup
    01182         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    01183         const_iterator find (size_type i) const {
    01184             return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01185         }
    01186         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    01187         iterator find (size_type i) {
    01188             return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01189         }
    01190
    01191
    01192         class const_iterator:
    01193             public container_const_reference<compressed_vector>,
    01194             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    01195                                                const_iterator, value_type> {
    01196         public:
    01197             typedef typename compressed_vector::value_type value_type;
    01198             typedef typename compressed_vector::difference_type difference_type;
    01199             typedef typename compressed_vector::const_reference reference;
    01200             typedef const typename compressed_vector::pointer pointer;
    01201
    01202             // Construction and destruction
    01203             BOOST_UBLAS_INLINE
    01204             const_iterator ():
    01205                 container_const_reference<self_type> (), it_ () {}
    01206             BOOST_UBLAS_INLINE
    01207             const_iterator (const self_type &v, const const_subiterator_type &it):
    01208                 container_const_reference<self_type> (v), it_ (it) {}
    01209             BOOST_UBLAS_INLINE
    01210             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
    01211                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
    01212
    01213             // Arithmetic
    01214             BOOST_UBLAS_INLINE
    01215             const_iterator &operator ++ () {
    01216                 ++ it_;
    01217                 return *this;
    01218             }
    01219             BOOST_UBLAS_INLINE
    01220             const_iterator &operator -- () {
    01221                 -- it_;
    01222                 return *this;
    01223             }
    01224
    01225             // Dereference
    01226             BOOST_UBLAS_INLINE
    01227             const_reference operator * () const {
    01228                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    01229                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
    01230             }
    01231
    01232             // Index
    01233             BOOST_UBLAS_INLINE
    01234             size_type index () const {
    01235                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    01236                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
    01237                 return (*this) ().zero_based (*it_);
    01238             }
    01239
    01240             // Assignment
    01241             BOOST_UBLAS_INLINE
    01242             const_iterator &operator = (const const_iterator &it) {
    01243                 container_const_reference<self_type>::assign (&it ());
    01244                 it_ = it.it_;
    01245                 return *this;
    01246             }
    01247
    01248             // Comparison
    01249             BOOST_UBLAS_INLINE
    01250             bool operator == (const const_iterator &it) const {
    01251                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    01252                 return it_ == it.it_;
    01253             }
    01254
    01255         private:
    01256             const_subiterator_type it_;
    01257         };
    01258
    01259         BOOST_UBLAS_INLINE
    01260         const_iterator begin () const {
    01261             return find (0);
    01262         }
    01263         BOOST_UBLAS_INLINE
    01264         const_iterator end () const {
    01265             return find (size_);
    01266         }
    01267
    01268         class iterator:
    01269             public container_reference<compressed_vector>,
    01270             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    01271                                                iterator, value_type> {
    01272         public:
    01273             typedef typename compressed_vector::value_type value_type;
    01274             typedef typename compressed_vector::difference_type difference_type;
    01275             typedef typename compressed_vector::true_reference reference;
    01276             typedef typename compressed_vector::pointer pointer;
    01277
    01278             // Construction and destruction
    01279             BOOST_UBLAS_INLINE
    01280             iterator ():
    01281                 container_reference<self_type> (), it_ () {}
    01282             BOOST_UBLAS_INLINE
    01283             iterator (self_type &v, const subiterator_type &it):
    01284                 container_reference<self_type> (v), it_ (it) {}
    01285
    01286             // Arithmetic
    01287             BOOST_UBLAS_INLINE
    01288             iterator &operator ++ () {
    01289                 ++ it_;
    01290                 return *this;
    01291             }
    01292             BOOST_UBLAS_INLINE
    01293             iterator &operator -- () {
    01294                 -- it_;
    01295                 return *this;
    01296             }
    01297
    01298             // Dereference
    01299             BOOST_UBLAS_INLINE
    01300             reference operator * () const {
    01301                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    01302                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
    01303             }
    01304
    01305             // Index
    01306             BOOST_UBLAS_INLINE
    01307             size_type index () const {
    01308                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    01309                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
    01310                 return (*this) ().zero_based (*it_);
    01311             }
    01312
    01313             // Assignment
    01314             BOOST_UBLAS_INLINE
    01315             iterator &operator = (const iterator &it) {
    01316                 container_reference<self_type>::assign (&it ());
    01317                 it_ = it.it_;
    01318                 return *this;
    01319             }
    01320
    01321             // Comparison
    01322             BOOST_UBLAS_INLINE
    01323             bool operator == (const iterator &it) const {
    01324                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    01325                 return it_ == it.it_;
    01326             }
    01327
    01328         private:
    01329             subiterator_type it_;
    01330
    01331             friend class const_iterator;
    01332         };
    01333
    01334         BOOST_UBLAS_INLINE
    01335         iterator begin () {
    01336             return find (0);
    01337         }
    01338         BOOST_UBLAS_INLINE
    01339         iterator end () {
    01340             return find (size_);
    01341         }
    01342
    01343         // Reverse iterator
    01344         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
    01345         typedef reverse_iterator_base<iterator> reverse_iterator;
    01346
    01347         BOOST_UBLAS_INLINE
    01348         const_reverse_iterator rbegin () const {
    01349             return const_reverse_iterator (end ());
    01350         }
    01351         BOOST_UBLAS_INLINE
    01352         const_reverse_iterator rend () const {
    01353             return const_reverse_iterator (begin ());
    01354         }
    01355         BOOST_UBLAS_INLINE
    01356         reverse_iterator rbegin () {
    01357             return reverse_iterator (end ());
    01358         }
    01359         BOOST_UBLAS_INLINE
    01360         reverse_iterator rend () {
    01361             return reverse_iterator (begin ());
    01362         }
    01363
    01364          // Serialization
    01365         template<class Archive>
    01366         void serialize(Archive & ar, const unsigned int /* file_version */){
    01367             serialization::collection_size_type s (size_);
    01368             ar & serialization::make_nvp("size",s);
    01369             if (Archive::is_loading::value) {
    01370                 size_ = s;
    01371             }
    01372             // ISSUE: filled may be much less than capacity
    01373             // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
    01374             ar & serialization::make_nvp("capacity", capacity_);
    01375             ar & serialization::make_nvp("filled", filled_);
    01376             ar & serialization::make_nvp("index_data", index_data_);
    01377             ar & serialization::make_nvp("value_data", value_data_);
    01378             storage_invariants();
    01379         }
    01380
    01381     private:
    01382         void storage_invariants () const
    01383         {
    01384             BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
    01385             BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
    01386             BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
    01387             BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
    01388         }
    01389
    01390         size_type size_;
    01391         typename index_array_type::size_type capacity_;
    01392         typename index_array_type::size_type filled_;
    01393         index_array_type index_data_;
    01394         value_array_type value_data_;
    01395         static const value_type zero_;
    01396
    01397         BOOST_UBLAS_INLINE
    01398         static size_type zero_based (size_type k_based_index) {
    01399             return k_based_index - IB;
    01400         }
    01401         BOOST_UBLAS_INLINE
    01402         static size_type k_based (size_type zero_based_index) {
    01403             return zero_based_index + IB;
    01404         }
    01405
    01406         friend class iterator;
    01407         friend class const_iterator;
    01408     };
    01409
    01410     template<class T, std::size_t IB, class IA, class TA>
    01411     const typename compressed_vector<T, IB, IA, TA>::value_type compressed_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
    01412
    01413     // Thanks to Kresimir Fresl for extending this to cover different index bases.
    01414
    01436     template<class T, std::size_t IB, class IA, class TA>
    01437     class coordinate_vector:
    01438         public vector_container<coordinate_vector<T, IB, IA, TA> > {
    01439
    01440         typedef T &true_reference;
    01441         typedef T *pointer;
    01442         typedef const T *const_pointer;
    01443         typedef coordinate_vector<T, IB, IA, TA> self_type;
    01444     public:
    01445 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
    01446         using vector_container<self_type>::operator ();
    01447 #endif
    01448         // ISSUE require type consistency check
    01449         // is_convertable (IA::size_type, TA::size_type)
    01450         typedef typename IA::value_type size_type;
    01451         typedef typename IA::difference_type difference_type;
    01452         typedef T value_type;
    01453         typedef const T &const_reference;
    01454 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    01455         typedef T &reference;
    01456 #else
    01457         typedef sparse_vector_element<self_type> reference;
    01458 #endif
    01459         typedef IA index_array_type;
    01460         typedef TA value_array_type;
    01461         typedef const vector_reference<const self_type> const_closure_type;
    01462         typedef vector_reference<self_type> closure_type;
    01463         typedef self_type vector_temporary_type;
    01464         typedef sparse_tag storage_category;
    01465
    01466         // Construction and destruction
    01467         BOOST_UBLAS_INLINE
    01468         coordinate_vector ():
    01469             vector_container<self_type> (),
    01470             size_ (0), capacity_ (restrict_capacity (0)),
    01471             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
    01472             index_data_ (capacity_), value_data_ (capacity_) {
    01473             storage_invariants ();
    01474         }
    01475         explicit BOOST_UBLAS_INLINE
    01476         coordinate_vector (size_type size, size_type non_zeros = 0):
    01477             vector_container<self_type> (),
    01478             size_ (size), capacity_ (restrict_capacity (non_zeros)),
    01479             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
    01480             index_data_ (capacity_), value_data_ (capacity_) {
    01481             storage_invariants ();
    01482         }
    01483         BOOST_UBLAS_INLINE
    01484         coordinate_vector (const coordinate_vector &v):
    01485             vector_container<self_type> (),
    01486             size_ (v.size_), capacity_ (v.capacity_),
    01487             filled_ (v.filled_), sorted_filled_ (v.sorted_filled_), sorted_ (v.sorted_),
    01488             index_data_ (v.index_data_), value_data_ (v.value_data_) {
    01489             storage_invariants ();
    01490         }
    01491         template<class AE>
    01492         BOOST_UBLAS_INLINE
    01493         coordinate_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
    01494             vector_container<self_type> (),
    01495             size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)),
    01496             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
    01497             index_data_ (capacity_), value_data_ (capacity_) {
    01498             storage_invariants ();
    01499             vector_assign<scalar_assign> (*this, ae);
    01500         }
    01501
    01502         // Accessors
    01503         BOOST_UBLAS_INLINE
    01504         size_type size () const {
    01505             return size_;
    01506         }
    01507         BOOST_UBLAS_INLINE
    01508         size_type nnz_capacity () const {
    01509             return capacity_;
    01510         }
    01511         BOOST_UBLAS_INLINE
    01512         size_type nnz () const {
    01513             return filled_;
    01514         }
    01515
    01516         // Storage accessors
    01517         BOOST_UBLAS_INLINE
    01518         static size_type index_base () {
    01519             return IB;
    01520         }
    01521         BOOST_UBLAS_INLINE
    01522         typename index_array_type::size_type filled () const {
    01523             return filled_;
    01524         }
    01525         BOOST_UBLAS_INLINE
    01526         const index_array_type &index_data () const {
    01527             return index_data_;
    01528         }
    01529         BOOST_UBLAS_INLINE
    01530         const value_array_type &value_data () const {
    01531             return value_data_;
    01532         }
    01533         BOOST_UBLAS_INLINE
    01534         void set_filled (const typename index_array_type::size_type &sorted, const typename index_array_type::size_type &filled) {
    01535             sorted_filled_ = sorted;
    01536             filled_ = filled;
    01537             storage_invariants ();
    01538         }
    01539         BOOST_UBLAS_INLINE
    01540         index_array_type &index_data () {
    01541             return index_data_;
    01542         }
    01543         BOOST_UBLAS_INLINE
    01544         value_array_type &value_data () {
    01545             return value_data_;
    01546         }
    01547
    01548         // Resizing
    01549     private:
    01550         BOOST_UBLAS_INLINE
    01551         size_type restrict_capacity (size_type non_zeros) const {
    01552              // minimum non_zeros
    01553              non_zeros = (std::max) (non_zeros, size_type (1));
    01554              // ISSUE no maximum as coordinate may contain inserted duplicates
    01555              return non_zeros;
    01556         }
    01557     public:
    01558         BOOST_UBLAS_INLINE
    01559         void resize (size_type size, bool preserve = true) {
    01560             if (preserve)
    01561                 sort ();    // remove duplicate elements.
    01562             size_ = size;
    01563             capacity_ = restrict_capacity (capacity_);
    01564             if (preserve) {
    01565                 index_data_. resize (capacity_, size_type ());
    01566                 value_data_. resize (capacity_, value_type ());
    01567                 filled_ = (std::min) (capacity_, filled_);
    01568                 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
    01569                     --filled_;
    01570                 }
    01571             }
    01572             else {
    01573                 index_data_. resize (capacity_);
    01574                 value_data_. resize (capacity_);
    01575                 filled_ = 0;
    01576             }
    01577             sorted_filled_ = filled_;
    01578             storage_invariants ();
    01579         }
    01580         // Reserving
    01581         BOOST_UBLAS_INLINE
    01582         void reserve (size_type non_zeros, bool preserve = true) {
    01583             if (preserve)
    01584                 sort ();    // remove duplicate elements.
    01585             capacity_ = restrict_capacity (non_zeros);
    01586             if (preserve) {
    01587                 index_data_. resize (capacity_, size_type ());
    01588                 value_data_. resize (capacity_, value_type ());
    01589                 filled_ = (std::min) (capacity_, filled_);
    01590                 }
    01591             else {
    01592                 index_data_. resize (capacity_);
    01593                 value_data_. resize (capacity_);
    01594                 filled_ = 0;
    01595             }
    01596             sorted_filled_ = filled_;
    01597             storage_invariants ();
    01598         }
    01599
    01600         // Element support
    01601         BOOST_UBLAS_INLINE
    01602         pointer find_element (size_type i) {
    01603             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
    01604         }
    01605         BOOST_UBLAS_INLINE
    01606         const_pointer find_element (size_type i) const {
    01607             sort ();
    01608             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01609             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    01610                 return 0;
    01611             return &value_data_ [it - index_data_.begin ()];
    01612         }
    01613
    01614         // Element access
    01615         BOOST_UBLAS_INLINE
    01616         const_reference operator () (size_type i) const {
    01617             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    01618             sort ();
    01619             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01620             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    01621                 return zero_;
    01622             return value_data_ [it - index_data_.begin ()];
    01623         }
    01624         BOOST_UBLAS_INLINE
    01625         true_reference ref (size_type i) {
    01626             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    01627             sort ();
    01628             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01629             if (it == index_data_.begin () + filled_ || *it != k_based (i))
    01630                 return insert_element (i, value_type/*zero*/());
    01631             else
    01632                 return value_data_ [it - index_data_.begin ()];
    01633         }
    01634         BOOST_UBLAS_INLINE
    01635         reference operator () (size_type i) {
    01636 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
    01637             return ref (i);
    01638 #else
    01639             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    01640             return reference (*this, i);
    01641 #endif
    01642         }
    01643
    01644         BOOST_UBLAS_INLINE
    01645         const_reference operator [] (size_type i) const {
    01646             return (*this) (i);
    01647         }
    01648         BOOST_UBLAS_INLINE
    01649         reference operator [] (size_type i) {
    01650             return (*this) (i);
    01651         }
    01652
    01653         // Element assignment
    01654         BOOST_UBLAS_INLINE
    01655         void append_element (size_type i, const_reference t) {
    01656             if (filled_ >= capacity_)
    01657                 reserve (2 * filled_, true);
    01658             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
    01659             index_data_ [filled_] = k_based (i);
    01660             value_data_ [filled_] = t;
    01661             ++ filled_;
    01662             sorted_ = false;
    01663             storage_invariants ();
    01664         }
    01665         BOOST_UBLAS_INLINE
    01666         true_reference insert_element (size_type i, const_reference t) {
    01667             BOOST_UBLAS_CHECK (!find_element (i), bad_index ());        // duplicate element
    01668             append_element (i, t);
    01669             return value_data_ [filled_ - 1];
    01670         }
    01671         BOOST_UBLAS_INLINE
    01672         void erase_element (size_type i) {
    01673             sort ();
    01674             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01675             typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
    01676             if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
    01677                 std::copy (it + 1, index_data_.begin () + filled_, it);
    01678                 typename value_array_type::iterator itt (value_data_.begin () + n);
    01679                 std::copy (itt + 1, value_data_.begin () + filled_, itt);
    01680                 -- filled_;
    01681                 sorted_filled_ = filled_;
    01682             }
    01683             storage_invariants ();
    01684         }
    01685
    01686         // Zeroing
    01687         BOOST_UBLAS_INLINE
    01688         void clear () {
    01689             filled_ = 0;
    01690             sorted_filled_ = filled_;
    01691             sorted_ = true;
    01692             storage_invariants ();
    01693         }
    01694
    01695         // Assignment
    01696         BOOST_UBLAS_INLINE
    01697         coordinate_vector &operator = (const coordinate_vector &v) {
    01698             if (this != &v) {
    01699                 size_ = v.size_;
    01700                 capacity_ = v.capacity_;
    01701                 filled_ = v.filled_;
    01702                 sorted_filled_ = v.sorted_filled_;
    01703                 sorted_ = v.sorted_;
    01704                 index_data_ = v.index_data_;
    01705                 value_data_ = v.value_data_;
    01706             }
    01707             storage_invariants ();
    01708             return *this;
    01709         }
    01710         template<class C>          // Container assignment without temporary
    01711         BOOST_UBLAS_INLINE
    01712         coordinate_vector &operator = (const vector_container<C> &v) {
    01713             resize (v ().size (), false);
    01714             assign (v);
    01715             return *this;
    01716         }
    01717         BOOST_UBLAS_INLINE
    01718         coordinate_vector &assign_temporary (coordinate_vector &v) {
    01719             swap (v);
    01720             return *this;
    01721         }
    01722         template<class AE>
    01723         BOOST_UBLAS_INLINE
    01724         coordinate_vector &operator = (const vector_expression<AE> &ae) {
    01725             self_type temporary (ae, capacity_);
    01726             return assign_temporary (temporary);
    01727         }
    01728         template<class AE>
    01729         BOOST_UBLAS_INLINE
    01730         coordinate_vector &assign (const vector_expression<AE> &ae) {
    01731             vector_assign<scalar_assign> (*this, ae);
    01732             return *this;
    01733         }
    01734
    01735         // Computed assignment
    01736         template<class AE>
    01737         BOOST_UBLAS_INLINE
    01738         coordinate_vector &operator += (const vector_expression<AE> &ae) {
    01739             self_type temporary (*this + ae, capacity_);
    01740             return assign_temporary (temporary);
    01741         }
    01742         template<class C>          // Container assignment without temporary
    01743         BOOST_UBLAS_INLINE
    01744         coordinate_vector &operator += (const vector_container<C> &v) {
    01745             plus_assign (v);
    01746             return *this;
    01747         }
    01748         template<class AE>
    01749         BOOST_UBLAS_INLINE
    01750         coordinate_vector &plus_assign (const vector_expression<AE> &ae) {
    01751             vector_assign<scalar_plus_assign> (*this, ae);
    01752             return *this;
    01753         }
    01754         template<class AE>
    01755         BOOST_UBLAS_INLINE
    01756         coordinate_vector &operator -= (const vector_expression<AE> &ae) {
    01757             self_type temporary (*this - ae, capacity_);
    01758             return assign_temporary (temporary);
    01759         }
    01760         template<class C>          // Container assignment without temporary
    01761         BOOST_UBLAS_INLINE
    01762         coordinate_vector &operator -= (const vector_container<C> &v) {
    01763             minus_assign (v);
    01764             return *this;
    01765         }
    01766         template<class AE>
    01767         BOOST_UBLAS_INLINE
    01768         coordinate_vector &minus_assign (const vector_expression<AE> &ae) {
    01769             vector_assign<scalar_minus_assign> (*this, ae);
    01770             return *this;
    01771         }
    01772         template<class AT>
    01773         BOOST_UBLAS_INLINE
    01774         coordinate_vector &operator *= (const AT &at) {
    01775             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
    01776             return *this;
    01777         }
    01778         template<class AT>
    01779         BOOST_UBLAS_INLINE
    01780         coordinate_vector &operator /= (const AT &at) {
    01781             vector_assign_scalar<scalar_divides_assign> (*this, at);
    01782             return *this;
    01783         }
    01784
    01785         // Swapping
    01786         BOOST_UBLAS_INLINE
    01787         void swap (coordinate_vector &v) {
    01788             if (this != &v) {
    01789                 std::swap (size_, v.size_);
    01790                 std::swap (capacity_, v.capacity_);
    01791                 std::swap (filled_, v.filled_);
    01792                 std::swap (sorted_filled_, v.sorted_filled_);
    01793                 std::swap (sorted_, v.sorted_);
    01794                 index_data_.swap (v.index_data_);
    01795                 value_data_.swap (v.value_data_);
    01796             }
    01797             storage_invariants ();
    01798         }
    01799         BOOST_UBLAS_INLINE
    01800         friend void swap (coordinate_vector &v1, coordinate_vector &v2) {
    01801             v1.swap (v2);
    01802         }
    01803
    01804         // Sorting and summation of duplicates
    01805         BOOST_UBLAS_INLINE
    01806         void sort () const {
    01807             if (! sorted_ && filled_ > 0) {
    01808                 typedef index_pair_array<index_array_type, value_array_type> array_pair;
    01809                 array_pair ipa (filled_, index_data_, value_data_);
    01810                 const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
    01811                 // sort new elements and merge
    01812                 std::sort (iunsorted, ipa.end ());
    01813                 std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
    01814
    01815                 // sum duplicates with += and remove
    01816                 size_type filled = 0;
    01817                 for (size_type i = 1; i < filled_; ++ i) {
    01818                     if (index_data_ [filled] != index_data_ [i]) {
    01819                         ++ filled;
    01820                         if (filled != i) {
    01821                             index_data_ [filled] = index_data_ [i];
    01822                             value_data_ [filled] = value_data_ [i];
    01823                         }
    01824                     } else {
    01825                         value_data_ [filled] += value_data_ [i];
    01826                     }
    01827                 }
    01828                 filled_ = filled + 1;
    01829                 sorted_filled_ = filled_;
    01830                 sorted_ = true;
    01831                 storage_invariants ();
    01832             }
    01833         }
    01834
    01835         // Back element insertion and erasure
    01836         BOOST_UBLAS_INLINE
    01837         void push_back (size_type i, const_reference t) {
    01838             // must maintain sort order
    01839             BOOST_UBLAS_CHECK (sorted_ && (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i)), external_logic ());
    01840             if (filled_ >= capacity_)
    01841                 reserve (2 * filled_, true);
    01842             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
    01843             index_data_ [filled_] = k_based (i);
    01844             value_data_ [filled_] = t;
    01845             ++ filled_;
    01846             sorted_filled_ = filled_;
    01847             storage_invariants ();
    01848         }
    01849         BOOST_UBLAS_INLINE
    01850         void pop_back () {
    01851             // ISSUE invariants could be simpilfied if sorted required as precondition
    01852             BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
    01853             -- filled_;
    01854             sorted_filled_ = (std::min) (sorted_filled_, filled_);
    01855             sorted_ = sorted_filled_ = filled_;
    01856             storage_invariants ();
    01857         }
    01858
    01859         // Iterator types
    01860     private:
    01861         // Use index array iterator
    01862         typedef typename IA::const_iterator const_subiterator_type;
    01863         typedef typename IA::iterator subiterator_type;
    01864
    01865         BOOST_UBLAS_INLINE
    01866         true_reference at_element (size_type i) {
    01867             BOOST_UBLAS_CHECK (i < size_, bad_index ());
    01868             sort ();
    01869             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01870             BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
    01871             return value_data_ [it - index_data_.begin ()];
    01872         }
    01873
    01874     public:
    01875         class const_iterator;
    01876         class iterator;
    01877
    01878         // Element lookup
    01879         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    01880         const_iterator find (size_type i) const {
    01881             sort ();
    01882             return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01883         }
    01884         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
    01885         iterator find (size_type i) {
    01886             sort ();
    01887             return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
    01888         }
    01889
    01890
    01891         class const_iterator:
    01892             public container_const_reference<coordinate_vector>,
    01893             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    01894                                                const_iterator, value_type> {
    01895         public:
    01896             typedef typename coordinate_vector::value_type value_type;
    01897             typedef typename coordinate_vector::difference_type difference_type;
    01898             typedef typename coordinate_vector::const_reference reference;
    01899             typedef const typename coordinate_vector::pointer pointer;
    01900
    01901             // Construction and destruction
    01902             BOOST_UBLAS_INLINE
    01903             const_iterator ():
    01904                 container_const_reference<self_type> (), it_ () {}
    01905             BOOST_UBLAS_INLINE
    01906             const_iterator (const self_type &v, const const_subiterator_type &it):
    01907                 container_const_reference<self_type> (v), it_ (it) {}
    01908             BOOST_UBLAS_INLINE
    01909             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
    01910                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
    01911
    01912             // Arithmetic
    01913             BOOST_UBLAS_INLINE
    01914             const_iterator &operator ++ () {
    01915                 ++ it_;
    01916                 return *this;
    01917             }
    01918             BOOST_UBLAS_INLINE
    01919             const_iterator &operator -- () {
    01920                 -- it_;
    01921                 return *this;
    01922             }
    01923
    01924             // Dereference
    01925             BOOST_UBLAS_INLINE
    01926             const_reference operator * () const {
    01927                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    01928                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
    01929             }
    01930
    01931             // Index
    01932             BOOST_UBLAS_INLINE
    01933             size_type index () const {
    01934                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    01935                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
    01936                 return (*this) ().zero_based (*it_);
    01937             }
    01938
    01939             // Assignment
    01940             BOOST_UBLAS_INLINE
    01941             const_iterator &operator = (const const_iterator &it) {
    01942                 container_const_reference<self_type>::assign (&it ());
    01943                 it_ = it.it_;
    01944                 return *this;
    01945             }
    01946
    01947             // Comparison
    01948             BOOST_UBLAS_INLINE
    01949             bool operator == (const const_iterator &it) const {
    01950                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    01951                 return it_ == it.it_;
    01952             }
    01953
    01954         private:
    01955             const_subiterator_type it_;
    01956         };
    01957
    01958         BOOST_UBLAS_INLINE
    01959         const_iterator begin () const {
    01960             return find (0);
    01961         }
    01962         BOOST_UBLAS_INLINE
    01963         const_iterator end () const {
    01964             return find (size_);
    01965         }
    01966
    01967         class iterator:
    01968             public container_reference<coordinate_vector>,
    01969             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
    01970                                                iterator, value_type> {
    01971         public:
    01972             typedef typename coordinate_vector::value_type value_type;
    01973             typedef typename coordinate_vector::difference_type difference_type;
    01974             typedef typename coordinate_vector::true_reference reference;
    01975             typedef typename coordinate_vector::pointer pointer;
    01976
    01977             // Construction and destruction
    01978             BOOST_UBLAS_INLINE
    01979             iterator ():
    01980                 container_reference<self_type> (), it_ () {}
    01981             BOOST_UBLAS_INLINE
    01982             iterator (self_type &v, const subiterator_type &it):
    01983                 container_reference<self_type> (v), it_ (it) {}
    01984
    01985             // Arithmetic
    01986             BOOST_UBLAS_INLINE
    01987             iterator &operator ++ () {
    01988                 ++ it_;
    01989                 return *this;
    01990             }
    01991             BOOST_UBLAS_INLINE
    01992             iterator &operator -- () {
    01993                 -- it_;
    01994                 return *this;
    01995             }
    01996
    01997             // Dereference
    01998             BOOST_UBLAS_INLINE
    01999             reference operator * () const {
    02000                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
    02001                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
    02002             }
    02003
    02004             // Index
    02005             BOOST_UBLAS_INLINE
    02006             size_type index () const {
    02007                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
    02008                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
    02009                 return (*this) ().zero_based (*it_);
    02010             }
    02011
    02012             // Assignment
    02013             BOOST_UBLAS_INLINE
    02014             iterator &operator = (const iterator &it) {
    02015                 container_reference<self_type>::assign (&it ());
    02016                 it_ = it.it_;
    02017                 return *this;
    02018             }
    02019
    02020             // Comparison
    02021             BOOST_UBLAS_INLINE
    02022             bool operator == (const iterator &it) const {
    02023                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
    02024                 return it_ == it.it_;
    02025             }
    02026
    02027         private:
    02028             subiterator_type it_;
    02029
    02030             friend class const_iterator;
    02031         };
    02032
    02033         BOOST_UBLAS_INLINE
    02034         iterator begin () {
    02035             return find (0);
    02036         }
    02037         BOOST_UBLAS_INLINE
    02038         iterator end () {
    02039             return find (size_);
    02040         }
    02041
    02042         // Reverse iterator
    02043         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
    02044         typedef reverse_iterator_base<iterator> reverse_iterator;
    02045
    02046         BOOST_UBLAS_INLINE
    02047         const_reverse_iterator rbegin () const {
    02048             return const_reverse_iterator (end ());
    02049         }
    02050         BOOST_UBLAS_INLINE
    02051         const_reverse_iterator rend () const {
    02052             return const_reverse_iterator (begin ());
    02053         }
    02054         BOOST_UBLAS_INLINE
    02055         reverse_iterator rbegin () {
    02056             return reverse_iterator (end ());
    02057         }
    02058         BOOST_UBLAS_INLINE
    02059         reverse_iterator rend () {
    02060             return reverse_iterator (begin ());
    02061         }
    02062
    02063          // Serialization
    02064         template<class Archive>
    02065         void serialize(Archive & ar, const unsigned int /* file_version */){
    02066             serialization::collection_size_type s (size_);
    02067             ar & serialization::make_nvp("size",s);
    02068             if (Archive::is_loading::value) {
    02069                 size_ = s;
    02070             }
    02071             // ISSUE: filled may be much less than capacity
    02072             // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
    02073             ar & serialization::make_nvp("capacity", capacity_);
    02074             ar & serialization::make_nvp("filled", filled_);
    02075             ar & serialization::make_nvp("sorted_filled", sorted_filled_);
    02076             ar & serialization::make_nvp("sorted", sorted_);
    02077             ar & serialization::make_nvp("index_data", index_data_);
    02078             ar & serialization::make_nvp("value_data", value_data_);
    02079             storage_invariants();
    02080         }
    02081
    02082     private:
    02083         void storage_invariants () const
    02084         {
    02085             BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
    02086             BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
    02087             BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
    02088             BOOST_UBLAS_CHECK (sorted_filled_ <= filled_, internal_logic ());
    02089             BOOST_UBLAS_CHECK (sorted_ == (sorted_filled_ == filled_), internal_logic ());
    02090             BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
    02091         }
    02092
    02093         size_type size_;
    02094         size_type capacity_;
    02095         mutable typename index_array_type::size_type filled_;
    02096         mutable typename index_array_type::size_type sorted_filled_;
    02097         mutable bool sorted_;
    02098         mutable index_array_type index_data_;
    02099         mutable value_array_type value_data_;
    02100         static const value_type zero_;
    02101
    02102         BOOST_UBLAS_INLINE
    02103         static size_type zero_based (size_type k_based_index) {
    02104             return k_based_index - IB;
    02105         }
    02106         BOOST_UBLAS_INLINE
    02107         static size_type k_based (size_type zero_based_index) {
    02108             return zero_based_index + IB;
    02109         }
    02110
    02111         friend class iterator;
    02112         friend class const_iterator;
    02113     };
    02114
    02115     template<class T, std::size_t IB, class IA, class TA>
    02116     const typename coordinate_vector<T, IB, IA, TA>::value_type coordinate_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
    02117
    02118 }}}
    02119
    02120 #endif