Generated on Thu Apr 5 2018 19:44:19 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$ by $Author$
11  * $Revision$
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>
81  : Propagator(home,p) {
82  x.update(home,p.x);
83  y.update(home,p.y);
84  }
85 
86  template<class VA, class VB, bool tiebreak>
87  Actor*
89  return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
90  }
91 
92  template<class VA, class VB, bool tiebreak>
93  PropCost
95  return PropCost::linear(PropCost::LO,x.size()+1);
96  }
97 
98  template<class VA, class VB, bool tiebreak>
99  void
101  x.reschedule(home,*this,PC_INT_BND);
102  y.reschedule(home,*this,PC_INT_DOM);
103  }
104 
105  template<class VA, class VB, bool tiebreak>
106  ExecStatus
108  /*
109  * A key invariant is as follows: for each value i in the domain
110  * of y there is an index-value pair with index i in x.
111  */
112 
113  // Compute lower and upper bounds for the maximum and its first position.
114  int p = x[0].idx;
115  int l = x[0].view.min();
116  int u = x[0].view.max();
117  for (int i=1; i<x.size(); i++) {
118  if (l < x[i].view.min()) {
119  p = x[i].idx; l = x[i].view.min();
120  }
121  if (u < x[i].view.max())
122  u = x[i].view.max();
123  }
124 
125  // Eliminate elements from x and y that are too small
126  {
127  Region r;
128 
129  // Values to delete from y
130  int* d=r.alloc<int>(y.size());
131  // Number of values to delete
132  int n = 0;
133 
134  int i=0, j=0;
135  ViewValues<VB> iy(y);
136 
137  while ((i < x.size()) && iy()) {
138  if (x[i].idx == iy.val()) {
139  if (x[i].view.max() < l) {
140  x[i].view.cancel(home,*this,PC_INT_BND);
141  d[n++]=x[i].idx;
142  } else {
143  x[j++]=x[i];
144  }
145  ++iy;
146  } else {
147  assert(x[i].idx < iy.val());
148  if (x[i].view.max() < l) {
149  x[i].view.cancel(home,*this,PC_INT_BND);
150  } else {
151  x[j++]=x[i];
152  }
153  }
154  i++;
155  }
156  while (i < x.size())
157  if (x[i].view.max() < l) {
158  x[i].view.cancel(home,*this,PC_INT_BND); i++;
159  } else {
160  x[j++]=x[i++];
161  }
162  x.size(j);
163 
164  if (static_cast<unsigned int>(n) == y.size())
165  return ES_FAILED;
166  Iter::Values::Array id(d,n);
167  GECODE_ME_CHECK(y.minus_v(home,id,false));
168  }
169 
170  /*
171  * Now the following invariant holds:
172  * - for all q in y: u >= x(q).max() >= l
173  * - if l==u, then exists q in y: x(q).max = u
174  */
175 
176  if (tiebreak && (l == u))
177  GECODE_ME_CHECK(y.lq(home,p));
178 
179  if (y.assigned()) {
180  int max=0;
181  while (x[max].idx < y.val())
182  max++;
183  assert(x[max].idx == y.val());
184  if (tiebreak)
185  for (int i=0; i<max; i++)
187  x[i].view,x[max].view)));
188  else
189  for (int i=0; i<max; i++)
191  x[i].view,x[max].view)));
192  for (int i=max+1; i<x.size(); i++)
194  x[i].view,x[max].view)));
195  return home.ES_SUBSUMED(*this);
196  }
197 
198  // Recompute the upper bound for elements in y
199  {
200  ViewValues<VB> iy(y);
201  int i=0;
202  // Skip smaller elements
203  while (x[i].idx < y.min())
204  i++;
205  u=x[i].view.max();
206  // Skip the minimal element
207  i++; ++iy;
208  while (iy()) {
209  if (x[i].idx == iy.val()) {
210  u = std::max(u,x[i].view.max());
211  ++iy;
212  } else {
213  assert(x[i].idx < iy.val());
214  }
215  i++;
216  }
217  }
218 
219  // Constrain elements in x but not in y
220  {
221  int i = 0;
222  // Elements which must be smaller (for tiebreaking)
223  if (tiebreak)
224  while ((i < x.size()) && (x[i].idx < y.min())) {
225  GECODE_ME_CHECK(x[i].view.le(home,u));
226  i++;
227  }
228  else
229  while ((i < x.size()) && (x[i].idx < y.min())) {
230  GECODE_ME_CHECK(x[i].view.lq(home,u));
231  i++;
232  }
233  assert(x[i].idx == y.min());
234 
235  // Elements which cannot be larger
236  ViewValues<VB> iy(y);
237  // Skip the minimal element
238  i++; ++iy;
239  while ((i < x.size()) && iy()) {
240  if (x[i].idx == iy.val()) {
241  ++iy;
242  } else {
243  assert(x[i].idx < iy.val());
244  GECODE_ME_CHECK(x[i].view.lq(home,u));
245  }
246  i++;
247  }
248  while (i < x.size()) {
249  assert(x[i].idx > y.max());
250  GECODE_ME_CHECK(x[i].view.lq(home,u));
251  i++;
252  }
253  }
254  return tiebreak ? ES_NOFIX : ES_FIX;
255  }
256 
257  template<class VA, class VB, bool tiebreak>
258  forceinline size_t
260  x.cancel(home,*this,PC_INT_BND);
261  y.cancel(home,*this,PC_INT_DOM);
262  (void) Propagator::dispose(home);
263  return sizeof(*this);
264  }
265 
266 }}}
267 
268 // STATISTICS: int-prop
269 
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:4643
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
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:384
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:1016
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:151
VB y
Position of maximum view (maximal argument)
Definition: arithmetic.hh:269
Handle to region.
Definition: region.hpp:57
Value iterator for integer views.
Definition: view.hpp:94
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Computation spaces.
Definition: core.hpp:1668
int val(void) const
Return current value.
Base-class for both propagators and branchers.
Definition: core.hpp:620
unsigned int id(void) const
Return propagator id.
Definition: core.hpp:3412
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:466
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:100
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: argmax.hpp:259
Argument maximum propagator.
Definition: arithmetic.hh:264
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: argmax.hpp:88
#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:94
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition: tiebreak.hpp:84
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:769
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
Propagation cost.
Definition: core.hpp:478
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
ExecStatus
Definition: core.hpp:464
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:267
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
ArgMax(Space &home, ArgMax &p)
Constructor for cloning p.
Definition: argmax.hpp:80
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: argmax.hpp:107
Gecode toplevel namespace
Less propagator.
Definition: rel.hh:523
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846