this repo has no description
dekker.one
1/*
2 * Main authors:
3 * Guido Tack <tack@gecode.org>
4 *
5 * Copyright:
6 * Guido Tack, 2006
7 *
8 * This file is part of Gecode, the generic constraint
9 * development environment:
10 * http://www.gecode.org
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining
13 * a copy of this software and associated documentation files (the
14 * "Software"), to deal in the Software without restriction, including
15 * without limitation the rights to use, copy, modify, merge, publish,
16 * distribute, sublicense, and/or sell copies of the Software, and to
17 * permit persons to whom the Software is furnished to do so, subject to
18 * the following conditions:
19 *
20 * The above copyright notice and this permission notice shall be
21 * included in all copies or substantial portions of the Software.
22 *
23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
24 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
26 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
27 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
28 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
29 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 *
31 */
32
33#ifndef GECODE_GIST_HH
34#define GECODE_GIST_HH
35
36#include <gecode/kernel.hh>
37#include <gecode/search.hh>
38#include <gecode/int.hh>
39#ifdef GECODE_HAS_SET_VARS
40#include <gecode/set.hh>
41#endif
42#ifdef GECODE_HAS_FLOAT_VARS
43#include <gecode/float.hh>
44#endif
45
46/*
47 * Configure linking
48 *
49 */
50
51#if !defined(GIST_STATIC_LIBS) && \
52 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
53
54#ifdef GECODE_BUILD_GIST
55#define GECODE_GIST_EXPORT __declspec( dllexport )
56#else
57#define GECODE_GIST_EXPORT __declspec( dllimport )
58#endif
59
60#else
61
62#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
63#define GECODE_GIST_EXPORT __attribute__ ((visibility("default")))
64#else
65#define GECODE_GIST_EXPORT
66#endif
67
68#endif
69
70// Configure auto-linking
71#ifndef GECODE_BUILD_GIST
72#define GECODE_LIBRARY_NAME "Gist"
73#include <gecode/support/auto-link.hpp>
74#endif
75
76#include <string>
77#include <sstream>
78
79namespace Gecode {
80
81 /**
82 * \namespace Gecode::Gist
83 * \brief The %Gecode Interactive %Search Tool
84 *
85 * The Gecode::Gist namespace contains the %Gecode Interactive %Search Tool,
86 * a Qt-based graphical search engine.
87 *
88 */
89 namespace Gist {
90
91 /** \brief Abstract base class for inspectors
92 *
93 * An inspector provides a virtual method that is called
94 * when a node in the search tree is inspected (e.g. by
95 * double-clicking)
96 *
97 * \ingroup TaskGist
98 */
99 class GECODE_GIST_EXPORT Inspector {
100 public:
101 /// Call-back function
102 virtual void inspect(const Space& s) = 0;
103 /// Name of the inspector
104 virtual std::string name(void);
105 /// Clean up when Gist exits
106 virtual void finalize(void);
107 /// Destructor
108 virtual ~Inspector(void);
109 };
110
111 /** \brief Abstract base class for comparators
112 *
113 * A comparator provides a virtual method that is called
114 * when a node in the search tree is compared to another
115 * node.
116 *
117 * \ingroup TaskGist
118 */
119 class GECODE_GIST_EXPORT Comparator {
120 public:
121 //@{
122 ///\name Comparator interface
123
124 /// Call-back function
125 virtual void compare(const Space& s0, const Space& s1) = 0;
126 /// Name of the comparator
127 virtual std::string name(void);
128 /// Clean up when Gist exits
129 virtual void finalize(void);
130 /// Destructor
131 virtual ~Comparator(void);
132
133 //@}
134
135 //@{
136 ///\name Helper methods
137
138 /// Return string representation of difference between arrays \a x and \a y, which are called \a x_n
139 template<class Var>
140 static std::string compare(std::string x_n, const VarArgArray<Var>& x,
141 const VarArgArray<Var>& y);
142 /// Return string representation of difference between \a x and \a y, which are called \a x_n
143 static std::string compare(std::string x_n, IntVar x, IntVar y);
144 /// Return string representation of difference between \a x and \a y, which are called \a x_n
145 static std::string compare(std::string x_n, BoolVar x, BoolVar y);
146#ifdef GECODE_HAS_SET_VARS
147 /// Return string representation of difference between \a x and \a y, which are called \a x_n
148 static std::string compare(std::string x_n, SetVar x, SetVar y);
149#endif
150#ifdef GECODE_HAS_FLOAT_VARS
151 /// Return string representation of difference between \a x and \a y, which are called \a x_n
152 static std::string compare(std::string x_n, FloatVar x, FloatVar y);
153#endif
154 //@}
155 };
156
157 class TextOutputI;
158
159 /// An window for simple text output
160 class GECODE_GIST_EXPORT TextOutput {
161 private:
162 /// The implementation object
163 TextOutputI *t;
164 /// The name of the window
165 std::string n;
166 protected:
167 /// Initialize the implementation object
168 void init(void);
169 /// Get the stream that is used to output text
170 std::ostream& getStream(void);
171 /// Flush stream
172 void flush(void);
173 /// Add html text \a s to the output
174 void addHtml(const char* s);
175 public:
176 /// Constructor
177 TextOutput(const std::string& name);
178 /// Clean up when Gist exits
179 void finalize(void);
180 /// Destructor
181 virtual ~TextOutput(void);
182 /// Name of the inspector
183 virtual std::string name(void);
184 };
185
186 /// An inspector for printing simple text output
187 template<class S>
188 class Print : public TextOutput, public Inspector {
189 public:
190 /// Constructor
191 Print(const std::string& name);
192 /// Use the print method of the template class S to print a space
193 virtual void inspect(const Space& node);
194 /// Return name
195 virtual std::string name(void);
196 /// Clean up when Gist exits
197 virtual void finalize(void);
198 };
199
200 /**
201 * \brief A simple comparator
202 *
203 * This class serves two purposes. First, it provides static methods
204 * that compare two variables or two arrays of variables and return
205 * a string representation of the differences.
206 * Second, it implements a Comparator that uses the compare method of
207 * the script to output the differences between two spaces.
208 *
209 */
210 template<class S>
211 class VarComparator : public TextOutput, public Comparator {
212 public:
213 /// Constructor
214 VarComparator(std::string name);
215 /// Compare \a s0 to \a s1
216 virtual void compare(const Space& s0, const Space& s1);
217 /// Return name
218 virtual std::string name(void);
219 /// Finalize when Gist exits
220 virtual void finalize(void);
221 };
222
223 /// A branching that stops exploration
224 GECODE_GIST_EXPORT
225 void stopBranch(Space& home);
226
227 /**
228 * \brief %Options for %Gist
229 *
230 * Note that the \a d and \a stop fields of the Search::Options class
231 * are not used by Gist.
232 *
233 */
234 class Options : public Search::Options {
235 public:
236 /// Helper class storing inspectors
237 class I_ {
238 private:
239 Support::DynamicArray<Inspector*,Heap> _click;
240 unsigned int n_click;
241 Support::DynamicArray<Inspector*,Heap> _solution;
242 unsigned int n_solution;
243 Support::DynamicArray<Inspector*,Heap> _move;
244 unsigned int n_move;
245 Support::DynamicArray<Comparator*,Heap> _compare;
246 unsigned int n_compare;
247 public:
248 /// Constructor
249 I_(void);
250 /// Add inspector that reacts on node double clicks
251 void click(Inspector* i);
252 /// Add inspector that reacts on each new solution that is found
253 void solution(Inspector* i);
254 /// Add inspector that reacts on each move of the cursor
255 void move(Inspector* i);
256 /// Add comparator
257 void compare(Comparator* c);
258
259 /// Return click inspector number \a i, or nullptr if it does not exist
260 Inspector* click(unsigned int i) const;
261 /// Return solution inspector number \a i, or nullptr if it does not exist
262 Inspector* solution(unsigned int i) const;
263 /// Return move inspector number \a i, or nullptr if it does not exist
264 Inspector* move(unsigned int i) const;
265 /// Return comparator number \a i, or nullptr if it does not exist
266 Comparator* compare(unsigned int i) const;
267 } inspect;
268 /// Default options
269 GECODE_GIST_EXPORT static const Options def;
270 /// Initialize with default values
271 Options(void);
272 };
273
274
275 /// Create a new stand-alone Gist for \a root using \a bab
276 GECODE_GIST_EXPORT int
277 explore(Space* root, bool bab, const Options& opt);
278
279 /**
280 * \brief Create a new stand-alone Gist for \a root
281 * \ingroup TaskGist
282 */
283 int
284 dfs(Space* root, const Gist::Options& opt = Gist::Options::def);
285
286 /**
287 * \brief Create a new stand-alone Gist for branch-and-bound search of \a root
288 * \ingroup TaskGist
289 */
290 int
291 bab(Space* root, const Gist::Options& opt = Gist::Options::def);
292
293 }
294
295}
296
297#include <gecode/gist/gist.hpp>
298
299#endif
300
301// STATISTICS: gist-any