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_STORAGE_SPARSE_
14 #define _BOOST_UBLAS_STORAGE_SPARSE_
17 #include <boost/serialization/collection_size_type.hpp>
18 #include <boost/serialization/nvp.hpp>
19 #include <boost/serialization/array.hpp>
20 #include <boost/serialization/map.hpp>
21 #include <boost/serialization/base_object.hpp>
23 #include <boost/numeric/ublas/storage.hpp>
26 namespace boost { namespace numeric { namespace ublas {
30 template<class I, class T, class C>
32 I lower_bound (const I &begin, const I &end, const T &t, C compare) {
33 // t <= *begin <=> ! (*begin < t)
34 if (begin == end || ! compare (*begin, t))
36 if (compare (*(end - 1), t))
38 return std::lower_bound (begin, end, t, compare);
40 template<class I, class T, class C>
42 I upper_bound (const I &begin, const I &end, const T &t, C compare) {
43 if (begin == end || compare (t, *begin))
45 // (*end - 1) <= t <=> ! (t < *end)
46 if (! compare (t, *(end - 1)))
48 return std::upper_bound (begin, end, t, compare);
54 bool operator () (const P &p1, const P &p2) {
55 return p1.first < p2.first;
61 bool operator () (const T &t1, const T &t2) {
62 return t1.first.first < t2.first.first ||
63 (t1.first.first == t2.first.first && t1.first.second < t2.first.second);
69 #ifdef BOOST_UBLAS_STRICT_MAP_ARRAY
71 class sparse_storage_element:
72 public container_reference<A> {
75 typedef typename A::key_type index_type;
76 typedef typename A::mapped_type data_value_type;
77 // typedef const data_value_type &data_const_reference;
78 typedef typename type_traits<data_value_type>::const_reference data_const_reference;
79 typedef data_value_type &data_reference;
80 typedef typename A::value_type value_type;
81 typedef value_type *pointer;
83 // Construction and destruction
85 sparse_storage_element (array_type &a, pointer it):
86 container_reference<array_type> (a), it_ (it), i_ (it->first), d_ (it->second), dirty_ (false) {}
88 sparse_storage_element (array_type &a, index_type i):
89 container_reference<array_type> (a), it_ (), i_ (i), d_ (), dirty_ (false) {
90 pointer it = (*this) ().find (i_);
91 if (it == (*this) ().end ())
92 it = (*this) ().insert ((*this) ().end (), value_type (i_, d_));
96 ~sparse_storage_element () {
99 it_ = (*this) ().find (i_);
100 BOOST_UBLAS_CHECK (it_ != (*this) ().end (), internal_logic ());
105 // Element access - only if data_const_reference is defined
107 typename data_value_type::data_const_reference
108 operator [] (index_type i) const {
114 sparse_storage_element &operator = (const sparse_storage_element &p) {
115 // Overide the implict copy assignment
122 sparse_storage_element &operator = (const D &d) {
129 sparse_storage_element &operator += (const D &d) {
136 sparse_storage_element &operator -= (const D &d) {
143 sparse_storage_element &operator *= (const D &d) {
150 sparse_storage_element &operator /= (const D &d) {
159 bool operator == (const D &d) const {
164 bool operator != (const D &d) const {
170 operator data_const_reference () const {
176 void swap (sparse_storage_element p) {
180 std::swap (d_, p.d_);
184 friend void swap (sparse_storage_element p1, sparse_storage_element p2) {
197 // Default map type is simply forwarded to std::map
198 // FIXME should use ALLOC for map but std::allocator of std::pair<const I, T> and std::pair<I,T> fail to compile
199 template<class I, class T, class ALLOC>
200 class map_std : public std::map<I, T /*, ALLOC */> {
203 template<class Archive>
204 void serialize(Archive & ar, const unsigned int /* file_version */){
205 ar & serialization::make_nvp("base", boost::serialization::base_object< std::map<I, T /*, ALLOC */> >(*this));
213 // Implementation requires pair<I, T> allocator definition (without const)
214 template<class I, class T, class ALLOC>
217 typedef ALLOC allocator_type;
218 typedef typename ALLOC::size_type size_type;
219 typedef typename ALLOC::difference_type difference_type;
220 typedef std::pair<I,T> value_type;
222 typedef T mapped_type;
223 typedef const value_type &const_reference;
224 typedef value_type &reference;
225 typedef const value_type *const_pointer;
226 typedef value_type *pointer;
227 // Iterators simply are pointers.
228 typedef const_pointer const_iterator;
229 typedef pointer iterator;
231 typedef const T &data_const_reference;
232 #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
233 typedef T &data_reference;
235 typedef sparse_storage_element<map_array> data_reference;
238 // Construction and destruction
240 map_array (const ALLOC &a = ALLOC()):
241 alloc_(a), capacity_ (0), size_ (0) {
245 map_array (const map_array &c):
246 alloc_ (c.alloc_), capacity_ (c.size_), size_ (c.size_) {
248 data_ = alloc_.allocate (capacity_);
249 std::uninitialized_copy (data_, data_ + capacity_, c.data_);
250 // capacity != size_ requires uninitialized_fill (size_ to capacity_)
258 std::for_each (data_, data_ + capacity_, static_destroy);
259 alloc_.deallocate (data_, capacity_);
264 // Resizing - implicitly exposses uninitialized (but default constructed) mapped_type
266 void resize (size_type size) {
267 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
268 if (size > capacity_) {
269 const size_type capacity = size << 1;
270 BOOST_UBLAS_CHECK (capacity, internal_logic ());
271 pointer data = alloc_.allocate (capacity);
272 std::uninitialized_copy (data_, data_ + (std::min) (size, size_), data);
273 std::uninitialized_fill (data + (std::min) (size, size_), data + capacity, value_type ());
276 std::for_each (data_, data_ + capacity_, static_destroy);
277 alloc_.deallocate (data_, capacity_);
279 capacity_ = capacity;
283 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
289 void reserve (size_type capacity) {
290 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
291 // Reduce capacity_ if size_ allows
292 BOOST_UBLAS_CHECK (capacity >= size_, bad_size ());
295 data = alloc_.allocate (capacity);
296 std::uninitialized_copy (data_, data_ + size_, data);
297 std::uninitialized_fill (data + size_, data + capacity, value_type ());
303 std::for_each (data_, data_ + capacity_, static_destroy);
304 alloc_.deallocate (data_, capacity_);
306 capacity_ = capacity;
308 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
311 // Random Access Container
313 size_type size () const {
317 size_type capacity () const {
321 size_type max_size () const {
326 bool empty () const {
332 data_reference operator [] (key_type i) {
333 #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
334 pointer it = find (i);
336 it = insert (end (), value_type (i, mapped_type (0)));
337 BOOST_UBLAS_CHECK (it != end (), internal_logic ());
340 return data_reference (*this, i);
346 map_array &operator = (const map_array &a) {
349 std::copy (a.data_, a.data_ + a.size_, data_);
354 map_array &assign_temporary (map_array &a) {
361 void swap (map_array &a) {
363 std::swap (capacity_, a.capacity_);
364 std::swap (data_, a.data_);
365 std::swap (size_, a.size_);
369 friend void swap (map_array &a1, map_array &a2) {
373 // Element insertion and deletion
375 // From Back Insertion Sequence concept
376 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
377 iterator push_back (iterator it, const value_type &p) {
378 if (size () == 0 || (it = end () - 1)->first < p.first) {
379 resize (size () + 1);
380 *(it = end () - 1) = p;
383 external_logic ().raise ();
386 // Form Unique Associative Container concept
387 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
388 std::pair<iterator,bool> insert (const value_type &p) {
389 iterator it = detail::lower_bound (begin (), end (), p, detail::less_pair<value_type> ());
390 if (it != end () && it->first == p.first)
391 return std::make_pair (it, false);
392 difference_type n = it - begin ();
393 resize (size () + 1);
394 it = begin () + n; // allow for invalidation
395 std::copy_backward (it, end () - 1, end ());
397 return std::make_pair (it, true);
399 // Form Sorted Associative Container concept
400 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
401 iterator insert (iterator hint, const value_type &p) {
402 return insert (p).first;
404 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
405 void erase (iterator it) {
406 BOOST_UBLAS_CHECK (begin () <= it && it < end (), bad_index ());
407 std::copy (it + 1, end (), it);
408 resize (size () - 1);
410 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
411 void erase (iterator it1, iterator it2) {
412 if (it1 == it2) return /* nothing to erase */;
413 BOOST_UBLAS_CHECK (begin () <= it1 && it1 < it2 && it2 <= end (), bad_index ());
414 std::copy (it2, end (), it1);
415 resize (size () - (it2 - it1));
417 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
423 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
424 const_iterator find (key_type i) const {
425 const_iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
426 if (it == end () || it->first != i)
430 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
431 iterator find (key_type i) {
432 iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
433 if (it == end () || it->first != i)
437 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
438 const_iterator lower_bound (key_type i) const {
439 return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
441 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
442 iterator lower_bound (key_type i) {
443 return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
447 const_iterator begin () const {
451 const_iterator cbegin () const {
455 const_iterator end () const {
456 return data_ + size_;
459 const_iterator cend () const {
469 return data_ + size_;
473 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
474 typedef std::reverse_iterator<iterator> reverse_iterator;
477 const_reverse_iterator rbegin () const {
478 return const_reverse_iterator (end ());
481 const_reverse_iterator crbegin () const {
485 const_reverse_iterator rend () const {
486 return const_reverse_iterator (begin ());
489 const_reverse_iterator crend () const {
494 reverse_iterator rbegin () {
495 return reverse_iterator (end ());
498 reverse_iterator rend () {
499 return reverse_iterator (begin ());
503 allocator_type get_allocator () {
508 template<class Archive>
509 void serialize(Archive & ar, const unsigned int /* file_version */){
510 serialization::collection_size_type s (size_);
511 ar & serialization::make_nvp("size",s);
512 if (Archive::is_loading::value) {
515 ar & serialization::make_array(data_, s);
519 // Provide destroy as a non member function
521 static void static_destroy (reference p) {
522 (&p) -> ~value_type ();
532 template<class A, class T>
534 typedef typename A::mapped_type &reference;
536 template<class I, class T, class ALLOC>
537 struct map_traits<map_array<I, T, ALLOC>, T > {
538 typedef typename map_array<I, T, ALLOC>::data_reference reference;
541 // reserve helpers for map_array and generic maps
542 // ISSUE should be in map_traits but want to use on all compilers
546 void map_reserve (M &/* m */, typename M::size_type /* capacity */) {
548 template<class I, class T, class ALLOC>
550 void map_reserve (map_array<I, T, ALLOC> &m, typename map_array<I, T, ALLOC>::size_type capacity) {
551 m.reserve (capacity);
555 struct map_capacity_traits {
556 typedef typename M::size_type type ;
557 type operator() ( M const& m ) const {
562 template<class I, class T, class ALLOC>
563 struct map_capacity_traits< map_array<I, T, ALLOC> > {
564 typedef typename map_array<I, T, ALLOC>::size_type type ;
565 type operator() ( map_array<I, T, ALLOC> const& m ) const {
566 return m.capacity ();
572 typename map_capacity_traits<M>::type map_capacity (M const& m) {
573 return map_capacity_traits<M>() ( m );