| // |
| // Copyright (c) 2000-2002 |
| // Joerg Walter, Mathias Koch |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // The authors gratefully acknowledge the support of |
| // GeNeSys mbH & Co. KG in producing this work. |
| // |
| |
| #ifndef _BOOST_UBLAS_STORAGE_SPARSE_ |
| #define _BOOST_UBLAS_STORAGE_SPARSE_ |
| |
| #include <map> |
| #include <boost/serialization/collection_size_type.hpp> |
| #include <boost/serialization/nvp.hpp> |
| #include <boost/serialization/array.hpp> |
| #include <boost/serialization/map.hpp> |
| #include <boost/serialization/base_object.hpp> |
| |
| #include <boost/numeric/ublas/storage.hpp> |
| |
| |
| namespace boost { namespace numeric { namespace ublas { |
| |
| namespace detail { |
| |
| template<class I, class T, class C> |
| BOOST_UBLAS_INLINE |
| I lower_bound (const I &begin, const I &end, const T &t, C compare) { |
| // t <= *begin <=> ! (*begin < t) |
| if (begin == end || ! compare (*begin, t)) |
| return begin; |
| if (compare (*(end - 1), t)) |
| return end; |
| return std::lower_bound (begin, end, t, compare); |
| } |
| template<class I, class T, class C> |
| BOOST_UBLAS_INLINE |
| I upper_bound (const I &begin, const I &end, const T &t, C compare) { |
| if (begin == end || compare (t, *begin)) |
| return begin; |
| // (*end - 1) <= t <=> ! (t < *end) |
| if (! compare (t, *(end - 1))) |
| return end; |
| return std::upper_bound (begin, end, t, compare); |
| } |
| |
| template<class P> |
| struct less_pair { |
| BOOST_UBLAS_INLINE |
| bool operator () (const P &p1, const P &p2) { |
| return p1.first < p2.first; |
| } |
| }; |
| template<class T> |
| struct less_triple { |
| BOOST_UBLAS_INLINE |
| bool operator () (const T &t1, const T &t2) { |
| return t1.first.first < t2.first.first || |
| (t1.first.first == t2.first.first && t1.first.second < t2.first.second); |
| } |
| }; |
| |
| } |
| |
| #ifdef BOOST_UBLAS_STRICT_MAP_ARRAY |
| template<class A> |
| class sparse_storage_element: |
| public container_reference<A> { |
| public: |
| typedef A array_type; |
| typedef typename A::key_type index_type; |
| typedef typename A::mapped_type data_value_type; |
| // typedef const data_value_type &data_const_reference; |
| typedef typename type_traits<data_value_type>::const_reference data_const_reference; |
| typedef data_value_type &data_reference; |
| typedef typename A::value_type value_type; |
| typedef value_type *pointer; |
| |
| // Construction and destruction |
| BOOST_UBLAS_INLINE |
| sparse_storage_element (array_type &a, pointer it): |
| container_reference<array_type> (a), it_ (it), i_ (it->first), d_ (it->second), dirty_ (false) {} |
| BOOST_UBLAS_INLINE |
| sparse_storage_element (array_type &a, index_type i): |
| container_reference<array_type> (a), it_ (), i_ (i), d_ (), dirty_ (false) { |
| pointer it = (*this) ().find (i_); |
| if (it == (*this) ().end ()) |
| it = (*this) ().insert ((*this) ().end (), value_type (i_, d_)); |
| d_ = it->second; |
| } |
| BOOST_UBLAS_INLINE |
| ~sparse_storage_element () { |
| if (dirty_) { |
| if (! it_) |
| it_ = (*this) ().find (i_); |
| BOOST_UBLAS_CHECK (it_ != (*this) ().end (), internal_logic ()); |
| it_->second = d_; |
| } |
| } |
| |
| // Element access - only if data_const_reference is defined |
| BOOST_UBLAS_INLINE |
| typename data_value_type::data_const_reference |
| operator [] (index_type i) const { |
| return d_ [i]; |
| } |
| |
| // Assignment |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator = (const sparse_storage_element &p) { |
| // Overide the implict copy assignment |
| d_ = p.d_; |
| dirty_ = true; |
| return *this; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator = (const D &d) { |
| d_ = d; |
| dirty_ = true; |
| return *this; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator += (const D &d) { |
| d_ += d; |
| dirty_ = true; |
| return *this; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator -= (const D &d) { |
| d_ -= d; |
| dirty_ = true; |
| return *this; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator *= (const D &d) { |
| d_ *= d; |
| dirty_ = true; |
| return *this; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| sparse_storage_element &operator /= (const D &d) { |
| d_ /= d; |
| dirty_ = true; |
| return *this; |
| } |
| |
| // Comparison |
| template<class D> |
| BOOST_UBLAS_INLINE |
| bool operator == (const D &d) const { |
| return d_ == d; |
| } |
| template<class D> |
| BOOST_UBLAS_INLINE |
| bool operator != (const D &d) const { |
| return d_ != d; |
| } |
| |
| // Conversion |
| BOOST_UBLAS_INLINE |
| operator data_const_reference () const { |
| return d_; |
| } |
| |
| // Swapping |
| BOOST_UBLAS_INLINE |
| void swap (sparse_storage_element p) { |
| if (this != &p) { |
| dirty_ = true; |
| p.dirty_ = true; |
| std::swap (d_, p.d_); |
| } |
| } |
| BOOST_UBLAS_INLINE |
| friend void swap (sparse_storage_element p1, sparse_storage_element p2) { |
| p1.swap (p2); |
| } |
| |
| private: |
| pointer it_; |
| index_type i_; |
| data_value_type d_; |
| bool dirty_; |
| }; |
| #endif |
| |
| |
| // Default map type is simply forwarded to std::map |
| // FIXME should use ALLOC for map but std::allocator of std::pair<const I, T> and std::pair<I,T> fail to compile |
| template<class I, class T, class ALLOC> |
| class map_std : public std::map<I, T /*, ALLOC */> { |
| public: |
| // Serialization |
| template<class Archive> |
| void serialize(Archive & ar, const unsigned int /* file_version */){ |
| ar & serialization::make_nvp("base", boost::serialization::base_object< std::map<I, T /*, ALLOC */> >(*this)); |
| } |
| }; |
| |
| |
| |
| |
| // Map array |
| // Implementation requires pair<I, T> allocator definition (without const) |
| template<class I, class T, class ALLOC> |
| class map_array { |
| public: |
| typedef ALLOC allocator_type; |
| typedef typename ALLOC::size_type size_type; |
| typedef typename ALLOC::difference_type difference_type; |
| typedef std::pair<I,T> value_type; |
| typedef I key_type; |
| typedef T mapped_type; |
| typedef const value_type &const_reference; |
| typedef value_type &reference; |
| typedef const value_type *const_pointer; |
| typedef value_type *pointer; |
| // Iterators simply are pointers. |
| typedef const_pointer const_iterator; |
| typedef pointer iterator; |
| |
| typedef const T &data_const_reference; |
| #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY |
| typedef T &data_reference; |
| #else |
| typedef sparse_storage_element<map_array> data_reference; |
| #endif |
| |
| // Construction and destruction |
| BOOST_UBLAS_INLINE |
| map_array (const ALLOC &a = ALLOC()): |
| alloc_(a), capacity_ (0), size_ (0) { |
| data_ = 0; |
| } |
| BOOST_UBLAS_INLINE |
| map_array (const map_array &c): |
| alloc_ (c.alloc_), capacity_ (c.size_), size_ (c.size_) { |
| if (capacity_) { |
| data_ = alloc_.allocate (capacity_); |
| std::uninitialized_copy (data_, data_ + capacity_, c.data_); |
| // capacity != size_ requires uninitialized_fill (size_ to capacity_) |
| } |
| else |
| data_ = 0; |
| } |
| BOOST_UBLAS_INLINE |
| ~map_array () { |
| if (capacity_) { |
| std::for_each (data_, data_ + capacity_, static_destroy); |
| alloc_.deallocate (data_, capacity_); |
| } |
| } |
| |
| private: |
| // Resizing - implicitly exposses uninitialized (but default constructed) mapped_type |
| BOOST_UBLAS_INLINE |
| void resize (size_type s) { |
| BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ()); |
| if (s > capacity_) { |
| const size_type cap = s << 1; |
| BOOST_UBLAS_CHECK (cap, internal_logic ()); |
| pointer data = alloc_.allocate (cap); |
| std::uninitialized_copy (data_, data_ + (std::min) (s, size_), data); |
| std::uninitialized_fill (data + (std::min) (s, size_), data + cap, value_type ()); |
| |
| if (capacity_) { |
| std::for_each (data_, data_ + capacity_, static_destroy); |
| alloc_.deallocate (data_, capacity_); |
| } |
| capacity_ = cap; |
| data_ = data; |
| } |
| size_ = s; |
| BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ()); |
| } |
| public: |
| |
| // Reserving |
| BOOST_UBLAS_INLINE |
| void reserve (size_type cap) { |
| BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ()); |
| // Reduce capacity_ if size_ allows |
| BOOST_UBLAS_CHECK (cap >= size_, bad_size ()); |
| pointer data; |
| if (cap) { |
| data = alloc_.allocate (cap); |
| std::uninitialized_copy (data_, data_ + size_, data); |
| std::uninitialized_fill (data + size_, data + cap, value_type ()); |
| } |
| else |
| data = 0; |
| |
| if (capacity_) { |
| std::for_each (data_, data_ + capacity_, static_destroy); |
| alloc_.deallocate (data_, capacity_); |
| } |
| capacity_ = cap; |
| data_ = data; |
| BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ()); |
| } |
| |
| // Random Access Container |
| BOOST_UBLAS_INLINE |
| size_type size () const { |
| return size_; |
| } |
| BOOST_UBLAS_INLINE |
| size_type capacity () const { |
| return capacity_; |
| } |
| BOOST_UBLAS_INLINE |
| size_type max_size () const { |
| return 0; //TODO |
| } |
| |
| BOOST_UBLAS_INLINE |
| bool empty () const { |
| return size_ == 0; |
| } |
| |
| // Element access |
| BOOST_UBLAS_INLINE |
| data_reference operator [] (key_type i) { |
| #ifndef BOOST_UBLAS_STRICT_MAP_ARRAY |
| pointer it = find (i); |
| if (it == end ()) |
| it = insert (end (), value_type (i, mapped_type (0))); |
| BOOST_UBLAS_CHECK (it != end (), internal_logic ()); |
| return it->second; |
| #else |
| return data_reference (*this, i); |
| #endif |
| } |
| |
| // Assignment |
| BOOST_UBLAS_INLINE |
| map_array &operator = (const map_array &a) { |
| if (this != &a) { |
| resize (a.size_); |
| std::copy (a.data_, a.data_ + a.size_, data_); |
| } |
| return *this; |
| } |
| BOOST_UBLAS_INLINE |
| map_array &assign_temporary (map_array &a) { |
| swap (a); |
| return *this; |
| } |
| |
| // Swapping |
| BOOST_UBLAS_INLINE |
| void swap (map_array &a) { |
| if (this != &a) { |
| std::swap (capacity_, a.capacity_); |
| std::swap (data_, a.data_); |
| std::swap (size_, a.size_); |
| } |
| } |
| BOOST_UBLAS_INLINE |
| friend void swap (map_array &a1, map_array &a2) { |
| a1.swap (a2); |
| } |
| |
| // Element insertion and deletion |
| |
| // From Back Insertion Sequence concept |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| iterator push_back (iterator it, const value_type &p) { |
| if (size () == 0 || (it = end () - 1)->first < p.first) { |
| resize (size () + 1); |
| *(it = end () - 1) = p; |
| return it; |
| } |
| external_logic ().raise (); |
| return it; |
| } |
| // Form Unique Associative Container concept |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| std::pair<iterator,bool> insert (const value_type &p) { |
| iterator it = detail::lower_bound (begin (), end (), p, detail::less_pair<value_type> ()); |
| if (it != end () && it->first == p.first) |
| return std::make_pair (it, false); |
| difference_type n = it - begin (); |
| resize (size () + 1); |
| it = begin () + n; // allow for invalidation |
| std::copy_backward (it, end () - 1, end ()); |
| *it = p; |
| return std::make_pair (it, true); |
| } |
| // Form Sorted Associative Container concept |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| iterator insert (iterator hint, const value_type &p) { |
| return insert (p).first; |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| void erase (iterator it) { |
| BOOST_UBLAS_CHECK (begin () <= it && it < end (), bad_index ()); |
| std::copy (it + 1, end (), it); |
| resize (size () - 1); |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| void erase (iterator it1, iterator it2) { |
| if (it1 == it2) return /* nothing to erase */; |
| BOOST_UBLAS_CHECK (begin () <= it1 && it1 < it2 && it2 <= end (), bad_index ()); |
| std::copy (it2, end (), it1); |
| resize (size () - (it2 - it1)); |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| void clear () { |
| resize (0); |
| } |
| |
| // Element lookup |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| const_iterator find (key_type i) const { |
| const_iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ())); |
| if (it == end () || it->first != i) |
| it = end (); |
| return it; |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| iterator find (key_type i) { |
| iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ())); |
| if (it == end () || it->first != i) |
| it = end (); |
| return it; |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| const_iterator lower_bound (key_type i) const { |
| return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()); |
| } |
| // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it. |
| iterator lower_bound (key_type i) { |
| return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()); |
| } |
| |
| BOOST_UBLAS_INLINE |
| const_iterator begin () const { |
| return data_; |
| } |
| BOOST_UBLAS_INLINE |
| const_iterator end () const { |
| return data_ + size_; |
| } |
| |
| BOOST_UBLAS_INLINE |
| iterator begin () { |
| return data_; |
| } |
| BOOST_UBLAS_INLINE |
| iterator end () { |
| return data_ + size_; |
| } |
| |
| // Reverse iterators |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| typedef std::reverse_iterator<iterator> reverse_iterator; |
| |
| BOOST_UBLAS_INLINE |
| const_reverse_iterator rbegin () const { |
| return const_reverse_iterator (end ()); |
| } |
| BOOST_UBLAS_INLINE |
| const_reverse_iterator rend () const { |
| return const_reverse_iterator (begin ()); |
| } |
| BOOST_UBLAS_INLINE |
| reverse_iterator rbegin () { |
| return reverse_iterator (end ()); |
| } |
| BOOST_UBLAS_INLINE |
| reverse_iterator rend () { |
| return reverse_iterator (begin ()); |
| } |
| |
| // Allocator |
| allocator_type get_allocator () { |
| return alloc_; |
| } |
| |
| // Serialization |
| template<class Archive> |
| void serialize(Archive & ar, const unsigned int /* file_version */){ |
| serialization::collection_size_type s (size_); |
| ar & serialization::make_nvp("size",s); |
| if (Archive::is_loading::value) { |
| resize(s); |
| } |
| ar & serialization::make_array(data_, s); |
| } |
| |
| private: |
| // Provide destroy as a non member function |
| BOOST_UBLAS_INLINE |
| static void static_destroy (reference p) { |
| (&p) -> ~value_type (); |
| } |
| ALLOC alloc_; |
| size_type capacity_; |
| pointer data_; |
| size_type size_; |
| }; |
| |
| |
| namespace detail { |
| template<class A, class T> |
| struct map_traits { |
| typedef typename A::mapped_type &reference; |
| }; |
| template<class I, class T, class ALLOC> |
| struct map_traits<map_array<I, T, ALLOC>, T > { |
| typedef typename map_array<I, T, ALLOC>::data_reference reference; |
| }; |
| |
| // reserve helpers for map_array and generic maps |
| // ISSUE should be in map_traits but want to use on all compilers |
| |
| template<class M> |
| BOOST_UBLAS_INLINE |
| void map_reserve (M &/* m */, typename M::size_type /* capacity */) { |
| } |
| template<class I, class T, class ALLOC> |
| BOOST_UBLAS_INLINE |
| void map_reserve (map_array<I, T, ALLOC> &m, typename map_array<I, T, ALLOC>::size_type capacity) { |
| m.reserve (capacity); |
| } |
| |
| template<class M> |
| struct map_capacity_traits { |
| typedef typename M::size_type type ; |
| type operator() ( M const& m ) const { |
| return m.size (); |
| } |
| } ; |
| |
| template<class I, class T, class ALLOC> |
| struct map_capacity_traits< map_array<I, T, ALLOC> > { |
| typedef typename map_array<I, T, ALLOC>::size_type type ; |
| type operator() ( map_array<I, T, ALLOC> const& m ) const { |
| return m.capacity (); |
| } |
| } ; |
| |
| template<class M> |
| BOOST_UBLAS_INLINE |
| typename map_capacity_traits<M>::type map_capacity (M const& m) { |
| return map_capacity_traits<M>() ( m ); |
| } |
| } |
| |
| }}} |
| |
| #endif |