main page modules namespaces classes files
Gecode home

search for 

var.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Contributing authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Gabor Szokoli <szokoli@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *     Gabor Szokoli, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-25 10:43:21 +0200 (Fri, 25 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3568 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "gecode/support/shared-array.hh"

#include <iostream>

#include "gecode/set/var/imp-hdr.icc"
#include "gecode/iter.hh"

namespace Gecode { namespace Set {

  class RangeList : public FreeList {
  protected:
    int        _min;
    int        _max;
  public:


    RangeList(void);
    RangeList(int min, int max, RangeList* p, RangeList* n);



    int min(void) const;
    int max(void) const;
    unsigned int width(void) const;

    RangeList* next(const RangeList* p) const;
    RangeList* prev(const RangeList* n) const;



    void min(int n);
    void max(int n);

    void prevnext(RangeList* p, RangeList* n);
    void next(RangeList* o, RangeList* n);
    void prev(RangeList* o, RangeList* n);
    void fix(RangeList* n);



    void dispose(Space* home, RangeList* p, RangeList* l);
    
    static void* operator new(size_t s, Space* home);
    static void  operator delete(void*);
    static void  operator delete(void*, Space* home);
  };


  class BndSet  {
  private:
    RangeList* first;
    RangeList* last;
  protected:
    unsigned int _size;
    void fst(RangeList* r);
    void lst(RangeList* r);

    RangeList* fst(void) const;
    RangeList* lst(void) const;

  public:
    static const int MAX_OF_EMPTY = Limits::Set::int_min-1;
    static const int MIN_OF_EMPTY = Limits::Set::int_max+1;



    BndSet(void);
    BndSet(Space* home, int i, int j);
    BndSet(Space* home, const IntSet& s);



    void dispose(Space* home);



    int min(void) const;
    int max(void) const;
    int minN(unsigned int n) const;
    int maxN(unsigned int n) const;
    unsigned int size(void) const;



    bool empty(void) const;
    bool in(int i) const;



    void linkTo(Space* home, const BndSet& s);
    


    RangeList* ranges(void) const;

  protected:
    template <class I> bool overwrite(Space* home,I& i);

  public:


    void update(Space* home, BndSet& x);

    GECODE_SET_EXPORT bool isConsistent(void) const;
  };

  class BndSetRanges {
  private:
    const RangeList* p;
    const RangeList* c;
  public:


    BndSetRanges(void);
    BndSetRanges(const BndSet& s);
    void init(const BndSet& s);



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



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

  class GLBndSet : public BndSet {
  private:
    GECODE_SET_EXPORT bool include_full(Space* home,int,int);
  public:


    GLBndSet(Space* =NULL);
    GLBndSet(Space* home, int i, int j);
    GLBndSet(Space* home, const IntSet& s);
    void init(Space* home);



    bool include(Space* home,int i,int j);
    template <class I> bool includeI(Space* home,I& i);
  private:
    GLBndSet(const GLBndSet&);
    const GLBndSet& operator=(const GLBndSet&);
  };

  class LUBndSet: public BndSet{
  private:
    GECODE_SET_EXPORT bool exclude_full(Space* home, int, int);
  public:


    LUBndSet(void);
    LUBndSet(Space* home);
    LUBndSet(Space* home, int i, int j);
    LUBndSet(Space* home, const IntSet& s);
    void init(Space* home);



    bool exclude(Space* home, int i, int j);
    template <class I> bool intersectI(Space* home, I& i);
    template <class I> bool excludeI(Space* home, I& i);
  private:
    LUBndSet(const LUBndSet&);
    const LUBndSet& operator=(const LUBndSet&);
  };

  /*
   * Iterators
   *
   */


  template <class I>
  class RangesCompl :
    public Iter::Ranges::Compl<Limits::Set::int_min, Limits::Set::int_max, I> {
  public:


    RangesCompl(void);
    RangesCompl(I& i);
    void init(I& i);
  };

  template <class T> class LubRanges {
  public:


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



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



    int min(void) const;
    int max(void) const;
    unsigned int width(void) const;
  };
  
  template <class T> class GlbRanges {
  public:


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



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



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

  template <class T>
  class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
  private:
    LubRanges<T> i1;
    GlbRanges<T> i2;
  public:


    UnknownRanges(void);
    UnknownRanges(const T& x);
    void init(const T& x);
  };
  
}}

#include "gecode/set/var/integerset.icc"
#include "gecode/set/var/iter.icc"

namespace Gecode { namespace Set {

  class SetVarImp : public SetVarImpBase {
    friend class LubRanges<SetVarImp*>;
    friend class GlbRanges<SetVarImp*>;
  private:
    LUBndSet lub;
    GLBndSet glb;
    unsigned int _cardMin;
    unsigned int _cardMax;

  protected:
    SetVarImp(Space* home, bool share, SetVarImp& x);
  public:


    SetVarImp(Space* home);
    SetVarImp(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
               unsigned int cardMin = 0,
               unsigned int cardMax = Limits::Set::card_max);
    SetVarImp(Space* home,const IntSet& glbD,int lubMin,int lubMax,
              unsigned int cardMin,unsigned int cardMax);
    SetVarImp(Space* home,int glbMin,int glbMax,const IntSet& lubD,
              unsigned int cardMin,unsigned int cardMax);
    SetVarImp(Space* home,const IntSet& glbD,const IntSet& lubD,
              unsigned int cardMin,unsigned int cardMax);



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



    bool assigned(void) const;
    bool knownIn(int n) const;
    bool knownOut(int) const;

  private:


    GECODE_SET_EXPORT ModEvent processLubChange(Space* home);
    GECODE_SET_EXPORT ModEvent processGlbChange(Space* home);
    ModEvent checkLubCardAssigned(Space* home,ModEvent me);
    ModEvent checkGlbCardAssigned(Space* home,ModEvent me);



    GECODE_SET_EXPORT ModEvent cardMin_full(Space* home,unsigned int n);
    GECODE_SET_EXPORT ModEvent cardMax_full(Space* home,unsigned int n);

    bool boundsConsistent(void) const;
  public:



    ModEvent include(Space* home,int n);
    ModEvent include(Space* home,int i,int j);
    ModEvent exclude(Space* home,int n);
    ModEvent exclude(Space* home,int i,int j);
    ModEvent intersect(Space* home,int n);
    ModEvent intersect(Space* home,int i,int j);
    ModEvent cardMin(Space* home,unsigned int n);
    ModEvent cardMax(Space* home,unsigned int n);



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

  public:


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

  private:
    GECODE_SET_EXPORT SetVarImp* perform_copy(Space* home, bool share);

  public:


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

  };

}}

#include "gecode/set/var/imp.icc"

namespace Gecode {

  class SetVar {
  private:
    Set::SetVarImp* x;
  public:


    GECODE_SET_EXPORT SetVar(void);

    GECODE_SET_EXPORT SetVar(Space* home);
    void init(Space* home);

    GECODE_SET_EXPORT 
    SetVar(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
           unsigned int cardMin = 0,
           unsigned int cardMax = Limits::Set::card_max);
    void init(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
              unsigned int cardMin = 0,
              unsigned int cardMax = Limits::Set::card_max);

    GECODE_SET_EXPORT 
    SetVar(Space* home,const IntSet& glbD,int lubMin,int lubMax,
           unsigned int cardMin = 0,
           unsigned int cardMax = Limits::Set::card_max);
    void init(Space* home,const IntSet& glbD,int lubMin,int lubMax,
              unsigned int cardMin = 0,
              unsigned int cardMax = Limits::Set::card_max);

    GECODE_SET_EXPORT 
    SetVar(Space* home,int glbMin,int glbMax,const IntSet& lubD,
           unsigned int cardMin = 0,
           unsigned int cardMax = Limits::Set::card_max);
    void init(Space* home,int glbMin,int glbMax,const IntSet& lubD,
              unsigned int cardMin = 0,
              unsigned int cardMax = Limits::Set::card_max);

    GECODE_SET_EXPORT 
    SetVar(Space* home,const IntSet& glbD,const IntSet& lubD,
           unsigned int cardMin = 0,
           unsigned int cardMax = Limits::Set::card_max);
    void init(Space* home,const IntSet& glbD,const IntSet& lubD,
              unsigned int cardMin = 0,
              unsigned int cardMax = Limits::Set::card_max);



    Set::SetVarImp* variable(void) const;
    


    unsigned int glbSize(void) const;
    unsigned int lubSize(void) const;
    unsigned int unknownSize(void) const;
    unsigned int cardMin(void) const;
    unsigned int cardMax(void) const;
    int lubMin(void) const;
    int lubMax(void) const;
    int glbMin(void) const;
    int glbMax(void) const;



    bool contains(int i) const;
    bool notContains(int i) const;
    bool assigned(void) const;



    void update(Space* home, bool, SetVar& x);
  };


  class SetVarGlbRanges {
  private:
    Set::GlbRanges<Set::SetVarImp*> iter;
  public:


    SetVarGlbRanges(void);
    SetVarGlbRanges(const SetVar& x);



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



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

  class SetVarLubRanges {
  private:
    Set::LubRanges<Set::SetVarImp*> iter;
  public:


    SetVarLubRanges(void);
    SetVarLubRanges(const SetVar& x);



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



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

  class SetVarUnknownRanges {
  private:
    Set::UnknownRanges<Set::SetVarImp*> iter;
  public:


    SetVarUnknownRanges(void);
    SetVarUnknownRanges(const SetVar& x);



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



    int min(void) const;
    int max(void) const;
    unsigned int width(void) const;
  };
  
  class SetVarGlbValues {
  private:
    Iter::Ranges::ToValues<SetVarGlbRanges> iter;
  public:


    SetVarGlbValues(void);
    SetVarGlbValues(const SetVar& x);



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



    int  val(void) const;
  };

  class SetVarLubValues {
  private:
    Iter::Ranges::ToValues<SetVarLubRanges> iter;
  public:


    SetVarLubValues(void);
    SetVarLubValues(const SetVar& x);



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



    int  val(void) const;
  };

  class SetVarUnknownValues {
  private:
    Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
  public:


    SetVarUnknownValues(void);
    SetVarUnknownValues(const SetVar& x);



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



    int  val(void) const;
  };

}

#include "gecode/set/var/set.icc"

GECODE_SET_EXPORT std::ostream&
operator<<(std::ostream&, const Gecode::SetVar& x);

// STATISTICS: set-var