set.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.dev>
 *     Christian Schulte <schulte@gecode.dev>
 *
 *  Copyright:
 *     Guido Tack, 2005
 *     Christian Schulte, 2005
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */
 
#ifndef GECODE_TEST_SET_HH
#define GECODE_TEST_SET_HH
 
#include <gecode/set.hh>
#include "test/test.hh"
#include "test/int.hh"
 
namespace Test {

  namespace Set {



    class CountableSetValues {
    private:
      Gecode::IntSetValues dv;
      int cur;
      int i;
    public:
      CountableSetValues(void) {}
      CountableSetValues(const Gecode::IntSet& d0, int cur0)
      : dv(d0), cur(cur0), i(1) {
        if (! (i & cur))
          operator++();
      }

      void init(const Gecode::IntSet& d0, int cur0) {
        dv = d0;
        cur = cur0;
        i = 1;
        if (! (i & cur))
          operator++();
      }

      bool operator()(void) const {
        return i<=cur;
      }

      void operator++(void) {
        do {
          ++dv;
          i = i<<1;
        } while (! (i & cur) && i<cur);
      }

      int val(void) const { return dv.val(); }
    };

    class CountableSetRanges
    : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
    private:
      CountableSetValues v;
    public:
      CountableSetRanges(void) {}
      CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
        Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
      }

      void init(const Gecode::IntSet& d, int cur) {
        v.init(d, cur);
        Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
      }
    };

    class CountableSet {
    private:
      Gecode::IntSet d;
      unsigned int cur;
      unsigned int lubmax;
    public:
      CountableSet(const Gecode::IntSet& s);
      CountableSet(void) {}
      void init(const Gecode::IntSet& s);
      bool operator()(void) const { return cur<lubmax; }
      void operator++(void);
      int val(void) const;
    };

    class SetAssignment {
    private:
      int n;
      CountableSet* dsv;
      Test::Int::CpltAssignment ir;
      bool done;
    public:
      Gecode::IntSet lub;
      int withInt;
      SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
      bool operator()(void) const { return !done; }
      void next(Gecode::Support::RandomGenerator& rand);
      int operator[](int i) const {
        assert((i>=0) && (i<n));
        return dsv[i].val();
      }

      int intval(void) const { return ir[0]; }
      const Test::Int::Assignment& ints(void) const { return ir; }
      int size(void) const { return n; }
      ~SetAssignment(void) { delete [] dsv; }
    };
 
 
    class SetTest;

    class SetTestSpace : public Gecode::Space {
    public:
      Gecode::IntSet d;
      Gecode::SetVarArray x;
      Gecode::IntVarArray y;
      int withInt;
      Gecode::Reify r;
      bool reified;
      SetTest* test;

      SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
                   bool log=true);
      SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
                   Gecode::ReifyMode rm, bool log=true);
      SetTestSpace(SetTestSpace& s);
      virtual Gecode::Space* copy(void);
      void post(void);
      bool failed(void);
      bool subsumed(bool b);
      void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
      void cardinality(int i, int cmin, int cmax);
      void rel(int i, Gecode::IntRelType irt, int n);
      void rel(bool sol);
      void assign(const SetAssignment& a, Gecode::Support::RandomGenerator& rand);
      bool assigned(void) const;
      void removeFromLub(int v, int i, const SetAssignment& a);
      void removeFromLub(int v, int i, const SetAssignment& a,
                         SetTestSpace& c);
      void addToGlb(int v, int i, const SetAssignment& a);
      void addToGlb(int v, int i, const SetAssignment& a,
                    SetTestSpace& c);
      bool fixprob(void);
      bool prune(const SetAssignment& a, Gecode::Support::RandomGenerator& rand);
      unsigned int propagators(void);
      void disable(void);
      void enable(void);
      bool disabled(const SetAssignment& a, SetTestSpace& c, Gecode::Support::RandomGenerator& rand);
      bool same(SetTestSpace& c);
    };

    class SetTest : public Base {
    private:
      int     arity;
      Gecode::IntSet  lub;
      bool reified;
      int withInt;

      void removeFromLub(int v, Gecode::SetVar& x, int i,
                         const Gecode::IntSet& a);
      void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
      SetAssignment* make_assignment(void);
    protected:
      bool disabled;
      bool testsubsumed;
    public:
      SetTest(const std::string& s,
              int a, const Gecode::IntSet& d, bool r=false, int w=0)
        : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
          disabled(true), testsubsumed(true) {}

      virtual bool solution(const SetAssignment&) const = 0;
      virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
                        Gecode::IntVarArray& y) = 0;
      virtual void post(Gecode::Space&, Gecode::SetVarArray&,
                        Gecode::IntVarArray&, Gecode::Reify) {}

      virtual bool run(void);



      static std::string str(Gecode::SetRelType srt);
      static std::string str(Gecode::SetOpType srt);
      static std::string str(int i);
      static std::string str(const Gecode::IntArgs& i);
    };


    class SetRelTypes {
    private:
      static const Gecode::SetRelType srts[6];
      int i;
    public:
      SetRelTypes(void);
      bool operator()(void) const;
      void operator++(void);
      Gecode::SetRelType srt(void) const;
    };

    class SetOpTypes {
    private:
      static const Gecode::SetOpType sots[4];
      int i;
    public:
      SetOpTypes(void);
      bool operator()(void) const;
      void operator++(void);
      Gecode::SetOpType sot(void) const;
    };
 
}}

std::ostream&
operator<<(std::ostream&, const Test::Set::SetAssignment& a);
 
#include "test/set.hpp"
 
#endif
 
// STATISTICS: test-set