14 #include "../DdSpec.hpp" 19 class LinearConstraints:
public PodArrayDdSpec<LinearConstraints<T>,T,2> {
46 typedef std::vector<CheckItem> Checklist;
49 std::vector<Checklist> checklists;
55 LinearConstraints(
int n) :
64 void addConstraint(std::map<int,T>
const& expr, T
const& lb, T
const& ub) {
68 for (
typename std::map<int,T>::const_iterator t = expr.begin();
69 t != expr.end(); ++t) {
70 T
const& w = t->second;
72 else if (w < 0) min += w;
74 if (lb <= min && max <= ub)
return;
75 if (ub < lb || max < lb || ub < min) {
79 if (expr.empty())
return;
84 for (
typename std::map<int,T>::const_iterator t = expr.begin();
85 t != expr.end(); ++t) {
86 Checklist& list = checklists[t->first];
87 T
const& w = t->second;
88 list.push_back(CheckItem(constraintId, w, min, max, lb, ub, fc));
90 else if (w < 0) min += w;
97 std::vector<int> indexMap(constraintId);
98 for (
int id = 0;
id < constraintId; ++id) {
101 std::vector<int> freeIndex;
103 for (
int i = n; i >= 1; --i) {
104 Checklist& list = checklists[i];
106 for (
typename Checklist::iterator t = list.begin(); t != list.end();
110 if (indexMap[
id] < 0) {
111 if (freeIndex.empty()) {
112 indexMap[id] = arraySize++;
115 indexMap[id] = freeIndex.back();
116 freeIndex.pop_back();
120 t->index = indexMap[id];
123 for (
typename Checklist::iterator t = list.begin(); t != list.end();
125 if (t->finalChoice) {
126 freeIndex.push_back(t->index);
131 this->setArraySize(arraySize);
134 int getRoot(T* value)
const {
135 if (isFalse)
return 0;
137 for (
int k = 0; k < arraySize; ++k) {
144 int getChild(T* value,
int level,
bool take)
const {
145 Checklist
const& list = checklists[level];
147 for (
typename Checklist::const_iterator t = list.begin();
148 t != list.end(); ++t) {
149 T& v = value[t->index];
150 if (take) v += t->weight;
151 if (v + t->addMax < t->lowerBound || t->upperBound < v + t->addMin)
153 if (t->lowerBound <= v + t->addMin
154 && v + t->addMax <= t->upperBound)
155 v = t->lowerBound - t->addMin;
156 if (t->finalChoice) v = 0;
159 return (--level >= 1) ? level : -1;