complement.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>
 *
 *  Contributing authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2008-07-11 10:24:32 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7328 $
 *
 *  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 {

  template <class View>
  forceinline
  ComplementView<View>::ComplementView(void) {}

  template <class View>
  forceinline
  ComplementView<View>::ComplementView(View& s0)
    : DerivedViewBase<View>(s0) {}

  template <class View>
  forceinline
  ComplementView<View>::ComplementView(Space* home,
                                       const Reflection::VarMap& vars,
                                       Reflection::Arg* arg)
  : DerivedViewBase<View>(View(home, vars, arg)) {}

  template <class View>
  forceinline ModEvent
  ComplementView<View>::me_negateset(ModEvent me) {
    switch(me) {
    case ME_SET_LUB : return ME_SET_GLB;
    case ME_SET_GLB : return ME_SET_LUB;
    case ME_SET_CLUB : return ME_SET_CGLB;
    case ME_SET_CGLB : return ME_SET_CLUB;
    default: return me;
    }
  }

  template <class View>
  forceinline PropCond
  ComplementView<View>::pc_negateset(PropCond pc) {
    switch(pc) {
    case PC_SET_CLUB  : return PC_SET_CGLB;
    case PC_SET_CGLB  : return PC_SET_CLUB;
    default: return pc;
    }
  }

  template <class View>
  forceinline bool
  ComplementView<View>::assigned(void) const { return view.assigned(); }

  template <class View>
  forceinline unsigned int
  ComplementView<View>::glbSize(void) const {
    return Limits::card - view.lubSize();
  }

  template <class View>
  forceinline unsigned int
  ComplementView<View>::lubSize(void) const {
    return Limits::card - view.glbSize();
  }

  template <class View>
  forceinline unsigned int
  ComplementView<View>::unknownSize(void) const {
    return lubSize() - glbSize();
  }

  template <class View>
  forceinline bool
  ComplementView<View>::contains(int n) const { return view.notContains(n); }

  template <class View>
  forceinline bool
  ComplementView<View>::notContains(int n) const { return view.contains(n); }

  template <class View>
  forceinline unsigned int
  ComplementView<View>::cardMin() const {
    return Limits::card - view.cardMax();
  }

  template <class View>
  forceinline unsigned int
  ComplementView<View>::cardMax() const {
    return Limits::card - view.cardMin();
  }

  template <class View>
  forceinline int
  ComplementView<View>::lubMin() const {
    GlbRanges<View> lb(view);
    RangesCompl<GlbRanges<View> > lbc(lb);
    if (lbc()) {
      return lbc.min();
    } else {
      return BndSet::MIN_OF_EMPTY;
    }
  }

  template <class View>
  forceinline int
  ComplementView<View>::lubMax() const {
    GlbRanges<View> lb(view);
    RangesCompl<GlbRanges<View> > lbc(lb);
    if (lbc()) {
      while(lbc()) ++lbc;
      return lbc.max();
    } else {
      return BndSet::MAX_OF_EMPTY;
    }
  }

  template <class View>
  forceinline int
  ComplementView<View>::glbMin() const {
    LubRanges<View> ub(view);
    RangesCompl<LubRanges<View> > ubc(ub);
    if (ubc()) {
      return ubc.min();
    } else {
      return BndSet::MIN_OF_EMPTY;
    }
  }

  template <class View>
  forceinline int
  ComplementView<View>::glbMax() const {
    LubRanges<View> ub(view);
    RangesCompl<LubRanges<View> > ubc(ub);
    if (ubc()) {
      while(ubc()) ++ubc;
      return ubc.max();
    } else {
      return BndSet::MAX_OF_EMPTY;
    }
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::cardMin(Space* home, unsigned int c) {
    if (c < Limits::card)
      return me_negateset(view.cardMax(home, Limits::card - c));
    return ME_SET_NONE;
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::cardMax(Space* home, unsigned int c) {
    if (c < Limits::card)
      return me_negateset(view.cardMin(home, Limits::card - c));
    return ME_SET_NONE;
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::include(Space* home, int c) {
    return me_negateset((view.exclude(home, c)));
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::exclude(Space* home, int c) {
    return me_negateset((view.include(home, c)));
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::intersect(Space* home, int c) {
    Iter::Ranges::Singleton si(c,c);
    RangesCompl<Iter::Ranges::Singleton> csi(si);
    return me_negateset((view.includeI(home, csi)));
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::intersect(Space* home, int i, int j) {
    Iter::Ranges::Singleton si(i,j);
    RangesCompl<Iter::Ranges::Singleton> csi(si);
    return me_negateset((view.includeI(home, csi)));
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::include(Space* home, int j, int k) {
    return me_negateset(view.exclude(home,j,k));
  }

  template <class View>
  forceinline ModEvent
  ComplementView<View>::exclude(Space* home, int j, int k) {
    return me_negateset(view.include(home,j,k));
  }

  template <class View>
  template <class I> ModEvent
  ComplementView<View>::excludeI(Space* home,I& iter) {
    return me_negateset(view.includeI(home,iter));
  }

  template <class View>
  template <class I> ModEvent
  ComplementView<View>::includeI(Space* home,I& iter) {
    return me_negateset(view.excludeI(home,iter));
  }

  template <class View>
  template <class I> ModEvent
  ComplementView<View>::intersectI(Space* home,I& iter) {
    RangesCompl<I> c(iter);
    return me_negateset(view.includeI(home,c));
  }

  template <class View>
  forceinline void
  ComplementView<View>::subscribe(Space* home, Propagator* p, PropCond pc,
                                  bool process) {
    view.subscribe(home,p, pc_negateset(pc),process);
  }

  template <class View>
  forceinline void
  ComplementView<View>::cancel(Space* home, Propagator* p, PropCond pc) {
    view.cancel(home,p, pc_negateset(pc));
  }

  template <class View>
  forceinline void
  ComplementView<View>::subscribe(Space* home, Advisor* a) {
    view.subscribe(home,a);
  }

  template <class View>
  forceinline void
  ComplementView<View>::cancel(Space* home, Advisor* a) {
    view.cancel(home,a);
  }

  template <class View>
  forceinline void
  ComplementView<View>::schedule(Space* home, Propagator* p, ModEvent me) {
    return View::schedule(home,p,me_negateset(me));
  }
  template <class View>
  forceinline ModEvent
  ComplementView<View>::me(ModEventDelta med) {
    return me_negateset(View::me(med));
  }

  template <class View>
  forceinline ModEventDelta
  ComplementView<View>::med(ModEvent me) {
    return me_negateset(View::med(me));
  }

  template <class View>
  forceinline void
  ComplementView<View>::update(Space* home, bool share, 
                               ComplementView& y) {
    view.update(home,share,y.view);
  }

  template <class View>
  forceinline Reflection::Arg*
  ComplementView<View>::spec(const Space* home, Reflection::VarMap& m) const {
    return view.spec(home, m);
  }

  template <class View>
  inline Support::Symbol
  ComplementView<View>::type(void) {
    Support::Symbol t("Set::ComplementView<");
    t += View::type();
    t += ">";
    return t;
  }

  /*
   * Delta information for advisors
   *
   */

  template <class View>
  forceinline ModEvent
  ComplementView<View>::modevent(const Delta* d) {
    return me_negateset(View::modevent(d));
  }
  
  template <class View>
  forceinline int
  ComplementView<View>::glbMin(const Delta* d) const {
    return view.lubMin(d);
  }

  template <class View>
  forceinline int
  ComplementView<View>::glbMax(const Delta* d) const {
    return view.lubMax(d);
  }

  template <class View>
  forceinline bool
  ComplementView<View>::glbAny(const Delta* d) const {
    return view.lubAny(d);
  }

  template <class View>
  forceinline int
  ComplementView<View>::lubMin(const Delta* d) const {
    return view.glbMin(d);
  }

  template <class View>
  forceinline int
  ComplementView<View>::lubMax(const Delta* d) const {
    return view.glbMax(d);
  }

  template <class View>
  forceinline bool
  ComplementView<View>::lubAny(const Delta* d) const {
    return view.glbAny(d);
  }


  template <class View>
  class LubRanges<ComplementView<View> > {
  private:
    GlbRanges<View> lb;
    RangesCompl<GlbRanges<View> > lbc;
  public:


    LubRanges(void) {}
    LubRanges(const ComplementView<View>& x);
    void init(const ComplementView<View>& x);



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



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

  template <class View>
  forceinline
  LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
    : lb(s.base()), lbc(lb) {}

  template <class View>
  forceinline void
  LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
    lb.init(s.base());
    lbc.init(lb);
  }

  template <class View>
  forceinline bool
  LubRanges<ComplementView<View> >::operator()(void) const { return lbc(); }

  template <class View>
  forceinline void
  LubRanges<ComplementView<View> >::operator++(void) { return ++lbc; }

  template <class View>
  forceinline int
  LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }

  template <class View>
  forceinline int
  LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }

  template <class View>
  forceinline unsigned int
  LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }

  template <class View>
  class LubRanges<ComplementView<ComplementView<View> > > :
  public LubRanges<View> {
  public:


    LubRanges(void) {}
    LubRanges(const ComplementView<ComplementView<View> >& x);
    void init(const ComplementView<ComplementView<View> >& x);
  };

  template <class View>
  forceinline
  LubRanges<ComplementView<ComplementView<View> > >::
  LubRanges(const ComplementView<ComplementView<View> >& x) :
  LubRanges<View>(x) {}

  template <class View>
  forceinline void
  LubRanges<ComplementView<ComplementView<View> > >::
  init(const ComplementView<ComplementView<View> >& x) {
    LubRanges<View>::init(x);
  }

  template <class View>
  class GlbRanges<ComplementView<View> > {
  private:
    LubRanges<View> ub;
    RangesCompl<LubRanges<View> > ubc;
  public:


    GlbRanges(void) {}
    GlbRanges(const ComplementView<View> & x);
    void init(const ComplementView<View> & x);



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



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

  template <class View>
  forceinline
  GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
    : ub(s.base()), ubc(ub) {}

  template <class View>
  forceinline void
  GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
    ub.init(s.base());
    ubc.init(ub);
  }

  template <class View>
  forceinline bool
  GlbRanges<ComplementView<View> >::operator()(void) const { return ubc(); }

  template <class View>
  forceinline void
  GlbRanges<ComplementView<View> >::operator++(void) { return ++ubc; }

  template <class View>
  forceinline int
  GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }

  template <class View>
  forceinline int
  GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }

  template <class View>
  forceinline unsigned int
  GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
  
  template <class View>
  class GlbRanges<ComplementView<ComplementView<View> > > :
  public GlbRanges<View> {
  public:


    GlbRanges(void) {}
    GlbRanges(const ComplementView<ComplementView<View> >& x);
    void init(const ComplementView<ComplementView<View> >& x);
  };

  template <class View>
  forceinline
  GlbRanges<ComplementView<ComplementView<View> > >::
  GlbRanges(const ComplementView<ComplementView<View> >& x) :
  GlbRanges<View>(x) {}

  template <class View>
  forceinline void
  GlbRanges<ComplementView<ComplementView<View> > >::
  init(const ComplementView<ComplementView<View> >& x) {
    GlbRanges<View>::init(x);
  }

}


  /*
   * Testing
   *
   */
  template <class View>
  forceinline bool
  same(const Set::ComplementView<View>& x, 
       const Set::ComplementView<View>& y) {
    return same(x.base(),y.base());
  }
  template <class View>
  forceinline bool
  before(const Set::ComplementView<View>& x, 
         const Set::ComplementView<View>& y) {
    return before(x.base(),y.base());
  }
  template <class View>
  forceinline bool
  same(const Set::ComplementView<Set::ComplementView<View> >& x, 
       const Set::ComplementView<Set::ComplementView<View> >& y) {
    return same(x,y);
  }
  template <class View>
  forceinline bool
  before(const Set::ComplementView<Set::ComplementView<View> >& x, 
         const Set::ComplementView<Set::ComplementView<View> >& y) {
    return before(x,y);
  }

}

template <class View>
forceinline
std::ostream&
operator<<(std::ostream& os, const Gecode::Set::ComplementView<View>& s) {
  return os << "(" << s.base() << ")^C";
}

// STATISTICS: set-var