Generated on Sat May 25 2013 18:00:37 for Gecode by doxygen 1.8.3.1
brancher.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christopher Mears <chris.mears@monash.edu>
5  *
6  * Copyright:
7  * Christopher Mears, 2012
8  *
9  * Last modified:
10  * $Date: 2013-03-07 17:39:13 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13458 $
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 <deque>
39 #include <set>
40 
41 namespace Gecode { namespace Int { namespace LDSB {
42 
45  : _variable(-1), _value(-1) {}
46 
48  Literal::Literal(int idx, int val)
49  : _variable(idx), _value(val) {}
50 
52  bool
53  Literal::operator <(const Literal &rhs) const {
54  int d = rhs._variable - _variable;
55  if (d > 0) return true;
56  else if (d == 0) return rhs._value > _value;
57  else return false;
58  }
59 
60 
61  template<class Val>
62  inline
63  LDSBChoice<Val>::LDSBChoice(const Brancher& b, unsigned int a, const Pos& p,
64  const Val& n, const Literal* literals,
65  int nliterals)
66  : PosValChoice<Val>(b,a,p,n), _literals(literals), _nliterals(nliterals)
67  {}
68 
69  template<class Val>
71  delete [] _literals;
72  }
73 
74  template<class Val>
75  forceinline const Literal*
76  LDSBChoice<Val>::literals(void) const { return _literals; }
77 
78  template<class Val>
79  forceinline int
80  LDSBChoice<Val>::nliterals(void) const { return _nliterals; }
81 
82  template<class Val>
83  size_t
84  LDSBChoice<Val>::size(void) const {
85  return sizeof(LDSBChoice<Val>);
86  }
87 
88  template<class Val>
89  void
92  e << _nliterals;
93  for (int i = 0 ; i < _nliterals ; i++) {
94  e << _literals[i]._variable;
95  e << _literals[i]._value;
96  }
97  }
98 
99 
100 
101  template<class View, int n, class Val, unsigned int a>
104  ViewSel<View>* vs[n],
106  SymmetryImp<View>** syms, int nsyms,
107  BranchFilter bf)
108  : ViewValBrancher<View,n,Val,a>(home, x, vs, vsc, bf),
109  _syms(syms),
110  _nsyms(nsyms),
111  _prevPos(-1)
112  {
113  home.notice(*this, AP_DISPOSE);
114  }
115 
116  template<class View, int n, class Val, unsigned int a>
121  SymmetryImp<View>** syms, int nsyms,
122  BranchFilter bf) {
123  return *new (home) LDSBBrancher<View,n,Val,a>(home,x,vs,vsc,syms,nsyms,bf);
124  }
125 
126  template<class View, int n, class Val, unsigned int a>
130  : ViewValBrancher<View,n,Val,a>(home,shared,b),
131  _nsyms(b._nsyms),
132  _prevPos(b._prevPos) {
134  for (int i = 0 ; i < _nsyms ; i++)
135  _syms[i] = b._syms[i]->copy(home, shared);
136  }
137 
138  template<class View, int n, class Val, unsigned int a>
139  Actor*
141  return new (home) LDSBBrancher<View,n,Val,a>(home,shared,*this);
142  }
143 
144 
145  // Compute choice
146  template<class View, int n, class Val, unsigned int a>
147  const Choice*
149  // Making the PVC here is not so nice, I think.
151  const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
152 
153  // Compute symmetries.
154 
155  int choicePos = pvc->pos().pos;
156  int choiceVal = pvc->val();
157  delete c;
158 
159  _prevPos = choicePos;
160 
161  // TODO: It should be possible to use simpler containers than the
162  // STL ones here.
163  std::deque<Literal> queue;
164  std::set<Literal> seen;
165 
166  seen.insert(Literal(choicePos, choiceVal));
167  queue.push_back(Literal(choicePos, choiceVal));
168 
169  do {
170  Literal l = queue[0];
171  queue.pop_front();
172 
173  for (int i = 0 ; i < _nsyms ; i++) {
174  ArgArray<Literal> toExclude = _syms[i]->symmetric(l, this->x);
175  for (int j = 0 ; j < toExclude.size() ; ++j) {
176  if (seen.find(toExclude[j]) == seen.end())
177  queue.push_back(toExclude[j]);
178  seen.insert(toExclude[j]);
179  }
180  }
181  } while (queue.size() > 0);
182 
183  // Convert "seen" vector into array.
184  int nliterals = seen.size();
185  Literal* literals = new Literal[nliterals];
186  std::set<Literal>::iterator it = seen.begin();
187  for (int i = 0 ; i < nliterals ; i++) {
188  literals[i] = *it;
189  ++it;
190  }
191 
192  return new LDSBChoice<Val>(*this,a,choicePos,choiceVal, literals, nliterals);
193  }
194 
195 
196  template<class View, int n, class Val, unsigned int a>
197  const Choice*
199  (void) home;
200  int p; e >> p;
201  Val v; e >> v;
202  int nliterals; e >> nliterals;
203  Literal* literals = new Literal[nliterals];
204  for (int i = 0 ; i < nliterals ; i++) {
205  e >> literals[i]._variable;
206  e >> literals[i]._value;
207  }
208  return new LDSBChoice<Val>(*this,a,p,v, literals, nliterals);
209  }
210 
211  template <>
212  inline
213  ModEvent
214  prune<Int::IntView>(Space& home, Int::IntView x, int v) {
215  return x.nq(home, v);
216  }
217 
218  template <>
219  inline
220  ModEvent
221  prune<Int::BoolView>(Space& home, Int::BoolView x, int v) {
222  return x.nq(home, v);
223  }
224 
225 
226  template<class View, int n, class Val, unsigned int a>
227  ExecStatus
229  ::commit(Space& home, const Choice& c, unsigned int b) {
230  const LDSBChoice<Val>& pvc
231  = static_cast<const LDSBChoice<Val>&>(c);
232  int choicePos = pvc.pos().pos;
233  int choiceVal = pvc.val();
234 
235  if (b == 0) {
236  // Post the branching constraint.
237  ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
238  GECODE_ES_CHECK(fromBase);
239  for (int i = 0 ; i < this->_nsyms ; i++)
240  this->_syms[i]->update(Literal(choicePos, choiceVal));
241  } else if (b == 1) {
242  // Post the branching constraint.
243  ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
244  GECODE_ES_CHECK(fromBase);
245 
246  // Post prunings.
247  int nliterals = pvc.nliterals();
248  const Literal* literals = pvc.literals();
249  for (int i = 0 ; i < nliterals ; i++) {
250  const Literal& l = literals[i];
251  ModEvent me = prune<View>(home, this->x[l._variable], l._value);
252  GECODE_ME_CHECK(me);
253  }
254  }
255 
256  return ES_OK;
257  }
258 
259  template<class View, int n, class Val, unsigned int a>
260  size_t
262  home.ignore(*this,AP_DISPOSE);
264  return sizeof(LDSBBrancher<View,n,Val,a>);
265  }
266 
267 }}}
268 
269 // STATISTICS: int-branch