Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
core.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 * Mikael Lagerkvist <lagerkvist@gecode.org>
7 *
8 * Contributing authors:
9 * Filip Konvicka <filip.konvicka@logis.cz>
10 * Samuel Gagnon <samuel.gagnon92@gmail.com>
11 *
12 * Copyright:
13 * Christian Schulte, 2002
14 * Guido Tack, 2003
15 * Mikael Lagerkvist, 2006
16 * LOGIS, s.r.o., 2009
17 * Samuel Gagnon, 2018
18 *
19 * Bugfixes provided by:
20 * Alexander Samoilov <alexander_samoilov@yahoo.com>
21 *
22 * This file is part of Gecode, the generic constraint
23 * development environment:
24 * http://www.gecode.org
25 *
26 * Permission is hereby granted, free of charge, to any person obtaining
27 * a copy of this software and associated documentation files (the
28 * "Software"), to deal in the Software without restriction, including
29 * without limitation the rights to use, copy, modify, merge, publish,
30 * distribute, sublicense, and/or sell copies of the Software, and to
31 * permit persons to whom the Software is furnished to do so, subject to
32 * the following conditions:
33 *
34 * The above copyright notice and this permission notice shall be
35 * included in all copies or substantial portions of the Software.
36 *
37 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
38 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
39 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
40 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
41 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
42 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
43 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44 *
45 */
46
47#include <iostream>
48
49namespace Gecode {
50
51 class Space;
52
61
62 typedef int ModEvent;
63
70
72 typedef int PropCond;
78
89 typedef int ModEventDelta;
90
91}
92
94
95namespace Gecode {
96
99 public:
101 static const int idx_c = -1;
103 static const int idx_d = -1;
107 static const int free_bits = 0;
109 static const int med_fst = 0;
111 static const int med_lst = 0;
113 static const int med_mask = 0;
117 static bool med_update(ModEventDelta& med, ModEvent me);
118 };
119
124 forceinline bool
128
129
130 /*
131 * These are the classes of interest
132 *
133 */
134 class ActorLink;
135 class Actor;
136 class Propagator;
138 class LocalObject;
139 class Advisor;
140 class AFC;
141 class Choice;
142 class Brancher;
143 class Group;
144 class PropagatorGroup;
145 class BrancherGroup;
146 class PostInfo;
147 class ViewTraceInfo;
148 class PropagateTraceInfo;
149 class CommitTraceInfo;
150 class PostTraceInfo;
151 class TraceRecorder;
152 class TraceFilter;
153 class Tracer;
154
155 template<class A> class Council;
156 template<class A> class Advisors;
157 template<class VIC> class VarImp;
158
159
160 /*
161 * Variable implementations
162 *
163 */
164
172 class VarImpBase {};
173
181 public:
183 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
186 };
187
194 template<class VarImp>
196 public:
198 VarImpDisposer(void);
200 virtual void dispose(Space& home, VarImpBase* x);
201 };
202
204 class Delta {
205 template<class VIC> friend class VarImp;
206 private:
208 ModEvent me;
209 };
210
218 template<class VIC>
219 class VarImp : public VarImpBase {
220 friend class Space;
221 friend class Propagator;
222 template<class VarImp> friend class VarImpDisposer;
224 private:
225 union {
243 } b;
244
246 static const int idx_c = VIC::idx_c;
248 static const int idx_d = VIC::idx_d;
250 static const int free_bits = VIC::free_bits;
252 unsigned int entries;
254 unsigned int free_and_bits;
256 static const Gecode::PropCond pc_max = VIC::pc_max;
257#ifdef GECODE_HAS_CBS
259 const unsigned var_id;
260#endif
261
262 union {
273 unsigned int idx[pc_max+1];
276 } u;
277
279 ActorLink** actor(PropCond pc);
281 ActorLink** actorNonZero(PropCond pc);
283 unsigned int& idx(PropCond pc);
285 unsigned int idx(PropCond pc) const;
286
293 void update(VarImp* x, ActorLink**& sub);
300 static void update(Space& home, ActorLink**& sub);
301
303 void enter(Space& home, Propagator* p, PropCond pc);
305 void enter(Space& home, Advisor* a);
307 void resize(Space& home);
309 void remove(Space& home, Propagator* p, PropCond pc);
311 void remove(Space& home, Advisor* a);
312
313
314 protected:
316 void cancel(Space& home);
322 bool advise(Space& home, ModEvent me, Delta& d);
323 private:
325 void _fail(Space& home);
326 protected:
329#ifdef GECODE_HAS_VAR_DISPOSE
331 static VarImp<VIC>* vars_d(Space& home);
333 static void vars_d(Space& home, VarImp<VIC>* x);
334#endif
335
336 public:
338 VarImp(Space& home);
340 VarImp(void);
341
342#ifdef GECODE_HAS_CBS
344 unsigned int id(void) const;
345#endif
346
348
349
361 void subscribe(Space& home, Propagator& p, PropCond pc,
362 bool assigned, ModEvent me, bool schedule);
364 void cancel(Space& home, Propagator& p, PropCond pc);
373 void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
375 void cancel(Space& home, Advisor& a, bool fail);
376
383 unsigned int degree(void) const;
390 double afc(void) const;
392
394
395
396 VarImp(Space& home, VarImp& x);
398 bool copied(void) const;
400 VarImp* forward(void) const;
402 VarImp* next(void) const;
404
406
407
414 static void schedule(Space& home, Propagator& p, ModEvent me,
415 bool force = false);
423 static void reschedule(Space& home, Propagator& p, PropCond pc,
424 bool assigned, ModEvent me);
426 static ModEvent me(const ModEventDelta& med);
432
434
435
436 static ModEvent modevent(const Delta& d);
438
440
441
442 unsigned int bits(void) const;
444 unsigned int& bits(void);
446
447 protected:
449 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
450
451 public:
453
454
455 static void* operator new(size_t,Space&);
457 static void operator delete(void*,Space&);
459 static void operator delete(void*);
461 };
462
463
481
486 class PropCost {
487 friend class Space;
488 public:
508
510 public:
512 enum Mod {
515 };
516 private:
518 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
521 public:
523 static PropCost record(void);
525 static PropCost crazy(PropCost::Mod m, unsigned int n);
527 static PropCost crazy(PropCost::Mod m, int n);
529 static PropCost cubic(PropCost::Mod m, unsigned int n);
531 static PropCost cubic(PropCost::Mod m, int n);
533 static PropCost quadratic(PropCost::Mod m, unsigned int n);
535 static PropCost quadratic(PropCost::Mod m, int n);
537 static PropCost linear(PropCost::Mod m, unsigned int n);
539 static PropCost linear(PropCost::Mod m, int n);
543 static PropCost binary(PropCost::Mod m);
545 static PropCost unary(PropCost::Mod m);
546 };
547
548
562 AP_DISPOSE = (1 << 0),
568 AP_WEAKLY = (1 << 1),
573 AP_VIEW_TRACE = (1 << 2),
578 AP_TRACE = (1 << 3)
579 };
580
581
589 class ActorLink {
590 friend class Actor;
591 friend class Propagator;
592 friend class Advisor;
593 friend class Brancher;
594 friend class LocalObject;
595 friend class Space;
596 template<class VIC> friend class VarImp;
597 private:
598 ActorLink* _next; ActorLink* _prev;
599 public:
601
602 ActorLink* prev(void) const; void prev(ActorLink*);
603 ActorLink* next(void) const; void next(ActorLink*);
604 ActorLink** next_ref(void);
606
608 void init(void);
610 void unlink(void);
612 void head(ActorLink* al);
614 void tail(ActorLink* al);
616 bool empty(void) const;
618 template<class T> static ActorLink* cast(T* a);
620 template<class T> static const ActorLink* cast(const T* a);
621 };
622
623
629 friend class ActorLink;
630 friend class Space;
631 friend class Propagator;
632 friend class Advisor;
633 friend class Brancher;
634 friend class LocalObject;
635 template<class VIC> friend class VarImp;
636 template<class A> friend class Council;
637 private:
639 static Actor* cast(ActorLink* al);
641 static const Actor* cast(const ActorLink* al);
643 GECODE_KERNEL_EXPORT static Actor* sentinel;
644 public:
646 virtual Actor* copy(Space& home) = 0;
647
649
650
652 virtual size_t dispose(Space& home);
654 static void* operator new(size_t s, Space& home);
656 static void operator delete(void* p, Space& home);
658 public:
660 GECODE_KERNEL_EXPORT virtual ~Actor(void);
662 static void* operator new(size_t s);
664 static void operator delete(void* p);
665 };
666
667 class Home;
668
673 class Group {
674 friend class Home;
675 friend class Propagator;
676 friend class Brancher;
677 friend class ViewTraceInfo;
678 friend class PropagateTraceInfo;
679 friend class CommitTraceInfo;
680 friend class PostTraceInfo;
681 protected:
683 static const unsigned int GROUPID_ALL = 0U;
685 static const unsigned int GROUPID_DEF = 1U;
687 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
689 unsigned int gid;
692 static unsigned int next;
697 Group(unsigned int gid0);
698 public:
700
701
703 Group(void);
705 Group(const Group& g);
707 Group& operator =(const Group& g);
709 unsigned int id(void) const;
711 bool in(Group a) const;
713 bool in(void) const;
715
717 static Group all;
720 static Group def;
721 };
722
727 class PropagatorGroup : public Group {
728 friend class Propagator;
729 friend class ViewTraceInfo;
730 friend class PropagateTraceInfo;
731 friend class PostTraceInfo;
732 protected:
734 PropagatorGroup(unsigned int gid);
735 public:
737
738
739 PropagatorGroup(void);
745 Home operator ()(Space& home);
747
749
761 PropagatorGroup& move(Space& home, unsigned int id);
763
765
766 bool operator ==(PropagatorGroup g) const;
768 bool operator !=(PropagatorGroup g) const;
771 unsigned int size(Space& home) const;
774 void kill(Space& home);
777 void disable(Space& home);
785 void enable(Space& home, bool s=true);
787
793 };
794
799 class BrancherGroup : public Group {
800 friend class Brancher;
801 protected:
803 BrancherGroup(unsigned int gid);
804 public:
806
807
808 BrancherGroup(void);
814 Home operator ()(Space& home);
816
818
822 BrancherGroup& move(Space& home, Brancher& b);
830 BrancherGroup& move(Space& home, unsigned int id);
832
834
835 bool operator ==(BrancherGroup g) const;
837 bool operator !=(BrancherGroup g) const;
840 unsigned int size(Space& home) const;
843 void kill(Space& home);
845
851 };
852
856 class Home {
857 friend class PostInfo;
858 protected:
867 public:
869
870
871 Home(Space& s, Propagator* p=NULL,
875 Home(const Home& h);
877 Home& operator =(const Home& h);
879 operator Space&(void);
881
883
890 Propagator* propagator(void) const;
894 BrancherGroup branchergroup(void) const;
896
898
899 bool failed(void) const;
901 void fail(void);
903 void notice(Actor& a, ActorProperty p, bool duplicate=false);
905 };
906
911 friend class Space;
912 friend class PostInfo;
913 public:
915 enum What {
921 POST = 2,
924 };
925 protected:
927 ptrdiff_t who;
929 void propagator(Propagator& p);
931 void brancher(Brancher& b);
933 void post(PropagatorGroup g);
935 void other(void);
936 public:
938 What what(void) const;
940 const Propagator& propagator(void) const;
942 const Brancher& brancher(void) const;
944 PropagatorGroup post(void) const;
945 };
946
950 class PostInfo {
951 friend class Space;
952 protected:
958 unsigned int pid;
960 bool nested;
961 public:
963 PostInfo(Home home);
965 ~PostInfo(void);
966 };
967
972 friend class Space;
973 public:
981 protected:
983 unsigned int i;
987 const Propagator* p;
992 const Propagator* p, Status s);
993 public:
995 unsigned int id(void) const;
997 PropagatorGroup group(void) const;
999 const Propagator* propagator(void) const;
1001 Status status(void) const;
1002 };
1003
1008 friend class Space;
1009 protected:
1011 const Brancher& b;
1013 const Choice& c;
1015 unsigned int a;
1017 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1018 public:
1020 unsigned int id(void) const;
1022 BrancherGroup group(void) const;
1024 const Brancher& brancher(void) const;
1026 const Choice& choice(void) const;
1028 unsigned int alternative(void) const;
1029 };
1030
1035 friend class Space;
1036 friend class PostInfo;
1037 public:
1044 protected:
1050 unsigned int n;
1052 PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
1053 public:
1055 Status status(void) const;
1057 PropagatorGroup group(void) const;
1059 unsigned int propagators(void) const;
1060 };
1061
1067 friend class ActorLink;
1068 friend class Space;
1069 template<class VIC> friend class VarImp;
1070 friend class Advisor;
1071 template<class A> friend class Council;
1073 friend class PropagatorGroup;
1074 private:
1075 union {
1079 size_t size;
1082 } u;
1084 void* gpi_disabled;
1086 static Propagator* cast(ActorLink* al);
1088 static const Propagator* cast(const ActorLink* al);
1090 void disable(Space& home);
1092 void enable(Space& home);
1093 protected:
1095 Propagator(Home home);
1097 Propagator(Space& home, Propagator& p);
1099 Propagator* fwd(void) const;
1101 Kernel::GPI::Info& gpi(void);
1102
1103 public:
1105
1106
1114 virtual void reschedule(Space& home) = 0;
1138 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1140 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1148 ModEventDelta modeventdelta(void) const;
1185 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1188 virtual void advise(Space& home, Advisor& a);
1190
1192
1193 double afc(void) const;
1195#ifdef GECODE_HAS_CBS
1197
1198
1205 typedef std::function<void(unsigned int prop_id, unsigned int var_id,
1206 int val, double dens)> SendMarginal;
1207 virtual void solndistrib(Space& home, SendMarginal send) const;
1216 typedef std::function<bool(unsigned int var_id)> InDecision;
1217 virtual void domainsizesum(InDecision in, unsigned int& size,
1218 unsigned int& size_b) const;
1220#endif
1222
1223
1224 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, 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, Advisor& a);
1316 const ViewTraceInfo& operator ()(const Space& home) const;
1317
1319
1320
1321 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__
1331 static void operator delete(void* p);
1332#endif
1334 static void* operator new(size_t s);
1335 };
1336
1337
1343 private:
1345 void* nl;
1346 public:
1353
1354 NGL(void);
1356 NGL(Space& home);
1358 NGL(Space& home, 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) = 0;
1373 virtual bool notice(void) const;
1375 virtual size_t dispose(Space& home);
1377
1378
1379 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
1392 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);
1432 virtual void archive(Archive& e) const;
1433 };
1434
1445 friend class ActorLink;
1446 friend class Space;
1447 friend class Choice;
1448 private:
1450 unsigned int bid;
1452 unsigned int gid;
1454 static Brancher* cast(ActorLink* al);
1456 static const Brancher* cast(const ActorLink* al);
1457 protected:
1459 Brancher(Home home);
1461 Brancher(Space& home, Brancher& b);
1462 public:
1464
1465
1473 virtual bool status(const Space& home) const = 0;
1481 virtual const Choice* choice(Space& home) = 0;
1483 virtual const Choice* choice(const Space& home, Archive& e) = 0;
1490 virtual ExecStatus commit(Space& home, const Choice& c,
1491 unsigned int a) = 0;
1506 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1515 virtual void print(const Space& home, const Choice& c, unsigned int a,
1516 std::ostream& o) const;
1518
1520
1521 unsigned int id(void) const;
1523 BrancherGroup group(void) const;
1525 void group(BrancherGroup g);
1527 };
1528
1535 class LocalObject : public Actor {
1536 friend class ActorLink;
1537 friend class Space;
1538 friend class LocalHandle;
1539 protected:
1541 LocalObject(Home home);
1543 LocalObject(Space& home, LocalObject& l);
1545 static LocalObject* cast(ActorLink* al);
1547 static const LocalObject* cast(const ActorLink* al);
1548 private:
1550 GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
1551 public:
1553 LocalObject* fwd(Space& home);
1554 };
1555
1561 private:
1563 LocalObject* o;
1564 protected:
1566 LocalHandle(void);
1570 LocalHandle(const LocalHandle& lh);
1571 public:
1575 void update(Space& home, LocalHandle& lh);
1577 ~LocalHandle(void);
1578 protected:
1580 LocalObject* object(void) const;
1582 void object(LocalObject* n);
1583 };
1584
1585
1591 protected:
1593 unsigned long int n;
1594 public:
1596 NoGoods(void);
1599 virtual void post(Space& home) const;
1601 unsigned long int ng(void) const;
1603 void ng(unsigned long int n);
1605 virtual ~NoGoods(void);
1608 static NoGoods eng;
1609 };
1610
1616 public:
1624 protected:
1626 const Type t;
1628
1629
1630 const unsigned long int r;
1632 const unsigned long int s;
1634 const unsigned long int f;
1636 const Space* l;
1638 const NoGoods& ng;
1640
1642
1643 const unsigned int a;
1645 public:
1647
1648
1649 MetaInfo(unsigned long int r,
1650 unsigned long int s,
1651 unsigned long int f,
1652 const Space* l,
1653 NoGoods& ng);
1655 MetaInfo(unsigned int a);
1657
1658 Type type(void) const;
1660
1661
1662 unsigned long int restart(void) const;
1664 unsigned long int solution(void) const;
1666 unsigned long int fail(void) const;
1668 const Space* last(void) const;
1670 const NoGoods& nogoods(void) const;
1672
1674
1675 unsigned int asset(void) const;
1677 };
1678
1688
1694 public:
1696 unsigned long int propagate;
1698 StatusStatistics(void);
1700 void reset(void);
1705 };
1706
1712 public:
1714 CloneStatistics(void);
1716 void reset(void);
1721 };
1722
1728 public:
1730 CommitStatistics(void);
1732 void reset(void);
1737 };
1738
1739
1740
1745 friend class Actor;
1746 friend class Propagator;
1747 friend class PropagatorGroup;
1748 friend class Propagators;
1749 friend class Brancher;
1750 friend class BrancherGroup;
1751 friend class Branchers;
1752 friend class Advisor;
1753 template <class A> friend class Council;
1754 template<class VIC> friend class VarImp;
1755 template<class VarImp> friend class VarImpDisposer;
1756 friend class LocalObject;
1757 friend class Region;
1758 friend class AFC;
1759 friend class PostInfo;
1761 void trace(Home home, TraceFilter tf, int te, Tracer& t);
1762 private:
1767#ifdef GECODE_HAS_CBS
1769 unsigned int var_id_counter;
1770#endif
1772 ActorLink pl;
1774 ActorLink bl;
1780 Brancher* b_status;
1792 Brancher* b_commit;
1794 Brancher* brancher(unsigned int id);
1795
1797 void kill(Brancher& b);
1799 void kill(Propagator& p);
1800
1803 void kill_brancher(unsigned int id);
1804
1806 static const unsigned reserved_bid = 0U;
1807
1809 static const unsigned int sc_bits = 2;
1811 static const unsigned int sc_fast = 0;
1813 static const unsigned int sc_disabled = 1;
1815 static const unsigned int sc_trace = 2;
1816
1817 union {
1819 struct {
1841 unsigned int bid_sc;
1843 unsigned int n_sub;
1846 } p;
1848 struct {
1855 } c;
1856 } pc;
1858 void enqueue(Propagator* p);
1863#ifdef GECODE_HAS_VAR_DISPOSE
1865 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1867 VarImpBase* _vars_d[AllVarConf::idx_d];
1869 template<class VIC> VarImpBase* vars_d(void) const;
1871 template<class VIC> void vars_d(VarImpBase* x);
1872#endif
1874 void update(ActorLink** sub);
1876
1878 Actor** d_fst;
1880 Actor** d_cur;
1882 Actor** d_lst;
1883
1885 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1887 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1889 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1890
1904 GECODE_KERNEL_EXPORT Space* _clone(void);
1905
1939 void _commit(const Choice& c, unsigned int a);
1940
1972 void _trycommit(const Choice& c, unsigned int a);
1973
1976 TraceRecorder* findtracerecorder(void);
1979 void post(const PostInfo& pi);
1980
1988 void ap_notice_dispose(Actor* a, bool d);
1996 void ap_ignore_dispose(Actor* a, bool d);
1997 public:
2003 Space(void);
2013 Space(Space& s);
2015 Space& operator =(const Space& s) = default;
2021 virtual ~Space(void);
2028 virtual Space* copy(void) = 0;
2039 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2064 virtual bool master(const MetaInfo& mi);
2091 virtual bool slave(const MetaInfo& mi);
2092
2093 /*
2094 * Member functions for search engines
2095 *
2096 */
2097
2110 SpaceStatus status(StatusStatistics& stat=unused_status);
2111
2144 const Choice* choice(void);
2145
2156 const Choice* choice(Archive& e) const;
2157
2173 Space* clone(CloneStatistics& stat=unused_clone) const;
2174
2209 void commit(const Choice& c, unsigned int a,
2210 CommitStatistics& stat=unused_commit);
2243 void trycommit(const Choice& c, unsigned int a,
2244 CommitStatistics& stat=unused_commit);
2264 NGL* ngl(const Choice& c, unsigned int a);
2265
2281 void print(const Choice& c, unsigned int a, std::ostream& o) const;
2282
2292 void notice(Actor& a, ActorProperty p, bool duplicate=false);
2301 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2302
2303
2352
2363 template<class A>
2375 template<class A>
2388 template<class A>
2390
2398 void fail(void);
2407 bool failed(void) const;
2412 bool stable(void) const;
2413
2415
2416
2417 Home operator ()(Propagator& p);
2419 Home operator ()(PropagatorGroup pg);
2421 Home operator ()(BrancherGroup bg);
2423
2429
2435 template<class T>
2436 T* alloc(long unsigned int n);
2443 template<class T>
2444 T* alloc(long int n);
2451 template<class T>
2452 T* alloc(unsigned int n);
2459 template<class T>
2460 T* alloc(int n);
2470 template<class T>
2471 void free(T* b, long unsigned int n);
2481 template<class T>
2482 void free(T* b, long int n);
2492 template<class T>
2493 void free(T* b, unsigned int n);
2503 template<class T>
2504 void free(T* b, int n);
2516 template<class T>
2517 T* realloc(T* b, long unsigned int n, long unsigned int m);
2529 template<class T>
2530 T* realloc(T* b, long int n, long int m);
2542 template<class T>
2543 T* realloc(T* b, unsigned int n, unsigned int m);
2555 template<class T>
2556 T* realloc(T* b, int n, int m);
2564 template<class T>
2565 T** realloc(T** b, long unsigned int n, long unsigned int m);
2573 template<class T>
2574 T** realloc(T** b, long int n, long int m);
2582 template<class T>
2583 T** realloc(T** b, unsigned int n, unsigned int m);
2591 template<class T>
2592 T** realloc(T** b, int n, int m);
2594 void* ralloc(size_t s);
2596 void rfree(void* p, size_t s);
2598 void* rrealloc(void* b, size_t n, size_t m);
2600 template<size_t> void* fl_alloc(void);
2606 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2608
2610
2613 template<class T>
2614 T& construct(void);
2620 template<class T, typename A1>
2621 T& construct(A1 const& a1);
2627 template<class T, typename A1, typename A2>
2628 T& construct(A1 const& a1, A2 const& a2);
2634 template<class T, typename A1, typename A2, typename A3>
2635 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2641 template<class T, typename A1, typename A2, typename A3, typename A4>
2642 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2648 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2649 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2651
2653
2654
2655 void afc_decay(double d);
2657 double afc_decay(void) const;
2661
2662 protected:
2669 private:
2671 Space& home;
2673 ActorLink* q;
2675 ActorLink* c;
2677 ActorLink* e;
2678 public:
2680 Propagators(Space& home);
2682 bool operator ()(void) const;
2684 void operator ++(void);
2686 Propagator& propagator(void) const;
2687 };
2688
2694 private:
2696 Space& home;
2698 ActorLink* q;
2700 ActorLink* c;
2702 ActorLink* e;
2703 public:
2707 bool operator ()(void) const;
2709 void operator ++(void);
2711 Propagator& propagator(void) const;
2712 };
2713
2719 private:
2721 ActorLink* c;
2723 ActorLink* e;
2724 public:
2726 IdlePropagators(Space& home);
2728 bool operator ()(void) const;
2730 void operator ++(void);
2732 Propagator& propagator(void) const;
2733 };
2734
2740 private:
2742 ActorLink* c;
2744 ActorLink* e;
2745 public:
2747 Branchers(Space& home);
2749 bool operator ()(void) const;
2751 void operator ++(void);
2753 Brancher& brancher(void) const;
2754 };
2755 };
2756
2759 private:
2764 public:
2766 Propagators(const Space& home, PropagatorGroup g);
2768 bool operator ()(void) const;
2770 void operator ++(void);
2772 const Propagator& propagator(void) const;
2773 };
2774
2777 private:
2781 BrancherGroup g;
2782 public:
2784 Branchers(const Space& home, BrancherGroup g);
2786 bool operator ()(void) const;
2788 void operator ++(void);
2790 const Brancher& brancher(void) const;
2791 };
2792
2793
2794
2795
2796 /*
2797 * Memory management
2798 *
2799 */
2800
2801 // Space allocation: general space heaps and free lists
2802 forceinline void*
2803 Space::ralloc(size_t s) {
2804 return mm.alloc(ssd.data().sm,s);
2805 }
2806 forceinline void
2807 Space::rfree(void* p, size_t s) {
2808 return mm.reuse(p,s);
2809 }
2810 forceinline void*
2811 Space::rrealloc(void* _b, size_t n, size_t m) {
2812 char* b = static_cast<char*>(_b);
2813 if (n < m) {
2814 char* p = static_cast<char*>(ralloc(m));
2815 memcpy(p,b,n);
2816 rfree(b,n);
2817 return p;
2818 } else {
2819 rfree(b+m,m-n);
2820 return b;
2821 }
2822 }
2823
2824 template<size_t s>
2825 forceinline void*
2827 return mm.template fl_alloc<s>(ssd.data().sm);
2828 }
2829 template<size_t s>
2830 forceinline void
2832 mm.template fl_dispose<s>(f,l);
2833 }
2834
2835 /*
2836 * Typed allocation routines
2837 *
2838 */
2839 template<class T>
2840 forceinline T*
2841 Space::alloc(long unsigned int n) {
2842 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2843 for (long unsigned int i=0; i<n; i++)
2844 (void) new (p+i) T();
2845 return p;
2846 }
2847 template<class T>
2848 forceinline T*
2849 Space::alloc(long int n) {
2850 assert(n >= 0);
2851 return alloc<T>(static_cast<long unsigned int>(n));
2852 }
2853 template<class T>
2854 forceinline T*
2855 Space::alloc(unsigned int n) {
2856 return alloc<T>(static_cast<long unsigned int>(n));
2857 }
2858 template<class T>
2859 forceinline T*
2861 assert(n >= 0);
2862 return alloc<T>(static_cast<long unsigned int>(n));
2863 }
2864
2865 template<class T>
2866 forceinline void
2867 Space::free(T* b, long unsigned int n) {
2868 for (long unsigned int i=0; i<n; i++)
2869 b[i].~T();
2870 rfree(b,n*sizeof(T));
2871 }
2872 template<class T>
2873 forceinline void
2874 Space::free(T* b, long int n) {
2875 assert(n >= 0);
2876 free<T>(b,static_cast<long unsigned int>(n));
2877 }
2878 template<class T>
2879 forceinline void
2880 Space::free(T* b, unsigned int n) {
2881 free<T>(b,static_cast<long unsigned int>(n));
2882 }
2883 template<class T>
2884 forceinline void
2885 Space::free(T* b, int n) {
2886 assert(n >= 0);
2887 free<T>(b,static_cast<long unsigned int>(n));
2888 }
2889
2890 template<class T>
2891 forceinline T*
2892 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2893 if (n < m) {
2894 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2895 for (long unsigned int i=0; i<n; i++)
2896 (void) new (p+i) T(b[i]);
2897 for (long unsigned int i=n; i<m; i++)
2898 (void) new (p+i) T();
2899 free<T>(b,n);
2900 return p;
2901 } else {
2902 free<T>(b+m,m-n);
2903 return b;
2904 }
2905 }
2906 template<class T>
2907 forceinline T*
2908 Space::realloc(T* b, long int n, long int m) {
2909 assert((n >= 0) && (m >= 0));
2910 return realloc<T>(b,static_cast<long unsigned int>(n),
2911 static_cast<long unsigned int>(m));
2912 }
2913 template<class T>
2914 forceinline T*
2915 Space::realloc(T* b, unsigned int n, unsigned int m) {
2916 return realloc<T>(b,static_cast<long unsigned int>(n),
2917 static_cast<long unsigned int>(m));
2918 }
2919 template<class T>
2920 forceinline T*
2921 Space::realloc(T* b, int n, int m) {
2922 assert((n >= 0) && (m >= 0));
2923 return realloc<T>(b,static_cast<long unsigned int>(n),
2924 static_cast<long unsigned int>(m));
2925 }
2926
2927#define GECODE_KERNEL_REALLOC(T) \
2928 template<> \
2929 forceinline T* \
2930 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2931 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2932 } \
2933 template<> \
2934 forceinline T* \
2935 Space::realloc<T>(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<> \
2941 forceinline T* \
2942 Space::realloc<T>(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<> \
2947 forceinline T* \
2948 Space::realloc<T>(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
2955 GECODE_KERNEL_REALLOC(signed char)
2956 GECODE_KERNEL_REALLOC(unsigned char)
2957 GECODE_KERNEL_REALLOC(signed short int)
2958 GECODE_KERNEL_REALLOC(unsigned short int)
2959 GECODE_KERNEL_REALLOC(signed int)
2960 GECODE_KERNEL_REALLOC(unsigned int)
2961 GECODE_KERNEL_REALLOC(signed long int)
2962 GECODE_KERNEL_REALLOC(unsigned long int)
2964 GECODE_KERNEL_REALLOC(double)
2965
2966#undef GECODE_KERNEL_REALLOC
2967
2968 template<class T>
2969 forceinline T**
2970 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2971 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2972 }
2973 template<class T>
2974 forceinline T**
2975 Space::realloc(T** b, long int n, long 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 template<class T>
2981 forceinline T**
2982 Space::realloc(T** b, unsigned int n, unsigned int m) {
2983 return realloc<T*>(b,static_cast<long unsigned int>(n),
2984 static_cast<long unsigned int>(m));
2985 }
2986 template<class T>
2987 forceinline T**
2988 Space::realloc(T** b, int n, int m) {
2989 assert((n >= 0) && (m >= 0));
2990 return realloc<T*>(b,static_cast<long unsigned int>(n),
2991 static_cast<long unsigned int>(m));
2992 }
2993
2994
2995#ifdef GECODE_HAS_VAR_DISPOSE
2996 template<class VIC>
2998 Space::vars_d(void) const {
2999 return _vars_d[VIC::idx_d];
3000 }
3001 template<class VIC>
3002 forceinline void
3003 Space::vars_d(VarImpBase* x) {
3004 _vars_d[VIC::idx_d] = x;
3005 }
3006#endif
3007
3008 // Space allocated entities: Actors, variable implementations, and advisors
3009 forceinline void
3010 Actor::operator delete(void*) {}
3011 forceinline void
3012 Actor::operator delete(void*, Space&) {}
3013 forceinline void*
3014 Actor::operator new(size_t s, Space& home) {
3015 return home.ralloc(s);
3016 }
3017
3018 template<class VIC>
3019 forceinline void
3020 VarImp<VIC>::operator delete(void*) {}
3021 template<class VIC>
3022 forceinline void
3023 VarImp<VIC>::operator delete(void*, Space&) {}
3024 template<class VIC>
3025 forceinline void*
3026 VarImp<VIC>::operator new(size_t s, Space& home) {
3027 return home.ralloc(s);
3028 }
3029
3030#ifndef __GNUC__
3031 forceinline void
3032 Advisor::operator delete(void*) {}
3033#endif
3034 forceinline void
3035 Advisor::operator delete(void*, Space&) {}
3036 forceinline void*
3037 Advisor::operator new(size_t s, Space& home) {
3038 return home.ralloc(s);
3039 }
3040
3041 forceinline void
3042 NGL::operator delete(void*) {}
3043 forceinline void
3044 NGL::operator delete(void*, Space&) {}
3045 forceinline void*
3046 NGL::operator new(size_t s, Space& home) {
3047 return home.ralloc(s);
3048 }
3049
3050
3051 /*
3052 * No-goods
3053 *
3054 */
3057 : n(0) {}
3058 forceinline unsigned long int
3059 NoGoods::ng(void) const {
3060 return n;
3061 }
3062 forceinline void
3063 NoGoods::ng(unsigned long int n0) {
3064 n=n0;
3065 }
3068
3069
3070 /*
3071 * Information from meta search engines
3072 */
3074 MetaInfo::MetaInfo(unsigned long int r0,
3075 unsigned long int s0,
3076 unsigned long int f0,
3077 const Space* l0,
3078 NoGoods& ng0)
3079 : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3080
3082 MetaInfo::MetaInfo(unsigned int a0)
3083 : t(PORTFOLIO), r(0), s(0), f(0), l(NULL), ng(NoGoods::eng), a(a0) {}
3084
3086 MetaInfo::type(void) const {
3087 return t;
3088 }
3089 forceinline unsigned long int
3090 MetaInfo::restart(void) const {
3091 assert(type() == RESTART);
3092 return r;
3093 }
3094 forceinline unsigned long int
3096 assert(type() == RESTART);
3097 return s;
3098 }
3099 forceinline unsigned long int
3100 MetaInfo::fail(void) const {
3101 assert(type() == RESTART);
3102 return f;
3103 }
3104 forceinline const Space*
3105 MetaInfo::last(void) const {
3106 assert(type() == RESTART);
3107 return l;
3108 }
3109 forceinline const NoGoods&
3110 MetaInfo::nogoods(void) const {
3111 assert(type() == RESTART);
3112 return ng;
3113 }
3114 forceinline unsigned int
3115 MetaInfo::asset(void) const {
3116 assert(type() == PORTFOLIO);
3117 return a;
3118 }
3119
3120
3121
3122 /*
3123 * ActorLink
3124 *
3125 */
3127 ActorLink::prev(void) const {
3128 return _prev;
3129 }
3130
3132 ActorLink::next(void) const {
3133 return _next;
3134 }
3135
3138 return &_next;
3139 }
3140
3141 forceinline void
3143 _prev = al;
3144 }
3145
3146 forceinline void
3148 _next = al;
3149 }
3150
3151 forceinline void
3153 ActorLink* p = _prev; ActorLink* n = _next;
3154 p->_next = n; n->_prev = p;
3155 }
3156
3157 forceinline void
3159 _next = this; _prev =this;
3160 }
3161
3162 forceinline void
3164 // Inserts al at head of link-chain (that is, after this)
3165 ActorLink* n = _next;
3166 this->_next = a; a->_prev = this;
3167 a->_next = n; n->_prev = a;
3168 }
3169
3170 forceinline void
3172 // Inserts al at tail of link-chain (that is, before this)
3173 ActorLink* p = _prev;
3174 a->_next = this; this->_prev = a;
3175 p->_next = a; a->_prev = p;
3176 }
3177
3178 forceinline bool
3179 ActorLink::empty(void) const {
3180 return _next == this;
3181 }
3182
3183 template<class T>
3186 // Turning al into a reference is for gcc, assume is for MSVC
3187 GECODE_NOT_NULL(a);
3188 ActorLink& t = *a;
3189 return static_cast<ActorLink*>(&t);
3190 }
3191
3192 template<class T>
3193 forceinline const ActorLink*
3194 ActorLink::cast(const T* a) {
3195 // Turning al into a reference is for gcc, assume is for MSVC
3196 GECODE_NOT_NULL(a);
3197 const ActorLink& t = *a;
3198 return static_cast<const ActorLink*>(&t);
3199 }
3200
3201
3202 /*
3203 * Actor
3204 *
3205 */
3207 Actor::cast(ActorLink* al) {
3208 // Turning al into a reference is for gcc, assume is for MSVC
3209 GECODE_NOT_NULL(al);
3210 ActorLink& t = *al;
3211 return static_cast<Actor*>(&t);
3212 }
3213
3214 forceinline const Actor*
3215 Actor::cast(const ActorLink* al) {
3216 // Turning al into a reference is for gcc, assume is for MSVC
3217 GECODE_NOT_NULL(al);
3218 const ActorLink& t = *al;
3219 return static_cast<const Actor*>(&t);
3220 }
3221
3222 forceinline void
3223 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3224 s.notice(a,p,duplicate);
3225 }
3226
3229 // Clone is only const for search engines. During cloning, several data
3230 // structures are updated (e.g. forwarding pointers), so we have to
3231 // cast away the constness.
3232 return const_cast<Space*>(this)->_clone();
3233 }
3234
3235 forceinline void
3236 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3237 _commit(c,a);
3238 }
3239
3240 forceinline void
3241 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3242 _trycommit(c,a);
3243 }
3244
3245 forceinline double
3246 Space::afc_decay(void) const {
3247 return ssd.data().gpi.decay();
3248 }
3249
3250 forceinline void
3252 ssd.data().gpi.decay(d);
3253 }
3254
3255 forceinline size_t
3257 return sizeof(*this);
3258 }
3259
3260
3261 /*
3262 * Home for posting actors
3263 *
3264 */
3268 : s(s0), p(p0), pg(pg0), bg(bg0) {}
3271 : s(h.s), p(h.p), pg(h.pg), bg(h.bg) {}
3274 s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3275 return *this;
3276 }
3278 Home::operator Space&(void) {
3279 return s;
3280 }
3283 return Home(s,&p);
3284 }
3295 return Home(*this,&p);
3296 }
3299 return Home(*this,NULL,pg,BrancherGroup::def);
3300 }
3303 return Home(*this,NULL,PropagatorGroup::def,bg);
3304 }
3306 Home::propagator(void) const {
3307 return p;
3308 }
3311 return pg;
3312 }
3315 return bg;
3316 }
3317
3318 /*
3319 * View trace information
3320 *
3321 */
3322 forceinline void
3324 who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3325 }
3326 forceinline void
3328 who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3329 }
3330 forceinline void
3332 who = (g.id() << 2) | POST;
3333 }
3334 forceinline void
3336 who = OTHER;
3337 }
3340 return static_cast<What>(who & 3);
3341 }
3342 forceinline const Propagator&
3344 assert(what() == PROPAGATOR);
3345 // Because PROPAGATOR == 0
3346 return *reinterpret_cast<Propagator*>(who);
3347 }
3348 forceinline const Brancher&
3350 assert(what() == BRANCHER);
3351 return *reinterpret_cast<Brancher*>(who & ~3);
3352 }
3355 assert(what() == POST);
3356 return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3357 }
3358
3359 /*
3360 * Post information
3361 */
3364 : h(home), pg(home.propagatorgroup()),
3365 pid(h.ssd.data().gpi.pid()),
3366 nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
3367 h.pc.p.vti.post(pg);
3368 }
3369
3372 if (!nested) {
3373 if (h.pc.p.bid_sc & Space::sc_trace)
3374 h.post(*this);
3375 h.pc.p.vti.other();
3376 }
3377 }
3378
3379
3380 /*
3381 * Propagate trace information
3382 *
3383 */
3386 const Propagator* p0, Status s0)
3387 : i(i0), g(g0), p(p0), s(s0) {}
3388 forceinline unsigned int
3390 return i;
3391 }
3394 return g;
3395 }
3396 forceinline const Propagator*
3398 return p;
3399 }
3402 return s;
3403 }
3404
3405
3406 /*
3407 * Commit trace information
3408 *
3409 */
3412 unsigned int a0)
3413 : b(b0), c(c0), a(a0) {}
3414 forceinline unsigned int
3416 return b.id();
3417 }
3420 return b.group();
3421 }
3422 forceinline const Brancher&
3424 return b;
3425 }
3426 forceinline const Choice&
3428 return c;
3429 }
3430 forceinline unsigned int
3432 return a;
3433 }
3434
3435
3436 /*
3437 * Post trace information
3438 *
3439 */
3442 : g(g0), s(s0), n(n0) {}
3445 return g;
3446 }
3449 return s;
3450 }
3451 forceinline unsigned int
3453 return n;
3454 }
3455
3456
3457 /*
3458 * Propagator
3459 *
3460 */
3462 Propagator::cast(ActorLink* al) {
3463 // Turning al into a reference is for gcc, assume is for MSVC
3464 GECODE_NOT_NULL(al);
3465 ActorLink& t = *al;
3466 return static_cast<Propagator*>(&t);
3467 }
3468
3469 forceinline const Propagator*
3470 Propagator::cast(const ActorLink* al) {
3471 // Turning al into a reference is for gcc, assume is for MSVC
3472 GECODE_NOT_NULL(al);
3473 const ActorLink& t = *al;
3474 return static_cast<const Propagator*>(&t);
3475 }
3476
3478 Propagator::fwd(void) const {
3479 return static_cast<Propagator*>(prev());
3480 }
3481
3482 forceinline bool
3484 return Support::marked(gpi_disabled);
3485 }
3486
3487 forceinline void
3488 Propagator::disable(Space& home) {
3489 home.pc.p.bid_sc |= Space::sc_disabled;
3490 gpi_disabled = Support::fmark(gpi_disabled);
3491 }
3492
3493 forceinline void
3494 Propagator::enable(Space& home) {
3495 (void) home;
3496 gpi_disabled = Support::funmark(gpi_disabled);
3497 }
3498
3501 return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
3502 }
3503
3506 : gpi_disabled((home.propagator() != NULL) ?
3507 // Inherit propagator information
3508 home.propagator()->gpi_disabled :
3509 // New propagator information
3510 static_cast<Space&>(home).ssd.data().gpi.allocate
3511 (home.propagatorgroup().gid)) {
3512 u.advisors = NULL;
3513 assert((u.med == 0) && (u.size == 0));
3514 static_cast<Space&>(home).pl.head(this);
3515 }
3516
3519 : gpi_disabled(p.gpi_disabled) {
3520 u.advisors = NULL;
3521 assert((u.med == 0) && (u.size == 0));
3522 // Set forwarding pointer
3523 p.prev(this);
3524 }
3525
3528 return u.med;
3529 }
3530
3531 forceinline double
3532 Propagator::afc(void) const {
3533 return const_cast<Propagator&>(*this).gpi().afc;
3534 }
3535
3536#ifdef GECODE_HAS_CBS
3537 forceinline void
3538 Propagator::solndistrib(Space&, SendMarginal) const {}
3539
3540 forceinline void
3541 Propagator::domainsizesum(InDecision, unsigned int& size,
3542 unsigned int& size_b) const {
3543 size = 0;
3544 size_b = 0;
3545 }
3546#endif
3547
3548 forceinline unsigned int
3549 Propagator::id(void) const {
3550 return const_cast<Propagator&>(*this).gpi().pid;
3551 }
3552
3554 Propagator::group(void) const {
3555 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3556 }
3557
3558 forceinline void
3560 gpi().gid = g.id();
3561 }
3562
3565 p.u.size = s;
3566 return __ES_SUBSUMED;
3567 }
3568
3571 p.u.size = p.dispose(*this);
3572 return __ES_SUBSUMED;
3573 }
3574
3577 p.u.med = med;
3578 assert(p.u.med != 0);
3579 return __ES_PARTIAL;
3580 }
3581
3584 p.u.med = AllVarConf::med_combine(p.u.med,med);
3585 assert(p.u.med != 0);
3586 return __ES_PARTIAL;
3587 }
3588
3589
3590
3591 /*
3592 * Brancher
3593 *
3594 */
3596 Brancher::cast(ActorLink* al) {
3597 // Turning al into a reference is for gcc, assume is for MSVC
3598 GECODE_NOT_NULL(al);
3599 ActorLink& t = *al;
3600 return static_cast<Brancher*>(&t);
3601 }
3602
3603 forceinline const Brancher*
3604 Brancher::cast(const ActorLink* al) {
3605 // Turning al into a reference is for gcc, assume is for MSVC
3606 GECODE_NOT_NULL(al);
3607 const ActorLink& t = *al;
3608 return static_cast<const Brancher*>(&t);
3609 }
3610
3613 gid(_home.branchergroup().gid) {
3614 Space& home = static_cast<Space&>(_home);
3615 bid = home.pc.p.bid_sc >> Space::sc_bits;
3616 home.pc.p.bid_sc += (1 << Space::sc_bits);
3617 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3618 throw TooManyBranchers("Brancher::Brancher");
3619 // If no brancher available, make it the first one
3620 if (home.b_status == &static_cast<Space&>(home).bl) {
3621 home.b_status = this;
3622 if (home.b_commit == &static_cast<Space&>(home).bl)
3623 home.b_commit = this;
3624 }
3625 home.bl.tail(this);
3626 }
3627
3630 : bid(b.bid), gid(b.gid) {
3631 // Set forwarding pointer
3632 b.prev(this);
3633 }
3634
3635 forceinline unsigned int
3636 Brancher::id(void) const {
3637 return bid;
3638 }
3639
3641 Brancher::group(void) const {
3642 return BrancherGroup(gid);
3643 }
3644
3645 forceinline void
3647 gid = g.id();
3648 }
3649
3650
3651 forceinline void
3652 Space::kill(Brancher& b) {
3653 assert(!failed());
3654 // Make sure that neither b_status nor b_commit does not point to b!
3655 if (b_commit == &b)
3656 b_commit = Brancher::cast(b.next());
3657 if (b_status == &b)
3658 b_status = Brancher::cast(b.next());
3659 b.unlink();
3660 rfree(&b,b.dispose(*this));
3661 }
3662
3663 forceinline void
3664 Space::kill(Propagator& p) {
3665 assert(!failed());
3666 p.unlink();
3667 rfree(&p,p.dispose(*this));
3668 }
3669
3671 Space::brancher(unsigned int id) {
3672 /*
3673 * Due to weakly monotonic propagators the following scenario might
3674 * occur: a brancher has been committed with all its available
3675 * choices. Then, propagation determines less information
3676 * than before and the brancher now will create new choices.
3677 * Later, during recomputation, all of these choices
3678 * can be used together, possibly interleaved with
3679 * choices for other branchers. That means all branchers
3680 * must be scanned to find the matching brancher for the choice.
3681 *
3682 * b_commit tries to optimize scanning as it is most likely that
3683 * recomputation does not generate new choices during recomputation
3684 * and hence b_commit is moved from newer to older branchers.
3685 */
3686 Brancher* b_old = b_commit;
3687 // Try whether we are lucky
3688 while (b_commit != Brancher::cast(&bl))
3689 if (id != b_commit->id())
3690 b_commit = Brancher::cast(b_commit->next());
3691 else
3692 return b_commit;
3693 if (b_commit == Brancher::cast(&bl)) {
3694 // We did not find the brancher, start at the beginning
3695 b_commit = Brancher::cast(bl.next());
3696 while (b_commit != b_old)
3697 if (id != b_commit->id())
3698 b_commit = Brancher::cast(b_commit->next());
3699 else
3700 return b_commit;
3701 }
3702 return NULL;
3703 }
3704
3705
3706 /*
3707 * Local objects
3708 *
3709 */
3710
3713 // Turning al into a reference is for gcc, assume is for MSVC
3714 GECODE_NOT_NULL(al);
3715 ActorLink& t = *al;
3716 return static_cast<LocalObject*>(&t);
3717 }
3718
3721 // Turning al into a reference is for gcc, assume is for MSVC
3722 GECODE_NOT_NULL(al);
3723 const ActorLink& t = *al;
3724 return static_cast<const LocalObject*>(&t);
3725 }
3726
3729 (void) home;
3730 ActorLink::cast(this)->prev(NULL);
3731 }
3732
3737
3740 if (prev() == NULL)
3741 fwdcopy(home);
3742 return LocalObject::cast(prev());
3743 }
3744
3746 LocalHandle::LocalHandle(void) : o(NULL) {}
3753 o = lh.o;
3754 return *this;
3755 }
3759 LocalHandle::object(void) const { return o; }
3760 forceinline void
3762 forceinline void
3764 object(lh.object()->fwd(home));
3765 }
3766
3767
3768 /*
3769 * Choices
3770 *
3771 */
3773 Choice::Choice(const Brancher& b, const unsigned int a)
3774 : bid(b.id()), alt(a) {}
3775
3776 forceinline unsigned int
3778 return alt;
3779 }
3780
3781 forceinline unsigned int
3782 Choice::id(void) const {
3783 return bid;
3784 }
3785
3788
3789
3790
3791 /*
3792 * No-good literal
3793 *
3794 */
3795 forceinline bool
3796 NGL::leaf(void) const {
3797 return Support::marked(nl);
3798 }
3800 NGL::next(void) const {
3801 return static_cast<NGL*>(Support::funmark(nl));
3802 }
3803 forceinline void
3804 NGL::leaf(bool l) {
3805 nl = l ? Support::fmark(nl) : Support::funmark(nl);
3806 }
3807 forceinline void
3809 nl = Support::marked(nl) ? Support::mark(n) : n;
3810 }
3812 NGL::add(NGL* n, bool l) {
3813 nl = Support::marked(nl) ? Support::mark(n) : n;
3814 n->leaf(l);
3815 return n;
3816 }
3817
3820 : nl(NULL) {}
3823 : nl(NULL) {}
3826 : nl(NULL) {}
3827 forceinline size_t
3829 return sizeof(*this);
3830 }
3831
3832 /*
3833 * Advisor
3834 *
3835 */
3836 template<class A>
3839 // Store propagator and forwarding in prev()
3840 ActorLink::prev(&p);
3841 // Link to next advisor in next()
3842 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3843 }
3844
3847
3848 forceinline bool
3849 Advisor::disposed(void) const {
3850 return prev() == NULL;
3851 }
3852
3853 forceinline Advisor*
3854 Advisor::cast(ActorLink* al) {
3855 return static_cast<Advisor*>(al);
3856 }
3857
3858 forceinline const Advisor*
3859 Advisor::cast(const ActorLink* al) {
3860 return static_cast<const Advisor*>(al);
3861 }
3862
3865 assert(!disposed());
3866 return *Propagator::cast(ActorLink::prev());
3867 }
3868
3869 template<class A>
3870 forceinline void
3872 assert(!disposed());
3873 ActorLink::prev(NULL);
3874 // Shorten chains of disposed advisors by one, if possible
3875 Advisor* n = Advisor::cast(next());
3876 if ((n != NULL) && n->disposed())
3877 next(n->next());
3878 }
3879
3881 Advisor::operator ()(const Space& home) const {
3882 return home.pc.p.vti;
3883 }
3884
3885 template<class A>
3888 a.dispose(*this,c);
3889 return ES_FIX;
3890 }
3891
3892 template<class A>
3895 a.dispose(*this,c);
3896 return ES_NOFIX;
3897 }
3898
3899 template<class A>
3902 a.dispose(*this,c);
3903 return ES_NOFIX_FORCE;
3904 }
3905
3906
3907
3908 /*
3909 * Advisor council
3910 *
3911 */
3912 template<class A>
3915
3916 template<class A>
3919 : advisors(NULL) {}
3920
3921 template<class A>
3922 forceinline bool
3923 Council<A>::empty(void) const {
3924 ActorLink* a = advisors;
3925 while ((a != NULL) && static_cast<A*>(a)->disposed())
3926 a = a->next();
3927 advisors = a;
3928 return a == NULL;
3929 }
3930
3931 template<class A>
3932 forceinline void
3934 // Skip all disposed advisors
3935 {
3936 ActorLink* a = c.advisors;
3937 while ((a != NULL) && static_cast<A*>(a)->disposed())
3938 a = a->next();
3939 c.advisors = a;
3940 }
3941 // Are there any advisors to be cloned?
3942 if (c.advisors != NULL) {
3943 // The propagator in from-space
3944 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3945 // The propagator in to-space
3946 Propagator* p_t = Propagator::cast(p_f->prev());
3947 // Advisors in from-space
3948 ActorLink** a_f = &c.advisors;
3949 // Advisors in to-space
3950 A* a_t = NULL;
3951 while (*a_f != NULL) {
3952 if (static_cast<A*>(*a_f)->disposed()) {
3953 *a_f = (*a_f)->next();
3954 } else {
3955 // Run specific copying part
3956 A* a = new (home) A(home,*static_cast<A*>(*a_f));
3957 // Set propagator pointer
3958 a->prev(p_t);
3959 // Set forwarding pointer
3960 (*a_f)->prev(a);
3961 // Link
3962 a->next(a_t);
3963 a_t = a;
3964 a_f = (*a_f)->next_ref();
3965 }
3966 }
3967 advisors = a_t;
3968 // Enter advisor link for reset
3969 assert(p_f->u.advisors == NULL);
3970 p_f->u.advisors = c.advisors;
3971 } else {
3972 advisors = NULL;
3973 }
3974 }
3975
3976 template<class A>
3977 forceinline void
3979 ActorLink* a = advisors;
3980 while (a != NULL) {
3981 if (!static_cast<A*>(a)->disposed())
3982 static_cast<A*>(a)->dispose(home,*this);
3983 a = a->next();
3984 }
3985 }
3986
3987
3988
3989 /*
3990 * Advisor iterator
3991 *
3992 */
3993 template<class A>
3996 : a(c.advisors) {
3997 while ((a != NULL) && static_cast<A*>(a)->disposed())
3998 a = a->next();
3999 }
4000
4001 template<class A>
4002 forceinline bool
4004 return a != NULL;
4005 }
4006
4007 template<class A>
4008 forceinline void
4010 do {
4011 a = a->next();
4012 } while ((a != NULL) && static_cast<A*>(a)->disposed());
4013 }
4014
4015 template<class A>
4016 forceinline A&
4018 return *static_cast<A*>(a);
4019 }
4020
4021
4022
4023 /*
4024 * Space
4025 *
4026 */
4027 forceinline void
4028 Space::enqueue(Propagator* p) {
4030 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
4031 c->tail(ActorLink::cast(p));
4032 if (c > pc.p.active)
4033 pc.p.active = c;
4034 }
4035
4036 forceinline void
4038 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
4039 /*
4040 * Now active points beyond the last queue. This is essential as
4041 * enqueuing a propagator in a failed space keeps the space
4042 * failed.
4043 */
4044 }
4045 forceinline void
4047 s.fail();
4048 }
4049
4050 forceinline bool
4051 Space::failed(void) const {
4052 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4053 }
4054 forceinline bool
4055 Home::failed(void) const {
4056 return s.failed();
4057 }
4058
4059 forceinline bool
4060 Space::stable(void) const {
4061 return ((pc.p.active < &pc.p.queue[0]) ||
4062 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
4063 }
4064
4065 forceinline void
4067 if (p & AP_DISPOSE) {
4068 ap_notice_dispose(&a,d);
4069 }
4070 if (p & AP_VIEW_TRACE) {
4071 pc.p.bid_sc |= sc_trace;
4072 }
4073 if (p & AP_TRACE) {
4074 pc.p.bid_sc |= sc_trace;
4075 }
4076 // Currently unused
4077 if (p & AP_WEAKLY) {}
4078 }
4079
4080 forceinline void
4082 // Check wether array has already been discarded as space
4083 // deletion is already in progress
4084 if ((p & AP_DISPOSE) && (d_fst != NULL))
4085 ap_ignore_dispose(&a,d);
4086 if (p & AP_VIEW_TRACE) {}
4087 if (p & AP_TRACE) {}
4088 // Currently unused
4089 if (p & AP_WEAKLY) {}
4090 }
4091
4092
4093
4094 /*
4095 * Variable implementation
4096 *
4097 */
4098 template<class VIC>
4100 VarImp<VIC>::actor(PropCond pc) {
4101 assert((pc >= 0) && (pc < pc_max+2));
4102 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4103 }
4104
4105 template<class VIC>
4106 forceinline ActorLink**
4107 VarImp<VIC>::actorNonZero(PropCond pc) {
4108 assert((pc > 0) && (pc < pc_max+2));
4109 return b.base+u.idx[pc-1];
4110 }
4111
4112 template<class VIC>
4113 forceinline unsigned int&
4115 assert((pc > 0) && (pc < pc_max+2));
4116 return u.idx[pc-1];
4117 }
4118
4119 template<class VIC>
4120 forceinline unsigned int
4121 VarImp<VIC>::idx(PropCond pc) const {
4122 assert((pc > 0) && (pc < pc_max+2));
4123 return u.idx[pc-1];
4124 }
4125
4126 template<class VIC>
4129#ifdef GECODE_HAS_CBS
4130 : var_id(++home.var_id_counter)
4131#endif
4132 {
4133#ifndef GECODE_HAS_CBS
4134 (void) home;
4135#endif
4136 b.base = NULL; entries = 0;
4137 for (PropCond pc=1; pc<pc_max+2; pc++)
4138 idx(pc) = 0;
4139 free_and_bits = 0;
4140 }
4141
4142 template<class VIC>
4145#ifdef GECODE_HAS_CBS
4146 : var_id(0)
4147#endif
4148 {
4149 b.base = NULL; entries = 0;
4150 for (PropCond pc=1; pc<pc_max+2; pc++)
4151 idx(pc) = 0;
4152 free_and_bits = 0;
4153 }
4154
4155#ifdef GECODE_HAS_CBS
4156 template<class VIC>
4157 forceinline unsigned int
4158 VarImp<VIC>::id(void) const {
4159 return var_id;
4160 }
4161#endif
4162
4163 template<class VIC>
4164 forceinline unsigned int
4166 assert(!copied());
4167 return entries;
4168 }
4169
4170 template<class VIC>
4171 forceinline double
4172 VarImp<VIC>::afc(void) const {
4173 double d = 0.0;
4174 // Count the afc of each propagator
4175 {
4176 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4177 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4178 while (a < e) {
4179 d += Propagator::cast(*a)->afc(); a++;
4180 }
4181 }
4182 // Count the afc of each advisor's propagator
4183 {
4184 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4185 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4186 while (a < e) {
4187 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4188 ->propagator().afc();
4189 a++;
4190 }
4191 }
4192 return d;
4193 }
4194
4195 template<class VIC>
4198 return d.me;
4199 }
4200
4201 template<class VIC>
4202 forceinline unsigned int
4203 VarImp<VIC>::bits(void) const {
4204 return free_and_bits;
4205 }
4206
4207 template<class VIC>
4208 forceinline unsigned int&
4210 return free_and_bits;
4211 }
4212
4213#ifdef GECODE_HAS_VAR_DISPOSE
4214 template<class VIC>
4216 VarImp<VIC>::vars_d(Space& home) {
4217 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4218 }
4219
4220 template<class VIC>
4221 forceinline void
4222 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
4223 home.vars_d<VIC>(x);
4224 }
4225#endif
4226
4227 template<class VIC>
4228 forceinline bool
4230 return Support::marked(b.fwd);
4231 }
4232
4233 template<class VIC>
4236 assert(copied());
4237 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4238 }
4239
4240 template<class VIC>
4242 VarImp<VIC>::next(void) const {
4243 assert(copied());
4244 return u.next;
4245 }
4246
4247 template<class VIC>
4250#ifdef GECODE_HAS_CBS
4251 : var_id(x.var_id)
4252#endif
4253 {
4254 VarImpBase** reg;
4255 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4256 if (x.b.base == NULL) {
4257 // Variable implementation needs no index structure
4258 reg = &home.pc.c.vars_noidx;
4259 assert(x.degree() == 0);
4260 } else {
4261 reg = &home.pc.c.vars_u[idx_c];
4262 }
4263 // Save subscriptions in copy
4264 b.base = x.b.base;
4265 entries = x.entries;
4266 for (PropCond pc=1; pc<pc_max+2; pc++)
4267 idx(pc) = x.idx(pc);
4268
4269 // Set forwarding pointer
4270 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4271 // Register original
4272 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4273 }
4274
4275 template<class VIC>
4278 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4279 }
4280
4281 template<class VIC>
4284 return static_cast<ModEventDelta>(me << VIC::med_fst);
4285 }
4286
4287 template<class VIC>
4290 return VIC::me_combine(me1,me2);
4291 }
4292
4293 template<class VIC>
4294 forceinline void
4296 bool force) {
4297 if (VIC::med_update(p.u.med,me) || force)
4298 home.enqueue(&p);
4299 }
4300
4301 template<class VIC>
4302 forceinline void
4304 ActorLink** b = actor(pc1);
4305 ActorLink** p = actorNonZero(pc2+1);
4306 while (p-- > b)
4307 schedule(home,*Propagator::cast(*p),me);
4308 }
4309
4310 template<class VIC>
4311 forceinline void
4312 VarImp<VIC>::resize(Space& home) {
4313 if (b.base == NULL) {
4314 assert((free_and_bits >> free_bits) == 0);
4315 // Create fresh dependency array with four entries
4316 free_and_bits += 4 << free_bits;
4317 b.base = home.alloc<ActorLink*>(4);
4318 for (int i=0; i<pc_max+1; i++)
4319 u.idx[i] = 0;
4320 } else {
4321 // Resize dependency array
4322 unsigned int n = degree();
4323 // Find out whether the area is most likely in the special area
4324 // reserved for subscriptions. If yes, just resize mildly otherwise
4325 // more agressively
4326 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4327 unsigned int m =
4328 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4329 (n+4) : ((n+1)*3>>1);
4330 ActorLink** prop = home.alloc<ActorLink*>(m);
4331 free_and_bits += (m-n) << free_bits;
4332 // Copy entries
4333 Heap::copy<ActorLink*>(prop, b.base, n);
4334 home.free<ActorLink*>(b.base,n);
4335 b.base = prop;
4336 }
4337 }
4338
4339 template<class VIC>
4340 forceinline void
4341 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4342 assert(pc <= pc_max);
4343 // Count one new subscription
4344 home.pc.p.n_sub += 1;
4345 if ((free_and_bits >> free_bits) == 0)
4346 resize(home);
4347 free_and_bits -= 1 << free_bits;
4348
4349 // Enter subscription
4350 b.base[entries] = *actorNonZero(pc_max+1);
4351 entries++;
4352 for (PropCond j = pc_max; j > pc; j--) {
4353 *actorNonZero(j+1) = *actorNonZero(j);
4354 idx(j+1)++;
4355 }
4356 *actorNonZero(pc+1) = *actor(pc);
4357 idx(pc+1)++;
4358 *actor(pc) = ActorLink::cast(p);
4359
4360#ifdef GECODE_AUDIT
4361 ActorLink** f = actor(pc);
4362 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4363 if (*f == p)
4364 goto found;
4365 else
4366 f++;
4368 found: ;
4369#endif
4370 }
4371
4372 template<class VIC>
4373 forceinline void
4374 VarImp<VIC>::enter(Space& home, Advisor* a) {
4375 // Note that a might be a marked pointer
4376 // Count one new subscription
4377 home.pc.p.n_sub += 1;
4378 if ((free_and_bits >> free_bits) == 0)
4379 resize(home);
4380 free_and_bits -= 1 << free_bits;
4381
4382 // Enter subscription
4383 b.base[entries++] = *actorNonZero(pc_max+1);
4384 *actorNonZero(pc_max+1) = a;
4385 }
4386
4387 template<class VIC>
4388 forceinline void
4390 bool assigned, ModEvent me, bool schedule) {
4391 if (assigned) {
4392 // Do not subscribe, just schedule the propagator
4393 if (schedule)
4395 } else {
4396 enter(home,&p,pc);
4397 // Schedule propagator
4398 if (schedule && (pc != PC_GEN_ASSIGNED))
4399 VarImp<VIC>::schedule(home,p,me);
4400 }
4401 }
4402
4403 template<class VIC>
4404 forceinline void
4405 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4406 if (!assigned) {
4407 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4408 enter(home,ma);
4409 }
4410 }
4411
4412 template<class VIC>
4413 forceinline void
4415 bool assigned, ModEvent me) {
4416 if (assigned)
4418 else if (pc != PC_GEN_ASSIGNED)
4419 VarImp<VIC>::schedule(home,p,me);
4420 }
4421
4422 template<class VIC>
4423 void
4424 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
4425 assert(pc <= pc_max);
4426 ActorLink* a = ActorLink::cast(p);
4427 // Find actor in dependency array
4428 ActorLink** f = actor(pc);
4429#ifdef GECODE_AUDIT
4430 while (f < actorNonZero(pc+1))
4431 if (*f == a)
4432 goto found;
4433 else
4434 f++;
4436 found: ;
4437#else
4438 while (*f != a) f++;
4439#endif
4440 // Remove actor
4441 *f = *(actorNonZero(pc+1)-1);
4442 for (PropCond j = pc+1; j< pc_max+1; j++) {
4443 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4444 idx(j)--;
4445 }
4446 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4447 idx(pc_max+1)--;
4448 entries--;
4449 free_and_bits += 1 << free_bits;
4450 home.pc.p.n_sub -= 1;
4451 }
4452
4453 template<class VIC>
4454 forceinline void
4456 if (b.base != NULL)
4457 remove(home,&p,pc);
4458 }
4459
4460 template<class VIC>
4461 void
4462 VarImp<VIC>::remove(Space& home, Advisor* a) {
4463 // Note that a might be a marked pointer
4464 // Find actor in dependency array
4465 ActorLink** f = actorNonZero(pc_max+1);
4466#ifdef GECODE_AUDIT
4467 while (f < b.base+entries)
4468 if (*f == a)
4469 goto found;
4470 else
4471 f++;
4473 found: ;
4474#else
4475 while (*f != a) f++;
4476#endif
4477 // Remove actor
4478 *f = b.base[--entries];
4479 free_and_bits += 1 << free_bits;
4480 home.pc.p.n_sub -= 1;
4481 }
4482
4483 template<class VIC>
4484 forceinline void
4486 if (b.base != NULL) {
4487 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4488 remove(home,ma);
4489 }
4490 }
4491
4492 template<class VIC>
4493 forceinline void
4495 unsigned int n_sub = degree();
4496 home.pc.p.n_sub -= n_sub;
4497 unsigned int n = (free_and_bits >> free_bits) + n_sub;
4498 home.free<ActorLink*>(b.base,n);
4499 // Must be NULL such that cloning works
4500 b.base = NULL;
4501 // Must be 0 such that degree works
4502 entries = 0;
4503 // Must be NULL such that afc works
4504 for (PropCond pc=1; pc<pc_max+2; pc++)
4505 idx(pc) = 0;
4506 free_and_bits &= (1 << free_bits) - 1;
4507 }
4508
4509 template<class VIC>
4510 forceinline bool
4512 /*
4513 * An advisor that is executed might remove itself due to subsumption.
4514 * As entries are removed from front to back, the advisors must
4515 * be iterated in forward direction.
4516 */
4517 ActorLink** la = actorNonZero(pc_max+1);
4518 ActorLink** le = b.base+entries;
4519 if (la == le)
4520 return true;
4521 d.me = me;
4522 // An advisor that is run, might be removed during execution.
4523 // As removal is done from the back the advisors have to be executed
4524 // in inverse order.
4525 do {
4526 Advisor* a = Advisor::cast
4527 (static_cast<ActorLink*>(Support::funmark(*la)));
4528 assert(!a->disposed());
4529 Propagator& p = a->propagator();
4530 switch (p.advise(home,*a,d)) {
4531 case ES_FIX:
4532 break;
4533 case ES_FAILED:
4534 return false;
4535 case ES_NOFIX:
4536 schedule(home,p,me);
4537 break;
4538 case ES_NOFIX_FORCE:
4539 schedule(home,p,me,true);
4540 break;
4541 case __ES_SUBSUMED:
4542 default:
4544 }
4545 } while (++la < le);
4546 return true;
4547 }
4548
4549 template<class VIC>
4550 void
4551 VarImp<VIC>::_fail(Space& home) {
4552 /*
4553 * An advisor that is executed might remove itself due to subsumption.
4554 * As entries are removed from front to back, the advisors must
4555 * be iterated in forward direction.
4556 */
4557 ActorLink** la = actorNonZero(pc_max+1);
4558 ActorLink** le = b.base+entries;
4559 if (la == le)
4560 return;
4561 // An advisor that is run, might be removed during execution.
4562 // As removal is done from the back the advisors have to be executed
4563 // in inverse order.
4564 do {
4565 if (Support::marked(*la)) {
4566 Advisor* a = Advisor::cast(static_cast<ActorLink*>
4567 (Support::unmark(*la)));
4568 assert(!a->disposed());
4569 Propagator& p = a->propagator();
4570 p.advise(home,*a);
4571 }
4572 } while (++la < le);
4573 }
4574
4575 template<class VIC>
4576 ModEvent
4578 _fail(home);
4579 return ME_GEN_FAILED;
4580 }
4581
4582 template<class VIC>
4583 forceinline void
4584 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
4585 // this refers to the variable to be updated (clone)
4586 // x refers to the original
4587 // Recover from copy
4588 x->b.base = b.base;
4589 x->u.idx[0] = u.idx[0];
4590 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4591 x->u.idx[1] = u.idx[1];
4592
4593 unsigned int np =
4594 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4595 unsigned int na =
4596 static_cast<unsigned int >(x->b.base + x->entries -
4597 x->actorNonZero(pc_max+1));
4598 unsigned int n = na + np;
4599 assert(n == x->degree());
4600
4601 ActorLink** f = x->b.base;
4602 ActorLink** t = sub;
4603
4604 sub += n;
4605 b.base = t;
4606 // Process propagator subscriptions
4607 while (np >= 4) {
4608 ActorLink* p3 = f[3]->prev();
4609 ActorLink* p0 = f[0]->prev();
4610 ActorLink* p1 = f[1]->prev();
4611 ActorLink* p2 = f[2]->prev();
4612 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4613 np -= 4; t += 4; f += 4;
4614 }
4615 if (np >= 2) {
4616 ActorLink* p0 = f[0]->prev();
4617 ActorLink* p1 = f[1]->prev();
4618 t[0] = p0; t[1] = p1;
4619 np -= 2; t += 2; f += 2;
4620 }
4621 if (np > 0) {
4622 ActorLink* p0 = f[0]->prev();
4623 t[0] = p0;
4624 t += 1; f += 1;
4625 }
4626 // Process advisor subscriptions
4627 while (na >= 4) {
4628 ptrdiff_t m0, m1, m2, m3;
4629 ActorLink* p3 =
4630 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4631 ActorLink* p0 =
4632 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4633 ActorLink* p1 =
4634 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4635 ActorLink* p2 =
4636 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4637 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4638 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4639 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4640 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4641 na -= 4; t += 4; f += 4;
4642 }
4643 if (na >= 2) {
4644 ptrdiff_t m0, m1;
4645 ActorLink* p0 =
4646 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4647 ActorLink* p1 =
4648 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4649 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4650 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4651 na -= 2; t += 2; f += 2;
4652 }
4653 if (na > 0) {
4654 ptrdiff_t m0;
4655 ActorLink* p0 =
4656 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4657 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4658 }
4659 }
4660
4661 template<class VIC>
4662 forceinline void
4663 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4664 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4665 while (x != NULL) {
4666 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4667 }
4668 }
4669
4670
4671
4672 /*
4673 * Variable disposer
4674 *
4675 */
4676 template<class VarImp>
4678#ifdef GECODE_HAS_VAR_DISPOSE
4679 Space::vd[VarImp::idx_d] = this;
4680#endif
4681 }
4682
4683 template<class VarImp>
4684 void
4686 VarImp* x = static_cast<VarImp*>(_x);
4687 do {
4688 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4689 } while (x != NULL);
4690 }
4691
4692 /*
4693 * Statistics
4694 */
4695
4696 forceinline void
4698 propagate = 0;
4699 }
4706 propagate += s.propagate;
4707 return *this;
4708 }
4711 StatusStatistics t(s);
4712 return t += *this;
4713 }
4714
4715 forceinline void
4717
4725 return s;
4726 }
4729 return *this;
4730 }
4731
4732 forceinline void
4734
4742 return s;
4743 }
4746 return *this;
4747 }
4748
4749 /*
4750 * Cost computation
4751 *
4752 */
4753
4755 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4756
4757 forceinline PropCost
4758 PropCost::cost(PropCost::Mod m,
4760 unsigned int n) {
4761 if (n < 2)
4762 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4763 else if (n == 2)
4764 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4765 else if (n == 3)
4766 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4767 else
4768 return (m == LO) ? lo : hi;
4769 }
4770
4773 return AC_RECORD;
4774 }
4776 PropCost::crazy(PropCost::Mod m, unsigned int n) {
4777 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4778 }
4781 assert(n >= 0);
4782 return crazy(m,static_cast<unsigned int>(n));
4783 }
4785 PropCost::cubic(PropCost::Mod m, unsigned int n) {
4786 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4787 }
4790 assert(n >= 0);
4791 return cubic(m,static_cast<unsigned int>(n));
4792 }
4795 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4796 }
4799 assert(n >= 0);
4800 return quadratic(m,static_cast<unsigned int>(n));
4801 }
4803 PropCost::linear(PropCost::Mod m, unsigned int n) {
4804 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4805 }
4808 assert(n >= 0);
4809 return linear(m,static_cast<unsigned int>(n));
4810 }
4813 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4814 }
4817 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4818 }
4821 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4822 }
4823
4824 /*
4825 * Iterators for propagators and branchers of a space
4826 *
4827 */
4830 : home(home0), q(home.pc.p.active) {
4831 while (q >= &home.pc.p.queue[0]) {
4832 if (q->next() != q) {
4833 c = q->next(); e = q; q--;
4834 return;
4835 }
4836 q--;
4837 }
4838 q = NULL;
4839 if (!home.pl.empty()) {
4840 c = Propagator::cast(home.pl.next());
4841 e = Propagator::cast(&home.pl);
4842 } else {
4843 c = e = NULL;
4844 }
4845 }
4846 forceinline bool
4848 return c != NULL;
4849 }
4850 forceinline void
4852 c = c->next();
4853 if (c == e) {
4854 if (q == NULL) {
4855 c = NULL;
4856 } else {
4857 while (q >= &home.pc.p.queue[0]) {
4858 if (q->next() != q) {
4859 c = q->next(); e = q; q--;
4860 return;
4861 }
4862 q--;
4863 }
4864 q = NULL;
4865 if (!home.pl.empty()) {
4866 c = Propagator::cast(home.pl.next());
4867 e = Propagator::cast(&home.pl);
4868 } else {
4869 c = NULL;
4870 }
4871 }
4872 }
4873 }
4876 return *Propagator::cast(c);
4877 }
4878
4879
4882 : home(home0), q(home.pc.p.active) {
4883 while (q >= &home.pc.p.queue[0]) {
4884 if (q->next() != q) {
4885 c = q->next(); e = q; q--;
4886 return;
4887 }
4888 q--;
4889 }
4890 q = c = e = NULL;
4891 }
4892 forceinline bool
4894 return c != NULL;
4895 }
4896 forceinline void
4898 c = c->next();
4899 if (c == e) {
4900 if (q == NULL) {
4901 c = NULL;
4902 } else {
4903 while (q >= &home.pc.p.queue[0]) {
4904 if (q->next() != q) {
4905 c = q->next(); e = q; q--;
4906 return;
4907 }
4908 q--;
4909 }
4910 q = c = e = NULL;
4911 }
4912 }
4913 }
4916 return *Propagator::cast(c);
4917 }
4918
4919
4922 c = Propagator::cast(home.pl.next());
4923 e = Propagator::cast(&home.pl);
4924 }
4925 forceinline bool
4927 return c != e;
4928 }
4929 forceinline void
4931 c = c->next();
4932 }
4935 return *Propagator::cast(c);
4936 }
4937
4938
4941 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4942 forceinline bool
4944 return c != e;
4945 }
4946 forceinline void
4948 c = c->next();
4949 }
4952 return *Brancher::cast(c);
4953 }
4954
4955
4956 /*
4957 * Groups of actors
4958 */
4960 Group::Group(unsigned int gid0) : gid(gid0) {}
4961
4962 forceinline bool
4963 Group::in(Group actor) const {
4964 return (gid == GROUPID_ALL) || (gid == actor.gid);
4965 }
4966
4967 forceinline bool
4968 Group::in(void) const {
4969 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
4970 }
4971
4973 Group::Group(const Group& g) : gid(g.gid) {}
4974
4977 gid=g.gid; return *this;
4978 }
4979
4980 forceinline unsigned int
4981 Group::id(void) const {
4982 return gid;
4983 }
4984
4985
4988
4992
4996
4999 return static_cast<PropagatorGroup&>(Group::operator =(g));
5000 }
5001
5004 return Home(home,NULL,*this,BrancherGroup::def);
5005 }
5006
5007 forceinline bool
5009 return id() == g.id();
5010 }
5011 forceinline bool
5013 return id() != g.id();
5014 }
5015
5018 if (id() != GROUPID_ALL)
5019 p.group(*this);
5020 return *this;
5021 }
5022
5023
5026
5029 : Group(gid) {}
5030
5034
5037 return static_cast<BrancherGroup&>(Group::operator =(g));
5038 }
5039
5042 return Home(home,NULL,PropagatorGroup::def,*this);
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 /*
5063 * Iterators for propagators and branchers in a group
5064 *
5065 */
5068 : ps(const_cast<Space&>(home)), g(g0) {
5069 while (ps() && !g.in(ps.propagator().group()))
5070 ++ps;
5071 }
5072 forceinline bool
5074 return ps();
5075 }
5076 forceinline void
5078 do
5079 ++ps;
5080 while (ps() && !g.in(ps.propagator().group()));
5081 }
5082 forceinline const Propagator&
5084 return ps.propagator();
5085 }
5086
5089 : bs(const_cast<Space&>(home)), g(g0) {
5090 while (bs() && !g.in(bs.brancher().group()))
5091 ++bs;
5092 }
5093 forceinline bool
5095 return bs();
5096 }
5097 forceinline void
5099 do
5100 ++bs;
5101 while (bs() && !g.in(bs.brancher().group()));
5102 }
5103 forceinline const Brancher&
5105 return bs.brancher();
5106 }
5107
5108
5109 /*
5110 * Space construction support
5111 *
5112 */
5113 template<class T>
5114 forceinline T&
5116 return alloc<T>(1);
5117 }
5118 template<class T, typename A1>
5119 forceinline T&
5120 Space::construct(A1 const& a1) {
5121 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5122 new (&t) T(a1);
5123 return t;
5124 }
5125 template<class T, typename A1, typename A2>
5126 forceinline T&
5127 Space::construct(A1 const& a1, A2 const& a2) {
5128 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5129 new (&t) T(a1,a2);
5130 return t;
5131 }
5132 template<class T, typename A1, typename A2, typename A3>
5133 forceinline T&
5134 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5135 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5136 new (&t) T(a1,a2,a3);
5137 return t;
5138 }
5139 template<class T, typename A1, typename A2, typename A3, typename A4>
5140 forceinline T&
5141 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5142 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5143 new (&t) T(a1,a2,a3,a4);
5144 return t;
5145 }
5146 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5147 forceinline T&
5148 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5149 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5150 new (&t) T(a1,a2,a3,a4,a5);
5151 return t;
5152 }
5153
5154}
5155
5156// STATISTICS: kernel-core
Class for AFC (accumulated failure count) management.
Definition afc.hpp:40
Base-class for both propagators and branchers.
Definition core.hpp:628
friend class Space
Definition core.hpp:630
friend class LocalObject
Definition core.hpp:634
friend class ActorLink
Definition core.hpp:629
friend class VarImp
Definition core.hpp:635
friend class Advisor
Definition core.hpp:632
friend class Propagator
Definition core.hpp:631
friend class Brancher
Definition core.hpp:633
virtual Actor * copy(Space &home)=0
Create copy.
friend class Council
Definition core.hpp:636
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
Base-class for advisors.
Definition core.hpp:1294
friend class SubscribedPropagators
Definition core.hpp:1298
Propagator & propagator(void) const
Return the advisor's propagator.
Definition core.hpp:3864
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3838
friend class VarImp
Definition core.hpp:1295
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:3871
friend class Advisors
Definition core.hpp:1297
friend class Council
Definition core.hpp:1296
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
Definition core.hpp:3881
Class to iterate over advisors of a council.
Definition core.hpp:1268
Advisors(const Council< A > &c)
Initialize.
Definition core.hpp:3995
bool operator()(void) const
Test whether there advisors left.
Definition core.hpp:4003
void operator++(void)
Move iterator to next advisor.
Definition core.hpp:4009
A & advisor(void) const
Return advisor.
Definition core.hpp:4017
static const int idx_c
Index for cloning.
Definition var-type.hpp:459
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition var-type.hpp:889
Archive representation
Definition archive.hpp:42
Group of branchers.
Definition core.hpp:799
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition core.cpp:1034
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition core.hpp:850
static BrancherGroup all
Group of all branchers.
Definition core.hpp:847
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition core.hpp:5036
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition core.cpp:1011
BrancherGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:5028
friend class Brancher
Definition core.hpp:800
Home operator()(Space &home)
To augment a space argument.
Definition core.hpp:5041
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition core.hpp:5050
void kill(Space &home)
Kill all branchers in a group.
Definition core.cpp:1045
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition core.hpp:5046
BrancherGroup(void)
Constructor.
Definition core.hpp:5025
Base-class for branchers.
Definition core.hpp:1444
virtual const Choice * choice(Space &home)=0
Return choice.
friend class Space
Definition core.hpp:1446
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int a)=0
Commit for choice c and alternative a.
friend class ActorLink
Definition core.hpp:1445
unsigned int id(void) const
Return brancher id.
Definition core.hpp:3636
virtual const Choice * choice(const Space &home, Archive &e)=0
Return choice from e.
BrancherGroup group(void) const
Return group brancher belongs to.
Definition core.hpp:3641
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
Definition core.cpp:92
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3612
friend class Choice
Definition core.hpp:1447
void operator++(void)
Move iterator to next brancher.
Definition core.hpp:5098
const Brancher & brancher(void) const
Return propagator.
Definition core.hpp:5104
bool operator()(void) const
Test whether there are branchers left.
Definition core.hpp:5094
Branchers(const Space &home, BrancherGroup g)
Initialize.
Definition core.hpp:5088
Choice for performing commit
Definition core.hpp:1414
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition core.hpp:3773
friend class Space
Definition core.hpp:1415
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:892
virtual ~Choice(void)
Destructor.
Definition core.hpp:3787
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3777
Statistics for execution of clone
Definition core.hpp:1711
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition core.hpp:4723
void reset(void)
Reset information.
Definition core.hpp:4716
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition core.hpp:4728
CloneStatistics(void)
Initialize.
Definition core.hpp:4719
Statistics for execution of commit
Definition core.hpp:1727
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition core.hpp:4745
void reset(void)
Reset information.
Definition core.hpp:4733
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition core.hpp:4740
CommitStatistics(void)
Initialize.
Definition core.hpp:4736
Commit trace information.
Definition core.hpp:1007
BrancherGroup group(void) const
Return brancher group.
Definition core.hpp:3419
friend class Space
Definition core.hpp:1008
unsigned int alternative(void) const
Return alternative.
Definition core.hpp:3431
const Brancher & b
Brancher.
Definition core.hpp:1011
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
Definition core.hpp:3411
unsigned int id(void) const
Return brancher identifier.
Definition core.hpp:3415
unsigned int a
Alternative.
Definition core.hpp:1015
const Choice & c
Choice.
Definition core.hpp:1013
const Choice & choice(void) const
Return choice.
Definition core.hpp:3427
const Brancher & brancher(void) const
Return brancher.
Definition core.hpp:3423
Council of advisors
Definition core.hpp:1243
bool empty(void) const
Test whether council has advisor left.
Definition core.hpp:3923
void update(Space &home, Council< A > &c)
Update during cloning (copies all advisors)
Definition core.hpp:3933
void dispose(Space &home)
Dispose council.
Definition core.hpp:3978
friend class Advisor
Definition core.hpp:1244
Council(void)
Default constructor.
Definition core.hpp:3914
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
friend class VarImp
Definition core.hpp:205
Base-class for freelist-managed objects.
Definition manager.hpp:98
Group baseclass for controlling actors.
Definition core.hpp:673
static Group all
Group of all actors.
Definition core.hpp:717
static Group def
Group of actors not in any user-defined group.
Definition core.hpp:720
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition core.hpp:683
Group(void)
Constructor.
Definition core.cpp:922
bool in(void) const
Check whether this is a real group (and not just default)
Definition core.hpp:4968
friend class CommitTraceInfo
Definition core.hpp:679
static Support::Mutex m
Mutex for protection.
Definition core.hpp:695
friend class PostTraceInfo
Definition core.hpp:680
static const unsigned int GROUPID_MAX
The maximal group number.
Definition core.hpp:687
Group & operator=(const Group &g)
Assignment operator.
Definition core.hpp:4976
unsigned int id(void) const
Return a unique id for the group.
Definition core.hpp:4981
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition core.hpp:685
unsigned int gid
The group id.
Definition core.hpp:689
friend class Propagator
Definition core.hpp:675
friend class Brancher
Definition core.hpp:676
static unsigned int next
Next group id.
Definition core.hpp:692
friend class PropagateTraceInfo
Definition core.hpp:678
Group(unsigned int gid0)
Construct with predefined group id gid0.
Definition core.hpp:4960
friend class Home
Definition core.hpp:674
friend class ViewTraceInfo
Definition core.hpp:677
Base class for heap allocated objects.
Definition heap.hpp:340
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:583
Home class for posting propagators
Definition core.hpp:856
PropagatorGroup pg
A propagator group.
Definition core.hpp:864
BrancherGroup branchergroup(void) const
Return brancher group.
Definition core.hpp:3314
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3223
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:3266
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition core.hpp:862
Space & s
The space where the propagator is to be posted.
Definition core.hpp:860
void fail(void)
Mark space as failed.
Definition core.hpp:4046
BrancherGroup bg
A brancher group.
Definition core.hpp:866
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition core.hpp:3306
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition core.hpp:3310
friend class PostInfo
Definition core.hpp:857
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition core.hpp:3282
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4055
Home & operator=(const Home &h)
Assignment operator.
Definition core.hpp:3273
Class for storing propagator information.
Definition gpi.hpp:42
unsigned int gid
Group identifier.
Definition gpi.hpp:47
Manage memory for space.
Definition manager.hpp:120
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition manager.hpp:297
Class to store data shared among several spaces.
Handles for local (space-shared) objects.
Definition core.hpp:1560
LocalHandle(void)
Create local handle pointing to NULL object.
Definition core.hpp:3746
~LocalHandle(void)
Destructor.
Definition core.hpp:3757
void update(Space &home, LocalHandle &lh)
Updating during cloning.
Definition core.hpp:3763
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition core.hpp:3752
LocalObject * object(void) const
Access to the local object.
Definition core.hpp:3759
Local (space-shared) object.
Definition core.hpp:1535
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition core.hpp:3712
friend class Space
Definition core.hpp:1537
LocalObject * fwd(Space &home)
Return forwarding pointer.
Definition core.hpp:3739
friend class ActorLink
Definition core.hpp:1536
LocalObject(Home home)
Constructor for creation.
Definition core.hpp:3728
friend class LocalHandle
Definition core.hpp:1538
Information passed by meta search engines.
Definition core.hpp:1615
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition core.hpp:3110
unsigned long int fail(void) const
Return number of failures since last restart.
Definition core.hpp:3100
Type
Which type of information is provided.
Definition core.hpp:1618
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1622
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1620
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition core.hpp:3095
const Type t
Type of information.
Definition core.hpp:1626
unsigned int asset(void) const
Return number of asset in portfolio.
Definition core.hpp:3115
const Space * l
Last solution found.
Definition core.hpp:1636
unsigned long int restart(void) const
Return number of restarts.
Definition core.hpp:3090
const Space * last(void) const
Return last solution found (possibly NULL)
Definition core.hpp:3105
const unsigned long int r
Number of restarts.
Definition core.hpp:1630
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:3074
const unsigned int a
Number of asset in portfolio.
Definition core.hpp:1643
const NoGoods & ng
No-goods from restart.
Definition core.hpp:1638
const unsigned long int f
Number of failures since last restart.
Definition core.hpp:1634
Type type(void) const
Return type of information.
Definition core.hpp:3086
const unsigned long int s
Number of solutions since last restart.
Definition core.hpp:1632
No-good literal recorded during search.
Definition core.hpp:1342
bool leaf(void) const
Test whether literal is a leaf.
Definition core.hpp:3796
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual void cancel(Space &home, Propagator &p)=0
Cancel propagator p from all views of the no-good literal.
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
NGL(void)
Constructor for creation.
Definition core.hpp:3819
virtual NGL * copy(Space &home)=0
Create copy.
Status
The status of a no-good literal.
Definition core.hpp:1348
@ SUBSUMED
The literal is subsumed.
Definition core.hpp:1350
@ FAILED
The literal is failed.
Definition core.hpp:1349
@ NONE
The literal is neither failed nor subsumed.
Definition core.hpp:1351
virtual void reschedule(Space &home, Propagator &p)=0
Schedule propagator p for all views of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition core.hpp:3800
virtual size_t dispose(Space &home)
Dispose.
Definition core.hpp:3828
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition core.hpp:3812
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition core.cpp:897
No-goods recorded from restarts.
Definition core.hpp:1590
virtual void post(Space &home) const
Post no-goods.
Definition core.cpp:82
static NoGoods eng
Empty no-goods.
Definition core.hpp:1608
virtual ~NoGoods(void)
Destructor.
Definition core.hpp:3067
NoGoods(void)
Initialize.
Definition core.hpp:3056
unsigned long int ng(void) const
Return number of no-goods posted.
Definition core.hpp:3059
unsigned long int n
Number of no-goods.
Definition core.hpp:1593
Configuration class for variable implementations without index structure.
Definition core.hpp:98
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition core.hpp:125
static const int free_bits
Freely available bits.
Definition core.hpp:107
static const int idx_c
Index for update.
Definition core.hpp:101
static const int med_fst
Start of bits for modification event delta.
Definition core.hpp:109
static const int med_lst
End of bits for modification event delta.
Definition core.hpp:111
static const PropCond pc_max
Maximal propagation condition.
Definition core.hpp:105
static const int idx_d
Index for disposal.
Definition core.hpp:103
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition core.hpp:121
static const int med_mask
Bitmask for modification event delta.
Definition core.hpp:113
Class to set group information when a post function is executed.
Definition core.hpp:950
Space & h
The home space.
Definition core.hpp:954
friend class Space
Definition core.hpp:951
PostInfo(Home home)
Set information.
Definition core.hpp:3363
bool nested
Whether it is used nested.
Definition core.hpp:960
unsigned int pid
Next free propagator id.
Definition core.hpp:958
PropagatorGroup pg
The propagator group.
Definition core.hpp:956
~PostInfo(void)
Reset information.
Definition core.hpp:3371
Post trace information.
Definition core.hpp:1034
unsigned int propagators(void) const
Return number of posted propagators.
Definition core.hpp:3452
friend class Space
Definition core.hpp:1035
PropagatorGroup group(void) const
Return propagator group.
Definition core.hpp:3444
PropagatorGroup g
Propagator group.
Definition core.hpp:1046
Status
Post status.
Definition core.hpp:1039
@ SUBSUMED
Propagator not posted as already subsumed.
Definition core.hpp:1042
@ FAILED
Posting failed.
Definition core.hpp:1041
@ POSTED
Propagator was posted.
Definition core.hpp:1040
Status status(void) const
Return post status.
Definition core.hpp:3448
friend class PostInfo
Definition core.hpp:1036
PostTraceInfo(PropagatorGroup g, Status s, unsigned int n)
Initialize.
Definition core.hpp:3441
Status s
Status.
Definition core.hpp:1048
unsigned int n
Number of posted propagators.
Definition core.hpp:1050
Propagation cost.
Definition core.hpp:486
ActualCost ac
Actual cost.
Definition core.hpp:509
friend class Space
Definition core.hpp:487
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4820
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:4812
static PropCost record(void)
For recording information (no propagation allowed)
Definition core.hpp:4772
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition core.hpp:4776
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4794
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4803
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition core.hpp:4785
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:4816
Mod
Propagation cost modifier.
Definition core.hpp:512
@ HI
Expensive.
Definition core.hpp:514
ActualCost
The actual cost values that are used.
Definition core.hpp:490
@ AC_TERNARY_LO
Three variables, cheap.
Definition core.hpp:502
@ AC_TERNARY_HI
Three variables, expensive.
Definition core.hpp:500
@ AC_BINARY_LO
Two variables, cheap.
Definition core.hpp:503
@ AC_CUBIC_LO
Cubic complexity, cheap.
Definition core.hpp:494
@ AC_UNARY_HI
Only single variable, expensive.
Definition core.hpp:505
@ AC_RECORD
Reserved for recording information.
Definition core.hpp:491
@ AC_BINARY_HI
Two variables, expensive.
Definition core.hpp:501
@ AC_LINEAR_HI
Linear complexity, expensive.
Definition core.hpp:498
@ AC_CUBIC_HI
Cubic complexity, expensive.
Definition core.hpp:495
@ AC_MAX
Maximal cost value.
Definition core.hpp:506
@ AC_CRAZY_LO
Exponential complexity, cheap.
Definition core.hpp:492
@ AC_LINEAR_LO
Linear complexity, cheap.
Definition core.hpp:499
@ AC_UNARY_LO
Only single variable, cheap.
Definition core.hpp:504
@ AC_QUADRATIC_LO
Quadratic complexity, cheap.
Definition core.hpp:496
@ AC_CRAZY_HI
Exponential complexity, expensive.
Definition core.hpp:493
@ AC_QUADRATIC_HI
Quadratic complexity, expensive.
Definition core.hpp:497
Propagate trace information.
Definition core.hpp:971
unsigned int i
Propagator id.
Definition core.hpp:983
Status
Propagator status.
Definition core.hpp:975
@ SUBSUMED
Propagator is subsumed.
Definition core.hpp:979
@ FIX
Propagator computed fixpoint.
Definition core.hpp:976
@ NOFIX
Propagator did not compute fixpoint.
Definition core.hpp:977
@ FAILED
Propagator failed.
Definition core.hpp:978
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
Definition core.hpp:3385
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
Definition core.hpp:3397
unsigned int id(void) const
Return propagator identifier.
Definition core.hpp:3389
Status status(void) const
Return propagator status.
Definition core.hpp:3401
const Propagator * p
Propagator.
Definition core.hpp:987
PropagatorGroup g
Propagator group.
Definition core.hpp:985
PropagatorGroup group(void) const
Return propagator group.
Definition core.hpp:3393
Group of propagators.
Definition core.hpp:727
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition core.cpp:956
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition core.hpp:5008
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition core.hpp:792
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition core.cpp:933
friend class PostTraceInfo
Definition core.hpp:731
PropagatorGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:4990
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition core.hpp:5012
PropagatorGroup(void)
Constructor.
Definition core.hpp:4987
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition core.hpp:4998
friend class Propagator
Definition core.hpp:728
void disable(Space &home)
Disable all propagators in a group.
Definition core.cpp:980
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition core.cpp:989
Home operator()(Space &home)
To augment a space argument.
Definition core.hpp:5003
friend class PropagateTraceInfo
Definition core.hpp:730
void kill(Space &home)
Kill all propagators in a group.
Definition core.cpp:967
friend class ViewTraceInfo
Definition core.hpp:729
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:789
Base-class for propagators.
Definition core.hpp:1066
virtual void reschedule(Space &home)=0
Schedule function.
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1079
friend class SubscribedPropagators
Definition core.hpp:1072
friend class Space
Definition core.hpp:1068
double afc(void) const
Return the accumlated failure count.
Definition core.hpp:3532
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition core.cpp:67
friend class ActorLink
Definition core.hpp:1067
Kernel::GPI::Info & gpi(void)
Provide access to global propagator information.
Definition core.hpp:3500
unsigned int id(void) const
Return propagator id.
Definition core.hpp:3549
friend class VarImp
Definition core.hpp:1069
friend class Advisor
Definition core.hpp:1070
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition core.hpp:3554
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition core.hpp:3527
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition core.hpp:3478
friend class PropagatorGroup
Definition core.hpp:1073
friend class Council
Definition core.hpp:1071
bool disabled(void) const
Whether propagator is currently disabled.
Definition core.hpp:3483
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition core.hpp:1081
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:5073
const Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5083
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:5077
Propagators(const Space &home, PropagatorGroup g)
Initialize.
Definition core.hpp:5067
Class to iterate over branchers of a space.
Definition core.hpp:2739
Brancher & brancher(void) const
Return propagator.
Definition core.hpp:4951
void operator++(void)
Move iterator to next brancher.
Definition core.hpp:4947
Branchers(Space &home)
Initialize.
Definition core.hpp:4940
bool operator()(void) const
Test whether there are branchers left.
Definition core.hpp:4943
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:4930
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:4934
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:4926
IdlePropagators(Space &home)
Initialize.
Definition core.hpp:4921
Class to iterate over propagators of a space.
Definition core.hpp:2668
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:4847
Propagators(Space &home)
Initialize.
Definition core.hpp:4829
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:4851
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:4875
ScheduledPropagators(Space &home)
Initialize.
Definition core.hpp:4881
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:4915
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:4893
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:4897
Computation spaces.
Definition core.hpp:1744
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:2892
friend void trace(Home home, TraceFilter tf, int te, Tracer &t)
Create tracer.
Definition general.cpp:39
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@275070317317120154232063063134255170030071110047 p
Data only available during propagation or branching.
void * ralloc(size_t s)
Allocate memory on space heap.
Definition core.hpp:2803
double afc_decay(void) const
Return AFC decay factor.
Definition core.hpp:3246
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
void afc_unshare(void)
Unshare AFC information for all propagators.
Definition core.cpp:870
T & construct(void)
Construction routines.
Definition core.hpp:5115
friend class LocalObject
Definition core.hpp:1756
ActorLink queue[PropCost::AC_MAX+1]
Scheduled propagators according to cost.
Definition core.hpp:1834
LocalObject * local
Linked list of local objects.
Definition core.hpp:1854
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:2811
friend class VarImpDisposer
Definition core.hpp:1755
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition core.hpp:2807
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition core.hpp:1852
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition core.hpp:2826
friend class AFC
Definition core.hpp:1758
VarImpBase * vars_u[AllVarConf::idx_c]
Entries for updating variables.
Definition core.hpp:1850
friend class VarImp
Definition core.hpp:1754
friend class Advisor
Definition core.hpp:1752
friend class PostInfo
Definition core.hpp:1759
void afc_decay(double d)
Set AFC decay factor to d
Definition core.hpp:3251
friend class Propagator
Definition core.hpp:1746
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition core.hpp:2831
unsigned int n_sub
Number of subscriptions.
Definition core.hpp:1843
friend class PropagatorGroup
Definition core.hpp:1747
friend class Region
Definition core.hpp:1757
friend class Brancher
Definition core.hpp:1749
friend class Council
Definition core.hpp:1753
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
unsigned int bid_sc
Id of next brancher to be created plus status control.
Definition core.hpp:1841
friend class BrancherGroup
Definition core.hpp:1750
ActorLink * active
Cost level with next propagator to be executed.
Definition core.hpp:1832
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition core.hpp:2867
ViewTraceInfo vti
View trace information.
Definition core.hpp:1845
friend class Actor
Definition core.hpp:1745
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition core.hpp:3294
Statistics for execution of status
Definition core.hpp:1693
unsigned long int propagate
Number of propagator executions.
Definition core.hpp:1696
void reset(void)
Reset information.
Definition core.hpp:4697
StatusStatistics(void)
Initialize.
Definition core.hpp:4701
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition core.hpp:4710
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition core.hpp:4705
Iterator over subscribed propagators.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Exception: too many branchers
Definition exception.hpp:93
Trace filters.
Definition filter.hpp:133
Propagator for recording trace information.
Definition recorder.hpp:154
Base-class for variable implementations.
Definition core.hpp:172
Base class for Variable type disposer.
Definition core.hpp:180
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.cpp:47
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition core.hpp:4677
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.hpp:4685
Base-class for variable implementations.
Definition core.hpp:219
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition core.hpp:4389
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition core.hpp:4577
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition core.hpp:4494
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:4511
VarImp(void)
Creation of static instances.
Definition core.hpp:4144
friend class SubscribedPropagators
Definition core.hpp:223
friend class Space
Definition core.hpp:220
double afc(void) const
Return accumulated failure count (plus degree)
Definition core.hpp:4172
unsigned int bits(void) const
Provide access to free bits.
Definition core.hpp:4203
ActorLink ** base
Subscribed actors.
Definition core.hpp:233
bool copied(void) const
Is variable already copied.
Definition core.hpp:4229
friend class VarImpDisposer
Definition core.hpp:222
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition core.hpp:4414
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Definition core.hpp:4295
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition core.hpp:273
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition core.hpp:4235
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4277
VarImp * next(void) const
Return next copied variable.
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition core.hpp:4289
friend class Propagator
Definition core.hpp:221
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition core.hpp:4165
VarImp(Space &home)
Creation.
Definition core.hpp:4128
static ModEventDelta med(ModEvent me)
Definition core.hpp:4283
VarImp< VIC > * fwd
Forwarding pointer.
Definition core.hpp:242
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition core.hpp:275
static ModEvent modevent(const Delta &d)
Return modification event.
Definition core.hpp:4197
View trace information.
Definition core.hpp:910
What what(void) const
Return what is currently executing.
Definition core.hpp:3339
friend class Space
Definition core.hpp:911
const Brancher & brancher(void) const
Return currently executing brancher.
Definition core.hpp:3349
const Propagator & propagator(void) const
Return currently executing propagator.
Definition core.hpp:3343
void other(void)
Record that nothing is known at this point.
Definition core.hpp:3335
friend class PostInfo
Definition core.hpp:912
What
What is currently executing.
Definition core.hpp:915
@ BRANCHER
A brancher is executing.
Definition core.hpp:919
@ POST
A post function is executing.
Definition core.hpp:921
@ PROPAGATOR
A propagator is currently executing.
Definition core.hpp:917
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition core.hpp:3354
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Definition core.hpp:927
#define GECODE_KERNEL_REALLOC(T)
Definition core.hpp:2927
const int * pi[]
Definition photo.cpp:14262
void update(const NoOffset &)
Integer-precision integer scale view.
Definition view.hpp:638
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3583
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition core.hpp:3576
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition core.hpp:3564
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition core.hpp:3887
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:3901
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3894
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4081
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4051
ActorProperty
Actor properties.
Definition core.hpp:553
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:4066
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition core.hpp:4060
void fail(void)
Fail space.
Definition core.hpp:4037
@ AP_VIEW_TRACE
Definition core.hpp:573
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
@ AP_TRACE
Definition core.hpp:578
@ AP_WEAKLY
Definition core.hpp:568
Space(void)
Default constructor.
Definition core.cpp:115
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:864
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:842
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition core.cpp:846
virtual Space * copy(void)=0
Copying member function.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition core.hpp:3241
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:538
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3236
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:642
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3228
SpaceStatus
Space status
Definition core.hpp:1683
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1686
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1685
@ SS_FAILED
Space is failed
Definition core.hpp:1684
void print(const Search::Statistics &stat, bool restart)
Print statistics.
Definition job-shop.cpp:606
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode toplevel namespace
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition core.hpp:76
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition core.hpp:67
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition filter.cpp:131
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_NOFIX_FORCE
Advisor forces rescheduling of propagator.
Definition core.hpp:478
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Definition core.hpp:473
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Definition core.hpp:479
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition core.hpp:65
int PropCond
Type for propagation conditions.
Definition core.hpp:72
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition core.hpp:69
Post propagator for SetVar x
Definition set.hh:773
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition core.hpp:74
int ModEvent
Type for modification events.
Definition core.hpp:62
Gecode::FloatVal b(9, 12)
Gecode::FloatVal a(-8, 5)
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition macros.hpp:75
#define GECODE_VTABLE_EXPORT
Definition support.hh:72