Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.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  * 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 #include <gecode/int/rel.hh>
35 
36 namespace Gecode { namespace Int { namespace Arithmetic {
37 
38  template<class VA, class VB, bool tiebreak>
41  : Propagator(home), x(x0), y(y0) {
42  x.subscribe(home,*this,PC_INT_BND);
43  y.subscribe(home,*this,PC_INT_DOM);
44  }
45 
46  template<class VA, class VB, bool tiebreak>
49  assert(x.size() > 0);
50  if (x.size() == 1) {
51  GECODE_ME_CHECK(y.eq(home,x[0].idx));
52  } else if (y.assigned()) {
53  int max=0;
54  while (x[max].idx < y.val())
55  max++;
56  assert(x[max].idx == y.val());
57  if (tiebreak)
58  for (int i=0; i<max; i++)
60  x[i].view,x[max].view)));
61  else
62  for (int i=0; i<max; i++)
64  x[i].view,x[max].view)));
65  for (int i=max+1; i<x.size(); i++)
67  x[i].view,x[max].view)));
68  } else {
69  (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
70  }
71  return ES_OK;
72  }
73 
74  template<class VA, class VB, bool tiebreak>
77  : Propagator(home,p) {
78  x.update(home,p.x);
79  y.update(home,p.y);
80  }
81 
82  template<class VA, class VB, bool tiebreak>
83  Actor*
85  return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
86  }
87 
88  template<class VA, class VB, bool tiebreak>
89  PropCost
91  return PropCost::linear(PropCost::LO,x.size()+1);
92  }
93 
94  template<class VA, class VB, bool tiebreak>
95  void
97  x.reschedule(home,*this,PC_INT_BND);
98  y.reschedule(home,*this,PC_INT_DOM);
99  }
100 
101  template<class VA, class VB, bool tiebreak>
102  ExecStatus
104  /*
105  * A key invariant is as follows: for each value i in the domain
106  * of y there is an index-value pair with index i in x.
107  */
108 
109  // Compute lower and upper bounds for the maximum and its first position.
110  int p = x[0].idx;
111  int l = x[0].view.min();
112  int u = x[0].view.max();
113  for (int i=1; i<x.size(); i++) {
114  if (l < x[i].view.min()) {
115  p = x[i].idx; l = x[i].view.min();
116  }
117  if (u < x[i].view.max())
118  u = x[i].view.max();
119  }
120 
121  // Eliminate elements from x and y that are too small
122  {
123  Region r;
124 
125  // Values to delete from y
126  int* d=r.alloc<int>(y.size());
127  // Number of values to delete
128  int n = 0;
129 
130  int i=0, j=0;
131  ViewValues<VB> iy(y);
132 
133  while ((i < x.size()) && iy()) {
134  if (x[i].idx == iy.val()) {
135  if (x[i].view.max() < l) {
136  x[i].view.cancel(home,*this,PC_INT_BND);
137  d[n++]=x[i].idx;
138  } else {
139  x[j++]=x[i];
140  }
141  ++iy;
142  } else {
143  assert(x[i].idx < iy.val());
144  if (x[i].view.max() < l) {
145  x[i].view.cancel(home,*this,PC_INT_BND);
146  } else {
147  x[j++]=x[i];
148  }
149  }
150  i++;
151  }
152  while (i < x.size())
153  if (x[i].view.max() < l) {
154  x[i].view.cancel(home,*this,PC_INT_BND); i++;
155  } else {
156  x[j++]=x[i++];
157  }
158  x.size(j);
159 
160  if (static_cast<unsigned int>(n) == y.size())
161  return ES_FAILED;
162  Iter::Values::Array id(d,n);
163  GECODE_ME_CHECK(y.minus_v(home,id,false));
164  }
165 
166  /*
167  * Now the following invariant holds:
168  * - for all q in y: u >= x(q).max() >= l
169  * - if l==u, then exists q in y: x(q).max = u
170  */
171 
172  if (tiebreak && (l == u))
173  GECODE_ME_CHECK(y.lq(home,p));
174 
175  if (y.assigned()) {
176  int max=0;
177  while (x[max].idx < y.val())
178  max++;
179  assert(x[max].idx == y.val());
180  if (tiebreak)
181  for (int i=0; i<max; i++)
183  x[i].view,x[max].view)));
184  else
185  for (int i=0; i<max; i++)
187  x[i].view,x[max].view)));
188  for (int i=max+1; i<x.size(); i++)
190  x[i].view,x[max].view)));
191  return home.ES_SUBSUMED(*this);
192  }
193 
194  // Recompute the upper bound for elements in y
195  {
196  ViewValues<VB> iy(y);
197  int i=0;
198  // Skip smaller elements
199  while (x[i].idx < y.min())
200  i++;
201  u=x[i].view.max();
202  // Skip the minimal element
203  i++; ++iy;
204  while (iy()) {
205  if (x[i].idx == iy.val()) {
206  u = std::max(u,x[i].view.max());
207  ++iy;
208  } else {
209  assert(x[i].idx < iy.val());
210  }
211  i++;
212  }
213  }
214 
215  // Constrain elements in x but not in y
216  {
217  int i = 0;
218  // Elements which must be smaller (for tiebreaking)
219  if (tiebreak)
220  while ((i < x.size()) && (x[i].idx < y.min())) {
221  GECODE_ME_CHECK(x[i].view.le(home,u));
222  i++;
223  }
224  else
225  while ((i < x.size()) && (x[i].idx < y.min())) {
226  GECODE_ME_CHECK(x[i].view.lq(home,u));
227  i++;
228  }
229  assert(x[i].idx == y.min());
230 
231  // Elements which cannot be larger
232  ViewValues<VB> iy(y);
233  // Skip the minimal element
234  i++; ++iy;
235  while ((i < x.size()) && iy()) {
236  if (x[i].idx == iy.val()) {
237  ++iy;
238  } else {
239  assert(x[i].idx < iy.val());
240  GECODE_ME_CHECK(x[i].view.lq(home,u));
241  }
242  i++;
243  }
244  while (i < x.size()) {
245  assert(x[i].idx > y.max());
246  GECODE_ME_CHECK(x[i].view.lq(home,u));
247  i++;
248  }
249  }
250  return tiebreak ? ES_NOFIX : ES_FIX;
251  }
252 
253  template<class VA, class VB, bool tiebreak>
254  forceinline size_t
256  x.cancel(home,*this,PC_INT_BND);
257  y.cancel(home,*this,PC_INT_DOM);
258  (void) Propagator::dispose(home);
259  return sizeof(*this);
260  }
261 
262 }}}
263 
264 // STATISTICS: int-prop
265 
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
Home class for posting propagators
Definition: core.hpp:856
Argument maximum propagator.
Definition: arithmetic.hh:260
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:263
VB y
Position of maximum view (maximal argument)
Definition: arithmetic.hh:265
ArgMax(Space &home, ArgMax &p)
Constructor for cloning p.
Definition: argmax.hpp:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: argmax.hpp:103
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: argmax.hpp:84
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: argmax.hpp:90
static ExecStatus post(Home home, IdxViewArray< VA > &x, VB y)
Post propagator .
Definition: argmax.hpp:48
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: argmax.hpp:255
virtual void reschedule(Space &home)
Schedule function.
Definition: argmax.hpp:96
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:131
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:153
Less propagator.
Definition: rel.hh:517
Less or equal propagator.
Definition: rel.hh:493
Value iterator for integer views.
Definition: view.hpp:94
int val(void) const
Return current value.
Value iterator for array of integers
Propagation cost.
Definition: core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
@ LO
Cheap.
Definition: core.hpp:513
Base-class for propagators.
Definition: core.hpp:1064
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
LDSB< TieBreak > tiebreak("TieBreak")
#define forceinline
Definition: config.hpp:185