1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libvpsc - A solver for the problem of Variable Placement with
* Separation Constraints.
*
* 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
*/
/*
* \brief A block is a group of variables that must be moved together to improve
* the goal function without violating already active constraints.
* The variables in a block are spanned by a tree of active constraints.
*/
#ifndef VPSC_BLOCK_H
#define VPSC_BLOCK_H
#include <iostream>
#include <vector>
template <class T, class TCompare> class PairingHeap;
namespace vpsc {
class Variable;
class Constraint;
class CompareConstraints;
class Blocks;
struct PositionStats {
PositionStats() : scale(0), AB(0), AD(0), A2(0) {}
void addVariable(Variable* const v);
double scale;
double AB;
double AD;
double A2;
};
class Block
{
typedef std::vector<Variable*> Variables;
typedef std::vector<Constraint*> Constraints;
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;
PairingHeap<Constraint*,CompareConstraints> *in;
PairingHeap<Constraint*,CompareConstraints> *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(PairingHeap<Constraint*,CompareConstraints>* &h,bool in);
// Parent container, that holds the blockTimeCtr.
Blocks *blocks;
};
}
#endif // VPSC_BLOCK_H
|
