flatzinc.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2007
 *
 *  Last modified:
 *     $Date: 2012-03-21 06:25:08 +0100 (Wed, 21 Mar 2012) $ by $Author: tack $
 *     $Revision: 12605 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#ifndef __GECODE_FLATZINC_HH__
#define __GECODE_FLATZINC_HH__

#include <iostream>

#include <gecode/kernel.hh>
#include <gecode/int.hh>
#ifdef GECODE_HAS_SET_VARS
#include <gecode/set.hh>
#endif

#include <map>

/*
 * Support for DLLs under Windows
 *
 */

#if !defined(GECODE_STATIC_LIBS) && \
    (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))

#ifdef GECODE_BUILD_FLATZINC
#define GECODE_FLATZINC_EXPORT __declspec( dllexport )
#else
#define GECODE_FLATZINC_EXPORT __declspec( dllimport )
#endif

#else

#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY

#define GECODE_FLATZINC_EXPORT __attribute__ ((visibility("default")))

#else

#define GECODE_FLATZINC_EXPORT

#endif
#endif

// Configure auto-linking
#ifndef GECODE_BUILD_FLATZINC
#define GECODE_LIBRARY_NAME "FlatZinc"
#include <gecode/support/auto-link.hpp>
#endif

#include <gecode/driver.hh>

#include <gecode/flatzinc/conexpr.hh>
#include <gecode/flatzinc/ast.hh>
#include <gecode/flatzinc/varspec.hh>

namespace Gecode { namespace FlatZinc {

  class GECODE_FLATZINC_EXPORT Printer {
  private:
    AST::Array* _output;
    void printElem(std::ostream& out,
                   AST::Node* ai,
                   const Gecode::IntVarArray& iv,
                   const Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
                   ,
                   const Gecode::SetVarArray& sv
#endif
                   ) const;
  public:
    Printer(void) : _output(NULL) {}
    void init(AST::Array* output);

    void print(std::ostream& out,
               const Gecode::IntVarArray& iv,
               const Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
               ,
               const Gecode::SetVarArray& sv
#endif
               ) const;
  
    ~Printer(void);
    
    void shrinkElement(AST::Node* node,
                       std::map<int,int>& iv, std::map<int,int>& bv, 
                       std::map<int,int>& sv);

    void shrinkArrays(Space& home,
                      int& optVar,
                      Gecode::IntVarArray& iv,
                      Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
                      ,
                      Gecode::SetVarArray& sv
#endif
                     );
    
  private:
    Printer(const Printer&);
    Printer& operator=(const Printer&);
  };

  class FlatZincOptions : public Gecode::BaseOptions {
  protected:

      Gecode::Driver::UnsignedIntOption _solutions; 
      Gecode::Driver::BoolOption        _allSolutions; 
      Gecode::Driver::DoubleOption      _threads;   
      Gecode::Driver::BoolOption        _free; 
      Gecode::Driver::StringOption      _search; 
      Gecode::Driver::UnsignedIntOption _c_d;       
      Gecode::Driver::UnsignedIntOption _a_d;       
      Gecode::Driver::UnsignedIntOption _node;      
      Gecode::Driver::UnsignedIntOption _fail;      
      Gecode::Driver::UnsignedIntOption _time;      
      Gecode::Driver::IntOption         _seed;      

    

      Gecode::Driver::StringOption      _mode;       
      Gecode::Driver::BoolOption        _stat;       
      Gecode::Driver::StringValueOption _output;     

  public:
    enum SearchOptions {
      FZ_SEARCH_BAB,    //< Branch-and-bound search
      FZ_SEARCH_RESTART //< Restart search
    };
    FlatZincOptions(const char* s)
    : Gecode::BaseOptions(s),
      _solutions("-n","number of solutions (0 = all)",1),
      _allSolutions("-a", "return all solutions (equal to -solutions 0)"),
      _threads("-p","number of threads (0 = #processing units)",
               Gecode::Search::Config::threads),
      _free("--free", "no need to follow search-specification"),
      _search("-search","search engine variant", FZ_SEARCH_BAB),
      _c_d("-c-d","recomputation commit distance",Gecode::Search::Config::c_d),
      _a_d("-a-d","recomputation adaption distance",Gecode::Search::Config::a_d),
      _node("-node","node cutoff (0 = none, solution mode)"),
      _fail("-fail","failure cutoff (0 = none, solution mode)"),
      _time("-time","time (in ms) cutoff (0 = none, solution mode)"),
      _seed("-r","random seed",0),
      _mode("-mode","how to execute script",Gecode::SM_SOLUTION),
      _stat("-s","emit statistics"),
      _output("-o","file to send output to") {

      _search.add(FZ_SEARCH_BAB, "bab");
      _search.add(FZ_SEARCH_RESTART, "restart");
      _mode.add(Gecode::SM_SOLUTION, "solution");
      _mode.add(Gecode::SM_STAT, "stat");
      _mode.add(Gecode::SM_GIST, "gist");
      add(_solutions); add(_threads); add(_c_d); add(_a_d);
      add(_allSolutions);
      add(_free);
      add(_search);
      add(_node); add(_fail); add(_time);
      add(_seed);
      add(_mode); add(_stat);
      add(_output);
    }

