Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
prop.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, 2011
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 Member {
37 
38  template<class View>
41  : NaryOnePropagator<View,PC_INT_DOM>(home,x,y),
42  vs(vs0) {}
43 
44  template<class View>
45  forceinline void
47  int n=x.size();
48  for (int i=n; i--; )
49  if (x[i].assigned()) {
50  vs.add(home, x[i].val());
51  x[i] = x[--n];
52  }
53  x.size(n);
54  }
55 
56  template<class View>
57  forceinline void
59  int n=x.size();
60  for (int i=n; i--; )
61  if ((rtest_eq_dom(x[i],y) == RT_FALSE) || vs.subset(x[i])) {
62  // x[i] is different from y or values are contained in vs
63  x[i].cancel(home, *this, PC_INT_DOM);
64  x[i] = x[--n];
65  }
66  x.size(n);
67  }
68 
69  template<class View>
70  inline ExecStatus
72  if (x.size() == 0)
73  return ES_FAILED;
74 
75  x.unique();
76 
77  if (x.size() == 1)
78  return Rel::EqDom<View,View>::post(home,x[0],y);
79 
80  if (x.same(y))
81  return ES_OK;
82 
83  // Eliminate assigned views and store them into the value set
84  ValSet vs;
85  add(home, vs, x);
86 
87  if (x.size() == 0) {
88  ValSet::Ranges vsr(vs);
89  GECODE_ME_CHECK(y.inter_r(home,vsr,false));
90  return ES_OK;
91  }
92 
93  (void) new (home) Prop<View>(home, vs, x, y);
94  return ES_OK;
95  }
96 
97  template<class View>
100  (void) new (home) Prop<View>(home, vs, x, y);
101  return ES_OK;
102  }
103 
104  template<class View>
107  : NaryOnePropagator<View,PC_INT_DOM>(home, p) {
108  vs.update(home, p.vs);
109  }
110 
111  template<class View>
112  Propagator*
114  return new (home) Prop<View>(home, *this);
115  }
116 
117  template<class View>
118  forceinline size_t
120  vs.dispose(home);
122  return sizeof(*this);
123  }
124 
125  template<class View>
126  PropCost
127  Prop<View>::cost(const Space&, const ModEventDelta&) const {
128  return PropCost::linear(PropCost::HI, x.size()+1);
129  }
130 
131  template<class View>
132  ExecStatus
134  // Add assigned views to value set
135  if (View::me(med) == ME_INT_VAL)
136  add(home,vs,x);
137 
138  // Eliminate views from x
139  eliminate(home);
140 
141  if (x.size() == 0) {
142  // y must have values in the value set
143  ValSet::Ranges vsr(vs);
144  GECODE_ME_CHECK(y.inter_r(home,vsr,false));
145  return home.ES_SUBSUMED(*this);
146  }
147 
148  // Constrain y to union of x and value set
149  Region r;
150 
151  assert(x.size() > 0);
152  ValSet::Ranges vsr(vs);
153  ViewRanges<View> xsr(x[0]);
154  Iter::Ranges::NaryUnion u(r,vsr,xsr);
155  for (int i=1; i<x.size(); i++) {
156  ViewRanges<View> xir(x[i]);
157  u |= xir;
158  }
159 
160  GECODE_ME_CHECK(y.inter_r(home,u,false));
161 
162  // Check whether all values in y are already in the value set
163  if (vs.subset(y))
164  return home.ES_SUBSUMED(*this);
165 
166  return ES_FIX;
167  }
168 
169 }}}
170 
171 // STATISTICS: int-prop
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4723
Binary domain consistent equality propagator.
Definition: rel.hh:67
ViewArray< View > x
Array of views.
Definition: pattern.hpp:175
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:65
Base-class for propagators.
Definition: core.hpp:1023
Membership propagator.
Definition: member.hh:54
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
Computation spaces.
Definition: core.hpp:1701
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: prop.hpp:119
Range iterator for integer views.
Definition: view.hpp:54
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator for .
Definition: prop.hpp:71
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
static void add(Space &home, ValSet &vs, ViewArray< View > &x)
Add values of assigned views in x to value set va.
Definition: prop.hpp:46
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
void dispose(Space &home)
Dispose value set.
Definition: val-set.hpp:126
Execution has resulted in failure.
Definition: core.hpp:473
Iterator over ranges.
Definition: val-set.hh:78
Relation does not hold.
Definition: view.hpp:1702
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Range iterator for union of iterators.
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
ValSet vs
Value set storing the values of already assigned views.
Definition: member.hh:59
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
void update(Space &home, ValSet &vs)
Update value set during cloning.
Definition: val-set.hpp:101
(n+1)-ary propagator
Definition: pattern.hpp:172
Expensive.
Definition: core.hpp:513
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: prop.hpp:133
View arrays.
Definition: array.hpp:235
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Propagation cost.
Definition: core.hpp:485
Prop(Home home, ValSet &vs, ViewArray< View > &x, View y)
Constructor for posting.
Definition: prop.hpp:40
virtual PropCost cost(const Space &, const ModEventDelta &med) const
Cost function.
Definition: prop.hpp:127
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
void unique(void)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1399
Class for storing values of already assigned views.
Definition: val-set.hh:44
Gecode toplevel namespace
bool subset(View x) const
Whether all values of x are included in the value set.
Definition: val-set.hpp:171
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: prop.hpp:113
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
Home class for posting propagators
Definition: core.hpp:853
void eliminate(Space &home)
Eliminate views from x that are not equal to y or ar subsumed by vs.
Definition: prop.hpp:58
bool same(void) const
Test whether array has multiple occurence of the same view.
Definition: array.hpp:1368
void add(Space &home, int v)
Add value v to value set.
Definition: val-set.hpp:45