Module: ppl/ppl Branch: devel Commit: 2415b288480b08b85692cff798a3ca823d307d79 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2415b288480b0...

Author: Enea Zaffanella zaffanella@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 {