vector_sparse.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 1,787 行 · 第 1/5 页

            storage_invariants ();
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
            vector_container<self_type> (),
            size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)),
            filled_ (0), sorted_filled_ (filled_), sorted_ (true),
            index_data_ (capacity_), value_data_ (capacity_) {
            storage_invariants ();
            vector_assign<scalar_assign> (*this, ae);
        }

        // Accessors
        BOOST_UBLAS_INLINE
        size_type size () const {
            return size_;
        }
        BOOST_UBLAS_INLINE
        size_type nnz_capacity () const {
            return capacity_;
        }
        BOOST_UBLAS_INLINE
        size_type nnz () const {
            return filled_;
        }

        // Storage accessors
        BOOST_UBLAS_INLINE
        static size_type index_base () {
            return IB;
        }
        BOOST_UBLAS_INLINE
        typename index_array_type::size_type filled () const {
            return filled_;
        }
        BOOST_UBLAS_INLINE
        const index_array_type &index_data () const {
            return index_data_;
        }
        BOOST_UBLAS_INLINE
        const value_array_type &value_data () const {
            return value_data_;
        }
        BOOST_UBLAS_INLINE
        void set_filled (const typename index_array_type::size_type &sorted, const typename index_array_type::size_type &filled) {
            sorted_filled_ = sorted;
            filled_ = filled;
            storage_invariants ();
            return filled_;
        }
        BOOST_UBLAS_INLINE
        index_array_type &index_data () {
            return index_data_;
        }
        BOOST_UBLAS_INLINE
        value_array_type &value_data () {
            return value_data_;
        }

        // Resizing
    private:
        BOOST_UBLAS_INLINE
        size_type restrict_capacity (size_type non_zeros) const {
             // minimum non_zeros
             non_zeros = (std::max) (non_zeros, size_type (1));
             // ISSUE no maximum as coordinate may contain inserted duplicates
             return non_zeros;
        }
    public:
        BOOST_UBLAS_INLINE
        void resize (size_type size, bool preserve = true) {
            if (preserve)
                sort ();    // remove duplicate elements.
            size_ = size;
            capacity_ = restrict_capacity (capacity_);
            if (preserve) {
                index_data_. resize (capacity_, size_type ());
                value_data_. resize (capacity_, value_type ());
                filled_ = (std::min) (capacity_, filled_);
                while ((filled_ > 0) && (zero_based(index_data_[filled_ - 1]) >= size)) {
                    --filled_;
                }
            }
            else {
                index_data_. resize (capacity_);
                value_data_. resize (capacity_);
                filled_ = 0;
            }
            sorted_filled_ = filled_;
            storage_invariants ();
        }
        // Reserving
        BOOST_UBLAS_INLINE
        void reserve (size_type non_zeros, bool preserve = true) {
            if (preserve)
                sort ();    // remove duplicate elements.
            capacity_ = restrict_capacity (non_zeros);
            if (preserve) {
                index_data_. resize (capacity_, size_type ());
                value_data_. resize (capacity_, value_type ());
                filled_ = (std::min) (capacity_, filled_);
                }
            else {
                index_data_. resize (capacity_);
                value_data_. resize (capacity_);
                filled_ = 0;
            }
            sorted_filled_ = filled_;
            storage_invariants ();
        }

        // Element support
        BOOST_UBLAS_INLINE
        pointer find_element (size_type i) {
            return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
        }
        BOOST_UBLAS_INLINE
        const_pointer find_element (size_type i) const {
            sort ();
            const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
            if (it == index_data_.begin () + filled_ || *it != k_based (i))
                return 0;
            return &value_data_ [it - index_data_.begin ()];
        }

        // Element access
        BOOST_UBLAS_INLINE
        const_reference operator () (size_type i) const {
            BOOST_UBLAS_CHECK (i < size_, bad_index ());
            sort ();
            const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
            if (it == index_data_.begin () + filled_ || *it != k_based (i))
                return zero_;
            return value_data_ [it - index_data_.begin ()];
        }
        BOOST_UBLAS_INLINE
        true_reference ref (size_type i) {
            BOOST_UBLAS_CHECK (i < size_, bad_index ());
            sort ();
            subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
            if (it == index_data_.begin () + filled_ || *it != k_based (i))
                return insert_element (i, value_type/*zero*/());
            else
                return value_data_ [it - index_data_.begin ()];
        }
        BOOST_UBLAS_INLINE
        reference operator () (size_type i) {
#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
            return ref (i);
#else
            BOOST_UBLAS_CHECK (i < size_, bad_index ());
            return reference (*this, i);
#endif
        }

        BOOST_UBLAS_INLINE
        const_reference operator [] (size_type i) const {
            return (*this) (i);
        }
        BOOST_UBLAS_INLINE
        reference operator [] (size_type i) {
            return (*this) (i);
        }

        // Element assignment
        BOOST_UBLAS_INLINE
        void append_element (size_type i, const_reference t) {
            if (filled_ >= capacity_)
                reserve (2 * filled_, true);
            BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
            index_data_ [filled_] = k_based (i);
            value_data_ [filled_] = t;
            ++ filled_;
            sorted_ = false;
            storage_invariants ();
        }
        BOOST_UBLAS_INLINE
        true_reference insert_element (size_type i, const_reference t) {
            BOOST_UBLAS_CHECK (!find_element (i), bad_index ());        // duplicate element
            append_element (i, t);
            return value_data_ [filled_ - 1];
        }
        BOOST_UBLAS_INLINE
        void erase_element (size_type i) {
            sort ();
            subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
            typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
            if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
                std::copy (it + 1, index_data_.begin () + filled_, it);
                typename value_array_type::iterator itt (value_data_.begin () + n);
                std::copy (itt + 1, value_data_.begin () + filled_, itt);
                -- filled_;
                sorted_filled_ = filled_;
            }
            storage_invariants ();
        }
        
        // Zeroing
        BOOST_UBLAS_INLINE
        void clear () {
            filled_ = 0;
            sorted_filled_ = filled_;
            sorted_ = true;
            storage_invariants ();
        }
        
        // Assignment
        BOOST_UBLAS_INLINE
        coordinate_vector &operator = (const coordinate_vector &v) {
            if (this != &v) {
                size_ = v.size_;
                capacity_ = v.capacity_;
                filled_ = v.filled_;
                sorted_filled_ = v.sorted_filled_;
                sorted_ = v.sorted_;
                index_data_ = v.index_data_;
                value_data_ = v.value_data_;
            }
            storage_invariants ();
            return *this;
        }
        template<class C>          // Container assignment without temporary
        BOOST_UBLAS_INLINE
        coordinate_vector &operator = (const vector_container<C> &v) {
            resize (v ().size (), false);
            assign (v);
            return *this;
        }
        BOOST_UBLAS_INLINE
        coordinate_vector &assign_temporary (coordinate_vector &v) {
            swap (v);
            return *this;
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &operator = (const vector_expression<AE> &ae) {
            self_type temporary (ae, capacity_);
            return assign_temporary (temporary);
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &assign (const vector_expression<AE> &ae) {
            vector_assign<scalar_assign> (*this, ae);
            return *this;
        }

        // Computed assignment
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &operator += (const vector_expression<AE> &ae) {
            self_type temporary (*this + ae, capacity_);
            return assign_temporary (temporary);
        }
        template<class C>          // Container assignment without temporary
        BOOST_UBLAS_INLINE
        coordinate_vector &operator += (const vector_container<C> &v) {
            plus_assign (v);
            return *this;
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &plus_assign (const vector_expression<AE> &ae) {
            vector_assign<scalar_plus_assign> (*this, ae);
            return *this;
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &operator -= (const vector_expression<AE> &ae) {
            self_type temporary (*this - ae, capacity_);
            return assign_temporary (temporary);
        }
        template<class C>          // Container assignment without temporary
        BOOST_UBLAS_INLINE
        coordinate_vector &operator -= (const vector_container<C> &v) {
            minus_assign (v);
            return *this;
        }
        template<class AE>
        BOOST_UBLAS_INLINE
        coordinate_vector &minus_assign (const vector_expression<AE> &ae) {
            vector_assign<scalar_minus_assign> (*this, ae);
            return *this;
        }
        template<class AT>
        BOOST_UBLAS_INLINE
        coordinate_vector &operator *= (const AT &at) {
            vector_assign_scalar<scalar_multiplies_assign> (*this, at);
            return *this;
        }
        template<class AT>
        BOOST_UBLAS_INLINE
        coordinate_vector &operator /= (const AT &at) {
            vector_assign_scalar<scalar_divides_assign> (*this, at);
            return *this;
        }

        // Swapping
        BOOST_UBLAS_INLINE
        void swap (coordinate_vector &v) {
            if (this != &v) {
                std::swap (size_, v.size_);
                std::swap (capacity_, v.capacity_);
                std::swap (filled_, v.filled_);
                std::swap (sorted_filled_, v.sorted_filled_);
                std::swap (sorted_, v.sorted_);
                index_data_.swap (v.index_data_);
                value_data_.swap (v.value_data_);
            }
            storage_invariants ();
        }
        BOOST_UBLAS_INLINE
        friend void swap (coordinate_vector &v1, coordinate_vector &v2) {
            v1.swap (v2);
        }

        // Sorting and summation of duplicates
        BOOST_UBLAS_INLINE
        void sort () const {
            if (! sorted_ && filled_ > 0) {
                typedef index_pair_array<index_array_type, value_array_type> array_pair;
                array_pair ipa (filled_, index_data_, value_data_);
                const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
                // sort new elements and merge
                std::sort (iunsorted, ipa.end ());
                std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
                
                // sum duplicates with += and remove
                size_type filled = 0;
                for (size_type i = 1; i < filled_; ++ i) {
                    if (index_data_ [filled] != index_data_ [i]) {
                        ++ filled;
                        if (filled != i) {
                            index_data_ [filled] = index_data_ [i];
                            value_data_ [filled] = value_data_ [i];
                        }
                    } else {
                        value_data_ [filled] += value_data_ [i];
                    }
                }
                filled_ = filled + 1;
                sorted_filled_ = filled_;
                sorted_ = true;
                storage_invariants ();
            }
        }

        // Back element insertion and erasure
        BOOST_UBLAS_INLINE
        void push_back (size_type i, const_reference t) {
            // must maintain sort order
            BOOST_UBLAS_CHECK (sorted_ && (filled_ == 0 || index_data_ [filled_ - 1] < k_based (i)), external_logic ());
            if (filled_ >= capacity_)
                reserve (2 * filled_, true);
            BOOST_UBLAS_CHECK (filled_ < capacity_, inter