00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef __GECODE_INT_HH__
00028 #define __GECODE_INT_HH__
00029
00030 namespace Gecode { namespace Int {
00031
00043 }}
00044
00045 #include "./limits.hh"
00046
00047 #include "./kernel.hh"
00048
00049
00050
00051
00052
00053
00054 #if !defined(GECODE_STATIC_LIBS) && \
00055 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00056
00057 #ifdef GECODE_BUILD_INT
00058 #define GECODE_INT_EXPORT __declspec( dllexport )
00059 #else
00060 #define GECODE_INT_EXPORT __declspec( dllimport )
00061 #endif
00062
00063 #else
00064
00065 #define GECODE_INT_EXPORT
00066
00067 #endif
00068
00069 #include <iostream>
00070
00071 #include "iter.hh"
00072 #include "support/shared-array.hh"
00073
00074 #include "int/exception.icc"
00075
00076 namespace Gecode {
00077
00078 class IntSetRanges;
00079
00087 class IntSet {
00088 friend class IntSetRanges;
00089 private:
00091 class Range {
00092 public:
00093 int min, max;
00094 };
00096 Support::SharedArray<Range> sar;
00098 class MinInc;
00100 GECODE_INT_EXPORT void normalize(int n);
00101 GECODE_INT_EXPORT void init(int n, int m);
00102 GECODE_INT_EXPORT void init(const int r[], int n);
00103 GECODE_INT_EXPORT void init(const int r[][2], int n);
00104 public:
00106
00107
00108 IntSet(void);
00110 IntSet(const IntSet& is);
00115 IntSet(int n, int m);
00117 IntSet(const int r[], int n);
00123 IntSet(const int r[][2], int n);
00125 template <class I>
00126 IntSet(I& i);
00128
00130
00131
00132 int size(void) const;
00134
00136
00137
00138 int min(int i) const;
00140 int max(int i) const;
00142 unsigned int width(int i) const;
00144
00146
00147
00148 int min(void) const;
00150 int max(void) const;
00152
00154
00155
00160 void update(bool share, IntSet& s);
00162
00164
00165
00166 GECODE_INT_EXPORT static const IntSet empty;
00168 };
00169
00175 class IntSetRanges {
00176 private:
00178 const IntSet::Range* i;
00180 const IntSet::Range* e;
00181 public:
00183
00184
00185 IntSetRanges(void);
00187 IntSetRanges(const IntSet& s);
00189 void init(const IntSet& s);
00191
00193
00194
00195 bool operator()(void) const;
00197 void operator++(void);
00199
00201
00202
00203 int min(void) const;
00205 int max(void) const;
00207 unsigned int width(void) const;
00209 };
00210
00216 class IntSetValues
00217 : public Iter::Ranges::ToValues<IntSetRanges> {
00218 public:
00220
00221
00222 IntSetValues(void);
00224 IntSetValues(const IntSet& s);
00226 void init(const IntSet& s);
00228 };
00229
00230 }
00231
00236 GECODE_INT_EXPORT std::ostream&
00237 operator<<(std::ostream&, const Gecode::IntSet& s);
00238
00239 #include "int/int-set.icc"
00240
00241
00242 #include "int/var.icc"
00243 #include "int/view.icc"
00244 #include "int/propagator.icc"
00245 #include "int/array.icc"
00246
00247
00248 namespace Gecode {
00249
00254 enum IntRelType {
00255 IRT_EQ,
00256 IRT_NQ,
00257 IRT_LQ,
00258 IRT_LE,
00259 IRT_GQ,
00260 IRT_GR
00261 };
00262
00276 enum IntConLevel {
00277 ICL_VAL,
00278 ICL_BND,
00279 ICL_DOM,
00280 ICL_DEF
00281 };
00282
00283
00284
00292
00293 GECODE_INT_EXPORT void
00294 dom(Space* home, IntVar x, int l, int m,
00295 IntConLevel=ICL_DEF);
00297 GECODE_INT_EXPORT void
00298 dom(Space* home, IntVarArgs& x, int l, int m,
00299 IntConLevel=ICL_DEF);
00300
00302 GECODE_INT_EXPORT void
00303 dom(Space* home, IntVar x, const IntSet& s,
00304 IntConLevel=ICL_DEF);
00306 GECODE_INT_EXPORT void
00307 dom(Space* home, IntVarArgs& x, const IntSet& s,
00308 IntConLevel=ICL_DEF);
00309
00311 GECODE_INT_EXPORT void
00312 dom(Space* home, IntVar x, int l, int m, BoolVar b,
00313 IntConLevel=ICL_DEF);
00315 GECODE_INT_EXPORT void
00316 dom(Space* home, IntVar x, const IntSet& s, BoolVar b,
00317 IntConLevel=ICL_DEF);
00319
00320
00327
00328
00334 GECODE_INT_EXPORT void
00335 rel(Space* home, IntVar x0, IntRelType r, IntVar x1,
00336 IntConLevel icl=ICL_DEF);
00338 GECODE_INT_EXPORT void
00339 rel(Space* home, IntVar x, IntRelType r, int c,
00340 IntConLevel icl=ICL_DEF);
00346 GECODE_INT_EXPORT void
00347 rel(Space* home, IntVar x0, IntRelType r, IntVar x1, BoolVar b,
00348 IntConLevel icl=ICL_DEF);
00354 GECODE_INT_EXPORT void
00355 rel(Space* home, IntVar x, IntRelType r, int c, BoolVar b,
00356 IntConLevel icl=ICL_DEF);
00357
00365 GECODE_INT_EXPORT void
00366 lex(Space* home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
00367 IntConLevel icl=ICL_DEF);
00369
00376
00382 GECODE_INT_EXPORT void
00383 eq(Space* home, IntVar x0, IntVar x1, IntConLevel icl=ICL_DEF);
00385 GECODE_INT_EXPORT void
00386 eq(Space* home, IntVar x, int n, IntConLevel=ICL_DEF);
00392 GECODE_INT_EXPORT void
00393 eq(Space* home, IntVar x0, IntVar x1, BoolVar b, IntConLevel icl=ICL_DEF);
00399 GECODE_INT_EXPORT void
00400 eq(Space* home, IntVar x, int n, BoolVar b, IntConLevel icl=ICL_DEF);
00406 GECODE_INT_EXPORT void
00407 eq(Space* home, const IntVarArgs& x, IntConLevel icl=ICL_DEF);
00409
00410
00411
00423 GECODE_INT_EXPORT void
00424 element(Space* home, const IntArgs& n, IntVar x0, IntVar x1,
00425 IntConLevel=ICL_DEF);
00431 GECODE_INT_EXPORT void
00432 element(Space* home, const IntVarArgs& x, IntVar y0, IntVar y1,
00433 IntConLevel icl=ICL_DEF);
00435
00436
00448 GECODE_INT_EXPORT void
00449 distinct(Space* home, const IntVarArgs& x,
00450 IntConLevel icl=ICL_DEF);
00460 GECODE_INT_EXPORT void
00461 distinct(Space* home, const IntArgs& n, const IntVarArgs& x,
00462 IntConLevel icl=ICL_DEF);
00464
00465
00509 GECODE_INT_EXPORT void
00510 cumulatives(Space* home, const IntVarArgs& machine,
00511 const IntVarArgs& start, const IntVarArgs& duration,
00512 const IntVarArgs& end, const IntVarArgs& height,
00513 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00518 GECODE_INT_EXPORT void
00519 cumulatives(Space* home, const IntArgs& machine,
00520 const IntVarArgs& start, const IntVarArgs& duration,
00521 const IntVarArgs& end, const IntVarArgs& height,
00522 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00527 GECODE_INT_EXPORT void
00528 cumulatives(Space* home, const IntVarArgs& machine,
00529 const IntVarArgs& start, const IntArgs& duration,
00530 const IntVarArgs& end, const IntVarArgs& height,
00531 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00536 GECODE_INT_EXPORT void
00537 cumulatives(Space* home, const IntArgs& machine,
00538 const IntVarArgs& start, const IntArgs& duration,
00539 const IntVarArgs& end, const IntVarArgs& height,
00540 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00545 GECODE_INT_EXPORT void
00546 cumulatives(Space* home, const IntVarArgs& machine,
00547 const IntVarArgs& start, const IntVarArgs& duration,
00548 const IntVarArgs& end, const IntArgs& height,
00549 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00554 GECODE_INT_EXPORT void
00555 cumulatives(Space* home, const IntArgs& machine,
00556 const IntVarArgs& start, const IntVarArgs& duration,
00557 const IntVarArgs& end, const IntArgs& height,
00558 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00563 GECODE_INT_EXPORT void
00564 cumulatives(Space* home, const IntVarArgs& machine,
00565 const IntVarArgs& start, const IntArgs& duration,
00566 const IntVarArgs& end, const IntArgs& height,
00567 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00572 GECODE_INT_EXPORT void
00573 cumulatives(Space* home, const IntArgs& machine,
00574 const IntVarArgs& start, const IntArgs& duration,
00575 const IntVarArgs& end, const IntArgs& height,
00576 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00578
00579
00585 class DFA;
00586
00588
00589 class GECODE_INT_EXPORT REG {
00590 friend class DFA;
00591 private:
00593 class Exp;
00595 Exp* e;
00597 REG(Exp* e);
00598 public:
00600 REG(const REG& r);
00602 const REG& operator=(const REG& r);
00603
00605 REG(void);
00607 REG(int);
00609 REG operator()(unsigned int n, unsigned int m);
00611 REG operator()(unsigned int n);
00613 REG operator|(const REG& r);
00615 REG operator+(const REG& r);
00617 REG operator*(void);
00621 REG operator+(void);
00623 std::ostream& print(std::ostream&) const;
00625 ~REG(void);
00626 };
00627
00635 class DFA {
00636 public:
00638 class Transition {
00639 public:
00640 int i_state;
00641 int symbol;
00642 int o_state;
00643 };
00645 class Transitions;
00646 private:
00648 class DFAI;
00650 DFAI* dfai;
00651 protected:
00652 GECODE_INT_EXPORT
00660 void init(int start, Transition t_spec[], int f_spec[],
00661 bool minimize);
00662 public:
00663 friend class Transitions;
00665 DFA(void);
00676 DFA(int s, Transition t[], int f[], bool minimize=true);
00677 GECODE_INT_EXPORT
00679 DFA(REG& r);
00681 DFA(const DFA& d);
00683 const DFA& operator=(const DFA&);
00685 ~DFA(void);
00692 void update(bool share, DFA& d);
00694 unsigned int n_states(void) const;
00696 unsigned int n_transitions(void) const;
00698 int final_fst(void) const;
00700 int final_lst(void) const;
00702 int symbol_min(void) const;
00704 int symbol_max(void) const;
00705 };
00706
00713 GECODE_INT_EXPORT void
00714 regular(Space* home, const IntVarArgs& x, DFA& d,
00715 IntConLevel=ICL_DEF);
00716
00718
00719 }
00720
00721 #include "int/regular/dfa.icc"
00722
00723 namespace Gecode {
00724
00746 GECODE_INT_EXPORT void
00747 sortedness(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00748 IntConLevel icl=ICL_DEF);
00760 GECODE_INT_EXPORT void
00761 sortedness(Space*, const IntVarArgs& x, const IntVarArgs& y,
00762 const IntVarArgs& z,
00763 IntConLevel icl=ICL_DEF);
00765
00777 GECODE_INT_EXPORT void
00778 count(Space* home, const IntVarArgs& x, int n, IntRelType r, int m,
00779 IntConLevel icl=ICL_DEF);
00785 GECODE_INT_EXPORT void
00786 count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, int m,
00787 IntConLevel icl=ICL_DEF);
00793 GECODE_INT_EXPORT void
00794 count(Space* home, const IntVarArgs& x, int n, IntRelType r, IntVar z,
00795 IntConLevel icl=ICL_DEF);
00801 GECODE_INT_EXPORT void
00802 count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, IntVar z,
00803 IntConLevel icl=ICL_DEF);
00804
00829 GECODE_INT_EXPORT void
00830 gcc(Space* home, const IntVarArgs& x, const IntArgs& c, int m, int unspec,
00831 int min, int max,
00832 IntConLevel icl);
00833
00865 GECODE_INT_EXPORT void
00866 gcc(Space* home, const IntVarArgs& x, const IntArgs& c, int m,
00867 int unspec_low, int unspec_up, int min, int max,
00868 IntConLevel icl);
00869
00881 GECODE_INT_EXPORT void
00882 gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel cl);
00883
00898 GECODE_INT_EXPORT void
00899 gcc(Space* home, const IntVarArgs& x, int lb, int ub, IntConLevel cl);
00900
00912 GECODE_INT_EXPORT void
00913 gcc(Space* home, const IntVarArgs& x, const IntVarArgs& c,
00914 int min, int max,
00915 IntConLevel cl);
00916
00929 GECODE_INT_EXPORT void
00930 gcc(Space* home, const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
00931 int m, int unspec, bool all, int min, int max,
00932 IntConLevel icl);
00933
00947 GECODE_INT_EXPORT void
00948 gcc(Space* home, const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
00949 int m, int unspec_low, int unspec_up, bool all, int min, int max,
00950 IntConLevel icl);
00951
00953
00960
00961 GECODE_INT_EXPORT void
00962 bool_not(Space* home, BoolVar b0, BoolVar b1,
00963 IntConLevel=ICL_DEF);
00964
00966 GECODE_INT_EXPORT void
00967 bool_eq(Space* home, BoolVar b0, BoolVar b1,
00968 IntConLevel=ICL_DEF);
00969
00971 GECODE_INT_EXPORT void
00972 bool_and(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00973 IntConLevel=ICL_DEF);
00975 GECODE_INT_EXPORT void
00976 bool_and(Space* home, const BoolVarArgs& b, BoolVar c,
00977 IntConLevel=ICL_DEF);
00978
00980 GECODE_INT_EXPORT void
00981 bool_or(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00982 IntConLevel=ICL_DEF);
00984 GECODE_INT_EXPORT void
00985 bool_or(Space* home, const BoolVarArgs& b, BoolVar c,
00986 IntConLevel=ICL_DEF);
00987
00989 GECODE_INT_EXPORT void
00990 bool_imp(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00991 IntConLevel=ICL_DEF);
00992
00994 GECODE_INT_EXPORT void
00995 bool_eqv(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00996 IntConLevel=ICL_DEF);
00998 GECODE_INT_EXPORT void
00999 bool_xor(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01000 IntConLevel=ICL_DEF);
01001
01003
01014 GECODE_INT_EXPORT void
01015 min(Space* home, IntVar x0, IntVar x1, IntVar x2,
01016 IntConLevel=ICL_DEF);
01021 GECODE_INT_EXPORT void
01022 min(Space* home, const IntVarArgs& x, IntVar y,
01023 IntConLevel=ICL_DEF);
01029 GECODE_INT_EXPORT void
01030 max(Space* home, IntVar x0, IntVar x1, IntVar x2,
01031 IntConLevel=ICL_DEF);
01037 GECODE_INT_EXPORT void
01038 max(Space* home, const IntVarArgs& x, IntVar y,
01039 IntConLevel=ICL_DEF);
01040
01045 GECODE_INT_EXPORT void
01046 abs(Space* home, IntVar x0, IntVar x1,
01047 IntConLevel=ICL_DEF);
01048
01054 GECODE_INT_EXPORT void
01055 mult(Space* home, IntVar x0, IntVar x1, IntVar x2,
01056 IntConLevel=ICL_DEF);
01058
01082
01083 GECODE_INT_EXPORT void
01084 linear(Space* home, const IntVarArgs& x,
01085 IntRelType r, int c,
01086 IntConLevel=ICL_DEF);
01088 GECODE_INT_EXPORT void
01089 linear(Space* home, const IntVarArgs& x,
01090 IntRelType r, IntVar y,
01091 IntConLevel=ICL_DEF);
01093 GECODE_INT_EXPORT void
01094 linear(Space* home, const IntVarArgs& x,
01095 IntRelType r, int c, BoolVar b, IntConLevel=ICL_DEF);
01097 GECODE_INT_EXPORT void
01098 linear(Space* home, const IntVarArgs& x,
01099 IntRelType r, IntVar y, BoolVar b, IntConLevel=ICL_DEF);
01105 GECODE_INT_EXPORT void
01106 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01107 IntRelType r, int c,
01108 IntConLevel=ICL_DEF);
01114 GECODE_INT_EXPORT void
01115 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01116 IntRelType r, IntVar y,
01117 IntConLevel=ICL_DEF);
01123 GECODE_INT_EXPORT void
01124 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01125 IntRelType r, int c, BoolVar b,
01126 IntConLevel=ICL_DEF);
01132 GECODE_INT_EXPORT void
01133 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01134 IntRelType r, IntVar y, BoolVar b,
01135 IntConLevel=ICL_DEF);
01136
01138 GECODE_INT_EXPORT void
01139 linear(Space* home, const BoolVarArgs& x,
01140 IntRelType r, int c,
01141 IntConLevel=ICL_DEF);
01142
01144 GECODE_INT_EXPORT void
01145 linear(Space* home, const BoolVarArgs& x,
01146 IntRelType r, IntVar y,
01147 IntConLevel=ICL_DEF);
01148
01150
01151
01158
01159 enum BvarSel {
01160 BVAR_NONE,
01161 BVAR_MIN_MIN,
01162 BVAR_MIN_MAX,
01163 BVAR_MAX_MIN,
01164 BVAR_MAX_MAX,
01165 BVAR_SIZE_MIN,
01166 BVAR_SIZE_MAX,
01167
01173 BVAR_DEGREE_MIN,
01180 BVAR_DEGREE_MAX,
01186 BVAR_REGRET_MIN_MIN,
01192 BVAR_REGRET_MIN_MAX,
01198 BVAR_REGRET_MAX_MIN,
01204 BVAR_REGRET_MAX_MAX
01205 };
01206
01208 enum BvalSel {
01209 BVAL_MIN,
01210 BVAL_MED,
01211 BVAL_MAX,
01212 BVAL_SPLIT_MIN,
01213 BVAL_SPLIT_MAX
01214 };
01215
01217 GECODE_INT_EXPORT void
01218 branch(Space* home, const IntVarArgs& x, BvarSel vars, BvalSel vals);
01220
01226
01227 enum AvalSel {
01228 AVAL_MIN,
01229 AVAL_MED,
01230 AVAL_MAX
01231 };
01232
01234 GECODE_INT_EXPORT void
01235 assign(Space* home, const IntVarArgs& x, AvalSel vals);
01236
01238
01239 }
01240
01244 GECODE_INT_EXPORT std::ostream&
01245 operator<<(std::ostream&, const Gecode::REG& r);
01246
01250 GECODE_INT_EXPORT std::ostream&
01251 operator<<(std::ostream&, const Gecode::DFA& d);
01252
01253 #endif
01254
01255
01256