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