main page namespaces classes files
CPSP home

src/cpsp/gecode/GC_Nq_Subsume.hh

Go to the documentation of this file.

/*
 *  Main authors:
 *     Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
 *
 *  Contributing authors:
 *     Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
 *
 *  Copyright:
 *     Martin Mann, 2007
 *
 *  This file is part of the CPSP-tools package:
 *     http://www.bioinf.uni-freiburg.de/sw/cpsp/
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#ifndef GC_NQ_SUBSUME_HH_
#define GC_NQ_SUBSUME_HH_


#include "gecode/int.hh"

#include "gecode/iter.hh"

#include <iostream>

namespace Gecode { namespace Int { namespace Rel {


  template <class View>
  class NqSubsume : public BinaryPropagator<View,PC_INT_DOM> {
  protected:
    using BinaryPropagator<View,PC_INT_DOM>::x0;
    using BinaryPropagator<View,PC_INT_DOM>::x1;
    unsigned int maxCheckSize;

    NqSubsume(Space* home, bool share, NqSubsume<View>& p);
    NqSubsume(Space* home, View x0, View x1, unsigned int maxCheckSize_);
  public:
    virtual Actor* copy(Space* home, bool share);
    virtual PropCost cost(void) const;
    virtual ExecStatus propagate(Space* home);
    static  ExecStatus post(Space* home, View x0, View x1, 
    unsigned int maxCheckSize_ = Limits::Int::int_max);
  };


  template <class View>
  forceinline
  NqSubsume<View>::NqSubsume(Space* home, View x0, View x1, unsigned int maxCheckSize_)
    : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1), maxCheckSize(maxCheckSize_) {}

  template <class View>
  forceinline
  ExecStatus
  NqSubsume<View>::post(Space* home, View x0, View x1, unsigned int maxCheckSize_){
    if (x0.assigned()) {
      GECODE_ME_CHECK(x1.nq(home,x0.val()));
    } else if (x1.assigned()) {
      GECODE_ME_CHECK(x0.nq(home,x1.val()));
    } else if (same(x0,x1)) {
      return ES_FAILED;
    } else {
      (void) new (home) NqSubsume<View>(home,x0,x1,maxCheckSize_);
    }
    return ES_OK;
  }

  template <class View>
  forceinline
  NqSubsume<View>::NqSubsume(Space* home, bool share, NqSubsume<View>& p)
    : BinaryPropagator<View,PC_INT_DOM>(home,share,p), maxCheckSize(p.maxCheckSize) {}

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

  template <class View>
  forceinline
  PropCost
  NqSubsume<View>::cost(void) const {
    return PC_BINARY_LO;
  }

  template <class View>
  forceinline
  ExecStatus
  NqSubsume<View>::propagate(Space* home) {
    if (x0.assigned()) {
      GECODE_ME_CHECK(x1.nq(home,x0.val()));
      return ES_SUBSUMED;
    } else if (x1.assigned()) {
      GECODE_ME_CHECK(x0.nq(home,x1.val()));
      return ES_SUBSUMED;
    } else {
            // a references the smaller view
        Gecode::Int::IntView* a = &x0, *b = &x1;
        if(a->size() > b->size()) {
            a = &x1, b = &x0;
        }
            // checking if view is small enough
        if (a->size() <= maxCheckSize) {
            ViewRanges< IntView >  ra(*a), rb(*b);
            while (ra() && rb()) {
                if ( (ra.min() <= rb.min() && ra.max() >= rb.min())
                    || (rb.min() <= ra.min() && rb.max() >= ra.min())) {
                    return ES_FIX;
                }
                while (ra() && ra.max() < rb.min()) ++ra;
                while (rb() && ra() && rb.max() < ra.min()) ++rb;
            }
/*          
            Iter::Ranges::ToValues< ViewRanges< IntView > > it;
            it.init( ra );
            while ( it() ) {    // check if all elements of a are not in b
                if (b->in(it.val())) {
                    return ES_FIX;
                }
                ++it;
            }
*/
            return ES_SUBSUMED;
        }
    }
    return ES_FIX;
  }

}}}

#endif /*GC_NQ_SUBSUME_HH_*/