Generated on Thu Apr 11 13:59:18 2019 for Gecode by doxygen 1.6.3

set.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Guido Tack, 2005
00009  *     Christian Schulte, 2005
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #ifndef __GECODE_TEST_SET_HH__
00037 #define __GECODE_TEST_SET_HH__
00038 
00039 #include <gecode/set.hh>
00040 #include "test/test.hh"
00041 #include "test/int.hh"
00042 
00043 namespace Test {
00044 
00046   namespace Set {
00047 
00058 
00060     class CountableSetValues {
00061     private:
00062       Gecode::IntSetValues dv;
00063       int cur;
00064       int i;
00065     public:
00067       CountableSetValues(void) {}
00069       CountableSetValues(const Gecode::IntSet& d0, int cur0)
00070       : dv(d0), cur(cur0), i(1) {
00071         if (! (i & cur))
00072           operator++();
00073       }
00075       void init(const Gecode::IntSet& d0, int cur0) {
00076         dv = d0;
00077         cur = cur0;
00078         i = 1;
00079         if (! (i & cur))
00080           operator++();
00081       }
00083       bool operator()(void) const {
00084         return i<=cur;
00085       }
00087       void operator++(void) {
00088         do {
00089           ++dv;
00090           i = i<<1;
00091         } while (! (i & cur) && i<cur);
00092       }
00094       int val(void) const { return dv.val(); }
00095     };
00096 
00098     class CountableSetRanges
00099     : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
00100     private:
00102       CountableSetValues v;
00103     public:
00105       CountableSetRanges(void) {}
00107       CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
00108         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00109       }
00111       void init(const Gecode::IntSet& d, int cur) {
00112         v.init(d, cur);
00113         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00114       }
00115     };
00116 
00118     class CountableSet {
00119     private:
00121       Gecode::IntSet d;
00123       unsigned int cur;
00125       unsigned int lubmax;
00126     public:
00128       CountableSet(const Gecode::IntSet& s);
00130       CountableSet(void) {}
00132       void init(const Gecode::IntSet& s);
00134       bool operator()(void) const { return cur<lubmax; }
00136       void operator++(void);
00138       int val(void) const;
00139     };
00140 
00142     class SetAssignment {
00143     private:
00145       int n;
00147       CountableSet* dsv;
00149       Test::Int::CpltAssignment ir;
00151       bool done;
00152     public:
00154       Gecode::IntSet lub;
00156       int withInt;
00158       SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
00160       bool operator()(void) const { return !done; }
00162       void operator++(void);
00164       int operator[](int i) const {
00165         assert((i>=0) && (i<n));
00166         return dsv[i].val();
00167       }
00169       int intval(void) const { return ir[0]; }
00171       const Test::Int::Assignment& ints(void) const { return ir; }
00173       int size(void) const { return n; }
00175       ~SetAssignment(void) { delete [] dsv; }
00176     };
00177 
00178 
00179     class SetTest;
00180 
00182     class SetTestSpace : public Gecode::Space {
00183     public:
00185       Gecode::IntSet d;
00187       Gecode::SetVarArray x;
00189       Gecode::IntVarArray y;
00191       int withInt;
00193       Gecode::Reify r;
00195       bool reified;
00197       SetTest* test;
00198 
00208       SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00209                    bool log=true);
00219       SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00220                    Gecode::ReifyMode rm, bool log=true);
00222       SetTestSpace(SetTestSpace& s);
00224       virtual Gecode::Space* copy(void);
00226       void post(void);
00228       bool failed(void);
00230       bool subsumed(bool b);
00232       void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00234       void cardinality(int i, int cmin, int cmax);
00236       void rel(int i, Gecode::IntRelType irt, int n);
00238       void rel(bool sol);
00240       void assign(const SetAssignment& a);
00242       bool assigned(void) const;
00244       void removeFromLub(int v, int i, const SetAssignment& a);
00246       void removeFromLub(int v, int i, const SetAssignment& a,
00247                          SetTestSpace& c);
00249       void addToGlb(int v, int i, const SetAssignment& a);
00251       void addToGlb(int v, int i, const SetAssignment& a,
00252                     SetTestSpace& c);
00254       bool fixprob(void);
00256       bool prune(const SetAssignment& a);
00258       unsigned int propagators(void);
00260       void disable(void);
00262       void enable(void);
00264       bool disabled(const SetAssignment& a, SetTestSpace& c);
00266       bool same(SetTestSpace& c);
00267     };
00268 
00273     class SetTest : public Base {
00274     private:
00276       int     arity;
00278       Gecode::IntSet  lub;
00280       bool reified;
00282       int withInt;
00283 
00285       void removeFromLub(int v, Gecode::SetVar& x, int i,
00286                          const Gecode::IntSet& a);
00288       void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00290       SetAssignment* make_assignment(void);
00291     protected:
00293       bool disabled;
00295       bool testsubsumed;
00296     public:
00304       SetTest(const std::string& s,
00305               int a, const Gecode::IntSet& d, bool r=false, int w=0)
00306         : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
00307           disabled(true), testsubsumed(true) {}
00309       virtual bool solution(const SetAssignment&) const = 0;
00311       virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00312                         Gecode::IntVarArray& y) = 0;
00314       virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00315                         Gecode::IntVarArray&, Gecode::Reify) {}
00317       virtual bool run(void);
00318 
00320 
00321 
00322       static std::string str(Gecode::SetRelType srt);
00324       static std::string str(Gecode::SetOpType srt);
00326       static std::string str(int i);
00328       static std::string str(const Gecode::IntArgs& i);
00330     };
00332 
00334     class SetRelTypes {
00335     private:
00337       static const Gecode::SetRelType srts[6];
00339       int i;
00340     public:
00342       SetRelTypes(void);
00344       bool operator()(void) const;
00346       void operator++(void);
00348       Gecode::SetRelType srt(void) const;
00349     };
00350 
00352     class SetOpTypes {
00353     private:
00355       static const Gecode::SetOpType sots[4];
00357       int i;
00358     public:
00360       SetOpTypes(void);
00362       bool operator()(void) const;
00364       void operator++(void);
00366       Gecode::SetOpType sot(void) const;
00367     };
00368 
00369 }}
00370 
00375 std::ostream&
00376 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00377 
00378 #include "test/set.hpp"
00379 
00380 #endif
00381 
00382 // STATISTICS: test-set