Generated on Sat May 25 2013 18:00:37 for Gecode by doxygen 1.8.3.1
ldsb.cpp
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 22:51:13 +0100 (Thu, 07 Mar 2013) $ by $Author: tack $
11  * $Revision: 13468 $
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 <gecode/set/ldsb.hh>
39 #include <gecode/set/branch.hh>
40 #include <map>
41 
42 namespace Gecode {
43  using namespace Int::LDSB;
44  /*
45  * Implementation of some SymmetryHandle methods.
46  */
47 
50  for (int i = 0 ; i < x.size() ; i++)
51  a[i] = x[i].varimp();
53  }
56  for (int i = 0 ; i < x.size() ; i++)
57  a[i] = x[i].varimp();
59  }
60 }
61 
62 namespace Gecode { namespace Int { namespace LDSB {
63  template <>
64  ModEvent prune<Set::SetView>(Space& home, Set::SetView x, int v) {
65  return x.exclude(home, v);
66  }
67 }}}
68 
69 namespace Gecode { namespace Set { namespace LDSB {
70 
72  class VariableMap : public std::map<VarImpBase*,int> {};
73 
74  /*
75  * The createSetSym function is an almost exact copy of
76  * createIntSym/createBoolSym.
77  */
79  VariableMap variableMap) {
80  VariableSymmetryObject* varref =
81  dynamic_cast<VariableSymmetryObject*>(s.ref);
82  ValueSymmetryObject* valref =
83  dynamic_cast<ValueSymmetryObject*>(s.ref);
84  VariableSequenceSymmetryObject* varseqref =
85  dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
86  ValueSequenceSymmetryObject* valseqref =
87  dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
88  if (varref) {
89  int n = varref->nxs;
90  int* indices = home.alloc<int>(n);
91  for (int i = 0 ; i < n ; i++) {
92  VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
93  if (index == variableMap.end())
94  throw
95  Int::LDSBUnbranchedVariable("VariableSymmetryObject::createSet");
96  indices[i] = index->second;
97  }
98  return new (home) VariableSymmetryImp<SetView>(home, indices, n);
99  }
100  if (valref) {
101  int n = valref->values.size();
102  int *vs = home.alloc<int>(n);
103  int i = 0;
104  for (IntSetValues v(valref->values) ; v() ; ++v) {
105  vs[i] = v.val();
106  i++;
107  }
108  return new (home) ValueSymmetryImp<SetView>(home, vs, n);
109  }
110  if (varseqref) {
111  int n = varseqref->nxs;
112  int* indices = home.alloc<int>(n);
113  for (int i = 0 ; i < n ; i++) {
114  VariableMap::const_iterator index =
115  variableMap.find(varseqref->xs[i]);
116  if (index == variableMap.end())
117  throw
118  Int::LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createSet");
119  indices[i] = index->second;
120  }
121  return new (home) VariableSequenceSymmetryImp<SetView>(home, indices, n,
122  varseqref->seq_size);
123  }
124  if (valseqref) {
125  unsigned int n = valseqref->values.size();
126  int *vs = home.alloc<int>(n);
127  for (unsigned int i = 0 ; i < n ; i++)
128  vs[i] = valseqref->values[i];
129  return new (home) ValueSequenceSymmetryImp<SetView>(home, vs, n,
130  valseqref->seq_size);
131  }
132  GECODE_NEVER;
133  return NULL;
134  }
135 }}}
136 
137 namespace Gecode {
138 
139  using namespace Set::LDSB;
140 
141  BrancherHandle
142  branch(Home home, const SetVarArgs& x,
143  SetVarBranch vars, SetValBranch vals,
144  const Symmetries& syms,
145  SetBranchFilter bf) {
146  using namespace Set;
147  if (home.failed()) return BrancherHandle();
148  ViewArray<SetView> xv(home,x);
149  ViewSel<SetView>* vs[1] = {
150  Branch::viewsel(home,vars)
151  };
152 
153  // Construct mapping from each variable in the array to its index
154  // in the array.
155  VariableMap variableMap;
156  for (int i = 0 ; i < x.size() ; i++)
157  variableMap[x[i].varimp()] = i;
158 
159  // Convert the modelling-level Symmetries object into an array of
160  // SymmetryImp objects.
161  int n = syms.size();
162  SymmetryImp<SetView>** array =
163  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
164  for (int i = 0 ; i < n ; i++) {
165  array[i] = createSetSym(home, syms[i], variableMap);
166  }
167 
169  (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf);
170  }
171 
172  BrancherHandle
173  branch(Home home, const SetVarArgs& x,
175  const Symmetries& syms, SetBranchFilter bf) {
176  using namespace Set;
177  if (home.failed()) return BrancherHandle();
178  vars.a.expand(home,x);
179  if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
180  (vars.a.select() == SetVarBranch::SEL_RND))
181  vars.b = SET_VAR_NONE();
182  vars.b.expand(home,x);
183  if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
184  (vars.b.select() == SetVarBranch::SEL_RND))
185  vars.c = SET_VAR_NONE();
186  vars.c.expand(home,x);
187  if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
188  (vars.c.select() == SetVarBranch::SEL_RND))
189  vars.d = SET_VAR_NONE();
190  vars.d.expand(home,x);
191  if (vars.b.select() == SetVarBranch::SEL_NONE) {
192  return branch(home,x,vars.a,vals,syms,bf);
193  } else {
194  // Construct mapping from each variable in the array to its index
195  // in the array.
196  VariableMap variableMap;
197  for (int i = 0 ; i < x.size() ; i++)
198  variableMap[x[i].varimp()] = i;
199 
200  // Convert the modelling-level Symmetries object into an array of
201  // SymmetryImp objects.
202  int n = syms.size();
203  SymmetryImp<SetView>** array =
204  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
205  for (int i = 0 ; i < n ; i++) {
206  array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
207  }
208 
209  ViewArray<SetView> xv(home,x);
211  if (vars.c.select() == SetVarBranch::SEL_NONE) {
212  ViewSel<SetView>* vs[2] = {
213  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
214  };
215  return
216  LDSBSetBrancher<SetView,2,int,2>::post(home,xv,vs,vsc,array,n,bf);
217  } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
218  ViewSel<SetView>* vs[3] = {
219  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
220  Branch::viewsel(home,vars.c)
221  };
222  return
223  LDSBSetBrancher<SetView,3,int,2>::post(home,xv,vs,vsc,array,n,bf);
224  } else {
225  ViewSel<SetView>* vs[4] = {
226  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
227  Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
228  };
229  return
230  LDSBSetBrancher<SetView,4,int,2>::post(home,xv,vs,vsc,array,n,bf);
231  }
232  }
233  }
234 
235 }
236 
237 // STATISTICS: set-branch