var-imp.icc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
 *
 *  Copyright:
 *     Patrick Pekczynski, 2006
 *
 *  Last modified:
 *     $Date: 2008-02-27 17:49:28 +0100 (Wed, 27 Feb 2008) $ by $Author: tack $
 *     $Revision: 6327 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  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.
 *
 */

#include <iostream>

namespace Gecode { namespace CpltSet {

  enum NodeStatus {
    INIT = -1,
    FIX_GLB = 1,
    FIX_NOT_LUB = 0,
    FIX_UNKNOWN = 2,
    UNDET = 5
  };

  template <class T> class GlbValues {
  public:


    GlbValues(void);
    GlbValues(const T& x);
    void init(const T& x);



    bool operator()(void) const;
    void operator++(void);



    int val(void) const;
  };

  template <class T> class LubValues {
  public:


    LubValues(void);
    LubValues(const T& x);
    void init(const T& x);



    bool operator()(void) const;
    void operator++(void);



    int min(void) const;
    int max(void) const;
  };

  template <class T> class UnknownValues {
  public:


    UnknownValues(void);
    UnknownValues(const T& x);
    void init(const T& x);



    bool operator()(void) const;
    void operator++(void);



    int val(void) const;
  };

  class CpltSetVarImp : public CpltSetVarImpBase {
    friend class BddIterator;
    friend class DomBddIterator;

    friend class GlbValues<CpltSetVarImp*>;
    friend class LubValues<CpltSetVarImp*>;
    friend class UnknownValues<CpltSetVarImp*>;

  public:
    static const int MAX_OF_EMPTY = Gecode::Set::Limits::min-1;
    static const int MIN_OF_EMPTY = Gecode::Set::Limits::max+1;

    void printdom(void) const;
  private:
    bdd domain;
    int min;
    int max;
    unsigned int _offset;
    bool _assigned;
  protected:
    GECODE_CPLTSET_EXPORT
    CpltSetVarImp(Space* home, bool share, CpltSetVarImp& x);
    template <class I>
    bdd iterToBdd(I& i);

  public:
    GECODE_CPLTSET_EXPORT
    CpltSetVarImp(Space* home, int glbMin, int glbMax, int lubMin, int lubMax, 
                  unsigned int cardMin, unsigned int cardMax);
    GECODE_CPLTSET_EXPORT
    CpltSetVarImp(Space* home, const IntSet& glbD, int lubMin, int lubMax, 
                  unsigned int cardMin, unsigned int cardMax);
    GECODE_CPLTSET_EXPORT
    CpltSetVarImp(Space* home, int glbMin, int glbMax, const IntSet& lubD,
                  unsigned int cardMin, unsigned int cardMax);
    GECODE_CPLTSET_EXPORT
    CpltSetVarImp(Space* home, const IntSet& glbD,const IntSet& lubD,
                  unsigned int cardMin, unsigned int cardMax);
    // Delete a bdd variable
    GECODE_CPLTSET_EXPORT
    void dispose(Space* home);
  public:


    ModEvent exclude(Space* home, int v);
    GECODE_CPLTSET_EXPORT ModEvent exclude(Space* home, int a, int b);

    ModEvent include(Space* home, int v);
    GECODE_CPLTSET_EXPORT ModEvent include(Space* home, int a, int b);

    ModEvent intersect(Space* home, int i);
    GECODE_CPLTSET_EXPORT ModEvent intersect(Space* home, int a, int b);



    template <class I> ModEvent intersectI(Space* home, I& i);
    template <class I> ModEvent excludeI(Space* home, I& i);  
    template <class I> ModEvent includeI(Space* home, I& i);  



    GECODE_CPLTSET_EXPORT ModEvent cardinality(Space* home, int l, int u);
    ModEvent cardMin(Space* home,unsigned int n);
    ModEvent cardMax(Space* home,unsigned int n);



    ModEvent nq(Space* home, int v);
    GECODE_CPLTSET_EXPORT ModEvent nq(Space* home, int a, int b);

    ModEvent eq(Space* home, int v);
    GECODE_CPLTSET_EXPORT ModEvent eq(Space* home, int a, int b);



    template <class I> ModEvent nqI(Space* home, I& i);
    template <class I> ModEvent eqI(Space* home, I& i);



    GECODE_CPLTSET_EXPORT ModEvent intersect(Space* home, bdd& d);
    


