Generated on Sat Feb 7 2015 02:01:15 for Gecode by doxygen 1.8.9.1
val.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, 2003
8  *
9  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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 namespace Gecode { namespace Int { namespace Distinct {
39 
40  /*
41  * Eliminating singleton variables
42  *
43  */
44  template<class View, bool complete>
47  assert(x.size() > 1);
48  int n = x.size();
49 
50  Region r(home);
51  int* stack = r.alloc<int>(n);
52  int* c_v = &stack[0];
53  // c_n is the current number of values on stack
54  int c_n = 0;
55 
56  // Collect all assigned variables on stack
57  for (int i = n; i--; )
58  if (x[i].assigned()) {
59  c_v[c_n++]=x[i].val(); x[i]=x[--n];
60  }
61 
62  // The number of trips
63  int t = 0;
64  do {
65  t++;
66  if (!complete && (t > 16)) {
67  // Give up after sixteen iterations, but the values must be
68  // propagated first
69  // Maybe we are lucky in that this iteration does the trick...
70  ExecStatus es = ES_FIX;
71  while (c_n > 0) {
72  int v = c_v[--c_n];
73  // Check whether value is on stack only once
74  for (int i = c_n; i--; )
75  if (c_v[i] == v)
76  goto failed;
77  // Tell and do not collect new values
78  for (int i = n; i--; ) {
79  ModEvent me = x[i].nq(home,v);
80  if (me_failed(me))
81  goto failed;
82  if (me == ME_INT_VAL)
83  es = ES_NOFIX;
84  }
85  }
86  x.size(n);
87  return es;
88  }
89  if (c_n > 31) {
90  // Many values, use full domain operation
91  IntSet d(&c_v[0],c_n);
92  // If the size s of d is different from the number of values,
93  // a value must have appeared multiply: failure
94  if (d.size() != static_cast<unsigned int>(c_n))
95  goto failed;
96  // We do not need the values on the stack any longer, reset
97  c_n = 0;
98  // Tell and collect new values
99  for (int i = n; i--; )
100  if ((d.min() <= x[i].max()) && (d.max() >= x[i].min())) {
101  IntSetRanges dr(d);
102  ModEvent me = x[i].minus_r(home,dr,false);
103  if (me_failed(me))
104  goto failed;
105  if (me == ME_INT_VAL) {
106  c_v[c_n++]=x[i].val(); x[i]=x[--n];
107  }
108  }
109  } else {
110  // Values for next iteration
111  int* n_v = &c_v[c_n];
112  // Stack top for the next iteration
113  int n_n = 0;
114  while (c_n > 0) {
115  int v = c_v[--c_n];
116  // Check whether value is not on current stack
117  for (int i = c_n; i--; )
118  if (c_v[i] == v)
119  goto failed;
120  // Check whether value is not on next stack
121  for (int i = n_n; i--; )
122  if (n_v[i] == v)
123  goto failed;
124  // Tell and collect new values
125  for (int i = n; i--; ) {
126  ModEvent me = x[i].nq(home,v);
127  if (me_failed(me))
128  goto failed;
129  if (me == ME_INT_VAL) {
130  n_v[n_n++]=x[i].val(); x[i]=x[--n];
131  }
132  }
133  }
134  c_v = n_v; c_n = n_n;
135  }
136  } while (c_n > 0);
137  x.size(n);
138  return ES_FIX;
139  failed:
140  x.size(0);
141  return ES_FAILED;
142  }
143 
144 
145  /*
146  * The propagator proper
147  *
148  */
149  template<class View>
152  : NaryPropagator<View,PC_INT_VAL>(home,x) {}
153 
154  template<class View>
156  Val<View>::Val(Space& home, bool share, Val<View>& p)
157  : NaryPropagator<View,PC_INT_VAL>(home,share,p) {}
158 
159  template<class View>
160  Actor*
161  Val<View>::copy(Space& home, bool share) {
162  return new (home) Val<View>(home,share,*this);
163  }
164 
165  template<class View>
166  ExecStatus
168  GECODE_ES_CHECK((prop_val<View,true>(home,x)));
169  return (x.size() < 2) ? home.ES_SUBSUMED(*this) : ES_FIX;
170  }
171 
172  template<class View>
173  ExecStatus
175  if (x.size() == 2)
176  return Rel::Nq<View>::post(home,x[0],x[1]);
177  if (x.size() > 2)
178  (void) new (home) Val<View>(home,x);
179  return ES_OK;
180  }
181 
182 }}}
183 
184 // STATISTICS: int-prop
185 
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:167
Range iterator for integer sets.
Definition: int.hh:271
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Val(Home home, ViewArray< View > &x)
Constructor for posting.
Definition: val.hpp:151
int ModEvent
Type for modification events.
Definition: core.hpp:146
Handle to region.
Definition: region.hpp:61
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 Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: val.hpp:161
#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::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
n-ary propagator
Definition: propagator.hpp:143
Integer sets.
Definition: int.hh:171
View arrays.
Definition: array.hpp:234
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: val.hpp:174
ExecStatus prop_val(Space &home, ViewArray< View > &x)
Eliminate singletons by naive value propagation.
Definition: val.hpp:46
const int v[7]
Definition: distinct.cpp:207
Naive value distinct propagator.
Definition: distinct.hh:68
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
Binary disequality propagator.
Definition: rel.hh:432
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82