[PPL-devel] [GIT] ppl/ppl(master): Sparse_Row: add some methods, to be fully compatible with Dense_Row.
Marco Poletti
poletti.marco at gmail.com
Sat Oct 16 17:51:44 CEST 2010
Module: ppl/ppl
Branch: master
Commit: 51b8b9197551f04bef467a5d3522e6d60ba86ac1
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=51b8b9197551f04bef467a5d3522e6d60ba86ac1
Author: Marco Poletti <poletti.marco at 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
More information about the PPL-devel
mailing list