Generated on Wed Jan 24 2018 21:22:26 for Gecode by doxygen 1.8.13
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: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
11  * $Revision: 15253 $
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  void
103  x.reschedule(home,*this,PC_INT_BND);
104  y.reschedule(home,*this,PC_INT_DOM);
105  }
106 
107  template<class VA, class VB, bool tiebreak>
108  ExecStatus
110  /*
111  * A key invariant is as follows: for each value i in the domain
112  * of y there is an index-value pair with index i in x.
113  */
114 
115  // Compute lower and upper bounds for the maximum and its first position.
116  int p = x[0].idx;
117  int l = x[0].view.min();
118  int u = x[0].view.max();
119  for (int i=1; i<x.size(); i++) {
120  if (l < x[i].view.min()) {
121  p = x[i].idx; l = x[i].view.min();
122  }
123  if (u < x[i].view.max())
124  u = x[i].view.max();
125  }
126 
127  // Eliminate elements from x and y that are too small
128  {
129  Region r(home);
130 
131  // Values to delete from y
132  int* d=r.alloc<int>(y.size());
133  // Number of values to delete
134  int n = 0;
135 
136  int i=0, j=0;
137  ViewValues<VB> iy(y);
138 
139  while ((i < x.size()) && iy()) {
140  if (x[i].idx == iy.val()) {
141  if (x[i].view.max() < l) {
142  x[i].view.cancel(home,*this,PC_INT_BND);
143  d[n++]=x[i].idx;
144  } else {
145  x[j++]=x[i];
146  }
147  ++iy;
148  } else {
149  assert(x[i].idx < iy.val());
150  if (x[i].view.max() < l) {
151  x[i].view.cancel(home,*this,PC_INT_BND);
152  } else {
153  x[j++]=x[i];
154  }
155  }
156  i++;
157  }
158  while (i < x.size())
159  if (x[i].view.max() < l) {
160  x[i].view.cancel(home,*this,PC_INT_BND); i++;
161  } else {
162  x[j++]=x[i++];
163  }
164  x.size(j);
165 
166  if (static_cast<unsigned int>(n) == y.size())
167  return ES_FAILED;
168  Iter::Values::Array id(d,n);
169  GECODE_ME_CHECK(y.minus_v(home,id,false));
170  }
171 
172  /*
173  * Now the following invariant holds:
174  * - for all q in y: u >= x(q).max() >= l
175  * - if l==u, then exists q in y: x(q).max = u
176  */
177 
178  if (tiebreak && (l == u))
179  GECODE_ME_CHECK(y.lq(home,p));
180 
181  if (y.assigned()) {
182  int max=0;
183  while (x[max].idx < y.val())
184  max++;
185  assert(x[max].idx == y.val());
186  if (tiebreak)
187  for (int i=0; i<max; i++)
189  x[i].view,x[max].view)));
190  else
191  for (int i=0; i<max; i++)
193  x[i].view,x[max].view)));
194  for (int i=max+1; i<x.size(); i++)
196  x[i].view,x[max].view)));
197  return home.ES_SUBSUMED(*this);
198  }
199 
200  // Recompute the upper bound for elements in y
201  {
202  ViewValues<VB> iy(y);
203  int i=0;
204  // Skip smaller elements
205  while (x[i].idx < y.min())
206  i++;
207  u=x[i].view.max();
208  // Skip the minimal element
209  i++; ++iy;
210  while (iy()) {
211  if (x[i].idx == iy.val()) {
212  u = std::max(u,x[i].view.max());
213  ++iy;
214  } else {
215  assert(x[i].idx < iy.val());
216  }
217  i++;
218  }
219  }
220 
221  // Constrain elements in x but not in y
222  {
223  int i = 0;
224  // Elements which must be smaller (for tiebreaking)
225  if (tiebreak)
226  while ((i < x.size()) && (x[i].idx < y.min())) {
227  GECODE_ME_CHECK(x[i].view.le(home,u));
228  i++;
229  }
230  else
231  while ((i < x.size()) && (x[i].idx < y.min())) {
232  GECODE_ME_CHECK(x[i].view.lq(home,u));
233  i++;
234  }
235  assert(x[i].idx == y.min());
236 
237  // Elements which cannot be larger
238  ViewValues<VB> iy(y);
239  // Skip the minimal element
240  i++; ++iy;
241  while ((i < x.size()) && iy()) {
242  if (x[i].idx == iy.val()) {
243  ++iy;
244  } else {
245  assert(x[i].idx < iy.val());
246  GECODE_ME_CHECK(x[i].view.lq(home,u));
247  }
248  i++;
249  }
250  while (i < x.size()) {
251  assert(x[i].idx > y.max());
252  GECODE_ME_CHECK(x[i].view.lq(home,u));
253  i++;
254  }
255  }
256  return tiebreak ? ES_NOFIX : ES_FIX;
257  }
258 
259  template<class VA, class VB, bool tiebreak>
260  forceinline size_t
262  x.cancel(home,*this,PC_INT_BND);
263  y.cancel(home,*this,PC_INT_DOM);
264  (void) Propagator::dispose(home);
265  return sizeof(*this);
266  }
267 
268 }}}
269 
270 // STATISTICS: int-prop
271 
ArgMax(Space &home, bool share, ArgMax &p)
Constructor for cloning p.
Definition: argmax.hpp:80
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
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:4841
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
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:53
Base-class for propagators.
Definition: core.hpp:1092
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:545
Computation spaces.
Definition: core.hpp:1748
int val(void) const
Return current value.
Base-class for both propagators and branchers.
Definition: core.hpp:696
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3593
Gecode::IntSet d(v, 7)
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
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:542
void cancel(Space &home, Propagator &p, PropCond pc)
Definition: idx-view.hpp:137
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:497
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual void reschedule(Space &home)
Schedule function.
Definition: argmax.hpp:102
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: argmax.hpp:261
Argument maximum propagator.
Definition: arithmetic.hh:264
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: argmax.hpp:95
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: idx-view.hpp:144
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
ExecStatus
Definition: core.hpp:540
#define forceinline
Definition: config.hpp:173
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:267
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: argmax.hpp:109
Gecode toplevel namespace
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: argmax.hpp:89
Less propagator.
Definition: rel.hh:523
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:151