1 /**
2 * \brief A block is a group of variables that must be moved together to improve
3 * the goal function without violating already active constraints.
4 * The variables in a block are spanned by a tree of active constraints.
5 *
6 * Authors:
7 * Tim Dwyer <tgdwyer@gmail.com>
8 *
9 * Copyright (C) 2005 Authors
10 *
11 * Released under GNU LGPL. Read the file 'COPYING' for more information.
12 */
14 #ifndef SEEN_REMOVEOVERLAP_BLOCK_H
15 #define SEEN_REMOVEOVERLAP_BLOCK_H
17 #include <vector>
18 #include <iostream>
19 template <class T> class PairingHeap;
20 namespace vpsc {
21 class Variable;
22 class Constraint;
24 class Block
25 {
26 typedef std::vector<Variable*> Variables;
27 typedef std::vector<Constraint*>::iterator Cit;
28 typedef std::vector<Variable*>::iterator Vit;
30 friend std::ostream& operator <<(std::ostream &os,const Block &b);
31 public:
32 Variables *vars;
33 double posn;
34 double weight;
35 double wposn;
36 Block(Variable* const v=NULL);
37 virtual ~Block(void);
38 Constraint* findMinLM();
39 Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
40 Constraint* findMinInConstraint();
41 Constraint* findMinOutConstraint();
42 void deleteMinInConstraint();
43 void deleteMinOutConstraint();
44 double desiredWeightedPosition();
45 void merge(Block *b, Constraint *c, double dist);
46 void merge(Block *b, Constraint *c);
47 void mergeIn(Block *b);
48 void mergeOut(Block *b);
49 void split(Block *&l, Block *&r, Constraint *c);
50 Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
51 void setUpInConstraints();
52 void setUpOutConstraints();
53 double cost();
54 bool deleted;
55 long timeStamp;
56 PairingHeap<Constraint*> *in;
57 PairingHeap<Constraint*> *out;
58 bool isActiveDirectedPathBetween(Variable* u, Variable *v);
59 private:
60 typedef enum {NONE, LEFT, RIGHT} Direction;
61 typedef std::pair<double, Constraint*> Pair;
62 void reset_active_lm(Variable* const v, Variable* const u);
63 double compute_dfdv(Variable* const v, Variable* const u,
64 Constraint *&min_lm);
65 Pair compute_dfdv_between(
66 Variable*, Variable* const, Variable* const,
67 const Direction, bool);
68 bool canFollowLeft(Constraint *c, const Variable* const last);
69 bool canFollowRight(Constraint *c, const Variable* const last);
70 void populateSplitBlock(Block *b, Variable* const v, Variable* const u);
71 void addVariable(Variable* const v);
72 void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
73 };
75 }
76 #endif // SEEN_REMOVEOVERLAP_BLOCK_H