Generated on Sat May 25 2013 18:00:38 for Gecode by doxygen 1.8.3.1
brancher.hpp
Go to the documentation of this file.
1 namespace Gecode { namespace Set { namespace LDSB {
2 
3  template<class View, int n, class Val, unsigned int a>
6  ViewSel<View>* vs[n],
8  SymmetryImp<View>** syms, int nsyms,
10  : LDSBBrancher<View,n,Val,a>(home, x, vs, vsc, syms, nsyms, bf),
11  _prevPos(-1),
12  _copiedSyms(NULL),
13  _nCopiedSyms(0),
14  _stable(false) {
15  // Put all the value symmetries at the end of the list.
16  int seen = 0;
17  int dest = this->_nsyms - 1;
18  for (int i = 0 ; i < this->_nsyms - seen ; i++) {
19  if (dynamic_cast<ValueSymmetryImp<View>*>(this->_syms[i])) {
20  SymmetryImp<View>* t = this->_syms[i];
21  this->_syms[i] = this->_syms[dest];
22  this->_syms[dest] = t;
23  dest--;
24  seen++;
25  }
26  }
27  _nValueSymmetries = seen;
28  _nNonValueSymmetries = this->_nsyms - seen;
29  }
30 
31  template<class View, int n, class Val, unsigned int a>
34  : LDSBBrancher<View,n,Val,a>(home,shared,b),
35  _prevPos(b._prevPos),
36  _nNonValueSymmetries(b._nNonValueSymmetries),
37  _nValueSymmetries(b._nValueSymmetries),
38  _nCopiedSyms(b._nCopiedSyms),
39  _leftBranchValues(b._leftBranchValues),
40  _stable(b._stable) {
41  if (_nCopiedSyms > 0) {
43  for (int i = 0 ; i < _nCopiedSyms ; i++)
44  _copiedSyms[i] = static_cast<ValueSymmetryImp<View>*>(
45  b._copiedSyms[i]->copy(home, shared));
46  } else {
47  _copiedSyms = NULL;
48  }
49  }
50 
60  template <class View>
63  // Calculate intersection and difference.
64  IntArgs intersection;
65  IntArgs difference;
66  int n = 0;
67  for (int i = s->values.next(s->values.offset()) ;
68  i <= s->values.max_bit() ; i = s->values.next(i+1)) {
69  n++;
70  if (usedValues.in(i))
71  intersection << i;
72  else
73  difference << i;
74  }
75 
76  for (IntSetValues v(usedValues) ; v() ; ++v) {
77  s->update(Literal(0, v.val()));
78  }
79 
80  if (intersection.size() < 2)
81  return NULL;
82  int *a = new int[intersection.size()];
83  for (int i = 0 ; i < intersection.size() ; i++) {
84  a[i] = intersection[i];
85  }
87  new (home) ValueSymmetryImp<View>(home, a, intersection.size());
88  delete [] a;
89  return ns;
90  }
91 
92  template<class View, int n, class Val, unsigned int a>
93  void
95  updatePart1(Space& home, int choicePos) {
96  if (_nValueSymmetries > 0) {
97  // If this is a different variable from the last commit, restore
98  // the old value symmetries and update the copy.
99  if (choicePos != _prevPos) {
100  if (_prevPos != -1) {
101  int i = 0;
102  for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
103  this->_syms[j] = _copiedSyms[i];
104  i++;
105  }
106 
107  for (int i = 0 ; i < _nCopiedSyms ; i++) {
109  specialUpdate(home, _copiedSyms[i], _leftBranchValues);
110  if (ns) {
111  this->_syms = home.realloc<SymmetryImp<View>*>(this->_syms,
112  this->_nsyms,
113  this->_nsyms+1);
114  this->_syms[this->_nsyms] = ns;
115  this->_nsyms++;
116  this->_nValueSymmetries++;
117  }
118  }
119  }
120 
121  // Reset for current variable, make copy of value symmetries
122  _leftBranchValues = IntSet::empty;
123  _prevPos = choicePos;
124  if (_nCopiedSyms > 0) home.free(_copiedSyms, _nCopiedSyms);
125  _nCopiedSyms = _nValueSymmetries;
126  _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
127  int i = 0;
128  for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
129  ValueSymmetryImp<View>* vsi =
130  static_cast<ValueSymmetryImp<View>*>(this->_syms[j]);
131  _copiedSyms[i] =
132  static_cast<ValueSymmetryImp<View>*>(vsi->copy(home, false));
133  i++;
134  }
135  }
136  }
137  }
138 
139  // Compute choice
140  template<class View, int n, class Val, unsigned int a>
141  const Choice*
143  // Making the PVC here is not so nice, I think.
145  const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
146 
147  // Compute symmetries.
148 
149  int choicePos = pvc->pos().pos;
150  delete c;
151 
152  assert(!_stable);
153  updatePart1(home, choicePos);
154 
156  }
157 
158  template<class View, int n, class Val, unsigned int a>
159  ExecStatus
161  ::commit(Space& home, const Choice& c, unsigned int b) {
162  const LDSBChoice<Val>& pvc
163  = static_cast<const LDSBChoice<Val>&>(c);
164  int choicePos = pvc.pos().pos;
165  int choiceVal = pvc.val();
166 
167  if (!_stable)
168  updatePart1(home, choicePos);
169 
170  if (b == 0) {
171  IntArgs ia;
172  for (IntSetValues v(_leftBranchValues) ; v() ; ++v) {
173  ia << v.val();
174  }
175  ia << choiceVal;
176  _leftBranchValues = IntSet(ia);
177 
178  // Post the branching constraint.
179  ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
180  GECODE_ES_CHECK(fromBase);
181  for (int i = 0 ; i < this->_nsyms ; i++)
182  this->_syms[i]->update(Literal(choicePos, choiceVal));
183  } else if (b == 1) {
184  // Post the branching constraint.
185  ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
186  GECODE_ES_CHECK(fromBase);
187 
188  // Post prunings.
189  int nliterals = pvc.nliterals();
190  const Literal* literals = pvc.literals();
191  for (int i = 0 ; i < nliterals ; i++) {
192  const Literal& l = literals[i];
193  ModEvent me = prune<View>(home, this->x[l._variable], l._value);
194  GECODE_ME_CHECK(me);
195  }
196  }
197 
198  return ES_OK;
199  }
200 
201  template<class View, int n, class Val, unsigned int a>
202  Actor*
204  return new (home) LDSBSetBrancher<View,n,Val,a>(home,shared,*this);
205  }
206 
207  template<class View, int n, class Val, unsigned int a>
212  SymmetryImp<View>** syms, int nsyms,
213  SetBranchFilter bf) {
214  return *new (home) LDSBSetBrancher<View,n,Val,a>(home,x,vs,vsc,syms,nsyms,bf);
215  }
216 
217 }}}
218 
219 // STATISTICS: set-branch