Generated on for Gecode by doxygen 1.18.0
open.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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#ifndef GECODE_INT_BRANCH_OPEN_HPP
35#define GECODE_INT_BRANCH_OPEN_HPP
36
37#include <gecode/int/branch.hh>
38
39namespace Gecode { namespace Int { namespace Branch {
40
42 template<class View, class Filter, int n>
43 class OpenListBrancher : public Brancher {
44 protected:
45 typedef typename View::VarType Var;
50 Filter filter;
55 mutable int start;
56
58 ViewSel<View>* vs0[n],
60 bool values_min0,
61 bool select_first0,
63 : Brancher(home), list(list0), vsc(vsc0),
64 filter(bf), printer(vvp), values_min(values_min0),
65 select_first(select_first0), start(0) {
66 for (int i=0; i<n; i++)
67 vs[i] = vs0[i];
68 home.notice(*this,AP_DISPOSE,true);
69 }
70
72 : Brancher(home,b), vsc(nullptr),
75 list.update(home,b.list);
76 int copied = 0;
77 try {
78 if (b.vsc)
79 vsc = b.vsc->copy(home);
80 for (; copied<n; copied++)
81 vs[copied] = b.vs[copied]->copy(home);
82 } catch (...) {
83 for (int i=0; i<copied; i++)
84 vs[i]->dispose(home);
85 if (vsc)
86 vsc->dispose(home);
87 throw;
88 }
89 }
90
92 int
93 position(Space& home) {
94 if (select_first)
95 return start;
96 Region r;
98 for (int i=0; i<x.size(); i++)
99 x[i] = list[i];
100 if (n == 1)
101 return filter ? vs[0]->select(home,x,start,filter)
102 : vs[0]->select(home,x,start);
103 int* ties = r.alloc<int>(x.size()-start);
104 int n_ties;
105 if (filter)
106 vs[0]->ties(home,x,start,ties,n_ties,filter);
107 else
108 vs[0]->ties(home,x,start,ties,n_ties);
109 for (int i=1; (i<n-1) && (n_ties>1); i++)
110 vs[i]->brk(home,x,ties,n_ties);
111 return (n_ties > 1) ? vs[n-1]->select(home,x,ties,n_ties) : ties[0];
112 }
113
114 static const Choice*
115 value_choice(const Brancher& b, int i, IntView x) {
116 return new PosValuesChoice(b,Pos(i),x);
117 }
118
119 static const Choice*
122 return nullptr;
123 }
124
125 int
126 value(const Choice& c, unsigned int a) const {
127 const PosValuesChoice& pvc =
128 static_cast<const PosValuesChoice&>(c);
129 return pvc.val(values_min ? a : pvc.alternatives()-1-a);
130 }
131
132 public:
133 virtual bool
134 status(const Space& home) const {
135 for (int i=start; i<list.known_length(); i++)
136 if (!list[i].assigned() && filter(home,list[i],i)) {
137 start = i;
138 return true;
139 }
140 return list.length().max() > list.known_length();
141 }
142
143 virtual const Choice*
144 choice(Space& home) {
145 for (int i=start; i<list.known_length(); i++)
146 if (!list[i].assigned() && filter(home,list[i],i)) {
147 start = i;
148 const int p = position(home);
149 View x(list[p]);
150 return vsc ? new PosValChoice<int>(*this,2,Pos(p),vsc->val(home,x,p))
151 : value_choice(*this,p,x);
152 }
153 // Position -1 marks a length choice: close here or require another item.
154 return new PosValChoice<int>(*this,2,Pos(-1),list.known_length());
155 }
156
157 virtual const Choice*
158 choice(const Space&, Archive& e) {
159 int p;
160 e >> p;
161 if ((p < 0) || vsc) {
162 int v;
163 e >> v;
164 return new PosValChoice<int>(*this,2,Pos(p),v);
165 }
166 unsigned int a;
167 e >> a;
168 return new PosValuesChoice(*this,a,Pos(p),e);
169 }
170
171 virtual ExecStatus
172 commit(Space& home, const Choice& c, unsigned int a) {
173 const int p = static_cast<const PosChoice&>(c).pos().pos;
174 if (p >= 0) {
175 // Recomputation can replay choices before propagation grows the prefix.
176 if (p >= list.known_length()) {
177 list.materialize(home,p+1);
178 if (home.failed())
179 return ES_FAILED;
180 }
181 View x(list[p]);
182 const ModEvent me = vsc
183 ? vsc->commit(home,a,x,p,static_cast<const PosValChoice<int>&>(c).val())
184 : x.eq(home,value(c,a));
185 return me_failed(me) ? ES_FAILED : ES_OK;
186 }
187 const int size = static_cast<const PosValChoice<int>&>(c).val();
188 if (a == 0)
189 return me_failed(list.length().eq(home,size))
190 ? ES_FAILED : ES_OK;
191 list.materialize(home,size+1);
192 return home.failed() ? ES_FAILED : ES_OK;
193 }
194
195 virtual NGL*
196 ngl(Space& home, const Choice& c, unsigned int a) const {
197 const int p = static_cast<const PosChoice&>(c).pos().pos;
198 if (p < 0)
199 return (a == 0) ? new (home) EqNGL<IntView>
200 (home,list.length(),
201 static_cast<const PosValChoice<int>&>(c).val()) : nullptr;
202 // No-good extraction can run in an ancestor with a shorter prefix.
203 if (p >= list.known_length())
204 return nullptr;
205 View x(list[p]);
206 return vsc
207 ? vsc->ngl(home,a,x,static_cast<const PosValChoice<int>&>(c).val())
208 : new (home) EqNGL<View>(home,x,value(c,a));
209 }
210
211 virtual void
212 print(const Space& home, const Choice& c, unsigned int a,
213 std::ostream& o) const {
214 const int p = static_cast<const PosChoice&>(c).pos().pos;
215 if (p < 0) {
216 o << "list length " << ((a == 0) ? "=" : ">") << " "
217 << static_cast<const PosValChoice<int>&>(c).val();
218 } else {
219 const int v = vsc ? static_cast<const PosValChoice<int>&>(c).val()
220 : value(c,a);
221 // Tracing can print replayed choices before commit grows the prefix.
222 if (p >= list.known_length()) {
223 o << "list[" << p << "] alternative " << a << " (value " << v << ")";
224 return;
225 }
226 View x(list[p]);
227 if (printer())
228 printer()(home,*this,a,Var(x),p,v,o);
229 else if (vsc)
230 vsc->print(home,a,x,p,v,o);
231 else
232 o << "list[" << p << "] = " << v;
233 }
234 }
235
236 virtual Actor*
237 copy(Space& home) {
238 return new (home) OpenListBrancher(home,*this);
239 }
240
241 virtual size_t
242 dispose(Space& home) {
243 home.ignore(*this,AP_DISPOSE,true);
244 for (int i=0; i<n; i++)
245 vs[i]->dispose(home);
246 if (vsc)
247 vsc->dispose(home);
248 filter.dispose(home);
250 list.~OpenViewList();
251 (void) Brancher::dispose(home);
252 return sizeof(*this);
253 }
254
255 template<class VarBranch>
256 static void
259 bool values_min,
261 ViewSel<View>* vs[n];
262 for (int i=0; i<n; i++)
263 vs[i] = viewsel(home,vars[i]);
264 (void) new (home)
266 vars[0].select() == VarBranch::SEL_NONE,bf,vvp);
267 }
268 };
269
271 inline void
273 switch (vars.select()) {
278 if (open)
279 throw UnknownBranching("Int::branch");
280 break;
281 default: break;
282 }
283 }
284
285 inline void
287 switch (vars.select()) {
290 if (open)
291 throw UnknownBranching("Int::branch");
292 break;
293 default: break;
294 }
295 }
296
299 open_valselcommit(Home home, IntValBranch vals, bool& values_min) {
300 values_min = vals.select() != IntValBranch::SEL_VALUES_MAX;
301 return ((vals.select() == IntValBranch::SEL_VALUES_MIN) ||
303 ? nullptr : valselcommit(home,vals);
304 }
305
308 open_valselcommit(Home home, BoolValBranch vals, bool& values_min) {
309 values_min = true;
310 return valselcommit(home,vals);
311 }
312
314 template<class View, int n, class VarBranch>
315 void
318 bool values_min,
321 if (bf)
323 (home,list,vars,vsc,values_min,bf,vvp);
324 else
326 (home,list,vars,vsc,values_min,bf,vvp);
327 }
328
329 template<class View, class VarBranch, class ValBranch>
330 void
335 VarBranch selectors[4] = {vars.a,vars.b,vars.c,vars.d};
336 int n = 1;
337 while ((n < 4) && (selectors[n-1].select() != VarBranch::SEL_NONE) &&
338 (selectors[n-1].select() != VarBranch::SEL_RND) &&
339 (selectors[n].select() != VarBranch::SEL_NONE))
340 n++;
341 typedef typename View::VarType Var;
343 for (int i=0; i<x.size(); i++)
344 x[i] = list[i];
345 for (int i=0; i<n; i++) {
346 check_open_selector(selectors[i],list.length().max() > list.known_length());
347 selectors[i].expand(home,x);
348 }
349 bool values_min;
350 ValSelCommitBase<View,int>* vsc = open_valselcommit(home,vals,values_min);
351 switch (n) {
352 case 1:
354 (home,list,selectors,vsc,values_min,bf,vvp);
355 break;
356 case 2:
358 (home,list,selectors,vsc,values_min,bf,vvp);
359 break;
360 case 3:
362 (home,list,selectors,vsc,values_min,bf,vvp);
363 break;
364 case 4:
366 (home,list,selectors,vsc,values_min,bf,vvp);
367 break;
368 }
369 }
370
371}}}
372
373#endif
374
375// STATISTICS: int-branch
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Archive representation
Definition archive.hpp:42
Traits of arrays in Gecode.
Definition array.hpp:94
Which values to select for branching first.
Definition int.hh:6004
Which Boolean variable to select for branching.
Definition int.hh:5771
Select select(void) const
Return selection strategy.
Definition var.hpp:340
@ SEL_CHB_MIN
With lowest CHB.
Definition int.hh:5785
@ SEL_ACTION_MIN
With lowest action.
Definition int.hh:5783
@ SEL_ACTION_MAX
With highest action.
Definition int.hh:5784
@ SEL_CHB_MAX
With highest CHB.
Definition int.hh:5786
friend class Space
Definition core.hpp:1462
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3822
friend class Choice
Definition core.hpp:1463
Choice for performing commit
Definition core.hpp:1430
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3999
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
Which values to select for branching first.
Definition int.hh:5969
@ SEL_VALUES_MIN
Select all values starting from smallest.
Definition int.hh:5982
@ SEL_VALUES_MAX
Select all values starting from largest.
Definition int.hh:5983
Select select(void) const
Return selection strategy.
Definition val.hpp:49
Which integer variable to select for branching.
Definition int.hh:5685
@ SEL_CHB_MAX
With highest CHB Q-score.
Definition int.hh:5700
@ SEL_ACTION_SIZE_MAX
With largest action divided by domain size.
Definition int.hh:5712
@ SEL_CHB_SIZE_MAX
With largest CHB Q-score divided by domain size.
Definition int.hh:5714
@ SEL_ACTION_MIN
With lowest action.
Definition int.hh:5697
@ SEL_ACTION_MAX
With highest action.
Definition int.hh:5698
@ SEL_CHB_MIN
With lowest CHB Q-score.
Definition int.hh:5699
@ SEL_CHB_SIZE_MIN
With smallest CHB Q-score divided by domain size.
Definition int.hh:5713
@ SEL_ACTION_SIZE_MIN
With smallest action divided by domain size.
Definition int.hh:5711
Select select(void) const
Return selection strategy.
Definition var.hpp:69
Boolean view for Boolean variables.
Definition view.hpp:1378
No-good literal for equality.
Definition branch.hh:411
Standard view/value selectors over the materialized prefix.
Definition open.hpp:43
int value(const Choice &c, unsigned int a) const
Definition open.hpp:126
static const Choice * value_choice(const Brancher &, int, BoolView)
Definition open.hpp:120
OpenListBrancher(Space &home, OpenListBrancher &b)
Definition open.hpp:71
virtual void print(const Space &home, const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition open.hpp:212
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:242
virtual const Choice * choice(const Space &, Archive &e)
Return choice from e.
Definition open.hpp:158
static const Choice * value_choice(const Brancher &b, int i, IntView x)
Definition open.hpp:115
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
Definition open.hpp:196
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int a)
Commit for choice c and alternative a.
Definition open.hpp:172
SharedData< VarValPrint< Var, int > > printer
Definition open.hpp:51
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition open.hpp:134
ValSelCommitBase< View, int > * vsc
Binary value selector, or null for one alternative per domain value.
Definition open.hpp:49
OpenViewList< View > list
Definition open.hpp:46
int position(Space &home)
Select from a temporary array, keeping positions stable across growth.
Definition open.hpp:93
OpenListBrancher(Home home, OpenViewList< View > list0, ViewSel< View > *vs0[n], ValSelCommitBase< View, int > *vsc0, bool values_min0, bool select_first0, BranchFilter< Var > bf, VarValPrint< Var, int > vvp)
Definition open.hpp:57
bool values_min
Whether enumerated domain values are tried in increasing order.
Definition open.hpp:53
virtual const Choice * choice(Space &home)
Return choice.
Definition open.hpp:144
static void post(Home home, OpenViewList< View > list, VarBranch vars[n], ValSelCommitBase< View, int > *vsc, bool values_min, BranchFilter< Var > bf, VarValPrint< Var, int > vvp)
Definition open.hpp:257
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:237
Choice storing position and values for integer views
int val(unsigned int a) const
Return value to branch with for alternative a.
PosValuesChoice(const Brancher &b, const Pos &p, IntView x)
Initialize choice for brancher b, position p, and view x.
Integer view for integer variables.
Definition view.hpp:129
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
UnknownBranching(const char *l)
Initialize with location l.
No-good literal recorded during search.
Definition core.hpp:1358
View interface to a space-local list with an open length.
Definition int.hh:1044
void materialize(Space &home, int n)
Require and construct at least the first n positions.
Int::IntView length(void) const
Return the eventual-length view.
int known_length(void) const
Return the number of constructed positions.
void update(Space &home, OpenViewList< View > &s)
Update during cloning.
Choices storing position
Definition view.hpp:55
Choice storing position and value
Definition view-val.hpp:46
const Val & val(void) const
Definition view-val.hpp:165
PosValChoice(const Brancher &b, unsigned int a, const Pos &p, const Val &n)
Initialize choice for brancher b, number of alternatives a, position p, and value n.
Definition view-val.hpp:159
Pos(int p)
Create position information.
Definition view.hpp:114
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Class for sharing data between spaces.
~SharedData(void)
Destructors.
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
VarBranch a
Branching criteria to try in order.
Definition tiebreak.hpp:41
Value branching information.
Definition val.hpp:41
Base class for value selection and commit.
virtual void dispose(Space &home)=0
Delete value selection.
virtual NGL * ngl(Space &home, unsigned int a, View x, Val n) const =0
Create no-good literal for choice c and alternative a.
virtual Val val(const Space &home, View x, int i)=0
Return value of view x at position i.
virtual ModEvent commit(Space &home, unsigned int a, View x, int i, Val n)=0
Commit view x at position i to value n for alternative a.
virtual void print(const Space &home, unsigned int a, View x, int i, const Val &n, std::ostream &o) const =0
Print on o branch for alternative a, view x at position i, and value n.
Variable branching information.
Definition var.hpp:55
Base class for variables.
Definition var.hpp:40
View arrays.
Definition array.hpp:255
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1165
Abstract class for view selection.
Definition view-sel.hpp:44
virtual void ties(Space &home, ViewArray< View > &x, int s, int *ties, int &n)=0
Select ties from x starting from s.
virtual int select(Space &home, ViewArray< View > &x, int s)=0
Select a view from x starting from s and return its position.
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
Integer branchers.
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
ValSelCommitBase< IntView, int > * open_valselcommit(Home home, IntValBranch vals, bool &values_min)
Select binary branching or enumeration of integer domain values.
Definition open.hpp:299
void post_open_brancher(Home home, OpenViewList< View > list, VarBranch vars[n], ValSelCommitBase< View, int > *vsc, bool values_min, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, int > vvp)
Choose the native filtered or unfiltered brancher policy.
Definition open.hpp:316
void check_open_selector(IntVarBranch vars, bool open)
Reject fixed-position statistics while new variables can still appear.
Definition open.hpp:272
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Finite domain integers.
Definition lastval.hh:52
Gecode toplevel namespace
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition filter.hpp:40
std::function< void(const Space &home, const Brancher &b, unsigned int a, Var x, int i, const Val &m, std::ostream &o)> VarValPrint
Function type for printing variable and value selection.
Definition print.hpp:40
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
int ModEvent
Type for modification events.
Definition core.hpp:67
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56