Generated on Fri Aug 24 2012 04:52:09 for Gecode by doxygen 1.8.1.2
int.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * David Rijsman <David.Rijsman@quintiq.com>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * David Rijsman, 2009
11  * Christian Schulte, 2009
12  *
13  * Last modified:
14  * $Date: 2011-05-24 00:48:31 +1000 (Tue, 24 May 2011) $
15  * $Revision: 12018 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int { namespace Sequence {
43 
44  template<class View, class Val>
47  int q0, int l0, int u0)
48  : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0),
49  vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home) {
50  home.notice(*this,AP_DISPOSE);
51  for (int i=x.size(); i--; ) {
52  if (undecided(x[i],s)) {
53  x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i));
54  } else {
55  x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
56  }
57  }
58  }
59 
60  template<class View, class Val>
63  : Propagator(home,share,p), s(p.s), q(p.q), l(p.l), u(p.u),
64  vvsamax(), vvsamin() {
65  x.update(home,share,p.x);
66  ac.update(home,share,p.ac);
67  vvsamax.update(home,share,p.vvsamax);
68  vvsamin.update(home,share,p.vvsamin);
69  }
70 
71  template<class View,class Val>
75  ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d);
76  if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) {
77  status = ES_NOFIX;
78  }
79 
80  if (!undecided(x[a.i],s)) {
81  if (!x[a.i].assigned())
82  x[a.i].cancel(home,a);
83 
84  if ( ES_NOFIX == status ) {
85  return home.ES_NOFIX_DISPOSE(ac,a);
86  } else {
87  return home.ES_FIX_DISPOSE(ac,a);
88  }
89  }
90 
91  return status;
92  }
93 
94  template<class View, class Val>
95  forceinline size_t
97  home.ignore(*this,AP_DISPOSE);
98  ac.dispose(home);
99  s.~Val();
100  (void) Propagator::dispose(home);
101  return sizeof(*this);
102  }
103 
104  template<class View, class Val>
106  Sequence<View,Val>::check(Space& home, ViewArray<View>& x, Val s, int q, int l, int u) {
107  Region r(home);
108  // could do this with an array of length q...
109  int* upper = r.alloc<int>(x.size()+1);
110  int* lower = r.alloc<int>(x.size()+1);
111  upper[0] = 0;
112  lower[0] = 0;
113  for ( int j=0; j<x.size(); j++ ) {
114  upper[j+1] = upper[j];
115  lower[j+1] = lower[j];
116  if (includes(x[j],s)) {
117  upper[j+1] += 1;
118  } else if (excludes(x[j],s)) {
119  lower[j+1] += 1;
120  }
121  if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) {
122  return ES_FAILED;
123  }
124  }
125  return ES_OK;
126  }
127 
128  template<class View, class Val>
129  ExecStatus
130  Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) {
131  GECODE_ES_CHECK(check(home,x,s,q,l,u));
132  Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u);
133 
134  GECODE_ES_CHECK(p->vvsamax.propagate(home,x,s,q,l,u));
135  GECODE_ES_CHECK(p->vvsamin.propagate(home,x,s,q,l,u));
136 
137  return ES_OK;
138  }
139 
140  template<class View, class Val>
141  Actor*
142  Sequence<View,Val>::copy(Space& home, bool share) {
143  return new (home) Sequence<View,Val>(home,share,*this);
144  }
145 
146  template<class View, class Val>
147  PropCost
149  return PropCost::cubic(PropCost::HI,x.size());
150  }
151 
152  template<class View, class Val>
153  ExecStatus
155  GECODE_ES_CHECK(vvsamax.propagate(home,x,s,q,l,u));
156  GECODE_ES_CHECK(vvsamin.propagate(home,x,s,q,l,u));
157 
158  for (int i=x.size(); i--; )
159  if (undecided(x[i],s))
160  return ES_FIX;
161 
162  return home.ES_SUBSUMED(*this);
163  }
164 
165 }}}
166 
167 // STATISTICS: int-prop
168