Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
62  typedef int ModEvent;
63 
65  const ModEvent ME_GEN_FAILED = -1;
67  const ModEvent ME_GEN_NONE = 0;
70 
72  typedef int PropCond;
74  const PropCond PC_GEN_NONE = -1;
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 PostTraceInfo;
151  class TraceRecorder;
152  class TraceFilter;
153  class Tracer;
154 
155  template<class A> class Council;
156  template<class A> class Advisors;
157  template<class VIC> class VarImp;
158 
159 
160  /*
161  * Variable implementations
162  *
163  */
164 
172  class VarImpBase {};
173 
181  public:
183  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
186  };
187 
194  template<class VarImp>
196  public:
198  VarImpDisposer(void);
200  virtual void dispose(Space& home, VarImpBase* x);
201  };
202 
204  class Delta {
205  template<class VIC> friend class VarImp;
206  private:
208  ModEvent me;
209  };
210 
218  template<class VIC>
219  class VarImp : public VarImpBase {
220  friend class Space;
221  friend class Propagator;
222  template<class VarImp> friend class VarImpDisposer;
223  friend class SubscribedPropagators;
224  private:
225  union {
243  } b;
244 
246  static const int idx_c = VIC::idx_c;
248  static const int idx_d = VIC::idx_d;
250  static const int free_bits = VIC::free_bits;
252  unsigned int entries;
254  unsigned int free_and_bits;
256  static const Gecode::PropCond pc_max = VIC::pc_max;
257 #ifdef GECODE_HAS_CBS
259  const unsigned var_id;
260 #endif
261 
262  union {
273  unsigned int idx[pc_max+1];
276  } u;
277 
279  ActorLink** actor(PropCond pc);
281  ActorLink** actorNonZero(PropCond pc);
283  unsigned int& idx(PropCond pc);
285  unsigned int idx(PropCond pc) const;
286 
293  void update(VarImp* x, ActorLink**& sub);
300  static void update(Space& home, ActorLink**& sub);
301 
303  void enter(Space& home, Propagator* p, PropCond pc);
305  void enter(Space& home, Advisor* a);
307  void resize(Space& home);
309  void remove(Space& home, Propagator* p, PropCond pc);
311  void remove(Space& home, Advisor* a);
312 
313 
314  protected:
316  void cancel(Space& home);
322  bool advise(Space& home, ModEvent me, Delta& d);
323  private:
325  void _fail(Space& home);
326  protected:
329 #ifdef GECODE_HAS_VAR_DISPOSE
331  static VarImp<VIC>* vars_d(Space& home);
333  static void vars_d(Space& home, VarImp<VIC>* x);
334 #endif
335 
336  public:
338  VarImp(Space& home);
340  VarImp(void);
341 
342 #ifdef GECODE_HAS_CBS
344  unsigned int id(void) const;
345 #endif
346 
348 
349 
361  void subscribe(Space& home, Propagator& p, PropCond pc,
362  bool assigned, ModEvent me, bool schedule);
364  void cancel(Space& home, Propagator& p, PropCond pc);
373  void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
375  void cancel(Space& home, Advisor& a, bool fail);
376 
383  unsigned int degree(void) const;
390  double afc(void) const;
392 
394 
395  VarImp(Space& home, VarImp& x);
398  bool copied(void) const;
400  VarImp* forward(void) const;
402  VarImp* next(void) const;
404 
406 
407 
414  static void schedule(Space& home, Propagator& p, ModEvent me,
415  bool force = false);
423  static void reschedule(Space& home, Propagator& p, PropCond pc,
424  bool assigned, ModEvent me);
426  static ModEvent me(const ModEventDelta& med);
432 
434 
435  static ModEvent modevent(const Delta& d);
438 
440 
441  unsigned int bits(void) const;
444  unsigned int& bits(void);
446 
447  protected:
449  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
450 
451  public:
453 
454  static void* operator new(size_t,Space&);
457  static void operator delete(void*,Space&);
459  static void operator delete(void*);
461  };
462 
463 
472  enum ExecStatus {
474  ES_FAILED = -1,
475  ES_NOFIX = 0,
476  ES_OK = 0,
477  ES_FIX = 1,
479  __ES_PARTIAL = 2
480  };
481 
486  class PropCost {
487  friend class Space;
488  public:
490  enum ActualCost {
491  AC_RECORD = 0,
506  AC_MAX = 6
507  };
510  public:
512  enum Mod {
513  LO,
514  HI
515  };
516  private:
518  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
521  public:
523  static PropCost record(void);
525  static PropCost crazy(PropCost::Mod m, unsigned int n);
527  static PropCost crazy(PropCost::Mod m, int n);
529  static PropCost cubic(PropCost::Mod m, unsigned int n);
531  static PropCost cubic(PropCost::Mod m, int n);
533  static PropCost quadratic(PropCost::Mod m, unsigned int n);
535  static PropCost quadratic(PropCost::Mod m, int n);
537  static PropCost linear(PropCost::Mod m, unsigned int n);
539  static PropCost linear(PropCost::Mod m, int n);
541  static PropCost ternary(PropCost::Mod m);
543  static PropCost binary(PropCost::Mod m);
545  static PropCost unary(PropCost::Mod m);
546  };
547 
548 
562  AP_DISPOSE = (1 << 0),
568  AP_WEAKLY = (1 << 1),
573  AP_VIEW_TRACE = (1 << 2),
578  AP_TRACE = (1 << 3)
579  };
580 
581 
589  class ActorLink {
590  friend class Actor;
591  friend class Propagator;
592  friend class Advisor;
593  friend class Brancher;
594  friend class LocalObject;
595  friend class Space;
596  template<class VIC> friend class VarImp;
597  private:
598  ActorLink* _next; ActorLink* _prev;
599  public:
601  ActorLink* prev(void) const; void prev(ActorLink*);
603  ActorLink* next(void) const; void next(ActorLink*);
604  ActorLink** next_ref(void);
606 
608  void init(void);
610  void unlink(void);
612  void head(ActorLink* al);
614  void tail(ActorLink* al);
616  bool empty(void) const;
618  template<class T> static ActorLink* cast(T* a);
620  template<class T> static const ActorLink* cast(const T* a);
621  };
622 
623 
629  friend class ActorLink;
630  friend class Space;
631  friend class Propagator;
632  friend class Advisor;
633  friend class Brancher;
634  friend class LocalObject;
635  template<class VIC> friend class VarImp;
636  template<class A> friend class Council;
637  private:
639  static Actor* cast(ActorLink* al);
641  static const Actor* cast(const ActorLink* al);
643  GECODE_KERNEL_EXPORT static Actor* sentinel;
644  public:
646  virtual Actor* copy(Space& home) = 0;
647 
649 
652  virtual size_t dispose(Space& home);
654  static void* operator new(size_t s, Space& home);
656  static void operator delete(void* p, Space& home);
658  public:
660  GECODE_KERNEL_EXPORT virtual ~Actor(void);
662  static void* operator new(size_t s);
664  static void operator delete(void* p);
665  };
666 
667  class Home;
668 
673  class Group {
674  friend class Home;
675  friend class Propagator;
676  friend class Brancher;
677  friend class ViewTraceInfo;
678  friend class PropagateTraceInfo;
679  friend class CommitTraceInfo;
680  friend class PostTraceInfo;
681  protected:
683  static const unsigned int GROUPID_ALL = 0U;
685  static const unsigned int GROUPID_DEF = 1U;
687  static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
689  unsigned int gid;
692  static unsigned int next;
697  Group(unsigned int gid0);
698  public:
700 
703  Group(void);
705  Group(const Group& g);
707  Group& operator =(const Group& g);
709  unsigned int id(void) const;
711  bool in(Group a) const;
713  bool in(void) const;
717  static Group all;
720  static Group def;
721  };
722 
727  class PropagatorGroup : public Group {
728  friend class Propagator;
729  friend class ViewTraceInfo;
730  friend class PropagateTraceInfo;
731  friend class PostTraceInfo;
732  protected:
734  PropagatorGroup(unsigned int gid);
735  public:
737 
738  PropagatorGroup(void);
745  Home operator ()(Space& home);
747 
761  PropagatorGroup& move(Space& home, unsigned int id);
763 
765  bool operator ==(PropagatorGroup g) const;
768  bool operator !=(PropagatorGroup g) const;
771  unsigned int size(Space& home) const;
774  void kill(Space& home);
777  void disable(Space& home);
785  void enable(Space& home, bool s=true);
793  };
794 
799  class BrancherGroup : public Group {
800  friend class Brancher;
801  protected:
803  BrancherGroup(unsigned int gid);
804  public:
806 
807  BrancherGroup(void);
810  BrancherGroup(const BrancherGroup& g);
814  Home operator ()(Space& home);
816 
822  BrancherGroup& move(Space& home, Brancher& b);
830  BrancherGroup& move(Space& home, unsigned int id);
832 
834  bool operator ==(BrancherGroup g) const;
837  bool operator !=(BrancherGroup g) const;
840  unsigned int size(Space& home) const;
843  void kill(Space& home);
851  };
852 
856  class Home {
857  friend class PostInfo;
858  protected:
867  public:
869 
870  Home(Space& s, Propagator* p=NULL,
875  Home& operator =(const Home& h);
877  operator Space&(void);
879 
888  Propagator* propagator(void) const;
890  PropagatorGroup propagatorgroup(void) const;
892  BrancherGroup branchergroup(void) const;
894 
896  bool failed(void) const;
899  void fail(void);
901  void notice(Actor& a, ActorProperty p, bool duplicate=false);
903  };
904 
909  friend class Space;
910  friend class PostInfo;
911  public:
913  enum What {
917  BRANCHER = 1,
919  POST = 2,
921  OTHER = 3
922  };
923  protected:
925  ptrdiff_t who;
927  void propagator(Propagator& p);
929  void brancher(Brancher& b);
931  void post(PropagatorGroup g);
933  void other(void);
934  public:
936  What what(void) const;
938  const Propagator& propagator(void) const;
940  const Brancher& brancher(void) const;
942  PropagatorGroup post(void) const;
943  };
944 
948  class PostInfo {
949  friend class Space;
950  protected:
956  unsigned int pid;
958  bool nested;
959  public:
961  PostInfo(Home home);
963  ~PostInfo(void);
964  };
965 
970  friend class Space;
971  public:
973  enum Status {
974  FIX,
977  SUBSUMED
978  };
979  protected:
981  unsigned int i;
985  const Propagator* p;
989  PropagateTraceInfo(unsigned int i, PropagatorGroup g,
990  const Propagator* p, Status s);
991  public:
993  unsigned int id(void) const;
995  PropagatorGroup group(void) const;
997  const Propagator* propagator(void) const;
999  Status status(void) const;
1000  };
1001 
1006  friend class Space;
1007  protected:
1009  const Brancher& b;
1011  const Choice& c;
1013  unsigned int a;
1015  CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1016  public:
1018  unsigned int id(void) const;
1020  BrancherGroup group(void) const;
1022  const Brancher& brancher(void) const;
1024  const Choice& choice(void) const;
1026  unsigned int alternative(void) const;
1027  };
1028 
1033  friend class Space;
1034  friend class PostInfo;
1035  public:
1037  enum Status {
1040  SUBSUMED
1041  };
1042  protected:
1048  unsigned int n;
1050  PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
1051  public:
1053  Status status(void) const;
1055  PropagatorGroup group(void) const;
1057  unsigned int propagators(void) const;
1058  };
1059 
1065  friend class ActorLink;
1066  friend class Space;
1067  template<class VIC> friend class VarImp;
1068  friend class Advisor;
1069  template<class A> friend class Council;
1071  friend class PropagatorGroup;
1072  private:
1073  union {
1077  size_t size;
1080  } u;
1082  void* gpi_disabled;
1084  static Propagator* cast(ActorLink* al);
1086  static const Propagator* cast(const ActorLink* al);
1088  void disable(Space& home);
1090  void enable(Space& home);
1091  protected:
1093  Propagator(Home home);
1095  Propagator(Space& home, Propagator& p);
1097  Propagator* fwd(void) const;
1099  Kernel::GPI::Info& gpi(void);
1100 
1101  public:
1103 
1104 
1112  virtual void reschedule(Space& home) = 0;
1136  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1138  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1146  ModEventDelta modeventdelta(void) const;
1183  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1186  virtual void advise(Space& home, Advisor& a);
1188 
1190  double afc(void) const;
1193 #ifdef GECODE_HAS_CBS
1195 
1196 
1203  typedef std::function<void(unsigned int prop_id, unsigned int var_id,
1204  int val, double dens)> SendMarginal;
1205  virtual void solndistrib(Space& home, SendMarginal send) const;
1214  typedef std::function<bool(unsigned int var_id)> InDecision;
1215  virtual void domainsizesum(InDecision in, unsigned int& size,
1216  unsigned int& size_b) const;
1218 #endif
1220 
1221  unsigned int id(void) const;
1224  PropagatorGroup group(void) const;
1226  void group(PropagatorGroup g);
1228  bool disabled(void) const;
1230  };
1231 
1232 
1240  template<class A>
1241  class Council {
1242  friend class Advisor;
1243  friend class Advisors<A>;
1244  private:
1246  mutable ActorLink* advisors;
1247  public:
1249  Council(void);
1251  Council(Space& home);
1253  bool empty(void) const;
1255  void update(Space& home, Council<A>& c);
1257  void dispose(Space& home);
1258  };
1259 
1260 
1265  template<class A>
1266  class Advisors {
1267  private:
1269  ActorLink* a;
1270  public:
1272  Advisors(const Council<A>& c);
1274  bool operator ()(void) const;
1276  void operator ++(void);
1278  A& advisor(void) const;
1279  };
1280 
1281 
1292  class Advisor : private ActorLink {
1293  template<class VIC> friend class VarImp;
1294  template<class A> friend class Council;
1295  template<class A> friend class Advisors;
1297  private:
1299  bool disposed(void) const;
1301  static Advisor* cast(ActorLink* al);
1303  static const Advisor* cast(const ActorLink* al);
1304  protected:
1306  Propagator& propagator(void) const;
1307  public:
1309  template<class A>
1310  Advisor(Space& home, Propagator& p, Council<A>& c);
1312  Advisor(Space& home, Advisor& a);
1314  const ViewTraceInfo& operator ()(const Space& home) const;
1315 
1317 
1318  template<class A>
1320  void dispose(Space& home, Council<A>& c);
1322  static void* operator new(size_t s, Space& home);
1324  static void operator delete(void* p, Space& home);
1326  private:
1327 #ifndef __GNUC__
1329  static void operator delete(void* p);
1330 #endif
1332  static void* operator new(size_t s);
1333  };
1334 
1335 
1341  private:
1343  void* nl;
1344  public:
1346  enum Status {
1349  NONE
1350  };
1352  NGL(void);
1354  NGL(Space& home);
1356  NGL(Space& home, NGL& ngl);
1358  virtual void subscribe(Space& home, Propagator& p) = 0;
1360  virtual void cancel(Space& home, Propagator& p) = 0;
1362  virtual void reschedule(Space& home, Propagator& p) = 0;
1364  virtual NGL::Status status(const Space& home) const = 0;
1366  virtual ExecStatus prune(Space& home) = 0;
1368  virtual NGL* copy(Space& home) = 0;
1371  virtual bool notice(void) const;
1373  virtual size_t dispose(Space& home);
1375 
1376  bool leaf(void) const;
1379  NGL* next(void) const;
1381  void leaf(bool l);
1383  void next(NGL* n);
1385  NGL* add(NGL* n, bool l);
1387 
1389  static void* operator new(size_t s, Space& home);
1392  static void operator delete(void* s, Space& home);
1394  static void operator delete(void* p);
1396  public:
1398  GECODE_KERNEL_EXPORT virtual ~NGL(void);
1400  static void* operator new(size_t s);
1401  };
1402 
1413  friend class Space;
1414  private:
1415  unsigned int bid;
1416  unsigned int alt;
1417 
1419  unsigned int id(void) const;
1420  protected:
1422  Choice(const Brancher& b, const unsigned int a);
1423  public:
1425  unsigned int alternatives(void) const;
1427  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1430  virtual void archive(Archive& e) const;
1431  };
1432 
1443  friend class ActorLink;
1444  friend class Space;
1445  friend class Choice;
1446  private:
1448  unsigned int bid;
1450  unsigned int gid;
1452  static Brancher* cast(ActorLink* al);
1454  static const Brancher* cast(const ActorLink* al);
1455  protected:
1457  Brancher(Home home);
1459  Brancher(Space& home, Brancher& b);
1460  public:
1462 
1463 
1471  virtual bool status(const Space& home) const = 0;
1479  virtual const Choice* choice(Space& home) = 0;
1481  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1488  virtual ExecStatus commit(Space& home, const Choice& c,
1489  unsigned int a) = 0;
1504  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1513  virtual void print(const Space& home, const Choice& c, unsigned int a,
1514  std::ostream& o) const;
1516 
1518  unsigned int id(void) const;
1521  BrancherGroup group(void) const;
1523  void group(BrancherGroup g);
1525  };
1526 
1533  class LocalObject : public Actor {
1534  friend class ActorLink;
1535  friend class Space;
1536  friend class LocalHandle;
1537  protected:
1539  LocalObject(Home home);
1541  LocalObject(Space& home, LocalObject& l);
1543  static LocalObject* cast(ActorLink* al);
1545  static const LocalObject* cast(const ActorLink* al);
1546  private:
1548  GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
1549  public:
1551  LocalObject* fwd(Space& home);
1552  };
1553 
1558  class LocalHandle {
1559  private:
1561  LocalObject* o;
1562  protected:
1564  LocalHandle(void);
1566  LocalHandle(LocalObject* lo);
1568  LocalHandle(const LocalHandle& lh);
1569  public:
1571  LocalHandle& operator =(const LocalHandle& lh);
1573  void update(Space& home, LocalHandle& lh);
1575  ~LocalHandle(void);
1576  protected:
1578  LocalObject* object(void) const;
1580  void object(LocalObject* n);
1581  };
1582 
1583 
1589  protected:
1591  unsigned long int n;
1592  public:
1594  NoGoods(void);
1597  virtual void post(Space& home) const;
1599  unsigned long int ng(void) const;
1601  void ng(unsigned long int n);
1603  virtual ~NoGoods(void);
1606  static NoGoods eng;
1607  };
1608 
1614  public:
1616  enum Type {
1620  PORTFOLIO
1621  };
1622  protected:
1624  const Type t;
1626 
1627  const unsigned long int r;
1630  const unsigned long int s;
1632  const unsigned long int f;
1634  const Space* l;
1636  const NoGoods& ng;
1638 
1640  const unsigned int a;
1643  public:
1645 
1646  MetaInfo(unsigned long int r,
1648  unsigned long int s,
1649  unsigned long int f,
1650  const Space* l,
1651  NoGoods& ng);
1653  MetaInfo(unsigned int a);
1655  Type type(void) const;
1658 
1659  unsigned long int restart(void) const;
1662  unsigned long int solution(void) const;
1664  unsigned long int fail(void) const;
1666  const Space* last(void) const;
1668  const NoGoods& nogoods(void) const;
1670 
1672  unsigned int asset(void) const;
1675  };
1676 
1684  SS_BRANCH
1685  };
1686 
1692  public:
1694  unsigned long int propagate;
1696  StatusStatistics(void);
1698  void reset(void);
1703  };
1704 
1710  public:
1712  CloneStatistics(void);
1714  void reset(void);
1719  };
1720 
1726  public:
1728  CommitStatistics(void);
1730  void reset(void);
1735  };
1736 
1737 
1738 
1743  friend class Actor;
1744  friend class Propagator;
1745  friend class PropagatorGroup;
1746  friend class Propagators;
1747  friend class Brancher;
1748  friend class BrancherGroup;
1749  friend class Branchers;
1750  friend class Advisor;
1751  template <class A> friend class Council;
1752  template<class VIC> friend class VarImp;
1753  template<class VarImp> friend class VarImpDisposer;
1754  friend class LocalObject;
1755  friend class Region;
1756  friend class AFC;
1757  friend class PostInfo;
1758  friend GECODE_KERNEL_EXPORT
1759  void trace(Home home, TraceFilter tf, int te, Tracer& t);
1760  private:
1765 #ifdef GECODE_HAS_CBS
1767  unsigned int var_id_counter;
1768 #endif
1770  ActorLink pl;
1772  ActorLink bl;
1778  Brancher* b_status;
1790  Brancher* b_commit;
1792  Brancher* brancher(unsigned int id);
1793 
1795  void kill(Brancher& b);
1797  void kill(Propagator& p);
1798 
1801  void kill_brancher(unsigned int id);
1802 
1804  static const unsigned reserved_bid = 0U;
1805 
1807  static const unsigned int sc_bits = 2;
1809  static const unsigned int sc_fast = 0;
1811  static const unsigned int sc_disabled = 1;
1813  static const unsigned int sc_trace = 2;
1814 
1815  union {
1817  struct {
1839  unsigned int bid_sc;
1841  unsigned int n_sub;
1844  } p;
1846  struct {
1853  } c;
1854  } pc;
1856  void enqueue(Propagator* p);
1861 #ifdef GECODE_HAS_VAR_DISPOSE
1863  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1865  VarImpBase* _vars_d[AllVarConf::idx_d];
1867  template<class VIC> VarImpBase* vars_d(void) const;
1869  template<class VIC> void vars_d(VarImpBase* x);
1870 #endif
1872  void update(ActorLink** sub);
1874 
1876  Actor** d_fst;
1878  Actor** d_cur;
1880  Actor** d_lst;
1881 
1883  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1885  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1887  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1888 
1902  GECODE_KERNEL_EXPORT Space* _clone(void);
1903 
1937  void _commit(const Choice& c, unsigned int a);
1938 
1970  void _trycommit(const Choice& c, unsigned int a);
1971 
1974  TraceRecorder* findtracerecorder(void);
1977  void post(const PostInfo& pi);
1978 
1986  void ap_notice_dispose(Actor* a, bool d);
1994  void ap_ignore_dispose(Actor* a, bool d);
1995  public:
2001  Space(void);
2011  Space(Space& s);
2017  virtual ~Space(void);
2024  virtual Space* copy(void) = 0;
2035  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2060  virtual bool master(const MetaInfo& mi);
2087  virtual bool slave(const MetaInfo& mi);
2088 
2089  /*
2090  * Member functions for search engines
2091  *
2092  */
2093 
2106  SpaceStatus status(StatusStatistics& stat=unused_status);
2107 
2140  const Choice* choice(void);
2141 
2152  const Choice* choice(Archive& e) const;
2153 
2169  Space* clone(CloneStatistics& stat=unused_clone) const;
2170 
2205  void commit(const Choice& c, unsigned int a,
2206  CommitStatistics& stat=unused_commit);
2239  void trycommit(const Choice& c, unsigned int a,
2240  CommitStatistics& stat=unused_commit);
2260  NGL* ngl(const Choice& c, unsigned int a);
2261 
2277  void print(const Choice& c, unsigned int a, std::ostream& o) const;
2278 
2288  void notice(Actor& a, ActorProperty p, bool duplicate=false);
2297  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2298 
2299 
2310  ExecStatus ES_SUBSUMED(Propagator& p);
2325  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
2336  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2347  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2348 
2359  template<class A>
2360  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
2371  template<class A>
2372  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
2384  template<class A>
2385  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
2386 
2394  void fail(void);
2403  bool failed(void) const;
2408  bool stable(void) const;
2409 
2411 
2412  Home operator ()(Propagator& p);
2415  Home operator ()(PropagatorGroup pg);
2417  Home operator ()(BrancherGroup bg);
2419 
2431  template<class T>
2432  T* alloc(long unsigned int n);
2439  template<class T>
2440  T* alloc(long int n);
2447  template<class T>
2448  T* alloc(unsigned int n);
2455  template<class T>
2456  T* alloc(int n);
2466  template<class T>
2467  void free(T* b, long unsigned int n);
2477  template<class T>
2478  void free(T* b, long int n);
2488  template<class T>
2489  void free(T* b, unsigned int n);
2499  template<class T>
2500  void free(T* b, int n);
2512  template<class T>
2513  T* realloc(T* b, long unsigned int n, long unsigned int m);
2525  template<class T>
2526  T* realloc(T* b, long int n, long int m);
2538  template<class T>
2539  T* realloc(T* b, unsigned int n, unsigned int m);
2551  template<class T>
2552  T* realloc(T* b, int n, int m);
2560  template<class T>
2561  T** realloc(T** b, long unsigned int n, long unsigned int m);
2569  template<class T>
2570  T** realloc(T** b, long int n, long int m);
2578  template<class T>
2579  T** realloc(T** b, unsigned int n, unsigned int m);
2587  template<class T>
2588  T** realloc(T** b, int n, int m);
2590  void* ralloc(size_t s);
2592  void rfree(void* p, size_t s);
2594  void* rrealloc(void* b, size_t n, size_t m);
2596  template<size_t> void* fl_alloc(void);
2602  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2604 
2606 
2609  template<class T>
2610  T& construct(void);
2616  template<class T, typename A1>
2617  T& construct(A1 const& a1);
2623  template<class T, typename A1, typename A2>
2624  T& construct(A1 const& a1, A2 const& a2);
2630  template<class T, typename A1, typename A2, typename A3>
2631  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2637  template<class T, typename A1, typename A2, typename A3, typename A4>
2638  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2644  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2645  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2647 
2649 
2650  void afc_decay(double d);
2653  double afc_decay(void) const;
2655  GECODE_KERNEL_EXPORT void afc_unshare(void);
2657 
2658  protected:
2664  class Propagators {
2665  private:
2667  Space& home;
2669  ActorLink* q;
2671  ActorLink* c;
2673  ActorLink* e;
2674  public:
2676  Propagators(Space& home);
2678  bool operator ()(void) const;
2680  void operator ++(void);
2682  Propagator& propagator(void) const;
2683  };
2690  private:
2692  Space& home;
2694  ActorLink* q;
2696  ActorLink* c;
2698  ActorLink* e;
2699  public:
2701  ScheduledPropagators(Space& home);
2703  bool operator ()(void) const;
2705  void operator ++(void);
2707  Propagator& propagator(void) const;
2708  };
2715  private:
2717  ActorLink* c;
2719  ActorLink* e;
2720  public:
2722  IdlePropagators(Space& home);
2724  bool operator ()(void) const;
2726  void operator ++(void);
2728  Propagator& propagator(void) const;
2729  };
2735  class Branchers {
2736  private:
2738  ActorLink* c;
2740  ActorLink* e;
2741  public:
2743  Branchers(Space& home);
2745  bool operator ()(void) const;
2747  void operator ++(void);
2749  Brancher& brancher(void) const;
2750  };
2751  };
2752 
2754  class Propagators {
2755  private:
2757  Space::Propagators ps;
2759  PropagatorGroup g;
2760  public:
2762  Propagators(const Space& home, PropagatorGroup g);
2764  bool operator ()(void) const;
2766  void operator ++(void);
2768  const Propagator& propagator(void) const;
2769  };
2770 
2772  class Branchers {
2773  private:
2775  Space::Branchers bs;
2777  BrancherGroup g;
2778  public:
2780  Branchers(const Space& home, BrancherGroup g);
2782  bool operator ()(void) const;
2784  void operator ++(void);
2786  const Brancher& brancher(void) const;
2787  };
2788 
2789 
2790 
2791 
2792  /*
2793  * Memory management
2794  *
2795  */
2796 
2797  // Space allocation: general space heaps and free lists
2798  forceinline void*
2799  Space::ralloc(size_t s) {
2800  return mm.alloc(ssd.data().sm,s);
2801  }
2802  forceinline void
2803  Space::rfree(void* p, size_t s) {
2804  return mm.reuse(p,s);
2805  }
2806  forceinline void*
2807  Space::rrealloc(void* _b, size_t n, size_t m) {
2808  char* b = static_cast<char*>(_b);
2809  if (n < m) {
2810  char* p = static_cast<char*>(ralloc(m));
2811  memcpy(p,b,n);
2812  rfree(b,n);
2813  return p;
2814  } else {
2815  rfree(b+m,m-n);
2816  return b;
2817  }
2818  }
2819 
2820  template<size_t s>
2821  forceinline void*
2823  return mm.template fl_alloc<s>(ssd.data().sm);
2824  }
2825  template<size_t s>
2826  forceinline void
2828  mm.template fl_dispose<s>(f,l);
2829  }
2830 
2831  /*
2832  * Typed allocation routines
2833  *
2834  */
2835  template<class T>
2836  forceinline T*
2837  Space::alloc(long unsigned int n) {
2838  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2839  for (long unsigned int i=0; i<n; i++)
2840  (void) new (p+i) T();
2841  return p;
2842  }
2843  template<class T>
2844  forceinline T*
2845  Space::alloc(long int n) {
2846  assert(n >= 0);
2847  return alloc<T>(static_cast<long unsigned int>(n));
2848  }
2849  template<class T>
2850  forceinline T*
2851  Space::alloc(unsigned int n) {
2852  return alloc<T>(static_cast<long unsigned int>(n));
2853  }
2854  template<class T>
2855  forceinline T*
2857  assert(n >= 0);
2858  return alloc<T>(static_cast<long unsigned int>(n));
2859  }
2860 
2861  template<class T>
2862  forceinline void
2863  Space::free(T* b, long unsigned int n) {
2864  for (long unsigned int i=0; i<n; i++)
2865  b[i].~T();
2866  rfree(b,n*sizeof(T));
2867  }
2868  template<class T>
2869  forceinline void
2870  Space::free(T* b, long int n) {
2871  assert(n >= 0);
2872  free<T>(b,static_cast<long unsigned int>(n));
2873  }
2874  template<class T>
2875  forceinline void
2876  Space::free(T* b, unsigned int n) {
2877  free<T>(b,static_cast<long unsigned int>(n));
2878  }
2879  template<class T>
2880  forceinline void
2881  Space::free(T* b, int n) {
2882  assert(n >= 0);
2883  free<T>(b,static_cast<long unsigned int>(n));
2884  }
2885 
2886  template<class T>
2887  forceinline T*
2888  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2889  if (n < m) {
2890  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2891  for (long unsigned int i=0; i<n; i++)
2892  (void) new (p+i) T(b[i]);
2893  for (long unsigned int i=n; i<m; i++)
2894  (void) new (p+i) T();
2895  free<T>(b,n);
2896  return p;
2897  } else {
2898  free<T>(b+m,m-n);
2899  return b;
2900  }
2901  }
2902  template<class T>
2903  forceinline T*
2904  Space::realloc(T* b, long int n, long int m) {
2905  assert((n >= 0) && (m >= 0));
2906  return realloc<T>(b,static_cast<long unsigned int>(n),
2907  static_cast<long unsigned int>(m));
2908  }
2909  template<class T>
2910  forceinline T*
2911  Space::realloc(T* b, unsigned int n, unsigned int m) {
2912  return realloc<T>(b,static_cast<long unsigned int>(n),
2913  static_cast<long unsigned int>(m));
2914  }
2915  template<class T>
2916  forceinline T*
2917  Space::realloc(T* b, int n, int m) {
2918  assert((n >= 0) && (m >= 0));
2919  return realloc<T>(b,static_cast<long unsigned int>(n),
2920  static_cast<long unsigned int>(m));
2921  }
2922 
2923 #define GECODE_KERNEL_REALLOC(T) \
2924  template<> \
2925  forceinline T* \
2926  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2927  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2928  } \
2929  template<> \
2930  forceinline T* \
2931  Space::realloc<T>(T* b, long int n, long int m) { \
2932  assert((n >= 0) && (m >= 0)); \
2933  return realloc<T>(b,static_cast<long unsigned int>(n), \
2934  static_cast<long unsigned int>(m)); \
2935  } \
2936  template<> \
2937  forceinline T* \
2938  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2939  return realloc<T>(b,static_cast<long unsigned int>(n), \
2940  static_cast<long unsigned int>(m)); \
2941  } \
2942  template<> \
2943  forceinline T* \
2944  Space::realloc<T>(T* b, int n, int m) { \
2945  assert((n >= 0) && (m >= 0)); \
2946  return realloc<T>(b,static_cast<long unsigned int>(n), \
2947  static_cast<long unsigned int>(m)); \
2948  }
2949 
2950  GECODE_KERNEL_REALLOC(bool)
2951  GECODE_KERNEL_REALLOC(signed char)
2952  GECODE_KERNEL_REALLOC(unsigned char)
2953  GECODE_KERNEL_REALLOC(signed short int)
2954  GECODE_KERNEL_REALLOC(unsigned short int)
2955  GECODE_KERNEL_REALLOC(signed int)
2956  GECODE_KERNEL_REALLOC(unsigned int)
2957  GECODE_KERNEL_REALLOC(signed long int)
2958  GECODE_KERNEL_REALLOC(unsigned long int)
2959  GECODE_KERNEL_REALLOC(float)
2960  GECODE_KERNEL_REALLOC(double)
2961 
2962 #undef GECODE_KERNEL_REALLOC
2963 
2964  template<class T>
2965  forceinline T**
2966  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2967  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2968  }
2969  template<class T>
2970  forceinline T**
2971  Space::realloc(T** b, long int n, long int m) {
2972  assert((n >= 0) && (m >= 0));
2973  return realloc<T*>(b,static_cast<long unsigned int>(n),
2974  static_cast<long unsigned int>(m));
2975  }
2976  template<class T>
2977  forceinline T**
2978  Space::realloc(T** b, unsigned int n, unsigned int m) {
2979  return realloc<T*>(b,static_cast<long unsigned int>(n),
2980  static_cast<long unsigned int>(m));
2981  }
2982  template<class T>
2983  forceinline T**
2984  Space::realloc(T** b, int n, int m) {
2985  assert((n >= 0) && (m >= 0));
2986  return realloc<T*>(b,static_cast<long unsigned int>(n),
2987  static_cast<long unsigned int>(m));
2988  }
2989 
2990 
2991 #ifdef GECODE_HAS_VAR_DISPOSE
2992  template<class VIC>
2994  Space::vars_d(void) const {
2995  return _vars_d[VIC::idx_d];
2996  }
2997  template<class VIC>
2998  forceinline void
2999  Space::vars_d(VarImpBase* x) {
3000  _vars_d[VIC::idx_d] = x;
3001  }
3002 #endif
3003 
3004  // Space allocated entities: Actors, variable implementations, and advisors
3005  forceinline void
3006  Actor::operator delete(void*) {}
3007  forceinline void
3008  Actor::operator delete(void*, Space&) {}
3009  forceinline void*
3010  Actor::operator new(size_t s, Space& home) {
3011  return home.ralloc(s);
3012  }
3013 
3014  template<class VIC>
3015  forceinline void
3016  VarImp<VIC>::operator delete(void*) {}
3017  template<class VIC>
3018  forceinline void
3019  VarImp<VIC>::operator delete(void*, Space&) {}
3020  template<class VIC>
3021  forceinline void*
3022  VarImp<VIC>::operator new(size_t s, Space& home) {
3023  return home.ralloc(s);
3024  }
3025 
3026 #ifndef __GNUC__
3027  forceinline void
3028  Advisor::operator delete(void*) {}
3029 #endif
3030  forceinline void
3031  Advisor::operator delete(void*, Space&) {}
3032  forceinline void*
3033  Advisor::operator new(size_t s, Space& home) {
3034  return home.ralloc(s);
3035  }
3036 
3037  forceinline void
3038  NGL::operator delete(void*) {}
3039  forceinline void
3040  NGL::operator delete(void*, Space&) {}
3041  forceinline void*
3042  NGL::operator new(size_t s, Space& home) {
3043  return home.ralloc(s);
3044  }
3045 
3046 
3047  /*
3048  * No-goods
3049  *
3050  */
3051  forceinline
3053  : n(0) {}
3054  forceinline unsigned long int
3055  NoGoods::ng(void) const {
3056  return n;
3057  }
3058  forceinline void
3059  NoGoods::ng(unsigned long int n0) {
3060  n=n0;
3061  }
3062  forceinline
3064 
3065 
3066  /*
3067  * Information from meta search engines
3068  */
3069  forceinline
3070  MetaInfo::MetaInfo(unsigned long int r0,
3071  unsigned long int s0,
3072  unsigned long int f0,
3073  const Space* l0,
3074  NoGoods& ng0)
3075  : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3076 
3077  forceinline
3078  MetaInfo::MetaInfo(unsigned int a0)
3079  : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
3080 
3082  MetaInfo::type(void) const {
3083  return t;
3084  }
3085  forceinline unsigned long int
3086  MetaInfo::restart(void) const {
3087  assert(type() == RESTART);
3088  return r;
3089  }
3090  forceinline unsigned long int
3091  MetaInfo::solution(void) const {
3092  assert(type() == RESTART);
3093  return s;
3094  }
3095  forceinline unsigned long int
3096  MetaInfo::fail(void) const {
3097  assert(type() == RESTART);
3098  return f;
3099  }
3100  forceinline const Space*
3101  MetaInfo::last(void) const {
3102  assert(type() == RESTART);
3103  return l;
3104  }
3105  forceinline const NoGoods&
3106  MetaInfo::nogoods(void) const {
3107  assert(type() == RESTART);
3108  return ng;
3109  }
3110  forceinline unsigned int
3111  MetaInfo::asset(void) const {
3112  assert(type() == PORTFOLIO);
3113  return a;
3114  }
3115 
3116 
3117 
3118  /*
3119  * ActorLink
3120  *
3121  */
3123  ActorLink::prev(void) const {
3124  return _prev;
3125  }
3126 
3128  ActorLink::next(void) const {
3129  return _next;
3130  }
3131 
3134  return &_next;
3135  }
3136 
3137  forceinline void
3139  _prev = al;
3140  }
3141 
3142  forceinline void
3144  _next = al;
3145  }
3146 
3147  forceinline void
3149  ActorLink* p = _prev; ActorLink* n = _next;
3150  p->_next = n; n->_prev = p;
3151  }
3152 
3153  forceinline void
3155  _next = this; _prev =this;
3156  }
3157 
3158  forceinline void
3160  // Inserts al at head of link-chain (that is, after this)
3161  ActorLink* n = _next;
3162  this->_next = a; a->_prev = this;
3163  a->_next = n; n->_prev = a;
3164  }
3165 
3166  forceinline void
3168  // Inserts al at tail of link-chain (that is, before this)
3169  ActorLink* p = _prev;
3170  a->_next = this; this->_prev = a;
3171  p->_next = a; a->_prev = p;
3172  }
3173 
3174  forceinline bool
3175  ActorLink::empty(void) const {
3176  return _next == this;
3177  }
3178 
3179  template<class T>
3182  // Turning al into a reference is for gcc, assume is for MSVC
3183  GECODE_NOT_NULL(a);
3184  ActorLink& t = *a;
3185  return static_cast<ActorLink*>(&t);
3186  }
3187 
3188  template<class T>
3189  forceinline const ActorLink*
3190  ActorLink::cast(const T* a) {
3191  // Turning al into a reference is for gcc, assume is for MSVC
3192  GECODE_NOT_NULL(a);
3193  const ActorLink& t = *a;
3194  return static_cast<const ActorLink*>(&t);
3195  }
3196 
3197 
3198  /*
3199  * Actor
3200  *
3201  */
3203  Actor::cast(ActorLink* al) {
3204  // Turning al into a reference is for gcc, assume is for MSVC
3205  GECODE_NOT_NULL(al);
3206  ActorLink& t = *al;
3207  return static_cast<Actor*>(&t);
3208  }
3209 
3210  forceinline const Actor*
3211  Actor::cast(const ActorLink* al) {
3212  // Turning al into a reference is for gcc, assume is for MSVC
3213  GECODE_NOT_NULL(al);
3214  const ActorLink& t = *al;
3215  return static_cast<const Actor*>(&t);
3216  }
3217 
3218  forceinline void
3219  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3220  s.notice(a,p,duplicate);
3221  }
3222 
3225  // Clone is only const for search engines. During cloning, several data
3226  // structures are updated (e.g. forwarding pointers), so we have to
3227  // cast away the constness.
3228  return const_cast<Space*>(this)->_clone();
3229  }
3230 
3231  forceinline void
3232  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3233  _commit(c,a);
3234  }
3235 
3236  forceinline void
3237  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3238  _trycommit(c,a);
3239  }
3240 
3241  forceinline double
3242  Space::afc_decay(void) const {
3243  return ssd.data().gpi.decay();
3244  }
3245 
3246  forceinline void
3248  ssd.data().gpi.decay(d);
3249  }
3250 
3251  forceinline size_t
3253  return sizeof(*this);
3254  }
3255 
3256 
3257  /*
3258  * Home for posting actors
3259  *
3260  */
3261  forceinline
3263  PropagatorGroup pg0, BrancherGroup bg0)
3264  : s(s0), p(p0), pg(pg0), bg(bg0) {}
3265  forceinline Home&
3267  s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3268  return *this;
3269  }
3270  forceinline
3271  Home::operator Space&(void) {
3272  return s;
3273  }
3276  return Home(s,&p);
3277  }
3280  return Home(s,NULL,pg,BrancherGroup::def);
3281  }
3284  return Home(s,NULL,PropagatorGroup::def,bg);
3285  }
3288  return Home(*this,&p);
3289  }
3292  return Home(*this,NULL,pg,BrancherGroup::def);
3293  }
3296  return Home(*this,NULL,PropagatorGroup::def,bg);
3297  }
3299  Home::propagator(void) const {
3300  return p;
3301  }
3304  return pg;
3305  }
3307  Home::branchergroup(void) const {
3308  return bg;
3309  }
3310 
3311  /*
3312  * View trace information
3313  *
3314  */
3315  forceinline void
3317  who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3318  }
3319  forceinline void
3321  who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3322  }
3323  forceinline void
3325  who = (g.id() << 2) | POST;
3326  }
3327  forceinline void
3329  who = OTHER;
3330  }
3332  ViewTraceInfo::what(void) const {
3333  return static_cast<What>(who & 3);
3334  }
3335  forceinline const Propagator&
3337  assert(what() == PROPAGATOR);
3338  // Because PROPAGATOR == 0
3339  return *reinterpret_cast<Propagator*>(who);
3340  }
3341  forceinline const Brancher&
3343  assert(what() == BRANCHER);
3344  return *reinterpret_cast<Brancher*>(who & ~3);
3345  }
3347  ViewTraceInfo::post(void) const {
3348  assert(what() == POST);
3349  return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3350  }
3351 
3352  /*
3353  * Post information
3354  */
3355  forceinline
3357  : h(home), pg(home.propagatorgroup()),
3358  pid(h.ssd.data().gpi.pid()),
3359  nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
3360  h.pc.p.vti.post(pg);
3361  }
3362 
3363  forceinline
3365  if (!nested) {
3366  if (h.pc.p.bid_sc & Space::sc_trace)
3367  h.post(*this);
3368  h.pc.p.vti.other();
3369  }
3370  }
3371 
3372 
3373  /*
3374  * Propagate trace information
3375  *
3376  */
3377  forceinline
3379  const Propagator* p0, Status s0)
3380  : i(i0), g(g0), p(p0), s(s0) {}
3381  forceinline unsigned int
3383  return i;
3384  }
3387  return g;
3388  }
3389  forceinline const Propagator*
3391  return p;
3392  }
3395  return s;
3396  }
3397 
3398 
3399  /*
3400  * Commit trace information
3401  *
3402  */
3403  forceinline
3405  unsigned int a0)
3406  : b(b0), c(c0), a(a0) {}
3407  forceinline unsigned int
3408  CommitTraceInfo::id(void) const {
3409  return b.id();
3410  }
3413  return b.group();
3414  }
3415  forceinline const Brancher&
3417  return b;
3418  }
3419  forceinline const Choice&
3421  return c;
3422  }
3423  forceinline unsigned int
3425  return a;
3426  }
3427 
3428 
3429  /*
3430  * Post trace information
3431  *
3432  */
3433  forceinline
3435  : g(g0), s(s0), n(n0) {}
3437  PostTraceInfo::group(void) const {
3438  return g;
3439  }
3442  return s;
3443  }
3444  forceinline unsigned int
3446  return n;
3447  }
3448 
3449 
3450  /*
3451  * Propagator
3452  *
3453  */
3455  Propagator::cast(ActorLink* al) {
3456  // Turning al into a reference is for gcc, assume is for MSVC
3457  GECODE_NOT_NULL(al);
3458  ActorLink& t = *al;
3459  return static_cast<Propagator*>(&t);
3460  }
3461 
3462  forceinline const Propagator*
3463  Propagator::cast(const ActorLink* al) {
3464  // Turning al into a reference is for gcc, assume is for MSVC
3465  GECODE_NOT_NULL(al);
3466  const ActorLink& t = *al;
3467  return static_cast<const Propagator*>(&t);
3468  }
3469 
3470  forceinline Propagator*
3471  Propagator::fwd(void) const {
3472  return static_cast<Propagator*>(prev());
3473  }
3474 
3475  forceinline bool
3476  Propagator::disabled(void) const {
3477  return Support::marked(gpi_disabled);
3478  }
3479 
3480  forceinline void
3481  Propagator::disable(Space& home) {
3482  home.pc.p.bid_sc |= Space::sc_disabled;
3483  gpi_disabled = Support::fmark(gpi_disabled);
3484  }
3485 
3486  forceinline void
3487  Propagator::enable(Space& home) {
3488  (void) home;
3489  gpi_disabled = Support::funmark(gpi_disabled);
3490  }
3491 
3492  forceinline Kernel::GPI::Info&
3494  return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
3495  }
3496 
3497  forceinline
3499  : gpi_disabled((home.propagator() != NULL) ?
3500  // Inherit propagator information
3501  home.propagator()->gpi_disabled :
3502  // New propagator information
3503  static_cast<Space&>(home).ssd.data().gpi.allocate
3504  (home.propagatorgroup().gid)) {
3505  u.advisors = NULL;
3506  assert((u.med == 0) && (u.size == 0));
3507  static_cast<Space&>(home).pl.head(this);
3508  }
3509 
3510  forceinline
3512  : gpi_disabled(p.gpi_disabled) {
3513  u.advisors = NULL;
3514  assert((u.med == 0) && (u.size == 0));
3515  // Set forwarding pointer
3516  p.prev(this);
3517  }
3518 
3521  return u.med;
3522  }
3523 
3524  forceinline double
3525  Propagator::afc(void) const {
3526  return const_cast<Propagator&>(*this).gpi().afc;
3527  }
3528 
3529 #ifdef GECODE_HAS_CBS
3530  forceinline void
3531  Propagator::solndistrib(Space&, SendMarginal) const {}
3532 
3533  forceinline void
3534  Propagator::domainsizesum(InDecision, unsigned int& size,
3535  unsigned int& size_b) const {
3536  size = 0;
3537  size_b = 0;
3538  }
3539 #endif
3540 
3541  forceinline unsigned int
3542  Propagator::id(void) const {
3543  return const_cast<Propagator&>(*this).gpi().pid;
3544  }
3545 
3547  Propagator::group(void) const {
3548  return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3549  }
3550 
3551  forceinline void
3553  gpi().gid = g.id();
3554  }
3555 
3558  p.u.size = s;
3559  return __ES_SUBSUMED;
3560  }
3561 
3564  p.u.size = p.dispose(*this);
3565  return __ES_SUBSUMED;
3566  }
3567 
3570  p.u.med = med;
3571  assert(p.u.med != 0);
3572  return __ES_PARTIAL;
3573  }
3574 
3577  p.u.med = AllVarConf::med_combine(p.u.med,med);
3578  assert(p.u.med != 0);
3579  return __ES_PARTIAL;
3580  }
3581 
3582 
3583 
3584  /*
3585  * Brancher
3586  *
3587  */
3589  Brancher::cast(ActorLink* al) {
3590  // Turning al into a reference is for gcc, assume is for MSVC
3591  GECODE_NOT_NULL(al);
3592  ActorLink& t = *al;
3593  return static_cast<Brancher*>(&t);
3594  }
3595 
3596  forceinline const Brancher*
3597  Brancher::cast(const ActorLink* al) {
3598  // Turning al into a reference is for gcc, assume is for MSVC
3599  GECODE_NOT_NULL(al);
3600  const ActorLink& t = *al;
3601  return static_cast<const Brancher*>(&t);
3602  }
3603 
3604  forceinline
3606  gid(_home.branchergroup().gid) {
3607  Space& home = static_cast<Space&>(_home);
3608  bid = home.pc.p.bid_sc >> Space::sc_bits;
3609  home.pc.p.bid_sc += (1 << Space::sc_bits);
3610  if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3611  throw TooManyBranchers("Brancher::Brancher");
3612  // If no brancher available, make it the first one
3613  if (home.b_status == &static_cast<Space&>(home).bl) {
3614  home.b_status = this;
3615  if (home.b_commit == &static_cast<Space&>(home).bl)
3616  home.b_commit = this;
3617  }
3618  home.bl.tail(this);
3619  }
3620 
3621  forceinline
3623  : bid(b.bid), gid(b.gid) {
3624  // Set forwarding pointer
3625  b.prev(this);
3626  }
3627 
3628  forceinline unsigned int
3629  Brancher::id(void) const {
3630  return bid;
3631  }
3632 
3634  Brancher::group(void) const {
3635  return BrancherGroup(gid);
3636  }
3637 
3638  forceinline void
3640  gid = g.id();
3641  }
3642 
3643 
3644  forceinline void
3645  Space::kill(Brancher& b) {
3646  assert(!failed());
3647  // Make sure that neither b_status nor b_commit does not point to b!
3648  if (b_commit == &b)
3649  b_commit = Brancher::cast(b.next());
3650  if (b_status == &b)
3651  b_status = Brancher::cast(b.next());
3652  b.unlink();
3653  rfree(&b,b.dispose(*this));
3654  }
3655 
3656  forceinline void
3657  Space::kill(Propagator& p) {
3658  assert(!failed());
3659  p.unlink();
3660  rfree(&p,p.dispose(*this));
3661  }
3662 
3663  forceinline Brancher*
3664  Space::brancher(unsigned int id) {
3665  /*
3666  * Due to weakly monotonic propagators the following scenario might
3667  * occur: a brancher has been committed with all its available
3668  * choices. Then, propagation determines less information
3669  * than before and the brancher now will create new choices.
3670  * Later, during recomputation, all of these choices
3671  * can be used together, possibly interleaved with
3672  * choices for other branchers. That means all branchers
3673  * must be scanned to find the matching brancher for the choice.
3674  *
3675  * b_commit tries to optimize scanning as it is most likely that
3676  * recomputation does not generate new choices during recomputation
3677  * and hence b_commit is moved from newer to older branchers.
3678  */
3679  Brancher* b_old = b_commit;
3680  // Try whether we are lucky
3681  while (b_commit != Brancher::cast(&bl))
3682  if (id != b_commit->id())
3683  b_commit = Brancher::cast(b_commit->next());
3684  else
3685  return b_commit;
3686  if (b_commit == Brancher::cast(&bl)) {
3687  // We did not find the brancher, start at the beginning
3688  b_commit = Brancher::cast(bl.next());
3689  while (b_commit != b_old)
3690  if (id != b_commit->id())
3691  b_commit = Brancher::cast(b_commit->next());
3692  else
3693  return b_commit;
3694  }
3695  return NULL;
3696  }
3697 
3698 
3699  /*
3700  * Local objects
3701  *
3702  */
3703 
3704  forceinline LocalObject*
3706  // Turning al into a reference is for gcc, assume is for MSVC
3707  GECODE_NOT_NULL(al);
3708  ActorLink& t = *al;
3709  return static_cast<LocalObject*>(&t);
3710  }
3711 
3712  forceinline const LocalObject*
3714  // Turning al into a reference is for gcc, assume is for MSVC
3715  GECODE_NOT_NULL(al);
3716  const ActorLink& t = *al;
3717  return static_cast<const LocalObject*>(&t);
3718  }
3719 
3720  forceinline
3722  (void) home;
3723  ActorLink::cast(this)->prev(NULL);
3724  }
3725 
3726  forceinline
3728  ActorLink::cast(this)->prev(NULL);
3729  }
3730 
3733  if (prev() == NULL)
3734  fwdcopy(home);
3735  return LocalObject::cast(prev());
3736  }
3737 
3738  forceinline
3739  LocalHandle::LocalHandle(void) : o(NULL) {}
3740  forceinline
3742  forceinline
3743  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3746  o = lh.o;
3747  return *this;
3748  }
3749  forceinline
3752  LocalHandle::object(void) const { return o; }
3753  forceinline void
3755  forceinline void
3757  object(lh.object()->fwd(home));
3758  }
3759 
3760 
3761  /*
3762  * Choices
3763  *
3764  */
3765  forceinline
3766  Choice::Choice(const Brancher& b, const unsigned int a)
3767  : bid(b.id()), alt(a) {}
3768 
3769  forceinline unsigned int
3770  Choice::alternatives(void) const {
3771  return alt;
3772  }
3773 
3774  forceinline unsigned int
3775  Choice::id(void) const {
3776  return bid;
3777  }
3778 
3779  forceinline
3781 
3782 
3783 
3784  /*
3785  * No-good literal
3786  *
3787  */
3788  forceinline bool
3789  NGL::leaf(void) const {
3790  return Support::marked(nl);
3791  }
3792  forceinline NGL*
3793  NGL::next(void) const {
3794  return static_cast<NGL*>(Support::funmark(nl));
3795  }
3796  forceinline void
3797  NGL::leaf(bool l) {
3798  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3799  }
3800  forceinline void
3802  nl = Support::marked(nl) ? Support::mark(n) : n;
3803  }
3804  forceinline NGL*
3805  NGL::add(NGL* n, bool l) {
3806  nl = Support::marked(nl) ? Support::mark(n) : n;
3807  n->leaf(l);
3808  return n;
3809  }
3810 
3811  forceinline
3812  NGL::NGL(void)
3813  : nl(NULL) {}
3814  forceinline
3816  : nl(NULL) {}
3817  forceinline
3819  : nl(NULL) {}
3820  forceinline size_t
3822  return sizeof(*this);
3823  }
3824 
3825  /*
3826  * Advisor
3827  *
3828  */
3829  template<class A>
3830  forceinline
3832  // Store propagator and forwarding in prev()
3833  ActorLink::prev(&p);
3834  // Link to next advisor in next()
3835  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3836  }
3837 
3838  forceinline
3840 
3841  forceinline bool
3842  Advisor::disposed(void) const {
3843  return prev() == NULL;
3844  }
3845 
3846  forceinline Advisor*
3847  Advisor::cast(ActorLink* al) {
3848  return static_cast<Advisor*>(al);
3849  }
3850 
3851  forceinline const Advisor*
3852  Advisor::cast(const ActorLink* al) {
3853  return static_cast<const Advisor*>(al);
3854  }
3855 
3856  forceinline Propagator&
3857  Advisor::propagator(void) const {
3858  assert(!disposed());
3859  return *Propagator::cast(ActorLink::prev());
3860  }
3861 
3862  template<class A>
3863  forceinline void
3865  assert(!disposed());
3866  ActorLink::prev(NULL);
3867  // Shorten chains of disposed advisors by one, if possible
3868  Advisor* n = Advisor::cast(next());
3869  if ((n != NULL) && n->disposed())
3870  next(n->next());
3871  }
3872 
3873  forceinline const ViewTraceInfo&
3874  Advisor::operator ()(const Space& home) const {
3875  return home.pc.p.vti;
3876  }
3877 
3878  template<class A>
3881  a.dispose(*this,c);
3882  return ES_FIX;
3883  }
3884 
3885  template<class A>
3888  a.dispose(*this,c);
3889  return ES_NOFIX;
3890  }
3891 
3892  template<class A>
3895  a.dispose(*this,c);
3896  return ES_NOFIX_FORCE;
3897  }
3898 
3899 
3900 
3901  /*
3902  * Advisor council
3903  *
3904  */
3905  template<class A>
3906  forceinline
3908 
3909  template<class A>
3910  forceinline
3912  : advisors(NULL) {}
3913 
3914  template<class A>
3915  forceinline bool
3916  Council<A>::empty(void) const {
3917  ActorLink* a = advisors;
3918  while ((a != NULL) && static_cast<A*>(a)->disposed())
3919  a = a->next();
3920  advisors = a;
3921  return a == NULL;
3922  }
3923 
3924  template<class A>
3925  forceinline void
3927  // Skip all disposed advisors
3928  {
3929  ActorLink* a = c.advisors;
3930  while ((a != NULL) && static_cast<A*>(a)->disposed())
3931  a = a->next();
3932  c.advisors = a;
3933  }
3934  // Are there any advisors to be cloned?
3935  if (c.advisors != NULL) {
3936  // The propagator in from-space
3937  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3938  // The propagator in to-space
3939  Propagator* p_t = Propagator::cast(p_f->prev());
3940  // Advisors in from-space
3941  ActorLink** a_f = &c.advisors;
3942  // Advisors in to-space
3943  A* a_t = NULL;
3944  while (*a_f != NULL) {
3945  if (static_cast<A*>(*a_f)->disposed()) {
3946  *a_f = (*a_f)->next();
3947  } else {
3948  // Run specific copying part
3949  A* a = new (home) A(home,*static_cast<A*>(*a_f));
3950  // Set propagator pointer
3951  a->prev(p_t);
3952  // Set forwarding pointer
3953  (*a_f)->prev(a);
3954  // Link
3955  a->next(a_t);
3956  a_t = a;
3957  a_f = (*a_f)->next_ref();
3958  }
3959  }
3960  advisors = a_t;
3961  // Enter advisor link for reset
3962  assert(p_f->u.advisors == NULL);
3963  p_f->u.advisors = c.advisors;
3964  } else {
3965  advisors = NULL;
3966  }
3967  }
3968 
3969  template<class A>
3970  forceinline void
3972  ActorLink* a = advisors;
3973  while (a != NULL) {
3974  if (!static_cast<A*>(a)->disposed())
3975  static_cast<A*>(a)->dispose(home,*this);
3976  a = a->next();
3977  }
3978  }
3979 
3980 
3981 
3982  /*
3983  * Advisor iterator
3984  *
3985  */
3986  template<class A>
3987  forceinline
3989  : a(c.advisors) {
3990  while ((a != NULL) && static_cast<A*>(a)->disposed())
3991  a = a->next();
3992  }
3993 
3994  template<class A>
3995  forceinline bool
3997  return a != NULL;
3998  }
3999 
4000  template<class A>
4001  forceinline void
4003  do {
4004  a = a->next();
4005  } while ((a != NULL) && static_cast<A*>(a)->disposed());
4006  }
4007 
4008  template<class A>
4009  forceinline A&
4010  Advisors<A>::advisor(void) const {
4011  return *static_cast<A*>(a);
4012  }
4013 
4014 
4015 
4016  /*
4017  * Space
4018  *
4019  */
4020  forceinline void
4021  Space::enqueue(Propagator* p) {
4022  ActorLink::cast(p)->unlink();
4023  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
4024  c->tail(ActorLink::cast(p));
4025  if (c > pc.p.active)
4026  pc.p.active = c;
4027  }
4028 
4029  forceinline void
4030  Space::fail(void) {
4031  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
4032  /*
4033  * Now active points beyond the last queue. This is essential as
4034  * enqueuing a propagator in a failed space keeps the space
4035  * failed.
4036  */
4037  }
4038  forceinline void
4039  Home::fail(void) {
4040  s.fail();
4041  }
4042 
4043  forceinline bool
4044  Space::failed(void) const {
4045  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4046  }
4047  forceinline bool
4048  Home::failed(void) const {
4049  return s.failed();
4050  }
4051 
4052  forceinline bool
4053  Space::stable(void) const {
4054  return ((pc.p.active < &pc.p.queue[0]) ||
4055  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
4056  }
4057 
4058  forceinline void
4060  if (p & AP_DISPOSE) {
4061  ap_notice_dispose(&a,d);
4062  }
4063  if (p & AP_VIEW_TRACE) {
4064  pc.p.bid_sc |= sc_trace;
4065  }
4066  if (p & AP_TRACE) {
4067  pc.p.bid_sc |= sc_trace;
4068  }
4069  // Currently unused
4070  if (p & AP_WEAKLY) {}
4071  }
4072 
4073  forceinline void
4075  // Check wether array has already been discarded as space
4076  // deletion is already in progress
4077  if ((p & AP_DISPOSE) && (d_fst != NULL))
4078  ap_ignore_dispose(&a,d);
4079  if (p & AP_VIEW_TRACE) {}
4080  if (p & AP_TRACE) {}
4081  // Currently unused
4082  if (p & AP_WEAKLY) {}
4083  }
4084 
4085 
4086 
4087  /*
4088  * Variable implementation
4089  *
4090  */
4091  template<class VIC>
4094  assert((pc >= 0) && (pc < pc_max+2));
4095  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4096  }
4097 
4098  template<class VIC>
4099  forceinline ActorLink**
4100  VarImp<VIC>::actorNonZero(PropCond pc) {
4101  assert((pc > 0) && (pc < pc_max+2));
4102  return b.base+u.idx[pc-1];
4103  }
4104 
4105  template<class VIC>
4106  forceinline unsigned int&
4107  VarImp<VIC>::idx(PropCond pc) {
4108  assert((pc > 0) && (pc < pc_max+2));
4109  return u.idx[pc-1];
4110  }
4111 
4112  template<class VIC>
4113  forceinline unsigned int
4114  VarImp<VIC>::idx(PropCond pc) const {
4115  assert((pc > 0) && (pc < pc_max+2));
4116  return u.idx[pc-1];
4117  }
4118 
4119  template<class VIC>
4120  forceinline
4122 #ifdef GECODE_HAS_CBS
4123  : var_id(++home.var_id_counter)
4124 #endif
4125  {
4126 #ifndef GECODE_HAS_CBS
4127  (void) home;
4128 #endif
4129  b.base = NULL; entries = 0;
4130  for (PropCond pc=1; pc<pc_max+2; pc++)
4131  idx(pc) = 0;
4132  free_and_bits = 0;
4133  }
4134 
4135  template<class VIC>
4136  forceinline
4138 #ifdef GECODE_HAS_CBS
4139  : var_id(0)
4140 #endif
4141  {
4142  b.base = NULL; entries = 0;
4143  for (PropCond pc=1; pc<pc_max+2; pc++)
4144  idx(pc) = 0;
4145  free_and_bits = 0;
4146  }
4147 
4148 #ifdef GECODE_HAS_CBS
4149  template<class VIC>
4150  forceinline unsigned int
4151  VarImp<VIC>::id(void) const {
4152  return var_id;
4153  }
4154 #endif
4155 
4156  template<class VIC>
4157  forceinline unsigned int
4158  VarImp<VIC>::degree(void) const {
4159  assert(!copied());
4160  return entries;
4161  }
4162 
4163  template<class VIC>
4164  forceinline double
4165  VarImp<VIC>::afc(void) const {
4166  double d = 0.0;
4167  // Count the afc of each propagator
4168  {
4169  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4170  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4171  while (a < e) {
4172  d += Propagator::cast(*a)->afc(); a++;
4173  }
4174  }
4175  // Count the afc of each advisor's propagator
4176  {
4177  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4178  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4179  while (a < e) {
4180  d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4181  ->propagator().afc();
4182  a++;
4183  }
4184  }
4185  return d;
4186  }
4187 
4188  template<class VIC>
4191  return d.me;
4192  }
4193 
4194  template<class VIC>
4195  forceinline unsigned int
4196  VarImp<VIC>::bits(void) const {
4197  return free_and_bits;
4198  }
4199 
4200  template<class VIC>
4201  forceinline unsigned int&
4203  return free_and_bits;
4204  }
4205 
4206 #ifdef GECODE_HAS_VAR_DISPOSE
4207  template<class VIC>
4209  VarImp<VIC>::vars_d(Space& home) {
4210  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4211  }
4212 
4213  template<class VIC>
4214  forceinline void
4215  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
4216  home.vars_d<VIC>(x);
4217  }
4218 #endif
4219 
4220  template<class VIC>
4221  forceinline bool
4222  VarImp<VIC>::copied(void) const {
4223  return Support::marked(b.fwd);
4224  }
4225 
4226  template<class VIC>
4228  VarImp<VIC>::forward(void) const {
4229  assert(copied());
4230  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4231  }
4232 
4233  template<class VIC>
4235  VarImp<VIC>::next(void) const {
4236  assert(copied());
4237  return u.next;
4238  }
4239 
4240  template<class VIC>
4241  forceinline
4243 #ifdef GECODE_HAS_CBS
4244  : var_id(x.var_id)
4245 #endif
4246  {
4247  VarImpBase** reg;
4248  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4249  if (x.b.base == NULL) {
4250  // Variable implementation needs no index structure
4251  reg = &home.pc.c.vars_noidx;
4252  assert(x.degree() == 0);
4253  } else {
4254  reg = &home.pc.c.vars_u[idx_c];
4255  }
4256  // Save subscriptions in copy
4257  b.base = x.b.base;
4258  entries = x.entries;
4259  for (PropCond pc=1; pc<pc_max+2; pc++)
4260  idx(pc) = x.idx(pc);
4261 
4262  // Set forwarding pointer
4263  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4264  // Register original
4265  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4266  }
4267 
4268  template<class VIC>
4271  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4272  }
4273 
4274  template<class VIC>
4277  return static_cast<ModEventDelta>(me << VIC::med_fst);
4278  }
4279 
4280  template<class VIC>
4283  return VIC::me_combine(me1,me2);
4284  }
4285 
4286  template<class VIC>
4287  forceinline void
4289  bool force) {
4290  if (VIC::med_update(p.u.med,me) || force)
4291  home.enqueue(&p);
4292  }
4293 
4294  template<class VIC>
4295  forceinline void
4297  ActorLink** b = actor(pc1);
4298  ActorLink** p = actorNonZero(pc2+1);
4299  while (p-- > b)
4300  schedule(home,*Propagator::cast(*p),me);
4301  }
4302 
4303  template<class VIC>
4304  forceinline void
4305  VarImp<VIC>::resize(Space& home) {
4306  if (b.base == NULL) {
4307  assert((free_and_bits >> free_bits) == 0);
4308  // Create fresh dependency array with four entries
4309  free_and_bits += 4 << free_bits;
4310  b.base = home.alloc<ActorLink*>(4);
4311  for (int i=0; i<pc_max+1; i++)
4312  u.idx[i] = 0;
4313  } else {
4314  // Resize dependency array
4315  unsigned int n = degree();
4316  // Find out whether the area is most likely in the special area
4317  // reserved for subscriptions. If yes, just resize mildly otherwise
4318  // more agressively
4319  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4320  unsigned int m =
4321  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4322  (n+4) : ((n+1)*3>>1);
4323  ActorLink** prop = home.alloc<ActorLink*>(m);
4324  free_and_bits += (m-n) << free_bits;
4325  // Copy entries
4326  Heap::copy<ActorLink*>(prop, b.base, n);
4327  home.free<ActorLink*>(b.base,n);
4328  b.base = prop;
4329  }
4330  }
4331 
4332  template<class VIC>
4333  forceinline void
4334  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4335  assert(pc <= pc_max);
4336  // Count one new subscription
4337  home.pc.p.n_sub += 1;
4338  if ((free_and_bits >> free_bits) == 0)
4339  resize(home);
4340  free_and_bits -= 1 << free_bits;
4341 
4342  // Enter subscription
4343  b.base[entries] = *actorNonZero(pc_max+1);
4344  entries++;
4345  for (PropCond j = pc_max; j > pc; j--) {
4346  *actorNonZero(j+1) = *actorNonZero(j);
4347  idx(j+1)++;
4348  }
4349  *actorNonZero(pc+1) = *actor(pc);
4350  idx(pc+1)++;
4351  *actor(pc) = ActorLink::cast(p);
4352 
4353 #ifdef GECODE_AUDIT
4354  ActorLink** f = actor(pc);
4355  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4356  if (*f == p)
4357  goto found;
4358  else
4359  f++;
4360  GECODE_NEVER;
4361  found: ;
4362 #endif
4363  }
4364 
4365  template<class VIC>
4366  forceinline void
4367  VarImp<VIC>::enter(Space& home, Advisor* a) {
4368  // Note that a might be a marked pointer
4369  // Count one new subscription
4370  home.pc.p.n_sub += 1;
4371  if ((free_and_bits >> free_bits) == 0)
4372  resize(home);
4373  free_and_bits -= 1 << free_bits;
4374 
4375  // Enter subscription
4376  b.base[entries++] = *actorNonZero(pc_max+1);
4377  *actorNonZero(pc_max+1) = a;
4378  }
4379 
4380  template<class VIC>
4381  forceinline void
4383  bool assigned, ModEvent me, bool schedule) {
4384  if (assigned) {
4385  // Do not subscribe, just schedule the propagator
4386  if (schedule)
4388  } else {
4389  enter(home,&p,pc);
4390  // Schedule propagator
4391  if (schedule && (pc != PC_GEN_ASSIGNED))
4392  VarImp<VIC>::schedule(home,p,me);
4393  }
4394  }
4395 
4396  template<class VIC>
4397  forceinline void
4398  VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4399  if (!assigned) {
4400  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4401  enter(home,ma);
4402  }
4403  }
4404 
4405  template<class VIC>
4406  forceinline void
4408  bool assigned, ModEvent me) {
4409  if (assigned)
4411  else if (pc != PC_GEN_ASSIGNED)
4412  VarImp<VIC>::schedule(home,p,me);
4413  }
4414 
4415  template<class VIC>
4416  void
4418  assert(pc <= pc_max);
4420  // Find actor in dependency array
4421  ActorLink** f = actor(pc);
4422 #ifdef GECODE_AUDIT
4423  while (f < actorNonZero(pc+1))
4424  if (*f == a)
4425  goto found;
4426  else
4427  f++;
4428  GECODE_NEVER;
4429  found: ;
4430 #else
4431  while (*f != a) f++;
4432 #endif
4433  // Remove actor
4434  *f = *(actorNonZero(pc+1)-1);
4435  for (PropCond j = pc+1; j< pc_max+1; j++) {
4436  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4437  idx(j)--;
4438  }
4439  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4440  idx(pc_max+1)--;
4441  entries--;
4442  free_and_bits += 1 << free_bits;
4443  home.pc.p.n_sub -= 1;
4444  }
4445 
4446  template<class VIC>
4447  forceinline void
4449  if (b.base != NULL)
4450  remove(home,&p,pc);
4451  }
4452 
4453  template<class VIC>
4454  void
4455  VarImp<VIC>::remove(Space& home, Advisor* a) {
4456  // Note that a might be a marked pointer
4457  // Find actor in dependency array
4458  ActorLink** f = actorNonZero(pc_max+1);
4459 #ifdef GECODE_AUDIT
4460  while (f < b.base+entries)
4461  if (*f == a)
4462  goto found;
4463  else
4464  f++;
4465  GECODE_NEVER;
4466  found: ;
4467 #else
4468  while (*f != a) f++;
4469 #endif
4470  // Remove actor
4471  *f = b.base[--entries];
4472  free_and_bits += 1 << free_bits;
4473  home.pc.p.n_sub -= 1;
4474  }
4475 
4476  template<class VIC>
4477  forceinline void
4478  VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
4479  if (b.base != NULL) {
4480  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4481  remove(home,ma);
4482  }
4483  }
4484 
4485  template<class VIC>
4486  forceinline void
4488  unsigned int n_sub = degree();
4489  home.pc.p.n_sub -= n_sub;
4490  unsigned int n = (free_and_bits >> free_bits) + n_sub;
4491  home.free<ActorLink*>(b.base,n);
4492  // Must be NULL such that cloning works
4493  b.base = NULL;
4494  // Must be 0 such that degree works
4495  entries = 0;
4496  // Must be NULL such that afc works
4497  for (PropCond pc=1; pc<pc_max+2; pc++)
4498  idx(pc) = 0;
4499  free_and_bits &= (1 << free_bits) - 1;
4500  }
4501 
4502  template<class VIC>
4503  forceinline bool
4505  /*
4506  * An advisor that is executed might remove itself due to subsumption.
4507  * As entries are removed from front to back, the advisors must
4508  * be iterated in forward direction.
4509  */
4510  ActorLink** la = actorNonZero(pc_max+1);
4511  ActorLink** le = b.base+entries;
4512  if (la == le)
4513  return true;
4514  d.me = me;
4515  // An advisor that is run, might be removed during execution.
4516  // As removal is done from the back the advisors have to be executed
4517  // in inverse order.
4518  do {
4519  Advisor* a = Advisor::cast
4520  (static_cast<ActorLink*>(Support::funmark(*la)));
4521  assert(!a->disposed());
4522  Propagator& p = a->propagator();
4523  switch (p.advise(home,*a,d)) {
4524  case ES_FIX:
4525  break;
4526  case ES_FAILED:
4527  return false;
4528  case ES_NOFIX:
4529  schedule(home,p,me);
4530  break;
4531  case ES_NOFIX_FORCE:
4532  schedule(home,p,me,true);
4533  break;
4534  case __ES_SUBSUMED:
4535  default:
4536  GECODE_NEVER;
4537  }
4538  } while (++la < le);
4539  return true;
4540  }
4541 
4542  template<class VIC>
4543  void
4544  VarImp<VIC>::_fail(Space& home) {
4545  /*
4546  * An advisor that is executed might remove itself due to subsumption.
4547  * As entries are removed from front to back, the advisors must
4548  * be iterated in forward direction.
4549  */
4550  ActorLink** la = actorNonZero(pc_max+1);
4551  ActorLink** le = b.base+entries;
4552  if (la == le)
4553  return;
4554  // An advisor that is run, might be removed during execution.
4555  // As removal is done from the back the advisors have to be executed
4556  // in inverse order.
4557  do {
4558  if (Support::marked(*la)) {
4559  Advisor* a = Advisor::cast(static_cast<ActorLink*>
4560  (Support::unmark(*la)));
4561  assert(!a->disposed());
4562  Propagator& p = a->propagator();
4563  p.advise(home,*a);
4564  }
4565  } while (++la < le);
4566  }
4567 
4568  template<class VIC>
4569  ModEvent
4571  _fail(home);
4572  return ME_GEN_FAILED;
4573  }
4574 
4575  template<class VIC>
4576  forceinline void
4578  // this refers to the variable to be updated (clone)
4579  // x refers to the original
4580  // Recover from copy
4581  x->b.base = b.base;
4582  x->u.idx[0] = u.idx[0];
4583  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4584  x->u.idx[1] = u.idx[1];
4585 
4586  unsigned int np =
4587  static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4588  unsigned int na =
4589  static_cast<unsigned int >(x->b.base + x->entries -
4590  x->actorNonZero(pc_max+1));
4591  unsigned int n = na + np;
4592  assert(n == x->degree());
4593 
4594  ActorLink** f = x->b.base;
4595  ActorLink** t = sub;
4596 
4597  sub += n;
4598  b.base = t;
4599  // Process propagator subscriptions
4600  while (np >= 4) {
4601  ActorLink* p3 = f[3]->prev();
4602  ActorLink* p0 = f[0]->prev();
4603  ActorLink* p1 = f[1]->prev();
4604  ActorLink* p2 = f[2]->prev();
4605  t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4606  np -= 4; t += 4; f += 4;
4607  }
4608  if (np >= 2) {
4609  ActorLink* p0 = f[0]->prev();
4610  ActorLink* p1 = f[1]->prev();
4611  t[0] = p0; t[1] = p1;
4612  np -= 2; t += 2; f += 2;
4613  }
4614  if (np > 0) {
4615  ActorLink* p0 = f[0]->prev();
4616  t[0] = p0;
4617  t += 1; f += 1;
4618  }
4619  // Process advisor subscriptions
4620  while (na >= 4) {
4621  ptrdiff_t m0, m1, m2, m3;
4622  ActorLink* p3 =
4623  static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4624  ActorLink* p0 =
4625  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4626  ActorLink* p1 =
4627  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4628  ActorLink* p2 =
4629  static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4630  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4631  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4632  t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4633  t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4634  na -= 4; t += 4; f += 4;
4635  }
4636  if (na >= 2) {
4637  ptrdiff_t m0, m1;
4638  ActorLink* p0 =
4639  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4640  ActorLink* p1 =
4641  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4642  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4643  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4644  na -= 2; t += 2; f += 2;
4645  }
4646  if (na > 0) {
4647  ptrdiff_t m0;
4648  ActorLink* p0 =
4649  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4650  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4651  }
4652  }
4653 
4654  template<class VIC>
4655  forceinline void
4656  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4657  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4658  while (x != NULL) {
4659  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4660  }
4661  }
4662 
4663 
4664 
4665  /*
4666  * Variable disposer
4667  *
4668  */
4669  template<class VarImp>
4671 #ifdef GECODE_HAS_VAR_DISPOSE
4672  Space::vd[VarImp::idx_d] = this;
4673 #endif
4674  }
4675 
4676  template<class VarImp>
4677  void
4679  VarImp* x = static_cast<VarImp*>(_x);
4680  do {
4681  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4682  } while (x != NULL);
4683  }
4684 
4685  /*
4686  * Statistics
4687  */
4688 
4689  forceinline void
4691  propagate = 0;
4692  }
4693  forceinline
4695  reset();
4696  }
4699  propagate += s.propagate;
4700  return *this;
4701  }
4704  StatusStatistics t(s);
4705  return t += *this;
4706  }
4707 
4708  forceinline void
4710 
4711  forceinline
4713  reset();
4714  }
4717  CloneStatistics s;
4718  return s;
4719  }
4722  return *this;
4723  }
4724 
4725  forceinline void
4727 
4728  forceinline
4730  reset();
4731  }
4734  CommitStatistics s;
4735  return s;
4736  }
4739  return *this;
4740  }
4741 
4742  /*
4743  * Cost computation
4744  *
4745  */
4746 
4747  forceinline
4748  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4749 
4750  forceinline PropCost
4751  PropCost::cost(PropCost::Mod m,
4753  unsigned int n) {
4754  if (n < 2)
4755  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4756  else if (n == 2)
4757  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4758  else if (n == 3)
4759  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4760  else
4761  return (m == LO) ? lo : hi;
4762  }
4763 
4764  forceinline PropCost
4766  return AC_RECORD;
4767  }
4769  PropCost::crazy(PropCost::Mod m, unsigned int n) {
4770  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4771  }
4774  assert(n >= 0);
4775  return crazy(m,static_cast<unsigned int>(n));
4776  }
4778  PropCost::cubic(PropCost::Mod m, unsigned int n) {
4779  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4780  }
4783  assert(n >= 0);
4784  return cubic(m,static_cast<unsigned int>(n));
4785  }
4788  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4789  }
4792  assert(n >= 0);
4793  return quadratic(m,static_cast<unsigned int>(n));
4794  }
4796  PropCost::linear(PropCost::Mod m, unsigned int n) {
4797  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4798  }
4801  assert(n >= 0);
4802  return linear(m,static_cast<unsigned int>(n));
4803  }
4806  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4807  }
4810  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4811  }
4814  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4815  }
4816 
4817  /*
4818  * Iterators for propagators and branchers of a space
4819  *
4820  */
4821  forceinline
4823  : home(home0), q(home.pc.p.active) {
4824  while (q >= &home.pc.p.queue[0]) {
4825  if (q->next() != q) {
4826  c = q->next(); e = q; q--;
4827  return;
4828  }
4829  q--;
4830  }
4831  q = NULL;
4832  if (!home.pl.empty()) {
4833  c = Propagator::cast(home.pl.next());
4834  e = Propagator::cast(&home.pl);
4835  } else {
4836  c = e = NULL;
4837  }
4838  }
4839  forceinline bool
4841  return c != NULL;
4842  }
4843  forceinline void
4845  c = c->next();
4846  if (c == e) {
4847  if (q == NULL) {
4848  c = NULL;
4849  } else {
4850  while (q >= &home.pc.p.queue[0]) {
4851  if (q->next() != q) {
4852  c = q->next(); e = q; q--;
4853  return;
4854  }
4855  q--;
4856  }
4857  q = NULL;
4858  if (!home.pl.empty()) {
4859  c = Propagator::cast(home.pl.next());
4860  e = Propagator::cast(&home.pl);
4861  } else {
4862  c = NULL;
4863  }
4864  }
4865  }
4866  }
4869  return *Propagator::cast(c);
4870  }
4871 
4872 
4873  forceinline
4875  : home(home0), q(home.pc.p.active) {
4876  while (q >= &home.pc.p.queue[0]) {
4877  if (q->next() != q) {
4878  c = q->next(); e = q; q--;
4879  return;
4880  }
4881  q--;
4882  }
4883  q = c = e = NULL;
4884  }
4885  forceinline bool
4887  return c != NULL;
4888  }
4889  forceinline void
4891  c = c->next();
4892  if (c == e) {
4893  if (q == NULL) {
4894  c = NULL;
4895  } else {
4896  while (q >= &home.pc.p.queue[0]) {
4897  if (q->next() != q) {
4898  c = q->next(); e = q; q--;
4899  return;
4900  }
4901  q--;
4902  }
4903  q = c = e = NULL;
4904  }
4905  }
4906  }
4909  return *Propagator::cast(c);
4910  }
4911 
4912 
4913  forceinline
4915  c = Propagator::cast(home.pl.next());
4916  e = Propagator::cast(&home.pl);
4917  }
4918  forceinline bool
4920  return c != e;
4921  }
4922  forceinline void
4924  c = c->next();
4925  }
4928  return *Propagator::cast(c);
4929  }
4930 
4931 
4932  forceinline
4934  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4935  forceinline bool
4937  return c != e;
4938  }
4939  forceinline void
4941  c = c->next();
4942  }
4945  return *Brancher::cast(c);
4946  }
4947 
4948 
4949  /*
4950  * Groups of actors
4951  */
4952  forceinline
4953  Group::Group(unsigned int gid0) : gid(gid0) {}
4954 
4955  forceinline bool
4956  Group::in(Group actor) const {
4957  return (gid == GROUPID_ALL) || (gid == actor.gid);
4958  }
4959 
4960  forceinline bool
4961  Group::in(void) const {
4962  return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
4963  }
4964 
4965  forceinline
4966  Group::Group(const Group& g) : gid(g.gid) {}
4967 
4970  gid=g.gid; return *this;
4971  }
4972 
4973  forceinline unsigned int
4974  Group::id(void) const {
4975  return gid;
4976  }
4977 
4978 
4979  forceinline
4981 
4982  forceinline
4984  : Group(gid) {}
4985 
4986  forceinline
4988  : Group(g) {}
4989 
4992  return static_cast<PropagatorGroup&>(Group::operator =(g));
4993  }
4994 
4997  return Home(home,NULL,*this,BrancherGroup::def);
4998  }
4999 
5000  forceinline bool
5002  return id() == g.id();
5003  }
5004  forceinline bool
5006  return id() != g.id();
5007  }
5008 
5011  if (id() != GROUPID_ALL)
5012  p.group(*this);
5013  return *this;
5014  }
5015 
5016 
5017  forceinline
5019 
5020  forceinline
5022  : Group(gid) {}
5023 
5024  forceinline
5026  : Group(g) {}
5027 
5030  return static_cast<BrancherGroup&>(Group::operator =(g));
5031  }
5032 
5035  return Home(home,NULL,PropagatorGroup::def,*this);
5036  }
5037 
5038  forceinline bool
5040  return id() == g.id();
5041  }
5042  forceinline bool
5044  return id() != g.id();
5045  }
5046 
5049  if (id() != GROUPID_ALL)
5050  p.group(*this);
5051  return *this;
5052  }
5053 
5054 
5055  /*
5056  * Iterators for propagators and branchers in a group
5057  *
5058  */
5059  forceinline
5061  : ps(const_cast<Space&>(home)), g(g0) {
5062  while (ps() && !g.in(ps.propagator().group()))
5063  ++ps;
5064  }
5065  forceinline bool
5067  return ps();
5068  }
5069  forceinline void
5071  do
5072  ++ps;
5073  while (ps() && !g.in(ps.propagator().group()));
5074  }
5075  forceinline const Propagator&
5077  return ps.propagator();
5078  }
5079 
5080  forceinline
5082  : bs(const_cast<Space&>(home)), g(g0) {
5083  while (bs() && !g.in(bs.brancher().group()))
5084  ++bs;
5085  }
5086  forceinline bool
5088  return bs();
5089  }
5090  forceinline void
5092  do
5093  ++bs;
5094  while (bs() && !g.in(bs.brancher().group()));
5095  }
5096  forceinline const Brancher&
5097  Branchers::brancher(void) const {
5098  return bs.brancher();
5099  }
5100 
5101 
5102  /*
5103  * Space construction support
5104  *
5105  */
5106  template<class T>
5107  forceinline T&
5109  return alloc<T>(1);
5110  }
5111  template<class T, typename A1>
5112  forceinline T&
5113  Space::construct(A1 const& a1) {
5114  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5115  new (&t) T(a1);
5116  return t;
5117  }
5118  template<class T, typename A1, typename A2>
5119  forceinline T&
5120  Space::construct(A1 const& a1, A2 const& a2) {
5121  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5122  new (&t) T(a1,a2);
5123  return t;
5124  }
5125  template<class T, typename A1, typename A2, typename A3>
5126  forceinline T&
5127  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5128  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5129  new (&t) T(a1,a2,a3);
5130  return t;
5131  }
5132  template<class T, typename A1, typename A2, typename A3, typename A4>
5133  forceinline T&
5134  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5135  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5136  new (&t) T(a1,a2,a3,a4);
5137  return t;
5138  }
5139  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5140  forceinline T&
5141  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5142  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5143  new (&t) T(a1,a2,a3,a4,a5);
5144  return t;
5145  }
5146 
5147 }
5148 
5149 // STATISTICS: kernel-core
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:40
Base-class for both propagators and branchers.
Definition: core.hpp:628
friend class LocalObject
Definition: core.hpp:634
virtual Actor * copy(Space &home)=0
Create copy.
friend class ActorLink
Definition: core.hpp:629
friend class Propagator
Definition: core.hpp:631
friend class Brancher
Definition: core.hpp:633
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
Base-class for advisors.
Definition: core.hpp:1292
Propagator & propagator(void) const
Return the advisor's propagator.
Definition: core.hpp:3857
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3864
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
Definition: core.hpp:3874
Class to iterate over advisors of a council.
Definition: core.hpp:1266
Advisors(const Council< A > &c)
Initialize.
Definition: core.hpp:3988
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:3996
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:4002
A & advisor(void) const
Return advisor.
Definition: core.hpp:4010
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition: var-type.hpp:889
Archive representation
Definition: archive.hpp:42
Group of branchers.
Definition: core.hpp:799
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition: core.cpp:1033
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:850
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:847
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition: core.hpp:5029
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:1010
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:5034
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:5043
void kill(Space &home)
Kill all branchers in a group.
Definition: core.cpp:1044
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:5039
BrancherGroup(void)
Constructor.
Definition: core.hpp:5018
Base-class for branchers.
Definition: core.hpp:1442
virtual const Choice * choice(Space &home)=0
Return choice.
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int a)=0
Commit for choice c and alternative a.
friend class ActorLink
Definition: core.hpp:1443
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3629
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3634
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
virtual const Choice * choice(const Space &home, Archive &e)=0
Return choice from e.
Class to iterate over branchers in a group.
Definition: core.hpp:2772
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:5091
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:5097
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:5087
Branchers(const Space &home, BrancherGroup g)
Initialize.
Definition: core.hpp:5081
Choice for performing commit
Definition: core.hpp:1412
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3766
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3780
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3770
Statistics for execution of clone
Definition: core.hpp:1709
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:4716
void reset(void)
Reset information.
Definition: core.hpp:4709
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:4721
CloneStatistics(void)
Initialize.
Definition: core.hpp:4712
Statistics for execution of commit
Definition: core.hpp:1725
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition: core.hpp:4738
void reset(void)
Reset information.
Definition: core.hpp:4726
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:4733
CommitStatistics(void)
Initialize.
Definition: core.hpp:4729
Commit trace information.
Definition: core.hpp:1005
BrancherGroup group(void) const
Return brancher group.
Definition: core.hpp:3412
unsigned int alternative(void) const
Return alternative.
Definition: core.hpp:3424
const Brancher & b
Brancher.
Definition: core.hpp:1009
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
Definition: core.hpp:3404
unsigned int id(void) const
Return brancher identifier.
Definition: core.hpp:3408
unsigned int a
Alternative.
Definition: core.hpp:1013
const Choice & c
Choice.
Definition: core.hpp:1011
const Choice & choice(void) const
Return choice.
Definition: core.hpp:3420
const Brancher & brancher(void) const
Return brancher.
Definition: core.hpp:3416
Council of advisors
Definition: core.hpp:1241
bool empty(void) const
Test whether council has advisor left.
Definition: core.hpp:3916
void update(Space &home, Council< A > &c)
Update during cloning (copies all advisors)
Definition: core.hpp:3926
void dispose(Space &home)
Dispose council.
Definition: core.hpp:3971
Council(Space &home)
Construct advisor council.
Definition: core.hpp:3911
Council(void)
Default constructor.
Definition: core.hpp:3907
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Base-class for freelist-managed objects.
Definition: manager.hpp:98
Group baseclass for controlling actors.
Definition: core.hpp:673
static Group all
Group of all actors.
Definition: core.hpp:717
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:720
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition: core.hpp:683
Group(void)
Constructor.
Definition: core.cpp:921
bool in(void) const
Check whether this is a real group (and not just default)
Definition: core.hpp:4961
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:695
static const unsigned int GROUPID_MAX
The maximal group number.
Definition: core.hpp:687
Group & operator=(const Group &g)
Assignment operator.
Definition: core.hpp:4969
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4974
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition: core.hpp:685
unsigned int gid
The group id.
Definition: core.hpp:689
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4956
static unsigned int next
Next group id.
Definition: core.hpp:692
friend class Home
Definition: core.hpp:674
Base class for heap allocated objects.
Definition: heap.hpp:340
Home class for posting propagators
Definition: core.hpp:856
PropagatorGroup pg
A propagator group.
Definition: core.hpp:864
BrancherGroup branchergroup(void) const
Return brancher group.
Definition: core.hpp:3307
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
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:3262
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:862
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:860
void fail(void)
Mark space as failed.
Definition: core.hpp:4039
BrancherGroup bg
A brancher group.
Definition: core.hpp:866
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:3299
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition: core.hpp:3303
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:3275
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4048
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:3266
Class for storing propagator information.
Definition: gpi.hpp:42
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:45
unsigned int gid
Group identifier.
Definition: gpi.hpp:47
double afc
The afc value.
Definition: gpi.hpp:49
void decay(double d)
Set decay factor to d.
Definition: gpi.hpp:163
Manage memory for space.
Definition: manager.hpp:120
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
Definition: manager.hpp:378
void * alloc(SharedMemory &sm, size_t s)
Allocate memory of size s.
Definition: manager.hpp:285
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition: manager.hpp:297
GPI gpi
The global propagator information.
SharedMemory sm
The shared memory area.
Class to store data shared among several spaces.
Data & data(void) const
Provide access.
Handles for local (space-shared) objects.
Definition: core.hpp:1558
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3739
~LocalHandle(void)
Destructor.
Definition: core.hpp:3750
void update(Space &home, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3756
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3745
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3752
Local (space-shared) object.
Definition: core.hpp:1533
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3705
LocalObject * fwd(Space &home)
Return forwarding pointer.
Definition: core.hpp:3732
Information passed by meta search engines.
Definition: core.hpp:1613
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3106
unsigned long int fail(void) const
Return number of failures since last restart.
Definition: core.hpp:3096
Type
Which type of information is provided.
Definition: core.hpp:1616
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition: core.hpp:1620
@ RESTART
Information is provided by a restart-based engine.
Definition: core.hpp:1618
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition: core.hpp:3091
const Type t
Type of information.
Definition: core.hpp:1624
unsigned int asset(void) const
Return number of asset in portfolio.
Definition: core.hpp:3111
const Space * l
Last solution found.
Definition: core.hpp:1634
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:3086
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3101
const unsigned long int r
Number of restarts.
Definition: core.hpp:1628
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:3070
const unsigned int a
Number of asset in portfolio.
Definition: core.hpp:1641
const NoGoods & ng
No-goods from restart.
Definition: core.hpp:1636
const unsigned long int f
Number of failures since last restart.
Definition: core.hpp:1632
Type type(void) const
Return type of information.
Definition: core.hpp:3082
const unsigned long int s
Number of solutions since last restart.
Definition: core.hpp:1630
No-good literal recorded during search.
Definition: core.hpp:1340
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3789
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual void cancel(Space &home, Propagator &p)=0
Cancel propagator p from all views of the no-good literal.
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
NGL(void)
Constructor for creation.
Definition: core.hpp:3812
Status
The status of a no-good literal.
Definition: core.hpp:1346
@ SUBSUMED
The literal is subsumed.
Definition: core.hpp:1348
@ FAILED
The literal is failed.
Definition: core.hpp:1347
virtual void reschedule(Space &home, Propagator &p)=0
Schedule propagator p for all views of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3793
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3821
virtual NGL * copy(Space &home)=0
Create copy.
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3805
No-goods recorded from restarts.
Definition: core.hpp:1588
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1606
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:3063
NoGoods(void)
Initialize.
Definition: core.hpp:3052
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:3055
unsigned long int n
Number of no-goods.
Definition: core.hpp:1591
Configuration class for variable implementations without index structure.
Definition: core.hpp:98
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:125
static const int free_bits
Freely available bits.
Definition: core.hpp:107
static const int idx_c
Index for update.
Definition: core.hpp:101
static const int med_fst
Start of bits for modification event delta.
Definition: core.hpp:109
static const int med_lst
End of bits for modification event delta.
Definition: core.hpp:111
static const PropCond pc_max
Maximal propagation condition.
Definition: core.hpp:105
static const int idx_d
Index for disposal.
Definition: core.hpp:103
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:121
static const int med_mask
Bitmask for modification event delta.
Definition: core.hpp:113
Class to set group information when a post function is executed.
Definition: core.hpp:948
Space & h
The home space.
Definition: core.hpp:952
PostInfo(Home home)
Set information.
Definition: core.hpp:3356
bool nested
Whether it is used nested.
Definition: core.hpp:958
unsigned int pid
Next free propagator id.
Definition: core.hpp:956
PropagatorGroup pg
The propagator group.
Definition: core.hpp:954
~PostInfo(void)
Reset information.
Definition: core.hpp:3364
Post trace information.
Definition: core.hpp:1032
unsigned int propagators(void) const
Return number of posted propagators.
Definition: core.hpp:3445
PropagatorGroup group(void) const
Return propagator group.
Definition: core.hpp:3437
PropagatorGroup g
Propagator group.
Definition: core.hpp:1044
Status
Post status.
Definition: core.hpp:1037
@ SUBSUMED
Propagator not posted as already subsumed.
Definition: core.hpp:1040
@ FAILED
Posting failed.
Definition: core.hpp:1039
@ POSTED
Propagator was posted.
Definition: core.hpp:1038
Status status(void) const
Return post status.
Definition: core.hpp:3441
PostTraceInfo(PropagatorGroup g, Status s, unsigned int n)
Initialize.
Definition: core.hpp:3434
Status s
Status.
Definition: core.hpp:1046
unsigned int n
Number of posted propagators.
Definition: core.hpp:1048
Propagation cost.
Definition: core.hpp:486
ActualCost ac
Actual cost.
Definition: core.hpp:509
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4813
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4805
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4765
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4769
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4787
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4778
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4809
Mod
Propagation cost modifier.
Definition: core.hpp:512
@ LO
Cheap.
Definition: core.hpp:513
@ HI
Expensive.
Definition: core.hpp:514
ActualCost
The actual cost values that are used.
Definition: core.hpp:490
@ AC_TERNARY_LO
Three variables, cheap.
Definition: core.hpp:502
@ AC_TERNARY_HI
Three variables, expensive.
Definition: core.hpp:500
@ AC_BINARY_LO
Two variables, cheap.
Definition: core.hpp:503
@ AC_CUBIC_LO
Cubic complexity, cheap.
Definition: core.hpp:494
@ AC_UNARY_HI
Only single variable, expensive.
Definition: core.hpp:505
@ AC_RECORD
Reserved for recording information.
Definition: core.hpp:491
@ AC_BINARY_HI
Two variables, expensive.
Definition: core.hpp:501
@ AC_LINEAR_HI
Linear complexity, expensive.
Definition: core.hpp:498
@ AC_CUBIC_HI
Cubic complexity, expensive.
Definition: core.hpp:495
@ AC_MAX
Maximal cost value.
Definition: core.hpp:506
@ AC_CRAZY_LO
Exponential complexity, cheap.
Definition: core.hpp:492
@ AC_LINEAR_LO
Linear complexity, cheap.
Definition: core.hpp:499
@ AC_UNARY_LO
Only single variable, cheap.
Definition: core.hpp:504
@ AC_QUADRATIC_LO
Quadratic complexity, cheap.
Definition: core.hpp:496
@ AC_CRAZY_HI
Exponential complexity, expensive.
Definition: core.hpp:493
@ AC_QUADRATIC_HI
Quadratic complexity, expensive.
Definition: core.hpp:497
Propagate trace information.
Definition: core.hpp:969
unsigned int i
Propagator id.
Definition: core.hpp:981
Status
Propagator status.
Definition: core.hpp:973
@ SUBSUMED
Propagator is subsumed.
Definition: core.hpp:977
@ FIX
Propagator computed fixpoint.
Definition: core.hpp:974
@ NOFIX
Propagator did not compute fixpoint.
Definition: core.hpp:975
@ FAILED
Propagator failed.
Definition: core.hpp:976
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
Definition: core.hpp:3378
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
Definition: core.hpp:3390
unsigned int id(void) const
Return propagator identifier.
Definition: core.hpp:3382
Status status(void) const
Return propagator status.
Definition: core.hpp:3394
const Propagator * p
Propagator.
Definition: core.hpp:985
PropagatorGroup g
Propagator group.
Definition: core.hpp:983
PropagatorGroup group(void) const
Return propagator group.
Definition: core.hpp:3386
Group of propagators.
Definition: core.hpp:727
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:955
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:5001
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:792
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:932
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:5005
PropagatorGroup(void)
Constructor.
Definition: core.hpp:4980
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition: core.hpp:4991
void disable(Space &home)
Disable all propagators in a group.
Definition: core.cpp:979
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition: core.cpp:988
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:4996
void kill(Space &home)
Kill all propagators in a group.
Definition: core.cpp:966
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:789
Base-class for propagators.
Definition: core.hpp:1064
virtual void reschedule(Space &home)=0
Schedule function.
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1077
double afc(void) const
Return the accumlated failure count.
Definition: core.hpp:3525
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
friend class ActorLink
Definition: core.hpp:1065
Kernel::GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3493
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3542
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3547
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:3520
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:3471
friend class PropagatorGroup
Definition: core.hpp:1071
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3476
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1079
Class to iterate over propagators in a group.
Definition: core.hpp:2754
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:5066
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:5076
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:5070
Propagators(const Space &home, PropagatorGroup g)
Initialize.
Definition: core.hpp:5060
Handle to region.
Definition: region.hpp:55
Class to iterate over branchers of a space.
Definition: core.hpp:2735
Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4944
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:4940
Branchers(Space &home)
Initialize.
Definition: core.hpp:4933
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:4936
Class to iterate over idle propagators of a space.
Definition: core.hpp:2714
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4923
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4927
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4919
IdlePropagators(Space &home)
Initialize.
Definition: core.hpp:4914
Class to iterate over propagators of a space.
Definition: core.hpp:2664
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4840
Propagators(Space &home)
Initialize.
Definition: core.hpp:4822
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4844
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4868
Class to iterate over scheduled propagators of a space.
Definition: core.hpp:2689
ScheduledPropagators(Space &home)
Initialize.
Definition: core.hpp:4874
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4908
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4886
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4890
Computation spaces.
Definition: core.hpp:1742
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:2888
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2799
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:3242
struct Gecode::Space::@61::@63 c
Data available only during copying.
T & construct(void)
Construction routines.
Definition: core.hpp:5108
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1852
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:2807
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2803
struct Gecode::Space::@61::@62 p
Data only available during propagation or branching.
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1850
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2822
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2827
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1841
friend class Brancher
Definition: core.hpp:1747
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
unsigned int bid_sc
Id of next brancher to be created plus status control.
Definition: core.hpp:1839
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1830
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2863
ViewTraceInfo vti
View trace information.
Definition: core.hpp:1843
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:3287
Statistics for execution of status
Definition: core.hpp:1691
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1694
void reset(void)
Reset information.
Definition: core.hpp:4690
StatusStatistics(void)
Initialize.
Definition: core.hpp:4694
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:4703
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:4698
Iterator over subscribed propagators.
Definition: subscribed.hpp:36
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Exception: too many branchers
Definition: exception.hpp:93
Trace filters.
Definition: filter.hpp:133
Propagator for recording trace information.
Definition: recorder.hpp:154
Tracer.
Definition: tracer.hpp:149
Base-class for variable implementations.
Definition: core.hpp:172
Base class for Variable type disposer.
Definition: core.hpp:180
Variable implementation disposer
Definition: core.hpp:195
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:4670
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:4678
Base-class for variable implementations.
Definition: core.hpp:219
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:4382
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4487
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:4504
VarImp(void)
Creation of static instances.
Definition: core.hpp:4137
double afc(void) const
Return accumulated failure count (plus degree)
Definition: core.hpp:4165
void subscribe(Space &home, Advisor &a, bool assigned, bool fail)
Subscribe advisor a to variable.
Definition: core.hpp:4398
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4196
ActorLink ** base
Subscribed actors.
Definition: core.hpp:233
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4222
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition: core.hpp:4407
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:4288
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:273
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4228
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4270
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:4282
void cancel(Space &home, Advisor &a, bool fail)
Cancel subscription of advisor a.
Definition: core.hpp:4478
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:4158
unsigned int & bits(void)
Provide access to free bits.
Definition: core.hpp:4202
VarImp(Space &home)
Creation.
Definition: core.hpp:4121
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4276
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:242
VarImp * next(void) const
Return next copied variable.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: core.hpp:4448
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:275
void schedule(Space &home, PropCond pc1, PropCond pc2, ModEvent me)
Schedule subscribed propagators.
Definition: core.hpp:4296
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:4190
View trace information.
Definition: core.hpp:908
What what(void) const
Return what is currently executing.
Definition: core.hpp:3332
const Brancher & brancher(void) const
Return currently executing brancher.
Definition: core.hpp:3342
const Propagator & propagator(void) const
Return currently executing propagator.
Definition: core.hpp:3336
void other(void)
Record that nothing is known at this point.
Definition: core.hpp:3328
What
What is currently executing.
Definition: core.hpp:913
@ BRANCHER
A brancher is executing.
Definition: core.hpp:917
@ OTHER
Unknown.
Definition: core.hpp:921
@ POST
A post function is executing.
Definition: core.hpp:919
@ PROPAGATOR
A propagator is currently executing.
Definition: core.hpp:915
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition: core.hpp:3347
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Definition: core.hpp:925
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:76
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:67
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
@ ES_NOFIX_FORCE
Advisor forces rescheduling of propagator.
Definition: core.hpp:478
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Definition: core.hpp:473
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:479
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:65
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:69
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2923
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:74
int ModEvent
Type for modification events.
Definition: core.hpp:62
const int * pi[]
Definition: photo.cpp:14262
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition: filter.cpp:131
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3576
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3569
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:3557
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3880
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:3894
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3887
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
ActorProperty
Actor properties.
Definition: core.hpp:553
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:4059
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:4053
void fail(void)
Fail space.
Definition: core.hpp:4030
@ AP_VIEW_TRACE
Definition: core.hpp:573
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
@ AP_TRACE
Definition: core.hpp:578
@ AP_WEAKLY
Definition: core.hpp:568
void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te, FloatTracer &t)
Create a tracer for float variables.
Definition: trace.cpp:39
virtual Space * copy(void)=0
Copying member function.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:3237
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3232
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
SpaceStatus
Space status
Definition: core.hpp:1681
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition: core.hpp:1683
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
void print(const Search::Statistics &stat, bool restart)
Print statistics.
Definition: job-shop.cpp:606
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
unsigned int size(I &i)
Size of all ranges of range iterator i.
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:108
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
Single _b(1, 4)
AFC afc
Definition: afc.cpp:135
#define forceinline
Definition: config.hpp:185
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:75
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72