1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *
6  *  Copyright:
7  *     Christian Schulte, 2009
8  *
9  *  This file is part of Gecode, the generic constraint
10  *  development environment:
11  *     http://www.gecode.org
12  *
13  *  Permission is hereby granted, free of charge, to any person obtaining
14  *  a copy of this software and associated documentation files (the
15  *  "Software"), to deal in the Software without restriction, including
16  *  without limitation the rights to use, copy, modify, merge, publish,
17  *  distribute, sublicense, and/or sell copies of the Software, and to
18  *  permit persons to whom the Software is furnished to do so, subject to
19  *  the following conditions:
20  *
21  *  The above copyright notice and this permission notice shall be
22  *  included in all copies or substantial portions of the Software.
23  *
24  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode {
35 
36   /**
37    * \brief Wait propagator for single view
38    *
39    * Requires \code #include <gecode/kernel/wait.hh> \endcode
40    * \ingroup FuncKernelProp
41    */
42   template<class View>
43   class UnaryWait : public Propagator {
44   protected:
45     /// View to wait for becoming assigned
46     View x;
47     /// Continuation to execute
48     SharedData<std::function<void(Space& home)>> c;
49     /// Constructor for creation
50     UnaryWait(Home home, View x, std::function<void(Space& home)> c0);
51     /// Constructor for cloning \a p
52     UnaryWait(Space& home, UnaryWait& p);
53   public:
54     /// Perform copying during cloning
55     virtual Actor* copy(Space& home);
56     /// Const function (defined as low unary)
57     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
58     /// Schedule function
59     virtual void reschedule(Space& home);
60     /// Perform propagation
61     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
62     /// Post propagator that waits until \a x becomes assigned and then executes \a c
63     static ExecStatus post(Home home, View x,
64                            std::function<void(Space& home)> c);
65     /// Delete propagator and return its size
66     virtual size_t dispose(Space& home);
67   };
68 
69   /**
70    * \brief Wait propagator for several views
71    *
72    * Requires \code #include <gecode/kernel/wait.hh> \endcode
73    * \ingroup FuncKernelProp
74    */
75   template<class View>
76   class NaryWait : public Propagator {
77   protected:
78     /// Views to wait for becoming assigned
79     ViewArray<View> x;
80     /// Continuation to execute
81     SharedData<std::function<void(Space& home)>> c;
82     /// Constructor for creation
83     NaryWait(Home home, ViewArray<View>& x,
84              std::function<void(Space& home)> c0);
85     /// Constructor for cloning \a p
86     NaryWait(Space& home, NaryWait& p);
87   public:
88     /// Perform copying during cloning
89     virtual Actor* copy(Space& home);
90     /// Const function (defined as high unary)
91     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
92     /// Schedule function
93     virtual void reschedule(Space& home);
94     /// Perform propagation
95     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
96     /// Post propagator that waits until \a x becomes assigned and then executes \a c
97     static ExecStatus post(Home home, ViewArray<View>& x,
98                            std::function<void(Space& home)> c);
99     /// Delete propagator and return its size
100     virtual size_t dispose(Space& home);
101   };
102 
103 
104   /*
105    * Wait propagator for single view
106    *
107    */
108   template<class View>
109   forceinline
UnaryWait(Home home,View x0,std::function<void (Space & home)> c0)110   UnaryWait<View>::UnaryWait(Home home, View x0,
111                              std::function<void(Space& home)> c0)
112     : Propagator(home), x(x0), c(c0) {
113     x.subscribe(home,*this,PC_GEN_ASSIGNED);
114     home.notice(*this,AP_DISPOSE);
115   }
116   template<class View>
117   forceinline
UnaryWait(Space & home,UnaryWait & p)118   UnaryWait<View>::UnaryWait(Space& home, UnaryWait& p)
119     : Propagator(home,p), c(p.c) {
120     x.update(home,p.x);
121   }
122   template<class View>
123   Actor*
copy(Space & home)124   UnaryWait<View>::copy(Space& home) {
125     return new (home) UnaryWait<View>(home,*this);
126   }
127   template<class View>
128   PropCost
cost(const Space &,const ModEventDelta &) const129   UnaryWait<View>::cost(const Space&, const ModEventDelta&) const {
130     return PropCost::unary(PropCost::LO);
131   }
132   template<class View>
133   void
reschedule(Space & home)134   UnaryWait<View>::reschedule(Space& home) {
135     x.reschedule(home,*this,PC_GEN_ASSIGNED);
136   }
137   template<class View>
138   ExecStatus
propagate(Space & home,const ModEventDelta &)139   UnaryWait<View>::propagate(Space& home, const ModEventDelta&) {
140     assert(x.assigned());
141     GECODE_VALID_FUNCTION(c());
142     c()(home);
143     return home.failed() ? ES_FAILED : home.ES_SUBSUMED(*this);
144   }
145   template<class View>
146   forceinline ExecStatus
post(Home home,View x,std::function<void (Space & home)> c)147   UnaryWait<View>::post(Home home, View x,
148                         std::function<void(Space& home)> c) {
149     if (!c)
150       throw InvalidFunction("UnaryWait::post");
151     if (x.assigned()) {
152       c(home);
153       return home.failed() ? ES_FAILED : ES_OK;
154     } else {
155       (void) new (home) UnaryWait<View>(home,x,c);
156       return ES_OK;
157     }
158   }
159   template<class View>
160   size_t
dispose(Space & home)161   UnaryWait<View>::dispose(Space& home) {
162     x.cancel(home,*this,PC_GEN_ASSIGNED);
163     home.ignore(*this,AP_DISPOSE);
164     c.~SharedData<std::function<void(Space& home)>>();
165     (void) Propagator::dispose(home);
166     return sizeof(*this);
167   }
168 
169 
170   /*
171    * Wait propagator for several views
172    *
173    */
174   template<class View>
175   forceinline
NaryWait(Home home,ViewArray<View> & x0,std::function<void (Space & home)> c0)176   NaryWait<View>::NaryWait(Home home, ViewArray<View>& x0,
177                            std::function<void(Space& home)> c0)
178     : Propagator(home), x(x0), c(c0) {
179     assert(!x[0].assigned());
180     x[0].subscribe(home,*this,PC_GEN_ASSIGNED);
181     home.notice(*this,AP_DISPOSE);
182   }
183   template<class View>
184   forceinline
NaryWait(Space & home,NaryWait & p)185   NaryWait<View>::NaryWait(Space& home, NaryWait& p)
186     : Propagator(home,p), c(p.c) {
187     x.update(home,p.x);
188   }
189   template<class View>
190   Actor*
copy(Space & home)191   NaryWait<View>::copy(Space& home) {
192     assert(!x[0].assigned());
193     for (int i=x.size()-1; i>0; i--)
194       if (x[i].assigned())
195         x.move_lst(i);
196     assert(x.size() > 0);
197     return new (home) NaryWait<View>(home,*this);
198   }
199   template<class View>
200   PropCost
cost(const Space &,const ModEventDelta &) const201   NaryWait<View>::cost(const Space&, const ModEventDelta&) const {
202     return PropCost::unary(PropCost::HI);
203   }
204   template<class View>
205   void
reschedule(Space & home)206   NaryWait<View>::reschedule(Space& home) {
207     x[0].reschedule(home,*this,PC_GEN_ASSIGNED);
208   }
209   template<class View>
210   ExecStatus
propagate(Space & home,const ModEventDelta &)211   NaryWait<View>::propagate(Space& home, const ModEventDelta& ) {
212     assert(x[0].assigned());
213     for (int i=x.size()-1; i>0; i--)
214       if (x[i].assigned())
215         x.move_lst(i);
216     assert(x.size() > 0);
217     if (x.size() == 1) {
218       x.size(0);
219       GECODE_VALID_FUNCTION(c());
220       c()(home);
221       return home.failed() ? ES_FAILED : home.ES_SUBSUMED(*this);
222     } else {
223       // Create new subscription
224       x.move_lst(0);
225       assert(!x[0].assigned());
226       x[0].subscribe(home,*this,PC_GEN_ASSIGNED,false);
227       return ES_OK;
228     }
229   }
230   template<class View>
231   forceinline ExecStatus
post(Home home,ViewArray<View> & x,std::function<void (Space & home)> c)232   NaryWait<View>::post(Home home, ViewArray<View>& x,
233                        std::function<void(Space& home)> c) {
234     if (!c)
235       throw InvalidFunction("NaryWait::post");
236     for (int i=x.size(); i--; )
237       if (x[i].assigned())
238         x.move_lst(i);
239     if (x.size() == 0) {
240       c(home);
241       return home.failed() ? ES_FAILED : ES_OK;
242     } else {
243       x.unique();
244       if (x.size() == 1) {
245         return UnaryWait<View>::post(home,x[0],c);
246       } else {
247         (void) new (home) NaryWait<View>(home,x,c);
248         return ES_OK;
249       }
250     }
251   }
252   template<class View>
253   size_t
dispose(Space & home)254   NaryWait<View>::dispose(Space& home) {
255     if (x.size() > 0)
256       x[0].cancel(home,*this,PC_GEN_ASSIGNED);
257     home.ignore(*this,AP_DISPOSE);
258     c.~SharedData<std::function<void(Space& home)>>();
259     (void) Propagator::dispose(home);
260     return sizeof(*this);
261   }
262 
263 }
264 
265 // STATISTICS: kernel-prop
266