Generated on Tue Jan 19 2021 06:15:49 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  * Samuel Gagnon <samuel.gagnon92@gmail.com>
11  *
12  * Copyright:
13  * Christian Schulte, 2002
14  * Guido Tack, 2003
15  * Mikael Lagerkvist, 2006
16  * LOGIS, s.r.o., 2009
17  * Samuel Gagnon, 2018
18  *
19  * Bugfixes provided by:
20  * Alexander Samoilov <alexander_samoilov@yahoo.com>
21  *
22  * This file is part of Gecode, the generic constraint
23  * development environment:
24  * http://www.gecode.org
25  *
26  * Permission is hereby granted, free of charge, to any person obtaining
27  * a copy of this software and associated documentation files (the
28  * "Software"), to deal in the Software without restriction, including
29  * without limitation the rights to use, copy, modify, merge, publish,
30  * distribute, sublicense, and/or sell copies of the Software, and to
31  * permit persons to whom the Software is furnished to do so, subject to
32  * the following conditions:
33  *
34  * The above copyright notice and this permission notice shall be
35  * included in all copies or substantial portions of the Software.
36  *
37  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
38  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
39  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
40  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
41  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
42  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
43  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44  *
45  */
46 
47 #include <iostream>
48 
49 namespace Gecode {
50 
51  class Space;
52 
61  typedef int ModEvent;
63 
65  const ModEvent ME_GEN_FAILED = -1;
67  const ModEvent ME_GEN_NONE = 0;
69  const ModEvent ME_GEN_ASSIGNED = 1;
70 
72  typedef int PropCond;
74  const PropCond PC_GEN_NONE = -1;
76  const PropCond PC_GEN_ASSIGNED = 0;
78 
89  typedef int ModEventDelta;
90 
91 }
92 
94 
95 namespace Gecode {
96 
99  public:
101  static const int idx_c = -1;
103  static const int idx_d = -1;
107  static const int free_bits = 0;
109  static const int med_fst = 0;
111  static const int med_lst = 0;
113  static const int med_mask = 0;
115  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
117  static bool med_update(ModEventDelta& med, ModEvent me);
118  };
119 
122  GECODE_NEVER; return 0;
123  }
124  forceinline bool
126  GECODE_NEVER; return false;
127  }
128 
129 
130  /*
131  * These are the classes of interest
132  *
133  */
134  class ActorLink;
135  class Actor;
136  class Propagator;
137  class SubscribedPropagators;
138  class LocalObject;
139  class Advisor;
140  class AFC;
141  class Choice;
142  class Brancher;
143  class Group;
144  class PropagatorGroup;
145  class BrancherGroup;
146  class PostInfo;
147  class ViewTraceInfo;
148  class PropagateTraceInfo;
149  class CommitTraceInfo;
150  class TraceRecorder;
151  class TraceFilter;
152  class Tracer;
153 
154  template<class A> class Council;
155  template<class A> class Advisors;
156  template<class VIC> class VarImp;
157 
158 
159  /*
160  * Variable implementations
161  *
162  */
163 
171  class VarImpBase {};
172 
180  public:
182  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
185  };
186 
193  template<class VarImp>
195  public:
197  VarImpDisposer(void);
199  virtual void dispose(Space& home, VarImpBase* x);
200  };
201 
203  class Delta {
204  template<class VIC> friend class VarImp;
205  private:
207  ModEvent me;
208  };
209 
217  template<class VIC>
218  class VarImp : public VarImpBase {
219  friend class Space;
220  friend class Propagator;
221  template<class VarImp> friend class VarImpDisposer;
222  friend class SubscribedPropagators;
223  private:
224  union {
242  } b;
243 
245  static const int idx_c = VIC::idx_c;
247  static const int idx_d = VIC::idx_d;
249  static const int free_bits = VIC::free_bits;
251  unsigned int entries;
253  unsigned int free_and_bits;
255  static const Gecode::PropCond pc_max = VIC::pc_max;
256 #ifdef GECODE_HAS_CBS
257  const unsigned var_id;
259 #endif
260 
261  union {
272  unsigned int idx[pc_max+1];
275  } u;
276 
278  ActorLink** actor(PropCond pc);
280  ActorLink** actorNonZero(PropCond pc);
282  unsigned int& idx(PropCond pc);
284  unsigned int idx(PropCond pc) const;
285 
292  void update(VarImp* x, ActorLink**& sub);
299  static void update(Space& home, ActorLink**& sub);
300 
302  void enter(Space& home, Propagator* p, PropCond pc);
304  void enter(Space& home, Advisor* a);
306  void resize(Space& home);
308  void remove(Space& home, Propagator* p, PropCond pc);
310  void remove(Space& home, Advisor* a);
311 
312 
313  protected:
315  void cancel(Space& home);
321  bool advise(Space& home, ModEvent me, Delta& d);
322  private:
324  void _fail(Space& home);
325  protected:
327  ModEvent fail(Space& home);
328 #ifdef GECODE_HAS_VAR_DISPOSE
329  static VarImp<VIC>* vars_d(Space& home);
332  static void vars_d(Space& home, VarImp<VIC>* x);
333 #endif
334 
335  public:
337  VarImp(Space& home);
339  VarImp(void);
340 
341 #ifdef GECODE_HAS_CBS
342  unsigned int id(void) const;
344 #endif
345 
347 
348 
360  void subscribe(Space& home, Propagator& p, PropCond pc,
361  bool assigned, ModEvent me, bool schedule);
363  void cancel(Space& home, Propagator& p, PropCond pc);
372  void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
374  void cancel(Space& home, Advisor& a, bool fail);
375 
382  unsigned int degree(void) const;
389  double afc(void) const;
391 
393 
394  VarImp(Space& home, VarImp& x);
397  bool copied(void) const;
399  VarImp* forward(void) const;
401  VarImp* next(void) const;
403 
405 
406 
413  static void schedule(Space& home, Propagator& p, ModEvent me,
414  bool force = false);
422  static void reschedule(Space& home, Propagator& p, PropCond pc,
423  bool assigned, ModEvent me);
425  static ModEvent me(const ModEventDelta& med);
427  static ModEventDelta med(ModEvent me);
429  static ModEvent me_combine(ModEvent me1, ModEvent me2);
431 
433 
434  static ModEvent modevent(const Delta& d);
437 
439 
440  unsigned int bits(void) const;
443  unsigned int& bits(void);
445 
446  protected:
448  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
449 
450  public:
452 
453  static void* operator new(size_t,Space&);
456  static void operator delete(void*,Space&);
458  static void operator delete(void*);
460  };
461 
462 
471  enum ExecStatus {
473  ES_FAILED = -1,
474  ES_NOFIX = 0,
475  ES_OK = 0,
476  ES_FIX = 1,
479  };
480 
485  class PropCost {
486  friend class Space;
487  public:
489  enum ActualCost {
490  AC_RECORD = 0,
491  AC_CRAZY_LO = 1,
492  AC_CRAZY_HI = 1,
493  AC_CUBIC_LO = 1,
494  AC_CUBIC_HI = 1,
495  AC_QUADRATIC_LO = 2,
496  AC_QUADRATIC_HI = 2,
497  AC_LINEAR_HI = 3,
498  AC_LINEAR_LO = 4,
499  AC_TERNARY_HI = 4,
500  AC_BINARY_HI = 5,
501  AC_TERNARY_LO = 5,
502  AC_BINARY_LO = 6,
503  AC_UNARY_LO = 6,
504  AC_UNARY_HI = 6,
505  AC_MAX = 6
506  };
509  public:
511  enum Mod {
512  LO,
513  HI
514  };
515  private:
517  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
519  PropCost(ActualCost ac);
520  public:
522  static PropCost record(void);
524  static PropCost crazy(PropCost::Mod m, unsigned int n);
526  static PropCost crazy(PropCost::Mod m, int n);
528  static PropCost cubic(PropCost::Mod m, unsigned int n);
530  static PropCost cubic(PropCost::Mod m, int n);
532  static PropCost quadratic(PropCost::Mod m, unsigned int n);
534  static PropCost quadratic(PropCost::Mod m, int n);
536  static PropCost linear(PropCost::Mod m, unsigned int n);
538  static PropCost linear(PropCost::Mod m, int n);
540  static PropCost ternary(PropCost::Mod m);
542  static PropCost binary(PropCost::Mod m);
544  static PropCost unary(PropCost::Mod m);
545  };
546 
547 
561  AP_DISPOSE = (1 << 0),
567  AP_WEAKLY = (1 << 1),
572  AP_VIEW_TRACE = (1 << 2),
577  AP_TRACE = (1 << 3)
578  };
579 
580 
588  class ActorLink {
589  friend class Actor;
590  friend class Propagator;
591  friend class Advisor;
592  friend class Brancher;
593  friend class LocalObject;
594  friend class Space;
595  template<class VIC> friend class VarImp;
596  private:
597  ActorLink* _next; ActorLink* _prev;
598  public:
600  ActorLink* prev(void) const; void prev(ActorLink*);
602  ActorLink* next(void) const; void next(ActorLink*);
603  ActorLink** next_ref(void);
605 
607  void init(void);
609  void unlink(void);
611  void head(ActorLink* al);
613  void tail(ActorLink* al);
615  bool empty(void) const;
617  template<class T> static ActorLink* cast(T* a);
619  template<class T> static const ActorLink* cast(const T* a);
620  };
621 
622 
628  friend class ActorLink;
629  friend class Space;
630  friend class Propagator;
631  friend class Advisor;
632  friend class Brancher;
633  friend class LocalObject;
634  template<class VIC> friend class VarImp;
635  template<class A> friend class Council;
636  private:
638  static Actor* cast(ActorLink* al);
640  static const Actor* cast(const ActorLink* al);
642  GECODE_KERNEL_EXPORT static Actor* sentinel;
643  public:
645  virtual Actor* copy(Space& home) = 0;
646 
648 
651  virtual size_t dispose(Space& home);
653  static void* operator new(size_t s, Space& home);
655  static void operator delete(void* p, Space& home);
657  public:
659  GECODE_KERNEL_EXPORT virtual ~Actor(void);
661  static void* operator new(size_t s);
663  static void operator delete(void* p);
664  };
665 
666  class Home;
667 
672  class Group {
673  friend class Home;
674  friend class Propagator;
675  friend class Brancher;
676  friend class ViewTraceInfo;
677  friend class PropagateTraceInfo;
678  friend class CommitTraceInfo;
679  protected:
681  static const unsigned int GROUPID_ALL = 0U;
683  static const unsigned int GROUPID_DEF = 1U;
685  static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
687  unsigned int gid;
690  static unsigned int next;
695  Group(unsigned int gid0);
696  public:
698 
701  Group(void);
703  Group(const Group& g);
705  Group& operator =(const Group& g);
707  unsigned int id(void) const;
709  bool in(Group a) const;
711  bool in(void) const;
715  static Group all;
718  static Group def;
719  };
720 
725  class PropagatorGroup : public Group {
726  friend class Propagator;
727  friend class ViewTraceInfo;
728  friend class PropagateTraceInfo;
729  protected:
731  PropagatorGroup(unsigned int gid);
732  public:
734 
735  PropagatorGroup(void);
740  PropagatorGroup& operator =(const PropagatorGroup& g);
742  Home operator ()(Space& home);
744 
748  PropagatorGroup& move(Space& home, PropagatorGroup g);
750  PropagatorGroup& move(Space& home, Propagator& p);
758  PropagatorGroup& move(Space& home, unsigned int id);
760 
762  bool operator ==(PropagatorGroup g) const;
765  bool operator !=(PropagatorGroup g) const;
768  unsigned int size(Space& home) const;
771  void kill(Space& home);
774  void disable(Space& home);
782  void enable(Space& home, bool s=true);
790  };
791 
796  class BrancherGroup : public Group {
797  friend class Brancher;
798  protected:
800  BrancherGroup(unsigned int gid);
801  public:
803 
804  BrancherGroup(void);
807  BrancherGroup(const BrancherGroup& g);
809  BrancherGroup& operator =(const BrancherGroup& g);
811  Home operator ()(Space& home);
813 
817  BrancherGroup& move(Space& home, BrancherGroup g);
819  BrancherGroup& move(Space& home, Brancher& b);
827  BrancherGroup& move(Space& home, unsigned int id);
829 
831  bool operator ==(BrancherGroup g) const;
834  bool operator !=(BrancherGroup g) const;
837  unsigned int size(Space& home) const;
840  void kill(Space& home);
848  };
849 
853  class Home {
854  friend class PostInfo;
855  protected:
864  public:
866 
867  Home(Space& s, Propagator* p=NULL,
872  Home& operator =(const Home& h);
874  operator Space&(void);
876 
878  Home operator ()(Propagator& p);
881  Home operator ()(PropagatorGroup pg);
883  Home operator ()(BrancherGroup bg);
885  Propagator* propagator(void) const;
887  PropagatorGroup propagatorgroup(void) const;
889  BrancherGroup branchergroup(void) const;
891 
893  bool failed(void) const;
896  void fail(void);
898  void notice(Actor& a, ActorProperty p, bool duplicate=false);
900  };
901 
906  friend class Space;
907  friend class PostInfo;
908  public:
910  enum What {
912  PROPAGATOR = 0,
914  BRANCHER = 1,
916  POST = 2,
918  OTHER = 3
919  };
920  protected:
922  ptrdiff_t who;
924  void propagator(Propagator& p);
926  void brancher(Brancher& b);
928  void post(PropagatorGroup g);
930  void other(void);
931  public:
933  What what(void) const;
935  const Propagator& propagator(void) const;
937  const Brancher& brancher(void) const;
939  PropagatorGroup post(void) const;
940  };
941 
945  class PostInfo {
946  protected:
949  public:
951  PostInfo(Home home);
953  ~PostInfo(void);
954  };
955 
960  friend class Space;
961  public:
963  enum Status {
964  FIX,
967  SUBSUMED
968  };
969  protected:
971  unsigned int i;
975  const Propagator* p;
979  PropagateTraceInfo(unsigned int i, PropagatorGroup g,
980  const Propagator* p, Status s);
981  public:
983  unsigned int id(void) const;
985  PropagatorGroup group(void) const;
987  const Propagator* propagator(void) const;
989  Status status(void) const;
990  };
991 
996  friend class Space;
997  protected:
999  const Brancher& b;
1001  const Choice& c;
1003  unsigned int a;
1005  CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1006  public:
1008  unsigned int id(void) const;
1010  BrancherGroup group(void) const;
1012  const Brancher& brancher(void) const;
1014  const Choice& choice(void) const;
1016  unsigned int alternative(void) const;
1017  };
1018 
1024  friend class ActorLink;
1025  friend class Space;
1026  template<class VIC> friend class VarImp;
1027  friend class Advisor;
1028  template<class A> friend class Council;
1030  friend class PropagatorGroup;
1031  private:
1032  union {
1036  size_t size;
1039  } u;
1041  void* gpi_disabled;
1043  static Propagator* cast(ActorLink* al);
1045  static const Propagator* cast(const ActorLink* al);
1047  void disable(Space& home);
1049  void enable(Space& home);
1050  protected:
1052  Propagator(Home home);
1054  Propagator(Space& home, Propagator& p);
1056  Propagator* fwd(void) const;
1058  Kernel::GPI::Info& gpi(void);
1059 
1060  public:
1062 
1063 
1071  virtual void reschedule(Space& home) = 0;
1095  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1097  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1105  ModEventDelta modeventdelta(void) const;
1142  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1145  virtual void advise(Space& home, Advisor& a);
1147 
1149  double afc(void) const;
1152 #ifdef GECODE_HAS_CBS
1153 
1155 
1161  typedef std::function<void(unsigned int prop_id, unsigned int var_id,
1163  int val, double dens)> SendMarginal;
1164  virtual void solndistrib(Space& home, SendMarginal send) const;
1172  typedef std::function<bool(unsigned int var_id)> InDecision;
1174  virtual void domainsizesum(InDecision in, unsigned int& size,
1175  unsigned int& size_b) const;
1177 #endif
1178 
1180  unsigned int id(void) const;
1183  PropagatorGroup group(void) const;
1185  void group(PropagatorGroup g);
1187  bool disabled(void) const;
1189  };
1190 
1191 
1199  template<class A>
1200  class Council {
1201  friend class Advisor;
1202  friend class Advisors<A>;
1203  private:
1205  mutable ActorLink* advisors;
1206  public:
1208  Council(void);
1210  Council(Space& home);
1212  bool empty(void) const;
1214  void update(Space& home, Council<A>& c);
1216  void dispose(Space& home);
1217  };
1218 
1219 
1224  template<class A>
1225  class Advisors {
1226  private:
1228  ActorLink* a;
1229  public:
1231  Advisors(const Council<A>& c);
1233  bool operator ()(void) const;
1235  void operator ++(void);
1237  A& advisor(void) const;
1238  };
1239 
1240 
1251  class Advisor : private ActorLink {
1252  template<class VIC> friend class VarImp;
1253  template<class A> friend class Council;
1254  template<class A> friend class Advisors;
1256  private:
1258  bool disposed(void) const;
1260  static Advisor* cast(ActorLink* al);
1262  static const Advisor* cast(const ActorLink* al);
1263  protected:
1265  Propagator& propagator(void) const;
1266  public:
1268  template<class A>
1269  Advisor(Space& home, Propagator& p, Council<A>& c);
1271  Advisor(Space& home, Advisor& a);
1273  const ViewTraceInfo& operator ()(const Space& home) const;
1274 
1276 
1277  template<class A>
1279  void dispose(Space& home, Council<A>& c);
1281  static void* operator new(size_t s, Space& home);
1283  static void operator delete(void* p, Space& home);
1285  private:
1286 #ifndef __GNUC__
1287  static void operator delete(void* p);
1289 #endif
1290  static void* operator new(size_t s);
1292  };
1293 
1294 
1300  private:
1302  void* nl;
1303  public:
1305  enum Status {
1308  NONE
1309  };
1311  NGL(void);
1313  NGL(Space& home);
1315  NGL(Space& home, NGL& ngl);
1317  virtual void subscribe(Space& home, Propagator& p) = 0;
1319  virtual void cancel(Space& home, Propagator& p) = 0;
1321  virtual void reschedule(Space& home, Propagator& p) = 0;
1323  virtual NGL::Status status(const Space& home) const = 0;
1325  virtual ExecStatus prune(Space& home) = 0;
1327  virtual NGL* copy(Space& home) = 0;
1330  virtual bool notice(void) const;
1332  virtual size_t dispose(Space& home);
1334 
1335  bool leaf(void) const;
1338  NGL* next(void) const;
1340  void leaf(bool l);
1342  void next(NGL* n);
1344  NGL* add(NGL* n, bool l);
1346 
1348  static void* operator new(size_t s, Space& home);
1351  static void operator delete(void* s, Space& home);
1353  static void operator delete(void* p);
1355  public:
1357  GECODE_KERNEL_EXPORT virtual ~NGL(void);
1359  static void* operator new(size_t s);
1360  };
1361 
1372  friend class Space;
1373  private:
1374  unsigned int bid;
1375  unsigned int alt;
1376 
1378  unsigned int id(void) const;
1379  protected:
1381  Choice(const Brancher& b, const unsigned int a);
1382  public:
1384  unsigned int alternatives(void) const;
1386  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1389  virtual void archive(Archive& e) const;
1390  };
1391 
1402  friend class ActorLink;
1403  friend class Space;
1404  friend class Choice;
1405  private:
1407  unsigned int bid;
1409  unsigned int gid;
1411  static Brancher* cast(ActorLink* al);
1413  static const Brancher* cast(const ActorLink* al);
1414  protected:
1416  Brancher(Home home);
1418  Brancher(Space& home, Brancher& b);
1419  public:
1421 
1422 
1430  virtual bool status(const Space& home) const = 0;
1438  virtual const Choice* choice(Space& home) = 0;
1440  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1447  virtual ExecStatus commit(Space& home, const Choice& c,
1448  unsigned int a) = 0;
1463  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1472  virtual void print(const Space& home, const Choice& c, unsigned int a,
1473  std::ostream& o) const;
1475 
1477  unsigned int id(void) const;
1480  BrancherGroup group(void) const;
1482  void group(BrancherGroup g);
1484  };
1485 
1492  class LocalObject : public Actor {
1493  friend class ActorLink;
1494  friend class Space;
1495  friend class LocalHandle;
1496  protected:
1498  LocalObject(Home home);
1500  LocalObject(Space& home, LocalObject& l);
1502  static LocalObject* cast(ActorLink* al);
1504  static const LocalObject* cast(const ActorLink* al);
1505  private:
1507  GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
1508  public:
1510  LocalObject* fwd(Space& home);
1511  };
1512 
1517  class LocalHandle {
1518  private:
1520  LocalObject* o;
1521  protected:
1523  LocalHandle(void);
1525  LocalHandle(LocalObject* lo);
1527  LocalHandle(const LocalHandle& lh);
1528  public:
1530  LocalHandle& operator =(const LocalHandle& lh);
1532  void update(Space& home, LocalHandle& lh);
1534  ~LocalHandle(void);
1535  protected:
1537  LocalObject* object(void) const;
1539  void object(LocalObject* n);
1540  };
1541 
1542 
1548  protected:
1550  unsigned long int n;
1551  public:
1553  NoGoods(void);
1556  virtual void post(Space& home) const;
1558  unsigned long int ng(void) const;
1560  void ng(unsigned long int n);
1562  virtual ~NoGoods(void);
1565  static NoGoods eng;
1566  };
1567 
1573  public:
1575  enum Type {
1579  PORTFOLIO
1580  };
1581  protected:
1583  const Type t;
1585 
1586  const unsigned long int r;
1589  const unsigned long int s;
1591  const unsigned long int f;
1593  const Space* l;
1595  const NoGoods& ng;
1597 
1599  const unsigned int a;
1602  public:
1604 
1605  MetaInfo(unsigned long int r,
1607  unsigned long int s,
1608  unsigned long int f,
1609  const Space* l,
1610  NoGoods& ng);
1612  MetaInfo(unsigned int a);
1614  Type type(void) const;
1617 
1618  unsigned long int restart(void) const;
1621  unsigned long int solution(void) const;
1623  unsigned long int fail(void) const;
1625  const Space* last(void) const;
1627  const NoGoods& nogoods(void) const;
1629 
1631  unsigned int asset(void) const;
1634  };
1635 
1644  };
1645 
1651  public:
1653  unsigned long int propagate;
1655  StatusStatistics(void);
1657  void reset(void);
1661  StatusStatistics& operator +=(const StatusStatistics& s);
1662  };
1663 
1669  public:
1671  CloneStatistics(void);
1673  void reset(void);
1677  CloneStatistics& operator +=(const CloneStatistics& s);
1678  };
1679 
1685  public:
1687  CommitStatistics(void);
1689  void reset(void);
1693  CommitStatistics& operator +=(const CommitStatistics& s);
1694  };
1695 
1696 
1697 
1702  friend class Actor;
1703  friend class Propagator;
1704  friend class PropagatorGroup;
1705  friend class Propagators;
1706  friend class Brancher;
1707  friend class BrancherGroup;
1708  friend class Branchers;
1709  friend class Advisor;
1710  template <class A> friend class Council;
1711  template<class VIC> friend class VarImp;
1712  template<class VarImp> friend class VarImpDisposer;
1713  friend class LocalObject;
1714  friend class Region;
1715  friend class AFC;
1716  friend class PostInfo;
1717  friend GECODE_KERNEL_EXPORT
1718  void trace(Home home, TraceFilter tf, int te, Tracer& t);
1719  private:
1724 #ifdef GECODE_HAS_CBS
1725  unsigned int var_id_counter;
1727 #endif
1728  ActorLink pl;
1731  ActorLink bl;
1737  Brancher* b_status;
1749  Brancher* b_commit;
1751  Brancher* brancher(unsigned int id);
1752 
1754  void kill(Brancher& b);
1756  void kill(Propagator& p);
1757 
1760  void kill_brancher(unsigned int id);
1761 
1763  static const unsigned reserved_bid = 0U;
1764 
1766  static const unsigned int sc_bits = 2;
1768  static const unsigned int sc_fast = 0;
1770  static const unsigned int sc_disabled = 1;
1772  static const unsigned int sc_trace = 2;
1773 
1774  union {
1776  struct {
1798  unsigned int bid_sc;
1800  unsigned int n_sub;
1803  } p;
1805  struct {
1812  } c;
1813  } pc;
1815  void enqueue(Propagator* p);
1820 #ifdef GECODE_HAS_VAR_DISPOSE
1824  VarImpBase* _vars_d[AllVarConf::idx_d];
1826  template<class VIC> VarImpBase* vars_d(void) const;
1828  template<class VIC> void vars_d(VarImpBase* x);
1829 #endif
1830  void update(ActorLink** sub);
1833 
1835  Actor** d_fst;
1837  Actor** d_cur;
1839  Actor** d_lst;
1840 
1842  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1844  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1846  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1847 
1861  GECODE_KERNEL_EXPORT Space* _clone(void);
1862 
1896  void _commit(const Choice& c, unsigned int a);
1897 
1929  void _trycommit(const Choice& c, unsigned int a);
1930 
1933  TraceRecorder* findtracerecorder(void);
1934 
1942  void ap_notice_dispose(Actor* a, bool d);
1950  void ap_ignore_dispose(Actor* a, bool d);
1951 
1952  public:
1958  Space(void);
1968  Space(Space& s);
1974  virtual ~Space(void);
1981  virtual Space* copy(void) = 0;
1992  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2017  virtual bool master(const MetaInfo& mi);
2044  virtual bool slave(const MetaInfo& mi);
2045 
2046  /*
2047  * Member functions for search engines
2048  *
2049  */
2050 
2063  SpaceStatus status(StatusStatistics& stat=unused_status);
2064 
2097  const Choice* choice(void);
2098 
2109  const Choice* choice(Archive& e) const;
2110 
2126  Space* clone(CloneStatistics& stat=unused_clone) const;
2127 
2162  void commit(const Choice& c, unsigned int a,
2163  CommitStatistics& stat=unused_commit);
2196  void trycommit(const Choice& c, unsigned int a,
2197  CommitStatistics& stat=unused_commit);
2217  NGL* ngl(const Choice& c, unsigned int a);
2218 
2234  void print(const Choice& c, unsigned int a, std::ostream& o) const;
2235 
2245  void notice(Actor& a, ActorProperty p, bool duplicate=false);
2254  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2255 
2256 
2267  ExecStatus ES_SUBSUMED(Propagator& p);
2282  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
2293  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2304  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2305 
2316  template<class A>
2317  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
2328  template<class A>
2329  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
2341  template<class A>
2342  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
2343 
2351  void fail(void);
2360  bool failed(void) const;
2365  bool stable(void) const;
2366 
2368 
2369  Home operator ()(Propagator& p);
2372  Home operator ()(PropagatorGroup pg);
2374  Home operator ()(BrancherGroup bg);
2376 
2388  template<class T>
2389  T* alloc(long unsigned int n);
2396  template<class T>
2397  T* alloc(long int n);
2404  template<class T>
2405  T* alloc(unsigned int n);
2412  template<class T>
2413  T* alloc(int n);
2423  template<class T>
2424  void free(T* b, long unsigned int n);
2434  template<class T>
2435  void free(T* b, long int n);
2445  template<class T>
2446  void free(T* b, unsigned int n);
2456  template<class T>
2457  void free(T* b, int n);
2469  template<class T>
2470  T* realloc(T* b, long unsigned int n, long unsigned int m);
2482  template<class T>
2483  T* realloc(T* b, long int n, long int m);
2495  template<class T>
2496  T* realloc(T* b, unsigned int n, unsigned int m);
2508  template<class T>
2509  T* realloc(T* b, int n, int m);
2517  template<class T>
2518  T** realloc(T** b, long unsigned int n, long unsigned int m);
2526  template<class T>
2527  T** realloc(T** b, long int n, long int m);
2535  template<class T>
2536  T** realloc(T** b, unsigned int n, unsigned int m);
2544  template<class T>
2545  T** realloc(T** b, int n, int m);
2547  void* ralloc(size_t s);
2549  void rfree(void* p, size_t s);
2551  void* rrealloc(void* b, size_t n, size_t m);
2553  template<size_t> void* fl_alloc(void);
2559  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2561 
2563 
2566  template<class T>
2567  T& construct(void);
2573  template<class T, typename A1>
2574  T& construct(A1 const& a1);
2580  template<class T, typename A1, typename A2>
2581  T& construct(A1 const& a1, A2 const& a2);
2587  template<class T, typename A1, typename A2, typename A3>
2588  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2594  template<class T, typename A1, typename A2, typename A3, typename A4>
2595  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2601  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2602  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2604 
2606 
2607  void afc_decay(double d);
2610  double afc_decay(void) const;
2612  GECODE_KERNEL_EXPORT void afc_unshare(void);
2614 
2615  protected:
2621  class Propagators {
2622  private:
2624  Space& home;
2626  ActorLink* q;
2628  ActorLink* c;
2630  ActorLink* e;
2631  public:
2633  Propagators(Space& home);
2635  bool operator ()(void) const;
2637  void operator ++(void);
2639  Propagator& propagator(void) const;
2640  };
2647  private:
2649  Space& home;
2651  ActorLink* q;
2653  ActorLink* c;
2655  ActorLink* e;
2656  public:
2658  ScheduledPropagators(Space& home);
2660  bool operator ()(void) const;
2662  void operator ++(void);
2664  Propagator& propagator(void) const;
2665  };
2672  private:
2674  ActorLink* c;
2676  ActorLink* e;
2677  public:
2679  IdlePropagators(Space& home);
2681  bool operator ()(void) const;
2683  void operator ++(void);
2685  Propagator& propagator(void) const;
2686  };
2692  class Branchers {
2693  private:
2695  ActorLink* c;
2697  ActorLink* e;
2698  public:
2700  Branchers(Space& home);
2702  bool operator ()(void) const;
2704  void operator ++(void);
2706  Brancher& brancher(void) const;
2707  };
2708  };
2709 
2711  class Propagators {
2712  private:
2714  Space::Propagators ps;
2716  PropagatorGroup g;
2717  public:
2719  Propagators(const Space& home, PropagatorGroup g);
2721  bool operator ()(void) const;
2723  void operator ++(void);
2725  const Propagator& propagator(void) const;
2726  };
2727 
2729  class Branchers {
2730  private:
2732  Space::Branchers bs;
2734  BrancherGroup g;
2735  public:
2737  Branchers(const Space& home, BrancherGroup g);
2739  bool operator ()(void) const;
2741  void operator ++(void);
2743  const Brancher& brancher(void) const;
2744  };
2745 
2746 
2747 
2748 
2749  /*
2750  * Memory management
2751  *
2752  */
2753 
2754  // Space allocation: general space heaps and free lists
2755  forceinline void*
2756  Space::ralloc(size_t s) {
2757  return mm.alloc(ssd.data().sm,s);
2758  }
2759  forceinline void
2760  Space::rfree(void* p, size_t s) {
2761  return mm.reuse(p,s);
2762  }
2763  forceinline void*
2764  Space::rrealloc(void* _b, size_t n, size_t m) {
2765  char* b = static_cast<char*>(_b);
2766  if (n < m) {
2767  char* p = static_cast<char*>(ralloc(m));
2768  memcpy(p,b,n);
2769  rfree(b,n);
2770  return p;
2771  } else {
2772  rfree(b+m,m-n);
2773  return b;
2774  }
2775  }
2776 
2777  template<size_t s>
2778  forceinline void*
2780  return mm.template fl_alloc<s>(ssd.data().sm);
2781  }
2782  template<size_t s>
2783  forceinline void
2785  mm.template fl_dispose<s>(f,l);
2786  }
2787 
2788  /*
2789  * Typed allocation routines
2790  *
2791  */
2792  template<class T>
2793  forceinline T*
2794  Space::alloc(long unsigned int n) {
2795  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2796  for (long unsigned int i=0; i<n; i++)
2797  (void) new (p+i) T();
2798  return p;
2799  }
2800  template<class T>
2801  forceinline T*
2802  Space::alloc(long int n) {
2803  assert(n >= 0);
2804  return alloc<T>(static_cast<long unsigned int>(n));
2805  }
2806  template<class T>
2807  forceinline T*
2808  Space::alloc(unsigned int n) {
2809  return alloc<T>(static_cast<long unsigned int>(n));
2810  }
2811  template<class T>
2812  forceinline T*
2814  assert(n >= 0);
2815  return alloc<T>(static_cast<long unsigned int>(n));
2816  }
2817 
2818  template<class T>
2819  forceinline void
2820  Space::free(T* b, long unsigned int n) {
2821  for (long unsigned int i=0; i<n; i++)
2822  b[i].~T();
2823  rfree(b,n*sizeof(T));
2824  }
2825  template<class T>
2826  forceinline void
2827  Space::free(T* b, long int n) {
2828  assert(n >= 0);
2829  free<T>(b,static_cast<long unsigned int>(n));
2830  }
2831  template<class T>
2832  forceinline void
2833  Space::free(T* b, unsigned int n) {
2834  free<T>(b,static_cast<long unsigned int>(n));
2835  }
2836  template<class T>
2837  forceinline void
2838  Space::free(T* b, int n) {
2839  assert(n >= 0);
2840  free<T>(b,static_cast<long unsigned int>(n));
2841  }
2842 
2843  template<class T>
2844  forceinline T*
2845  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2846  if (n < m) {
2847  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2848  for (long unsigned int i=0; i<n; i++)
2849  (void) new (p+i) T(b[i]);
2850  for (long unsigned int i=n; i<m; i++)
2851  (void) new (p+i) T();
2852  free<T>(b,n);
2853  return p;
2854  } else {
2855  free<T>(b+m,m-n);
2856  return b;
2857  }
2858  }
2859  template<class T>
2860  forceinline T*
2861  Space::realloc(T* b, long int n, long int m) {
2862  assert((n >= 0) && (m >= 0));
2863  return realloc<T>(b,static_cast<long unsigned int>(n),
2864  static_cast<long unsigned int>(m));
2865  }
2866  template<class T>
2867  forceinline T*
2868  Space::realloc(T* b, unsigned int n, unsigned int m) {
2869  return realloc<T>(b,static_cast<long unsigned int>(n),
2870  static_cast<long unsigned int>(m));
2871  }
2872  template<class T>
2873  forceinline T*
2874  Space::realloc(T* b, int n, int m) {
2875  assert((n >= 0) && (m >= 0));
2876  return realloc<T>(b,static_cast<long unsigned int>(n),
2877  static_cast<long unsigned int>(m));
2878  }
2879 
2880 #define GECODE_KERNEL_REALLOC(T) \
2881  template<> \
2882  forceinline T* \
2883  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2884  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2885  } \
2886  template<> \
2887  forceinline T* \
2888  Space::realloc<T>(T* b, long int n, long int m) { \
2889  assert((n >= 0) && (m >= 0)); \
2890  return realloc<T>(b,static_cast<long unsigned int>(n), \
2891  static_cast<long unsigned int>(m)); \
2892  } \
2893  template<> \
2894  forceinline T* \
2895  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2896  return realloc<T>(b,static_cast<long unsigned int>(n), \
2897  static_cast<long unsigned int>(m)); \
2898  } \
2899  template<> \
2900  forceinline T* \
2901  Space::realloc<T>(T* b, int n, int m) { \
2902  assert((n >= 0) && (m >= 0)); \
2903  return realloc<T>(b,static_cast<long unsigned int>(n), \
2904  static_cast<long unsigned int>(m)); \
2905  }
2906 
2907  GECODE_KERNEL_REALLOC(bool)
2908  GECODE_KERNEL_REALLOC(signed char)
2909  GECODE_KERNEL_REALLOC(unsigned char)
2910  GECODE_KERNEL_REALLOC(signed short int)
2911  GECODE_KERNEL_REALLOC(unsigned short int)
2912  GECODE_KERNEL_REALLOC(signed int)
2913  GECODE_KERNEL_REALLOC(unsigned int)
2914  GECODE_KERNEL_REALLOC(signed long int)
2915  GECODE_KERNEL_REALLOC(unsigned long int)
2916  GECODE_KERNEL_REALLOC(float)
2917  GECODE_KERNEL_REALLOC(double)
2918 
2919 #undef GECODE_KERNEL_REALLOC
2920 
2921  template<class T>
2922  forceinline T**
2923  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2924  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2925  }
2926  template<class T>
2927  forceinline T**
2928  Space::realloc(T** b, long int n, long int m) {
2929  assert((n >= 0) && (m >= 0));
2930  return realloc<T*>(b,static_cast<long unsigned int>(n),
2931  static_cast<long unsigned int>(m));
2932  }
2933  template<class T>
2934  forceinline T**
2935  Space::realloc(T** b, unsigned int n, unsigned int m) {
2936  return realloc<T*>(b,static_cast<long unsigned int>(n),
2937  static_cast<long unsigned int>(m));
2938  }
2939  template<class T>
2940  forceinline T**
2941  Space::realloc(T** b, int n, int m) {
2942  assert((n >= 0) && (m >= 0));
2943  return realloc<T*>(b,static_cast<long unsigned int>(n),
2944  static_cast<long unsigned int>(m));
2945  }
2946 
2947 
2948 #ifdef GECODE_HAS_VAR_DISPOSE
2949  template<class VIC>
2951  Space::vars_d(void) const {
2952  return _vars_d[VIC::idx_d];
2953  }
2954  template<class VIC>
2955  forceinline void
2956  Space::vars_d(VarImpBase* x) {
2957  _vars_d[VIC::idx_d] = x;
2958  }
2959 #endif
2960 
2961  // Space allocated entities: Actors, variable implementations, and advisors
2962  forceinline void
2963  Actor::operator delete(void*) {}
2964  forceinline void
2965  Actor::operator delete(void*, Space&) {}
2966  forceinline void*
2967  Actor::operator new(size_t s, Space& home) {
2968  return home.ralloc(s);
2969  }
2970 
2971  template<class VIC>
2972  forceinline void
2973  VarImp<VIC>::operator delete(void*) {}
2974  template<class VIC>
2975  forceinline void
2976  VarImp<VIC>::operator delete(void*, Space&) {}
2977  template<class VIC>
2978  forceinline void*
2979  VarImp<VIC>::operator new(size_t s, Space& home) {
2980  return home.ralloc(s);
2981  }
2982 
2983 #ifndef __GNUC__
2984  forceinline void
2985  Advisor::operator delete(void*) {}
2986 #endif
2987  forceinline void
2988  Advisor::operator delete(void*, Space&) {}
2989  forceinline void*
2990  Advisor::operator new(size_t s, Space& home) {
2991  return home.ralloc(s);
2992  }
2993 
2994  forceinline void
2995  NGL::operator delete(void*) {}
2996  forceinline void
2997  NGL::operator delete(void*, Space&) {}
2998  forceinline void*
2999  NGL::operator new(size_t s, Space& home) {
3000  return home.ralloc(s);
3001  }
3002 
3003 
3004  /*
3005  * No-goods
3006  *
3007  */
3008  forceinline
3010  : n(0) {}
3011  forceinline unsigned long int
3012  NoGoods::ng(void) const {
3013  return n;
3014  }
3015  forceinline void
3016  NoGoods::ng(unsigned long int n0) {
3017  n=n0;
3018  }
3019  forceinline
3021 
3022 
3023  /*
3024  * Information from meta search engines
3025  */
3026  forceinline
3027  MetaInfo::MetaInfo(unsigned long int r0,
3028  unsigned long int s0,
3029  unsigned long int f0,
3030  const Space* l0,
3031  NoGoods& ng0)
3032  : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3033 
3034  forceinline
3035  MetaInfo::MetaInfo(unsigned int a0)
3036  : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
3037 
3039  MetaInfo::type(void) const {
3040  return t;
3041  }
3042  forceinline unsigned long int
3043  MetaInfo::restart(void) const {
3044  assert(type() == RESTART);
3045  return r;
3046  }
3047  forceinline unsigned long int
3048  MetaInfo::solution(void) const {
3049  assert(type() == RESTART);
3050  return s;
3051  }
3052  forceinline unsigned long int
3053  MetaInfo::fail(void) const {
3054  assert(type() == RESTART);
3055  return f;
3056  }
3057  forceinline const Space*
3058  MetaInfo::last(void) const {
3059  assert(type() == RESTART);
3060  return l;
3061  }
3062  forceinline const NoGoods&
3063  MetaInfo::nogoods(void) const {
3064  assert(type() == RESTART);
3065  return ng;
3066  }
3067  forceinline unsigned int
3068  MetaInfo::asset(void) const {
3069  assert(type() == PORTFOLIO);
3070  return a;
3071  }
3072 
3073 
3074 
3075  /*
3076  * ActorLink
3077  *
3078  */
3080  ActorLink::prev(void) const {
3081  return _prev;
3082  }
3083 
3085  ActorLink::next(void) const {
3086  return _next;
3087  }
3088 
3091  return &_next;
3092  }
3093 
3094  forceinline void
3096  _prev = al;
3097  }
3098 
3099  forceinline void
3101  _next = al;
3102  }
3103 
3104  forceinline void
3106  ActorLink* p = _prev; ActorLink* n = _next;
3107  p->_next = n; n->_prev = p;
3108  }
3109 
3110  forceinline void
3112  _next = this; _prev =this;
3113  }
3114 
3115  forceinline void
3117  // Inserts al at head of link-chain (that is, after this)
3118  ActorLink* n = _next;
3119  this->_next = a; a->_prev = this;
3120  a->_next = n; n->_prev = a;
3121  }
3122 
3123  forceinline void
3125  // Inserts al at tail of link-chain (that is, before this)
3126  ActorLink* p = _prev;
3127  a->_next = this; this->_prev = a;
3128  p->_next = a; a->_prev = p;
3129  }
3130 
3131  forceinline bool
3132  ActorLink::empty(void) const {
3133  return _next == this;
3134  }
3135 
3136  template<class T>
3139  // Turning al into a reference is for gcc, assume is for MSVC
3140  GECODE_NOT_NULL(a);
3141  ActorLink& t = *a;
3142  return static_cast<ActorLink*>(&t);
3143  }
3144 
3145  template<class T>
3146  forceinline const ActorLink*
3147  ActorLink::cast(const T* a) {
3148  // Turning al into a reference is for gcc, assume is for MSVC
3149  GECODE_NOT_NULL(a);
3150  const ActorLink& t = *a;
3151  return static_cast<const ActorLink*>(&t);
3152  }
3153 
3154 
3155  /*
3156  * Actor
3157  *
3158  */
3160  Actor::cast(ActorLink* al) {
3161  // Turning al into a reference is for gcc, assume is for MSVC
3162  GECODE_NOT_NULL(al);
3163  ActorLink& t = *al;
3164  return static_cast<Actor*>(&t);
3165  }
3166 
3167  forceinline const Actor*
3168  Actor::cast(const ActorLink* al) {
3169  // Turning al into a reference is for gcc, assume is for MSVC
3170  GECODE_NOT_NULL(al);
3171  const ActorLink& t = *al;
3172  return static_cast<const Actor*>(&t);
3173  }
3174 
3175  forceinline void
3176  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3177  s.notice(a,p,duplicate);
3178  }
3179 
3182  // Clone is only const for search engines. During cloning, several data
3183  // structures are updated (e.g. forwarding pointers), so we have to
3184  // cast away the constness.
3185  return const_cast<Space*>(this)->_clone();
3186  }
3187 
3188  forceinline void
3189  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3190  _commit(c,a);
3191  }
3192 
3193  forceinline void
3194  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3195  _trycommit(c,a);
3196  }
3197 
3198  forceinline double
3199  Space::afc_decay(void) const {
3200  return ssd.data().gpi.decay();
3201  }
3202 
3203  forceinline void
3205  ssd.data().gpi.decay(d);
3206  }
3207 
3208  forceinline size_t
3210  return sizeof(*this);
3211  }
3212 
3213 
3214  /*
3215  * Home for posting actors
3216  *
3217  */
3218  forceinline
3220  PropagatorGroup pg0, BrancherGroup bg0)
3221  : s(s0), p(p0), pg(pg0), bg(bg0) {}
3222  forceinline Home&
3224  s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3225  return *this;
3226  }
3227  forceinline
3228  Home::operator Space&(void) {
3229  return s;
3230  }
3233  return Home(s,&p);
3234  }
3237  return Home(s,NULL,pg,BrancherGroup::def);
3238  }
3241  return Home(s,NULL,PropagatorGroup::def,bg);
3242  }
3245  return Home(*this,&p);
3246  }
3249  return Home(*this,NULL,pg,BrancherGroup::def);
3250  }
3253  return Home(*this,NULL,PropagatorGroup::def,bg);
3254  }
3256  Home::propagator(void) const {
3257  return p;
3258  }
3261  return pg;
3262  }
3264  Home::branchergroup(void) const {
3265  return bg;
3266  }
3267 
3268  /*
3269  * View trace information
3270  *
3271  */
3272  forceinline void
3274  who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3275  }
3276  forceinline void
3278  who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3279  }
3280  forceinline void
3282  who = (g.id() << 2) | POST;
3283  }
3284  forceinline void
3286  who = OTHER;
3287  }
3289  ViewTraceInfo::what(void) const {
3290  return static_cast<What>(who & 3);
3291  }
3292  forceinline const Propagator&
3294  assert(what() == PROPAGATOR);
3295  // Because PROPAGATOR == 0
3296  return *reinterpret_cast<Propagator*>(who);
3297  }
3298  forceinline const Brancher&
3300  assert(what() == BRANCHER);
3301  return *reinterpret_cast<Brancher*>(who & ~3);
3302  }
3304  ViewTraceInfo::post(void) const {
3305  assert(what() == POST);
3306  return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3307  }
3308 
3309  /*
3310  * Post information
3311  */
3312  forceinline
3313  PostInfo::PostInfo(Home home) : h(home) {
3314  h.pc.p.vti.post(home.propagatorgroup());
3315  }
3316  forceinline
3318  h.pc.p.vti.other();
3319  }
3320 
3321  /*
3322  * Propagate trace information
3323  *
3324  */
3325  forceinline
3327  const Propagator* p0, Status s0)
3328  : i(i0), g(g0), p(p0), s(s0) {}
3329  forceinline unsigned int
3331  return i;
3332  }
3335  return g;
3336  }
3337  forceinline const Propagator*
3339  return p;
3340  }
3343  return s;
3344  }
3345 
3346 
3347  /*
3348  * Commit trace information
3349  *
3350  */
3351  forceinline
3353  unsigned int a0)
3354  : b(b0), c(c0), a(a0) {}
3355  forceinline unsigned int
3356  CommitTraceInfo::id(void) const {
3357  return b.id();
3358  }
3361  return b.group();
3362  }
3363  forceinline const Brancher&
3365  return b;
3366  }
3367  forceinline const Choice&
3369  return c;
3370  }
3371  forceinline unsigned int
3373  return a;
3374  }
3375 
3376 
3377  /*
3378  * Propagator
3379  *
3380  */
3382  Propagator::cast(ActorLink* al) {
3383  // Turning al into a reference is for gcc, assume is for MSVC
3384  GECODE_NOT_NULL(al);
3385  ActorLink& t = *al;
3386  return static_cast<Propagator*>(&t);
3387  }
3388 
3389  forceinline const Propagator*
3390  Propagator::cast(const ActorLink* al) {
3391  // Turning al into a reference is for gcc, assume is for MSVC
3392  GECODE_NOT_NULL(al);
3393  const ActorLink& t = *al;
3394  return static_cast<const Propagator*>(&t);
3395  }
3396 
3398  Propagator::fwd(void) const {
3399  return static_cast<Propagator*>(prev());
3400  }
3401 
3402  forceinline bool
3403  Propagator::disabled(void) const {
3404  return Support::marked(gpi_disabled);
3405  }
3406 
3407  forceinline void
3408  Propagator::disable(Space& home) {
3409  home.pc.p.bid_sc |= Space::sc_disabled;
3410  gpi_disabled = Support::fmark(gpi_disabled);
3411  }
3412 
3413  forceinline void
3414  Propagator::enable(Space& home) {
3415  (void) home;
3416  gpi_disabled = Support::funmark(gpi_disabled);
3417  }
3418 
3421  return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
3422  }
3423 
3424  forceinline
3426  : gpi_disabled((home.propagator() != NULL) ?
3427  // Inherit propagator information
3428  home.propagator()->gpi_disabled :
3429  // New propagator information
3430  static_cast<Space&>(home).ssd.data().gpi.allocate
3431  (home.propagatorgroup().gid)) {
3432  u.advisors = NULL;
3433  assert((u.med == 0) && (u.size == 0));
3434  static_cast<Space&>(home).pl.head(this);
3435  }
3436 
3437  forceinline
3439  : gpi_disabled(p.gpi_disabled) {
3440  u.advisors = NULL;
3441  assert((u.med == 0) && (u.size == 0));
3442  // Set forwarding pointer
3443  p.prev(this);
3444  }
3445 
3448  return u.med;
3449  }
3450 
3451  forceinline double
3452  Propagator::afc(void) const {
3453  return const_cast<Propagator&>(*this).gpi().afc;
3454  }
3455 
3456 #ifdef GECODE_HAS_CBS
3457  forceinline void
3458  Propagator::solndistrib(Space&, SendMarginal) const {}
3459 
3460  forceinline void
3461  Propagator::domainsizesum(InDecision, unsigned int& size,
3462  unsigned int& size_b) const {
3463  size = 0;
3464  size_b = 0;
3465  }
3466 #endif
3467 
3468  forceinline unsigned int
3469  Propagator::id(void) const {
3470  return const_cast<Propagator&>(*this).gpi().pid;
3471  }
3472 
3474  Propagator::group(void) const {
3475  return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3476  }
3477 
3478  forceinline void
3480  gpi().gid = g.id();
3481  }
3482 
3485  p.u.size = s;
3486  return __ES_SUBSUMED;
3487  }
3488 
3491  p.u.size = p.dispose(*this);
3492  return __ES_SUBSUMED;
3493  }
3494 
3497  p.u.med = med;
3498  assert(p.u.med != 0);
3499  return __ES_PARTIAL;
3500  }
3501 
3504  p.u.med = AllVarConf::med_combine(p.u.med,med);
3505  assert(p.u.med != 0);
3506  return __ES_PARTIAL;
3507  }
3508 
3509 
3510 
3511  /*
3512  * Brancher
3513  *
3514  */
3516  Brancher::cast(ActorLink* al) {
3517  // Turning al into a reference is for gcc, assume is for MSVC
3518  GECODE_NOT_NULL(al);
3519  ActorLink& t = *al;
3520  return static_cast<Brancher*>(&t);
3521  }
3522 
3523  forceinline const Brancher*
3524  Brancher::cast(const ActorLink* al) {
3525  // Turning al into a reference is for gcc, assume is for MSVC
3526  GECODE_NOT_NULL(al);
3527  const ActorLink& t = *al;
3528  return static_cast<const Brancher*>(&t);
3529  }
3530 
3531  forceinline
3533  gid(_home.branchergroup().gid) {
3534  Space& home = static_cast<Space&>(_home);
3535  bid = home.pc.p.bid_sc >> Space::sc_bits;
3536  home.pc.p.bid_sc += (1 << Space::sc_bits);
3537  if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3538  throw TooManyBranchers("Brancher::Brancher");
3539  // If no brancher available, make it the first one
3540  if (home.b_status == &static_cast<Space&>(home).bl) {
3541  home.b_status = this;
3542  if (home.b_commit == &static_cast<Space&>(home).bl)
3543  home.b_commit = this;
3544  }
3545  home.bl.tail(this);
3546  }
3547 
3548  forceinline
3550  : bid(b.bid), gid(b.gid) {
3551  // Set forwarding pointer
3552  b.prev(this);
3553  }
3554 
3555  forceinline unsigned int
3556  Brancher::id(void) const {
3557  return bid;
3558  }
3559 
3561  Brancher::group(void) const {
3562  return BrancherGroup(gid);
3563  }
3564 
3565  forceinline void
3567  gid = g.id();
3568  }
3569 
3570 
3571  forceinline void
3572  Space::kill(Brancher& b) {
3573  assert(!failed());
3574  // Make sure that neither b_status nor b_commit does not point to b!
3575  if (b_commit == &b)
3576  b_commit = Brancher::cast(b.next());
3577  if (b_status == &b)
3578  b_status = Brancher::cast(b.next());
3579  b.unlink();
3580  rfree(&b,b.dispose(*this));
3581  }
3582 
3583  forceinline void
3584  Space::kill(Propagator& p) {
3585  assert(!failed());
3586  p.unlink();
3587  rfree(&p,p.dispose(*this));
3588  }
3589 
3591  Space::brancher(unsigned int id) {
3592  /*
3593  * Due to weakly monotonic propagators the following scenario might
3594  * occur: a brancher has been committed with all its available
3595  * choices. Then, propagation determines less information
3596  * than before and the brancher now will create new choices.
3597  * Later, during recomputation, all of these choices
3598  * can be used together, possibly interleaved with
3599  * choices for other branchers. That means all branchers
3600  * must be scanned to find the matching brancher for the choice.
3601  *
3602  * b_commit tries to optimize scanning as it is most likely that
3603  * recomputation does not generate new choices during recomputation
3604  * and hence b_commit is moved from newer to older branchers.
3605  */
3606  Brancher* b_old = b_commit;
3607  // Try whether we are lucky
3608  while (b_commit != Brancher::cast(&bl))
3609  if (id != b_commit->id())
3610  b_commit = Brancher::cast(b_commit->next());
3611  else
3612  return b_commit;
3613  if (b_commit == Brancher::cast(&bl)) {
3614  // We did not find the brancher, start at the beginning
3615  b_commit = Brancher::cast(bl.next());
3616  while (b_commit != b_old)
3617  if (id != b_commit->id())
3618  b_commit = Brancher::cast(b_commit->next());
3619  else
3620  return b_commit;
3621  }
3622  return NULL;
3623  }
3624 
3625 
3626  /*
3627  * Local objects
3628  *
3629  */
3630 
3633  // Turning al into a reference is for gcc, assume is for MSVC
3634  GECODE_NOT_NULL(al);
3635  ActorLink& t = *al;
3636  return static_cast<LocalObject*>(&t);
3637  }
3638 
3639  forceinline const LocalObject*
3641  // Turning al into a reference is for gcc, assume is for MSVC
3642  GECODE_NOT_NULL(al);
3643  const ActorLink& t = *al;
3644  return static_cast<const LocalObject*>(&t);
3645  }
3646 
3647  forceinline
3649  (void) home;
3650  ActorLink::cast(this)->prev(NULL);
3651  }
3652 
3653  forceinline
3655  ActorLink::cast(this)->prev(NULL);
3656  }
3657 
3660  if (prev() == NULL)
3661  fwdcopy(home);
3662  return LocalObject::cast(prev());
3663  }
3664 
3665  forceinline
3666  LocalHandle::LocalHandle(void) : o(NULL) {}
3667  forceinline
3669  forceinline
3670  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3673  o = lh.o;
3674  return *this;
3675  }
3676  forceinline
3679  LocalHandle::object(void) const { return o; }
3680  forceinline void
3682  forceinline void
3684  object(lh.object()->fwd(home));
3685  }
3686 
3687 
3688  /*
3689  * Choices
3690  *
3691  */
3692  forceinline
3693  Choice::Choice(const Brancher& b, const unsigned int a)
3694  : bid(b.id()), alt(a) {}
3695 
3696  forceinline unsigned int
3697  Choice::alternatives(void) const {
3698  return alt;
3699  }
3700 
3701  forceinline unsigned int
3702  Choice::id(void) const {
3703  return bid;
3704  }
3705 
3706  forceinline
3708 
3709 
3710 
3711  /*
3712  * No-good literal
3713  *
3714  */
3715  forceinline bool
3716  NGL::leaf(void) const {
3717  return Support::marked(nl);
3718  }
3719  forceinline NGL*
3720  NGL::next(void) const {
3721  return static_cast<NGL*>(Support::funmark(nl));
3722  }
3723  forceinline void
3724  NGL::leaf(bool l) {
3725  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3726  }
3727  forceinline void
3729  nl = Support::marked(nl) ? Support::mark(n) : n;
3730  }
3731  forceinline NGL*
3732  NGL::add(NGL* n, bool l) {
3733  nl = Support::marked(nl) ? Support::mark(n) : n;
3734  n->leaf(l);
3735  return n;
3736  }
3737 
3738  forceinline
3739  NGL::NGL(void)
3740  : nl(NULL) {}
3741  forceinline
3743  : nl(NULL) {}
3744  forceinline
3746  : nl(NULL) {}
3747  forceinline size_t
3749  return sizeof(*this);
3750  }
3751 
3752  /*
3753  * Advisor
3754  *
3755  */
3756  template<class A>
3757  forceinline
3759  // Store propagator and forwarding in prev()
3760  ActorLink::prev(&p);
3761  // Link to next advisor in next()
3762  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3763  }
3764 
3765  forceinline
3767 
3768  forceinline bool
3769  Advisor::disposed(void) const {
3770  return prev() == NULL;
3771  }
3772 
3774  Advisor::cast(ActorLink* al) {
3775  return static_cast<Advisor*>(al);
3776  }
3777 
3778  forceinline const Advisor*
3779  Advisor::cast(const ActorLink* al) {
3780  return static_cast<const Advisor*>(al);
3781  }
3782 
3784  Advisor::propagator(void) const {
3785  assert(!disposed());
3786  return *Propagator::cast(ActorLink::prev());
3787  }
3788 
3789  template<class A>
3790  forceinline void
3792  assert(!disposed());
3793  ActorLink::prev(NULL);
3794  // Shorten chains of disposed advisors by one, if possible
3795  Advisor* n = Advisor::cast(next());
3796  if ((n != NULL) && n->disposed())
3797  next(n->next());
3798  }
3799 
3800  forceinline const ViewTraceInfo&
3801  Advisor::operator ()(const Space& home) const {
3802  return home.pc.p.vti;
3803  }
3804 
3805  template<class A>
3808  a.dispose(*this,c);
3809  return ES_FIX;
3810  }
3811 
3812  template<class A>
3815  a.dispose(*this,c);
3816  return ES_NOFIX;
3817  }
3818 
3819  template<class A>
3822  a.dispose(*this,c);
3823  return ES_NOFIX_FORCE;
3824  }
3825 
3826 
3827 
3828  /*
3829  * Advisor council
3830  *
3831  */
3832  template<class A>
3833  forceinline
3835 
3836  template<class A>
3837  forceinline
3839  : advisors(NULL) {}
3840 
3841  template<class A>
3842  forceinline bool
3843  Council<A>::empty(void) const {
3844  ActorLink* a = advisors;
3845  while ((a != NULL) && static_cast<A*>(a)->disposed())
3846  a = a->next();
3847  advisors = a;
3848  return a == NULL;
3849  }
3850 
3851  template<class A>
3852  forceinline void
3854  // Skip all disposed advisors
3855  {
3856  ActorLink* a = c.advisors;
3857  while ((a != NULL) && static_cast<A*>(a)->disposed())
3858  a = a->next();
3859  c.advisors = a;
3860  }
3861  // Are there any advisors to be cloned?
3862  if (c.advisors != NULL) {
3863  // The propagator in from-space
3864  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3865  // The propagator in to-space
3866  Propagator* p_t = Propagator::cast(p_f->prev());
3867  // Advisors in from-space
3868  ActorLink** a_f = &c.advisors;
3869  // Advisors in to-space
3870  A* a_t = NULL;
3871  while (*a_f != NULL) {
3872  if (static_cast<A*>(*a_f)->disposed()) {
3873  *a_f = (*a_f)->next();
3874  } else {
3875  // Run specific copying part
3876  A* a = new (home) A(home,*static_cast<A*>(*a_f));
3877  // Set propagator pointer
3878  a->prev(p_t);
3879  // Set forwarding pointer
3880  (*a_f)->prev(a);
3881  // Link
3882  a->next(a_t);
3883  a_t = a;
3884  a_f = (*a_f)->next_ref();
3885  }
3886  }
3887  advisors = a_t;
3888  // Enter advisor link for reset
3889  assert(p_f->u.advisors == NULL);
3890  p_f->u.advisors = c.advisors;
3891  } else {
3892  advisors = NULL;
3893  }
3894  }
3895 
3896  template<class A>
3897  forceinline void
3899  ActorLink* a = advisors;
3900  while (a != NULL) {
3901  if (!static_cast<A*>(a)->disposed())
3902  static_cast<A*>(a)->dispose(home,*this);
3903  a = a->next();
3904  }
3905  }
3906 
3907 
3908 
3909  /*
3910  * Advisor iterator
3911  *
3912  */
3913  template<class A>
3914  forceinline
3916  : a(c.advisors) {
3917  while ((a != NULL) && static_cast<A*>(a)->disposed())
3918  a = a->next();
3919  }
3920 
3921  template<class A>
3922  forceinline bool
3924  return a != NULL;
3925  }
3926 
3927  template<class A>
3928  forceinline void
3930  do {
3931  a = a->next();
3932  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3933  }
3934 
3935  template<class A>
3936  forceinline A&
3937  Advisors<A>::advisor(void) const {
3938  return *static_cast<A*>(a);
3939  }
3940 
3941 
3942 
3943  /*
3944  * Space
3945  *
3946  */
3947  forceinline void
3948  Space::enqueue(Propagator* p) {
3949  ActorLink::cast(p)->unlink();
3950  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3951  c->tail(ActorLink::cast(p));
3952  if (c > pc.p.active)
3953  pc.p.active = c;
3954  }
3955 
3956  forceinline void
3957  Space::fail(void) {
3958  /*
3959  * Now active points beyond the last queue. This is essential as
3960  * enqueuing a propagator in a failed space keeps the space
3961  * failed.
3962  */
3963  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3964  }
3965  forceinline void
3966  Home::fail(void) {
3967  s.fail();
3968  }
3969 
3970  forceinline bool
3971  Space::failed(void) const {
3972  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3973  }
3974  forceinline bool
3975  Home::failed(void) const {
3976  return s.failed();
3977  }
3978 
3979  forceinline bool
3980  Space::stable(void) const {
3981  return ((pc.p.active < &pc.p.queue[0]) ||
3982  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3983  }
3984 
3985  forceinline void
3987  if (p & AP_DISPOSE) {
3988  ap_notice_dispose(&a,d);
3989  }
3990  if (p & AP_VIEW_TRACE) {
3991  pc.p.bid_sc |= sc_trace;
3992  }
3993  if (p & AP_TRACE) {
3994  pc.p.bid_sc |= sc_trace;
3995  }
3996  // Currently unused
3997  if (p & AP_WEAKLY) {}
3998  }
3999 
4000  forceinline void
4002  // Check wether array has already been discarded as space
4003  // deletion is already in progress
4004  if ((p & AP_DISPOSE) && (d_fst != NULL))
4005  ap_ignore_dispose(&a,d);
4006  if (p & AP_VIEW_TRACE) {}
4007  if (p & AP_TRACE) {}
4008  // Currently unused
4009  if (p & AP_WEAKLY) {}
4010  }
4011 
4012 
4013 
4014  /*
4015  * Variable implementation
4016  *
4017  */
4018  template<class VIC>
4021  assert((pc >= 0) && (pc < pc_max+2));
4022  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4023  }
4024 
4025  template<class VIC>
4028  assert((pc > 0) && (pc < pc_max+2));
4029  return b.base+u.idx[pc-1];
4030  }
4031 
4032  template<class VIC>
4033  forceinline unsigned int&
4035  assert((pc > 0) && (pc < pc_max+2));
4036  return u.idx[pc-1];
4037  }
4038 
4039  template<class VIC>
4040  forceinline unsigned int
4041  VarImp<VIC>::idx(PropCond pc) const {
4042  assert((pc > 0) && (pc < pc_max+2));
4043  return u.idx[pc-1];
4044  }
4045 
4046  template<class VIC>
4047  forceinline
4049 #ifdef GECODE_HAS_CBS
4050  : var_id(++home.var_id_counter)
4051 #endif
4052  {
4053 #ifndef GECODE_HAS_CBS
4054  (void) home;
4055 #endif
4056  b.base = NULL; entries = 0;
4057  for (PropCond pc=1; pc<pc_max+2; pc++)
4058  idx(pc) = 0;
4059  free_and_bits = 0;
4060  }
4061 
4062  template<class VIC>
4063  forceinline
4065 #ifdef GECODE_HAS_CBS
4066  : var_id(0)
4067 #endif
4068  {
4069  b.base = NULL; entries = 0;
4070  for (PropCond pc=1; pc<pc_max+2; pc++)
4071  idx(pc) = 0;
4072  free_and_bits = 0;
4073  }
4074 
4075 #ifdef GECODE_HAS_CBS
4076  template<class VIC>
4077  forceinline unsigned int
4078  VarImp<VIC>::id(void) const {
4079  return var_id;
4080  }
4081 #endif
4082 
4083  template<class VIC>
4084  forceinline unsigned int
4085  VarImp<VIC>::degree(void) const {
4086  assert(!copied());
4087  return entries;
4088  }
4089 
4090  template<class VIC>
4091  forceinline double
4092  VarImp<VIC>::afc(void) const {
4093  double d = 0.0;
4094  // Count the afc of each propagator
4095  {
4096  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4097  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4098  while (a < e) {
4099  d += Propagator::cast(*a)->afc(); a++;
4100  }
4101  }
4102  // Count the afc of each advisor's propagator
4103  {
4104  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4105  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4106  while (a < e) {
4107  d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4108  ->propagator().afc();
4109  a++;
4110  }
4111  }
4112  return d;
4113  }
4114 
4115  template<class VIC>
4118  return d.me;
4119  }
4120 
4121  template<class VIC>
4122  forceinline unsigned int
4123  VarImp<VIC>::bits(void) const {
4124  return free_and_bits;
4125  }
4126 
4127  template<class VIC>
4128  forceinline unsigned int&
4130  return free_and_bits;
4131  }
4132 
4133 #ifdef GECODE_HAS_VAR_DISPOSE
4134  template<class VIC>
4136  VarImp<VIC>::vars_d(Space& home) {
4137  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4138  }
4139 
4140  template<class VIC>
4141  forceinline void
4143  home.vars_d<VIC>(x);
4144  }
4145 #endif
4146 
4147  template<class VIC>
4148  forceinline bool
4149  VarImp<VIC>::copied(void) const {
4150  return Support::marked(b.fwd);
4151  }
4152 
4153  template<class VIC>
4155  VarImp<VIC>::forward(void) const {
4156  assert(copied());
4157  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4158  }
4159 
4160  template<class VIC>
4162  VarImp<VIC>::next(void) const {
4163  assert(copied());
4164  return u.next;
4165  }
4166 
4167  template<class VIC>
4168  forceinline
4170 #ifdef GECODE_HAS_CBS
4171  : var_id(x.var_id)
4172 #endif
4173  {
4174  VarImpBase** reg;
4175  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4176  if (x.b.base == NULL) {
4177  // Variable implementation needs no index structure
4178  reg = &home.pc.c.vars_noidx;
4179  assert(x.degree() == 0);
4180  } else {
4181  reg = &home.pc.c.vars_u[idx_c];
4182  }
4183  // Save subscriptions in copy
4184  b.base = x.b.base;
4185  entries = x.entries;
4186  for (PropCond pc=1; pc<pc_max+2; pc++)
4187  idx(pc) = x.idx(pc);
4188 
4189  // Set forwarding pointer
4190  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4191  // Register original
4192  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4193  }
4194 
4195  template<class VIC>
4198  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4199  }
4200 
4201  template<class VIC>
4204  return static_cast<ModEventDelta>(me << VIC::med_fst);
4205  }
4206 
4207  template<class VIC>
4210  return VIC::me_combine(me1,me2);
4211  }
4212 
4213  template<class VIC>
4214  forceinline void
4216  bool force) {
4217  if (VIC::med_update(p.u.med,me) || force)
4218  home.enqueue(&p);
4219  }
4220 
4221  template<class VIC>
4222  forceinline void
4224  ActorLink** b = actor(pc1);
4225  ActorLink** p = actorNonZero(pc2+1);
4226  while (p-- > b)
4227  schedule(home,*Propagator::cast(*p),me);
4228  }
4229 
4230  template<class VIC>
4231  forceinline void
4232  VarImp<VIC>::resize(Space& home) {
4233  if (b.base == NULL) {
4234  assert((free_and_bits >> free_bits) == 0);
4235  // Create fresh dependency array with four entries
4236  free_and_bits += 4 << free_bits;
4237  b.base = home.alloc<ActorLink*>(4);
4238  for (int i=0; i<pc_max+1; i++)
4239  u.idx[i] = 0;
4240  } else {
4241  // Resize dependency array
4242  unsigned int n = degree();
4243  // Find out whether the area is most likely in the special area
4244  // reserved for subscriptions. If yes, just resize mildly otherwise
4245  // more agressively
4246  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4247  unsigned int m =
4248  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4249  (n+4) : ((n+1)*3>>1);
4250  ActorLink** prop = home.alloc<ActorLink*>(m);
4251  free_and_bits += (m-n) << free_bits;
4252  // Copy entries
4253  Heap::copy<ActorLink*>(prop, b.base, n);
4254  home.free<ActorLink*>(b.base,n);
4255  b.base = prop;
4256  }
4257  }
4258 
4259  template<class VIC>
4260  forceinline void
4261  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4262  assert(pc <= pc_max);
4263  // Count one new subscription
4264  home.pc.p.n_sub += 1;
4265  if ((free_and_bits >> free_bits) == 0)
4266  resize(home);
4267  free_and_bits -= 1 << free_bits;
4268 
4269  // Enter subscription
4270  b.base[entries] = *actorNonZero(pc_max+1);
4271  entries++;
4272  for (PropCond j = pc_max; j > pc; j--) {
4273  *actorNonZero(j+1) = *actorNonZero(j);
4274  idx(j+1)++;
4275  }
4276  *actorNonZero(pc+1) = *actor(pc);
4277  idx(pc+1)++;
4278  *actor(pc) = ActorLink::cast(p);
4279 
4280 #ifdef GECODE_AUDIT
4281  ActorLink** f = actor(pc);
4282  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4283  if (*f == p)
4284  goto found;
4285  else
4286  f++;
4287  GECODE_NEVER;
4288  found: ;
4289 #endif
4290  }
4291 
4292  template<class VIC>
4293  forceinline void
4294  VarImp<VIC>::enter(Space& home, Advisor* a) {
4295  // Note that a might be a marked pointer
4296  // Count one new subscription
4297  home.pc.p.n_sub += 1;
4298  if ((free_and_bits >> free_bits) == 0)
4299  resize(home);
4300  free_and_bits -= 1 << free_bits;
4301 
4302  // Enter subscription
4303  b.base[entries++] = *actorNonZero(pc_max+1);
4304  *actorNonZero(pc_max+1) = a;
4305  }
4306 
4307  template<class VIC>
4308  forceinline void
4310  bool assigned, ModEvent me, bool schedule) {
4311  if (assigned) {
4312  // Do not subscribe, just schedule the propagator
4313  if (schedule)
4315  } else {
4316  enter(home,&p,pc);
4317  // Schedule propagator
4318  if (schedule && (pc != PC_GEN_ASSIGNED))
4319  VarImp<VIC>::schedule(home,p,me);
4320  }
4321  }
4322 
4323  template<class VIC>
4324  forceinline void
4325  VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4326  if (!assigned) {
4327  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4328  enter(home,ma);
4329  }
4330  }
4331 
4332  template<class VIC>
4333  forceinline void
4335  bool assigned, ModEvent me) {
4336  if (assigned)
4338  else if (pc != PC_GEN_ASSIGNED)
4339  VarImp<VIC>::schedule(home,p,me);
4340  }
4341 
4342  template<class VIC>
4343  void
4344  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
4345  assert(pc <= pc_max);
4346  ActorLink* a = ActorLink::cast(p);
4347  // Find actor in dependency array
4348  ActorLink** f = actor(pc);
4349 #ifdef GECODE_AUDIT
4350  while (f < actorNonZero(pc+1))
4351  if (*f == a)
4352  goto found;
4353  else
4354  f++;
4355  GECODE_NEVER;
4356  found: ;
4357 #else
4358  while (*f != a) f++;
4359 #endif
4360  // Remove actor
4361  *f = *(actorNonZero(pc+1)-1);
4362  for (PropCond j = pc+1; j< pc_max+1; j++) {
4363  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4364  idx(j)--;
4365  }
4366  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4367  idx(pc_max+1)--;
4368  entries--;
4369  free_and_bits += 1 << free_bits;
4370  home.pc.p.n_sub -= 1;
4371  }
4372 
4373  template<class VIC>
4374  forceinline void
4376  if (b.base != NULL)
4377  remove(home,&p,pc);
4378  }
4379 
4380  template<class VIC>
4381  void
4382  VarImp<VIC>::remove(Space& home, Advisor* a) {
4383  // Note that a might be a marked pointer
4384  // Find actor in dependency array
4385  ActorLink** f = actorNonZero(pc_max+1);
4386 #ifdef GECODE_AUDIT
4387  while (f < b.base+entries)
4388  if (*f == a)
4389  goto found;
4390  else
4391  f++;
4392  GECODE_NEVER;
4393  found: ;
4394 #else
4395  while (*f != a) f++;
4396 #endif
4397  // Remove actor
4398  *f = b.base[--entries];
4399  free_and_bits += 1 << free_bits;
4400  home.pc.p.n_sub -= 1;
4401  }
4402 
4403  template<class VIC>
4404  forceinline void
4405  VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
4406  if (b.base != NULL) {
4407  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4408  remove(home,ma);
4409  }
4410  }
4411 
4412  template<class VIC>
4413  forceinline void
4415  unsigned int n_sub = degree();
4416  home.pc.p.n_sub -= n_sub;
4417  unsigned int n = (free_and_bits >> free_bits) + n_sub;
4418  home.free<ActorLink*>(b.base,n);
4419  // Must be NULL such that cloning works
4420  b.base = NULL;
4421  // Must be 0 such that degree works
4422  entries = 0;
4423  // Must be NULL such that afc works
4424  for (PropCond pc=1; pc<pc_max+2; pc++)
4425  idx(pc) = 0;
4426  free_and_bits &= (1 << free_bits) - 1;
4427  }
4428 
4429  template<class VIC>
4430  forceinline bool
4432  /*
4433  * An advisor that is executed might remove itself due to subsumption.
4434  * As entries are removed from front to back, the advisors must
4435  * be iterated in forward direction.
4436  */
4437  ActorLink** la = actorNonZero(pc_max+1);
4438  ActorLink** le = b.base+entries;
4439  if (la == le)
4440  return true;
4441  d.me = me;
4442  // An advisor that is run, might be removed during execution.
4443  // As removal is done from the back the advisors have to be executed
4444  // in inverse order.
4445  do {
4446  Advisor* a = Advisor::cast
4447  (static_cast<ActorLink*>(Support::funmark(*la)));
4448  assert(!a->disposed());
4449  Propagator& p = a->propagator();
4450  switch (p.advise(home,*a,d)) {
4451  case ES_FIX:
4452  break;
4453  case ES_FAILED:
4454  return false;
4455  case ES_NOFIX:
4456  schedule(home,p,me);
4457  break;
4458  case ES_NOFIX_FORCE:
4459  schedule(home,p,me,true);
4460  break;
4461  case __ES_SUBSUMED:
4462  default:
4463  GECODE_NEVER;
4464  }
4465  } while (++la < le);
4466  return true;
4467  }
4468 
4469  template<class VIC>
4470  void
4471  VarImp<VIC>::_fail(Space& home) {
4472  /*
4473  * An advisor that is executed might remove itself due to subsumption.
4474  * As entries are removed from front to back, the advisors must
4475  * be iterated in forward direction.
4476  */
4477  ActorLink** la = actorNonZero(pc_max+1);
4478  ActorLink** le = b.base+entries;
4479  if (la == le)
4480  return;
4481  // An advisor that is run, might be removed during execution.
4482  // As removal is done from the back the advisors have to be executed
4483  // in inverse order.
4484  do {
4485  if (Support::marked(*la)) {
4486  Advisor* a = Advisor::cast(static_cast<ActorLink*>
4487  (Support::unmark(*la)));
4488  assert(!a->disposed());
4489  Propagator& p = a->propagator();
4490  p.advise(home,*a);
4491  }
4492  } while (++la < le);
4493  }
4494 
4495  template<class VIC>
4496  ModEvent
4498  _fail(home);
4499  return ME_GEN_FAILED;
4500  }
4501 
4502  template<class VIC>
4503  forceinline void
4505  // this refers to the variable to be updated (clone)
4506  // x refers to the original
4507  // Recover from copy
4508  x->b.base = b.base;
4509  x->u.idx[0] = u.idx[0];
4510  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4511  x->u.idx[1] = u.idx[1];
4512 
4513  unsigned int np =
4514  static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4515  unsigned int na =
4516  static_cast<unsigned int >(x->b.base + x->entries -
4517  x->actorNonZero(pc_max+1));
4518  unsigned int n = na + np;
4519  assert(n == x->degree());
4520 
4521  ActorLink** f = x->b.base;
4522  ActorLink** t = sub;
4523 
4524  sub += n;
4525  b.base = t;
4526  // Process propagator subscriptions
4527  while (np >= 4) {
4528  ActorLink* p3 = f[3]->prev();
4529  ActorLink* p0 = f[0]->prev();
4530  ActorLink* p1 = f[1]->prev();
4531  ActorLink* p2 = f[2]->prev();
4532  t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4533  np -= 4; t += 4; f += 4;
4534  }
4535  if (np >= 2) {
4536  ActorLink* p0 = f[0]->prev();
4537  ActorLink* p1 = f[1]->prev();
4538  t[0] = p0; t[1] = p1;
4539  np -= 2; t += 2; f += 2;
4540  }
4541  if (np > 0) {
4542  ActorLink* p0 = f[0]->prev();
4543  t[0] = p0;
4544  t += 1; f += 1;
4545  }
4546  // Process advisor subscriptions
4547  while (na >= 4) {
4548  ptrdiff_t m0, m1, m2, m3;
4549  ActorLink* p3 =
4550  static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4551  ActorLink* p0 =
4552  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4553  ActorLink* p1 =
4554  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4555  ActorLink* p2 =
4556  static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4557  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4558  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4559  t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4560  t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4561  na -= 4; t += 4; f += 4;
4562  }
4563  if (na >= 2) {
4564  ptrdiff_t m0, m1;
4565  ActorLink* p0 =
4566  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4567  ActorLink* p1 =
4568  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4569  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4570  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4571  na -= 2; t += 2; f += 2;
4572  }
4573  if (na > 0) {
4574  ptrdiff_t m0;
4575  ActorLink* p0 =
4576  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4577  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4578  }
4579  }
4580 
4581  template<class VIC>
4582  forceinline void
4583  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4584  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4585  while (x != NULL) {
4586  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4587  }
4588  }
4589 
4590 
4591 
4592  /*
4593  * Variable disposer
4594  *
4595  */
4596  template<class VarImp>
4598 #ifdef GECODE_HAS_VAR_DISPOSE
4599  Space::vd[VarImp::idx_d] = this;
4600 #endif
4601  }
4602 
4603  template<class VarImp>
4604  void
4606  VarImp* x = static_cast<VarImp*>(_x);
4607  do {
4608  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4609  } while (x != NULL);
4610  }
4611 
4612  /*
4613  * Statistics
4614  */
4615 
4616  forceinline void
4618  propagate = 0;
4619  }
4620  forceinline
4622  reset();
4623  }
4626  propagate += s.propagate;
4627  return *this;
4628  }
4631  StatusStatistics t(s);
4632  return t += *this;
4633  }
4634 
4635  forceinline void
4637 
4638  forceinline
4640  reset();
4641  }
4644  CloneStatistics s;
4645  return s;
4646  }
4649  return *this;
4650  }
4651 
4652  forceinline void
4654 
4655  forceinline
4657  reset();
4658  }
4661  CommitStatistics s;
4662  return s;
4663  }
4666  return *this;
4667  }
4668 
4669  /*
4670  * Cost computation
4671  *
4672  */
4673 
4674  forceinline
4675  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4676 
4678  PropCost::cost(PropCost::Mod m,
4680  unsigned int n) {
4681  if (n < 2)
4682  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4683  else if (n == 2)
4684  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4685  else if (n == 3)
4686  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4687  else
4688  return (m == LO) ? lo : hi;
4689  }
4690 
4693  return AC_RECORD;
4694  }
4696  PropCost::crazy(PropCost::Mod m, unsigned int n) {
4697  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4698  }
4701  assert(n >= 0);
4702  return crazy(m,static_cast<unsigned int>(n));
4703  }
4705  PropCost::cubic(PropCost::Mod m, unsigned int n) {
4706  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4707  }
4710  assert(n >= 0);
4711  return cubic(m,static_cast<unsigned int>(n));
4712  }
4714  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
4715  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4716  }
4719  assert(n >= 0);
4720  return quadratic(m,static_cast<unsigned int>(n));
4721  }
4723  PropCost::linear(PropCost::Mod m, unsigned int n) {
4724  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4725  }
4728  assert(n >= 0);
4729  return linear(m,static_cast<unsigned int>(n));
4730  }
4733  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4734  }
4737  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4738  }
4741  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4742  }
4743 
4744  /*
4745  * Iterators for propagators and branchers of a space
4746  *
4747  */
4748  forceinline
4750  : home(home0), q(home.pc.p.active) {
4751  while (q >= &home.pc.p.queue[0]) {
4752  if (q->next() != q) {
4753  c = q->next(); e = q; q--;
4754  return;
4755  }
4756  q--;
4757  }
4758  q = NULL;
4759  if (!home.pl.empty()) {
4760  c = Propagator::cast(home.pl.next());
4761  e = Propagator::cast(&home.pl);
4762  } else {
4763  c = e = NULL;
4764  }
4765  }
4766  forceinline bool
4768  return c != NULL;
4769  }
4770  forceinline void
4772  c = c->next();
4773  if (c == e) {
4774  if (q == NULL) {
4775  c = NULL;
4776  } else {
4777  while (q >= &home.pc.p.queue[0]) {
4778  if (q->next() != q) {
4779  c = q->next(); e = q; q--;
4780  return;
4781  }
4782  q--;
4783  }
4784  q = NULL;
4785  if (!home.pl.empty()) {
4786  c = Propagator::cast(home.pl.next());
4787  e = Propagator::cast(&home.pl);
4788  } else {
4789  c = NULL;
4790  }
4791  }
4792  }
4793  }
4796  return *Propagator::cast(c);
4797  }
4798 
4799 
4800  forceinline
4802  : home(home0), q(home.pc.p.active) {
4803  while (q >= &home.pc.p.queue[0]) {
4804  if (q->next() != q) {
4805  c = q->next(); e = q; q--;
4806  return;
4807  }
4808  q--;
4809  }
4810  q = c = e = NULL;
4811  }
4812  forceinline bool
4814  return c != NULL;
4815  }
4816  forceinline void
4818  c = c->next();
4819  if (c == e) {
4820  if (q == NULL) {
4821  c = NULL;
4822  } else {
4823  while (q >= &home.pc.p.queue[0]) {
4824  if (q->next() != q) {
4825  c = q->next(); e = q; q--;
4826  return;
4827  }
4828  q--;
4829  }
4830  q = c = e = NULL;
4831  }
4832  }
4833  }
4836  return *Propagator::cast(c);
4837  }
4838 
4839 
4840  forceinline
4842  c = Propagator::cast(home.pl.next());
4843  e = Propagator::cast(&home.pl);
4844  }
4845  forceinline bool
4847  return c != e;
4848  }
4849  forceinline void
4851  c = c->next();
4852  }
4855  return *Propagator::cast(c);
4856  }
4857 
4858 
4859  forceinline
4861  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4862  forceinline bool
4864  return c != e;
4865  }
4866  forceinline void
4868  c = c->next();
4869  }
4872  return *Brancher::cast(c);
4873  }
4874 
4875 
4876  /*
4877  * Groups of actors
4878  */
4879  forceinline
4880  Group::Group(unsigned int gid0) : gid(gid0) {}
4881 
4882  forceinline bool
4883  Group::in(Group actor) const {
4884  return (gid == GROUPID_ALL) || (gid == actor.gid);
4885  }
4886 
4887  forceinline bool
4888  Group::in(void) const {
4889  return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
4890  }
4891 
4892  forceinline
4893  Group::Group(const Group& g) : gid(g.gid) {}
4894 
4897  gid=g.gid; return *this;
4898  }
4899 
4900  forceinline unsigned int
4901  Group::id(void) const {
4902  return gid;
4903  }
4904 
4905 
4906  forceinline
4908 
4909  forceinline
4911  : Group(gid) {}
4912 
4913  forceinline
4915  : Group(g) {}
4916 
4919  return static_cast<PropagatorGroup&>(Group::operator =(g));
4920  }
4921 
4924  return Home(home,NULL,*this,BrancherGroup::def);
4925  }
4926 
4927  forceinline bool
4929  return id() == g.id();
4930  }
4931  forceinline bool
4933  return id() != g.id();
4934  }
4935 
4938  if (id() != GROUPID_ALL)
4939  p.group(*this);
4940  return *this;
4941  }
4942 
4943 
4944  forceinline
4946 
4947  forceinline
4949  : Group(gid) {}
4950 
4951  forceinline
4953  : Group(g) {}
4954 
4957  return static_cast<BrancherGroup&>(Group::operator =(g));
4958  }
4959 
4962  return Home(home,NULL,PropagatorGroup::def,*this);
4963  }
4964 
4965  forceinline bool
4967  return id() == g.id();
4968  }
4969  forceinline bool
4971  return id() != g.id();
4972  }
4973 
4976  if (id() != GROUPID_ALL)
4977  p.group(*this);
4978  return *this;
4979  }
4980 
4981 
4982  /*
4983  * Iterators for propagators and branchers in a group
4984  *
4985  */
4986  forceinline
4988  : ps(const_cast<Space&>(home)), g(g0) {
4989  while (ps() && !g.in(ps.propagator().group()))
4990  ++ps;
4991  }
4992  forceinline bool
4994  return ps();
4995  }
4996  forceinline void
4998  do
4999  ++ps;
5000  while (ps() && !g.in(ps.propagator().group()));
5001  }
5002  forceinline const Propagator&
5004  return ps.propagator();
5005  }
5006 
5007  forceinline
5009  : bs(const_cast<Space&>(home)), g(g0) {
5010  while (bs() && !g.in(bs.brancher().group()))
5011  ++bs;
5012  }
5013  forceinline bool
5015  return bs();
5016  }
5017  forceinline void
5019  do
5020  ++bs;
5021  while (bs() && !g.in(bs.brancher().group()));
5022  }
5023  forceinline const Brancher&
5024  Branchers::brancher(void) const {
5025  return bs.brancher();
5026  }
5027 
5028 
5029  /*
5030  * Space construction support
5031  *
5032  */
5033  template<class T>
5034  forceinline T&
5036  return alloc<T>(1);
5037  }
5038  template<class T, typename A1>
5039  forceinline T&
5040  Space::construct(A1 const& a1) {
5041  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5042  new (&t) T(a1);
5043  return t;
5044  }
5045  template<class T, typename A1, typename A2>
5046  forceinline T&
5047  Space::construct(A1 const& a1, A2 const& a2) {
5048  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5049  new (&t) T(a1,a2);
5050  return t;
5051  }
5052  template<class T, typename A1, typename A2, typename A3>
5053  forceinline T&
5054  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5055  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5056  new (&t) T(a1,a2,a3);
5057  return t;
5058  }
5059  template<class T, typename A1, typename A2, typename A3, typename A4>
5060  forceinline T&
5061  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5062  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5063  new (&t) T(a1,a2,a3,a4);
5064  return t;
5065  }
5066  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5067  forceinline T&
5068  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5069  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5070  new (&t) T(a1,a2,a3,a4,a5);
5071  return t;
5072  }
5073 
5074 }
5075 
5076 // STATISTICS: kernel-core
static const int med_lst
End of bits for modification event delta.
Definition: core.hpp:111
void other(void)
Record that nothing is known at this point.
Definition: core.hpp:3285
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3697
void reset(void)
Reset information.
Definition: core.hpp:4636
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition: core.hpp:3048
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:74
bool marked(void *p)
Check whether p is marked.
Iterator over subscribed propagators.
Definition: subscribed.hpp:36
Council of advisors
Definition: core.hpp:154
Base-class for variable implementations.
Definition: core.hpp:156
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:3398
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Space must be branched (at least one brancher left)
Definition: core.hpp:1643
Class to iterate over branchers in a group.
Definition: core.hpp:2729
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4714
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:4932
unsigned int bid_sc
Id of next brancher to be created plus status control.
Definition: core.hpp:1798
BrancherGroup group(void) const
Return brancher group.
Definition: core.hpp:3360
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition: core.hpp:3260
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
unsigned int a
Alternative.
Definition: core.hpp:1003
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4155
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:844
Kernel::GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3420
LocalObject(Home home)
Constructor for creation.
Definition: core.hpp:3648
Type
Which type of information is provided.
Definition: core.hpp:1575
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4723
View trace information.
Definition: core.hpp:905
Group & operator=(const Group &g)
Assignment operator.
Definition: core.hpp:4896
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4883
VarImp(void)
Creation of static instances.
Definition: core.hpp:4064
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:4597
void update(Space &home, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3683
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:274
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3679
Actor must always be disposed.
Definition: core.hpp:561
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1038
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
Definition: core.hpp:3801
const Type t
Type of information.
Definition: core.hpp:1583
PropagatorGroup(void)
Constructor.
Definition: core.hpp:4907
NGL(void)
Constructor for creation.
Definition: core.hpp:3739
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:81
static const int free_bits
Freely available bits.
Definition: core.hpp:107
SpaceStatus
Space status
Definition: core.hpp:1640
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3503
~PostInfo(void)
Reset information.
Definition: core.hpp:3317
Group of branchers.
Definition: core.hpp:796
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:786
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:847
friend class Home
Definition: core.hpp:673
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:2845
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
Definition: core.hpp:3338
Class to iterate over propagators in a group.
Definition: core.hpp:2711
Statistics for execution of commit
Definition: core.hpp:1684
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:69
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:4085
AFC afc
Definition: afc.cpp:135
Local (space-shared) object.
Definition: core.hpp:1492
Status
The status of a no-good literal.
Definition: core.hpp:1305
unsigned long int fail(void) const
Return number of failures since last restart.
Definition: core.hpp:3053
int ModEvent
Type for modification events.
Definition: core.hpp:62
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:4215
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
Branchers(Space &home)
Initialize.
Definition: core.hpp:4860
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:4117
Base-class for propagators.
Definition: core.hpp:1023
Internal: propagator is subsumed, do not use.
Definition: core.hpp:472
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3707
const Brancher & b
Brancher.
Definition: core.hpp:999
T & construct(void)
Construction routines.
Definition: core.hpp:5035
Information is provided by a restart-based engine.
Definition: core.hpp:1577
Base-class for advisors.
Definition: core.hpp:1251
static const int idx_d
Index for disposal.
Definition: core.hpp:103
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4203
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4692
ActorLink ** base
Subscribed actors.
Definition: core.hpp:232
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4835
Manage memory for space.
Definition: manager.hpp:120
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3814
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:272
const NoGoods & ng
No-goods from restart.
Definition: core.hpp:1595
Class to iterate over advisors of a council.
Definition: core.hpp:155
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:718
Space & h
The home space.
Definition: core.hpp:948
Handle to region.
Definition: region.hpp:55
void * mark(void *p)
Return marked pointer for unmarked pointer p.
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:981
PropagatorGroup pg
A propagator group.
Definition: core.hpp:861
Base-class for variable implementations.
Definition: core.hpp:171
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1811
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1653
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4901
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:5018
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:4740
Propagator failed.
Definition: core.hpp:966
Computation spaces.
Definition: core.hpp:1701
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:264
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3672
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:2764
PostInfo(Home home)
Set information.
Definition: core.hpp:3313
Base-class for both propagators and branchers.
Definition: core.hpp:627
Statistics for execution of status
Definition: core.hpp:1650
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4414
Branchers(const Space &home, BrancherGroup g)
Initialize.
Definition: core.hpp:5008
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3469
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
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:2794
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:4643
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:903
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition: core.hpp:683
const Choice & c
Choice.
Definition: core.hpp:1001
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:4863
The literal is subsumed.
Definition: core.hpp:1307
Gecode::FloatVal c(-8, 8)
Maximal cost value.
Definition: core.hpp:505
Configuration class for variable implementations without index structure.
Definition: core.hpp:98
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3716
Handles for local (space-shared) objects.
Definition: core.hpp:1517
Class to iterate over branchers of a space.
Definition: core.hpp:2692
Base-class for branchers.
Definition: core.hpp:1401
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:40
const Brancher & brancher(void) const
Return currently executing brancher.
Definition: core.hpp:3299
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3561
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:4648
const Propagator * p
Propagator.
Definition: core.hpp:975
What
What is currently executing.
Definition: core.hpp:910
void reset(void)
Reset information.
Definition: core.hpp:4653
void reset(void)
Reset information.
Definition: core.hpp:4617
Status s
Status.
Definition: core.hpp:977
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition: core.hpp:4956
Gecode::IntArgs i({1, 2, 3, 4})
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4767
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:3199
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4197
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4149
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4854
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3632
Propagators(const Space &home, PropagatorGroup g)
Initialize.
Definition: core.hpp:4987
Execution has resulted in failure.
Definition: core.hpp:473
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition: core.hpp:4918
Commit trace information.
Definition: core.hpp:995
StatusStatistics(void)
Initialize.
Definition: core.hpp:4621
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4795
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3058
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:164
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4817
PropagatorGroup group(void) const
Return propagator group.
Definition: core.hpp:3334
Propagator for recording trace information.
Definition: recorder.hpp:153
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3181
Statistics for execution of clone
Definition: core.hpp:1668
Class to set group information when a post function is executed.
Definition: core.hpp:945
bool operator!=(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:317
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:71
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:3027
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:3020
Type type(void) const
Return type of information.
Definition: core.hpp:3039
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3971
Propagator computed fixpoint.
Definition: core.hpp:964
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3189
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1800
void fail(void)
Fail space.
Definition: core.hpp:3957
static const int idx_c
Index for update.
Definition: core.hpp:101
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4850
Group(void)
Constructor.
Definition: core.cpp:893
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:121
struct Gecode::Space::@58::@59 p
Data only available during propagation or branching.
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3975
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
const Space * l
Last solution found.
Definition: core.hpp:1593
static const int med_mask
Bitmask for modification event delta.
Definition: core.hpp:113
PropagatorGroup g
Propagator group.
Definition: core.hpp:973
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:5003
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3980
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:3484
CloneStatistics(void)
Initialize.
Definition: core.hpp:4639
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3666
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:3219
struct Gecode::Space::@58::@60 c
Data available only during copying.
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:76
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:4605
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3474
Trace filters.
Definition: filter.hpp:133
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4813
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition: core.cpp:67
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:693
Group baseclass for controlling actors.
Definition: core.hpp:672
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:3923
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3403
friend class PropagatorGroup
Definition: core.hpp:1030
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4846
const Choice & choice(void) const
Return choice.
Definition: core.hpp:3368
Information is provided by a portfolio-based engine.
Definition: core.hpp:1579
Council(void)
Default constructor.
Definition: core.hpp:3834
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition: core.hpp:3304
#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:3807
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
unsigned int alternative(void) const
Return alternative.
Definition: core.hpp:3372
static unsigned int next
Next group id.
Definition: core.hpp:690
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:3223
IdlePropagators(Space &home)
Initialize.
Definition: core.hpp:4841
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:4928
Propagate trace information.
Definition: core.hpp:959
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3693
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition: filter.cpp:131
Exception: too many branchers
Definition: exception.hpp:93
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3496
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3176
Mod
Propagation cost modifier.
Definition: core.hpp:511
Single _b(1, 4)
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:5014
double afc(void) const
Return accumulated failure count (plus degree)
Definition: core.hpp:4092
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3720
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4993
BrancherGroup branchergroup(void) const
Return brancher group.
Definition: core.hpp:3264
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:3447
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3063
Advisor forces rescheduling of propagator.
Definition: core.hpp:477
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
NoGoods(void)
Initialize.
Definition: core.hpp:3009
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2820
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition: manager.hpp:298
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3556
Class to iterate over propagators of a space.
Definition: core.hpp:2621
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:4923
Class to iterate over idle propagators of a space.
Definition: core.hpp:2671
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:5024
Class to store data shared among several spaces.
unsigned int i
Propagator id.
Definition: core.hpp:971
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:63
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:789
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2756
ScheduledPropagators(Space &home)
Initialize.
Definition: core.hpp:4801
BrancherGroup(void)
Constructor.
Definition: core.hpp:4945
Propagators(Space &home)
Initialize.
Definition: core.hpp:4749
Class for storing propagator information.
Definition: gpi.hpp:42
ActualCost ac
Actual cost.
Definition: core.hpp:508
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:3232
const Brancher & brancher(void) const
Return brancher.
Definition: core.hpp:3364
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4705
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:4660
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4001
Brancher(Home home)
Constructor for creation.
Definition: core.hpp:3532
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:3244
Propagator did not compute fixpoint.
Definition: core.hpp:965
Propagator & propagator(void) const
Return the advisor&#39;s propagator.
Definition: core.hpp:3784
Choice for performing commit
Definition: core.hpp:1371
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3986
The literal is failed.
Definition: core.hpp:1306
No-goods recorded from restarts.
Definition: core.hpp:1547
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3791
Propagation cost.
Definition: core.hpp:485
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:3929
Archive representation
Definition: archive.hpp:42
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition: core.hpp:3758
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2880
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:4970
ExecStatus
Definition: core.hpp:471
const unsigned long int r
Number of restarts.
Definition: core.hpp:1587
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:4665
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4771
unsigned int id(void) const
Return brancher identifier.
Definition: core.hpp:3356
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4696
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:3043
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:857
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1565
const Propagator & propagator(void) const
Return currently executing propagator.
Definition: core.hpp:3293
static const PropCond pc_max
Maximal propagation condition.
Definition: core.hpp:105
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:4961
LocalObject * fwd(Space &home)
Return forwarding pointer.
Definition: core.hpp:3659
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:4867
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition: core.hpp:4334
Base-class for freelist-managed objects.
Definition: manager.hpp:98
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:3194
unsigned int asset(void) const
Return number of asset in portfolio.
Definition: core.hpp:3068
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4497
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4997
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:478
Variable implementation disposer
Definition: core.hpp:194
double afc
The afc value.
Definition: gpi.hpp:49
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2784
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:67
Post propagator for SetVar x
Definition: set.hh:767
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:241
Execution is okay.
Definition: core.hpp:475
Status status(void) const
Return propagator status.
Definition: core.hpp:3342
Tracer.
Definition: tracer.hpp:149
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3748
Propagation has not computed fixpoint.
Definition: core.hpp:474
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
Definition: core.hpp:3326
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:4966
unsigned int id(void) const
Return propagator identifier.
Definition: core.hpp:3330
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:859
void fail(void)
Mark space as failed.
Definition: core.hpp:3966
void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te, FloatTracer &t)
Create a tracer for float variables.
Definition: trace.cpp:39
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3732
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:3256
bool in(void) const
Check whether this is a real group (and not just default)
Definition: core.hpp:4888
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
bool operator==(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:294
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:4630
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:75
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4732
Propagator(Home home)
Constructor for posting.
Definition: core.hpp:3425
Gecode toplevel namespace
static Group all
Group of all actors.
Definition: core.hpp:715
Information passed by meta search engines.
Definition: core.hpp:1572
BrancherGroup bg
A brancher group.
Definition: core.hpp:863
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:4209
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1789
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72
Class to iterate over scheduled propagators of a space.
Definition: core.hpp:2646
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:45
What what(void) const
Return what is currently executing.
Definition: core.hpp:3289
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1809
Group of propagators.
Definition: core.hpp:725
ActorProperty
Actor properties.
Definition: core.hpp:552
VarImp * next(void) const
Return next copied variable.
Space is failed
Definition: core.hpp:1641
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:92
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:3012
ActualCost
The actual cost values that are used.
Definition: core.hpp:489
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition: core.hpp:681
unsigned long int n
Number of no-goods.
Definition: core.hpp:1550
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2779
const unsigned long int s
Number of solutions since last restart.
Definition: core.hpp:1589
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
Definition: core.hpp:3352
unsigned int gid
Group identifier.
Definition: gpi.hpp:47
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Definition: core.hpp:922
Home class for posting propagators
Definition: core.hpp:853
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4123
Base class for heap allocated objects.
Definition: heap.hpp:340
static const int med_fst
Start of bits for modification event delta.
Definition: core.hpp:109
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4736
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
A & advisor(void) const
Return advisor.
Definition: core.hpp:3937
const unsigned long int f
Number of failures since last restart.
Definition: core.hpp:1591
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:125
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:4625
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:44
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
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:4431
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4871
const unsigned int a
Number of asset in portfolio.
Definition: core.hpp:1600
CommitStatistics(void)
Initialize.
Definition: core.hpp:4656
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:65
ViewTraceInfo vti
View trace information.
Definition: core.hpp:1802
Base class for Variable type disposer.
Definition: core.hpp:179
Status
Propagator status.
Definition: core.hpp:963
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:3821
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:108
double afc(void) const
Return the accumlated failure count.
Definition: core.hpp:3452
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2760
unsigned int gid
The group id.
Definition: core.hpp:687
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:4309
Space is solved (no brancher left)
Definition: core.hpp:1642
No-good literal recorded during search.
Definition: core.hpp:1299
~LocalHandle(void)
Destructor.
Definition: core.hpp:3677