set.icc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *     Gabor Szokoli <szokoli@gecode.org>
 *
 *  Contributing authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *     Gabor Szokoli, 2004
 *
 *  Last modified:
 *     $Date: 2008-02-06 18:48:22 +0100 (Wed, 06 Feb 2008) $ by $Author: schulte $
 *     $Revision: 6102 $
 *
 *  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.
 *
 */

namespace Gecode { namespace Set {

  /*
   * Creation of new variable implementations
   *
   */

  forceinline
  SetVarImp::SetVarImp(Space* home)
    : SetVarImpBase(home), lub(home), glb(home) {
    _cardMin = 0;
    _cardMax = Limits::card;
    assert(_cardMax==lub.size());
  }

  forceinline
  SetVarImp::SetVarImp(Space* home,int lbMin,int lbMax,int ubMin,int ubMax,
                       unsigned int cardMin, unsigned int cardMax)
    : SetVarImpBase(home),
      lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
    _cardMin = std::max(cardMin, glb.size() );
    _cardMax = std::min(cardMax, lub.size() );
  }

  forceinline
  SetVarImp::SetVarImp(Space* home,
                       const IntSet& theGlb,int ubMin,int ubMax,
                       unsigned int cardMin, unsigned int cardMax)
    : SetVarImpBase(home),
      lub(home,ubMin,ubMax), glb(home,theGlb) {
    _cardMin = std::max(cardMin, glb.size() );
    _cardMax = std::min(cardMax, lub.size() );
  }

  forceinline
  SetVarImp::SetVarImp(Space* home,
                       int lbMin,int lbMax,const IntSet& theLub,
                       unsigned int cardMin, unsigned int cardMax)
    : SetVarImpBase(home),
      lub(home,theLub), glb(home,lbMin,lbMax) {
    _cardMin = std::max(cardMin, glb.size() );
    _cardMax = std::min(cardMax, lub.size() );
  }
  
