Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
13 kB · 495 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Guido Tack <tack@gecode.org> * * Copyright: * Guido Tack, 2011 * * 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 { namespace Rel {
/** * \brief Representation of the characteristic functions of two sets */ class CharacteristicSets { protected: /// Size of the combined upper bounds unsigned int xsize; /// Storage for the characteristic functions Support::BitSetBase b; /// Elements in the combined upper bounds int* ub; /// Whether lower bound of x was updated bool xlm; /// Whether upper bound of x was updated bool xum; /// Whether lower bound of y was updated bool ylm; /// Whether upper bound of y was updated bool yum; /// Get bit \a i bool get(unsigned int i) const; /// Set bit \a i to value \a j void set(unsigned int i, bool j);
/// \brief Value iterator for characteristic function class CSIter { public: /// Pointer to the underlying set CharacteristicSets* cs; /// Current position unsigned int i; /// Offset from start of bitset unsigned int xoff; /// Offset for each element (0=lower bound, 1=upper bound) unsigned int yoff; /// Move iterator to next element void operator++ (void); /// Default constructor CSIter(void); /// Constructor CSIter(CharacteristicSets& cs0, unsigned int xoff0, unsigned int yoff0); /// Test if iterator is finished bool operator() (void) const; /// Value of current iterator position int val(void) const; };
public: /// Constructor template<class View0, class View1> CharacteristicSets(Region& re, View0 x, View1 y);
/// Return minimum of element \a i for variable x bool xmin(unsigned int i) const; /// Return maximum of element \a i for variable x bool xmax(unsigned int i) const; /// Return minimum of element \a i for variable y bool ymin(unsigned int i) const; /// Return maximum of element \a i for variable y bool ymax(unsigned int i) const;
/// Set minimum of element \a i for variable x to \a j void xmin(unsigned int i, bool j); /// Set maximum of element \a i for variable x to \a j void xmax(unsigned int i, bool j); /// Set minimum of element \a i for variable y to \a j void ymin(unsigned int i, bool j); /// Set maximum of element \a i for variable y to \a j void ymax(unsigned int i, bool j);
/// Update upper bound of \f$x_i\f$ to \a j ModEvent xlq(unsigned int i, bool j); /// Update lower bound of \f$x_i\f$ to \a j ModEvent xgq(unsigned int i, bool j); /// Update upper bound of \f$y_i\f$ to \a j ModEvent ylq(unsigned int i, bool j); /// Update lower bound of \f$y_i\f$ to \a j ModEvent ygq(unsigned int i, bool j);
/// Return size of combined upper bounds unsigned int size(void) const;
/// Prune \a x and \a y using computed bounds template<class View0, class View1> ExecStatus prune(Space& home, View0 x, View1 y);
};
forceinline bool CharacteristicSets::get(unsigned int i) const { return b.get(i); } forceinline void CharacteristicSets::set(unsigned int i, bool j) { if (j) b.set(i); else b.clear(i); } forceinline unsigned int CharacteristicSets::size(void) const { return xsize; }
forceinline CharacteristicSets::CSIter::CSIter(void) {} forceinline CharacteristicSets::CSIter::CSIter(CharacteristicSets& cs0, unsigned int xoff0, unsigned int yoff0) : cs(&cs0), i(0), xoff(xoff0), yoff(yoff0) { while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff)) i++; } forceinline void CharacteristicSets::CSIter::operator++ (void) { i++; while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff)) i++; } forceinline bool CharacteristicSets::CSIter::operator() (void) const { return i<cs->xsize; } forceinline int CharacteristicSets::CSIter::val(void) const { return cs->ub[i]; }
forceinline bool CharacteristicSets::xmin(unsigned int i) const { return get(2*i); } forceinline bool CharacteristicSets::xmax(unsigned int i) const { return get(2*i+1); } forceinline bool CharacteristicSets::ymin(unsigned int i) const { return get(2*xsize+2*i); } forceinline bool CharacteristicSets::ymax(unsigned int i) const { return get(2*xsize+2*i+1); }
forceinline void CharacteristicSets::xmin(unsigned int i, bool j) { set(2*i,j); } forceinline void CharacteristicSets::xmax(unsigned int i, bool j) { set(2*i+1,j); } forceinline void CharacteristicSets::ymin(unsigned int i, bool j) { set(2*xsize+2*i,j); } forceinline void CharacteristicSets::ymax(unsigned int i, bool j) { set(2*xsize+2*i+1,j); }
forceinline ModEvent CharacteristicSets::xlq(unsigned int i, bool j) { if (!j) { if (xmin(i)) return ME_SET_FAILED; if (xmax(i)) { xmax(i,false); xum=true; } } return ME_SET_NONE; } forceinline ModEvent CharacteristicSets::xgq(unsigned int i, bool j) { if (j) { if (!xmax(i)) return ME_SET_FAILED; if (!xmin(i)) { xmin(i,true); xlm=true; } } return ME_SET_NONE; } forceinline ModEvent CharacteristicSets::ylq(unsigned int i, bool j) { if (!j) { if (ymin(i)) return ME_SET_FAILED; if (ymax(i)) { ymax(i,false); yum=true; } } return ME_SET_NONE; } forceinline ModEvent CharacteristicSets::ygq(unsigned int i, bool j) { if (j) { if (!ymax(i)) return ME_SET_FAILED; if (!ymin(i)) { ymin(i,true); ylm=true; } } return ME_SET_NONE; }
template<class View0, class View1> forceinline ExecStatus CharacteristicSets::prune(Space& home, View0 x, View1 y) { if (xlm) { CSIter i(*this,0,0); Iter::Values::ToRanges<CSIter> ir(i); GECODE_ME_CHECK(x.includeI(home,ir)); } if (xum) { CSIter i(*this,0,1); Iter::Values::ToRanges<CSIter> ir(i); GECODE_ME_CHECK(x.intersectI(home,ir)); } if (ylm) { CSIter i(*this,2*xsize,0); Iter::Values::ToRanges<CSIter> ir(i); GECODE_ME_CHECK(y.includeI(home,ir)); } if (yum) { CSIter i(*this,2*xsize,1); Iter::Values::ToRanges<CSIter> ir(i); GECODE_ME_CHECK(y.intersectI(home,ir)); } return ES_OK; }
template<class View0, class View1> forceinline CharacteristicSets::CharacteristicSets(Region& re,View0 x, View1 y) : xlm(false), xum(false), ylm(false), yum(false) { LubRanges<View0> xlub(x); LubRanges<View1> ylub(y); Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > xylub(xlub,ylub); Iter::Ranges::Cache xylubc(re,xylub); xsize = Iter::Ranges::size(xylubc); b.init(re,4*xsize); ub = re.alloc<int>(xsize); xylubc.reset(); Iter::Ranges::ToValues<Iter::Ranges::Cache> xylubv(xylubc); LubRanges<View0> xur(x); GlbRanges<View0> xlr(x); LubRanges<View1> yur(y); GlbRanges<View1> ylr(y); Iter::Ranges::ToValues<LubRanges<View0> > xuv(xur); Iter::Ranges::ToValues<GlbRanges<View0> > xlv(xlr); Iter::Ranges::ToValues<LubRanges<View1> > yuv(yur); Iter::Ranges::ToValues<GlbRanges<View1> > ylv(ylr); for (unsigned int i=0; xylubv(); ++xylubv, ++i) { ub[i] = xylubv.val(); if (xlv() && xylubv.val()==xlv.val()) { b.set(2*i); ++xlv; } if (xuv() && xylubv.val()==xuv.val()) { b.set(2*i+1); ++xuv; } if (ylv() && xylubv.val()==ylv.val()) { b.set(2*xsize+2*i); ++ylv; } if (yuv() && xylubv.val()==yuv.val()) { b.set(2*xsize+2*i+1); ++yuv; } } }
template<class View0, class View1, bool strict> forceinline Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y) : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
template<class View0, class View1, bool strict> forceinline Lq<View0,View1,strict>::Lq(Space& home, Lq& p) : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p) {}
template<class View0, class View1, bool strict> ExecStatus Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) { if (strict) GECODE_ME_CHECK(y.cardMin(home,1)); if (same(x,y)) return strict ? ES_FAILED : ES_OK; (void) new (home) Lq(home,x,y); return ES_OK; }
template<class View0, class View1, bool strict> Actor* Lq<View0,View1,strict>::copy(Space& home) { return new (home) Lq(home,*this); }
template<class View0, class View1, bool strict> ExecStatus Lq<View0,View1,strict>::propagate(Space& home, const ModEventDelta&) { if ( (!strict) && x1.cardMax()==0) { GECODE_ME_CHECK(x0.cardMax(home,0)); }
if (x0.cardMax()==0) { return home.ES_SUBSUMED(*this); }
if (x0.glbMin() < x1.lubMin()) return ES_FAILED; if (x1.glbMin() < x0.lubMin()) return home.ES_SUBSUMED(*this);
bool assigned = x0.assigned() && x1.assigned();
Region re; CharacteristicSets cs(re,x0,x1);
/* * State 1 * */ unsigned int i=0; unsigned int firsti=0; unsigned int n=cs.size(); while ((i<n) && (cs.xmin(i) == cs.ymax(i))) { // case: =, >= GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i))); GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i))); i++; }
if (i == n) {// case: $ if (strict) { return ES_FAILED; } else { GECODE_ES_CHECK(cs.prune(home,x0,x1)); return home.ES_SUBSUMED(*this); } }
// Possible cases left: <, <=, > (yields failure), ? GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i))); GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
if (cs.xmax(i) < cs.ymin(i)) { // case: < (after tell) GECODE_ES_CHECK(cs.prune(home,x0,x1)); return home.ES_SUBSUMED(*this); }
firsti=i;
/* * State 2 * prefix: (?|<=) * */ i++;
while ((i < n) && (cs.xmin(i) == cs.ymax(i)) && (cs.xmax(i) == cs.ymin(i))) { // case: = i++; }
if (i == n) { // case: $ if (strict) goto rewrite_le; else goto rewrite_lq; }
if (cs.xmax(i) < cs.ymin(i)) // case: < goto rewrite_lq;
if (cs.xmin(i) > cs.ymax(i)) // case: > goto rewrite_le;
if (cs.xmax(i) <= cs.ymin(i)) { // case: <= (invariant: not =, <) /* * State 3 * prefix: (?|<=),<= * */ i++;
while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {// case: <=, = i++; }
if (i == n) { // case: $ if (strict) { GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; } else { goto rewrite_lq; } }
if (cs.xmax(i) < cs.ymin(i)) // case: < goto rewrite_lq;
GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; }
if (cs.xmin(i) >= cs.ymax(i)) { // case: >= (invariant: not =, >) /* * State 4 * prefix: (?|<=) >= * */ i++;
while ((i < n) && (cs.xmin(i) == cs.ymax(i))) { // case: >=, = i++; }
if (i == n) { // case: $ if (strict) { goto rewrite_le; } else { GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; } }
if (cs.xmin(i) > cs.ymax(i)) // case: > goto rewrite_le;
GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; }
GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
rewrite_le: GECODE_ME_CHECK(cs.xlq(firsti,false)); GECODE_ME_CHECK(cs.ygq(firsti,true)); GECODE_ES_CHECK(cs.prune(home,x0,x1)); return home.ES_SUBSUMED(*this); rewrite_lq: GECODE_ES_CHECK(cs.prune(home,x0,x1)); return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; }
}}}
// STATISTICS: set-prop