Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
flatzinc.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Contributing authors:
7  * Gabriel Hjort Blindell <gabriel.hjort.blindell@gmail.com>
8  *
9  * Copyright:
10  * Guido Tack, 2007-2012
11  * Gabriel Hjort Blindell, 2012
12  *
13  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/flatzinc.hh>
46 
47 #include <gecode/search.hh>
48 
49 #include <vector>
50 #include <string>
51 #include <sstream>
52 #include <limits>
53 #include <unordered_set>
54 
55 
56 namespace std {
57 
59  template<> struct hash<Gecode::TupleSet> {
61  forceinline size_t
62  operator()(const Gecode::TupleSet& x) const {
63  return x.hash();
64  }
65  };
66 
68  template<> struct hash<Gecode::SharedArray<int> > {
70  forceinline size_t
72  size_t seed = static_cast<size_t>(x.size());
73  for (int i=x.size(); i--; )
74  Gecode::cmb_hash(seed, x[i]);
75  return seed;
76  }
77  };
78 
80  template<> struct hash<Gecode::DFA> {
82  forceinline size_t operator()(const Gecode::DFA& d) const {
83  return d.hash();
84  }
85  };
86 
87 }
88 
89 namespace Gecode { namespace FlatZinc {
90 
91  // Unitialized default random number generator
93 
106  class AuxVarBrancher : public Brancher {
107  protected:
109  bool done;
112  IntValBranch int_valsel0,
113  TieBreak<BoolVarBranch> bool_varsel0,
114  BoolValBranch bool_valsel0
115 #ifdef GECODE_HAS_SET_VARS
116  ,
117  SetVarBranch set_varsel0,
118  SetValBranch set_valsel0
119 #endif
121  ,
122  TieBreak<FloatVarBranch> float_varsel0,
123  FloatValBranch float_valsel0
124 #endif
125  )
126  : Brancher(home), done(false),
127  int_varsel(int_varsel0), int_valsel(int_valsel0),
128  bool_varsel(bool_varsel0), bool_valsel(bool_valsel0)
129 #ifdef GECODE_HAS_SET_VARS
130  , set_varsel(set_varsel0), set_valsel(set_valsel0)
131 #endif
132 #ifdef GECODE_HAS_FLOAT_VARS
133  , float_varsel(float_varsel0), float_valsel(float_valsel0)
134 #endif
135  {}
138  : Brancher(home, b), done(b.done) {}
139 
141  class Choice : public Gecode::Choice {
142  public:
144  bool fail;
146  Choice(const Brancher& b, bool fail0)
147  : Gecode::Choice(b,1), fail(fail0) {}
149  virtual size_t size(void) const {
150  return sizeof(Choice);
151  }
153  virtual void archive(Archive& e) const {
155  e.put(fail);
156  }
157  };
158 
163 #ifdef GECODE_HAS_SET_VARS
166 #endif
167 #ifdef GECODE_HAS_FLOAT_VARS
170 #endif
171 
172  public:
174  virtual bool status(const Space& _home) const {
175  if (done) return false;
176  const FlatZincSpace& home = static_cast<const FlatZincSpace&>(_home);
177  for (int i=0; i<home.iv_aux.size(); i++)
178  if (!home.iv_aux[i].assigned()) return true;
179  for (int i=0; i<home.bv_aux.size(); i++)
180  if (!home.bv_aux[i].assigned()) return true;
181 #ifdef GECODE_HAS_SET_VARS
182  for (int i=0; i<home.sv_aux.size(); i++)
183  if (!home.sv_aux[i].assigned()) return true;
184 #endif
185 #ifdef GECODE_HAS_FLOAT_VARS
186  for (int i=0; i<home.fv_aux.size(); i++)
187  if (!home.fv_aux[i].assigned()) return true;
188 #endif
189  // No non-assigned variables left
190  return false;
191  }
193  virtual Choice* choice(Space& home) {
194  done = true;
195  FlatZincSpace& fzs = static_cast<FlatZincSpace&>(*home.clone());
196  fzs.needAuxVars = false;
197  branch(fzs,fzs.iv_aux,int_varsel,int_valsel);
198  branch(fzs,fzs.bv_aux,bool_varsel,bool_valsel);
199 #ifdef GECODE_HAS_SET_VARS
200  branch(fzs,fzs.sv_aux,set_varsel,set_valsel);
201 #endif
202 #ifdef GECODE_HAS_FLOAT_VARS
203  branch(fzs,fzs.fv_aux,float_varsel,float_valsel);
204 #endif
205  Search::Options opt; opt.clone = false;
206  FlatZincSpace* sol = dfs(&fzs, opt);
207  if (sol) {
208  delete sol;
209  return new Choice(*this,false);
210  } else {
211  return new Choice(*this,true);
212  }
213  }
215  virtual Choice* choice(const Space&, Archive& e) {
216  bool fail; e >> fail;
217  return new Choice(*this, fail);
218  }
220  virtual ExecStatus commit(Space&, const Gecode::Choice& c, unsigned int) {
221  return static_cast<const Choice&>(c).fail ? ES_FAILED : ES_OK;
222  }
224  virtual void print(const Space&, const Gecode::Choice& c,
225  unsigned int,
226  std::ostream& o) const {
227  o << "FlatZinc("
228  << (static_cast<const Choice&>(c).fail ? "fail" : "ok")
229  << ")";
230  }
232  virtual Actor* copy(Space& home) {
233  return new (home) AuxVarBrancher(home, *this);
234  }
236  static void post(Home home,
237  TieBreak<IntVarBranch> int_varsel,
238  IntValBranch int_valsel,
239  TieBreak<BoolVarBranch> bool_varsel,
240  BoolValBranch bool_valsel
241 #ifdef GECODE_HAS_SET_VARS
242  ,
243  SetVarBranch set_varsel,
244  SetValBranch set_valsel
245 #endif
247  ,
248  TieBreak<FloatVarBranch> float_varsel,
249  FloatValBranch float_valsel
250 #endif
251  ) {
252  (void) new (home) AuxVarBrancher(home, int_varsel, int_valsel,
253  bool_varsel, bool_valsel
254 #ifdef GECODE_HAS_SET_VARS
255  , set_varsel, set_valsel
256 #endif
257 #ifdef GECODE_HAS_FLOAT_VARS
258  , float_varsel, float_valsel
259 #endif
260  );
261  }
263  virtual size_t dispose(Space&) {
264  return sizeof(*this);
265  }
266  };
267 
269  private:
270  struct BI {
271  std::string r0;
272  std::string r1;
273  std::vector<std::string> n;
274  BI(void) : r0(""), r1(""), n(0) {}
275  BI(const std::string& r00, const std::string& r10,
276  const std::vector<std::string>& n0)
277  : r0(r00), r1(r10), n(n0) {}
278  };
279  std::vector<BI> v;
280  BranchInformationO(std::vector<BI> v0) : v(v0) {}
281  public:
283  virtual ~BranchInformationO(void) {}
284  virtual SharedHandle::Object* copy(void) const {
285  return new BranchInformationO(v);
286  }
289  const std::string& rel0,
290  const std::string& rel1,
291  const std::vector<std::string>& n) {
292  v.resize(std::max(static_cast<unsigned int>(v.size()),bg.id()+1));
293  v[bg.id()] = BI(rel0,rel1,n);
294  }
296  void print(const Brancher& b,
297  unsigned int a, int i, int n, std::ostream& o) const {
298  const BI& bi = v[b.group().id()];
299  o << bi.n[i] << " " << (a==0 ? bi.r0 : bi.r1) << " " << n;
300  }
301 #ifdef GECODE_HAS_FLOAT_VARS
302  void print(const Brancher& b,
303  unsigned int a, int i, const FloatNumBranch& nl,
304  std::ostream& o) const {
305  const BI& bi = v[b.group().id()];
306  o << bi.n[i] << " "
307  << (((a == 0) == nl.l) ? "<=" : ">=") << nl.n;
308  }
309 #endif
310  };
311 
312  BranchInformation::BranchInformation(void)
313  : SharedHandle(NULL) {}
314 
316  : SharedHandle(bi) {}
317 
318  void
320  assert(object() == NULL);
321  object(new BranchInformationO());
322  }
323 
324  void
326  const std::string& rel0,
327  const std::string& rel1,
328  const std::vector<std::string>& n) {
329  static_cast<BranchInformationO*>(object())->add(bg,rel0,rel1,n);
330  }
331  void
332  BranchInformation::print(const Brancher& b, unsigned int a, int i,
333  int n, std::ostream& o) const {
334  static_cast<const BranchInformationO*>(object())->print(b,a,i,n,o);
335  }
336 #ifdef GECODE_HAS_FLOAT_VARS
337  void
338  BranchInformation::print(const Brancher& b, unsigned int a, int i,
339  const FloatNumBranch& nl, std::ostream& o) const {
340  static_cast<const BranchInformationO*>(object())->print(b,a,i,nl,o);
341  }
342 #endif
343  template<class Var>
344  void varValPrint(const Space &home, const Brancher& b,
345  unsigned int a,
346  Var, int i, const int& n,
347  std::ostream& o) {
348  static_cast<const FlatZincSpace&>(home).branchInfo.print(b,a,i,n,o);
349  }
350 
351 #ifdef GECODE_HAS_FLOAT_VARS
352  void varValPrintF(const Space &home, const Brancher& b,
353  unsigned int a,
354  FloatVar, int i, const FloatNumBranch& nl,
355  std::ostream& o) {
356  static_cast<const FlatZincSpace&>(home).branchInfo.print(b,a,i,nl,o);
357  }
358 #endif
359 
361  if (vs->assigned) {
362  return IntSet(vs->i,vs->i);
363  }
364  if (vs->domain()) {
365  AST::SetLit* sl = vs->domain.some();
366  if (sl->interval) {
367  return IntSet(sl->min, sl->max);
368  } else {
369  int* newdom = heap.alloc<int>(static_cast<unsigned long int>(sl->s.size()));
370  for (int i=sl->s.size(); i--;)
371  newdom[i] = sl->s[i];
372  IntSet ret(newdom, sl->s.size());
373  heap.free(newdom, static_cast<unsigned long int>(sl->s.size()));
374  return ret;
375  }
376  }
378  }
379 
380  int vs2bsl(BoolVarSpec* bs) {
381  if (bs->assigned) {
382  return bs->i;
383  }
384  if (bs->domain()) {
385  AST::SetLit* sl = bs->domain.some();
386  assert(sl->interval);
387  return std::min(1, std::max(0, sl->min));
388  }
389  return 0;
390  }
391 
392  int vs2bsh(BoolVarSpec* bs) {
393  if (bs->assigned) {
394  return bs->i;
395  }
396  if (bs->domain()) {
397  AST::SetLit* sl = bs->domain.some();
398  assert(sl->interval);
399  return std::max(0, std::min(1, sl->max));
400  }
401  return 1;
402  }
403 
404  TieBreak<IntVarBranch> ann2ivarsel(AST::Node* ann, Rnd rnd, double decay) {
405  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
406  if (s->id == "input_order")
408  if (s->id == "first_fail")
410  if (s->id == "anti_first_fail")
412  if (s->id == "smallest")
414  if (s->id == "largest")
416  if (s->id == "occurrence")
418  if (s->id == "max_regret")
420  if (s->id == "most_constrained")
423  if (s->id == "random") {
424  return TieBreak<IntVarBranch>(INT_VAR_RND(rnd));
425  }
426  if (s->id == "dom_w_deg") {
428  }
429  if (s->id == "afc_min")
431  if (s->id == "afc_max")
433  if (s->id == "afc_size_min")
435  if (s->id == "afc_size_max") {
437  }
438  if (s->id == "action_min")
440  if (s->id == "action_max")
442  if (s->id == "action_size_min")
444  if (s->id == "action_size_max")
446  }
447  std::cerr << "Warning, ignored search annotation: ";
448  ann->print(std::cerr);
449  std::cerr << std::endl;
451  }
452 
453  IntValBranch ann2ivalsel(AST::Node* ann, std::string& r0, std::string& r1,
454  Rnd rnd) {
455  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
456  if (s->id == "indomain_min") {
457  r0 = "="; r1 = "!=";
458  return INT_VAL_MIN();
459  }
460  if (s->id == "indomain_max") {
461  r0 = "="; r1 = "!=";
462  return INT_VAL_MAX();
463  }
464  if (s->id == "indomain_median") {
465  r0 = "="; r1 = "!=";
466  return INT_VAL_MED();
467  }
468  if (s->id == "indomain_split") {
469  r0 = "<="; r1 = ">";
470  return INT_VAL_SPLIT_MIN();
471  }
472  if (s->id == "indomain_reverse_split") {
473  r0 = ">"; r1 = "<=";
474  return INT_VAL_SPLIT_MAX();
475  }
476  if (s->id == "indomain_random") {
477  r0 = "="; r1 = "!=";
478  return INT_VAL_RND(rnd);
479  }
480  if (s->id == "indomain") {
481  r0 = "="; r1 = "=";
482  return INT_VALUES_MIN();
483  }
484  if (s->id == "indomain_middle") {
485  std::cerr << "Warning, replacing unsupported annotation "
486  << "indomain_middle with indomain_median" << std::endl;
487  r0 = "="; r1 = "!=";
488  return INT_VAL_MED();
489  }
490  if (s->id == "indomain_interval") {
491  std::cerr << "Warning, replacing unsupported annotation "
492  << "indomain_interval with indomain_split" << std::endl;
493  r0 = "<="; r1 = ">";
494  return INT_VAL_SPLIT_MIN();
495  }
496  }
497  std::cerr << "Warning, ignored search annotation: ";
498  ann->print(std::cerr);
499  std::cerr << std::endl;
500  r0 = "="; r1 = "!=";
501  return INT_VAL_MIN();
502  }
503 
505  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
506  if (s->id == "indomain_min")
507  return INT_ASSIGN_MIN();
508  if (s->id == "indomain_max")
509  return INT_ASSIGN_MAX();
510  if (s->id == "indomain_median")
511  return INT_ASSIGN_MED();
512  if (s->id == "indomain_random") {
513  return INT_ASSIGN_RND(rnd);
514  }
515  }
516  std::cerr << "Warning, ignored search annotation: ";
517  ann->print(std::cerr);
518  std::cerr << std::endl;
519  return INT_ASSIGN_MIN();
520  }
521 
523  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
524  if ((s->id == "input_order") ||
525  (s->id == "first_fail") ||
526  (s->id == "anti_first_fail") ||
527  (s->id == "smallest") ||
528  (s->id == "largest") ||
529  (s->id == "max_regret"))
531  if ((s->id == "occurrence") ||
532  (s->id == "most_constrained"))
534  if (s->id == "random")
536  if ((s->id == "afc_min") ||
537  (s->id == "afc_size_min"))
539  if ((s->id == "afc_max") ||
540  (s->id == "afc_size_max") ||
541  (s->id == "dom_w_deg"))
543  if ((s->id == "action_min") &&
544  (s->id == "action_size_min"))
546  if ((s->id == "action_max") ||
547  (s->id == "action_size_max"))
549  }
550  std::cerr << "Warning, ignored search annotation: ";
551  ann->print(std::cerr);
552  std::cerr << std::endl;
554  }
555 
556  BoolValBranch ann2bvalsel(AST::Node* ann, std::string& r0, std::string& r1,
557  Rnd rnd) {
558  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
559  if (s->id == "indomain_min") {
560  r0 = "="; r1 = "!=";
561  return BOOL_VAL_MIN();
562  }
563  if (s->id == "indomain_max") {
564  r0 = "="; r1 = "!=";
565  return BOOL_VAL_MAX();
566  }
567  if (s->id == "indomain_median") {
568  r0 = "="; r1 = "!=";
569  return BOOL_VAL_MIN();
570  }
571  if (s->id == "indomain_split") {
572  r0 = "<="; r1 = ">";
573  return BOOL_VAL_MIN();
574  }
575  if (s->id == "indomain_reverse_split") {
576  r0 = ">"; r1 = "<=";
577  return BOOL_VAL_MAX();
578  }
579  if (s->id == "indomain_random") {
580  r0 = "="; r1 = "!=";
581  return BOOL_VAL_RND(rnd);
582  }
583  if (s->id == "indomain") {
584  r0 = "="; r1 = "=";
585  return BOOL_VAL_MIN();
586  }
587  if (s->id == "indomain_middle") {
588  std::cerr << "Warning, replacing unsupported annotation "
589  << "indomain_middle with indomain_median" << std::endl;
590  r0 = "="; r1 = "!=";
591  return BOOL_VAL_MIN();
592  }
593  if (s->id == "indomain_interval") {
594  std::cerr << "Warning, replacing unsupported annotation "
595  << "indomain_interval with indomain_split" << std::endl;
596  r0 = "<="; r1 = ">";
597  return BOOL_VAL_MIN();
598  }
599  }
600  std::cerr << "Warning, ignored search annotation: ";
601  ann->print(std::cerr);
602  std::cerr << std::endl;
603  r0 = "="; r1 = "!=";
604  return BOOL_VAL_MIN();
605  }
606 
608  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
609  if ((s->id == "indomain_min") ||
610  (s->id == "indomain_median"))
611  return BOOL_ASSIGN_MIN();
612  if (s->id == "indomain_max")
613  return BOOL_ASSIGN_MAX();
614  if (s->id == "indomain_random") {
615  return BOOL_ASSIGN_RND(rnd);
616  }
617  }
618  std::cerr << "Warning, ignored search annotation: ";
619  ann->print(std::cerr);
620  std::cerr << std::endl;
621  return BOOL_ASSIGN_MIN();
622  }
623 
624 #ifdef GECODE_HAS_SET_VARS
625  SetVarBranch ann2svarsel(AST::Node* ann, Rnd rnd, double decay) {
626  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
627  if (s->id == "input_order")
628  return SET_VAR_NONE();
629  if (s->id == "first_fail")
630  return SET_VAR_SIZE_MIN();
631  if (s->id == "anti_first_fail")
632  return SET_VAR_SIZE_MAX();
633  if (s->id == "smallest")
634  return SET_VAR_MIN_MIN();
635  if (s->id == "largest")
636  return SET_VAR_MAX_MAX();
637  if (s->id == "afc_min")
638  return SET_VAR_AFC_MIN(decay);
639  if (s->id == "afc_max")
640  return SET_VAR_AFC_MAX(decay);
641  if (s->id == "afc_size_min")
642  return SET_VAR_AFC_SIZE_MIN(decay);
643  if (s->id == "afc_size_max")
644  return SET_VAR_AFC_SIZE_MAX(decay);
645  if (s->id == "action_min")
646  return SET_VAR_ACTION_MIN(decay);
647  if (s->id == "action_max")
648  return SET_VAR_ACTION_MAX(decay);
649  if (s->id == "action_size_min")
650  return SET_VAR_ACTION_SIZE_MIN(decay);
651  if (s->id == "action_size_max")
652  return SET_VAR_ACTION_SIZE_MAX(decay);
653  if (s->id == "random") {
654  return SET_VAR_RND(rnd);
655  }
656  }
657  std::cerr << "Warning, ignored search annotation: ";
658  ann->print(std::cerr);
659  std::cerr << std::endl;
660  return SET_VAR_NONE();
661  }
662 
663  SetValBranch ann2svalsel(AST::Node* ann, std::string r0, std::string r1,
664  Rnd rnd) {
665  (void) rnd;
666  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
667  if (s->id == "indomain_min") {
668  r0 = "in"; r1 = "not in";
669  return SET_VAL_MIN_INC();
670  }
671  if (s->id == "indomain_max") {
672  r0 = "in"; r1 = "not in";
673  return SET_VAL_MAX_INC();
674  }
675  if (s->id == "outdomain_min") {
676  r1 = "in"; r0 = "not in";
677  return SET_VAL_MIN_EXC();
678  }
679  if (s->id == "outdomain_max") {
680  r1 = "in"; r0 = "not in";
681  return SET_VAL_MAX_EXC();
682  }
683  }
684  std::cerr << "Warning, ignored search annotation: ";
685  ann->print(std::cerr);
686  std::cerr << std::endl;
687  r0 = "in"; r1 = "not in";
688  return SET_VAL_MIN_INC();
689  }
690 #endif
691 
692 #ifdef GECODE_HAS_FLOAT_VARS
694  double decay) {
695  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
696  if (s->id == "input_order")
698  if (s->id == "first_fail")
700  if (s->id == "anti_first_fail")
702  if (s->id == "smallest")
704  if (s->id == "largest")
706  if (s->id == "occurrence")
708  if (s->id == "most_constrained")
711  if (s->id == "random") {
713  }
714  if (s->id == "afc_min")
716  if (s->id == "afc_max")
718  if (s->id == "afc_size_min")
720  if (s->id == "afc_size_max")
722  if (s->id == "action_min")
724  if (s->id == "action_max")
726  if (s->id == "action_size_min")
728  if (s->id == "action_size_max")
730  }
731  std::cerr << "Warning, ignored search annotation: ";
732  ann->print(std::cerr);
733  std::cerr << std::endl;
735  }
736 
737  FloatValBranch ann2fvalsel(AST::Node* ann, std::string r0, std::string r1) {
738  if (AST::Atom* s = dynamic_cast<AST::Atom*>(ann)) {
739  if (s->id == "indomain_split") {
740  r0 = "<="; r1 = ">";
741  return FLOAT_VAL_SPLIT_MIN();
742  }
743  if (s->id == "indomain_reverse_split") {
744  r1 = "<="; r0 = ">";
745  return FLOAT_VAL_SPLIT_MAX();
746  }
747  }
748  std::cerr << "Warning, ignored search annotation: ";
749  ann->print(std::cerr);
750  std::cerr << std::endl;
751  r0 = "<="; r1 = ">";
752  return FLOAT_VAL_SPLIT_MIN();
753  }
754 
755 #endif
756 
758  public:
760  typedef std::unordered_set<TupleSet> TupleSetSet;
762  TupleSetSet tupleSetSet;
763 
765  typedef std::unordered_set<SharedArray<int> > IntSharedArraySet;
767  IntSharedArraySet intSharedArraySet;
768 
770  typedef std::unordered_set<DFA> DFASet;
772  DFASet dfaSet;
773 
776  };
777 
779  : Space(f),
780  _initData(NULL), _random(f._random),
781  _solveAnnotations(NULL), iv_boolalias(NULL),
783  step(f.step),
784 #endif
785  needAuxVars(f.needAuxVars) {
786  _optVar = f._optVar;
788  _method = f._method;
789  _lns = f._lns;
792  iv.update(*this, f.iv);
793  iv_lns.update(*this, f.iv_lns);
795 
796  if (needAuxVars) {
797  IntVarArgs iva;
798  for (int i=0; i<f.iv_aux.size(); i++) {
799  if (!f.iv_aux[i].assigned()) {
800  iva << IntVar();
801  iva[iva.size()-1].update(*this, f.iv_aux[i]);
802  }
803  }
804  iv_aux = IntVarArray(*this, iva);
805  }
806 
807  bv.update(*this, f.bv);
809  if (needAuxVars) {
810  BoolVarArgs bva;
811  for (int i=0; i<f.bv_aux.size(); i++) {
812  if (!f.bv_aux[i].assigned()) {
813  bva << BoolVar();
814  bva[bva.size()-1].update(*this, f.bv_aux[i]);
815  }
816  }
817  bv_aux = BoolVarArray(*this, bva);
818  }
819 
820 #ifdef GECODE_HAS_SET_VARS
821  sv.update(*this, f.sv);
823  if (needAuxVars) {
824  SetVarArgs sva;
825  for (int i=0; i<f.sv_aux.size(); i++) {
826  if (!f.sv_aux[i].assigned()) {
827  sva << SetVar();
828  sva[sva.size()-1].update(*this, f.sv_aux[i]);
829  }
830  }
831  sv_aux = SetVarArray(*this, sva);
832  }
833 #endif
834 #ifdef GECODE_HAS_FLOAT_VARS
835  fv.update(*this, f.fv);
837  if (needAuxVars) {
838  FloatVarArgs fva;
839  for (int i=0; i<f.fv_aux.size(); i++) {
840  if (!f.fv_aux[i].assigned()) {
841  fva << FloatVar();
842  fva[fva.size()-1].update(*this, f.fv_aux[i]);
843  }
844  }
845  fv_aux = FloatVarArray(*this, fva);
846  }
847 #endif
848  }
849 
853  _optVar(-1), _optVarIsInt(true), _lns(0), _lnsInitialSolution(0),
854  _random(random),
855  _solveAnnotations(NULL), needAuxVars(true) {
856  branchInfo.init();
857  }
858 
859  void
860  FlatZincSpace::init(int intVars, int boolVars,
861  int setVars, int floatVars) {
862  (void) setVars;
863  (void) floatVars;
864 
865  intVarCount = 0;
866  iv = IntVarArray(*this, intVars);
867  iv_introduced = std::vector<bool>(2*intVars);
868  iv_boolalias = alloc<int>(intVars+(intVars==0?1:0));
869  boolVarCount = 0;
870  bv = BoolVarArray(*this, boolVars);
871  bv_introduced = std::vector<bool>(2*boolVars);
872 #ifdef GECODE_HAS_SET_VARS
873  setVarCount = 0;
874  sv = SetVarArray(*this, setVars);
875  sv_introduced = std::vector<bool>(2*setVars);
876 #endif
877 #ifdef GECODE_HAS_FLOAT_VARS
878  floatVarCount = 0;
879  fv = FloatVarArray(*this, floatVars);
880  fv_introduced = std::vector<bool>(2*floatVars);
881 #endif
882  }
883 
884  void
886  if (vs->alias) {
887  iv[intVarCount++] = iv[vs->i];
888  } else {
889  IntSet dom(vs2is(vs));
890  if (dom.size()==0) {
891  fail();
892  return;
893  } else {
894  iv[intVarCount++] = IntVar(*this, dom);
895  }
896  }
897  iv_introduced[2*(intVarCount-1)] = vs->introduced;
898  iv_introduced[2*(intVarCount-1)+1] = vs->funcDep;
899  iv_boolalias[intVarCount-1] = -1;
900  }
901 
902  void
904  iv_boolalias[iv] = bv;
905  }
906  int
908  return iv_boolalias[iv];
909  }
910 
911  void
913  if (vs->alias) {
914  bv[boolVarCount++] = bv[vs->i];
915  } else {
916  bv[boolVarCount++] = BoolVar(*this, vs2bsl(vs), vs2bsh(vs));
917  }
919  bv_introduced[2*(boolVarCount-1)+1] = vs->funcDep;
920  }
921 
922 #ifdef GECODE_HAS_SET_VARS
923  void
925  if (vs->alias) {
926  sv[setVarCount++] = sv[vs->i];
927  } else if (vs->assigned) {
928  assert(vs->upperBound());
929  AST::SetLit* vsv = vs->upperBound.some();
930  if (vsv->interval) {
931  IntSet d(vsv->min, vsv->max);
932  sv[setVarCount++] = SetVar(*this, d, d);
933  } else {
934  int* is = heap.alloc<int>(static_cast<unsigned long int>(vsv->s.size()));
935  for (int i=vsv->s.size(); i--; )
936  is[i] = vsv->s[i];
937  IntSet d(is, vsv->s.size());
938  heap.free(is,static_cast<unsigned long int>(vsv->s.size()));
939  sv[setVarCount++] = SetVar(*this, d, d);
940  }
941  } else if (vs->upperBound()) {
942  AST::SetLit* vsv = vs->upperBound.some();
943  if (vsv->interval) {
944  IntSet d(vsv->min, vsv->max);
945  sv[setVarCount++] = SetVar(*this, IntSet::empty, d);
946  } else {
947  int* is = heap.alloc<int>(static_cast<unsigned long int>(vsv->s.size()));
948  for (int i=vsv->s.size(); i--; )
949  is[i] = vsv->s[i];
950  IntSet d(is, vsv->s.size());
951  heap.free(is,static_cast<unsigned long int>(vsv->s.size()));
952  sv[setVarCount++] = SetVar(*this, IntSet::empty, d);
953  }
954  } else {
955  sv[setVarCount++] = SetVar(*this, IntSet::empty,
958  }
959  sv_introduced[2*(setVarCount-1)] = vs->introduced;
960  sv_introduced[2*(setVarCount-1)+1] = vs->funcDep;
961  }
962 #else
963  void
965  throw FlatZinc::Error("Gecode", "set variables not supported");
966  }
967 #endif
968 
969 #ifdef GECODE_HAS_FLOAT_VARS
970  void
972  if (vs->alias) {
973  fv[floatVarCount++] = fv[vs->i];
974  } else {
975  double dmin, dmax;
976  if (vs->domain()) {
977  dmin = vs->domain.some().first;
978  dmax = vs->domain.some().second;
979  if (dmin > dmax) {
980  fail();
981  return;
982  }
983  } else {
984  dmin = Float::Limits::min;
985  dmax = Float::Limits::max;
986  }
987  fv[floatVarCount++] = FloatVar(*this, dmin, dmax);
988  }
990  fv_introduced[2*(floatVarCount-1)+1] = vs->funcDep;
991  }
992 #else
993  void
995  throw FlatZinc::Error("Gecode", "float variables not supported");
996  }
997 #endif
998 
999  namespace {
1000  struct ConExprOrder {
1001  bool operator() (ConExpr* ce0, ConExpr* ce1) {
1002  return ce0->args->a.size() < ce1->args->a.size();
1003  }
1004  };
1005  }
1006 
1007  void
1008  FlatZincSpace::postConstraints(std::vector<ConExpr*>& ces) {
1009  ConExprOrder ceo;
1010  std::sort(ces.begin(), ces.end(), ceo);
1011 
1012  for (unsigned int i=0; i<ces.size(); i++) {
1013  const ConExpr& ce = *ces[i];
1014  try {
1015  registry().post(*this, ce);
1016  } catch (Gecode::Exception& e) {
1017  throw FlatZinc::Error("Gecode", e.what());
1018  } catch (AST::TypeError& e) {
1019  throw FlatZinc::Error("Type error", e.what());
1020  }
1021  delete ces[i];
1022  ces[i] = NULL;
1023  }
1024  }
1025 
1026  void flattenAnnotations(AST::Array* ann, std::vector<AST::Node*>& out) {
1027  for (unsigned int i=0; i<ann->a.size(); i++) {
1028  if (ann->a[i]->isCall("seq_search")) {
1029  AST::Call* c = ann->a[i]->getCall();
1030  if (c->args->isArray())
1031  flattenAnnotations(c->args->getArray(), out);
1032  else
1033  out.push_back(c->args);
1034  } else {
1035  out.push_back(ann->a[i]);
1036  }
1037  }
1038  }
1039 
1040  void
1042  double decay,
1043  bool ignoreUnknown,
1044  std::ostream& err) {
1045  Rnd rnd(static_cast<unsigned int>(seed));
1046  TieBreak<IntVarBranch> def_int_varsel = INT_VAR_AFC_SIZE_MAX(0.99);
1047  IntBoolVarBranch def_intbool_varsel = INTBOOL_VAR_AFC_SIZE_MAX(0.99);
1048  IntValBranch def_int_valsel = INT_VAL_MIN();
1049  std::string def_int_rel_left = "=";
1050  std::string def_int_rel_right = "!=";
1051  TieBreak<BoolVarBranch> def_bool_varsel = BOOL_VAR_AFC_MAX(0.99);
1052  BoolValBranch def_bool_valsel = BOOL_VAL_MIN();
1053  std::string def_bool_rel_left = "=";
1054  std::string def_bool_rel_right = "!=";
1055 #ifdef GECODE_HAS_SET_VARS
1056  SetVarBranch def_set_varsel = SET_VAR_AFC_SIZE_MAX(0.99);
1057  SetValBranch def_set_valsel = SET_VAL_MIN_INC();
1058  std::string def_set_rel_left = "in";
1059  std::string def_set_rel_right = "not in";
1060 #endif
1061 #ifdef GECODE_HAS_FLOAT_VARS
1062  TieBreak<FloatVarBranch> def_float_varsel = FLOAT_VAR_SIZE_MIN();
1063  FloatValBranch def_float_valsel = FLOAT_VAL_SPLIT_MIN();
1064  std::string def_float_rel_left = "<=";
1065  std::string def_float_rel_right = ">";
1066 #endif
1067 
1068  std::vector<bool> iv_searched(iv.size());
1069  for (unsigned int i=iv.size(); i--;)
1070  iv_searched[i] = false;
1071  std::vector<bool> bv_searched(bv.size());
1072  for (unsigned int i=bv.size(); i--;)
1073  bv_searched[i] = false;
1074 #ifdef GECODE_HAS_SET_VARS
1075  std::vector<bool> sv_searched(sv.size());
1076  for (unsigned int i=sv.size(); i--;)
1077  sv_searched[i] = false;
1078 #endif
1079 #ifdef GECODE_HAS_FLOAT_VARS
1080  std::vector<bool> fv_searched(fv.size());
1081  for (unsigned int i=fv.size(); i--;)
1082  fv_searched[i] = false;
1083 #endif
1084 
1085  _lns = 0;
1086  if (ann) {
1087  std::vector<AST::Node*> flatAnn;
1088  if (ann->isArray()) {
1089  flattenAnnotations(ann->getArray() , flatAnn);
1090  } else {
1091  flatAnn.push_back(ann);
1092  }
1093 
1094  for (unsigned int i=0; i<flatAnn.size(); i++) {
1095  if (flatAnn[i]->isCall("relax_and_reconstruct")) {
1096  if (_lns != 0)
1097  throw FlatZinc::Error("FlatZinc",
1098  "Only one relax_and_reconstruct annotation allowed");
1099  AST::Call *call = flatAnn[i]->getCall("relax_and_reconstruct");
1100  AST::Array* args;
1101  if (call->args->getArray()->a.size()==2) {
1102  args = call->getArgs(2);
1103  } else {
1104  args = call->getArgs(3);
1105  }
1106  _lns = args->a[1]->getInt();
1107  AST::Array *vars = args->a[0]->getArray();
1108  int k=vars->a.size();
1109  for (int i=vars->a.size(); i--;)
1110  if (vars->a[i]->isInt())
1111  k--;
1112  iv_lns = IntVarArray(*this, k);
1113  k = 0;
1114  for (unsigned int i=0; i<vars->a.size(); i++) {
1115  if (vars->a[i]->isInt())
1116  continue;
1117  iv_lns[k++] = iv[vars->a[i]->getIntVar()];
1118  }
1119  if (args->a.size()==3) {
1120  AST::Array *initial = args->a[2]->getArray();
1121  _lnsInitialSolution = IntSharedArray(initial->a.size());
1122  for (unsigned int i=initial->a.size(); i--;)
1123  _lnsInitialSolution[i] = initial->a[i]->getInt();
1124  }
1125  } else if (flatAnn[i]->isCall("gecode_search")) {
1126  AST::Call* c = flatAnn[i]->getCall();
1127  branchWithPlugin(c->args);
1128  } else if (flatAnn[i]->isCall("int_search")) {
1129  AST::Call *call = flatAnn[i]->getCall("int_search");
1130  AST::Array *args = call->getArgs(4);
1131  AST::Array *vars = args->a[0]->getArray();
1132  int k=vars->a.size();
1133  for (int i=vars->a.size(); i--;)
1134  if (vars->a[i]->isInt())
1135  k--;
1136  IntVarArgs va(k);
1137  std::vector<std::string> names;
1138  k=0;
1139  for (unsigned int i=0; i<vars->a.size(); i++) {
1140  if (vars->a[i]->isInt())
1141  continue;
1142  va[k++] = iv[vars->a[i]->getIntVar()];
1143  iv_searched[vars->a[i]->getIntVar()] = true;
1144  names.push_back(vars->a[i]->getVarName());
1145  }
1146  std::string r0, r1;
1147  {
1148  BrancherGroup bg;
1149  branch(bg(*this), va,
1150  ann2ivarsel(args->a[1],rnd,decay),
1151  ann2ivalsel(args->a[2],r0,r1,rnd),
1152  nullptr,
1153  &varValPrint<IntVar>);
1154  branchInfo.add(bg,r0,r1,names);
1155  }
1156  } else if (flatAnn[i]->isCall("int_assign")) {
1157  AST::Call *call = flatAnn[i]->getCall("int_assign");
1158  AST::Array *args = call->getArgs(2);
1159  AST::Array *vars = args->a[0]->getArray();
1160  int k=vars->a.size();
1161  for (int i=vars->a.size(); i--;)
1162  if (vars->a[i]->isInt())
1163  k--;
1164  IntVarArgs va(k);
1165  k=0;
1166  for (unsigned int i=0; i<vars->a.size(); i++) {
1167  if (vars->a[i]->isInt())
1168  continue;
1169  va[k++] = iv[vars->a[i]->getIntVar()];
1170  iv_searched[vars->a[i]->getIntVar()] = true;
1171  }
1172  assign(*this, va, ann2asnivalsel(args->a[1],rnd), nullptr,
1173  &varValPrint<IntVar>);
1174  } else if (flatAnn[i]->isCall("bool_search")) {
1175  AST::Call *call = flatAnn[i]->getCall("bool_search");
1176  AST::Array *args = call->getArgs(4);
1177  AST::Array *vars = args->a[0]->getArray();
1178  int k=vars->a.size();
1179  for (int i=vars->a.size(); i--;)
1180  if (vars->a[i]->isBool())
1181  k--;
1182  BoolVarArgs va(k);
1183  k=0;
1184  std::vector<std::string> names;
1185  for (unsigned int i=0; i<vars->a.size(); i++) {
1186  if (vars->a[i]->isBool())
1187  continue;
1188  va[k++] = bv[vars->a[i]->getBoolVar()];
1189  bv_searched[vars->a[i]->getBoolVar()] = true;
1190  names.push_back(vars->a[i]->getVarName());
1191  }
1192 
1193  std::string r0, r1;
1194  {
1195  BrancherGroup bg;
1196  branch(bg(*this), va,
1197  ann2bvarsel(args->a[1],rnd,decay),
1198  ann2bvalsel(args->a[2],r0,r1,rnd),
1199  nullptr,
1200  &varValPrint<BoolVar>);
1201  branchInfo.add(bg,r0,r1,names);
1202  }
1203  } else if (flatAnn[i]->isCall("int_default_search")) {
1204  AST::Call *call = flatAnn[i]->getCall("int_default_search");
1205  AST::Array *args = call->getArgs(2);
1206  def_int_varsel = ann2ivarsel(args->a[0],rnd,decay);
1207  def_int_valsel = ann2ivalsel(args->a[1],
1208  def_int_rel_left,def_int_rel_right,rnd);
1209  } else if (flatAnn[i]->isCall("bool_default_search")) {
1210  AST::Call *call = flatAnn[i]->getCall("bool_default_search");
1211  AST::Array *args = call->getArgs(2);
1212  def_bool_varsel = ann2bvarsel(args->a[0],rnd,decay);
1213  def_bool_valsel = ann2bvalsel(args->a[1],
1214  def_bool_rel_left,def_bool_rel_right,
1215  rnd);
1216  } else if (flatAnn[i]->isCall("set_search")) {
1217 #ifdef GECODE_HAS_SET_VARS
1218  AST::Call *call = flatAnn[i]->getCall("set_search");
1219  AST::Array *args = call->getArgs(4);
1220  AST::Array *vars = args->a[0]->getArray();
1221  int k=vars->a.size();
1222  for (int i=vars->a.size(); i--;)
1223  if (vars->a[i]->isSet())
1224  k--;
1225  SetVarArgs va(k);
1226  k=0;
1227  std::vector<std::string> names;
1228  for (unsigned int i=0; i<vars->a.size(); i++) {
1229  if (vars->a[i]->isSet())
1230  continue;
1231  va[k++] = sv[vars->a[i]->getSetVar()];
1232  sv_searched[vars->a[i]->getSetVar()] = true;
1233  names.push_back(vars->a[i]->getVarName());
1234  }
1235  std::string r0, r1;
1236  {
1237  BrancherGroup bg;
1238  branch(bg(*this), va,
1239  ann2svarsel(args->a[1],rnd,decay),
1240  ann2svalsel(args->a[2],r0,r1,rnd),
1241  nullptr,
1242  &varValPrint<SetVar>);
1243  branchInfo.add(bg,r0,r1,names);
1244  }
1245 #else
1246  if (!ignoreUnknown) {
1247  err << "Warning, ignored search annotation: ";
1248  flatAnn[i]->print(err);
1249  err << std::endl;
1250  }
1251 #endif
1252  } else if (flatAnn[i]->isCall("set_default_search")) {
1253 #ifdef GECODE_HAS_SET_VARS
1254  AST::Call *call = flatAnn[i]->getCall("set_default_search");
1255  AST::Array *args = call->getArgs(2);
1256  def_set_varsel = ann2svarsel(args->a[0],rnd,decay);
1257  def_set_valsel = ann2svalsel(args->a[1],
1258  def_set_rel_left,def_set_rel_right,rnd);
1259 #else
1260  if (!ignoreUnknown) {
1261  err << "Warning, ignored search annotation: ";
1262  flatAnn[i]->print(err);
1263  err << std::endl;
1264  }
1265 #endif
1266  } else if (flatAnn[i]->isCall("float_default_search")) {
1267 #ifdef GECODE_HAS_FLOAT_VARS
1268  AST::Call *call = flatAnn[i]->getCall("float_default_search");
1269  AST::Array *args = call->getArgs(2);
1270  def_float_varsel = ann2fvarsel(args->a[0],rnd,decay);
1271  def_float_valsel = ann2fvalsel(args->a[1],
1272  def_float_rel_left,def_float_rel_right);
1273 #else
1274  if (!ignoreUnknown) {
1275  err << "Warning, ignored search annotation: ";
1276  flatAnn[i]->print(err);
1277  err << std::endl;
1278  }
1279 #endif
1280  } else if (flatAnn[i]->isCall("float_search")) {
1281 #ifdef GECODE_HAS_FLOAT_VARS
1282  AST::Call *call = flatAnn[i]->getCall("float_search");
1283  AST::Array *args = call->getArgs(5);
1284  AST::Array *vars = args->a[0]->getArray();
1285  int k=vars->a.size();
1286  for (int i=vars->a.size(); i--;)
1287  if (vars->a[i]->isFloat())
1288  k--;
1289  FloatVarArgs va(k);
1290  k=0;
1291  std::vector<std::string> names;
1292  for (unsigned int i=0; i<vars->a.size(); i++) {
1293  if (vars->a[i]->isFloat())
1294  continue;
1295  va[k++] = fv[vars->a[i]->getFloatVar()];
1296  fv_searched[vars->a[i]->getFloatVar()] = true;
1297  names.push_back(vars->a[i]->getVarName());
1298  }
1299  std::string r0, r1;
1300  {
1301  BrancherGroup bg;
1302  branch(bg(*this), va,
1303  ann2fvarsel(args->a[2],rnd,decay),
1304  ann2fvalsel(args->a[3],r0,r1),
1305  nullptr,
1306  &varValPrintF);
1307  branchInfo.add(bg,r0,r1,names);
1308  }
1309 #else
1310  if (!ignoreUnknown) {
1311  err << "Warning, ignored search annotation: ";
1312  flatAnn[i]->print(err);
1313  err << std::endl;
1314  }
1315 #endif
1316  } else {
1317  if (!ignoreUnknown) {
1318  err << "Warning, ignored search annotation: ";
1319  flatAnn[i]->print(err);
1320  err << std::endl;
1321  }
1322  }
1323  }
1324  }
1325  int introduced = 0;
1326  int funcdep = 0;
1327  int searched = 0;
1328  for (int i=iv.size(); i--;) {
1329  if (iv_searched[i] || (_method != SAT && _optVarIsInt && _optVar==i)) {
1330  searched++;
1331  } else if (iv_introduced[2*i]) {
1332  if (iv_introduced[2*i+1]) {
1333  funcdep++;
1334  } else {
1335  introduced++;
1336  }
1337  }
1338  }
1339  std::vector<std::string> iv_sol_names(iv.size()-(introduced+funcdep+searched));
1340  IntVarArgs iv_sol(iv.size()-(introduced+funcdep+searched));
1341  std::vector<std::string> iv_tmp_names(introduced);
1342  IntVarArgs iv_tmp(introduced);
1343  for (int i=iv.size(), j=0, k=0; i--;) {
1344  if (iv_searched[i] || (_method != SAT && _optVarIsInt && _optVar==i))
1345  continue;
1346  if (iv_introduced[2*i]) {
1347  if (!iv_introduced[2*i+1]) {
1348  iv_tmp_names[j] = p.intVarName(i);
1349  iv_tmp[j++] = iv[i];
1350  }
1351  } else {
1352  iv_sol_names[k] = p.intVarName(i);
1353  iv_sol[k++] = iv[i];
1354  }
1355  }
1356 
1357  introduced = 0;
1358  funcdep = 0;
1359  searched = 0;
1360  for (int i=bv.size(); i--;) {
1361  if (bv_searched[i]) {
1362  searched++;
1363  } else if (bv_introduced[2*i]) {
1364  if (bv_introduced[2*i+1]) {
1365  funcdep++;
1366  } else {
1367  introduced++;
1368  }
1369  }
1370  }
1371  std::vector<std::string> bv_sol_names(bv.size()-(introduced+funcdep+searched));
1372  BoolVarArgs bv_sol(bv.size()-(introduced+funcdep+searched));
1373  BoolVarArgs bv_tmp(introduced);
1374  std::vector<std::string> bv_tmp_names(introduced);
1375  for (int i=bv.size(), j=0, k=0; i--;) {
1376  if (bv_searched[i])
1377  continue;
1378  if (bv_introduced[2*i]) {
1379  if (!bv_introduced[2*i+1]) {
1380  bv_tmp_names[j] = p.boolVarName(i);
1381  bv_tmp[j++] = bv[i];
1382  }
1383  } else {
1384  bv_sol_names[k] = p.boolVarName(i);
1385  bv_sol[k++] = bv[i];
1386  }
1387  }
1388 
1389  if (iv_sol.size() > 0 && bv_sol.size() > 0) {
1390  branch(*this, iv_sol, bv_sol, def_intbool_varsel, def_int_valsel);
1391  } else if (iv_sol.size() > 0) {
1392  BrancherGroup bg;
1393  branch(bg(*this), iv_sol, def_int_varsel, def_int_valsel, nullptr,
1394  &varValPrint<IntVar>);
1395  branchInfo.add(bg,def_int_rel_left,def_int_rel_right,iv_sol_names);
1396  } else if (bv_sol.size() > 0) {
1397  BrancherGroup bg;
1398  branch(bg(*this), bv_sol, def_bool_varsel, def_bool_valsel, nullptr,
1399  &varValPrint<BoolVar>);
1400  branchInfo.add(bg,def_bool_rel_left,def_bool_rel_right,bv_sol_names);
1401  }
1402 #ifdef GECODE_HAS_FLOAT_VARS
1403  introduced = 0;
1404  funcdep = 0;
1405  searched = 0;
1406  for (int i=fv.size(); i--;) {
1407  if (fv_searched[i] || (_method != SAT && !_optVarIsInt && _optVar==i)) {
1408  searched++;
1409  } else if (fv_introduced[2*i]) {
1410  if (fv_introduced[2*i+1]) {
1411  funcdep++;
1412  } else {
1413  introduced++;
1414  }
1415  }
1416  }
1417  std::vector<std::string> fv_sol_names(fv.size()-(introduced+funcdep+searched));
1418  FloatVarArgs fv_sol(fv.size()-(introduced+funcdep+searched));
1419  FloatVarArgs fv_tmp(introduced);
1420  std::vector<std::string> fv_tmp_names(introduced);
1421  for (int i=fv.size(), j=0, k=0; i--;) {
1422  if (fv_searched[i] || (_method != SAT && !_optVarIsInt && _optVar==i))
1423  continue;
1424  if (fv_introduced[2*i]) {
1425  if (!fv_introduced[2*i+1]) {
1426  fv_tmp_names[j] = p.floatVarName(i);
1427  fv_tmp[j++] = fv[i];
1428  }
1429  } else {
1430  fv_sol_names[k] = p.floatVarName(i);
1431  fv_sol[k++] = fv[i];
1432  }
1433  }
1434 
1435  if (fv_sol.size() > 0) {
1436  BrancherGroup bg;
1437  branch(bg(*this), fv_sol, def_float_varsel, def_float_valsel, nullptr,
1438  &varValPrintF);
1439  branchInfo.add(bg,def_float_rel_left,def_float_rel_right,fv_sol_names);
1440  }
1441 #endif
1442 #ifdef GECODE_HAS_SET_VARS
1443  introduced = 0;
1444  funcdep = 0;
1445  searched = 0;
1446  for (int i=sv.size(); i--;) {
1447  if (sv_searched[i]) {
1448  searched++;
1449  } else if (sv_introduced[2*i]) {
1450  if (sv_introduced[2*i+1]) {
1451  funcdep++;
1452  } else {
1453  introduced++;
1454  }
1455  }
1456  }
1457  std::vector<std::string> sv_sol_names(sv.size()-(introduced+funcdep+searched));
1458  SetVarArgs sv_sol(sv.size()-(introduced+funcdep+searched));
1459  SetVarArgs sv_tmp(introduced);
1460  std::vector<std::string> sv_tmp_names(introduced);
1461  for (int i=sv.size(), j=0, k=0; i--;) {
1462  if (sv_searched[i])
1463  continue;
1464  if (sv_introduced[2*i]) {
1465  if (!sv_introduced[2*i+1]) {
1466  sv_tmp_names[j] = p.setVarName(i);
1467  sv_tmp[j++] = sv[i];
1468  }
1469  } else {
1470  sv_sol_names[k] = p.setVarName(i);
1471  sv_sol[k++] = sv[i];
1472  }
1473  }
1474 
1475  if (sv_sol.size() > 0) {
1476  BrancherGroup bg;
1477  branch(bg(*this), sv_sol, def_set_varsel, def_set_valsel, nullptr,
1478  &varValPrint<SetVar>);
1479  branchInfo.add(bg,def_set_rel_left,def_set_rel_right,sv_sol_names);
1480 
1481  }
1482 #endif
1483  iv_aux = IntVarArray(*this, iv_tmp);
1484  bv_aux = BoolVarArray(*this, bv_tmp);
1485  int n_aux = iv_aux.size() + bv_aux.size();
1486 #ifdef GECODE_HAS_SET_VARS
1487  sv_aux = SetVarArray(*this, sv_tmp);
1488  n_aux += sv_aux.size();
1489 #endif
1490 #ifdef GECODE_HAS_FLOAT_VARS
1491  fv_aux = FloatVarArray(*this, fv_tmp);
1492  n_aux += fv_aux.size();
1493 #endif
1494 
1495  if (n_aux > 0) {
1496  if (_method == SAT) {
1497  AuxVarBrancher::post(*this, def_int_varsel, def_int_valsel,
1498  def_bool_varsel, def_bool_valsel
1499 #ifdef GECODE_HAS_SET_VARS
1500  , def_set_varsel, def_set_valsel
1501 #endif
1502 #ifdef GECODE_HAS_FLOAT_VARS
1503  , def_float_varsel, def_float_valsel
1504 #endif
1505  );
1506  } else {
1507  {
1508  BrancherGroup bg;
1509  branch(bg(*this),iv_aux,def_int_varsel,def_int_valsel, nullptr,
1510  &varValPrint<IntVar>);
1511  branchInfo.add(bg,def_int_rel_left,def_int_rel_right,iv_tmp_names);
1512  }
1513  {
1514  BrancherGroup bg;
1515  branch(bg(*this),bv_aux,def_bool_varsel,def_bool_valsel, nullptr,
1516  &varValPrint<BoolVar>);
1517  branchInfo.add(bg,def_bool_rel_left,def_bool_rel_right,bv_tmp_names);
1518  }
1519  #ifdef GECODE_HAS_SET_VARS
1520  {
1521  BrancherGroup bg;
1522  branch(bg(*this),sv_aux,def_set_varsel,def_set_valsel, nullptr,
1523  &varValPrint<SetVar>);
1524  branchInfo.add(bg,def_set_rel_left,def_set_rel_right,sv_tmp_names);
1525  }
1526  #endif
1527  #ifdef GECODE_HAS_FLOAT_VARS
1528  {
1529  BrancherGroup bg;
1530  branch(bg(*this),fv_aux,def_float_varsel,def_float_valsel, nullptr,
1531  &varValPrintF);
1532  branchInfo.add(bg,def_float_rel_left,def_float_rel_right,fv_tmp_names);
1533  }
1534  #endif
1535 
1536  }
1537  }
1538 
1539  if (_method == MIN) {
1540  if (_optVarIsInt) {
1541  std::vector<std::string> names(1);
1542  names[0] = p.intVarName(_optVar);
1543  BrancherGroup bg;
1544  branch(bg(*this), iv[_optVar], INT_VAL_MIN(),
1545  &varValPrint<IntVar>);
1546  branchInfo.add(bg,"=","!=",names);
1547  } else {
1548 #ifdef GECODE_HAS_FLOAT_VARS
1549  std::vector<std::string> names(1);
1550  names[0] = p.floatVarName(_optVar);
1551  BrancherGroup bg;
1552  branch(bg(*this), fv[_optVar], FLOAT_VAL_SPLIT_MIN(),
1553  &varValPrintF);
1554  branchInfo.add(bg,"<=",">",names);
1555 #endif
1556  }
1557  } else if (_method == MAX) {
1558  if (_optVarIsInt) {
1559  std::vector<std::string> names(1);
1560  names[0] = p.intVarName(_optVar);
1561  BrancherGroup bg;
1562  branch(bg(*this), iv[_optVar], INT_VAL_MAX(),
1563  &varValPrint<IntVar>);
1564  branchInfo.add(bg,"=","!=",names);
1565  } else {
1566 #ifdef GECODE_HAS_FLOAT_VARS
1567  std::vector<std::string> names(1);
1568  names[0] = p.floatVarName(_optVar);
1569  BrancherGroup bg;
1570  branch(bg(*this), fv[_optVar], FLOAT_VAL_SPLIT_MAX(),
1571  &varValPrintF);
1572  branchInfo.add(bg,"<=",">",names);
1573 #endif
1574  }
1575  }
1576 
1577  }
1578 
1579  AST::Array*
1581  return _solveAnnotations;
1582  }
1583 
1584  void
1586  _method = SAT;
1587  _solveAnnotations = ann;
1588  }
1589 
1590  void
1591  FlatZincSpace::minimize(int var, bool isInt, AST::Array* ann) {
1592  _method = MIN;
1593  _optVar = var;
1594  _optVarIsInt = isInt;
1595  _solveAnnotations = ann;
1596  }
1597 
1598  void
1599  FlatZincSpace::maximize(int var, bool isInt, AST::Array* ann) {
1600  _method = MAX;
1601  _optVar = var;
1602  _optVarIsInt = isInt;
1603  _solveAnnotations = ann;
1604  }
1605 
1607  delete _initData;
1608  delete _solveAnnotations;
1609  }
1610 
1611 #ifdef GECODE_HAS_GIST
1612 
1616  template<class Engine>
1617  class GistEngine {
1618  };
1619 
1621  template<typename S>
1622  class GistEngine<DFS<S> > {
1623  public:
1624  static void explore(S* root, const FlatZincOptions& opt,
1627  o.c_d = opt.c_d(); o.a_d = opt.a_d();
1628  o.inspect.click(i);
1629  o.inspect.compare(c);
1630  (void) Gecode::Gist::dfs(root, o);
1631  }
1632  };
1633 
1635  template<typename S>
1636  class GistEngine<BAB<S> > {
1637  public:
1638  static void explore(S* root, const FlatZincOptions& opt,
1641  o.c_d = opt.c_d(); o.a_d = opt.a_d();
1642  o.inspect.click(i);
1643  o.inspect.compare(c);
1644  (void) Gecode::Gist::bab(root, o);
1645  }
1646  };
1647 
1649  template<class S>
1652  private:
1653  const Printer& p;
1654  public:
1656  FZPrintingInspector(const Printer& p0);
1658  virtual void inspect(const Space& node);
1660  virtual void finalize(void);
1661  };
1662 
1663  template<class S>
1665  : TextOutput("Gecode/FlatZinc"), p(p0) {}
1666 
1667  template<class S>
1668  void
1670  init();
1671  dynamic_cast<const S&>(node).print(getStream(), p);
1672  getStream() << std::endl;
1673  }
1674 
1675  template<class S>
1676  void
1679  }
1680 
1681  template<class S>
1683  : public Gecode::Gist::VarComparator<S> {
1684  private:
1685  const Printer& p;
1686  public:
1688  FZPrintingComparator(const Printer& p0);
1689 
1691  virtual void compare(const Space& s0, const Space& s1);
1692  };
1693 
1694  template<class S>
1696  : Gecode::Gist::VarComparator<S>("Gecode/FlatZinc"), p(p0) {}
1697 
1698  template<class S>
1699  void
1701  this->init();
1702  try {
1703  dynamic_cast<const S&>(s0).compare(dynamic_cast<const S&>(s1),
1704  this->getStream(), p);
1705  } catch (Exception& e) {
1706  this->getStream() << "Exception: " << e.what();
1707  }
1708  this->getStream() << std::endl;
1709  }
1710 
1711 #endif
1712 
1713  template<template<class> class Engine>
1714  void
1715  FlatZincSpace::runEngine(std::ostream& out, const Printer& p,
1716  const FlatZincOptions& opt, Support::Timer& t_total) {
1717  if (opt.restart()==RM_NONE) {
1718  runMeta<Engine,Driver::EngineToMeta>(out,p,opt,t_total);
1719  } else {
1720  runMeta<Engine,RBS>(out,p,opt,t_total);
1721  }
1722  }
1723 
1724 #ifdef GECODE_HAS_CPPROFILER
1725 
1727  public:
1728  const Printer& p;
1729  FlatZincGetInfo(const Printer& printer) : p(printer) {}
1730  virtual std::string
1731  getInfo(const Space& space) const {
1732  std::stringstream ss;
1733  if (const FlatZincSpace* fz_space = dynamic_cast<const FlatZincSpace*>(&space)) {
1734  ss << "{domains = \"";
1735  ss << fz_space->getDomains(p);
1736  ss << "\"}";
1737  }
1738  return ss.str();
1739  }
1741  };
1742 
1743  void printIntVar(std::ostream& os, const std::string name, const Int::IntView& x) {
1744  os << "var ";
1745  if (x.assigned()) {
1746  os << "int: " << name << " = " << x.val() << ";";
1747  } else if (x.range()) {
1748  os << x.min() << ".." << x.max() << ": " << name << ";";
1749  } else {
1750  os << "array_union([";
1752  while (true) {
1753  os << r.min() << ".." << r.max();
1754  ++r;
1755  if (!r()) break;
1756  os << ',';
1757  }
1758  os << "]): " << name << ";";
1759  }
1760  os << "\n";
1761  }
1762  void printBoolVar(std::ostream& os, const std::string name, const BoolVar& b) {
1763  os << "var bool: " << name;
1764  if(b.assigned())
1765  os << " = " << (b.val() ? "true" : "false");
1766  os << ";\n";
1767  }
1768 #ifdef GECODE_HAS_FLOAT_VARS
1769  void printFloatVar(std::ostream& os, const std::string name, const Float::FloatView& f) {
1770  os << "var ";
1771  if(f.assigned())
1772  os << "float: " << name << " = " << f.med() << ";";
1773  else
1774  os << f.min() << ".." << f.max() << ": " << name << ";";
1775  os << "\n";
1776  }
1777 #endif
1778  std::string FlatZincSpace::getDomains(const Printer& p) const {
1779  std::ostringstream oss;
1780 
1781  for (int i = 0; i < iv.size(); i++)
1782  printIntVar(oss, p.intVarName(i), iv[i]);
1783 
1784  for (int i = 0; i < bv.size(); i++)
1785  printBoolVar(oss, p.boolVarName(i), bv[i]);
1786 
1787 #ifdef GECODE_HAS_FLOAT_VARS
1788  for (int i = 0; i < fv.size(); i++)
1789  printFloatVar(oss, p.floatVarName(i), fv[i]);
1790 #endif
1791 #ifdef GECODE_HAS_SET_VARS
1792  for (int i = 0; i < sv.size(); i++)
1793  oss << "var " << sv[i] << ": " << p.setVarName(i) << ";" << std::endl;
1794 #endif
1795 
1796  return oss.str();
1797  }
1798 
1799 #endif
1800 
1801  template<template<class> class Engine,
1802  template<class,template<class> class> class Meta>
1803  void
1804  FlatZincSpace::runMeta(std::ostream& out, const Printer& p,
1805  const FlatZincOptions& opt, Support::Timer& t_total) {
1806 #ifdef GECODE_HAS_GIST
1807  if (opt.mode() == SM_GIST) {
1810  (void) GistEngine<Engine<FlatZincSpace> >::explore(this,opt,&pi,&pc);
1811  return;
1812  }
1813 #endif
1814  StatusStatistics sstat;
1815  unsigned int n_p = 0;
1816  Support::Timer t_solve;
1817  t_solve.start();
1818  if (status(sstat) != SS_FAILED) {
1819  n_p = PropagatorGroup::all.size(*this);
1820  }
1821  Search::Options o;
1822  o.stop = Driver::CombinedStop::create(opt.node(), opt.fail(), opt.time(),
1823  true);
1824  o.c_d = opt.c_d();
1825  o.a_d = opt.a_d();
1826 
1827 #ifdef GECODE_HAS_CPPROFILER
1828 
1829  if (opt.mode() == SM_CPPROFILER) {
1830  FlatZincGetInfo* getInfo = nullptr;
1831  if (opt.profiler_info())
1832  getInfo = new FlatZincGetInfo(p);
1834  opt.name(), opt.profiler_port(),
1835  getInfo);
1836  }
1837 
1838 #endif
1839 
1840 #ifdef GECODE_HAS_FLOAT_VARS
1841  step = opt.step();
1842 #endif
1843  o.threads = opt.threads();
1844  o.nogoods_limit = opt.nogoods() ? opt.nogoods_limit() : 0;
1846  if (opt.interrupt())
1848  Meta<FlatZincSpace,Engine> se(this,o);
1849  int noOfSolutions = opt.solutions();
1850  if (noOfSolutions == -1) {
1851  noOfSolutions = (_method == SAT) ? 1 : 0;
1852  }
1853  bool printAll = _method == SAT || opt.allSolutions() || noOfSolutions != 0;
1854  int findSol = noOfSolutions;
1855  FlatZincSpace* sol = NULL;
1856  while (FlatZincSpace* next_sol = se.next()) {
1857  delete sol;
1858  sol = next_sol;
1859  if (printAll) {
1860  sol->print(out, p);
1861  out << "----------" << std::endl;
1862  }
1863  if (--findSol==0)
1864  goto stopped;
1865  }
1866  if (sol && !printAll) {
1867  sol->print(out, p);
1868  out << "----------" << std::endl;
1869  }
1870  if (!se.stopped()) {
1871  if (sol) {
1872  out << "==========" << std::endl;
1873  } else {
1874  out << "=====UNSATISFIABLE=====" << std::endl;
1875  }
1876  } else if (!sol) {
1877  out << "=====UNKNOWN=====" << std::endl;
1878  }
1879  delete sol;
1880  stopped:
1881  if (opt.interrupt())
1883  if (opt.mode() == SM_STAT) {
1884  Gecode::Search::Statistics stat = se.statistics();
1885  out << std::endl
1886  << "%% runtime: ";
1887  Driver::stop(t_total,out);
1888  out << std::endl
1889  << "%% solvetime: ";
1890  Driver::stop(t_solve,out);
1891  out << std::endl
1892  << "%% solutions: "
1893  << std::abs(noOfSolutions - findSol) << std::endl
1894  << "%% variables: "
1895  << (intVarCount + boolVarCount + setVarCount) << std::endl
1896  << "%% propagators: " << n_p << std::endl
1897  << "%% propagations: " << sstat.propagate+stat.propagate << std::endl
1898  << "%% nodes: " << stat.node << std::endl
1899  << "%% failures: " << stat.fail << std::endl
1900  << "%% restarts: " << stat.restart << std::endl
1901  << "%% peak depth: " << stat.depth << std::endl
1902  << std::endl;
1903  }
1904  delete o.stop;
1905  delete o.tracer;
1906  }
1907 
1908 #ifdef GECODE_HAS_QT
1909  void
1910  FlatZincSpace::branchWithPlugin(AST::Node* ann) {
1911  if (AST::Call* c = dynamic_cast<AST::Call*>(ann)) {
1912  QString pluginName(c->id.c_str());
1913  if (QLibrary::isLibrary(pluginName+".dll")) {
1914  pluginName += ".dll";
1915  } else if (QLibrary::isLibrary(pluginName+".dylib")) {
1916  pluginName = "lib" + pluginName + ".dylib";
1917  } else if (QLibrary::isLibrary(pluginName+".so")) {
1918  // Must check .so after .dylib so that Mac OS uses .dylib
1919  pluginName = "lib" + pluginName + ".so";
1920  }
1921  QPluginLoader pl(pluginName);
1922  QObject* plugin_o = pl.instance();
1923  if (!plugin_o) {
1924  throw FlatZinc::Error("FlatZinc",
1925  "Error loading plugin "+pluginName.toStdString()+
1926  ": "+pl.errorString().toStdString());
1927  }
1928  BranchPlugin* pb = qobject_cast<BranchPlugin*>(plugin_o);
1929  if (!pb) {
1930  throw FlatZinc::Error("FlatZinc",
1931  "Error loading plugin "+pluginName.toStdString()+
1932  ": does not contain valid PluginBrancher");
1933  }
1934  pb->branch(*this, c);
1935  }
1936  }
1937 #else
1938  void
1939  FlatZincSpace::branchWithPlugin(AST::Node*) {
1940  throw FlatZinc::Error("FlatZinc",
1941  "Branching with plugins not supported (requires Qt support)");
1942  }
1943 #endif
1944 
1945  void
1946  FlatZincSpace::run(std::ostream& out, const Printer& p,
1947  const FlatZincOptions& opt, Support::Timer& t_total) {
1948  switch (_method) {
1949  case MIN:
1950  case MAX:
1951  runEngine<BAB>(out,p,opt,t_total);
1952  break;
1953  case SAT:
1954  runEngine<DFS>(out,p,opt,t_total);
1955  break;
1956  }
1957  }
1958 
1959  void
1961  if (_optVarIsInt) {
1962  if (_method == MIN)
1963  rel(*this, iv[_optVar], IRT_LE,
1964  static_cast<const FlatZincSpace*>(&s)->iv[_optVar].val());
1965  else if (_method == MAX)
1966  rel(*this, iv[_optVar], IRT_GR,
1967  static_cast<const FlatZincSpace*>(&s)->iv[_optVar].val());
1968  } else {
1969 #ifdef GECODE_HAS_FLOAT_VARS
1970  if (_method == MIN)
1971  rel(*this, fv[_optVar], FRT_LE,
1972  static_cast<const FlatZincSpace*>(&s)->fv[_optVar].val()-step);
1973  else if (_method == MAX)
1974  rel(*this, fv[_optVar], FRT_GR,
1975  static_cast<const FlatZincSpace*>(&s)->fv[_optVar].val()+step);
1976 #endif
1977  }
1978  }
1979 
1980  bool
1982  if ((mi.type() == MetaInfo::RESTART) && (mi.restart() != 0) &&
1983  (_lns > 0) && (mi.last()==NULL) && (_lnsInitialSolution.size()>0)) {
1984  for (unsigned int i=iv_lns.size(); i--;) {
1985  if (_random(99) <= _lns) {
1986  rel(*this, iv_lns[i], IRT_EQ, _lnsInitialSolution[i]);
1987  }
1988  }
1989  return false;
1990  } else if ((mi.type() == MetaInfo::RESTART) && (mi.restart() != 0) &&
1991  (_lns > 0) && mi.last()) {
1992  const FlatZincSpace& last =
1993  static_cast<const FlatZincSpace&>(*mi.last());
1994  for (unsigned int i=iv_lns.size(); i--;) {
1995  if (_random(99) <= _lns) {
1996  rel(*this, iv_lns[i], IRT_EQ, last.iv_lns[i]);
1997  }
1998  }
1999  return false;
2000  }
2001  return true;
2002  }
2003 
2004  Space*
2006  return new FlatZincSpace(*this);
2007  }
2008 
2011  return _method;
2012  }
2013 
2014  int
2016  return _optVar;
2017  }
2018 
2019  bool
2021  return _optVarIsInt;
2022  }
2023 
2024  void
2025  FlatZincSpace::print(std::ostream& out, const Printer& p) const {
2026  p.print(out, iv, bv
2027 #ifdef GECODE_HAS_SET_VARS
2028  , sv
2029 #endif
2030 #ifdef GECODE_HAS_FLOAT_VARS
2031  , fv
2032 #endif
2033  );
2034  }
2035 
2036  void
2037  FlatZincSpace::compare(const Space& s, std::ostream& out) const {
2038  (void) s; (void) out;
2039 #ifdef GECODE_HAS_GIST
2040  const FlatZincSpace& fs = dynamic_cast<const FlatZincSpace&>(s);
2041  for (int i = 0; i < iv.size(); ++i) {
2042  std::stringstream ss;
2043  ss << "iv[" << i << "]";
2044  std::string result(Gecode::Gist::Comparator::compare(ss.str(), iv[i],
2045  fs.iv[i]));
2046  if (result.length() > 0) out << result << std::endl;
2047  }
2048  for (int i = 0; i < bv.size(); ++i) {
2049  std::stringstream ss;
2050  ss << "bv[" << i << "]";
2051  std::string result(Gecode::Gist::Comparator::compare(ss.str(), bv[i],
2052  fs.bv[i]));
2053  if (result.length() > 0) out << result << std::endl;
2054  }
2055 #ifdef GECODE_HAS_SET_VARS
2056  for (int i = 0; i < sv.size(); ++i) {
2057  std::stringstream ss;
2058  ss << "sv[" << i << "]";
2059  std::string result(Gecode::Gist::Comparator::compare(ss.str(), sv[i],
2060  fs.sv[i]));
2061  if (result.length() > 0) out << result << std::endl;
2062  }
2063 #endif
2064 #ifdef GECODE_HAS_FLOAT_VARS
2065  for (int i = 0; i < fv.size(); ++i) {
2066  std::stringstream ss;
2067  ss << "fv[" << i << "]";
2068  std::string result(Gecode::Gist::Comparator::compare(ss.str(), fv[i],
2069  fs.fv[i]));
2070  if (result.length() > 0) out << result << std::endl;
2071  }
2072 #endif
2073 #endif
2074  }
2075 
2076  void
2077  FlatZincSpace::compare(const FlatZincSpace& s, std::ostream& out,
2078  const Printer& p) const {
2079  p.printDiff(out, iv, s.iv, bv, s.bv
2080 #ifdef GECODE_HAS_SET_VARS
2081  , sv, s.sv
2082 #endif
2083 #ifdef GECODE_HAS_FLOAT_VARS
2084  , fv, s.fv
2085 #endif
2086  );
2087  }
2088 
2089  void
2091  p.shrinkArrays(*this, _optVar, _optVarIsInt, iv, bv
2092 #ifdef GECODE_HAS_SET_VARS
2093  , sv
2094 #endif
2095 #ifdef GECODE_HAS_FLOAT_VARS
2096  , fv
2097 #endif
2098  );
2099  }
2100 
2101  IntArgs
2103  AST::Array* a = arg->getArray();
2104  IntArgs ia(a->a.size()+offset);
2105  for (int i=offset; i--;)
2106  ia[i] = 0;
2107  for (int i=a->a.size(); i--;)
2108  ia[i+offset] = a->a[i]->getInt();
2109  return ia;
2110  }
2111  TupleSet
2113  AST::Array* a = arg->getArray();
2114  int noOfTuples = a->a.size() == 0 ? 0 : (a->a.size()/noOfVars);
2115 
2116  // Build TupleSet
2117  TupleSet ts(noOfVars);
2118  for (int i=0; i<noOfTuples; i++) {
2119  IntArgs t(noOfVars);
2120  for (int j=0; j<noOfVars; j++) {
2121  t[j] = a->a[i*noOfVars+j]->getInt();
2122  }
2123  ts.add(t);
2124  }
2125  ts.finalize();
2126 
2127  if (_initData) {
2128  FlatZincSpaceInitData::TupleSetSet::iterator it = _initData->tupleSetSet.find(ts);
2129  if (it != _initData->tupleSetSet.end()) {
2130  return *it;
2131  }
2132  _initData->tupleSetSet.insert(ts);
2133  }
2134 
2135 
2136  return ts;
2137  }
2140  IntArgs ia(arg2intargs(arg,offset));
2141  SharedArray<int> sia(ia);
2142  if (_initData) {
2143  FlatZincSpaceInitData::IntSharedArraySet::iterator it = _initData->intSharedArraySet.find(sia);
2144  if (it != _initData->intSharedArraySet.end()) {
2145  return *it;
2146  }
2147  _initData->intSharedArraySet.insert(sia);
2148  }
2149 
2150  return sia;
2151  }
2152  IntArgs
2154  AST::Array* a = arg->getArray();
2155  IntArgs ia(a->a.size()+offset);
2156  for (int i=offset; i--;)
2157  ia[i] = 0;
2158  for (int i=a->a.size(); i--;)
2159  ia[i+offset] = a->a[i]->getBool();
2160  return ia;
2161  }
2164  IntArgs ia(arg2boolargs(arg,offset));
2165  SharedArray<int> sia(ia);
2166  if (_initData) {
2167  FlatZincSpaceInitData::IntSharedArraySet::iterator it = _initData->intSharedArraySet.find(sia);
2168  if (it != _initData->intSharedArraySet.end()) {
2169  return *it;
2170  }
2171  _initData->intSharedArraySet.insert(sia);
2172  }
2173 
2174  return sia;
2175  }
2176  IntSet
2178  AST::SetLit* sl = n->getSet();
2179  IntSet d;
2180  if (sl->interval) {
2181  d = IntSet(sl->min, sl->max);
2182  } else {
2183  Region re;
2184  int* is = re.alloc<int>(static_cast<unsigned long int>(sl->s.size()));
2185  for (int i=sl->s.size(); i--; )
2186  is[i] = sl->s[i];
2187  d = IntSet(is, sl->s.size());
2188  }
2189  return d;
2190  }
2191  IntSetArgs
2193  AST::Array* a = arg->getArray();
2194  if (a->a.size() == 0) {
2195  IntSetArgs emptyIa(0);
2196  return emptyIa;
2197  }
2198  IntSetArgs ia(a->a.size()+offset);
2199  for (int i=offset; i--;)
2200  ia[i] = IntSet::empty;
2201  for (int i=a->a.size(); i--;) {
2202  ia[i+offset] = arg2intset(a->a[i]);
2203  }
2204  return ia;
2205  }
2206  IntVarArgs
2208  AST::Array* a = arg->getArray();
2209  if (a->a.size() == 0) {
2210  IntVarArgs emptyIa(0);
2211  return emptyIa;
2212  }
2213  IntVarArgs ia(a->a.size()+offset);
2214  for (int i=offset; i--;)
2215  ia[i] = IntVar(*this, 0, 0);
2216  for (int i=a->a.size(); i--;) {
2217  if (a->a[i]->isIntVar()) {
2218  ia[i+offset] = iv[a->a[i]->getIntVar()];
2219  } else {
2220  int value = a->a[i]->getInt();
2221  IntVar iv(*this, value, value);
2222  ia[i+offset] = iv;
2223  }
2224  }
2225  return ia;
2226  }
2227  BoolVarArgs
2228  FlatZincSpace::arg2boolvarargs(AST::Node* arg, int offset, int siv) {
2229  AST::Array* a = arg->getArray();
2230  if (a->a.size() == 0) {
2231  BoolVarArgs emptyIa(0);
2232  return emptyIa;
2233  }
2234  BoolVarArgs ia(a->a.size()+offset-(siv==-1?0:1));
2235  for (int i=offset; i--;)
2236  ia[i] = BoolVar(*this, 0, 0);
2237  for (int i=0; i<static_cast<int>(a->a.size()); i++) {
2238  if (i==siv)
2239  continue;
2240  if (a->a[i]->isBool()) {
2241  bool value = a->a[i]->getBool();
2242  BoolVar iv(*this, value, value);
2243  ia[offset++] = iv;
2244  } else if (a->a[i]->isIntVar() &&
2245  aliasBool2Int(a->a[i]->getIntVar()) != -1) {
2246  ia[offset++] = bv[aliasBool2Int(a->a[i]->getIntVar())];
2247  } else {
2248  ia[offset++] = bv[a->a[i]->getBoolVar()];
2249  }
2250  }
2251  return ia;
2252  }
2253  BoolVar
2255  BoolVar x0;
2256  if (n->isBool()) {
2257  x0 = BoolVar(*this, n->getBool(), n->getBool());
2258  }
2259  else {
2260  x0 = bv[n->getBoolVar()];
2261  }
2262  return x0;
2263  }
2264  IntVar
2266  IntVar x0;
2267  if (n->isIntVar()) {
2268  x0 = iv[n->getIntVar()];
2269  } else {
2270  x0 = IntVar(*this, n->getInt(), n->getInt());
2271  }
2272  return x0;
2273  }
2274  bool
2276  AST::Array* a = b->getArray();
2277  singleInt = -1;
2278  if (a->a.size() == 0)
2279  return true;
2280  for (int i=a->a.size(); i--;) {
2281  if (a->a[i]->isBoolVar() || a->a[i]->isBool()) {
2282  } else if (a->a[i]->isIntVar()) {
2283  if (aliasBool2Int(a->a[i]->getIntVar()) == -1) {
2284  if (singleInt != -1) {
2285  return false;
2286  }
2287  singleInt = i;
2288  }
2289  } else {
2290  return false;
2291  }
2292  }
2293  return singleInt==-1 || a->a.size() > 1;
2294  }
2295 #ifdef GECODE_HAS_SET_VARS
2296  SetVar
2298  SetVar x0;
2299  if (!n->isSetVar()) {
2300  IntSet d = arg2intset(n);
2301  x0 = SetVar(*this, d, d);
2302  } else {
2303  x0 = sv[n->getSetVar()];
2304  }
2305  return x0;
2306  }
2307  SetVarArgs
2308  FlatZincSpace::arg2setvarargs(AST::Node* arg, int offset, int doffset,
2309  const IntSet& od) {
2310  AST::Array* a = arg->getArray();
2311  SetVarArgs ia(a->a.size()+offset);
2312  for (int i=offset; i--;) {
2313  IntSet d = i<doffset ? od : IntSet::empty;
2314  ia[i] = SetVar(*this, d, d);
2315  }
2316  for (int i=a->a.size(); i--;) {
2317  ia[i+offset] = arg2SetVar(a->a[i]);
2318  }
2319  return ia;
2320  }
2321 #endif
2322 #ifdef GECODE_HAS_FLOAT_VARS
2323  FloatValArgs
2325  AST::Array* a = arg->getArray();
2326  FloatValArgs fa(a->a.size()+offset);
2327  for (int i=offset; i--;)
2328  fa[i] = 0.0;
2329  for (int i=a->a.size(); i--;)
2330  fa[i+offset] = a->a[i]->getFloat();
2331  return fa;
2332  }
2333  FloatVarArgs
2335  AST::Array* a = arg->getArray();
2336  if (a->a.size() == 0) {
2337  FloatVarArgs emptyFa(0);
2338  return emptyFa;
2339  }
2340  FloatVarArgs fa(a->a.size()+offset);
2341  for (int i=offset; i--;)
2342  fa[i] = FloatVar(*this, 0.0, 0.0);
2343  for (int i=a->a.size(); i--;) {
2344  if (a->a[i]->isFloatVar()) {
2345  fa[i+offset] = fv[a->a[i]->getFloatVar()];
2346  } else {
2347  double value = a->a[i]->getFloat();
2348  FloatVar fv(*this, value, value);
2349  fa[i+offset] = fv;
2350  }
2351  }
2352  return fa;
2353  }
2354  FloatVar
2356  FloatVar x0;
2357  if (n->isFloatVar()) {
2358  x0 = fv[n->getFloatVar()];
2359  } else {
2360  x0 = FloatVar(*this, n->getFloat(), n->getFloat());
2361  }
2362  return x0;
2363  }
2364 #endif
2365  IntPropLevel
2367  if (ann) {
2368  if (ann->hasAtom("val"))
2369  return IPL_VAL;
2370  if (ann->hasAtom("domain"))
2371  return IPL_DOM;
2372  if (ann->hasAtom("bounds") ||
2373  ann->hasAtom("boundsR") ||
2374  ann->hasAtom("boundsD") ||
2375  ann->hasAtom("boundsZ"))
2376  return IPL_BND;
2377  }
2378  return IPL_DEF;
2379  }
2380 
2381  DFA
2383  if (_initData) {
2384  FlatZincSpaceInitData::DFASet::iterator it = _initData->dfaSet.find(a);
2385  if (it != _initData->dfaSet.end()) {
2386  return *it;
2387  }
2388  _initData->dfaSet.insert(a);
2389  }
2390  return a;
2391  }
2392 
2393  void
2395  _output = output;
2396  }
2397 
2398  void
2399  Printer::printElem(std::ostream& out,
2400  AST::Node* ai,
2401  const Gecode::IntVarArray& iv,
2402  const Gecode::BoolVarArray& bv
2403 #ifdef GECODE_HAS_SET_VARS
2404  , const Gecode::SetVarArray& sv
2405 #endif
2406 #ifdef GECODE_HAS_FLOAT_VARS
2407  ,
2408  const Gecode::FloatVarArray& fv
2409 #endif
2410  ) const {
2411  int k;
2412  if (ai->isInt(k)) {
2413  out << k;
2414  } else if (ai->isIntVar()) {
2415  out << iv[ai->getIntVar()];
2416  } else if (ai->isBoolVar()) {
2417  if (bv[ai->getBoolVar()].min() == 1) {
2418  out << "true";
2419  } else if (bv[ai->getBoolVar()].max() == 0) {
2420  out << "false";
2421  } else {
2422  out << "false..true";
2423  }
2424 #ifdef GECODE_HAS_SET_VARS
2425  } else if (ai->isSetVar()) {
2426  if (!sv[ai->getSetVar()].assigned()) {
2427  out << sv[ai->getSetVar()];
2428  return;
2429  }
2430  SetVarGlbRanges svr(sv[ai->getSetVar()]);
2431  if (!svr()) {
2432  out << "{}";
2433  return;
2434  }
2435  int min = svr.min();
2436  int max = svr.max();
2437  ++svr;
2438  if (svr()) {
2439  SetVarGlbValues svv(sv[ai->getSetVar()]);
2440  int i = svv.val();
2441  out << "{" << i;
2442  ++svv;
2443  for (; svv(); ++svv)
2444  out << ", " << svv.val();
2445  out << "}";
2446  } else {
2447  out << min << ".." << max;
2448  }
2449 #endif
2450 #ifdef GECODE_HAS_FLOAT_VARS
2451  } else if (ai->isFloatVar()) {
2452  if (fv[ai->getFloatVar()].assigned()) {
2453  FloatVal vv = fv[ai->getFloatVar()].val();
2454  FloatNum v;
2455  if (vv.singleton())
2456  v = vv.min();
2457  else if (vv < 0.0)
2458  v = vv.max();
2459  else
2460  v = vv.min();
2461  std::ostringstream oss;
2462  // oss << std::scientific;
2463  oss << std::setprecision(std::numeric_limits<double>::digits10);
2464  oss << v;
2465  if (oss.str().find(".") == std::string::npos)
2466  oss << ".0";
2467  out << oss.str();
2468  } else {
2469  out << fv[ai->getFloatVar()];
2470  }
2471 #endif
2472  } else if (ai->isBool()) {
2473  out << (ai->getBool() ? "true" : "false");
2474  } else if (ai->isSet()) {
2475  AST::SetLit* s = ai->getSet();
2476  if (s->interval) {
2477  out << s->min << ".." << s->max;
2478  } else {
2479  out << "{";
2480  for (unsigned int i=0; i<s->s.size(); i++) {
2481  out << s->s[i] << (i < s->s.size()-1 ? ", " : "}");
2482  }
2483  }
2484  } else if (ai->isString()) {
2485  std::string s = ai->getString();
2486  for (unsigned int i=0; i<s.size(); i++) {
2487  if (s[i] == '\\' && i<s.size()-1) {
2488  switch (s[i+1]) {
2489  case 'n': out << "\n"; break;
2490  case '\\': out << "\\"; break;
2491  case 't': out << "\t"; break;
2492  default: out << "\\" << s[i+1];
2493  }
2494  i++;
2495  } else {
2496  out << s[i];
2497  }
2498  }
2499  }
2500  }
2501 
2502  void
2503  Printer::printElemDiff(std::ostream& out,
2504  AST::Node* ai,
2505  const Gecode::IntVarArray& iv1,
2506  const Gecode::IntVarArray& iv2,
2507  const Gecode::BoolVarArray& bv1,
2508  const Gecode::BoolVarArray& bv2
2509 #ifdef GECODE_HAS_SET_VARS
2510  , const Gecode::SetVarArray& sv1,
2511  const Gecode::SetVarArray& sv2
2512 #endif
2513 #ifdef GECODE_HAS_FLOAT_VARS
2514  , const Gecode::FloatVarArray& fv1,
2515  const Gecode::FloatVarArray& fv2
2516 #endif
2517  ) const {
2518 #ifdef GECODE_HAS_GIST
2519  using namespace Gecode::Gist;
2520  int k;
2521  if (ai->isInt(k)) {
2522  out << k;
2523  } else if (ai->isIntVar()) {
2524  std::string res(Comparator::compare("",iv1[ai->getIntVar()],
2525  iv2[ai->getIntVar()]));
2526  if (res.length() > 0) {
2527  res.erase(0, 1); // Remove '='
2528  out << res;
2529  } else {
2530  out << iv1[ai->getIntVar()];
2531  }
2532  } else if (ai->isBoolVar()) {
2533  std::string res(Comparator::compare("",bv1[ai->getBoolVar()],
2534  bv2[ai->getBoolVar()]));
2535  if (res.length() > 0) {
2536  res.erase(0, 1); // Remove '='
2537  out << res;
2538  } else {
2539  out << bv1[ai->getBoolVar()];
2540  }
2541 #ifdef GECODE_HAS_SET_VARS
2542  } else if (ai->isSetVar()) {
2543  std::string res(Comparator::compare("",sv1[ai->getSetVar()],
2544  sv2[ai->getSetVar()]));
2545  if (res.length() > 0) {
2546  res.erase(0, 1); // Remove '='
2547  out << res;
2548  } else {
2549  out << sv1[ai->getSetVar()];
2550  }
2551 #endif
2552 #ifdef GECODE_HAS_FLOAT_VARS
2553  } else if (ai->isFloatVar()) {
2554  std::string res(Comparator::compare("",fv1[ai->getFloatVar()],
2555  fv2[ai->getFloatVar()]));
2556  if (res.length() > 0) {
2557  res.erase(0, 1); // Remove '='
2558  out << res;
2559  } else {
2560  out << fv1[ai->getFloatVar()];
2561  }
2562 #endif
2563  } else if (ai->isBool()) {
2564  out << (ai->getBool() ? "true" : "false");
2565  } else if (ai->isSet()) {
2566  AST::SetLit* s = ai->getSet();
2567  if (s->interval) {
2568  out << s->min << ".." << s->max;
2569  } else {
2570  out << "{";
2571  for (unsigned int i=0; i<s->s.size(); i++) {
2572  out << s->s[i] << (i < s->s.size()-1 ? ", " : "}");
2573  }
2574  }
2575  } else if (ai->isString()) {
2576  std::string s = ai->getString();
2577  for (unsigned int i=0; i<s.size(); i++) {
2578  if (s[i] == '\\' && i<s.size()-1) {
2579  switch (s[i+1]) {
2580  case 'n': out << "\n"; break;
2581  case '\\': out << "\\"; break;
2582  case 't': out << "\t"; break;
2583  default: out << "\\" << s[i+1];
2584  }
2585  i++;
2586  } else {
2587  out << s[i];
2588  }
2589  }
2590  }
2591 #else
2592  (void) out;
2593  (void) ai;
2594  (void) iv1;
2595  (void) iv2;
2596  (void) bv1;
2597  (void) bv2;
2598 #ifdef GECODE_HAS_SET_VARS
2599  (void) sv1;
2600  (void) sv2;
2601 #endif
2602 #ifdef GECODE_HAS_FLOAT_VARS
2603  (void) fv1;
2604  (void) fv2;
2605 #endif
2606 
2607 #endif
2608  }
2609 
2610  void
2611  Printer::print(std::ostream& out,
2612  const Gecode::IntVarArray& iv,
2613  const Gecode::BoolVarArray& bv
2614 #ifdef GECODE_HAS_SET_VARS
2615  ,
2616  const Gecode::SetVarArray& sv
2617 #endif
2618 #ifdef GECODE_HAS_FLOAT_VARS
2619  ,
2620  const Gecode::FloatVarArray& fv
2621 #endif
2622  ) const {
2623  if (_output == NULL)
2624  return;
2625  for (unsigned int i=0; i< _output->a.size(); i++) {
2626  AST::Node* ai = _output->a[i];
2627  if (ai->isArray()) {
2628  AST::Array* aia = ai->getArray();
2629  int size = aia->a.size();
2630  out << "[";
2631  for (int j=0; j<size; j++) {
2632  printElem(out,aia->a[j],iv,bv
2633 #ifdef GECODE_HAS_SET_VARS
2634  ,sv
2635 #endif
2636 #ifdef GECODE_HAS_FLOAT_VARS
2637  ,fv
2638 #endif
2639  );
2640  if (j<size-1)
2641  out << ", ";
2642  }
2643  out << "]";
2644  } else {
2645  printElem(out,ai,iv,bv
2646 #ifdef GECODE_HAS_SET_VARS
2647  ,sv
2648 #endif
2649 #ifdef GECODE_HAS_FLOAT_VARS
2650  ,fv
2651 #endif
2652  );
2653  }
2654  }
2655  }
2656 
2657  void
2658  Printer::printDiff(std::ostream& out,
2659  const Gecode::IntVarArray& iv1,
2660  const Gecode::IntVarArray& iv2,
2661  const Gecode::BoolVarArray& bv1,
2662  const Gecode::BoolVarArray& bv2
2663 #ifdef GECODE_HAS_SET_VARS
2664  ,
2665  const Gecode::SetVarArray& sv1,
2666  const Gecode::SetVarArray& sv2
2667 #endif
2668 #ifdef GECODE_HAS_FLOAT_VARS
2669  ,
2670  const Gecode::FloatVarArray& fv1,
2671  const Gecode::FloatVarArray& fv2
2672 #endif
2673  ) const {
2674  if (_output == NULL)
2675  return;
2676  for (unsigned int i=0; i< _output->a.size(); i++) {
2677  AST::Node* ai = _output->a[i];
2678  if (ai->isArray()) {
2679  AST::Array* aia = ai->getArray();
2680  int size = aia->a.size();
2681  out << "[";
2682  for (int j=0; j<size; j++) {
2683  printElemDiff(out,aia->a[j],iv1,iv2,bv1,bv2
2684 #ifdef GECODE_HAS_SET_VARS
2685  ,sv1,sv2
2686 #endif
2687 #ifdef GECODE_HAS_FLOAT_VARS
2688  ,fv1,fv2
2689 #endif
2690  );
2691  if (j<size-1)
2692  out << ", ";
2693  }
2694  out << "]";
2695  } else {
2696  printElemDiff(out,ai,iv1,iv2,bv1,bv2
2697 #ifdef GECODE_HAS_SET_VARS
2698  ,sv1,sv2
2699 #endif
2700 #ifdef GECODE_HAS_FLOAT_VARS
2701  ,fv1,fv2
2702 #endif
2703  );
2704  }
2705  }
2706  }
2707 
2708  void
2709  Printer::addIntVarName(const std::string& n) {
2710  iv_names.push_back(n);
2711  }
2712  void
2713  Printer::addBoolVarName(const std::string& n) {
2714  bv_names.push_back(n);
2715  }
2716 #ifdef GECODE_HAS_FLOAT_VARS
2717  void
2718  Printer::addFloatVarName(const std::string& n) {
2719  fv_names.push_back(n);
2720  }
2721 #endif
2722 #ifdef GECODE_HAS_SET_VARS
2723  void
2724  Printer::addSetVarName(const std::string& n) {
2725  sv_names.push_back(n);
2726  }
2727 #endif
2728 
2729  void
2731  std::map<int,int>& iv, std::map<int,int>& bv,
2732  std::map<int,int>& sv, std::map<int,int>& fv) {
2733  if (node->isIntVar()) {
2734  AST::IntVar* x = static_cast<AST::IntVar*>(node);
2735  if (iv.find(x->i) == iv.end()) {
2736  int newi = iv.size();
2737  iv[x->i] = newi;
2738  }
2739  x->i = iv[x->i];
2740  } else if (node->isBoolVar()) {
2741  AST::BoolVar* x = static_cast<AST::BoolVar*>(node);
2742  if (bv.find(x->i) == bv.end()) {
2743  int newi = bv.size();
2744  bv[x->i] = newi;
2745  }
2746  x->i = bv[x->i];
2747  } else if (node->isSetVar()) {
2748  AST::SetVar* x = static_cast<AST::SetVar*>(node);
2749  if (sv.find(x->i) == sv.end()) {
2750  int newi = sv.size();
2751  sv[x->i] = newi;
2752  }
2753  x->i = sv[x->i];
2754  } else if (node->isFloatVar()) {
2755  AST::FloatVar* x = static_cast<AST::FloatVar*>(node);
2756  if (fv.find(x->i) == fv.end()) {
2757  int newi = fv.size();
2758  fv[x->i] = newi;
2759  }
2760  x->i = fv[x->i];
2761  }
2762  }
2763 
2764  void
2766  int& optVar, bool optVarIsInt,
2767  Gecode::IntVarArray& iv,
2769 #ifdef GECODE_HAS_SET_VARS
2770  ,
2772 #endif
2773 #ifdef GECODE_HAS_FLOAT_VARS
2774  ,
2776 #endif
2777  ) {
2778  if (_output == NULL) {
2779  if (optVarIsInt && optVar != -1) {
2780  IntVar ov = iv[optVar];
2781  iv = IntVarArray(home, 1);
2782  iv[0] = ov;
2783  optVar = 0;
2784  } else {
2785  iv = IntVarArray(home, 0);
2786  }
2787  bv = BoolVarArray(home, 0);
2788 #ifdef GECODE_HAS_SET_VARS
2789  sv = SetVarArray(home, 0);
2790 #endif
2791 #ifdef GECODE_HAS_FLOAT_VARS
2792  if (!optVarIsInt && optVar != -1) {
2793  FloatVar ov = fv[optVar];
2794  fv = FloatVarArray(home, 1);
2795  fv[0] = ov;
2796  optVar = 0;
2797  } else {
2798  fv = FloatVarArray(home,0);
2799  }
2800 #endif
2801  return;
2802  }
2803  std::map<int,int> iv_new;
2804  std::map<int,int> bv_new;
2805  std::map<int,int> sv_new;
2806  std::map<int,int> fv_new;
2807 
2808  if (optVar != -1) {
2809  if (optVarIsInt)
2810  iv_new[optVar] = 0;
2811  else
2812  fv_new[optVar] = 0;
2813  optVar = 0;
2814  }
2815 
2816  for (unsigned int i=0; i< _output->a.size(); i++) {
2817  AST::Node* ai = _output->a[i];
2818  if (ai->isArray()) {
2819  AST::Array* aia = ai->getArray();
2820  for (unsigned int j=0; j<aia->a.size(); j++) {
2821  shrinkElement(aia->a[j],iv_new,bv_new,sv_new,fv_new);
2822  }
2823  } else {
2824  shrinkElement(ai,iv_new,bv_new,sv_new,fv_new);
2825  }
2826  }
2827 
2828  IntVarArgs iva(iv_new.size());
2829  for (std::map<int,int>::iterator i=iv_new.begin(); i != iv_new.end(); ++i) {
2830  iva[(*i).second] = iv[(*i).first];
2831  }
2832  iv = IntVarArray(home, iva);
2833 
2834  BoolVarArgs bva(bv_new.size());
2835  for (std::map<int,int>::iterator i=bv_new.begin(); i != bv_new.end(); ++i) {
2836  bva[(*i).second] = bv[(*i).first];
2837  }
2838  bv = BoolVarArray(home, bva);
2839 
2840 #ifdef GECODE_HAS_SET_VARS
2841  SetVarArgs sva(sv_new.size());
2842  for (std::map<int,int>::iterator i=sv_new.begin(); i != sv_new.end(); ++i) {
2843  sva[(*i).second] = sv[(*i).first];
2844  }
2845  sv = SetVarArray(home, sva);
2846 #endif
2847 
2848 #ifdef GECODE_HAS_FLOAT_VARS
2849  FloatVarArgs fva(fv_new.size());
2850  for (std::map<int,int>::iterator i=fv_new.begin(); i != fv_new.end(); ++i) {
2851  fva[(*i).second] = fv[(*i).first];
2852  }
2853  fv = FloatVarArray(home, fva);
2854 #endif
2855  }
2856 
2858  delete _output;
2859  }
2860 
2861 }}
2862 
2863 // STATISTICS: flatzinc-any
void click(Inspector *i)
Add inspector that reacts on node double clicks.
Definition: gist.hpp:174
void shrinkArrays(Printer &p)
Remove all variables not needed for output.
Definition: flatzinc.cpp:2090
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:757
BoolValBranch BOOL_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:144
Bounds propagation.
Definition: int.hh:957
Which values to select for branching first.
Definition: set.hh:1449
Gecode::SetVarArray sv_aux
The introduced set variables.
Definition: flatzinc.hh:500
int floatVarCount
Number of float variables.
Definition: flatzinc.hh:437
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
const Gecode::FloatNum step
Definition: arithmetic.cpp:789
Passing float arguments.
Definition: float.hh:954
Option< AST::SetLit *> domain
Definition: varspec.hh:78
Options for running FlatZinc models
Definition: flatzinc.hh:230
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl)
Definition: var.hpp:210
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:765
virtual Choice * choice(Space &home)
Return choice.
Definition: flatzinc.cpp:193
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:100
RestartMode restart(void) const
Definition: flatzinc.hh:368
Combine variable selection criteria for tie-breaking.
Definition: tiebreak.hpp:42
IntSet vs2is(IntVarSpec *vs)
Definition: flatzinc.cpp:360
virtual void print(const Space &, const Gecode::Choice &c, unsigned int, std::ostream &o) const
Print explanation.
Definition: flatzinc.cpp:224
FlatZincGetInfo(const Printer &printer)
Definition: flatzinc.cpp:1729
Which values to select for branching first.
Definition: float.hh:1821
std::ostream & getStream(void)
Get the stream that is used to output text.
Definition: gist.cpp:89
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:368
The shared handle.
FloatNum med(void) const
Return median of domain (closest representation)
Definition: float.hpp:72
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:159
IntArgs arg2intargs(AST::Node *arg, int offset=0)
Convert arg (array of integers) to IntArgs.
Definition: flatzinc.cpp:2102
void post(FlatZincSpace &s, const ConExpr &ce)
Post constraint specified by ce.
Definition: registry.cpp:63
FloatValBranch FLOAT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition: val.hpp:64
void cmb_hash(std::size_t &seed, int h)
Combine hash value h into seed.
Definition: hash.hpp:56
BoolVarBranch BOOL_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:398
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
Traits class for search engines.
Definition: flatzinc.cpp:1617
Search engine statistics
Definition: search.hh:149
Boolean variable node.
Definition: ast.hh:201
const int min
Smallest allowed integer in integer set.
Definition: set.hh:103
FloatVarArgs arg2floatvarargs(AST::Node *arg, int offset=0)
Convert n to FloatVarArgs.
Definition: flatzinc.cpp:2334
bool isBool(void)
Test if node is a Boolean node.
Definition: ast.hh:494
BoolAssign BOOL_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:104
std::vector< bool > sv_introduced
Indicates whether a set variable is introduced by mzn2fzn.
Definition: flatzinc.hh:502
Class to send solution information to CPProfiler.
Definition: search.hh:425
void print(const Brancher &b, unsigned int a, int i, const FloatNumBranch &nl, std::ostream &o) const
Definition: flatzinc.cpp:302
Which values to select for branching first.
Definition: int.hh:4686
bool getBool(void)
Cast this node to a Boolean node.
Definition: ast.hh:450
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:973
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Gecode::BoolVarArray bv
The Boolean variables.
Definition: flatzinc.hh:491
size_t operator()(const Gecode::DFA &d) const
Return hash key for d.
Definition: flatzinc.cpp:82
void put(unsigned int i)
Add i to the contents.
Definition: archive.hpp:178
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1060
Meth _method
Whether to solve as satisfaction or optimization problem.
Definition: flatzinc.hh:447
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:755
FloatVarBranch FLOAT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:126
Cutoff generator appending two cutoff generators.
Definition: search.hh:638
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
SetValBranch ann2svalsel(AST::Node *ann, std::string r0, std::string r1, Rnd rnd)
Definition: flatzinc.cpp:663
Which values to select for branching first.
Definition: int.hh:4651
Search engine options
Definition: search.hh:748
SetLit * getSet(void)
Cast this node to a set literal node.
Definition: ast.hh:462
void newIntVar(IntVarSpec *vs)
Create new integer variable from specification.
Definition: flatzinc.cpp:885
IntVarBranch INT_VAR_SIZE_MAX(BranchTbl tbl)
Select variable with largest domain size.
Definition: var.hpp:215
Group of branchers.
Definition: core.hpp:789
Abstract base class for comparators.
Definition: gist.hh:123
Call * getCall(void)
Return function call.
Definition: ast.hh:347
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
int getFloatVar(void)
Cast this node to a Float variable node.
Definition: ast.hh:432
Gecode::ScriptMode mode(void) const
Definition: flatzinc.hh:363
Gecode::IntVarArray iv
The integer variables.
Definition: flatzinc.hh:479
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:45
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:779
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
IntAssign INT_ASSIGN_MED(void)
Select greatest value not greater than the median.
Definition: assign.hpp:64
Passing float variables.
Definition: float.hh:981
Specification for set variables.
Definition: varspec.hh:143
FloatVarBranch FLOAT_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smalllest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:231
virtual void compare(const Space &s0, const Space &s1)
Use the compare method of the template class S to compare two spaces.
Definition: flatzinc.cpp:1700
size_t operator()(const Gecode::SharedArray< int > &x) const
Return hash key for x.
Definition: flatzinc.cpp:71
BranchInformation branchInfo
Information for printing branches.
Definition: flatzinc.hh:602
void compare(const Space &s, std::ostream &out) const
Compare this space with space s and print the differences on out.
Definition: flatzinc.cpp:2037
int boolVarCount
Number of Boolean variables.
Definition: flatzinc.hh:435
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:125
BoolVarBranch BOOL_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:418
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1073
std::size_t hash(void) const
Return hash key.
Definition: dfa.hpp:193
IntVarBranch INT_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:130
bool singleton(void) const
Test whether float is a singleton.
Definition: val.hpp:96
AuxVarBrancher(Home home, TieBreak< IntVarBranch > int_varsel0, IntValBranch int_valsel0, TieBreak< BoolVarBranch > bool_varsel0, BoolValBranch bool_valsel0, SetVarBranch set_varsel0, SetValBranch set_valsel0, TieBreak< FloatVarBranch > float_varsel0, FloatValBranch float_valsel0)
Construct brancher.
Definition: flatzinc.cpp:111
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
bool optVarIsInt(void) const
Return whether variable used for optimization is integer (or float)
Definition: flatzinc.cpp:2020
Which values to select for assignment.
Definition: int.hh:4797
void minimize(int var, bool isInt, AST::Array *annotation)
Post that integer variable var should be minimized.
Definition: flatzinc.cpp:1591
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
bool isSetVar(void)
Test if node is a set variable node.
Definition: ast.hh:482
bool isBoolVar(void)
Test if node is a Boolean variable node.
Definition: ast.hh:478
virtual SharedHandle::Object * copy(void) const
Definition: flatzinc.cpp:284
std::vector< Node * > a
Definition: ast.hh:237
Information is provided by a restart-based engine.
Definition: core.hpp:1544
unsigned long int depth
Maximum depth of search stack.
Definition: search.hh:156
TieBreak< IntVarBranch > ann2ivarsel(AST::Node *ann, Rnd rnd, double decay)
Definition: flatzinc.cpp:404
Integer variable array.
Definition: int.hh:742
DFASet dfaSet
Hash table of DFAs.
Definition: flatzinc.cpp:772
bool profiler_info(void) const
Definition: flatzinc.hh:381
Definition: flatzinc.cpp:56
FloatValBranch ann2fvalsel(AST::Node *ann, std::string r0, std::string r1)
Definition: flatzinc.cpp:737
No restarts.
Definition: driver.hh:111
BoolAssign ann2asnbvalsel(AST::Node *ann, Rnd rnd)
Definition: flatzinc.cpp:607
Less ( )
Definition: float.hh:1073
BoolAssign BOOL_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:109
int vs2bsh(BoolVarSpec *bs)
Definition: flatzinc.cpp:392
IntVarBranch INT_VAR_REGRET_MIN_MAX(BranchTbl tbl)
Select variable with largest min-regret.
Definition: var.hpp:295
SetVarBranch SET_VAR_MAX_MAX(BranchTbl tbl)
Definition: var.hpp:205
void init(int intVars, int boolVars, int setVars, int floatVars)
Initialize space with given number of variables.
Definition: flatzinc.cpp:860
Handle to region.
Definition: region.hpp:57
Greater ( )
Definition: int.hh:910
static void explore(S *root, const FlatZincOptions &opt, Gist::Inspector *i, Gist::Comparator *c)
Definition: flatzinc.cpp:1624
BoolValBranch ann2bvalsel(AST::Node *ann, std::string &r0, std::string &r1, Rnd rnd)
Definition: flatzinc.cpp:556
Class to record search trace info for CPProfiler.
Definition: search.hh:422
void varValPrint(const Space &home, const Brancher &b, unsigned int a, Var, int i, const int &n, std::ostream &o)
Definition: flatzinc.cpp:344
void printIntVar(std::ostream &os, const std::string name, const Int::IntView &x)
Definition: flatzinc.cpp:1743
Meth method(void) const
Return whether to solve a satisfaction or optimization problem.
Definition: flatzinc.cpp:2010
void print(const Brancher &b, unsigned int a, int i, int n, std::ostream &o) const
Output branch information.
Definition: flatzinc.cpp:296
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1620
#define forceinline
Definition: config.hpp:182
Search::Cutoff * createCutoff(const Options &o)
Create cutoff object from options.
Definition: script.hpp:157
const int max
Largest allowed integer in integer set.
Definition: set.hh:101
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:100
Array * getArray(void)
Cast this node to an array node.
Definition: ast.hh:400
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4821
const int max
Largest allowed integer value.
Definition: int.hh:116
FloatVarBranch FLOAT_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest action divided by domain size with decay factor d.
Definition: var.hpp:251
Float variable array.
Definition: float.hh:1031
int vs2bsl(BoolVarSpec *bs)
Definition: flatzinc.cpp:380
Computation spaces.
Definition: core.hpp:1668
An inspector for printing simple text output.
Definition: flatzinc.cpp:1650
Abstract base class for inspectors.
Definition: gist.hh:103
FloatVarBranch FLOAT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:101
IntSharedArray arg2intsharedarray(AST::Node *arg, int offset=0)
Convert arg (array of integers) to IntSharedArray.
Definition: flatzinc.cpp:2139
unsigned int profiler_port(void) const
Definition: flatzinc.hh:380
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:920
const int min
Smallest allowed integer value.
Definition: int.hh:118
Base-class for both propagators and branchers.
Definition: core.hpp:620
virtual size_t size(void) const
Report size occupied.
Definition: flatzinc.cpp:149
Statistics for execution of status
Definition: core.hpp:1617
virtual Gecode::Space * copy(void)
Copy function.
Definition: flatzinc.cpp:2005
void newSetVar(SetVarSpec *vs)
Create new set variable from specification.
Definition: flatzinc.cpp:924
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
IntValBranch INT_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:74
virtual Choice * choice(const Space &, Archive &e)
Return choice.
Definition: flatzinc.cpp:215
std::vector< bool > iv_introduced
Indicates whether an integer variable is introduced by mzn2fzn.
Definition: flatzinc.hh:487
Gecode::IntSet d(v, 7)
IntVarBranch INT_VAR_MAX_MAX(BranchTbl tbl)
Select variable with largest max.
Definition: var.hpp:205
void newBoolVar(BoolVarSpec *vs)
Create new Boolean variable from specification.
Definition: flatzinc.cpp:912
const BoolInstr * bi[]
Definition: mm-bool.cpp:4173
IntSharedArray arg2boolsharedarray(AST::Node *arg, int offset=0)
Convert arg (array of integers) to IntSharedArray.
Definition: flatzinc.cpp:2163
bool alias
Whether the variable aliases another variable.
Definition: varspec.hh:63
SetVarBranch ann2svarsel(AST::Node *ann, Rnd rnd, double decay)
Definition: flatzinc.cpp:625
void start(void)
Start timer.
Definition: timer.hpp:70
DFA getSharedDFA(DFA &a)
Share DFA a if possible.
Definition: flatzinc.cpp:2382
SetVar arg2SetVar(AST::Node *n)
Convert n to SetVar.
Definition: flatzinc.cpp:2297
unsigned int nogoods_limit(void) const
Definition: flatzinc.hh:374
int getSetVar(void)
Cast this node to a set variable node.
Definition: ast.hh:438
double getFloat(void)
Cast this node to a Float node.
Definition: ast.hh:456
Gecode::FloatVal c(-8, 8)
std::size_t hash(void) const
Return hash key.
Definition: tuple-set.hpp:231
FloatVarBranch FLOAT_VAR_SIZE_MAX(BranchTbl tbl)
Select variable with largest domain size.
Definition: var.hpp:216
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:769
int optVar(void) const
Return index of variable used for optimization.
Definition: flatzinc.cpp:2015
double threads
Number of threads to use.
Definition: search.hh:753
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
size_t operator()(const Gecode::TupleSet &x) const
Return hash key for x.
Definition: flatzinc.cpp:62
SetVarBranch SET_VAR_AFC_MAX(double d, BranchTbl tbl)
Definition: var.hpp:140
Deterministic finite automaton (DFA)
Definition: int.hh:2027
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
IntVarBranch INT_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:160
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
Gecode::FloatVarArray fv
The float variables.
Definition: flatzinc.hh:506
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:134
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:240
Gecode::IntArgs i(4, 1, 2, 3, 4)
IntAssign ann2asnivalsel(AST::Node *ann, Rnd rnd)
Definition: flatzinc.cpp:504
Base-class for branchers.
Definition: core.hpp:1368
FloatNum n
The middle value for branching.
Definition: float.hh:1466
virtual bool status(const Space &_home) const
Check status of brancher, return true if alternatives left.
Definition: flatzinc.cpp:174
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:139
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3504
Equality ( )
Definition: int.hh:905
#define GECODE_HAS_SET_VARS
Definition: config.hpp:53
std::vector< bool > fv_introduced
Indicates whether a float variable is introduced by mzn2fzn.
Definition: flatzinc.hh:510
Options opt
The options.
Definition: test.cpp:101
IntPropLevel ann2ipl(AST::Node *ann)
Convert ann to integer propagation level.
Definition: flatzinc.cpp:2366
Option< std::pair< double, double > > domain
Definition: varspec.hh:125
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:207
IntAssign INT_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:74
Depth-first branch-and-bound search engine.
Definition: search.hh:1073
void createBranchers(Printer &p, AST::Node *ann, int seed, double decay, bool ignoreUnknown, std::ostream &err=std::cerr)
Create branchers corresponding to the solve item annotations.
Definition: flatzinc.cpp:1041
static void post(Home home, TieBreak< IntVarBranch > int_varsel, IntValBranch int_valsel, TieBreak< BoolVarBranch > bool_varsel, BoolValBranch bool_valsel, SetVarBranch set_varsel, SetValBranch set_valsel, TieBreak< FloatVarBranch > float_varsel, FloatValBranch float_valsel)
Post brancher.
Definition: flatzinc.cpp:236
Execution has resulted in failure.
Definition: core.hpp:466
Specification for Boolean variables.
Definition: varspec.hh:101
Value description class for branching.
Definition: float.hh:1463
double threads(void) const
Definition: flatzinc.hh:352
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3021
Node representing an atom
Definition: ast.hh:294
SharedHandle::Object * object(void) const
Access to the shared object.
int _optVar
Index of the variable to optimize.
Definition: flatzinc.hh:442
int getIntVar(void)
Cast this node to an integer variable node.
Definition: ast.hh:420
void finalize(void)
Clean up when Gist exits.
Definition: gist.cpp:68
int size(void) const
Return number of elements.
Output support class for FlatZinc interpreter.
Definition: flatzinc.hh:111
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:190
IntVar arg2IntVar(AST::Node *n)
Convert n to IntVar.
Definition: flatzinc.cpp:2265
Choice(const Brancher &b, bool fail0)
Initialize choice for brancher b.
Definition: flatzinc.cpp:146
FZPrintingInspector(const Printer &p0)
Constructor.
Definition: flatzinc.cpp:1664
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
static void installCtrlHandler(bool install, bool force=false)
Install handler for catching Ctrl-C.
Definition: script.hpp:120
static Search::Stop * create(unsigned int node, unsigned int fail, unsigned int time, bool intr)
Create appropriate stop-object.
Definition: script.hpp:94
IntAssign INT_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:69
FloatNum min(void) const
Return minimum of domain.
Definition: float.hpp:64
Which integer or Boolean variable to select for branching.
Definition: branch.hh:48
Simple propagation levels.
Definition: int.hh:955
int getBoolVar(void)
Cast this node to a Boolean variable node.
Definition: ast.hh:426
The Gecode Interactive Search Tool.
virtual const char * what(void) const
Return information.
Definition: exception.cpp:59
Type type(void) const
Return type of information.
Definition: core.hpp:3002
virtual void archive(Archive &e) const
Archive into e.
Definition: flatzinc.cpp:153
bool isSet(void)
Test if node is a set literal node.
Definition: ast.hh:502
std::vector< int > s
Definition: ast.hh:179
void fail(void)
Fail space.
Definition: core.hpp:3900
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
BoolVarArgs arg2boolvarargs(AST::Node *arg, int offset=0, int siv=-1)
Convert arg to BoolVarArgs.
Definition: flatzinc.cpp:2228
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:59
struct Gecode::Space::@58::@59 p
Data only available during propagation or branching.
const std::string & floatVarName(int i) const
Definition: flatzinc.hh:196
std::string what(void) const
Definition: ast.hh:65
unsigned int size(I &i)
Size of all ranges of range iterator i.
void newFloatVar(FloatVarSpec *vs)
Create new float variable from specification.
Definition: flatzinc.cpp:971
static void explore(S *root, const FlatZincOptions &opt, Gist::Inspector *i, Gist::Comparator *c)
Definition: flatzinc.cpp:1638
Value propagation.
Definition: int.hh:956
virtual ExecStatus commit(Space &, const Gecode::Choice &c, unsigned int)
Perform commit for choice c.
Definition: flatzinc.cpp:220
int min(void) const
Return smallest value of range.
IntValBranch INT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition: val.hpp:84
void shrinkElement(AST::Node *node, std::map< int, int > &iv, std::map< int, int > &bv, std::map< int, int > &sv, std::map< int, int > &fv)
Definition: flatzinc.cpp:2730
bool l
Whether to try the lower or upper half first.
Definition: float.hh:1468
const char * name(void) const
Return name of script.
Definition: options.hpp:170
IntVarBranch INT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:105
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1677
Iterator for the greatest lower bound ranges of a set variable.
Definition: set.hh:274
Gecode::BoolVarArray bv_aux
The introduced Boolean variables.
Definition: flatzinc.hh:493
struct Gecode::Space::@58::@60 c
Data available only during copying.
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition: branch.cpp:124
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
void print(std::ostream &out, const Gecode::IntVarArray &iv, const Gecode::BoolVarArray &bv, const Gecode::SetVarArray &sv, const Gecode::FloatVarArray &fv) const
Definition: flatzinc.cpp:2611
Array * getArgs(unsigned int n)
Definition: ast.hh:269
BoolAssign BOOL_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:114
FlatZincSpaceInitData * _initData
Initialisation data (only used for posting constraints)
Definition: flatzinc.hh:431
FloatValBranch FLOAT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:59
void addSetVarName(const std::string &n)
Definition: flatzinc.cpp:2724
bool funcDep
Whether the variable functionally depends on another variable.
Definition: varspec.hh:69
Less ( )
Definition: int.hh:908
Integer sets.
Definition: int.hh:174
const int * pi[]
Definition: photo.cpp:14266
SetVarBranch SET_VAR_AFC_MIN(double d, BranchTbl tbl)
Definition: var.hpp:130
IntVarBranch INT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:140
FloatVarBranch FLOAT_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:131
Float variable node.
Definition: ast.hh:218
virtual std::string getInfo(const Space &space) const
Return info for a space.
Definition: flatzinc.cpp:1731
virtual void compare(const Space &s0, const Space &s1)=0
Call-back function.
Set variable node
Definition: ast.hh:226
Choice that only signals failure or success
Definition: flatzinc.cpp:141
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:97
SetVarBranch SET_VAR_RND(Rnd r)
Definition: var.hpp:105
IntSharedArraySet intSharedArraySet
Hash table of shared integer arrays.
Definition: flatzinc.cpp:767
A simple comparator.
Definition: gist.hh:215
unsigned int node(void) const
Definition: flatzinc.hh:356
Option< AST::SetLit *> domain
Definition: varspec.hh:103
TieBreak< BoolVarBranch > ann2bvarsel(AST::Node *ann, Rnd rnd, double decay)
Definition: flatzinc.cpp:522
IntVarArgs arg2intvarargs(AST::Node *arg, int offset=0)
Convert arg to IntVarArgs.
Definition: flatzinc.cpp:2207
virtual void constrain(const Space &s)
Implement optimization.
Definition: flatzinc.cpp:1960
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:771
bool isIntVar(void)
Test if node is an integer variable node.
Definition: ast.hh:474
std::unordered_set< SharedArray< int > > IntSharedArraySet
Hash table of shared integer arrays.
Definition: flatzinc.cpp:765
const std::string & intVarName(int i) const
Definition: flatzinc.hh:191
FloatVarBranch FLOAT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:116
Passing integer variables.
Definition: int.hh:637
bool isBoolArray(AST::Node *b, int &singleInt)
Check if b is array of Booleans (or has a single integer)
Definition: flatzinc.cpp:2275
std::vector< bool > bv_introduced
Indicates whether a Boolean variable is introduced by mzn2fzn.
Definition: flatzinc.hh:495
SetValBranch SET_VAL_MIN_EXC(void)
Definition: val.hpp:64
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition: int.hh:1455
bool done
Flag whether brancher is done.
Definition: flatzinc.cpp:109
Passing integer arguments.
Definition: int.hh:608
Passing Boolean variables.
Definition: int.hh:691
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:59
static const IntSet empty
Empty set.
Definition: int.hh:263
bool isInt(int &i)
Test if node is int, if yes set i to the value.
Definition: ast.hh:368
Float view for float variables.
Definition: view.hpp:56
bool _optVarIsInt
Whether variable to optimize is integer (or float)
Definition: flatzinc.hh:444
FloatVarBranch FLOAT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:211
IntSet arg2intset(AST::Node *n)
Convert n to IntSet.
Definition: flatzinc.cpp:2177
Gecode::FloatVarArray fv_aux
The introduced float variables.
Definition: flatzinc.hh:508
void add(BrancherGroup bg, const std::string &rel0, const std::string &rel1, const std::vector< std::string > &n)
Add new brancher information.
Definition: flatzinc.cpp:325
Boolean variable array.
Definition: int.hh:787
Greater ( )
Definition: float.hh:1075
Boolean integer variables.
Definition: int.hh:492
bool isString(void)
Test if node is a string node.
Definition: ast.hh:506
SetValBranch SET_VAL_MAX_EXC(void)
Definition: val.hpp:84
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
virtual bool slave(const MetaInfo &mi)
Slave function for restarts.
Definition: flatzinc.cpp:1981
void init(void)
Initialize the implementation object.
Definition: gist.cpp:81
const int v[7]
Definition: distinct.cpp:263
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Class represeting a set of tuples.
Definition: int.hh:2144
bool assigned
Whether the variable is assigned.
Definition: varspec.hh:65
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:69
SetValBranch SET_VAL_MAX_INC(void)
Definition: val.hpp:79
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:953
Cutoff generator for constant sequence.
Definition: search.hh:527
AST::Array * args
Constraint arguments.
Definition: conexpr.hh:52
int getInt(void)
Cast this node to an integer node.
Definition: ast.hh:444
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:67
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Integer variable node.
Definition: ast.hh:210
void printDiff(std::ostream &out, const Gecode::IntVarArray &iv1, const Gecode::IntVarArray &iv2, const Gecode::BoolVarArray &bv1, const Gecode::BoolVarArray &bv2, const Gecode::SetVarArray &sv1, const Gecode::SetVarArray &sv2, const Gecode::FloatVarArray &fv1, const Gecode::FloatVarArray &fv2) const
Definition: flatzinc.cpp:2658
Passing set variables.
Definition: set.hh:492
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:210
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer view for integer variables.
Definition: view.hpp:129
SetVarBranch SET_VAR_SIZE_MAX(BranchTbl tbl)
Definition: var.hpp:215
void postConstraints(std::vector< ConExpr *> &ces)
Post a constraint specified by ce.
Definition: flatzinc.cpp:1008
BoolVarBranch BOOL_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:408
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:478
Exception: Base-class for exceptions
Definition: exception.hpp:46
Print statistics for script.
Definition: driver.hh:101
Base class for variables.
Definition: var.hpp:44
Float value type.
Definition: float.hh:338
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:104
Run script with CP-profiler.
Definition: driver.hh:103
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
virtual void print(std::ostream &)=0
Output string representation.
BranchInformation(void)
Constructor.
Definition: flatzinc.cpp:312
Exception signaling type error
Definition: ast.hh:59
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:393
Set variables
Definition: set.hh:131
FloatNum max(void) const
Return maximum of domain.
Definition: float.hpp:68
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:3207
void print(std::ostream &out, const Printer &p) const
Produce output on out using p.
Definition: flatzinc.cpp:2025
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:857
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
unsigned int fail(void) const
Definition: flatzinc.hh:357
bool hasAtom(const std::string &id)
Test if node has atom with id.
Definition: ast.hh:325
virtual Actor * copy(Space &home)
Copy brancher.
Definition: flatzinc.cpp:232
bool isFloatVar(void)
Test if node is a float variable node.
Definition: ast.hh:486
Archive representation
Definition: archive.hpp:46
int i
Variable index.
Definition: varspec.hh:61
IntBoolVarBranch INTBOOL_VAR_AFC_SIZE_MAX(double d=1.0)
Select variable with largest accumulated failure count divided by domain size.
Definition: branch.hpp:142
Set literal node
Definition: ast.hh:175
void init(void)
Initialise for use.
Definition: flatzinc.cpp:319
ExecStatus
Definition: core.hpp:464
void flattenAnnotations(AST::Array *ann, std::vector< AST::Node *> &out)
Definition: flatzinc.cpp:1026
SetVarBranch SET_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Definition: var.hpp:230
FloatVarBranch FLOAT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:141
Integer variables.
Definition: int.hh:351
Heap heap
The single global heap.
Definition: heap.cpp:48
Iterator for the values in the greatest lower bound of a set variable.
Definition: set.hh:370
FlatZincSpace(FlatZincSpace &)
Copy constructor.
Definition: flatzinc.cpp:778
IntVarBranch INT_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:150
BoolVarBranch BOOL_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:428
IntVarBranch INT_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:230
Which values to select for assignment.
Definition: int.hh:4768
std::unordered_set< TupleSet > TupleSetSet
Hash table of tuple sets.
Definition: flatzinc.cpp:760
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Exception class for FlatZinc errors
Definition: flatzinc.hh:660
Specification for floating point variables.
Definition: varspec.hh:123
FloatVarBranch FLOAT_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:151
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:958
TieBreak< FloatVarBranch > ann2fvarsel(AST::Node *ann, Rnd rnd, double decay)
Definition: flatzinc.cpp:693
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:3006
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:212
AST::Array * _solveAnnotations
Annotations on the solve item.
Definition: flatzinc.hh:459
virtual void inspect(const Space &node)
Use the print method of the template class S to print a space.
Definition: flatzinc.cpp:1669
unsigned int c_d(void) const
Definition: flatzinc.hh:354
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition: val.hpp:64
std::unordered_set< DFA > DFASet
Hash table of DFAs.
Definition: flatzinc.cpp:770
IntVarBranch INT_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest action divided by domain size with decay factor d.
Definition: var.hpp:250
void printFloatVar(std::ostream &os, const std::string name, const Float::FloatView &f)
Definition: flatzinc.cpp:1769
~FlatZincSpace(void)
Destructor.
Definition: flatzinc.cpp:1606
An window for simple text output.
Definition: gist.hh:164
void add(BrancherGroup bg, const std::string &rel0, const std::string &rel1, const std::vector< std::string > &n)
Add new brancher information.
Definition: flatzinc.cpp:288
Run script in Gist.
Definition: driver.hh:102
bool needAuxVars
Whether the introduced variables still need to be copied.
Definition: flatzinc.hh:515
virtual std::string name(void)
Return name.
Definition: gist.hpp:59
void printBoolVar(std::ostream &os, const std::string name, const BoolVar &b)
Definition: flatzinc.cpp:1762
int max(void) const
Return largest value of range.
void solve(AST::Array *annotation)
Post the solve item.
Definition: flatzinc.cpp:1585
unsigned int time(void) const
Definition: flatzinc.hh:358
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
unsigned long int restart
Number of restarts.
Definition: search.hh:158
AST::Array * solveAnnotations(void) const
Return the solve item annotations.
Definition: flatzinc.cpp:1580
BoolVarBranch BOOL_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:373
TieBreak< FloatVarBranch > float_varsel
Definition: flatzinc.cpp:168
bool isArray(void)
Test if node is an array node.
Definition: ast.hh:510
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:146
Float variables.
Definition: float.hh:874
void aliasBool2Int(int iv, int bv)
Link integer variable iv to Boolean variable bv.
Definition: flatzinc.cpp:903
Rnd _random
Random number generator.
Definition: flatzinc.hh:456
FloatVarBranch FLOAT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:191
#define GECODE_HAS_FLOAT_VARS
Definition: config.hpp:32
A space that can be initialized with a FlatZinc model.
Definition: flatzinc.hh:422
Gecode::IntVarArray iv_aux
The introduced integer variables.
Definition: flatzinc.hh:481
Set variable array
Definition: set.hh:572
void addBoolVarName(const std::string &n)
Definition: flatzinc.cpp:2713
void shrinkArrays(Space &home, int &optVar, bool optVarIsInt, Gecode::IntVarArray &iv, Gecode::BoolVarArray &bv, Gecode::SetVarArray &sv, Gecode::FloatVarArray &fv)
Definition: flatzinc.cpp:2765
TieBreak< BoolVarBranch > bool_varsel
Definition: flatzinc.cpp:161
CompareStatus compare(I &i, J &j)
Check whether range iterator i is a subset of j, or whether they are disjoint.
Stop * stop
Stop object for stopping search.
Definition: search.hh:767
class Gecode::Gist::Options::_I inspect
const std::string & setVarName(int i) const
Definition: flatzinc.hh:200
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:79
int explore(Space *root, bool bab, const Options &opt)
Create a new stand-alone Gist for root using bab.
Definition: gist.cpp:106
void print(const Brancher &b, unsigned int a, int i, int n, std::ostream &o) const
Output branch information.
Definition: flatzinc.cpp:332
void run(std::ostream &out, const Printer &p, const FlatZincOptions &opt, Gecode::Support::Timer &t_total)
Run the search.
Definition: flatzinc.cpp:1946
Gecode toplevel namespace
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
Information passed by meta search engines.
Definition: core.hpp:1539
void addIntVarName(const std::string &n)
Definition: flatzinc.cpp:2709
int * iv_boolalias
Indicates whether an integer variable aliases a Boolean variable.
Definition: flatzinc.hh:489
unsigned long int node
Number of nodes expanded.
Definition: search.hh:154
void maximize(int var, bool isInt, AST::Array *annotation)
Post that integer variable var should be maximized.
Definition: flatzinc.cpp:1599
int setVarCount
Number of set variables.
Definition: flatzinc.hh:439
Node representing a function call
Definition: ast.hh:259
int intVarCount
Number of integer variables.
Definition: flatzinc.hh:433
unsigned int a_d(void) const
Definition: flatzinc.hh:355
FZPrintingComparator(const Printer &p0)
Constructor.
Definition: flatzinc.cpp:1695
IntValBranch ann2ivalsel(AST::Node *ann, std::string &r0, std::string &r1, Rnd rnd)
Definition: flatzinc.cpp:453
SetVarArgs arg2setvarargs(AST::Node *arg, int offset=0, int doffset=0, const IntSet &od=IntSet::empty)
Convert n to SetVarArgs.
Definition: flatzinc.cpp:2308
A node in a FlatZinc abstract syntax tree.
Definition: ast.hh:71
SetVarBranch SET_VAR_ACTION_MAX(double d, BranchTbl tbl)
Definition: var.hpp:160
SetVarBranch SET_VAR_MIN_MIN(BranchTbl tbl)
Definition: var.hpp:190
IntArgs arg2boolargs(AST::Node *arg, int offset=0)
Convert arg (array of Booleans) to IntArgs.
Definition: flatzinc.cpp:2153
FloatVarBranch FLOAT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
Definition: var.hpp:261
Which variable to select for branching.
Definition: set.hh:1298
Random number generator.
Definition: rnd.hpp:46
FloatVarBranch FLOAT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:241
SetVarBranch SET_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Definition: var.hpp:240
void addFloatVarName(const std::string &n)
Definition: flatzinc.cpp:2718
Space is failed
Definition: core.hpp:1608
unsigned int _lns
Percentage of variables to keep in LNS (or 0 for no LNS)
Definition: flatzinc.hh:450
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1689
TupleSet arg2tupleset(AST::Node *n, int noOfVars)
Convert n to TupleSet.
Definition: flatzinc.cpp:2112
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:115
FloatVarBranch FLOAT_VAR_MAX_MAX(BranchTbl tbl)
Select variable with largest max.
Definition: var.hpp:206
void varValPrintF(const Space &home, const Brancher &b, unsigned int a, FloatVar, int i, const FloatNumBranch &nl, std::ostream &o)
Definition: flatzinc.cpp:352
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Gecode::SetVarArray sv
The set variables.
Definition: flatzinc.hh:498
Home class for posting propagators
Definition: core.hpp:846
FloatVarBranch FLOAT_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:161
Options for Gist
Definition: gist.hh:238
std::string getDomains(const Printer &p) const
Get string representing the domains of variables (for cpprofiler)
Definition: flatzinc.cpp:1778
double FloatNum
Floating point number base type.
Definition: float.hh:110
Specification for integer variables.
Definition: varspec.hh:76
void compare(Comparator *c)
Add comparator.
Definition: gist.hpp:186
SetVarBranch SET_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Definition: var.hpp:260
const std::string & boolVarName(int i) const
Definition: flatzinc.hh:193
bool introduced
Whether the variable was introduced in the mzn2fzn translation.
Definition: varspec.hh:67
virtual void finalize(void)
Finalize when Gist exits.
Definition: flatzinc.cpp:1677
std::string getString(void)
Cast this node to a string node.
Definition: ast.hh:468
Gecode::IntVarArray iv_lns
The integer variables used in LNS.
Definition: flatzinc.hh:484
FloatVar arg2FloatVar(AST::Node *n)
Convert n to FloatVar.
Definition: flatzinc.cpp:2355
Depth-first search engine.
Definition: search.hh:1039
Branching on the introduced variables.
Definition: flatzinc.cpp:106
const Val & some(void) const
Definition: option.hh:51
SetVarBranch SET_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Definition: var.hpp:250
IntSharedArray _lnsInitialSolution
Initial solution to start the LNS (or NULL for no LNS)
Definition: flatzinc.hh:453
Registry & registry(void)
Return global registry object.
Definition: registry.cpp:57
TupleSetSet tupleSetSet
Hash table of tuple sets.
Definition: flatzinc.cpp:762
FloatValArgs arg2floatargs(AST::Node *arg, int offset=0)
Convert n to FloatValArgs.
Definition: flatzinc.cpp:2324
IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
Definition: var.hpp:260
Option< AST::SetLit * > upperBound
Definition: varspec.hh:145
virtual size_t dispose(Space &)
Delete brancher and return its size.
Definition: flatzinc.cpp:263
T * a
Element array.
Definition: array.hpp:519
bool fail
Whether brancher should fail.
Definition: flatzinc.cpp:144
AuxVarBrancher(Space &home, AuxVarBrancher &b)
Copy constructor.
Definition: flatzinc.cpp:137
TieBreak< IntVarBranch > int_varsel
Definition: flatzinc.cpp:159
int val(void) const
Return assigned value.
Definition: bool.hpp:61
void init(AST::Array *output)
Definition: flatzinc.cpp:2394
BoolVar arg2BoolVar(AST::Node *n)
Convert n to BoolVar.
Definition: flatzinc.cpp:2254
IntSetArgs arg2intsetargs(AST::Node *arg, int offset=0)
Convert arg to IntSetArgs.
Definition: flatzinc.cpp:2192
Rnd defrnd
Uninitialized default random number generator.
Definition: flatzinc.cpp:92
SetVarBranch SET_VAR_ACTION_MIN(double d, BranchTbl tbl)
Definition: var.hpp:150
Abstract representation of a constraint.
Definition: conexpr.hh:47