Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
40 kB · 1180 lines
C++
at develop
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Guido Tack <tack@gecode.org> * * Contributing authors: * Christian Schulte <schulte@gecode.org> * * Copyright: * Guido Tack, 2004 * Christian Schulte, 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. * */
#include <iostream>
namespace Gecode { namespace Set {
/** * \defgroup TaskActorSetView Set views * * Set propagators and branchings compute with set views. * Set views provide views on set variable implementations, * set constants, and integer variable implementations. * \ingroup TaskActorSet */
/** * \brief %Set view for set variables * \ingroup TaskActorSetView */
class SetView : public VarImpView<SetVar> { protected: using VarImpView<SetVar>::x; public: /// \name Constructors and initialization //@{ /// Default constructor SetView(void); /// Initialize from set variable \a y SetView(const SetVar& y); /// Initialize from set variable implementation \a y SetView(SetVarImp* y); //@}
/// \name Value access //@{
/// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name Delta information for advisors //@{ /// Return modification event static ModEvent modevent(const Delta& d); /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@} };
/** * \brief Print set variable view * \relates Gecode::Set::SetView */ template<class Char, class Traits> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const SetView& x);
// Forward declarations for friends class ConstSetView; bool operator ==(const ConstSetView&, const ConstSetView&); bool operator !=(const ConstSetView&, const ConstSetView&);
/** * \brief Constant view * * A constant set view \f$x\f$ for a set \f$s\f$ provides operations such * that \f$x\f$ behaves like \f$s\f$. * \ingroup TaskActorSetView */ class ConstSetView : public ConstView<SetView> { friend class LubRanges<ConstSetView>; friend class GlbRanges<ConstSetView>; friend bool Gecode::Set::operator ==(const Gecode::Set::ConstSetView&, const Gecode::Set::ConstSetView&); friend bool Gecode::Set::operator !=(const Gecode::Set::ConstSetView&, const Gecode::Set::ConstSetView&); private: int *ranges; int size; unsigned int domSize; public: /// \name Constructors and initialization //@{ /// Default constructor ConstSetView(void); /// Construct with \a s as the domain ConstSetView(Space& home, const IntSet& s); //@}
/// \name Value access //@{ /// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name Cloning //@{ /// Update this view to be a clone of view \a y void update(Space& home, ConstSetView& y); //@}
/// \name Delta information for advisors //@{ /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
/// \name Ordering //@{ /// Whether this view comes before view \a y (arbitray order) bool operator <(const ConstSetView& y) const; //@} };
/** * \brief Print constant set view * \relates Gecode::Set::ConstSetView */ template<class Char, class Traits> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ConstSetView& x);
/** \name View comparison * \relates Gecode::Set::ConstSetView */ //@{ /// Test whether views \a x and \a y are the same bool operator ==(const ConstSetView& x, const ConstSetView& y); /// Test whether views \a x and \a y are not the same bool operator !=(const ConstSetView& x, const ConstSetView& y); //@}
/** * \brief Constant view for the empty set * * A constant set view \f$x\f$ for the empty set provides operations such * that \f$x\f$ behaves like the empty set. * \ingroup TaskActorSetView */
class EmptyView : public ConstView<SetView> { public: /// \name Constructors and initialization //@{ /// Default constructor EmptyView(void); //@}
/// \name Value access //@{ /// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name Delta information for advisors //@{ /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
};
/** * \brief Print empty set view * \relates Gecode::Set::EmptyView */ template<class Char, class Traits> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const EmptyView& x);
/** \name View comparison * \relates Gecode::Set::EmptyView */ //@{ /// Test whether views \a x and \a y are the same bool operator ==(const EmptyView& x, const EmptyView& y); /// Test whether views \a x and \a y are the same bool operator !=(const EmptyView& x, const EmptyView& y); //@}
/** * \brief Constant view for the universe * * A constant set view \f$x\f$ for the universe provides operations such * that \f$x\f$ behaves like the universe. * \ingroup TaskActorSetView */
class UniverseView : public ConstView<SetView> { public: /// \name Constructors and initialization //@{ /// Default constructor UniverseView(void); //@}
/// \name Value access //@{
/// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name Delta information for advisors //@{ /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
};
/** * \brief Print universe set view * \relates Gecode::Set::UniverseView */ template<class Char, class Traits> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const UniverseView& x);
/** \name View comparison * \relates Gecode::Set::UniverseView */ //@{ /// Test whether views \a x and \a y are the same bool operator ==(const UniverseView& x, const UniverseView& y); /// Test whether views \a x and \a y are the not same bool operator !=(const UniverseView& x, const UniverseView& y); //@}
/** * \brief Singleton set view * * A singleton set view \f$s\f$ for an integer view \f$x\f$ provides * operations such that \f$s\f$ behaves like the singleton set \f$\{x\}\f$. * \ingroup TaskActorSetView */
class SingletonView : public DerivedView<Gecode::Int::IntView> { protected: using DerivedView<Gecode::Int::IntView>::x;
/// Convert set variable PropCond \a pc to a PropCond for integer variables static PropCond pc_settoint(PropCond pc); /// Convert integer variable ModEvent \a me to a ModEvent for set variables static ModEvent me_inttoset(ModEvent me); /// Convert set variable ModEvent \a me to a ModEvent for integer variables static ModEvent me_settoint(ModEvent me);
public: /// \name Constructors and initialization //@{ /// Default constructor SingletonView(void); /// Initialize with integer view \a y SingletonView(Gecode::Int::IntView& y); /// Initialize with integer variable \a y SingletonView(const Gecode::IntVar& y); //@}
/// \name Value access //@{
/// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name View-dependent propagator support //@{ /// Schedule propagator \a p with modification event \a me static void schedule(Space& home, Propagator& p, ModEvent me); /// Return modification event for view type in \a med static ModEvent me(const ModEventDelta& med); /// Translate modification event \a me to modification event delta for view static ModEventDelta med(ModEvent); //@}
/// \name Dependencies //@{ /** * \brief Subscribe propagator \a p with propagation condition \a pc to view * * In case \a schedule is false, the propagator is just subscribed but * not scheduled for execution (this must be used when creating * subscriptions during propagation). */ void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /// Cancel subscription of propagator \a p with propagation condition \a pc to view void cancel(Space& home, Propagator& p, PropCond pc); /// Re-schedule propagator \a p with propagation condition \a pc void reschedule(Space& home, Propagator& p, PropCond pc); /// Subscribe advisor \a a to view void subscribe(Space& home, Advisor& a); /// Cancel subscription of advisor \a a void cancel(Space& home, Advisor& a); //@}
/// \name Delta information for advisors //@{ /// Return modification event static ModEvent modevent(const Delta& d); /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
};
/** * \brief Print singleton set view * \relates Gecode::Set::SingletonView */ template<class Char, class Traits> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const SingletonView& x);
/** \name View comparison * \relates Gecode::Set::SingletonView */ //@{ /// Test whether views \a x and \a y are the same bool operator ==(const SingletonView& x, const SingletonView& y); /// Test whether views \a x and \a y are the not same bool operator !=(const SingletonView& x, const SingletonView& y); //@}
/** * \brief Complement set view * * A complement set view \f$s\f$ for a set view \f$t\f$ provides * operations such that \f$s\f$ behaves like the complement of \f$\{t\}\f$. * The complement is defined in terms of the set universe. * \ingroup TaskActorSetView */
template<class View> class ComplementView : public DerivedView<View> { protected: using DerivedView<View>::x;
public: /// Negate the propagation condition \a pc static PropCond pc_negateset(PropCond pc); /// Negate the modification event \a me static ModEvent me_negateset(ModEvent me);
/// \name Constructors and initialization //@{ /// Default constructor ComplementView(void); /// Initialize with set view \a y explicit ComplementView(View& y); //@}
/// \name Value access //@{
/// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return \a n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name View-dependent propagator support //@{ /// Schedule propagator \a p with modification event \a me static void schedule(Space& home, Propagator& p, ModEvent me); /// Return modification event for view type in \a med static ModEvent me(const ModEventDelta& med); /// Translate modification event \a me to modification event delta for view static ModEventDelta med(ModEvent); //@}
/// \name Dependencies //@{ /** * \brief Subscribe propagator \a p with propagation condition \a pc to view * * In case \a schedule is false, the propagator is just subscribed but * not scheduled for execution (this must be used when creating * subscriptions during propagation). */ void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /// Cancel subscription of propagator \a p with propagation condition \a pc to view void cancel(Space& home, Propagator& p, PropCond pc); /// Subscribe advisor \a a to view void subscribe(Space& home, Advisor& a); /// Cancel subscription of advisor \a a void cancel(Space& home, Advisor& a); //@}
/// \name Delta information for advisors //@{ /// Return modification event static ModEvent modevent(const Delta& d); /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
};
/** * \brief Print complement set view * \relates Gecode::Set::ComplementView */ template<class Char, class Traits, class View> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ComplementView<View>& x);
/** \name View comparison * \relates Gecode::Set::ComplementView */ //@{ /// Test whether views \a x and \a y are the same template<class View> bool operator ==(const ComplementView<View>& x, const ComplementView<View>& y); /// Test whether views \a x and \a y are the not same template<class View> bool operator !=(const ComplementView<View>& x, const ComplementView<View>& y); //@}
template<class View> class LubDiffRanges; template<class View> class GlbDiffRanges;
/** * \brief Cached set view * * A cached set view \f$s\f$ for a set view \f$t\f$ adds operations * for cacheing the current domain of \f$t\f$ and comparing the current * domain to the cached domain. Cached views make it easy to implement * incremental propagation algorithms. * * \ingroup TaskActorSetView */
template<class View> class CachedView : public DerivedView<View> { friend class LubDiffRanges<View>; friend class GlbDiffRanges<View>; protected: using DerivedView<View>::x;
/// The cached least upper bound LUBndSet lubCache; /// The cached greatest lower bound GLBndSet glbCache;
public:
/// \name Constructors and initialization //@{ /// Default constructor CachedView(void); /// Initialize with set view \a y explicit CachedView(const View& y); //@}
/// \name Value access //@{
/// Return minimum cardinality unsigned int cardMin(void) const; /// Return maximum cardinality unsigned int cardMax(void) const; /// Return minimum of the least upper bound int lubMin(void) const; /// Return maximum of the least upper bound int lubMax(void) const; /// Return \a n-th smallest element of the least upper bound int lubMinN(unsigned int n) const; /// Return minimum of the greatest lower bound int glbMin(void) const; /// Return maximum of the greatest lower bound int glbMax(void) const;
/// Return the number of elements in the greatest lower bound unsigned int glbSize(void) const; /// Return the number of elements in the least upper bound unsigned int lubSize(void) const; /// Return the number of unknown elements unsigned int unknownSize(void) const; //@}
/// \name Domain tests //@{ /// Test whether \a i is in the greatest lower bound bool contains(int i) const; /// Test whether \a i is not in the least upper bound bool notContains(int i) const; //@}
/// \name Domain update by value //@{ /// Restrict cardinality to be greater than or equal to \a m ModEvent cardMin(Space& home, unsigned int m); /// Restrict cardinality to be less than or equal to \a m ModEvent cardMax(Space& home, unsigned int m); /** * \brief Update greatest lower bound to include all elements * between and including \a i and \a j */ ModEvent include(Space& home,int i,int j); /** * \brief Restrict least upper bound to not contain all elements * between and including \a i and \a j */ ModEvent exclude(Space& home,int i,int j); /// Update greatest lower bound to contain \a i ModEvent include(Space& home,int i); /// Restrict least upper bound to not contain \a i ModEvent exclude(Space& home,int i); /** * \brief Update least upper bound to contain at most all elements * between and including \a i and \a j */ ModEvent intersect(Space& home,int i,int j); /// Update least upper bound to contain at most the element \a i ModEvent intersect(Space& home,int i); //@}
/// \name Domain update by range iterator //@{
/// Remove range sequence described by \a i from least upper bound template<class I> ModEvent excludeI(Space& home, I& i); /// Include range sequence described by \a i in greatest lower bound template<class I> ModEvent includeI(Space& home, I& i); /// Intersect least upper bound with range sequence described by \a i template<class I> ModEvent intersectI(Space& home, I& iter); //@}
/// \name View-dependent propagator support //@{ /// Schedule propagator \a p with modification event \a me static void schedule(Space& home, Propagator& p, ModEvent me); /// Return modification event for view type in \a med static ModEvent me(const ModEventDelta& med); /// Translate modification event \a me to modification event delta for view static ModEventDelta med(ModEvent); //@}
/// \name Dependencies //@{ /** * \brief Subscribe propagator \a p with propagation condition \a pc to view * * In case \a schedule is false, the propagator is just subscribed but * not scheduled for execution (this must be used when creating * subscriptions during propagation). */ void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /// Cancel subscription of propagator \a p with propagation condition \a pc to view void cancel(Space& home, Propagator& p, PropCond pc); /// Subscribe advisor \a a to view void subscribe(Space& home, Advisor& a); /// Cancel subscription of advisor \a a void cancel(Space& home, Advisor& a); //@}
/// \name Delta information for advisors //@{ /// Return modification event static ModEvent modevent(const Delta& d); /// Return minimum value just pruned from glb int glbMin(const Delta& d) const; /// Return maximum value just pruned from glb int glbMax(const Delta& d) const; /// Test whether arbitrary values got pruned from glb bool glbAny(const Delta& d) const; /// Return minimum value just pruned from lub int lubMin(const Delta& d) const; /// Return maximum value just pruned from lub int lubMax(const Delta& d) const; /// Test whether arbitrary values got pruned from lub bool lubAny(const Delta& d) const; //@}
/// \name Domain cache operations //@{ /// Initialize cache to bounds \a glb and \a lub void initCache(Space& home, const IntSet& glb, const IntSet& lub); /// Update greatest lower bound cache to current domain void cacheGlb(Space& home); /// Update least upper bound cache to current domain void cacheLub(Space& home); /// Check whether greatest lower bound cache differs from current domain bool glbModified(void) const; /// Check whether least upper bound cache differs from current domain bool lubModified(void) const; //@}
/// \name Cloning //@{ /// Update this view to be a clone of view \a y void update(Space& home, CachedView<View>& y); //@} };
/** * \brief Print cached set view * \relates Gecode::Set::CachedView */ template<class Char, class Traits, class View> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const CachedView<View>& x);
/** \name View comparison * \relates Gecode::Set::CachedView */ //@{ /// Test whether views \a x and \a y are the same template<class View> bool operator ==(const CachedView<View>& x, const CachedView<View>& y); /// Test whether views \a x and \a y are the not same template<class View> bool operator !=(const CachedView<View>& x, const CachedView<View>& y); //@}
/** * \brief %Range iterator for difference of greatest lower bound and cache * \relates Gecode::Set::CachedView */ template<class View> class GlbDiffRanges : public Iter::Ranges::Diff<GlbRanges<View>,BndSetRanges> { protected: /// Lower bound iterator GlbRanges<View> gr; /// Cached lower bound BndSetRanges cr; public: /// Constructor GlbDiffRanges(const CachedView<View>& x); };
/** * \brief %Range iterator for difference of least upper bound and cache * \relates Gecode::Set::CachedView */ template<class View> class LubDiffRanges : public Iter::Ranges::Diff<BndSetRanges,LubRanges<View> > { protected: /// Cached upper bound BndSetRanges cr; /// Upper bound iterator LubRanges<View> lr; public: /// Constructor LubDiffRanges(const CachedView<View>& x); };
}}
#include <gecode/set/var/set.hpp>
#include <gecode/set/view/set.hpp>
#include <gecode/set/view/const.hpp>#include <gecode/set/view/singleton.hpp>#include <gecode/set/view/complement.hpp>#include <gecode/set/view/cached.hpp>
#include <gecode/set/view/print.hpp>#include <gecode/set/var/print.hpp>
// STATISTICS: set-var