37 #ifndef LIBAVOID_VPSC_H
38 #define LIBAVOID_VPSC_H
50 typedef std::vector<Variable*> Variables;
51 typedef std::vector<Constraint*> Constraints;
52 class CompareConstraints {
54 bool operator() (Constraint *
const &l, Constraint *
const &r)
const;
56 struct PositionStats {
57 PositionStats() : scale(0), AB(0), AD(0), A2(0) {}
58 void addVariable(Variable*
const v);
65 typedef std::priority_queue<Constraint*,std::vector<Constraint*>,
66 CompareConstraints> Heap;
70 typedef Variables::iterator Vit;
71 typedef Constraints::iterator Cit;
72 typedef Constraints::const_iterator Cit_const;
74 friend std::ostream& operator <<(std::ostream &os,
const Block &b);
81 Block(Blocks *blocks, Variable*
const v=NULL);
83 Constraint* findMinLM();
84 Constraint* findMinLMBetween(Variable*
const lv, Variable*
const rv);
85 Constraint* findMinInConstraint();
86 Constraint* findMinOutConstraint();
87 void deleteMinInConstraint();
88 void deleteMinOutConstraint();
89 void updateWeightedPosition();
90 void merge(Block *b, Constraint *c,
double dist);
91 Block* merge(Block *b, Constraint *c);
92 void mergeIn(Block *b);
93 void mergeOut(Block *b);
94 void split(Block *&l, Block *&r, Constraint *c);
95 Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
96 void setUpInConstraints();
97 void setUpOutConstraints();
103 bool getActivePathBetween(Constraints& path, Variable
const* u,
104 Variable
const* v, Variable
const *w)
const;
105 bool isActiveDirectedPathBetween(
106 Variable
const* u, Variable
const* v)
const;
107 bool getActiveDirectedPathBetween(Constraints& path, Variable
const * u, Variable
const * v)
const;
109 typedef enum {NONE, LEFT, RIGHT} Direction;
110 typedef std::pair<double, Constraint*> Pair;
111 void reset_active_lm(Variable*
const v, Variable*
const u);
112 void list_active(Variable*
const v, Variable*
const u);
113 double compute_dfdv(Variable*
const v, Variable*
const u);
114 double compute_dfdv(Variable*
const v, Variable*
const u, Constraint *&min_lm);
115 bool split_path(Variable*, Variable*
const, Variable*
const,
116 Constraint* &min_lm,
bool desperation);
117 bool canFollowLeft(Constraint
const* c, Variable
const* last)
const;
118 bool canFollowRight(Constraint
const* c, Variable
const* last)
const;
119 void populateSplitBlock(Block *b, Variable* v, Variable
const* u);
120 void addVariable(Variable* v);
121 void setUpConstraintHeap(Heap* &h,
bool in);
129 typedef std::vector<Constraint*> Constraints;
132 friend std::ostream& operator <<(std::ostream &os,
const Variable &v);
134 friend class Constraint;
135 friend class IncSolver;
138 double desiredPosition;
139 double finalPosition;
146 bool fixedDesiredPosition;
150 inline Variable(
const int id,
const double desiredPos=-1.0,
151 const double weight=1.0,
const double scale=1.0)
153 , desiredPosition(desiredPos)
159 , fixedDesiredPosition(false)
162 double dfdv()
const {
163 return 2. * weight * ( position() - desiredPosition );
166 double position()
const {
167 return (block->ps.scale*block->posn+offset)/scale;
174 friend std::ostream& operator <<(std::ostream &os,
const Constraint &c);
180 Constraint(Variable *left, Variable *right,
double gap,
bool equality=
false);
182 double slack()
const;
193 class Blocks :
public std::set<Block*>
196 Blocks(Variables
const &vs);
198 void mergeLeft(Block *r);
199 void mergeRight(Block *l);
200 void split(Block *b, Block *&l, Block *&r, Constraint *c);
201 std::list<Variable*> *totalOrder();
207 void dfsVisit(Variable *v, std::list<Variable*> *order);
208 void removeBlock(Block *doomed);
213 extern long blockTimeCtr;
215 struct UnsatisfiableException {
218 struct UnsatisfiedConstraint {
219 UnsatisfiedConstraint(Constraint& c):c(c) {}
232 IncSolver(Variables
const &vs, Constraints
const &cs);
235 Variables
const & getVariables() {
return vs; }
239 Constraints
const &cs;
245 bool constraintGraphIsCyclic(
const unsigned n, Variable*
const vs[]);
246 bool blockGraphIsCyclic();
247 Constraints inactive;
248 Constraints violated;
249 Constraint* mostViolated(Constraints &l);
254 template <
typename T>
255 void operator()(T *ptr){
delete ptr;}
261 #endif // AVOID_VPSC_H