Generated on Tue Oct 22 2013 00:49:07 for Gecode by doxygen 1.8.4
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: 2013-05-08 13:30:48 +0200 (Wed, 08 May 2013) $ by $Author: schulte $
17  * $Revision: 13622 $
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) : VarArgArray<SetVar>(n) {}
503  SetVarArgs(const std::vector<SetVar>& a) : VarArgArray<SetVar>(a) {}
505  template<class InputIterator>
506  SetVarArgs(InputIterator first, InputIterator last)
507  : VarArgArray<SetVar>(first,last) {}
515  SetVarArgs(Space& home,int n,int glbMin,int glbMax,
516  int lubMin,int lubMax,
517  unsigned int minCard = 0,
518  unsigned int maxCard = Set::Limits::card);
526  SetVarArgs(Space& home,int n,const IntSet& glb,
527  int lubMin, int lubMax,
528  unsigned int minCard = 0,
529  unsigned int maxCard = Set::Limits::card);
537  SetVarArgs(Space& home,int n,int glbMin,int glbMax,
538  const IntSet& lub,
539  unsigned int minCard = 0,
540  unsigned int maxCard = Set::Limits::card);
548  SetVarArgs(Space& home,int n,
549  const IntSet& glb,const IntSet& lub,
550  unsigned int minCard = 0,
551  unsigned int maxCard = Set::Limits::card);
553  };
555 
571  class SetVarArray : public VarArray<SetVar> {
572  public:
574 
575  SetVarArray(void);
578  SetVarArray(const SetVarArray&);
580  SetVarArray(Space& home, const SetVarArgs&);
582  GECODE_SET_EXPORT SetVarArray(Space& home, int n);
590  SetVarArray(Space& home,int n,int glbMin,int glbMax,int lubMin,int lubMax,
591  unsigned int minCard = 0,
592  unsigned int maxCard = Set::Limits::card);
600  SetVarArray(Space& home,int n,const IntSet& glb, int lubMin, int lubMax,
601  unsigned int minCard = 0,
602  unsigned int maxCard = Set::Limits::card);
610  SetVarArray(Space& home,int n,int glbMin,int glbMax,const IntSet& lub,
611  unsigned int minCard = 0,
612  unsigned int maxCard = Set::Limits::card);
620  SetVarArray(Space& home,int n,
621  const IntSet& glb,const IntSet& lub,
622  unsigned int minCard = 0,
623  unsigned int maxCard = Set::Limits::card);
625  };
626 
627 }
628 
629 #include <gecode/set/array.hpp>
630 
631 namespace Gecode {
632 
644  enum SetRelType {
655  };
656 
661  enum SetOpType {
666  };
667 
675 
677  GECODE_SET_EXPORT void
678  dom(Home home, SetVar x, SetRelType r, int i);
680  GECODE_SET_EXPORT void
681  dom(Home home, const SetVarArgs& x, SetRelType r, int i);
683  GECODE_SET_EXPORT void
684  dom(Home home, SetVar x, SetRelType r, int i, int j);
686  GECODE_SET_EXPORT void
687  dom(Home home, const SetVarArgs& x, SetRelType r, int i, int j);
689  GECODE_SET_EXPORT void
690  dom(Home home, SetVar x, SetRelType r, const IntSet& s);
692  GECODE_SET_EXPORT void
693  dom(Home home, const SetVarArgs& x, SetRelType r, const IntSet& s);
695  GECODE_SET_EXPORT void
696  cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
698  GECODE_SET_EXPORT void
699  cardinality(Home home, const SetVarArgs& x, unsigned int i, unsigned int j);
701  GECODE_SET_EXPORT void
702  dom(Home home, SetVar x, SetRelType rt, int i, Reify r);
704  GECODE_SET_EXPORT void
705  dom(Home home, SetVar x, SetRelType rt, int i, int j, Reify r);
707  GECODE_SET_EXPORT void
708  dom(Home home, SetVar x, SetRelType rt, const IntSet& s, Reify r);
710  GECODE_SET_EXPORT void
711  dom(Home home, SetVar x, SetVar d);
713  GECODE_SET_EXPORT void
714  dom(Home home, const SetVarArgs& x, const SetVarArgs& d);
716 
717 
725 
727  GECODE_SET_EXPORT void
728  rel(Home home, SetVar x, SetRelType r, SetVar y);
729 
731  GECODE_SET_EXPORT void
732  rel(Home home, SetVar x, SetRelType rt, SetVar y, Reify r);
733 
735  GECODE_SET_EXPORT void
736  rel(Home home, SetVar s, SetRelType r, IntVar x);
737 
739  GECODE_SET_EXPORT void
740  rel(Home home, IntVar x, SetRelType r, SetVar s);
741 
743  GECODE_SET_EXPORT void
744  rel(Home home, SetVar s, SetRelType rt, IntVar x, Reify r);
745 
747  GECODE_SET_EXPORT void
748  rel(Home home, IntVar x, SetRelType rt, SetVar s, Reify r);
749 
751  GECODE_SET_EXPORT void
752  rel(Home home, SetVar s, IntRelType r, IntVar x);
753 
755  GECODE_SET_EXPORT void
756  rel(Home home, IntVar x, IntRelType r, SetVar s);
757 
759 
767 
769  GECODE_SET_EXPORT void
770  rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
771 
773  GECODE_SET_EXPORT void
774  rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
775 
777  GECODE_SET_EXPORT void
778  rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
779 
781  GECODE_SET_EXPORT void
782  rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
783 
785  GECODE_SET_EXPORT void
786  rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
787 
789  GECODE_SET_EXPORT void
790  rel(Home home, const IntSet& x, SetOpType op, SetVar y,
791  SetRelType r, SetVar z);
792 
794  GECODE_SET_EXPORT void
795  rel(Home home, SetVar x, SetOpType op, const IntSet& y,
796  SetRelType r, SetVar z);
797 
799  GECODE_SET_EXPORT void
800  rel(Home home, SetVar x, SetOpType op, SetVar y,
801  SetRelType r, const IntSet& z);
802 
804  GECODE_SET_EXPORT void
805  rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
806  const IntSet& z);
807 
809  GECODE_SET_EXPORT void
810  rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
811  const IntSet& z);
812 
814 
815 
822 
824  GECODE_SET_EXPORT void
825  convex(Home home, SetVar x);
826 
828  GECODE_SET_EXPORT void
829  convex(Home home, SetVar x, SetVar y);
830 
832 
839 
841  GECODE_SET_EXPORT void
842  sequence(Home home, const SetVarArgs& x);
843 
845  GECODE_SET_EXPORT void
846  sequence(Home home, const SetVarArgs& y, SetVar x);
847 
849 
856 
857 
859  GECODE_SET_EXPORT void
860  atmostOne(Home home, const SetVarArgs& x, unsigned int c);
861 
863 
871 
874  GECODE_SET_EXPORT void
875  min(Home home, SetVar s, IntVar x);
876 
879  GECODE_SET_EXPORT void
880  notMin(Home home, SetVar s, IntVar x);
881 
884  GECODE_SET_EXPORT void
885  min(Home home, SetVar s, IntVar x, Reify r);
886 
889  GECODE_SET_EXPORT void
890  max(Home home, SetVar s, IntVar x);
891 
894  GECODE_SET_EXPORT void
895  notMax(Home home, SetVar s, IntVar x);
896 
899  GECODE_SET_EXPORT void
900  max(Home home, SetVar s, IntVar x, Reify r);
901 
903  GECODE_SET_EXPORT void
904  cardinality(Home home, SetVar s, IntVar x);
905 
916  GECODE_SET_EXPORT void
917  weights(Home home, IntSharedArray elements, IntSharedArray weights,
918  SetVar x, IntVar y);
919 
921 
929 
931  GECODE_SET_EXPORT void
932  channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
933 
935  GECODE_SET_EXPORT void
936  channelSorted(Home home, const IntVarArgs& x, SetVar y);
937 
939  GECODE_SET_EXPORT void
940  channel(Home home, const BoolVarArgs& x, SetVar y);
941 
943  GECODE_SET_EXPORT void
944  channel(Home home, const SetVarArgs& x, const SetVarArgs& y);
945 
947 
959  GECODE_SET_EXPORT void
960  precede(Home home, const SetVarArgs& x, int s, int t);
964  GECODE_SET_EXPORT void
965  precede(Home home, const SetVarArgs& x, const IntArgs& c);
966 
980 
990  GECODE_SET_EXPORT void
991  element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
992  const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
993 
1003  GECODE_SET_EXPORT void
1004  element(Home home, SetOpType op, const IntVarArgs& x, SetVar y, SetVar z,
1005  const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
1006 
1016  GECODE_SET_EXPORT void
1017  element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
1018  const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
1019 
1029  GECODE_SET_EXPORT void
1030  element(Home home, SetOpType op, const IntArgs& x, SetVar y, SetVar z,
1031  const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
1032 
1038  GECODE_SET_EXPORT void
1039  element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
1040 
1046  GECODE_SET_EXPORT void
1047  element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
1048 
1054  GECODE_SET_EXPORT void
1055  element(Home home, const IntSetArgs& a,
1056  IntVar x, int w, IntVar y, int h, SetVar z);
1062  GECODE_SET_EXPORT void
1063  element(Home home, const SetVarArgs& a,
1064  IntVar x, int w, IntVar y, int h, SetVar z);
1066 
1077  GECODE_SET_EXPORT void
1079  wait(Home home, SetVar x, void (*c)(Space& home));
1081  GECODE_SET_EXPORT void
1082  wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
1084 
1085 }
1086 
1087 namespace Gecode {
1088 
1102  typedef bool (*SetBranchFilter)(const Space& home, SetVar x, int i);
1103 
1114  typedef double (*SetBranchMerit)(const Space& home, SetVar x, int i);
1115 
1126  typedef int (*SetBranchVal)(const Space& home, SetVar x, int i);
1127 
1139  typedef void (*SetBranchCommit)(Space& home, unsigned int a,
1140  SetVar x, int i, int n);
1141 
1142 }
1143 
1145 
1146 namespace Gecode {
1147 
1153  class SetAFC : public AFC {
1154  public:
1162  SetAFC(void);
1164  SetAFC(const SetAFC& a);
1166  SetAFC& operator =(const SetAFC& a);
1168  SetAFC(Home home, const SetVarArgs& x, double d=1.0);
1176  void init(Home, const SetVarArgs& x, double d=1.0);
1177  };
1178 
1179 }
1180 
1181 #include <gecode/set/branch/afc.hpp>
1182 
1183 namespace Gecode {
1184 
1185 
1191  class SetActivity : public Activity {
1192  public:
1200  SetActivity(void);
1202  SetActivity(const SetActivity& a);
1204  SetActivity& operator =(const SetActivity& a);
1207  SetActivity(Home home, const SetVarArgs& x, double d=1.0);
1215  GECODE_SET_EXPORT void
1216  init(Home, const SetVarArgs& x, double d=1.0);
1217  };
1218 
1219 }
1220 
1222 
1223 namespace Gecode {
1224 
1226  typedef void (*SetVarValPrint)(const Space &home, const BrancherHandle& bh,
1227  unsigned int a,
1228  SetVar x, int i, const int& n,
1229  std::ostream& o);
1230 
1231 }
1232 
1233 namespace Gecode {
1234 
1240  class SetVarBranch : public VarBranch {
1241  public:
1243  enum Select {
1244  SEL_NONE = 0,
1266  };
1267  protected:
1270  public:
1272  SetVarBranch(void);
1274  SetVarBranch(Rnd r);
1278  SetVarBranch(Select s, double d, BranchTbl t);
1286  Select select(void) const;
1288  void expand(Home home, const SetVarArgs& x);
1289  };
1290 
1296  SetVarBranch SET_VAR_NONE(void);
1309  SetVarBranch SET_VAR_AFC_MIN(double d=1.0, BranchTbl tbl=NULL);
1313  SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=NULL);
1317  SetVarBranch SET_VAR_ACTIVITY_MIN(double d=1.0, BranchTbl tbl=NULL);
1321  SetVarBranch SET_VAR_ACTIVITY_MAX(double d=1.0, BranchTbl tbl=NULL);
1341  SetVarBranch SET_VAR_AFC_SIZE_MIN(double d=1.0, BranchTbl tbl=NULL);
1345  SetVarBranch SET_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=NULL);
1357 
1358 }
1359 
1360 #include <gecode/set/branch/var.hpp>
1361 
1362 namespace Gecode {
1363 
1369  class SetValBranch : public ValBranch {
1370  public:
1372  enum Select {
1382  };
1383  protected:
1386  public:
1394  Select select(void) const;
1395  };
1396 
1427 
1428 }
1429 
1430 #include <gecode/set/branch/val.hpp>
1431 
1432 namespace Gecode {
1433 
1439  class SetAssign : public ValBranch {
1440  public:
1442  enum Select {
1452  };
1453  protected:
1456  public:
1460  SetAssign(Select s, Rnd r);
1464  Select select(void) const;
1465  };
1466 
1496 
1497 }
1498 
1500 
1501 namespace Gecode {
1502 
1508  GECODE_SET_EXPORT BrancherHandle
1509  branch(Home home, const SetVarArgs& x,
1510  SetVarBranch vars, SetValBranch vals,
1511  SetBranchFilter bf=NULL,
1512  SetVarValPrint vvp=NULL);
1518  GECODE_SET_EXPORT BrancherHandle
1519  branch(Home home, const SetVarArgs& x,
1520  TieBreak<SetVarBranch> vars, SetValBranch vals,
1521  SetBranchFilter bf=NULL,
1522  SetVarValPrint vvp=NULL);
1528  GECODE_SET_EXPORT BrancherHandle
1529  branch(Home home, SetVar x, SetValBranch vals,
1530  SetVarValPrint vvp=NULL);
1536  GECODE_SET_EXPORT BrancherHandle
1537  assign(Home home, const SetVarArgs& x, SetAssign vals,
1538  SetBranchFilter bf=NULL,
1539  SetVarValPrint vvp=NULL);
1545  GECODE_SET_EXPORT BrancherHandle
1546  assign(Home home, SetVar x, SetAssign vals,
1547  SetVarValPrint vvp=NULL);
1548 
1549 }
1550 
1551 // LDSB-related declarations.
1552 namespace Gecode {
1554  GECODE_SET_EXPORT SymmetryHandle VariableSymmetry(const SetVarArgs& x);
1561  SymmetryHandle VariableSequenceSymmetry(const SetVarArgs& x, int ss);
1568  GECODE_SET_EXPORT BrancherHandle
1569  branch(Home home, const SetVarArgs& x,
1570  SetVarBranch vars, SetValBranch vals,
1571  const Symmetries& syms,
1572  SetBranchFilter bf=NULL,
1573  SetVarValPrint vvp=NULL);
1580  GECODE_SET_EXPORT BrancherHandle
1581  branch(Home home, const SetVarArgs& x,
1582  TieBreak<SetVarBranch> vars, SetValBranch vals,
1583  const Symmetries& syms,
1584  SetBranchFilter bf=NULL,
1585  SetVarValPrint vvp=NULL);
1586 }
1587 
1588 #endif
1589 
1590 // IFDEF: GECODE_HAS_SET_VARS
1591 // STATISTICS: set-post