Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
19 kB · 743 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Guido Tack <tack@gecode.org> * * Copyright: * Guido Tack, 2004 * * 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 {
/** * \brief %Range iterator for a two-dimensional array * \ingroup TaskActorSetView */ class ArrayRanges { private: int *_ranges; int _size; int _pos; public: /// \name Constructors and initialization //@{ /// Default constructor ArrayRanges(void) : _ranges(nullptr), _size(0), _pos(0) {} /// Initialize with ranges for array \a ranges which is of size \a size ArrayRanges(int *ranges, int size) : _ranges(ranges), _size(size), _pos(0) {} /// Initialize with ranges for array \a ranges which is of size \a size void init(int* ranges, int size) { _ranges = ranges; _size = size; _pos = 0; } //@}
/// \name Iteration control //@{ /// Test whether iterator is still at a range or done bool operator ()(void) const { return _pos<_size; } /// Move iterator to next range (if possible) void operator ++(void) { _pos++; } //@}
/// \name Range access //@{ /// Return smallest value of range int min(void) const { return _ranges[_pos*2]; } /// Return largest value of range int max(void) const { return _ranges[_pos*2+1]; } /// Return width of range (distance between minimum and maximum) unsigned int width(void) const { return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1); } //@} };
forceinline ConstSetView::ConstSetView(void) : ranges(nullptr), size(0), domSize(0) {}
forceinline ConstSetView::ConstSetView(Space& home, const IntSet& dom) { size = dom.ranges(); domSize = 0; if (size > 0) { ranges = home.alloc<int>(2*size); IntSetRanges dr(dom); for (int i=0; dr(); ++dr, i+=2) { int min = dr.min(); int max = dr.max(); ranges[i] = min; ranges[i+1] = max; domSize += static_cast<unsigned int>(max-min+1); } } else { ranges = nullptr; } }
forceinline unsigned int ConstSetView::glbSize(void) const { return domSize; }
forceinline unsigned int ConstSetView::lubSize(void) const { return domSize; }
forceinline unsigned int ConstSetView::unknownSize(void) const { return 0; }
forceinline bool ConstSetView::contains(int i) const { for (int j=size; j--; ) { if (ranges[2*j+1] < i) return false; if (ranges[2*j] >= i) return true; } return false; }
forceinline bool ConstSetView::notContains(int i) const { return !contains(i); }
forceinline unsigned int ConstSetView::cardMin(void) const { return domSize; }
forceinline unsigned int ConstSetView::cardMax(void) const { return domSize; }
forceinline int ConstSetView::lubMin(void) const { return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0]; }
forceinline int ConstSetView::lubMax(void) const { return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1]; }
forceinline int ConstSetView::glbMin(void) const { return lubMin(); }
forceinline int ConstSetView::glbMax(void) const { return lubMax(); }
forceinline ModEvent ConstSetView::cardMin(Space&,unsigned int c) { return c<=domSize ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::cardMax(Space&,unsigned int c) { return c>=domSize ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::include(Space&,int c) { return contains(c) ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::exclude(Space&,int c) { return contains(c) ? ME_SET_FAILED : ME_SET_NONE; }
forceinline ModEvent ConstSetView::intersect(Space&,int c) { return (size==0 || (size==1 && ranges[0]==ranges[1] && ranges[0]==c)) ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::intersect(Space&,int i,int j) { return (glbMin()>=i && glbMax()<=j) ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::include(Space&,int i,int j) { Iter::Ranges::Singleton single(i,j); ArrayRanges ar(ranges, size); return (single() && Iter::Ranges::subset(single, ar)) ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent ConstSetView::exclude(Space&,int i,int j) { Iter::Ranges::Singleton single(i,j); ArrayRanges ar(ranges, size); return (single() && Iter::Ranges::subset(single, ar)) ? ME_SET_FAILED : ME_SET_NONE; }
template<class I> ModEvent ConstSetView::excludeI(Space&,I& i) { ArrayRanges ar(ranges, size); return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE; }
template<class I> ModEvent ConstSetView::includeI(Space&,I& i) { ArrayRanges ar(ranges, size); return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED; }
template<class I> ModEvent ConstSetView::intersectI(Space&,I& i) { ArrayRanges ar(ranges, size); return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED; }
forceinline void ConstSetView::update(Space& home, ConstSetView& p) { ConstView<SetView>::update(home,p); // dispose old ranges if (size > 0) home.free<int>(ranges, 2);
domSize = p.domSize; size = p.size; if (size == 0) { ranges = nullptr; } else { // copy ranges from p ranges = home.alloc<int>(2*size); for (int i=size; i--; ) { ranges[2*i] = p.ranges[2*i]; ranges[2*i+1] = p.ranges[2*i+1]; } } }
/* * Delta information for advisors * */ forceinline int ConstSetView::glbMin(const Delta&) const { GECODE_NEVER; return 0; } forceinline int ConstSetView::glbMax(const Delta&) const { GECODE_NEVER; return 0; } forceinline bool ConstSetView::glbAny(const Delta&) const { GECODE_NEVER; return false; } forceinline int ConstSetView::lubMin(const Delta&) const { GECODE_NEVER; return 0; } forceinline int ConstSetView::lubMax(const Delta&) const { GECODE_NEVER; return 0; } forceinline bool ConstSetView::lubAny(const Delta&) const { GECODE_NEVER; return false; }
forceinline EmptyView::EmptyView(void) {}
forceinline unsigned int EmptyView::glbSize(void) const { return 0; }
forceinline unsigned int EmptyView::lubSize(void) const { return 0; }
forceinline unsigned int EmptyView::unknownSize(void) const { return 0; }
forceinline bool EmptyView::contains(int) const { return false; }
forceinline bool EmptyView::notContains(int) const { return true; }
forceinline unsigned int EmptyView::cardMin(void) const { return 0; }
forceinline unsigned int EmptyView::cardMax(void) const { return 0; }
forceinline int EmptyView::lubMin(void) const { return 0; }
forceinline int EmptyView::lubMax(void) const { return 0; }
forceinline int EmptyView::glbMin(void) const { return 0; }
forceinline int EmptyView::glbMax(void) const { return 0; }
forceinline ModEvent EmptyView::cardMin(Space&,unsigned int c) { return c==0 ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent EmptyView::cardMax(Space&,unsigned int) { return ME_SET_NONE; }
forceinline ModEvent EmptyView::include(Space&,int) { return ME_SET_FAILED; }
forceinline ModEvent EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
forceinline ModEvent EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
forceinline ModEvent EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
forceinline ModEvent EmptyView::include(Space&,int,int) { return ME_SET_FAILED; }
forceinline ModEvent EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
template<class I> ModEvent EmptyView::excludeI(Space&,I&) { return ME_SET_NONE; }
template<class I> ModEvent EmptyView::includeI(Space&,I& i) { return i() ? ME_SET_FAILED : ME_SET_NONE; }
template<class I> ModEvent EmptyView::intersectI(Space&,I&) { return ME_SET_NONE; }
/* * Delta information for advisors * */ forceinline int EmptyView::glbMin(const Delta&) const { GECODE_NEVER; return 0; }
forceinline int EmptyView::glbMax(const Delta&) const { GECODE_NEVER; return 0; }
forceinline bool EmptyView::glbAny(const Delta&) const { GECODE_NEVER; return false; }
forceinline int EmptyView::lubMin(const Delta&) const { GECODE_NEVER; return 0; }
forceinline int EmptyView::lubMax(const Delta&) const { GECODE_NEVER; return 0; }
forceinline bool EmptyView::lubAny(const Delta&) const { GECODE_NEVER; return false; }
// Constant universe variable
forceinline UniverseView::UniverseView(void) {}
forceinline unsigned int UniverseView::glbSize(void) const { return Set::Limits::card; }
forceinline unsigned int UniverseView::lubSize(void) const { return Set::Limits::card; }
forceinline unsigned int UniverseView::unknownSize(void) const { return 0; }
forceinline bool UniverseView::contains(int) const { return true; }
forceinline bool UniverseView::notContains(int) const { return false; }
forceinline unsigned int UniverseView::cardMin(void) const { return Set::Limits::card; }
forceinline unsigned int UniverseView::cardMax(void) const { return Limits::card; }
forceinline int UniverseView::lubMin(void) const { return Limits::card; }
forceinline int UniverseView::lubMax(void) const { return Limits::card; }
forceinline int UniverseView::glbMin(void) const { return Limits::card; }
forceinline int UniverseView::glbMax(void) const { return Limits::card; }
forceinline ModEvent UniverseView::cardMin(Space&,unsigned int c) { return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE; }
forceinline ModEvent UniverseView::cardMax(Space&,unsigned int c) { return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED; }
forceinline ModEvent UniverseView::include(Space&,int) { return ME_SET_NONE; }
forceinline ModEvent UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
forceinline ModEvent UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
forceinline ModEvent UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
forceinline ModEvent UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
template<class I> ModEvent UniverseView::excludeI(Space&,I& i) { return i() ? ME_SET_FAILED : ME_SET_NONE; }
template<class I> forceinline ModEvent UniverseView::includeI(Space&,I&) { return ME_SET_NONE; }
forceinline ModEvent UniverseView::intersect(Space&,int i,int j) { return (i>Limits::min || j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE; }
template<class I> forceinline ModEvent UniverseView::intersectI(Space&,I& i) { return (i() && (i.min()>Limits::min || i.max()<Limits::max) ) ? ME_SET_FAILED : ME_SET_NONE; }
/* * Delta information for advisors * */ forceinline int UniverseView::glbMin(const Delta&) const { GECODE_NEVER; return 0; }
forceinline int UniverseView::glbMax(const Delta&) const { GECODE_NEVER; return 0; }
forceinline bool UniverseView::glbAny(const Delta&) const { GECODE_NEVER; return false; }
forceinline int UniverseView::lubMin(const Delta&) const { GECODE_NEVER; return 0; }
forceinline int UniverseView::lubMax(const Delta&) const { GECODE_NEVER; return 0; }
forceinline bool UniverseView::lubAny(const Delta&) const { GECODE_NEVER; return false; }
/* * Iterators * */
/** * \brief %Range iterator for least upper bound of constantly empty set view * \ingroup TaskActorSetView */ template<> class LubRanges<EmptyView> : public Iter::Ranges::Empty { public: /// \name Constructors and initialization //@{ /// Default constructor LubRanges(void) {} /// Initialize with ranges for view \a x LubRanges(const EmptyView& x) { (void)x; } /// Initialize with ranges for view \a x void init(const EmptyView& x) { (void)x; } //@} };
/** * \brief %Range iterator for greatest lower bound of constantly empty set view * \ingroup TaskActorSetView */ template<> class GlbRanges<EmptyView> : public Iter::Ranges::Empty { public: /// \name Constructors and initialization //@{ /// Default constructor GlbRanges(void) {} /// Initialize with ranges for view \a x GlbRanges(const EmptyView& x) { (void)x; } /// Initialize with ranges for view \a x void init(const EmptyView& x) { (void)x; } //@} };
/** * \brief %Range iterator for least upper bound of constant universe set view * \ingroup TaskActorSetView */ template<> class LubRanges<UniverseView> : public Iter::Ranges::Singleton { public: /// \name Constructors and initialization //@{ /// Default constructor LubRanges(void) : Iter::Ranges::Singleton(Limits::min, Limits::max) {} /// Initialize with ranges for view \a x LubRanges(const UniverseView& x) : Iter::Ranges::Singleton(Limits::min, Limits::max) { (void)x; } /// Initialize with ranges for view \a x void init(const UniverseView& x) { (void)x; } //@} };
/** * \brief %Range iterator for greatest lower bound of constant universe set view * \ingroup TaskActorSetView */ template<> class GlbRanges<UniverseView> : public Iter::Ranges::Singleton { public: /// \name Constructors and initialization //@{ /// Default constructor GlbRanges(void) : Iter::Ranges::Singleton(Limits::min, Limits::max) {} /// Initialize with ranges for view \a x GlbRanges(const UniverseView& x) : Iter::Ranges::Singleton(Limits::min, Limits::max) { (void)x; } /// Initialize with ranges for view \a x void init(const UniverseView& x) { (void)x; } //@} };
/** * \brief %Range iterator for least upper bound of constant set view * \ingroup TaskActorSetView */ template<> class LubRanges<ConstSetView> { private: ArrayRanges ar; public: /// \name Constructors and initialization //@{ /// Default constructor LubRanges(void) {} /// Initialize with ranges for view \a x LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {} /// Initialize with ranges for view \a x void init(const ConstSetView& x) { ar.init(x.ranges,x.size); } //@}
/// \name Iteration control //@{ /// Test whether iterator is still at a value or done bool operator ()(void) const { return ar(); } /// Move iterator to next value (if possible) void operator ++(void) { ++ar; } //@}
/// \name Range access //@{ /// Return smallest value of range int min(void) const { return ar.min(); } /// Return largest value of range int max(void) const { return ar.max(); } /// Return width of range (distance between minimum and maximum) unsigned int width(void) const { return ar.width(); } //@} };
/** * \brief %Range iterator for greatest lower bound of constant set view * \ingroup TaskActorSetView */ template<> class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> { public: /// \name Constructors and initialization //@{ /// Default constructor GlbRanges(void) {} /// Initialize with ranges for view \a x GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {} /// Initialize with ranges for view \a x void init(const ConstSetView& x) { LubRanges<ConstSetView>::init(x); } //@} };
forceinline bool ConstSetView::operator <(const ConstSetView& y) const { if (size < y.size) return true; if (size > y.size) return false; if (domSize < y.domSize) return true; if (domSize > y.domSize) return false; for (int i=size; i--; ) { if (ranges[2*i] < y.ranges[2*i]) return true; if (ranges[2*i] > y.ranges[2*i]) return false; if (ranges[2*i+1] < y.ranges[2*i+1]) return true; if (ranges[2*i+1] > y.ranges[2*i+1]) return false; } return false; }
/* * Testing * */ forceinline bool operator ==(const ConstSetView& x, const ConstSetView& y) { if ((x.size != y.size) || (x.domSize != y.domSize)) return false; for (int i=x.size; i--; ) if ((x.ranges[2*i] != y.ranges[2*i]) || (x.ranges[2*i+1] != y.ranges[2*i+1])) return false; return true; } forceinline bool operator !=(const ConstSetView& x, const ConstSetView& y) { return !(x == y); }
forceinline bool operator ==(const EmptyView&, const EmptyView&) { return true; } forceinline bool operator !=(const EmptyView&, const EmptyView&) { return false; }
forceinline bool operator ==(const UniverseView&, const UniverseView&) { return true; } forceinline bool operator !=(const UniverseView&, const UniverseView&) { return false; }
}}
// STATISTICS: set-var