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 "gecode/limits.hh"
00046
00047 #include "gecode/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 "gecode/iter.hh"
00072 #include "gecode/support/shared-array.hh"
00073
00074 #include "gecode/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 "gecode/int/int-set.icc"
00240
00241
00242 #include "gecode/int/var.icc"
00243 #include "gecode/int/view.icc"
00244 #include "gecode/int/propagator.icc"
00245 #include "gecode/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
00451 GECODE_INT_EXPORT void
00452 distinct(Space* home, const IntVarArgs& x,
00453 IntConLevel icl=ICL_DEF);
00465 GECODE_INT_EXPORT void
00466 distinct(Space* home, const IntArgs& n, const IntVarArgs& x,
00467 IntConLevel icl=ICL_DEF);
00469
00470
00486 GECODE_INT_EXPORT void
00487 channel(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00488 IntConLevel icl=ICL_DEF);
00490
00491
00535 GECODE_INT_EXPORT void
00536 cumulatives(Space* home, const IntVarArgs& machine,
00537 const IntVarArgs& start, const IntVarArgs& duration,
00538 const IntVarArgs& end, const IntVarArgs& height,
00539 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00544 GECODE_INT_EXPORT void
00545 cumulatives(Space* home, const IntArgs& machine,
00546 const IntVarArgs& start, const IntVarArgs& duration,
00547 const IntVarArgs& end, const IntVarArgs& height,
00548 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00553 GECODE_INT_EXPORT void
00554 cumulatives(Space* home, const IntVarArgs& machine,
00555 const IntVarArgs& start, const IntArgs& duration,
00556 const IntVarArgs& end, const IntVarArgs& height,
00557 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00562 GECODE_INT_EXPORT void
00563 cumulatives(Space* home, const IntArgs& machine,
00564 const IntVarArgs& start, const IntArgs& duration,
00565 const IntVarArgs& end, const IntVarArgs& height,
00566 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00571 GECODE_INT_EXPORT void
00572 cumulatives(Space* home, const IntVarArgs& machine,
00573 const IntVarArgs& start, const IntVarArgs& duration,
00574 const IntVarArgs& end, const IntArgs& height,
00575 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00580 GECODE_INT_EXPORT void
00581 cumulatives(Space* home, const IntArgs& machine,
00582 const IntVarArgs& start, const IntVarArgs& duration,
00583 const IntVarArgs& end, const IntArgs& height,
00584 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00589 GECODE_INT_EXPORT void
00590 cumulatives(Space* home, const IntVarArgs& machine,
00591 const IntVarArgs& start, const IntArgs& duration,
00592 const IntVarArgs& end, const IntArgs& height,
00593 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00598 GECODE_INT_EXPORT void
00599 cumulatives(Space* home, const IntArgs& machine,
00600 const IntVarArgs& start, const IntArgs& duration,
00601 const IntVarArgs& end, const IntArgs& height,
00602 const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00604
00605
00611 class DFA;
00612
00614
00615 class GECODE_INT_EXPORT REG {
00616 friend class DFA;
00617 private:
00619 class Exp;
00621 Exp* e;
00623 REG(Exp* e);
00624 public:
00626 REG(const REG& r);
00628 const REG& operator=(const REG& r);
00629
00631 REG(void);
00633 REG(int);
00635 REG operator()(unsigned int n, unsigned int m);
00637 REG operator()(unsigned int n);
00639 REG operator|(const REG& r);
00641 REG operator+(const REG& r);
00643 REG operator*(void);
00647 REG operator+(void);
00649 std::ostream& print(std::ostream&) const;
00651 ~REG(void);
00652 };
00653
00661 class DFA {
00662 public:
00664 class Transition {
00665 public:
00666 int i_state;
00667 int symbol;
00668 int o_state;
00669 };
00671 class Transitions;
00672 private:
00674 class DFAI;
00676 DFAI* dfai;
00677 protected:
00678 GECODE_INT_EXPORT
00686 void init(int start, Transition t_spec[], int f_spec[],
00687 bool minimize);
00688 public:
00689 friend class Transitions;
00691 DFA(void);
00702 DFA(int s, Transition t[], int f[], bool minimize=true);
00703 GECODE_INT_EXPORT
00705 DFA(REG& r);
00707 DFA(const DFA& d);
00709 const DFA& operator=(const DFA&);
00711 ~DFA(void);
00718 void update(bool share, DFA& d);
00720 unsigned int n_states(void) const;
00722 unsigned int n_transitions(void) const;
00724 int final_fst(void) const;
00726 int final_lst(void) const;
00728 int symbol_min(void) const;
00730 int symbol_max(void) const;
00731 };
00732
00739 GECODE_INT_EXPORT void
00740 regular(Space* home, const IntVarArgs& x, DFA& d,
00741 IntConLevel=ICL_DEF);
00742
00744
00745 }
00746
00747 #include "gecode/int/regular/dfa.icc"
00748
00749 namespace Gecode {
00750
00777 GECODE_INT_EXPORT void
00778 sortedness(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00779 IntConLevel icl=ICL_DEF);
00780
00797 GECODE_INT_EXPORT void
00798 sortedness(Space*, const IntVarArgs& x, const IntVarArgs& y,
00799 const IntVarArgs& z,
00800 IntConLevel icl=ICL_DEF);
00802
00822 GECODE_INT_EXPORT void
00823 count(Space* home, const IntVarArgs& x, int n, IntRelType r, int m,
00824 IntConLevel icl=ICL_DEF);
00830 GECODE_INT_EXPORT void
00831 count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, int m,
00832 IntConLevel icl=ICL_DEF);
00838 GECODE_INT_EXPORT void
00839 count(Space* home, const IntVarArgs& x, int n, IntRelType r, IntVar z,
00840 IntConLevel icl=ICL_DEF);
00846 GECODE_INT_EXPORT void
00847 count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, IntVar z,
00848 IntConLevel icl=ICL_DEF);
00849
00850
00892 GECODE_INT_EXPORT void
00893 gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00894 int m, int unspec_low, int unspec_up, int min, int max,
00895 IntConLevel icl);
00896
00931 GECODE_INT_EXPORT void
00932 gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00933 int m, int unspec, int min, int max,
00934 IntConLevel icl);
00935
00957 GECODE_INT_EXPORT void
00958 gcc(Space* home, const IntVarArgs& x, int lb, int ub, IntConLevel icl);
00959
00980 GECODE_INT_EXPORT void
00981 gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel icl);
00982
00983
01006 GECODE_INT_EXPORT void
01007 gcc(Space* home, const IntVarArgs& x, const IntVarArgs& c,
01008 int min, int max,
01009 IntConLevel icl);
01010
01042 GECODE_INT_EXPORT void
01043 gcc(Space* home,
01044 const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
01045 int m, int unspec_low, int unspec_up, bool all, int min, int max,
01046 IntConLevel icl);
01047
01076 GECODE_INT_EXPORT void
01077 gcc(Space* home,
01078 const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
01079 int m, int unspec, bool all, int min, int max,
01080 IntConLevel icl);
01082
01089
01090 GECODE_INT_EXPORT void
01091 bool_not(Space* home, BoolVar b0, BoolVar b1,
01092 IntConLevel=ICL_DEF);
01093
01095 GECODE_INT_EXPORT void
01096 bool_eq(Space* home, BoolVar b0, BoolVar b1,
01097 IntConLevel=ICL_DEF);
01098
01100 GECODE_INT_EXPORT void
01101 bool_and(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01102 IntConLevel=ICL_DEF);
01104 GECODE_INT_EXPORT void
01105 bool_and(Space* home, BoolVar b0, BoolVar b1, bool b2,
01106 IntConLevel=ICL_DEF);
01108 GECODE_INT_EXPORT void
01109 bool_and(Space* home, const BoolVarArgs& b, BoolVar c,
01110 IntConLevel=ICL_DEF);
01112 GECODE_INT_EXPORT void
01113 bool_and(Space* home, const BoolVarArgs& b, bool c,
01114 IntConLevel=ICL_DEF);
01115
01117 GECODE_INT_EXPORT void
01118 bool_or(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01119 IntConLevel=ICL_DEF);
01121 GECODE_INT_EXPORT void
01122 bool_or(Space* home, BoolVar b0, BoolVar b1, bool b2,
01123 IntConLevel=ICL_DEF);
01125 GECODE_INT_EXPORT void
01126 bool_or(Space* home, const BoolVarArgs& b, BoolVar c,
01127 IntConLevel=ICL_DEF);
01129 GECODE_INT_EXPORT void
01130 bool_or(Space* home, const BoolVarArgs& b, bool c,
01131 IntConLevel=ICL_DEF);
01132
01134 GECODE_INT_EXPORT void
01135 bool_imp(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01136 IntConLevel=ICL_DEF);
01138 GECODE_INT_EXPORT void
01139 bool_imp(Space* home, BoolVar b0, BoolVar b1, bool b2,
01140 IntConLevel=ICL_DEF);
01141
01143 GECODE_INT_EXPORT void
01144 bool_eqv(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01145 IntConLevel=ICL_DEF);
01147 GECODE_INT_EXPORT void
01148 bool_eqv(Space* home, BoolVar b0, BoolVar b1, bool b2,
01149 IntConLevel=ICL_DEF);
01151 GECODE_INT_EXPORT void
01152 bool_xor(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01153 IntConLevel=ICL_DEF);
01155 GECODE_INT_EXPORT void
01156 bool_xor(Space* home, BoolVar b0, BoolVar b1, bool b2,
01157 IntConLevel=ICL_DEF);
01158
01160
01171 GECODE_INT_EXPORT void
01172 min(Space* home, IntVar x0, IntVar x1, IntVar x2,
01173 IntConLevel=ICL_DEF);
01178 GECODE_INT_EXPORT void
01179 min(Space* home, const IntVarArgs& x, IntVar y,
01180 IntConLevel=ICL_DEF);
01186 GECODE_INT_EXPORT void
01187 max(Space* home, IntVar x0, IntVar x1, IntVar x2,
01188 IntConLevel=ICL_DEF);
01194 GECODE_INT_EXPORT void
01195 max(Space* home, const IntVarArgs& x, IntVar y,
01196 IntConLevel=ICL_DEF);
01197
01202 GECODE_INT_EXPORT void
01203 abs(Space* home, IntVar x0, IntVar x1,
01204 IntConLevel=ICL_DEF);
01205
01211 GECODE_INT_EXPORT void
01212 mult(Space* home, IntVar x0, IntVar x1, IntVar x2,
01213 IntConLevel=ICL_DEF);
01215
01245
01246 GECODE_INT_EXPORT void
01247 linear(Space* home, const IntVarArgs& x,
01248 IntRelType r, int c,
01249 IntConLevel=ICL_DEF);
01251 GECODE_INT_EXPORT void
01252 linear(Space* home, const IntVarArgs& x,
01253 IntRelType r, IntVar y,
01254 IntConLevel=ICL_DEF);
01256 GECODE_INT_EXPORT void
01257 linear(Space* home, const IntVarArgs& x,
01258 IntRelType r, int c, BoolVar b, IntConLevel=ICL_DEF);
01260 GECODE_INT_EXPORT void
01261 linear(Space* home, const IntVarArgs& x,
01262 IntRelType r, IntVar y, BoolVar b, IntConLevel=ICL_DEF);
01268 GECODE_INT_EXPORT void
01269 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01270 IntRelType r, int c,
01271 IntConLevel=ICL_DEF);
01277 GECODE_INT_EXPORT void
01278 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01279 IntRelType r, IntVar y,
01280 IntConLevel=ICL_DEF);
01286 GECODE_INT_EXPORT void
01287 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01288 IntRelType r, int c, BoolVar b,
01289 IntConLevel=ICL_DEF);
01295 GECODE_INT_EXPORT void
01296 linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01297 IntRelType r, IntVar y, BoolVar b,
01298 IntConLevel=ICL_DEF);
01299
01301 GECODE_INT_EXPORT void
01302 linear(Space* home, const BoolVarArgs& x,
01303 IntRelType r, int c,
01304 IntConLevel=ICL_DEF);
01305
01307 GECODE_INT_EXPORT void
01308 linear(Space* home, const BoolVarArgs& x,
01309 IntRelType r, IntVar y,
01310 IntConLevel=ICL_DEF);
01311
01313
01314
01321
01322 enum BvarSel {
01323 BVAR_NONE,
01324 BVAR_MIN_MIN,
01325 BVAR_MIN_MAX,
01326 BVAR_MAX_MIN,
01327 BVAR_MAX_MAX,
01328 BVAR_SIZE_MIN,
01329 BVAR_SIZE_MAX,
01330
01336 BVAR_DEGREE_MIN,
01343 BVAR_DEGREE_MAX,
01349 BVAR_REGRET_MIN_MIN,
01355 BVAR_REGRET_MIN_MAX,
01361 BVAR_REGRET_MAX_MIN,
01367 BVAR_REGRET_MAX_MAX
01368 };
01369
01371 enum BvalSel {
01372 BVAL_MIN,
01373 BVAL_MED,
01374 BVAL_MAX,
01375 BVAL_SPLIT_MIN,
01376 BVAL_SPLIT_MAX
01377 };
01378
01380 GECODE_INT_EXPORT void
01381 branch(Space* home, const IntVarArgs& x, BvarSel vars, BvalSel vals);
01383
01389
01390 enum AvalSel {
01391 AVAL_MIN,
01392 AVAL_MED,
01393 AVAL_MAX
01394 };
01395
01397 GECODE_INT_EXPORT void
01398 assign(Space* home, const IntVarArgs& x, AvalSel vals);
01399
01401
01402 }
01403
01407 GECODE_INT_EXPORT std::ostream&
01408 operator<<(std::ostream&, const Gecode::REG& r);
01409
01413 GECODE_INT_EXPORT std::ostream&
01414 operator<<(std::ostream&, const Gecode::DFA& d);
01415
01416 #endif
01417
01418
01419