Generated on Fri May 13 2011 22:41:22 for Gecode by doxygen 1.7.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: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $
00013  *     $Revision: 11390 $
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 
00057 
00058     class FakeSpace : public Gecode::Space {
00059     public:
00061       FakeSpace(void) {}
00063       virtual Gecode::Space* copy(bool share) {
00064         return NULL;
00065       }
00066     };
00067 
00073 
00075     class CountableSetValues {
00076     private:
00077       Gecode::IntSetValues dv;
00078       int cur;
00079       int i;
00080     public:
00082       CountableSetValues(void) {}
00084       CountableSetValues(const Gecode::IntSet& d0, int cur0)
00085       : dv(d0), cur(cur0), i(1) {
00086         if (! (i & cur))
00087           operator++();
00088       }
00090       void init(const Gecode::IntSet& d0, int cur0) {
00091         dv = d0;
00092         cur = cur0;
00093         i = 1;
00094         if (! (i & cur))
00095           operator++();
00096       }
00098       bool operator()(void) const {
00099         return i<=cur;
00100       }
00102       void operator++(void) {
00103         do {
00104           ++dv;
00105           i = i<<1;
00106         } while (! (i & cur) && i<cur);
00107       }
00109       int val(void) const { return dv.val(); }
00110     };
00111 
00113     class CountableSetRanges
00114     : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
00115     private:
00117       CountableSetValues v;
00118     public:
00120       CountableSetRanges(void) {}
00122       CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
00123         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00124       }
00126       void init(const Gecode::IntSet& d, int cur) {
00127         v.init(d, cur);
00128         Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00129       }
00130     };
00131 
00133     class CountableSet {
00134     private:
00136       Gecode::IntSet d;
00138       unsigned int cur;
00140       unsigned int lubmax;
00141     public:
00143       CountableSet(const Gecode::IntSet& s);
00145       CountableSet(void) {}
00147       void init(const Gecode::IntSet& s);
00149       bool operator()(void) const { return cur<lubmax; }
00151       void operator++(void);
00153       int val(void) const;
00154     };
00155 
00157     class SetAssignment {
00158     private:
00160       int n;
00162       CountableSet* dsv;
00164       Test::Int::CpltAssignment ir;
00166       bool done;
00167     public:
00169       Gecode::IntSet lub;
00171       int withInt;
00173       SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
00175       bool operator()(void) const { return !done; }
00177       void operator++(void);
00179       int operator[](int i) const {
00180         assert((i>=0) && (i<n));
00181         return dsv[i].val();
00182       }
00184       int intval(void) const { return ir[0]; }
00186       const Test::Int::Assignment& ints(void) const { return ir; }
00188       int size(void) const { return n; }
00190       ~SetAssignment(void) { delete [] dsv; }
00191     };
00192 
00193 
00194     class SetTest;
00195     
00197     class SetTestSpace : public Gecode::Space {
00198     public:
00200       Gecode::IntSet d;
00202       Gecode::SetVarArray x;
00204       Gecode::IntVarArray y;
00206       int withInt;
00208       Gecode::BoolVar b;
00210       bool reified;
00212       SetTest* test;
00213       
00223       SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t,
00224                    bool log=true);
00226       SetTestSpace(bool share, SetTestSpace& s);
00228       virtual Gecode::Space* copy(bool share);
00230       void post(void);
00232       bool failed(void);
00234       void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00236       void cardinality(int i, int cmin, int cmax);
00238       void rel(int i, Gecode::IntRelType irt, int n);
00240       void rel(bool sol);
00242       void assign(const SetAssignment& a);
00244       bool assigned(void) const;
00246       void removeFromLub(int v, int i, const SetAssignment& a);
00248       void addToGlb(int v, int i, const SetAssignment& a);
00250       bool fixprob(void);
00252       bool prune(const SetAssignment& a);
00253     };
00254 
00259     class SetTest : public Base {
00260     private:
00262       int     arity;
00264       Gecode::IntSet  lub;
00266       bool    reified;
00268       int    withInt;
00269 
00271       void removeFromLub(int v, Gecode::SetVar& x, int i,
00272                          const Gecode::IntSet& a);
00274       void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00275       SetAssignment* make_assignment(void);
00276     public:
00284       SetTest(const std::string& s,
00285               int a, const Gecode::IntSet& d, bool r=false, int w=0)
00286         : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w)  {}
00288       virtual bool solution(const SetAssignment&) const = 0;
00290       virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00291                         Gecode::IntVarArray& y) = 0;
00293       virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00294                         Gecode::IntVarArray&, Gecode::BoolVar) {}
00296       virtual bool run(void);
00297 
00299 
00300 
00301       static std::string str(Gecode::SetRelType srt);
00303       static std::string str(Gecode::SetOpType srt);
00305       static std::string str(int i);
00307     };
00309 
00311     class SetRelTypes {
00312     private:
00314       static const Gecode::SetRelType srts[6];
00316       int i;
00317     public:
00319       SetRelTypes(void);
00321       bool operator()(void) const;
00323       void operator++(void);
00325       Gecode::SetRelType srt(void) const;
00326     };
00327 
00329     class SetOpTypes {
00330     private:
00332       static const Gecode::SetOpType sots[4];
00334       int i;
00335     public:
00337       SetOpTypes(void);
00339       bool operator()(void) const;
00341       void operator++(void);
00343       Gecode::SetOpType sot(void) const;
00344     };
00345 
00346 }}
00347 
00352 std::ostream&
00353 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00354 
00355 #include "test/set.hpp"
00356 
00357 #endif
00358 
00359 // STATISTICS: test-set