Generated on Mon Nov 30 23:53:35 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00012  *     $Date: 2009-06-08 11:14:18 +0200 (Mon, 08 Jun 2009) $ by $Author: schulte $
00013  *     $Revision: 9211 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #ifndef __GECODE_TEST_SET_HH__
00041 #define __GECODE_TEST_SET_HH__
00042 
00043 #include <gecode/set.hh>
00044 #include "test/test.hh"
00045 #include "test/int.hh"
00046 
00047 namespace Test {
00048 
00050   namespace Set {
00051 
00062 
00064     class CountableSetValues {
00065     private:
00066       Gecode::IntSetValues dv;
00067       int cur;
00068       int i;
00069     public:
00071       CountableSetValues(void) {}
00073       CountableSetValues(const Gecode::IntSet& d0, int cur0)
00074       : dv(d0), cur(cur0), i(1) {
00075         if (! (i & cur))
00076           operator++();
00077       }
00079       void init(const Gecode::IntSet& d0, int cur0) {
00080         dv = d0;
00081         cur = cur0;
00082         i = 1;
00083         if (! (i & cur))
00084           operator++();
00085       }
00087       bool operator()(void) const {
00088         return i<=cur;
00089       }
00091       void operator++(void) {
00092         do {
00093           ++dv;
00094           i = i<<1;
00095         } while (! (i & cur) && i<cur);
00096       }
00098       int val(void) const { return dv.val(); }
00099     };
00100 
00102     class CountableSetRanges
00103     : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
00104     private:
00106       CountableSetValues v;
00107     public:
00109       CountableSetRanges(void) {}
00111       CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
00112         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00113       }
00115       void init(const Gecode::IntSet& d, int cur) {
00116         v.init(d, cur);
00117         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00118       }
00119     };
00120 
00122     class CountableSet {
00123     private:
00125       Gecode::IntSet d;
00127       unsigned int cur;
00129       unsigned int lubmax;
00130     public:
00132       CountableSet(const Gecode::IntSet& s);
00134       CountableSet(void) {}
00136       void init(const Gecode::IntSet& s);
00138       bool operator()(void) const { return cur<lubmax; }
00140       void operator++(void);
00142       int val(void) const;
00143     };
00144 
00146     class SetAssignment {
00147     private:
00149       int n;
00151       CountableSet* dsv;
00153       Test::Int::CpltAssignment ir;
00155       bool done;
00156     public:
00158       Gecode::IntSet lub;
00160       int withInt;
00162       SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
00164       bool operator()(void) const { return !done; }
00166       void operator++(void);
00168       int operator[](int i) const {
00169         assert((i>=0) && (i<n));
00170         return dsv[i].val();
00171       }
00173       int intval(void) const { return ir[0]; }
00175       const Test::Int::Assignment& ints(void) const { return ir; }
00177       int size(void) const { return n; }
00179       ~SetAssignment(void) { delete [] dsv; }
00180     };
00181 
00182 
00183     class SetTest;
00184     
00186     class SetTestSpace : public Gecode::Space {
00187     public:
00189       Gecode::IntSet d;
00191       Gecode::SetVarArray x;
00193       Gecode::IntVarArray y;
00195       int withInt;
00197       Gecode::BoolVar b;
00199       bool reified;
00201       SetTest* test;
00202       
00212       SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t,
00213                    bool log=true);
00215       SetTestSpace(bool share, SetTestSpace& s);
00217       virtual Gecode::Space* copy(bool share);
00219       void post(void);
00221       bool failed(void);
00223       void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00225       void cardinality(int i, int cmin, int cmax);
00227       void rel(int i, Gecode::IntRelType irt, int n);
00229       void rel(bool sol);
00231       void assign(const SetAssignment& a);
00233       bool assigned(void) const;
00235       void removeFromLub(int v, int i, const SetAssignment& a);
00237       void addToGlb(int v, int i, const SetAssignment& a);
00239       bool fixprob(void);
00241       bool prune(const SetAssignment& a);
00242     };
00243 
00248     class SetTest : public Base {
00249     private:
00251       int     arity;
00253       Gecode::IntSet  lub;
00255       bool    reified;
00257       int    withInt;
00258 
00260       void removeFromLub(int v, Gecode::SetVar& x, int i,
00261                          const Gecode::IntSet& a);
00263       void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00264       SetAssignment* make_assignment(void);
00265     public:
00273       SetTest(const std::string& s,
00274               int a, const Gecode::IntSet& d, bool r=false, int w=0)
00275         : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w)  {}
00277       virtual bool solution(const SetAssignment&) const = 0;
00279       virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00280                         Gecode::IntVarArray& y) = 0;
00282       virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00283                         Gecode::IntVarArray&, Gecode::BoolVar) {}
00285       virtual bool run(void);
00286 
00288 
00289 
00290       static std::string str(Gecode::SetRelType srt);
00292       static std::string str(Gecode::SetOpType srt);
00294       static std::string str(int i);
00296     };
00298 
00300     class SetRelTypes {
00301     private:
00303       static const Gecode::SetRelType srts[6];
00305       int i;
00306     public:
00308       SetRelTypes(void);
00310       bool operator()(void) const;
00312       void operator++(void);
00314       Gecode::SetRelType srt(void) const;
00315     };
00316 
00318     class SetOpTypes {
00319     private:
00321       static const Gecode::SetOpType sots[4];
00323       int i;
00324     public:
00326       SetOpTypes(void);
00328       bool operator()(void) const;
00330       void operator++(void);
00332       Gecode::SetOpType sot(void) const;
00333     };
00334 
00335 }}
00336 
00341 std::ostream&
00342 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00343 
00344 #include "test/set.hpp"
00345 
00346 #endif
00347 
00348 // STATISTICS: test-set