Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
argmax.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2015
8  *
9  * Last modified:
10  * $Date: 2015-01-16 14:10:48 +0100 (Fri, 16 Jan 2015) $ by $Author: schulte $
11  * $Revision: 14362 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/int/rel.hh>
39 
40 namespace Gecode { namespace Int { namespace Arithmetic {
41 
42  template<class VA, class VB, bool tiebreak>
45  : Propagator(home), x(x0), y(y0) {
46  x.subscribe(home,*this,PC_INT_BND);
47  y.subscribe(home,*this,PC_INT_DOM);
48  }
49 
50  template<class VA, class VB, bool tiebreak>
53  assert(x.size() > 0);
54  if (x.size() == 1) {
55  GECODE_ME_CHECK(y.eq(home,x[0].idx));
56  } else if (y.assigned()) {
57  int max=0;
58  while (x[max].idx < y.val())
59  max++;
60  assert(x[max].idx == y.val());
61  if (tiebreak)
62  for (int i=0; i<max; i++)
64  x[i].view,x[max].view));
65  else
66  for (int i=0; i<max; i++)
68  x[i].view,x[max].view));
69  for (int i=max+1; i<x.size(); i++)
71  x[i].view,x[max].view));
72  } else {
73  (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
74  }
75  return ES_OK;
76  }
77 
78  template<class VA, class VB, bool tiebreak>
82  : Propagator(home,share,p) {
83  x.update(home,share,p.x);
84  y.update(home,share,p.y);
85  }
86 
87  template<class VA, class VB, bool tiebreak>
88  Actor*
89  ArgMax<VA,VB,tiebreak>::copy(Space& home, bool share) {
90  return new (home) ArgMax<VA,VB,tiebreak>(home,share,*this);
91  }
92 
93  template<class VA, class VB, bool tiebreak>
94  PropCost
96  const ModEventDelta&) const {
97  return PropCost::linear(PropCost::LO,x.size()+1);
98  }
99 
100  template<class VA, class VB, bool tiebreak>
101  ExecStatus
103  /*
104  * A key invariant is as follows: for each value i in the domain
105  * of y there is an index-value pair with index i in x.
106  */
107 
108  // Compute lower and upper bounds for the maximum and its first position.
109  int p = x[0].idx;
110  int l = x[0].view.min();
111  int u = x[0].view.max();
112  for (int i=1; i<x.size(); i++) {
113  if (l < x[i].view.min()) {
114  p = x[i].idx; l = x[i].view.min();
115  }
116  if (u < x[i].view.max())
117  u = x[i].view.max();
118  }
119 
120  // Eliminate elements from x and y that are too small
121  {
122  Region r(home);
123 
124  // Values to delete from y
125  int* d=r.alloc<int>(y.size());
126  // Number of values to delete
127  int n = 0;
128 
129  int i=0, j=0;
130  ViewValues<VB> iy(y);
131 
132  while ((i < x.size()) && iy()) {
133  if (x[i].idx == iy.val()) {
134  if (x[i].view.max() < l) {
135  x[i].view.cancel(home,*this,PC_INT_BND);
136  d[n++]=x[i].idx;
137  } else {
138  x[j++]=x[i];
139  }
140  ++iy;
141  } else {
142  assert(x[i].idx < iy.val());
143  if (x[i].view.max() < l) {
144  x[i].view.cancel(home,*this,PC_INT_BND);
145  } else {
146  x[j++]=x[i];
147  }
148  }
149  i++;
150  }
151  while (i < x.size())
152  if (x[i].view.max() < l) {
153  x[i].view.cancel(home,*this,PC_INT_BND); i++;
154  } else {
155  x[j++]=x[i++];
156  }
157  x.size(j);
158 
159  if (n == y.size())
160  return ES_FAILED;
161  Iter::Values::Array id(d,n);
162  GECODE_ME_CHECK(y.minus_v(home,id,false));
163  }
164 
165  /*
166  * Now the following invariant holds:
167  * - for all q in y: u >= x(q).max() >= l
168  * - if l==u, then exists q in y: x(q).max = u
169  */
170 
171  if (tiebreak && (l == u))
172  GECODE_ME_CHECK(y.lq(home,p));
173 
174  if (y.assigned()) {
175  int max=0;
176  while (x[max].idx < y.val())
177  max++;
178  assert(x[max].idx == y.val());
179  if (tiebreak)
180  for (int i=0; i<max; i++)
182  x[i].view,x[max].view));
183  else
184  for (int i=0; i<max; i++)
186  x[i].view,x[max].view));
187  for (int i=max+1; i<x.size(); i++)
189  x[i].view,x[max].view));
190  return home.ES_SUBSUMED(*this);
191  }
192 
193  // Recompute the upper bound for elements in y
194  {
195  ViewValues<VB> iy(y);
196  int i=0;
197  // Skip smaller elements
198  while (x[i].idx < y.min())
199  i++;
200  u=x[i].view.max();
201  // Skip the minimal element
202  i++; ++iy;
203  while (iy()) {
204  if (x[i].idx == iy.val()) {
205  u = std::max(u,x[i].view.max());
206  ++iy;
207  } else {
208  assert(x[i].idx < iy.val());
209  }
210  i++;
211  }
212  }
213 
214  // Constrain elements in x but not in y
215  {
216  int i = 0;
217  // Elements which must be smaller (for tiebreaking)
218  if (tiebreak)
219  while ((i < x.size()) && (x[i].idx < y.min())) {
220  GECODE_ME_CHECK(x[i].view.le(home,u));
221  i++;
222  }
223  else
224  while ((i < x.size()) && (x[i].idx < y.min())) {
225  GECODE_ME_CHECK(x[i].view.lq(home,u));
226  i++;
227  }
228  assert(x[i].idx == y.min());
229 
230  // Elements which cannot be larger
231  ViewValues<VB> iy(y);
232  // Skip the minimal element
233  i++; ++iy;
234  while ((i < x.size()) && iy()) {
235  if (x[i].idx == iy.val()) {
236  ++iy;
237  } else {
238  assert(x[i].idx < iy.val());
239  GECODE_ME_CHECK(x[i].view.lq(home,u));
240  }
241  i++;
242  }
243  while (i < x.size()) {
244  assert(x[i].idx > y.max());
245  GECODE_ME_CHECK(x[i].view.lq(home,u));
246  i++;
247  }
248  }
249  return tiebreak ? ES_NOFIX : ES_FIX;
250  }
251 
252  template<class VA, class VB, bool tiebreak>
253  forceinline size_t
255  x.cancel(home,*this,PC_INT_BND);
256  y.cancel(home,*this,PC_INT_DOM);
257  (void) Propagator::dispose(home);
258  return sizeof(*this);
259  }
260 
261 }}}
262 
263 // STATISTICS: int-prop
264 
ArgMax(Space &home, bool share, ArgMax &p)
Constructor for cloning p.
Definition: argmax.hpp:80
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
static ExecStatus post(Home home, IdxViewArray< VA > &x, VB y)
Post propagator .
Definition: argmax.hpp:52
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Value iterator for array of integers
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Base-class for propagators.
Definition: core.hpp:755
VB y
Position of maximum view (maximal argument)
Definition: arithmetic.hh:269
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::IntSet d(v, 7)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: argmax.hpp:95
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Less or equal propagator.
Definition: rel.hh:465
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: argmax.hpp:254
Argument maximum propagator.
Definition: arithmetic.hh:264
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:267
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int val(void) const
Return current value.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: argmax.hpp:102
Gecode toplevel namespace
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: argmax.hpp:89
Less propagator.
Definition: rel.hh:490
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:144