int-dom.icc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2006
 *
 *  Last modified:
 *     $Date: 2008-07-11 09:28:48 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7285 $
 *
 *  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 Int { namespace Linear {

  class SupportSet {
  private:
    static const unsigned int bpui = sizeof(unsigned int) * 8;
    unsigned int* bits;
  public:
    void init(unsigned int n);
    void support(unsigned int i);
    bool supported(unsigned int i) const;

  private:
    class ResultIter : public ViewValues<IntView> {
    protected:
      const SupportSet* s;
      unsigned int p;
    public:
      ResultIter(const SupportSet* s0, const IntView& x);
      void operator++(void);
    };

  public:
    ModEvent tell(Space* home, IntView& x) const;
    void dispose(void);
  };

  template <class Val>
  class SupportIter {
  protected:
    int           a;
    IntView       x;
    SupportSet    s;
    int           c;
    unsigned int  p;
    Val           l;
    Val           u;
  public:
    void init(int a, const IntView& x, Val l, Val u);
    void support(void);
    ModEvent tell(Space* home);
    void dispose(void);
  };


  template <class Val>
  class PosSupportIter : public SupportIter<Val> {
  private:
    IntVarImpFwd i;
    // Using-declarations for dependant names
    using SupportIter<Val>::a;
    using SupportIter<Val>::x;
    using SupportIter<Val>::s;
    using SupportIter<Val>::c;
    using SupportIter<Val>::p;
    using SupportIter<Val>::l;
    using SupportIter<Val>::u;
  public:
    bool reset(Val& d);
    bool adjust(Val& d);
  };


  template <class Val>
  class NegSupportIter : public SupportIter<Val> {
  private:
    IntVarImpBwd i;
    // Using-declarations for dependant names
    using SupportIter<Val>::a;
    using SupportIter<Val>::x;
    using SupportIter<Val>::s;
    using SupportIter<Val>::c;
    using SupportIter<Val>::p;
    using SupportIter<Val>::l;
    using SupportIter<Val>::u;
  public:
    bool reset(Val& d);
    bool adjust(Val& d);
  };


  /*
   * Support set
   *
   */
  forceinline void
  SupportSet::init(unsigned int n) {
    bits = Memory::bmalloc<unsigned int>((n / bpui) + 1);
    for (unsigned int i = (n / bpui) + 1; i--; )
      bits[i] = 0;
  }
  forceinline void
  SupportSet::support(unsigned int i) {
    unsigned int p = i / bpui;
    bits[p] |= 1 << (i-p*bpui);
  }
  forceinline bool
  SupportSet::supported(unsigned int i) const {
    unsigned int p = i / bpui;
    return (bits[p] & (1 << (i-p*bpui))) != 0;
  }

  forceinline
  SupportSet::ResultIter::ResultIter(const SupportSet* s0, const IntView& x)
    : ViewValues<IntView>(x), s(s0), p(0) {
    while (ViewValues<IntView>::operator()() && s->supported(p)) {
      ViewValues<IntView>::operator++(); ++p;
    }
  }
  forceinline void
  SupportSet::ResultIter::operator++(void) {
    do {
      ViewValues<IntView>::operator++(); ++p;
    } while (ViewValues<IntView>::operator()() && s->supported(p));
  }


  inline ModEvent
  SupportSet::tell(Space* home, IntView& x) const {
    unsigned int n = x.size() / bpui;
    // Check whether all bits are zero: failure
    for (unsigned int i=n+1; i--; )
      if (bits[i] != 0)
        goto all;
    return ME_INT_FAILED;
  all:
    // Check whether all bits are one: nothing changed
    for (unsigned int i=n; i--; )
      if (bits[i] != ~0U)
        goto tell;
    // Now check the bits in the last word
    for (unsigned int i=n*bpui; i<x.size(); i++)
      if (!supported(i))
        goto tell;
    return ME_INT_NONE;
  tell:
    {
      ResultIter i(this,x);
      return x.minus_v(home,i);
    }
  }

  forceinline void
  SupportSet::dispose(void) {
    Memory::free(bits);
  }


  /*
   * Base-class for support-based iterator
   *
   */
  template <class Val>
  forceinline void
  SupportIter<Val>::init(int a0, const IntView& x0, Val l0, Val u0) {
    a=a0; x=x0; l=l0; u=u0;
    s.init(x.size());
  }
  template <class Val>
  forceinline void
  SupportIter<Val>::support(void) {
    s.support(p);
  }
  template <class Val>
  forceinline ModEvent
  SupportIter<Val>::tell(Space* home) {
    return s.tell(home,x);
  }
  template <class Val>
  forceinline void
  SupportIter<Val>::dispose(void) {
    s.dispose();
  }


  /*
   * Support-based iterator for positive view
   *
   */
  template <class Val>
  forceinline bool
  PosSupportIter<Val>::reset(Val& d) {
    // Way too small, no value can make it big enough
    if (d + static_cast<Val>(a)*x.max() < u)
      return false;
    // Restart iterator and position of values
    i.init(x.var()); p = 0;
    // Skip all ranges which are too small
    while (d + static_cast<Val>(a)*i.max() < u) {
      p += i.width(); ++i;
    }
    // There is at least one range left (check of max)
    assert(i());
    // Initialize current range and adjust value
    c = i.min();
    // Skip all values which are too small
    while (d + static_cast<Val>(a)*c < u) {
      p++; c++;
    }
    // Adjust to new value
    d += static_cast<Val>(a) * c;
    return true;
  }
  template <class Val>
  forceinline bool
  PosSupportIter<Val>::adjust(Val& d) {
    // Current value
    Val v = static_cast<Val>(a) * c;
    // Subtract current value from d
    d -= v;
    // Move to next position (number of value)
    p++;
    // Still in the same range
    if (c < i.max()) {
      // Decrement current values
      c += 1; v += a;
    } else {
      // Go to next range
      ++i;
      if (!i())
        return false;
      c = i.min(); v = static_cast<Val>(a) * c;
    }
    // Is d with the current value too large?
    if (d + v > l)
      return false;
    // Update d
    d += v;
    return true;
  }


  /*
   * Support-based iterator for negative view
   *
   */
  template <class Val>
  forceinline bool
  NegSupportIter<Val>::reset(Val& d) {
    // Way too small, no value can make it big enough
    if (d + static_cast<Val>(a)*x.min() < u)
      return false;
    // Restart iterator and position of values
    i.init(x.var()); p = x.size()-1;
    // Skip all ranges which are too small
    while (d + static_cast<Val>(a)*i.min() < u) {
      p -= i.width(); ++i;
    }
    // There is at least one range left (check of max)
    assert(i());
    // Initialize current range
    c = i.max();
    // Skip all values which are too small
    while (d + static_cast<Val>(a)*c < u) {
      p--; c--;
    }
    // Adjust to new value
    d += static_cast<Val>(a) * c;
    return true;
  }
  template <class Val>
  forceinline bool
  NegSupportIter<Val>::adjust(Val& d) {
    // Current value
    Val v = static_cast<Val>(a) * c;
    // Subtract current value from d
    d -= v;
    // Move to next position (number of value)
    p--;
    // Still in the same range
    if (c > i.min()) {
      // Decrement current values
      c -= 1; v -= a;
    } else {
      // Go to next range
      ++i;
      if (!i())
        return false;
      c = i.max(); v = static_cast<Val>(a) * c;
    }
    // Is d with the current value too large?
    if (d + v > l)
      return false;
    // Update d
    d += v;
    return true;
  }



  /*
   * The domain consisten equality propagator
   *
   */
  template <class Val, class View>
  forceinline
  DomEq<Val,View>::DomEq(Space* home,
                         ViewArray<View >& x, ViewArray<View >& y,
                         Val c)
    : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}

  template <class Val, class View>
  ExecStatus
  DomEq<Val,View>::post(Space* home,
                        ViewArray<View>& x, ViewArray<View>& y,
                        Val c) {
    (void) new (home) DomEq<Val,View>(home,x,y,c);
    return ES_OK;
  }

  template <class Val, class View>
  forceinline
  DomEq<Val,View>::DomEq(Space* home, bool share, DomEq<Val,View>& p)
    : Lin<Val,View,View,PC_INT_DOM>(home,share,p) {}

  template <class Val, class View>
  Actor*
  DomEq<Val,View>::copy(Space* home, bool share) {
    return new (home) DomEq<Val,View>(home,share,*this);
  }

  template <class Val, class View>
  PropCost
  DomEq<Val,View>::cost(ModEventDelta med) const {
    return (View::me(med) != ME_INT_DOM)
      ? cost_hi(x.size()+y.size(),PC_LINEAR_LO)
      : cost_hi(x.size()+y.size(),PC_CRAZY_HI);
  }

  template <class Val, class View>
  inline Support::Symbol
  DomEq<Val,View>::ati(void) {
    return Reflection::mangle<Val,View>("Gecode::Int::Linear::DomEq");
  }

  template <class Val, class View>
  Reflection::ActorSpec
  DomEq<Val,View>::spec(const Space* home, Reflection::VarMap& m) const {
    return Lin<Val,View,View,PC_INT_DOM>::spec(home, m, ati());
  }
  
  template <class Val, class View>
  void
  DomEq<Val,View>::post(Space* home, Reflection::VarMap& vars,
                        const Reflection::ActorSpec& spec) {
    spec.checkArity(3);
    ViewArray<View> x(home, vars, spec[0]);
    ViewArray<View> y(home, vars, spec[1]);
    Val c = spec[2]->toInt();
    (void) new (home) DomEq<Val,View>(home, x, y, c);
  }  

  template <class Val, class View>
  ExecStatus
  DomEq<Val,View>::propagate(Space* home, ModEventDelta med) {
    if (View::me(med) != ME_INT_DOM) {
      ExecStatus es = prop_bnd<Val,View,View>(home,med,this,x,y,c);
      GECODE_ES_CHECK(es);
      return ES_FIX_PARTIAL(this,View::med(ME_INT_DOM));
    }

    // Value of equation for partial assignment
    Val d = -c;

    int n = x.size();
    int m = y.size();

    // Create support-base iterators
    GECODE_AUTOARRAY(PosSupportIter<Val>, xp, n);
    GECODE_AUTOARRAY(NegSupportIter<Val>, yp, m);

    // Initialize views for assignments
    {
      Val l = 0;
      Val u = 0;
      for (int j=m; j--; ) {
        yp[j].init(-y[j].scale(),y[j].base(),l,u);
        l += y[j].max(); u += y[j].min();
      }
      for (int i=n; i--; ) {
        xp[i].init(x[i].scale(),x[i].base(),l,u);
        l -= x[i].min(); u -= x[i].max();
      }
    }

    // Collect support information by iterating assignments
    {
      // Force reset of all iterators in first round
      int i = 0;
      int j = 0;

    next_i:
      // Reset all iterators for positive views and update d
      while (i<n) {
        if (!xp[i].reset(d)) goto prev_i;
        i++;
      }
    next_j:
      // Reset all iterators for negative views and update d
      while (j<m) {
        if (!yp[j].reset(d)) goto prev_j;
        j++;
      }
      // Check whether current assignment is solution
      if (d == 0) {
        // Record support
        for (int is=n; is--; ) xp[is].support();
        for (int js=m; js--; ) yp[js].support();
      }
    prev_j:
      // Try iterating to next assignment: negative views
      while (j>0) {
        if (yp[j-1].adjust(d)) goto next_j;
        j--;
      }
    prev_i:
      // Try iterating to next assignment: positive views
      while (i>0) {
        if (xp[i-1].adjust(d)) goto next_i;
        i--;
      }
    }

    // Tell back new variable domains
    ExecStatus es = ES_NOFIX;
    for (int i=n; i--; ) {
      ModEvent me = xp[i].tell(home);
      if (me_failed(me)) {
        es = ES_FAILED; goto dispose;
      }
      if (!x[i].assigned())
        es = ES_FIX;
    }
    for (int j=m; j--; ) {
      ModEvent me = yp[j].tell(home);
      if (me_failed(me)) {
        es = ES_FAILED; goto dispose;
      }
      if (!y[j].assigned())
        es = ES_FIX;
    }

    // Release memory
  dispose:
    for (int i=n; i--; ) xp[i].dispose();
    for (int j=m; j--; ) yp[j].dispose();

    if (es == ES_NOFIX)
      return ES_SUBSUMED(this,sizeof(*this));
    return es;
  }

}}}

// STATISTICS: int-prop