1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *     Guido Tack <tack@gecode.org>
6  *     Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  *  Contributing authors:
9  *     Filip Konvicka <filip.konvicka@logis.cz>
10  *     Samuel Gagnon <samuel.gagnon92@gmail.com>
11  *
12  *  Copyright:
13  *     Christian Schulte, 2002
14  *     Guido Tack, 2003
15  *     Mikael Lagerkvist, 2006
16  *     LOGIS, s.r.o., 2009
17  *     Samuel Gagnon, 2018
18  *
19  *  Bugfixes provided by:
20  *     Alexander Samoilov <alexander_samoilov@yahoo.com>
21  *
22  *  This file is part of Gecode, the generic constraint
23  *  development environment:
24  *     http://www.gecode.org
25  *
26  *  Permission is hereby granted, free of charge, to any person obtaining
27  *  a copy of this software and associated documentation files (the
28  *  "Software"), to deal in the Software without restriction, including
29  *  without limitation the rights to use, copy, modify, merge, publish,
30  *  distribute, sublicense, and/or sell copies of the Software, and to
31  *  permit persons to whom the Software is furnished to do so, subject to
32  *  the following conditions:
33  *
34  *  The above copyright notice and this permission notice shall be
35  *  included in all copies or substantial portions of the Software.
36  *
37  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
38  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
39  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
40  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
41  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
42  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
43  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44  *
45  */
46 
47 #include <iostream>
48 
49 namespace Gecode {
50 
51   class Space;
52 
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 
95 namespace 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
me_combine(ModEvent,ModEvent)121   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
122     GECODE_NEVER; return 0;
123   }
124   forceinline bool
med_update(ModEventDelta &,ModEvent)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*
ralloc(size_t s)2810   Space::ralloc(size_t s) {
2811     return mm.alloc(ssd.data().sm,s);
2812   }
2813   forceinline void
rfree(void * p,size_t s)2814   Space::rfree(void* p, size_t s) {
2815     return mm.reuse(p,s);
2816   }
2817   forceinline void*
rrealloc(void * _b,size_t n,size_t m)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*
fl_alloc(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
fl_dispose(FreeList * f,FreeList * l)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*
alloc(long unsigned int n)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*
alloc(long int n)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*
alloc(unsigned int n)2862   Space::alloc(unsigned int n) {
2863     return alloc<T>(static_cast<long unsigned int>(n));
2864   }
2865   template<class T>
2866   forceinline T*
alloc(int n)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
free(T * b,long unsigned int n)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
free(T * b,long int n)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
free(T * b,unsigned int n)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
free(T * b,int n)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*
realloc(T * b,long unsigned int n,long unsigned int m)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*
realloc(T * b,long int n,long int m)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*
realloc(T * b,unsigned int n,unsigned int m)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*
realloc(T * b,int n,int m)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)
GECODE_KERNEL_REALLOC(signed char)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**
realloc(T ** b,long int n,long int m)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**
realloc(T ** b,unsigned int n,unsigned int m)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**
realloc(T ** b,int n,int m)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*
vars_d(void) const3005   Space::vars_d(void) const {
3006     return _vars_d[VIC::idx_d];
3007   }
3008   template<class VIC>
3009   forceinline void
vars_d(VarImpBase * x)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
operator delete(void *)3017   Actor::operator delete(void*) {}
3018   forceinline void
operator delete(void *,Space &)3019   Actor::operator delete(void*, Space&) {}
3020   forceinline void*
operator new(size_t s,Space & home)3021   Actor::operator new(size_t s, Space& home) {
3022     return home.ralloc(s);
3023   }
3024 
3025   template<class VIC>
3026   forceinline void
operator delete(void *)3027   VarImp<VIC>::operator delete(void*) {}
3028   template<class VIC>
3029   forceinline void
operator delete(void *,Space &)3030   VarImp<VIC>::operator delete(void*, Space&) {}
3031   template<class VIC>
3032   forceinline void*
operator new(size_t s,Space & home)3033   VarImp<VIC>::operator new(size_t s, Space& home) {
3034     return home.ralloc(s);
3035   }
3036 
3037 #ifndef __GNUC__
3038   forceinline void
operator delete(void *)3039   Advisor::operator delete(void*) {}
3040 #endif
3041   forceinline void
operator delete(void *,Space &)3042   Advisor::operator delete(void*, Space&) {}
3043   forceinline void*
operator new(size_t s,Space & home)3044   Advisor::operator new(size_t s, Space& home) {
3045     return home.ralloc(s);
3046   }
3047 
3048   forceinline void
operator delete(void *)3049   NGL::operator delete(void*) {}
3050   forceinline void
operator delete(void *,Space &)3051   NGL::operator delete(void*, Space&) {}
3052   forceinline void*
operator new(size_t s,Space & home)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
NoGoods(void)3063   NoGoods::NoGoods(void)
3064     : n(0) {}
3065   forceinline unsigned long int
ng(void) const3066   NoGoods::ng(void) const {
3067     return n;
3068   }
3069   forceinline void
ng(unsigned long int n0)3070   NoGoods::ng(unsigned long int n0) {
3071     n=n0;
3072   }
3073   forceinline
~NoGoods(void)3074   NoGoods::~NoGoods(void) {}
3075 
3076 
3077   /*
3078    * Information from meta search engines
3079    */
3080   forceinline
MetaInfo(unsigned long int r0,unsigned long long int s0,unsigned long long int f0,const Space * l0,NoGoods & ng0)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
MetaInfo(unsigned int a0)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
type(void) const3093   MetaInfo::type(void) const {
3094     return t;
3095   }
3096   forceinline unsigned long int
restart(void) const3097   MetaInfo::restart(void) const {
3098     assert(type() == RESTART);
3099     return r;
3100   }
3101   forceinline unsigned long long int
solution(void) const3102   MetaInfo::solution(void) const {
3103     assert(type() == RESTART);
3104     return s;
3105   }
3106   forceinline unsigned long long int
fail(void) const3107   MetaInfo::fail(void) const {
3108     assert(type() == RESTART);
3109     return f;
3110   }
3111   forceinline const Space*
last(void) const3112   MetaInfo::last(void) const {
3113     assert(type() == RESTART);
3114     return l;
3115   }
3116   forceinline const NoGoods&
nogoods(void) const3117   MetaInfo::nogoods(void) const {
3118     assert(type() == RESTART);
3119     return ng;
3120   }
3121   forceinline unsigned int
asset(void) const3122   MetaInfo::asset(void) const {
3123     assert(type() == PORTFOLIO);
3124     return a;
3125   }
3126 
3127 
3128 
3129   /*
3130    * ActorLink
3131    *
3132    */
3133   forceinline ActorLink*
prev(void) const3134   ActorLink::prev(void) const {
3135     return _prev;
3136   }
3137 
3138   forceinline ActorLink*
next(void) const3139   ActorLink::next(void) const {
3140     return _next;
3141   }
3142 
3143   forceinline ActorLink**
next_ref(void)3144   ActorLink::next_ref(void) {
3145     return &_next;
3146   }
3147 
3148   forceinline void
prev(ActorLink * al)3149   ActorLink::prev(ActorLink* al) {
3150     _prev = al;
3151   }
3152 
3153   forceinline void
next(ActorLink * al)3154   ActorLink::next(ActorLink* al) {
3155     _next = al;
3156   }
3157 
3158   forceinline void
unlink(void)3159   ActorLink::unlink(void) {
3160     ActorLink* p = _prev; ActorLink* n = _next;
3161     p->_next = n; n->_prev = p;
3162   }
3163 
3164   forceinline void
init(void)3165   ActorLink::init(void) {
3166     _next = this; _prev =this;
3167   }
3168 
3169   forceinline void
head(ActorLink * a)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
tail(ActorLink * a)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
empty(void) const3186   ActorLink::empty(void) const {
3187     return _next == this;
3188   }
3189 
3190   template<class T>
3191   forceinline ActorLink*
cast(T * a)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*
cast(const T * a)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*
cast(ActorLink * al)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*
cast(const ActorLink * al)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
notice(Actor & a,ActorProperty p,bool duplicate)3230   Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3231     s.notice(a,p,duplicate);
3232   }
3233 
3234   forceinline Space*
clone(CloneStatistics &) const3235   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
commit(const Choice & c,unsigned int a,CommitStatistics &)3243   Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3244     _commit(c,a);
3245   }
3246 
3247   forceinline void
trycommit(const Choice & c,unsigned int a,CommitStatistics &)3248   Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3249     _trycommit(c,a);
3250   }
3251 
3252   forceinline double
afc_decay(void) const3253   Space::afc_decay(void) const {
3254     return ssd.data().gpi.decay();
3255   }
3256 
3257   forceinline void
afc_decay(double d)3258   Space::afc_decay(double d) {
3259     ssd.data().gpi.decay(d);
3260   }
3261 
3262   forceinline size_t
dispose(Space &)3263   Actor::dispose(Space&) {
3264     return sizeof(*this);
3265   }
3266 
3267 
3268   /*
3269    * Home for posting actors
3270    *
3271    */
3272   forceinline
Home(Space & s0,Propagator * p0,PropagatorGroup pg0,BrancherGroup bg0)3273   Home::Home(Space& s0, Propagator* p0,
3274              PropagatorGroup pg0, BrancherGroup bg0)
3275     : s(s0), p(p0), pg(pg0), bg(bg0) {}
3276   forceinline
Home(const Home & h)3277   Home::Home(const Home& h)
3278     : s(h.s), p(h.p), pg(h.pg), bg(h.bg) {}
3279   forceinline Home&
operator =(const Home & h)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
operator Space&(void)3285   Home::operator Space&(void) {
3286     return s;
3287   }
3288   forceinline Home
operator ()(Propagator & p)3289   Home::operator ()(Propagator& p) {
3290     return Home(s,&p);
3291   }
3292   forceinline Home
operator ()(PropagatorGroup pg)3293   Home::operator ()(PropagatorGroup pg) {
3294     return Home(s,nullptr,pg,BrancherGroup::def);
3295   }
3296   forceinline Home
operator ()(BrancherGroup bg)3297   Home::operator ()(BrancherGroup bg) {
3298     return Home(s,nullptr,PropagatorGroup::def,bg);
3299   }
3300   forceinline Home
operator ()(Propagator & p)3301   Space::operator ()(Propagator& p) {
3302     return Home(*this,&p);
3303   }
3304   forceinline Home
operator ()(PropagatorGroup pg)3305   Space::operator ()(PropagatorGroup pg) {
3306     return Home(*this,nullptr,pg,BrancherGroup::def);
3307   }
3308   forceinline Home
operator ()(BrancherGroup bg)3309   Space::operator ()(BrancherGroup bg) {
3310     return Home(*this,nullptr,PropagatorGroup::def,bg);
3311   }
3312   forceinline Propagator*
propagator(void) const3313   Home::propagator(void) const {
3314     return p;
3315   }
3316   forceinline PropagatorGroup
propagatorgroup(void) const3317   Home::propagatorgroup(void) const {
3318     return pg;
3319   }
3320   forceinline BrancherGroup
branchergroup(void) const3321   Home::branchergroup(void) const {
3322     return bg;
3323   }
3324 
3325   /*
3326    * View trace information
3327    *
3328    */
3329   forceinline void
propagator(Propagator & p)3330   ViewTraceInfo::propagator(Propagator& p) {
3331     who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR;
3332   }
3333   forceinline void
brancher(Brancher & b)3334   ViewTraceInfo::brancher(Brancher& b) {
3335     who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER;
3336   }
3337   forceinline void
post(PropagatorGroup g)3338   ViewTraceInfo::post(PropagatorGroup g) {
3339     who = (g.id() << 2) | POST;
3340   }
3341   forceinline void
other(void)3342   ViewTraceInfo::other(void) {
3343     who = OTHER;
3344   }
3345   forceinline ViewTraceInfo::What
what(void) const3346   ViewTraceInfo::what(void) const {
3347     return static_cast<What>(who & 3);
3348   }
3349   forceinline const Propagator&
propagator(void) const3350   ViewTraceInfo::propagator(void) const {
3351     assert(what() == PROPAGATOR);
3352     // Because PROPAGATOR == 0
3353     return *reinterpret_cast<Propagator*>(who);
3354   }
3355   forceinline const Brancher&
brancher(void) const3356   ViewTraceInfo::brancher(void) const {
3357     assert(what() == BRANCHER);
3358     return *reinterpret_cast<Brancher*>(who & ~3);
3359   }
3360   forceinline PropagatorGroup
post(void) const3361   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
PostInfo(Home home)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
~PostInfo(void)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
PropagateTraceInfo(unsigned int i0,PropagatorGroup g0,const Propagator * p0,Status s0)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
id(void) const3396   PropagateTraceInfo::id(void) const {
3397     return i;
3398   }
3399   forceinline PropagatorGroup
group(void) const3400   PropagateTraceInfo::group(void) const {
3401     return g;
3402   }
3403   forceinline const Propagator*
propagator(void) const3404   PropagateTraceInfo::propagator(void) const {
3405     return p;
3406   }
3407   forceinline PropagateTraceInfo::Status
status(void) const3408   PropagateTraceInfo::status(void) const {
3409     return s;
3410   }
3411 
3412 
3413   /*
3414    * Commit trace information
3415    *
3416    */
3417   forceinline
CommitTraceInfo(const Brancher & b0,const Choice & c0,unsigned int a0)3418   CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0,
3419                                    unsigned int a0)
3420     : b(b0), c(c0), a(a0) {}
3421   forceinline unsigned int
id(void) const3422   CommitTraceInfo::id(void) const {
3423     return b.id();
3424   }
3425   forceinline BrancherGroup
group(void) const3426   CommitTraceInfo::group(void) const {
3427     return b.group();
3428   }
3429   forceinline const Brancher&
brancher(void) const3430   CommitTraceInfo::brancher(void) const {
3431     return b;
3432   }
3433   forceinline const Choice&
choice(void) const3434   CommitTraceInfo::choice(void) const {
3435     return c;
3436   }
3437   forceinline unsigned int
alternative(void) const3438   CommitTraceInfo::alternative(void) const {
3439     return a;
3440   }
3441 
3442 
3443   /*
3444    * Post trace information
3445    *
3446    */
3447   forceinline
PostTraceInfo(PropagatorGroup g0,Status s0,unsigned int n0)3448   PostTraceInfo::PostTraceInfo(PropagatorGroup g0, Status s0, unsigned int n0)
3449     : g(g0), s(s0), n(n0) {}
3450   forceinline PropagatorGroup
group(void) const3451   PostTraceInfo::group(void) const {
3452     return g;
3453   }
3454   forceinline PostTraceInfo::Status
status(void) const3455   PostTraceInfo::status(void) const {
3456     return s;
3457   }
3458   forceinline unsigned int
propagators(void) const3459   PostTraceInfo::propagators(void) const {
3460     return n;
3461   }
3462 
3463 
3464   /*
3465    * Propagator
3466    *
3467    */
3468   forceinline Propagator*
cast(ActorLink * al)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*
cast(const ActorLink * al)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*
fwd(void) const3485   Propagator::fwd(void) const {
3486     return static_cast<Propagator*>(prev());
3487   }
3488 
3489   forceinline bool
disabled(void) const3490   Propagator::disabled(void) const {
3491     return Support::marked(gpi_disabled);
3492   }
3493 
3494   forceinline void
disable(Space & home)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
enable(Space & home)3501   Propagator::enable(Space& home) {
3502     (void) home;
3503     gpi_disabled = Support::funmark(gpi_disabled);
3504   }
3505 
3506   forceinline Kernel::GPI::Info&
gpi(void)3507   Propagator::gpi(void) {
3508     return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled));
3509   }
3510 
3511   forceinline
Propagator(Home home)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
Propagator(Space &,Propagator & p)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
modeventdelta(void) const3534   Propagator::modeventdelta(void) const {
3535     return u.med;
3536   }
3537 
3538   forceinline double
afc(void) const3539   Propagator::afc(void) const {
3540     return const_cast<Propagator&>(*this).gpi().afc;
3541   }
3542 
3543 #ifdef GECODE_HAS_CBS
3544   forceinline void
solndistrib(Space &,SendMarginal) const3545   Propagator::solndistrib(Space&, SendMarginal) const {}
3546 
3547   forceinline void
domainsizesum(InDecision,unsigned int & size,unsigned int & size_b) const3548   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
id(void) const3556   Propagator::id(void) const {
3557     return const_cast<Propagator&>(*this).gpi().pid;
3558   }
3559 
3560   forceinline PropagatorGroup
group(void) const3561   Propagator::group(void) const {
3562     return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3563   }
3564 
3565   forceinline void
group(PropagatorGroup g)3566   Propagator::group(PropagatorGroup g) {
3567     gpi().gid = g.id();
3568   }
3569 
3570   forceinline ExecStatus
ES_SUBSUMED_DISPOSED(Propagator & p,size_t s)3571   Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) {
3572     p.u.size = s;
3573     return ES_SUBSUMED_;
3574   }
3575 
3576   forceinline ExecStatus
ES_SUBSUMED(Propagator & p)3577   Space::ES_SUBSUMED(Propagator& p) {
3578     p.u.size = p.dispose(*this);
3579     return ES_SUBSUMED_;
3580   }
3581 
3582   forceinline ExecStatus
ES_FIX_PARTIAL(Propagator & p,const ModEventDelta & med)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
ES_NOFIX_PARTIAL(Propagator & p,const ModEventDelta & med)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*
cast(ActorLink * al)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*
cast(const ActorLink * al)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
Brancher(Home _home)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
Brancher(Space &,Brancher & b)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
id(void) const3643   Brancher::id(void) const {
3644     return bid;
3645   }
3646 
3647   forceinline BrancherGroup
group(void) const3648   Brancher::group(void) const {
3649     return BrancherGroup(gid);
3650   }
3651 
3652   forceinline void
group(BrancherGroup g)3653   Brancher::group(BrancherGroup g) {
3654     gid = g.id();
3655   }
3656 
3657 
3658   forceinline void
kill(Brancher & b)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
kill(Propagator & p)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*
brancher(unsigned int id)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*
cast(ActorLink * al)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*
cast(const ActorLink * al)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
LocalObject(Home home)3747   LocalObject::LocalObject(Home home) {
3748     (void) home;
3749     ActorLink::cast(this)->prev(nullptr);
3750   }
3751 
3752   forceinline
LocalObject(Space &,LocalObject &)3753   LocalObject::LocalObject(Space&, LocalObject&) {
3754     ActorLink::cast(this)->prev(nullptr);
3755   }
3756 
3757   forceinline LocalObject*
fwd(Space & home)3758   LocalObject::fwd(Space& home) {
3759     if (prev() == nullptr)
3760       fwdcopy(home);
3761     return LocalObject::cast(prev());
3762   }
3763 
3764   forceinline
LocalHandle(void)3765   LocalHandle::LocalHandle(void) : o(nullptr) {}
3766   forceinline
LocalHandle(LocalObject * lo)3767   LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {}
3768   forceinline
LocalHandle(const LocalHandle & lh)3769   LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3770   forceinline LocalHandle&
operator =(const LocalHandle & lh)3771   LocalHandle::operator =(const LocalHandle& lh) {
3772     o = lh.o;
3773     return *this;
3774   }
3775   forceinline
~LocalHandle(void)3776   LocalHandle::~LocalHandle(void) {}
3777   forceinline LocalObject*
object(void) const3778   LocalHandle::object(void) const { return o; }
3779   forceinline void
object(LocalObject * n)3780   LocalHandle::object(LocalObject* n) { o = n; }
3781   forceinline void
update(Space & home,LocalHandle & lh)3782   LocalHandle::update(Space& home, LocalHandle& lh) {
3783     object(lh.object()->fwd(home));
3784   }
3785 
3786 
3787   /*
3788    * Choices
3789    *
3790    */
3791   forceinline
Choice(const Brancher & b,const unsigned int a)3792   Choice::Choice(const Brancher& b, const unsigned int a)
3793     : bid(b.id()), alt(a) {}
3794 
3795   forceinline unsigned int
alternatives(void) const3796   Choice::alternatives(void) const {
3797     return alt;
3798   }
3799 
3800   forceinline unsigned int
id(void) const3801   Choice::id(void) const {
3802     return bid;
3803   }
3804 
3805   forceinline
~Choice(void)3806   Choice::~Choice(void) {}
3807 
3808 
3809 
3810   /*
3811    * No-good literal
3812    *
3813    */
3814   forceinline bool
leaf(void) const3815   NGL::leaf(void) const {
3816     return Support::marked(nl);
3817   }
3818   forceinline NGL*
next(void) const3819   NGL::next(void) const {
3820     return static_cast<NGL*>(Support::funmark(nl));
3821   }
3822   forceinline void
leaf(bool l)3823   NGL::leaf(bool l) {
3824     nl = l ? Support::fmark(nl) : Support::funmark(nl);
3825   }
3826   forceinline void
next(NGL * n)3827   NGL::next(NGL* n) {
3828     nl = Support::marked(nl) ? Support::mark(n) : n;
3829   }
3830   forceinline NGL*
add(NGL * n,bool l)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
NGL(void)3838   NGL::NGL(void)
3839     : nl(nullptr) {}
3840   forceinline
NGL(Space &)3841   NGL::NGL(Space&)
3842     : nl(nullptr) {}
3843   forceinline
NGL(Space &,NGL &)3844   NGL::NGL(Space&, NGL&)
3845     : nl(nullptr) {}
3846   forceinline size_t
dispose(Space &)3847   NGL::dispose(Space&) {
3848     return sizeof(*this);
3849   }
3850 
3851   /*
3852    * Advisor
3853    *
3854    */
3855   template<class A>
3856   forceinline
Advisor(Space &,Propagator & p,Council<A> & c)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
Advisor(Space &,Advisor &)3865   Advisor::Advisor(Space&, Advisor&) {}
3866 
3867   forceinline bool
disposed(void) const3868   Advisor::disposed(void) const {
3869     return prev() == nullptr;
3870   }
3871 
3872   forceinline Advisor*
cast(ActorLink * al)3873   Advisor::cast(ActorLink* al) {
3874     return static_cast<Advisor*>(al);
3875   }
3876 
3877   forceinline const Advisor*
cast(const ActorLink * al)3878   Advisor::cast(const ActorLink* al) {
3879     return static_cast<const Advisor*>(al);
3880   }
3881 
3882   forceinline Propagator&
propagator(void) const3883   Advisor::propagator(void) const {
3884     assert(!disposed());
3885     return *Propagator::cast(ActorLink::prev());
3886   }
3887 
3888   template<class A>
3889   forceinline void
dispose(Space &,Council<A> &)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&
operator ()(const Space & home) const3900   Advisor::operator ()(const Space& home) const {
3901     return home.pc.p.vti;
3902   }
3903 
3904   template<class A>
3905   forceinline ExecStatus
ES_FIX_DISPOSE(Council<A> & c,A & a)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
ES_NOFIX_DISPOSE(Council<A> & c,A & a)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
ES_NOFIX_DISPOSE_FORCE(Council<A> & c,A & a)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
Council(void)3933   Council<A>::Council(void) {}
3934 
3935   template<class A>
3936   forceinline
Council(Space &)3937   Council<A>::Council(Space&)
3938     : advisors(nullptr) {}
3939 
3940   template<class A>
3941   forceinline bool
empty(void) const3942   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
update(Space & home,Council<A> & c)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
dispose(Space & home)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
Advisors(const Council<A> & c)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
operator ()(void) const4022   Advisors<A>::operator ()(void) const {
4023     return a != nullptr;
4024   }
4025 
4026   template<class A>
4027   forceinline void
operator ++(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&
advisor(void) const4036   Advisors<A>::advisor(void) const {
4037     return *static_cast<A*>(a);
4038   }
4039 
4040 
4041 
4042   /*
4043    * Space
4044    *
4045    */
4046   forceinline void
enqueue(Propagator * p)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
fail(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
fail(void)4065   Home::fail(void) {
4066     s.fail();
4067   }
4068 
4069   forceinline bool
failed(void) const4070   Space::failed(void) const {
4071     return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4072   }
4073   forceinline bool
failed(void) const4074   Home::failed(void) const {
4075     return s.failed();
4076   }
4077 
4078   forceinline bool
stable(void) const4079   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
notice(Actor & a,ActorProperty p,bool d)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
ignore(Actor & a,ActorProperty p,bool d)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**
actor(PropCond pc)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**
actorNonZero(PropCond pc)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&
idx(PropCond pc)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
idx(PropCond pc) const4148   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
VarImp(Space & home)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
VarImp(void)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
id(void) const4185   VarImp<VIC>::id(void) const {
4186     return var_id;
4187   }
4188 #endif
4189 
4190   template<class VIC>
4191   forceinline unsigned int
degree(void) const4192   VarImp<VIC>::degree(void) const {
4193     assert(!copied());
4194     return entries;
4195   }
4196 
4197   template<class VIC>
4198   forceinline double
afc(void) const4199   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
modevent(const Delta & d)4224   VarImp<VIC>::modevent(const Delta& d) {
4225     return d.me;
4226   }
4227 
4228   template<class VIC>
4229   forceinline unsigned int
bits(void) const4230   VarImp<VIC>::bits(void) const {
4231     return free_and_bits;
4232   }
4233 
4234   template<class VIC>
4235   forceinline unsigned int&
bits(void)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>*
vars_d(Space & home)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
vars_d(Space & home,VarImp<VIC> * x)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
copied(void) const4256   VarImp<VIC>::copied(void) const {
4257     return Support::marked(b.fwd);
4258   }
4259 
4260   template<class VIC>
4261   forceinline VarImp<VIC>*
forward(void) const4262   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>*
next(void) const4269   VarImp<VIC>::next(void) const {
4270     assert(copied());
4271     return u.next;
4272   }
4273 
4274   template<class VIC>
4275   forceinline
VarImp(Space & home,VarImp<VIC> & x)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
me(const ModEventDelta & med)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
med(ModEvent me)4310   VarImp<VIC>::med(ModEvent me) {
4311     return static_cast<ModEventDelta>(me << VIC::med_fst);
4312   }
4313 
4314   template<class VIC>
4315   forceinline ModEvent
me_combine(ModEvent me1,ModEvent me2)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
schedule(Space & home,Propagator & p,ModEvent me,bool force)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
schedule(Space & home,PropCond pc1,PropCond pc2,ModEvent me)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
resize(Space & home)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
enter(Space & home,Propagator * p,PropCond pc)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
enter(Space & home,Advisor * a)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
subscribe(Space & home,Propagator & p,PropCond pc,bool assigned,ModEvent me,bool schedule)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
subscribe(Space & home,Advisor & a,bool assigned,bool fail)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
reschedule(Space & home,Propagator & p,PropCond pc,bool assigned,ModEvent me)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
remove(Space & home,Propagator * p,PropCond pc)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
cancel(Space & home,Propagator & p,PropCond pc)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
remove(Space & home,Advisor * a)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
cancel(Space & home,Advisor & a,bool fail)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
cancel(Space & home)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
advise(Space & home,ModEvent me,Delta & d)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
_fail(Space & home)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
fail(Space & home)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
update(VarImp<VIC> * x,ActorLink ** & sub)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
update(Space & home,ActorLink ** & sub)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>
VarImpDisposer(void)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
dispose(Space & home,VarImpBase * _x)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
reset(void)4730   StatusStatistics::reset(void) {
4731     propagate = 0;
4732   }
4733   forceinline
StatusStatistics(void)4734   StatusStatistics::StatusStatistics(void) {
4735     reset();
4736   }
4737   forceinline StatusStatistics&
operator +=(const StatusStatistics & s)4738   StatusStatistics::operator +=(const StatusStatistics& s) {
4739     propagate += s.propagate;
4740     return *this;
4741   }
4742   forceinline StatusStatistics
operator +(const StatusStatistics & s)4743   StatusStatistics::operator +(const StatusStatistics& s) {
4744     StatusStatistics t(s);
4745     return t += *this;
4746   }
4747 
4748   forceinline void
reset(void)4749   CloneStatistics::reset(void) {}
4750 
4751   forceinline
CloneStatistics(void)4752   CloneStatistics::CloneStatistics(void) {
4753     reset();
4754   }
4755   forceinline CloneStatistics
operator +(const CloneStatistics &)4756   CloneStatistics::operator +(const CloneStatistics&) {
4757     CloneStatistics s;
4758     return s;
4759   }
4760   forceinline CloneStatistics&
operator +=(const CloneStatistics &)4761   CloneStatistics::operator +=(const CloneStatistics&) {
4762     return *this;
4763   }
4764 
4765   forceinline void
reset(void)4766   CommitStatistics::reset(void) {}
4767 
4768   forceinline
CommitStatistics(void)4769   CommitStatistics::CommitStatistics(void) {
4770     reset();
4771   }
4772   forceinline CommitStatistics
operator +(const CommitStatistics &)4773   CommitStatistics::operator +(const CommitStatistics&) {
4774     CommitStatistics s;
4775     return s;
4776   }
4777   forceinline CommitStatistics&
operator +=(const CommitStatistics &)4778   CommitStatistics::operator +=(const CommitStatistics&) {
4779     return *this;
4780   }
4781 
4782   /*
4783    * Cost computation
4784    *
4785    */
4786 
4787   forceinline
PropCost(PropCost::ActualCost ac0)4788   PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
4789 
4790   forceinline PropCost
cost(PropCost::Mod m,PropCost::ActualCost lo,PropCost::ActualCost hi,unsigned int n)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
record(void)4805   PropCost::record(void) {
4806     return AC_RECORD;
4807   }
4808   forceinline PropCost
crazy(PropCost::Mod m,unsigned int n)4809   PropCost::crazy(PropCost::Mod m, unsigned int n) {
4810     return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4811   }
4812   forceinline PropCost
crazy(PropCost::Mod m,int n)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
cubic(PropCost::Mod m,unsigned int n)4818   PropCost::cubic(PropCost::Mod m, unsigned int n) {
4819     return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4820   }
4821   forceinline PropCost
cubic(PropCost::Mod m,int n)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
quadratic(PropCost::Mod m,unsigned int n)4827   PropCost::quadratic(PropCost::Mod m, unsigned int n) {
4828     return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4829   }
4830   forceinline PropCost
quadratic(PropCost::Mod m,int n)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
linear(PropCost::Mod m,unsigned int n)4836   PropCost::linear(PropCost::Mod m, unsigned int n) {
4837     return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4838   }
4839   forceinline PropCost
linear(PropCost::Mod m,int n)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
ternary(PropCost::Mod m)4845   PropCost::ternary(PropCost::Mod m) {
4846     return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4847   }
4848   forceinline PropCost
binary(PropCost::Mod m)4849   PropCost::binary(PropCost::Mod m) {
4850     return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4851   }
4852   forceinline PropCost
unary(PropCost::Mod m)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
Propagators(Space & home0)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
operator ()(void) const4880   Space::Propagators::operator ()(void) const {
4881     return c != nullptr;
4882   }
4883   forceinline void
operator ++(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&
propagator(void) const4908   Space::Propagators::propagator(void) const {
4909     return *Propagator::cast(c);
4910   }
4911 
4912 
4913   forceinline
ScheduledPropagators(Space & home0)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
operator ()(void) const4926   Space::ScheduledPropagators::operator ()(void) const {
4927     return c != nullptr;
4928   }
4929   forceinline void
operator ++(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&
propagator(void) const4948   Space::ScheduledPropagators::propagator(void) const {
4949     return *Propagator::cast(c);
4950   }
4951 
4952 
4953   forceinline
IdlePropagators(Space & home)4954   Space::IdlePropagators::IdlePropagators(Space& home) {
4955     c = Propagator::cast(home.pl.next());
4956     e = Propagator::cast(&home.pl);
4957   }
4958   forceinline bool
operator ()(void) const4959   Space::IdlePropagators::operator ()(void) const {
4960     return c != e;
4961   }
4962   forceinline void
operator ++(void)4963   Space::IdlePropagators::operator ++(void) {
4964     c = c->next();
4965   }
4966   forceinline Propagator&
propagator(void) const4967   Space::IdlePropagators::propagator(void) const {
4968     return *Propagator::cast(c);
4969   }
4970 
4971 
4972   forceinline
Branchers(Space & home)4973   Space::Branchers::Branchers(Space& home)
4974     : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4975   forceinline bool
operator ()(void) const4976   Space::Branchers::operator ()(void) const {
4977     return c != e;
4978   }
4979   forceinline void
operator ++(void)4980   Space::Branchers::operator ++(void) {
4981     c = c->next();
4982   }
4983   forceinline Brancher&
brancher(void) const4984   Space::Branchers::brancher(void) const {
4985     return *Brancher::cast(c);
4986   }
4987 
4988 
4989   /*
4990    * Groups of actors
4991    */
4992   forceinline
Group(unsigned int gid0)4993   Group::Group(unsigned int gid0) : gid(gid0) {}
4994 
4995   forceinline bool
in(Group actor) const4996   Group::in(Group actor) const {
4997     return (gid == GROUPID_ALL) || (gid == actor.gid);
4998   }
4999 
5000   forceinline bool
in(void) const5001   Group::in(void) const {
5002     return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
5003   }
5004 
5005   forceinline
Group(const Group & g)5006   Group::Group(const Group& g) : gid(g.gid) {}
5007 
5008   forceinline Group&
operator =(const Group & g)5009   Group::operator =(const Group& g) {
5010     gid=g.gid; return *this;
5011   }
5012 
5013   forceinline unsigned int
id(void) const5014   Group::id(void) const {
5015     return gid;
5016   }
5017 
5018 
5019   forceinline
PropagatorGroup(void)5020   PropagatorGroup::PropagatorGroup(void) {}
5021 
5022   forceinline
PropagatorGroup(unsigned int gid)5023   PropagatorGroup::PropagatorGroup(unsigned int gid)
5024     : Group(gid) {}
5025 
5026   forceinline
PropagatorGroup(const PropagatorGroup & g)5027   PropagatorGroup::PropagatorGroup(const PropagatorGroup& g)
5028     : Group(g) {}
5029 
5030   forceinline PropagatorGroup&
operator =(const PropagatorGroup & g)5031   PropagatorGroup::operator =(const PropagatorGroup& g) {
5032     return static_cast<PropagatorGroup&>(Group::operator =(g));
5033   }
5034 
5035   forceinline Home
operator ()(Space & home)5036   PropagatorGroup::operator ()(Space& home) {
5037     return Home(home,nullptr,*this,BrancherGroup::def);
5038   }
5039 
5040   forceinline bool
operator ==(PropagatorGroup g) const5041   PropagatorGroup::operator ==(PropagatorGroup g) const {
5042     return id() == g.id();
5043   }
5044   forceinline bool
operator !=(PropagatorGroup g) const5045   PropagatorGroup::operator !=(PropagatorGroup g) const {
5046     return id() != g.id();
5047   }
5048 
5049   forceinline PropagatorGroup&
move(Space &,Propagator & p)5050   PropagatorGroup::move(Space& , Propagator& p) {
5051     if (id() != GROUPID_ALL)
5052       p.group(*this);
5053     return *this;
5054   }
5055 
5056 
5057   forceinline
BrancherGroup(void)5058   BrancherGroup::BrancherGroup(void) {}
5059 
5060   forceinline
BrancherGroup(unsigned int gid)5061   BrancherGroup::BrancherGroup(unsigned int gid)
5062     : Group(gid) {}
5063 
5064   forceinline
BrancherGroup(const BrancherGroup & g)5065   BrancherGroup::BrancherGroup(const BrancherGroup& g)
5066     : Group(g) {}
5067 
5068   forceinline BrancherGroup&
operator =(const BrancherGroup & g)5069   BrancherGroup::operator =(const BrancherGroup& g) {
5070     return static_cast<BrancherGroup&>(Group::operator =(g));
5071   }
5072 
5073   forceinline Home
operator ()(Space & home)5074   BrancherGroup::operator ()(Space& home) {
5075     return Home(home,nullptr,PropagatorGroup::def,*this);
5076   }
5077 
5078   forceinline bool
operator ==(BrancherGroup g) const5079   BrancherGroup::operator ==(BrancherGroup g) const {
5080     return id() == g.id();
5081   }
5082   forceinline bool
operator !=(BrancherGroup g) const5083   BrancherGroup::operator !=(BrancherGroup g) const {
5084     return id() != g.id();
5085   }
5086 
5087   forceinline BrancherGroup&
move(Space &,Brancher & p)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
Propagators(const Space & home,PropagatorGroup g0)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
operator ()(void) const5106   Propagators::operator ()(void) const {
5107     return ps();
5108   }
5109   forceinline void
operator ++(void)5110   Propagators::operator ++(void) {
5111     do
5112       ++ps;
5113     while (ps() && !g.in(ps.propagator().group()));
5114   }
5115   forceinline const Propagator&
propagator(void) const5116   Propagators::propagator(void) const {
5117     return ps.propagator();
5118   }
5119 
5120   forceinline
Branchers(const Space & home,BrancherGroup g0)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
operator ()(void) const5127   Branchers::operator ()(void) const {
5128     return bs();
5129   }
5130   forceinline void
operator ++(void)5131   Branchers::operator ++(void) {
5132     do
5133       ++bs;
5134     while (bs() && !g.in(bs.brancher().group()));
5135   }
5136   forceinline const Brancher&
brancher(void) const5137   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&
construct(void)5148   Space::construct(void) {
5149     return alloc<T>(1);
5150   }
5151   template<class T, typename A1>
5152   forceinline T&
construct(A1 const & a1)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&
construct(A1 const & a1,A2 const & a2)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&
construct(A1 const & a1,A2 const & a2,A3 const & a3)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&
construct(A1 const & a1,A2 const & a2,A3 const & a3,A4 const & a4)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&
construct(A1 const & a1,A2 const & a2,A3 const & a3,A4 const & a4,A5 const & a5)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
5190