2 // Copyright (c) 2000-2002
3 // Joerg Walter, Mathias Koch
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 // The authors gratefully acknowledge the support of
10 // GeNeSys mbH & Co. KG in producing this work.
13 #ifndef _BOOST_UBLAS_VECTOR_SPARSE_
14 #define _BOOST_UBLAS_VECTOR_SPARSE_
16 #include <boost/config.hpp>
18 // In debug mode, MSCV enables iterator debugging, which additional checks are
19 // executed for consistency. So, when two iterators are compared, it is tested
20 // that they point to elements of the same container. If the check fails, then
21 // the program is aborted.
23 // When matrices MVOV are traversed by column and then by row, the previous
26 // MVOV::iterator2 iter2 = mvov.begin2();
27 // for (; iter2 != mvov.end() ; iter2++) {
28 // MVOV::iterator1 iter1 = iter2.begin();
32 // These additional checks in iterators are disabled in this file, but their
33 // status are restored at the end of file.
34 // https://msdn.microsoft.com/en-us/library/hh697468.aspx
36 #define _BACKUP_ITERATOR_DEBUG_LEVEL _ITERATOR_DEBUG_LEVEL
37 #undef _ITERATOR_DEBUG_LEVEL
38 #define _ITERATOR_DEBUG_LEVEL 0
41 #include <boost/numeric/ublas/storage_sparse.hpp>
42 #include <boost/numeric/ublas/vector_expression.hpp>
43 #include <boost/numeric/ublas/detail/vector_assign.hpp>
44 #if BOOST_UBLAS_TYPE_CHECK
45 #include <boost/numeric/ublas/vector.hpp>
48 // Iterators based on ideas of Jeremy Siek
50 namespace boost { namespace numeric { namespace ublas {
52 #ifdef BOOST_UBLAS_STRICT_VECTOR_SPARSE
55 class sparse_vector_element:
56 public container_reference<V> {
58 typedef V vector_type;
59 typedef typename V::size_type size_type;
60 typedef typename V::value_type value_type;
61 typedef const value_type &const_reference;
62 typedef value_type *pointer;
65 // Proxied element operations
67 pointer p = (*this) ().find_element (i_);
71 d_ = value_type/*zero*/();
74 void set (const value_type &s) const {
75 pointer p = (*this) ().find_element (i_);
77 (*this) ().insert_element (i_, s);
83 // Construction and destruction
84 sparse_vector_element (vector_type &v, size_type i):
85 container_reference<vector_type> (v), i_ (i) {
88 sparse_vector_element (const sparse_vector_element &p):
89 container_reference<vector_type> (p), i_ (p.i_) {}
91 ~sparse_vector_element () {
96 sparse_vector_element &operator = (const sparse_vector_element &p) {
97 // Overide the implict copy assignment
104 sparse_vector_element &operator = (const D &d) {
110 sparse_vector_element &operator += (const D &d) {
118 sparse_vector_element &operator -= (const D &d) {
126 sparse_vector_element &operator *= (const D &d) {
134 sparse_vector_element &operator /= (const D &d) {
144 bool operator == (const D &d) const {
150 bool operator != (const D &d) const {
155 // Conversion - weak link in proxy as d_ is not a perfect alias for the element
157 operator const_reference () const {
162 // Conversion to reference - may be invalidated
164 value_type& ref () const {
165 const pointer p = (*this) ().find_element (i_);
167 return (*this) ().insert_element (i_, value_type/*zero*/());
174 mutable value_type d_;
178 * Generalise explicit reference access
182 struct element_reference {
183 typedef R& reference;
184 static reference get_reference (reference r)
190 struct element_reference<sparse_vector_element<V> > {
191 typedef typename V::value_type& reference;
192 static reference get_reference (const sparse_vector_element<V>& sve)
199 typename detail::element_reference<VER>::reference ref (VER& ver) {
200 return detail::element_reference<VER>::get_reference (ver);
203 typename detail::element_reference<VER>::reference ref (const VER& ver) {
204 return detail::element_reference<VER>::get_reference (ver);
209 struct type_traits<sparse_vector_element<V> > {
210 typedef typename V::value_type element_type;
211 typedef type_traits<sparse_vector_element<V> > self_type;
212 typedef typename type_traits<element_type>::value_type value_type;
213 typedef typename type_traits<element_type>::const_reference const_reference;
214 typedef sparse_vector_element<V> reference;
215 typedef typename type_traits<element_type>::real_type real_type;
216 typedef typename type_traits<element_type>::precision_type precision_type;
218 static const unsigned plus_complexity = type_traits<element_type>::plus_complexity;
219 static const unsigned multiplies_complexity = type_traits<element_type>::multiplies_complexity;
223 real_type real (const_reference t) {
224 return type_traits<element_type>::real (t);
228 real_type imag (const_reference t) {
229 return type_traits<element_type>::imag (t);
233 value_type conj (const_reference t) {
234 return type_traits<element_type>::conj (t);
239 real_type type_abs (const_reference t) {
240 return type_traits<element_type>::type_abs (t);
244 value_type type_sqrt (const_reference t) {
245 return type_traits<element_type>::type_sqrt (t);
250 real_type norm_1 (const_reference t) {
251 return type_traits<element_type>::norm_1 (t);
255 real_type norm_2 (const_reference t) {
256 return type_traits<element_type>::norm_2 (t);
260 real_type norm_inf (const_reference t) {
261 return type_traits<element_type>::norm_inf (t);
266 bool equals (const_reference t1, const_reference t2) {
267 return type_traits<element_type>::equals (t1, t2);
271 template<class V1, class T2>
272 struct promote_traits<sparse_vector_element<V1>, T2> {
273 typedef typename promote_traits<typename sparse_vector_element<V1>::value_type, T2>::promote_type promote_type;
275 template<class T1, class V2>
276 struct promote_traits<T1, sparse_vector_element<V2> > {
277 typedef typename promote_traits<T1, typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
279 template<class V1, class V2>
280 struct promote_traits<sparse_vector_element<V1>, sparse_vector_element<V2> > {
281 typedef typename promote_traits<typename sparse_vector_element<V1>::value_type,
282 typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
288 /** \brief Index map based sparse vector
290 * A sparse vector of values of type T of variable size. The sparse storage type A can be
291 * \c std::map<size_t, T> or \c map_array<size_t, T>. This means that only non-zero elements
292 * are effectively stored.
294 * For a \f$n\f$-dimensional sparse vector, and 0 <= i < n the non-zero elements \f$v_i\f$
295 * are mapped to consecutive elements of the associative container, i.e. for elements
296 * \f$k = v_{i_1}\f$ and \f$k + 1 = v_{i_2}\f$ of the container, holds \f$i_1 < i_2\f$.
298 * Supported parameters for the adapted array are \c map_array<std::size_t, T> and
299 * \c map_std<std::size_t, T>. The latter is equivalent to \c std::map<std::size_t, T>.
301 * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
302 * \tparam A the type of Storage array
304 template<class T, class A>
306 public vector_container<mapped_vector<T, A> > {
308 typedef T &true_reference;
310 typedef const T *const_pointer;
311 typedef mapped_vector<T, A> self_type;
313 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
314 using vector_container<self_type>::operator ();
316 typedef typename A::size_type size_type;
317 typedef typename A::difference_type difference_type;
318 typedef T value_type;
319 typedef A array_type;
320 typedef const value_type &const_reference;
321 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
322 typedef typename detail::map_traits<A,T>::reference reference;
324 typedef sparse_vector_element<self_type> reference;
326 typedef const vector_reference<const self_type> const_closure_type;
327 typedef vector_reference<self_type> closure_type;
328 typedef self_type vector_temporary_type;
329 typedef sparse_tag storage_category;
331 // Construction and destruction
334 vector_container<self_type> (),
335 size_ (0), data_ () {}
337 mapped_vector (size_type size, size_type non_zeros = 0):
338 vector_container<self_type> (),
339 size_ (size), data_ () {
340 detail::map_reserve (data(), restrict_capacity (non_zeros));
343 mapped_vector (const mapped_vector &v):
344 vector_container<self_type> (),
345 size_ (v.size_), data_ (v.data_) {}
348 mapped_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
349 vector_container<self_type> (),
350 size_ (ae ().size ()), data_ () {
351 detail::map_reserve (data(), restrict_capacity (non_zeros));
352 vector_assign<scalar_assign> (*this, ae);
357 size_type size () const {
361 size_type nnz_capacity () const {
362 return detail::map_capacity (data ());
365 size_type nnz () const {
366 return data (). size ();
371 const array_type &data () const {
375 array_type &data () {
382 size_type restrict_capacity (size_type non_zeros) const {
383 non_zeros = (std::min) (non_zeros, size_);
388 void resize (size_type size, bool preserve = true) {
391 data ().erase (data ().lower_bound(size_), data ().end());
400 void reserve (size_type non_zeros, bool /*preserve*/ = true) {
401 detail::map_reserve (data (), restrict_capacity (non_zeros));
406 pointer find_element (size_type i) {
407 return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
410 const_pointer find_element (size_type i) const {
411 const_subiterator_type it (data ().find (i));
412 if (it == data ().end ())
414 BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
415 return &(*it).second;
420 const_reference operator () (size_type i) const {
421 BOOST_UBLAS_CHECK (i < size_, bad_index ());
422 const_subiterator_type it (data ().find (i));
423 if (it == data ().end ())
425 BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
429 true_reference ref (size_type i) {
430 BOOST_UBLAS_CHECK (i < size_, bad_index ());
431 std::pair<subiterator_type, bool> ii (data ().insert (typename array_type::value_type (i, value_type/*zero*/())));
432 BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ()); // broken map
433 return (ii.first)->second;
436 reference operator () (size_type i) {
437 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
440 BOOST_UBLAS_CHECK (i < size_, bad_index ());
441 return reference (*this, i);
446 const_reference operator [] (size_type i) const {
450 reference operator [] (size_type i) {
454 // Element assignment
456 true_reference insert_element (size_type i, const_reference t) {
457 std::pair<subiterator_type, bool> ii = data ().insert (typename array_type::value_type (i, t));
458 BOOST_UBLAS_CHECK (ii.second, bad_index ()); // duplicate element
459 BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ()); // broken map
460 if (!ii.second) // existing element
461 (ii.first)->second = t;
462 return (ii.first)->second;
465 void erase_element (size_type i) {
466 subiterator_type it = data ().find (i);
467 if (it == data ().end ())
480 mapped_vector &operator = (const mapped_vector &v) {
487 template<class C> // Container assignment without temporary
489 mapped_vector &operator = (const vector_container<C> &v) {
490 resize (v ().size (), false);
495 mapped_vector &assign_temporary (mapped_vector &v) {
501 mapped_vector &operator = (const vector_expression<AE> &ae) {
502 self_type temporary (ae, detail::map_capacity (data()));
503 return assign_temporary (temporary);
507 mapped_vector &assign (const vector_expression<AE> &ae) {
508 vector_assign<scalar_assign> (*this, ae);
512 // Computed assignment
515 mapped_vector &operator += (const vector_expression<AE> &ae) {
516 self_type temporary (*this + ae, detail::map_capacity (data()));
517 return assign_temporary (temporary);
519 template<class C> // Container assignment without temporary
521 mapped_vector &operator += (const vector_container<C> &v) {
527 mapped_vector &plus_assign (const vector_expression<AE> &ae) {
528 vector_assign<scalar_plus_assign> (*this, ae);
533 mapped_vector &operator -= (const vector_expression<AE> &ae) {
534 self_type temporary (*this - ae, detail::map_capacity (data()));
535 return assign_temporary (temporary);
537 template<class C> // Container assignment without temporary
539 mapped_vector &operator -= (const vector_container<C> &v) {
545 mapped_vector &minus_assign (const vector_expression<AE> &ae) {
546 vector_assign<scalar_minus_assign> (*this, ae);
551 mapped_vector &operator *= (const AT &at) {
552 vector_assign_scalar<scalar_multiplies_assign> (*this, at);
557 mapped_vector &operator /= (const AT &at) {
558 vector_assign_scalar<scalar_divides_assign> (*this, at);
564 void swap (mapped_vector &v) {
566 std::swap (size_, v.size_);
567 data ().swap (v.data ());
571 friend void swap (mapped_vector &v1, mapped_vector &v2) {
577 // Use storage iterator
578 typedef typename A::const_iterator const_subiterator_type;
579 typedef typename A::iterator subiterator_type;
582 true_reference at_element (size_type i) {
583 BOOST_UBLAS_CHECK (i < size_, bad_index ());
584 subiterator_type it (data ().find (i));
585 BOOST_UBLAS_CHECK (it != data ().end(), bad_index ());
586 BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
591 class const_iterator;
595 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
596 const_iterator find (size_type i) const {
597 return const_iterator (*this, data ().lower_bound (i));
599 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
600 iterator find (size_type i) {
601 return iterator (*this, data ().lower_bound (i));
605 class const_iterator:
606 public container_const_reference<mapped_vector>,
607 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
608 const_iterator, value_type> {
610 typedef typename mapped_vector::value_type value_type;
611 typedef typename mapped_vector::difference_type difference_type;
612 typedef typename mapped_vector::const_reference reference;
613 typedef const typename mapped_vector::pointer pointer;
615 // Construction and destruction
618 container_const_reference<self_type> (), it_ () {}
620 const_iterator (const self_type &v, const const_subiterator_type &it):
621 container_const_reference<self_type> (v), it_ (it) {}
623 const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
624 container_const_reference<self_type> (it ()), it_ (it.it_) {}
628 const_iterator &operator ++ () {
633 const_iterator &operator -- () {
640 const_reference operator * () const {
641 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
642 return (*it_).second;
647 size_type index () const {
648 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
649 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
655 const_iterator &operator = (const const_iterator &it) {
656 container_const_reference<self_type>::assign (&it ());
663 bool operator == (const const_iterator &it) const {
664 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
665 return it_ == it.it_;
669 const_subiterator_type it_;
673 const_iterator begin () const {
674 return const_iterator (*this, data ().begin ());
677 const_iterator cbegin () const {
681 const_iterator end () const {
682 return const_iterator (*this, data ().end ());
685 const_iterator cend () const {
690 public container_reference<mapped_vector>,
691 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
692 iterator, value_type> {
694 typedef typename mapped_vector::value_type value_type;
695 typedef typename mapped_vector::difference_type difference_type;
696 typedef typename mapped_vector::true_reference reference;
697 typedef typename mapped_vector::pointer pointer;
699 // Construction and destruction
702 container_reference<self_type> (), it_ () {}
704 iterator (self_type &v, const subiterator_type &it):
705 container_reference<self_type> (v), it_ (it) {}
709 iterator &operator ++ () {
714 iterator &operator -- () {
721 reference operator * () const {
722 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
723 return (*it_).second;
728 size_type index () const {
729 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
730 BOOST_UBLAS_CHECK ((*it_).first < (*this) ().size (), bad_index ());
736 iterator &operator = (const iterator &it) {
737 container_reference<self_type>::assign (&it ());
744 bool operator == (const iterator &it) const {
745 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
746 return it_ == it.it_;
750 subiterator_type it_;
752 friend class const_iterator;
757 return iterator (*this, data ().begin ());
761 return iterator (*this, data ().end ());
765 typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
766 typedef reverse_iterator_base<iterator> reverse_iterator;
769 const_reverse_iterator rbegin () const {
770 return const_reverse_iterator (end ());
773 const_reverse_iterator crbegin () const {
777 const_reverse_iterator rend () const {
778 return const_reverse_iterator (begin ());
781 const_reverse_iterator crend () const {
785 reverse_iterator rbegin () {
786 return reverse_iterator (end ());
789 reverse_iterator rend () {
790 return reverse_iterator (begin ());
794 template<class Archive>
795 void serialize(Archive & ar, const unsigned int /* file_version */){
796 serialization::collection_size_type s (size_);
797 ar & serialization::make_nvp("size",s);
798 if (Archive::is_loading::value) {
801 ar & serialization::make_nvp("data", data_);
807 static const value_type zero_;
810 template<class T, class A>
811 const typename mapped_vector<T, A>::value_type mapped_vector<T, A>::zero_ = value_type/*zero*/();
814 // Thanks to Kresimir Fresl for extending this to cover different index bases.
816 /** \brief Compressed array based sparse vector
818 * a sparse vector of values of type T of variable size. The non zero values are stored as
819 * two seperate arrays: an index array and a value array. The index array is always sorted
820 * and there is at most one entry for each index. Inserting an element can be time consuming.
821 * If the vector contains a few zero entries, then it is better to have a normal vector.
822 * If the vector has a very high dimension with a few non-zero values, then this vector is
823 * very memory efficient (at the cost of a few more computations).
825 * For a \f$n\f$-dimensional compressed vector and \f$0 \leq i < n\f$ the non-zero elements
826 * \f$v_i\f$ are mapped to consecutive elements of the index and value container, i.e. for
827 * 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$.
829 * Supported parameters for the adapted array (indices and values) are \c unbounded_array<> ,
830 * \c bounded_array<> and \c std::vector<>.
832 * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
833 * \tparam IB the index base of the compressed vector. Default is 0. Other supported value is 1
834 * \tparam IA the type of adapted array for indices. Default is \c unbounded_array<std::size_t>
835 * \tparam TA the type of adapted array for values. Default is unbounded_array<T>
837 template<class T, std::size_t IB, class IA, class TA>
838 class compressed_vector:
839 public vector_container<compressed_vector<T, IB, IA, TA> > {
841 typedef T &true_reference;
843 typedef const T *const_pointer;
844 typedef compressed_vector<T, IB, IA, TA> self_type;
846 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
847 using vector_container<self_type>::operator ();
849 // ISSUE require type consistency check
850 // is_convertable (IA::size_type, TA::size_type)
851 typedef typename IA::value_type size_type;
852 typedef typename IA::difference_type difference_type;
853 typedef T value_type;
854 typedef const T &const_reference;
855 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
856 typedef T &reference;
858 typedef sparse_vector_element<self_type> reference;
860 typedef IA index_array_type;
861 typedef TA value_array_type;
862 typedef const vector_reference<const self_type> const_closure_type;
863 typedef vector_reference<self_type> closure_type;
864 typedef self_type vector_temporary_type;
865 typedef sparse_tag storage_category;
867 // Construction and destruction
869 compressed_vector ():
870 vector_container<self_type> (),
871 size_ (0), capacity_ (restrict_capacity (0)), filled_ (0),
872 index_data_ (capacity_), value_data_ (capacity_) {
873 storage_invariants ();
875 explicit BOOST_UBLAS_INLINE
876 compressed_vector (size_type size, size_type non_zeros = 0):
877 vector_container<self_type> (),
878 size_ (size), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
879 index_data_ (capacity_), value_data_ (capacity_) {
880 storage_invariants ();
883 compressed_vector (const compressed_vector &v):
884 vector_container<self_type> (),
885 size_ (v.size_), capacity_ (v.capacity_), filled_ (v.filled_),
886 index_data_ (v.index_data_), value_data_ (v.value_data_) {
887 storage_invariants ();
891 compressed_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
892 vector_container<self_type> (),
893 size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
894 index_data_ (capacity_), value_data_ (capacity_) {
895 storage_invariants ();
896 vector_assign<scalar_assign> (*this, ae);
901 size_type size () const {
905 size_type nnz_capacity () const {
909 size_type nnz () const {
915 static size_type index_base () {
919 typename index_array_type::size_type filled () const {
923 const index_array_type &index_data () const {
927 const value_array_type &value_data () const {
931 void set_filled (const typename index_array_type::size_type & filled) {
933 storage_invariants ();
936 index_array_type &index_data () {
940 value_array_type &value_data () {
947 size_type restrict_capacity (size_type non_zeros) const {
948 non_zeros = (std::max) (non_zeros, size_type (1));
949 non_zeros = (std::min) (non_zeros, size_);
954 void resize (size_type size, bool preserve = true) {
956 capacity_ = restrict_capacity (capacity_);
958 index_data_. resize (capacity_, size_type ());
959 value_data_. resize (capacity_, value_type ());
960 filled_ = (std::min) (capacity_, filled_);
961 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
966 index_data_. resize (capacity_);
967 value_data_. resize (capacity_);
970 storage_invariants ();
975 void reserve (size_type non_zeros, bool preserve = true) {
976 capacity_ = restrict_capacity (non_zeros);
978 index_data_. resize (capacity_, size_type ());
979 value_data_. resize (capacity_, value_type ());
980 filled_ = (std::min) (capacity_, filled_);
983 index_data_. resize (capacity_);
984 value_data_. resize (capacity_);
987 storage_invariants ();
992 pointer find_element (size_type i) {
993 return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
996 const_pointer find_element (size_type i) const {
997 const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
998 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1000 return &value_data_ [it - index_data_.begin ()];
1005 const_reference operator () (size_type i) const {
1006 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1007 const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1008 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1010 return value_data_ [it - index_data_.begin ()];
1013 true_reference ref (size_type i) {
1014 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1015 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1016 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1017 return insert_element (i, value_type/*zero*/());
1019 return value_data_ [it - index_data_.begin ()];
1022 reference operator () (size_type i) {
1023 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
1026 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1027 return reference (*this, i);
1032 const_reference operator [] (size_type i) const {
1036 reference operator [] (size_type i) {
1040 // Element assignment
1042 true_reference insert_element (size_type i, const_reference t) {
1043 BOOST_UBLAS_CHECK (!find_element (i), bad_index ()); // duplicate element
1044 if (filled_ >= capacity_)
1045 reserve (2 * capacity_, true);
1046 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1047 // ISSUE max_capacity limit due to difference_type
1048 typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
1049 BOOST_UBLAS_CHECK (filled_ == 0 || filled_ == typename index_array_type::size_type (n) || *it != k_based (i), internal_logic ()); // duplicate found by lower_bound
1051 it = index_data_.begin () + n;
1052 std::copy_backward (it, index_data_.begin () + filled_ - 1, index_data_.begin () + filled_);
1054 typename value_array_type::iterator itt (value_data_.begin () + n);
1055 std::copy_backward (itt, value_data_.begin () + filled_ - 1, value_data_.begin () + filled_);
1057 storage_invariants ();
1061 void erase_element (size_type i) {
1062 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1063 typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
1064 if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
1065 std::copy (it + 1, index_data_.begin () + filled_, it);
1066 typename value_array_type::iterator itt (value_data_.begin () + n);
1067 std::copy (itt + 1, value_data_.begin () + filled_, itt);
1070 storage_invariants ();
1077 storage_invariants ();
1082 compressed_vector &operator = (const compressed_vector &v) {
1085 capacity_ = v.capacity_;
1086 filled_ = v.filled_;
1087 index_data_ = v.index_data_;
1088 value_data_ = v.value_data_;
1090 storage_invariants ();
1093 template<class C> // Container assignment without temporary
1095 compressed_vector &operator = (const vector_container<C> &v) {
1096 resize (v ().size (), false);
1101 compressed_vector &assign_temporary (compressed_vector &v) {
1107 compressed_vector &operator = (const vector_expression<AE> &ae) {
1108 self_type temporary (ae, capacity_);
1109 return assign_temporary (temporary);
1113 compressed_vector &assign (const vector_expression<AE> &ae) {
1114 vector_assign<scalar_assign> (*this, ae);
1118 // Computed assignment
1121 compressed_vector &operator += (const vector_expression<AE> &ae) {
1122 self_type temporary (*this + ae, capacity_);
1123 return assign_temporary (temporary);
1125 template<class C> // Container assignment without temporary
1127 compressed_vector &operator += (const vector_container<C> &v) {
1133 compressed_vector &plus_assign (const vector_expression<AE> &ae) {
1134 vector_assign<scalar_plus_assign> (*this, ae);
1139 compressed_vector &operator -= (const vector_expression<AE> &ae) {
1140 self_type temporary (*this - ae, capacity_);
1141 return assign_temporary (temporary);
1143 template<class C> // Container assignment without temporary
1145 compressed_vector &operator -= (const vector_container<C> &v) {
1151 compressed_vector &minus_assign (const vector_expression<AE> &ae) {
1152 vector_assign<scalar_minus_assign> (*this, ae);
1157 compressed_vector &operator *= (const AT &at) {
1158 vector_assign_scalar<scalar_multiplies_assign> (*this, at);
1163 compressed_vector &operator /= (const AT &at) {
1164 vector_assign_scalar<scalar_divides_assign> (*this, at);
1170 void swap (compressed_vector &v) {
1172 std::swap (size_, v.size_);
1173 std::swap (capacity_, v.capacity_);
1174 std::swap (filled_, v.filled_);
1175 index_data_.swap (v.index_data_);
1176 value_data_.swap (v.value_data_);
1178 storage_invariants ();
1181 friend void swap (compressed_vector &v1, compressed_vector &v2) {
1185 // Back element insertion and erasure
1187 void push_back (size_type i, const_reference t) {
1188 BOOST_UBLAS_CHECK (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i), external_logic ());
1189 if (filled_ >= capacity_)
1190 reserve (2 * capacity_, true);
1191 BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1192 index_data_ [filled_] = k_based (i);
1193 value_data_ [filled_] = t;
1195 storage_invariants ();
1199 BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
1201 storage_invariants ();
1206 // Use index array iterator
1207 typedef typename IA::const_iterator const_subiterator_type;
1208 typedef typename IA::iterator subiterator_type;
1211 true_reference at_element (size_type i) {
1212 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1213 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1214 BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
1215 return value_data_ [it - index_data_.begin ()];
1219 class const_iterator;
1223 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1224 const_iterator find (size_type i) const {
1225 return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1227 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1228 iterator find (size_type i) {
1229 return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1233 class const_iterator:
1234 public container_const_reference<compressed_vector>,
1235 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1236 const_iterator, value_type> {
1238 typedef typename compressed_vector::value_type value_type;
1239 typedef typename compressed_vector::difference_type difference_type;
1240 typedef typename compressed_vector::const_reference reference;
1241 typedef const typename compressed_vector::pointer pointer;
1243 // Construction and destruction
1246 container_const_reference<self_type> (), it_ () {}
1248 const_iterator (const self_type &v, const const_subiterator_type &it):
1249 container_const_reference<self_type> (v), it_ (it) {}
1251 const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
1252 container_const_reference<self_type> (it ()), it_ (it.it_) {}
1256 const_iterator &operator ++ () {
1261 const_iterator &operator -- () {
1268 const_reference operator * () const {
1269 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1270 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
1275 size_type index () const {
1276 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
1277 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
1278 return (*this) ().zero_based (*it_);
1283 const_iterator &operator = (const const_iterator &it) {
1284 container_const_reference<self_type>::assign (&it ());
1291 bool operator == (const const_iterator &it) const {
1292 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1293 return it_ == it.it_;
1297 const_subiterator_type it_;
1301 const_iterator begin () const {
1305 const_iterator cbegin () const {
1309 const_iterator end () const {
1310 return find (size_);
1313 const_iterator cend () const {
1318 public container_reference<compressed_vector>,
1319 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1320 iterator, value_type> {
1322 typedef typename compressed_vector::value_type value_type;
1323 typedef typename compressed_vector::difference_type difference_type;
1324 typedef typename compressed_vector::true_reference reference;
1325 typedef typename compressed_vector::pointer pointer;
1327 // Construction and destruction
1330 container_reference<self_type> (), it_ () {}
1332 iterator (self_type &v, const subiterator_type &it):
1333 container_reference<self_type> (v), it_ (it) {}
1337 iterator &operator ++ () {
1342 iterator &operator -- () {
1349 reference operator * () const {
1350 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1351 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
1356 size_type index () const {
1357 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
1358 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
1359 return (*this) ().zero_based (*it_);
1364 iterator &operator = (const iterator &it) {
1365 container_reference<self_type>::assign (&it ());
1372 bool operator == (const iterator &it) const {
1373 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1374 return it_ == it.it_;
1378 subiterator_type it_;
1380 friend class const_iterator;
1389 return find (size_);
1393 typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
1394 typedef reverse_iterator_base<iterator> reverse_iterator;
1397 const_reverse_iterator rbegin () const {
1398 return const_reverse_iterator (end ());
1401 const_reverse_iterator crbegin () const {
1405 const_reverse_iterator rend () const {
1406 return const_reverse_iterator (begin ());
1409 const_reverse_iterator crend () const {
1413 reverse_iterator rbegin () {
1414 return reverse_iterator (end ());
1417 reverse_iterator rend () {
1418 return reverse_iterator (begin ());
1422 template<class Archive>
1423 void serialize(Archive & ar, const unsigned int /* file_version */){
1424 serialization::collection_size_type s (size_);
1425 ar & serialization::make_nvp("size",s);
1426 if (Archive::is_loading::value) {
1429 // ISSUE: filled may be much less than capacity
1430 // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
1431 ar & serialization::make_nvp("capacity", capacity_);
1432 ar & serialization::make_nvp("filled", filled_);
1433 ar & serialization::make_nvp("index_data", index_data_);
1434 ar & serialization::make_nvp("value_data", value_data_);
1435 storage_invariants();
1439 void storage_invariants () const
1441 BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
1442 BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
1443 BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
1444 BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
1448 typename index_array_type::size_type capacity_;
1449 typename index_array_type::size_type filled_;
1450 index_array_type index_data_;
1451 value_array_type value_data_;
1452 static const value_type zero_;
1455 static size_type zero_based (size_type k_based_index) {
1456 return k_based_index - IB;
1459 static size_type k_based (size_type zero_based_index) {
1460 return zero_based_index + IB;
1463 friend class iterator;
1464 friend class const_iterator;
1467 template<class T, std::size_t IB, class IA, class TA>
1468 const typename compressed_vector<T, IB, IA, TA>::value_type compressed_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
1470 // Thanks to Kresimir Fresl for extending this to cover different index bases.
1472 /** \brief Coordimate array based sparse vector
1474 * a sparse vector of values of type \c T of variable size. The non zero values are stored
1475 * as two seperate arrays: an index array and a value array. The arrays may be out of order
1476 * with multiple entries for each vector element. If there are multiple values for the same
1477 * index the sum of these values is the real value. It is way more efficient for inserting values
1478 * than a \c compressed_vector but less memory efficient. Also linearly parsing a vector can
1479 * be longer in specific cases than a \c compressed_vector.
1481 * For a n-dimensional sorted coordinate vector and \f$ 0 \leq i < n\f$ the non-zero elements
1482 * \f$v_i\f$ are mapped to consecutive elements of the index and value container, i.e. for
1483 * 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$.
1485 * Supported parameters for the adapted array (indices and values) are \c unbounded_array<> ,
1486 * \c bounded_array<> and \c std::vector<>.
1488 * \tparam T the type of object stored in the vector (like double, float, complex, etc...)
1489 * \tparam IB the index base of the compressed vector. Default is 0. Other supported value is 1
1490 * \tparam IA the type of adapted array for indices. Default is \c unbounded_array<std::size_t>
1491 * \tparam TA the type of adapted array for values. Default is unbounded_array<T>
1493 template<class T, std::size_t IB, class IA, class TA>
1494 class coordinate_vector:
1495 public vector_container<coordinate_vector<T, IB, IA, TA> > {
1497 typedef T &true_reference;
1499 typedef const T *const_pointer;
1500 typedef coordinate_vector<T, IB, IA, TA> self_type;
1502 #ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
1503 using vector_container<self_type>::operator ();
1505 // ISSUE require type consistency check
1506 // is_convertable (IA::size_type, TA::size_type)
1507 typedef typename IA::value_type size_type;
1508 typedef typename IA::difference_type difference_type;
1509 typedef T value_type;
1510 typedef const T &const_reference;
1511 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
1512 typedef T &reference;
1514 typedef sparse_vector_element<self_type> reference;
1516 typedef IA index_array_type;
1517 typedef TA value_array_type;
1518 typedef const vector_reference<const self_type> const_closure_type;
1519 typedef vector_reference<self_type> closure_type;
1520 typedef self_type vector_temporary_type;
1521 typedef sparse_tag storage_category;
1523 // Construction and destruction
1525 coordinate_vector ():
1526 vector_container<self_type> (),
1527 size_ (0), capacity_ (restrict_capacity (0)),
1528 filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1529 index_data_ (capacity_), value_data_ (capacity_) {
1530 storage_invariants ();
1532 explicit BOOST_UBLAS_INLINE
1533 coordinate_vector (size_type size, size_type non_zeros = 0):
1534 vector_container<self_type> (),
1535 size_ (size), capacity_ (restrict_capacity (non_zeros)),
1536 filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1537 index_data_ (capacity_), value_data_ (capacity_) {
1538 storage_invariants ();
1541 coordinate_vector (const coordinate_vector &v):
1542 vector_container<self_type> (),
1543 size_ (v.size_), capacity_ (v.capacity_),
1544 filled_ (v.filled_), sorted_filled_ (v.sorted_filled_), sorted_ (v.sorted_),
1545 index_data_ (v.index_data_), value_data_ (v.value_data_) {
1546 storage_invariants ();
1550 coordinate_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
1551 vector_container<self_type> (),
1552 size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)),
1553 filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1554 index_data_ (capacity_), value_data_ (capacity_) {
1555 storage_invariants ();
1556 vector_assign<scalar_assign> (*this, ae);
1561 size_type size () const {
1565 size_type nnz_capacity () const {
1569 size_type nnz () const {
1573 // Storage accessors
1575 static size_type index_base () {
1579 typename index_array_type::size_type filled () const {
1583 const index_array_type &index_data () const {
1587 const value_array_type &value_data () const {
1591 void set_filled (const typename index_array_type::size_type &sorted, const typename index_array_type::size_type &filled) {
1592 sorted_filled_ = sorted;
1594 storage_invariants ();
1597 index_array_type &index_data () {
1601 value_array_type &value_data () {
1608 size_type restrict_capacity (size_type non_zeros) const {
1609 // minimum non_zeros
1610 non_zeros = (std::max) (non_zeros, size_type (1));
1611 // ISSUE no maximum as coordinate may contain inserted duplicates
1616 void resize (size_type size, bool preserve = true) {
1618 sort (); // remove duplicate elements.
1620 capacity_ = restrict_capacity (capacity_);
1622 index_data_. resize (capacity_, size_type ());
1623 value_data_. resize (capacity_, value_type ());
1624 filled_ = (std::min) (capacity_, filled_);
1625 while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
1630 index_data_. resize (capacity_);
1631 value_data_. resize (capacity_);
1634 sorted_filled_ = filled_;
1635 storage_invariants ();
1639 void reserve (size_type non_zeros, bool preserve = true) {
1641 sort (); // remove duplicate elements.
1642 capacity_ = restrict_capacity (non_zeros);
1644 index_data_. resize (capacity_, size_type ());
1645 value_data_. resize (capacity_, value_type ());
1646 filled_ = (std::min) (capacity_, filled_);
1649 index_data_. resize (capacity_);
1650 value_data_. resize (capacity_);
1653 sorted_filled_ = filled_;
1654 storage_invariants ();
1659 pointer find_element (size_type i) {
1660 return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
1663 const_pointer find_element (size_type i) const {
1665 const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1666 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1668 return &value_data_ [it - index_data_.begin ()];
1673 const_reference operator () (size_type i) const {
1674 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1676 const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1677 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1679 return value_data_ [it - index_data_.begin ()];
1682 true_reference ref (size_type i) {
1683 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1685 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1686 if (it == index_data_.begin () + filled_ || *it != k_based (i))
1687 return insert_element (i, value_type/*zero*/());
1689 return value_data_ [it - index_data_.begin ()];
1692 reference operator () (size_type i) {
1693 #ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
1696 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1697 return reference (*this, i);
1702 const_reference operator [] (size_type i) const {
1706 reference operator [] (size_type i) {
1710 // Element assignment
1712 void append_element (size_type i, const_reference t) {
1713 if (filled_ >= capacity_)
1714 reserve (2 * filled_, true);
1715 BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1716 index_data_ [filled_] = k_based (i);
1717 value_data_ [filled_] = t;
1720 storage_invariants ();
1723 true_reference insert_element (size_type i, const_reference t) {
1724 BOOST_UBLAS_CHECK (!find_element (i), bad_index ()); // duplicate element
1725 append_element (i, t);
1726 return value_data_ [filled_ - 1];
1729 void erase_element (size_type i) {
1731 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1732 typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
1733 if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
1734 std::copy (it + 1, index_data_.begin () + filled_, it);
1735 typename value_array_type::iterator itt (value_data_.begin () + n);
1736 std::copy (itt + 1, value_data_.begin () + filled_, itt);
1738 sorted_filled_ = filled_;
1740 storage_invariants ();
1747 sorted_filled_ = filled_;
1749 storage_invariants ();
1754 coordinate_vector &operator = (const coordinate_vector &v) {
1757 capacity_ = v.capacity_;
1758 filled_ = v.filled_;
1759 sorted_filled_ = v.sorted_filled_;
1760 sorted_ = v.sorted_;
1761 index_data_ = v.index_data_;
1762 value_data_ = v.value_data_;
1764 storage_invariants ();
1767 template<class C> // Container assignment without temporary
1769 coordinate_vector &operator = (const vector_container<C> &v) {
1770 resize (v ().size (), false);
1775 coordinate_vector &assign_temporary (coordinate_vector &v) {
1781 coordinate_vector &operator = (const vector_expression<AE> &ae) {
1782 self_type temporary (ae, capacity_);
1783 return assign_temporary (temporary);
1787 coordinate_vector &assign (const vector_expression<AE> &ae) {
1788 vector_assign<scalar_assign> (*this, ae);
1792 // Computed assignment
1795 coordinate_vector &operator += (const vector_expression<AE> &ae) {
1796 self_type temporary (*this + ae, capacity_);
1797 return assign_temporary (temporary);
1799 template<class C> // Container assignment without temporary
1801 coordinate_vector &operator += (const vector_container<C> &v) {
1807 coordinate_vector &plus_assign (const vector_expression<AE> &ae) {
1808 vector_assign<scalar_plus_assign> (*this, ae);
1813 coordinate_vector &operator -= (const vector_expression<AE> &ae) {
1814 self_type temporary (*this - ae, capacity_);
1815 return assign_temporary (temporary);
1817 template<class C> // Container assignment without temporary
1819 coordinate_vector &operator -= (const vector_container<C> &v) {
1825 coordinate_vector &minus_assign (const vector_expression<AE> &ae) {
1826 vector_assign<scalar_minus_assign> (*this, ae);
1831 coordinate_vector &operator *= (const AT &at) {
1832 vector_assign_scalar<scalar_multiplies_assign> (*this, at);
1837 coordinate_vector &operator /= (const AT &at) {
1838 vector_assign_scalar<scalar_divides_assign> (*this, at);
1844 void swap (coordinate_vector &v) {
1846 std::swap (size_, v.size_);
1847 std::swap (capacity_, v.capacity_);
1848 std::swap (filled_, v.filled_);
1849 std::swap (sorted_filled_, v.sorted_filled_);
1850 std::swap (sorted_, v.sorted_);
1851 index_data_.swap (v.index_data_);
1852 value_data_.swap (v.value_data_);
1854 storage_invariants ();
1857 friend void swap (coordinate_vector &v1, coordinate_vector &v2) {
1861 // replacement if STL lower bound algorithm for use of inplace_merge
1862 size_type lower_bound (size_type beg, size_type end, size_type target) const {
1864 size_type mid = (beg + end) / 2;
1865 if (index_data_[mid] < index_data_[target]) {
1874 // specialized replacement of STL inplace_merge to avoid compilation
1875 // problems with respect to the array_triple iterator
1876 void inplace_merge (size_type beg, size_type mid, size_type end) const {
1877 size_type len_lef = mid - beg;
1878 size_type len_rig = end - mid;
1880 if (len_lef == 1 && len_rig == 1) {
1881 if (index_data_[mid] < index_data_[beg]) {
1882 std::swap(index_data_[beg], index_data_[mid]);
1883 std::swap(value_data_[beg], value_data_[mid]);
1885 } else if (len_lef > 0 && len_rig > 0) {
1886 size_type lef_mid, rig_mid;
1887 if (len_lef >= len_rig) {
1888 lef_mid = (beg + mid) / 2;
1889 rig_mid = lower_bound(mid, end, lef_mid);
1891 rig_mid = (mid + end) / 2;
1892 lef_mid = lower_bound(beg, mid, rig_mid);
1894 std::rotate(&index_data_[0] + lef_mid, &index_data_[0] + mid, &index_data_[0] + rig_mid);
1895 std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
1897 size_type new_mid = lef_mid + rig_mid - mid;
1898 inplace_merge(beg, lef_mid, new_mid);
1899 inplace_merge(new_mid, rig_mid, end);
1903 // Sorting and summation of duplicates
1905 void sort () const {
1906 if (! sorted_ && filled_ > 0) {
1907 typedef index_pair_array<index_array_type, value_array_type> array_pair;
1908 array_pair ipa (filled_, index_data_, value_data_);
1909 #ifndef BOOST_UBLAS_COO_ALWAYS_DO_FULL_SORT
1910 const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
1911 // sort new elements and merge
1912 std::sort (iunsorted, ipa.end ());
1913 inplace_merge(0, sorted_filled_, filled_);
1915 const typename array_pair::iterator iunsorted = ipa.begin ();
1916 std::sort (iunsorted, ipa.end ());
1919 // sum duplicates with += and remove
1920 size_type filled = 0;
1921 for (size_type i = 1; i < filled_; ++ i) {
1922 if (index_data_ [filled] != index_data_ [i]) {
1925 index_data_ [filled] = index_data_ [i];
1926 value_data_ [filled] = value_data_ [i];
1929 value_data_ [filled] += value_data_ [i];
1932 filled_ = filled + 1;
1933 sorted_filled_ = filled_;
1935 storage_invariants ();
1939 // Back element insertion and erasure
1941 void push_back (size_type i, const_reference t) {
1942 // must maintain sort order
1943 BOOST_UBLAS_CHECK (sorted_ && (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i)), external_logic ());
1944 if (filled_ >= capacity_)
1945 reserve (2 * filled_, true);
1946 BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1947 index_data_ [filled_] = k_based (i);
1948 value_data_ [filled_] = t;
1950 sorted_filled_ = filled_;
1951 storage_invariants ();
1955 // ISSUE invariants could be simpilfied if sorted required as precondition
1956 BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
1958 sorted_filled_ = (std::min) (sorted_filled_, filled_);
1959 sorted_ = sorted_filled_ = filled_;
1960 storage_invariants ();
1965 // Use index array iterator
1966 typedef typename IA::const_iterator const_subiterator_type;
1967 typedef typename IA::iterator subiterator_type;
1970 true_reference at_element (size_type i) {
1971 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1973 subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1974 BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
1975 return value_data_ [it - index_data_.begin ()];
1979 class const_iterator;
1983 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1984 const_iterator find (size_type i) const {
1986 return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1988 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1989 iterator find (size_type i) {
1991 return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1995 class const_iterator:
1996 public container_const_reference<coordinate_vector>,
1997 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1998 const_iterator, value_type> {
2000 typedef typename coordinate_vector::value_type value_type;
2001 typedef typename coordinate_vector::difference_type difference_type;
2002 typedef typename coordinate_vector::const_reference reference;
2003 typedef const typename coordinate_vector::pointer pointer;
2005 // Construction and destruction
2008 container_const_reference<self_type> (), it_ () {}
2010 const_iterator (const self_type &v, const const_subiterator_type &it):
2011 container_const_reference<self_type> (v), it_ (it) {}
2013 const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
2014 container_const_reference<self_type> (it ()), it_ (it.it_) {}
2018 const_iterator &operator ++ () {
2023 const_iterator &operator -- () {
2030 const_reference operator * () const {
2031 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
2032 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
2037 size_type index () const {
2038 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
2039 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
2040 return (*this) ().zero_based (*it_);
2045 const_iterator &operator = (const const_iterator &it) {
2046 container_const_reference<self_type>::assign (&it ());
2053 bool operator == (const const_iterator &it) const {
2054 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
2055 return it_ == it.it_;
2059 const_subiterator_type it_;
2063 const_iterator begin () const {
2067 const_iterator cbegin () const {
2071 const_iterator end () const {
2072 return find (size_);
2075 const_iterator cend () const {
2080 public container_reference<coordinate_vector>,
2081 public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
2082 iterator, value_type> {
2084 typedef typename coordinate_vector::value_type value_type;
2085 typedef typename coordinate_vector::difference_type difference_type;
2086 typedef typename coordinate_vector::true_reference reference;
2087 typedef typename coordinate_vector::pointer pointer;
2089 // Construction and destruction
2092 container_reference<self_type> (), it_ () {}
2094 iterator (self_type &v, const subiterator_type &it):
2095 container_reference<self_type> (v), it_ (it) {}
2099 iterator &operator ++ () {
2104 iterator &operator -- () {
2111 reference operator * () const {
2112 BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
2113 return (*this) ().value_data_ [it_ - (*this) ().index_data_.begin ()];
2118 size_type index () const {
2119 BOOST_UBLAS_CHECK (*this != (*this) ().end (), bad_index ());
2120 BOOST_UBLAS_CHECK ((*this) ().zero_based (*it_) < (*this) ().size (), bad_index ());
2121 return (*this) ().zero_based (*it_);
2126 iterator &operator = (const iterator &it) {
2127 container_reference<self_type>::assign (&it ());
2134 bool operator == (const iterator &it) const {
2135 BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
2136 return it_ == it.it_;
2140 subiterator_type it_;
2142 friend class const_iterator;
2151 return find (size_);
2155 typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
2156 typedef reverse_iterator_base<iterator> reverse_iterator;
2159 const_reverse_iterator rbegin () const {
2160 return const_reverse_iterator (end ());
2163 const_reverse_iterator crbegin () const {
2167 const_reverse_iterator rend () const {
2168 return const_reverse_iterator (begin ());
2171 const_reverse_iterator crend () const {
2175 reverse_iterator rbegin () {
2176 return reverse_iterator (end ());
2179 reverse_iterator rend () {
2180 return reverse_iterator (begin ());
2184 template<class Archive>
2185 void serialize(Archive & ar, const unsigned int /* file_version */){
2186 serialization::collection_size_type s (size_);
2187 ar & serialization::make_nvp("size",s);
2188 if (Archive::is_loading::value) {
2191 // ISSUE: filled may be much less than capacity
2192 // ISSUE: index_data_ and value_data_ are undefined between filled and capacity (trouble with 'nan'-values)
2193 ar & serialization::make_nvp("capacity", capacity_);
2194 ar & serialization::make_nvp("filled", filled_);
2195 ar & serialization::make_nvp("sorted_filled", sorted_filled_);
2196 ar & serialization::make_nvp("sorted", sorted_);
2197 ar & serialization::make_nvp("index_data", index_data_);
2198 ar & serialization::make_nvp("value_data", value_data_);
2199 storage_invariants();
2203 void storage_invariants () const
2205 BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
2206 BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
2207 BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
2208 BOOST_UBLAS_CHECK (sorted_filled_ <= filled_, internal_logic ());
2209 BOOST_UBLAS_CHECK (sorted_ == (sorted_filled_ == filled_), internal_logic ());
2210 BOOST_UBLAS_CHECK ((0 == filled_) || (zero_based(index_data_[filled_ - 1]) < size_), internal_logic ());
2214 size_type capacity_;
2215 mutable typename index_array_type::size_type filled_;
2216 mutable typename index_array_type::size_type sorted_filled_;
2217 mutable bool sorted_;
2218 mutable index_array_type index_data_;
2219 mutable value_array_type value_data_;
2220 static const value_type zero_;
2223 static size_type zero_based (size_type k_based_index) {
2224 return k_based_index - IB;
2227 static size_type k_based (size_type zero_based_index) {
2228 return zero_based_index + IB;
2231 friend class iterator;
2232 friend class const_iterator;
2235 template<class T, std::size_t IB, class IA, class TA>
2236 const typename coordinate_vector<T, IB, IA, TA>::value_type coordinate_vector<T, IB, IA, TA>::zero_ = value_type/*zero*/();
2241 #undef _ITERATOR_DEBUG_LEVEL
2242 #define _ITERATOR_DEBUG_LEVEL _BACKUP_ITERATOR_DEBUG_LEVEL
2243 #undef _BACKUP_ITERATOR_DEBUG_LEVEL