From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- src/3rdparty/adaptagrams/libavoid/vpsc.h | 341 +++++++++++++++++++++++++++++++ 1 file changed, 341 insertions(+) create mode 100644 src/3rdparty/adaptagrams/libavoid/vpsc.h (limited to 'src/3rdparty/adaptagrams/libavoid/vpsc.h') 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 +#include +#include +#include +#include +#include + +#include "libavoid/assertions.h" + +namespace Avoid { + +class Variable; +class Constraint; +class Blocks; +typedef std::vector Variables; +typedef std::vector 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, + 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 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 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 *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 *order); + void removeBlock(Block *doomed); + + std::vector 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 + void operator()(T *ptr){ delete ptr;} +}; + +extern Constraints constraintsRemovingRedundantEqualities( + Variables const &vars, Constraints const &constraints); + +} + +#endif // ! USELIBVPSC + +#endif // AVOID_VPSC_H -- cgit v1.2.3