Module: ppl/ppl Branch: master Commit: 51b8b9197551f04bef467a5d3522e6d60ba86ac1 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=51b8b9197551f... Author: Marco Poletti <poletti.marco@gmail.com> Date: Sat Oct 16 17:17:45 2010 +0200 Sparse_Row: add some methods, to be fully compatible with Dense_Row. --- src/Sparse_Row.cc | 46 +++++++++++++++++++++++++++ src/Sparse_Row.defs.hh | 75 ++++++++++++++++++++++++++++++++++++++++++--- src/Sparse_Row.inlines.hh | 34 +++++++++++++++++++- 3 files changed, 148 insertions(+), 7 deletions(-) diff --git a/src/Sparse_Row.cc b/src/Sparse_Row.cc index 1dec76d..7a7a078 100644 --- a/src/Sparse_Row.cc +++ b/src/Sparse_Row.cc @@ -503,3 +503,49 @@ PPL::Sparse_Row::OK() const { --last; return (last.index() < size_); } + +bool +PPL::Sparse_Row::OK(dimension_type /* capacity */) const { + return OK(); +} + +bool +PPL::operator==(const Sparse_Row& x, const Sparse_Row& y) { + if (x.size() != y.size()) + return false; + Sparse_Row::const_iterator i = x.begin(); + Sparse_Row::const_iterator i_end = x.end(); + Sparse_Row::const_iterator j = y.begin(); + Sparse_Row::const_iterator j_end = y.end(); + while (i != i_end && j != j_end) { + if (i.index() == j.index()) { + if (*i != *j) + return false; + ++i; + ++j; + } else { + if (i.index() < j.index()) { + if (*i != 0) + return false; + ++i; + } else { + PPL_ASSERT(i.index() > j.index()); + if (*j != 0) + return false; + ++j; + } + } + } + for ( ; i != i_end; ++i) + if (*i != 0) + return false; + for ( ; j != j_end; ++j) + if (*j != 0) + return false; + return true; +} + +bool +PPL::operator!=(const Sparse_Row& x, const Sparse_Row& y) { + return !(x == y); +} diff --git a/src/Sparse_Row.defs.hh b/src/Sparse_Row.defs.hh index 1aca6ed..dc74266 100644 --- a/src/Sparse_Row.defs.hh +++ b/src/Sparse_Row.defs.hh @@ -133,7 +133,7 @@ public: Sparse_Row& operator=(const Dense_Row& row); - //! Resizes the row to size \p n. + //! Resizes the row to size \p n and sets the flags to \p flags. /*! \param n The new size for the row. @@ -145,9 +145,9 @@ public: row and removing the trailing k elements. It takes \f$O(1)\f$ time when enlarging the row. */ - void construct(dimension_type n); + void construct(dimension_type n, Flags flags = Flags()); - //! Resizes the row to size \p n. + //! Resizes the row to size \p n and sets the flags to \p flags. /*! \param n The new size for the row. @@ -162,7 +162,8 @@ public: row and removing the trailing k elements. It takes \f$O(1)\f$ time when enlarging the row. */ - void construct(dimension_type n, dimension_type capacity); + void construct(dimension_type n, dimension_type capacity, + Flags flags = Flags()); //! Swaps *this and x. /*! @@ -198,6 +199,18 @@ public: This method, with this signature, is needed for compatibility with Dense_Row. + This method takes \f$O(1)\f$ time. + */ + void expand_within_capacity(dimension_type new_size); + + //! Resizes the row to size \p n. + /*! + \param n + The new size for the row. + + This method, with this signature, is needed for compatibility with + Dense_Row. + This method takes \f$O(k*\log^2 n)\f$ amortized time where k is the number of removed elements. */ @@ -280,6 +293,9 @@ public: */ const const_iterator& cend() const; + //! Returns the size() of the largest possible Sparse_Row. + static dimension_type max_size(); + //! Returns the flags associated with this row. const Flags& flags() const; @@ -770,10 +786,47 @@ public: */ memory_size_type external_memory_in_bytes() const; -private: + //! Returns the size in bytes of the memory managed by \p *this. + /*! + This method is provided for compatibility with Dense_Row. + + This method takes \f$O(n)\f$ time. + + \param capacity + This parameter is ignored. + */ + memory_size_type external_memory_in_bytes(dimension_type capacity) const; + + //! Returns the size in bytes of the memory managed by \p *this. + /*! + This method takes \f$O(n)\f$ time. + */ + memory_size_type total_memory_in_bytes() const; + + //! Returns the size in bytes of the memory managed by \p *this. + /*! + This method is provided for compatibility with Dense_Row. + + This method takes \f$O(n)\f$ time. + + \param capacity + This parameter is ignored. + */ + memory_size_type total_memory_in_bytes(dimension_type capacity) const; + //! Checks the invariant. bool OK() const; + //! Checks the invariant. + /*! + This method is provided for compatibility with Dense_Row. + + \param capacity + This parameter is ignored. + */ + bool OK(dimension_type capacity) const; + +private: //! The tree used to store the elements. CO_Tree tree; @@ -800,6 +853,18 @@ void swap(Parma_Polyhedra_Library::Sparse_Row& x, } // namespace std +namespace Parma_Polyhedra_Library { + +//! Returns <CODE>true</CODE> if and only if \p x and \p y are equal. +/*! \relates Sparse_Row */ +bool operator==(const Sparse_Row& x, const Sparse_Row& y); + +//! Returns <CODE>true</CODE> if and only if \p x and \p y are different. +/*! \relates Sparse_Row */ +bool operator!=(const Sparse_Row& x, const Sparse_Row& y); + +} // namespace Parma_Polyhedra_Library + #include "Sparse_Row.templates.hh" #include "Sparse_Row.inlines.hh" diff --git a/src/Sparse_Row.inlines.hh b/src/Sparse_Row.inlines.hh index ec75549..2e7a17f 100644 --- a/src/Sparse_Row.inlines.hh +++ b/src/Sparse_Row.inlines.hh @@ -55,12 +55,15 @@ Sparse_Row::Sparse_Row(const Sparse_Row& y, dimension_type sz, } inline void -Sparse_Row::construct(dimension_type sz) { +Sparse_Row::construct(dimension_type sz, Flags flags1) { + flags() = flags1; resize(sz); } inline void -Sparse_Row::construct(dimension_type sz, dimension_type /* capacity */) { +Sparse_Row::construct(dimension_type sz, dimension_type /* capacity */, + Flags flags1) { + flags() = flags1; resize(sz); } @@ -88,6 +91,13 @@ Sparse_Row::resize(dimension_type n) { inline void Sparse_Row::shrink(dimension_type n) { + PPL_ASSERT(size() >= n); + resize(n); +} + +inline void +Sparse_Row::expand_within_capacity(dimension_type n) { + PPL_ASSERT(size() <= n); resize(n); } @@ -137,6 +147,11 @@ Sparse_Row::cend() const { return tree.cend(); } +inline dimension_type +Sparse_Row::max_size() { + return CO_Tree::max_size(); +} + inline const Sparse_Row::Flags& Sparse_Row::flags() const { return flags_; @@ -345,6 +360,21 @@ Sparse_Row::external_memory_in_bytes() const { return tree.external_memory_in_bytes(); } +inline memory_size_type +Sparse_Row::external_memory_in_bytes(dimension_type /* capacity */) const { + return external_memory_in_bytes(); +} + +inline memory_size_type +Sparse_Row::total_memory_in_bytes() const { + return external_memory_in_bytes() + sizeof(*this); +} + +inline memory_size_type +Sparse_Row::total_memory_in_bytes(dimension_type /* capacity */) const { + return total_memory_in_bytes(); +} + } // namespace Parma_Polyhedra_Library