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