[PPL-devel] [GIT] ppl/ppl(devel): Modified the comparison function for generators.
Enea Zaffanella
zaffanella at cs.unipr.it
Thu Aug 3 19:22:18 CEST 2017
Module: ppl/ppl
Branch: devel
Commit: 2415b288480b08b85692cff798a3ca823d307d79
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2415b288480b08b85692cff798a3ca823d307d79
Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date: Thu Aug 3 18:19:45 2017 +0200
Modified the comparison function for generators.
The epsilon coefficient is checked last, after the divisor.
This fixes the bug identified in test07() of nncminimize1.cc.
---
src/Expression_Hide_Last_defs.hh | 8 +++++
src/Expression_Hide_Last_inlines.hh | 52 +++++++++++++++++++++++++++++++
src/Generator.cc | 43 ++++++++++++++++++++++---
src/Linear_Expression_Impl_defs.hh | 3 ++
src/Linear_Expression_Impl_templates.hh | 6 +++
src/Linear_Expression_Interface_defs.hh | 3 ++
src/Linear_Expression_defs.hh | 3 ++
src/Linear_Expression_inlines.hh | 7 ++++
8 files changed, 119 insertions(+), 6 deletions(-)
diff --git a/src/Expression_Hide_Last_defs.hh b/src/Expression_Hide_Last_defs.hh
index d57005c..392a25e 100644
--- a/src/Expression_Hide_Last_defs.hh
+++ b/src/Expression_Hide_Last_defs.hh
@@ -160,6 +160,14 @@ private:
const bool hide_last_;
};
+namespace Parma_Polyhedra_Library {
+
+template <typename T>
+int compare(const Expression_Hide_Last<T>& x,
+ const Expression_Hide_Last<T>& y);
+
+} // namespace Parma_Polyhedra_Library
+
#include "Expression_Hide_Last_inlines.hh"
#endif // !defined(PPL_Expression_Hide_Last_defs_hh)
diff --git a/src/Expression_Hide_Last_inlines.hh b/src/Expression_Hide_Last_inlines.hh
index 17306dd..58bc72b 100644
--- a/src/Expression_Hide_Last_inlines.hh
+++ b/src/Expression_Hide_Last_inlines.hh
@@ -239,6 +239,58 @@ Expression_Hide_Last<T>
return this->inner().have_a_common_variable(y, first, last);
}
+template <typename T>
+inline int
+compare(const Expression_Hide_Last<T>& x, const Expression_Hide_Last<T>& y) {
+ typedef typename Expression_Hide_Last<T>::const_iterator CIter;
+ CIter i = x.begin();
+ CIter i_end = x.end();
+ CIter j = y.begin();
+ CIter j_end = y.end();
+ while (i != i_end && j != j_end) {
+ if (i.index() < j.index()) {
+ const int s = sgn(*i);
+ if (s != 0) {
+ return 2*s;
+ }
+ ++i;
+ continue;
+ }
+ if (i.index() > j.index()) {
+ const int s = sgn(*j);
+ if (s != 0) {
+ return -2*s;
+ }
+ ++j;
+ continue;
+ }
+ PPL_ASSERT(i.index() == j.index());
+ const int s = cmp(*i, *j);
+ if (s < 0) {
+ return -2;
+ }
+ if (s > 0) {
+ return 2;
+ }
+ PPL_ASSERT(s == 0);
+ ++i;
+ ++j;
+ }
+ for ( ; i != i_end; ++i) {
+ const int s = sgn(*i);
+ if (s != 0) {
+ return 2*s;
+ }
+ }
+ for ( ; j != j_end; ++j) {
+ const int s = sgn(*j);
+ if (s != 0) {
+ return -2*s;
+ }
+ }
+ return 0;
+}
+
} // namespace Parma_Polyhedra_Library
#endif // !defined(PPL_Expression_Hide_Last_inlines_hh)
diff --git a/src/Generator.cc b/src/Generator.cc
index 8958163..4ee294d 100644
--- a/src/Generator.cc
+++ b/src/Generator.cc
@@ -212,14 +212,45 @@ PPL::Generator::linear_combine(const Generator& y, const dimension_type i) {
/*! \relates Parma_Polyhedra_Library::Generator */
int
PPL::compare(const Generator& x, const Generator& y) {
- const bool x_is_line_or_equality = x.is_line_or_equality();
- const bool y_is_line_or_equality = y.is_line_or_equality();
- if (x_is_line_or_equality != y_is_line_or_equality) {
- // Equalities (lines) precede inequalities (ray/point).
- return y_is_line_or_equality ? 2 : -2;
+ const bool x_is_line = x.is_line();
+ const bool y_is_line = y.is_line();
+ if (x_is_line != y_is_line) {
+ // Lines precede rays and (closure) points.
+ return y_is_line ? 2 : -2;
+ }
+ if (x.is_necessarily_closed() && y.is_necessarily_closed()) {
+ return compare(x.expr, y.expr);
}
- return compare(x.expr, y.expr);
+ // Epsilon coefficient should be checked last:
+ // to this end, we use the adapted expression().
+ int comp = compare(x.expression(), y.expression());
+ if (comp != 0) {
+ return comp;
+ }
+ // Same homogeneous terms (disregarding epsilon).
+ if (x_is_line) {
+ PPL_ASSERT(y_is_line);
+ // Same line.
+ return 0;
+ }
+ if (x.is_ray()) {
+ return y.is_ray() ? 0 : -1;
+ }
+ if (y.is_ray()) {
+ return 1;
+ }
+ // Compare divisors.
+ comp = cmp(x.divisor(), y.divisor());
+ if (comp > 0) {
+ return 1;
+ }
+ if (comp < 0) {
+ return -1;
+ }
+ PPL_ASSERT(comp == 0);
+ // `x' and `y' may only differ on their epsilon coefficient.
+ return cmp(x.epsilon_coefficient(), y.epsilon_coefficient());
}
bool
diff --git a/src/Linear_Expression_Impl_defs.hh b/src/Linear_Expression_Impl_defs.hh
index f6e41e8..51094af 100644
--- a/src/Linear_Expression_Impl_defs.hh
+++ b/src/Linear_Expression_Impl_defs.hh
@@ -172,6 +172,9 @@ public:
*/
virtual Variable variable() const;
+ //! Returns the index of the coefficient pointed to by \c *this.
+ virtual dimension_type index() const;
+
//! Compares \p *this with x .
/*!
\param x
diff --git a/src/Linear_Expression_Impl_templates.hh b/src/Linear_Expression_Impl_templates.hh
index f388a97..fd0d86f 100644
--- a/src/Linear_Expression_Impl_templates.hh
+++ b/src/Linear_Expression_Impl_templates.hh
@@ -1327,6 +1327,12 @@ Linear_Expression_Impl<Row>::const_iterator
}
template <typename Row>
+dimension_type
+Linear_Expression_Impl<Row>::const_iterator::index() const {
+ return itr.index();
+}
+
+template <typename Row>
bool
Linear_Expression_Impl<Row>::const_iterator
::operator==(const const_iterator_interface& x) const {
diff --git a/src/Linear_Expression_Interface_defs.hh b/src/Linear_Expression_Interface_defs.hh
index 3e973e9..e616a1b 100644
--- a/src/Linear_Expression_Interface_defs.hh
+++ b/src/Linear_Expression_Interface_defs.hh
@@ -96,6 +96,9 @@ public:
*/
virtual Variable variable() const = 0;
+ //! Returns the index of the coefficient pointed to by \c *this.
+ virtual dimension_type index() const = 0;
+
//! Compares \p *this with x .
/*!
\param x
diff --git a/src/Linear_Expression_defs.hh b/src/Linear_Expression_defs.hh
index b6e72d3..db10bcb 100644
--- a/src/Linear_Expression_defs.hh
+++ b/src/Linear_Expression_defs.hh
@@ -459,6 +459,9 @@ public:
*/
Variable variable() const;
+ //! Returns the index of the coefficient pointed to by \c *this.
+ dimension_type index() const;
+
//! Compares \p *this with \p i.
/*!
\param i
diff --git a/src/Linear_Expression_inlines.hh b/src/Linear_Expression_inlines.hh
index 202bb21..b5b532a 100644
--- a/src/Linear_Expression_inlines.hh
+++ b/src/Linear_Expression_inlines.hh
@@ -682,6 +682,13 @@ Linear_Expression::const_iterator
return itr->variable();
}
+inline dimension_type
+Linear_Expression::const_iterator
+::index() const {
+ PPL_ASSERT(itr != NULL);
+ return itr->index();
+}
+
inline bool
Linear_Expression::const_iterator
::operator==(const const_iterator& i) const {
More information about the PPL-devel
mailing list