this repo has no description
dekker.one
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
53 /**
54 * \defgroup TaskVarMEPC Generic modification events and propagation conditions
55 *
56 * Predefined modification events must be taken into account
57 * by variable types.
58 * \ingroup TaskVar
59 */
60 //@{
61 /// Type for modification events
62 typedef int ModEvent;
63
64 /// Generic modification event: failed variable
65 const ModEvent ME_GEN_FAILED = -1;
66 /// Generic modification event: no modification
67 const ModEvent ME_GEN_NONE = 0;
68 /// Generic modification event: variable is assigned a value
69 const ModEvent ME_GEN_ASSIGNED = 1;
70
71 /// Type for propagation conditions
72 typedef int PropCond;
73 /// Propagation condition to be ignored (convenience)
74 const PropCond PC_GEN_NONE = -1;
75 /// Propagation condition for an assigned variable
76 const PropCond PC_GEN_ASSIGNED = 0;
77 //@}
78
79 /**
80 * \brief Modification event deltas
81 *
82 * Modification event deltas are used by propagators. A
83 * propagator stores a modification event for each variable type.
84 * They can be accessed through a variable or a view from a given
85 * propagator. They can be constructed from a given modevent by
86 * a variable or view.
87 * \ingroup TaskActor
88 */
89 typedef int ModEventDelta;
90
91}
92
93#include <gecode/kernel/var-type.hpp>
94
95namespace Gecode {
96
97 /// Configuration class for variable implementations without index structure
98 class NoIdxVarImpConf {
99 public:
100 /// Index for update
101 static const int idx_c = -1;
102 /// Index for disposal
103 static const int idx_d = -1;
104 /// Maximal propagation condition
105 static const PropCond pc_max = PC_GEN_ASSIGNED;
106 /// Freely available bits
107 static const int free_bits = 0;
108 /// Start of bits for modification event delta
109 static const int med_fst = 0;
110 /// End of bits for modification event delta
111 static const int med_lst = 0;
112 /// Bitmask for modification event delta
113 static const int med_mask = 0;
114 /// Combine modification events \a me1 and \a me2
115 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
116 /// Update modification even delta \a med by \a me, return true on change
117 static bool med_update(ModEventDelta& med, ModEvent me);
118 };
119
120 forceinline ModEvent
121 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
122 GECODE_NEVER; return 0;
123 }
124 forceinline bool
125 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
126 GECODE_NEVER; return false;
127 }
128
129
130 /*
131 * These are the classes of interest
132 *
133 */
134 class ActorLink;
135 class Actor;
136 class Propagator;
137 class SubscribedPropagators;
138 class LocalObject;
139 class Advisor;
140 class AFC;
141 class Choice;
142 class Brancher;
143 class Group;
144 class PropagatorGroup;
145 class BrancherGroup;
146 class PostInfo;
147 class ViewTraceInfo;
148 class PropagateTraceInfo;
149 class CommitTraceInfo;
150 class PostTraceInfo;
151 class TraceRecorder;
152 class TraceFilter;
153 class Tracer;
154
155 template<class A> class Council;
156 template<class A> class Advisors;
157 template<class VIC> class VarImp;
158
159
160 /*
161 * Variable implementations
162 *
163 */
164
165 /**
166 * \brief Base-class for variable implementations
167 *
168 * Serves as base-class that can be used without having to know any
169 * template arguments.
170 * \ingroup TaskVar
171 */
172 class VarImpBase {};
173
174 /**
175 * \brief Base class for %Variable type disposer
176 *
177 * Controls disposal of variable implementations.
178 * \ingroup TaskVar
179 */
180 class GECODE_VTABLE_EXPORT VarImpDisposerBase {
181 public:
182 /// Dispose list of variable implementations starting at \a x
183 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
184 /// Destructor (not used)
185 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void);
186 };
187
188 /**
189 * \brief %Variable implementation disposer
190 *
191 * Controls disposal of variable implementations.
192 * \ingroup TaskVar
193 */
194 template<class VarImp>
195 class VarImpDisposer : public VarImpDisposerBase {
196 public:
197 /// Constructor (registers disposer with kernel)
198 VarImpDisposer(void);
199 /// Dispose list of variable implementations starting at \a x
200 virtual void dispose(Space& home, VarImpBase* x);
201 };
202
203 /// Generic domain change information to be supplied to advisors
204 class Delta {
205 template<class VIC> friend class VarImp;
206 private:
207 /// Modification event
208 ModEvent me;
209 };
210
211 /**
212 * \brief Base-class for variable implementations
213 *
214 * Implements variable implementation for variable implementation
215 * configuration of type \a VIC.
216 * \ingroup TaskVar
217 */
218 template<class VIC>
219 class VarImp : public VarImpBase {
220 friend class Space;
221 friend class Propagator;
222 template<class VarImp> friend class VarImpDisposer;
223 friend class SubscribedPropagators;
224 private:
225 union {
226 /**
227 * \brief Subscribed actors
228 *
229 * The base pointer of the array of subscribed actors.
230 *
231 * This pointer must be first to avoid padding on 64 bit machines.
232 */
233 ActorLink** base;
234 /**
235 * \brief Forwarding pointer
236 *
237 * During cloning, this is used as the forwarding pointer for the
238 * variable. The original value is saved in the copy and restored after
239 * cloning.
240 *
241 */
242 VarImp<VIC>* fwd;
243 } b;
244
245 /// Index for update
246 static const int idx_c = VIC::idx_c;
247 /// Index for disposal
248 static const int idx_d = VIC::idx_d;
249 /// Number of freely available bits
250 static const int free_bits = VIC::free_bits;
251 /// Number of used subscription entries
252 unsigned int entries;
253 /// Number of free subscription entries
254 unsigned int free_and_bits;
255 /// Maximal propagation condition
256 static const Gecode::PropCond pc_max = VIC::pc_max;
257#ifdef GECODE_HAS_CBS
258 /// Unique id for variable
259 const unsigned var_id;
260#endif
261
262 union {
263 /**
264 * \brief Indices of subscribed actors
265 *
266 * The entries from base[0] to base[idx[pc_max]] are propagators,
267 * where the entries between base[idx[pc-1]] and base[idx[pc]] are
268 * the propagators that have subscribed with propagation condition pc.
269 *
270 * The entries between base[idx[pc_max]] and base[idx[pc_max+1]] are the
271 * advisors subscribed to the variable implementation.
272 */
273 unsigned int idx[pc_max+1];
274 /// During cloning, points to the next copied variable
275 VarImp<VIC>* next;
276 } u;
277
278 /// Return subscribed actor at index \a pc
279 ActorLink** actor(PropCond pc);
280 /// Return subscribed actor at index \a pc, where \a pc is non-zero
281 ActorLink** actorNonZero(PropCond pc);
282 /// Return reference to index \a pc, where \a pc is non-zero
283 unsigned int& idx(PropCond pc);
284 /// Return index \a pc, where \a pc is non-zero
285 unsigned int idx(PropCond pc) const;
286
287 /**
288 * \brief Update copied variable \a x
289 *
290 * The argument \a sub gives the memory area where subscriptions are
291 * to be stored.
292 */
293 void update(VarImp* x, ActorLink**& sub);
294 /**
295 * \brief Update all copied variables of this type
296 *
297 * The argument \a sub gives the memory area where subscriptions are
298 * to be stored.
299 */
300 static void update(Space& home, ActorLink**& sub);
301
302 /// Enter propagator to subscription array
303 void enter(Space& home, Propagator* p, PropCond pc);
304 /// Enter advisor to subscription array
305 void enter(Space& home, Advisor* a);
306 /// Resize subscription array
307 void resize(Space& home);
308 /// Remove propagator from subscription array
309 void remove(Space& home, Propagator* p, PropCond pc);
310 /// Remove advisor from subscription array
311 void remove(Space& home, Advisor* a);
312
313
314 protected:
315 /// Cancel all subscriptions when variable implementation is assigned
316 void cancel(Space& home);
317 /**
318 * \brief Run advisors when variable implementation has been modified with modification event \a me and domain change \a d
319 *
320 * Returns false if an advisor has failed.
321 */
322 bool advise(Space& home, ModEvent me, Delta& d);
323 private:
324 /// Run advisors to be run on failure
325 void _fail(Space& home);
326 protected:
327 /// Run advisors to be run on failure and returns ME_GEN_FAILED
328 ModEvent fail(Space& home);
329#ifdef GECODE_HAS_VAR_DISPOSE
330 /// Return reference to variables (dispose)
331 static VarImp<VIC>* vars_d(Space& home);
332 /// %Set reference to variables (dispose)
333 static void vars_d(Space& home, VarImp<VIC>* x);
334#endif
335
336 public:
337 /// Creation
338 VarImp(Space& home);
339 /// Creation of static instances
340 VarImp(void);
341
342#ifdef GECODE_HAS_CBS
343 /// Return variable id
344 unsigned int id(void) const;
345#endif
346
347 /// \name Dependencies
348 //@{
349 /** \brief Subscribe propagator \a p with propagation condition \a pc
350 *
351 * In case \a schedule is false, the propagator is just subscribed but
352 * not scheduled for execution (this must be used when creating
353 * subscriptions during propagation).
354 *
355 * In case the variable is assigned (that is, \a assigned is
356 * true), the subscribing propagator is scheduled for execution.
357 * Otherwise, the propagator subscribes and is scheduled for execution
358 * with modification event \a me provided that \a pc is different
359 * from \a PC_GEN_ASSIGNED.
360 */
361 void subscribe(Space& home, Propagator& p, PropCond pc,
362 bool assigned, ModEvent me, bool schedule);
363 /// Cancel subscription of propagator \a p with propagation condition \a pc
364 void cancel(Space& home, Propagator& p, PropCond pc);
365 /** \brief Subscribe advisor \a a to variable
366 *
367 * The advisor \a a is only subscribed if \a assigned is false.
368 *
369 * If \a fail is true, the advisor \a a is also run when a variable
370 * operation triggers failure. This feature is undocumented.
371 *
372 */
373 void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
374 /// Cancel subscription of advisor \a a
375 void cancel(Space& home, Advisor& a, bool fail);
376
377 /**
378 * \brief Return degree (number of subscribed propagators and advisors)
379 *
380 * Note that the degree of a variable implementation is not available
381 * during cloning.
382 */
383 unsigned int degree(void) const;
384 /**
385 * \brief Return accumulated failure count (plus degree)
386 *
387 * Note that the accumulated failure count of a variable implementation
388 * is not available during cloning.
389 */
390 double afc(void) const;
391 //@}
392
393 /// \name Cloning variables
394 //@{
395 /// Constructor for cloning
396 VarImp(Space& home, VarImp& x);
397 /// Is variable already copied
398 bool copied(void) const;
399 /// Use forward pointer if variable already copied
400 VarImp* forward(void) const;
401 /// Return next copied variable
402 VarImp* next(void) const;
403 //@}
404
405 /// \name Variable implementation-dependent propagator support
406 //@{
407 /**
408 * \brief Schedule propagator \a p with modification event \a me
409 *
410 * If \a force is true, the propagator is re-scheduled (including
411 * cost computation) even though its modification event delta has
412 * not changed.
413 */
414 static void schedule(Space& home, Propagator& p, ModEvent me,
415 bool force = false);
416 /**
417 * \brief Schedule propagator \a p
418 *
419 * Schedules a propagator for propagation condition \a pc and
420 * modification event \a me. If the variable is assigned,
421 * the appropriate modification event is used for scheduling.
422 */
423 static void reschedule(Space& home, Propagator& p, PropCond pc,
424 bool assigned, ModEvent me);
425 /// Project modification event for this variable type from \a med
426 static ModEvent me(const ModEventDelta& med);
427 /// Translate modification event \a me into modification event delta
428 static ModEventDelta med(ModEvent me);
429 /// Combine modifications events \a me1 and \a me2
430 static ModEvent me_combine(ModEvent me1, ModEvent me2);
431 //@}
432
433 /// \name Delta information for advisors
434 //@{
435 /// Return modification event
436 static ModEvent modevent(const Delta& d);
437 //@}
438
439 /// \name Bit management
440 //@{
441 /// Provide access to free bits
442 unsigned int bits(void) const;
443 /// Provide access to free bits
444 unsigned int& bits(void);
445 //@}
446
447 protected:
448 /// Schedule subscribed propagators
449 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
450
451 public:
452 /// \name Memory management
453 //@{
454 /// Allocate memory from space
455 static void* operator new(size_t,Space&);
456 /// Return memory to space
457 static void operator delete(void*,Space&);
458 /// Needed for exceptions
459 static void operator delete(void*);
460 //@}
461 };
462
463
464 /**
465 * \defgroup TaskActorStatus Status of constraint propagation and branching commit
466 * Note that the enum values starting with a double underscore should not
467 * be used directly. Instead, use the provided functions with the same
468 * name without leading underscores.
469 *
470 * \ingroup TaskActor
471 */
472 enum ExecStatus {
473 ES_SUBSUMED_ = -2, ///< Internal: propagator is subsumed, do not use
474 ES_FAILED = -1, ///< Execution has resulted in failure
475 ES_NOFIX = 0, ///< Propagation has not computed fixpoint
476 ES_OK = 0, ///< Execution is okay
477 ES_FIX = 1, ///< Propagation has computed fixpoint
478 ES_NOFIX_FORCE = 2, ///< Advisor forces rescheduling of propagator
479 ES_PARTIAL_ = 2 ///< Internal: propagator has computed partial fixpoint, do not use
480 };
481
482 /**
483 * \brief Propagation cost
484 * \ingroup TaskActor
485 */
486 class PropCost {
487 friend class Space;
488 public:
489 /// The actual cost values that are used
490 enum ActualCost {
491 AC_RECORD = 0, ///< Reserved for recording information
492 AC_CRAZY_LO = 1, ///< Exponential complexity, cheap
493 AC_CRAZY_HI = 1, ///< Exponential complexity, expensive
494 AC_CUBIC_LO = 1, ///< Cubic complexity, cheap
495 AC_CUBIC_HI = 1, ///< Cubic complexity, expensive
496 AC_QUADRATIC_LO = 2, ///< Quadratic complexity, cheap
497 AC_QUADRATIC_HI = 2, ///< Quadratic complexity, expensive
498 AC_LINEAR_HI = 3, ///< Linear complexity, expensive
499 AC_LINEAR_LO = 4, ///< Linear complexity, cheap
500 AC_TERNARY_HI = 4, ///< Three variables, expensive
501 AC_BINARY_HI = 5, ///< Two variables, expensive
502 AC_TERNARY_LO = 5, ///< Three variables, cheap
503 AC_BINARY_LO = 6, ///< Two variables, cheap
504 AC_UNARY_LO = 6, ///< Only single variable, cheap
505 AC_UNARY_HI = 6, ///< Only single variable, expensive
506 AC_MAX = 6 ///< Maximal cost value
507 };
508 /// Actual cost
509 ActualCost ac;
510 public:
511 /// Propagation cost modifier
512 enum Mod {
513 LO, ///< Cheap
514 HI ///< Expensive
515 };
516 private:
517 /// Compute dynamic cost for cost \a lo, expensive cost \a hi, and size measure \a n
518 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
519 /// Constructor for automatic coercion of \a ac
520 PropCost(ActualCost ac);
521 public:
522 /// For recording information (no propagation allowed)
523 static PropCost record(void);
524 /// Exponential complexity for modifier \a m and size measure \a n
525 static PropCost crazy(PropCost::Mod m, unsigned int n);
526 /// Exponential complexity for modifier \a m and size measure \a n
527 static PropCost crazy(PropCost::Mod m, int n);
528 /// Cubic complexity for modifier \a m and size measure \a n
529 static PropCost cubic(PropCost::Mod m, unsigned int n);
530 /// Cubic complexity for modifier \a m and size measure \a n
531 static PropCost cubic(PropCost::Mod m, int n);
532 /// Quadratic complexity for modifier \a m and size measure \a n
533 static PropCost quadratic(PropCost::Mod m, unsigned int n);
534 /// Quadratic complexity for modifier \a m and size measure \a n
535 static PropCost quadratic(PropCost::Mod m, int n);
536 /// Linear complexity for modifier \a pcm and size measure \a n
537 static PropCost linear(PropCost::Mod m, unsigned int n);
538 /// Linear complexity for modifier \a pcm and size measure \a n
539 static PropCost linear(PropCost::Mod m, int n);
540 /// Three variables for modifier \a pcm
541 static PropCost ternary(PropCost::Mod m);
542 /// Two variables for modifier \a pcm
543 static PropCost binary(PropCost::Mod m);
544 /// Single variable for modifier \a pcm
545 static PropCost unary(PropCost::Mod m);
546 };
547
548
549 /**
550 * \brief Actor properties
551 * \ingroup TaskActor
552 */
553 enum ActorProperty {
554 /**
555 * \brief Actor must always be disposed
556 *
557 * Normally, a propagator will not be disposed if its home space
558 * is deleted. However, if an actor uses external resources,
559 * this property can be used to make sure that the actor
560 * will always be disposed.
561 */
562 AP_DISPOSE = (1 << 0),
563 /**
564 * Propagator is only weakly monotonic, that is, the propagator
565 * is only monotonic on assignments.
566 *
567 */
568 AP_WEAKLY = (1 << 1),
569 /**
570 * A propagator is in fact implementing a view trace recorder.
571 *
572 */
573 AP_VIEW_TRACE = (1 << 2),
574 /**
575 * A propagator is in fact implementing a trace recorder.
576 *
577 */
578 AP_TRACE = (1 << 3)
579 };
580
581
582 /**
583 * \brief Double-linked list for actors
584 *
585 * Used to maintain which actors belong to a space and also
586 * (for propagators) to organize actors in the queue of
587 * waiting propagators.
588 */
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:
600 //@{
601 /// Routines for double-linked list
602 ActorLink* prev(void) const; void prev(ActorLink*);
603 ActorLink* next(void) const; void next(ActorLink*);
604 ActorLink** next_ref(void);
605 //@}
606
607 /// Initialize links (self-linked)
608 void init(void);
609 /// Remove from predecessor and successor
610 void unlink(void);
611 /// Insert \a al directly after this
612 void head(ActorLink* al);
613 /// Insert \a al directly before this
614 void tail(ActorLink* al);
615 /// Test whether actor link is empty (points to itself)
616 bool empty(void) const;
617 /// Static cast for a non-null pointer (to give a hint to optimizer)
618 template<class T> static ActorLink* cast(T* a);
619 /// Static cast for a non-null pointer (to give a hint to optimizer)
620 template<class T> static const ActorLink* cast(const T* a);
621 };
622
623
624 /**
625 * \brief Base-class for both propagators and branchers
626 * \ingroup TaskActor
627 */
628 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
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:
638 /// Static cast for a non-null pointer (to give a hint to optimizer)
639 static Actor* cast(ActorLink* al);
640 /// Static cast for a non-null pointer (to give a hint to optimizer)
641 static const Actor* cast(const ActorLink* al);
642 /// Static member to test against during space cloning
643 GECODE_KERNEL_EXPORT static Actor* sentinel;
644 public:
645 /// Create copy
646 virtual Actor* copy(Space& home) = 0;
647
648 /// \name Memory management
649 //@{
650 /// Delete actor and return its size
651 GECODE_KERNEL_EXPORT
652 virtual size_t dispose(Space& home);
653 /// Allocate memory from space
654 static void* operator new(size_t s, Space& home);
655 /// No-op for exceptions
656 static void operator delete(void* p, Space& home);
657 //@}
658 public:
659 /// To avoid warnings
660 GECODE_KERNEL_EXPORT virtual ~Actor(void);
661 /// Not used
662 static void* operator new(size_t s);
663 /// Not used
664 static void operator delete(void* p);
665 };
666
667 class Home;
668
669 /**
670 * \brief Group baseclass for controlling actors
671 * \ingroup TaskGroup
672 */
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:
682 /// Fake id for group of all actors
683 static const unsigned int GROUPID_ALL = 0U;
684 /// Pre-defined default group id
685 static const unsigned int GROUPID_DEF = 1U;
686 /// The maximal group number
687 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
688 /// The group id
689 unsigned int gid;
690 /// Next group id
691 GECODE_KERNEL_EXPORT
692 static unsigned int next;
693 /// Mutex for protection
694 GECODE_KERNEL_EXPORT
695 static Support::Mutex m;
696 /// Construct with predefined group id \a gid0
697 Group(unsigned int gid0);
698 public:
699 /// \name Construction and access
700 //@{
701 /// Constructor
702 GECODE_KERNEL_EXPORT
703 Group(void);
704 /// Copy constructor
705 Group(const Group& g);
706 /// Assignment operator
707 Group& operator =(const Group& g);
708 /// Return a unique id for the group
709 unsigned int id(void) const;
710 /// Check whether actor group \a a is included in this group
711 bool in(Group a) const;
712 /// Check whether this is a real group (and not just default)
713 bool in(void) const;
714 //@}
715 /// Group of all actors
716 GECODE_KERNEL_EXPORT
717 static Group all;
718 /// Group of actors not in any user-defined group
719 GECODE_KERNEL_EXPORT
720 static Group def;
721 };
722
723 /**
724 * \brief Group of propagators
725 * \ingroup TaskGroup
726 */
727 class PropagatorGroup : public Group {
728 friend class Propagator;
729 friend class ViewTraceInfo;
730 friend class PropagateTraceInfo;
731 friend class PostTraceInfo;
732 protected:
733 /// Initialize with group id \a gid
734 PropagatorGroup(unsigned int gid);
735 public:
736 /// \name Construction
737 //@{
738 /// Constructor
739 PropagatorGroup(void);
740 /// Copy constructor
741 PropagatorGroup(const PropagatorGroup& g);
742 /// Assignment operator
743 PropagatorGroup& operator =(const PropagatorGroup& g);
744 /// To augment a space argument
745 Home operator ()(Space& home);
746 //@}
747 /// \name Move propagators between groups
748 //@{
749 /// Move propagators from group \a g to this group
750 GECODE_KERNEL_EXPORT
751 PropagatorGroup& move(Space& home, PropagatorGroup g);
752 /// Move propagator \a p to this group
753 PropagatorGroup& move(Space& home, Propagator& p);
754 /**
755 * \brief Move propagator with id \a id to this group
756 *
757 * Throws an exception of type UnknownPropagator, if no propagator
758 * with id \a id exists.
759 */
760 GECODE_KERNEL_EXPORT
761 PropagatorGroup& move(Space& home, unsigned int id);
762 //@}
763 /// \name Operations on groups
764 //@{
765 /// Test whether this group is equal to group \a g
766 bool operator ==(PropagatorGroup g) const;
767 /// Test whether this group is different from group \a g
768 bool operator !=(PropagatorGroup g) const;
769 /// Return number of propagators in a group
770 GECODE_KERNEL_EXPORT
771 unsigned int size(Space& home) const;
772 /// Kill all propagators in a group
773 GECODE_KERNEL_EXPORT
774 void kill(Space& home);
775 /// Disable all propagators in a group
776 GECODE_KERNEL_EXPORT
777 void disable(Space& home);
778 /**
779 * \brief Enable all propagators in a group
780 *
781 * If \a s is true, the propagators will be scheduled for propagation
782 * if needed.
783 */
784 GECODE_KERNEL_EXPORT
785 void enable(Space& home, bool s=true);
786 //@}
787 /// Group of all propagators
788 GECODE_KERNEL_EXPORT
789 static PropagatorGroup all;
790 /// Group of propagators not in any user-defined group
791 GECODE_KERNEL_EXPORT
792 static PropagatorGroup def;
793 };
794
795 /**
796 * \brief Group of branchers
797 * \ingroup TaskGroup
798 */
799 class BrancherGroup : public Group {
800 friend class Brancher;
801 protected:
802 /// Initialize with group id \a gid
803 BrancherGroup(unsigned int gid);
804 public:
805 /// \name Construction
806 //@{
807 /// Constructor
808 BrancherGroup(void);
809 /// Copy constructor
810 BrancherGroup(const BrancherGroup& g);
811 /// Assignment operator
812 BrancherGroup& operator =(const BrancherGroup& g);
813 /// To augment a space argument
814 Home operator ()(Space& home);
815 //@}
816 /// \name Move branchers between groups
817 //@{
818 /// Move branchers from group \a g to this group
819 GECODE_KERNEL_EXPORT
820 BrancherGroup& move(Space& home, BrancherGroup g);
821 /// Move brancher \a b to this group
822 BrancherGroup& move(Space& home, Brancher& b);
823 /**
824 * \brief Move brancher with id \a id to this group
825 *
826 * Throws an exception of type UnknownBrancher, if no brancher
827 * with id \a id exists.
828 */
829 GECODE_KERNEL_EXPORT
830 BrancherGroup& move(Space& home, unsigned int id);
831 //@}
832 /// \name Operations on groups
833 //@{
834 /// Test whether this group is equal to group \a g
835 bool operator ==(BrancherGroup g) const;
836 /// Test whether this group is different from group \a g
837 bool operator !=(BrancherGroup g) const;
838 /// Return number of branchers in a group
839 GECODE_KERNEL_EXPORT
840 unsigned int size(Space& home) const;
841 /// Kill all branchers in a group
842 GECODE_KERNEL_EXPORT
843 void kill(Space& home);
844 //@}
845 /// Group of all branchers
846 GECODE_KERNEL_EXPORT
847 static BrancherGroup all;
848 /// Group of branchers not in any user-defined group
849 GECODE_KERNEL_EXPORT
850 static BrancherGroup def;
851 };
852
853 /**
854 * \brief %Home class for posting propagators
855 */
856 class Home {
857 friend class PostInfo;
858 protected:
859 /// The space where the propagator is to be posted
860 Space& s;
861 /// A propagator (possibly) that is currently being rewritten
862 Propagator* p;
863 /// A propagator group
864 PropagatorGroup pg;
865 /// A brancher group
866 BrancherGroup bg;
867 public:
868 /// \name Conversion
869 //@{
870 /// Initialize the home with space \a s and propagator \a p and group \a g
871 Home(Space& s, Propagator* p=nullptr,
872 PropagatorGroup pg=PropagatorGroup::def,
873 BrancherGroup bg=BrancherGroup::def);
874 /// Copy constructor
875 Home(const Home& h);
876 /// Assignment operator
877 Home& operator =(const Home& h);
878 /// Retrieve the space of the home
879 operator Space&(void);
880 //@}
881 /// \name Extended information
882 //@{
883 /// Return a home extended by propagator to be rewritten
884 Home operator ()(Propagator& p);
885 /// Return a home extended by a propagator group
886 Home operator ()(PropagatorGroup pg);
887 /// Return a home extended by a brancher group
888 Home operator ()(BrancherGroup bg);
889 /// Return propagator (or nullptr) for currently rewritten propagator
890 Propagator* propagator(void) const;
891 /// Return propagator group
892 PropagatorGroup propagatorgroup(void) const;
893 /// Return brancher group
894 BrancherGroup branchergroup(void) const;
895 //@}
896 /// \name Forwarding of common space operations
897 //@{
898 /// Check whether corresponding space is failed
899 bool failed(void) const;
900 /// Mark space as failed
901 void fail(void);
902 /// Notice actor property
903 void notice(Actor& a, ActorProperty p, bool duplicate=false);
904 //@}
905 };
906
907 /**
908 * \brief View trace information
909 */
910 class ViewTraceInfo {
911 friend class Space;
912 friend class PostInfo;
913 public:
914 /// What is currently executing
915 enum What {
916 /// A propagator is currently executing
917 PROPAGATOR = 0,
918 /// A brancher is executing
919 BRANCHER = 1,
920 /// A post function is executing
921 POST = 2,
922 /// Unknown
923 OTHER = 3
924 };
925 protected:
926 /// Encoding a tagged pointer or a tagged group id
927 ptrdiff_t who;
928 /// Record that propagator \a p is executing
929 void propagator(Propagator& p);
930 /// Record that brancher \a b is executing
931 void brancher(Brancher& b);
932 /// Record that a post function with propagator group \a g is executing
933 void post(PropagatorGroup g);
934 /// Record that nothing is known at this point
935 void other(void);
936 public:
937 /// Return what is currently executing
938 What what(void) const;
939 /// Return currently executing propagator
940 const Propagator& propagator(void) const;
941 /// Return currently executing brancher
942 const Brancher& brancher(void) const;
943 /// Return propagator group of currently executing post function
944 PropagatorGroup post(void) const;
945 };
946
947 /**
948 * \brief Class to set group information when a post function is executed
949 */
950 class PostInfo {
951 friend class Space;
952 protected:
953 /// The home space
954 Space& h;
955 /// The propagator group
956 PropagatorGroup pg;
957 /// Next free propagator id
958 unsigned int pid;
959 /// Whether it is used nested
960 bool nested;
961 public:
962 /// Set information
963 PostInfo(Home home);
964 /// Reset information
965 ~PostInfo(void);
966 };
967
968 /**
969 * \brief Propagate trace information
970 */
971 class PropagateTraceInfo {
972 friend class Space;
973 public:
974 /// Propagator status
975 enum Status {
976 FIX, ///< Propagator computed fixpoint
977 NOFIX, ///< Propagator did not compute fixpoint
978 FAILED, ///< Propagator failed
979 SUBSUMED ///< Propagator is subsumed
980 };
981 protected:
982 /// Propagator id
983 unsigned int i;
984 /// Propagator group
985 PropagatorGroup g;
986 /// Propagator
987 const Propagator* p;
988 /// Status
989 Status s;
990 /// Initialize
991 PropagateTraceInfo(unsigned int i, PropagatorGroup g,
992 const Propagator* p, Status s);
993 public:
994 /// Return propagator identifier
995 unsigned int id(void) const;
996 /// Return propagator group
997 PropagatorGroup group(void) const;
998 /// Return pointer to non-subsumed propagator
999 const Propagator* propagator(void) const;
1000 /// Return propagator status
1001 Status status(void) const;
1002 };
1003
1004 /**
1005 * \brief Commit trace information
1006 */
1007 class CommitTraceInfo {
1008 friend class Space;
1009 protected:
1010 /// Brancher
1011 const Brancher& b;
1012 /// Choice
1013 const Choice& c;
1014 /// Alternative
1015 unsigned int a;
1016 /// Initialize
1017 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1018 public:
1019 /// Return brancher identifier
1020 unsigned int id(void) const;
1021 /// Return brancher group
1022 BrancherGroup group(void) const;
1023 /// Return brancher
1024 const Brancher& brancher(void) const;
1025 /// Return choice
1026 const Choice& choice(void) const;
1027 /// Return alternative
1028 unsigned int alternative(void) const;
1029 };
1030
1031 /**
1032 * \brief Post trace information
1033 */
1034 class PostTraceInfo {
1035 friend class Space;
1036 friend class PostInfo;
1037 public:
1038 /// Post status
1039 enum Status {
1040 POSTED, ///< Propagator was posted
1041 FAILED, ///< Posting failed
1042 SUBSUMED ///< Propagator not posted as already subsumed
1043 };
1044 protected:
1045 /// Propagator group
1046 PropagatorGroup g;
1047 /// Status
1048 Status s;
1049 /// Number of posted propagators
1050 unsigned int n;
1051 /// Initialize
1052 PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
1053 public:
1054 /// Return post status
1055 Status status(void) const;
1056 /// Return propagator group
1057 PropagatorGroup group(void) const;
1058 /// Return number of posted propagators
1059 unsigned int propagators(void) const;
1060 };
1061
1062 /**
1063 * \brief Base-class for propagators
1064 * \ingroup TaskActor
1065 */
1066 class GECODE_VTABLE_EXPORT Propagator : public Actor {
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;
1072 friend class SubscribedPropagators;
1073 friend class PropagatorGroup;
1074 private:
1075 union {
1076 /// A set of modification events (used during propagation)
1077 ModEventDelta med;
1078 /// The size of the propagator (used during subsumption)
1079 size_t size;
1080 /// A list of advisors (used during cloning)
1081 Gecode::ActorLink* advisors;
1082 } u;
1083 /// A tagged pointer combining a pointer to global propagator information and whether the propagator is disabled
1084 void* gpi_disabled;
1085 /// Static cast for a non-null pointer (to give a hint to optimizer)
1086 static Propagator* cast(ActorLink* al);
1087 /// Static cast for a non-null pointer (to give a hint to optimizer)
1088 static const Propagator* cast(const ActorLink* al);
1089 /// Disable propagator
1090 void disable(Space& home);
1091 /// Enable propagator
1092 void enable(Space& home);
1093 protected:
1094 /// Constructor for posting
1095 Propagator(Home home);
1096 /// Constructor for cloning \a p
1097 Propagator(Space& home, Propagator& p);
1098 /// Return forwarding pointer during copying
1099 Propagator* fwd(void) const;
1100 /// Provide access to global propagator information
1101 Kernel::GPI::Info& gpi(void);
1102
1103 public:
1104 /// \name Propagation
1105 //@{
1106 /**
1107 * \brief Schedule function
1108 *
1109 * The function is executed when a propagator is enabled again.
1110 * Note that a propagator should be scheduled with the right
1111 * modification event delta and should only be scheduled if
1112 * it is legal to execute the propagator.
1113 */
1114 virtual void reschedule(Space& home) = 0;
1115 /**
1116 * \brief Propagation function
1117 *
1118 * The propagation function must return an execution status as
1119 * follows:
1120 * - ES_FAILED: the propagator has detected failure
1121 * - ES_NOFIX: the propagator has done propagation
1122 * - ES_FIX: the propagator has done propagation and has computed
1123 * a fixpoint. That is, running the propagator immediately
1124 * again will do nothing.
1125 *
1126 * Apart from the above values, a propagator can return
1127 * the result from calling one of the functions defined by a space:
1128 * - ES_SUBSUMED: the propagator is subsumed and has been already
1129 * deleted.
1130 * - ES_NOFIX_PARTIAL: the propagator has consumed some of its
1131 * propagation events.
1132 * - ES_FIX_PARTIAL: the propagator has consumed some of its
1133 * propagation events and with respect to these events is
1134 * at fixpoint
1135 * For more details, see the individual functions.
1136 *
1137 */
1138 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1139 /// Cost function
1140 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1141 /**
1142 * \brief Return the modification event delta
1143 *
1144 * This function returns the modification event delta of the currently
1145 * executing propagator and hence can only be called within the
1146 * propagate function of a propagator.
1147 */
1148 ModEventDelta modeventdelta(void) const;
1149 /**
1150 * \brief Advise function
1151 *
1152 * The advisor is passed as argument \a a.
1153 *
1154 * A propagator must specialize this advise function, if it
1155 * uses advisors. The advise function must return an execution
1156 * status as follows:
1157 * - ES_FAILED: the advisor has detected failure.
1158 * - ES_FIX: the advisor's propagator (that is, this propagator)
1159 * does not need to be run.
1160 * - ES_NOFIX: the advisor's propagator (that is, this propagator)
1161 * must be run.
1162 * - ES_NOFIX_FORCE: the advisor's propagator (that is, this propagator)
1163 * must be run and it must forcefully be rescheduled (including
1164 * recomputation of cost).
1165 *
1166 * Apart from the above values, an advisor can return
1167 * the result from calling the function defined by a space:
1168 * - ES_FIX_DISPOSE: the advisor's propagator does not need to be run
1169 * and the advisor will be disposed.
1170 * - ES_NOFIX_DISPOSE: the advisor's propagator must be run and the
1171 * advisor will be disposed.
1172 * - ES_NOFIX_FORCE_DISPOSE: the advisor's propagator must be run
1173 * , it must forcefully be rescheduled (including recomputation
1174 * of cost), and the adviser will be disposed.
1175 * For more details, see the function documentation.
1176 *
1177 * The delta \a d describes how the variable has been changed
1178 * by an operation on the advisor's variable. Typically,
1179 * the delta information can only be utilized by either
1180 * static or member functions of views as the actual delta
1181 * information is both domain and view dependent.
1182 *
1183 */
1184 GECODE_KERNEL_EXPORT
1185 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1186 /// Run advisor \a a to be run on failure in failed space
1187 GECODE_KERNEL_EXPORT
1188 virtual void advise(Space& home, Advisor& a);
1189 //@}
1190 /// \name Information
1191 //@{
1192 /// Return the accumlated failure count
1193 double afc(void) const;
1194 //@}
1195#ifdef GECODE_HAS_CBS
1196 /// \name Marginal distribution
1197 //@{
1198 /**
1199 * \brief Solution distribution
1200 *
1201 * Computes the marginal distribution for every variable and value in the
1202 * propagator. A callback is used to transmit each result.
1203 */
1204 /// Signature for function transmitting marginal distributions
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;
1208 /**
1209 * \brief Sum of variable cardinalities
1210 *
1211 * \param size Sum of variable cardinalities
1212 * \param size_b Sum of variable cardinalities for subset involved
1213 * in branching decisions
1214 */
1215 /// Signature for function testing if variables are candidates to branching decisions
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;
1219 //@}
1220#endif
1221 /// \name Id and group support
1222 //@{
1223 /// Return propagator id
1224 unsigned int id(void) const;
1225 /// Return group propagator belongs to
1226 PropagatorGroup group(void) const;
1227 /// Add propagator to group \a g
1228 void group(PropagatorGroup g);
1229 /// Whether propagator is currently disabled
1230 bool disabled(void) const;
1231 //@}
1232 };
1233
1234
1235 /**
1236 * \brief %Council of advisors
1237 *
1238 * If a propagator uses advisors, it must maintain its advisors
1239 * through a council.
1240 * \ingroup TaskActor
1241 */
1242 template<class A>
1243 class Council {
1244 friend class Advisor;
1245 friend class Advisors<A>;
1246 private:
1247 /// Starting point for a linked list of advisors
1248 mutable ActorLink* advisors;
1249 public:
1250 /// Default constructor
1251 Council(void);
1252 /// Construct advisor council
1253 Council(Space& home);
1254 /// Test whether council has advisor left
1255 bool empty(void) const;
1256 /// Update during cloning (copies all advisors)
1257 void update(Space& home, Council<A>& c);
1258 /// Dispose council
1259 void dispose(Space& home);
1260 };
1261
1262
1263 /**
1264 * \brief Class to iterate over advisors of a council
1265 * \ingroup TaskActor
1266 */
1267 template<class A>
1268 class Advisors {
1269 private:
1270 /// The current advisor
1271 ActorLink* a;
1272 public:
1273 /// Initialize
1274 Advisors(const Council<A>& c);
1275 /// Test whether there advisors left
1276 bool operator ()(void) const;
1277 /// Move iterator to next advisor
1278 void operator ++(void);
1279 /// Return advisor
1280 A& advisor(void) const;
1281 };
1282
1283
1284 /**
1285 * \brief Base-class for advisors
1286 *
1287 * Advisors are typically subclassed for each propagator that
1288 * wants to use advisors. The actual member function that
1289 * is executed when a variable is changed, must be implemented
1290 * by the advisor's propagator.
1291 *
1292 * \ingroup TaskActor
1293 */
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;
1298 friend class SubscribedPropagators;
1299 private:
1300 /// Is the advisor disposed?
1301 bool disposed(void) const;
1302 /// Static cast
1303 static Advisor* cast(ActorLink* al);
1304 /// Static cast
1305 static const Advisor* cast(const ActorLink* al);
1306 protected:
1307 /// Return the advisor's propagator
1308 Propagator& propagator(void) const;
1309 public:
1310 /// Constructor for creation
1311 template<class A>
1312 Advisor(Space& home, Propagator& p, Council<A>& c);
1313 /// Copying constructor
1314 Advisor(Space& home, Advisor& a);
1315 /// Provide access to view trace information
1316 const ViewTraceInfo& operator ()(const Space& home) const;
1317
1318 /// \name Memory management
1319 //@{
1320 /// Dispose the advisor
1321 template<class A>
1322 void dispose(Space& home, Council<A>& c);
1323 /// Allocate memory from space
1324 static void* operator new(size_t s, Space& home);
1325 /// No-op for exceptions
1326 static void operator delete(void* p, Space& home);
1327 //@}
1328 private:
1329#ifndef __GNUC__
1330 /// Not used (uses dispose instead)
1331 static void operator delete(void* p);
1332#endif
1333 /// Not used
1334 static void* operator new(size_t s);
1335 };
1336
1337
1338 /**
1339 * \brief No-good literal recorded during search
1340 *
1341 */
1342 class GECODE_VTABLE_EXPORT NGL {
1343 private:
1344 /// Combines pointer to next literal and mark whether it is a leaf
1345 void* nl;
1346 public:
1347 /// The status of a no-good literal
1348 enum Status {
1349 FAILED, ///< The literal is failed
1350 SUBSUMED, ///< The literal is subsumed
1351 NONE ///< The literal is neither failed nor subsumed
1352 };
1353 /// Constructor for creation
1354 NGL(void);
1355 /// Constructor for creation
1356 NGL(Space& home);
1357 /// Constructor for cloning \a ngl
1358 NGL(Space& home, NGL& ngl);
1359 /// Subscribe propagator \a p to all views of the no-good literal
1360 virtual void subscribe(Space& home, Propagator& p) = 0;
1361 /// Cancel propagator \a p from all views of the no-good literal
1362 virtual void cancel(Space& home, Propagator& p) = 0;
1363 /// Schedule propagator \a p for all views of the no-good literal
1364 virtual void reschedule(Space& home, Propagator& p) = 0;
1365 /// Test the status of the no-good literal
1366 virtual NGL::Status status(const Space& home) const = 0;
1367 /// Propagate the negation of the no-good literal
1368 virtual ExecStatus prune(Space& home) = 0;
1369 /// Create copy
1370 virtual NGL* copy(Space& home) = 0;
1371 /// Whether dispose must always be called (returns false)
1372 GECODE_KERNEL_EXPORT
1373 virtual bool notice(void) const;
1374 /// Dispose
1375 virtual size_t dispose(Space& home);
1376 /// \name Internal management routines
1377 //@{
1378 /// Test whether literal is a leaf
1379 bool leaf(void) const;
1380 /// Return pointer to next literal
1381 NGL* next(void) const;
1382 /// Mark literal as leaf or not
1383 void leaf(bool l);
1384 /// %Set pointer to next literal
1385 void next(NGL* n);
1386 /// Add node \a n and mark it as leaf \a l and return \a n
1387 NGL* add(NGL* n, bool l);
1388 //@}
1389 /// \name Memory management
1390 //@{
1391 /// Allocate memory from space
1392 static void* operator new(size_t s, Space& home);
1393 /// Return memory to space
1394 static void operator delete(void* s, Space& home);
1395 /// Needed for exceptions
1396 static void operator delete(void* p);
1397 //@}
1398 public:
1399 /// To avoid warnings
1400 GECODE_KERNEL_EXPORT virtual ~NGL(void);
1401 /// Not used
1402 static void* operator new(size_t s);
1403 };
1404
1405 /**
1406 * \brief %Choice for performing commit
1407 *
1408 * Must be refined by inheritance such that the information stored
1409 * inside a choice is sufficient to redo a commit performed by a
1410 * particular brancher.
1411 *
1412 * \ingroup TaskActor
1413 */
1414 class GECODE_VTABLE_EXPORT Choice : public HeapAllocated {
1415 friend class Space;
1416 private:
1417 unsigned int bid; ///< Identity to match creating brancher
1418 unsigned int alt; ///< Number of alternatives
1419
1420 /// Return id of the creating brancher
1421 unsigned int id(void) const;
1422 protected:
1423 /// Initialize for particular brancher \a b and alternatives \a a
1424 Choice(const Brancher& b, const unsigned int a);
1425 public:
1426 /// Return number of alternatives
1427 unsigned int alternatives(void) const;
1428 /// Destructor
1429 GECODE_KERNEL_EXPORT virtual ~Choice(void);
1430 /// Archive into \a e
1431 GECODE_KERNEL_EXPORT
1432 virtual void archive(Archive& e) const;
1433 };
1434
1435 /**
1436 * \brief Base-class for branchers
1437 *
1438 * Note that branchers cannot be created inside a propagator
1439 * (no idea why one would like to do that anyway). If you do that
1440 * the system will explode in a truly interesting way.
1441 *
1442 * \ingroup TaskActor
1443 */
1444 class GECODE_VTABLE_EXPORT Brancher : public Actor {
1445 friend class ActorLink;
1446 friend class Space;
1447 friend class Choice;
1448 private:
1449 /// Unique brancher identity
1450 unsigned int bid;
1451 /// Group id
1452 unsigned int gid;
1453 /// Static cast for a non-null pointer (to give a hint to optimizer)
1454 static Brancher* cast(ActorLink* al);
1455 /// Static cast for a non-null pointer (to give a hint to optimizer)
1456 static const Brancher* cast(const ActorLink* al);
1457 protected:
1458 /// Constructor for creation
1459 Brancher(Home home);
1460 /// Constructor for cloning \a b
1461 Brancher(Space& home, Brancher& b);
1462 public:
1463 /// \name Brancher
1464 //@{
1465 /**
1466 * \brief Check status of brancher, return true if alternatives left
1467 *
1468 * This method is called when Space::status is called, it determines
1469 * whether to continue branching with this brancher or move on to
1470 * the (possibly) next brancher.
1471 *
1472 */
1473 virtual bool status(const Space& home) const = 0;
1474 /**
1475 * \brief Return choice
1476 *
1477 * Note that this method relies on the fact that it is called
1478 * immediately after a previous call to status. Moreover, the
1479 * member function can only be called once.
1480 */
1481 virtual const Choice* choice(Space& home) = 0;
1482 /// Return choice from \a e
1483 virtual const Choice* choice(const Space& home, Archive& e) = 0;
1484 /**
1485 * \brief Commit for choice \a c and alternative \a a
1486 *
1487 * The current brancher in the space \a home performs a commit from
1488 * the information provided by the choice \a c and the alternative \a a.
1489 */
1490 virtual ExecStatus commit(Space& home, const Choice& c,
1491 unsigned int a) = 0;
1492 /**
1493 * \brief Create no-good literal for choice \a c and alternative \a a
1494 *
1495 * The current brancher in the space \a home creates a no-good literal
1496 * from the information provided by the choice \a c and the alternative
1497 * \a a. The brancher has the following options:
1498 * - it returns nullptr for all alternatives \a a. This means that the
1499 * brancher does not support no-good literals (default).
1500 * - it returns nullptr for the last alternative \a a. This means that
1501 * this alternative is equivalent to the negation of the disjunction
1502 * of all other alternatives.
1503 *
1504 */
1505 GECODE_KERNEL_EXPORT
1506 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1507 /**
1508 * \brief Print branch for choice \a c and alternative \a a
1509 *
1510 * Prints an explanation of the alternative \a a of choice \a c
1511 * on the stream \a o.
1512 *
1513 */
1514 GECODE_KERNEL_EXPORT
1515 virtual void print(const Space& home, const Choice& c, unsigned int a,
1516 std::ostream& o) const;
1517 //@}
1518 /// \name Id and group support
1519 //@{
1520 /// Return brancher id
1521 unsigned int id(void) const;
1522 /// Return group brancher belongs to
1523 BrancherGroup group(void) const;
1524 /// Add brancher to group \a g
1525 void group(BrancherGroup g);
1526 //@}
1527 };
1528
1529 /**
1530 * \brief Local (space-shared) object
1531 *
1532 * Local objects must inherit from this base class.
1533 *
1534 */
1535 class LocalObject : public Actor {
1536 friend class ActorLink;
1537 friend class Space;
1538 friend class LocalHandle;
1539 protected:
1540 /// Constructor for creation
1541 LocalObject(Home home);
1542 /// Copy constructor
1543 LocalObject(Space& home, LocalObject& l);
1544 /// Static cast for a non-null pointer (to give a hint to optimizer)
1545 static LocalObject* cast(ActorLink* al);
1546 /// Static cast for a non-null pointer (to give a hint to optimizer)
1547 static const LocalObject* cast(const ActorLink* al);
1548 private:
1549 /// Make copy and set forwarding pointer
1550 GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
1551 public:
1552 /// Return forwarding pointer
1553 LocalObject* fwd(Space& home);
1554 };
1555
1556 /**
1557 * \brief Handles for local (space-shared) objects
1558 *
1559 */
1560 class LocalHandle {
1561 private:
1562 /// The local object
1563 LocalObject* o;
1564 protected:
1565 /// Create local handle pointing to nullptr object
1566 LocalHandle(void);
1567 /// Create local handle that points to local object \a lo
1568 LocalHandle(LocalObject* lo);
1569 /// Copy constructor
1570 LocalHandle(const LocalHandle& lh);
1571 public:
1572 /// Assignment operator
1573 LocalHandle& operator =(const LocalHandle& lh);
1574 /// Updating during cloning
1575 void update(Space& home, LocalHandle& lh);
1576 /// Destructor
1577 ~LocalHandle(void);
1578 protected:
1579 /// Access to the local object
1580 LocalObject* object(void) const;
1581 /// Modify local object
1582 void object(LocalObject* n);
1583 };
1584
1585
1586 /**
1587 * \brief No-goods recorded from restarts
1588 *
1589 */
1590 class GECODE_VTABLE_EXPORT NoGoods {
1591 protected:
1592 /// Number of no-goods
1593 unsigned long int n;
1594 public:
1595 /// Initialize
1596 NoGoods(void);
1597 /// Post no-goods
1598 GECODE_KERNEL_EXPORT
1599 virtual void post(Space& home) const;
1600 /// Return number of no-goods posted
1601 unsigned long int ng(void) const;
1602 /// %Set number of no-goods posted to \a n
1603 void ng(unsigned long int n);
1604 /// Destructor
1605 virtual ~NoGoods(void);
1606 /// Empty no-goods
1607 GECODE_KERNEL_EXPORT
1608 static NoGoods eng;
1609 };
1610
1611 /**
1612 * \brief Information passed by meta search engines
1613 *
1614 */
1615 class GECODE_VTABLE_EXPORT MetaInfo {
1616 public:
1617 /// Which type of information is provided
1618 enum Type {
1619 /// Information is provided by a restart-based engine
1620 RESTART,
1621 /// Information is provided by a portfolio-based engine
1622 PORTFOLIO
1623 };
1624 protected:
1625 /// Type of information
1626 const Type t;
1627 /// \name Restart-based information
1628 //@{
1629 /// Number of restarts
1630 const unsigned long int r;
1631 /// Number of solutions since last restart
1632 const unsigned long long int s;
1633 /// Number of failures since last restart
1634 const unsigned long long int f;
1635 /// Last solution found
1636 const Space* l;
1637 /// No-goods from restart
1638 const NoGoods& ng;
1639 //@}
1640 /// \name Portfolio-based information
1641 //@{
1642 /// Number of asset in portfolio
1643 const unsigned int a;
1644 //@}
1645 public:
1646 /// \name Constructors depending on type of engine
1647 //@{
1648 /// Constructor for restart-based engine
1649 MetaInfo(unsigned long int r,
1650 unsigned long long int s,
1651 unsigned long long int f,
1652 const Space* l,
1653 NoGoods& ng);
1654 /// Constructor for portfolio-based engine
1655 MetaInfo(unsigned int a);
1656 //@}
1657 /// Return type of information
1658 Type type(void) const;
1659 /// \name Restart-based information
1660 //@{
1661 /// Return number of restarts
1662 unsigned long int restart(void) const;
1663 /// Return number of solutions since last restart
1664 unsigned long long int solution(void) const;
1665 /// Return number of failures since last restart
1666 unsigned long long int fail(void) const;
1667 /// Return last solution found (possibly nullptr)
1668 const Space* last(void) const;
1669 /// Return no-goods recorded from restart
1670 const NoGoods& nogoods(void) const;
1671 //@}
1672 /// \name Portfolio-based information
1673 //@{
1674 /// Return number of asset in portfolio
1675 unsigned int asset(void) const;
1676 //@}
1677 };
1678
1679 /**
1680 * \brief %Space status
1681 * \ingroup TaskSearch
1682 */
1683 enum SpaceStatus {
1684 SS_FAILED, ///< %Space is failed
1685 SS_SOLVED, ///< %Space is solved (no brancher left)
1686 SS_BRANCH ///< %Space must be branched (at least one brancher left)
1687 };
1688
1689 /**
1690 * \brief %Statistics for execution of status
1691 *
1692 */
1693 class StatusStatistics {
1694 public:
1695 /// Number of propagator executions
1696 unsigned long long int propagate;
1697 /// Initialize
1698 StatusStatistics(void);
1699 /// Reset information
1700 void reset(void);
1701 /// Return sum with \a s
1702 StatusStatistics operator +(const StatusStatistics& s);
1703 /// Increment by statistics \a s
1704 StatusStatistics& operator +=(const StatusStatistics& s);
1705 };
1706
1707 /**
1708 * \brief %Statistics for execution of clone
1709 *
1710 */
1711 class CloneStatistics {
1712 public:
1713 /// Initialize
1714 CloneStatistics(void);
1715 /// Reset information
1716 void reset(void);
1717 /// Return sum with \a s
1718 CloneStatistics operator +(const CloneStatistics& s);
1719 /// Increment by statistics \a s
1720 CloneStatistics& operator +=(const CloneStatistics& s);
1721 };
1722
1723 /**
1724 * \brief %Statistics for execution of commit
1725 *
1726 */
1727 class CommitStatistics {
1728 public:
1729 /// Initialize
1730 CommitStatistics(void);
1731 /// Reset information
1732 void reset(void);
1733 /// Return sum with \a s
1734 CommitStatistics operator +(const CommitStatistics& s);
1735 /// Increment by statistics \a s
1736 CommitStatistics& operator +=(const CommitStatistics& s);
1737 };
1738
1739
1740
1741 /**
1742 * \brief Computation spaces
1743 */
1744 class GECODE_VTABLE_EXPORT Space : public HeapAllocated {
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;
1760 friend GECODE_KERNEL_EXPORT
1761 void trace(Home home, TraceFilter tf, int te, Tracer& t);
1762 private:
1763 /// Shared data for space
1764 Kernel::SharedSpaceData ssd;
1765 /// Performs memory management for space
1766 Kernel::MemoryManager mm;
1767#ifdef GECODE_HAS_CBS
1768 /// Global counter for variable ids
1769 unsigned int var_id_counter;
1770#endif
1771 /// Doubly linked list of all propagators
1772 ActorLink pl;
1773 /// Doubly linked list of all branchers
1774 ActorLink bl;
1775 /**
1776 * \brief Points to the first brancher to be used for status
1777 *
1778 * If equal to &bl, no brancher does exist.
1779 */
1780 Brancher* b_status;
1781 /**
1782 * \brief Points to the first brancher to be used for commit
1783 *
1784 * Note that \a b_commit can point to an earlier brancher
1785 * than \a b_status. This reflects the fact that the earlier
1786 * brancher is already done (that is, status on that brancher
1787 * returns false) but there might be still choices
1788 * referring to the earlier brancher.
1789 *
1790 * If equal to &bl, no brancher does exist.
1791 */
1792 Brancher* b_commit;
1793 /// Find brancher with identity \a id
1794 Brancher* brancher(unsigned int id);
1795
1796 /// Kill brancher \a b
1797 void kill(Brancher& b);
1798 /// Kill propagator \a p
1799 void kill(Propagator& p);
1800
1801 /// Kill brancher with identity \a id
1802 GECODE_KERNEL_EXPORT
1803 void kill_brancher(unsigned int id);
1804
1805 /// Reserved brancher id (never created)
1806 static const unsigned reserved_bid = 0U;
1807
1808 /// Number of bits for status control
1809 static const unsigned int sc_bits = 2;
1810 /// No special features activated
1811 static const unsigned int sc_fast = 0;
1812 /// Disabled propagators are supported
1813 static const unsigned int sc_disabled = 1;
1814 /// Tracing is supported
1815 static const unsigned int sc_trace = 2;
1816
1817 union {
1818 /// Data only available during propagation or branching
1819 struct {
1820 /**
1821 * \brief Cost level with next propagator to be executed
1822 *
1823 * This maintains the following invariant (but only if the
1824 * space does not perform propagation):
1825 * - If active points to a queue, this queue might contain
1826 * a propagator. However, there will be at least one queue
1827 * containing a propagator.
1828 * - Otherwise, active is smaller than the first queue
1829 * or larger than the last queue. Then, the space is stable.
1830 * - If active is larger than the last queue, the space is failed.
1831 */
1832 ActorLink* active;
1833 /// Scheduled propagators according to cost
1834 ActorLink queue[PropCost::AC_MAX+1];
1835 /**
1836 * \brief Id of next brancher to be created plus status control
1837 *
1838 * The last two bits are reserved for status control.
1839 *
1840 */
1841 unsigned int bid_sc;
1842 /// Number of subscriptions
1843 unsigned int n_sub;
1844 /// View trace information
1845 ViewTraceInfo vti;
1846 } p;
1847 /// Data available only during copying
1848 struct {
1849 /// Entries for updating variables
1850 VarImpBase* vars_u[AllVarConf::idx_c];
1851 /// Keep variables during copying without index structure
1852 VarImpBase* vars_noidx;
1853 /// Linked list of local objects
1854 LocalObject* local;
1855 } c;
1856 } pc;
1857 /// Put propagator \a p into right queue
1858 void enqueue(Propagator* p);
1859 /**
1860 * \name update, and dispose variables
1861 */
1862 //@{
1863#ifdef GECODE_HAS_VAR_DISPOSE
1864 /// Registered variable type disposers
1865 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1866 /// Entries for disposing variables
1867 VarImpBase* _vars_d[AllVarConf::idx_d];
1868 /// Return reference to variables (dispose)
1869 template<class VIC> VarImpBase* vars_d(void) const;
1870 /// %Set reference to variables (dispose)
1871 template<class VIC> void vars_d(VarImpBase* x);
1872#endif
1873 /// Update all cloned variables
1874 void update(ActorLink** sub);
1875 //@}
1876
1877 /// First actor for forced disposal
1878 Actor** d_fst;
1879 /// Current actor for forced disposal
1880 Actor** d_cur;
1881 /// Last actor for forced disposal
1882 Actor** d_lst;
1883
1884 /// Used for default argument
1885 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1886 /// Used for default argument
1887 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1888 /// Used for default argument
1889 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1890
1891 /**
1892 * \brief Clone space
1893 *
1894 * Assumes that the space is stable and not failed. If the space is
1895 * failed, an exception of type SpaceFailed is thrown. If the space
1896 * is not stable, an exception of SpaceNotStable is thrown.
1897 *
1898 * Otherwise, a clone of the space is returned.
1899 *
1900 * Throws an exception of type SpaceNotCloned when the copy constructor
1901 * of the Space class is not invoked during cloning.
1902 *
1903 */
1904 GECODE_KERNEL_EXPORT Space* _clone(void);
1905
1906 /**
1907 * \brief Commit choice \a c for alternative \a a
1908 *
1909 * The current brancher in the space performs a commit from
1910 * the information provided by the choice \a c
1911 * and the alternative \a a. The statistics information \a stat is
1912 * updated.
1913 *
1914 * Note that no propagation is perfomed (to support path
1915 * recomputation), in order to perform propagation the member
1916 * function status must be used.
1917 *
1918 * Committing with choices must be carried
1919 * out in the same order as the choices have been
1920 * obtained by the member function Space::choice().
1921 *
1922 * It is perfectly okay to add constraints interleaved with
1923 * choices (provided they are in the right order).
1924 * However, if propagation is performed by calling the member
1925 * function status and then new choices are
1926 * computed, these choices are different.
1927 *
1928 * Only choices can be used that are up-to-date in the following
1929 * sense: if a new choice is created (via the choice member
1930 * function), no older choices can be used.
1931 *
1932 * Committing throws the following exceptions:
1933 * - SpaceNoBrancher, if the space has no current brancher (it is
1934 * already solved).
1935 * - SpaceIllegalAlternative, if \a a is not smaller than the number
1936 * of alternatives supported by the choice \a c.
1937 */
1938 GECODE_KERNEL_EXPORT
1939 void _commit(const Choice& c, unsigned int a);
1940
1941 /**
1942 * \brief Commit choice \a c for alternative \a a if possible
1943 *
1944 * The current brancher in the space performs a commit from
1945 * the information provided by the choice \a c
1946 * and the alternative \a a. The statistics information \a stat is
1947 * updated.
1948 *
1949 * Note that no propagation is perfomed (to support path
1950 * recomputation), in order to perform propagation the member
1951 * function status must be used.
1952 *
1953 * Committing with choices must be carried
1954 * out in the same order as the choices have been
1955 * obtained by the member function Space::choice().
1956 *
1957 * It is perfectly okay to add constraints interleaved with
1958 * choices (provided they are in the right order).
1959 * However, if propagation is performed by calling the member
1960 * function status and then new choices are
1961 * computed, these choices are different.
1962 *
1963 * Only choices can be used that are up-to-date in the following
1964 * sense: if a new choice is created (via the choice member
1965 * function), no older choices can be used.
1966 *
1967 * Committing throws the following exceptions:
1968 * - SpaceIllegalAlternative, if \a a is not smaller than the number
1969 * of alternatives supported by the choice \a c.
1970 */
1971 GECODE_KERNEL_EXPORT
1972 void _trycommit(const Choice& c, unsigned int a);
1973
1974 /// Find trace recorder if exists
1975 GECODE_KERNEL_EXPORT
1976 TraceRecorder* findtracerecorder(void);
1977 /// Trace posting event
1978 GECODE_KERNEL_EXPORT
1979 void post(const PostInfo& pi);
1980
1981 /**
1982 * \brief Notice that an actor must be disposed
1983 *
1984 * Note that \a a might be a marked pointer where the mark
1985 * indicates that \a a is a trace recorder.
1986 */
1987 GECODE_KERNEL_EXPORT
1988 void ap_notice_dispose(Actor* a, bool d);
1989 /**
1990 * \brief Ignore that an actor must be disposed
1991 *
1992 * Note that \a a might be a marked pointer where the mark
1993 * indicates that \a a is a trace recorder.
1994 */
1995 GECODE_KERNEL_EXPORT
1996 void ap_ignore_dispose(Actor* a, bool d);
1997 public:
1998 /**
1999 * \brief Default constructor
2000 * \ingroup TaskModelScript
2001 */
2002 GECODE_KERNEL_EXPORT
2003 Space(void);
2004 /**
2005 * \brief Constructor for cloning
2006 *
2007 * Must copy and update all data structures (such as variables
2008 * and variable arrays) required by the subclass of Space.
2009 *
2010 * Should not be used directly, use Space::clone to create a clone
2011 * of a Space.
2012 *
2013 * \ingroup TaskModelScript
2014 */
2015 GECODE_KERNEL_EXPORT
2016 Space(Space& s);
2017 /// Assignment operator
2018 Space& operator =(const Space& s) = default;
2019 /**
2020 * \brief Destructor
2021 * \ingroup TaskModelScript
2022 */
2023 GECODE_KERNEL_EXPORT
2024 virtual ~Space(void);
2025 /**
2026 * \brief Copying member function
2027 *
2028 * Must create a new object using the constructor for cloning.
2029 *
2030 * Should not be used directly, use Space::clone to create a clone
2031 * of a Space.
2032 *
2033 * \ingroup TaskModelScript
2034 */
2035 virtual Space* copy(void) = 0;
2036 /**
2037 * \brief Constrain function for best solution search
2038 *
2039 * Must constrain this space to be better than the so far best
2040 * solution \a best.
2041 *
2042 * The default function does nothing.
2043 *
2044 * \ingroup TaskModelScript
2045 */
2046 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2047 /**
2048 * \brief Master configuration function for meta search engines
2049 *
2050 * This configuration function is used by both restart and
2051 * portfolio meta search engines.
2052 *
2053 * \li A restart meta search engine calls this function on its
2054 * master space whenever it finds a solution or exploration
2055 * restarts. \a mi contains information about the current restart.
2056 *
2057 * If a solution has been found, then search will continue with
2058 * a restart id the function returns true, otherwise search
2059 * will continue.
2060 *
2061 * The default function posts no-goods obtained from \a mi.
2062 *
2063 * \li A portfolio meta engine calls this function once on
2064 * the master space. The return value is ignored.
2065 *
2066 * The default function does nothing.
2067 *
2068 * \ingroup TaskModelScript
2069 */
2070 GECODE_KERNEL_EXPORT
2071 virtual bool master(const MetaInfo& mi);
2072 /**
2073 * \brief Slave configuration function for meta search engines
2074 *
2075 * This configuration function is used by both restart and
2076 * portfolio meta search engines.
2077 *
2078 * \li A restart meta search engine calls this function on its
2079 * slave space whenever it finds a solution or exploration
2080 * restarts. \a mi contains information about the current restart.
2081 *
2082 * If the function returns true, the search on the slave space is
2083 * considered complete, i.e., if it fails or exhaustively explores the
2084 * entire search space, the meta search engine finishes. If the
2085 * function returns false, the search on the slave space is considered
2086 * incomplete, and the meta engine will restart the search regardless
2087 * of whether the search on the slave space finishes or times out.
2088 *
2089 * \li A portfolio meta engine calls this function once on each asset
2090 * (that is, on each slave) and passes the number of the asset,
2091 * starting from zero.
2092 *
2093 * The default function does nothing and returns true.
2094 *
2095 * \ingroup TaskModelScript
2096 */
2097 GECODE_KERNEL_EXPORT
2098 virtual bool slave(const MetaInfo& mi);
2099
2100 /*
2101 * Member functions for search engines
2102 *
2103 */
2104
2105 /**
2106 * \brief Query space status
2107 *
2108 * Propagates the space until fixpoint or failure;
2109 * updates the statistics information \a stat; and:
2110 * - if the space is failed, SpaceStatus::SS_FAILED is returned.
2111 * - if the space is not failed but the space has no brancher left,
2112 * SpaceStatus::SS_SOLVED is returned.
2113 * - otherwise, SpaceStatus::SS_BRANCH is returned.
2114 * \ingroup TaskSearch
2115 */
2116 GECODE_KERNEL_EXPORT
2117 SpaceStatus status(StatusStatistics& stat=unused_status);
2118
2119 /**
2120 * \brief Create new choice for current brancher
2121 *
2122 * This member function can only be called after the member function
2123 * Space::status on the same space has been called and in between
2124 * no non-const member function has been called on this space.
2125 *
2126 * Moreover, the member function can only be called at most once
2127 * (otherwise, it might generate conflicting choices).
2128 *
2129 * Note that the above invariant only pertains to calls of member
2130 * functions of the same space. If the invariant is violated, the
2131 * system is likely to crash (hopefully it does). In particular, if
2132 * applied to a space with no current brancher, the system will
2133 * crash.
2134 *
2135 * After a new choice has been created, no older choices
2136 * can be used on the space.
2137 *
2138 * If the status() member function has returned that the space has
2139 * no more branchers (that is, the result was either SS_FAILED or
2140 * SS_SOLVED), a call to choice() will return nullptr and purge
2141 * all remaining branchers inside the space. This is interesting
2142 * for the case SS_SOLVED, where the call to choice can serve as
2143 * garbage collection.
2144 *
2145 * Throws an exception of type SpaceNotStable when applied to a not
2146 * yet stable space.
2147 *
2148 * \ingroup TaskSearch
2149 */
2150 GECODE_KERNEL_EXPORT
2151 const Choice* choice(void);
2152
2153 /**
2154 * \brief Create new choice from \a e
2155 *
2156 * The archived representation \a e must have been created from
2157 * a Choice that is compatible with this space (i.e., created from
2158 * the same model).
2159 *
2160 * \ingroup TaskSearch
2161 */
2162 GECODE_KERNEL_EXPORT
2163 const Choice* choice(Archive& e) const;
2164
2165 /**
2166 * \brief Clone space
2167 *
2168 * Assumes that the space is stable and not failed. If the space is
2169 * failed, an exception of type SpaceFailed is thrown. If the space
2170 * is not stable, an exception of SpaceNotStable is thrown.
2171 *
2172 * Otherwise, a clone of the space is returned and the statistics
2173 * information \a stat is updated.
2174 *
2175 * Throws an exception of type SpaceNotCloned when the copy constructor
2176 * of the Space class is not invoked during cloning.
2177 *
2178 * \ingroup TaskSearch
2179 */
2180 Space* clone(CloneStatistics& stat=unused_clone) const;
2181
2182 /**
2183 * \brief Commit choice \a c for alternative \a a
2184 *
2185 * The current brancher in the space performs a commit from
2186 * the information provided by the choice \a c
2187 * and the alternative \a a. The statistics information \a stat is
2188 * updated.
2189 *
2190 * Note that no propagation is perfomed (to support path
2191 * recomputation), in order to perform propagation the member
2192 * function status must be used.
2193 *
2194 * Committing with choices must be carried
2195 * out in the same order as the choices have been
2196 * obtained by the member function Space::choice().
2197 *
2198 * It is perfectly okay to add constraints interleaved with
2199 * choices (provided they are in the right order).
2200 * However, if propagation is performed by calling the member
2201 * function status and then new choices are
2202 * computed, these choices are different.
2203 *
2204 * Only choices can be used that are up-to-date in the following
2205 * sense: if a new choice is created (via the choice member
2206 * function), no older choices can be used.
2207 *
2208 * Committing throws the following exceptions:
2209 * - SpaceNoBrancher, if the space has no current brancher (it is
2210 * already solved).
2211 * - SpaceIllegalAlternative, if \a a is not smaller than the number
2212 * of alternatives supported by the choice \a c.
2213 *
2214 * \ingroup TaskSearch
2215 */
2216 void commit(const Choice& c, unsigned int a,
2217 CommitStatistics& stat=unused_commit);
2218 /**
2219 * \brief If possible, commit choice \a c for alternative \a a
2220 *
2221 * The current brancher in the space performs a commit from
2222 * the information provided by the choice \a c
2223 * and the alternative \a a. The statistics information \a stat is
2224 * updated.
2225 *
2226 * Note that no propagation is perfomed (to support path
2227 * recomputation), in order to perform propagation the member
2228 * function status must be used.
2229 *
2230 * Committing with choices must be carried
2231 * out in the same order as the choices have been
2232 * obtained by the member function Space::choice().
2233 *
2234 * It is perfectly okay to add constraints interleaved with
2235 * choices (provided they are in the right order).
2236 * However, if propagation is performed by calling the member
2237 * function status and then new choices are
2238 * computed, these choices are different.
2239 *
2240 * Only choices can be used that are up-to-date in the following
2241 * sense: if a new choice is created (via the choice member
2242 * function), no older choices can be used.
2243 *
2244 * Committing throws the following exceptions:
2245 * - SpaceIllegalAlternative, if \a a is not smaller than the number
2246 * of alternatives supported by the choice \a c.
2247 *
2248 * \ingroup TaskSearch
2249 */
2250 void trycommit(const Choice& c, unsigned int a,
2251 CommitStatistics& stat=unused_commit);
2252 /**
2253 * \brief Create no-good literal for choice \a c and alternative \a a
2254 *
2255 * The current brancher in the space \a home creates a no-good literal
2256 * from the information provided by the choice \a c and the alternative
2257 * \a a. The brancher has the following options:
2258 * - it returns nullptr for all alternatives \a a. This means that the
2259 * brancher does not support no-good literals.
2260 * - it returns nullptr for the last alternative \a a. This means that
2261 * this alternative is equivalent to the negation of the disjunction
2262 * of all other alternatives.
2263 *
2264 * It throws the following exceptions:
2265 * - SpaceIllegalAlternative, if \a a is not smaller than the number
2266 * of alternatives supported by the choice \a c.
2267 *
2268 * \ingroup TaskSearch
2269 */
2270 GECODE_KERNEL_EXPORT
2271 NGL* ngl(const Choice& c, unsigned int a);
2272
2273 /**
2274 * \brief Print branch for choice \a c and alternative \a a
2275 *
2276 * Prints an explanation of the alternative \a a of choice \a c
2277 * on the stream \a o.
2278 *
2279 * Print throws the following exceptions:
2280 * - SpaceNoBrancher, if the space has no current brancher (it is
2281 * already solved).
2282 * - SpaceIllegalAlternative, if \a a is not smaller than the number
2283 * of alternatives supported by the choice \a c.
2284 *
2285 * \ingroup TaskSearch
2286 */
2287 GECODE_KERNEL_EXPORT
2288 void print(const Choice& c, unsigned int a, std::ostream& o) const;
2289
2290 /**
2291 * \brief Notice actor property
2292 *
2293 * Make the space notice that the actor \a a has the property \a p.
2294 * Note that the same property can only be noticed once for an actor
2295 * unless \a duplicate is true.
2296 * \ingroup TaskActor
2297 */
2298 GECODE_KERNEL_EXPORT
2299 void notice(Actor& a, ActorProperty p, bool duplicate=false);
2300 /**
2301 * \brief Ignore actor property
2302 *
2303 * Make the space ignore that the actor \a a has the property \a p.
2304 * Note that a property must be ignored before an actor is disposed.
2305 * \ingroup TaskActor
2306 */
2307 GECODE_KERNEL_EXPORT
2308 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2309
2310
2311 /**
2312 * \brief %Propagator \a p is subsumed
2313 *
2314 * First disposes the propagator and then returns subsumption.
2315 *
2316 * \warning Has a side-effect on the propagator. Overwrites
2317 * the modification event delta of a propagator.
2318 * Use only directly with returning from propagation.
2319 * \ingroup TaskActorStatus
2320 */
2321 ExecStatus ES_SUBSUMED(Propagator& p);
2322 /**
2323 * \brief %Propagator \a p is subsumed
2324 *
2325 * The size of the propagator is \a s.
2326 *
2327 * Note that the propagator must be subsumed and also disposed. So
2328 * in general, there should be code such as
2329 * \code return ES_SUBSUMED_DISPOSE(home,*this,dispose(home)) \endcode.
2330 *
2331 * \warning Has a side-effect on the propagator. Overwrites
2332 * the modification event delta of a propagator.
2333 * Use only directly with returning from propagation.
2334 * \ingroup TaskActorStatus
2335 */
2336 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
2337 /**
2338 * \brief %Propagator \a p has computed partial fixpoint
2339 *
2340 * %Set modification event delta to \a med and schedule propagator
2341 * accordingly.
2342 *
2343 * \warning Has a side-effect on the propagator.
2344 * Use only directly with returning from propagation.
2345 * \ingroup TaskActorStatus
2346 */
2347 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2348 /**
2349 * \brief %Propagator \a p has not computed partial fixpoint
2350 *
2351 * Combine current modification event delta with \a and schedule
2352 * propagator accordingly.
2353 *
2354 * \warning Has a side-effect on the propagator.
2355 * Use only directly with returning from propagation.
2356 * \ingroup TaskActorStatus
2357 */
2358 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
2359
2360 /**
2361 * \brief %Advisor \a a must be disposed
2362 *
2363 * Disposes the advisor and returns that the propagator of \a a
2364 * need not be run.
2365 *
2366 * \warning Has a side-effect on the advisor. Use only directly when
2367 * returning from advise.
2368 * \ingroup TaskActorStatus
2369 */
2370 template<class A>
2371 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
2372 /**
2373 * \brief %Advisor \a a must be disposed and its propagator must be run
2374 *
2375 * Disposes the advisor and returns that the propagator of \a a
2376 * must be run.
2377 *
2378 * \warning Has a side-effect on the advisor. Use only directly when
2379 * returning from advise.
2380 * \ingroup TaskActorStatus
2381 */
2382 template<class A>
2383 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
2384 /**
2385 * \brief %Advisor \a a must be disposed and its propagator must be forcefully rescheduled
2386 *
2387 * Disposes the advisor and returns that the propagator of \a a
2388 * must be run and must be forcefully rescheduled (including
2389 * recomputation of cost).
2390 *
2391 * \warning Has a side-effect on the advisor. Use only directly when
2392 * returning from advise.
2393 * \ingroup TaskActorStatus
2394 */
2395 template<class A>
2396 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
2397
2398 /**
2399 * \brief Fail space
2400 *
2401 * This is useful for failing outside of actors. Never use inside
2402 * a propagate or commit member function. The system will crash!
2403 * \ingroup TaskActor
2404 */
2405 void fail(void);
2406 /**
2407 * \brief Check whether space is failed
2408 *
2409 * Note that this does not perform propagation. This is useful
2410 * for posting actors: only if a space is not yet failed, new
2411 * actors are allowed to be created.
2412 * \ingroup TaskActor
2413 */
2414 bool failed(void) const;
2415 /**
2416 * \brief Return if space is stable (at fixpoint or failed)
2417 * \ingroup TaskActor
2418 */
2419 bool stable(void) const;
2420
2421 /// \name Conversion from Space to Home
2422 //@{
2423 /// Return a home for this space with the information that \a p is being rewritten
2424 Home operator ()(Propagator& p);
2425 /// Return a home for this space with propagator group information \a pg
2426 Home operator ()(PropagatorGroup pg);
2427 /// Return a home for this space with brancher group information \a bg
2428 Home operator ()(BrancherGroup bg);
2429 //@}
2430
2431 /**
2432 * \defgroup FuncMemSpace Space-memory management
2433 * \ingroup FuncMem
2434 */
2435 //@{
2436 /**
2437 * \brief Allocate block of \a n objects of type \a T from space heap
2438 *
2439 * Note that this function implements C++ semantics: the default
2440 * constructor of \a T is run for all \a n objects.
2441 */
2442 template<class T>
2443 T* alloc(long unsigned int n);
2444 /**
2445 * \brief Allocate block of \a n objects of type \a T from space heap
2446 *
2447 * Note that this function implements C++ semantics: the default
2448 * constructor of \a T is run for all \a n objects.
2449 */
2450 template<class T>
2451 T* alloc(long int n);
2452 /**
2453 * \brief Allocate block of \a n objects of type \a T from space heap
2454 *
2455 * Note that this function implements C++ semantics: the default
2456 * constructor of \a T is run for all \a n objects.
2457 */
2458 template<class T>
2459 T* alloc(unsigned int n);
2460 /**
2461 * \brief Allocate block of \a n objects of type \a T from space heap
2462 *
2463 * Note that this function implements C++ semantics: the default
2464 * constructor of \a T is run for all \a n objects.
2465 */
2466 template<class T>
2467 T* alloc(int n);
2468 /**
2469 * \brief Delete \a n objects allocated from space heap starting at \a b
2470 *
2471 * Note that this function implements C++ semantics: the destructor
2472 * of \a T is run for all \a n objects.
2473 *
2474 * Note that the memory is not freed, it is just scheduled for later
2475 * reusal.
2476 */
2477 template<class T>
2478 void free(T* b, long unsigned int n);
2479 /**
2480 * \brief Delete \a n objects allocated from space heap starting at \a b
2481 *
2482 * Note that this function implements C++ semantics: the destructor
2483 * of \a T is run for all \a n objects.
2484 *
2485 * Note that the memory is not freed, it is just scheduled for later
2486 * reusal.
2487 */
2488 template<class T>
2489 void free(T* b, long int n);
2490 /**
2491 * \brief Delete \a n objects allocated from space heap starting at \a b
2492 *
2493 * Note that this function implements C++ semantics: the destructor
2494 * of \a T is run for all \a n objects.
2495 *
2496 * Note that the memory is not freed, it is just scheduled for later
2497 * reusal.
2498 */
2499 template<class T>
2500 void free(T* b, unsigned int n);
2501 /**
2502 * \brief Delete \a n objects allocated from space heap starting at \a b
2503 *
2504 * Note that this function implements C++ semantics: the destructor
2505 * of \a T is run for all \a n objects.
2506 *
2507 * Note that the memory is not freed, it is just scheduled for later
2508 * reusal.
2509 */
2510 template<class T>
2511 void free(T* b, int n);
2512 /**
2513 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap
2514 *
2515 * Note that this function implements C++ semantics: the copy constructor
2516 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
2517 * constructor of \a T is run for all remaining
2518 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
2519 * run for all \a n objects in \a b.
2520 *
2521 * Returns the address of the new block.
2522 */
2523 template<class T>
2524 T* realloc(T* b, long unsigned int n, long unsigned int m);
2525 /**
2526 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap
2527 *
2528 * Note that this function implements C++ semantics: the copy constructor
2529 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
2530 * constructor of \a T is run for all remaining
2531 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
2532 * run for all \a n objects in \a b.
2533 *
2534 * Returns the address of the new block.
2535 */
2536 template<class T>
2537 T* realloc(T* b, long int n, long int m);
2538 /**
2539 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap
2540 *
2541 * Note that this function implements C++ semantics: the copy constructor
2542 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
2543 * constructor of \a T is run for all remaining
2544 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
2545 * run for all \a n objects in \a b.
2546 *
2547 * Returns the address of the new block.
2548 */
2549 template<class T>
2550 T* realloc(T* b, unsigned int n, unsigned int m);
2551 /**
2552 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap
2553 *
2554 * Note that this function implements C++ semantics: the copy constructor
2555 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
2556 * constructor of \a T is run for all remaining
2557 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
2558 * run for all \a n objects in \a b.
2559 *
2560 * Returns the address of the new block.
2561 */
2562 template<class T>
2563 T* realloc(T* b, int n, int m);
2564 /**
2565 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap
2566 *
2567 * Returns the address of the new block.
2568 *
2569 * This is a specialization for performance.
2570 */
2571 template<class T>
2572 T** realloc(T** b, long unsigned int n, long unsigned int m);
2573 /**
2574 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap
2575 *
2576 * Returns the address of the new block.
2577 *
2578 * This is a specialization for performance.
2579 */
2580 template<class T>
2581 T** realloc(T** b, long int n, long int m);
2582 /**
2583 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap
2584 *
2585 * Returns the address of the new block.
2586 *
2587 * This is a specialization for performance.
2588 */
2589 template<class T>
2590 T** realloc(T** b, unsigned int n, unsigned int m);
2591 /**
2592 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap
2593 *
2594 * Returns the address of the new block.
2595 *
2596 * This is a specialization for performance.
2597 */
2598 template<class T>
2599 T** realloc(T** b, int n, int m);
2600 /// Allocate memory on space heap
2601 void* ralloc(size_t s);
2602 /// Free memory previously allocated with alloc (might be reused later)
2603 void rfree(void* p, size_t s);
2604 /// Reallocate memory block starting at \a b from size \a n to size \a s
2605 void* rrealloc(void* b, size_t n, size_t m);
2606 /// Allocate from freelist-managed memory
2607 template<size_t> void* fl_alloc(void);
2608 /**
2609 * \brief Return freelist-managed memory to freelist
2610 *
2611 * The first list element to be retuned is \a f, the last is \a l.
2612 */
2613 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2614 //@}
2615 /// Construction routines
2616 //@{
2617 /**
2618 * \brief Constructs a single object of type \a T from space heap using the default constructor.
2619 */
2620 template<class T>
2621 T& construct(void);
2622 /**
2623 * \brief Constructs a single object of type \a T from space heap using a unary constructor.
2624 *
2625 * The parameter is passed as a const reference.
2626 */
2627 template<class T, typename A1>
2628 T& construct(A1 const& a1);
2629 /**
2630 * \brief Constructs a single object of type \a T from space heap using a binary constructor.
2631 *
2632 * The parameters are passed as const references.
2633 */
2634 template<class T, typename A1, typename A2>
2635 T& construct(A1 const& a1, A2 const& a2);
2636 /**
2637 * \brief Constructs a single object of type \a T from space heap using a ternary constructor.
2638 *
2639 * The parameters are passed as const references.
2640 */
2641 template<class T, typename A1, typename A2, typename A3>
2642 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2643 /**
2644 * \brief Constructs a single object of type \a T from space heap using a quaternary constructor.
2645 *
2646 * The parameters are passed as const references.
2647 */
2648 template<class T, typename A1, typename A2, typename A3, typename A4>
2649 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2650 /**
2651 * \brief Constructs a single object of type \a T from space heap using a quinary constructor.
2652 *
2653 * The parameters are passed as const references.
2654 */
2655 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2656 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2657 //@}
2658
2659 /// \name Low-level support for AFC
2660 //@{
2661 /// %Set AFC decay factor to \a d
2662 void afc_decay(double d);
2663 /// Return AFC decay factor
2664 double afc_decay(void) const;
2665 /// Unshare AFC information for all propagators
2666 GECODE_KERNEL_EXPORT void afc_unshare(void);
2667 //@}
2668
2669 protected:
2670 /**
2671 * \brief Class to iterate over propagators of a space
2672 *
2673 * Note that the iterator cannot be used during cloning.
2674 */
2675 class Propagators {
2676 private:
2677 /// Current space
2678 Space& home;
2679 /// Current queue
2680 ActorLink* q;
2681 /// Current propagator
2682 ActorLink* c;
2683 /// End mark
2684 ActorLink* e;
2685 public:
2686 /// Initialize
2687 Propagators(Space& home);
2688 /// Test whether there are propagators left
2689 bool operator ()(void) const;
2690 /// Move iterator to next propagator
2691 void operator ++(void);
2692 /// Return propagator
2693 Propagator& propagator(void) const;
2694 };
2695 /**
2696 * \brief Class to iterate over scheduled propagators of a space
2697 *
2698 * Note that the iterator cannot be used during cloning.
2699 */
2700 class ScheduledPropagators {
2701 private:
2702 /// current space
2703 Space& home;
2704 /// current queue
2705 ActorLink* q;
2706 /// current propagator
2707 ActorLink* c;
2708 /// end mark
2709 ActorLink* e;
2710 public:
2711 /// Initialize
2712 ScheduledPropagators(Space& home);
2713 /// Test whether there are propagators left
2714 bool operator ()(void) const;
2715 /// Move iterator to next propagator
2716 void operator ++(void);
2717 /// Return propagator
2718 Propagator& propagator(void) const;
2719 };
2720 /**
2721 * \brief Class to iterate over idle propagators of a space
2722 *
2723 * Note that the iterator cannot be used during cloning.
2724 */
2725 class IdlePropagators {
2726 private:
2727 /// Current propagator
2728 ActorLink* c;
2729 /// End mark
2730 ActorLink* e;
2731 public:
2732 /// Initialize
2733 IdlePropagators(Space& home);
2734 /// Test whether there are propagators left
2735 bool operator ()(void) const;
2736 /// Move iterator to next propagator
2737 void operator ++(void);
2738 /// Return propagator
2739 Propagator& propagator(void) const;
2740 };
2741 /**
2742 * \brief Class to iterate over branchers of a space
2743 *
2744 * Note that the iterator cannot be used during cloning.
2745 */
2746 class Branchers {
2747 private:
2748 /// current brancher
2749 ActorLink* c;
2750 /// end mark
2751 ActorLink* e;
2752 public:
2753 /// Initialize
2754 Branchers(Space& home);
2755 /// Test whether there are branchers left
2756 bool operator ()(void) const;
2757 /// Move iterator to next brancher
2758 void operator ++(void);
2759 /// Return propagator
2760 Brancher& brancher(void) const;
2761 };
2762 };
2763
2764 /// Class to iterate over propagators in a group
2765 class Propagators {
2766 private:
2767 /// Propagators
2768 Space::Propagators ps;
2769 /// Current group
2770 PropagatorGroup g;
2771 public:
2772 /// Initialize
2773 Propagators(const Space& home, PropagatorGroup g);
2774 /// Test whether there are propagators left
2775 bool operator ()(void) const;
2776 /// Move iterator to next propagator
2777 void operator ++(void);
2778 /// Return propagator
2779 const Propagator& propagator(void) const;
2780 };
2781
2782 /// Class to iterate over branchers in a group
2783 class Branchers {
2784 private:
2785 /// Branchers
2786 Space::Branchers bs;
2787 /// Current group
2788 BrancherGroup g;
2789 public:
2790 /// Initialize
2791 Branchers(const Space& home, BrancherGroup g);
2792 /// Test whether there are branchers left
2793 bool operator ()(void) const;
2794 /// Move iterator to next brancher
2795 void operator ++(void);
2796 /// Return propagator
2797 const Brancher& brancher(void) const;
2798 };
2799
2800
2801
2802
2803 /*
2804 * Memory management
2805 *
2806 */
2807
2808 // Space allocation: general space heaps and free lists
2809 forceinline void*
2810 Space::ralloc(size_t s) {
2811 return mm.alloc(ssd.data().sm,s);
2812 }
2813 forceinline void
2814 Space::rfree(void* p, size_t s) {
2815 return mm.reuse(p,s);
2816 }
2817 forceinline void*
2818 Space::rrealloc(void* _b, size_t n, size_t m) {
2819 char* b = static_cast<char*>(_b);
2820 if (n < m) {
2821 char* p = static_cast<char*>(ralloc(m));
2822 memcpy(p,b,n);
2823 rfree(b,n);
2824 return p;
2825 } else {
2826 rfree(b+m,m-n);
2827 return b;
2828 }
2829 }
2830
2831 template<size_t s>
2832 forceinline void*
2833 Space::fl_alloc(void) {
2834 return mm.template fl_alloc<s>(ssd.data().sm);
2835 }
2836 template<size_t s>
2837 forceinline void
2838 Space::fl_dispose(FreeList* f, FreeList* l) {
2839 mm.template fl_dispose<s>(f,l);
2840 }
2841
2842 /*
2843 * Typed allocation routines
2844 *
2845 */
2846 template<class T>
2847 forceinline T*
2848 Space::alloc(long unsigned int n) {
2849 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2850 for (long unsigned int i=0; i<n; i++)
2851 (void) new (p+i) T();
2852 return p;
2853 }
2854 template<class T>
2855 forceinline T*
2856 Space::alloc(long int n) {
2857 assert(n >= 0);
2858 return alloc<T>(static_cast<long unsigned int>(n));
2859 }
2860 template<class T>
2861 forceinline T*
2862 Space::alloc(unsigned int n) {
2863 return alloc<T>(static_cast<long unsigned int>(n));
2864 }
2865 template<class T>
2866 forceinline T*
2867 Space::alloc(int n) {
2868 assert(n >= 0);
2869 return alloc<T>(static_cast<long unsigned int>(n));
2870 }
2871
2872 template<class T>
2873 forceinline void
2874 Space::free(T* b, long unsigned int n) {
2875 for (long unsigned int i=0; i<n; i++)
2876 b[i].~T();
2877 rfree(b,n*sizeof(T));
2878 }
2879 template<class T>
2880 forceinline void
2881 Space::free(T* b, long int n) {
2882 assert(n >= 0);
2883 free<T>(b,static_cast<long unsigned int>(n));
2884 }
2885 template<class T>
2886 forceinline void
2887 Space::free(T* b, unsigned int n) {
2888 free<T>(b,static_cast<long unsigned int>(n));
2889 }
2890 template<class T>
2891 forceinline void
2892 Space::free(T* b, int n) {
2893 assert(n >= 0);
2894 free<T>(b,static_cast<long unsigned int>(n));
2895 }
2896
2897 template<class T>
2898 forceinline T*
2899 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2900 if (n < m) {
2901 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2902 for (long unsigned int i=0; i<n; i++)
2903 (void) new (p+i) T(b[i]);
2904 for (long unsigned int i=n; i<m; i++)
2905 (void) new (p+i) T();
2906 free<T>(b,n);
2907 return p;
2908 } else {
2909 free<T>(b+m,m-n);
2910 return b;
2911 }
2912 }
2913 template<class T>
2914 forceinline T*
2915 Space::realloc(T* b, long int n, long int m) {
2916 assert((n >= 0) && (m >= 0));
2917 return realloc<T>(b,static_cast<long unsigned int>(n),
2918 static_cast<long unsigned int>(m));
2919 }
2920 template<class T>
2921 forceinline T*
2922 Space::realloc(T* b, unsigned int n, unsigned int m) {
2923 return realloc<T>(b,static_cast<long unsigned int>(n),
2924 static_cast<long unsigned int>(m));
2925 }
2926 template<class T>
2927 forceinline T*
2928 Space::realloc(T* b, int n, int m) {
2929 assert((n >= 0) && (m >= 0));
2930 return realloc<T>(b,static_cast<long unsigned int>(n),
2931 static_cast<long unsigned int>(m));
2932 }
2933
2934#define GECODE_KERNEL_REALLOC(T) \
2935 template<> \
2936 forceinline T* \
2937 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2938 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2939 } \
2940 template<> \
2941 forceinline T* \
2942 Space::realloc<T>(T* b, long int n, long int m) { \
2943 assert((n >= 0) && (m >= 0)); \
2944 return realloc<T>(b,static_cast<long unsigned int>(n), \
2945 static_cast<long unsigned int>(m)); \
2946 } \
2947 template<> \
2948 forceinline T* \
2949 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2950 return realloc<T>(b,static_cast<long unsigned int>(n), \
2951 static_cast<long unsigned int>(m)); \
2952 } \
2953 template<> \
2954 forceinline T* \
2955 Space::realloc<T>(T* b, int n, int m) { \
2956 assert((n >= 0) && (m >= 0)); \
2957 return realloc<T>(b,static_cast<long unsigned int>(n), \
2958 static_cast<long unsigned int>(m)); \
2959 }
2960
2961 GECODE_KERNEL_REALLOC(bool)
2962 GECODE_KERNEL_REALLOC(signed char)
2963 GECODE_KERNEL_REALLOC(unsigned char)
2964 GECODE_KERNEL_REALLOC(signed short int)
2965 GECODE_KERNEL_REALLOC(unsigned short int)
2966 GECODE_KERNEL_REALLOC(signed int)
2967 GECODE_KERNEL_REALLOC(unsigned int)
2968 GECODE_KERNEL_REALLOC(signed long int)
2969 GECODE_KERNEL_REALLOC(unsigned long int)
2970 GECODE_KERNEL_REALLOC(float)
2971 GECODE_KERNEL_REALLOC(double)
2972
2973#undef GECODE_KERNEL_REALLOC
2974
2975 template<class T>
2976 forceinline T**
2977 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2978 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2979 }
2980 template<class T>
2981 forceinline T**
2982 Space::realloc(T** b, long int n, long int m) {
2983 assert((n >= 0) && (m >= 0));
2984 return realloc<T*>(b,static_cast<long unsigned int>(n),
2985 static_cast<long unsigned int>(m));
2986 }
2987 template<class T>
2988 forceinline T**
2989 Space::realloc(T** b, unsigned int n, unsigned int m) {
2990 return realloc<T*>(b,static_cast<long unsigned int>(n),
2991 static_cast<long unsigned int>(m));
2992 }
2993 template<class T>
2994 forceinline T**
2995 Space::realloc(T** b, int n, int m) {
2996 assert((n >= 0) && (m >= 0));
2997 return realloc<T*>(b,static_cast<long unsigned int>(n),
2998 static_cast<long unsigned int>(m));
2999 }
3000
3001
3002#ifdef GECODE_HAS_VAR_DISPOSE
3003 template<class VIC>
3004 forceinline VarImpBase*
3005 Space::vars_d(void) const {
3006 return _vars_d[VIC::idx_d];
3007 }
3008 template<class VIC>
3009 forceinline void
3010 Space::vars_d(VarImpBase* x) {
3011 _vars_d[VIC::idx_d] = x;
3012 }
3013#endif
3014
3015 // Space allocated entities: Actors, variable implementations, and advisors
3016 forceinline void
3017 Actor::operator delete(void*) {}
3018 forceinline void
3019 Actor::operator delete(void*, Space&) {}
3020 forceinline void*
3021 Actor::operator new(size_t s, Space& home) {
3022 return home.ralloc(s);
3023 }
3024
3025 template<class VIC>
3026 forceinline void
3027 VarImp<VIC>::operator delete(void*) {}
3028 template<class VIC>
3029 forceinline void
3030 VarImp<VIC>::operator delete(void*, Space&) {}
3031 template<class VIC>
3032 forceinline void*
3033 VarImp<VIC>::operator new(size_t s, Space& home) {
3034 return home.ralloc(s);
3035 }
3036
3037#ifndef __GNUC__
3038 forceinline void
3039 Advisor::operator delete(void*) {}
3040#endif
3041 forceinline void
3042 Advisor::operator delete(void*, Space&) {}
3043 forceinline void*
3044 Advisor::operator new(size_t s, Space& home) {
3045 return home.ralloc(s);
3046 }
3047
3048 forceinline void
3049 NGL::operator delete(void*) {}
3050 forceinline void
3051 NGL::operator delete(void*, Space&) {}
3052 forceinline void*
3053 NGL::operator new(size_t s, Space& home) {
3054 return home.ralloc(s);
3055 }
3056
3057
3058 /*
3059 * No-goods
3060 *
3061 */
3062 forceinline
3063 NoGoods::NoGoods(void)
3064 : n(0) {}
3065 forceinline unsigned long int
3066 NoGoods::ng(void) const {
3067 return n;
3068 }
3069 forceinline void
3070 NoGoods::ng(unsigned long int n0) {
3071 n=n0;
3072 }
3073 forceinline
3074 NoGoods::~NoGoods(void) {}
3075
3076
3077 /*
3078 * Information from meta search engines
3079 */
3080 forceinline
3081 MetaInfo::MetaInfo(unsigned long int r0,
3082 unsigned long long int s0,
3083 unsigned long long int f0,
3084 const Space* l0,
3085 NoGoods& ng0)
3086 : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3087
3088 forceinline
3089 MetaInfo::MetaInfo(unsigned int a0)
3090 : t(PORTFOLIO), r(0), s(0), f(0), l(nullptr), ng(NoGoods::eng), a(a0) {}
3091
3092 forceinline MetaInfo::Type
3093 MetaInfo::type(void) const {
3094 return t;
3095 }
3096 forceinline unsigned long int
3097 MetaInfo::restart(void) const {
3098 assert(type() == RESTART);
3099 return r;
3100 }
3101 forceinline unsigned long long int
3102 MetaInfo::solution(void) const {
3103 assert(type() == RESTART);
3104 return s;
3105 }
3106 forceinline unsigned long long int
3107 MetaInfo::fail(void) const {
3108 assert(type() == RESTART);
3109 return f;
3110 }
3111 forceinline const Space*
3112 MetaInfo::last(void) const {
3113 assert(type() == RESTART);
3114 return l;
3115 }
3116 forceinline const NoGoods&
3117 MetaInfo::nogoods(void) const {
3118 assert(type() == RESTART);
3119 return ng;
3120 }
3121 forceinline unsigned int
3122 MetaInfo::asset(void) const {
3123 assert(type() == PORTFOLIO);
3124 return a;
3125 }
3126
3127
3128
3129 /*
3130 * ActorLink
3131 *
3132 */
3133 forceinline ActorLink*
3134 ActorLink::prev(void) const {
3135 return _prev;
3136 }
3137
3138 forceinline ActorLink*
3139 ActorLink::next(void) const {
3140 return _next;
3141 }
3142
3143 forceinline ActorLink**
3144 ActorLink::next_ref(void) {
3145 return &_next;
3146 }
3147
3148 forceinline void
3149 ActorLink::prev(ActorLink* al) {
3150 _prev = al;
3151 }
3152
3153 forceinline void
3154 ActorLink::next(ActorLink* al) {
3155 _next = al;
3156 }
3157
3158 forceinline void
3159 ActorLink::unlink(void) {
3160 ActorLink* p = _prev; ActorLink* n = _next;
3161 p->_next = n; n->_prev = p;
3162 }
3163
3164 forceinline void
3165 ActorLink::init(void) {
3166 _next = this; _prev =this;
3167 }
3168
3169 forceinline void
3170 ActorLink::head(ActorLink* a) {
3171 // Inserts al at head of link-chain (that is, after this)
3172 ActorLink* n = _next;
3173 this->_next = a; a->_prev = this;
3174 a->_next = n; n->_prev = a;
3175 }
3176
3177 forceinline void
3178 ActorLink::tail(ActorLink* a) {
3179 // Inserts al at tail of link-chain (that is, before this)
3180 ActorLink* p = _prev;
3181 a->_next = this; this->_prev = a;
3182 p->_next = a; a->_prev = p;
3183 }
3184
3185 forceinline bool
3186 ActorLink::empty(void) const {
3187 return _next == this;
3188 }
3189
3190 template<class T>
3191 forceinline ActorLink*
3192 ActorLink::cast(T* a) {
3193 // Turning al into a reference is for gcc, assume is for MSVC
3194 GECODE_NOT_NULL(a);
3195 ActorLink& t = *a;
3196 return static_cast<ActorLink*>(&t);
3197 }
3198
3199 template<class T>
3200 forceinline const ActorLink*
3201 ActorLink::cast(const T* a) {
3202 // Turning al into a reference is for gcc, assume is for MSVC
3203 GECODE_NOT_NULL(a);
3204 const ActorLink& t = *a;
3205 return static_cast<const ActorLink*>(&t);
3206 }
3207
3208
3209 /*
3210 * Actor
3211 *
3212 */
3213 forceinline Actor*
3214 Actor::cast(ActorLink* al) {
3215 // Turning al into a reference is for gcc, assume is for MSVC
3216 GECODE_NOT_NULL(al);
3217 ActorLink& t = *al;
3218 return static_cast<Actor*>(&t);
3219 }
3220
3221 forceinline const Actor*
3222 Actor::cast(const ActorLink* al) {
3223 // Turning al into a reference is for gcc, assume is for MSVC
3224 GECODE_NOT_NULL(al);
3225 const ActorLink& t = *al;
3226 return static_cast<const Actor*>(&t);
3227 }
3228
3229 forceinline void
3230 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3231 s.notice(a,p,duplicate);
3232 }
3233
3234 forceinline Space*
3235 Space::clone(CloneStatistics&) const {
3236 // Clone is only const for search engines. During cloning, several data
3237 // structures are updated (e.g. forwarding pointers), so we have to
3238 // cast away the constness.
3239 return const_cast<Space*>(this)->_clone();
3240 }
3241
3242 forceinline void
3243 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3244 _commit(c,a);
3245 }
3246
3247 forceinline void
3248 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3249 _trycommit(c,a);
3250 }
3251
3252 forceinline double
3253 Space::afc_decay(void) const {
3254 return ssd.data().gpi.decay();
3255 }
3256
3257 forceinline void
3258 Space::afc_decay(double d) {
3259 ssd.data().gpi.decay(d);
3260 }
3261
3262 forceinline size_t
3263 Actor::dispose(Space&) {
3264 return sizeof(*this);
3265 }
3266
3267
3268 /*
3269 * Home for posting actors
3270 *
3271 */
3272 forceinline
3273 Home::Home(Space& s0, Propagator* p0,
3274 PropagatorGroup pg0, BrancherGroup bg0)
3275 : s(s0), p(p0), pg(pg0), bg(bg0) {}
3276 forceinline
3277 Home::Home(const Home& h)
3278 : s(h.s), p(h.p), pg(h.pg), bg(h.bg) {}
3279 forceinline Home&
3280 Home::operator =(const Home& h) {
3281 s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3282 return *this;
3283 }
3284 forceinline
3285 Home::operator Space&(void) {
3286 return s;
3287 }
3288 forceinline Home
3289 Home::operator ()(Propagator& p) {
3290 return Home(s,&p);
3291 }
3292 forceinline Home
3293 Home::operator ()(PropagatorGroup pg) {
3294 return Home(s,nullptr,pg,BrancherGroup::def);
3295 }
3296 forceinline Home
3297 Home::operator ()(BrancherGroup bg) {
3298 return Home(s,nullptr,PropagatorGroup::def,bg);
3299 }
3300 forceinline Home
3301 Space::operator ()(Propagator& p) {
3302 return Home(*this,&p);
3303 }
3304 forceinline Home
3305 Space::operator ()(PropagatorGroup pg) {
3306 return Home(*this,nullptr,pg,BrancherGroup::def);
3307 }
3308 forceinline Home
3309 Space::operator ()(BrancherGroup bg) {
3310 return Home(*this,nullptr,PropagatorGroup::def,bg);
3311 }
3312 forceinline Propagator*
3313 Home::propagator(void) const {
3314 return p;
3315 }
3316 forceinline PropagatorGroup
3317 Home::propagatorgroup(void) const {
3318 return pg;
3319 }
3320 forceinline BrancherGroup
3321 Home::branchergroup(void) const {
3322 return bg;
3323 }
3324
3325 /*
3326 * View trace information
3327 *
3328 */
3329 forceinline void
3330 ViewTraceInfo::propagator(Propagator& p) {
3331 who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3332 }
3333 forceinline void
3334 ViewTraceInfo::brancher(Brancher& b) {
3335 who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3336 }
3337 forceinline void
3338 ViewTraceInfo::post(PropagatorGroup g) {
3339 who = (g.id() << 2) | POST;
3340 }
3341 forceinline void
3342 ViewTraceInfo::other(void) {
3343 who = OTHER;
3344 }
3345 forceinline ViewTraceInfo::What
3346 ViewTraceInfo::what(void) const {
3347 return static_cast<What>(who & 3);
3348 }
3349 forceinline const Propagator&
3350 ViewTraceInfo::propagator(void) const {
3351 assert(what() == PROPAGATOR);
3352 // Because PROPAGATOR == 0
3353 return *reinterpret_cast<Propagator*>(who);
3354 }
3355 forceinline const Brancher&
3356 ViewTraceInfo::brancher(void) const {
3357 assert(what() == BRANCHER);
3358 return *reinterpret_cast<Brancher*>(who & ~3);
3359 }
3360 forceinline PropagatorGroup
3361 ViewTraceInfo::post(void) const {
3362 assert(what() == POST);
3363 return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3364 }
3365
3366 /*
3367 * Post information
3368 */
3369 forceinline
3370 PostInfo::PostInfo(Home home)
3371 : h(home), pg(home.propagatorgroup()),
3372 pid(h.ssd.data().gpi.pid()),
3373 nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
3374 h.pc.p.vti.post(pg);
3375 }
3376
3377 forceinline
3378 PostInfo::~PostInfo(void) {
3379 if (!nested) {
3380 if (h.pc.p.bid_sc & Space::sc_trace)
3381 h.post(*this);
3382 h.pc.p.vti.other();
3383 }
3384 }
3385
3386
3387 /*
3388 * Propagate trace information
3389 *
3390 */
3391 forceinline
3392 PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0,
3393 const Propagator* p0, Status s0)
3394 : i(i0), g(g0), p(p0), s(s0) {}
3395 forceinline unsigned int
3396 PropagateTraceInfo::id(void) const {
3397 return i;
3398 }
3399 forceinline PropagatorGroup
3400 PropagateTraceInfo::group(void) const {
3401 return g;
3402 }
3403 forceinline const Propagator*
3404 PropagateTraceInfo::propagator(void) const {
3405 return p;
3406 }
3407 forceinline PropagateTraceInfo::Status
3408 PropagateTraceInfo::status(void) const {
3409 return s;
3410 }
3411
3412
3413 /*
3414 * Commit trace information
3415 *
3416 */
3417 forceinline
3418 CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
3419 unsigned int a0)
3420 : b(b0), c(c0), a(a0) {}
3421 forceinline unsigned int
3422 CommitTraceInfo::id(void) const {
3423 return b.id();
3424 }
3425 forceinline BrancherGroup
3426 CommitTraceInfo::group(void) const {
3427 return b.group();
3428 }
3429 forceinline const Brancher&
3430 CommitTraceInfo::brancher(void) const {
3431 return b;
3432 }
3433 forceinline const Choice&
3434 CommitTraceInfo::choice(void) const {
3435 return c;
3436 }
3437 forceinline unsigned int
3438 CommitTraceInfo::alternative(void) const {
3439 return a;
3440 }
3441
3442
3443 /*
3444 * Post trace information
3445 *
3446 */
3447 forceinline
3448 PostTraceInfo::PostTraceInfo(PropagatorGroup g0, Status s0, unsigned int n0)
3449 : g(g0), s(s0), n(n0) {}
3450 forceinline PropagatorGroup
3451 PostTraceInfo::group(void) const {
3452 return g;
3453 }
3454 forceinline PostTraceInfo::Status
3455 PostTraceInfo::status(void) const {
3456 return s;
3457 }
3458 forceinline unsigned int
3459 PostTraceInfo::propagators(void) const {
3460 return n;
3461 }
3462
3463
3464 /*
3465 * Propagator
3466 *
3467 */
3468 forceinline Propagator*
3469 Propagator::cast(ActorLink* al) {
3470 // Turning al into a reference is for gcc, assume is for MSVC
3471 GECODE_NOT_NULL(al);
3472 ActorLink& t = *al;
3473 return static_cast<Propagator*>(&t);
3474 }
3475
3476 forceinline const Propagator*
3477 Propagator::cast(const ActorLink* al) {
3478 // Turning al into a reference is for gcc, assume is for MSVC
3479 GECODE_NOT_NULL(al);
3480 const ActorLink& t = *al;
3481 return static_cast<const Propagator*>(&t);
3482 }
3483
3484 forceinline Propagator*
3485 Propagator::fwd(void) const {
3486 return static_cast<Propagator*>(prev());
3487 }
3488
3489 forceinline bool
3490 Propagator::disabled(void) const {
3491 return Support::marked(gpi_disabled);
3492 }
3493
3494 forceinline void
3495 Propagator::disable(Space& home) {
3496 home.pc.p.bid_sc |= Space::sc_disabled;
3497 gpi_disabled = Support::fmark(gpi_disabled);
3498 }
3499
3500 forceinline void
3501 Propagator::enable(Space& home) {
3502 (void) home;
3503 gpi_disabled = Support::funmark(gpi_disabled);
3504 }
3505
3506 forceinline Kernel::GPI::Info&
3507 Propagator::gpi(void) {
3508 return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
3509 }
3510
3511 forceinline
3512 Propagator::Propagator(Home home)
3513 : gpi_disabled((home.propagator() != nullptr) ?
3514 // Inherit propagator information
3515 home.propagator()->gpi_disabled :
3516 // New propagator information
3517 static_cast<Space&>(home).ssd.data().gpi.allocate
3518 (home.propagatorgroup().gid)) {
3519 u.advisors = nullptr;
3520 assert((u.med == 0) && (u.size == 0));
3521 static_cast<Space&>(home).pl.head(this);
3522 }
3523
3524 forceinline
3525 Propagator::Propagator(Space&, Propagator& p)
3526 : gpi_disabled(p.gpi_disabled) {
3527 u.advisors = nullptr;
3528 assert((u.med == 0) && (u.size == 0));
3529 // Set forwarding pointer
3530 p.prev(this);
3531 }
3532
3533 forceinline ModEventDelta
3534 Propagator::modeventdelta(void) const {
3535 return u.med;
3536 }
3537
3538 forceinline double
3539 Propagator::afc(void) const {
3540 return const_cast<Propagator&>(*this).gpi().afc;
3541 }
3542
3543#ifdef GECODE_HAS_CBS
3544 forceinline void
3545 Propagator::solndistrib(Space&, SendMarginal) const {}
3546
3547 forceinline void
3548 Propagator::domainsizesum(InDecision, unsigned int& size,
3549 unsigned int& size_b) const {
3550 size = 0;
3551 size_b = 0;
3552 }
3553#endif
3554
3555 forceinline unsigned int
3556 Propagator::id(void) const {
3557 return const_cast<Propagator&>(*this).gpi().pid;
3558 }
3559
3560 forceinline PropagatorGroup
3561 Propagator::group(void) const {
3562 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3563 }
3564
3565 forceinline void
3566 Propagator::group(PropagatorGroup g) {
3567 gpi().gid = g.id();
3568 }
3569
3570 forceinline ExecStatus
3571 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
3572 p.u.size = s;
3573 return ES_SUBSUMED_;
3574 }
3575
3576 forceinline ExecStatus
3577 Space::ES_SUBSUMED(Propagator& p) {
3578 p.u.size = p.dispose(*this);
3579 return ES_SUBSUMED_;
3580 }
3581
3582 forceinline ExecStatus
3583 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
3584 p.u.med = med;
3585 assert(p.u.med != 0);
3586 return ES_PARTIAL_;
3587 }
3588
3589 forceinline ExecStatus
3590 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
3591 p.u.med = AllVarConf::med_combine(p.u.med,med);
3592 assert(p.u.med != 0);
3593 return ES_PARTIAL_;
3594 }
3595
3596
3597
3598 /*
3599 * Brancher
3600 *
3601 */
3602 forceinline Brancher*
3603 Brancher::cast(ActorLink* al) {
3604 // Turning al into a reference is for gcc, assume is for MSVC
3605 GECODE_NOT_NULL(al);
3606 ActorLink& t = *al;
3607 return static_cast<Brancher*>(&t);
3608 }
3609
3610 forceinline const Brancher*
3611 Brancher::cast(const ActorLink* al) {
3612 // Turning al into a reference is for gcc, assume is for MSVC
3613 GECODE_NOT_NULL(al);
3614 const ActorLink& t = *al;
3615 return static_cast<const Brancher*>(&t);
3616 }
3617
3618 forceinline
3619 Brancher::Brancher(Home _home) :
3620 gid(_home.branchergroup().gid) {
3621 Space& home = static_cast<Space&>(_home);
3622 bid = home.pc.p.bid_sc >> Space::sc_bits;
3623 home.pc.p.bid_sc += (1 << Space::sc_bits);
3624 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3625 throw TooManyBranchers("Brancher::Brancher");
3626 // If no brancher available, make it the first one
3627 if (home.b_status == &static_cast<Space&>(home).bl) {
3628 home.b_status = this;
3629 if (home.b_commit == &static_cast<Space&>(home).bl)
3630 home.b_commit = this;
3631 }
3632 home.bl.tail(this);
3633 }
3634
3635 forceinline
3636 Brancher::Brancher(Space&, Brancher& b)
3637 : bid(b.bid), gid(b.gid) {
3638 // Set forwarding pointer
3639 b.prev(this);
3640 }
3641
3642 forceinline unsigned int
3643 Brancher::id(void) const {
3644 return bid;
3645 }
3646
3647 forceinline BrancherGroup
3648 Brancher::group(void) const {
3649 return BrancherGroup(gid);
3650 }
3651
3652 forceinline void
3653 Brancher::group(BrancherGroup g) {
3654 gid = g.id();
3655 }
3656
3657
3658 forceinline void
3659 Space::kill(Brancher& b) {
3660 assert(!failed());
3661 // Make sure that neither b_status nor b_commit does not point to b!
3662 if (b_commit == &b)
3663 b_commit = Brancher::cast(b.next());
3664 if (b_status == &b)
3665 b_status = Brancher::cast(b.next());
3666 b.unlink();
3667 rfree(&b,b.dispose(*this));
3668 }
3669
3670 forceinline void
3671 Space::kill(Propagator& p) {
3672 assert(!failed());
3673 p.unlink();
3674 rfree(&p,p.dispose(*this));
3675 // Is the space already stable?
3676 if (pc.p.active < &pc.p.queue[0])
3677 return;
3678 // Enforce that empty queues are ignored
3679 do {
3680 assert(pc.p.active >= &pc.p.queue[0]);
3681 // First propagator or link back to queue?
3682 if (pc.p.active != pc.p.active->next())
3683 return; // A propagator is left in the queue
3684 } while (--pc.p.active >= &pc.p.queue[0]);
3685 // The space is stable now
3686 assert(pc.p.active < &pc.p.queue[0]);
3687 }
3688
3689 forceinline Brancher*
3690 Space::brancher(unsigned int id) {
3691 /*
3692 * Due to weakly monotonic propagators the following scenario might
3693 * occur: a brancher has been committed with all its available
3694 * choices. Then, propagation determines less information
3695 * than before and the brancher now will create new choices.
3696 * Later, during recomputation, all of these choices
3697 * can be used together, possibly interleaved with
3698 * choices for other branchers. That means all branchers
3699 * must be scanned to find the matching brancher for the choice.
3700 *
3701 * b_commit tries to optimize scanning as it is most likely that
3702 * recomputation does not generate new choices during recomputation
3703 * and hence b_commit is moved from newer to older branchers.
3704 */
3705 Brancher* b_old = b_commit;
3706 // Try whether we are lucky
3707 while (b_commit != Brancher::cast(&bl))
3708 if (id != b_commit->id())
3709 b_commit = Brancher::cast(b_commit->next());
3710 else
3711 return b_commit;
3712 if (b_commit == Brancher::cast(&bl)) {
3713 // We did not find the brancher, start at the beginning
3714 b_commit = Brancher::cast(bl.next());
3715 while (b_commit != b_old)
3716 if (id != b_commit->id())
3717 b_commit = Brancher::cast(b_commit->next());
3718 else
3719 return b_commit;
3720 }
3721 return nullptr;
3722 }
3723
3724
3725 /*
3726 * Local objects
3727 *
3728 */
3729
3730 forceinline LocalObject*
3731 LocalObject::cast(ActorLink* al) {
3732 // Turning al into a reference is for gcc, assume is for MSVC
3733 GECODE_NOT_NULL(al);
3734 ActorLink& t = *al;
3735 return static_cast<LocalObject*>(&t);
3736 }
3737
3738 forceinline const LocalObject*
3739 LocalObject::cast(const ActorLink* al) {
3740 // Turning al into a reference is for gcc, assume is for MSVC
3741 GECODE_NOT_NULL(al);
3742 const ActorLink& t = *al;
3743 return static_cast<const LocalObject*>(&t);
3744 }
3745
3746 forceinline
3747 LocalObject::LocalObject(Home home) {
3748 (void) home;
3749 ActorLink::cast(this)->prev(nullptr);
3750 }
3751
3752 forceinline
3753 LocalObject::LocalObject(Space&, LocalObject&) {
3754 ActorLink::cast(this)->prev(nullptr);
3755 }
3756
3757 forceinline LocalObject*
3758 LocalObject::fwd(Space& home) {
3759 if (prev() == nullptr)
3760 fwdcopy(home);
3761 return LocalObject::cast(prev());
3762 }
3763
3764 forceinline
3765 LocalHandle::LocalHandle(void) : o(nullptr) {}
3766 forceinline
3767 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
3768 forceinline
3769 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3770 forceinline LocalHandle&
3771 LocalHandle::operator =(const LocalHandle& lh) {
3772 o = lh.o;
3773 return *this;
3774 }
3775 forceinline
3776 LocalHandle::~LocalHandle(void) {}
3777 forceinline LocalObject*
3778 LocalHandle::object(void) const { return o; }
3779 forceinline void
3780 LocalHandle::object(LocalObject* n) { o = n; }
3781 forceinline void
3782 LocalHandle::update(Space& home, LocalHandle& lh) {
3783 object(lh.object()->fwd(home));
3784 }
3785
3786
3787 /*
3788 * Choices
3789 *
3790 */
3791 forceinline
3792 Choice::Choice(const Brancher& b, const unsigned int a)
3793 : bid(b.id()), alt(a) {}
3794
3795 forceinline unsigned int
3796 Choice::alternatives(void) const {
3797 return alt;
3798 }
3799
3800 forceinline unsigned int
3801 Choice::id(void) const {
3802 return bid;
3803 }
3804
3805 forceinline
3806 Choice::~Choice(void) {}
3807
3808
3809
3810 /*
3811 * No-good literal
3812 *
3813 */
3814 forceinline bool
3815 NGL::leaf(void) const {
3816 return Support::marked(nl);
3817 }
3818 forceinline NGL*
3819 NGL::next(void) const {
3820 return static_cast<NGL*>(Support::funmark(nl));
3821 }
3822 forceinline void
3823 NGL::leaf(bool l) {
3824 nl = l ? Support::fmark(nl) : Support::funmark(nl);
3825 }
3826 forceinline void
3827 NGL::next(NGL* n) {
3828 nl = Support::marked(nl) ? Support::mark(n) : n;
3829 }
3830 forceinline NGL*
3831 NGL::add(NGL* n, bool l) {
3832 nl = Support::marked(nl) ? Support::mark(n) : n;
3833 n->leaf(l);
3834 return n;
3835 }
3836
3837 forceinline
3838 NGL::NGL(void)
3839 : nl(nullptr) {}
3840 forceinline
3841 NGL::NGL(Space&)
3842 : nl(nullptr) {}
3843 forceinline
3844 NGL::NGL(Space&, NGL&)
3845 : nl(nullptr) {}
3846 forceinline size_t
3847 NGL::dispose(Space&) {
3848 return sizeof(*this);
3849 }
3850
3851 /*
3852 * Advisor
3853 *
3854 */
3855 template<class A>
3856 forceinline
3857 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
3858 // Store propagator and forwarding in prev()
3859 ActorLink::prev(&p);
3860 // Link to next advisor in next()
3861 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3862 }
3863
3864 forceinline
3865 Advisor::Advisor(Space&, Advisor&) {}
3866
3867 forceinline bool
3868 Advisor::disposed(void) const {
3869 return prev() == nullptr;
3870 }
3871
3872 forceinline Advisor*
3873 Advisor::cast(ActorLink* al) {
3874 return static_cast<Advisor*>(al);
3875 }
3876
3877 forceinline const Advisor*
3878 Advisor::cast(const ActorLink* al) {
3879 return static_cast<const Advisor*>(al);
3880 }
3881
3882 forceinline Propagator&
3883 Advisor::propagator(void) const {
3884 assert(!disposed());
3885 return *Propagator::cast(ActorLink::prev());
3886 }
3887
3888 template<class A>
3889 forceinline void
3890 Advisor::dispose(Space&,Council<A>&) {
3891 assert(!disposed());
3892 ActorLink::prev(nullptr);
3893 // Shorten chains of disposed advisors by one, if possible
3894 Advisor* n = Advisor::cast(next());
3895 if ((n != nullptr) && n->disposed())
3896 next(n->next());
3897 }
3898
3899 forceinline const ViewTraceInfo&
3900 Advisor::operator ()(const Space& home) const {
3901 return home.pc.p.vti;
3902 }
3903
3904 template<class A>
3905 forceinline ExecStatus
3906 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) {
3907 a.dispose(*this,c);
3908 return ES_FIX;
3909 }
3910
3911 template<class A>
3912 forceinline ExecStatus
3913 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) {
3914 a.dispose(*this,c);
3915 return ES_NOFIX;
3916 }
3917
3918 template<class A>
3919 forceinline ExecStatus
3920 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) {
3921 a.dispose(*this,c);
3922 return ES_NOFIX_FORCE;
3923 }
3924
3925
3926
3927 /*
3928 * Advisor council
3929 *
3930 */
3931 template<class A>
3932 forceinline
3933 Council<A>::Council(void) {}
3934
3935 template<class A>
3936 forceinline
3937 Council<A>::Council(Space&)
3938 : advisors(nullptr) {}
3939
3940 template<class A>
3941 forceinline bool
3942 Council<A>::empty(void) const {
3943 ActorLink* a = advisors;
3944 while ((a != nullptr) && static_cast<A*>(a)->disposed())
3945 a = a->next();
3946 advisors = a;
3947 return a == nullptr;
3948 }
3949
3950 template<class A>
3951 forceinline void
3952 Council<A>::update(Space& home, Council<A>& c) {
3953 // Skip all disposed advisors
3954 {
3955 ActorLink* a = c.advisors;
3956 while ((a != nullptr) && static_cast<A*>(a)->disposed())
3957 a = a->next();
3958 c.advisors = a;
3959 }
3960 // Are there any advisors to be cloned?
3961 if (c.advisors != nullptr) {
3962 // The propagator in from-space
3963 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3964 // The propagator in to-space
3965 Propagator* p_t = Propagator::cast(p_f->prev());
3966 // Advisors in from-space
3967 ActorLink** a_f = &c.advisors;
3968 // Advisors in to-space
3969 A* a_t = nullptr;
3970 while (*a_f != nullptr) {
3971 if (static_cast<A*>(*a_f)->disposed()) {
3972 *a_f = (*a_f)->next();
3973 } else {
3974 // Run specific copying part
3975 A* a = new (home) A(home,*static_cast<A*>(*a_f));
3976 // Set propagator pointer
3977 a->prev(p_t);
3978 // Set forwarding pointer
3979 (*a_f)->prev(a);
3980 // Link
3981 a->next(a_t);
3982 a_t = a;
3983 a_f = (*a_f)->next_ref();
3984 }
3985 }
3986 advisors = a_t;
3987 // Enter advisor link for reset
3988 assert(p_f->u.advisors == nullptr);
3989 p_f->u.advisors = c.advisors;
3990 } else {
3991 advisors = nullptr;
3992 }
3993 }
3994
3995 template<class A>
3996 forceinline void
3997 Council<A>::dispose(Space& home) {
3998 ActorLink* a = advisors;
3999 while (a != nullptr) {
4000 if (!static_cast<A*>(a)->disposed())
4001 static_cast<A*>(a)->dispose(home,*this);
4002 a = a->next();
4003 }
4004 }
4005
4006
4007
4008 /*
4009 * Advisor iterator
4010 *
4011 */
4012 template<class A>
4013 forceinline
4014 Advisors<A>::Advisors(const Council<A>& c)
4015 : a(c.advisors) {
4016 while ((a != nullptr) && static_cast<A*>(a)->disposed())
4017 a = a->next();
4018 }
4019
4020 template<class A>
4021 forceinline bool
4022 Advisors<A>::operator ()(void) const {
4023 return a != nullptr;
4024 }
4025
4026 template<class A>
4027 forceinline void
4028 Advisors<A>::operator ++(void) {
4029 do {
4030 a = a->next();
4031 } while ((a != nullptr) && static_cast<A*>(a)->disposed());
4032 }
4033
4034 template<class A>
4035 forceinline A&
4036 Advisors<A>::advisor(void) const {
4037 return *static_cast<A*>(a);
4038 }
4039
4040
4041
4042 /*
4043 * Space
4044 *
4045 */
4046 forceinline void
4047 Space::enqueue(Propagator* p) {
4048 ActorLink::cast(p)->unlink();
4049 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
4050 c->tail(ActorLink::cast(p));
4051 if (c > pc.p.active)
4052 pc.p.active = c;
4053 }
4054
4055 forceinline void
4056 Space::fail(void) {
4057 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
4058 /*
4059 * Now active points beyond the last queue. This is essential as
4060 * enqueuing a propagator in a failed space keeps the space
4061 * failed.
4062 */
4063 }
4064 forceinline void
4065 Home::fail(void) {
4066 s.fail();
4067 }
4068
4069 forceinline bool
4070 Space::failed(void) const {
4071 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4072 }
4073 forceinline bool
4074 Home::failed(void) const {
4075 return s.failed();
4076 }
4077
4078 forceinline bool
4079 Space::stable(void) const {
4080 return ((pc.p.active < &pc.p.queue[0]) ||
4081 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
4082 }
4083
4084 forceinline void
4085 Space::notice(Actor& a, ActorProperty p, bool d) {
4086 if (p & AP_DISPOSE) {
4087 ap_notice_dispose(&a,d);
4088 }
4089 if (p & AP_VIEW_TRACE) {
4090 pc.p.bid_sc |= sc_trace;
4091 }
4092 if (p & AP_TRACE) {
4093 pc.p.bid_sc |= sc_trace;
4094 }
4095 // Currently unused
4096 if (p & AP_WEAKLY) {
4097 // Nothing to do
4098 }
4099 }
4100
4101 forceinline void
4102 Space::ignore(Actor& a, ActorProperty p, bool d) {
4103 // Check whether array has already been discarded as space
4104 // deletion is already in progress
4105 if ((p & AP_DISPOSE) && (d_fst != nullptr))
4106 ap_ignore_dispose(&a,d);
4107 if (p & AP_VIEW_TRACE) {
4108 // Nothing to do
4109 }
4110 if (p & AP_TRACE) {
4111 // Nothing to do
4112 }
4113 // Currently unused
4114 if (p & AP_WEAKLY) {
4115 // Nothing to do
4116 }
4117 }
4118
4119
4120
4121 /*
4122 * Variable implementation
4123 *
4124 */
4125 template<class VIC>
4126 forceinline ActorLink**
4127 VarImp<VIC>::actor(PropCond pc) {
4128 assert((pc >= 0) && (pc < pc_max+2));
4129 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4130 }
4131
4132 template<class VIC>
4133 forceinline ActorLink**
4134 VarImp<VIC>::actorNonZero(PropCond pc) {
4135 assert((pc > 0) && (pc < pc_max+2));
4136 return b.base+u.idx[pc-1];
4137 }
4138
4139 template<class VIC>
4140 forceinline unsigned int&
4141 VarImp<VIC>::idx(PropCond pc) {
4142 assert((pc > 0) && (pc < pc_max+2));
4143 return u.idx[pc-1];
4144 }
4145
4146 template<class VIC>
4147 forceinline unsigned int
4148 VarImp<VIC>::idx(PropCond pc) const {
4149 assert((pc > 0) && (pc < pc_max+2));
4150 return u.idx[pc-1];
4151 }
4152
4153 template<class VIC>
4154 forceinline
4155 VarImp<VIC>::VarImp(Space& home)
4156#ifdef GECODE_HAS_CBS
4157 : var_id(++home.var_id_counter)
4158#endif
4159 {
4160#ifndef GECODE_HAS_CBS
4161 (void) home;
4162#endif
4163 b.base = nullptr; entries = 0;
4164 for (PropCond pc=1; pc<pc_max+2; pc++)
4165 idx(pc) = 0;
4166 free_and_bits = 0;
4167 }
4168
4169 template<class VIC>
4170 forceinline
4171 VarImp<VIC>::VarImp(void)
4172#ifdef GECODE_HAS_CBS
4173 : var_id(0)
4174#endif
4175 {
4176 b.base = nullptr; entries = 0;
4177 for (PropCond pc=1; pc<pc_max+2; pc++)
4178 idx(pc) = 0;
4179 free_and_bits = 0;
4180 }
4181
4182#ifdef GECODE_HAS_CBS
4183 template<class VIC>
4184 forceinline unsigned int
4185 VarImp<VIC>::id(void) const {
4186 return var_id;
4187 }
4188#endif
4189
4190 template<class VIC>
4191 forceinline unsigned int
4192 VarImp<VIC>::degree(void) const {
4193 assert(!copied());
4194 return entries;
4195 }
4196
4197 template<class VIC>
4198 forceinline double
4199 VarImp<VIC>::afc(void) const {
4200 double d = 0.0;
4201 // Count the afc of each propagator
4202 {
4203 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4204 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4205 while (a < e) {
4206 d += Propagator::cast(*a)->afc(); a++;
4207 }
4208 }
4209 // Count the afc of each advisor's propagator
4210 {
4211 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4212 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4213 while (a < e) {
4214 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4215 ->propagator().afc();
4216 a++;
4217 }
4218 }
4219 return d;
4220 }
4221
4222 template<class VIC>
4223 forceinline ModEvent
4224 VarImp<VIC>::modevent(const Delta& d) {
4225 return d.me;
4226 }
4227
4228 template<class VIC>
4229 forceinline unsigned int
4230 VarImp<VIC>::bits(void) const {
4231 return free_and_bits;
4232 }
4233
4234 template<class VIC>
4235 forceinline unsigned int&
4236 VarImp<VIC>::bits(void) {
4237 return free_and_bits;
4238 }
4239
4240#ifdef GECODE_HAS_VAR_DISPOSE
4241 template<class VIC>
4242 forceinline VarImp<VIC>*
4243 VarImp<VIC>::vars_d(Space& home) {
4244 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4245 }
4246
4247 template<class VIC>
4248 forceinline void
4249 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
4250 home.vars_d<VIC>(x);
4251 }
4252#endif
4253
4254 template<class VIC>
4255 forceinline bool
4256 VarImp<VIC>::copied(void) const {
4257 return Support::marked(b.fwd);
4258 }
4259
4260 template<class VIC>
4261 forceinline VarImp<VIC>*
4262 VarImp<VIC>::forward(void) const {
4263 assert(copied());
4264 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4265 }
4266
4267 template<class VIC>
4268 forceinline VarImp<VIC>*
4269 VarImp<VIC>::next(void) const {
4270 assert(copied());
4271 return u.next;
4272 }
4273
4274 template<class VIC>
4275 forceinline
4276 VarImp<VIC>::VarImp(Space& home, VarImp<VIC>& x)
4277#ifdef GECODE_HAS_CBS
4278 : var_id(x.var_id)
4279#endif
4280 {
4281 VarImpBase** reg;
4282 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4283 if (x.b.base == nullptr) {
4284 // Variable implementation needs no index structure
4285 reg = &home.pc.c.vars_noidx;
4286 assert(x.degree() == 0);
4287 } else {
4288 reg = &home.pc.c.vars_u[idx_c];
4289 }
4290 // Save subscriptions in copy
4291 b.base = x.b.base;
4292 entries = x.entries;
4293 for (PropCond pc=1; pc<pc_max+2; pc++)
4294 idx(pc) = x.idx(pc);
4295
4296 // Set forwarding pointer
4297 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4298 // Register original
4299 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4300 }
4301
4302 template<class VIC>
4303 forceinline ModEvent
4304 VarImp<VIC>::me(const ModEventDelta& med) {
4305 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4306 }
4307
4308 template<class VIC>
4309 forceinline ModEventDelta
4310 VarImp<VIC>::med(ModEvent me) {
4311 return static_cast<ModEventDelta>(me << VIC::med_fst);
4312 }
4313
4314 template<class VIC>
4315 forceinline ModEvent
4316 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
4317 return VIC::me_combine(me1,me2);
4318 }
4319
4320 template<class VIC>
4321 forceinline void
4322 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me,
4323 bool force) {
4324 if (VIC::med_update(p.u.med,me) || force)
4325 home.enqueue(&p);
4326 }
4327
4328 template<class VIC>
4329 forceinline void
4330 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
4331 ActorLink** b = actor(pc1);
4332 ActorLink** p = actorNonZero(pc2+1);
4333 while (p-- > b)
4334 schedule(home,*Propagator::cast(*p),me);
4335 }
4336
4337 template<class VIC>
4338 forceinline void
4339 VarImp<VIC>::resize(Space& home) {
4340 if (b.base == nullptr) {
4341 assert((free_and_bits >> free_bits) == 0);
4342 // Create fresh dependency array with four entries
4343 free_and_bits += 4 << free_bits;
4344 b.base = home.alloc<ActorLink*>(4);
4345 for (int i=0; i<pc_max+1; i++)
4346 u.idx[i] = 0;
4347 } else {
4348 // Resize dependency array
4349 unsigned int n = degree();
4350 // Find out whether the area is most likely in the special area
4351 // reserved for subscriptions. If yes, just resize mildly otherwise
4352 // more agressively
4353 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4354 unsigned int m =
4355 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4356 (n+4) : ((n+1)*3>>1);
4357 ActorLink** prop = home.alloc<ActorLink*>(m);
4358 free_and_bits += (m-n) << free_bits;
4359 // Copy entries
4360 Heap::copy<ActorLink*>(prop, b.base, n);
4361 home.free<ActorLink*>(b.base,n);
4362 b.base = prop;
4363 }
4364 }
4365
4366 template<class VIC>
4367 forceinline void
4368 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4369 assert(pc <= pc_max);
4370 // Count one new subscription
4371 home.pc.p.n_sub += 1;
4372 if ((free_and_bits >> free_bits) == 0)
4373 resize(home);
4374 free_and_bits -= 1 << free_bits;
4375
4376 // Enter subscription
4377 b.base[entries] = *actorNonZero(pc_max+1);
4378 entries++;
4379 for (PropCond j = pc_max; j > pc; j--) {
4380 *actorNonZero(j+1) = *actorNonZero(j);
4381 idx(j+1)++;
4382 }
4383 *actorNonZero(pc+1) = *actor(pc);
4384 idx(pc+1)++;
4385 *actor(pc) = ActorLink::cast(p);
4386
4387#ifdef GECODE_AUDIT
4388 ActorLink** f = actor(pc);
4389 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4390 if (*f == p)
4391 goto found;
4392 else
4393 f++;
4394 GECODE_NEVER;
4395 found: ;
4396#endif
4397 }
4398
4399 template<class VIC>
4400 forceinline void
4401 VarImp<VIC>::enter(Space& home, Advisor* a) {
4402 // Note that a might be a marked pointer
4403 // Count one new subscription
4404 home.pc.p.n_sub += 1;
4405 if ((free_and_bits >> free_bits) == 0)
4406 resize(home);
4407 free_and_bits -= 1 << free_bits;
4408
4409 // Enter subscription
4410 b.base[entries++] = *actorNonZero(pc_max+1);
4411 *actorNonZero(pc_max+1) = a;
4412 }
4413
4414 template<class VIC>
4415 forceinline void
4416 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
4417 bool assigned, ModEvent me, bool schedule) {
4418 if (assigned) {
4419 // Do not subscribe, just schedule the propagator
4420 if (schedule)
4421 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
4422 } else {
4423 enter(home,&p,pc);
4424 // Schedule propagator
4425 if (schedule && (pc != PC_GEN_ASSIGNED))
4426 VarImp<VIC>::schedule(home,p,me);
4427 }
4428 }
4429
4430 template<class VIC>
4431 forceinline void
4432 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4433 if (!assigned) {
4434 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4435 enter(home,ma);
4436 }
4437 }
4438
4439 template<class VIC>
4440 forceinline void
4441 VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc,
4442 bool assigned, ModEvent me) {
4443 if (assigned)
4444 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
4445 else if (pc != PC_GEN_ASSIGNED)
4446 VarImp<VIC>::schedule(home,p,me);
4447 }
4448
4449 template<class VIC>
4450 void
4451 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
4452 assert(pc <= pc_max);
4453 ActorLink* a = ActorLink::cast(p);
4454 // Find actor in dependency array
4455 ActorLink** f = actor(pc);
4456#ifdef GECODE_AUDIT
4457 while (f < actorNonZero(pc+1))
4458 if (*f == a)
4459 goto found;
4460 else
4461 f++;
4462 GECODE_NEVER;
4463 found: ;
4464#else
4465 while (*f != a) f++;
4466#endif
4467 // Remove actor
4468 *f = *(actorNonZero(pc+1)-1);
4469 for (PropCond j = pc+1; j< pc_max+1; j++) {
4470 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4471 idx(j)--;
4472 }
4473 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4474 idx(pc_max+1)--;
4475 entries--;
4476 free_and_bits += 1 << free_bits;
4477 home.pc.p.n_sub -= 1;
4478 }
4479
4480 template<class VIC>
4481 forceinline void
4482 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) {
4483 if (b.base != nullptr)
4484 remove(home,&p,pc);
4485 }
4486
4487 template<class VIC>
4488 void
4489 VarImp<VIC>::remove(Space& home, Advisor* a) {
4490 // Note that a might be a marked pointer
4491 // Find actor in dependency array
4492 ActorLink** f = actorNonZero(pc_max+1);
4493#ifdef GECODE_AUDIT
4494 while (f < b.base+entries)
4495 if (*f == a)
4496 goto found;
4497 else
4498 f++;
4499 GECODE_NEVER;
4500 found: ;
4501#else
4502 while (*f != a) f++;
4503#endif
4504 // Remove actor
4505 *f = b.base[--entries];
4506 free_and_bits += 1 << free_bits;
4507 home.pc.p.n_sub -= 1;
4508 }
4509
4510 template<class VIC>
4511 forceinline void
4512 VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) {
4513 if (b.base != nullptr) {
4514 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0));
4515 remove(home,ma);
4516 }
4517 }
4518
4519 template<class VIC>
4520 forceinline void
4521 VarImp<VIC>::cancel(Space& home) {
4522 unsigned int n_sub = degree();
4523 home.pc.p.n_sub -= n_sub;
4524 unsigned int n = (free_and_bits >> free_bits) + n_sub;
4525 home.free<ActorLink*>(b.base,n);
4526 // Must be nullptr such that cloning works
4527 b.base = nullptr;
4528 // Must be 0 such that degree works
4529 entries = 0;
4530 // Must be nullptr such that afc works
4531 for (PropCond pc=1; pc<pc_max+2; pc++)
4532 idx(pc) = 0;
4533 free_and_bits &= (1 << free_bits) - 1;
4534 }
4535
4536 template<class VIC>
4537 forceinline bool
4538 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
4539 /*
4540 * An advisor that is executed might remove itself due to subsumption.
4541 * As entries are removed from front to back, the advisors must
4542 * be iterated in forward direction.
4543 */
4544 ActorLink** la = actorNonZero(pc_max+1);
4545 ActorLink** le = b.base+entries;
4546 if (la == le)
4547 return true;
4548 d.me = me;
4549 // An advisor that is run, might be removed during execution.
4550 // As removal is done from the back the advisors have to be executed
4551 // in inverse order.
4552 do {
4553 Advisor* a = Advisor::cast
4554 (static_cast<ActorLink*>(Support::funmark(*la)));
4555 assert(!a->disposed());
4556 Propagator& p = a->propagator();
4557 switch (p.advise(home,*a,d)) {
4558 case ES_FIX:
4559 break;
4560 case ES_FAILED:
4561 return false;
4562 case ES_NOFIX:
4563 schedule(home,p,me);
4564 break;
4565 case ES_NOFIX_FORCE:
4566 schedule(home,p,me,true);
4567 break;
4568 case ES_SUBSUMED_:
4569 default:
4570 GECODE_NEVER;
4571 }
4572 } while (++la < le);
4573 return true;
4574 }
4575
4576 template<class VIC>
4577 void
4578 VarImp<VIC>::_fail(Space& home) {
4579 /*
4580 * An advisor that is executed might remove itself due to subsumption.
4581 * As entries are removed from front to back, the advisors must
4582 * be iterated in forward direction.
4583 */
4584 ActorLink** la = actorNonZero(pc_max+1);
4585 ActorLink** le = b.base+entries;
4586 if (la == le)
4587 return;
4588 // An advisor that is run, might be removed during execution.
4589 // As removal is done from the back the advisors have to be executed
4590 // in inverse order.
4591 do {
4592 if (Support::marked(*la)) {
4593 Advisor* a = Advisor::cast(static_cast<ActorLink*>
4594 (Support::unmark(*la)));
4595 assert(!a->disposed());
4596 Propagator& p = a->propagator();
4597 p.advise(home,*a);
4598 }
4599 } while (++la < le);
4600 }
4601
4602 template<class VIC>
4603 ModEvent
4604 VarImp<VIC>::fail(Space& home) {
4605 _fail(home);
4606 return ME_GEN_FAILED;
4607 }
4608
4609 // Clang incorrectly reports an error on the access to u.idx[1] for BoolVarImp,
4610 // even though the access is guarded by pc_max > 0 which implies that the size is sufficient.
4611#pragma clang diagnostic push
4612#pragma clang diagnostic ignored "-Warray-bounds"
4613
4614 template<class VIC>
4615 forceinline void
4616 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
4617 // this refers to the variable to be updated (clone)
4618 // x refers to the original
4619 // Recover from copy
4620 x->b.base = b.base;
4621 x->u.idx[0] = u.idx[0];
4622 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4623 x->u.idx[1] = u.idx[1];
4624
4625 unsigned int np =
4626 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4627 unsigned int na =
4628 static_cast<unsigned int >(x->b.base + x->entries -
4629 x->actorNonZero(pc_max+1));
4630 unsigned int n = na + np;
4631 assert(n == x->degree());
4632
4633 ActorLink** f = x->b.base;
4634 ActorLink** t = sub;
4635
4636 sub += n;
4637 b.base = t;
4638 // Process propagator subscriptions
4639 while (np >= 4) {
4640 ActorLink* p3 = f[3]->prev();
4641 ActorLink* p0 = f[0]->prev();
4642 ActorLink* p1 = f[1]->prev();
4643 ActorLink* p2 = f[2]->prev();
4644 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4645 np -= 4; t += 4; f += 4;
4646 }
4647 if (np >= 2) {
4648 ActorLink* p0 = f[0]->prev();
4649 ActorLink* p1 = f[1]->prev();
4650 t[0] = p0; t[1] = p1;
4651 np -= 2; t += 2; f += 2;
4652 }
4653 if (np > 0) {
4654 ActorLink* p0 = f[0]->prev();
4655 t[0] = p0;
4656 t += 1; f += 1;
4657 }
4658 // Process advisor subscriptions
4659 while (na >= 4) {
4660 ptrdiff_t m0, m1, m2, m3;
4661 ActorLink* p3 =
4662 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4663 ActorLink* p0 =
4664 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4665 ActorLink* p1 =
4666 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4667 ActorLink* p2 =
4668 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4669 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4670 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4671 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4672 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4673 na -= 4; t += 4; f += 4;
4674 }
4675 if (na >= 2) {
4676 ptrdiff_t m0, m1;
4677 ActorLink* p0 =
4678 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4679 ActorLink* p1 =
4680 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4681 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4682 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4683 na -= 2; t += 2; f += 2;
4684 }
4685 if (na > 0) {
4686 ptrdiff_t m0;
4687 ActorLink* p0 =
4688 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4689 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4690 }
4691 }
4692#pragma clang diagnostic pop
4693
4694 template<class VIC>
4695 forceinline void
4696 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4697 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4698 while (x != nullptr) {
4699 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4700 }
4701 }
4702
4703
4704
4705 /*
4706 * Variable disposer
4707 *
4708 */
4709 template<class VarImp>
4710 VarImpDisposer<VarImp>::VarImpDisposer(void) {
4711#ifdef GECODE_HAS_VAR_DISPOSE
4712 Space::vd[VarImp::idx_d] = this;
4713#endif
4714 }
4715
4716 template<class VarImp>
4717 void
4718 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) {
4719 VarImp* x = static_cast<VarImp*>(_x);
4720 do {
4721 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4722 } while (x != nullptr);
4723 }
4724
4725 /*
4726 * Statistics
4727 */
4728
4729 forceinline void
4730 StatusStatistics::reset(void) {
4731 propagate = 0;
4732 }
4733 forceinline
4734 StatusStatistics::StatusStatistics(void) {
4735 reset();
4736 }
4737 forceinline StatusStatistics&
4738 StatusStatistics::operator +=(const StatusStatistics& s) {
4739 propagate += s.propagate;
4740 return *this;
4741 }
4742 forceinline StatusStatistics
4743 StatusStatistics::operator +(const StatusStatistics& s) {
4744 StatusStatistics t(s);
4745 return t += *this;
4746 }
4747
4748 forceinline void
4749 CloneStatistics::reset(void) {}
4750
4751 forceinline
4752 CloneStatistics::CloneStatistics(void) {
4753 reset();
4754 }
4755 forceinline CloneStatistics
4756 CloneStatistics::operator +(const CloneStatistics&) {
4757 CloneStatistics s;
4758 return s;
4759 }
4760 forceinline CloneStatistics&
4761 CloneStatistics::operator +=(const CloneStatistics&) {
4762 return *this;
4763 }
4764
4765 forceinline void
4766 CommitStatistics::reset(void) {}
4767
4768 forceinline
4769 CommitStatistics::CommitStatistics(void) {
4770 reset();
4771 }
4772 forceinline CommitStatistics
4773 CommitStatistics::operator +(const CommitStatistics&) {
4774 CommitStatistics s;
4775 return s;
4776 }
4777 forceinline CommitStatistics&
4778 CommitStatistics::operator +=(const CommitStatistics&) {
4779 return *this;
4780 }
4781
4782 /*
4783 * Cost computation
4784 *
4785 */
4786
4787 forceinline
4788 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4789
4790 forceinline PropCost
4791 PropCost::cost(PropCost::Mod m,
4792 PropCost::ActualCost lo, PropCost::ActualCost hi,
4793 unsigned int n) {
4794 if (n < 2)
4795 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4796 else if (n == 2)
4797 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4798 else if (n == 3)
4799 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4800 else
4801 return (m == LO) ? lo : hi;
4802 }
4803
4804 forceinline PropCost
4805 PropCost::record(void) {
4806 return AC_RECORD;
4807 }
4808 forceinline PropCost
4809 PropCost::crazy(PropCost::Mod m, unsigned int n) {
4810 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4811 }
4812 forceinline PropCost
4813 PropCost::crazy(PropCost::Mod m, int n) {
4814 assert(n >= 0);
4815 return crazy(m,static_cast<unsigned int>(n));
4816 }
4817 forceinline PropCost
4818 PropCost::cubic(PropCost::Mod m, unsigned int n) {
4819 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4820 }
4821 forceinline PropCost
4822 PropCost::cubic(PropCost::Mod m, int n) {
4823 assert(n >= 0);
4824 return cubic(m,static_cast<unsigned int>(n));
4825 }
4826 forceinline PropCost
4827 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
4828 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4829 }
4830 forceinline PropCost
4831 PropCost::quadratic(PropCost::Mod m, int n) {
4832 assert(n >= 0);
4833 return quadratic(m,static_cast<unsigned int>(n));
4834 }
4835 forceinline PropCost
4836 PropCost::linear(PropCost::Mod m, unsigned int n) {
4837 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4838 }
4839 forceinline PropCost
4840 PropCost::linear(PropCost::Mod m, int n) {
4841 assert(n >= 0);
4842 return linear(m,static_cast<unsigned int>(n));
4843 }
4844 forceinline PropCost
4845 PropCost::ternary(PropCost::Mod m) {
4846 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4847 }
4848 forceinline PropCost
4849 PropCost::binary(PropCost::Mod m) {
4850 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4851 }
4852 forceinline PropCost
4853 PropCost::unary(PropCost::Mod m) {
4854 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4855 }
4856
4857 /*
4858 * Iterators for propagators and branchers of a space
4859 *
4860 */
4861 forceinline
4862 Space::Propagators::Propagators(Space& home0)
4863 : home(home0), q(home.pc.p.active) {
4864 while (q >= &home.pc.p.queue[0]) {
4865 if (q->next() != q) {
4866 c = q->next(); e = q; q--;
4867 return;
4868 }
4869 q--;
4870 }
4871 q = nullptr;
4872 if (!home.pl.empty()) {
4873 c = Propagator::cast(home.pl.next());
4874 e = Propagator::cast(&home.pl);
4875 } else {
4876 c = e = nullptr;
4877 }
4878 }
4879 forceinline bool
4880 Space::Propagators::operator ()(void) const {
4881 return c != nullptr;
4882 }
4883 forceinline void
4884 Space::Propagators::operator ++(void) {
4885 c = c->next();
4886 if (c == e) {
4887 if (q == nullptr) {
4888 c = nullptr;
4889 } else {
4890 while (q >= &home.pc.p.queue[0]) {
4891 if (q->next() != q) {
4892 c = q->next(); e = q; q--;
4893 return;
4894 }
4895 q--;
4896 }
4897 q = nullptr;
4898 if (!home.pl.empty()) {
4899 c = Propagator::cast(home.pl.next());
4900 e = Propagator::cast(&home.pl);
4901 } else {
4902 c = nullptr;
4903 }
4904 }
4905 }
4906 }
4907 forceinline Propagator&
4908 Space::Propagators::propagator(void) const {
4909 return *Propagator::cast(c);
4910 }
4911
4912
4913 forceinline
4914 Space::ScheduledPropagators::ScheduledPropagators(Space& home0)
4915 : home(home0), q(home.pc.p.active) {
4916 while (q >= &home.pc.p.queue[0]) {
4917 if (q->next() != q) {
4918 c = q->next(); e = q; q--;
4919 return;
4920 }
4921 q--;
4922 }
4923 q = c = e = nullptr;
4924 }
4925 forceinline bool
4926 Space::ScheduledPropagators::operator ()(void) const {
4927 return c != nullptr;
4928 }
4929 forceinline void
4930 Space::ScheduledPropagators::operator ++(void) {
4931 c = c->next();
4932 if (c == e) {
4933 if (q == nullptr) {
4934 c = nullptr;
4935 } else {
4936 while (q >= &home.pc.p.queue[0]) {
4937 if (q->next() != q) {
4938 c = q->next(); e = q; q--;
4939 return;
4940 }
4941 q--;
4942 }
4943 q = c = e = nullptr;
4944 }
4945 }
4946 }
4947 forceinline Propagator&
4948 Space::ScheduledPropagators::propagator(void) const {
4949 return *Propagator::cast(c);
4950 }
4951
4952
4953 forceinline
4954 Space::IdlePropagators::IdlePropagators(Space& home) {
4955 c = Propagator::cast(home.pl.next());
4956 e = Propagator::cast(&home.pl);
4957 }
4958 forceinline bool
4959 Space::IdlePropagators::operator ()(void) const {
4960 return c != e;
4961 }
4962 forceinline void
4963 Space::IdlePropagators::operator ++(void) {
4964 c = c->next();
4965 }
4966 forceinline Propagator&
4967 Space::IdlePropagators::propagator(void) const {
4968 return *Propagator::cast(c);
4969 }
4970
4971
4972 forceinline
4973 Space::Branchers::Branchers(Space& home)
4974 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4975 forceinline bool
4976 Space::Branchers::operator ()(void) const {
4977 return c != e;
4978 }
4979 forceinline void
4980 Space::Branchers::operator ++(void) {
4981 c = c->next();
4982 }
4983 forceinline Brancher&
4984 Space::Branchers::brancher(void) const {
4985 return *Brancher::cast(c);
4986 }
4987
4988
4989 /*
4990 * Groups of actors
4991 */
4992 forceinline
4993 Group::Group(unsigned int gid0) : gid(gid0) {}
4994
4995 forceinline bool
4996 Group::in(Group actor) const {
4997 return (gid == GROUPID_ALL) || (gid == actor.gid);
4998 }
4999
5000 forceinline bool
5001 Group::in(void) const {
5002 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
5003 }
5004
5005 forceinline
5006 Group::Group(const Group& g) : gid(g.gid) {}
5007
5008 forceinline Group&
5009 Group::operator =(const Group& g) {
5010 gid=g.gid; return *this;
5011 }
5012
5013 forceinline unsigned int
5014 Group::id(void) const {
5015 return gid;
5016 }
5017
5018
5019 forceinline
5020 PropagatorGroup::PropagatorGroup(void) {}
5021
5022 forceinline
5023 PropagatorGroup::PropagatorGroup(unsigned int gid)
5024 : Group(gid) {}
5025
5026 forceinline
5027 PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
5028 : Group(g) {}
5029
5030 forceinline PropagatorGroup&
5031 PropagatorGroup::operator =(const PropagatorGroup& g) {
5032 return static_cast<PropagatorGroup&>(Group::operator =(g));
5033 }
5034
5035 forceinline Home
5036 PropagatorGroup::operator ()(Space& home) {
5037 return Home(home,nullptr,*this,BrancherGroup::def);
5038 }
5039
5040 forceinline bool
5041 PropagatorGroup::operator ==(PropagatorGroup g) const {
5042 return id() == g.id();
5043 }
5044 forceinline bool
5045 PropagatorGroup::operator !=(PropagatorGroup g) const {
5046 return id() != g.id();
5047 }
5048
5049 forceinline PropagatorGroup&
5050 PropagatorGroup::move(Space& , Propagator& p) {
5051 if (id() != GROUPID_ALL)
5052 p.group(*this);
5053 return *this;
5054 }
5055
5056
5057 forceinline
5058 BrancherGroup::BrancherGroup(void) {}
5059
5060 forceinline
5061 BrancherGroup::BrancherGroup(unsigned int gid)
5062 : Group(gid) {}
5063
5064 forceinline
5065 BrancherGroup::BrancherGroup(const BrancherGroup& g)
5066 : Group(g) {}
5067
5068 forceinline BrancherGroup&
5069 BrancherGroup::operator =(const BrancherGroup& g) {
5070 return static_cast<BrancherGroup&>(Group::operator =(g));
5071 }
5072
5073 forceinline Home
5074 BrancherGroup::operator ()(Space& home) {
5075 return Home(home,nullptr,PropagatorGroup::def,*this);
5076 }
5077
5078 forceinline bool
5079 BrancherGroup::operator ==(BrancherGroup g) const {
5080 return id() == g.id();
5081 }
5082 forceinline bool
5083 BrancherGroup::operator !=(BrancherGroup g) const {
5084 return id() != g.id();
5085 }
5086
5087 forceinline BrancherGroup&
5088 BrancherGroup::move(Space& , Brancher& p) {
5089 if (id() != GROUPID_ALL)
5090 p.group(*this);
5091 return *this;
5092 }
5093
5094
5095 /*
5096 * Iterators for propagators and branchers in a group
5097 *
5098 */
5099 forceinline
5100 Propagators::Propagators(const Space& home, PropagatorGroup g0)
5101 : ps(const_cast<Space&>(home)), g(g0) {
5102 while (ps() && !g.in(ps.propagator().group()))
5103 ++ps;
5104 }
5105 forceinline bool
5106 Propagators::operator ()(void) const {
5107 return ps();
5108 }
5109 forceinline void
5110 Propagators::operator ++(void) {
5111 do
5112 ++ps;
5113 while (ps() && !g.in(ps.propagator().group()));
5114 }
5115 forceinline const Propagator&
5116 Propagators::propagator(void) const {
5117 return ps.propagator();
5118 }
5119
5120 forceinline
5121 Branchers::Branchers(const Space& home, BrancherGroup g0)
5122 : bs(const_cast<Space&>(home)), g(g0) {
5123 while (bs() && !g.in(bs.brancher().group()))
5124 ++bs;
5125 }
5126 forceinline bool
5127 Branchers::operator ()(void) const {
5128 return bs();
5129 }
5130 forceinline void
5131 Branchers::operator ++(void) {
5132 do
5133 ++bs;
5134 while (bs() && !g.in(bs.brancher().group()));
5135 }
5136 forceinline const Brancher&
5137 Branchers::brancher(void) const {
5138 return bs.brancher();
5139 }
5140
5141
5142 /*
5143 * Space construction support
5144 *
5145 */
5146 template<class T>
5147 forceinline T&
5148 Space::construct(void) {
5149 return alloc<T>(1);
5150 }
5151 template<class T, typename A1>
5152 forceinline T&
5153 Space::construct(A1 const& a1) {
5154 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5155 new (&t) T(a1);
5156 return t;
5157 }
5158 template<class T, typename A1, typename A2>
5159 forceinline T&
5160 Space::construct(A1 const& a1, A2 const& a2) {
5161 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5162 new (&t) T(a1,a2);
5163 return t;
5164 }
5165 template<class T, typename A1, typename A2, typename A3>
5166 forceinline T&
5167 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5168 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5169 new (&t) T(a1,a2,a3);
5170 return t;
5171 }
5172 template<class T, typename A1, typename A2, typename A3, typename A4>
5173 forceinline T&
5174 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5175 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5176 new (&t) T(a1,a2,a3,a4);
5177 return t;
5178 }
5179 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5180 forceinline T&
5181 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5182 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5183 new (&t) T(a1,a2,a3,a4,a5);
5184 return t;
5185 }
5186
5187}
5188
5189// STATISTICS: kernel-core