Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
core.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Contributing authors:
9  * Filip Konvicka <filip.konvicka@logis.cz>
10  *
11  * Copyright:
12  * Christian Schulte, 2002
13  * Guido Tack, 2003
14  * Mikael Lagerkvist, 2006
15  * LOGIS, s.r.o., 2009
16  *
17  * Bugfixes provided by:
18  * Alexander Samoilov <alexander_samoilov@yahoo.com>
19  *
20  * Last modified:
21  * $Date: 2017-03-17 23:04:57 +0100 (Fri, 17 Mar 2017) $ by $Author: schulte $
22  * $Revision: 15597 $
23  *
24  * This file is part of Gecode, the generic constraint
25  * development environment:
26  * http://www.gecode.org
27  *
28  * Permission is hereby granted, free of charge, to any person obtaining
29  * a copy of this software and associated documentation files (the
30  * "Software"), to deal in the Software without restriction, including
31  * without limitation the rights to use, copy, modify, merge, publish,
32  * distribute, sublicense, and/or sell copies of the Software, and to
33  * permit persons to whom the Software is furnished to do so, subject to
34  * the following conditions:
35  *
36  * The above copyright notice and this permission notice shall be
37  * included in all copies or substantial portions of the Software.
38  *
39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46  *
47  */
48 
49 #include <iostream>
50 
51 namespace Gecode {
52 
53  class Space;
54 
79  class SharedHandle {
80  public:
88  class Object : public HeapAllocated {
89  friend class Space;
90  friend class SharedHandle;
91  private:
93  Object* next;
95  Object* fwd;
97  unsigned int use_cnt;
98  public:
100  Object(void);
102  virtual Object* copy(void) const = 0;
104  virtual ~Object(void);
105  };
106  private:
108  Object* o;
110  void subscribe(void);
112  void cancel(void);
113  public:
115  SharedHandle(void);
119  SharedHandle(const SharedHandle& sh);
123  void update(Space& home, bool share, SharedHandle& sh);
125  ~SharedHandle(void);
126  protected:
128  SharedHandle::Object* object(void) const;
131  };
132 
141  typedef int ModEvent;
143 
150 
152  typedef int PropCond;
154  const PropCond PC_GEN_NONE = -1;
158 
169  typedef int ModEventDelta;
170 
171 }
172 
174 
175 namespace Gecode {
176 
179  public:
181  static const int idx_c = -1;
183  static const int idx_d = -1;
187  static const int free_bits = 0;
189  static const int med_fst = 0;
191  static const int med_lst = 0;
193  static const int med_mask = 0;
195  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
197  static bool med_update(ModEventDelta& med, ModEvent me);
198  };
199 
202  GECODE_NEVER; return 0;
203  }
204  forceinline bool
206  GECODE_NEVER; return false;
207  }
208 
209 
210  /*
211  * These are the classes of interest
212  *
213  */
214  class ActorLink;
215  class Actor;
216  class Propagator;
217  class SubscribedPropagators;
218  class LocalObject;
219  class Advisor;
220  class AFC;
221  class Choice;
222  class Brancher;
223  class Group;
224  class PropagatorGroup;
225  class BrancherGroup;
226  class PostInfo;
227  class ViewTraceInfo;
228  class PropagateTraceInfo;
229  class CommitTraceInfo;
230  class TraceRecorder;
231 
232  template<class A> class Council;
233  template<class A> class Advisors;
234  template<class VIC> class VarImp;
235 
236 
237  /*
238  * Variable implementations
239  *
240  */
241 
249  class VarImpBase {};
250 
258  public:
260  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
263  };
264 
271  template<class VarImp>
273  public:
275  VarImpDisposer(void);
277  virtual void dispose(Space& home, VarImpBase* x);
278  };
279 
281  class Delta {
282  template<class VIC> friend class VarImp;
283  private:
285  ModEvent me;
286  };
287 
295  template<class VIC>
296  class VarImp : public VarImpBase {
297  friend class Space;
298  friend class Propagator;
299  template<class VarImp> friend class VarImpDisposer;
300  friend class SubscribedPropagators;
301  private:
302  union {
320  } b;
321 
323  static const int idx_c = VIC::idx_c;
325  static const int idx_d = VIC::idx_d;
327  static const int free_bits = VIC::free_bits;
329  unsigned int entries;
331  unsigned int free_and_bits;
333  static const Gecode::PropCond pc_max = VIC::pc_max;
334 
335  union {
346  unsigned int idx[pc_max+1];
349  } u;
350 
352  ActorLink** actor(PropCond pc);
354  ActorLink** actorNonZero(PropCond pc);
356  unsigned int& idx(PropCond pc);
358  unsigned int idx(PropCond pc) const;
359 
366  void update(VarImp* x, ActorLink**& sub);
373  static void update(Space& home, ActorLink**& sub);
374 
376  void enter(Space& home, Propagator* p, PropCond pc);
378  void enter(Space& home, Advisor* a);
380  void resize(Space& home);
382  void remove(Space& home, Propagator* p, PropCond pc);
384  void remove(Space& home, Advisor* a);
385 
386 
387  protected:
389  void cancel(Space& home);
395  bool advise(Space& home, ModEvent me, Delta& d);
396  private:
398  void _fail(Space& home);
399  protected:
401  ModEvent fail(Space& home);
402 #ifdef GECODE_HAS_VAR_DISPOSE
403  static VarImp<VIC>* vars_d(Space& home);
406  static void vars_d(Space& home, VarImp<VIC>* x);
407 #endif
408 
409  public:
411  VarImp(Space& home);
413  VarImp(void);
414 
416 
417 
429  void subscribe(Space& home, Propagator& p, PropCond pc,
430  bool assigned, ModEvent me, bool schedule);
432  void cancel(Space& home, Propagator& p, PropCond pc);
441  void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
443  void cancel(Space& home, Advisor& a, bool fail);
444 
451  unsigned int degree(void) const;
458  double afc(void) const;
460 
462 
463  VarImp(Space& home, bool share, VarImp& x);
466  bool copied(void) const;
468  VarImp* forward(void) const;
470  VarImp* next(void) const;
472 
474 
475 
482  static void schedule(Space& home, Propagator& p, ModEvent me,
483  bool force = false);
491  static void reschedule(Space& home, Propagator& p, PropCond pc,
492  bool assigned, ModEvent me);
494  static ModEvent me(const ModEventDelta& med);
496  static ModEventDelta med(ModEvent me);
498  static ModEvent me_combine(ModEvent me1, ModEvent me2);
500 
502 
503  static ModEvent modevent(const Delta& d);
506 
508 
509  unsigned int bits(void) const;
512  unsigned int& bits(void);
514 
515  protected:
517  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
518 
519  public:
521 
522  static void* operator new(size_t,Space&);
525  static void operator delete(void*,Space&);
527  static void operator delete(void*);
529  };
530 
531 
540  enum ExecStatus {
542  ES_FAILED = -1,
543  ES_NOFIX = 0,
544  ES_OK = 0,
545  ES_FIX = 1,
548  };
549 
554  class PropCost {
555  friend class Space;
556  public:
558  enum ActualCost {
559  AC_RECORD = 0,
574  AC_MAX = 6
575  };
578  public:
580  enum Mod {
581  LO,
582  HI
583  };
584  private:
586  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
589  public:
591  static PropCost record(void);
593  static PropCost crazy(PropCost::Mod m, unsigned int n);
595  static PropCost crazy(PropCost::Mod m, int n);
597  static PropCost cubic(PropCost::Mod m, unsigned int n);
599  static PropCost cubic(PropCost::Mod m, int n);
601  static PropCost quadratic(PropCost::Mod m, unsigned int n);
603  static PropCost quadratic(PropCost::Mod m, int n);
605  static PropCost linear(PropCost::Mod m, unsigned int n);
607  static PropCost linear(PropCost::Mod m, int n);
609  static PropCost ternary(PropCost::Mod m);
611  static PropCost binary(PropCost::Mod m);
613  static PropCost unary(PropCost::Mod m);
614  };
615 
616 
630  AP_DISPOSE = (1 << 0),
636  AP_WEAKLY = (1 << 1),
641  AP_VIEW_TRACE = (1 << 2),
646  AP_TRACE = (1 << 3)
647  };
648 
649 
657  class ActorLink {
658  friend class Actor;
659  friend class Propagator;
660  friend class Advisor;
661  friend class Brancher;
662  friend class LocalObject;
663  friend class Space;
664  template<class VIC> friend class VarImp;
665  private:
666  ActorLink* _next; ActorLink* _prev;
667  public:
669  ActorLink* prev(void) const; void prev(ActorLink*);
671  ActorLink* next(void) const; void next(ActorLink*);
672  ActorLink** next_ref(void);
674 
676  void init(void);
678  void unlink(void);
680  void head(ActorLink* al);
682  void tail(ActorLink* al);
684  bool empty(void) const;
686  template<class T> static ActorLink* cast(T* a);
688  template<class T> static const ActorLink* cast(const T* a);
689  };
690 
691 
697  friend class ActorLink;
698  friend class Space;
699  friend class Propagator;
700  friend class Advisor;
701  friend class Brancher;
702  friend class LocalObject;
703  template<class VIC> friend class VarImp;
704  template<class A> friend class Council;
705  private:
707  static Actor* cast(ActorLink* al);
709  static const Actor* cast(const ActorLink* al);
711  GECODE_KERNEL_EXPORT static Actor* sentinel;
712  public:
714  virtual Actor* copy(Space& home, bool share) = 0;
715 
717 
720  virtual size_t dispose(Space& home);
722  static void* operator new(size_t s, Space& home);
724  static void operator delete(void* p, Space& home);
726  public:
728  GECODE_KERNEL_EXPORT virtual ~Actor(void);
730  static void* operator new(size_t s);
732  static void operator delete(void* p);
733  };
734 
735  class Home;
736 
741  class Group {
742  friend class Home;
743  friend class Propagator;
744  friend class Brancher;
745  friend class ViewTraceInfo;
746  friend class PropagateTraceInfo;
747  friend class CommitTraceInfo;
748  protected:
750  static const unsigned int GROUPID_ALL = 0U;
752  static const unsigned int GROUPID_DEF = 1U;
754  static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
756  unsigned int gid;
759  static unsigned int next;
764  Group(unsigned int gid0);
765  public:
767 
770  Group(void);
772  Group(const Group& g);
774  Group& operator =(const Group& g);
776  unsigned int id(void) const;
778  bool in(Group a) const;
780  bool in(void) const;
784  static Group all;
787  static Group def;
788  };
789 
794  class PropagatorGroup : public Group {
795  friend class Propagator;
796  friend class ViewTraceInfo;
797  friend class PropagateTraceInfo;
798  protected:
800  PropagatorGroup(unsigned int gid);
801  public:
803 
804  PropagatorGroup(void);
811  Home operator ()(Space& home);
813 
827  PropagatorGroup& move(Space& home, unsigned int id);
829 
831  bool operator ==(PropagatorGroup g) const;
834  bool operator !=(PropagatorGroup g) const;
837  unsigned int size(Space& home) const;
840  void kill(Space& home);
843  void disable(Space& home);
851  void enable(Space& home, bool s=true);
859  };
860 
865  class BrancherGroup : public Group {
866  friend class Brancher;
867  protected:
869  BrancherGroup(unsigned int gid);
870  public:
872 
873  BrancherGroup(void);
876  BrancherGroup(const BrancherGroup& g);
880  Home operator ()(Space& home);
882 
888  BrancherGroup& move(Space& home, Brancher& b);
896  BrancherGroup& move(Space& home, unsigned int id);
898 
900  bool operator ==(BrancherGroup g) const;
903  bool operator !=(BrancherGroup g) const;
906  unsigned int size(Space& home) const;
909  void kill(Space& home);
917  };
918 
922  class Home {
923  friend class PostInfo;
924  protected:
933  public:
935 
936  Home(Space& s, Propagator* p=NULL,
941  Home& operator =(const Home& h);
943  operator Space&(void);
945 
954  Propagator* propagator(void) const;
956  PropagatorGroup propagatorgroup(void) const;
958  BrancherGroup branchergroup(void) const;
960 
962  bool failed(void) const;
965  void fail(void);
967  void notice(Actor& a, ActorProperty p, bool duplicate=false);
969  };
970 
975  friend class Space;
976  friend class PostInfo;
977  public:
979  enum What {
983  BRANCHER = 1,
985  POST = 2,
987  OTHER = 3
988  };
989  protected:
991  ptrdiff_t who;
993  void propagator(Propagator& p);
995  void brancher(Brancher& b);
997  void post(PropagatorGroup g);
999  void other(void);
1000  public:
1002  What what(void) const;
1004  const Propagator& propagator(void) const;
1006  const Brancher& brancher(void) const;
1008  PropagatorGroup post(void) const;
1009  };
1010 
1014  class PostInfo {
1015  protected:
1018  public:
1020  PostInfo(Home home);
1022  ~PostInfo(void);
1023  };
1024 
1029  friend class Space;
1030  public:
1032  enum Status {
1037  };
1038  protected:
1040  unsigned int i;
1044  const Propagator* p;
1048  PropagateTraceInfo(unsigned int i, PropagatorGroup g,
1049  const Propagator* p, Status s);
1050  public:
1052  unsigned int id(void) const;
1054  PropagatorGroup group(void) const;
1056  const Propagator* propagator(void) const;
1058  Status status(void) const;
1059  };
1060 
1065  friend class Space;
1066  protected:
1068  const Brancher& b;
1070  const Choice& c;
1072  unsigned int a;
1074  CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1075  public:
1077  unsigned int id(void) const;
1079  BrancherGroup group(void) const;
1081  const Brancher& brancher(void) const;
1083  const Choice& choice(void) const;
1085  unsigned int alternative(void) const;
1086  };
1087 
1093  friend class ActorLink;
1094  friend class Space;
1095  template<class VIC> friend class VarImp;
1096  friend class Advisor;
1097  template<class A> friend class Council;
1099  friend class PropagatorGroup;
1100  private:
1101  union {
1105  size_t size;
1108  } u;
1110  void* gpi_disabled;
1112  static Propagator* cast(ActorLink* al);
1114  static const Propagator* cast(const ActorLink* al);
1116  void disable(Space& home);
1118  void enable(Space& home);
1119  protected:
1121  Propagator(Home home);
1123  Propagator(Space& home, bool share, Propagator& p);
1125  Propagator* fwd(void) const;
1127  GPI::Info& gpi(void);
1128 
1129  public:
1131 
1132 
1140  virtual void reschedule(Space& home) = 0;
1164  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1166  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1174  ModEventDelta modeventdelta(void) const;
1211  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1214  virtual void advise(Space& home, Advisor& a);
1216 
1218  double afc(void) const;
1221 
1223  unsigned int id(void) const;
1226  PropagatorGroup group(void) const;
1228  void group(PropagatorGroup g);
1230  bool disabled(void) const;
1232  };
1233 
1234 
1242  template<class A>
1243  class Council {
1244  friend class Advisor;
1245  friend class Advisors<A>;
1246  private:
1248  mutable ActorLink* advisors;
1249  public:
1251  Council(void);
1253  Council(Space& home);
1255  bool empty(void) const;
1257  void update(Space& home, bool share, Council<A>& c);
1259  void dispose(Space& home);
1260  };
1261 
1262 
1267  template<class A>
1268  class Advisors {
1269  private:
1271  ActorLink* a;
1272  public:
1274  Advisors(const Council<A>& c);
1276  bool operator ()(void) const;
1278  void operator ++(void);
1280  A& advisor(void) const;
1281  };
1282 
1283 
1294  class Advisor : private ActorLink {
1295  template<class VIC> friend class VarImp;
1296  template<class A> friend class Council;
1297  template<class A> friend class Advisors;
1299  private:
1301  bool disposed(void) const;
1303  static Advisor* cast(ActorLink* al);
1305  static const Advisor* cast(const ActorLink* al);
1306  protected:
1308  Propagator& propagator(void) const;
1309  public:
1311  template<class A>
1312  Advisor(Space& home, Propagator& p, Council<A>& c);
1314  Advisor(Space& home, bool share, Advisor& a);
1316  const ViewTraceInfo& operator ()(const Space& home) const;
1317 
1319 
1320  template<class A>
1322  void dispose(Space& home, Council<A>& c);
1324  static void* operator new(size_t s, Space& home);
1326  static void operator delete(void* p, Space& home);
1328  private:
1329 #ifndef __GNUC__
1330  static void operator delete(void* p);
1332 #endif
1333  static void* operator new(size_t s);
1335  };
1336 
1337 
1343  private:
1345  void* nl;
1346  public:
1348  enum Status {
1351  NONE
1352  };
1354  NGL(void);
1356  NGL(Space& home);
1358  NGL(Space& home, bool share, NGL& ngl);
1360  virtual void subscribe(Space& home, Propagator& p) = 0;
1362  virtual void cancel(Space& home, Propagator& p) = 0;
1364  virtual void reschedule(Space& home, Propagator& p) = 0;
1366  virtual NGL::Status status(const Space& home) const = 0;
1368  virtual ExecStatus prune(Space& home) = 0;
1370  virtual NGL* copy(Space& home, bool share) = 0;
1373  virtual bool notice(void) const;
1375  virtual size_t dispose(Space& home);
1377 
1378  bool leaf(void) const;
1381  NGL* next(void) const;
1383  void leaf(bool l);
1385  void next(NGL* n);
1387  NGL* add(NGL* n, bool l);
1389 
1391  static void* operator new(size_t s, Space& home);
1394  static void operator delete(void* s, Space& home);
1396  static void operator delete(void* p);
1398  public:
1400  GECODE_KERNEL_EXPORT virtual ~NGL(void);
1402  static void* operator new(size_t s);
1403  };
1404 
1415  friend class Space;
1416  private:
1417  unsigned int bid;
1418  unsigned int alt;
1419 
1421  unsigned int id(void) const;
1422  protected:
1424  Choice(const Brancher& b, const unsigned int a);
1425  public:
1427  unsigned int alternatives(void) const;
1429  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1431  virtual size_t size(void) const = 0;
1434  virtual void archive(Archive& e) const;
1435  };
1436 
1447  friend class ActorLink;
1448  friend class Space;
1449  friend class Choice;
1450  private:
1452  unsigned int bid;
1454  unsigned int gid;
1456  static Brancher* cast(ActorLink* al);
1458  static const Brancher* cast(const ActorLink* al);
1459  protected:
1461  Brancher(Home home);
1463  Brancher(Space& home, bool share, Brancher& b);
1464  public:
1466 
1467 
1475  virtual bool status(const Space& home) const = 0;
1483  virtual const Choice* choice(Space& home) = 0;
1485  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1492  virtual ExecStatus commit(Space& home, const Choice& c,
1493  unsigned int a) = 0;
1508  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1517  virtual void print(const Space& home, const Choice& c, unsigned int a,
1518  std::ostream& o) const;
1520 
1522  unsigned int id(void) const;
1525  BrancherGroup group(void) const;
1527  void group(BrancherGroup g);
1529  };
1530 
1538  class LocalObject : public Actor {
1539  friend class ActorLink;
1540  friend class Space;
1541  friend class LocalHandle;
1542  protected:
1544  LocalObject(Home home);
1546  LocalObject(Space& home, bool share, LocalObject& l);
1548  static LocalObject* cast(ActorLink* al);
1550  static const LocalObject* cast(const ActorLink* al);
1551  private:
1553  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1554  public:
1556  LocalObject* fwd(Space& home, bool share);
1557  };
1558 
1565  class LocalHandle {
1566  private:
1568  LocalObject* o;
1569  protected:
1571  LocalHandle(void);
1573  LocalHandle(LocalObject* lo);
1575  LocalHandle(const LocalHandle& lh);
1576  public:
1578  LocalHandle& operator =(const LocalHandle& lh);
1580  void update(Space& home, bool share, LocalHandle& lh);
1582  ~LocalHandle(void);
1583  protected:
1585  LocalObject* object(void) const;
1587  void object(LocalObject* n);
1588  };
1589 
1590 
1596  protected:
1598  unsigned long int n;
1599  public:
1601  NoGoods(void);
1604  virtual void post(Space& home) const;
1606  unsigned long int ng(void) const;
1608  void ng(unsigned long int n);
1610  virtual ~NoGoods(void);
1613  static NoGoods eng;
1614  };
1615 
1621  public:
1623  enum Type {
1627  PORTFOLIO
1628  };
1629  protected:
1631  const Type t;
1633 
1634  const unsigned long int r;
1637  const unsigned long int s;
1639  const unsigned long int f;
1641  const Space* l;
1643  const NoGoods& ng;
1645 
1647  const unsigned int a;
1650  public:
1652 
1653  MetaInfo(unsigned long int r,
1655  unsigned long int s,
1656  unsigned long int f,
1657  const Space* l,
1658  NoGoods& ng);
1660  MetaInfo(unsigned int a);
1662  Type type(void) const;
1665 
1666  unsigned long int restart(void) const;
1669  unsigned long int solution(void) const;
1671  unsigned long int fail(void) const;
1673  const Space* last(void) const;
1675  const NoGoods& nogoods(void) const;
1677 
1679  unsigned int asset(void) const;
1682  };
1683 
1692  };
1693 
1699  public:
1701  unsigned long int propagate;
1703  StatusStatistics(void);
1705  void reset(void);
1710  };
1711 
1717  public:
1719  CloneStatistics(void);
1721  void reset(void);
1726  };
1727 
1733  public:
1735  CommitStatistics(void);
1737  void reset(void);
1742  };
1743 
1744 
1749  friend class Actor;
1750  friend class Propagator;
1751  friend class PropagatorGroup;
1752  friend class Propagators;
1753  friend class Brancher;
1754  friend class BrancherGroup;
1755  friend class Branchers;
1756  friend class Advisor;
1757  template <class A> friend class Council;
1758  template<class VIC> friend class VarImp;
1759  template<class VarImp> friend class VarImpDisposer;
1760  friend class SharedHandle;
1761  friend class LocalObject;
1762  friend class Region;
1763  friend class AFC;
1764  friend class PostInfo;
1765  private:
1767  SharedMemory* sm;
1769  MemoryManager mm;
1771  GPI gpi;
1773  ActorLink pl;
1775  ActorLink bl;
1781  Brancher* b_status;
1793  Brancher* b_commit;
1795  Brancher* brancher(unsigned int id);
1796 
1798  void kill(Brancher& b);
1800  void kill(Propagator& p);
1801 
1804  void kill_brancher(unsigned int id);
1805 
1807  static const unsigned reserved_bid = 0U;
1808 
1810  static const unsigned int sc_bits = 2;
1812  static const unsigned int sc_fast = 0;
1814  static const unsigned int sc_disabled = 1;
1816  static const unsigned int sc_trace = 2;
1817 
1818  union {
1820  struct {
1842  unsigned int bid_sc;
1844  unsigned int n_sub;
1847  } p;
1849  struct {
1858  } c;
1859  } pc;
1861  void enqueue(Propagator* p);
1866 #ifdef GECODE_HAS_VAR_DISPOSE
1867  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1870  VarImpBase* _vars_d[AllVarConf::idx_d];
1872  template<class VIC> VarImpBase* vars_d(void) const;
1874  template<class VIC> void vars_d(VarImpBase* x);
1875 #endif
1876  void update(ActorLink** sub);
1879 
1881  TraceRecorder* findtr(void);
1882 
1884  Actor** d_fst;
1886  Actor** d_cur;
1888  Actor** d_lst;
1889 
1891  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1893  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1895  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1896 
1918  GECODE_KERNEL_EXPORT Space* _clone(bool share_data=true,
1919  bool share_info=true);
1920 
1954  void _commit(const Choice& c, unsigned int a);
1955 
1987  void _trycommit(const Choice& c, unsigned int a);
1988 
1996  void ap_notice_dispose(Actor* a, bool d);
2004  void ap_ignore_dispose(Actor* a, bool d);
2005 
2006  public:
2012  Space(void);
2025  Space(bool share, Space& s);
2031  virtual ~Space(void);
2038  virtual Space* copy(bool share) = 0;
2049  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2074  virtual bool master(const MetaInfo& mi);
2101  virtual bool slave(const MetaInfo& mi);
2102 
2103  /*
2104  * Member functions for search engines
2105  *
2106  */
2107 
2120  SpaceStatus status(StatusStatistics& stat=unused_status);
2121 
2154  const Choice* choice(void);
2155 
2166  const Choice* choice(Archive& e) const;
2167 
2191  Space* clone(bool share_data=true,
2192  bool share_info=true,
2193  CloneStatistics& stat=unused_clone) const;
2194 
2229  void commit(const Choice& c, unsigned int a,
2230  CommitStatistics& stat=unused_commit);
2263  void trycommit(const Choice& c, unsigned int a,
2264  CommitStatistics& stat=unused_commit);
2284  NGL* ngl(const Choice& c, unsigned int a);
2285 
2301  void print(const Choice& c, unsigned int a, std::ostream& o) const;
2302 
2312  void notice(Actor& a, ActorProperty p, bool duplicate=false);
2321  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2322 
2323 
2334  ExecStatus ES_SUBSUMED(Propagator& p);
2349  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
2360  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2371  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2372 
2383  template<class A>
2384  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
2395  template<class A>
2396  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
2408  template<class A>
2409  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
2410 
2418  void fail(void);
2427  bool failed(void) const;
2432  bool stable(void) const;
2433 
2435 
2436  Home operator ()(Propagator& p);
2439  Home operator ()(PropagatorGroup pg);
2441  Home operator ()(BrancherGroup bg);
2443 
2455  template<class T>
2456  T* alloc(long unsigned int n);
2463  template<class T>
2464  T* alloc(long int n);
2471  template<class T>
2472  T* alloc(unsigned int n);
2479  template<class T>
2480  T* alloc(int n);
2490  template<class T>
2491  void free(T* b, long unsigned int n);
2501  template<class T>
2502  void free(T* b, long int n);
2512  template<class T>
2513  void free(T* b, unsigned int n);
2523  template<class T>
2524  void free(T* b, int n);
2536  template<class T>
2537  T* realloc(T* b, long unsigned int n, long unsigned int m);
2549  template<class T>
2550  T* realloc(T* b, long int n, long int m);
2562  template<class T>
2563  T* realloc(T* b, unsigned int n, unsigned int m);
2575  template<class T>
2576  T* realloc(T* b, int n, int m);
2584  template<class T>
2585  T** realloc(T** b, long unsigned int n, long unsigned int m);
2593  template<class T>
2594  T** realloc(T** b, long int n, long int m);
2602  template<class T>
2603  T** realloc(T** b, unsigned int n, unsigned int m);
2611  template<class T>
2612  T** realloc(T** b, int n, int m);
2614  void* ralloc(size_t s);
2616  void rfree(void* p, size_t s);
2618  void* rrealloc(void* b, size_t n, size_t m);
2620  template<size_t> void* fl_alloc(void);
2626  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2635  GECODE_KERNEL_EXPORT void flush(void);
2637 
2639 
2642  template<class T>
2643  T& construct(void);
2649  template<class T, typename A1>
2650  T& construct(A1 const& a1);
2656  template<class T, typename A1, typename A2>
2657  T& construct(A1 const& a1, A2 const& a2);
2663  template<class T, typename A1, typename A2, typename A3>
2664  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2670  template<class T, typename A1, typename A2, typename A3, typename A4>
2671  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2677  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2678  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2680 
2682 
2683  void afc_decay(double d);
2686  double afc_decay(void) const;
2688 
2689  private:
2695  class Propagators {
2696  private:
2698  Space& home;
2700  ActorLink* q;
2702  ActorLink* c;
2704  ActorLink* e;
2705  public:
2707  Propagators(Space& home);
2709  bool operator ()(void) const;
2711  void operator ++(void);
2713  Propagator& propagator(void) const;
2714  };
2720  class ScheduledPropagators {
2721  private:
2723  Space& home;
2725  ActorLink* q;
2727  ActorLink* c;
2729  ActorLink* e;
2730  public:
2732  ScheduledPropagators(Space& home);
2734  bool operator ()(void) const;
2736  void operator ++(void);
2738  Propagator& propagator(void) const;
2739  };
2745  class IdlePropagators {
2746  private:
2748  ActorLink* c;
2750  ActorLink* e;
2751  public:
2753  IdlePropagators(Space& home);
2755  bool operator ()(void) const;
2757  void operator ++(void);
2759  Propagator& propagator(void) const;
2760  };
2766  class Branchers {
2767  private:
2769  ActorLink* c;
2771  ActorLink* e;
2772  public:
2774  Branchers(Space& home);
2776  bool operator ()(void) const;
2778  void operator ++(void);
2780  Brancher& brancher(void) const;
2781  };
2782  };
2783 
2785  class Propagators {
2786  private:
2788  Space::Propagators ps;
2790  PropagatorGroup g;
2791  public:
2793  Propagators(Space& home, PropagatorGroup g);
2795  bool operator ()(void) const;
2797  void operator ++(void);
2799  const Propagator& propagator(void) const;
2800  };
2801 
2803  class Branchers {
2804  private:
2806  Space::Branchers bs;
2808  BrancherGroup g;
2809  public:
2811  Branchers(Space& home, BrancherGroup g);
2813  bool operator ()(void) const;
2815  void operator ++(void);
2817  const Brancher& brancher(void) const;
2818  };
2819 
2820 
2821 
2822 
2823  /*
2824  * Memory management
2825  *
2826  */
2827 
2828  // Space allocation: general space heaps and free lists
2829  forceinline void*
2830  Space::ralloc(size_t s) {
2831  return mm.alloc(sm,s);
2832  }
2833  forceinline void
2834  Space::rfree(void* p, size_t s) {
2835  return mm.reuse(p,s);
2836  }
2837  forceinline void*
2838  Space::rrealloc(void* _b, size_t n, size_t m) {
2839  char* b = static_cast<char*>(_b);
2840  if (n < m) {
2841  char* p = static_cast<char*>(ralloc(m));
2842  memcpy(p,b,n);
2843  rfree(b,n);
2844  return p;
2845  } else {
2846  rfree(b+m,m-n);
2847  return b;
2848  }
2849  }
2850 
2851  template<size_t s>
2852  forceinline void*
2854  return mm.template fl_alloc<s>(sm);
2855  }
2856  template<size_t s>
2857  forceinline void
2859  mm.template fl_dispose<s>(f,l);
2860  }
2861 
2862  /*
2863  * Typed allocation routines
2864  *
2865  */
2866  template<class T>
2867  forceinline T*
2868  Space::alloc(long unsigned int n) {
2869  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2870  for (long unsigned int i=n; i--; )
2871  (void) new (p+i) T();
2872  return p;
2873  }
2874  template<class T>
2875  forceinline T*
2876  Space::alloc(long int n) {
2877  assert(n >= 0);
2878  return alloc<T>(static_cast<long unsigned int>(n));
2879  }
2880  template<class T>
2881  forceinline T*
2882  Space::alloc(unsigned int n) {
2883  return alloc<T>(static_cast<long unsigned int>(n));
2884  }
2885  template<class T>
2886  forceinline T*
2888  assert(n >= 0);
2889  return alloc<T>(static_cast<long unsigned int>(n));
2890  }
2891 
2892  template<class T>
2893  forceinline void
2894  Space::free(T* b, long unsigned int n) {
2895  for (long unsigned int i=n; i--; )
2896  b[i].~T();
2897  rfree(b,n*sizeof(T));
2898  }
2899  template<class T>
2900  forceinline void
2901  Space::free(T* b, long int n) {
2902  assert(n >= 0);
2903  free<T>(b,static_cast<long unsigned int>(n));
2904  }
2905  template<class T>
2906  forceinline void
2907  Space::free(T* b, unsigned int n) {
2908  free<T>(b,static_cast<long unsigned int>(n));
2909  }
2910  template<class T>
2911  forceinline void
2912  Space::free(T* b, int n) {
2913  assert(n >= 0);
2914  free<T>(b,static_cast<long unsigned int>(n));
2915  }
2916 
2917  template<class T>
2918  forceinline T*
2919  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2920  if (n < m) {
2921  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2922  for (long unsigned int i=n; i--; )
2923  (void) new (p+i) T(b[i]);
2924  for (long unsigned int i=n; i<m; i++)
2925  (void) new (p+i) T();
2926  free<T>(b,n);
2927  return p;
2928  } else {
2929  free<T>(b+m,m-n);
2930  return b;
2931  }
2932  }
2933  template<class T>
2934  forceinline T*
2935  Space::realloc(T* b, long int n, long int m) {
2936  assert((n >= 0) && (m >= 0));
2937  return realloc<T>(b,static_cast<long unsigned int>(n),
2938  static_cast<long unsigned int>(m));
2939  }
2940  template<class T>
2941  forceinline T*
2942  Space::realloc(T* b, unsigned int n, unsigned int m) {
2943  return realloc<T>(b,static_cast<long unsigned int>(n),
2944  static_cast<long unsigned int>(m));
2945  }
2946  template<class T>
2947  forceinline T*
2948  Space::realloc(T* b, int n, int m) {
2949  assert((n >= 0) && (m >= 0));
2950  return realloc<T>(b,static_cast<long unsigned int>(n),
2951  static_cast<long unsigned int>(m));
2952  }
2953 
2954 #define GECODE_KERNEL_REALLOC(T) \
2955  template<> \
2956  forceinline T* \
2957  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2958  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2959  } \
2960  template<> \
2961  forceinline T* \
2962  Space::realloc<T>(T* b, long int n, long int m) { \
2963  assert((n >= 0) && (m >= 0)); \
2964  return realloc<T>(b,static_cast<long unsigned int>(n), \
2965  static_cast<long unsigned int>(m)); \
2966  } \
2967  template<> \
2968  forceinline T* \
2969  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2970  return realloc<T>(b,static_cast<long unsigned int>(n), \
2971  static_cast<long unsigned int>(m)); \
2972  } \
2973  template<> \
2974  forceinline T* \
2975  Space::realloc<T>(T* b, int n, int m) { \
2976  assert((n >= 0) && (m >= 0)); \
2977  return realloc<T>(b,static_cast<long unsigned int>(n), \
2978  static_cast<long unsigned int>(m)); \
2979  }
2980 
2981  GECODE_KERNEL_REALLOC(bool)
2982  GECODE_KERNEL_REALLOC(signed char)
2983  GECODE_KERNEL_REALLOC(unsigned char)
2984  GECODE_KERNEL_REALLOC(signed short int)
2985  GECODE_KERNEL_REALLOC(unsigned short int)
2986  GECODE_KERNEL_REALLOC(signed int)
2987  GECODE_KERNEL_REALLOC(unsigned int)
2988  GECODE_KERNEL_REALLOC(signed long int)
2989  GECODE_KERNEL_REALLOC(unsigned long int)
2990  GECODE_KERNEL_REALLOC(float)
2991  GECODE_KERNEL_REALLOC(double)
2992 
2993 #undef GECODE_KERNEL_REALLOC
2994 
2995  template<class T>
2996  forceinline T**
2997  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2998  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2999  }
3000  template<class T>
3001  forceinline T**
3002  Space::realloc(T** b, long int n, long int m) {
3003  assert((n >= 0) && (m >= 0));
3004  return realloc<T*>(b,static_cast<long unsigned int>(n),
3005  static_cast<long unsigned int>(m));
3006  }
3007  template<class T>
3008  forceinline T**
3009  Space::realloc(T** b, unsigned int n, unsigned int m) {
3010  return realloc<T*>(b,static_cast<long unsigned int>(n),
3011  static_cast<long unsigned int>(m));
3012  }
3013  template<class T>
3014  forceinline T**
3015  Space::realloc(T** b, int n, int m) {
3016  assert((n >= 0) && (m >= 0));
3017  return realloc<T*>(b,static_cast<long unsigned int>(n),
3018  static_cast<long unsigned int>(m));
3019  }
3020 
3021 
3022 #ifdef GECODE_HAS_VAR_DISPOSE
3023  template<class VIC>
3025  Space::vars_d(void) const {
3026  return _vars_d[VIC::idx_d];
3027  }
3028  template<class VIC>
3029  forceinline void
3030  Space::vars_d(VarImpBase* x) {
3031  _vars_d[VIC::idx_d] = x;
3032  }
3033 #endif
3034 
3035  // Space allocated entities: Actors, variable implementations, and advisors
3036  forceinline void
3037  Actor::operator delete(void*) {}
3038  forceinline void
3039  Actor::operator delete(void*, Space&) {}
3040  forceinline void*
3041  Actor::operator new(size_t s, Space& home) {
3042  return home.ralloc(s);
3043  }
3044 
3045  template<class VIC>
3046  forceinline void
3047  VarImp<VIC>::operator delete(void*) {}
3048  template<class VIC>
3049  forceinline void
3050  VarImp<VIC>::operator delete(void*, Space&) {}
3051  template<class VIC>
3052  forceinline void*
3053  VarImp<VIC>::operator new(size_t s, Space& home) {
3054  return home.ralloc(s);
3055  }
3056 
3057 #ifndef __GNUC__
3058  forceinline void
3059  Advisor::operator delete(void*) {}
3060 #endif
3061  forceinline void
3062  Advisor::operator delete(void*, Space&) {}
3063  forceinline void*
3064  Advisor::operator new(size_t s, Space& home) {
3065  return home.ralloc(s);
3066  }
3067 
3068  forceinline void
3069  NGL::operator delete(void*) {}
3070  forceinline void
3071  NGL::operator delete(void*, Space&) {}
3072  forceinline void*
3073  NGL::operator new(size_t s, Space& home) {
3074  return home.ralloc(s);
3075  }
3076 
3077  /*
3078  * Shared objects and handles
3079  *
3080  */
3081  forceinline
3083  : next(NULL), fwd(NULL), use_cnt(0) {}
3084  forceinline
3086  assert(use_cnt == 0);
3087  }
3088 
3090  SharedHandle::object(void) const {
3091  return o;
3092  }
3093  forceinline void
3094  SharedHandle::subscribe(void) {
3095  if (o != NULL) o->use_cnt++;
3096  }
3097  forceinline void
3098  SharedHandle::cancel(void) {
3099  if ((o != NULL) && (--o->use_cnt == 0))
3100  delete o;
3101  o=NULL;
3102  }
3103  forceinline void
3105  if (n != o) {
3106  cancel(); o=n; subscribe();
3107  }
3108  }
3109  forceinline
3110  SharedHandle::SharedHandle(void) : o(NULL) {}
3111  forceinline
3113  subscribe();
3114  }
3115  forceinline
3117  subscribe();
3118  }
3121  if (&sh != this) {
3122  cancel(); o=sh.o; subscribe();
3123  }
3124  return *this;
3125  }
3126  forceinline void
3127  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
3128  if (sh.o == NULL) {
3129  o=NULL; return;
3130  } else if (share) {
3131  o=sh.o;
3132  } else if (sh.o->fwd != NULL) {
3133  o=sh.o->fwd;
3134  } else {
3135  o = sh.o->copy();
3136  sh.o->fwd = o;
3137  sh.o->next = home.pc.c.shared;
3138  home.pc.c.shared = sh.o;
3139  }
3140  subscribe();
3141  }
3142  forceinline
3144  cancel();
3145  }
3146 
3147 
3148 
3149  /*
3150  * No-goods
3151  *
3152  */
3153  forceinline
3155  : n(0) {}
3156  forceinline unsigned long int
3157  NoGoods::ng(void) const {
3158  return n;
3159  }
3160  forceinline void
3161  NoGoods::ng(unsigned long int n0) {
3162  n=n0;
3163  }
3164  forceinline
3166 
3167 
3168  /*
3169  * Information from meta search engines
3170  */
3171  forceinline
3172  MetaInfo::MetaInfo(unsigned long int r0,
3173  unsigned long int s0,
3174  unsigned long int f0,
3175  const Space* l0,
3176  NoGoods& ng0)
3177  : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3178 
3179  forceinline
3180  MetaInfo::MetaInfo(unsigned int a0)
3181  : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
3182 
3184  MetaInfo::type(void) const {
3185  return t;
3186  }
3187  forceinline unsigned long int
3188  MetaInfo::restart(void) const {
3189  assert(type() == RESTART);
3190  return r;
3191  }
3192  forceinline unsigned long int
3193  MetaInfo::solution(void) const {
3194  assert(type() == RESTART);
3195  return s;
3196  }
3197  forceinline unsigned long int
3198  MetaInfo::fail(void) const {
3199  assert(type() == RESTART);
3200  return f;
3201  }
3202  forceinline const Space*
3203  MetaInfo::last(void) const {
3204  assert(type() == RESTART);
3205  return l;
3206  }
3207  forceinline const NoGoods&
3208  MetaInfo::nogoods(void) const {
3209  assert(type() == RESTART);
3210  return ng;
3211  }
3212  forceinline unsigned int
3213  MetaInfo::asset(void) const {
3214  assert(type() == PORTFOLIO);
3215  return a;
3216  }
3217 
3218 
3219 
3220  /*
3221  * ActorLink
3222  *
3223  */
3225  ActorLink::prev(void) const {
3226  return _prev;
3227  }
3228 
3230  ActorLink::next(void) const {
3231  return _next;
3232  }
3233 
3236  return &_next;
3237  }
3238 
3239  forceinline void
3241  _prev = al;
3242  }
3243 
3244  forceinline void
3246  _next = al;
3247  }
3248 
3249  forceinline void
3251  ActorLink* p = _prev; ActorLink* n = _next;
3252  p->_next = n; n->_prev = p;
3253  }
3254 
3255  forceinline void
3257  _next = this; _prev =this;
3258  }
3259 
3260  forceinline void
3262  // Inserts al at head of link-chain (that is, after this)
3263  ActorLink* n = _next;
3264  this->_next = a; a->_prev = this;
3265  a->_next = n; n->_prev = a;
3266  }
3267 
3268  forceinline void
3270  // Inserts al at tail of link-chain (that is, before this)
3271  ActorLink* p = _prev;
3272  a->_next = this; this->_prev = a;
3273  p->_next = a; a->_prev = p;
3274  }
3275 
3276  forceinline bool
3277  ActorLink::empty(void) const {
3278  return _next == this;
3279  }
3280 
3281  template<class T>
3284  // Turning al into a reference is for gcc, assume is for MSVC
3285  GECODE_NOT_NULL(a);
3286  ActorLink& t = *a;
3287  return static_cast<ActorLink*>(&t);
3288  }
3289 
3290  template<class T>
3291  forceinline const ActorLink*
3292  ActorLink::cast(const T* a) {
3293  // Turning al into a reference is for gcc, assume is for MSVC
3294  GECODE_NOT_NULL(a);
3295  const ActorLink& t = *a;
3296  return static_cast<const ActorLink*>(&t);
3297  }
3298 
3299 
3300  /*
3301  * Actor
3302  *
3303  */
3305  Actor::cast(ActorLink* al) {
3306  // Turning al into a reference is for gcc, assume is for MSVC
3307  GECODE_NOT_NULL(al);
3308  ActorLink& t = *al;
3309  return static_cast<Actor*>(&t);
3310  }
3311 
3312  forceinline const Actor*
3313  Actor::cast(const ActorLink* al) {
3314  // Turning al into a reference is for gcc, assume is for MSVC
3315  GECODE_NOT_NULL(al);
3316  const ActorLink& t = *al;
3317  return static_cast<const Actor*>(&t);
3318  }
3319 
3320  forceinline void
3321  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3322  s.notice(a,p,duplicate);
3323  }
3324 
3326  Space::clone(bool share_data, bool share_info, CloneStatistics&) const {
3327  // Clone is only const for search engines. During cloning, several data
3328  // structures are updated (e.g. forwarding pointers), so we have to
3329  // cast away the constness.
3330  return const_cast<Space*>(this)->_clone(share_data,share_info);
3331  }
3332 
3333  forceinline void
3334  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3335  _commit(c,a);
3336  }
3337 
3338  forceinline void
3339  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3340  _trycommit(c,a);
3341  }
3342 
3343  forceinline double
3344  Space::afc_decay(void) const {
3345  return gpi.decay();
3346  }
3347 
3348  forceinline void
3350  gpi.decay(d);
3351  }
3352 
3353  forceinline size_t
3355  return sizeof(*this);
3356  }
3357 
3358 
3359  /*
3360  * Home for posting actors
3361  *
3362  */
3363  forceinline
3365  PropagatorGroup pg0, BrancherGroup bg0)
3366  : s(s0), p(p0), pg(pg0), bg(bg0) {}
3367  forceinline Home&
3369  s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3370  return *this;
3371  }
3372  forceinline
3373  Home::operator Space&(void) {
3374  return s;
3375  }
3378  return Home(s,&p);
3379  }
3382  return Home(s,NULL,pg,BrancherGroup::def);
3383  }
3386  return Home(s,NULL,PropagatorGroup::def,bg);
3387  }
3390  return Home(*this,&p);
3391  }
3393  Home::propagator(void) const {
3394  return p;
3395  }
3398  return pg;
3399  }
3401  Home::branchergroup(void) const {
3402  return bg;
3403  }
3404 
3405  /*
3406  * View trace information
3407  *
3408  */
3409  forceinline void
3411  who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3412  }
3413  forceinline void
3415  who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3416  }
3417  forceinline void
3419  who = (g.id() << 2) | POST;
3420  }
3421  forceinline void
3423  who = OTHER;
3424  }
3426  ViewTraceInfo::what(void) const {
3427  return static_cast<What>(who & 3);
3428  }
3429  forceinline const Propagator&
3431  assert(what() == PROPAGATOR);
3432  // Because PROPAGATOR == 0
3433  return *reinterpret_cast<Propagator*>(who);
3434  }
3435  forceinline const Brancher&
3437  assert(what() == BRANCHER);
3438  return *reinterpret_cast<Brancher*>(who & ~3);
3439  }
3441  ViewTraceInfo::post(void) const {
3442  assert(what() == POST);
3443  return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3444  }
3445 
3446  /*
3447  * Post information
3448  */
3449  forceinline
3450  PostInfo::PostInfo(Home home) : h(home) {
3451  h.pc.p.vti.post(home.propagatorgroup());
3452  }
3453  forceinline
3455  h.pc.p.vti.other();
3456  }
3457 
3458  /*
3459  * Propagate trace information
3460  *
3461  */
3462  forceinline
3464  const Propagator* p0, Status s0)
3465  : i(i0), g(g0), p(p0), s(s0) {}
3466  forceinline unsigned int
3468  return i;
3469  }
3472  return g;
3473  }
3474  forceinline const Propagator*
3476  return p;
3477  }
3480  return s;
3481  }
3482 
3483 
3484  /*
3485  * Commit trace information
3486  *
3487  */
3488  forceinline
3490  unsigned int a0)
3491  : b(b0), c(c0), a(a0) {}
3492  forceinline unsigned int
3493  CommitTraceInfo::id(void) const {
3494  return b.id();
3495  }
3498  return b.group();
3499  }
3500  forceinline const Brancher&
3502  return b;
3503  }
3504  forceinline const Choice&
3506  return c;
3507  }
3508  forceinline unsigned int
3510  return a;
3511  }
3512 
3513 
3514  /*
3515  * Propagator
3516  *
3517  */
3519  Propagator::cast(ActorLink* al) {
3520  // Turning al into a reference is for gcc, assume is for MSVC
3521  GECODE_NOT_NULL(al);
3522  ActorLink& t = *al;
3523  return static_cast<Propagator*>(&t);
3524  }
3525 
3526  forceinline const Propagator*
3527  Propagator::cast(const ActorLink* al) {
3528  // Turning al into a reference is for gcc, assume is for MSVC
3529  GECODE_NOT_NULL(al);
3530  const ActorLink& t = *al;
3531  return static_cast<const Propagator*>(&t);
3532  }
3533 
3534  forceinline Propagator*
3535  Propagator::fwd(void) const {
3536  return static_cast<Propagator*>(prev());
3537  }
3538 
3539  forceinline bool
3540  Propagator::disabled(void) const {
3541  return Support::marked(gpi_disabled);
3542  }
3543 
3544  forceinline void
3545  Propagator::disable(Space& home) {
3546  home.pc.p.bid_sc |= Space::sc_disabled;
3547  gpi_disabled = Support::fmark(gpi_disabled);
3548  }
3549 
3550  forceinline void
3551  Propagator::enable(Space& home) {
3552  (void) home;
3553  gpi_disabled = Support::funmark(gpi_disabled);
3554  }
3555 
3556  forceinline GPI::Info&
3558  return *static_cast<GPI::Info*>(Support::funmark(gpi_disabled));
3559  }
3560 
3561  forceinline
3563  : gpi_disabled((home.propagator() != NULL) ?
3564  // Inherit propagator information
3565  home.propagator()->gpi_disabled :
3566  // New propagator information
3567  static_cast<Space&>(home).gpi.allocate(home.propagatorgroup().gid)) {
3568  u.advisors = NULL;
3569  assert((u.med == 0) && (u.size == 0));
3570  static_cast<Space&>(home).pl.head(this);
3571  }
3572 
3573  forceinline
3575  : gpi_disabled(p.gpi_disabled) {
3576  u.advisors = NULL;
3577  assert((u.med == 0) && (u.size == 0));
3578  // Set forwarding pointer
3579  p.prev(this);
3580  }
3581 
3584  return u.med;
3585  }
3586 
3587  forceinline double
3588  Propagator::afc(void) const {
3589  return const_cast<Propagator&>(*this).gpi().afc;
3590  }
3591 
3592  forceinline unsigned int
3593  Propagator::id(void) const {
3594  return const_cast<Propagator&>(*this).gpi().pid;
3595  }
3596 
3598  Propagator::group(void) const {
3599  return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3600  }
3601 
3602  forceinline void
3604  gpi().gid = g.id();
3605  }
3606 
3609  p.u.size = s;
3610  return __ES_SUBSUMED;
3611  }
3612 
3615  p.u.size = p.dispose(*this);
3616  return __ES_SUBSUMED;
3617  }
3618 
3621  p.u.med = med;
3622  assert(p.u.med != 0);
3623  return __ES_PARTIAL;
3624  }
3625 
3628  p.u.med = AllVarConf::med_combine(p.u.med,med);
3629  assert(p.u.med != 0);
3630  return __ES_PARTIAL;
3631  }
3632 
3633 
3634 
3635  /*
3636  * Brancher
3637  *
3638  */
3640  Brancher::cast(ActorLink* al) {
3641  // Turning al into a reference is for gcc, assume is for MSVC
3642  GECODE_NOT_NULL(al);
3643  ActorLink& t = *al;
3644  return static_cast<Brancher*>(&t);
3645  }
3646 
3647  forceinline const Brancher*
3648  Brancher::cast(const ActorLink* al) {
3649  // Turning al into a reference is for gcc, assume is for MSVC
3650  GECODE_NOT_NULL(al);
3651  const ActorLink& t = *al;
3652  return static_cast<const Brancher*>(&t);
3653  }
3654 
3655  forceinline
3657  gid(_home.branchergroup().gid) {
3658  Space& home = static_cast<Space&>(_home);
3659  bid = home.pc.p.bid_sc >> Space::sc_bits;
3660  home.pc.p.bid_sc += (1 << Space::sc_bits);
3661  if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3662  throw TooManyBranchers("Brancher::Brancher");
3663  // If no brancher available, make it the first one
3664  if (home.b_status == &static_cast<Space&>(home).bl) {
3665  home.b_status = this;
3666  if (home.b_commit == &static_cast<Space&>(home).bl)
3667  home.b_commit = this;
3668  }
3669  home.bl.tail(this);
3670  }
3671 
3672  forceinline
3674  : bid(b.bid), gid(b.gid) {
3675  // Set forwarding pointer
3676  b.prev(this);
3677  }
3678 
3679  forceinline unsigned int
3680  Brancher::id(void) const {
3681  return bid;
3682  }
3683 
3685  Brancher::group(void) const {
3686  return BrancherGroup(gid);
3687  }
3688 
3689  forceinline void
3691  gid = g.id();
3692  }
3693 
3694 
3695  forceinline void
3696  Space::kill(Brancher& b) {
3697  assert(!failed());
3698  // Make sure that neither b_status nor b_commit does not point to b!
3699  if (b_commit == &b)
3700  b_commit = Brancher::cast(b.next());
3701  if (b_status == &b)
3702  b_status = Brancher::cast(b.next());
3703  b.unlink();
3704  rfree(&b,b.dispose(*this));
3705  }
3706 
3707  forceinline void
3708  Space::kill(Propagator& p) {
3709  assert(!failed());
3710  p.unlink();
3711  rfree(&p,p.dispose(*this));
3712  }
3713 
3714  forceinline Brancher*
3715  Space::brancher(unsigned int id) {
3716  /*
3717  * Due to weakly monotonic propagators the following scenario might
3718  * occur: a brancher has been committed with all its available
3719  * choices. Then, propagation determines less information
3720  * than before and the brancher now will create new choices.
3721  * Later, during recomputation, all of these choices
3722  * can be used together, possibly interleaved with
3723  * choices for other branchers. That means all branchers
3724  * must be scanned to find the matching brancher for the choice.
3725  *
3726  * b_commit tries to optimize scanning as it is most likely that
3727  * recomputation does not generate new choices during recomputation
3728  * and hence b_commit is moved from newer to older branchers.
3729  */
3730  Brancher* b_old = b_commit;
3731  // Try whether we are lucky
3732  while (b_commit != Brancher::cast(&bl))
3733  if (id != b_commit->id())
3734  b_commit = Brancher::cast(b_commit->next());
3735  else
3736  return b_commit;
3737  if (b_commit == Brancher::cast(&bl)) {
3738  // We did not find the brancher, start at the beginning
3739  b_commit = Brancher::cast(bl.next());
3740  while (b_commit != b_old)
3741  if (id != b_commit->id())
3742  b_commit = Brancher::cast(b_commit->next());
3743  else
3744  return b_commit;
3745  }
3746  return NULL;
3747  }
3748 
3749 
3750  /*
3751  * Local objects
3752  *
3753  */
3754 
3755  forceinline LocalObject*
3757  // Turning al into a reference is for gcc, assume is for MSVC
3758  GECODE_NOT_NULL(al);
3759  ActorLink& t = *al;
3760  return static_cast<LocalObject*>(&t);
3761  }
3762 
3763  forceinline const LocalObject*
3765  // Turning al into a reference is for gcc, assume is for MSVC
3766  GECODE_NOT_NULL(al);
3767  const ActorLink& t = *al;
3768  return static_cast<const LocalObject*>(&t);
3769  }
3770 
3771  forceinline
3773  (void) home;
3774  ActorLink::cast(this)->prev(NULL);
3775  }
3776 
3777  forceinline
3779  ActorLink::cast(this)->prev(NULL);
3780  }
3781 
3783  LocalObject::fwd(Space& home, bool share) {
3784  if (prev() == NULL)
3785  fwdcopy(home,share);
3786  return LocalObject::cast(prev());
3787  }
3788 
3789  forceinline
3790  LocalHandle::LocalHandle(void) : o(NULL) {}
3791  forceinline
3793  forceinline
3794  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3797  o = lh.o;
3798  return *this;
3799  }
3800  forceinline
3803  LocalHandle::object(void) const { return o; }
3804  forceinline void
3806  forceinline void
3807  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
3808  object(lh.object()->fwd(home,share));
3809  }
3810 
3811 
3812  /*
3813  * Choices
3814  *
3815  */
3816  forceinline
3817  Choice::Choice(const Brancher& b, const unsigned int a)
3818  : bid(b.id()), alt(a) {}
3819 
3820  forceinline unsigned int
3821  Choice::alternatives(void) const {
3822  return alt;
3823  }
3824 
3825  forceinline unsigned int
3826  Choice::id(void) const {
3827  return bid;
3828  }
3829 
3830  forceinline
3832 
3833 
3834 
3835  /*
3836  * No-good literal
3837  *
3838  */
3839  forceinline bool
3840  NGL::leaf(void) const {
3841  return Support::marked(nl);
3842  }
3843  forceinline NGL*
3844  NGL::next(void) const {
3845  return static_cast<NGL*>(Support::funmark(nl));
3846  }
3847  forceinline void
3848  NGL::leaf(bool l) {
3849  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3850  }
3851  forceinline void
3853  nl = Support::marked(nl) ? Support::mark(n) : n;
3854  }
3855  forceinline NGL*
3856  NGL::add(NGL* n, bool l) {
3857  nl = Support::marked(nl) ? Support::mark(n) : n;
3858  n->leaf(l);
3859  return n;
3860  }
3861 
3862  forceinline
3863  NGL::NGL(void)
3864  : nl(NULL) {}
3865  forceinline
3867  : nl(NULL) {}
3868  forceinline
3869  NGL::NGL(Space&, bool, NGL&)
3870  : nl(NULL) {}
3871  forceinline size_t
3873  return sizeof(*this);
3874  }
3875 
3876  /*
3877  * Advisor
3878  *
3879  */
3880  template<class A>
3881  forceinline
3883  // Store propagator and forwarding in prev()
3884  ActorLink::prev(&p);
3885  // Link to next advisor in next()
3886  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3887  }
3888 
3889  forceinline
3891 
3892  forceinline bool
3893  Advisor::disposed(void) const {
3894  return prev() == NULL;
3895  }
3896 
3897  forceinline Advisor*
3898  Advisor::cast(ActorLink* al) {
3899  return static_cast<Advisor*>(al);
3900  }
3901 
3902  forceinline const Advisor*
3903  Advisor::cast(const ActorLink* al) {
3904  return static_cast<const Advisor*>(al);
3905  }
3906 
3907  forceinline Propagator&
3908  Advisor::propagator(void) const {
3909  assert(!disposed());
3910  return *Propagator::cast(ActorLink::prev());
3911  }
3912 
3913  template<class A>
3914  forceinline void
3916  assert(!disposed());
3917  ActorLink::prev(NULL);
3918  // Shorten chains of disposed advisors by one, if possible
3919  Advisor* n = Advisor::cast(next());
3920  if ((n != NULL) && n->disposed())
3921  next(n->next());
3922  }
3923 
3924  forceinline const ViewTraceInfo&
3925  Advisor::operator ()(const Space& home) const {
3926  return home.pc.p.vti;
3927  }
3928 
3929  template<class A>
3932  a.dispose(*this,c);
3933  return ES_FIX;
3934  }
3935 
3936  template<class A>
3939  a.dispose(*this,c);
3940  return ES_NOFIX;
3941  }
3942 
3943  template<class A>
3946  a.dispose(*this,c);
3947  return ES_NOFIX_FORCE;
3948  }
3949 
3950 
3951 
3952  /*
3953  * Advisor council
3954  *
3955  */
3956  template<class A>
3957  forceinline
3959 
3960  template<class A>
3961  forceinline
3963  : advisors(NULL) {}
3964 
3965  template<class A>
3966  forceinline bool
3967  Council<A>::empty(void) const {
3968  ActorLink* a = advisors;
3969  while ((a != NULL) && static_cast<A*>(a)->disposed())
3970  a = a->next();
3971  advisors = a;
3972  return a == NULL;
3973  }
3974 
3975  template<class A>
3976  forceinline void
3977  Council<A>::update(Space& home, bool share, Council<A>& c) {
3978  // Skip all disposed advisors
3979  {
3980  ActorLink* a = c.advisors;
3981  while ((a != NULL) && static_cast<A*>(a)->disposed())
3982  a = a->next();
3983  c.advisors = a;
3984  }
3985  // Are there any advisors to be cloned?
3986  if (c.advisors != NULL) {
3987  // The propagator in from-space
3988  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3989  // The propagator in to-space
3990  Propagator* p_t = Propagator::cast(p_f->prev());
3991  // Advisors in from-space
3992  ActorLink** a_f = &c.advisors;
3993  // Advisors in to-space
3994  A* a_t = NULL;
3995  while (*a_f != NULL) {
3996  if (static_cast<A*>(*a_f)->disposed()) {
3997  *a_f = (*a_f)->next();
3998  } else {
3999  // Run specific copying part
4000  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
4001  // Set propagator pointer
4002  a->prev(p_t);
4003  // Set forwarding pointer
4004  (*a_f)->prev(a);
4005  // Link
4006  a->next(a_t);
4007  a_t = a;
4008  a_f = (*a_f)->next_ref();
4009  }
4010  }
4011  advisors = a_t;
4012  // Enter advisor link for reset
4013  assert(p_f->u.advisors == NULL);
4014  p_f->u.advisors = c.advisors;
4015  } else {
4016  advisors = NULL;
4017  }
4018  }
4019 
4020  template<class A>
4021  forceinline void
4023  ActorLink* a = advisors;
4024  while (a != NULL) {
4025  if (!static_cast<A*>(a)->disposed())
4026  static_cast<A*>(a)->dispose(home,*this);
4027  a = a->next();
4028  }
4029  }
4030 
4031 
4032 
4033  /*
4034  * Advisor iterator
4035  *
4036  */
4037  template<class A>
4038  forceinline
4040  : a(c.advisors) {
4041  while ((a != NULL) && static_cast<A*>(a)->disposed())
4042  a = a->next();
4043  }
4044 
4045  template<class A>
4046  forceinline bool
4048  return a != NULL;
4049  }
4050 
4051  template<class A>
4052  forceinline void
4054  do {
4055  a = a->next();
4056  } while ((a != NULL) && static_cast<A*>(a)->disposed());
4057  }
4058 
4059  template<class A>
4060  forceinline A&
4061  Advisors<A>::advisor(void) const {
4062  return *static_cast<A*>(a);
4063  }
4064 
4065 
4066 
4067  /*
4068  * Space
4069  *
4070  */
4071  forceinline void
4072  Space::enqueue(Propagator* p) {
4073  ActorLink::cast(p)->unlink();
4074  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
4075  c->tail(ActorLink::cast(p));
4076  if (c > pc.p.active)
4077  pc.p.active = c;
4078  }
4079 
4080  forceinline void
4081  Space::fail(void) {
4082  /*
4083  * Now active points beyond the last queue. This is essential as
4084  * enqueuing a propagator in a failed space keeps the space
4085  * failed.
4086  */
4087  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
4088  }
4089  forceinline void
4090  Home::fail(void) {
4091  s.fail();
4092  }
4093 
4094  forceinline bool
4095  Space::failed(void) const {
4096  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4097  }
4098  forceinline bool
4099  Home::failed(void) const {
4100  return s.failed();
4101  }
4102 
4103  forceinline bool
4104  Space::stable(void) const {
4105  return ((pc.p.active < &pc.p.queue[0]) ||
4106  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
4107  }
4108 
4110  Space::findtr(void) {
4111  TraceRecorder* tr = NULL;
4112  for (Actor** a=d_fst; a<d_cur; a++)
4113  if (Support::marked(*a) &&
4114  !static_cast<Propagator*>(Support::unmark(*a))->disabled()) {
4115  tr = static_cast<TraceRecorder*>(Support::unmark(*a));
4116  std::swap(*d_fst,*a);
4117  break;
4118  }
4119  return tr;
4120  }
4121 
4122  forceinline void
4124  if (p & AP_DISPOSE) {
4125  ap_notice_dispose(&a,d);
4126  }
4127  if (p & AP_VIEW_TRACE) {
4128  pc.p.bid_sc |= sc_trace;
4129  }
4130  if (p & AP_TRACE) {
4131  pc.p.bid_sc |= sc_trace;
4132  if (findtr())
4133  throw MoreThanOneTracer("Space::notice");
4134  ap_notice_dispose(static_cast<Actor*>(Support::fmark(&a)),d);
4135  }
4136  // Currently unused
4137  if (p & AP_WEAKLY) {}
4138  }
4139 
4140  forceinline void
4142  // Check wether array has already been discarded as space
4143  // deletion is already in progress
4144  if ((p & AP_DISPOSE) && (d_fst != NULL))
4145  ap_ignore_dispose(&a,d);
4146  if (p & AP_VIEW_TRACE) {}
4147  if ((p & AP_TRACE) && (d_fst != NULL))
4148  ap_ignore_dispose(static_cast<Actor*>(Support::fmark(&a)),d);
4149  // Currently unused
4150  if (p & AP_WEAKLY) {}
4151  }
4152 
4153 
4154 
4155  /*
4156  * Variable implementation
4157  *
4158  */
4159  template<class VIC>
4162  assert((pc >= 0) && (pc < pc_max+2));
4163  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4164  }
4165 
4166  template<class VIC>
4167  forceinline ActorLink**
4168  VarImp<VIC>::actorNonZero(PropCond pc) {
4169  assert((pc > 0) && (pc < pc_max+2));
4170  return b.base+u.idx[pc-1];
4171  }
4172 
4173  template<class VIC>
4174  forceinline unsigned int&
4176  assert((pc > 0) && (pc < pc_max+2));
4177  return u.idx[pc-1];
4178  }
4179 
4180  template<class VIC>
4181  forceinline unsigned int
4182  VarImp<VIC>::idx(PropCond pc) const {
4183  assert((pc > 0) && (pc < pc_max+2));
4184  return u.idx[pc-1];
4185  }
4186 
4187  template<class VIC>
4188  forceinline
4190  b.base = NULL; entries = 0;
4191  for (PropCond pc=1; pc<pc_max+2; pc++)
4192  idx(pc) = 0;
4193  free_and_bits = 0;
4194  }
4195 
4196  template<class VIC>
4197  forceinline
4199  b.base = NULL; entries = 0;
4200  for (PropCond pc=1; pc<pc_max+2; pc++)
4201  idx(pc) = 0;
4202  free_and_bits = 0;
4203  }
4204 
4205  template<class VIC>
4206  forceinline unsigned int
4207  VarImp<VIC>::degree(void) const {
4208  assert(!copied());
4209  return entries;
4210  }
4211 
4212  template<class VIC>
4213  forceinline double
4214  VarImp<VIC>::afc(void) const {
4215  double d = 0.0;
4216  // Count the afc of each propagator
4217  {
4218  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4219  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4220  while (a < e) {
4221  d += Propagator::cast(*a)->afc(); a++;
4222  }
4223  }
4224  // Count the afc of each advisor's propagator
4225  {
4226  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4227  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4228  while (a < e) {
4229  d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4230  ->propagator().afc();
4231  a++;
4232  }
4233  }
4234  return d;
4235  }
4236 
4237  template<class VIC>
4240  return d.me;
4241  }
4242 
4243  template<class VIC>
4244  forceinline unsigned int
4245  VarImp<VIC>::bits(void) const {
4246  return free_and_bits;
4247  }
4248 
4249  template<class VIC>
4250  forceinline unsigned int&
4252  return free_and_bits;
4253  }
4254 
4255 #ifdef GECODE_HAS_VAR_DISPOSE
4256  template<class VIC>
4258  VarImp<VIC>::vars_d(Space& home) {
4259  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4260  }
4261 
4262  template<class VIC>
4263  forceinline void
4264  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
4265  home.vars_d<VIC>(x);
4266  }
4267 #endif
4268 
4269  template<class VIC>
4270  forceinline bool
4271  VarImp<VIC>::copied(void) const {
4272  return Support::marked(b.fwd);
4273  }
4274 
4275  template<class VIC>
4277  VarImp<VIC>::forward(void) const {
4278  assert(copied());
4279  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4280  }
4281 
4282  template<class VIC>
4284  VarImp<VIC>::next(void) const {
4285  assert(copied());
4286  return u.next;
4287  }
4288 
4289  template<class VIC>
4290  forceinline
4292  VarImpBase** reg;
4293  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4294  if (x.b.base == NULL) {
4295  // Variable implementation needs no index structure
4296  reg = &home.pc.c.vars_noidx;
4297  assert(x.degree() == 0);
4298  } else {
4299  reg = &home.pc.c.vars_u[idx_c];
4300  }
4301  // Save subscriptions in copy
4302  b.base = x.b.base;
4303  entries = x.entries;
4304  for (PropCond pc=1; pc<pc_max+2; pc++)
4305  idx(pc) = x.idx(pc);
4306 
4307  // Set forwarding pointer
4308  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4309  // Register original
4310  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4311  }
4312 
4313  template<class VIC>
4316  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4317  }
4318 
4319  template<class VIC>
4322  return static_cast<ModEventDelta>(me << VIC::med_fst);
4323  }
4324 
4325  template<class VIC>
4328  return VIC::me_combine(me1,me2);
4329  }
4330 
4331  template<class VIC>
4332  forceinline void
4334  bool force) {
4335  if (VIC::med_update(p.u.med,me) || force)
4336  home.enqueue(&p);
4337  }
4338 
4339  template<class VIC>
4340  forceinline void
4342  ActorLink** b = actor(pc1);
4343  ActorLink** p = actorNonZero(pc2+1);
4344  while (p-- > b)
4345  schedule(home,*Propagator::cast(*p),me);
4346  }
4347 
4348  template<class VIC>
4349  forceinline void
4350  VarImp<VIC>::resize(Space& home) {
4351  if (b.base == NULL) {
4352  assert((free_and_bits >> free_bits) == 0);
4353  // Create fresh dependency array with four entries
4354  free_and_bits += 4 << free_bits;
4355  b.base = home.alloc<ActorLink*>(4);
4356  for (int i=0; i<pc_max+1; i++)
4357  u.idx[i] = 0;
4358  } else {
4359  // Resize dependency array
4360  unsigned int n = degree();
4361  // Find out whether the area is most likely in the special area
4362  // reserved for subscriptions. If yes, just resize mildly otherwise
4363  // more agressively
4364  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4365  unsigned int m =
4366  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4367  (n+4) : ((n+1)*3>>1);
4368  ActorLink** prop = home.alloc<ActorLink*>(m);
4369  free_and_bits += (m-n) << free_bits;
4370  // Copy entries
4371  Heap::copy<ActorLink*>(prop, b.base, n);
4372  home.free<ActorLink*>(b.base,n);
4373  b.base = prop;
4374  }
4375  }
4376 
4377  template<class VIC>
4378  forceinline void
4379  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4380  assert(pc <= pc_max);
4381  // Count one new subscription
4382  home.pc.p.n_sub += 1;
4383  if ((free_and_bits >> free_bits) == 0)
4384  resize(home);
4385  free_and_bits -= 1 << free_bits;
4386 
4387  // Enter subscription
4388  b.base[entries] = *actorNonZero(pc_max+1);
4389  entries++;
4390  for (PropCond j = pc_max; j > pc; j--) {
4391  *actorNonZero(j+1) = *actorNonZero(j);
4392  idx(j+1)++;
4393  }
4394  *actorNonZero(pc+1) = *actor(pc);
4395  idx(pc+1)++;
4396  *actor(pc) = ActorLink::cast(p);
4397 
4398 #ifdef GECODE_AUDIT
4399  ActorLink** f = actor(pc);
4400  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4401  if (*f == p)
4402  goto found;
4403  else
4404  f++;
4405  GECODE_NEVER;
4406  found: ;
4407 #endif
4408  }
4409 
4410  template<class VIC>
4411  forceinline void
4412  VarImp<VIC>::enter(Space& home, Advisor* a) {
4413  // Note that a might be a marked pointer
4414  // Count one new subscription
4415  home.pc.p.n_sub += 1;
4416  if ((free_and_bits >> free_bits) == 0)
4417  resize(home);
4418  free_and_bits -= 1 << free_bits;
4419 
4420  // Enter subscription
4421  b.base[entries++] = *actorNonZero(pc_max+1);
4422  *actorNonZero(pc_max+1) = a;
4423  }
4424 
4425  template<class VIC>
4426  forceinline void
4428  bool assigned, ModEvent me, bool schedule) {
4429  if (assigned) {
4430  // Do not subscribe, just schedule the propagator
4431  if (schedule)
4433  } else {
4434  enter(home,&p,pc);
4435  // Schedule propagator
4436  if (schedule && (pc != PC_GEN_ASSIGNED))
4437  VarImp<VIC>::schedule(home,p,me);
4438  }
4439  }
4440 
4441  template<class VIC>
4442  forceinline void
4443  VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4444  if (!assigned) {
4445  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4446  enter(home,ma);
4447  }
4448  }
4449 
4450  template<class VIC>
4451  forceinline void
4453  bool assigned, ModEvent me) {
4454  if (assigned)
4456  else if (pc != PC_GEN_ASSIGNED)
4457  VarImp<VIC>::schedule(home,p,me);
4458  }
4459 
4460  template<class VIC>
4461  void
4463  assert(pc <= pc_max);
4465  // Find actor in dependency array
4466  ActorLink** f = actor(pc);
4467 #ifdef GECODE_AUDIT
4468  while (f < actorNonZero(pc+1))
4469  if (*f == a)
4470  goto found;
4471  else
4472  f++;
4473  GECODE_NEVER;
4474  found: ;
4475 #else
4476  while (*f != a) f++;
4477 #endif
4478  // Remove actor
4479  *f = *(actorNonZero(pc+1)-1);
4480  for (PropCond j = pc+1; j< pc_max+1; j++) {
4481  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4482  idx(j)--;
4483  }
4484  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4485  idx(pc_max+1)--;
4486  entries--;
4487  free_and_bits += 1 << free_bits;
4488  home.pc.p.n_sub -= 1;
4489  }
4490 
4491  template<class VIC>
4492  forceinline void
4494  if (b.base != NULL)
4495  remove(home,&p,pc);
4496  }
4497 
4498  template<class VIC>
4499  void
4500  VarImp<VIC>::remove(Space& home, Advisor* a) {
4501  // Note that a might be a marked pointer
4502  // Find actor in dependency array
4503  ActorLink** f = actorNonZero(pc_max+1);
4504 #ifdef GECODE_AUDIT
4505  while (f < b.base+entries)
4506  if (*f == a)
4507  goto found;
4508  else
4509  f++;
4510  GECODE_NEVER;
4511  found: ;
4512 #else
4513  while (*f != a) f++;
4514 #endif
4515  // Remove actor
4516  *f = b.base[--entries];
4517  free_and_bits += 1 << free_bits;
4518  home.pc.p.n_sub -= 1;
4519  }
4520 
4521  template<class VIC>
4522  forceinline void
4523  VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
4524  if (b.base != NULL) {
4525  Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4526  remove(home,ma);
4527  }
4528  }
4529 
4530  template<class VIC>
4531  forceinline void
4533  unsigned int n_sub = degree();
4534  home.pc.p.n_sub -= n_sub;
4535  unsigned int n = (free_and_bits >> free_bits) + n_sub;
4536  home.free<ActorLink*>(b.base,n);
4537  // Must be NULL such that cloning works
4538  b.base = NULL;
4539  // Must be 0 such that degree works
4540  entries = 0;
4541  // Must be NULL such that afc works
4542  for (PropCond pc=1; pc<pc_max+2; pc++)
4543  idx(pc) = 0;
4544  free_and_bits &= (1 << free_bits) - 1;
4545  }
4546 
4547  template<class VIC>
4548  forceinline bool
4550  /*
4551  * An advisor that is executed might remove itself due to subsumption.
4552  * As entries are removed from front to back, the advisors must
4553  * be iterated in forward direction.
4554  */
4555  ActorLink** la = actorNonZero(pc_max+1);
4556  ActorLink** le = b.base+entries;
4557  if (la == le)
4558  return true;
4559  d.me = me;
4560  // An advisor that is run, might be removed during execution.
4561  // As removal is done from the back the advisors have to be executed
4562  // in inverse order.
4563  do {
4564  Advisor* a = Advisor::cast
4565  (static_cast<ActorLink*>(Support::funmark(*la)));
4566  assert(!a->disposed());
4567  Propagator& p = a->propagator();
4568  switch (p.advise(home,*a,d)) {
4569  case ES_FIX:
4570  break;
4571  case ES_FAILED:
4572  return false;
4573  case ES_NOFIX:
4574  schedule(home,p,me);
4575  break;
4576  case ES_NOFIX_FORCE:
4577  schedule(home,p,me,true);
4578  break;
4579  case __ES_SUBSUMED:
4580  default:
4581  GECODE_NEVER;
4582  }
4583  } while (++la < le);
4584  return true;
4585  }
4586 
4587  template<class VIC>
4588  void
4589  VarImp<VIC>::_fail(Space& home) {
4590  /*
4591  * An advisor that is executed might remove itself due to subsumption.
4592  * As entries are removed from front to back, the advisors must
4593  * be iterated in forward direction.
4594  */
4595  ActorLink** la = actorNonZero(pc_max+1);
4596  ActorLink** le = b.base+entries;
4597  if (la == le)
4598  return;
4599  // An advisor that is run, might be removed during execution.
4600  // As removal is done from the back the advisors have to be executed
4601  // in inverse order.
4602  do {
4603  if (Support::marked(*la)) {
4604  Advisor* a = Advisor::cast(static_cast<ActorLink*>
4605  (Support::unmark(*la)));
4606  assert(!a->disposed());
4607  Propagator& p = a->propagator();
4608  p.advise(home,*a);
4609  }
4610  } while (++la < le);
4611  }
4612 
4613  template<class VIC>
4614  ModEvent
4616  _fail(home);
4617  return ME_GEN_FAILED;
4618  }
4619 
4620  template<class VIC>
4621  forceinline void
4623  // this refers to the variable to be updated (clone)
4624  // x refers to the original
4625  // Recover from copy
4626  x->b.base = b.base;
4627  x->u.idx[0] = u.idx[0];
4628  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4629  x->u.idx[1] = u.idx[1];
4630 
4631  unsigned int np =
4632  static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4633  unsigned int na =
4634  static_cast<unsigned int >(x->b.base + x->entries -
4635  x->actorNonZero(pc_max+1));
4636  unsigned int n = na + np;
4637  assert(n == x->degree());
4638 
4639  ActorLink** f = x->b.base;
4640  ActorLink** t = sub;
4641 
4642  sub += n;
4643  b.base = t;
4644  // Process propagator subscriptions
4645  while (np >= 4) {
4646  ActorLink* p3 = f[3]->prev();
4647  ActorLink* p0 = f[0]->prev();
4648  ActorLink* p1 = f[1]->prev();
4649  ActorLink* p2 = f[2]->prev();
4650  t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4651  np -= 4; t += 4; f += 4;
4652  }
4653  if (np >= 2) {
4654  ActorLink* p0 = f[0]->prev();
4655  ActorLink* p1 = f[1]->prev();
4656  t[0] = p0; t[1] = p1;
4657  np -= 2; t += 2; f += 2;
4658  }
4659  if (np > 0) {
4660  ActorLink* p0 = f[0]->prev();
4661  t[0] = p0;
4662  t += 1; f += 1;
4663  }
4664  // Process advisor subscriptions
4665  while (na >= 4) {
4666  ptrdiff_t m0, m1, m2, m3;
4667  ActorLink* p3 =
4668  static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4669  ActorLink* p0 =
4670  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4671  ActorLink* p1 =
4672  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4673  ActorLink* p2 =
4674  static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4675  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4676  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4677  t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4678  t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4679  na -= 4; t += 4; f += 4;
4680  }
4681  if (na >= 2) {
4682  ptrdiff_t m0, m1;
4683  ActorLink* p0 =
4684  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4685  ActorLink* p1 =
4686  static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4687  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4688  t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4689  na -= 2; t += 2; f += 2;
4690  }
4691  if (na > 0) {
4692  ptrdiff_t m0;
4693  ActorLink* p0 =
4694  static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4695  t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4696  }
4697  }
4698 
4699  template<class VIC>
4700  forceinline void
4701  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4702  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4703  while (x != NULL) {
4704  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4705  }
4706  }
4707 
4708 
4709 
4710  /*
4711  * Variable disposer
4712  *
4713  */
4714  template<class VarImp>
4716 #ifdef GECODE_HAS_VAR_DISPOSE
4717  Space::vd[VarImp::idx_d] = this;
4718 #endif
4719  }
4720 
4721  template<class VarImp>
4722  void
4724  VarImp* x = static_cast<VarImp*>(_x);
4725  do {
4726  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4727  } while (x != NULL);
4728  }
4729 
4730  /*
4731  * Statistics
4732  */
4733 
4734  forceinline void
4736  propagate = 0;
4737  }
4738  forceinline
4740  reset();
4741  }
4744  propagate += s.propagate;
4745  return *this;
4746  }
4749  StatusStatistics t(s);
4750  return t += *this;
4751  }
4752 
4753  forceinline void
4755 
4756  forceinline
4758  reset();
4759  }
4762  CloneStatistics s;
4763  return s;
4764  }
4767  return *this;
4768  }
4769 
4770  forceinline void
4772 
4773  forceinline
4775  reset();
4776  }
4779  CommitStatistics s;
4780  return s;
4781  }
4784  return *this;
4785  }
4786 
4787  /*
4788  * Cost computation
4789  *
4790  */
4791 
4792  forceinline
4793  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4794 
4795  forceinline PropCost
4796  PropCost::cost(PropCost::Mod m,
4798  unsigned int n) {
4799  if (n < 2)
4800  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4801  else if (n == 2)
4802  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4803  else if (n == 3)
4804  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4805  else
4806  return (m == LO) ? lo : hi;
4807  }
4808 
4809  forceinline PropCost
4811  return AC_RECORD;
4812  }
4814  PropCost::crazy(PropCost::Mod m, unsigned int n) {
4815  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4816  }
4819  assert(n >= 0);
4820  return crazy(m,static_cast<unsigned int>(n));
4821  }
4823  PropCost::cubic(PropCost::Mod m, unsigned int n) {
4824  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4825  }
4828  assert(n >= 0);
4829  return cubic(m,static_cast<unsigned int>(n));
4830  }
4833  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4834  }
4837  assert(n >= 0);
4838  return quadratic(m,static_cast<unsigned int>(n));
4839  }
4841  PropCost::linear(PropCost::Mod m, unsigned int n) {
4842  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4843  }
4846  assert(n >= 0);
4847  return linear(m,static_cast<unsigned int>(n));
4848  }
4851  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4852  }
4855  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4856  }
4859  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4860  }
4861 
4862  /*
4863  * Iterators for propagators and branchers of a space
4864  *
4865  */
4866  forceinline
4867  Space::Propagators::Propagators(Space& home0)
4868  : home(home0), q(home.pc.p.active) {
4869  while (q >= &home.pc.p.queue[0]) {
4870  if (q->next() != q) {
4871  c = q->next(); e = q; q--;
4872  return;
4873  }
4874  q--;
4875  }
4876  q = NULL;
4877  if (!home.pl.empty()) {
4878  c = Propagator::cast(home.pl.next());
4879  e = Propagator::cast(&home.pl);
4880  } else {
4881  c = e = NULL;
4882  }
4883  }
4884  forceinline bool
4885  Space::Propagators::operator ()(void) const {
4886  return c != NULL;
4887  }
4888  forceinline void
4889  Space::Propagators::operator ++(void) {
4890  c = c->next();
4891  if (c == e) {
4892  if (q == NULL) {
4893  c = NULL;
4894  } else {
4895  while (q >= &home.pc.p.queue[0]) {
4896  if (q->next() != q) {
4897  c = q->next(); e = q; q--;
4898  return;
4899  }
4900  q--;
4901  }
4902  q = NULL;
4903  if (!home.pl.empty()) {
4904  c = Propagator::cast(home.pl.next());
4905  e = Propagator::cast(&home.pl);
4906  } else {
4907  c = NULL;
4908  }
4909  }
4910  }
4911  }
4912  forceinline Propagator&
4913  Space::Propagators::propagator(void) const {
4914  return *Propagator::cast(c);
4915  }
4916 
4917 
4918  forceinline
4919  Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
4920  : home(home0), q(home.pc.p.active) {
4921  while (q >= &home.pc.p.queue[0]) {
4922  if (q->next() != q) {
4923  c = q->next(); e = q; q--;
4924  return;
4925  }
4926  q--;
4927  }
4928  q = c = e = NULL;
4929  }
4930  forceinline bool
4931  Space::ScheduledPropagators::operator ()(void) const {
4932  return c != NULL;
4933  }
4934  forceinline void
4935  Space::ScheduledPropagators::operator ++(void) {
4936  c = c->next();
4937  if (c == e) {
4938  if (q == NULL) {
4939  c = NULL;
4940  } else {
4941  while (q >= &home.pc.p.queue[0]) {
4942  if (q->next() != q) {
4943  c = q->next(); e = q; q--;
4944  return;
4945  }
4946  q--;
4947  }
4948  q = c = e = NULL;
4949  }
4950  }
4951  }
4952  forceinline Propagator&
4954  return *Propagator::cast(c);
4955  }
4956 
4957 
4958  forceinline
4959  Space::IdlePropagators::IdlePropagators(Space& home) {
4960  c = Propagator::cast(home.pl.next());
4961  e = Propagator::cast(&home.pl);
4962  }
4963  forceinline bool
4964  Space::IdlePropagators::operator ()(void) const {
4965  return c != e;
4966  }
4967  forceinline void
4968  Space::IdlePropagators::operator ++(void) {
4969  c = c->next();
4970  }
4971  forceinline Propagator&
4973  return *Propagator::cast(c);
4974  }
4975 
4976 
4977  forceinline
4978  Space::Branchers::Branchers(Space& home)
4979  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4980  forceinline bool
4981  Space::Branchers::operator ()(void) const {
4982  return c != e;
4983  }
4984  forceinline void
4985  Space::Branchers::operator ++(void) {
4986  c = c->next();
4987  }
4988  forceinline Brancher&
4989  Space::Branchers::brancher(void) const {
4990  return *Brancher::cast(c);
4991  }
4992 
4993 
4994  /*
4995  * Groups of actors
4996  */
4997  forceinline
4998  Group::Group(unsigned int gid0) : gid(gid0) {}
4999 
5000  forceinline bool
5001  Group::in(Group actor) const {
5002  return (gid == GROUPID_ALL) || (gid == actor.gid);
5003  }
5004 
5005  forceinline bool
5006  Group::in(void) const {
5007  return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
5008  }
5009 
5010  forceinline
5011  Group::Group(const Group& g) : gid(g.gid) {}
5012 
5015  gid=g.gid; return *this;
5016  }
5017 
5018  forceinline unsigned int
5019  Group::id(void) const {
5020  return gid;
5021  }
5022 
5023 
5024  forceinline
5026 
5027  forceinline
5029  : Group(gid) {}
5030 
5031  forceinline
5033  : Group(g) {}
5034 
5037  return static_cast<PropagatorGroup&>(Group::operator =(g));
5038  }
5039 
5042  return Home(home,NULL,*this,BrancherGroup::def);
5043  }
5044 
5045  forceinline bool
5047  return id() == g.id();
5048  }
5049  forceinline bool
5051  return id() != g.id();
5052  }
5053 
5056  if (id() != GROUPID_ALL)
5057  p.group(*this);
5058  return *this;
5059  }
5060 
5061 
5062  forceinline
5064 
5065  forceinline
5067  : Group(gid) {}
5068 
5069  forceinline
5071  : Group(g) {}
5072 
5075  return static_cast<BrancherGroup&>(Group::operator =(g));
5076  }
5077 
5080  return Home(home,NULL,PropagatorGroup::def,*this);
5081  }
5082 
5083  forceinline bool
5085  return id() == g.id();
5086  }
5087  forceinline bool
5089  return id() != g.id();
5090  }
5091 
5094  if (id() != GROUPID_ALL)
5095  p.group(*this);
5096  return *this;
5097  }
5098 
5099 
5100  /*
5101  * Iterators for propagators and branchers in a group
5102  *
5103  */
5104  forceinline
5106  : ps(home), g(g0) {
5107  while (ps() && !g.in(ps.propagator().group()))
5108  ++ps;
5109  }
5110  forceinline bool
5112  return ps();
5113  }
5114  forceinline void
5116  do
5117  ++ps;
5118  while (ps() && !g.in(ps.propagator().group()));
5119  }
5120  forceinline const Propagator&
5122  return ps.propagator();
5123  }
5124 
5125  forceinline
5127  : bs(home), g(g0) {
5128  while (bs() && !g.in(bs.brancher().group()))
5129  ++bs;
5130  }
5131  forceinline bool
5133  return bs();
5134  }
5135  forceinline void
5137  do
5138  ++bs;
5139  while (bs() && !g.in(bs.brancher().group()));
5140  }
5141  forceinline const Brancher&
5142  Branchers::brancher(void) const {
5143  return bs.brancher();
5144  }
5145 
5146 
5147  /*
5148  * Space construction support
5149  *
5150  */
5151  template<class T>
5152  forceinline T&
5154  return alloc<T>(1);
5155  }
5156  template<class T, typename A1>
5157  forceinline T&
5158  Space::construct(A1 const& a1) {
5159  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5160  new (&t) T(a1);
5161  return t;
5162  }
5163  template<class T, typename A1, typename A2>
5164  forceinline T&
5165  Space::construct(A1 const& a1, A2 const& a2) {
5166  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5167  new (&t) T(a1,a2);
5168  return t;
5169  }
5170  template<class T, typename A1, typename A2, typename A3>
5171  forceinline T&
5172  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5173  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5174  new (&t) T(a1,a2,a3);
5175  return t;
5176  }
5177  template<class T, typename A1, typename A2, typename A3, typename A4>
5178  forceinline T&
5179  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5180  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5181  new (&t) T(a1,a2,a3,a4);
5182  return t;
5183  }
5184  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5185  forceinline T&
5186  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5187  T& t = *static_cast<T*>(ralloc(sizeof(T)));
5188  new (&t) T(a1,a2,a3,a4,a5);
5189  return t;
5190  }
5191 
5192 }
5193 
5194 // STATISTICS: kernel-core
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: var.hpp:113
CommitStatistics(void)
Initialize.
Definition: core.hpp:4774
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
Post propagator for SetVar x
Definition: set.hh:784
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1844
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:5041
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4810
@ SUBSUMED
Propagator is subsumed.
Definition: core.hpp:1036
#define forceinline
Definition: config.hpp:173
Status status(void) const
Return propagator status.
Definition: core.hpp:3479
void kill(Space &home)
Kill all branchers in a group.
Definition: core.cpp:1006
@ SS_SOLVED
Space is solved (no brancher left)
Definition: core.hpp:1690
Advisors(const Council< A > &c)
Initialize.
Definition: core.hpp:4039
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
Definition: core.hpp:3463
@ FAILED
The literal is failed.
Definition: core.hpp:1349
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1105
@ AC_MAX
Maximal cost value.
Definition: core.hpp:574
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3593
Configuration class for variable implementations without index structure.
Definition: core.hpp:178
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:913
static const PropCond pc_max
Maximal propagation condition.
Definition: core.hpp:185
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:5050
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
Definition: core.hpp:3925
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:4723
@ AP_TRACE
Definition: core.hpp:646
PropagatorGroup group(void) const
Return propagator group.
Definition: core.hpp:3471
ViewTraceInfo vti
View trace information.
Definition: core.hpp:1846
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3938
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2894
@ AP_WEAKLY
Definition: core.hpp:636
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
const unsigned long int s
Number of solutions since last restart.
Definition: core.hpp:1637
Propagator for recording trace information.
BrancherGroup branchergroup(void) const
Return brancher group.
Definition: core.hpp:3401
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3856
Base class for Variable type disposer.
Definition: core.hpp:257
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4615
@ AC_TERNARY_HI
Three variables, expensive.
Definition: core.hpp:568
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:4104
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4854
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3821
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:916
@ OTHER
Unknown.
Definition: core.hpp:987
friend class Branchers
Definition: core.hpp:1755
void update(Space &home, bool share, Council< A > &c)
Update during cloning (copies all advisors)
Definition: core.hpp:3977
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:4748
Manage memory for space.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:5136
double afc(void) const
Return accumulated failure count (plus degree)
Definition: core.hpp:4214
Object(void)
Initialize.
Definition: core.hpp:3082
void reset(void)
Reset information.
Definition: core.hpp:4754
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3831
const unsigned int a
Number of asset in portfolio.
Definition: core.hpp:1648
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:4766
PostInfo(Home home)
Set information.
Definition: core.hpp:3450
static const int idx_c
Index for update.
Definition: core.hpp:181
@ FAILED
Propagator failed.
Definition: core.hpp:1035
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:917
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:156
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Class to iterate over advisors of a council.
Definition: core.hpp:233
Class to iterate over branchers in a group.
Definition: core.hpp:2803
struct Gecode::Space::@56::@57 p
Data only available during propagation or branching.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
Gecode::IntArgs i(4, 1, 2, 3, 4)
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition: core.hpp:3397
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3790
bool empty(void) const
Test whether council has advisor left.
Definition: core.hpp:3967
Archive representation
Definition: archive.hpp:45
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition: core.hpp:1691
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:4327
BrancherGroup bg
A brancher group.
Definition: core.hpp:932
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition: core.hpp:750
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:926
@ LO
Cheap.
Definition: core.hpp:581
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:3090
NodeType t
Type of node.
Definition: bool-expr.cpp:234
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3334
PropagatorGroup g
Propagator group.
Definition: core.hpp:1042
void disable(Space &home)
Disable all propagators in a group.
Definition: core.cpp:941
static const int med_fst
Start of bits for modification event delta.
Definition: core.hpp:189
Exception: too many branchers
Definition: exception.hpp:97
Single _b(1, 4)
The shared object.
Definition: core.hpp:88
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:319
Computation spaces.
Definition: core.hpp:1748
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
const Brancher & b
Brancher.
Definition: core.hpp:1068
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3627
unsigned int alternative(void) const
Return alternative.
Definition: core.hpp:3509
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition: var-type.hpp:889
Local (space-shared) object.
Definition: core.hpp:1538
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3796
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:3172
Base-class for both propagators and branchers.
Definition: core.hpp:696
@ PROPAGATOR
A propagator is currently executing.
Definition: core.hpp:981
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4832
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3598
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4245
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:547
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:49
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3203
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
CloneStatistics(void)
Initialize.
Definition: core.hpp:4757
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:3608
const Type t
Type of information.
Definition: core.hpp:1631
unsigned int i
Propagator id.
Definition: core.hpp:1040
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:104
unsigned int bid_sc
Id of next brancher to be created plus status control.
Definition: core.hpp:1842
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3817
@ ES_NOFIX_FORCE
Advisor forces rescheduling of propagator.
Definition: core.hpp:546
@ AC_BINARY_HI
Two variables, expensive.
Definition: core.hpp:569
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition: core.hpp:5036
friend class Brancher
Definition: core.hpp:1753
~LocalHandle(void)
Destructor.
Definition: core.hpp:3801
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:787
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2858
unsigned int gid
The group id.
Definition: core.hpp:756
What
What is currently executing.
Definition: core.hpp:979
~PostInfo(void)
Reset information.
Definition: core.hpp:3454
@ NOFIX
Propagator did not compute fixpoint.
Definition: core.hpp:1034
unsigned long int fail(void) const
Return number of failures since last restart.
Definition: core.hpp:3198
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Definition: core.hpp:541
Gecode toplevel namespace
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition: core.cpp:950
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:972
Base-class for propagators.
Definition: core.hpp:1092
Group of branchers.
Definition: core.hpp:865
@ AC_UNARY_LO
Only single variable, cheap.
Definition: core.hpp:572
double afc(void) const
Return the accumlated failure count.
Definition: core.hpp:3588
No-goods recorded from restarts.
Definition: core.hpp:1595
const Choice & choice(void) const
Return choice.
Definition: core.hpp:3505
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:67
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:5115
const Brancher & brancher(void) const
Return brancher.
Definition: core.hpp:3501
@ AC_LINEAR_HI
Linear complexity, expensive.
Definition: core.hpp:566
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:3393
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:4053
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition: core.hpp:4452
const NoGoods & ng
No-goods from restart.
Definition: core.hpp:1643
@ FIX
Propagator computed fixpoint.
Definition: core.hpp:1033
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:3377
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition: core.cpp:995
@ POST
A post function is executing.
Definition: core.hpp:985
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3680
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:855
Handles for local (space-shared) objects.
Definition: core.hpp:1565
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:3389
Base-class for branchers.
Definition: core.hpp:1446
friend class LocalObject
Definition: core.hpp:702
Commit trace information.
Definition: core.hpp:1064
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4277
Mod
Propagation cost modifier.
Definition: core.hpp:580
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:205
const Brancher & brancher(void) const
Return currently executing brancher.
Definition: core.hpp:3436
NGL(void)
Constructor for creation.
Definition: core.hpp:3863
Home class for posting propagators
Definition: core.hpp:922
VarImp(void)
Creation of static instances.
Definition: core.hpp:4198
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
@ AC_BINARY_LO
Two variables, cheap.
Definition: core.hpp:571
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3872
Space & h
The home space.
Definition: core.hpp:1017
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4823
Handle to region.
Definition: region.hpp:61
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:630
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:3127
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:147
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3756
@ AC_QUADRATIC_LO
Quadratic complexity, cheap.
Definition: core.hpp:564
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:5121
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4858
friend class Propagator
Definition: core.hpp:699
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
static const int med_lst
End of bits for modification event delta.
Definition: core.hpp:191
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition: core.hpp:5074
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:3165
ActualCost ac
Actual cost.
Definition: core.hpp:577
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2868
friend class ActorLink
Definition: core.hpp:1093
Global propagator information.
Definition: gpi.hpp:43
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:3368
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:3583
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:3339
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:5001
@ RESTART
Information is provided by a restart-based engine.
Definition: core.hpp:1625
unsigned int id(void) const
Return propagator identifier.
Definition: core.hpp:3467
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
Definition: core.hpp:3475
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:5019
void * alloc(SharedMemory *sm, size_t s)
Allocate memory of size s.
Statistics for execution of clone
Definition: core.hpp:1716
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:894
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2853
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition: core.hpp:4783
Class to set group information when a post function is executed.
Definition: core.hpp:1014
const Choice & c
Choice.
Definition: core.hpp:1070
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:928
Group baseclass for controlling actors.
Definition: core.hpp:741
Propagators(Space &home, PropagatorGroup g)
Initialize.
Definition: core.hpp:5105
Class for storing timed-decay value.
Definition: gpi.hpp:46
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:4549
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:74
Council(void)
Default constructor.
Definition: core.hpp:3958
IntSet * A
Position of a piece in a square board.
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:5142
unsigned int gid
Group identifier.
Definition: gpi.hpp:51
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1833
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition: core.hpp:3441
Base class for heap allocated objects.
Definition: heap.hpp:344
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1853
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
@ AC_CUBIC_LO
Cubic complexity, cheap.
Definition: core.hpp:562
void reset(void)
Reset information.
Definition: core.hpp:4771
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3803
Group & operator=(const Group &g)
Assignment operator.
Definition: core.hpp:5014
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:4427
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:257
static const int free_bits
Freely available bits.
Definition: core.hpp:187
AFC afc
Definition: afc.cpp:139
Exception: action has wrong arity
Definition: exception.hpp:153
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
int ModEvent
Type for modification events.
Definition: core.hpp:142
Propagator & propagator(void) const
Return the advisor's propagator.
Definition: core.hpp:3908
Base-class for freelist-managed objects.
PropagatorGroup(void)
Constructor.
Definition: core.hpp:5025
BrancherGroup(void)
Constructor.
Definition: core.hpp:5063
const Propagator * p
Propagator.
Definition: core.hpp:1044
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:348
@ AC_UNARY_HI
Only single variable, expensive.
Definition: core.hpp:573
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:4743
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1107
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition: core.hpp:5088
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:3344
Type type(void) const
Return type of information.
Definition: core.hpp:3184
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
ActorProperty
Actor properties.
Definition: core.hpp:621
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:5046
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition: core.hpp:752
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4095
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:4715
void fail(void)
Fail space.
Definition: core.hpp:4081
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4850
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4099
NoGoods(void)
Initialize.
Definition: core.hpp:3154
Propagation cost.
Definition: core.hpp:554
ActualCost
The actual cost values that are used.
Definition: core.hpp:558
const Space * l
Last solution found.
Definition: core.hpp:1641
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1701
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3840
bool in(void) const
Check whether this is a real group (and not just default)
Definition: core.hpp:5006
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition: core.hpp:5084
void * subscriptions(void) const
Get the memory area for subscriptions.
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3685
Iterator over subscribed propagators.
void fail(void)
Mark space as failed.
Definition: core.hpp:4090
@ AC_RECORD
Reserved for recording information.
Definition: core.hpp:559
Status
Propagator status.
Definition: core.hpp:1032
Council of advisors
Definition: core.hpp:232
void reset(void)
Reset information.
Definition: core.hpp:4735
Branchers(Space &home, BrancherGroup g)
Initialize.
Definition: core.hpp:5126
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:2838
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
friend class ActorLink
Definition: core.hpp:697
const unsigned long int f
Number of failures since last restart.
Definition: core.hpp:1639
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1857
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:858
friend class Propagators
Definition: core.hpp:1752
Group(void)
Constructor.
Definition: core.cpp:884
static Group all
Group of all actors.
Definition: core.hpp:784
Gecode::IntSet d(v, 7)
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:4778
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:5132
Base-class for advisors.
Definition: core.hpp:1294
StatusStatistics(void)
Initialize.
Definition: core.hpp:4739
IntPropLevel sm(IntPropLevel ipl)
Extract speed or memory from propagation level.
Definition: ipl.hpp:47
double afc
The afc value.
Definition: gpi.hpp:53
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3915
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:4207
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3540
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:4333
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:545
Status s
Status.
Definition: core.hpp:1046
@ AC_CRAZY_LO
Exponential complexity, cheap.
Definition: core.hpp:560
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2834
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
Definition: core.hpp:3489
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4315
~SharedHandle(void)
Destructor that maintains reference count.
Definition: core.hpp:3143
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:4239
Statistics for execution of status
Definition: core.hpp:1698
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3208
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
View trace information.
Definition: core.hpp:974
friend class Brancher
Definition: core.hpp:701
@ AC_CRAZY_HI
Exponential complexity, expensive.
Definition: core.hpp:561
struct Gecode::Space::@56::@58 c
Data available only during copying.
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4321
void update(Space &home, bool share, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3807
virtual ~Object(void)
Delete shared object.
Definition: core.hpp:3085
void decay(double d)
Set decay factor to d.
Definition: gpi.hpp:237
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition: core.hpp:3193
unsigned int id(void) const
Return brancher identifier.
Definition: core.hpp:3493
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1613
const Propagator & propagator(void) const
Return currently executing propagator.
Definition: core.hpp:3430
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:145
SharedHandle & operator=(const SharedHandle &sh)
Assignment operator maintaining reference count.
Definition: core.hpp:3120
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:3945
@ SUBSUMED
The literal is subsumed.
Definition: core.hpp:1350
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:4047
friend class ActorLink
Definition: core.hpp:1447
BrancherGroup group(void) const
Return brancher group.
Definition: core.hpp:3497
PropagatorGroup pg
A propagator group.
Definition: core.hpp:930
friend class Home
Definition: core.hpp:742
@ AC_TERNARY_LO
Three variables, cheap.
Definition: core.hpp:570
Base-class for variable implementations.
Definition: core.hpp:249
Base-class for variable implementations.
Definition: core.hpp:234
Information passed by meta search engines.
Definition: core.hpp:1620
SpaceStatus
Space status
Definition: core.hpp:1688
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
Group of propagators.
Definition: core.hpp:794
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
unsigned long int n
Number of no-goods.
Definition: core.hpp:1598
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
The shared handle.
Definition: core.hpp:79
Home operator()(Space &home)
To augment a space argument.
Definition: core.hpp:5079
@ HI
Expensive.
Definition: core.hpp:582
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Definition: core.hpp:991
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition: core.hpp:1627
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:2919
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
Definition: core.hpp:3783
static unsigned int next
Next group id.
Definition: core.hpp:759
Gecode::FloatVal c(-8, 8)
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4271
void kill(Space &home)
Kill all propagators in a group.
Definition: core.cpp:928
Shared object for several memory areas.
No-good literal recorded during search.
Definition: core.hpp:1342
A & advisor(void) const
Return advisor.
Definition: core.hpp:4061
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4532
SharedHandle::Object * shared
Linked list of shared objects.
Definition: core.hpp:1855
void dispose(Space &home)
Dispose council.
Definition: core.hpp:4022
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:154
friend class PropagatorGroup
Definition: core.hpp:1099
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Propagate trace information.
Definition: core.hpp:1028
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
ActorLink ** base
Subscribed actors.
Definition: core.hpp:310
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:346
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Status
The status of a no-good literal.
Definition: core.hpp:1348
Choice for performing commit
Definition: core.hpp:1414
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:4123
Variable implementation disposer
Definition: core.hpp:272
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:542
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3620
@ AC_LINEAR_LO
Linear complexity, cheap.
Definition: core.hpp:567
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2830
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:3188
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
@ AC_QUADRATIC_HI
Quadratic complexity, expensive.
Definition: core.hpp:565
SharedHandle(void)
Create shared handle with no object pointing to.
Definition: core.hpp:3110
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:543
@ BRANCHER
A brancher is executing.
Definition: core.hpp:983
static const unsigned int GROUPID_MAX
The maximal group number.
Definition: core.hpp:754
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3844
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:3535
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3931
What what(void) const
Return what is currently executing.
Definition: core.hpp:3426
virtual Object * copy(void) const =0
Return fresh copy for update.
static const int idx_d
Index for disposal.
Definition: core.hpp:183
const unsigned long int r
Number of restarts.
Definition: core.hpp:1635
unsigned int asset(void) const
Return number of asset in portfolio.
Definition: core.hpp:3213
Type
Which type of information is provided.
Definition: core.hpp:1623
@ ES_OK
Execution is okay.
Definition: core.hpp:544
@ SS_FAILED
Space is failed
Definition: core.hpp:1689
Class to iterate over propagators in a group.
Definition: core.hpp:2785
Statistics for execution of commit
Definition: core.hpp:1732
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:4761
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:3157
void other(void)
Record that nothing is known at this point.
Definition: core.hpp:3422
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:5111
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:79
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:3364
bool marked(void *p)
Check whether p is marked.
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4814
@ AC_CUBIC_HI
Cubic complexity, expensive.
Definition: core.hpp:563
GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3557
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:762
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:201
T & construct(void)
Construction routines.
Definition: core.hpp:5153
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2954
unsigned int a
Alternative.
Definition: core.hpp:1072
static const int med_mask
Bitmask for modification event delta.
Definition: core.hpp:193
@ AP_VIEW_TRACE
Definition: core.hpp:641
ExecStatus
Definition: core.hpp:540