    void parse(int& argc, char* argv[]) {
      Gecode::BaseOptions::parse(argc,argv);
      if (_allSolutions.value()) {
        _solutions.value(0);
      }
      if (_stat.value())
        _mode.value(Gecode::SM_STAT);
    }
  
    virtual void help(void) {
      std::cerr << "Gecode FlatZinc interpreter" << std::endl
                << " - Supported FlatZinc version: " << GECODE_FLATZINC_VERSION
                << std::endl << std::endl;
      Gecode::BaseOptions::help();
    }
  
    unsigned int solutions(void) const { return _solutions.value(); }
    bool allSolutions(void) const { return _allSolutions.value(); }
    double threads(void) const { return _threads.value(); }
    bool free(void) const { return _free.value(); }
    SearchOptions search(void) const {
      return static_cast<SearchOptions>(_search.value());
    }
    unsigned int c_d(void) const { return _c_d.value(); }
    unsigned int a_d(void) const { return _a_d.value(); }
    unsigned int node(void) const { return _node.value(); }
    unsigned int fail(void) const { return _fail.value(); }
    unsigned int time(void) const { return _time.value(); }
    int seed(void) const { return _seed.value(); }
    const char* output(void) const { return _output.value(); }
    Gecode::ScriptMode mode(void) const {
      return static_cast<Gecode::ScriptMode>(_mode.value());
    }
  };

  class GECODE_FLATZINC_EXPORT FlatZincSpace : public Space {
  public:
    enum Meth {
      SAT, //< Solve as satisfaction problem
      MIN, //< Solve as minimization problem
      MAX  //< Solve as maximization problem
    };
  protected:
    int intVarCount;
    int boolVarCount;
    int setVarCount;

    int _optVar;
  
    Meth _method;
    
    AST::Array* _solveAnnotations;

    FlatZincSpace(bool share, FlatZincSpace&);
  private:
    template<template<class> class Engine>
    void
    runEngine(std::ostream& out, const Printer& p, 
              const FlatZincOptions& opt, Gecode::Support::Timer& t_total);
    void
    branchWithPlugin(AST::Node* ann);
  public:
    Gecode::IntVarArray iv;
    std::vector<bool> iv_introduced;
    int* iv_boolalias;
    Gecode::BoolVarArray bv;
    std::vector<bool> bv_introduced;
#ifdef GECODE_HAS_SET_VARS

    Gecode::SetVarArray sv;
    std::vector<bool> sv_introduced;
#endif

    FlatZincSpace(void);
  
    ~FlatZincSpace(void);
  
    void init(int intVars, int boolVars, int setVars);

    void newIntVar(IntVarSpec* vs);
    void aliasBool2Int(int iv, int bv);
    int aliasBool2Int(int iv);
    void newBoolVar(BoolVarSpec* vs);
    void newSetVar(SetVarSpec* vs);
  
    void postConstraint(const ConExpr& ce, AST::Node* annotation);
  
    void solve(AST::Array* annotation);
    void minimize(int var, AST::Array* annotation);
    void maximize(int var, AST::Array* annotation);

    void run(std::ostream& out, const Printer& p, 
             const FlatZincOptions& opt, Gecode::Support::Timer& t_total);
  
    void print(std::ostream& out, const Printer& p) const;

    void shrinkArrays(Printer& p);

    Meth method(void) const;

    int optVar(void) const;

    void createBranchers(AST::Node* ann,
                         int seed,
                         bool ignoreUnknown,
                         std::ostream& err = std::cerr);

    AST::Array* solveAnnotations(void) const;

    virtual void constrain(const Space& s);
    virtual Gecode::Space* copy(bool share);
  };

  class Error {
  private:
    const std::string msg;
  public:
    Error(const std::string& where, const std::string& what)
    : msg(where+": "+what) {}
    const std::string& toString(void) const { return msg; }
  };

  GECODE_FLATZINC_EXPORT
  FlatZincSpace* parse(const std::string& fileName,
                       Printer& p, std::ostream& err = std::cerr,
                       FlatZincSpace* fzs=NULL);

  GECODE_FLATZINC_EXPORT
  FlatZincSpace* parse(std::istream& is,
                       Printer& p, std::ostream& err = std::cerr,
                       FlatZincSpace* fzs=NULL);

}}

#endif

// STATISTICS: flatzinc-any