    unsigned int cardMin(void) const;
    unsigned int cardMax(void) const;

    GECODE_CPLTSET_EXPORT int glbMin(void) const;
    GECODE_CPLTSET_EXPORT int glbMax(void) const;
    GECODE_CPLTSET_EXPORT unsigned int glbSize(void) const;
    GECODE_CPLTSET_EXPORT int lubMin(void) const;
    GECODE_CPLTSET_EXPORT int lubMax(void) const;
    GECODE_CPLTSET_EXPORT unsigned int lubSize(void) const;
    GECODE_CPLTSET_EXPORT int lubMinN(int n) const;
    GECODE_CPLTSET_EXPORT int lubMaxN(int n) const;

    GECODE_CPLTSET_EXPORT int unknownMin(void) const;
    GECODE_CPLTSET_EXPORT int unknownMax(void) const;
    GECODE_CPLTSET_EXPORT unsigned int unknownSize(void) const;





    int initialLubMin(void) const;
    int initialLubMax(void) const;
    unsigned int tableWidth(void) const;
    unsigned int offset(void) const;
    bdd element(int i) const;
    bdd elementNeg(int i) const;
    bdd dom(void) const;



    GECODE_CPLTSET_EXPORT bool assigned(void) ;
    GECODE_CPLTSET_EXPORT bool knownIn(int i) const;
    GECODE_CPLTSET_EXPORT bool knownOut(int i) const;
    bool range(void) const;
    


    void subscribe(Space* home, Propagator* p, PropCond pc, bool process=true);
    void cancel(Space* home, Propagator* p, PropCond pc);

  private:
    GECODE_CPLTSET_EXPORT 
    CpltSetVarImp* perform_copy(Space* home, bool share);

  public:


    CpltSetVarImp* copy(Space* home, bool share);


    GECODE_CPLTSET_EXPORT Reflection::Arg*
    spec(const Space* home, Reflection::VarMap& m) const;



    static ModEvent modevent(const Delta* d);

  };


  class BddIterator {
  private:
    // Stores the bdd to be iterated
    bdd c;
    // Stores the current sub-bdd under exploration
    bdd cur;
    // ensure that there are no marked nodes when we leave the iterator
    int markref;
    // Number of nodes of c
    int n;
    // Range size of the initial variable domain, i.e. \f$ |[min, max]| \f$
    int m;
    // Stores for each node whether it is fixed, nonfixed or undetermined
    NodeStatus flag;
    bool singleton;
    // Explores the iterated bdd
    SharedArray<bdd> nodes;
    // Left end of the nodes array
    int l;
    // Right end of the nodes array
    int r;
    // If bypassed is true the current level cannot be fixed
    bool bypassed;
    // If on the same level an internal node has only leaf childs
    // and on another path has at least some internal child
    // then this child cannot be fixed
    bool onlyleaves;
    // The number of the current level in the bdd
    int _level;
    
    // marks all nodes in the cache 
    GECODE_CPLTSET_EXPORT void cache_mark(void);
    // unmarks all nodes in the cache 
    GECODE_CPLTSET_EXPORT void cache_unmark(void);
  public:

    BddIterator(void);
    BddIterator(const bdd&);
    GECODE_CPLTSET_EXPORT void init(const bdd&);



    bool operator()(void) const;
    GECODE_CPLTSET_EXPORT void operator++(void);



    NodeStatus status(void) const;
    int level(void) const;
    int label(void) const;
    bool empty(void) const;
    int size(void) const;
  };


  class DomBddIterator : public BddIterator {
  private:
    int vector_level;
    int mi;
    int ma;
    int off;
    int bdd_level;
  protected:
    bool same(void) const;
  public:

    DomBddIterator(void);
    DomBddIterator(const CpltSetVarImp* x);
    DomBddIterator(const CpltSetVarImp* x, bdd& remain);
    void init(const CpltSetVarImp* x);
    void init(const CpltSetVarImp* x, bdd& remain);



    bool operator()(void) const;
    void operator++(void);



    NodeStatus status(void) const;
    int val(void) const;
  };

}}

#include "gecode/cpltset/var-imp/cpltset.icc"

namespace Gecode {

  class CpltSetVar;

  template <>
  class VarImpVarTraits<CpltSet::CpltSetVarImp> {
  public:
    typedef CpltSetVar Var;
  };
}

// STATISTICS: cpltset-var