Generated on Thu Mar 16 2017 03:24:22 for Gecode by doxygen 1.8.13
core.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Contributing authors:
9  * Filip Konvicka <filip.konvicka@logis.cz>
10  *
11  * Copyright:
12  * Christian Schulte, 2002
13  * Guido Tack, 2003
14  * Mikael Lagerkvist, 2006
15  * LOGIS, s.r.o., 2009
16  *
17  * Bugfixes provided by:
18  * Alexander Samoilov <alexander_samoilov@yahoo.com>
19  *
20  * Last modified:
21  * $Date: 2016-08-12 03:03:41 +0200 (Fri, 12 Aug 2016) $ by $Author: tack $
22  * $Revision: 15144 $
23  *
24  * This file is part of Gecode, the generic constraint
25  * development environment:
26  * http://www.gecode.org
27  *
28  * Permission is hereby granted, free of charge, to any person obtaining
29  * a copy of this software and associated documentation files (the
30  * "Software"), to deal in the Software without restriction, including
31  * without limitation the rights to use, copy, modify, merge, publish,
32  * distribute, sublicense, and/or sell copies of the Software, and to
33  * permit persons to whom the Software is furnished to do so, subject to
34  * the following conditions:
35  *
36  * The above copyright notice and this permission notice shall be
37  * included in all copies or substantial portions of the Software.
38  *
39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46  *
47  */
48 
49 #include <iostream>
50 
51 namespace Gecode {
52 
53  class Space;
54 
79  class SharedHandle {
80  public:
88  class Object : public HeapAllocated {
89  friend class Space;
90  friend class SharedHandle;
91  private:
93  Object* next;
95  Object* fwd;
97  unsigned int use_cnt;
98  public:
100  Object(void);
102  virtual Object* copy(void) const = 0;
104  virtual ~Object(void);
105  };
106  private:
108  Object* o;
110  void subscribe(void);
112  void cancel(void);
113  public:
115  SharedHandle(void);
119  SharedHandle(const SharedHandle& sh);
123  void update(Space& home, bool share, SharedHandle& sh);
125  ~SharedHandle(void);
126  protected:
128  SharedHandle::Object* object(void) const;
131  };
132 
141  typedef int ModEvent;
143 
145  const ModEvent ME_GEN_FAILED = -1;
147  const ModEvent ME_GEN_NONE = 0;
149  const ModEvent ME_GEN_ASSIGNED = 1;
150 
152  typedef int PropCond;
154  const PropCond PC_GEN_NONE = -1;
156  const PropCond PC_GEN_ASSIGNED = 0;
158 
169  typedef int ModEventDelta;
170 
171 }
172 
174 
175 namespace Gecode {
176 
179  public:
181  static const int idx_c = -1;
183  static const int idx_d = -1;
185  static const PropCond pc_max = PC_GEN_ASSIGNED;
187  static const int free_bits = 0;
189  static const int med_fst = 0;
191  static const int med_lst = 0;
193  static const int med_mask = 0;
195  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
197  static bool med_update(ModEventDelta& med, ModEvent me);
198  };
199 
202  GECODE_NEVER; return 0;
203  }
204  forceinline bool
206  GECODE_NEVER; return false;
207  }
208 
209 
210  /*
211  * These are the classes of interest
212  *
213  */
214  class ActorLink;
215  class Actor;
216  class Propagator;
217  class SubscribedPropagators;
218  class LocalObject;
219  class Advisor;
220  class AFC;
221  class Brancher;
222  class Group;
223  class PropagatorGroup;
224  class BrancherGroup;
225  class PostInfo;
226  class ExecInfo;
227 
228  template<class A> class Council;
229  template<class A> class Advisors;
230  template<class VIC> class VarImp;
231 
232 
233  /*
234  * Variable implementations
235  *
236  */
237 
245  class VarImpBase {};
246 
254  public:
256  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
259  };
260 
267  template<class VarImp>
269  public:
271  VarImpDisposer(void);
273  virtual void dispose(Space& home, VarImpBase* x);
274  };
275 
277  class Delta {
278  template<class VIC> friend class VarImp;
279  private:
281  ModEvent me;
282  };
283 
291  template<class VIC>
292  class VarImp : public VarImpBase {
293  friend class Space;
294  friend class Propagator;
295  template<class VarImp> friend class VarImpDisposer;
296  friend class SubscribedPropagators;
297  private:
298  union {
316  } b;
317 
319  static const int idx_c = VIC::idx_c;
321  static const int idx_d = VIC::idx_d;
323  static const int free_bits = VIC::free_bits;
325  unsigned int entries;
327  unsigned int free_and_bits;
329  static const Gecode::PropCond pc_max = VIC::pc_max;
330 
331  union {
342  unsigned int idx[pc_max+1];
345  } u;
346 
348  ActorLink** actor(PropCond pc);
350  ActorLink** actorNonZero(PropCond pc);
352  unsigned int& idx(PropCond pc);
354  unsigned int idx(PropCond pc) const;
355 
362  void update(VarImp* x, ActorLink**& sub);
369  static void update(Space& home, ActorLink**& sub);
370 
372  void enter(Space& home, Propagator* p, PropCond pc);
374  void enter(Space& home, Advisor* a);
376  void resize(Space& home);
378  void remove(Space& home, Propagator* p, PropCond pc);
380  void remove(Space& home, Advisor* a);
381 
382 
383  protected:
385  void cancel(Space& home);
391  bool advise(Space& home, ModEvent me, Delta& d);
392 #ifdef GECODE_HAS_VAR_DISPOSE
393  static VarImp<VIC>* vars_d(Space& home);
396  static void vars_d(Space& home, VarImp<VIC>* x);
397 #endif
398 
399  public:
401  VarImp(Space& home);
403  VarImp(void);
404 
406 
407 
419  void subscribe(Space& home, Propagator& p, PropCond pc,
420  bool assigned, ModEvent me, bool schedule);
426  void cancel(Space& home, Propagator& p, PropCond pc,
427  bool assigned);
433  void subscribe(Space& home, Advisor& a, bool assigned);
439  void cancel(Space& home, Advisor& a, bool assigned);
440 
447  unsigned int degree(void) const;
454  double afc(const Space& home) const;
456 
458 
459  VarImp(Space& home, bool share, VarImp& x);
462  bool copied(void) const;
464  VarImp* forward(void) const;
466  VarImp* next(void) const;
468 
470 
471 
478  static void schedule(Space& home, Propagator& p, ModEvent me,
479  bool force = false);
487  static void reschedule(Space& home, Propagator& p, PropCond pc,
488  bool assigned, ModEvent me);
490  static ModEvent me(const ModEventDelta& med);
492  static ModEventDelta med(ModEvent me);
494  static ModEvent me_combine(ModEvent me1, ModEvent me2);
496 
498 
499  static ModEvent modevent(const Delta& d);
502 
504 
505  unsigned int bits(void) const;
508  unsigned int& bits(void);
510 
511  protected:
513  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
514 
515  public:
517 
518  static void* operator new(size_t,Space&);
521  static void operator delete(void*,Space&);
523  static void operator delete(void*);
525  };
526 
527 
536  enum ExecStatus {
538  ES_FAILED = -1,
539  ES_NOFIX = 0,
540  ES_OK = 0,
541  ES_FIX = 1,
544  };
545 
550  class PropCost {
551  friend class Space;
552  public:
554  enum ActualCost {
555  AC_RECORD = 0,
556  AC_CRAZY_LO = 1,
557  AC_CRAZY_HI = 1,
558  AC_CUBIC_LO = 1,
559  AC_CUBIC_HI = 1,
560  AC_QUADRATIC_LO = 2,
561  AC_QUADRATIC_HI = 2,
562  AC_LINEAR_HI = 3,
563  AC_LINEAR_LO = 4,
564  AC_TERNARY_HI = 4,
565  AC_BINARY_HI = 5,
566  AC_TERNARY_LO = 5,
567  AC_BINARY_LO = 6,
568  AC_UNARY_LO = 6,
569  AC_UNARY_HI = 6,
570  AC_MAX = 6
571  };
574  public:
576  enum Mod {
577  LO,
578  HI
579  };
580  private:
582  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
584  PropCost(ActualCost ac);
585  public:
587  static PropCost record(void);
589  static PropCost crazy(PropCost::Mod m, unsigned int n);
591  static PropCost crazy(PropCost::Mod m, int n);
593  static PropCost cubic(PropCost::Mod m, unsigned int n);
595  static PropCost cubic(PropCost::Mod m, int n);
597  static PropCost quadratic(PropCost::Mod m, unsigned int n);
599  static PropCost quadratic(PropCost::Mod m, int n);
601  static PropCost linear(PropCost::Mod m, unsigned int n);
603  static PropCost linear(PropCost::Mod m, int n);
605  static PropCost ternary(PropCost::Mod m);
607  static PropCost binary(PropCost::Mod m);
609  static PropCost unary(PropCost::Mod m);
610  };
611 
612 
626  AP_DISPOSE = (1 << 0),
632  AP_WEAKLY = (1 << 1)
633  };
634 
635 
643  class ActorLink {
644  friend class Actor;
645  friend class Propagator;
646  friend class Advisor;
647  friend class Brancher;
648  friend class LocalObject;
649  friend class Space;
650  template<class VIC> friend class VarImp;
651  private:
652  ActorLink* _next; ActorLink* _prev;
653  public:
655  ActorLink* prev(void) const; void prev(ActorLink*);
657  ActorLink* next(void) const; void next(ActorLink*);
658  ActorLink** next_ref(void);
660 
662  void init(void);
664  void unlink(void);
666  void head(ActorLink* al);
668  void tail(ActorLink* al);
670  bool empty(void) const;
672  template<class T> static ActorLink* cast(T* a);
674  template<class T> static const ActorLink* cast(const T* a);
675  };
676 
677 
683  friend class ActorLink;
684  friend class Space;
685  friend class Propagator;
686  friend class Advisor;
687  friend class Brancher;
688  friend class LocalObject;
689  template<class VIC> friend class VarImp;
690  template<class A> friend class Council;
691  private:
693  static Actor* cast(ActorLink* al);
695  static const Actor* cast(const ActorLink* al);
697  GECODE_KERNEL_EXPORT static Actor* sentinel;
698  public:
700  virtual Actor* copy(Space& home, bool share) = 0;
701 
703 
706  virtual size_t dispose(Space& home);
708  static void* operator new(size_t s, Space& home);
710  static void operator delete(void* p, Space& home);
712  public:
714  GECODE_KERNEL_EXPORT virtual ~Actor(void);
716  static void* operator new(size_t s);
718  static void operator delete(void* p);
719  };
720 
721  class Home;
722 
727  class Group {
728  friend class Home;
729  friend class Propagator;
730  friend class Brancher;
731  friend class ExecInfo;
732  protected:
734  static const unsigned int GROUPID_ALL = 0U;
736  static const unsigned int GROUPID_DEF = 1U;
738  static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
740  unsigned int gid;
743  static unsigned int next;
748  Group(unsigned int gid0);
749  public:
751 
754  Group(void);
756  Group(const Group& g);
758  Group& operator =(const Group& g);
760  unsigned int id(void) const;
762  bool in(Group a) const;
764  bool in(void) const;
768  static Group all;
771  static Group def;
772  };
773 
778  class PropagatorGroup : public Group {
779  friend class Propagator;
780  friend class ExecInfo;
781  protected:
783  PropagatorGroup(unsigned int gid);
784  public:
786 
787  PropagatorGroup(void);
794  Home operator ()(Space& home);
796 
800  PropagatorGroup& move(Space& home, PropagatorGroup g);
802  PropagatorGroup& move(Space& home, Propagator& p);
810  PropagatorGroup& move(Space& home, unsigned int id);
812 
814  bool operator ==(PropagatorGroup g) const;
817  bool operator !=(PropagatorGroup g) const;
820  unsigned int size(Space& home) const;
823  void kill(Space& home);
826  void disable(Space& home);
834  void enable(Space& home, bool s=true);
842  };
843 
848  class BrancherGroup : public Group {
849  friend class Brancher;
850  protected:
852  BrancherGroup(unsigned int gid);
853  public:
855 
856  BrancherGroup(void);
859  BrancherGroup(const BrancherGroup& g);
863  Home operator ()(Space& home);
865 
869  BrancherGroup& move(Space& home, BrancherGroup g);
871  BrancherGroup& move(Space& home, Brancher& b);
879  BrancherGroup& move(Space& home, unsigned int id);
881 
883  bool operator ==(BrancherGroup g) const;
886  bool operator !=(BrancherGroup g) const;
889  unsigned int size(Space& home) const;
892  void kill(Space& home);
900  };
901 
905  class Home {
906  friend class PostInfo;
907  protected:
916  public:
918 
919  Home(Space& s, Propagator* p=NULL,
924  Home& operator =(const Home& h);
926  operator Space&(void);
928 
930  Home operator ()(Propagator& p);
933  Home operator ()(PropagatorGroup pg);
935  Home operator ()(BrancherGroup bg);
937  Propagator* propagator(void) const;
939  PropagatorGroup propagatorgroup(void) const;
941  BrancherGroup branchergroup(void) const;
943 
945  bool failed(void) const;
948  void fail(void);
950  void notice(Actor& a, ActorProperty p, bool duplicate=false);
952  };
953 
957  class ExecInfo {
958  friend class Space;
959  friend class PostInfo;
960  public:
962  enum What {
964  PROPAGATOR = 0,
966  BRANCHER = 1,
968  POST = 2,
970  OTHER = 3
971  };
972  protected:
974  ptrdiff_t who;
976  void propagator(Propagator& p);
978  void brancher(Brancher& b);
980  void post(PropagatorGroup g);
982  void other(void);
983  public:
985  What what(void) const;
987  const Propagator& propagator(void) const;
989  const Brancher& brancher(void) const;
991  PropagatorGroup post(void) const;
992  };
993 
997  class PostInfo {
998  protected:
1001  public:
1003  PostInfo(Home home);
1005  ~PostInfo(void);
1006  };
1007 
1013  friend class ActorLink;
1014  friend class Space;
1015  template<class VIC> friend class VarImp;
1016  friend class Advisor;
1017  template<class A> friend class Council;
1019  private:
1020  union {
1024  size_t size;
1027  } u;
1029  void* gpi_disabled;
1031  static Propagator* cast(ActorLink* al);
1033  static const Propagator* cast(const ActorLink* al);
1034  protected:
1036  Propagator(Home home);
1038  Propagator(Space& home, bool share, Propagator& p);
1040  Propagator* fwd(void) const;
1042  GPI::Info& gpi(void);
1043 
1044  public:
1046 
1047 
1055  virtual void reschedule(Space& home) = 0;
1079  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1081  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1089  ModEventDelta modeventdelta(void) const;
1126  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1128 
1130  double afc(const Space& home) const;
1133 
1135  unsigned int id(void) const;
1138  PropagatorGroup group(void) const;
1140  void group(PropagatorGroup g);
1142  bool disabled(void) const;
1144  void kill(Space& home);
1146  void disable(void);
1148  void enable(void);
1150  };
1151 
1152 
1160  template<class A>
1161  class Council {
1162  friend class Advisor;
1163  friend class Advisors<A>;
1164  private:
1166  mutable ActorLink* advisors;
1167  public:
1169  Council(void);
1171  Council(Space& home);
1173  bool empty(void) const;
1175  void update(Space& home, bool share, Council<A>& c);
1177  void dispose(Space& home);
1178  };
1179 
1180 
1185  template<class A>
1186  class Advisors {
1187  private:
1189  ActorLink* a;
1190  public:
1192  Advisors(const Council<A>& c);
1194  bool operator ()(void) const;
1196  void operator ++(void);
1198  A& advisor(void) const;
1199  };
1200 
1201 
1212  class Advisor : private ActorLink {
1213  template<class VIC> friend class VarImp;
1214  template<class A> friend class Council;
1215  template<class A> friend class Advisors;
1217  private:
1219  bool disposed(void) const;
1221  static Advisor* cast(ActorLink* al);
1223  static const Advisor* cast(const ActorLink* al);
1224  protected:
1226  Propagator& propagator(void) const;
1227  public:
1229  template<class A>
1230  Advisor(Space& home, Propagator& p, Council<A>& c);
1232  Advisor(Space& home, bool share, Advisor& a);
1234  const ExecInfo& operator ()(const Space& home) const;
1235 
1237 
1238  template<class A>
1240  void dispose(Space& home, Council<A>& c);
1242  static void* operator new(size_t s, Space& home);
1244  static void operator delete(void* p, Space& home);
1246  private:
1247 #ifndef __GNUC__
1248  static void operator delete(void* p);
1250 #endif
1251  static void* operator new(size_t s);
1253  };
1254 
1255 
1261  private:
1263  void* nl;
1264  public:
1266  enum Status {
1269  NONE
1270  };
1272  NGL(void);
1274  NGL(Space& home);
1276  NGL(Space& home, bool share, NGL& ngl);
1278  virtual void subscribe(Space& home, Propagator& p) = 0;
1280  virtual void cancel(Space& home, Propagator& p) = 0;
1282  virtual void reschedule(Space& home, Propagator& p) = 0;
1284  virtual NGL::Status status(const Space& home) const = 0;
1286  virtual ExecStatus prune(Space& home) = 0;
1288  virtual NGL* copy(Space& home, bool share) = 0;
1291  virtual bool notice(void) const;
1293  virtual size_t dispose(Space& home);
1295 
1296  bool leaf(void) const;
1299  NGL* next(void) const;
1301  void leaf(bool l);
1303  void next(NGL* n);
1305  NGL* add(NGL* n, bool l);
1307 
1309  static void* operator new(size_t s, Space& home);
1312  static void operator delete(void* s, Space& home);
1314  static void operator delete(void* p);
1316  public:
1318  GECODE_KERNEL_EXPORT virtual ~NGL(void);
1320  static void* operator new(size_t s);
1321  };
1322 
1333  friend class Space;
1334  private:
1335  unsigned int bid;
1336  unsigned int alt;
1337 
1339  unsigned int id(void) const;
1340  protected:
1342  Choice(const Brancher& b, const unsigned int a);
1343  public:
1345  unsigned int alternatives(void) const;
1347  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1349  virtual size_t size(void) const = 0;
1352  virtual void archive(Archive& e) const;
1353  };
1354 
1365  friend class ActorLink;
1366  friend class Space;
1367  friend class Choice;
1368  private:
1370  unsigned int bid;
1372  unsigned int gid;
1374  static Brancher* cast(ActorLink* al);
1376  static const Brancher* cast(const ActorLink* al);
1377  protected:
1379  Brancher(Home home);
1381  Brancher(Space& home, bool share, Brancher& b);
1382  public:
1384 
1385 
1393  virtual bool status(const Space& home) const = 0;
1401  virtual const Choice* choice(Space& home) = 0;
1403  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1410  virtual ExecStatus commit(Space& home, const Choice& c,
1411  unsigned int a) = 0;
1426  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1437  virtual void print(const Space& home, const Choice& c, unsigned int a,
1438  std::ostream& o) const;
1440 
1442  unsigned int id(void) const;
1445  BrancherGroup group(void) const;
1447  void group(BrancherGroup g);
1449  void kill(Space& home);
1451  };
1452 
1460  class LocalObject : public Actor {
1461  friend class ActorLink;
1462  friend class Space;
1463  friend class LocalHandle;
1464  protected:
1466  LocalObject(Home home);
1468  LocalObject(Space& home, bool share, LocalObject& l);
1470  static LocalObject* cast(ActorLink* al);
1472  static const LocalObject* cast(const ActorLink* al);
1473  private:
1475  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1476  public:
1478  LocalObject* fwd(Space& home, bool share);
1479  };
1480 
1487  class LocalHandle {
1488  private:
1490  LocalObject* o;
1491  protected:
1493  LocalHandle(void);
1495  LocalHandle(LocalObject* lo);
1497  LocalHandle(const LocalHandle& lh);
1498  public:
1500  LocalHandle& operator =(const LocalHandle& lh);
1502  void update(Space& home, bool share, LocalHandle& lh);
1504  ~LocalHandle(void);
1505  protected:
1507  LocalObject* object(void) const;
1509  void object(LocalObject* n);
1510  };
1511 
1512 
1518  protected:
1520  unsigned long int n;
1521  public:
1523  NoGoods(void);
1526  virtual void post(Space& home) const;
1528  unsigned long int ng(void) const;
1530  void ng(unsigned long int n);
1532  virtual ~NoGoods(void);
1535  static NoGoods eng;
1536  };
1537 
1543  public:
1545  enum Type {
1549  PORTFOLIO
1550  };
1551  protected:
1553  const Type t;
1555 
1556  const unsigned long int r;
1559  const unsigned long int s;
1561  const unsigned long int f;
1563  const Space* l;
1565  const NoGoods& ng;
1567 
1569  const unsigned int a;
1572  public:
1574 
1575  MetaInfo(unsigned long int r,
1577  unsigned long int s,
1578  unsigned long int f,
1579  const Space* l,
1580  NoGoods& ng);
1582  MetaInfo(unsigned int a);
1584  Type type(void) const;
1587 
1588  unsigned long int restart(void) const;
1591  unsigned long int solution(void) const;
1593  unsigned long int fail(void) const;
1595  const Space* last(void) const;
1597  const NoGoods& nogoods(void) const;
1599 
1601  unsigned int asset(void) const;
1604  };
1605 
1614  };
1615 
1621  public:
1623  unsigned long int propagate;
1625  bool wmp;
1627  StatusStatistics(void);
1629  void reset(void);
1633  StatusStatistics& operator +=(const StatusStatistics& s);
1634  };
1635 
1641  public:
1643  CloneStatistics(void);
1645  void reset(void);
1649  CloneStatistics& operator +=(const CloneStatistics& s);
1650  };
1651 
1657  public:
1659  CommitStatistics(void);
1661  void reset(void);
1665  CommitStatistics& operator +=(const CommitStatistics& s);
1666  };
1667 
1668 
1673  friend class Actor;
1674  friend class Propagator;
1675  friend class PropagatorGroup;
1676  friend class Propagators;
1677  friend class Brancher;
1678  friend class BrancherGroup;
1679  friend class Branchers;
1680  friend class Advisor;
1681  template <class A> friend class Council;
1682  template<class VIC> friend class VarImp;
1683  template<class VarImp> friend class VarImpDisposer;
1684  friend class SharedHandle;
1685  friend class LocalObject;
1686  friend class Region;
1687  friend class AFC;
1688  friend class PostInfo;
1689  private:
1691  SharedMemory* sm;
1693  MemoryManager mm;
1695  GPI gpi;
1697  ActorLink pl;
1699  ActorLink bl;
1705  Brancher* b_status;
1717  Brancher* b_commit;
1719  Brancher* brancher(unsigned int id);
1720 
1722  void kill(Brancher& b);
1724  void kill(Propagator& p);
1725 
1728  void kill_brancher(unsigned int id);
1729 
1731  static const unsigned reserved_bid = 0U;
1732 
1733  union {
1735  struct {
1752  unsigned int bid;
1754  unsigned int n_sub;
1757  } p;
1759  struct {
1768  } c;
1769  } pc;
1771  void enqueue(Propagator* p);
1776 #ifdef GECODE_HAS_VAR_DISPOSE
1780  VarImpBase* _vars_d[AllVarConf::idx_d];
1782  template<class VIC> VarImpBase* vars_d(void) const;
1784  template<class VIC> void vars_d(VarImpBase* x);
1785 #endif
1786  void update(ActorLink** sub);
1789 
1791  Actor** d_fst;
1793  Actor** d_cur;
1795  Actor** d_lst;
1796 
1808  unsigned int _wmp_afc;
1810  void afc_enable(void);
1812  bool afc_enabled(void) const;
1814  void wmp(unsigned int n);
1816  unsigned int wmp(void) const;
1817 
1819  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1821  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1823  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1824 
1846  GECODE_KERNEL_EXPORT Space* _clone(bool share_data=true,
1847  bool share_info=true);
1848 
1882  void _commit(const Choice& c, unsigned int a);
1883 
1915  void _trycommit(const Choice& c, unsigned int a);
1916 
1917  public:
1923  Space(void);
1936  Space(bool share, Space& s);
1942  virtual ~Space(void);
1949  virtual Space* copy(bool share) = 0;
1960  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1985  virtual bool master(const MetaInfo& mi);
2012  virtual bool slave(const MetaInfo& mi);
2013 
2014  /*
2015  * Member functions for search engines
2016  *
2017  */
2018 
2031  SpaceStatus status(StatusStatistics& stat=unused_status);
2032 
2065  const Choice* choice(void);
2066 
2077  const Choice* choice(Archive& e) const;
2078 
2102  Space* clone(bool share_data=true,
2103  bool share_info=true,
2104  CloneStatistics& stat=unused_clone) const;
2105 
2140  void commit(const Choice& c, unsigned int a,
2141  CommitStatistics& stat=unused_commit);
2174  void trycommit(const Choice& c, unsigned int a,
2175  CommitStatistics& stat=unused_commit);
2195  NGL* ngl(const Choice& c, unsigned int a);
2196 
2212  void print(const Choice& c, unsigned int a, std::ostream& o) const;
2213 
2223  void notice(Actor& a, ActorProperty p, bool duplicate=false);
2232  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2233 
2234 
2245  ExecStatus ES_SUBSUMED(Propagator& p);
2260  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
2271  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2282  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2283 
2294  template<class A>
2295  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
2306  template<class A>
2307  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
2319  template<class A>
2320  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
2321 
2329  void fail(void);
2338  bool failed(void) const;
2343  bool stable(void) const;
2344 
2346 
2347  Home operator ()(Propagator& p);
2350  Home operator ()(PropagatorGroup pg);
2352  Home operator ()(BrancherGroup bg);
2354 
2366  template<class T>
2367  T* alloc(long unsigned int n);
2374  template<class T>
2375  T* alloc(long int n);
2382  template<class T>
2383  T* alloc(unsigned int n);
2390  template<class T>
2391  T* alloc(int n);
2401  template<class T>
2402  void free(T* b, long unsigned int n);
2412  template<class T>
2413  void free(T* b, long int n);
2423  template<class T>
2424  void free(T* b, unsigned int n);
2434  template<class T>
2435  void free(T* b, int n);
2447  template<class T>
2448  T* realloc(T* b, long unsigned int n, long unsigned int m);
2460  template<class T>
2461  T* realloc(T* b, long int n, long int m);
2473  template<class T>
2474  T* realloc(T* b, unsigned int n, unsigned int m);
2486  template<class T>
2487  T* realloc(T* b, int n, int m);
2495  template<class T>
2496  T** realloc(T** b, long unsigned int n, long unsigned int m);
2504  template<class T>
2505  T** realloc(T** b, long int n, long int m);
2513  template<class T>
2514  T** realloc(T** b, unsigned int n, unsigned int m);
2522  template<class T>
2523  T** realloc(T** b, int n, int m);
2525  void* ralloc(size_t s);
2527  void rfree(void* p, size_t s);
2529  void* rrealloc(void* b, size_t n, size_t m);
2531  template<size_t> void* fl_alloc(void);
2537  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2546  GECODE_KERNEL_EXPORT void flush(void);
2548 
2550 
2553  template<class T>
2554  T& construct(void);
2560  template<class T, typename A1>
2561  T& construct(A1 const& a1);
2567  template<class T, typename A1, typename A2>
2568  T& construct(A1 const& a1, A2 const& a2);
2574  template<class T, typename A1, typename A2, typename A3>
2575  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2581  template<class T, typename A1, typename A2, typename A3, typename A4>
2582  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2588  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2589  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2591 
2593 
2596  void afc_decay(double d);
2598  double afc_decay(void) const;
2601  void afc_set(double a);
2603 
2604  private:
2610  class Propagators {
2611  private:
2613  Space& home;
2615  ActorLink* q;
2617  ActorLink* c;
2619  ActorLink* e;
2620  public:
2622  Propagators(Space& home);
2624  bool operator ()(void) const;
2626  void operator ++(void);
2628  Propagator& propagator(void) const;
2629  };
2635  class ScheduledPropagators {
2636  private:
2638  Space& home;
2640  ActorLink* q;
2642  ActorLink* c;
2644  ActorLink* e;
2645  public:
2647  ScheduledPropagators(Space& home);
2649  bool operator ()(void) const;
2651  void operator ++(void);
2653  Propagator& propagator(void) const;
2654  };
2660  class IdlePropagators {
2661  private:
2663  ActorLink* c;
2665  ActorLink* e;
2666  public:
2668  IdlePropagators(Space& home);
2670  bool operator ()(void) const;
2672  void operator ++(void);
2674  Propagator& propagator(void) const;
2675  };
2681  class Branchers {
2682  private:
2684  ActorLink* c;
2686  ActorLink* e;
2687  public:
2689  Branchers(Space& home);
2691  bool operator ()(void) const;
2693  void operator ++(void);
2695  Brancher& brancher(void) const;
2696  };
2697  };
2698 
2700  class Propagators {
2701  private:
2703  Space::Propagators ps;
2705  PropagatorGroup g;
2706  public:
2708  Propagators(Space& home, PropagatorGroup g);
2710  bool operator ()(void) const;
2712  void operator ++(void);
2714  const Propagator& propagator(void) const;
2715  };
2716 
2718  class Branchers {
2719  private:
2721  Space::Branchers bs;
2723  BrancherGroup g;
2724  public:
2726  Branchers(Space& home, BrancherGroup g);
2728  bool operator ()(void) const;
2730  void operator ++(void);
2732  const Brancher& brancher(void) const;
2733  };
2734 
2735 
2736 
2737 
2738  /*
2739  * Memory management
2740  *
2741  */
2742 
2743  // Space allocation: general space heaps and free lists
2744  forceinline void*
2745  Space::ralloc(size_t s) {
2746  return mm.alloc(sm,s);
2747  }
2748  forceinline void
2749  Space::rfree(void* p, size_t s) {
2750  return mm.reuse(p,s);
2751  }
2752  forceinline void*
2753  Space::rrealloc(void* _b, size_t n, size_t m) {
2754  char* b = static_cast<char*>(_b);
2755  if (n < m) {
2756  char* p = static_cast<char*>(ralloc(m));
2757  memcpy(p,b,n);
2758  rfree(b,n);
2759  return p;
2760  } else {
2761  rfree(b+m,m-n);
2762  return b;
2763  }
2764  }
2765 
2766  template<size_t s>
2767  forceinline void*
2769  return mm.template fl_alloc<s>(sm);
2770  }
2771  template<size_t s>
2772  forceinline void
2774  mm.template fl_dispose<s>(f,l);
2775  }
2776 
2777  /*
2778  * Typed allocation routines
2779  *
2780  */
2781  template<class T>
2782  forceinline T*
2783  Space::alloc(long unsigned int n) {
2784  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2785  for (long unsigned int i=n; i--; )
2786  (void) new (p+i) T();
2787  return p;
2788  }
2789  template<class T>
2790  forceinline T*
2791  Space::alloc(long int n) {
2792  assert(n >= 0);
2793  return alloc<T>(static_cast<long unsigned int>(n));
2794  }
2795  template<class T>
2796  forceinline T*
2797  Space::alloc(unsigned int n) {
2798  return alloc<T>(static_cast<long unsigned int>(n));
2799  }
2800  template<class T>
2801  forceinline T*
2803  assert(n >= 0);
2804  return alloc<T>(static_cast<long unsigned int>(n));
2805  }
2806 
2807  template<class T>
2808  forceinline void
2809  Space::free(T* b, long unsigned int n) {
2810  for (long unsigned int i=n; i--; )
2811  b[i].~T();
2812  rfree(b,n*sizeof(T));
2813  }
2814  template<class T>
2815  forceinline void
2816  Space::free(T* b, long int n) {
2817  assert(n >= 0);
2818  free<T>(b,static_cast<long unsigned int>(n));
2819  }
2820  template<class T>
2821  forceinline void
2822  Space::free(T* b, unsigned int n) {
2823  free<T>(b,static_cast<long unsigned int>(n));
2824  }
2825  template<class T>
2826  forceinline void
2827  Space::free(T* b, int n) {
2828  assert(n >= 0);
2829  free<T>(b,static_cast<long unsigned int>(n));
2830  }
2831 
2832  template<class T>
2833  forceinline T*
2834  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2835  if (n < m) {
2836  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2837  for (long unsigned int i=n; i--; )
2838  (void) new (p+i) T(b[i]);
2839  for (long unsigned int i=n; i<m; i++)
2840  (void) new (p+i) T();
2841  free<T>(b,n);
2842  return p;
2843  } else {
2844  free<T>(b+m,m-n);
2845  return b;
2846  }
2847  }
2848  template<class T>
2849  forceinline T*
2850  Space::realloc(T* b, long int n, long int m) {
2851  assert((n >= 0) && (m >= 0));
2852  return realloc<T>(b,static_cast<long unsigned int>(n),
2853  static_cast<long unsigned int>(m));
2854  }
2855  template<class T>
2856  forceinline T*
2857  Space::realloc(T* b, unsigned int n, unsigned int m) {
2858  return realloc<T>(b,static_cast<long unsigned int>(n),
2859  static_cast<long unsigned int>(m));
2860  }
2861  template<class T>
2862  forceinline T*
2863  Space::realloc(T* b, int n, int m) {
2864  assert((n >= 0) && (m >= 0));
2865  return realloc<T>(b,static_cast<long unsigned int>(n),
2866  static_cast<long unsigned int>(m));
2867  }
2868 
2869 #define GECODE_KERNEL_REALLOC(T) \
2870  template<> \
2871  forceinline T* \
2872  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2873  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2874  } \
2875  template<> \
2876  forceinline T* \
2877  Space::realloc<T>(T* b, long int n, long int m) { \
2878  assert((n >= 0) && (m >= 0)); \
2879  return realloc<T>(b,static_cast<long unsigned int>(n), \
2880  static_cast<long unsigned int>(m)); \
2881  } \
2882  template<> \
2883  forceinline T* \
2884  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2885  return realloc<T>(b,static_cast<long unsigned int>(n), \
2886  static_cast<long unsigned int>(m)); \
2887  } \
2888  template<> \
2889  forceinline T* \
2890  Space::realloc<T>(T* b, int n, int m) { \
2891  assert((n >= 0) && (m >= 0)); \
2892  return realloc<T>(b,static_cast<long unsigned int>(n), \
2893  static_cast<long unsigned int>(m)); \
2894  }
2895 
2896  GECODE_KERNEL_REALLOC(bool)
2897  GECODE_KERNEL_REALLOC(signed char)
2898  GECODE_KERNEL_REALLOC(unsigned char)
2899  GECODE_KERNEL_REALLOC(signed short int)
2900  GECODE_KERNEL_REALLOC(unsigned short int)
2901  GECODE_KERNEL_REALLOC(signed int)
2902  GECODE_KERNEL_REALLOC(unsigned int)
2903  GECODE_KERNEL_REALLOC(signed long int)
2904  GECODE_KERNEL_REALLOC(unsigned long int)
2905  GECODE_KERNEL_REALLOC(float)
2906  GECODE_KERNEL_REALLOC(double)
2907 
2908 #undef GECODE_KERNEL_REALLOC
2909 
2910  template<class T>
2911  forceinline T**
2912  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2913  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2914  }
2915  template<class T>
2916  forceinline T**
2917  Space::realloc(T** b, long int n, long int m) {
2918  assert((n >= 0) && (m >= 0));
2919  return realloc<T*>(b,static_cast<long unsigned int>(n),
2920  static_cast<long unsigned int>(m));
2921  }
2922  template<class T>
2923  forceinline T**
2924  Space::realloc(T** b, unsigned int n, unsigned int m) {
2925  return realloc<T*>(b,static_cast<long unsigned int>(n),
2926  static_cast<long unsigned int>(m));
2927  }
2928  template<class T>
2929  forceinline T**
2930  Space::realloc(T** b, int n, int m) {
2931  assert((n >= 0) && (m >= 0));
2932  return realloc<T*>(b,static_cast<long unsigned int>(n),
2933  static_cast<long unsigned int>(m));
2934  }
2935 
2936 
2937 #ifdef GECODE_HAS_VAR_DISPOSE
2938  template<class VIC>
2940  Space::vars_d(void) const {
2941  return _vars_d[VIC::idx_d];
2942  }
2943  template<class VIC>
2944  forceinline void
2945  Space::vars_d(VarImpBase* x) {
2946  _vars_d[VIC::idx_d] = x;
2947  }
2948 #endif
2949 
2950  // Space allocated entities: Actors, variable implementations, and advisors
2951  forceinline void
2952  Actor::operator delete(void*) {}
2953  forceinline void
2954  Actor::operator delete(void*, Space&) {}
2955  forceinline void*
2956  Actor::operator new(size_t s, Space& home) {
2957  return home.ralloc(s);
2958  }
2959 
2960  template<class VIC>
2961  forceinline void
2962  VarImp<VIC>::operator delete(void*) {}
2963  template<class VIC>
2964  forceinline void
2965  VarImp<VIC>::operator delete(void*, Space&) {}
2966  template<class VIC>
2967  forceinline void*
2968  VarImp<VIC>::operator new(size_t s, Space& home) {
2969  return home.ralloc(s);
2970  }
2971 
2972 #ifndef __GNUC__
2973  forceinline void
2974  Advisor::operator delete(void*) {}
2975 #endif
2976  forceinline void
2977  Advisor::operator delete(void*, Space&) {}
2978  forceinline void*
2979  Advisor::operator new(size_t s, Space& home) {
2980  return home.ralloc(s);
2981  }
2982 
2983  forceinline void
2984  NGL::operator delete(void*) {}
2985  forceinline void
2986  NGL::operator delete(void*, Space&) {}
2987  forceinline void*
2988  NGL::operator new(size_t s, Space& home) {
2989  return home.ralloc(s);
2990  }
2991 
2992  /*
2993  * Shared objects and handles
2994  *
2995  */
2996  forceinline
2998  : next(NULL), fwd(NULL), use_cnt(0) {}
2999  forceinline
3001  assert(use_cnt == 0);
3002  }
3003 
3005  SharedHandle::object(void) const {
3006  return o;
3007  }
3008  forceinline void
3009  SharedHandle::subscribe(void) {
3010  if (o != NULL) o->use_cnt++;
3011  }
3012  forceinline void
3013  SharedHandle::cancel(void) {
3014  if ((o != NULL) && (--o->use_cnt == 0))
3015  delete o;
3016  o=NULL;
3017  }
3018  forceinline void
3020  if (n != o) {
3021  cancel(); o=n; subscribe();
3022  }
3023  }
3024  forceinline
3025  SharedHandle::SharedHandle(void) : o(NULL) {}
3026  forceinline
3028  subscribe();
3029  }
3030  forceinline
3032  subscribe();
3033  }
3036  if (&sh != this) {
3037  cancel(); o=sh.o; subscribe();
3038  }
3039  return *this;
3040  }
3041  forceinline void
3042  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
3043  if (sh.o == NULL) {
3044  o=NULL; return;
3045  } else if (share) {
3046  o=sh.o;
3047  } else if (sh.o->fwd != NULL) {
3048  o=sh.o->fwd;
3049  } else {
3050  o = sh.o->copy();
3051  sh.o->fwd = o;
3052  sh.o->next = home.pc.c.shared;
3053  home.pc.c.shared = sh.o;
3054  }
3055  subscribe();
3056  }
3057  forceinline
3059  cancel();
3060  }
3061 
3062 
3063 
3064  /*
3065  * No-goods
3066  *
3067  */
3068  forceinline
3070  : n(0) {}
3071  forceinline unsigned long int
3072  NoGoods::ng(void) const {
3073  return n;
3074  }
3075  forceinline void
3076  NoGoods::ng(unsigned long int n0) {
3077  n=n0;
3078  }
3079  forceinline
3081 
3082 
3083  /*
3084  * Information from meta search engines
3085  */
3086  forceinline
3087  MetaInfo::MetaInfo(unsigned long int r0,
3088  unsigned long int s0,
3089  unsigned long int f0,
3090  const Space* l0,
3091  NoGoods& ng0)
3092  : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3093 
3094  forceinline
3095  MetaInfo::MetaInfo(unsigned int a0)
3096  : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
3097 
3099  MetaInfo::type(void) const {
3100  return t;
3101  }
3102  forceinline unsigned long int
3103  MetaInfo::restart(void) const {
3104  assert(type() == RESTART);
3105  return r;
3106  }
3107  forceinline unsigned long int
3108  MetaInfo::solution(void) const {
3109  assert(type() == RESTART);
3110  return s;
3111  }
3112  forceinline unsigned long int
3113  MetaInfo::fail(void) const {
3114  assert(type() == RESTART);
3115  return f;
3116  }
3117  forceinline const Space*
3118  MetaInfo::last(void) const {
3119  assert(type() == RESTART);
3120  return l;
3121  }
3122  forceinline const NoGoods&
3123  MetaInfo::nogoods(void) const {
3124  assert(type() == RESTART);
3125  return ng;
3126  }
3127  forceinline unsigned int
3128  MetaInfo::asset(void) const {
3129  assert(type() == PORTFOLIO);
3130  return a;
3131  }
3132 
3133 
3134 
3135  /*
3136  * ActorLink
3137  *
3138  */
3140  ActorLink::prev(void) const {
3141  return _prev;
3142  }
3143 
3145  ActorLink::next(void) const {
3146  return _next;
3147  }
3148 
3151  return &_next;
3152  }
3153 
3154  forceinline void
3156  _prev = al;
3157  }
3158 
3159  forceinline void
3161  _next = al;
3162  }
3163 
3164  forceinline void
3166  ActorLink* p = _prev; ActorLink* n = _next;
3167  p->_next = n; n->_prev = p;
3168  }
3169 
3170  forceinline void
3172  _next = this; _prev =this;
3173  }
3174 
3175  forceinline void
3177  // Inserts al at head of link-chain (that is, after this)
3178  ActorLink* n = _next;
3179  this->_next = a; a->_prev = this;
3180  a->_next = n; n->_prev = a;
3181  }
3182 
3183  forceinline void
3185  // Inserts al at tail of link-chain (that is, before this)
3186  ActorLink* p = _prev;
3187  a->_next = this; this->_prev = a;
3188  p->_next = a; a->_prev = p;
3189  }
3190 
3191  forceinline bool
3192  ActorLink::empty(void) const {
3193  return _next == this;
3194  }
3195 
3196  template<class T>
3199  // Turning al into a reference is for gcc, assume is for MSVC
3200  GECODE_NOT_NULL(a);
3201  ActorLink& t = *a;
3202  return static_cast<ActorLink*>(&t);
3203  }
3204 
3205  template<class T>
3206  forceinline const ActorLink*
3207  ActorLink::cast(const T* a) {
3208  // Turning al into a reference is for gcc, assume is for MSVC
3209  GECODE_NOT_NULL(a);
3210  const ActorLink& t = *a;
3211  return static_cast<const ActorLink*>(&t);
3212  }
3213 
3214 
3215  /*
3216  * Actor
3217  *
3218  */
3220  Actor::cast(ActorLink* al) {
3221  // Turning al into a reference is for gcc, assume is for MSVC
3222  GECODE_NOT_NULL(al);
3223  ActorLink& t = *al;
3224  return static_cast<Actor*>(&t);
3225  }
3226 
3227  forceinline const Actor*
3228  Actor::cast(const ActorLink* al) {
3229  // Turning al into a reference is for gcc, assume is for MSVC
3230  GECODE_NOT_NULL(al);
3231  const ActorLink& t = *al;
3232  return static_cast<const Actor*>(&t);
3233  }
3234 
3235  forceinline void
3236  Space::afc_enable(void) {
3237  _wmp_afc |= 1U;
3238  }
3239  forceinline bool
3240  Space::afc_enabled(void) const {
3241  return (_wmp_afc & 1U) != 0U;
3242  }
3243  forceinline void
3244  Space::wmp(unsigned int n) {
3245  _wmp_afc = (_wmp_afc & 1U) | (n << 1);
3246  }
3247  forceinline unsigned int
3248  Space::wmp(void) const {
3249  return _wmp_afc >> 1U;
3250  }
3251 
3252  forceinline void
3253  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3254  s.notice(a,p,duplicate);
3255  }
3256 
3258  Space::clone(bool share_data, bool share_info, CloneStatistics&) const {
3259  // Clone is only const for search engines. During cloning, several data
3260  // structures are updated (e.g. forwarding pointers), so we have to
3261  // cast away the constness.
3262  return const_cast<Space*>(this)->_clone(share_data,share_info);
3263  }
3264 
3265  forceinline void
3266  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3267  _commit(c,a);
3268  }
3269 
3270  forceinline void
3271  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3272  _trycommit(c,a);
3273  }
3274 
3275  forceinline double
3276  Space::afc_decay(void) const {
3277  return gpi.decay();
3278  }
3279 
3280  forceinline size_t
3282  return sizeof(*this);
3283  }
3284 
3285 
3286  /*
3287  * Home for posting actors
3288  *
3289  */
3290  forceinline
3292  PropagatorGroup pg0, BrancherGroup bg0)
3293  : s(s0), p(p0), pg(pg0), bg(bg0) {}
3294  forceinline Home&
3296  s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3297  return *this;
3298  }
3299  forceinline
3300  Home::operator Space&(void) {
3301  return s;
3302  }
3305  return Home(s,&p);
3306  }
3309  return Home(s,NULL,pg,BrancherGroup::def);
3310  }
3313  return Home(s,NULL,PropagatorGroup::def,bg);
3314  }
3317  return Home(*this,&p);
3318  }
3320  Home::propagator(void) const {
3321  return p;
3322  }
3325  return pg;
3326  }
3328  Home::branchergroup(void) const {
3329  return bg;
3330  }
3331 
3332  /*
3333  * Execution information
3334  *
3335  */
3336  forceinline void
3338  who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3339  }
3340  forceinline void
3342  who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3343  }
3344  forceinline void
3346  who = (g.id() << 2) | POST;
3347  }
3348  forceinline void
3350  who = OTHER;
3351  }
3353  ExecInfo::what(void) const {
3354  return static_cast<What>(who & 3);
3355  }
3356  forceinline const Propagator&
3357  ExecInfo::propagator(void) const {
3358  assert(what() == PROPAGATOR);
3359  // Because PROPAGATOR == 0
3360  return *reinterpret_cast<Propagator*>(who);
3361  }
3362  forceinline const Brancher&
3363  ExecInfo::brancher(void) const {
3364  assert(what() == BRANCHER);
3365  return *reinterpret_cast<Brancher*>(who & ~3);
3366  }
3368  ExecInfo::post(void) const {
3369  assert(what() == POST);
3370  return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3371  }
3372 
3373  /*
3374  * Post information
3375  */
3376  forceinline
3377  PostInfo::PostInfo(Home home) : h(home) {
3378  h.pc.p.ei.post(home.propagatorgroup());
3379  }
3380  forceinline
3382  h.pc.p.ei.other();
3383  }
3384 
3385 
3386  /*
3387  * Propagator
3388  *
3389  */
3391  Propagator::cast(ActorLink* al) {
3392  // Turning al into a reference is for gcc, assume is for MSVC
3393  GECODE_NOT_NULL(al);
3394  ActorLink& t = *al;
3395  return static_cast<Propagator*>(&t);
3396  }
3397 
3398  forceinline const Propagator*
3399  Propagator::cast(const ActorLink* al) {
3400  // Turning al into a reference is for gcc, assume is for MSVC
3401  GECODE_NOT_NULL(al);
3402  const ActorLink& t = *al;
3403  return static_cast<const Propagator*>(&t);
3404  }
3405 
3407  Propagator::fwd(void) const {
3408  return static_cast<Propagator*>(prev());
3409  }
3410 
3411  forceinline bool
3412  Propagator::disabled(void) const {
3413  return Support::marked(gpi_disabled);
3414  }
3415 
3416  forceinline void
3418  gpi_disabled = Support::mark(gpi_disabled);
3419  }
3420 
3421  forceinline void
3423  gpi_disabled = Support::funmark(gpi_disabled);
3424  }
3425 
3428  return *static_cast<GPI::Info*>(Support::funmark(gpi_disabled));
3429  }
3430 
3431  forceinline
3433  : gpi_disabled((home.propagator() != NULL) ?
3434  // Inherit propagator information
3435  home.propagator()->gpi_disabled :
3436  // New propagator information
3437  static_cast<Space&>(home).gpi.allocate(home.propagatorgroup().gid)) {
3438  u.advisors = NULL;
3439  assert((u.med == 0) && (u.size == 0));
3440  static_cast<Space&>(home).pl.head(this);
3441  }
3442 
3443  forceinline
3445  : gpi_disabled(p.gpi_disabled) {
3446  u.advisors = NULL;
3447  assert((u.med == 0) && (u.size == 0));
3448  // Set forwarding pointer
3449  p.prev(this);
3450  }
3451 
3454  return u.med;
3455  }
3456 
3457  forceinline double
3458  Propagator::afc(const Space& home) const {
3459  return const_cast<Space&>(home).gpi.afc(const_cast<Propagator&>(*this).gpi());
3460  }
3461 
3462  forceinline unsigned int
3463  Propagator::id(void) const {
3464  return const_cast<Propagator&>(*this).gpi().pid;
3465  }
3466 
3468  Propagator::group(void) const {
3469  return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3470  }
3471 
3472  forceinline void
3474  gpi().gid = g.id();
3475  }
3476 
3479  p.u.size = s;
3480  return __ES_SUBSUMED;
3481  }
3482 
3485  p.u.size = p.dispose(*this);
3486  return __ES_SUBSUMED;
3487  }
3488 
3491  p.u.med = med;
3492  assert(p.u.med != 0);
3493  return __ES_PARTIAL;
3494  }
3495 
3498  p.u.med = AllVarConf::med_combine(p.u.med,med);
3499  assert(p.u.med != 0);
3500  return __ES_PARTIAL;
3501  }
3502 
3503 
3504 
3505  /*
3506  * Brancher
3507  *
3508  */
3510  Brancher::cast(ActorLink* al) {
3511  // Turning al into a reference is for gcc, assume is for MSVC
3512  GECODE_NOT_NULL(al);
3513  ActorLink& t = *al;
3514  return static_cast<Brancher*>(&t);
3515  }
3516 
3517  forceinline const Brancher*
3518  Brancher::cast(const ActorLink* al) {
3519  // Turning al into a reference is for gcc, assume is for MSVC
3520  GECODE_NOT_NULL(al);
3521  const ActorLink& t = *al;
3522  return static_cast<const Brancher*>(&t);
3523  }
3524 
3525  forceinline
3527  bid(static_cast<Space&>(home).pc.p.bid++),
3528  gid(home.branchergroup().gid) {
3529  if (static_cast<Space&>(home).pc.p.bid == 0U)
3530  throw TooManyBranchers("Brancher::Brancher");
3531  // If no brancher available, make it the first one
3532  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
3533  static_cast<Space&>(home).b_status = this;
3534  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
3535  static_cast<Space&>(home).b_commit = this;
3536  }
3537  static_cast<Space&>(home).bl.tail(this);
3538  }
3539 
3540  forceinline
3542  : bid(b.bid), gid(b.gid) {
3543  // Set forwarding pointer
3544  b.prev(this);
3545  }
3546 
3547  forceinline unsigned int
3548  Brancher::id(void) const {
3549  return bid;
3550  }
3551 
3553  Brancher::group(void) const {
3554  return BrancherGroup(gid);
3555  }
3556 
3557  forceinline void
3559  gid = g.id();
3560  }
3561 
3562 
3563  forceinline void
3564  Space::kill(Brancher& b) {
3565  assert(!failed());
3566  // Make sure that neither b_status nor b_commit does not point to b!
3567  if (b_commit == &b)
3568  b_commit = Brancher::cast(b.next());
3569  if (b_status == &b)
3570  b_status = Brancher::cast(b.next());
3571  b.unlink();
3572  rfree(&b,b.dispose(*this));
3573  }
3574 
3575  forceinline void
3576  Space::kill(Propagator& p) {
3577  assert(!failed());
3578  p.unlink();
3579  rfree(&p,p.dispose(*this));
3580  }
3581 
3583  Space::brancher(unsigned int id) {
3584  /*
3585  * Due to weakly monotonic propagators the following scenario might
3586  * occur: a brancher has been committed with all its available
3587  * choices. Then, propagation determines less information
3588  * than before and the brancher now will create new choices.
3589  * Later, during recomputation, all of these choices
3590  * can be used together, possibly interleaved with
3591  * choices for other branchers. That means all branchers
3592  * must be scanned to find the matching brancher for the choice.
3593  *
3594  * b_commit tries to optimize scanning as it is most likely that
3595  * recomputation does not generate new choices during recomputation
3596  * and hence b_commit is moved from newer to older branchers.
3597  */
3598  Brancher* b_old = b_commit;
3599  // Try whether we are lucky
3600  while (b_commit != Brancher::cast(&bl))
3601  if (id != b_commit->id())
3602  b_commit = Brancher::cast(b_commit->next());
3603  else
3604  return b_commit;
3605  if (b_commit == Brancher::cast(&bl)) {
3606  // We did not find the brancher, start at the beginning
3607  b_commit = Brancher::cast(bl.next());
3608  while (b_commit != b_old)
3609  if (id != b_commit->id())
3610  b_commit = Brancher::cast(b_commit->next());
3611  else
3612  return b_commit;
3613  }
3614  return NULL;
3615  }
3616 
3617 
3618  /*
3619  * Local objects
3620  *
3621  */
3622 
3625  // Turning al into a reference is for gcc, assume is for MSVC
3626  GECODE_NOT_NULL(al);
3627  ActorLink& t = *al;
3628  return static_cast<LocalObject*>(&t);
3629  }
3630 
3631  forceinline const LocalObject*
3633  // Turning al into a reference is for gcc, assume is for MSVC
3634  GECODE_NOT_NULL(al);
3635  const ActorLink& t = *al;
3636  return static_cast<const LocalObject*>(&t);
3637  }
3638 
3639  forceinline
3641  (void) home;
3642  ActorLink::cast(this)->prev(NULL);
3643  }
3644 
3645  forceinline
3647  ActorLink::cast(this)->prev(NULL);
3648  }
3649 
3651  LocalObject::fwd(Space& home, bool share) {
3652  if (prev() == NULL)
3653  fwdcopy(home,share);
3654  return LocalObject::cast(prev());
3655  }
3656 
3657  forceinline
3658  LocalHandle::LocalHandle(void) : o(NULL) {}
3659  forceinline
3661  forceinline
3662  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3665  o = lh.o;
3666  return *this;
3667  }
3668  forceinline
3671  LocalHandle::object(void) const { return o; }
3672  forceinline void
3674  forceinline void
3675  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
3676  object(lh.object()->fwd(home,share));
3677  }
3678 
3679 
3680  /*
3681  * Choices
3682  *
3683  */
3684  forceinline
3685  Choice::Choice(const Brancher& b, const unsigned int a)
3686  : bid(b.id()), alt(a) {}
3687 
3688  forceinline unsigned int
3689  Choice::alternatives(void) const {
3690  return alt;
3691  }
3692 
3693  forceinline unsigned int
3694  Choice::id(void) const {
3695  return bid;
3696  }
3697 
3698  forceinline
3700 
3701 
3702 
3703  /*
3704  * No-good literal
3705  *
3706  */
3707  forceinline bool
3708  NGL::leaf(void) const {
3709  return Support::marked(nl);
3710  }
3711  forceinline NGL*
3712  NGL::next(void) const {
3713  return static_cast<NGL*>(Support::funmark(nl));
3714  }
3715  forceinline void
3716  NGL::leaf(bool l) {
3717  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3718  }
3719  forceinline void
3721  nl = Support::marked(nl) ? Support::mark(n) : n;
3722  }
3723  forceinline NGL*
3724  NGL::add(NGL* n, bool l) {
3725  nl = Support::marked(nl) ? Support::mark(n) : n;
3726  n->leaf(l);
3727  return n;
3728  }
3729 
3730  forceinline
3731  NGL::NGL(void)
3732  : nl(NULL) {}
3733  forceinline
3735  : nl(NULL) {}
3736  forceinline
3737  NGL::NGL(Space&, bool, NGL&)
3738  : nl(NULL) {}
3739  forceinline size_t
3741  return sizeof(*this);
3742  }
3743 
3744  /*
3745  * Advisor
3746  *
3747  */
3748  template<class A>
3749  forceinline
3751  // Store propagator and forwarding in prev()
3752  ActorLink::prev(&p);
3753  // Link to next advisor in next()
3754  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3755  }
3756 
3757  forceinline
3759 
3760  forceinline bool
3761  Advisor::disposed(void) const {
3762  return prev() == NULL;
3763  }
3764 
3766  Advisor::cast(ActorLink* al) {
3767  return static_cast<Advisor*>(al);
3768  }
3769 
3770  forceinline const Advisor*
3771  Advisor::cast(const ActorLink* al) {
3772  return static_cast<const Advisor*>(al);
3773  }
3774 
3776  Advisor::propagator(void) const {
3777  assert(!disposed());
3778  return *Propagator::cast(ActorLink::prev());
3779  }
3780 
3781  template<class A>
3782  forceinline void
3784  assert(!disposed());
3785  ActorLink::prev(NULL);
3786  // Shorten chains of disposed advisors by one, if possible
3787  Advisor* n = Advisor::cast(next());
3788  if ((n != NULL) && n->disposed())
3789  next(n->next());
3790  }
3791 
3792  forceinline const ExecInfo&
3793  Advisor::operator ()(const Space& home) const {
3794  return home.pc.p.ei;
3795  }
3796 
3797  template<class A>
3800  a.dispose(*this,c);
3801  return ES_FIX;
3802  }
3803 
3804  template<class A>
3807  a.dispose(*this,c);
3808  return ES_NOFIX;
3809  }
3810 
3811  template<class A>
3814  a.dispose(*this,c);
3815  return ES_NOFIX_FORCE;
3816  }
3817 
3818 
3819 
3820  /*
3821  * Advisor council
3822  *
3823  */
3824  template<class A>
3825  forceinline
3827 
3828  template<class A>
3829  forceinline
3831  : advisors(NULL) {}
3832 
3833  template<class A>
3834  forceinline bool
3835  Council<A>::empty(void) const {
3836  ActorLink* a = advisors;
3837  while ((a != NULL) && static_cast<A*>(a)->disposed())
3838  a = a->next();
3839  advisors = a;
3840  return a == NULL;
3841  }
3842 
3843  template<class A>
3844  forceinline void
3845  Council<A>::update(Space& home, bool share, Council<A>& c) {
3846  // Skip all disposed advisors
3847  {
3848  ActorLink* a = c.advisors;
3849  while ((a != NULL) && static_cast<A*>(a)->disposed())
3850  a = a->next();
3851  c.advisors = a;
3852  }
3853  // Are there any advisors to be cloned?
3854  if (c.advisors != NULL) {
3855  // The propagator in from-space
3856  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3857  // The propagator in to-space
3858  Propagator* p_t = Propagator::cast(p_f->prev());
3859  // Advisors in from-space
3860  ActorLink** a_f = &c.advisors;
3861  // Advisors in to-space
3862  A* a_t = NULL;
3863  while (*a_f != NULL) {
3864  if (static_cast<A*>(*a_f)->disposed()) {
3865  *a_f = (*a_f)->next();
3866  } else {
3867  // Run specific copying part
3868  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
3869  // Set propagator pointer
3870  a->prev(p_t);
3871  // Set forwarding pointer
3872  (*a_f)->prev(a);
3873  // Link
3874  a->next(a_t);
3875  a_t = a;
3876  a_f = (*a_f)->next_ref();
3877  }
3878  }
3879  advisors = a_t;
3880  // Enter advisor link for reset
3881  assert(p_f->u.advisors == NULL);
3882  p_f->u.advisors = c.advisors;
3883  } else {
3884  advisors = NULL;
3885  }
3886  }
3887 
3888  template<class A>
3889  forceinline void
3891  ActorLink* a = advisors;
3892  while (a != NULL) {
3893  if (!static_cast<A*>(a)->disposed())
3894  static_cast<A*>(a)->dispose(home,*this);
3895  a = a->next();
3896  }
3897  }
3898 
3899 
3900 
3901  /*
3902  * Advisor iterator
3903  *
3904  */
3905  template<class A>
3906  forceinline
3908  : a(c.advisors) {
3909  while ((a != NULL) && static_cast<A*>(a)->disposed())
3910  a = a->next();
3911  }
3912 
3913  template<class A>
3914  forceinline bool
3916  return a != NULL;
3917  }
3918 
3919  template<class A>
3920  forceinline void
3922  do {
3923  a = a->next();
3924  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3925  }
3926 
3927  template<class A>
3928  forceinline A&
3929  Advisors<A>::advisor(void) const {
3930  return *static_cast<A*>(a);
3931  }
3932 
3933 
3934 
3935  /*
3936  * Space
3937  *
3938  */
3939  forceinline void
3940  Space::enqueue(Propagator* p) {
3941  ActorLink::cast(p)->unlink();
3942  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3943  c->tail(ActorLink::cast(p));
3944  if (c > pc.p.active)
3945  pc.p.active = c;
3946  }
3947 
3948  forceinline void
3949  Space::fail(void) {
3950  /*
3951  * Now active points beyond the last queue. This is essential as
3952  * enqueuing a propagator in a failed space keeps the space
3953  * failed.
3954  */
3955  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3956  }
3957  forceinline void
3958  Home::fail(void) {
3959  s.fail();
3960  }
3961 
3962  forceinline bool
3963  Space::failed(void) const {
3964  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3965  }
3966  forceinline bool
3967  Home::failed(void) const {
3968  return s.failed();
3969  }
3970 
3971  forceinline bool
3972  Space::stable(void) const {
3973  return ((pc.p.active < &pc.p.queue[0]) ||
3974  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3975  }
3976 
3977 
3978 
3979  /*
3980  * Variable implementation
3981  *
3982  */
3983  template<class VIC>
3986  assert((pc >= 0) && (pc < pc_max+2));
3987  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
3988  }
3989 
3990  template<class VIC>
3993  assert((pc > 0) && (pc < pc_max+2));
3994  return b.base+u.idx[pc-1];
3995  }
3996 
3997  template<class VIC>
3998  forceinline unsigned int&
4000  assert((pc > 0) && (pc < pc_max+2));
4001  return u.idx[pc-1];
4002  }
4003 
4004  template<class VIC>
4005  forceinline unsigned int
4006  VarImp<VIC>::idx(PropCond pc) const {
4007  assert((pc > 0) && (pc < pc_max+2));
4008  return u.idx[pc-1];
4009  }
4010 
4011  template<class VIC>
4012  forceinline
4014  b.base = NULL; entries = 0;
4015  for (PropCond pc=1; pc<pc_max+2; pc++)
4016  idx(pc) = 0;
4017  free_and_bits = 0;
4018  }
4019 
4020  template<class VIC>
4021  forceinline
4023  b.base = NULL; entries = 0;
4024  for (PropCond pc=1; pc<pc_max+2; pc++)
4025  idx(pc) = 0;
4026  free_and_bits = 0;
4027  }
4028 
4029  template<class VIC>
4030  forceinline unsigned int
4031  VarImp<VIC>::degree(void) const {
4032  assert(!copied());
4033  return entries;
4034  }
4035 
4036  template<class VIC>
4037  forceinline double
4038  VarImp<VIC>::afc(const Space& home) const {
4039  double d = 0.0;
4040  // Count the afc of each propagator
4041  {
4042  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4043  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4044  while (a < e) {
4045  d += Propagator::cast(*a)->afc(home); a++;
4046  }
4047  }
4048  // Count the afc of each advisor's propagator
4049  {
4050  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4051  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4052  while (a < e) {
4053  d += Advisor::cast(*a)->propagator().afc(home); a++;
4054  }
4055  }
4056  return d;
4057  }
4058 
4059  template<class VIC>
4062  return d.me;
4063  }
4064 
4065  template<class VIC>
4066  forceinline unsigned int
4067  VarImp<VIC>::bits(void) const {
4068  return free_and_bits;
4069  }
4070 
4071  template<class VIC>
4072  forceinline unsigned int&
4074  return free_and_bits;
4075  }
4076 
4077 #ifdef GECODE_HAS_VAR_DISPOSE
4078  template<class VIC>
4080  VarImp<VIC>::vars_d(Space& home) {
4081  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4082  }
4083 
4084  template<class VIC>
4085  forceinline void
4087  home.vars_d<VIC>(x);
4088  }
4089 #endif
4090 
4091  template<class VIC>
4092  forceinline bool
4093  VarImp<VIC>::copied(void) const {
4094  return Support::marked(b.fwd);
4095  }
4096 
4097  template<class VIC>
4099  VarImp<VIC>::forward(void) const {
4100  assert(copied());
4101  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4102  }
4103 
4104  template<class VIC>
4106  VarImp<VIC>::next(void) const {
4107  assert(copied());
4108  return u.next;
4109  }
4110 
4111  template<class VIC>
4112  forceinline
4114  VarImpBase** reg;
4115  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4116  if (x.b.base == NULL) {
4117  // Variable implementation needs no index structure
4118  reg = &home.pc.c.vars_noidx;
4119  assert(x.degree() == 0);
4120  } else {
4121  reg = &home.pc.c.vars_u[idx_c];
4122  }
4123  // Save subscriptions in copy
4124  b.base = x.b.base;
4125  entries = x.entries;
4126  for (PropCond pc=1; pc<pc_max+2; pc++)
4127  idx(pc) = x.idx(pc);
4128 
4129  // Set forwarding pointer
4130  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4131  // Register original
4132  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4133  }
4134 
4135  template<class VIC>
4138  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4139  }
4140 
4141  template<class VIC>
4144  return static_cast<ModEventDelta>(me << VIC::med_fst);
4145  }
4146 
4147  template<class VIC>
4150  return VIC::me_combine(me1,me2);
4151  }
4152 
4153  template<class VIC>
4154  forceinline void
4156  bool force) {
4157  if (VIC::med_update(p.u.med,me) || force)
4158  home.enqueue(&p);
4159  }
4160 
4161  template<class VIC>
4162  forceinline void
4164  ActorLink** b = actor(pc1);
4165  ActorLink** p = actorNonZero(pc2+1);
4166  while (p-- > b)
4167  schedule(home,*Propagator::cast(*p),me);
4168  }
4169 
4170  template<class VIC>
4171  forceinline void
4172  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4173  assert(pc <= pc_max);
4174  // Count one new subscription
4175  home.pc.p.n_sub += 1;
4176  if ((free_and_bits >> free_bits) == 0)
4177  resize(home);
4178  free_and_bits -= 1 << free_bits;
4179 
4180  // Enter subscription
4181  b.base[entries] = *actorNonZero(pc_max+1);
4182  entries++;
4183  for (PropCond j = pc_max; j > pc; j--) {
4184  *actorNonZero(j+1) = *actorNonZero(j);
4185  idx(j+1)++;
4186  }
4187  *actorNonZero(pc+1) = *actor(pc);
4188  idx(pc+1)++;
4189  *actor(pc) = ActorLink::cast(p);
4190 
4191 #ifdef GECODE_AUDIT
4192  ActorLink** f = actor(pc);
4193  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4194  if (*f == p)
4195  goto found;
4196  else
4197  f++;
4198  GECODE_NEVER;
4199  found: ;
4200 #endif
4201  }
4202 
4203  template<class VIC>
4204  forceinline void
4205  VarImp<VIC>::enter(Space& home, Advisor* a) {
4206  // Count one new subscription
4207  home.pc.p.n_sub += 1;
4208  if ((free_and_bits >> free_bits) == 0)
4209  resize(home);
4210  free_and_bits -= 1 << free_bits;
4211 
4212  // Enter subscription
4213  b.base[entries++] = *actorNonZero(pc_max+1);
4214  *actorNonZero(pc_max+1) = a;
4215  }
4216 
4217  template<class VIC>
4218  void
4219  VarImp<VIC>::resize(Space& home) {
4220  if (b.base == NULL) {
4221  assert((free_and_bits >> free_bits) == 0);
4222  // Create fresh dependency array with four entries
4223  free_and_bits += 4 << free_bits;
4224  b.base = home.alloc<ActorLink*>(4);
4225  for (int i=0; i<pc_max+1; i++)
4226  u.idx[i] = 0;
4227  } else {
4228  // Resize dependency array
4229  unsigned int n = degree();
4230  // Find out whether the area is most likely in the special area
4231  // reserved for subscriptions. If yes, just resize mildly otherwise
4232  // more agressively
4233  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4234  unsigned int m =
4235  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4236  (n+4) : ((n+1)*3>>1);
4237  ActorLink** prop = home.alloc<ActorLink*>(m);
4238  free_and_bits += (m-n) << free_bits;
4239  // Copy entries
4240  Heap::copy<ActorLink*>(prop, b.base, n);
4241  home.free<ActorLink*>(b.base,n);
4242  b.base = prop;
4243  }
4244  }
4245 
4246  template<class VIC>
4247  void
4249  bool assigned, ModEvent me, bool schedule) {
4250  if (assigned) {
4251  // Do not subscribe, just schedule the propagator
4252  if (schedule)
4254  } else {
4255  enter(home,&p,pc);
4256  // Schedule propagator
4257  if (schedule && (pc != PC_GEN_ASSIGNED))
4258  VarImp<VIC>::schedule(home,p,me);
4259  }
4260  }
4261 
4262  template<class VIC>
4263  forceinline void
4265  if (!assigned)
4266  enter(home,&a);
4267  }
4268 
4269  template<class VIC>
4270  void
4272  bool assigned, ModEvent me) {
4273  if (assigned)
4275  else if (pc != PC_GEN_ASSIGNED)
4276  VarImp<VIC>::schedule(home,p,me);
4277  }
4278 
4279  template<class VIC>
4280  forceinline void
4281  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
4282  assert(pc <= pc_max);
4283  ActorLink* a = ActorLink::cast(p);
4284  // Find actor in dependency array
4285  ActorLink** f = actor(pc);
4286 #ifdef GECODE_AUDIT
4287  while (f < actorNonZero(pc+1))
4288  if (*f == a)
4289  goto found;
4290  else
4291  f++;
4292  GECODE_NEVER;
4293  found: ;
4294 #else
4295  while (*f != a) f++;
4296 #endif
4297  // Remove actor
4298  *f = *(actorNonZero(pc+1)-1);
4299  for (PropCond j = pc+1; j< pc_max+1; j++) {
4300  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4301  idx(j)--;
4302  }
4303  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4304  idx(pc_max+1)--;
4305  entries--;
4306  free_and_bits += 1 << free_bits;
4307  home.pc.p.n_sub -= 1;
4308  }
4309 
4310  template<class VIC>
4311  forceinline void
4312  VarImp<VIC>::remove(Space& home, Advisor* a) {
4313  // Find actor in dependency array
4314  ActorLink** f = actorNonZero(pc_max+1);
4315 #ifdef GECODE_AUDIT
4316  while (f < b.base+entries)
4317  if (*f == a)
4318  goto found;
4319  else
4320  f++;
4321  GECODE_NEVER;
4322  found: ;
4323 #else
4324  while (*f != a) f++;
4325 #endif
4326  // Remove actor
4327  *f = b.base[--entries];
4328  free_and_bits += 1 << free_bits;
4329  home.pc.p.n_sub -= 1;
4330  }
4331 
4332  template<class VIC>
4333  forceinline void
4335  if (!assigned)
4336  remove(home,&p,pc);
4337  }
4338 
4339  template<class VIC>
4340  forceinline void
4342  if (!assigned)
4343  remove(home,&a);
4344  }
4345 
4346  template<class VIC>
4347  forceinline void
4349  unsigned int n_sub = degree();
4350  home.pc.p.n_sub -= n_sub;
4351  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
4352  home.free<ActorLink*>(b.base,n);
4353  // Must be NULL such that cloning works
4354  b.base = NULL;
4355  // Must be 0 such that degree works
4356  entries = 0;
4357  }
4358 
4359  template<class VIC>
4360  forceinline bool
4362  /*
4363  * An advisor that is executed might remove itself due to subsumption.
4364  * As entries are removed from front to back, the advisors must
4365  * be iterated in forward direction.
4366  */
4367  ActorLink** la = actorNonZero(pc_max+1);
4368  ActorLink** le = b.base+entries;
4369  if (la == le)
4370  return true;
4371  d.me = me;
4372  // An advisor that is run, might be removed during execution.
4373  // As removal is done from the back the advisors have to be executed
4374  // in inverse order.
4375  do {
4376  Advisor* a = Advisor::cast(*la);
4377  assert(!a->disposed());
4378  Propagator& p = a->propagator();
4379  switch (p.advise(home,*a,d)) {
4380  case ES_FIX:
4381  break;
4382  case ES_FAILED:
4383  if (home.afc_enabled())
4384  home.gpi.fail(p.gpi());
4385  return false;
4386  case ES_NOFIX:
4387  schedule(home,p,me);
4388  break;
4389  case ES_NOFIX_FORCE:
4390  schedule(home,p,me,true);
4391  break;
4392  case __ES_SUBSUMED:
4393  default:
4394  GECODE_NEVER;
4395  }
4396  } while (++la < le);
4397  return true;
4398  }
4399 
4400  template<class VIC>
4401  forceinline void
4403  // this refers to the variable to be updated (clone)
4404  // x refers to the original
4405  // Recover from copy
4406  x->b.base = b.base;
4407  x->u.idx[0] = u.idx[0];
4408  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4409  x->u.idx[1] = u.idx[1];
4410 
4411  ActorLink** f = x->b.base;
4412  unsigned int n = x->degree();
4413  ActorLink** t = sub;
4414  sub += n;
4415  b.base = t;
4416  // Set subscriptions using actor forwarding pointers
4417  while (n >= 4) {
4418  n -= 4;
4419  t[0]=f[0]->prev(); t[1]=f[1]->prev();
4420  t[2]=f[2]->prev(); t[3]=f[3]->prev();
4421  t += 4; f += 4;
4422  }
4423  if (n >= 2) {
4424  n -= 2;
4425  t[0]=f[0]->prev(); t[1]=f[1]->prev();
4426  t += 2; f += 2;
4427  }
4428  if (n > 0) {
4429  t[0]=f[0]->prev();
4430  }
4431  }
4432 
4433  template<class VIC>
4434  forceinline void
4435  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4436  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4437  while (x != NULL) {
4438  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4439  }
4440  }
4441 
4442 
4443 
4444  /*
4445  * Variable disposer
4446  *
4447  */
4448  template<class VarImp>
4450 #ifdef GECODE_HAS_VAR_DISPOSE
4451  Space::vd[VarImp::idx_d] = this;
4452 #endif
4453  }
4454 
4455  template<class VarImp>
4456  void
4458  VarImp* x = static_cast<VarImp*>(_x);
4459  do {
4460  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4461  } while (x != NULL);
4462  }
4463 
4464  /*
4465  * Statistics
4466  */
4467 
4468  forceinline void
4470  propagate = 0;
4471  wmp = false;
4472  }
4473  forceinline
4475  reset();
4476  }
4479  propagate += s.propagate;
4480  wmp |= s.wmp;
4481  return *this;
4482  }
4485  StatusStatistics t(s);
4486  return t += *this;
4487  }
4488 
4489  forceinline void
4491 
4492  forceinline
4494  reset();
4495  }
4498  CloneStatistics s;
4499  return s;
4500  }
4503  return *this;
4504  }
4505 
4506  forceinline void
4508 
4509  forceinline
4511  reset();
4512  }
4515  CommitStatistics s;
4516  return s;
4517  }
4520  return *this;
4521  }
4522 
4523  /*
4524  * Cost computation
4525  *
4526  */
4527 
4528  forceinline
4529  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4530 
4532  PropCost::cost(PropCost::Mod m,
4534  unsigned int n) {
4535  if (n < 2)
4536  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4537  else if (n == 2)
4538  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4539  else if (n == 3)
4540  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4541  else
4542  return (m == LO) ? lo : hi;
4543  }
4544 
4547  return AC_RECORD;
4548  }
4550  PropCost::crazy(PropCost::Mod m, unsigned int n) {
4551  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4552  }
4555  assert(n >= 0);
4556  return crazy(m,static_cast<unsigned int>(n));
4557  }
4559  PropCost::cubic(PropCost::Mod m, unsigned int n) {
4560  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4561  }
4564  assert(n >= 0);
4565  return cubic(m,static_cast<unsigned int>(n));
4566  }
4568  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
4569  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4570  }
4573  assert(n >= 0);
4574  return quadratic(m,static_cast<unsigned int>(n));
4575  }
4577  PropCost::linear(PropCost::Mod m, unsigned int n) {
4578  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4579  }
4582  assert(n >= 0);
4583  return linear(m,static_cast<unsigned int>(n));
4584  }
4587  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4588  }
4591  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4592  }
4595  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4596  }
4597 
4598  /*
4599  * Iterators for propagators and branchers of a space
4600  *
4601  */
4602  forceinline
4603  Space::Propagators::Propagators(Space& home0)
4604  : home(home0), q(home.pc.p.active) {
4605  while (q >= &home.pc.p.queue[0]) {
4606  if (q->next() != q) {
4607  c = q->next(); e = q; q--;
4608  return;
4609  }
4610  q--;
4611  }
4612  q = NULL;
4613  if (!home.pl.empty()) {
4614  c = Propagator::cast(home.pl.next());
4615  e = Propagator::cast(&home.pl);
4616  } else {
4617  c = e = NULL;
4618  }
4619  }
4620  forceinline bool
4621  Space::Propagators::operator ()(void) const {
4622  return c != NULL;
4623  }
4624  forceinline void
4625  Space::Propagators::operator ++(void) {
4626  c = c->next();
4627  if (c == e) {
4628  if (q == NULL) {
4629  c = NULL;
4630  } else {
4631  while (q >= &home.pc.p.queue[0]) {
4632  if (q->next() != q) {
4633  c = q->next(); e = q; q--;
4634  return;
4635  }
4636  q--;
4637  }
4638  q = NULL;
4639  if (!home.pl.empty()) {
4640  c = Propagator::cast(home.pl.next());
4641  e = Propagator::cast(&home.pl);
4642  } else {
4643  c = NULL;
4644  }
4645  }
4646  }
4647  }
4649  Space::Propagators::propagator(void) const {
4650  return *Propagator::cast(c);
4651  }
4652 
4653 
4654  forceinline
4655  Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
4656  : home(home0), q(home.pc.p.active) {
4657  while (q >= &home.pc.p.queue[0]) {
4658  if (q->next() != q) {
4659  c = q->next(); e = q; q--;
4660  return;
4661  }
4662  q--;
4663  }
4664  q = c = e = NULL;
4665  }
4666  forceinline bool
4667  Space::ScheduledPropagators::operator ()(void) const {
4668  return c != NULL;
4669  }
4670  forceinline void
4671  Space::ScheduledPropagators::operator ++(void) {
4672  c = c->next();
4673  if (c == e) {
4674  if (q == NULL) {
4675  c = NULL;
4676  } else {
4677  while (q >= &home.pc.p.queue[0]) {
4678  if (q->next() != q) {
4679  c = q->next(); e = q; q--;
4680  return;
4681  }
4682  q--;
4683  }
4684  q = c = e = NULL;
4685  }
4686  }
4687  }
4690  return *Propagator::cast(c);
4691  }
4692 
4693 
4694  forceinline
4695  Space::IdlePropagators::IdlePropagators(Space& home) {
4696  c = Propagator::cast(home.pl.next());
4697  e = Propagator::cast(&home.pl);
4698  }
4699  forceinline bool
4700  Space::IdlePropagators::operator ()(void) const {
4701  return c != e;
4702  }
4703  forceinline void
4704  Space::IdlePropagators::operator ++(void) {
4705  c = c->next();
4706  }
4709  return *Propagator::cast(c);
4710  }
4711 
4712 
4713  forceinline
4714  Space::Branchers::Branchers(Space& home)
4715  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4716  forceinline bool
4717  Space::Branchers::operator ()(void) const {
4718  return c != e;
4719  }
4720  forceinline void
4721  Space::Branchers::operator ++(void) {
4722  c = c->next();
4723  }
4725  Space::Branchers::brancher(void) const {
4726  return *Brancher::cast(c);
4727  }
4728 
4729 
4730  /*
4731  * Groups of actors
4732  */
4733  forceinline
4734  Group::Group(unsigned int gid0) : gid(gid0) {}
4735 
4736  forceinline bool
4737  Group::in(Group actor) const {
4738  return (gid == GROUPID_ALL) || (gid == actor.gid);
4739  }
4740 
4741  forceinline bool
4742  Group::in(void) const {
4743  return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
4744  }
4745 
4746  forceinline
4747  Group::Group(const Group& g) : gid(g.gid) {}
4748 
4751  gid=g.gid; return *this;
4752  }
4753 
4754  forceinline unsigned int
4755  Group::id(void) const {
4756  return gid;
4757  }
4758 
4759 
4760  forceinline
4762 
4763  forceinline
4765  : Group(gid) {}
4766 
4767  forceinline
4769  : Group(g) {}
4770 
4773  return static_cast<PropagatorGroup&>(Group::operator =(g));
4774  }
4775 
4778  return Home(home,NULL,*this,BrancherGroup::def);
4779  }
4780 
4781  forceinline bool
4783  return id() == g.id();
4784  }
4785  forceinline bool
4787  return id() != g.id();
4788  }
4789 
4792  if (id() != GROUPID_ALL)
4793  p.group(*this);
4794  return *this;
4795  }
4796 
4797 
4798  forceinline
4800 
4801  forceinline
4803  : Group(gid) {}
4804 
4805  forceinline
4807  : Group(g) {}
4808 
4811  return static_cast<BrancherGroup&>(Group::operator =(g));
4812  }
4813 
4816  return Home(home,NULL,PropagatorGroup::def,*this);
4817  }
4818 
4819  forceinline bool
4821  return id() == g.id();
4822  }
4823  forceinline bool
4825  return id() != g.id();
4826  }
4827 
4830  if (id() != GROUPID_ALL)
4831  p.group(*this);
4832  return *this;
4833  }
4834 
4835 
4836  /*
4837  * Iterators for propagators and branchers in a group
4838  *
4839  */
4840  forceinline
4842  : ps(home), g(g0) {
4843  while (ps() && !g.in(ps.propagator().group()))
4844  ++ps;
4845  }
4846  forceinline bool
4848  return ps();
4849  }
4850  forceinline void
4852  do
4853  ++ps;
4854  while (ps() && !g.in(ps.propagator().group()));
4855  }
4856  forceinline const Propagator&
4858  return ps.propagator();
4859  }
4860 
4861  forceinline
4863  : bs(home), g(g0) {
4864  while (bs() && !g.in(bs.brancher().group()))
4865  ++bs;
4866  }
4867  forceinline bool
4869  return bs();
4870  }
4871  forceinline void
4873  do
4874  ++bs;
4875  while (bs() && !g.in(bs.brancher().group()));
4876  }
4877  forceinline const Brancher&
4878  Branchers::brancher(void) const {
4879  return bs.brancher();
4880  }
4881 
4882 
4883  /*
4884  * Space construction support
4885  *
4886  */
4887  template<class T>
4888  forceinline T&
4890  return alloc<T>(1);
4891  }
4892  template<class T, typename A1>
4893  forceinline T&
4894  Space::construct(A1 const& a1) {
4895  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4896  new (&t) T(a1);
4897  return t;
4898  }
4899  template<class T, typename A1, typename A2>
4900  forceinline T&
4901  Space::construct(A1 const& a1, A2 const& a2) {
4902  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4903  new (&t) T(a1,a2);
4904  return t;
4905  }
4906  template<class T, typename A1, typename A2, typename A3>
4907  forceinline T&
4908  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
4909  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4910  new (&t) T(a1,a2,a3);
4911  return t;
4912  }
4913  template<class T, typename A1, typename A2, typename A3, typename A4>
4914  forceinline T&
4915  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
4916  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4917  new (&t) T(a1,a2,a3,a4);
4918  return t;
4919  }
4920  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
4921  forceinline T&
4922  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
4923  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4924  new (&t) T(a1,a2,a3,a4,a5);
4925  return t;
4926  }
4927 
4928 }
4929 
4930 // STATISTICS: kernel-core
virtual Object * copy(void) const =0
Return fresh copy for update.
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3689
void reset(void)
Reset information.
Definition: core.hpp:4490
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition: core.hpp:3108
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:154
bool marked(void *p)
Check whether p is marked.
Iterator over subscribed propagators.
friend class Branchers
Definition: core.hpp:1679
Council of advisors
Definition: core.hpp:228
SharedHandle(void)
Create shared handle with no object pointing to.
Definition: core.hpp:3025
Base-class for variable implementations.
Definition: core.hpp:230
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:3407
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Space must be branched (at least one brancher left)
Definition: core.hpp:1613
double afc(const Space &home) const
Return the accumlated failure count.
Definition: core.hpp:3458
Class to iterate over branchers in a group.
Definition: core.hpp:2718
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4568
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:4786
unsigned int bid
Id of next brancher to be created.
Definition: core.hpp:1752
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition: core.hpp:3324
The shared handle.
Definition: core.hpp:79
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4099
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:896
LocalObject(Home home)
Constructor for creation.
Definition: core.hpp:3640
Type
Which type of information is provided.
Definition: core.hpp:1545
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4577
Group & operator=(const Group &g)
Assignment operator.
Definition: core.hpp:4750
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4737
VarImp(void)
Creation of static instances.
Definition: core.hpp:4022
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3484
ExecInfo ei
Execution information.
Definition: core.hpp:1756
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:4449
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:344
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3671
Actor must always be disposed.
Definition: core.hpp:626
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1026
const Type t
Type of information.
Definition: core.hpp:1553
PropagatorGroup(void)
Constructor.
Definition: core.hpp:4761
NGL(void)
Constructor for creation.
Definition: core.hpp:3731
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
SpaceStatus
Space status
Definition: core.hpp:1610
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3497
~PostInfo(void)
Reset information.
Definition: core.hpp:3381
Group of branchers.
Definition: core.hpp:848
void * subscriptions(void) const
Get the memory area for subscriptions.
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:838
Manage memory for space.
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:899
Propagators(Space &home, PropagatorGroup g)
Initialize.
Definition: core.hpp:4841
friend class Home
Definition: core.hpp:728
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from the space heap...
Definition: core.hpp:2834
double afc(const Space &home) const
Return accumulated failure count (plus degree)
Definition: core.hpp:4038
Class to iterate over propagators in a group.
Definition: core.hpp:2700
Statistics for execution of commit
Definition: core.hpp:1656
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:4031
AFC afc
Definition: afc.cpp:139
Local (space-shared) object.
Definition: core.hpp:1460
Status
The status of a no-good literal.
Definition: core.hpp:1266
unsigned long int fail(void) const
Return number of failures since last restart.
Definition: core.hpp:3113
int ModEvent
Type for modification events.
Definition: core.hpp:142
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:4155
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:4061
Base-class for propagators.
Definition: core.hpp:1012
Internal: propagator is subsumed, do not use.
Definition: core.hpp:537
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3699
T & construct(void)
Construction routines.
Definition: core.hpp:4889
Information is provided by a restart-based engine.
Definition: core.hpp:1547
Base-class for advisors.
Definition: core.hpp:1212
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4143
bool wmp
Whether a weakly monotonic propagator might have been executed.
Definition: core.hpp:1625
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4546
ActorLink ** base
Subscribed actors.
Definition: core.hpp:306
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3806
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:342
const NoGoods & ng
No-goods from restart.
Definition: core.hpp:1565
Class to iterate over advisors of a council.
Definition: core.hpp:229
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:771
Space & h
The home space.
Definition: core.hpp:1000
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3258
Handle to region.
Definition: region.hpp:61
friend class SharedHandle
Definition: core.hpp:90
void * mark(void *p)
Return marked pointer for p.
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:817
PropagatorGroup pg
A propagator group.
Definition: core.hpp:913
Base-class for variable implementations.
Definition: core.hpp:245
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1767
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1623
Propagation has computed fixpoint.
Definition: core.hpp:541
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4755
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:4872
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4594
Computation spaces.
Definition: core.hpp:1672
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:257
const Propagator & propagator(void) const
Return currently executing propagator.
Definition: core.hpp:3357
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3664
void * rrealloc(void *b, size_t n, size_t m)
Reallocate memory block starting at b from size n to size s.
Definition: core.hpp:2753
PostInfo(Home home)
Set information.
Definition: core.hpp:3377
Base-class for both propagators and branchers.
Definition: core.hpp:682
Statistics for execution of status
Definition: core.hpp:1620
What what(void) const
Return what is currently executing.
Definition: core.hpp:3353
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4348
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3463
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Gecode::IntSet d(v, 7)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2783
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:4497
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:739
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition: core.hpp:736
The literal is subsumed.
Definition: core.hpp:1268
Gecode::FloatVal c(-8, 8)
Maximal cost value.
Definition: core.hpp:570
Configuration class for variable implementations without index structure.
Definition: core.hpp:178
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3708
Handles for local (space-shared) objects.
Definition: core.hpp:1487
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1364
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3553
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:4502
Global propagator information.
Definition: gpi.hpp:43
void reset(void)
Reset information.
Definition: core.hpp:4507
void reset(void)
Reset information.
Definition: core.hpp:4469
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition: core.hpp:4810
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:49
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:3276
struct Gecode::Space::@55::@56 p
Data only available during propagation or branching.
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4137
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4093
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3624
union Gecode::@554::NNF::@60 u
Union depending on nodetype t.
Execution has resulted in failure.
Definition: core.hpp:538
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition: core.hpp:4772
StatusStatistics(void)
Initialize.
Definition: core.hpp:4474
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3118
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:3005
void other(void)
Record that nothing is known at this point.
Definition: core.hpp:3349
Statistics for execution of clone
Definition: core.hpp:1640
Class to set group information when a post function is executed.
Definition: core.hpp:997
bool operator!=(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:321
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
MetaInfo(unsigned long int r, unsigned long int s, unsigned long int f, const Space *l, NoGoods &ng)
Constructor for restart-based engine.
Definition: core.hpp:3087
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:3080
SharedHandle & operator=(const SharedHandle &sh)
Assignment operator maintaining reference count.
Definition: core.hpp:3035
Type type(void) const
Return type of information.
Definition: core.hpp:3099
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3963
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1022
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3266
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1754
void fail(void)
Fail space.
Definition: core.hpp:3949
Group(void)
Constructor.
Definition: core.cpp:729
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:201
const Brancher & brancher(void) const
Return currently executing brancher.
Definition: core.hpp:3363
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3967
const Space * l
Last solution found.
Definition: core.hpp:1563
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4857
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3972
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:3478
CloneStatistics(void)
Initialize.
Definition: core.hpp:4493
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3658
Home(Space &s, Propagator *p=NULL, PropagatorGroup pg=PropagatorGroup::def, BrancherGroup bg=BrancherGroup::def)
Initialize the home with space s and propagator p and group g.
Definition: core.hpp:3291
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:156
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:4457
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3468
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1024
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:746
Group baseclass for controlling actors.
Definition: core.hpp:727
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:3915
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3412
Information is provided by a portfolio-based engine.
Definition: core.hpp:1549
Council(void)
Default constructor.
Definition: core.hpp:3826
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
Definition: core.hpp:3651
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3799
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
Execution information.
Definition: core.hpp:957
static unsigned int next
Next group id.
Definition: core.hpp:743
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:3295
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:4782
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3685
Branchers(Space &home, BrancherGroup g)
Initialize.
Definition: core.hpp:4862
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
IntPropLevel sm(IntPropLevel ipl)
Extract speed or memory from propagation level.
Definition: ipl.hpp:47
Exception: too many branchers
Definition: exception.hpp:97
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3490
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3253
Mod
Propagation cost modifier.
Definition: core.hpp:576
Single _b(1, 4)
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:4868
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3712
~SharedHandle(void)
Destructor that maintains reference count.
Definition: core.hpp:3058
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4847
BrancherGroup branchergroup(void) const
Return brancher group.
Definition: core.hpp:3328
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:3453
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3123
void update(Space &home, bool share, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3675
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Definition: core.hpp:974
Advisor forces rescheduling of propagator.
Definition: core.hpp:542
NoGoods(void)
Initialize.
Definition: core.hpp:3069
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2809
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3548
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:4777
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:3042
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4878
What
What is currently executing.
Definition: core.hpp:962
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:67
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:841
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2745
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition: core.hpp:3368
BrancherGroup(void)
Constructor.
Definition: core.hpp:4799
ActualCost ac
Actual cost.
Definition: core.hpp:573
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:3304
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4559
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:4514
const ExecInfo & operator()(const Space &home) const
Provide access to execution information.
Definition: core.hpp:3793
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:277
Brancher(Home home)
Constructor for creation.
Definition: core.hpp:3526
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:3316
virtual ~Object(void)
Delete shared object.
Definition: core.hpp:3000
Propagator & propagator(void) const
Return the advisor&#39;s propagator.
Definition: core.hpp:3776
Choice for performing commit
Definition: core.hpp:1332
unsigned int gid
Group identifier.
Definition: gpi.hpp:51
struct Gecode::Space::@55::@57 c
Data available only during copying.
The literal is failed.
Definition: core.hpp:1267
No-goods recorded from restarts.
Definition: core.hpp:1517
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3281
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3783
Propagation cost.
Definition: core.hpp:550
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:3921
Archive representation
Definition: archive.hpp:45
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition: core.hpp:3750
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2869
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:4824
ExecStatus
Definition: core.hpp:536
const unsigned long int r
Number of restarts.
Definition: core.hpp:1557
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition: var-type.hpp:889
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition: core.hpp:4519
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void enable(void)
Enable propagator.
Definition: core.hpp:3422
#define forceinline
Definition: config.hpp:173
void fail(Info &c)
Increment failure count.
Definition: gpi.hpp:312
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4550
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:3103
SharedHandle::Object * shared
Linked list of shared objects.
Definition: core.hpp:1765
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:909
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1535
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:4815
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition: core.hpp:4271
Base-class for freelist-managed objects.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:3271
unsigned int asset(void) const
Return number of asset in portfolio.
Definition: core.hpp:3128
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4851
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:543
Variable implementation disposer
Definition: core.hpp:268
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2773
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:147
The shared object.
Definition: core.hpp:88
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:315
Execution is okay.
Definition: core.hpp:540
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3740
Propagation has not computed fixpoint.
Definition: core.hpp:539
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:4820
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:911
void fail(void)
Mark space as failed.
Definition: core.hpp:3958
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3724
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:3320
bool in(void) const
Check whether this is a real group (and not just default)
Definition: core.hpp:4742
bool operator==(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:298
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:4484
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:79
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4586
Propagator(Home home)
Constructor for posting.
Definition: core.hpp:3432
Gecode toplevel namespace
static Group all
Group of all actors.
Definition: core.hpp:768
Information passed by meta search engines.
Definition: core.hpp:1542
BrancherGroup bg
A brancher group.
Definition: core.hpp:915
friend class Propagators
Definition: core.hpp:1676
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:4149
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1748
Class for storing timed-decay value.
Definition: gpi.hpp:46
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1763
Group of propagators.
Definition: core.hpp:778
ActorProperty
Actor properties.
Definition: core.hpp:617
VarImp * next(void) const
Return next copied variable.
Space is failed
Definition: core.hpp:1611
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:3072
ActualCost
The actual cost values that are used.
Definition: core.hpp:554
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition: core.hpp:734
unsigned long int n
Number of no-goods.
Definition: core.hpp:1520
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2768
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
const unsigned long int s
Number of solutions since last restart.
Definition: core.hpp:1559
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
Home class for posting propagators
Definition: core.hpp:905
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4067
Base class for heap allocated objects.
Definition: heap.hpp:344
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4590
Shared object for several memory areas.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
A & advisor(void) const
Return advisor.
Definition: core.hpp:3929
const unsigned long int f
Number of failures since last restart.
Definition: core.hpp:1561
Object(void)
Initialize.
Definition: core.hpp:2997
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:205
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:4478
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:48
bool advise(Space &home, ModEvent me, Delta &d)
Run advisors when variable implementation has been modified with modification event me and domain cha...
Definition: core.hpp:4361
const unsigned int a
Number of asset in portfolio.
Definition: core.hpp:1570
CommitStatistics(void)
Initialize.
Definition: core.hpp:4510
void disable(void)
Disable propagator.
Definition: core.hpp:3417
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:145
Base class for Variable type disposer.
Definition: core.hpp:253
GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3427
ExecStatus ES_NOFIX_DISPOSE_FORCE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be forcefully rescheduled
Definition: core.hpp:3813
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:104
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2749
unsigned int gid
The group id.
Definition: core.hpp:740
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:4248
Space is solved (no brancher left)
Definition: core.hpp:1612
No-good literal recorded during search.
Definition: core.hpp:1260
~LocalHandle(void)
Destructor.
Definition: core.hpp:3669