Generated on Mon Sep 22 2014 12:49:30 for Gecode by doxygen 1.8.7
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: 2013-10-30 16:01:30 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
22  * $Revision: 14038 $
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 {
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);
106  static void* operator new(size_t s);
108  static void operator delete(void* p);
109  };
110  private:
112  Object* o;
114  void subscribe(void);
116  void cancel(void);
117  public:
119  SharedHandle(void);
123  SharedHandle(const SharedHandle& sh);
127  void update(Space& home, bool share, SharedHandle& sh);
129  ~SharedHandle(void);
130  protected:
132  SharedHandle::Object* object(void) const;
135  };
136 
145  typedef int ModEvent;
147 
154 
156  typedef int PropCond;
158  const PropCond PC_GEN_NONE = -1;
162 
173  typedef int ModEventDelta;
174 
175 }
176 
178 
179 namespace Gecode {
180 
183  public:
185  static const int idx_c = -1;
187  static const int idx_d = -1;
191  static const int free_bits = 0;
193  static const int med_fst = 0;
195  static const int med_lst = 0;
197  static const int med_mask = 0;
199  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
201  static bool med_update(ModEventDelta& med, ModEvent me);
202  };
203 
206  GECODE_NEVER; return 0;
207  }
208  forceinline bool
210  GECODE_NEVER; return false;
211  }
212 
213 
214  /*
215  * These are the classes of interest
216  *
217  */
218  class ActorLink;
219  class Actor;
220  class Propagator;
221  class LocalObject;
222  class Advisor;
223  class AFC;
224  class Brancher;
225  class BrancherHandle;
226  template<class A> class Council;
227  template<class A> class Advisors;
228  template<class VIC> class VarImp;
229 
230 
231  /*
232  * Variable implementations
233  *
234  */
235 
243  class VarImpBase {};
244 
252  public:
254  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
257  };
258 
265  template<class VarImp>
267  public:
269  VarImpDisposer(void);
271  virtual void dispose(Space& home, VarImpBase* x);
272  };
273 
275  class Delta {
276  template<class VIC> friend class VarImp;
277  private:
279  ModEvent me;
280  };
281 
289  template<class VIC>
290  class VarImp : public VarImpBase {
291  friend class Space;
292  friend class Propagator;
293  template<class VarImp> friend class VarImpDisposer;
294  private:
295  union {
313  } b;
314 
316  static const int idx_c = VIC::idx_c;
318  static const int idx_d = VIC::idx_d;
320  static const int free_bits = VIC::free_bits;
322  unsigned int entries;
324  unsigned int free_and_bits;
326  static const Gecode::PropCond pc_max = VIC::pc_max;
327 
328  union {
339  unsigned int idx[pc_max+1];
342  } u;
343 
345  ActorLink** actor(PropCond pc);
347  ActorLink** actorNonZero(PropCond pc);
349  unsigned int& idx(PropCond pc);
351  unsigned int idx(PropCond pc) const;
352 
359  void update(VarImp* x, ActorLink**& sub);
366  static void update(Space& home, ActorLink**& sub);
367 
369  void enter(Space& home, Propagator* p, PropCond pc);
371  void enter(Space& home, Advisor* a);
373  void resize(Space& home);
375  void remove(Space& home, Propagator* p, PropCond pc);
377  void remove(Space& home, Advisor* a);
378 
379 
380  protected:
382  void cancel(Space& home);
388  bool advise(Space& home, ModEvent me, Delta& d);
389 #ifdef GECODE_HAS_VAR_DISPOSE
390  static VarImp<VIC>* vars_d(Space& home);
393  static void vars_d(Space& home, VarImp<VIC>* x);
394 #endif
395 
396  public:
398  VarImp(Space& home);
400  VarImp(void);
401 
403 
404 
416  void subscribe(Space& home, Propagator& p, PropCond pc,
417  bool assigned, ModEvent me, bool schedule);
423  void cancel(Space& home, Propagator& p, PropCond pc,
424  bool assigned);
430  void subscribe(Space& home, Advisor& a, bool assigned);
436  void cancel(Space& home, Advisor& a, bool assigned);
437 
444  unsigned int degree(void) const;
451  double afc(const Space& home) const;
453 
455 
456  VarImp(Space& home, bool share, VarImp& x);
459  bool copied(void) const;
461  VarImp* forward(void) const;
463  VarImp* next(void) const;
465 
467 
468 
475  static void schedule(Space& home, Propagator& p, ModEvent me,
476  bool force = false);
478  static ModEvent me(const ModEventDelta& med);
480  static ModEventDelta med(ModEvent me);
482  static ModEvent me_combine(ModEvent me1, ModEvent me2);
484 
486 
487  static ModEvent modevent(const Delta& d);
490 
492 
493  unsigned int bits(void) const;
496  unsigned int& bits(void);
498 
499  protected:
501  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
502 
503  public:
505 
506  static void* operator new(size_t,Space&);
509  static void operator delete(void*,Space&);
511  static void operator delete(void*);
513  };
514 
523  enum ExecStatus {
525  ES_FAILED = -1,
526  ES_NOFIX = 0,
527  ES_OK = 0,
528  ES_FIX = 1,
531  };
532 
537  class PropCost {
538  friend class Space;
539  public:
541  enum ActualCost {
556  AC_MAX = 6
557  };
560  public:
562  enum Mod {
563  LO,
564  HI
565  };
566  private:
568  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
571  public:
573  static PropCost crazy(PropCost::Mod m, unsigned int n);
575  static PropCost crazy(PropCost::Mod m, int n);
577  static PropCost cubic(PropCost::Mod m, unsigned int n);
579  static PropCost cubic(PropCost::Mod m, int n);
581  static PropCost quadratic(PropCost::Mod m, unsigned int n);
583  static PropCost quadratic(PropCost::Mod m, int n);
585  static PropCost linear(PropCost::Mod m, unsigned int n);
587  static PropCost linear(PropCost::Mod m, int n);
589  static PropCost ternary(PropCost::Mod m);
591  static PropCost binary(PropCost::Mod m);
593  static PropCost unary(PropCost::Mod m);
594  };
595 
596 
610  AP_DISPOSE = (1 << 0),
616  AP_WEAKLY = (1 << 1)
617  };
618 
619 
627  class ActorLink {
628  friend class Actor;
629  friend class Propagator;
630  friend class Advisor;
631  friend class Brancher;
632  friend class LocalObject;
633  friend class Space;
634  template<class VIC> friend class VarImp;
635  private:
636  ActorLink* _next; ActorLink* _prev;
637  public:
639  ActorLink* prev(void) const; void prev(ActorLink*);
641  ActorLink* next(void) const; void next(ActorLink*);
642  ActorLink** next_ref(void);
644 
646  void init(void);
648  void unlink(void);
650  void head(ActorLink* al);
652  void tail(ActorLink* al);
654  bool empty(void) const;
656  template<class T> static ActorLink* cast(T* a);
658  template<class T> static const ActorLink* cast(const T* a);
659  };
660 
661 
667  friend class ActorLink;
668  friend class Space;
669  friend class Propagator;
670  friend class Advisor;
671  friend class Brancher;
672  friend class LocalObject;
673  template<class VIC> friend class VarImp;
674  template<class A> friend class Council;
675  private:
677  static Actor* cast(ActorLink* al);
679  static const Actor* cast(const ActorLink* al);
681  GECODE_KERNEL_EXPORT static Actor* sentinel;
682  public:
684  virtual Actor* copy(Space& home, bool share) = 0;
685 
687 
690  virtual size_t dispose(Space& home);
692  static void* operator new(size_t s, Space& home);
694  static void operator delete(void* p, Space& home);
695  private:
696 #ifndef __GNUC__
697  static void operator delete(void* p);
699 #endif
700  static void* operator new(size_t s);
703 #ifdef __GNUC__
704  public:
706  GECODE_KERNEL_EXPORT virtual ~Actor(void);
708  static void operator delete(void* p);
709 #endif
710  };
711 
712 
713 
717  class Home {
718  protected:
723  public:
725 
726  Home(Space& s, Propagator* p=NULL);
729  Home& operator =(const Home& h);
731  operator Space&(void);
733 
738  Propagator* propagator(void) const;
740 
742  bool failed(void) const;
745  void fail(void);
747  void notice(Actor& a, ActorProperty p, bool duplicate=false);
749  };
750 
756  friend class ActorLink;
757  friend class Space;
758  template<class VIC> friend class VarImp;
759  friend class Advisor;
760  template<class A> friend class Council;
761  private:
762  union {
766  size_t size;
769  } u;
771  GlobalAFC::Counter& gafc;
773  static Propagator* cast(ActorLink* al);
775  static const Propagator* cast(const ActorLink* al);
776  protected:
778  Propagator(Home home);
780  Propagator(Space& home, bool share, Propagator& p);
782  Propagator* fwd(void) const;
783 
784  public:
786 
787 
810  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
812  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
820  ModEventDelta modeventdelta(void) const;
857  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
859 
861  double afc(const Space& home) const;
864  };
865 
866 
874  template<class A>
875  class Council {
876  friend class Advisor;
877  friend class Advisors<A>;
878  private:
880  mutable ActorLink* advisors;
881  public:
883  Council(void);
885  Council(Space& home);
887  bool empty(void) const;
889  void update(Space& home, bool share, Council<A>& c);
891  void dispose(Space& home);
892  };
893 
894 
899  template<class A>
900  class Advisors {
901  private:
903  ActorLink* a;
904  public:
906  Advisors(const Council<A>& c);
908  bool operator ()(void) const;
910  void operator ++(void);
912  A& advisor(void) const;
913  };
914 
915 
926  class Advisor : private ActorLink {
927  template<class VIC> friend class VarImp;
928  template<class A> friend class Council;
929  template<class A> friend class Advisors;
930  private:
932  bool disposed(void) const;
934  static Advisor* cast(ActorLink* al);
936  static const Advisor* cast(const ActorLink* al);
937  protected:
939  Propagator& propagator(void) const;
940  public:
942  template<class A>
943  Advisor(Space& home, Propagator& p, Council<A>& c);
945  Advisor(Space& home, bool share, Advisor& a);
946 
948 
949  template<class A>
951  void dispose(Space& home, Council<A>& c);
953  static void* operator new(size_t s, Space& home);
955  static void operator delete(void* p, Space& home);
957  private:
958 #ifndef __GNUC__
959  static void operator delete(void* p);
961 #endif
962  static void* operator new(size_t s);
964  };
965 
966 
972  private:
974  void* nl;
975  public:
977  enum Status {
980  NONE
981  };
983  NGL(void);
985  NGL(Space& home);
987  NGL(Space& home, bool share, NGL& ngl);
989  virtual void subscribe(Space& home, Propagator& p) = 0;
991  virtual void cancel(Space& home, Propagator& p) = 0;
993  virtual NGL::Status status(const Space& home) const = 0;
995  virtual ExecStatus prune(Space& home) = 0;
997  virtual NGL* copy(Space& home, bool share) = 0;
1000  virtual bool notice(void) const;
1002  virtual size_t dispose(Space& home);
1004 
1005  bool leaf(void) const;
1008  NGL* next(void) const;
1010  void leaf(bool l);
1012  void next(NGL* n);
1014  NGL* add(NGL* n, bool l);
1016 
1018  static void* operator new(size_t s, Space& home);
1021  static void operator delete(void* s, Space& home);
1023  static void operator delete(void* p);
1025  };
1026 
1037  friend class Space;
1038  private:
1039  unsigned int _id;
1040  unsigned int _alt;
1041 
1043  unsigned int id(void) const;
1044  protected:
1046  Choice(const Brancher& b, const unsigned int a);
1047  public:
1049  unsigned int alternatives(void) const;
1051  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1053  virtual size_t size(void) const = 0;
1055  static void* operator new(size_t);
1057  static void operator delete(void*);
1059  GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
1060  };
1061 
1072  friend class ActorLink;
1073  friend class Space;
1074  friend class Choice;
1075  private:
1077  unsigned int _id;
1079  static Brancher* cast(ActorLink* al);
1081  static const Brancher* cast(const ActorLink* al);
1082  protected:
1084  Brancher(Home home);
1086  Brancher(Space& home, bool share, Brancher& b);
1087  public:
1089 
1090  unsigned int id(void) const;
1100  virtual bool status(const Space& home) const = 0;
1108  virtual const Choice* choice(Space& home) = 0;
1110  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1117  virtual ExecStatus commit(Space& home, const Choice& c,
1118  unsigned int a) = 0;
1133  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1144  virtual void print(const Space& home, const Choice& c, unsigned int a,
1145  std::ostream& o) const;
1147  };
1148 
1158  private:
1160  unsigned int _id;
1161  public:
1163  BrancherHandle(void);
1165  BrancherHandle(const Brancher& b);
1167  void update(Space& home, bool share, BrancherHandle& bh);
1169  unsigned int id(void) const;
1171  bool operator ()(const Space& home) const;
1173  void kill(Space& home);
1174  };
1175 
1183  class LocalObject : public Actor {
1184  friend class ActorLink;
1185  friend class Space;
1186  friend class LocalHandle;
1187  protected:
1189  LocalObject(Home home);
1191  LocalObject(Space& home, bool share, LocalObject& l);
1193  static LocalObject* cast(ActorLink* al);
1195  static const LocalObject* cast(const ActorLink* al);
1196  private:
1198  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1199  public:
1201  LocalObject* fwd(Space& home, bool share);
1202  };
1203 
1210  class LocalHandle {
1211  private:
1213  LocalObject* o;
1214  protected:
1216  LocalHandle(void);
1218  LocalHandle(LocalObject* lo);
1220  LocalHandle(const LocalHandle& lh);
1221  public:
1223  LocalHandle& operator =(const LocalHandle& lh);
1225  void update(Space& home, bool share, LocalHandle& lh);
1227  ~LocalHandle(void);
1228  protected:
1230  LocalObject* object(void) const;
1232  void object(LocalObject* n);
1233  };
1234 
1235 
1241  protected:
1243  unsigned long int n;
1244  public:
1246  NoGoods(void);
1249  virtual void post(Space& home);
1251  unsigned long int ng(void) const;
1253  void ng(unsigned long int n);
1255  virtual ~NoGoods(void);
1256  };
1257 
1258 
1267  };
1268 
1274  public:
1276  unsigned long int propagate;
1278  bool wmp;
1280  StatusStatistics(void);
1282  void reset(void);
1287  };
1288 
1294  public:
1296  CloneStatistics(void);
1298  void reset(void);
1303  };
1304 
1310  public:
1312  CommitStatistics(void);
1314  void reset(void);
1319  };
1320 
1321 
1326  friend class Actor;
1327  friend class Propagator;
1328  friend class Brancher;
1329  friend class Advisor;
1330  template<class VIC> friend class VarImp;
1331  template<class VarImp> friend class VarImpDisposer;
1332  friend class SharedHandle;
1333  friend class LocalObject;
1334  friend class Region;
1335  friend class AFC;
1336  friend class BrancherHandle;
1337  private:
1339  SharedMemory* sm;
1341  MemoryManager mm;
1343  GlobalAFC gafc;
1345  ActorLink pl;
1347  ActorLink bl;
1353  Brancher* b_status;
1365  Brancher* b_commit;
1367  Brancher* brancher(unsigned int id);
1370  void kill_brancher(unsigned int id);
1372  static const unsigned reserved_branch_id = 0U;
1373  union {
1375  struct {
1392  unsigned int branch_id;
1394  unsigned int n_sub;
1395  } p;
1397  struct {
1406  } c;
1407  } pc;
1409  void enqueue(Propagator* p);
1414 #ifdef GECODE_HAS_VAR_DISPOSE
1415  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1418  VarImpBase* _vars_d[AllVarConf::idx_d];
1420  template<class VIC> VarImpBase* vars_d(void) const;
1422  template<class VIC> void vars_d(VarImpBase* x);
1423 #endif
1424  void update(ActorLink** sub);
1427 
1429  Actor** d_fst;
1431  Actor** d_cur;
1433  Actor** d_lst;
1434 
1446  unsigned int _wmp_afc;
1448  void afc_enable(void);
1450  bool afc_enabled(void) const;
1452  void wmp(unsigned int n);
1454  unsigned int wmp(void) const;
1455 
1457  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1459  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1461  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1462 
1481  GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
1482 
1516  void _commit(const Choice& c, unsigned int a);
1517 
1549  void _trycommit(const Choice& c, unsigned int a);
1550 
1551  public:
1556  GECODE_KERNEL_EXPORT Space(void);
1561  GECODE_KERNEL_EXPORT virtual ~Space(void);
1572  GECODE_KERNEL_EXPORT Space(bool share, Space& s);
1579  virtual Space* copy(bool share) = 0;
1590  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1605  virtual void master(unsigned long int i, const Space* s,
1606  NoGoods& ng);
1620  virtual void slave(unsigned long int i, const Space* s);
1625  static void* operator new(size_t);
1630  static void operator delete(void*);
1631 
1632 
1633  /*
1634  * Member functions for search engines
1635  *
1636  */
1637 
1650  SpaceStatus status(StatusStatistics& stat=unused_status);
1651 
1684  const Choice* choice(void);
1685 
1696  const Choice* choice(Archive& e) const;
1697 
1718  Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
1719 
1754  void commit(const Choice& c, unsigned int a,
1755  CommitStatistics& stat=unused_commit);
1788  void trycommit(const Choice& c, unsigned int a,
1789  CommitStatistics& stat=unused_commit);
1809  NGL* ngl(const Choice& c, unsigned int a);
1810 
1826  void print(const Choice& c, unsigned int a, std::ostream& o) const;
1827 
1837  void notice(Actor& a, ActorProperty p, bool duplicate=false);
1846  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
1847 
1848 
1859  ExecStatus ES_SUBSUMED(Propagator& p);
1874  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
1885  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1896  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1897 
1908  template<class A>
1909  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
1920  template<class A>
1921  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
1933  template<class A>
1934  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
1935 
1943  void fail(void);
1952  bool failed(void) const;
1957  bool stable(void) const;
1964  GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
1971  GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
1972 
1974 
1975  Home operator ()(Propagator& p);
1978 
1990  template<class T>
1991  T* alloc(long unsigned int n);
1998  template<class T>
1999  T* alloc(long int n);
2006  template<class T>
2007  T* alloc(unsigned int n);
2014  template<class T>
2015  T* alloc(int n);
2025  template<class T>
2026  void free(T* b, long unsigned int n);
2036  template<class T>
2037  void free(T* b, long int n);
2047  template<class T>
2048  void free(T* b, unsigned int n);
2058  template<class T>
2059  void free(T* b, int n);
2071  template<class T>
2072  T* realloc(T* b, long unsigned int n, long unsigned int m);
2084  template<class T>
2085  T* realloc(T* b, long int n, long int m);
2097  template<class T>
2098  T* realloc(T* b, unsigned int n, unsigned int m);
2110  template<class T>
2111  T* realloc(T* b, int n, int m);
2119  template<class T>
2120  T** realloc(T** b, long unsigned int n, long unsigned int m);
2128  template<class T>
2129  T** realloc(T** b, long int n, long int m);
2137  template<class T>
2138  T** realloc(T** b, unsigned int n, unsigned int m);
2146  template<class T>
2147  T** realloc(T** b, int n, int m);
2149  void* ralloc(size_t s);
2151  void rfree(void* p, size_t s);
2153  void* rrealloc(void* b, size_t n, size_t m);
2155  template<size_t> void* fl_alloc(void);
2161  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2170  GECODE_KERNEL_EXPORT void flush(void);
2172 
2174 
2177  template<class T>
2178  T& construct(void);
2184  template<class T, typename A1>
2185  T& construct(A1 const& a1);
2191  template<class T, typename A1, typename A2>
2192  T& construct(A1 const& a1, A2 const& a2);
2198  template<class T, typename A1, typename A2, typename A3>
2199  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2205  template<class T, typename A1, typename A2, typename A3, typename A4>
2206  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2212  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2213  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2215 
2221  class Propagators {
2222  private:
2224  const Space& home;
2226  const ActorLink* q;
2228  const ActorLink* c;
2230  const ActorLink* e;
2231  public:
2233  Propagators(const Space& home);
2235  bool operator ()(void) const;
2237  void operator ++(void);
2239  const Propagator& propagator(void) const;
2240  };
2241 
2247  class Branchers {
2248  private:
2250  const ActorLink* c;
2252  const ActorLink* e;
2253  public:
2255  Branchers(const Space& home);
2257  bool operator ()(void) const;
2259  void operator ++(void);
2261  const Brancher& brancher(void) const;
2262  };
2263 
2265 
2268  void afc_decay(double d);
2270  double afc_decay(void) const;
2273  void afc_set(double a);
2275  };
2276 
2277 
2278 
2279 
2280  /*
2281  * Memory management
2282  *
2283  */
2284 
2285  // Heap allocated
2286  forceinline void*
2287  SharedHandle::Object::operator new(size_t s) {
2288  return heap.ralloc(s);
2289  }
2290  forceinline void
2291  SharedHandle::Object::operator delete(void* p) {
2292  heap.rfree(p);
2293  }
2294 
2295  forceinline void*
2296  Space::operator new(size_t s) {
2297  return heap.ralloc(s);
2298  }
2299  forceinline void
2300  Space::operator delete(void* p) {
2301  heap.rfree(p);
2302  }
2303 
2304  forceinline void
2305  Choice::operator delete(void* p) {
2306  heap.rfree(p);
2307  }
2308  forceinline void*
2309  Choice::operator new(size_t s) {
2310  return heap.ralloc(s);
2311  }
2312 
2313 
2314  // Space allocation: general space heaps and free lists
2315  forceinline void*
2316  Space::ralloc(size_t s) {
2317  return mm.alloc(sm,s);
2318  }
2319  forceinline void
2320  Space::rfree(void* p, size_t s) {
2321  return mm.reuse(p,s);
2322  }
2323  forceinline void*
2324  Space::rrealloc(void* _b, size_t n, size_t m) {
2325  char* b = static_cast<char*>(_b);
2326  if (n < m) {
2327  char* p = static_cast<char*>(ralloc(m));
2328  memcpy(p,b,n);
2329  rfree(b,n);
2330  return p;
2331  } else {
2332  rfree(b+m,m-n);
2333  return b;
2334  }
2335  }
2336 
2337  template<size_t s>
2338  forceinline void*
2340  return mm.template fl_alloc<s>(sm);
2341  }
2342  template<size_t s>
2343  forceinline void
2345  mm.template fl_dispose<s>(f,l);
2346  }
2347 
2348  /*
2349  * Typed allocation routines
2350  *
2351  */
2352  template<class T>
2353  forceinline T*
2354  Space::alloc(long unsigned int n) {
2355  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2356  for (long unsigned int i=n; i--; )
2357  (void) new (p+i) T();
2358  return p;
2359  }
2360  template<class T>
2361  forceinline T*
2362  Space::alloc(long int n) {
2363  assert(n >= 0);
2364  return alloc<T>(static_cast<long unsigned int>(n));
2365  }
2366  template<class T>
2367  forceinline T*
2368  Space::alloc(unsigned int n) {
2369  return alloc<T>(static_cast<long unsigned int>(n));
2370  }
2371  template<class T>
2372  forceinline T*
2374  assert(n >= 0);
2375  return alloc<T>(static_cast<long unsigned int>(n));
2376  }
2377 
2378  template<class T>
2379  forceinline void
2380  Space::free(T* b, long unsigned int n) {
2381  for (long unsigned int i=n; i--; )
2382  b[i].~T();
2383  rfree(b,n*sizeof(T));
2384  }
2385  template<class T>
2386  forceinline void
2387  Space::free(T* b, long int n) {
2388  assert(n >= 0);
2389  free<T>(b,static_cast<long unsigned int>(n));
2390  }
2391  template<class T>
2392  forceinline void
2393  Space::free(T* b, unsigned int n) {
2394  free<T>(b,static_cast<long unsigned int>(n));
2395  }
2396  template<class T>
2397  forceinline void
2398  Space::free(T* b, int n) {
2399  assert(n >= 0);
2400  free<T>(b,static_cast<long unsigned int>(n));
2401  }
2402 
2403  template<class T>
2404  forceinline T*
2405  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2406  if (n < m) {
2407  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2408  for (long unsigned int i=n; i--; )
2409  (void) new (p+i) T(b[i]);
2410  for (long unsigned int i=n; i<m; i++)
2411  (void) new (p+i) T();
2412  free<T>(b,n);
2413  return p;
2414  } else {
2415  free<T>(b+m,m-n);
2416  return b;
2417  }
2418  }
2419  template<class T>
2420  forceinline T*
2421  Space::realloc(T* b, long int n, long int m) {
2422  assert((n >= 0) && (m >= 0));
2423  return realloc<T>(b,static_cast<long unsigned int>(n),
2424  static_cast<long unsigned int>(m));
2425  }
2426  template<class T>
2427  forceinline T*
2428  Space::realloc(T* b, unsigned int n, unsigned int m) {
2429  return realloc<T>(b,static_cast<long unsigned int>(n),
2430  static_cast<long unsigned int>(m));
2431  }
2432  template<class T>
2433  forceinline T*
2434  Space::realloc(T* b, int n, int m) {
2435  assert((n >= 0) && (m >= 0));
2436  return realloc<T>(b,static_cast<long unsigned int>(n),
2437  static_cast<long unsigned int>(m));
2438  }
2439 
2440 #define GECODE_KERNEL_REALLOC(T) \
2441  template<> \
2442  forceinline T* \
2443  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2444  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2445  } \
2446  template<> \
2447  forceinline T* \
2448  Space::realloc<T>(T* b, long int n, long int m) { \
2449  assert((n >= 0) && (m >= 0)); \
2450  return realloc<T>(b,static_cast<long unsigned int>(n), \
2451  static_cast<long unsigned int>(m)); \
2452  } \
2453  template<> \
2454  forceinline T* \
2455  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2456  return realloc<T>(b,static_cast<long unsigned int>(n), \
2457  static_cast<long unsigned int>(m)); \
2458  } \
2459  template<> \
2460  forceinline T* \
2461  Space::realloc<T>(T* b, int n, int m) { \
2462  assert((n >= 0) && (m >= 0)); \
2463  return realloc<T>(b,static_cast<long unsigned int>(n), \
2464  static_cast<long unsigned int>(m)); \
2465  }
2466 
2467  GECODE_KERNEL_REALLOC(bool)
2468  GECODE_KERNEL_REALLOC(signed char)
2469  GECODE_KERNEL_REALLOC(unsigned char)
2470  GECODE_KERNEL_REALLOC(signed short int)
2471  GECODE_KERNEL_REALLOC(unsigned short int)
2472  GECODE_KERNEL_REALLOC(signed int)
2473  GECODE_KERNEL_REALLOC(unsigned int)
2474  GECODE_KERNEL_REALLOC(signed long int)
2475  GECODE_KERNEL_REALLOC(unsigned long int)
2476  GECODE_KERNEL_REALLOC(float)
2477  GECODE_KERNEL_REALLOC(double)
2478 
2479 #undef GECODE_KERNEL_REALLOC
2480 
2481  template<class T>
2482  forceinline T**
2483  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2484  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2485  }
2486  template<class T>
2487  forceinline T**
2488  Space::realloc(T** b, long int n, long int m) {
2489  assert((n >= 0) && (m >= 0));
2490  return realloc<T*>(b,static_cast<long unsigned int>(n),
2491  static_cast<long unsigned int>(m));
2492  }
2493  template<class T>
2494  forceinline T**
2495  Space::realloc(T** b, unsigned int n, unsigned int m) {
2496  return realloc<T*>(b,static_cast<long unsigned int>(n),
2497  static_cast<long unsigned int>(m));
2498  }
2499  template<class T>
2500  forceinline T**
2501  Space::realloc(T** b, int n, int m) {
2502  assert((n >= 0) && (m >= 0));
2503  return realloc<T*>(b,static_cast<long unsigned int>(n),
2504  static_cast<long unsigned int>(m));
2505  }
2506 
2507 
2508 #ifdef GECODE_HAS_VAR_DISPOSE
2509  template<class VIC>
2511  Space::vars_d(void) const {
2512  return _vars_d[VIC::idx_d];
2513  }
2514  template<class VIC>
2515  forceinline void
2516  Space::vars_d(VarImpBase* x) {
2517  _vars_d[VIC::idx_d] = x;
2518  }
2519 #endif
2520 
2521  // Space allocated entities: Actors, variable implementations, and advisors
2522  forceinline void
2523  Actor::operator delete(void*) {}
2524  forceinline void
2525  Actor::operator delete(void*, Space&) {}
2526  forceinline void*
2527  Actor::operator new(size_t s, Space& home) {
2528  return home.ralloc(s);
2529  }
2530 
2531  template<class VIC>
2532  forceinline void
2533  VarImp<VIC>::operator delete(void*) {}
2534  template<class VIC>
2535  forceinline void
2536  VarImp<VIC>::operator delete(void*, Space&) {}
2537  template<class VIC>
2538  forceinline void*
2539  VarImp<VIC>::operator new(size_t s, Space& home) {
2540  return home.ralloc(s);
2541  }
2542 
2543 #ifndef __GNUC__
2544  forceinline void
2545  Advisor::operator delete(void*) {}
2546 #endif
2547  forceinline void
2548  Advisor::operator delete(void*, Space&) {}
2549  forceinline void*
2550  Advisor::operator new(size_t s, Space& home) {
2551  return home.ralloc(s);
2552  }
2553 
2554  forceinline void
2555  NGL::operator delete(void*) {}
2556  forceinline void
2557  NGL::operator delete(void*, Space&) {}
2558  forceinline void*
2559  NGL::operator new(size_t s, Space& home) {
2560  return home.ralloc(s);
2561  }
2562 
2563  /*
2564  * Shared objects and handles
2565  *
2566  */
2567  forceinline
2569  : next(NULL), fwd(NULL), use_cnt(0) {}
2570  forceinline
2572  assert(use_cnt == 0);
2573  }
2574 
2576  SharedHandle::object(void) const {
2577  return o;
2578  }
2579  forceinline void
2580  SharedHandle::subscribe(void) {
2581  if (o != NULL) o->use_cnt++;
2582  }
2583  forceinline void
2584  SharedHandle::cancel(void) {
2585  if ((o != NULL) && (--o->use_cnt == 0))
2586  delete o;
2587  o=NULL;
2588  }
2589  forceinline void
2591  if (n != o) {
2592  cancel(); o=n; subscribe();
2593  }
2594  }
2595  forceinline
2596  SharedHandle::SharedHandle(void) : o(NULL) {}
2597  forceinline
2599  subscribe();
2600  }
2601  forceinline
2603  subscribe();
2604  }
2607  if (&sh != this) {
2608  cancel(); o=sh.o; subscribe();
2609  }
2610  return *this;
2611  }
2612  forceinline void
2613  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
2614  if (sh.o == NULL) {
2615  o=NULL; return;
2616  } else if (share) {
2617  o=sh.o;
2618  } else if (sh.o->fwd != NULL) {
2619  o=sh.o->fwd;
2620  } else {
2621  o = sh.o->copy();
2622  sh.o->fwd = o;
2623  sh.o->next = home.pc.c.shared;
2624  home.pc.c.shared = sh.o;
2625  }
2626  subscribe();
2627  }
2628  forceinline
2630  cancel();
2631  }
2632 
2633 
2634 
2635  /*
2636  * No-goods
2637  *
2638  */
2639  forceinline
2641  : n(0) {}
2642  forceinline unsigned long int
2643  NoGoods::ng(void) const {
2644  return n;
2645  }
2646  forceinline void
2647  NoGoods::ng(unsigned long int n0) {
2648  n=n0;
2649  }
2650  forceinline
2652 
2653 
2654  /*
2655  * ActorLink
2656  *
2657  */
2659  ActorLink::prev(void) const {
2660  return _prev;
2661  }
2662 
2664  ActorLink::next(void) const {
2665  return _next;
2666  }
2667 
2670  return &_next;
2671  }
2672 
2673  forceinline void
2675  _prev = al;
2676  }
2677 
2678  forceinline void
2680  _next = al;
2681  }
2682 
2683  forceinline void
2685  ActorLink* p = _prev; ActorLink* n = _next;
2686  p->_next = n; n->_prev = p;
2687  }
2688 
2689  forceinline void
2691  _next = this; _prev =this;
2692  }
2693 
2694  forceinline void
2696  // Inserts al at head of link-chain (that is, after this)
2697  ActorLink* n = _next;
2698  this->_next = a; a->_prev = this;
2699  a->_next = n; n->_prev = a;
2700  }
2701 
2702  forceinline void
2704  // Inserts al at tail of link-chain (that is, before this)
2705  ActorLink* p = _prev;
2706  a->_next = this; this->_prev = a;
2707  p->_next = a; a->_prev = p;
2708  }
2709 
2710  forceinline bool
2711  ActorLink::empty(void) const {
2712  return _next == this;
2713  }
2714 
2715  template<class T>
2718  // Turning al into a reference is for gcc, assume is for MSVC
2719  GECODE_NOT_NULL(a);
2720  ActorLink& t = *a;
2721  return static_cast<ActorLink*>(&t);
2722  }
2723 
2724  template<class T>
2725  forceinline const ActorLink*
2726  ActorLink::cast(const T* a) {
2727  // Turning al into a reference is for gcc, assume is for MSVC
2728  GECODE_NOT_NULL(a);
2729  const ActorLink& t = *a;
2730  return static_cast<const ActorLink*>(&t);
2731  }
2732 
2733 
2734  /*
2735  * Actor
2736  *
2737  */
2739  Actor::cast(ActorLink* al) {
2740  // Turning al into a reference is for gcc, assume is for MSVC
2741  GECODE_NOT_NULL(al);
2742  ActorLink& t = *al;
2743  return static_cast<Actor*>(&t);
2744  }
2745 
2746  forceinline const Actor*
2747  Actor::cast(const ActorLink* al) {
2748  // Turning al into a reference is for gcc, assume is for MSVC
2749  GECODE_NOT_NULL(al);
2750  const ActorLink& t = *al;
2751  return static_cast<const Actor*>(&t);
2752  }
2753 
2754  forceinline void
2755  Space::afc_enable(void) {
2756  _wmp_afc |= 1U;
2757  }
2758  forceinline bool
2759  Space::afc_enabled(void) const {
2760  return (_wmp_afc & 1U) != 0U;
2761  }
2762  forceinline void
2763  Space::wmp(unsigned int n) {
2764  _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2765  }
2766  forceinline unsigned int
2767  Space::wmp(void) const {
2768  return _wmp_afc >> 1U;
2769  }
2770 
2771  forceinline void
2772  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
2773  s.notice(a,p,duplicate);
2774  }
2775 
2777  Space::clone(bool share, CloneStatistics&) const {
2778  // Clone is only const for search engines. During cloning, several data
2779  // structures are updated (e.g. forwarding pointers), so we have to
2780  // cast away the constness.
2781  return const_cast<Space*>(this)->_clone(share);
2782  }
2783 
2784  forceinline void
2785  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
2786  _commit(c,a);
2787  }
2788 
2789  forceinline void
2790  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
2791  _trycommit(c,a);
2792  }
2793 
2794  forceinline double
2795  Space::afc_decay(void) const {
2796  return gafc.decay();
2797  }
2798 
2799  forceinline size_t
2801  return sizeof(*this);
2802  }
2803 
2804 
2805  /*
2806  * Home for posting actors
2807  *
2808  */
2809  forceinline
2810  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
2811  forceinline Home&
2813  s=h.s; p=h.p;
2814  return *this;
2815  }
2816  forceinline
2817  Home::operator Space&(void) {
2818  return s;
2819  }
2822  return Home(s,&p);
2823  }
2826  return Home(*this,&p);
2827  }
2829  Home::propagator(void) const {
2830  return p;
2831  }
2832 
2833  /*
2834  * Propagator
2835  *
2836  */
2838  Propagator::cast(ActorLink* al) {
2839  // Turning al into a reference is for gcc, assume is for MSVC
2840  GECODE_NOT_NULL(al);
2841  ActorLink& t = *al;
2842  return static_cast<Propagator*>(&t);
2843  }
2844 
2845  forceinline const Propagator*
2846  Propagator::cast(const ActorLink* al) {
2847  // Turning al into a reference is for gcc, assume is for MSVC
2848  GECODE_NOT_NULL(al);
2849  const ActorLink& t = *al;
2850  return static_cast<const Propagator*>(&t);
2851  }
2852 
2853  forceinline Propagator*
2854  Propagator::fwd(void) const {
2855  return static_cast<Propagator*>(prev());
2856  }
2857 
2858  forceinline
2860  : gafc((home.propagator() != NULL) ?
2861  // Inherit time counter information
2862  home.propagator()->gafc :
2863  // New propagator information
2864  static_cast<Space&>(home).gafc.allocate()) {
2865  u.advisors = NULL;
2866  assert((u.med == 0) && (u.size == 0));
2867  static_cast<Space&>(home).pl.head(this);
2868  }
2869 
2870  forceinline
2872  : gafc(p.gafc) {
2873  u.advisors = NULL;
2874  assert((u.med == 0) && (u.size == 0));
2875  // Set forwarding pointer
2876  p.prev(this);
2877  }
2878 
2881  return u.med;
2882  }
2883 
2884  forceinline double
2885  Propagator::afc(const Space& home) const {
2886  return const_cast<Space&>(home).gafc.afc(gafc);
2887  }
2888 
2891  p.u.size = s;
2892  return __ES_SUBSUMED;
2893  }
2894 
2897  p.u.size = p.dispose(*this);
2898  return __ES_SUBSUMED;
2899  }
2900 
2903  p.u.med = med;
2904  assert(p.u.med != 0);
2905  return __ES_PARTIAL;
2906  }
2907 
2910  p.u.med = AllVarConf::med_combine(p.u.med,med);
2911  assert(p.u.med != 0);
2912  return __ES_PARTIAL;
2913  }
2914 
2915 
2916 
2917  /*
2918  * Brancher
2919  *
2920  */
2922  Brancher::cast(ActorLink* al) {
2923  // Turning al into a reference is for gcc, assume is for MSVC
2924  GECODE_NOT_NULL(al);
2925  ActorLink& t = *al;
2926  return static_cast<Brancher*>(&t);
2927  }
2928 
2929  forceinline const Brancher*
2930  Brancher::cast(const ActorLink* al) {
2931  // Turning al into a reference is for gcc, assume is for MSVC
2932  GECODE_NOT_NULL(al);
2933  const ActorLink& t = *al;
2934  return static_cast<const Brancher*>(&t);
2935  }
2936 
2937  forceinline
2939  _id(static_cast<Space&>(home).pc.p.branch_id++) {
2940  if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2941  throw TooManyBranchers("Brancher::Brancher");
2942  // If no brancher available, make it the first one
2943  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2944  static_cast<Space&>(home).b_status = this;
2945  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
2946  static_cast<Space&>(home).b_commit = this;
2947  }
2948  static_cast<Space&>(home).bl.tail(this);
2949  }
2950 
2951  forceinline
2953  : _id(b._id) {
2954  // Set forwarding pointer
2955  b.prev(this);
2956  }
2957 
2958  forceinline unsigned int
2959  Brancher::id(void) const {
2960  return _id;
2961  }
2962 
2964  Space::brancher(unsigned int id) {
2965  /*
2966  * Due to weakly monotonic propagators the following scenario might
2967  * occur: a brancher has been committed with all its available
2968  * choices. Then, propagation determines less information
2969  * than before and the brancher now will create new choices.
2970  * Later, during recomputation, all of these choices
2971  * can be used together, possibly interleaved with
2972  * choices for other branchers. That means all branchers
2973  * must be scanned to find the matching brancher for the choice.
2974  *
2975  * b_commit tries to optimize scanning as it is most likely that
2976  * recomputation does not generate new choices during recomputation
2977  * and hence b_commit is moved from newer to older branchers.
2978  */
2979  Brancher* b_old = b_commit;
2980  // Try whether we are lucky
2981  while (b_commit != Brancher::cast(&bl))
2982  if (id != b_commit->id())
2983  b_commit = Brancher::cast(b_commit->next());
2984  else
2985  return b_commit;
2986  if (b_commit == Brancher::cast(&bl)) {
2987  // We did not find the brancher, start at the beginning
2988  b_commit = Brancher::cast(bl.next());
2989  while (b_commit != b_old)
2990  if (id != b_commit->id())
2991  b_commit = Brancher::cast(b_commit->next());
2992  else
2993  return b_commit;
2994  }
2995  return NULL;
2996  }
2997 
2998  /*
2999  * Brancher handle
3000  *
3001  */
3002  forceinline
3004  : _id(Space::reserved_branch_id) {}
3005  forceinline
3007  : _id(b.id()) {}
3008  forceinline void
3010  _id = bh._id;
3011  }
3012  forceinline unsigned int
3013  BrancherHandle::id(void) const {
3014  return _id;
3015  }
3016  forceinline bool
3017  BrancherHandle::operator ()(const Space& home) const {
3018  return const_cast<Space&>(home).brancher(_id) != NULL;
3019  }
3020  forceinline void
3022  home.kill_brancher(_id);
3023  }
3024 
3025 
3026  /*
3027  * Local objects
3028  *
3029  */
3030 
3033  // Turning al into a reference is for gcc, assume is for MSVC
3034  GECODE_NOT_NULL(al);
3035  ActorLink& t = *al;
3036  return static_cast<LocalObject*>(&t);
3037  }
3038 
3039  forceinline const LocalObject*
3041  // Turning al into a reference is for gcc, assume is for MSVC
3042  GECODE_NOT_NULL(al);
3043  const ActorLink& t = *al;
3044  return static_cast<const LocalObject*>(&t);
3045  }
3046 
3047  forceinline
3049  ActorLink::cast(this)->prev(NULL);
3050  }
3051 
3052  forceinline
3054  ActorLink::cast(this)->prev(NULL);
3055  }
3056 
3058  LocalObject::fwd(Space& home, bool share) {
3059  if (prev() == NULL)
3060  fwdcopy(home,share);
3061  return LocalObject::cast(prev());
3062  }
3063 
3064  forceinline
3065  LocalHandle::LocalHandle(void) : o(NULL) {}
3066  forceinline
3068  forceinline
3069  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3072  o = lh.o;
3073  return *this;
3074  }
3075  forceinline
3078  LocalHandle::object(void) const { return o; }
3079  forceinline void
3081  forceinline void
3082  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
3083  object(lh.object()->fwd(home,share));
3084  }
3085 
3086 
3087  /*
3088  * Choices
3089  *
3090  */
3091  forceinline
3092  Choice::Choice(const Brancher& b, const unsigned int a)
3093  : _id(b.id()), _alt(a) {}
3094 
3095  forceinline unsigned int
3096  Choice::alternatives(void) const {
3097  return _alt;
3098  }
3099 
3100  forceinline unsigned int
3101  Choice::id(void) const {
3102  return _id;
3103  }
3104 
3105  forceinline
3107 
3108 
3109 
3110  /*
3111  * No-good literal
3112  *
3113  */
3114  forceinline bool
3115  NGL::leaf(void) const {
3116  return Support::marked(nl);
3117  }
3118  forceinline NGL*
3119  NGL::next(void) const {
3120  return static_cast<NGL*>(Support::funmark(nl));
3121  }
3122  forceinline void
3123  NGL::leaf(bool l) {
3124  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3125  }
3126  forceinline void
3128  nl = Support::marked(nl) ? Support::mark(n) : n;
3129  }
3130  forceinline NGL*
3131  NGL::add(NGL* n, bool l) {
3132  nl = Support::marked(nl) ? Support::mark(n) : n;
3133  n->leaf(l);
3134  return n;
3135  }
3136 
3137  forceinline
3138  NGL::NGL(void)
3139  : nl(NULL) {}
3140  forceinline
3142  : nl(NULL) {}
3143  forceinline
3144  NGL::NGL(Space&, bool, NGL&)
3145  : nl(NULL) {}
3146  forceinline size_t
3148  return sizeof(*this);
3149  }
3150 
3151  /*
3152  * Advisor
3153  *
3154  */
3155  template<class A>
3156  forceinline
3158  // Store propagator and forwarding in prev()
3159  ActorLink::prev(&p);
3160  // Link to next advisor in next()
3161  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3162  }
3163 
3164  forceinline
3166 
3167  forceinline bool
3168  Advisor::disposed(void) const {
3169  return prev() == NULL;
3170  }
3171 
3172  forceinline Advisor*
3173  Advisor::cast(ActorLink* al) {
3174  return static_cast<Advisor*>(al);
3175  }
3176 
3177  forceinline const Advisor*
3178  Advisor::cast(const ActorLink* al) {
3179  return static_cast<const Advisor*>(al);
3180  }
3181 
3182  forceinline Propagator&
3183  Advisor::propagator(void) const {
3184  assert(!disposed());
3185  return *Propagator::cast(ActorLink::prev());
3186  }
3187 
3188  template<class A>
3189  forceinline void
3191  assert(!disposed());
3192  ActorLink::prev(NULL);
3193  // Shorten chains of disposed advisors by one, if possible
3194  Advisor* n = Advisor::cast(next());
3195  if ((n != NULL) && n->disposed())
3196  next(n->next());
3197  }
3198 
3199  template<class A>
3202  a.dispose(*this,c);
3203  return ES_FIX;
3204  }
3205 
3206  template<class A>
3209  a.dispose(*this,c);
3210  return ES_NOFIX;
3211  }
3212 
3213  template<class A>
3216  a.dispose(*this,c);
3217  return ES_NOFIX_FORCE;
3218  }
3219 
3220 
3221 
3222  /*
3223  * Advisor council
3224  *
3225  */
3226  template<class A>
3227  forceinline
3229 
3230  template<class A>
3231  forceinline
3233  : advisors(NULL) {}
3234 
3235  template<class A>
3236  forceinline bool
3237  Council<A>::empty(void) const {
3238  ActorLink* a = advisors;
3239  while ((a != NULL) && static_cast<A*>(a)->disposed())
3240  a = a->next();
3241  advisors = a;
3242  return a == NULL;
3243  }
3244 
3245  template<class A>
3246  forceinline void
3247  Council<A>::update(Space& home, bool share, Council<A>& c) {
3248  // Skip all disposed advisors
3249  {
3250  ActorLink* a = c.advisors;
3251  while ((a != NULL) && static_cast<A*>(a)->disposed())
3252  a = a->next();
3253  c.advisors = a;
3254  }
3255  // Are there any advisors to be cloned?
3256  if (c.advisors != NULL) {
3257  // The propagator in from-space
3258  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3259  // The propagator in to-space
3260  Propagator* p_t = Propagator::cast(p_f->prev());
3261  // Advisors in from-space
3262  ActorLink** a_f = &c.advisors;
3263  // Advisors in to-space
3264  A* a_t = NULL;
3265  while (*a_f != NULL) {
3266  if (static_cast<A*>(*a_f)->disposed()) {
3267  *a_f = (*a_f)->next();
3268  } else {
3269  // Run specific copying part
3270  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
3271  // Set propagator pointer
3272  a->prev(p_t);
3273  // Set forwarding pointer
3274  (*a_f)->prev(a);
3275  // Link
3276  a->next(a_t);
3277  a_t = a;
3278  a_f = (*a_f)->next_ref();
3279  }
3280  }
3281  advisors = a_t;
3282  // Enter advisor link for reset
3283  assert(p_f->u.advisors == NULL);
3284  p_f->u.advisors = c.advisors;
3285  } else {
3286  advisors = NULL;
3287  }
3288  }
3289 
3290  template<class A>
3291  forceinline void
3293  ActorLink* a = advisors;
3294  while (a != NULL) {
3295  if (!static_cast<A*>(a)->disposed())
3296  static_cast<A*>(a)->dispose(home,*this);
3297  a = a->next();
3298  }
3299  }
3300 
3301 
3302 
3303  /*
3304  * Advisor iterator
3305  *
3306  */
3307  template<class A>
3308  forceinline
3310  : a(c.advisors) {
3311  while ((a != NULL) && static_cast<A*>(a)->disposed())
3312  a = a->next();
3313  }
3314 
3315  template<class A>
3316  forceinline bool
3318  return a != NULL;
3319  }
3320 
3321  template<class A>
3322  forceinline void
3324  do {
3325  a = a->next();
3326  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3327  }
3328 
3329  template<class A>
3330  forceinline A&
3331  Advisors<A>::advisor(void) const {
3332  return *static_cast<A*>(a);
3333  }
3334 
3335 
3336 
3337  /*
3338  * Space
3339  *
3340  */
3341  forceinline void
3342  Space::enqueue(Propagator* p) {
3343  ActorLink::cast(p)->unlink();
3344  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3345  c->tail(ActorLink::cast(p));
3346  if (c > pc.p.active)
3347  pc.p.active = c;
3348  }
3349 
3350  forceinline void
3351  Space::fail(void) {
3352  /*
3353  * Now active points beyond the last queue. This is essential as
3354  * enqueuing a propagator in a failed space keeps the space
3355  * failed.
3356  */
3357  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3358  }
3359  forceinline void
3360  Home::fail(void) {
3361  s.fail();
3362  }
3363 
3364  forceinline bool
3365  Space::failed(void) const {
3366  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3367  }
3368  forceinline bool
3369  Home::failed(void) const {
3370  return s.failed();
3371  }
3372 
3373  forceinline bool
3374  Space::stable(void) const {
3375  return ((pc.p.active < &pc.p.queue[0]) ||
3376  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3377  }
3378 
3379 
3380 
3381  /*
3382  * Variable implementation
3383  *
3384  */
3385  template<class VIC>
3388  assert((pc >= 0) && (pc < pc_max+2));
3389  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
3390  }
3391 
3392  template<class VIC>
3393  forceinline ActorLink**
3394  VarImp<VIC>::actorNonZero(PropCond pc) {
3395  assert((pc > 0) && (pc < pc_max+2));
3396  return b.base+u.idx[pc-1];
3397  }
3398 
3399  template<class VIC>
3400  forceinline unsigned int&
3402  assert((pc > 0) && (pc < pc_max+2));
3403  return u.idx[pc-1];
3404  }
3405 
3406  template<class VIC>
3407  forceinline unsigned int
3408  VarImp<VIC>::idx(PropCond pc) const {
3409  assert((pc > 0) && (pc < pc_max+2));
3410  return u.idx[pc-1];
3411  }
3412 
3413  template<class VIC>
3414  forceinline
3416  b.base = NULL; entries = 0;
3417  for (PropCond pc=1; pc<pc_max+2; pc++)
3418  idx(pc) = 0;
3419  free_and_bits = 0;
3420  }
3421 
3422  template<class VIC>
3423  forceinline
3425  b.base = NULL; entries = 0;
3426  for (PropCond pc=1; pc<pc_max+2; pc++)
3427  idx(pc) = 0;
3428  free_and_bits = 0;
3429  }
3430 
3431  template<class VIC>
3432  forceinline unsigned int
3433  VarImp<VIC>::degree(void) const {
3434  assert(!copied());
3435  return entries;
3436  }
3437 
3438  template<class VIC>
3439  forceinline double
3440  VarImp<VIC>::afc(const Space& home) const {
3441  double d = 0.0;
3442  // Count the afc of each propagator
3443  {
3444  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
3445  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3446  while (a < e) {
3447  d += Propagator::cast(*a)->afc(home); a++;
3448  }
3449  }
3450  // Count the afc of each advisor's propagator
3451  {
3452  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3453  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
3454  while (a < e) {
3455  d += Advisor::cast(*a)->propagator().afc(home); a++;
3456  }
3457  }
3458  return d;
3459  }
3460 
3461  template<class VIC>
3464  return d.me;
3465  }
3466 
3467  template<class VIC>
3468  forceinline unsigned int
3469  VarImp<VIC>::bits(void) const {
3470  return free_and_bits;
3471  }
3472 
3473  template<class VIC>
3474  forceinline unsigned int&
3476  return free_and_bits;
3477  }
3478 
3479 #ifdef GECODE_HAS_VAR_DISPOSE
3480  template<class VIC>
3482  VarImp<VIC>::vars_d(Space& home) {
3483  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
3484  }
3485 
3486  template<class VIC>
3487  forceinline void
3488  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3489  home.vars_d<VIC>(x);
3490  }
3491 #endif
3492 
3493  template<class VIC>
3494  forceinline bool
3495  VarImp<VIC>::copied(void) const {
3496  return Support::marked(b.fwd);
3497  }
3498 
3499  template<class VIC>
3501  VarImp<VIC>::forward(void) const {
3502  assert(copied());
3503  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
3504  }
3505 
3506  template<class VIC>
3508  VarImp<VIC>::next(void) const {
3509  assert(copied());
3510  return u.next;
3511  }
3512 
3513  template<class VIC>
3514  forceinline
3516  VarImpBase** reg;
3517  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3518  if (x.b.base == NULL) {
3519  // Variable implementation needs no index structure
3520  reg = &home.pc.c.vars_noidx;
3521  assert(x.degree() == 0);
3522  } else {
3523  reg = &home.pc.c.vars_u[idx_c];
3524  }
3525  // Save subscriptions in copy
3526  b.base = x.b.base;
3527  entries = x.entries;
3528  for (PropCond pc=1; pc<pc_max+2; pc++)
3529  idx(pc) = x.idx(pc);
3530 
3531  // Set forwarding pointer
3532  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
3533  // Register original
3534  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
3535  }
3536 
3537  template<class VIC>
3540  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3541  }
3542 
3543  template<class VIC>
3546  return static_cast<ModEventDelta>(me << VIC::med_fst);
3547  }
3548 
3549  template<class VIC>
3552  return VIC::me_combine(me1,me2);
3553  }
3554 
3555  template<class VIC>
3556  forceinline void
3558  bool force) {
3559  if (VIC::med_update(p.u.med,me) || force)
3560  home.enqueue(&p);
3561  }
3562 
3563  template<class VIC>
3564  forceinline void
3566  ActorLink** b = actor(pc1);
3567  ActorLink** p = actorNonZero(pc2+1);
3568  while (p-- > b)
3569  schedule(home,*Propagator::cast(*p),me);
3570  }
3571 
3572  template<class VIC>
3573  forceinline void
3574  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
3575  assert(pc <= pc_max);
3576  // Count one new subscription
3577  home.pc.p.n_sub += 1;
3578  if ((free_and_bits >> free_bits) == 0)
3579  resize(home);
3580  free_and_bits -= 1 << free_bits;
3581 
3582  // Enter subscription
3583  b.base[entries] = *actorNonZero(pc_max+1);
3584  entries++;
3585  for (PropCond j = pc_max; j > pc; j--) {
3586  *actorNonZero(j+1) = *actorNonZero(j);
3587  idx(j+1)++;
3588  }
3589  *actorNonZero(pc+1) = *actor(pc);
3590  idx(pc+1)++;
3591  *actor(pc) = ActorLink::cast(p);
3592 
3593 #ifdef GECODE_AUDIT
3594  ActorLink** f = actor(pc);
3595  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
3596  if (*f == p)
3597  goto found;
3598  else
3599  f++;
3600  GECODE_NEVER;
3601  found: ;
3602 #endif
3603  }
3604 
3605  template<class VIC>
3606  forceinline void
3607  VarImp<VIC>::enter(Space& home, Advisor* a) {
3608  // Count one new subscription
3609  home.pc.p.n_sub += 1;
3610  if ((free_and_bits >> free_bits) == 0)
3611  resize(home);
3612  free_and_bits -= 1 << free_bits;
3613 
3614  // Enter subscription
3615  b.base[entries++] = *actorNonZero(pc_max+1);
3616  *actorNonZero(pc_max+1) = a;
3617  }
3618 
3619  template<class VIC>
3620  void
3621  VarImp<VIC>::resize(Space& home) {
3622  if (b.base == NULL) {
3623  assert((free_and_bits >> free_bits) == 0);
3624  // Create fresh dependency array with four entries
3625  free_and_bits += 4 << free_bits;
3626  b.base = home.alloc<ActorLink*>(4);
3627  for (int i=0; i<pc_max+1; i++)
3628  u.idx[i] = 0;
3629  } else {
3630  // Resize dependency array
3631  unsigned int n = degree();
3632  // Find out whether the area is most likely in the special area
3633  // reserved for subscriptions. If yes, just resize mildly otherwise
3634  // more agressively
3635  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
3636  unsigned int m =
3637  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
3638  (n+4) : ((n+1)*3>>1);
3639  ActorLink** prop = home.alloc<ActorLink*>(m);
3640  free_and_bits += (m-n) << free_bits;
3641  // Copy entries
3642  Heap::copy<ActorLink*>(prop, b.base, n);
3643  home.free<ActorLink*>(b.base,n);
3644  b.base = prop;
3645  }
3646  }
3647 
3648  template<class VIC>
3649  void
3651  bool assigned, ModEvent me, bool schedule) {
3652  if (assigned) {
3653  // Do not subscribe, just schedule the propagator
3654  if (schedule)
3656  } else {
3657  enter(home,&p,pc);
3658  // Schedule propagator
3659  if (schedule && (pc != PC_GEN_ASSIGNED))
3660  VarImp<VIC>::schedule(home,p,me);
3661  }
3662  }
3663 
3664  template<class VIC>
3665  forceinline void
3667  if (!assigned)
3668  enter(home,&a);
3669  }
3670 
3671  template<class VIC>
3672  forceinline void
3673  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
3674  assert(pc <= pc_max);
3675  ActorLink* a = ActorLink::cast(p);
3676  // Find actor in dependency array
3677  ActorLink** f = actor(pc);
3678 #ifdef GECODE_AUDIT
3679  while (f < actorNonZero(pc+1))
3680  if (*f == a)
3681  goto found;
3682  else
3683  f++;
3684  GECODE_NEVER;
3685  found: ;
3686 #else
3687  while (*f != a) f++;
3688 #endif
3689  // Remove actor
3690  *f = *(actorNonZero(pc+1)-1);
3691  for (PropCond j = pc+1; j< pc_max+1; j++) {
3692  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3693  idx(j)--;
3694  }
3695  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
3696  idx(pc_max+1)--;
3697  entries--;
3698  free_and_bits += 1 << free_bits;
3699  home.pc.p.n_sub -= 1;
3700  }
3701 
3702  template<class VIC>
3703  forceinline void
3704  VarImp<VIC>::remove(Space& home, Advisor* a) {
3705  // Find actor in dependency array
3706  ActorLink** f = actorNonZero(pc_max+1);
3707 #ifdef GECODE_AUDIT
3708  while (f < b.base+entries)
3709  if (*f == a)
3710  goto found;
3711  else
3712  f++;
3713  GECODE_NEVER;
3714  found: ;
3715 #else
3716  while (*f != a) f++;
3717 #endif
3718  // Remove actor
3719  *f = b.base[--entries];
3720  free_and_bits += 1 << free_bits;
3721  home.pc.p.n_sub -= 1;
3722  }
3723 
3724  template<class VIC>
3725  forceinline void
3727  if (!assigned)
3728  remove(home,&p,pc);
3729  }
3730 
3731  template<class VIC>
3732  forceinline void
3734  if (!assigned)
3735  remove(home,&a);
3736  }
3737 
3738  template<class VIC>
3739  forceinline void
3741  unsigned int n_sub = degree();
3742  home.pc.p.n_sub -= n_sub;
3743  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3744  home.free<ActorLink*>(b.base,n);
3745  // Must be NULL such that cloning works
3746  b.base = NULL;
3747  // Must be 0 such that degree works
3748  entries = 0;
3749  }
3750 
3751  template<class VIC>
3752  forceinline bool
3754  /*
3755  * An advisor that is executed might remove itself due to subsumption.
3756  * As entries are removed from front to back, the advisors must
3757  * be iterated in forward direction.
3758  */
3759  ActorLink** la = actorNonZero(pc_max+1);
3760  ActorLink** le = b.base+entries;
3761  if (la == le)
3762  return true;
3763  d.me = me;
3764  // An advisor that is run, might be removed during execution.
3765  // As removal is done from the back the advisors have to be executed
3766  // in inverse order.
3767  do {
3768  Advisor* a = Advisor::cast(*la);
3769  assert(!a->disposed());
3770  Propagator& p = a->propagator();
3771  switch (p.advise(home,*a,d)) {
3772  case ES_FIX:
3773  break;
3774  case ES_FAILED:
3775  if (home.afc_enabled())
3776  home.gafc.fail(p.gafc);
3777  return false;
3778  case ES_NOFIX:
3779  schedule(home,p,me);
3780  break;
3781  case ES_NOFIX_FORCE:
3782  schedule(home,p,me,true);
3783  break;
3784  default:
3785  GECODE_NEVER;
3786  }
3787  } while (++la < le);
3788  return true;
3789  }
3790 
3791  template<class VIC>
3792  forceinline void
3794  // this refers to the variable to be updated (clone)
3795  // x refers to the original
3796  // Recover from copy
3797  x->b.base = b.base;
3798  x->u.idx[0] = u.idx[0];
3799  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
3800  x->u.idx[1] = u.idx[1];
3801 
3802  ActorLink** f = x->b.base;
3803  unsigned int n = x->degree();
3804  ActorLink** t = sub;
3805  sub += n;
3806  b.base = t;
3807  // Set subscriptions using actor forwarding pointers
3808  while (n >= 4) {
3809  n -= 4;
3810  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3811  t[2]=f[2]->prev(); t[3]=f[3]->prev();
3812  t += 4; f += 4;
3813  }
3814  if (n >= 2) {
3815  n -= 2;
3816  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3817  t += 2; f += 2;
3818  }
3819  if (n > 0) {
3820  t[0]=f[0]->prev();
3821  }
3822  }
3823 
3824  template<class VIC>
3825  forceinline void
3826  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3827  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
3828  while (x != NULL) {
3829  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
3830  }
3831  }
3832 
3833 
3834 
3835  /*
3836  * Variable disposer
3837  *
3838  */
3839  template<class VarImp>
3841 #ifdef GECODE_HAS_VAR_DISPOSE
3842  Space::vd[VarImp::idx_d] = this;
3843 #endif
3844  }
3845 
3846  template<class VarImp>
3847  void
3849  VarImp* x = static_cast<VarImp*>(_x);
3850  do {
3851  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
3852  } while (x != NULL);
3853  }
3854 
3855  /*
3856  * Statistics
3857  */
3858 
3859  forceinline void
3861  propagate = 0;
3862  wmp = false;
3863  }
3864  forceinline
3866  reset();
3867  }
3870  propagate += s.propagate;
3871  wmp |= s.wmp;
3872  return *this;
3873  }
3876  StatusStatistics t(s);
3877  return t += *this;
3878  }
3879 
3880  forceinline void
3882 
3883  forceinline
3885  reset();
3886  }
3889  CloneStatistics s;
3890  return s;
3891  }
3894  return *this;
3895  }
3896 
3897  forceinline void
3899 
3900  forceinline
3902  reset();
3903  }
3906  CommitStatistics s;
3907  return s;
3908  }
3911  return *this;
3912  }
3913 
3914  /*
3915  * Cost computation
3916  *
3917  */
3918 
3919  forceinline
3920  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
3921 
3922  forceinline PropCost
3923  PropCost::cost(PropCost::Mod m,
3925  unsigned int n) {
3926  if (n < 2)
3927  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3928  else if (n == 2)
3929  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3930  else if (n == 3)
3931  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3932  else
3933  return (m == LO) ? lo : hi;
3934  }
3935 
3936  forceinline PropCost
3937  PropCost::crazy(PropCost::Mod m, unsigned int n) {
3938  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
3939  }
3942  assert(n >= 0);
3943  return crazy(m,static_cast<unsigned int>(n));
3944  }
3946  PropCost::cubic(PropCost::Mod m, unsigned int n) {
3947  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
3948  }
3951  assert(n >= 0);
3952  return cubic(m,static_cast<unsigned int>(n));
3953  }
3955  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
3956  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
3957  }
3960  assert(n >= 0);
3961  return quadratic(m,static_cast<unsigned int>(n));
3962  }
3964  PropCost::linear(PropCost::Mod m, unsigned int n) {
3965  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
3966  }
3969  assert(n >= 0);
3970  return linear(m,static_cast<unsigned int>(n));
3971  }
3974  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3975  }
3978  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3979  }
3982  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3983  }
3984 
3985  /*
3986  * Iterators for propagators and branchers of a space
3987  *
3988  */
3989  forceinline
3991  : home(home0), q(home.pc.p.active) {
3992  while (q >= &home.pc.p.queue[0]) {
3993  if (q->next() != q) {
3994  c = q->next(); e = q; q--;
3995  return;
3996  }
3997  q--;
3998  }
3999  q = NULL;
4000  if (!home.pl.empty()) {
4001  c = Propagator::cast(home.pl.next());
4002  e = Propagator::cast(&home.pl);
4003  } else {
4004  c = e = NULL;
4005  }
4006  }
4007  forceinline bool
4009  return c != NULL;
4010  }
4011  forceinline void
4013  c = c->next();
4014  if (c == e) {
4015  if (q == NULL) {
4016  c = NULL;
4017  } else {
4018  while (q >= &home.pc.p.queue[0]) {
4019  if (q->next() != q) {
4020  c = q->next(); e = q; q--;
4021  return;
4022  }
4023  q--;
4024  }
4025  q = NULL;
4026  if (!home.pl.empty()) {
4027  c = Propagator::cast(home.pl.next());
4028  e = Propagator::cast(&home.pl);
4029  } else {
4030  c = NULL;
4031  }
4032  }
4033  }
4034  }
4035  forceinline const Propagator&
4037  return *Propagator::cast(c);
4038  }
4039 
4040  forceinline
4042  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4043  forceinline bool
4045  return c != e;
4046  }
4047  forceinline void
4049  c = c->next();
4050  }
4051  forceinline const Brancher&
4053  return *Brancher::cast(c);
4054  }
4055 
4056  /*
4057  * Space construction support
4058  *
4059  */
4060  template<class T>
4061  forceinline T&
4063  return alloc<T>(1);
4064  }
4065  template<class T, typename A1>
4066  forceinline T&
4067  Space::construct(A1 const& a1) {
4068  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4069  new (&t) T(a1);
4070  return t;
4071  }
4072  template<class T, typename A1, typename A2>
4073  forceinline T&
4074  Space::construct(A1 const& a1, A2 const& a2) {
4075  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4076  new (&t) T(a1,a2);
4077  return t;
4078  }
4079  template<class T, typename A1, typename A2, typename A3>
4080  forceinline T&
4081  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
4082  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4083  new (&t) T(a1,a2,a3);
4084  return t;
4085  }
4086  template<class T, typename A1, typename A2, typename A3, typename A4>
4087  forceinline T&
4088  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
4089  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4090  new (&t) T(a1,a2,a3,a4);
4091  return t;
4092  }
4093  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
4094  forceinline T&
4095  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
4096  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4097  new (&t) T(a1,a2,a3,a4,a5);
4098  return t;
4099  }
4100 
4101 }
4102 
4103 // STATISTICS: kernel-core
static const int med_lst
End of bits for modification event delta.
Definition: core.hpp:195
virtual Object * copy(void) const =0
Return fresh copy for update.
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3369
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:2643
void reset(void)
Reset information.
Definition: core.hpp:3881
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:4044
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:158
bool marked(void *p)
Check whether p is marked.
Linear complexity, cheap.
Definition: core.hpp:549
Council of advisors
Definition: core.hpp:226
SharedHandle(void)
Create shared handle with no object pointing to.
Definition: core.hpp:2596
Base-class for variable implementations.
Definition: core.hpp:228
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Space must be branched (at least one brancher left)
Definition: core.hpp:1266
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:3955
The shared handle.
Definition: core.hpp:79
Propagators(const Space &home)
Initialize.
Definition: core.hpp:3990
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Only single variable, cheap.
Definition: core.hpp:554
unsigned int branch_id
Id of next brancher to be created.
Definition: core.hpp:1392
Exponential complexity, cheap.
Definition: core.hpp:542
Cubic complexity, expensive.
Definition: core.hpp:545
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
LocalObject(Home home)
Constructor for creation.
Definition: core.hpp:3048
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4036
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:3964
VarImp(void)
Creation of static instances.
Definition: core.hpp:3424
Exponential complexity, expensive.
Definition: core.hpp:543
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2896
void update(Space &home, bool share, Council< A > &c)
Update during cloning (copies all advisors)
Definition: core.hpp:3247
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:3840
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:341
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3119
union Gecode::@512::NNF::@54 u
Union depending on nodetype t.
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
Actor must always be disposed.
Definition: core.hpp:610
double afc(const Space &home) const
Return accumulated failure count (plus degree)
Definition: core.hpp:3440
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:768
NGL(void)
Constructor for creation.
Definition: core.hpp:3138
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:84
static const int free_bits
Freely available bits.
Definition: core.hpp:191
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2777
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:2795
SpaceStatus
Space status
Definition: core.hpp:1263
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2909
Handle for brancher.
Definition: core.hpp:1157
Manage memory for space.
Branchers(const Space &home)
Initialize.
Definition: core.hpp:4041
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:2405
friend class ActorLink
Definition: core.hpp:667
Statistics for execution of commit
Definition: core.hpp:1309
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:153
AFC afc
Definition: afc.cpp:139
Local (space-shared) object.
Definition: core.hpp:1183
friend class ActorLink
Definition: core.hpp:1072
Status
The status of a no-good literal.
Definition: core.hpp:977
A & advisor(void) const
Return advisor.
Definition: core.hpp:3331
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:3557
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:3463
Base-class for propagators.
Definition: core.hpp:755
Internal: propagator is subsumed, do not use.
Definition: core.hpp:524
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3106
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
T & construct(void)
Construction routines.
Definition: core.hpp:4062
Base-class for advisors.
Definition: core.hpp:926
static const int idx_d
Index for disposal.
Definition: core.hpp:187
bool wmp
Whether a weakly monotonic propagator might have been executed.
Definition: core.hpp:1278
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:3545
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3078
ActorLink ** base
Subscribed actors.
Definition: core.hpp:303
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3208
Three variables, expensive.
Definition: core.hpp:550
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:339
Class to iterate over advisors of a council.
Definition: core.hpp:227
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3096
Handle to region.
Definition: region.hpp:61
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
void * mark(void *p)
Return marked pointer for p.
Base-class for variable implementations.
Definition: core.hpp:243
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1405
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1276
Linear complexity, expensive.
Definition: core.hpp:548
Propagation has computed fixpoint.
Definition: core.hpp:528
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:3981
Computation spaces.
Definition: core.hpp:1325
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:245
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3071
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3365
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:2324
Base-class for both propagators and branchers.
Definition: core.hpp:666
Statistics for execution of status
Definition: core.hpp:1273
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:3740
Heap heap
The single global heap.
Definition: heap.cpp:49
void fail(Counter &c)
Increment failure count.
Definition: global-afc.hpp:317
Gecode::IntSet d(v, 7)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2354
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3013
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:3888
Only single variable, expensive.
Definition: core.hpp:555
bool operator()(const Space &home) const
Check whether brancher is still active.
Definition: core.hpp:3017
The literal is subsumed.
Definition: core.hpp:979
Gecode::FloatVal c(-8, 8)
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4008
Maximal cost value.
Definition: core.hpp:556
Configuration class for variable implementations without index structure.
Definition: core.hpp:182
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Handles for local (space-shared) objects.
Definition: core.hpp:1210
Class to iterate over branchers of a space.
Definition: core.hpp:2247
double afc(const Space &home) const
Return the accumlated failure count.
Definition: core.hpp:2885
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1071
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
bool copied(void) const
Is variable already copied.
Definition: core.hpp:3495
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:2854
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:3893
void reset(void)
Reset information.
Definition: core.hpp:3898
void reset(void)
Reset information.
Definition: core.hpp:3860
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:3539
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3032
Execution has resulted in failure.
Definition: core.hpp:525
StatusStatistics(void)
Initialize.
Definition: core.hpp:3865
Statistics for execution of clone
Definition: core.hpp:1293
Two variables, expensive.
Definition: core.hpp:551
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:2651
SharedHandle & operator=(const SharedHandle &sh)
Assignment operator maintaining reference count.
Definition: core.hpp:2606
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:2785
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1394
void fail(void)
Fail space.
Definition: core.hpp:3351
static const int idx_c
Index for update.
Definition: core.hpp:185
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:205
friend class ActorLink
Definition: core.hpp:756
static const int med_mask
Bitmask for modification event delta.
Definition: core.hpp:197
unsigned int size(I &i)
Size of all ranges of range iterator i.
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:2890
CloneStatistics(void)
Initialize.
Definition: core.hpp:3884
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3065
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:160
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3374
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:3848
Three variables, cheap.
Definition: core.hpp:552
Propagator & propagator(void) const
Return the advisor's propagator.
Definition: core.hpp:3183
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:766
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:3317
Expensive.
Definition: core.hpp:564
Council(void)
Default constructor.
Definition: core.hpp:3228
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
Definition: core.hpp:3058
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3201
void * alloc(SharedMemory *sm, size_t s)
Allocate memory of size s.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
struct Gecode::@512::NNF::@54::@55 b
For binary nodes (and, or, eqv)
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:2812
Class for storing timed-decay value.
Definition: global-afc.hpp:46
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:2880
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3092
Exception: too many branchers
Definition: exception.hpp:83
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2902
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2772
Mod
Propagation cost modifier.
Definition: core.hpp:562
Single _b(1, 4)
~SharedHandle(void)
Destructor that maintains reference count.
Definition: core.hpp:2629
Quadratic complexity, cheap.
Definition: core.hpp:546
void update(Space &home, bool share, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3082
Advisor forces rescheduling of propagator.
Definition: core.hpp:529
NoGoods(void)
Initialize.
Definition: core.hpp:2640
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2380
Class to iterate over propagators of a space.
Definition: core.hpp:2221
Globally shared object for propagator information.
Definition: global-afc.hpp:43
BrancherHandle bh
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2613
void update(Space &home, bool share, BrancherHandle &bh)
Update during cloning.
Definition: core.hpp:3009
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
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:3433
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2316
bool empty(void) const
Test whether council has advisor left.
Definition: core.hpp:3237
ActualCost ac
Actual cost.
Definition: core.hpp:559
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:2821
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:3946
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:3905
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
Brancher(Home home)
Constructor for creation.
Definition: core.hpp:2938
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:2825
virtual ~Object(void)
Delete shared object.
Definition: core.hpp:2571
VarImp * next(void) const
Return next copied variable.
Choice for performing commit
Definition: core.hpp:1036
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.cpp:135
The literal is failed.
Definition: core.hpp:978
No-goods recorded from restarts.
Definition: core.hpp:1240
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:2576
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2800
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3190
Propagation cost.
Definition: core.hpp:537
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:3323
Archive representation
Definition: archive.hpp:45
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2440
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition: core.hpp:3157
ExecStatus
Definition: core.hpp:523
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition: var-type.hpp:889
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition: core.hpp:3910
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4012
#define forceinline
Definition: config.hpp:129
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4052
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:3937
SharedHandle::Object * shared
Linked list of shared objects.
Definition: core.hpp:1403
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:720
static const PropCond pc_max
Maximal propagation condition.
Definition: core.hpp:189
struct Gecode::Space::@49::@51 c
Data available only during copying.
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:4048
Base-class for freelist-managed objects.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:2790
Advisors(const Council< A > &c)
Initialize.
Definition: core.hpp:3309
Two variables, cheap.
Definition: core.hpp:553
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:530
Variable implementation disposer
Definition: core.hpp:266
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2344
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:151
The shared object.
Definition: core.hpp:88
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:312
Execution is okay.
Definition: core.hpp:527
Quadratic complexity, expensive.
Definition: core.hpp:547
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3147
Propagation has not computed fixpoint.
Definition: core.hpp:526
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:722
void fail(void)
Mark space as failed.
Definition: core.hpp:3360
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3131
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:3469
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:2829
struct Gecode::Space::@49::@50 p
Data only available during propagation.
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:3875
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:79
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:3973
unsigned int id(void) const
Return unsigned brancher id.
Definition: core.hpp:2959
Propagator(Home home)
Constructor for posting.
Definition: core.hpp:2859
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:3551
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3115
BrancherHandle(void)
Create handle as unitialized.
Definition: core.hpp:3003
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1388
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1401
ActorProperty
Actor properties.
Definition: core.hpp:601
struct Gecode::@512::NNF::@54::@56 a
For atomic nodes.
Space is failed
Definition: core.hpp:1264
ActualCost
The actual cost values that are used.
Definition: core.hpp:541
unsigned long int n
Number of no-goods.
Definition: core.hpp:1243
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2339
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
Home class for posting propagators
Definition: core.hpp:717
void dispose(Space &home)
Dispose council.
Definition: core.hpp:3292
static const int med_fst
Start of bits for modification event delta.
Definition: core.hpp:193
void kill(Space &home)
Kill the brancher.
Definition: core.hpp:3021
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:3977
Shared object for several memory areas.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Cubic complexity, cheap.
Definition: core.hpp:544
Object(void)
Initialize.
Definition: core.hpp:2568
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:209
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:3869
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:3753
CommitStatistics(void)
Initialize.
Definition: core.hpp:3901
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:3501
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:149
Base class for Variable type disposer.
Definition: core.hpp:251
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:3215
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:93
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2320
Home(Space &s, Propagator *p=NULL)
Initialize the home with space s and propagator p.
Definition: core.hpp:2810
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:3650
void decay(double d)
Set decay factor to d.
Definition: global-afc.hpp:353
Space is solved (no brancher left)
Definition: core.hpp:1265
No-good literal recorded during search.
Definition: core.hpp:971
~LocalHandle(void)
Destructor.
Definition: core.hpp:3076