Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
24 kB · 726 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * * Contributing authors: * Guido Tack <tack@gecode.org> * * Copyright: * Christian Schulte, 2002 * 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. * */
#include <cmath>
namespace Gecode { namespace Int {
class IntVarImp; class BoolVarImp;
/** * \brief Integer delta information for advisors * * Note that the same delta information is used for both * integer and Boolean variables and views. */ class IntDelta : public Delta { friend class IntVarImp; friend class BoolVarImp; private: int _min; ///< Smallest value just pruned int _max; ///< Largest value just pruned public: /// Create integer delta as providing no information IntDelta(void); /// Create integer delta with \a min and \a max IntDelta(int min, int max); /// Create integer delta with \a min IntDelta(int min); private: /// Return minimum int min(void) const; /// Return maximum int max(void) const; /// Return width unsigned int width(void) const; /// Test whether any domain change has happened bool any(void) const; };
}}
#include <gecode/int/var-imp/delta.hpp>
namespace Gecode { namespace Int {
class IntVarImpFwd; class IntVarImpBwd;
/** * \brief Integer variable implementation * * \ingroup Other */ class IntVarImp : public IntVarImpBase { friend class IntVarImpFwd; friend class IntVarImpBwd; protected: /** * \brief Lists of ranges (intervals) * * Range lists are doubly-linked storing the pointer to both * the next and the previous element in a single pointer. * That means that the next element is only available when * the previous element is supplied as additional information. * The same holds true for access to the previous element. */ class RangeList : public FreeList { protected: /// Minimum of range int _min; /// Maximum of range int _max; public: /// \name Constructors //@{ /// Default constructor (noop) RangeList(void); /// Initialize with minimum \a min and maximum \a max RangeList(int min, int max); /// Initialize with minimum \a min and maximum \a max and predecessor \a p and successor \a n RangeList(int min, int max, RangeList* p, RangeList* n); //@}
/// \name Access //@{ /// Return minimum int min(void) const; /// Return maximum int max(void) const; /// Return width (distance between maximum and minimum) unsigned int width(void) const;
/// Return next element (from previous \a p) RangeList* next(const RangeList* p) const; /// Return previous element (from next \a n) RangeList* prev(const RangeList* n) const; //@}
/// \name Update //@{ /// Set minimum to \a n void min(int n); /// Set maximum to \a n void max(int n);
/// Set previous element to \a p and next element to \a n void prevnext(RangeList* p, RangeList* n); /// Set next element from \a o to \a n void next(RangeList* o, RangeList* n); /// Set previous element from \a o to \a n void prev(RangeList* o, RangeList* n); /// Restore simple link to next element (so that it becomes a true free list) void fix(RangeList* n); //@}
/// \name Memory management //@{ /** * \brief Free memory for all elements between this and \a l (inclusive) * * \a p must be the pointer to the previous element of \c this. */ void dispose(Space& home, RangeList* p, RangeList* l); /** * \brief Free memory for all elements between this and \a l (inclusive) * * This routine assumes that the list has already been fixed. */ void dispose(Space& home, RangeList* l); /// Free memory for this element void dispose(Space& home);
/// Allocate memory from space static void* operator new(size_t s, Space& home); /// Placement new static void* operator new(size_t s, void* p); /// No-op (for exceptions) static void operator delete(void*); /// No-op (use dispose instead) static void operator delete(void*, Space&); /// No-op (use dispose instead) static void operator delete(void*, void*); //@} };
/** * \brief Domain information * * Provides fast access to minimum and maximum of the * entire domain and links to the first element * of a RangeList defining the domain. */ RangeList dom; /// Link the last element RangeList* _lst; /// Return first element of rangelist RangeList* fst(void) const; /// Set first element of rangelist void fst(RangeList* f); /// Return last element of rangelist RangeList* lst(void) const; /// Set last element of rangelist void lst(RangeList* l); /// Size of holes in the domain unsigned int holes;
protected: /// Constructor for cloning \a x IntVarImp(Space& home, IntVarImp& x); public: /// Initialize with range domain IntVarImp(Space& home, int min, int max); /// Initialize with domain specified by \a d IntVarImp(Space& home, const IntSet& d);
/// \name Value access //@{ /// Return minimum of domain int min(void) const; /// Return maximum of domain int max(void) const; /// Return assigned value (only if assigned) int val(void) const; /// Return median of domain (greatest element not greater than the median) GECODE_INT_EXPORT int med(void) const;
/// Return size (cardinality) of domain unsigned int size(void) const; /// Return width of domain (distance between maximum and minimum) unsigned int width(void) const; /// Return regret of domain minimum (distance to next larger value) unsigned int regret_min(void) const; /// Return regret of domain maximum (distance to next smaller value) unsigned int regret_max(void) const; //@}
private: /// Test whether \a n is contained in domain (full domain) GECODE_INT_EXPORT bool in_full(int n) const;
public: /// \name Domain tests //@{ /// Test whether domain is a range bool range(void) const; /// Test whether variable is assigned bool assigned(void) const;
/// Test whether \a n is contained in domain bool in(int n) const; /// Test whether \a n is contained in domain bool in(long long int n) const; //@}
protected: /// \name Range list access for iteration //@{ /// Return range list for forward iteration const RangeList* ranges_fwd(void) const; /// Return range list for backward iteration const RangeList* ranges_bwd(void) const; //@}
private: /// Test whether \a n is closer to the minimum or maximum bool closer_min(int b) const; /// \name Domain update by value (full domain) //@{ /// Restrict domain values to be less or equal than \a n GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n); /// Restrict domain values to be greater or equal than \a n GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n); /// Restrict domain values to be equal to current minimum of domain GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n); /// Restrict domain values to be different from \a n GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n); //@} public: /// \name Domain update by value //@{ /// Restrict domain values to be less or equal than \a n ModEvent lq(Space& home, int n); /// Restrict domain values to be less or equal than \a n ModEvent lq(Space& home, long long int n);
/// Restrict domain values to be greater or equal than \a n ModEvent gq(Space& home, int n); /// Restrict domain values to be greater or equal than \a n ModEvent gq(Space& home, long long int n);
/// Restrict domain values to be different from \a n ModEvent nq(Space& home, int n); /// Restrict domain values to be different from \a n ModEvent nq(Space& home, long long int n);
/// Restrict domain values to be equal to \a n ModEvent eq(Space& home, int n); /// Restrict domain values to be equal to \a n ModEvent eq(Space& home, long long int n); //@}
/** * \name Domain update by iterator * * Variable domains can be both updated by range and value iterators. * Value iterators do not need to be strict in that the same value * is allowed to occur more than once in the iterated sequence. * * The argument \a depends must be true, if the iterator * passed as argument depends on the variable implementation * on which the operation is invoked. In this case, the variable * implementation is only updated after the iterator has been * consumed. Otherwise, the domain might be updated concurrently * while following the iterator. * */ //@{ /// Replace domain by ranges described by \a i template<class I> ModEvent narrow_r(Space& home, I& i, bool depends=true); /// Intersect domain with ranges described by \a i template<class I> ModEvent inter_r(Space& home, I& i, bool depends=true); /// Remove from domain the ranges described by \a i template<class I> ModEvent minus_r(Space& home, I& i, bool depends=true); /// Replace domain by values described by \a i template<class I> ModEvent narrow_v(Space& home, I& i, bool depends=true); /// Intersect domain with values described by \a i template<class I> ModEvent inter_v(Space& home, I& i, bool depends=true); /// Remove from domain the values described by \a i template<class I> ModEvent minus_v(Space& home, I& i, bool depends=true); //@}
/// \name Dependencies //@{ /** * \brief Subscribe propagator \a p with propagation condition \a pc to variable * * 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). * */ GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /// Re-schedule propagator \a p GECODE_INT_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc); /** \brief Subscribe advisor \a a to variable * * The advisor \a a is only subscribed if \a assigned is false. * * If \a fail is true, the advisor \a a is also run when a variable * operation triggers failure. This feature is undocumented. * */ GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail); //@}
/// \name Variable implementation-dependent propagator support //@{ /// Translate modification event \a me to modification event delta for view static ModEventDelta med(ModEvent me); //@}
private: /// Return copy of not-yet copied variable GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home); public: /// \name Cloning //@{ /// Return copy of this variable IntVarImp* copy(Space& home); //@}
/// \name Delta information for advisors //@{ /// Return minimum value just pruned static int min(const Delta& d); /// Return maximum value just pruned static int max(const Delta& d); /// Return width of values just pruned static unsigned int width(const Delta& d); /// Test whether arbitrary values got pruned static bool any(const Delta& d); //@} };
/** * \brief Range iterator for ranges of integer variable implementation * */ class IntVarImpFwd { private: /// Previous range const IntVarImp::RangeList* p; /// Current range const IntVarImp::RangeList* c; public: /// \name Constructors and initialization //@{ /// Default constructor IntVarImpFwd(void); /// Initialize with ranges from variable implementation \a x IntVarImpFwd(const IntVarImp* x); /// Initialize with ranges from variable implementation \a x void init(const IntVarImp* x); //@}
/// \name Iteration control //@{ /// Test whether iterator is still at a range or done bool operator ()(void) const; /// Move iterator to next range (if possible) void operator ++(void); //@}
/// \name Range access //@{ /// Return smallest value of range int min(void) const; /// Return largest value of range int max(void) const; /// Return width of range (distance between minimum and maximum) unsigned int width(void) const; //@} };
/** * \brief Backward iterator for ranges of integer variable implementations * * Note that this iterator is not a range iterator as the ranges * are not iterated in increasing but in decreasing order. * */ class IntVarImpBwd { private: /// Next range const IntVarImp::RangeList* n; /// Current range const IntVarImp::RangeList* c; public: /// \name Constructors and initialization //@{ /// Default constructor IntVarImpBwd(void); /// Initialize with ranges from variable implementation \a x IntVarImpBwd(const IntVarImp* x); /// Initialize with ranges from variable implementation \a x void init(const IntVarImp* x); //@}
/// \name Iteration control //@{ /// Test whether iterator is still at a range or done bool operator ()(void) const; /// Move iterator to previous range (if possible) void operator ++(void); //@}
/// \name Range access //@{ /// Return smallest value of range int min(void) const; /// Return largest value of range int max(void) const; /// Return width of range (distance between minimum and maximum) unsigned int width(void) const; //@} };
}}
#include <gecode/int/var-imp/int.hpp>
namespace Gecode {
class IntVar; class BoolVar;}
namespace Gecode { namespace Int {
/// Type for status of a Boolean variable typedef unsigned int BoolStatus;
/** * \brief Boolean variable implementation * * \ingroup Other */ class BoolVarImp : public BoolVarImpBase { friend class ::Gecode::BoolVar; private: /** * \brief Domain information * * - The bit at position 0 corresponds to the minimum * - The bit at position 1 corresponds to the maximum * - Interpreted as an unsigned, that is: 0 represents * a variable assigned to 0, 3 represents a variable * assigned to 1, and 2 represents an unassigned variable. * - No other values are possible. */
GECODE_INT_EXPORT static BoolVarImp s_one; GECODE_INT_EXPORT static BoolVarImp s_zero;
/// Constructor for cloning \a x BoolVarImp(Space& home, BoolVarImp& x); /// Initialize static instance assigned to \a n BoolVarImp(int n); public: /// Initialize with range domain BoolVarImp(Space& home, int min, int max);
/// \name Domain status access //@{ /// How many bits does the status have static const int BITS = 2; /// Status of domain assigned to zero static const BoolStatus ZERO = 0; /// Status of domain assigned to one static const BoolStatus ONE = 3; /// Status of domain not yet assigned static const BoolStatus NONE = 2; /// Return current domain status BoolStatus status(void) const; //@}
/// \name Value access //@{ /// Return minimum of domain int min(void) const; /// Return maximum of domain int max(void) const; /// Return assigned value (only if assigned) int val(void) const; /// Return median of domain (greatest element not greater than the median) int med(void) const;
/// Return size (cardinality) of domain unsigned int size(void) const; /// Return width of domain (distance between maximum and minimum) unsigned int width(void) const; /// Return regret of domain minimum (distance to next larger value) unsigned int regret_min(void) const; /// Return regret of domain maximum (distance to next smaller value) unsigned int regret_max(void) const; //@}
/// \name Boolean domain tests //@{ /// Test whether variable is assigned to zero bool zero(void) const; /// Test whether variable is assigned to one bool one(void) const; /// Test whether variable is not yet assigned bool none(void) const; //@}
/// \name Domain tests //@{ /// Test whether domain is a range bool range(void) const; /// Test whether variable is assigned bool assigned(void) const;
/// Test whether \a n is contained in domain bool in(int n) const; /// Test whether \a n is contained in domain bool in(long long int n) const; //@}
/// \name Domain update by value //@{ /// Restrict domain values to be less or equal than \a n ModEvent lq(Space& home, int n); /// Restrict domain values to be less or equal than \a n ModEvent lq(Space& home, long long int n);
/// Restrict domain values to be greater or equal than \a n ModEvent gq(Space& home, int n); /// Restrict domain values to be greater or equal than \a n ModEvent gq(Space& home, long long int n);
/// Restrict domain values to be different from \a n ModEvent nq(Space& home, int n); /// Restrict domain values to be different from \a n ModEvent nq(Space& home, long long int n);
/// Restrict domain values to be equal to \a n ModEvent eq(Space& home, int n); /// Restrict domain values to be equal to \a n ModEvent eq(Space& home, long long int n); //@}
/** * \name Domain update by iterator * * Variable domains can be both updated by range and value iterators. * Value iterators do not need to be strict in that the same value * is allowed to occur more than once in the iterated sequence. * * The argument \a depends must be true, if the iterator * passed as argument depends on the variable implementation * on which the operation is invoked. In this case, the variable * implementation is only updated after the iterator has been * consumed. Otherwise, the domain might be updated concurrently * while following the iterator. * */ //@{ /// Replace domain by ranges described by \a i template<class I> ModEvent narrow_r(Space& home, I& i, bool depends=true); /// Intersect domain with ranges described by \a i template<class I> ModEvent inter_r(Space& home, I& i, bool depends=true); /// Remove from domain the ranges described by \a i template<class I> ModEvent minus_r(Space& home, I& i, bool depends=true); /// Replace domain by values described by \a i template<class I> ModEvent narrow_v(Space& home, I& i, bool depends=true); /// Intersect domain with values described by \a i template<class I> ModEvent inter_v(Space& home, I& i, bool depends=true); /// Remove from domain the values described by \a i template<class I> ModEvent minus_v(Space& home, I& i, bool depends=true); //@}
/// \name Boolean update operations //@{ /// Assign variable to zero ModEvent zero(Space& home); /// Assign variable to one ModEvent one(Space& home); /// Assign unassigned variable to zero GECODE_INT_EXPORT ModEvent zero_none(Space& home); /// Assign unassigned variable to one GECODE_INT_EXPORT ModEvent one_none(Space& home); //@}
public: /// \name Dependencies //@{ /** * \brief Subscribe propagator \a p to variable with propagation condition \a pc * * 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). * * The propagation condition \a pc can be a propagation condition * for integer variables, which will be mapped to PC_BOOL_VAL. */ GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /** * \brief Cancel subscription of propagator \a p with propagation condition \a pc * * The propagation condition \a pc can be a propagation condition * for integer variables, which will be mapped to PC_BOOL_VAL. */ void cancel(Space& home, Propagator& p, PropCond pc); /** \brief Subscribe advisor \a a to variable * * The advisor \a a is only subscribed if \a assigned is false. * * If \a fail is true, the advisor \a a is also run when a variable * operation triggers failure. This feature is undocumented. * */ GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail); /// Cancel subscription of advisor \a a void cancel(Space& home, Advisor& a, bool fail); //@}
/// \name Variable implementation-dependent propagator support //@{ /** * \brief Schedule propagator \a p with modification event \a me * * The modfication event \a me can be a modification event for * integer variables, however \a me will be ignored if it is not * ME_INT_VAL (or ME_BOOL_VAL). */ static void schedule(Space& home, Propagator& p, ModEvent me); /// Re-schedule propagator \a p GECODE_INT_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc); /// Translate modification event \a me to modification event delta for view static ModEventDelta med(ModEvent me); //@}
/// \name Support for delta information for advisors //@{ /// Return modification event static ModEvent modevent(const Delta& d); /// Return minimum value just pruned static int min(const Delta& d); /// Return maximum value just pruned static int max(const Delta& d); /// Return width of values just pruned static unsigned int width(const Delta& d); /// Test whether arbitrary values got pruned static bool any(const Delta& d); /// Test whether a variable has been assigned to zero static bool zero(const Delta& d); /// Test whether a variable has been assigned to one static bool one(const Delta& d); //@}
/// \name Cloning //@{ /// Return copy of this variable BoolVarImp* copy(Space& home); //@}
};
}}
#include <gecode/int/var-imp/bool.hpp>
// STATISTICS: int-var