Merge https://gitlab.com/inkscape/inkscape into selectable-knots

1 files changed, 198 insertions, 26 deletions

diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp
index 0ec06dfac..f1b7f0571 100644
--- a/src/libvpsc/constraint.cpp
+++ b/src/libvpsc/constraint.cpp
@@ -1,14 +1,36 @@
 /*
- * Authors:
- *   Tim Dwyer <tgdwyer@gmail.com>
+ * vim: ts=4 sw=4 et tw=0 wm=0
  *
- * Copyright (C) 2005 Authors
+ * libvpsc - A solver for the problem of Variable Placement with 
+ *           Separation Constraints.
  *
- * Released under GNU LGPL.  Read the file 'COPYING' for more information.
- */
+ * Copyright (C) 2005-2008  Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s):  Tim Dwyer
+*/
 
-#include "constraint.h"
+
+#include <map>
+#include <list>
+#include <sstream>
 #include <cassert>
+#include <cfloat>
+#include <cmath>
+
+
+#include "libvpsc/constraint.h"
+#include "libvpsc/variable.h"
+
 namespace vpsc {
 Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality)
 : left(left),
@@ -16,31 +38,181 @@ Constraint::Constraint(Variable *left, Variable *right, double gap, bool equalit
   gap(gap),
   timeStamp(0),
   active(false),
-  visited(false),
-  equality(equality)
+  equality(equality),
+  unsatisfiable(false),
+  needsScaling(true),
+  creator(NULL)
 {
-	left->out.push_back(this);
-	right->in.push_back(this);
+    // In hindsight I think it's probably better to build the constraint DAG
+    // (by creating variable in/out lists) when needed, rather than in advance
+    //left->out.push_back(this);
+    //right->in.push_back(this);
 }
 Constraint::~Constraint() {
-	Constraints::iterator i;
-	for(i=left->out.begin(); i!=left->out.end(); ++i) {
-		if(*i==this) break;
-	}
-	left->out.erase(i);
-	for(i=right->in.begin(); i!=right->in.end(); ++i) {
-		if(*i==this) break;
-	}
-	right->in.erase(i);
+    // see constructor: the following is just way too slow.  
+    // Better to create a
+    // new DAG on demand than maintain the lists dynamically.
+    //Constraints::iterator i;
+    //for(i=left->out.begin(); i!=left->out.end(); i++) {
+        //if(*i==this) break;
+    //}
+    //left->out.erase(i);
+    //for(i=right->in.begin(); i!=right->in.end(); i++) {
+        //if(*i==this) break;
+    //}
+    //right->in.erase(i);
 }
 std::ostream& operator <<(std::ostream &os, const Constraint &c)
 {
-	if(&c==NULL) {
-		os<<"NULL";
-	} else {
-		const char *type=c.equality?"=":"<=";
-		os<<*c.left<<"+"<<c.gap<<type<<*c.right<<"("<<c.slack()<<")"<<(c.active?"-active":"");
-	}
-	return os;
+    const char *type = c.equality ? "=" : "<=";
+    std::ostringstream lscale, rscale;
+    if (c.left->scale != 1) 
+    {
+        lscale << c.left->scale << "*";
+    }
+    if (c.right->scale != 1)
+    {
+        rscale << c.right->scale << "*";
+    }
+    os << lscale.str() << *c.left << "+" << c.gap << type << 
+          rscale.str() << *c.right;
+    if (c.left->block && c.right->block)
+    {
+        os << "(" << c.slack() << ")" << (c.active ? "-active" : "") <<
+              "(lm=" << c.lm << ")";
+    }
+    else
+    {
+        os << "(vars have no position)";
+    }
+    return os;
+}
+#include "libvpsc/block.h"
+bool CompareConstraints::operator() (
+    Constraint *const &l, Constraint *const &r
+) const {
+    double const sl = 
+        l->left->block->timeStamp > l->timeStamp
+        ||l->left->block==l->right->block
+        ?-DBL_MAX:l->slack();
+    double const sr = 
+        r->left->block->timeStamp > r->timeStamp
+        ||r->left->block==r->right->block
+        ?-DBL_MAX:r->slack();
+    if(sl==sr) {
+        // arbitrary choice based on id
+        if(l->left->id==r->left->id) {
+            if(l->right->id<r->right->id) return true;
+            return false;
+        }
+        if(l->left->id<r->left->id) return true;
+        return false;
+    }
+    return sl < sr;
+}
+
+
+typedef std::list<std::map<Variable *, double> > VarOffsetMapList;
+
+class EqualityConstraintSet
+{
+    public:
+        EqualityConstraintSet(Variables vs)
+        {
+            for (size_t i = 0; i < vs.size(); ++i)
+            {
+                std::map<Variable *, double> varSet;
+                varSet[vs[i]] = 0;
+                variableGroups.push_back(varSet);
+            }
+        }
+        bool isRedundant(Variable *lhs, Variable *rhs, double sep)
+        {
+            VarOffsetMapList::iterator lhsSet = setForVar(lhs);
+            VarOffsetMapList::iterator rhsSet = setForVar(rhs);
+            COLA_ASSERT(lhsSet != variableGroups.end());
+            COLA_ASSERT(rhsSet != variableGroups.end());
+            if (lhsSet == rhsSet)
+            {
+                // Check if this is a redundant constraint.
+                if (fabs(((*lhsSet)[lhs] + sep) - (*rhsSet)[rhs]) < 0.0001)
+                {
+                    // If so, return true.
+                    return true;
+                }
+            }
+            return false;
+        }
+        void mergeSets(Variable *lhs, Variable *rhs, double sep)
+        {
+            VarOffsetMapList::iterator lhsSet = setForVar(lhs);
+            VarOffsetMapList::iterator rhsSet = setForVar(rhs);
+            if (lhsSet == rhsSet)
+            {
+                return;
+            }
+
+            double rhsOldOffset = (*rhsSet)[rhs];
+            double rhsNewOffset = (*lhsSet)[lhs] + sep;
+            double offset = rhsNewOffset - rhsOldOffset;
+
+            // Update offsets
+            for (std::map<Variable *, double>::iterator it = rhsSet->begin();
+                    it != rhsSet->end(); ++it)
+            {
+                it->second += offset;
+            }
+            
+            // Merge rhsSet into lhsSet
+            lhsSet->insert(rhsSet->begin(), rhsSet->end());
+            variableGroups.erase(rhsSet);
+        }
+
+    private:
+        VarOffsetMapList::iterator setForVar(Variable *var)
+        {
+            for (VarOffsetMapList::iterator it = variableGroups.begin();
+                    it != variableGroups.end(); ++it)
+            {
+                if (it->find(var) != it->end())
+                {
+                    return it;
+                }
+            }
+            return variableGroups.end();
+        }
+
+    VarOffsetMapList variableGroups;
+};
+
+Constraints constraintsRemovingRedundantEqualities(const Variables& vars, 
+        const Constraints& constraints)
+{
+    EqualityConstraintSet equalitySets(vars);
+    Constraints cs = Constraints(constraints.size());
+    int csSize = 0;
+
+    for (unsigned i = 0; i < constraints.size(); ++i)
+    {
+        Constraint *c = constraints[i];
+        if (c->equality)
+        {
+            if (!equalitySets.isRedundant(c->left, c->right, c->gap))
+            {
+                // Only add non-redundant equalities
+                equalitySets.mergeSets(c->left, c->right, c->gap);
+                cs[csSize++] = c;
+            }
+        }
+        else
+        {
+            // Add all non-equalities
+            cs[csSize++] = c;
+        }
+    }
+    cs.resize(csSize);
+    return cs;
 }
+
+
 }