1/* BEGIN LICENSE BLOCK
2 * Version: CMPL 1.1
3 *
4 * The contents of this file are subject to the Cisco-style Mozilla Public
5 * License Version 1.1 (the "License"); you may not use this file except
6 * in compliance with the License.  You may obtain a copy of the License
7 * at www.eclipse-clp.org/license.
8 *
9 * Software distributed under the License is distributed on an "AS IS"
10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11 * the License for the specific language governing rights and limitations
12 * under the License.
13 *
14 * The Original Code is  The ECLiPSe Constraint Logic Programming System.
15 * The Initial Developer of the Original Code is  Cisco Systems, Inc.
16 * Portions created by the Initial Developer are
17 * Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
18 *
19 * Contributor(s): Kish Shen, CrossCore Optimization.
20 *
21 * END LICENSE BLOCK */
22
23#include <gecode/int.hh>
24#include <gecode/minimodel.hh>
25#include <gecode/search.hh>
26/* not used in Gecode >= 3.6.0
27#include <gecode/graph.hh>
28#include <gecode/scheduling.hh>
29*/
30#include <vector>
31
32#if defined(__APPLE__) && defined(__MACH__)
33/* Mac OS X */
34
35# define VisAtt __attribute__((visibility ("default")))
36
37#else
38
39# define VisAtt
40
41#endif
42
43using namespace Gecode;
44
45class GecodeSpace : public Gecode::MinimizeSpace {
46public:
47    Gecode::IntVarArgs vInt;   // vInt[0] not used, to match ECLiPSe
48    Gecode::BoolVarArgs vBool; // for linked booleans
49    Gecode::BoolVar booltrue;  // true and false constants, for convenience
50    Gecode::BoolVar boolfalse;
51    Gecode::IntVar vCost;      // objective val for min
52
53    GecodeSpace(void) : vInt(*this, 1, 0, 0), vBool(*this, 0, 0, 0),
54			booltrue(*this, 1, 1), boolfalse(*this, 0, 0),
55			vCost(*this, 0, 0),
56			first(true),
57			d_args(NULL),
58			actp(NULL),
59			valid_snapshot(false) {}
60
61    std::vector<int>  dom_snapshot;
62
63    void set_snapshot() {valid_snapshot = true;}
64    void clear_snapshot() {valid_snapshot = false;}
65    bool snapshot_valid() {return valid_snapshot;}
66
67    void stop_caching() {first = false;}
68    void start_caching() {first = true;}
69    bool is_first() {return first;}
70
71    void set_d_args(double* m) {delete d_args; d_args = m;}
72    double get_d_args(int i) const {
73	return ((d_args != NULL) ? d_args[i] : 0.0);
74    }
75
76    // for using activity for var selection in C++
77    bool init_select_activity(IntVarArgs& vars, double decay, IntBranchMerit initf) {
78	if (actp == NULL) {
79	    actp = new IntActivity(*this, vars, decay, initf);
80	    return true;
81	} else
82	    return false;
83    }
84    double get_select_activity(int idx) {
85	return ((actp != NULL) ? (*actp)[idx] : -1);
86    }
87
88  GecodeSpace(bool share, GecodeSpace& s) : vInt(s.vInt.size()), vBool(s.vBool.size()),
89					    valid_snapshot(s.valid_snapshot),
90					    first(true),
91	                                    booltrue(*this, 1, 1), boolfalse(*this, 0, 0),
92					    d_args(NULL),
93					    actp(NULL),
94					    Gecode::MinimizeSpace(share,s) {
95//	valid_snapshot = s.valid_snapshot;
96	if (snapshot_valid()) dom_snapshot = s.dom_snapshot;
97	for (int i=vInt.size(); i--;)
98	  vInt[i].update(*this, share, s.vInt[i]);
99	for (int i=vBool.size(); i--;)
100	  vBool[i].update(*this, share, s.vBool[i]);
101	vCost.update(*this, share, s.vCost);
102	if (s.actp != NULL) actp = new IntActivity(*(s.actp));
103
104  }
105
106    virtual Gecode::MinimizeSpace*
107    copy(bool share) {
108	return new GecodeSpace(share,*this);
109    }
110
111    virtual Gecode::IntVar cost(void)  const {
112	return vCost;
113    }
114
115    ~GecodeSpace(void) {
116	delete d_args;
117	delete actp;
118    }
119
120private:
121    bool valid_snapshot;
122    bool first;  // true if not recomputing
123    double* d_args; // args for passing information for activity calls
124    Gecode::IntActivity* actp; // for using IntActivity outside search engines
125    // change to using vector to lift limit of 1 IntActivity per space
126};
127
128enum SearchMethod {METHOD_COMPLETE,
129		   METHOD_RESTART,
130		   METHOD_CONTINUE_BAB,
131		   METHOD_RESTART_BAB,
132                   METHOD_RESTART_RBAB};
133
134// taken from gecode/driver/script.hpp, by Christian Schulte
135class Cutoff : public Gecode::Search::Stop {
136private:
137    Search::NodeStop* ns; ///< Used node stop object
138    Search::FailStop* fs; ///< Used fail stop object
139    Search::TimeStop* ts; ///< Used time stop object
140    //    Search::MemoryStop* ms; ///< Used memory stop object
141    long stop_reason;
142public:
143    /// Initialize stop object
144    Cutoff(unsigned int node, unsigned int fail, unsigned int time/*, size_t mem*/)
145	: ns((node > 0) ? new Search::NodeStop(node) : NULL),
146	  fs((fail > 0) ? new Search::FailStop(fail) : NULL),
147	  ts((time > 0) ? new Search::TimeStop(time) : NULL),
148	  //  ms((mem  > 0) ? new Search::MemoryStop(mem) : NULL),
149	  stop_reason(0) {}
150    /// Reason why search has been stopped
151    enum {
152	SR_NODE = 1 << 2, ///< Node limit reached
153	SR_FAIL = 1 << 3, ///< Fail limit reached
154	SR_TIME = 1 << 4 ///< Time limit reached
155	//SR_MEM  = 1 << 5  ///< Memory limit reached
156    };
157    /// Test whether search must be stopped
158    virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
159	bool stopping;
160	stopping =
161	    ((ns != NULL) && ns->stop(s,o)) ||
162	    ((fs != NULL) && fs->stop(s,o)) ||
163	    //    ((ms != NULL) && ms->stop(s,o)) ||
164	    ((ts != NULL) && ts->stop(s,o));
165	if (stopping) {
166	    this->stop_reason =
167		(((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
168		(((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
169		//(((ms != NULL) && ms->stop(s,o)) ? SR_MEM  : 0) |
170		(((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0);
171	}
172	return stopping;
173    }
174    /// Report reason why search has been stopped
175    long reason(void) {
176	return this->stop_reason;
177    }
178    /// Reset (currently only for timer)
179    void reset(void) {
180	if (ts != NULL) ts->reset();
181    }
182    /// Destructor
183    ~Cutoff(void) {
184	delete ns; delete fs; delete ts; //delete ms;
185    }
186};
187
188/* based on code from Christian Schulte posted on Gecode mailing list,
189   2013-08-27
190*/
191class GecodeEngineBase {
192public:
193    GecodeEngineBase(void) {}
194    virtual GecodeSpace* next(void) = 0;
195    virtual Search::Statistics statistics(void) const = 0;
196    virtual bool stopped(void) const = 0;
197    virtual ~GecodeEngineBase(void) {}
198};
199
200class GecodeDFS : public GecodeEngineBase {
201protected:
202    DFS<GecodeSpace> e;
203
204public:
205    GecodeDFS(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {}
206    virtual GecodeSpace* next(void) {
207	return e.next();
208    }
209    virtual Search::Statistics statistics(void) const {
210	return e.statistics();
211    }
212    virtual bool stopped(void) const {
213	return e.stopped();
214    }
215    virtual ~GecodeDFS(void) {}
216};
217
218class GecodeBAB : public GecodeEngineBase {
219protected:
220    BAB<GecodeSpace> e;
221
222public:
223    GecodeBAB(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {}
224    virtual GecodeSpace* next(void) {
225	return e.next();
226    }
227    virtual Search::Statistics statistics(void) const {
228	return e.statistics();
229    }
230    virtual bool stopped(void) const {
231	return e.stopped();
232    }
233    virtual ~GecodeBAB(void) {}
234};
235
236template<template<class> class E>
237class GecodeRBS : public GecodeEngineBase {
238protected:
239    RBS<E,GecodeSpace> e;
240
241public:
242    GecodeRBS(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {}
243    virtual GecodeSpace* next(void) {
244	return e.next();
245    }
246    virtual Search::Statistics statistics(void) const {
247	return e.statistics();
248    }
249    virtual bool stopped(void) const {
250	return e.stopped();
251    }
252    virtual ~GecodeRBS(void) {}
253};
254
255
256class GecodeSearch {
257private:
258    GecodeEngineBase* sengine;
259public:
260    SearchMethod method;
261    Cutoff* stopp;
262
263    GecodeSearch(GecodeSpace* solver, Search::Options o, unsigned extra,
264		 Cutoff* cutoffp,
265		 const SearchMethod& m) : stopp(cutoffp), method(m) {
266	switch (m) {
267	case METHOD_COMPLETE:
268	    sengine = new GecodeDFS(solver,o);
269	    break;
270	case METHOD_CONTINUE_BAB:
271	    solver->vCost = solver->vInt[extra];
272	    sengine = new GecodeBAB(solver,o);
273	    break;
274	case METHOD_RESTART_BAB:
275	    solver->vCost = solver->vInt[extra];
276	    o.cutoff = Search::Cutoff::constant(ULONG_MAX);
277	    sengine = new GecodeRBS<BAB>(solver, o);
278	    break;
279	case METHOD_RESTART_RBAB:
280	    // cutoff and nogoods limit set already for o
281	    solver->vCost = solver->vInt[extra];
282	    sengine = new GecodeRBS<BAB>(solver, o);
283	    break;
284	case METHOD_RESTART:
285	    sengine = new GecodeRBS<DFS>(solver, o);
286	    break;
287	    /*
288	default:
289	    printf("Error\n");
290	    break;*/
291	}
292    }
293
294    GecodeSpace* next(void) {
295	//	return static_cast<Gecodeace*>(sengine->next());
296	return sengine->next();
297    }
298
299    Search::Statistics statistics(void) const {
300	return sengine->statistics();
301    }
302
303    bool stopped(void) const {
304	return sengine->stopped();
305    }
306
307    ~GecodeSearch(void) {
308	delete sengine;
309	delete stopp;
310    }
311};
312
313class LDSBSymsStore {
314public:
315
316    std::queue<SymmetryHandle>* symsp; // symmetries
317    std::queue<IntVar*>* intsp;        // dummy IntVars representing integers
318
319    LDSBSymsStore(void) : symsp(new std::queue<SymmetryHandle>()),
320			  intsp(new std::queue<IntVar*>()) {}
321
322    ~LDSBSymsStore(void) {
323	delete symsp;
324	delete intsp;
325    }
326};
327
328
329class VarSelectH {
330public :
331    int* idxs;
332    bool act_inited;
333
334    VarSelectH(void) : idxs(NULL), act_inited(false) {}
335
336    ~VarSelectH(void) {
337	delete idxs;
338    }
339
340};
341
342class Ec2gcException {};
343
344