Boost.uBlas 1.49
Linear Algebra in C++: matrices, vectors and numeric algorithms

vector_sparse.hpp

Go to the documentation of this file.
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