  forceinline
  SetVarImp::SetVarImp(Space* home,
                       const IntSet& theGlb,const IntSet& theLub,
                       unsigned int cardMin, unsigned int cardMax)
    : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
    _cardMin = std::max(cardMin, glb.size() );
    _cardMax = std::min(cardMax, lub.size() );
  }


  forceinline  bool
  SetVarImp::assigned(void) const {
    return ( glb.size() == lub.size() );
  }

  forceinline unsigned int
  SetVarImp::cardMin(void) const { return _cardMin; }

  forceinline unsigned int
  SetVarImp::cardMax(void) const { return _cardMax; }

  forceinline bool
  SetVarImp::knownIn(int i) const { return (glb.in(i)); }

  forceinline bool
  SetVarImp::knownOut(int i) const { return !(lub.in(i)); }

  forceinline int
  SetVarImp::lubMin(void) const { return lub.min(); }

  forceinline int
  SetVarImp::lubMax(void) const { return lub.max(); }

  forceinline int
  SetVarImp::lubMinN(int n) const { return lub.minN(n); }

  forceinline int
  SetVarImp::glbMin(void) const { return glb.min(); }

  forceinline int
  SetVarImp::glbMax(void) const { return glb.max(); }

  forceinline unsigned int
  SetVarImp::glbSize() const { return glb.size(); }

  forceinline unsigned int
  SetVarImp::lubSize() const { return lub.size(); }

  /*
   * Support for delta information
   *
   */
  forceinline ModEvent
  SetVarImp::modevent(const Delta* d) {
    return d->modevent();
  }
  forceinline int 
  SetVarImp::glbMin(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->glbMin();
  }
  forceinline int 
  SetVarImp::glbMax(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->glbMax();
  }
  forceinline bool 
  SetVarImp::glbAny(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->glbAny(); 
  }
  forceinline int 
  SetVarImp::lubMin(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->lubMin();
  }
  forceinline int 
  SetVarImp::lubMax(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->lubMax();
  }
  forceinline bool 
  SetVarImp::lubAny(const Delta* d) const {
    return static_cast<const SetDelta*>(d)->lubAny(); 
  }

  forceinline ModEvent
  SetVarImp::cardMin(Space* home,unsigned int newMin) {
    if (_cardMin >= newMin)
      return ME_SET_NONE;
    if (newMin > _cardMax)
      return ME_SET_FAILED;
    _cardMin=newMin;
    return cardMin_full(home);
  }

  forceinline ModEvent
  SetVarImp::cardMax(Space* home,unsigned int newMax) {
    if (_cardMax <= newMax)
      return ME_SET_NONE;
    if (_cardMin > newMax)
      return ME_SET_FAILED;
    _cardMax=newMax;
    return cardMax_full(home);
  }

  forceinline ModEvent
  SetVarImp::intersect(Space* home,int i, int j) {
    BndSetRanges lb(glb);
    Iter::Ranges::Singleton s(i,j);
    Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
    if (probe())
      return ME_SET_FAILED;
    if (assigned())
      return ME_SET_NONE;
    int oldMin = lub.min();
    int oldMax = lub.max();
    if (lub.intersect(home, i, j)) {
      SetDelta d;
      if (i == oldMin) {
        d._lubMin = lub.max()+1;
        d._lubMax = oldMax;
      } else if (j == oldMax) {
        d._lubMin = oldMin;
        d._lubMax = lub.min()-1;        
      }
      return processLubChange(home, d);
    }
    return ME_SET_NONE;
  }

  forceinline ModEvent
  SetVarImp::intersect(Space* home,int i) {
    return intersect(home, i, i);
  }

  template <class I>
  inline ModEvent
  SetVarImp::intersectI(Space* home, I& iterator) {
    if (assigned()) {
      BndSetRanges lbi(glb);
      Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
      if (probe())
        return ME_SET_FAILED;
      return ME_SET_NONE;      
    }
    if (!iterator()) {
      if (_cardMin > 0)
        return ME_SET_FAILED;
      _cardMax = 0;
      SetDelta d(1, 0, lub.min(), lub.max());
      lub.excludeAll(home);
      return notify(home, ME_SET_VAL, &d);
    }
    int mi=iterator.min();
    int ma=iterator.max();
    ++iterator;
    if (iterator())
      return intersectI_full(home, mi, ma, iterator);
    else
      return intersect(home, mi, ma);    
  }

  template <class I>
  ModEvent
  SetVarImp::intersectI_full(Space* home, int mi, int ma, I& iterator) {
    Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
    if (lub.intersectI(home, si)) {
      BndSetRanges ub(lub);
      BndSetRanges lb(glb);
      if (!Iter::Ranges::subset(lb,ub)) {
        glb.become(home, lub);
        _cardMin = glb.size();
        _cardMax = glb.size();
        return ME_SET_FAILED;
      }
      ModEvent me = ME_SET_LUB;
      if (_cardMax > lub.size()) {
        _cardMax = lub.size();
        if (_cardMin > _cardMax) {
          glb.become(home, lub);
          _cardMin = glb.size();
          _cardMax = glb.size();
          return ME_SET_FAILED;
        }
        me = ME_SET_CLUB;
      }
      if (_cardMax == lub.size() && _cardMin == _cardMax) {
        glb.become(home, lub);
        me = ME_SET_VAL;
      }
      SetDelta d;
      return notify(home, me, &d);
    }
    return ME_SET_NONE;
  }

  forceinline ModEvent
  SetVarImp::include(Space* home, int i, int j) {
    BndSetRanges ub(lub);
    Iter::Ranges::Singleton sij(i,j);
    if (!Iter::Ranges::subset(sij,ub)) {
      return ME_SET_FAILED;
    }
    SetDelta d;
    if (glb.include(home, i, j, d))
      return processGlbChange(home, d);      
    return ME_SET_NONE;
  }

  forceinline ModEvent
  SetVarImp::include(Space* home, int i) {
    return include(home, i, i);
  }

  template <class I> forceinline ModEvent
  SetVarImp::includeI(Space* home, I& iterator) {
    if (!iterator()) {
      return ME_SET_NONE;
    }
    if (assigned()) {
      BndSetRanges lbi(glb);
      Iter::Ranges::Diff<I,BndSetRanges>
        probe(iterator,lbi);
      return probe() ? ME_SET_FAILED : ME_SET_NONE;
    }
    int mi=iterator.min();
    int ma=iterator.max();
    ++iterator;
    if (iterator())
      return includeI_full(home, mi, ma, iterator);
    else
      return include(home, mi, ma);
  }

  template <class I>
  ModEvent
  SetVarImp::includeI_full(Space* home, int mi, int ma, I& iterator) {
    Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
    if (glb.includeI(home, si)) {
      BndSetRanges ub(lub);
      BndSetRanges lb(glb);
      if (!Iter::Ranges::subset(lb,ub)) {
        glb.become(home, lub);
        _cardMin = glb.size();
        _cardMax = glb.size();
        return ME_SET_FAILED;
      }
      ModEvent me = ME_SET_GLB;
      if (_cardMin < glb.size()) {
        _cardMin = glb.size();
        if (_cardMin > _cardMax) {
          glb.become(home, lub);
          _cardMin = glb.size();
          _cardMax = glb.size();
          return ME_SET_FAILED;
        }
        me = ME_SET_CGLB;
      }
      if (_cardMin == glb.size() && _cardMin == _cardMax) {
        lub.become(home, glb);
        me = ME_SET_VAL;
      }
      SetDelta d;
      return notify(home, me, &d);
    }
    return ME_SET_NONE;
  }

  forceinline ModEvent
  SetVarImp::exclude(Space* home, int i, int j) {
    Iter::Ranges::Singleton sij(i,j);
    BndSetRanges lb(glb);
    Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
    if (probe())
      return ME_SET_FAILED;
    SetDelta d;
    if (lub.exclude(home, i, j, d))
      return processLubChange(home, d);      
    return ME_SET_NONE;
  }

  forceinline ModEvent
  SetVarImp::exclude(Space* home, int i) {
    return exclude(home, i, i);
  }

  template <class I>
  inline ModEvent
  SetVarImp::excludeI(Space* home, I& iterator) {
    if (!iterator())
      return ME_SET_NONE;
    if (assigned()) {
      BndSetRanges ubi(lub);
      Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
      return probe() ? ME_SET_FAILED : ME_SET_NONE;
    }
    int mi=iterator.min();
    int ma=iterator.max();
    ++iterator;
    if (iterator())
      return excludeI_full(home, mi, ma, iterator);
    else
      return exclude(home, mi, ma);
  }

  template <class I>
  ModEvent
  SetVarImp::excludeI_full(Space* home, int mi, int ma, I& iterator) {
    Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
    if (lub.excludeI(home, si)) {
      BndSetRanges ub(lub);
      BndSetRanges lb(glb);
      if (!Iter::Ranges::subset(lb,ub)) {
        glb.become(home, lub);
        _cardMin = glb.size();
        _cardMax = glb.size();
        return ME_SET_FAILED;
      }
      ModEvent me = ME_SET_LUB;
      if (_cardMax > lub.size()) {
        _cardMax = lub.size();
        if (_cardMin > _cardMax) {
          glb.become(home, lub);
          _cardMin = glb.size();
          _cardMax = glb.size();
          return ME_SET_FAILED;
        }
        me = ME_SET_CLUB;
      }
      if (_cardMax == lub.size() && _cardMin == _cardMax) {
        glb.become(home, lub);
        me = ME_SET_VAL;
      }
      SetDelta d;
      return notify(home, me, &d);
    }
    return ME_SET_NONE;
  }

  /*
   * Copying a variable
   *
   */

  forceinline SetVarImp*
  SetVarImp::copy(Space* home, bool share) {
    return copied() ?
      static_cast<SetVarImp*>(forward()) :
      perform_copy(home,share);
  }

  /*
   * Iterator specializations
   *
   */

  template <>
  class LubRanges<SetVarImp*> : public BndSetRanges {
  public:


    LubRanges(void);
    LubRanges(const SetVarImp*);
    void init(const SetVarImp*);
  };

  forceinline
  LubRanges<SetVarImp*>::LubRanges(void) {}

  forceinline
  LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
    : BndSetRanges(x->lub) {}

  forceinline void
  LubRanges<SetVarImp*>::init(const SetVarImp* x) {
    BndSetRanges::init(x->lub);
  }

  template <>
  class GlbRanges<SetVarImp*> : public BndSetRanges {
  public:


    GlbRanges(void);
    GlbRanges(const SetVarImp* x);
    void init(const SetVarImp*);
  };

  forceinline
  GlbRanges<SetVarImp*>::GlbRanges(void) {}

  forceinline
  GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
    : BndSetRanges(x->glb) {}

  forceinline void
  GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
    BndSetRanges::init(x->glb);
  }


  /*
   * Dependencies
   *
   */
  forceinline void
  SetVarImp::subscribe(Space* home, Propagator* p, PropCond pc, bool process) {
    SetVarImpBase::subscribe(home,p,pc,assigned(),process);
  }
  forceinline void
  SetVarImp::cancel(Space* home, Propagator* p, PropCond pc) {
    SetVarImpBase::cancel(home,p,pc,assigned());
  }
  forceinline void
  SetVarImp::subscribe(Space* home, Advisor* a) {
    SetVarImpBase::subscribe(home,a,assigned());
  }
  forceinline void
  SetVarImp::cancel(Space* home, Advisor* a) {
    SetVarImpBase::cancel(home,a,assigned());
  }

}}

// STATISTICS: set-var