[PPL-devel] [GIT] ppl/ppl(pip): Implemented row sign detection.

[François Galea]

Module: ppl/ppl
Branch: pip
Commit: 9ce39ca898aa35e1639b768a5d7c92e987a9d3d2
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9ce39ca898aa35e1639b768a5d7c92e987a9d3d2

Author: François Galea <francois.galea at uvsq.fr>
Date:   Fri Sep 11 13:16:08 2009 +0200

Implemented row sign detection.

---

 src/PIP_Tree.cc      |   33 +++++++++++++++++++++++++++++++++
 src/PIP_Tree.defs.hh |   20 ++++++++++++++++++++
 2 files changed, 53 insertions(+), 0 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 2f1afe0..b552c72 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -209,6 +209,38 @@ PIP_Solution_Node::ascii_load(std::istream& s) {
   return true;
 }
 
+PIP_Solution_Node::Row_Sign
+PIP_Solution_Node::row_sign(const Row &x) {
+  PIP_Solution_Node::Row_Sign sign = ZERO;
+  Coefficient c;
+  for (int i = x.size(); i-- > 0; ) {
+    c = x[i];
+    switch (sign) {
+      case UNKNOWN:
+        // cannot happen
+        break;
+      case ZERO:
+        if (c < 0)
+          sign = NEGATIVE;
+        else if (c > 0)
+          sign = POSITIVE;
+        break;
+      case NEGATIVE:
+        if (c > 0)
+          return MIXED;
+        break;
+      case POSITIVE:
+        if (c < 0)
+          return MIXED;
+        break;
+      case MIXED:
+        // cannot happen
+        break;
+    }
+  }
+  return sign;
+}
+
 void
 PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */,
                                   dimension_type external_space_dim,
@@ -273,6 +305,7 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */,
     // FIXME: must handle equality constraints
     tableau.s.add_row(var);
     tableau.t.add_row(param);
+    sign.push_back(row_sign(param));
   }
   // FIXME: decide emptiness detection (and node removal)
 }
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index 13dc12b..e0ce99c 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -232,9 +232,29 @@ private:
   */
   std::vector<dimension_type> mapping;
 
+  //! The possible values for the sign of a parametric linear expression.
+  enum Row_Sign {
+    //! Not computed yet (default)
+    UNKNOWN,
+    //! All row coefficients are zero.
+    ZERO,
+    //! All nonzero row coefficients are positive.
+    POSITIVE,
+    //! All nonzero row coefficients are negative.
+    NEGATIVE,
+    //! The row contains positive and negative coefficients.
+    MIXED
+  };
+
+  //! A cache for computed sign values of constraint parametric RHS
+  std::vector<Row_Sign> sign;
+
   //! The local system of parameter constraints
   Constraint_System constraints_;
 
+  //! Determines the sign of given Row
+  static Row_Sign row_sign(const Row &x);
+
 protected:
   /*! \brief
     Populates the parametric simplex tableau using external data, if necessary