Generated on Thu Mar 16 2017 03:24:23 for Gecode by doxygen 1.8.13
set.hh
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  * Christian Schulte <schulte@gecode.org>
6  *
7  * Contributing authors:
8  * Gabor Szokoli <szokoli@gecode.org>
9  *
10  * Copyright:
11  * Guido Tack, 2004
12  * Christian Schulte, 2004
13  * Gabor Szokoli, 2004
14  *
15  * Last modified:
16  * $Date: 2016-10-25 12:52:26 +0200 (Tue, 25 Oct 2016) $ by $Author: schulte $
17  * $Revision: 15233 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #ifndef __GECODE_SET_HH__
45 #define __GECODE_SET_HH__
46 
47 #include <gecode/kernel.hh>
48 #include <gecode/int.hh>
49 #include <gecode/iter.hh>
50 
51 /*
52  * Configure linking
53  *
54  */
55 #if !defined(GECODE_STATIC_LIBS) && \
56  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
57 
58 #ifdef GECODE_BUILD_SET
59 #define GECODE_SET_EXPORT __declspec( dllexport )
60 #else
61 #define GECODE_SET_EXPORT __declspec( dllimport )
62 #endif
63 
64 #else
65 
66 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
67 #define GECODE_SET_EXPORT __attribute__ ((visibility("default")))
68 #else
69 #define GECODE_SET_EXPORT
70 #endif
71 
72 #endif
73 
74 // Configure auto-linking
75 #ifndef GECODE_BUILD_SET
76 #define GECODE_LIBRARY_NAME "Set"
78 #endif
79 
80 
92 #include <gecode/set/exception.hpp>
93 
94 namespace Gecode { namespace Set {
95 
97  namespace Limits {
99  const int max = (Gecode::Int::Limits::max / 2) - 1;
101  const int min = -max;
103  const unsigned int card = max-min+1;
105  void check(int n, const char* l);
107  void check(unsigned int n, const char* l);
109  void check(const IntSet& s, const char* l);
110  }
111 
112 }}
113 
114 #include <gecode/set/limits.hpp>
115 
116 #include <gecode/set/var-imp.hpp>
117 
118 namespace Gecode {
119 
120  namespace Set {
121  class SetView;
122  }
123 
129  class SetVar : public VarImpVar<Set::SetVarImp> {
130  friend class SetVarArray;
131  friend class SetVarArgs;
133  public:
135 
136  SetVar(void);
139  SetVar(const SetVar& y);
141  SetVar(const Set::SetView& y);
142 
145 
164  SetVar(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
165  unsigned int cardMin = 0,
166  unsigned int cardMax = Set::Limits::card);
167 
185  SetVar(Space& home,const IntSet& glbD,int lubMin,int lubMax,
186  unsigned int cardMin = 0,
187  unsigned int cardMax = Set::Limits::card);
188 
207  SetVar(Space& home,int glbMin,int glbMax,const IntSet& lubD,
208  unsigned int cardMin = 0,
209  unsigned int cardMax = Set::Limits::card);
210 
229  SetVar(Space& home,const IntSet& glbD,const IntSet& lubD,
230  unsigned int cardMin = 0,
231  unsigned int cardMax = Set::Limits::card);
233 
235 
236  unsigned int glbSize(void) const;
239  unsigned int lubSize(void) const;
241  unsigned int unknownSize(void) const;
243  unsigned int cardMin(void) const;
245  unsigned int cardMax(void) const;
247  int lubMin(void) const;
249  int lubMax(void) const;
251  int glbMin(void) const;
253  int glbMax(void) const;
255 
257 
258  bool contains(int i) const;
261  bool notContains(int i) const;
263  };
264 
270 
273  private:
275  public:
277 
278  SetVarGlbRanges(void);
281  SetVarGlbRanges(const SetVar& x);
283 
285 
286  bool operator ()(void) const;
289  void operator ++(void);
291 
293 
294  int min(void) const;
297  int max(void) const;
299  unsigned int width(void) const;
301  };
302 
305  private:
307  public:
309 
310  SetVarLubRanges(void);
313  SetVarLubRanges(const SetVar& x);
315 
317 
318  bool operator ()(void) const;
321  void operator ++(void);
323 
325 
326  int min(void) const;
329  int max(void) const;
331  unsigned int width(void) const;
333  };
334 
337  private:
339  public:
341 
342  SetVarUnknownRanges(void);
345  SetVarUnknownRanges(const SetVar& x);
347 
349 
350  bool operator ()(void) const;
353  void operator ++(void);
355 
357 
358  int min(void) const;
361  int max(void) const;
363  unsigned int width(void) const;
365  };
366 
369  private:
371  public:
373 
374  SetVarGlbValues(void);
377  SetVarGlbValues(const SetVar& x);
379 
381 
382  bool operator ()(void) const;
385  void operator ++(void);
387 
389 
390  int val(void) const;
393  };
394 
397  private:
399  public:
401 
402  SetVarLubValues(void);
405  SetVarLubValues(const SetVar& x);
407 
409 
410  bool operator ()(void) const;
413  void operator ++(void);
415 
417 
418  int val(void) const;
421  };
422 
425  private:
427  public:
429 
430  SetVarUnknownValues(void);
433  SetVarUnknownValues(const SetVar& x);
435 
437 
438  bool operator ()(void) const;
441  void operator ++(void);
443 
445 
446  int val(void) const;
449  };
450 
452 
457  template<class Char, class Traits>
458  std::basic_ostream<Char,Traits>&
459  operator <<(std::basic_ostream<Char,Traits>& os, const SetVar& x);
460 
461 }
462 
463 #include <gecode/set/view.hpp>
464 
465 namespace Gecode {
475 
476 }
477 
479 
480 namespace Gecode {
481 
490  class SetVarArgs : public VarArgArray<SetVar> {
491  public:
493 
494  SetVarArgs(void);
497  explicit SetVarArgs(int n);
499  SetVarArgs(const SetVarArgs& a);
501  SetVarArgs(const VarArray<SetVar>& a);
503  SetVarArgs(const std::vector<SetVar>& a);
505  template<class InputIterator>
506  SetVarArgs(InputIterator first, InputIterator last);
514  SetVarArgs(Space& home,int n,int glbMin,int glbMax,
515  int lubMin,int lubMax,
516  unsigned int minCard = 0,
517  unsigned int maxCard = Set::Limits::card);
525  SetVarArgs(Space& home,int n,const IntSet& glb,
526  int lubMin, int lubMax,
527  unsigned int minCard = 0,
528  unsigned int maxCard = Set::Limits::card);
536  SetVarArgs(Space& home,int n,int glbMin,int glbMax,
537  const IntSet& lub,
538  unsigned int minCard = 0,
539  unsigned int maxCard = Set::Limits::card);
547  SetVarArgs(Space& home,int n,
548  const IntSet& glb,const IntSet& lub,
549  unsigned int minCard = 0,
550  unsigned int maxCard = Set::Limits::card);
552  };
554 
570  class SetVarArray : public VarArray<SetVar> {
571  public:
573 
574  SetVarArray(void);
577  SetVarArray(const SetVarArray&);
579  SetVarArray(Space& home, const SetVarArgs&);
581  GECODE_SET_EXPORT SetVarArray(Space& home, int n);
589  SetVarArray(Space& home,int n,int glbMin,int glbMax,int lubMin,int lubMax,
590  unsigned int minCard = 0,
591  unsigned int maxCard = Set::Limits::card);
599  SetVarArray(Space& home,int n,const IntSet& glb, int lubMin, int lubMax,
600  unsigned int minCard = 0,
601  unsigned int maxCard = Set::Limits::card);
609  SetVarArray(Space& home,int n,int glbMin,int glbMax,const IntSet& lub,
610  unsigned int minCard = 0,
611  unsigned int maxCard = Set::Limits::card);
619  SetVarArray(Space& home,int n,
620  const IntSet& glb,const IntSet& lub,
621  unsigned int minCard = 0,
622  unsigned int maxCard = Set::Limits::card);
624  };
625 
626 }
627 
628 #include <gecode/set/array.hpp>
629 
630 namespace Gecode {
631 
643  enum SetRelType {
654  };
655 
660  enum SetOpType {
665  };
666 
674 
676  GECODE_SET_EXPORT void
677  dom(Home home, SetVar x, SetRelType r, int i);
679  GECODE_SET_EXPORT void
680  dom(Home home, const SetVarArgs& x, SetRelType r, int i);
682  GECODE_SET_EXPORT void
683  dom(Home home, SetVar x, SetRelType r, int i, int j);
685  GECODE_SET_EXPORT void
686  dom(Home home, const SetVarArgs& x, SetRelType r, int i, int j);
688  GECODE_SET_EXPORT void
689  dom(Home home, SetVar x, SetRelType r, const IntSet& s);
691  GECODE_SET_EXPORT void
692  dom(Home home, const SetVarArgs& x, SetRelType r, const IntSet& s);
694  GECODE_SET_EXPORT void
695  cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
697  GECODE_SET_EXPORT void
698  cardinality(Home home, const SetVarArgs& x, unsigned int i, unsigned int j);
700  GECODE_SET_EXPORT void
701  dom(Home home, SetVar x, SetRelType rt, int i, Reify r);
703  GECODE_SET_EXPORT void
704  dom(Home home, SetVar x, SetRelType rt, int i, int j, Reify r);
706  GECODE_SET_EXPORT void
707  dom(Home home, SetVar x, SetRelType rt, const IntSet& s, Reify r);
709  GECODE_SET_EXPORT void
710  dom(Home home, SetVar x, SetVar d);
712  GECODE_SET_EXPORT void
713  dom(Home home, const SetVarArgs& x, const SetVarArgs& d);
715 
716 
724 
726  GECODE_SET_EXPORT void
727  rel(Home home, SetVar x, SetRelType r, SetVar y);
728 
730  GECODE_SET_EXPORT void
731  rel(Home home, SetVar x, SetRelType rt, SetVar y, Reify r);
732 
734  GECODE_SET_EXPORT void
735  rel(Home home, SetVar s, SetRelType r, IntVar x);
736 
738  GECODE_SET_EXPORT void
739  rel(Home home, IntVar x, SetRelType r, SetVar s);
740 
742  GECODE_SET_EXPORT void
743  rel(Home home, SetVar s, SetRelType rt, IntVar x, Reify r);
744 
746  GECODE_SET_EXPORT void
747  rel(Home home, IntVar x, SetRelType rt, SetVar s, Reify r);
748 
750  GECODE_SET_EXPORT void
751  rel(Home home, SetVar s, IntRelType r, IntVar x);
752 
754  GECODE_SET_EXPORT void
755  rel(Home home, IntVar x, IntRelType r, SetVar s);
756 
758 
766 
768  GECODE_SET_EXPORT void
769  rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
770 
772  GECODE_SET_EXPORT void
773  rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
774 
776  GECODE_SET_EXPORT void
777  rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
778 
780  GECODE_SET_EXPORT void
781  rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
782 
784  GECODE_SET_EXPORT void
785  rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
786 
788  GECODE_SET_EXPORT void
789  rel(Home home, const IntSet& x, SetOpType op, SetVar y,
790  SetRelType r, SetVar z);
791 
793  GECODE_SET_EXPORT void
794  rel(Home home, SetVar x, SetOpType op, const IntSet& y,
795  SetRelType r, SetVar z);
796 
798  GECODE_SET_EXPORT void
799  rel(Home home, SetVar x, SetOpType op, SetVar y,
800  SetRelType r, const IntSet& z);
801 
803  GECODE_SET_EXPORT void
804  rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
805  const IntSet& z);
806 
808  GECODE_SET_EXPORT void
809  rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
810  const IntSet& z);
811 
813 
814 
821 
823  GECODE_SET_EXPORT void
824  convex(Home home, SetVar x);
825 
827  GECODE_SET_EXPORT void
828  convex(Home home, SetVar x, SetVar y);
829 
831 
838 
840  GECODE_SET_EXPORT void
841  sequence(Home home, const SetVarArgs& x);
842 
844  GECODE_SET_EXPORT void
845  sequence(Home home, const SetVarArgs& y, SetVar x);
846 
848 
855 
856 
858  GECODE_SET_EXPORT void
859  atmostOne(Home home, const SetVarArgs& x, unsigned int c);
860 
862 
870 
873  GECODE_SET_EXPORT void
874  min(Home home, SetVar s, IntVar x);
875 
878  GECODE_SET_EXPORT void
879  notMin(Home home, SetVar s, IntVar x);
880 
883  GECODE_SET_EXPORT void
884  min(Home home, SetVar s, IntVar x, Reify r);
885 
888  GECODE_SET_EXPORT void
889  max(Home home, SetVar s, IntVar x);
890 
893  GECODE_SET_EXPORT void
894  notMax(Home home, SetVar s, IntVar x);
895 
898  GECODE_SET_EXPORT void
899  max(Home home, SetVar s, IntVar x, Reify r);
900 
902  GECODE_SET_EXPORT void
903  cardinality(Home home, SetVar s, IntVar x);
904 
915  GECODE_SET_EXPORT void
917  SetVar x, IntVar y);
918 
920 
928 
930  GECODE_SET_EXPORT void
931  channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
932 
934  GECODE_SET_EXPORT void
935  channelSorted(Home home, const IntVarArgs& x, SetVar y);
936 
938  GECODE_SET_EXPORT void
939  channel(Home home, const BoolVarArgs& x, SetVar y);
940 
942  GECODE_SET_EXPORT void
943  channel(Home home, const SetVarArgs& x, const SetVarArgs& y);
944 
946 
958  GECODE_SET_EXPORT void
959  precede(Home home, const SetVarArgs& x, int s, int t);
963  GECODE_SET_EXPORT void
964  precede(Home home, const SetVarArgs& x, const IntArgs& c);
965 
979 
989  GECODE_SET_EXPORT void
990  element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
992 
1002  GECODE_SET_EXPORT void
1003  element(Home home, SetOpType op, const IntVarArgs& x, SetVar y, SetVar z,
1005 
1015  GECODE_SET_EXPORT void
1016  element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
1018 
1028  GECODE_SET_EXPORT void
1029  element(Home home, SetOpType op, const IntArgs& x, SetVar y, SetVar z,
1031 
1037  GECODE_SET_EXPORT void
1038  element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
1039 
1045  GECODE_SET_EXPORT void
1046  element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
1047 
1053  GECODE_SET_EXPORT void
1054  element(Home home, const IntSetArgs& a,
1055  IntVar x, int w, IntVar y, int h, SetVar z);
1061  GECODE_SET_EXPORT void
1062  element(Home home, const SetVarArgs& a,
1063  IntVar x, int w, IntVar y, int h, SetVar z);
1065 
1076  GECODE_SET_EXPORT void
1078  wait(Home home, SetVar x, void (*c)(Space& home));
1080  GECODE_SET_EXPORT void
1081  wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
1083 
1084 }
1085 
1086 namespace Gecode {
1087 
1101  typedef bool (*SetBranchFilter)(const Space& home, SetVar x, int i);
1102 
1113  typedef double (*SetBranchMerit)(const Space& home, SetVar x, int i);
1114 
1125  typedef int (*SetBranchVal)(const Space& home, SetVar x, int i);
1126 
1138  typedef void (*SetBranchCommit)(Space& home, unsigned int a,
1139  SetVar x, int i, int n);
1140 
1141 }
1142 
1144 
1145 namespace Gecode {
1146 
1152  class SetAFC : public AFC {
1153  public:
1161  SetAFC(void);
1163  SetAFC(const SetAFC& a);
1165  SetAFC& operator =(const SetAFC& a);
1167  SetAFC(Home home, const SetVarArgs& x, double d=1.0);
1175  void init(Home home, const SetVarArgs& x, double d=1.0);
1176  };
1177 
1178 }
1179 
1180 #include <gecode/set/branch/afc.hpp>
1181 
1182 namespace Gecode {
1183 
1184 
1190  class SetActivity : public Activity {
1191  public:
1199  SetActivity(void);
1201  SetActivity(const SetActivity& a);
1203  SetActivity& operator =(const SetActivity& a);
1213  SetActivity(Home home, const SetVarArgs& x, double d=1.0,
1214  SetBranchMerit bm=NULL);
1226  GECODE_SET_EXPORT void
1227  init(Home home, const SetVarArgs& x, double d=1.0,
1228  SetBranchMerit bm=NULL);
1229  };
1230 
1231 }
1232 
1234 
1235 namespace Gecode {
1236 
1238  typedef void (*SetVarValPrint)(const Space &home, const Brancher& b,
1239  unsigned int a,
1240  SetVar x, int i, const int& n,
1241  std::ostream& o);
1242 
1243 }
1244 
1245 namespace Gecode {
1246 
1252  class SetVarBranch : public VarBranch {
1253  public:
1255  enum Select {
1256  SEL_NONE = 0,
1277  SEL_ACTIVITY_SIZE_MAX
1278  };
1279  protected:
1282  public:
1284  SetVarBranch(void);
1286  SetVarBranch(Rnd r);
1290  SetVarBranch(Select s, double d, BranchTbl t);
1298  Select select(void) const;
1300  void expand(Home home, const SetVarArgs& x);
1301  };
1302 
1308  SetVarBranch SET_VAR_NONE(void);
1321  SetVarBranch SET_VAR_AFC_MIN(double d=1.0, BranchTbl tbl=NULL);
1325  SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=NULL);
1329  SetVarBranch SET_VAR_ACTIVITY_MIN(double d=1.0, BranchTbl tbl=NULL);
1333  SetVarBranch SET_VAR_ACTIVITY_MAX(double d=1.0, BranchTbl tbl=NULL);
1353  SetVarBranch SET_VAR_AFC_SIZE_MIN(double d=1.0, BranchTbl tbl=NULL);
1357  SetVarBranch SET_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=NULL);
1369 
1370 }
1371 
1372 #include <gecode/set/branch/var.hpp>
1373 
1374 namespace Gecode {
1375 
1381  class SetValBranch : public ValBranch {
1382  public:
1384  enum Select {
1393  SEL_VAL_COMMIT
1394  };
1395  protected:
1398  public:
1400  SetValBranch(Select s = SEL_MIN_INC);
1402  SetValBranch(Select s, Rnd r);
1406  Select select(void) const;
1407  };
1408 
1439 
1440 }
1441 
1442 #include <gecode/set/branch/val.hpp>
1443 
1444 namespace Gecode {
1445 
1451  class SetAssign : public ValBranch {
1452  public:
1454  enum Select {
1463  SEL_VAL_COMMIT
1464  };
1465  protected:
1468  public:
1470  SetAssign(Select s = SEL_MIN_INC);
1472  SetAssign(Select s, Rnd r);
1476  Select select(void) const;
1477  };
1478 
1508 
1509 }
1510 
1512 
1513 namespace Gecode {
1514 
1520  GECODE_SET_EXPORT void
1521  branch(Home home, const SetVarArgs& x,
1522  SetVarBranch vars, SetValBranch vals,
1523  SetBranchFilter bf=NULL,
1524  SetVarValPrint vvp=NULL);
1530  GECODE_SET_EXPORT void
1531  branch(Home home, const SetVarArgs& x,
1533  SetBranchFilter bf=NULL,
1534  SetVarValPrint vvp=NULL);
1540  GECODE_SET_EXPORT void
1541  branch(Home home, SetVar x, SetValBranch vals,
1542  SetVarValPrint vvp=NULL);
1548  GECODE_SET_EXPORT void
1549  assign(Home home, const SetVarArgs& x, SetAssign vals,
1550  SetBranchFilter bf=NULL,
1551  SetVarValPrint vvp=NULL);
1557  GECODE_SET_EXPORT void
1558  assign(Home home, SetVar x, SetAssign vals,
1559  SetVarValPrint vvp=NULL);
1560 
1561 }
1562 
1563 // LDSB-related declarations.
1564 namespace Gecode {
1580  GECODE_SET_EXPORT void
1581  branch(Home home, const SetVarArgs& x,
1582  SetVarBranch vars, SetValBranch vals,
1583  const Symmetries& syms,
1584  SetBranchFilter bf=NULL,
1585  SetVarValPrint vvp=NULL);
1592  GECODE_SET_EXPORT void
1593  branch(Home home, const SetVarArgs& x,
1595  const Symmetries& syms,
1596  SetBranchFilter bf=NULL,
1597  SetVarValPrint vvp=NULL);
1598 }
1599 
1600 namespace Gecode {
1601 
1602  /*
1603  * \brief Relaxed assignment of variables in \a x from values in \a sx
1604  *
1605  * The variables in \a x are assigned values from the assigned variables
1606  * in the solution \a sx with a relaxation probability \a p. That is,
1607  * if \$fp=0.1\f$ approximately 10% of the variables in \a x will be
1608  * assigned a value from \a sx.
1609  *
1610  * The random numbers are generated from the generator \a r. At least
1611  * one variable will not be assigned: in case the relaxation attempt
1612  * would suggest that all variables should be assigned, a single
1613  * variable will be selected randomly to remain unassigned.
1614  *
1615  * Throws an exception of type Set::ArgumentSizeMismatch, if \a x and
1616  * \a sx are of different size.
1617  *
1618  * Throws an exception of type Set::OutOfLimits, if \a p is not between
1619  * \a 0.0 and \a 1.0.
1620  *
1621  * \ingroup TaskModeSet
1622  */
1623  GECODE_SET_EXPORT void
1624  relax(Home home, const SetVarArgs& x, const SetVarArgs& sx,
1625  Rnd r, double p);
1626 
1627 }
1628 
1630 
1631 namespace Gecode {
1632 
1643  protected:
1645  public:
1647  class Glb
1648  : public Iter::Ranges::Diff<Set::GlbRanges<Set::SetView>,
1649  Iter::Ranges::RangeList> {
1650  protected:
1655  public:
1657 
1658  Glb(RangeList* o, Set::SetView n);
1661  };
1664  class Lub
1665  : public Iter::Ranges::Diff<Iter::Ranges::RangeList,
1666  Set::LubRanges<Set::SetView> > {
1667  protected:
1672  public:
1674 
1675  Lub(RangeList* o, Set::SetView n);
1678  };
1681 
1685 
1687  Glb& glb(void);
1690  Lub& lub(void);
1692  };
1693 
1694 }
1695 
1696 #include <gecode/set/trace/delta.hpp>
1697 
1698 #include <gecode/set/trace/traits.hpp>
1699 
1700 namespace Gecode {
1701 
1712 
1717  class GECODE_SET_EXPORT StdSetTracer : public SetTracer {
1718  protected:
1720  std::ostream& os;
1721  public:
1723  StdSetTracer(std::ostream& os0 = std::cerr);
1725  virtual void init(const Space& home, const SetTraceRecorder& t);
1727  virtual void prune(const Space& home, const SetTraceRecorder& t,
1728  const ExecInfo& ei, int i, SetTraceDelta& d);
1730  virtual void fix(const Space& home, const SetTraceRecorder& t);
1732  virtual void done(const Space& home, const SetTraceRecorder& t);
1734  static StdSetTracer def;
1735  };
1736 
1737 
1742  GECODE_SET_EXPORT void
1743  trace(Home home, const SetVarArgs& x,
1744  TraceFilter tf,
1745  int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_DONE),
1746  SetTracer& t = StdSetTracer::def);
1751  void
1752  trace(Home home, const SetVarArgs& x,
1753  int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_DONE),
1754  SetTracer& t = StdSetTracer::def);
1755 
1756 }
1757 
1758 #include <gecode/set/trace.hpp>
1759 
1760 #endif
1761 
1762 // IFDEF: GECODE_HAS_SET_VARS
1763 // STATISTICS: set-post
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest unknown set.
Definition: var.hpp:183
With largest accumulated failure count divided by domain size.
Definition: set.hh:1275
Which values to select for branching first.
Definition: set.hh:1381
Tracer< Set::SetView > SetTracer
Tracer for set variables.
Definition: set.hh:1706
SetVarBranch SET_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:123
SetVarBranch SET_VAR_MIN_MAX(BranchTbl tbl)
Select variable with largest minimum unknown element.
Definition: var.hpp:168
void channelSorted(Home home, const IntVarArgs &x, SetVar y)
Post propagator for and .
Definition: channel.cpp:49
Variables as interfaces to variable implementations.
Definition: var.hpp:51
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Include smallest element.
Definition: set.hh:1455
Combine variable selection criteria for tie-breaking.
void check(int n, const char *l)
Check whether integer n is in range, otherwise throw overflow exception with information l...
Definition: limits.hpp:41
SetRelType
Common relation types for sets.
Definition: set.hh:643
SetAssign SET_ASSIGN_MIN_EXC(void)
Exclude smallest element.
Definition: assign.hpp:64
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
With largest accumulated failure count.
Definition: set.hh:1263
Range iterator for the unknown set.
Definition: var-imp.hpp:406
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:91
Exclude random element.
Definition: set.hh:1392
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:51
With smallest accumulated failure count divided by domain size.
Definition: set.hh:1274
void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te, FloatTracer &t)
Create a tracer for float variables.
Definition: trace.cpp:43
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: arithmetic.cpp:218
SetVarBranch SET_VAR_DEGREE_MIN(BranchTbl tbl)
Select variable with smallest degree.
Definition: var.hpp:113
With smallest activity divided by domain size.
Definition: set.hh:1276
SetValBranch SET_VAL_MED_INC(void)
Include median element (rounding downwards)
Definition: val.hpp:69
With smallest maximum unknown element.
Definition: set.hh:1268
SetVarBranch SET_VAR_ACTIVITY_MIN(double d, BranchTbl tbl)
Select variable with lowest activity with decay factor d.
Definition: var.hpp:143
Standard set variable tracer.
Definition: set.hh:1717
With highest merit.
Definition: set.hh:1259
Random (uniform, for tie breaking)
Definition: set.hh:1257
Range iterator for range lists
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
Definition: val.hpp:59
SetVarBranch SET_VAR_ACTIVITY_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest activity divided by domain size with decay factor d.
Definition: var.hpp:223
Select
Which variable selection.
Definition: set.hh:1255
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
Collection of symmetries.
Definition: int.hh:4472
SetAssign SET_ASSIGN(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:99
void atmostOne(Home home, const SetVarArgs &xa, unsigned int c)
Post propagator for and .
Definition: distinct.cpp:45
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
Iterator over new glb Set::GlbRanges< Set::SetView > n
Definition: set.hh:1654
With largest degree.
Definition: set.hh:1261
With largest minimum unknown element.
Definition: set.hh:1267
With largest degree divided by domain size.
Definition: set.hh:1273
SetOpType
Common operations for sets.
Definition: set.hh:660
With lowest activity.
Definition: set.hh:1264
Superset ( )
Definition: set.hh:647
Recording activities for set variables.
Definition: set.hh:1190
SetAssign SET_ASSIGN_MAX_INC(void)
Include largest element.
Definition: assign.hpp:79
SetValBranch SET_VAL_RND_EXC(Rnd r)
Exclude random element.
Definition: val.hpp:94
Complement.
Definition: set.hh:649
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Trace init events.
const int max
Largest allowed integer value.
Definition: int.hh:114
Exclude median element (rounding downwards)
Definition: set.hh:1458
Computation spaces.
Definition: core.hpp:1672
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:257
Difference.
Definition: set.hh:664
SetAssign SET_ASSIGN_RND_EXC(Rnd r)
Exclude random element.
Definition: assign.hpp:94
Exclude smallest element.
Definition: set.hh:1456
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
Include largest element.
Definition: set.hh:1459
SetVarBranch SET_VAR_SIZE_MAX(BranchTbl tbl)
Select variable with largest unknown set.
Definition: var.hpp:188
Exclude median element (rounding downwards)
Definition: set.hh:1388
Iterator for the unknown ranges of a set variable.
Definition: set.hh:336
Duplicate of a set view.
Definition: trace-view.hpp:41
With largest maximum unknown element.
Definition: set.hh:1269
Gecode::IntSet d(v, 7)
Iterator for the values in the unknown set of a set variable.
Definition: set.hh:424
Iterator over old lub Iter::Ranges::RangeList o
Definition: set.hh:1669
std::string expand(Gecode::IntRelType irt)
Expand relation to abbreviation.
Definition: mm-count.cpp:48
TraceRecorder< Set::SetView > SetTraceRecorder
TraceRecorder for set variables.
Definition: set.hh:1711
Gecode::FloatVal c(-8, 8)
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
Trace prune events.
Include largest element.
Definition: set.hh:1389
SetAssign SET_ASSIGN_MAX_EXC(void)
Exclude largest element.
Definition: assign.hpp:84
SymmetryHandle VariableSymmetry(const IntVarArgs &vars)
Variables in x are interchangeable.
Definition: ldsb.cpp:66
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
With highest activity.
Definition: set.hh:1265
SetVarBranch SET_VAR_DEGREE_SIZE_MIN(BranchTbl tbl)
Select variable with smallest degree divided by domain size.
Definition: var.hpp:193
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1364
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
A reference-counted pointer to a SymmetryObject.
Definition: int.hh:4435
union Gecode::@554::NNF::@60 u
Union depending on nodetype t.
int(* SetBranchVal)(const Space &home, SetVar x, int i)
Branch value function type for set variables.
Definition: set.hh:1125
IntRelType
Relation types for integers.
Definition: int.hh:904
SetVarBranch SET_VAR_MERIT_MAX(SetBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:107
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Propagator for recording trace information.
Less or equal ( )
Definition: set.hh:650
SetVarBranch SET_VAR_ACTIVITY_MAX(double d, BranchTbl tbl)
Select variable with highest activity with decay factor d.
Definition: var.hpp:153
Include smallest element.
Definition: set.hh:1385
With smallest unknown set.
Definition: set.hh:1270
Value iterator from range iterator.
Reification specification.
Definition: int.hh:855
void(* SetVarValPrint)(const Space &home, const Brancher &b, unsigned int a, SetVar x, int i, const int &n, std::ostream &o)
Function type for printing branching alternatives for set variables.
Definition: set.hh:1238
void(* SetBranchCommit)(Space &home, unsigned int a, SetVar x, int i, int n)
Branch commit function type for set variables.
Definition: set.hh:1138
SetValBranch SET_VAL_MAX_EXC(void)
Exclude largest element.
Definition: val.hpp:84
Iterator for the greatest lower bound ranges of a set variable.
Definition: set.hh:272
Subset ( )
Definition: set.hh:646
Include median element (rounding downwards)
Definition: set.hh:1457
SetVarBranch SET_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:118
Trace filters.
Include random element.
Definition: set.hh:1391
SetValBranch SET_VAL_MAX_INC(void)
Include largest element.
Definition: val.hpp:79
SetVarBranch SET_VAR_MAX_MAX(BranchTbl tbl)
Select variable with largest maximum unknown element.
Definition: var.hpp:178
Output stream to use std::ostream & os
Definition: set.hh:1720
double(* SetBranchMerit)(const Space &home, SetVar x, int i)
Branch merit function type for set variables.
Definition: set.hh:1113
Intersection
Definition: set.hh:663
void(* VoidFunction)(void)
Base type for any function pointer.
Definition: cast.hpp:45
Integer sets.
Definition: int.hh:172
With smallest minimum unknown element.
Definition: set.hh:1266
Less ( )
Definition: set.hh:651
SetVarBranch SET_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:203
With largest unknown set.
Definition: set.hh:1271
SetVarBranch SET_VAR_MAX_MIN(BranchTbl tbl)
Select variable with smallest maximum unknown element.
Definition: var.hpp:173
Execution information.
Definition: core.hpp:957
Recording AFC information for set variables.
Definition: set.hh:1152
Exclude random element.
Definition: set.hh:1462
Iterator for the least upper bound ranges of a set variable.
Definition: set.hh:304
Passing integer variables.
Definition: int.hh:637
Select s
Which value to select.
Definition: set.hh:1397
Passing integer arguments.
Definition: int.hh:608
Passing Boolean variables.
Definition: int.hh:691
With smallest degree.
Definition: set.hh:1260
void notMax(Home home, SetVar s, IntVar x)
Post propagator that propagates that x is not the maximal element of s.
Definition: int.cpp:155
Trace delta information for set variables.
Definition: set.hh:1642
SetValBranch SET_VAL_MIN_EXC(void)
Exclude smallest element.
Definition: val.hpp:64
SetVarBranch SET_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:213
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:818
SetAssign SET_ASSIGN_MIN_INC(void)
Include smallest element.
Definition: assign.hpp:59
const int v[7]
Definition: distinct.cpp:263
Set view for set variables
Definition: view.hpp:60
Union.
Definition: set.hh:661
Passing set variables.
Definition: set.hh:490
Greater or equal ( )
Definition: set.hh:652
SetAssign SET_ASSIGN_MED_INC(void)
Include median element (rounding downwards)
Definition: assign.hpp:69
Value branching information.
Definition: branch-val.hpp:44
Trace done events.
void relax(Home home, const FloatVarArgs &x, const FloatVarArgs &sx, Rnd r, double p)
Definition: relax.cpp:61
SetVarBranch SET_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:96
Select
Which value selection.
Definition: set.hh:1384
Variable branching information.
Definition: branch-var.hpp:55
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:277
Set variables
Definition: set.hh:129
Disjoint union.
Definition: set.hh:662
void convex(Home home, SetVar x)
Post propagator that propagates that x is convex.
Definition: convex.cpp:45
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:198
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel)
Post propagator that s precedes t in x.
Definition: precede.cpp:47
Integer variables.
Definition: int.hh:351
SetAssign SET_ASSIGN_MED_EXC(void)
Exclude median element (rounding downwards)
Definition: assign.hpp:74
Iterator for the values in the greatest lower bound of a set variable.
Definition: set.hh:368
Iterator over new lub Set::LubRanges< Set::SetView > n
Definition: set.hh:1671
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
With smallest degree divided by domain size.
Definition: set.hh:1272
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Post propagator for .
Definition: int.cpp:179
SetValBranch SET_VAL_MED_EXC(void)
Exclude median element (rounding downwards)
Definition: val.hpp:74
bool(* SetBranchFilter)(const Space &home, SetVar x, int i)
Branch filter function type for set variables.
Definition: set.hh:1101
Greater ( )
Definition: set.hh:653
Equality ( )
Definition: set.hh:644
Disjoint ( )
Definition: set.hh:648
Include median element (rounding downwards)
Definition: set.hh:1387
Tracer that process trace information.
Definition: tracer.hpp:55
Select
Which value selection.
Definition: set.hh:1454
Trace fixpoint events.
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &vars, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:94
Set variable array
Definition: set.hh:570
Lists of ranges (intervals)
Definition: range-list.hpp:53
Disequality ( )
Definition: set.hh:645
Exclude largest element.
Definition: set.hh:1390
Which value to select for assignment.
Definition: set.hh:1451
Gecode toplevel namespace
Argument array for variables.
Definition: array.hpp:53
void wait(Home home, FloatVar x, void(*c)(Space &home))
Execute c when x becomes assigned.
Definition: exec.cpp:44
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
SetVarBranch SET_VAR_ACTIVITY_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest activity divided by domain size with decay factor d. ...
Definition: var.hpp:233
SetAssign SET_ASSIGN_RND_INC(Rnd r)
Include random element.
Definition: assign.hpp:89
Include random element.
Definition: set.hh:1461
Which variable to select for branching.
Definition: set.hh:1252
Random number generator.
Definition: rnd.hpp:46
Exclude largest element.
Definition: set.hh:1460
Select s
Which variable to select.
Definition: set.hh:1281
SetVarBranch SET_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest minimum unknown element.
Definition: var.hpp:163
Class for activity management.
Definition: activity.hpp:44
Iterator over old glb Iter::Ranges::RangeList o
Definition: set.hh:1652
Select s
Which value to select.
Definition: set.hh:1467
SetValBranch SET_VAL_RND_INC(Rnd r)
Include random element.
Definition: val.hpp:89
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
Home class for posting propagators
Definition: core.hpp:905
double tbl(const Gecode::Space &, double w, double b)
Test function for tie-break limit function.
Definition: branch.cpp:65
void notMin(Home home, SetVar s, IntVar x)
Post propagator that propagates that x is not the minimal element of s.
Definition: int.cpp:126
SetVarBranch SET_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:133
SetVarBranch SET_VAR_MERIT_MIN(SetBranchMerit bm, BranchTbl tbl)
Select variable with least merit according to branch merit function bm.
Definition: var.hpp:101
With smallest accumulated failure count.
Definition: set.hh:1262
#define GECODE_SET_EXPORT
Definition: set.hh:69
Iterator for the values in the least upper bound of a set variable.
Definition: set.hh:396
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
SetValBranch SET_VAL(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: val.hpp:99
Exclude smallest element.
Definition: set.hh:1386
double(* BranchTbl)(const Space &home, double w, double b)
Tie-break limit function.
Definition: branch-var.hpp:49