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