Chris@16: //
Chris@16: //  Copyright (c) 2000-2002
Chris@16: //  Joerg Walter, Mathias Koch
Chris@16: //
Chris@16: //  Distributed under the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: //  The authors gratefully acknowledge the support of
Chris@16: //  GeNeSys mbH & Co. KG in producing this work.
Chris@16: //
Chris@16: 
Chris@16: #ifndef _BOOST_UBLAS_VECTOR_SPARSE_
Chris@16: #define _BOOST_UBLAS_VECTOR_SPARSE_
Chris@16: 
Chris@16: #include <boost/numeric/ublas/storage_sparse.hpp>
Chris@16: #include <boost/numeric/ublas/vector_expression.hpp>
Chris@16: #include <boost/numeric/ublas/detail/vector_assign.hpp>
Chris@16: #if BOOST_UBLAS_TYPE_CHECK
Chris@16: #include <boost/numeric/ublas/vector.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: // Iterators based on ideas of Jeremy Siek
Chris@16: 
Chris@16: namespace boost { namespace numeric { namespace ublas {
Chris@16: 
Chris@16: #ifdef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16: 
Chris@16:     template<class V>
Chris@16:     class sparse_vector_element:
Chris@16:        public container_reference<V> {
Chris@16:     public:
Chris@16:         typedef V vector_type;
Chris@16:         typedef typename V::size_type size_type;
Chris@16:         typedef typename V::value_type value_type;
Chris@16:         typedef const value_type &const_reference;
Chris@16:         typedef value_type *pointer;
Chris@16: 
Chris@16:     private:
Chris@16:         // Proxied element operations
Chris@16:         void get_d () const {
Chris@16:             pointer p = (*this) ().find_element (i_);
Chris@16:             if (p)
Chris@16:                 d_ = *p;
Chris@16:             else
Chris@16:                 d_ = value_type/*zero*/();
Chris@16:         }
Chris@16: 
Chris@16:         void set (const value_type &s) const {
Chris@16:             pointer p = (*this) ().find_element (i_);
Chris@16:             if (!p)
Chris@16:                 (*this) ().insert_element (i_, s);
Chris@16:             else
Chris@16:                 *p = s;
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         // Construction and destruction
Chris@16:         sparse_vector_element (vector_type &v, size_type i):
Chris@16:             container_reference<vector_type> (v), i_ (i) {
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element (const sparse_vector_element &p):
Chris@16:             container_reference<vector_type> (p), i_ (p.i_) {}
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         ~sparse_vector_element () {
Chris@16:         }
Chris@16: 
Chris@16:         // Assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator = (const sparse_vector_element &p) {
Chris@16:             // Overide the implict copy assignment
Chris@16:             p.get_d ();
Chris@16:             set (p.d_);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator = (const D &d) {
Chris@16:             set (d);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator += (const D &d) {
Chris@16:             get_d ();
Chris@16:             d_ += d;
Chris@16:             set (d_);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator -= (const D &d) {
Chris@16:             get_d ();
Chris@16:             d_ -= d;
Chris@16:             set (d_);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator *= (const D &d) {
Chris@16:             get_d ();
Chris@16:             d_ *= d;
Chris@16:             set (d_);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         sparse_vector_element &operator /= (const D &d) {
Chris@16:             get_d ();
Chris@16:             d_ /= d;
Chris@16:             set (d_);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Comparison
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         bool operator == (const D &d) const {
Chris@16:             get_d ();
Chris@16:             return d_ == d;
Chris@16:         }
Chris@16:         template<class D>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         bool operator != (const D &d) const {
Chris@16:             get_d ();
Chris@16:             return d_ != d;
Chris@16:         }
Chris@16: 
Chris@16:         // Conversion - weak link in proxy as d_ is not a perfect alias for the element
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         operator const_reference () const {
Chris@16:             get_d ();
Chris@16:             return d_;
Chris@16:         }
Chris@16: 
Chris@16:         // Conversion to reference - may be invalidated
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         value_type& ref () const {
Chris@16:             const pointer p = (*this) ().find_element (i_);
Chris@16:             if (!p)
Chris@16:                 return (*this) ().insert_element (i_, value_type/*zero*/());
Chris@16:             else
Chris@16:                 return *p;
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         size_type i_;
Chris@16:         mutable value_type d_;
Chris@16:     };
Chris@16: 
Chris@16:     /*
Chris@16:      * Generalise explicit reference access
Chris@16:      */
Chris@16:     namespace detail {
Chris@16:         template <class R>
Chris@16:         struct element_reference {
Chris@16:             typedef R& reference;
Chris@16:             static reference get_reference (reference r)
Chris@16:             {
Chris@16:                 return r;
Chris@16:             }
Chris@16:         };
Chris@16:         template <class V>
Chris@16:         struct element_reference<sparse_vector_element<V> > {
Chris@16:             typedef typename V::value_type& reference;
Chris@16:             static reference get_reference (const sparse_vector_element<V>& sve)
Chris@16:             {
Chris@16:                 return sve.ref ();
Chris@16:             }
Chris@16:         };
Chris@16:     }
Chris@16:     template <class VER>
Chris@16:     typename detail::element_reference<VER>::reference ref (VER& ver) {
Chris@16:         return detail::element_reference<VER>::get_reference (ver);
Chris@16:     }
Chris@16:     template <class VER>
Chris@16:     typename detail::element_reference<VER>::reference ref (const VER& ver) {
Chris@16:         return detail::element_reference<VER>::get_reference (ver);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template<class V>
Chris@16:     struct type_traits<sparse_vector_element<V> > {
Chris@16:         typedef typename V::value_type element_type;
Chris@16:         typedef type_traits<sparse_vector_element<V> > self_type;
Chris@16:         typedef typename type_traits<element_type>::value_type value_type;
Chris@16:         typedef typename type_traits<element_type>::const_reference const_reference;
Chris@16:         typedef sparse_vector_element<V> reference;
Chris@16:         typedef typename type_traits<element_type>::real_type real_type;
Chris@16:         typedef typename type_traits<element_type>::precision_type precision_type;
Chris@16: 
Chris@16:         static const unsigned plus_complexity = type_traits<element_type>::plus_complexity;
Chris@16:         static const unsigned multiplies_complexity = type_traits<element_type>::multiplies_complexity;
Chris@16: 
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type real (const_reference t) {
Chris@16:             return type_traits<element_type>::real (t);
Chris@16:         }
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type imag (const_reference t) {
Chris@16:             return type_traits<element_type>::imag (t);
Chris@16:         }
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         value_type conj (const_reference t) {
Chris@16:             return type_traits<element_type>::conj (t);
Chris@16:         }
Chris@16: 
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type type_abs (const_reference t) {
Chris@16:             return type_traits<element_type>::type_abs (t);
Chris@16:         }
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         value_type type_sqrt (const_reference t) {
Chris@16:             return type_traits<element_type>::type_sqrt (t);
Chris@16:         }
Chris@16: 
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type norm_1 (const_reference t) {
Chris@16:             return type_traits<element_type>::norm_1 (t);
Chris@16:         }
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type norm_2 (const_reference t) {
Chris@16:             return type_traits<element_type>::norm_2 (t);
Chris@16:         }
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         real_type norm_inf (const_reference t) {
Chris@16:             return type_traits<element_type>::norm_inf (t);
Chris@16:         }
Chris@16: 
Chris@16:         static
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         bool equals (const_reference t1, const_reference t2) {
Chris@16:             return type_traits<element_type>::equals (t1, t2);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template<class V1, class T2>
Chris@16:     struct promote_traits<sparse_vector_element<V1>, T2> {
Chris@16:         typedef typename promote_traits<typename sparse_vector_element<V1>::value_type, T2>::promote_type promote_type;
Chris@16:     };
Chris@16:     template<class T1, class V2>
Chris@16:     struct promote_traits<T1, sparse_vector_element<V2> > {
Chris@16:         typedef typename promote_traits<T1, typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
Chris@16:     };
Chris@16:     template<class V1, class V2>
Chris@16:     struct promote_traits<sparse_vector_element<V1>, sparse_vector_element<V2> > {
Chris@16:         typedef typename promote_traits<typename sparse_vector_element<V1>::value_type,
Chris@16:                                         typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
Chris@16:     };
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16:     /** \brief Index map based sparse vector
Chris@16:      *
Chris@16:      * A sparse vector of values of type T of variable size. The sparse storage type A can be 
Chris@16:      * \c std::map<size_t, T> or \c map_array<size_t, T>. This means that only non-zero elements
Chris@16:      * are effectively stored.
Chris@16:      *
Chris@16:      * For a \f$n\f$-dimensional sparse vector,  and 0 <= i < n the non-zero elements \f$v_i\f$ 
Chris@16:      * are mapped to consecutive elements of the associative container, i.e. for elements 
Chris@16:      * \f$k = v_{i_1}\f$ and \f$k + 1 = v_{i_2}\f$ of the container, holds \f$i_1 < i_2\f$.
Chris@16:      *
Chris@16:      * Supported parameters for the adapted array are \c map_array<std::size_t, T> and 
Chris@16:      * \c map_std<std::size_t, T>. The latter is equivalent to \c std::map<std::size_t, T>.
Chris@16:      *
Chris@16:      * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
Chris@16:      * \tparam A the type of Storage array
Chris@16:      */
Chris@16:     template<class T, class A>
Chris@16:     class mapped_vector:
Chris@16:         public vector_container<mapped_vector<T, A> > {
Chris@16: 
Chris@16:         typedef T &true_reference;
Chris@16:         typedef T *pointer;
Chris@16:         typedef const T *const_pointer;
Chris@16:         typedef mapped_vector<T, A> self_type;
Chris@16:     public:
Chris@16: #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
Chris@16:         using vector_container<self_type>::operator ();
Chris@16: #endif
Chris@16:         typedef typename A::size_type size_type;
Chris@16:         typedef typename A::difference_type difference_type;
Chris@16:         typedef T value_type;
Chris@16:         typedef A array_type;
Chris@16:         typedef const value_type &const_reference;
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:         typedef typename detail::map_traits<A,T>::reference reference;
Chris@16: #else
Chris@16:         typedef sparse_vector_element<self_type> reference;
Chris@16: #endif
Chris@16:         typedef const vector_reference<const self_type> const_closure_type;
Chris@16:         typedef vector_reference<self_type> closure_type;
Chris@16:         typedef self_type vector_temporary_type;
Chris@16:         typedef sparse_tag storage_category;
Chris@16: 
Chris@16:         // Construction and destruction
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector ():
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (0), data_ () {}
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector (size_type size, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (size), data_ () {
Chris@16:             detail::map_reserve (data(), restrict_capacity (non_zeros));
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector (const mapped_vector &v):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (v.size_), data_ (v.data_) {}
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (ae ().size ()), data_ () {
Chris@16:             detail::map_reserve (data(), restrict_capacity (non_zeros));
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:         }
Chris@16: 
Chris@16:         // Accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type size () const {
Chris@16:             return size_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz_capacity () const {
Chris@16:             return detail::map_capacity (data ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz () const {
Chris@16:             return data (). size ();
Chris@16:         }
Chris@16: 
Chris@16:         // Storage accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const array_type &data () const {
Chris@16:             return data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         array_type &data () {
Chris@16:             return data_;
Chris@16:         }
Chris@16: 
Chris@16:         // Resizing
Chris@16:     private:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type restrict_capacity (size_type non_zeros) const {
Chris@16:             non_zeros = (std::min) (non_zeros, size_);
Chris@16:             return non_zeros;
Chris@16:         }
Chris@16:     public:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void resize (size_type size, bool preserve = true) {
Chris@16:             size_ = size;
Chris@16:             if (preserve) {
Chris@16:                 data ().erase (data ().lower_bound(size_), data ().end());
Chris@16:             }
Chris@16:             else {
Chris@16:                 data ().clear ();
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Reserving
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void reserve (size_type non_zeros = 0, bool preserve = true) {
Chris@16:             detail::map_reserve (data (), restrict_capacity (non_zeros));
Chris@16:         }
Chris@16: 
Chris@16:         // Element support
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         pointer find_element (size_type i) {
Chris@16:             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_pointer find_element (size_type i) const {
Chris@16:             const_subiterator_type it (data ().find (i));
Chris@16:             if (it == data ().end ())
Chris@16:                 return 0;
Chris@16:             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
Chris@16:             return &(*it).second;
Chris@16:         }
Chris@16: 
Chris@16:         // Element access
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator () (size_type i) const {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             const_subiterator_type it (data ().find (i));
Chris@16:             if (it == data ().end ())
Chris@16:                 return zero_;
Chris@16:             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
Chris@16:             return (*it).second;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference ref (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             std::pair<subiterator_type, bool> ii (data ().insert (typename array_type::value_type (i, value_type/*zero*/())));
Chris@16:             BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ());   // broken map
Chris@16:             return (ii.first)->second;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator () (size_type i) {
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:             return ref (i);
Chris@16: #else
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             return reference (*this, i);
Chris@16: #endif
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator [] (size_type i) const {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator [] (size_type i) {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16: 
Chris@16:         // Element assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference insert_element (size_type i, const_reference t) {
Chris@16:             std::pair<subiterator_type, bool> ii = data ().insert (typename array_type::value_type (i, t));
Chris@16:             BOOST_UBLAS_CHECK (ii.second, bad_index ());        // duplicate element
Chris@16:             BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ());   // broken map
Chris@16:             if (!ii.second)     // existing element
Chris@16:                 (ii.first)->second = t;
Chris@16:             return (ii.first)->second;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void erase_element (size_type i) {
Chris@16:             subiterator_type it = data ().find (i);
Chris@16:             if (it == data ().end ())
Chris@16:                 return;
Chris@16:             data ().erase (it);
Chris@16:         }
Chris@16: 
Chris@16:         // Zeroing
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void clear () {
Chris@16:             data ().clear ();
Chris@16:         }
Chris@16: 
Chris@16:         // Assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator = (const mapped_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 size_ = v.size_;
Chris@16:                 data () = v.data ();
Chris@16:             }
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator = (const vector_container<C> &v) {
Chris@16:             resize (v ().size (), false);
Chris@16:             assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &assign_temporary (mapped_vector &v) {
Chris@16:             swap (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator = (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (ae, detail::map_capacity (data()));
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Computed assignment
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator += (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this + ae, detail::map_capacity (data()));
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator += (const vector_container<C> &v) {
Chris@16:             plus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &plus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_plus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator -= (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this - ae, detail::map_capacity (data()));
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator -= (const vector_container<C> &v) {
Chris@16:             minus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &minus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_minus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator *= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         mapped_vector &operator /= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_divides_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Swapping
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void swap (mapped_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 std::swap (size_, v.size_);
Chris@16:                 data ().swap (v.data ());
Chris@16:             }
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         friend void swap (mapped_vector &v1, mapped_vector &v2) {
Chris@16:             v1.swap (v2);
Chris@16:         }
Chris@16: 
Chris@16:         // Iterator types
Chris@16:     private:
Chris@16:         // Use storage iterator
Chris@16:         typedef typename A::const_iterator const_subiterator_type;
Chris@16:         typedef typename A::iterator subiterator_type;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference at_element (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             subiterator_type it (data ().find (i));
Chris@16:             BOOST_UBLAS_CHECK (it != data ().end(), bad_index ());
Chris@16:             BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ());   // broken map
Chris@16:             return it->second;
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         class const_iterator;
Chris@16:         class iterator;
Chris@16: 
Chris@16:         // Element lookup
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         const_iterator find (size_type i) const {
Chris@16:             return const_iterator (*this, data ().lower_bound (i));
Chris@16:         }
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         iterator find (size_type i) {
Chris@16:             return iterator (*this, data ().lower_bound (i));
Chris@16:         }
Chris@16: 
Chris@16: 
Chris@16:         class const_iterator:
Chris@16:             public container_const_reference<mapped_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                const_iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename mapped_vector::value_type value_type;
Chris@16:             typedef typename mapped_vector::difference_type difference_type;
Chris@16:             typedef typename mapped_vector::const_reference reference;
Chris@16:             typedef const typename mapped_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator ():
Chris@16:                 container_const_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const self_type &v, const const_subiterator_type &it):
Chris@16:                 container_const_reference<self_type> (v), it_ (it) {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
Chris@16:                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*it_).second;
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
Chris@16:                 return (*it_).first;
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator = (const const_iterator &it) {
Chris@16:                 container_const_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const const_iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             const_subiterator_type it_;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator begin () const {
Chris@16:             return const_iterator (*this, data ().begin ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cbegin () const {
Chris@101:             return begin ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator end () const {
Chris@16:             return const_iterator (*this, data ().end ());
Chris@16:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cend () const {
Chris@101:             return end ();
Chris@101:         }
Chris@16: 
Chris@16:         class iterator:
Chris@16:             public container_reference<mapped_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename mapped_vector::value_type value_type;
Chris@16:             typedef typename mapped_vector::difference_type difference_type;
Chris@16:             typedef typename mapped_vector::true_reference reference;
Chris@16:             typedef typename mapped_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator ():
Chris@16:                 container_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator (self_type &v, const subiterator_type &it):
Chris@16:                 container_reference<self_type> (v), it_ (it) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*it_).second;
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
Chris@16:                 return (*it_).first;
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator = (const iterator &it) {
Chris@16:                 container_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             subiterator_type it_;
Chris@16: 
Chris@16:             friend class const_iterator;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator begin () {
Chris@16:             return iterator (*this, data ().begin ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator end () {
Chris@16:             return iterator (*this, data ().end ());
Chris@16:         }
Chris@16: 
Chris@16:         // Reverse iterator
Chris@16:         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
Chris@16:         typedef reverse_iterator_base<iterator> reverse_iterator;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rbegin () const {
Chris@16:             return const_reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crbegin () const {
Chris@101:             return rbegin ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rend () const {
Chris@16:             return const_reverse_iterator (begin ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crend () const {
Chris@101:             return rend ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rbegin () {
Chris@16:             return reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rend () {
Chris@16:             return reverse_iterator (begin ());
Chris@16:         }
Chris@16: 
Chris@16:          // Serialization
Chris@16:         template<class Archive>
Chris@16:         void serialize(Archive & ar, const unsigned int /* file_version */){
Chris@16:             serialization::collection_size_type s (size_);
Chris@16:             ar & serialization::make_nvp("size",s);
Chris@16:             if (Archive::is_loading::value) {
Chris@16:                 size_ = s;
Chris@16:             }
Chris@16:             ar & serialization::make_nvp("data", data_);
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         size_type size_;
Chris@16:         array_type data_;
Chris@16:         static const value_type zero_;
Chris@16:     };
Chris@16: 
Chris@16:     template<class T, class A>
Chris@16:     const typename mapped_vector<T, A>::value_type mapped_vector<T, A>::zero_ = value_type/*zero*/();
Chris@16: 
Chris@16: 
Chris@16:     // Thanks to Kresimir Fresl for extending this to cover different index bases.
Chris@16:     
Chris@16:     /** \brief Compressed array based sparse vector
Chris@16:      *
Chris@16:      * a sparse vector of values of type T of variable size. The non zero values are stored as 
Chris@16:      * two seperate arrays: an index array and a value array. The index array is always sorted 
Chris@16:      * and there is at most one entry for each index. Inserting an element can be time consuming.
Chris@16:      * If the vector contains a few zero entries, then it is better to have a normal vector.
Chris@16:      * If the vector has a very high dimension with a few non-zero values, then this vector is
Chris@16:      * very memory efficient (at the cost of a few more computations).
Chris@16:      *
Chris@16:      * For a \f$n\f$-dimensional compressed vector and \f$0 \leq i < n\f$ the non-zero elements 
Chris@16:      * \f$v_i\f$ are mapped to consecutive elements of the index and value container, i.e. for 
Chris@16:      * elements \f$k = v_{i_1}\f$ and \f$k + 1 = v_{i_2}\f$ of these containers holds \f$i_1 < i_2\f$.
Chris@16:      *
Chris@16:      * Supported parameters for the adapted array (indices and values) are \c unbounded_array<> ,
Chris@16:      * \c bounded_array<> and \c std::vector<>.
Chris@16:      *
Chris@16:      * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
Chris@16:      * \tparam IB the index base of the compressed vector. Default is 0. Other supported value is 1
Chris@16:      * \tparam IA the type of adapted array for indices. Default is \c unbounded_array<std::size_t>
Chris@16:      * \tparam TA the type of adapted array for values. Default is unbounded_array<T>
Chris@16:      */
Chris@16:     template<class T, std::size_t IB, class IA, class TA>
Chris@16:     class compressed_vector:
Chris@16:         public vector_container<compressed_vector<T, IB, IA, TA> > {
Chris@16: 
Chris@16:         typedef T &true_reference;
Chris@16:         typedef T *pointer;
Chris@16:         typedef const T *const_pointer;
Chris@16:         typedef compressed_vector<T, IB, IA, TA> self_type;
Chris@16:     public:
Chris@16: #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
Chris@16:         using vector_container<self_type>::operator ();
Chris@16: #endif
Chris@16:         // ISSUE require type consistency check
Chris@16:         // is_convertable (IA::size_type, TA::size_type)
Chris@16:         typedef typename IA::value_type size_type;
Chris@16:         typedef typename IA::difference_type difference_type;
Chris@16:         typedef T value_type;
Chris@16:         typedef const T &const_reference;
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:         typedef T &reference;
Chris@16: #else
Chris@16:         typedef sparse_vector_element<self_type> reference;
Chris@16: #endif
Chris@16:         typedef IA index_array_type;
Chris@16:         typedef TA value_array_type;
Chris@16:         typedef const vector_reference<const self_type> const_closure_type;
Chris@16:         typedef vector_reference<self_type> closure_type;
Chris@16:         typedef self_type vector_temporary_type;
Chris@16:         typedef sparse_tag storage_category;
Chris@16: 
Chris@16:         // Construction and destruction
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector ():
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (0), capacity_ (restrict_capacity (0)), filled_ (0),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         explicit BOOST_UBLAS_INLINE
Chris@16:         compressed_vector (size_type size, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (size), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:         storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector (const compressed_vector &v):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (v.size_), capacity_ (v.capacity_), filled_ (v.filled_),
Chris@16:             index_data_ (v.index_data_), value_data_ (v.value_data_) {
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:             storage_invariants ();
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:         }
Chris@16: 
Chris@16:         // Accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type size () const {
Chris@16:             return size_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz_capacity () const {
Chris@16:             return capacity_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz () const {
Chris@16:             return filled_;
Chris@16:         }
Chris@16: 
Chris@16:         // Storage accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type index_base () {
Chris@16:             return IB;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         typename index_array_type::size_type filled () const {
Chris@16:             return filled_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const index_array_type &index_data () const {
Chris@16:             return index_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const value_array_type &value_data () const {
Chris@16:             return value_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void set_filled (const typename index_array_type::size_type & filled) {
Chris@16:             filled_ = filled;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         index_array_type &index_data () {
Chris@16:             return index_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         value_array_type &value_data () {
Chris@16:             return value_data_;
Chris@16:         }
Chris@16: 
Chris@16:         // Resizing
Chris@16:     private:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type restrict_capacity (size_type non_zeros) const {
Chris@16:             non_zeros = (std::max) (non_zeros, size_type (1));
Chris@16:             non_zeros = (std::min) (non_zeros, size_);
Chris@16:             return non_zeros;
Chris@16:         }
Chris@16:     public:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void resize (size_type size, bool preserve = true) {
Chris@16:             size_ = size;
Chris@16:             capacity_ = restrict_capacity (capacity_);
Chris@16:             if (preserve) {
Chris@16:                 index_data_. resize (capacity_, size_type ());
Chris@16:                 value_data_. resize (capacity_, value_type ());
Chris@16:                 filled_ = (std::min) (capacity_, filled_);
Chris@16:                 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
Chris@16:                     --filled_;
Chris@16:                 }
Chris@16:             }
Chris@16:             else {
Chris@16:                 index_data_. resize (capacity_);
Chris@16:                 value_data_. resize (capacity_);
Chris@16:                 filled_ = 0;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Reserving
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void reserve (size_type non_zeros, bool preserve = true) {
Chris@16:             capacity_ = restrict_capacity (non_zeros);
Chris@16:             if (preserve) {
Chris@16:                 index_data_. resize (capacity_, size_type ());
Chris@16:                 value_data_. resize (capacity_, value_type ());
Chris@16:                 filled_ = (std::min) (capacity_, filled_);
Chris@16:             }
Chris@16:             else {
Chris@16:                 index_data_. resize (capacity_);
Chris@16:                 value_data_. resize (capacity_);
Chris@16:                 filled_ = 0;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Element support
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         pointer find_element (size_type i) {
Chris@16:             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_pointer find_element (size_type i) const {
Chris@16:             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return 0;
Chris@16:             return &value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16: 
Chris@16:         // Element access
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator () (size_type i) const {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return zero_;
Chris@16:             return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference ref (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return insert_element (i, value_type/*zero*/());
Chris@16:             else
Chris@16:                 return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator () (size_type i) {
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:             return ref (i) ;
Chris@16: #else
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             return reference (*this, i);
Chris@16: #endif
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator [] (size_type i) const {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator [] (size_type i) {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16: 
Chris@16:         // Element assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference insert_element (size_type i, const_reference t) {
Chris@16:             BOOST_UBLAS_CHECK (!find_element (i), bad_index ());        // duplicate element
Chris@16:             if (filled_ >= capacity_)
Chris@16:                 reserve (2 * capacity_, true);
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             // ISSUE max_capacity limit due to difference_type
Chris@16:             typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
Chris@16:             BOOST_UBLAS_CHECK (filled_ == 0 || filled_ == typename index_array_type::size_type (n) || *it != k_based (i), internal_logic ());   // duplicate found by lower_bound
Chris@16:             ++ filled_;
Chris@16:             it = index_data_.begin () + n;
Chris@16:             std::copy_backward (it, index_data_.begin () + filled_ - 1, index_data_.begin () + filled_);
Chris@16:             *it = k_based (i);
Chris@16:             typename value_array_type::iterator itt (value_data_.begin () + n);
Chris@16:             std::copy_backward (itt, value_data_.begin () + filled_ - 1, value_data_.begin () + filled_);
Chris@16:             *itt = t;
Chris@16:             storage_invariants ();
Chris@16:             return *itt;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void erase_element (size_type i) {
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             typename std::iterator_traits<subiterator_type>::difference_type  n = it - index_data_.begin ();
Chris@16:             if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
Chris@16:                 std::copy (it + 1, index_data_.begin () + filled_, it);
Chris@16:                 typename value_array_type::iterator itt (value_data_.begin () + n);
Chris@16:                 std::copy (itt + 1, value_data_.begin () + filled_, itt);
Chris@16:                 -- filled_;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Zeroing
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void clear () {
Chris@16:             filled_ = 0;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator = (const compressed_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 size_ = v.size_;
Chris@16:                 capacity_ = v.capacity_;
Chris@16:                 filled_ = v.filled_;
Chris@16:                 index_data_ = v.index_data_;
Chris@16:                 value_data_ = v.value_data_;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator = (const vector_container<C> &v) {
Chris@16:             resize (v ().size (), false);
Chris@16:             assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &assign_temporary (compressed_vector &v) {
Chris@16:             swap (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator = (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Computed assignment
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator += (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this + ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator += (const vector_container<C> &v) {
Chris@16:             plus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &plus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_plus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator -= (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this - ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator -= (const vector_container<C> &v) {
Chris@16:             minus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &minus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_minus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator *= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         compressed_vector &operator /= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_divides_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Swapping
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void swap (compressed_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 std::swap (size_, v.size_);
Chris@16:                 std::swap (capacity_, v.capacity_);
Chris@16:                 std::swap (filled_, v.filled_);
Chris@16:                 index_data_.swap (v.index_data_);
Chris@16:                 value_data_.swap (v.value_data_);
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         friend void swap (compressed_vector &v1, compressed_vector &v2) {
Chris@16:             v1.swap (v2);
Chris@16:         }
Chris@16: 
Chris@16:         // Back element insertion and erasure
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void push_back (size_type i, const_reference t) {
Chris@16:             BOOST_UBLAS_CHECK (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i), external_logic ());
Chris@16:             if (filled_ >= capacity_)
Chris@16:                 reserve (2 * capacity_, true);
Chris@16:             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
Chris@16:             index_data_ [filled_] = k_based (i);
Chris@16:             value_data_ [filled_] = t;
Chris@16:             ++ filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void pop_back () {
Chris@16:             BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
Chris@16:             -- filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Iterator types
Chris@16:     private:
Chris@16:         // Use index array iterator
Chris@16:         typedef typename IA::const_iterator const_subiterator_type;
Chris@16:         typedef typename IA::iterator subiterator_type;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference at_element (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
Chris@16:             return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         class const_iterator;
Chris@16:         class iterator;
Chris@16: 
Chris@16:         // Element lookup
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         const_iterator find (size_type i) const {
Chris@16:             return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:         }
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         iterator find (size_type i) {
Chris@16:             return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:         }
Chris@16: 
Chris@16: 
Chris@16:         class const_iterator:
Chris@16:             public container_const_reference<compressed_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                const_iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename compressed_vector::value_type value_type;
Chris@16:             typedef typename compressed_vector::difference_type difference_type;
Chris@16:             typedef typename compressed_vector::const_reference reference;
Chris@16:             typedef const typename compressed_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator ():
Chris@16:                 container_const_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const self_type &v, const const_subiterator_type &it):
Chris@16:                 container_const_reference<self_type> (v), it_ (it) {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
Chris@16:                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().zero_based (*it_);
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator = (const const_iterator &it) {
Chris@16:                 container_const_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const const_iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             const_subiterator_type it_;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator begin () const {
Chris@16:             return find (0);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cbegin () const {
Chris@101:             return begin ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator end () const {
Chris@16:             return find (size_);
Chris@16:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cend () const {
Chris@101:             return end ();
Chris@101:         }
Chris@16: 
Chris@16:         class iterator:
Chris@16:             public container_reference<compressed_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename compressed_vector::value_type value_type;
Chris@16:             typedef typename compressed_vector::difference_type difference_type;
Chris@16:             typedef typename compressed_vector::true_reference reference;
Chris@16:             typedef typename compressed_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator ():
Chris@16:                 container_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator (self_type &v, const subiterator_type &it):
Chris@16:                 container_reference<self_type> (v), it_ (it) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().zero_based (*it_);
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator = (const iterator &it) {
Chris@16:                 container_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             subiterator_type it_;
Chris@16: 
Chris@16:             friend class const_iterator;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator begin () {
Chris@16:             return find (0);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator end () {
Chris@16:             return find (size_);
Chris@16:         }
Chris@16: 
Chris@16:         // Reverse iterator
Chris@16:         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
Chris@16:         typedef reverse_iterator_base<iterator> reverse_iterator;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rbegin () const {
Chris@16:             return const_reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crbegin () const {
Chris@101:             return rbegin ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rend () const {
Chris@16:             return const_reverse_iterator (begin ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crend () const {
Chris@101:             return rend ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rbegin () {
Chris@16:             return reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rend () {
Chris@16:             return reverse_iterator (begin ());
Chris@16:         }
Chris@16: 
Chris@16:          // Serialization
Chris@16:         template<class Archive>
Chris@16:         void serialize(Archive & ar, const unsigned int /* file_version */){
Chris@16:             serialization::collection_size_type s (size_);
Chris@16:             ar & serialization::make_nvp("size",s);
Chris@16:             if (Archive::is_loading::value) {
Chris@16:                 size_ = s;
Chris@16:             }
Chris@16:             // ISSUE: filled may be much less than capacity
Chris@16:             // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
Chris@16:             ar & serialization::make_nvp("capacity", capacity_);
Chris@16:             ar & serialization::make_nvp("filled", filled_);
Chris@16:             ar & serialization::make_nvp("index_data", index_data_);
Chris@16:             ar & serialization::make_nvp("value_data", value_data_);
Chris@16:             storage_invariants();
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         void storage_invariants () const
Chris@16:         {
Chris@16:             BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
Chris@16:         }
Chris@16: 
Chris@16:         size_type size_;
Chris@16:         typename index_array_type::size_type capacity_;
Chris@16:         typename index_array_type::size_type filled_;
Chris@16:         index_array_type index_data_;
Chris@16:         value_array_type value_data_;
Chris@16:         static const value_type zero_;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type zero_based (size_type k_based_index) {
Chris@16:             return k_based_index - IB;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type k_based (size_type zero_based_index) {
Chris@16:             return zero_based_index + IB;
Chris@16:         }
Chris@16: 
Chris@16:         friend class iterator;
Chris@16:         friend class const_iterator;
Chris@16:     };
Chris@16: 
Chris@16:     template<class T, std::size_t IB, class IA, class TA>
Chris@16:     const typename compressed_vector<T, IB, IA, TA>::value_type compressed_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
Chris@16: 
Chris@16:     // Thanks to Kresimir Fresl for extending this to cover different index bases.
Chris@16: 
Chris@16:     /** \brief Coordimate array based sparse vector
Chris@16:      *
Chris@16:      * a sparse vector of values of type \c T of variable size. The non zero values are stored 
Chris@16:      * as two seperate arrays: an index array and a value array. The arrays may be out of order 
Chris@16:      * with multiple entries for each vector element. If there are multiple values for the same 
Chris@16:      * index the sum of these values is the real value. It is way more efficient for inserting values
Chris@16:      * than a \c compressed_vector but less memory efficient. Also linearly parsing a vector can 
Chris@16:      * be longer in specific cases than a \c compressed_vector.
Chris@16:      *
Chris@16:      * For a n-dimensional sorted coordinate vector and \f$ 0 \leq i < n\f$ the non-zero elements 
Chris@16:      * \f$v_i\f$ are mapped to consecutive elements of the index and value container, i.e. for 
Chris@16:      * elements \f$k = v_{i_1}\f$ and \f$k + 1 = v_{i_2}\f$ of these containers holds \f$i_1 < i_2\f$.
Chris@16:      *
Chris@16:      * Supported parameters for the adapted array (indices and values) are \c unbounded_array<> ,
Chris@16:      * \c bounded_array<> and \c std::vector<>.
Chris@16:      *
Chris@16:      * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
Chris@16:      * \tparam IB the index base of the compressed vector. Default is 0. Other supported value is 1
Chris@16:      * \tparam IA the type of adapted array for indices. Default is \c unbounded_array<std::size_t>
Chris@16:      * \tparam TA the type of adapted array for values. Default is unbounded_array<T>
Chris@16:      */
Chris@16:     template<class T, std::size_t IB, class IA, class TA>
Chris@16:     class coordinate_vector:
Chris@16:         public vector_container<coordinate_vector<T, IB, IA, TA> > {
Chris@16: 
Chris@16:         typedef T &true_reference;
Chris@16:         typedef T *pointer;
Chris@16:         typedef const T *const_pointer;
Chris@16:         typedef coordinate_vector<T, IB, IA, TA> self_type;
Chris@16:     public:
Chris@16: #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
Chris@16:         using vector_container<self_type>::operator ();
Chris@16: #endif
Chris@16:         // ISSUE require type consistency check
Chris@16:         // is_convertable (IA::size_type, TA::size_type)
Chris@16:         typedef typename IA::value_type size_type;
Chris@16:         typedef typename IA::difference_type difference_type;
Chris@16:         typedef T value_type;
Chris@16:         typedef const T &const_reference;
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:         typedef T &reference;
Chris@16: #else
Chris@16:         typedef sparse_vector_element<self_type> reference;
Chris@16: #endif
Chris@16:         typedef IA index_array_type;
Chris@16:         typedef TA value_array_type;
Chris@16:         typedef const vector_reference<const self_type> const_closure_type;
Chris@16:         typedef vector_reference<self_type> closure_type;
Chris@16:         typedef self_type vector_temporary_type;
Chris@16:         typedef sparse_tag storage_category;
Chris@16: 
Chris@16:         // Construction and destruction
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector ():
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (0), capacity_ (restrict_capacity (0)),
Chris@16:             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         explicit BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector (size_type size, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (size), capacity_ (restrict_capacity (non_zeros)),
Chris@16:             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector (const coordinate_vector &v):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (v.size_), capacity_ (v.capacity_),
Chris@16:             filled_ (v.filled_), sorted_filled_ (v.sorted_filled_), sorted_ (v.sorted_),
Chris@16:             index_data_ (v.index_data_), value_data_ (v.value_data_) {
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
Chris@16:             vector_container<self_type> (),
Chris@16:             size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)),
Chris@16:             filled_ (0), sorted_filled_ (filled_), sorted_ (true),
Chris@16:             index_data_ (capacity_), value_data_ (capacity_) {
Chris@16:             storage_invariants ();
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:         }
Chris@16: 
Chris@16:         // Accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type size () const {
Chris@16:             return size_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz_capacity () const {
Chris@16:             return capacity_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type nnz () const {
Chris@16:             return filled_;
Chris@16:         }
Chris@16: 
Chris@16:         // Storage accessors
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type index_base () {
Chris@16:             return IB;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         typename index_array_type::size_type filled () const {
Chris@16:             return filled_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const index_array_type &index_data () const {
Chris@16:             return index_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const value_array_type &value_data () const {
Chris@16:             return value_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void set_filled (const typename index_array_type::size_type &sorted, const typename index_array_type::size_type &filled) {
Chris@16:             sorted_filled_ = sorted;
Chris@16:             filled_ = filled;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         index_array_type &index_data () {
Chris@16:             return index_data_;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         value_array_type &value_data () {
Chris@16:             return value_data_;
Chris@16:         }
Chris@16: 
Chris@16:         // Resizing
Chris@16:     private:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         size_type restrict_capacity (size_type non_zeros) const {
Chris@16:              // minimum non_zeros
Chris@16:              non_zeros = (std::max) (non_zeros, size_type (1));
Chris@16:              // ISSUE no maximum as coordinate may contain inserted duplicates
Chris@16:              return non_zeros;
Chris@16:         }
Chris@16:     public:
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void resize (size_type size, bool preserve = true) {
Chris@16:             if (preserve)
Chris@16:                 sort ();    // remove duplicate elements.
Chris@16:             size_ = size;
Chris@16:             capacity_ = restrict_capacity (capacity_);
Chris@16:             if (preserve) {
Chris@16:                 index_data_. resize (capacity_, size_type ());
Chris@16:                 value_data_. resize (capacity_, value_type ());
Chris@16:                 filled_ = (std::min) (capacity_, filled_);
Chris@16:                 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
Chris@16:                     --filled_;
Chris@16:                 }
Chris@16:             }
Chris@16:             else {
Chris@16:                 index_data_. resize (capacity_);
Chris@16:                 value_data_. resize (capacity_);
Chris@16:                 filled_ = 0;
Chris@16:             }
Chris@16:             sorted_filled_ = filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         // Reserving
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void reserve (size_type non_zeros, bool preserve = true) {
Chris@16:             if (preserve)
Chris@16:                 sort ();    // remove duplicate elements.
Chris@16:             capacity_ = restrict_capacity (non_zeros);
Chris@16:             if (preserve) {
Chris@16:                 index_data_. resize (capacity_, size_type ());
Chris@16:                 value_data_. resize (capacity_, value_type ());
Chris@16:                 filled_ = (std::min) (capacity_, filled_);
Chris@16:                 }
Chris@16:             else {
Chris@16:                 index_data_. resize (capacity_);
Chris@16:                 value_data_. resize (capacity_);
Chris@16:                 filled_ = 0;
Chris@16:             }
Chris@16:             sorted_filled_ = filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Element support
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         pointer find_element (size_type i) {
Chris@16:             return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_pointer find_element (size_type i) const {
Chris@16:             sort ();
Chris@16:             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return 0;
Chris@16:             return &value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16: 
Chris@16:         // Element access
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator () (size_type i) const {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             sort ();
Chris@16:             const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return zero_;
Chris@16:             return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference ref (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             sort ();
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             if (it == index_data_.begin () + filled_ || *it != k_based (i))
Chris@16:                 return insert_element (i, value_type/*zero*/());
Chris@16:             else
Chris@16:                 return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator () (size_type i) {
Chris@16: #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
Chris@16:             return ref (i);
Chris@16: #else
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             return reference (*this, i);
Chris@16: #endif
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reference operator [] (size_type i) const {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reference operator [] (size_type i) {
Chris@16:             return (*this) (i);
Chris@16:         }
Chris@16: 
Chris@16:         // Element assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void append_element (size_type i, const_reference t) {
Chris@16:             if (filled_ >= capacity_)
Chris@16:                 reserve (2 * filled_, true);
Chris@16:             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
Chris@16:             index_data_ [filled_] = k_based (i);
Chris@16:             value_data_ [filled_] = t;
Chris@16:             ++ filled_;
Chris@16:             sorted_ = false;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference insert_element (size_type i, const_reference t) {
Chris@16:             BOOST_UBLAS_CHECK (!find_element (i), bad_index ());        // duplicate element
Chris@16:             append_element (i, t);
Chris@16:             return value_data_ [filled_ - 1];
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void erase_element (size_type i) {
Chris@16:             sort ();
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
Chris@16:             if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
Chris@16:                 std::copy (it + 1, index_data_.begin () + filled_, it);
Chris@16:                 typename value_array_type::iterator itt (value_data_.begin () + n);
Chris@16:                 std::copy (itt + 1, value_data_.begin () + filled_, itt);
Chris@16:                 -- filled_;
Chris@16:                 sorted_filled_ = filled_;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Zeroing
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void clear () {
Chris@16:             filled_ = 0;
Chris@16:             sorted_filled_ = filled_;
Chris@16:             sorted_ = true;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Assignment
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator = (const coordinate_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 size_ = v.size_;
Chris@16:                 capacity_ = v.capacity_;
Chris@16:                 filled_ = v.filled_;
Chris@16:                 sorted_filled_ = v.sorted_filled_;
Chris@16:                 sorted_ = v.sorted_;
Chris@16:                 index_data_ = v.index_data_;
Chris@16:                 value_data_ = v.value_data_;
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator = (const vector_container<C> &v) {
Chris@16:             resize (v ().size (), false);
Chris@16:             assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &assign_temporary (coordinate_vector &v) {
Chris@16:             swap (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator = (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Computed assignment
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator += (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this + ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator += (const vector_container<C> &v) {
Chris@16:             plus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &plus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_plus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator -= (const vector_expression<AE> &ae) {
Chris@16:             self_type temporary (*this - ae, capacity_);
Chris@16:             return assign_temporary (temporary);
Chris@16:         }
Chris@16:         template<class C>          // Container assignment without temporary
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator -= (const vector_container<C> &v) {
Chris@16:             minus_assign (v);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AE>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &minus_assign (const vector_expression<AE> &ae) {
Chris@16:             vector_assign<scalar_minus_assign> (*this, ae);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator *= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_multiplies_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16:         template<class AT>
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         coordinate_vector &operator /= (const AT &at) {
Chris@16:             vector_assign_scalar<scalar_divides_assign> (*this, at);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         // Swapping
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void swap (coordinate_vector &v) {
Chris@16:             if (this != &v) {
Chris@16:                 std::swap (size_, v.size_);
Chris@16:                 std::swap (capacity_, v.capacity_);
Chris@16:                 std::swap (filled_, v.filled_);
Chris@16:                 std::swap (sorted_filled_, v.sorted_filled_);
Chris@16:                 std::swap (sorted_, v.sorted_);
Chris@16:                 index_data_.swap (v.index_data_);
Chris@16:                 value_data_.swap (v.value_data_);
Chris@16:             }
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         friend void swap (coordinate_vector &v1, coordinate_vector &v2) {
Chris@16:             v1.swap (v2);
Chris@16:         }
Chris@16: 
Chris@16:         // replacement if STL lower bound algorithm for use of inplace_merge
Chris@16:         size_type lower_bound (size_type beg, size_type end, size_type target) const {
Chris@16:             while (end > beg) {
Chris@16:                 size_type mid = (beg + end) / 2;
Chris@16:                 if (index_data_[mid] < index_data_[target]) {
Chris@16:                     beg = mid + 1;
Chris@16:                 } else {
Chris@16:                     end = mid;
Chris@16:                 }
Chris@16:             }
Chris@16:             return beg;
Chris@16:         }
Chris@16: 
Chris@16:         // specialized replacement of STL inplace_merge to avoid compilation
Chris@16:         // problems with respect to the array_triple iterator
Chris@16:         void inplace_merge (size_type beg, size_type mid, size_type end) const {
Chris@16:             size_type len_lef = mid - beg;
Chris@16:             size_type len_rig = end - mid;
Chris@16: 
Chris@16:             if (len_lef == 1 && len_rig == 1) {
Chris@16:                 if (index_data_[mid] < index_data_[beg]) {
Chris@16:                     std::swap(index_data_[beg], index_data_[mid]);
Chris@16:                     std::swap(value_data_[beg], value_data_[mid]);
Chris@16:                 }
Chris@16:             } else if (len_lef > 0 && len_rig > 0) {
Chris@16:                 size_type lef_mid, rig_mid;
Chris@16:                 if (len_lef >= len_rig) {
Chris@16:                     lef_mid = (beg + mid) / 2;
Chris@16:                     rig_mid = lower_bound(mid, end, lef_mid);
Chris@16:                 } else {
Chris@16:                     rig_mid = (mid + end) / 2;
Chris@16:                     lef_mid = lower_bound(beg, mid, rig_mid);
Chris@16:                 }
Chris@16:                 std::rotate(&index_data_[0] + lef_mid, &index_data_[0] + mid, &index_data_[0] + rig_mid);
Chris@16:                 std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
Chris@16: 
Chris@16:                 size_type new_mid = lef_mid + rig_mid - mid;
Chris@16:                 inplace_merge(beg, lef_mid, new_mid);
Chris@16:                 inplace_merge(new_mid, rig_mid, end);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Sorting and summation of duplicates
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void sort () const {
Chris@16:             if (! sorted_ && filled_ > 0) {
Chris@16:                 typedef index_pair_array<index_array_type, value_array_type> array_pair;
Chris@16:                 array_pair ipa (filled_, index_data_, value_data_);
Chris@16: #ifndef BOOST_UBLAS_COO_ALWAYS_DO_FULL_SORT
Chris@16:                 const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
Chris@16:                 // sort new elements and merge
Chris@16:                 std::sort (iunsorted, ipa.end ());
Chris@16:                 inplace_merge(0, sorted_filled_, filled_);
Chris@16: #else
Chris@16:                 const typename array_pair::iterator iunsorted = ipa.begin ();
Chris@16:                 std::sort (iunsorted, ipa.end ());
Chris@16: #endif
Chris@16: 
Chris@16:                 // sum duplicates with += and remove
Chris@16:                 size_type filled = 0;
Chris@16:                 for (size_type i = 1; i < filled_; ++ i) {
Chris@16:                     if (index_data_ [filled] != index_data_ [i]) {
Chris@16:                         ++ filled;
Chris@16:                         if (filled != i) {
Chris@16:                             index_data_ [filled] = index_data_ [i];
Chris@16:                             value_data_ [filled] = value_data_ [i];
Chris@16:                         }
Chris@16:                     } else {
Chris@16:                         value_data_ [filled] += value_data_ [i];
Chris@16:                     }
Chris@16:                 }
Chris@16:                 filled_ = filled + 1;
Chris@16:                 sorted_filled_ = filled_;
Chris@16:                 sorted_ = true;
Chris@16:                 storage_invariants ();
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Back element insertion and erasure
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void push_back (size_type i, const_reference t) {
Chris@16:             // must maintain sort order
Chris@16:             BOOST_UBLAS_CHECK (sorted_ && (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i)), external_logic ());
Chris@16:             if (filled_ >= capacity_)
Chris@16:                 reserve (2 * filled_, true);
Chris@16:             BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
Chris@16:             index_data_ [filled_] = k_based (i);
Chris@16:             value_data_ [filled_] = t;
Chris@16:             ++ filled_;
Chris@16:             sorted_filled_ = filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         void pop_back () {
Chris@16:             // ISSUE invariants could be simpilfied if sorted required as precondition
Chris@16:             BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
Chris@16:             -- filled_;
Chris@16:             sorted_filled_ = (std::min) (sorted_filled_, filled_);
Chris@16:             sorted_ = sorted_filled_ = filled_;
Chris@16:             storage_invariants ();
Chris@16:         }
Chris@16: 
Chris@16:         // Iterator types
Chris@16:     private:
Chris@16:         // Use index array iterator
Chris@16:         typedef typename IA::const_iterator const_subiterator_type;
Chris@16:         typedef typename IA::iterator subiterator_type;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         true_reference at_element (size_type i) {
Chris@16:             BOOST_UBLAS_CHECK (i < size_, bad_index ());
Chris@16:             sort ();
Chris@16:             subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:             BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
Chris@16:             return value_data_ [it - index_data_.begin ()];
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         class const_iterator;
Chris@16:         class iterator;
Chris@16: 
Chris@16:         // Element lookup
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         const_iterator find (size_type i) const {
Chris@16:             sort ();
Chris@16:             return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:         }
Chris@16:         // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
Chris@16:         iterator find (size_type i) {
Chris@16:             sort ();
Chris@16:             return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
Chris@16:         }
Chris@16: 
Chris@16: 
Chris@16:         class const_iterator:
Chris@16:             public container_const_reference<coordinate_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                const_iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename coordinate_vector::value_type value_type;
Chris@16:             typedef typename coordinate_vector::difference_type difference_type;
Chris@16:             typedef typename coordinate_vector::const_reference reference;
Chris@16:             typedef const typename coordinate_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator ():
Chris@16:                 container_const_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const self_type &v, const const_subiterator_type &it):
Chris@16:                 container_const_reference<self_type> (v), it_ (it) {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator (const typename self_type::iterator &it):  // ISSUE self_type:: stops VC8 using std::iterator here
Chris@16:                 container_const_reference<self_type> (it ()), it_ (it.it_) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().zero_based (*it_);
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             const_iterator &operator = (const const_iterator &it) {
Chris@16:                 container_const_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const const_iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             const_subiterator_type it_;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator begin () const {
Chris@16:             return find (0);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cbegin () const {
Chris@101:             return begin();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_iterator end () const {
Chris@16:             return find (size_);
Chris@16:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@101:         const_iterator cend () const {
Chris@101:             return end();
Chris@101:         }
Chris@16: 
Chris@16:         class iterator:
Chris@16:             public container_reference<coordinate_vector>,
Chris@16:             public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
Chris@16:                                                iterator, value_type> {
Chris@16:         public:
Chris@16:             typedef typename coordinate_vector::value_type value_type;
Chris@16:             typedef typename coordinate_vector::difference_type difference_type;
Chris@16:             typedef typename coordinate_vector::true_reference reference;
Chris@16:             typedef typename coordinate_vector::pointer pointer;
Chris@16: 
Chris@16:             // Construction and destruction
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator ():
Chris@16:                 container_reference<self_type> (), it_ () {}
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator (self_type &v, const subiterator_type &it):
Chris@16:                 container_reference<self_type> (v), it_ (it) {}
Chris@16: 
Chris@16:             // Arithmetic
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator ++ () {
Chris@16:                 ++ it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator -- () {
Chris@16:                 -- it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Dereference
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             reference operator * () const {
Chris@16:                 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
Chris@16:             }
Chris@16: 
Chris@16:             // Index
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             size_type index () const {
Chris@16:                 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
Chris@16:                 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
Chris@16:                 return (*this) ().zero_based (*it_);
Chris@16:             }
Chris@16: 
Chris@16:             // Assignment
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             iterator &operator = (const iterator &it) {
Chris@16:                 container_reference<self_type>::assign (&it ());
Chris@16:                 it_ = it.it_;
Chris@16:                 return *this;
Chris@16:             }
Chris@16: 
Chris@16:             // Comparison
Chris@16:             BOOST_UBLAS_INLINE
Chris@16:             bool operator == (const iterator &it) const {
Chris@16:                 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
Chris@16:                 return it_ == it.it_;
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             subiterator_type it_;
Chris@16: 
Chris@16:             friend class const_iterator;
Chris@16:         };
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator begin () {
Chris@16:             return find (0);
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         iterator end () {
Chris@16:             return find (size_);
Chris@16:         }
Chris@16: 
Chris@16:         // Reverse iterator
Chris@16:         typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
Chris@16:         typedef reverse_iterator_base<iterator> reverse_iterator;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rbegin () const {
Chris@16:             return const_reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crbegin () const {
Chris@101:             return rbegin ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         const_reverse_iterator rend () const {
Chris@16:             return const_reverse_iterator (begin ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@101:         const_reverse_iterator crend () const {
Chris@101:             return rend ();
Chris@101:         }
Chris@101:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rbegin () {
Chris@16:             return reverse_iterator (end ());
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         reverse_iterator rend () {
Chris@16:             return reverse_iterator (begin ());
Chris@16:         }
Chris@16: 
Chris@16:          // Serialization
Chris@16:         template<class Archive>
Chris@16:         void serialize(Archive & ar, const unsigned int /* file_version */){
Chris@16:             serialization::collection_size_type s (size_);
Chris@16:             ar & serialization::make_nvp("size",s);
Chris@16:             if (Archive::is_loading::value) {
Chris@16:                 size_ = s;
Chris@16:             }
Chris@16:             // ISSUE: filled may be much less than capacity
Chris@16:             // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
Chris@16:             ar & serialization::make_nvp("capacity", capacity_);
Chris@16:             ar & serialization::make_nvp("filled", filled_);
Chris@16:             ar & serialization::make_nvp("sorted_filled", sorted_filled_);
Chris@16:             ar & serialization::make_nvp("sorted", sorted_);
Chris@16:             ar & serialization::make_nvp("index_data", index_data_);
Chris@16:             ar & serialization::make_nvp("value_data", value_data_);
Chris@16:             storage_invariants();
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         void storage_invariants () const
Chris@16:         {
Chris@16:             BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (sorted_filled_ <= filled_, internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK (sorted_ == (sorted_filled_ == filled_), internal_logic ());
Chris@16:             BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
Chris@16:         }
Chris@16: 
Chris@16:         size_type size_;
Chris@16:         size_type capacity_;
Chris@16:         mutable typename index_array_type::size_type filled_;
Chris@16:         mutable typename index_array_type::size_type sorted_filled_;
Chris@16:         mutable bool sorted_;
Chris@16:         mutable index_array_type index_data_;
Chris@16:         mutable value_array_type value_data_;
Chris@16:         static const value_type zero_;
Chris@16: 
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type zero_based (size_type k_based_index) {
Chris@16:             return k_based_index - IB;
Chris@16:         }
Chris@16:         BOOST_UBLAS_INLINE
Chris@16:         static size_type k_based (size_type zero_based_index) {
Chris@16:             return zero_based_index + IB;
Chris@16:         }
Chris@16: 
Chris@16:         friend class iterator;
Chris@16:         friend class const_iterator;
Chris@16:     };
Chris@16: 
Chris@16:     template<class T, std::size_t IB, class IA, class TA>
Chris@16:     const typename coordinate_vector<T, IB, IA, TA>::value_type coordinate_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
Chris@16: 
Chris@16: }}}
Chris@16: 
Chris@16: #endif