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
|
#ifndef FIXPOINT_ALGORITHM_HPP
#define FIXPOINT_ALGORITHM_HPP
#include "VariableAssignment.hpp"
template<typename T>
struct EquationSystem;
template<typename T>
struct MaxStrategy;
template<typename T>
struct FixpointAlgorithm {
virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>&, const EquationSystem<T>&) const = 0;
};
#include "EquationSystem.hpp"
#include "MaxStrategy.hpp"
template<typename T>
struct NaiveFixpoint : public FixpointAlgorithm<T> {
virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
unsigned int size = system.varCount();
VariableAssignment<T> newResult(size, infinity<T>());
VariableAssignment<T> result(0);
do {
result = newResult;
newResult = strat(system, result);
} while (newResult != result);
return result;
}
};
template<typename T>
struct RecursiveFixpoint : public FixpointAlgorithm<T> {
// this is a "VariableAssignment" which actually performs a recursive
// call to determine what value to return
struct EvaluatingVariableAssignment : public VariableAssignment<T> {
EvaluatingVariableAssignment(const MaxStrategy<T>& strategy, const EquationSystem<T>& system)
: VariableAssignment<T>(system.varCount(), infinity<T>()),
_strategy(strategy), _system(system),
_evaluating(NULL),
_influence(system.varCount(), IdSet<Variable<T> >(system.varCount())),
_stable(system.varCount()) {
}
virtual T& operator[] (const Variable<T>& x) const {
if (_evaluating == NULL) {
solve(x);
return VariableAssignment<T>::_assignment[x.id()];
} else {
solve(x);
_influence[x].insert(*_evaluating);
return VariableAssignment<T>::_assignment[x.id()];
}
}
void solve(const Variable<T>& x) const {
if (!_stable.contains(x)) {
_stable.insert(x);
const Variable<T>* oldEval = _evaluating;
_evaluating = &x;
T t = _strategy(*_system[x], *this);
_evaluating = oldEval;
if (t != VariableAssignment<T>::_assignment[x.id()]) {
IdSet<Variable<T> > oldInfluence = _influence[x];
_influence[x].clear(); // clear out our idea of what x influences
VariableAssignment<T>::_assignment[x.id()] = t;
_stable.filter(oldInfluence); // whatever x influences needs to be re-evaluated
for (typename IdSet<Variable<T> >::iterator it = oldInfluence.begin();
it != oldInfluence.end();
++it) {
solve(*_system.getVar(*it));
}
}
}
}
private:
const MaxStrategy<T>& _strategy;
const EquationSystem<T>& _system;
mutable const Variable<T>* _evaluating;
mutable IdMap<Variable<T>, IdSet<Variable<T> > > _influence;
mutable IdSet<Variable<T> > _stable;
};
virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
EvaluatingVariableAssignment assignment(strat, system);
VariableAssignment<T> result(system.varCount());
for (unsigned int i = 0; i < system.varCount(); ++i) {
result[*system.getVar(i)] = assignment[*system.getVar(i)];
}
return result;
}
};
#endif
|
