incremental.icc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2007
 *
 *  Last modified:
 *     $Date: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
 *     $Revision: 6017 $
 *
 *  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 Extensional {
  /*
   * Support entries
   *
   */
  
  template <class View>
  forceinline
  Incremental<View>::SupportEntry::SupportEntry(void) 
    : t(NULL), next(NULL) {}

  template <class View>
  forceinline
  Incremental<View>::SupportEntry::SupportEntry(Tuple t0, SupportEntry* n0)
    : t(t0), next(n0) {}

  template <class View>
  forceinline void
  Incremental<View>::SupportEntry::operator delete(void*) {}

  template <class View>
  forceinline void
  Incremental<View>::SupportEntry::operator delete(void*, Space*) {
    GECODE_NEVER;
  }

  template <class View>
  forceinline void*
  Incremental<View>::SupportEntry::operator new(size_t, Space* home) {
    return home->fl_alloc<sizeof(SupportEntry)>();
  }

  template <class View>
  forceinline void
  Incremental<View>::SupportEntry::dispose(Space* home, SupportEntry* l) {
    home->fl_dispose<sizeof(SupportEntry)>(this,l);
  }

  template <class View>
  forceinline void
  Incremental<View>::SupportEntry::dispose(Space* home) {
    next = NULL;
    home->fl_dispose<sizeof(SupportEntry)>(this,this);
  }



  /*
   * The propagator proper
   *
   */

  template <class View>
  forceinline
  Incremental<View>::Incremental(Space* home, ViewArray<View>& x, const TupleSet& t)
    : Base<View,false>(home,x,t), support_data(NULL), 
      work(x.size()), unassigned(x.size()), ac(home) {
    init_support(home);

    ModEvent me = ME_INT_DOM;

    // Post advisors
    for (int i = x.size(); i--; ) {
      if (x[i].assigned()) {
        --unassigned;
        me = ME_INT_VAL;
      } else {
        (void) new (home) SupportAdvisor(home, this, ac, x[i], i);
      }
    }

    // Add initial supports
    GECODE_AUTOARRAY(BitSet, dom, x.size());
    init_dom(home, dom);
    for (int i = x.size(); i--; ) {
      ViewValues<View> vv(x[i]);
      while (vv()) {
        find_support(home, dom, i, vv.val());
        ++vv;
      }
    }
    if (!work.empty() || unassigned==0) {
      // Work to be done or subsumption
      View::schedule(home,this,me);
    }
  }

  template <class View>
  ExecStatus
  Incremental<View>::post(Space* home, ViewArray<View>& x, const TupleSet& t) {
    (void) new (home) Incremental<View>(home,x,t);
    return ES_OK;
  }

  template <class View>
  forceinline
  Incremental<View>::Incremental(Space* home, bool share, Incremental<View>& p)
    : Base<View,false>(home,share,p), support_data(NULL), 
      work(2), unassigned(p.unassigned) {
    ac.update(home,share,p.ac);

    init_support(home);
    int literals = ts()->domsize*x.size();    
    for (int i = literals; i--; ) {
      SupportEntry** n = &(support_data[i]);
      SupportEntry*  o = p.support_data[i];
      while (o) {
        // Allocate new support entry
        SupportEntry* s = new (home) SupportEntry(o->t);
        // Link in support entry
        (*n) = s;
        n = &(s->next);
        // move to next one
        o = o->next;
      }
    }
  }

  template <class View>
  PropCost
  Incremental<View>::cost(ModEventDelta med) const {
    return (View::me(med) == ME_INT_VAL)
      ? PC_QUADRATIC_HI : PC_CUBIC_HI;
  }

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

  template <class View>
  Gecode::Support::Symbol
  Incremental<View>::ati(void) {
    return Reflection::mangle<View>("Gecode::Int::Extensional::Incremental");
  }

  template <class View>
  Reflection::ActorSpec
  Incremental<View>::spec(const Space* home, Reflection::VarMap& m) const {
    Reflection::ActorSpec s(ati());
    return s << x.spec(home, m)
             << tupleSet.spec(m);
  }

  template <class View>
  void
  Incremental<View>::post(Space* home, Reflection::VarMap& vars,
                    const Reflection::ActorSpec& spec) {
    spec.checkArity(2);
    ViewArray<View> x(home, vars, spec[0]);
    TupleSet tupleSet(vars, spec[1]);
    (void) new (home) Incremental<View>(home,x,tupleSet);    
  }

  template <class View>
  ExecStatus
  Incremental<View>::propagate(Space* home, ModEventDelta) {
    assert(!work.empty() || unassigned==0);
    GECODE_AUTOARRAY(BitSet, dom, x.size());
    init_dom(home, dom);

    while (!work.empty()) {
      Work w = work.pop();
      if (dom[w.var].get(w.val-ts()->min)) {
        // Work is still relevant
        switch (w.work) {
        case WT_FIND_SUPPORT:
          find_support(home, dom, w.var, w.val);
          break;
        case WT_REMOVE_VALUE:
          {
            assert(support(w.var, w.val) == NULL);
            ModEvent me = x[w.var].nq(home,w.val);
            if (me_failed(me)) {
              return ES_FAILED;
            }
            dom[w.var].set(w.val-ts()->min, false);
          }
          break;
        default:
          GECODE_NEVER;
          break;
        };
      }
    }
    /*
    for (int i = 0; i < x.size(); ++i) {
      ViewValues<View> vv(x[i]);
      while(vv()) {
        assert(support(i, vv.val()) != NULL);
        ++vv;
      }
    }
    */
    if (unassigned != 0) {
      return ES_FIX;
    }

    return ES_SUBSUMED(this, home);
  }



  template <class View>
  forceinline void
  Incremental<View>::add_support(Space* home, Tuple l) {
    for (int i = x.size(); i--; ) {
      int pos = (i*ts()->domsize) + (l[i] - ts()->min);

      SupportEntry* s = new (home) SupportEntry(l, support_data[pos]);
      support_data[pos] = s;
    }
  }

  template <class View>
  forceinline void
  Incremental<View>::remove_support(Space* home, Tuple l,
                                    int var, int /*val*/) {
    for (int i = x.size(); i--; ) {
      int v = l[i];
      int ov = v - ts()->min;
      int pos = (i*(ts()->domsize)) + ov;

      assert(support_data[pos] != NULL);
      
      SupportEntry** a = &(support_data[pos]);
      while ((*a)->t != l) {
        assert((*a)->next != NULL);
        a = &((*a)->next);
      }
      SupportEntry* old = *a;
      *a = (*a)->next;
      
      old->dispose(home);
      if (i != var && support_data[pos] == NULL) {
        work.push(Work(WT_FIND_SUPPORT, i, v));
      }
    }
  }

  template <class View>
  forceinline void
  Incremental<View>::find_support(Space* home, Domain dom, int var, int val) {
    if (support(var, val) == NULL) {
      int oval = val - ts()->min;
      // Find support for value vv.val() in variable var
      Tuple l = Base<View,false>::find_support(dom, var, oval);
      if (l == NULL) {
        // No possible supports left
        work.push(Work(WT_REMOVE_VALUE, var, val));
      } else {
        // Mark values in support as supported
        add_support(home, l);
      }
    }
  }

  template <class View>
  forceinline void
  Incremental<View>::init_support(Space* home) {
    assert(support_data == NULL);
    int literals = ts()->domsize*x.size();
    support_data = static_cast<SupportEntry**>
      (home->alloc(literals*sizeof(SupportEntry*)));
    for (int i = literals; i--; ) {
      support_data[i] = NULL;
    }
  }

  template <class View>
  forceinline typename Incremental<View>::SupportEntry*
  Incremental<View>::support(int var, int val) {
    int oval = val - ts()->min;
    return support_data[(var*(ts()->domsize)) + oval];
  }


  // 
  // Advisor proper
  //
  template <class View>
  ExecStatus
  Incremental<View>::advise(Space *home, Advisor* a0, const Delta* d) {
    SupportAdvisor* a = static_cast<SupportAdvisor*>(a0);
    ModEvent me = View::modevent(d);
    bool scheduled = !work.empty();

    if (a->x.any(d)) {
      ViewValues<View> vv(a->x);
      for (int i = ts()->min; i <= ts()->max; ++i) {
        if (vv() && i == vv.val()) {
          ++vv;  
          continue;
        }
        while (SupportEntry* s = support(a->pos, i)) {
          remove_support(home, s->t, a->pos, i);
        }
      } 
    } else {
      int lo = a->x.min(d);
      int hi = a->x.max(d);
      for (int val = lo; val <= hi; ++val) {
        while (SupportEntry* s = support(a->pos, val)) {
          remove_support(home, s->t, a->pos, val);
        }
      }
    }

    
    if (me == ME_INT_VAL) {
      --unassigned;
      if ((work.empty() || scheduled) && unassigned!=0) {
        // nothing to do or already scheduled
        // propagator is not subsumed since unassigned!=0
        return ES_SUBSUMED_FIX(a,home,ac);
      }
      return ES_SUBSUMED_NOFIX(a,home,ac);
    }
    if (work.empty() || scheduled) {
      // nothing to do or already scheduled
      return ES_FIX;
    }
    return ES_NOFIX;
  }
  

  template <class View>
  size_t
  Incremental<View>::dispose(Space* home) {
    if (!home->failed()) {
      int literals = ts()->domsize*x.size();    
      for (int i = literals; i--; ) {
        if (support_data[i]) {
          SupportEntry* lastse = support_data[i];
          while (lastse->next) lastse = lastse->next;
          support_data[i]->dispose(home, lastse);
        }
      }
      home->reuse(support_data, sizeof(SupportEntry*)*literals);
    }
    work.~WorkStack();
    (void) ac.dispose(home);

    (void) Base<View,false>::dispose(home);

    return sizeof(*this);
  }

}}}

// STATISTICS: int-prop