1 files changed, 341 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/vpsc.h b/src/3rdparty/adaptagrams/libavoid/vpsc.h
new file mode 100644
index 0000000..947cb90
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libavoid/vpsc.h
@@ -0,0 +1,341 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ *
+ * Copyright (C) 2005-2014  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.
+ *
+ * Licensees holding a valid commercial license may use this file in
+ * accordance with the commercial license agreement provided 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
+ *              Michael Wybrow
+ *
+ * --------------
+ *
+ * This file contains a slightly modified version of IncSolver() from libvpsc:
+ * A solver for the problem of Variable Placement with Separation Constraints.
+ * It has the following changes from the Adaptagrams VPSC version:
+ *  -  The required VPSC code has been consolidated into a single file.
+ *  -  Unnecessary code (like Solver) has been removed.
+ *  -  The PairingHeap code has been replaced by a STL priority_queue.
+ *
+ * Modifications:  Michael Wybrow
+ *
+*/
+
+#ifndef LIBAVOID_VPSC_H
+#define LIBAVOID_VPSC_H
+
+
+#ifdef USELIBVPSC
+
+// By default, libavoid will use it's own version of VPSC defined in this file.
+//
+// Alternatively, you can directly use IncSolver from libvpsc.  This
+// introduces a dependency on libvpsc but it can be preferable in cases
+// where you are building all of Adaptagrams together and want to work
+// with a set of CompoundConstraints or other classes built upon the
+// base libvpsc Constraint classes.
+
+// Include necessary headers from libvpsc.
+#include "libvpsc/variable.h"
+#include "libvpsc/constraint.h"
+#include "libvpsc/rectangle.h"
+#include "libvpsc/solve_VPSC.h"
+
+// Use the libvpsc versions of things needed by libavoid.
+using vpsc::Variable;
+using vpsc::Variables;
+using vpsc::Constraint;
+using vpsc::Constraints;
+using vpsc::IncSolver;
+using vpsc::delete_object;
+
+#else
+
+#include <vector>
+#include <list>
+#include <set>
+#include <queue>
+#include <iostream>
+#include <cfloat>
+
+#include "libavoid/assertions.h"
+
+namespace Avoid {
+
+class Variable;
+class Constraint;
+class Blocks;
+typedef std::vector<Variable*> Variables;
+typedef std::vector<Constraint*> Constraints;
+class CompareConstraints {
+public:
+    bool operator() (Constraint *const &l, Constraint *const &r) const;
+};
+struct PositionStats {
+    PositionStats() : scale(0), AB(0), AD(0), A2(0) {}
+    void addVariable(Variable* const v);
+    double scale;
+    double AB;
+    double AD;
+    double A2;
+};
+
+typedef std::priority_queue<Constraint*,std::vector<Constraint*>,
+        CompareConstraints> Heap;
+
+class Block
+{
+    typedef Variables::iterator Vit;
+    typedef Constraints::iterator Cit;
+    typedef Constraints::const_iterator Cit_const;
+
+    friend std::ostream& operator <<(std::ostream &os,const Block &b);
+public:
+    Variables *vars;
+    double posn;
+    //double weight;
+    //double wposn;
+    PositionStats ps;
+    Block(Blocks *blocks, Variable* const v=nullptr);
+    ~Block(void);
+    Constraint* findMinLM();
+    Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
+    Constraint* findMinInConstraint();
+    Constraint* findMinOutConstraint();
+    void deleteMinInConstraint();
+    void deleteMinOutConstraint();
+    void updateWeightedPosition();
+    void merge(Block *b, Constraint *c, double dist);
+    Block* merge(Block *b, Constraint *c);
+    void mergeIn(Block *b);
+    void mergeOut(Block *b);
+    void split(Block *&l, Block *&r, Constraint *c);
+    Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
+    void setUpInConstraints();
+    void setUpOutConstraints();
+    double cost();
+    bool deleted;
+    long timeStamp;
+    Heap *in;
+    Heap *out;
+    bool getActivePathBetween(Constraints& path, Variable const* u,
+               Variable const* v, Variable const *w) const;
+    bool isActiveDirectedPathBetween(
+            Variable const* u, Variable const* v) const;
+    bool getActiveDirectedPathBetween(Constraints& path, Variable const * u, Variable const * v) const;
+private:
+    typedef enum {NONE, LEFT, RIGHT} Direction;
+    typedef std::pair<double, Constraint*> Pair;
+    void reset_active_lm(Variable* const v, Variable* const u);
+    void list_active(Variable* const v, Variable* const u);
+    double compute_dfdv(Variable* const v, Variable* const u);
+    double compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm);
+    bool split_path(Variable*, Variable* const, Variable* const,
+            Constraint* &min_lm, bool desperation);
+    bool canFollowLeft(Constraint const* c, Variable const* last) const;
+    bool canFollowRight(Constraint const* c, Variable const* last) const;
+    void populateSplitBlock(Block *b, Variable* v, Variable const* u);
+    void addVariable(Variable* v);
+    void setUpConstraintHeap(Heap* &h,bool in);
+
+    // Parent container, that holds the blockTimeCtr.
+    Blocks *blocks;
+};
+
+
+class Constraint;
+typedef std::vector<Constraint*> Constraints;
+class Variable
+{
+    friend std::ostream& operator <<(std::ostream &os, const Variable &v);
+    friend class Block;
+    friend class Constraint;
+    friend class IncSolver;
+public:
+    int id; // useful in log files
+    double desiredPosition;
+    double finalPosition;
+    double weight; // how much the variable wants to
+                   // be at it's desired position
+    double scale; // translates variable to another space
+    double offset;
+    Block *block;
+    bool visited;
+    bool fixedDesiredPosition;
+    Constraints in;
+    Constraints out;
+    inline Variable(const int id, const double desiredPos=-1.0,
+            const double weight=1.0, const double scale=1.0)
+        : id(id)
+        , desiredPosition(desiredPos)
+        , weight(weight)
+        , scale(scale)
+        , offset(0)
+        , block(nullptr)
+        , visited(false)
+        , fixedDesiredPosition(false)
+    {
+    }
+    double dfdv(void) const {
+        return 2. * weight * ( position() - desiredPosition );
+    }
+private:
+    inline double position(void) const {
+        return (block->ps.scale*block->posn+offset)/scale;
+    }
+    inline double unscaledPosition(void) const {
+        COLA_ASSERT(block->ps.scale == 1);
+        COLA_ASSERT(scale == 1);
+        return block->posn + offset;
+    }
+};
+
+
+class Constraint
+{
+public:
+    Constraint(Variable *left, Variable *right, double gap, bool equality=false);
+    ~Constraint();
+    inline double slack(void) const
+    {
+        if (unsatisfiable)
+        {
+            return DBL_MAX;
+        }
+        if (needsScaling)
+        {
+            return right->scale * right->position() - gap -
+                    left->scale * left->position();
+        }
+        COLA_ASSERT(left->scale == 1);
+        COLA_ASSERT(right->scale == 1);
+        return right->unscaledPosition() - gap - left->unscaledPosition();
+    }
+    std::string toString(void) const;
+
+    friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
+    Variable *left;
+    Variable *right;
+    double gap;
+    double lm;
+    long timeStamp;
+    bool active;
+    const bool equality;
+    bool unsatisfiable;
+    bool needsScaling;
+    void *creator;
+};
+/*
+ * A block structure defined over the variables such that each block contains
+ * 1 or more variables, with the invariant that all constraints inside a block
+ * are satisfied by keeping the variables fixed relative to one another
+ */
+class Blocks
+{
+public:
+    Blocks(Variables const &vs);
+    ~Blocks(void);
+    void mergeLeft(Block *r);
+    void mergeRight(Block *l);
+    void split(Block *b, Block *&l, Block *&r, Constraint *c);
+    std::list<Variable*> *totalOrder();
+    void cleanup();
+    double cost();
+
+    size_t size() const;
+    Block *at(size_t index) const;
+    void insert(Block *block);
+
+    long blockTimeCtr;
+private:
+    void dfsVisit(Variable *v, std::list<Variable*> *order);
+    void removeBlock(Block *doomed);
+
+    std::vector<Block *> m_blocks;
+    Variables const &vs;
+    size_t nvs;
+};
+
+inline size_t Blocks::size() const
+{
+    return m_blocks.size();
+}
+
+inline Block *Blocks::at(size_t index) const
+{
+    return m_blocks[index];
+}
+
+inline void Blocks::insert(Block *block)
+{
+    m_blocks.push_back(block);
+}
+
+struct UnsatisfiableException {
+    Constraints path;
+};
+struct UnsatisfiedConstraint {
+    UnsatisfiedConstraint(Constraint& c):c(c) {}
+    Constraint& c;
+};
+/*
+ * Variable Placement with Separation Constraints problem instance
+ */
+class IncSolver {
+public:
+    unsigned splitCnt;
+    bool satisfy();
+    bool solve();
+    void moveBlocks();
+    void splitBlocks();
+    IncSolver(Variables const &vs, Constraints const &cs);
+
+    ~IncSolver();
+    void addConstraint(Constraint *constraint);
+    Variables const & getVariables() { return vs; }
+protected:
+    Blocks *bs;
+    size_t m;
+    Constraints const &cs;
+    size_t n;
+    Variables const &vs;
+    bool needsScaling;
+
+    void printBlocks();
+    void copyResult();
+private:
+    bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]);
+    bool blockGraphIsCyclic();
+    Constraints inactive;
+    Constraints violated;
+    Constraint* mostViolated(Constraints &l);
+};
+
+struct delete_object
+{
+    template <typename T>
+    void operator()(T *ptr){ delete ptr;}
+};
+
+extern Constraints constraintsRemovingRedundantEqualities(
+        Variables const &vars, Constraints const &constraints);
+
+}
+
+#endif // ! USELIBVPSC
+
+#endif // AVOID_VPSC_H