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 
79 namespace 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
302