this repo has no description
dekker.one
1/**** , [ Worker.cc ],
2 Copyright (c) 2010 Universite de Caen Basse Normandie- Jeremie Vautard
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 *************************************************************************/
22
23#include "Worker.hh"
24
25
26inline vector<int> getTheValues(MySpace* sol,int vmin,int vmax){
27 vector<int> zevalues;
28// cout<<sol<<" "<<vmin<<" "<<vmax<<endl;
29 if (vmax > (sol->nbVars())) cout<<"getTheValues mal appele"<<endl;
30 for (int i = vmin; i<=vmax;i++) {
31 // cout<<i<<" ";
32 // cout.flush();
33 switch (sol->type_of_v[i]) {
34 case VTYPE_INT :
35 zevalues.push_back( (static_cast<IntVar*>(sol->v[i]))->val() );
36 break;
37 case VTYPE_BOOL :
38 zevalues.push_back( (static_cast<BoolVar*>(sol->v[i]))->val() );
39 break;
40 default :
41 cout<<"4Unknown variable type"<<endl;
42 abort();
43 }
44 }
45// cout<<endl;
46
47 return zevalues;
48}
49
50
51QWorker::~QWorker() {
52 // cout<<"Destroying "<<this<<endl;
53}
54
55void QWorker::stopAndReturn() {
56 access.acquire();
57 if (stopandforget < 1) stopandforget=1;
58 access.release();
59}
60
61void QWorker::stopAndForget() {
62 access.acquire();
63 if (stopandforget < 2) stopandforget=2;
64 access.release();
65}
66
67bool QWorker::mustStop() {
68 return (stopandforget > 0);
69}
70
71void QWorker::wake() {
72 // cout<<"Awaking "<<this<<endl;
73 goToWork.signal();
74}
75
76vector<int> QWorker::workPosition() {
77 // access.acquire();
78 // vector<int> ret = currentWork.root();
79 // access.release();
80 return currentWork.root();
81}
82
83void QWorker::run() {
84
85 while(true) {
86 access.acquire();
87 stopandforget=0;
88 finished=false;
89 todo.clear();
90 access.release();
91 // cout<<"QWorker "<<this<<" : One turn !"<<endl;
92 QWork cur= wm->getWork(this);
93 // cout<<"QWorker "<<this<<" got work"<<endl;
94 if (cur.isStop()) {
95 return;
96 }
97 else if (cur.isWait()) {
98 // clock_t start = clock();
99 // cout<<this<<" WAIT goToWork "<<start<<endl;
100 goToWork.wait();
101 // clock_t stop = clock();
102 // cout<<this<<" CONT goToWork "<<stop<<" waited "<<(stop-start)<<endl;
103 }
104 else {
105 access.acquire();
106 currentWork = cur;
107 access.release();
108 Strategy ret=solve();
109 access.acquire();
110 bool forget= (stopandforget == 2);
111 access.release();
112 if (!forget) {
113 // cout<<"QWorker "<<this<<" returning work..."<<ret.nbTodos()<<" todo in strategy and "<<todo.size()<<" works to do."<<endl;
114 wm->returnWork(this,ret,todo,cur.root());
115 }
116 else {
117 // cout<<"QWorker "<<this<<" forgetting work..."<<endl;
118
119 for(list<QWork>::iterator i(todo.begin());i != todo.end();i++) {
120 (*i).clean();
121 }
122 todo.clear();
123 }
124 }
125 }
126}
127
128Strategy QWorker::solve() {
129 return rsolve(currentWork.getScope(),currentWork.getRemaining());
130}
131
132
133Strategy QWorker::rsolve(int scope,/*vector<int> assignments,*/Engine* L) {
134 access.acquire();
135 bool forget = (stopandforget==2);
136 access.release();
137 if (forget) {
138 delete L;
139 return Strategy::Dummy();
140 }
141
142 MySpace* sol = static_cast<MySpace*>(L->next());
143 Strategy ret=Strategy::Dummy();
144 bool LwasEmpty = true;
145
146
147 while ((sol != NULL) ) {
148 LwasEmpty=false;
149 vector<int> assignments = getTheValues(sol,0,sol->nbVars()-1);
150 Strategy result;
151
152 if (scope == (problem->spaces() - 1) ) { // last scope reached. Verify the goal...
153 MySpace* g = problem->getGoal();
154 for (int i=0;i<g->nbVars();i++) {
155 switch (g->type_of_v[i]) {
156 case VTYPE_INT :
157 rel(*g,*(static_cast<IntVar*>(g->v[i])) == assignments[i]);
158 break;
159 case VTYPE_BOOL :
160 rel(*g,*(static_cast<BoolVar*>(g->v[i])) == assignments[i]);
161 break;
162 default :
163 cout<<"Unknown variable type"<<endl;
164 abort();
165 }
166 }
167 Gecode::DFS<MySpace> solutions(g);
168 MySpace* goalsol = solutions.next();
169 if (goalsol == NULL) {
170 delete g;
171 delete L;
172 result = Strategy::SFalse();
173 }
174 else {
175 int vmin = ( (scope==0)? 0 : (problem->nbVarInScope(scope-1)) );
176 int vmax = (problem->nbVarInScope(scope))-1;
177 vector<int> zevalues=getTheValues(sol,vmin,vmax);
178 result=Strategy(problem->quantification(scope),vmin,vmax,scope,zevalues);
179 result.attach(Strategy::STrue());
180 delete g;
181 // delete sol;
182 delete goalsol;
183 }
184 }
185
186 else { // This is not the last scope...
187 MySpace* espace = problem->getSpace(scope+1);
188 for (int i=0;i<assignments.size();i++) {
189 switch (espace->type_of_v[i]) {
190 case VTYPE_INT :
191 rel(*espace,*(static_cast<IntVar*>(espace->v[i])) == assignments[i]);
192 break;
193 case VTYPE_BOOL :
194 rel(*espace,*(static_cast<BoolVar*>(espace->v[i])) == assignments[i]);
195 break;
196 default :
197 cout<<"Unknown variable type"<<endl;
198 abort();
199 }
200 }
201 Options o;
202 Engine* solutions = new WorkerToEngine<Gecode::Search::Sequential::DFS>(espace,/*sizeof(MySpace),*/o);
203 delete espace;
204
205 access.acquire();
206 forget=(stopandforget == 2);
207 bool stop=(stopandforget==1);
208 access.release();
209 if (forget) {
210 delete sol;
211 delete solutions;
212 return Strategy::Dummy();
213 }
214 if (stop) {
215 vector<int> root1;
216 if (scope!=0) {root1= getTheValues(sol,0,problem->nbVarInScope(scope-1)-1);}
217 QWork current(scope,root1,L);
218 vector<int> root2 = getTheValues(sol,0,problem->nbVarInScope(scope)-1);
219 QWork onemore(scope+1,root2,solutions);
220 todo.push_back(current);
221 todo.push_back(onemore);
222 int vmin = ( (scope==0)? 0 : (problem->nbVarInScope(scope-1)) );
223 int vmax = (problem->nbVarInScope(scope))-1;
224 vector<int> zevalues=getTheValues(sol,vmin,vmax);
225 Strategy toAttach(problem->quantification(scope),vmin,vmax,scope,zevalues);
226 toAttach.attach(Strategy::Stodo());
227 ret.attach(toAttach);
228 ret.attach(Strategy::Stodo());
229 return ret;
230 }
231
232 result=rsolve(scope+1,solutions);
233 }
234
235 int vmin = ( (scope == 0) ? 0 : (problem->nbVarInScope(scope-1)) );
236 int vmax = (problem->nbVarInScope(scope))-1;
237 vector<int> zevalues=getTheValues(sol,vmin,vmax);
238 delete sol;
239 access.acquire();
240 forget=(stopandforget == 2);
241 access.release();
242 if (forget) {
243 delete L;
244 return Strategy::Dummy();
245 }
246 if (problem->quantification(scope)) { // current scope is universal
247 if (result.isFalse()) // one branch fails
248 {
249 delete L;
250 return Strategy::SFalse();
251 }
252 else {
253 Strategy toAttach(true,vmin,vmax,scope,zevalues);
254
255 toAttach.attach(result);
256 ret.attach(toAttach);
257 }
258 }
259 else { //current scope is existential
260 if (!result.isFalse()) { // result not the truivilally false strategy...
261 if (result.isComplete()) { // ...and has no todo nodes. So...
262 ret = Strategy(problem->quantification(scope),vmin,vmax,scope,zevalues);
263 ret.attach(result);
264 delete L;
265 return ret; // we return it immediately
266 }
267 else { // If result is not false, but still has todo nodes...
268 Strategy toAttach(problem->quantification(scope),vmin,vmax,scope,zevalues);
269 toAttach.attach(result); // the node corresponding to the current scope iis added...
270 ret.attach(toAttach); // and the corresponding strategy is attached to a Dummy node. Next loop in the outer while will need it...
271 }
272 }
273 }
274 sol = static_cast<MySpace*>(L->next());
275 }
276 delete L;
277 if (problem->quantification(scope)) //universal scope
278 return (LwasEmpty ? Strategy::STrue() : ret);
279 else {
280 if (ret.isComplete())
281 return Strategy::SFalse();
282 else
283 return ret;
284 }
285}