main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:04 for Gecode by
doxygen
1.8.4
gecode
int
ldsb.hh
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-05-08 13:30:48 +0200 (Wed, 08 May 2013) $ by $Author: schulte $
11
* $Revision: 13622 $
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
#ifndef __GECODE_INT_LDSB_HH__
39
#define __GECODE_INT_LDSB_HH__
40
41
#include <
gecode/int.hh
>
42
47
namespace
Gecode {
namespace
Int {
namespace
LDSB {
48
50
class
Literal
{
51
public
:
53
Literal
(
void
);
55
Literal
(
int
_var,
int
_val);
56
59
int
_variable
;
63
int
_value
;
64
67
bool
operator <
(
const
Literal
&rhs)
const
;
68
};
69
81
GECODE_INT_EXPORT
82
std::pair<int,int>
83
findVar
(
int
*indices,
unsigned
int
n_values,
unsigned
int
seq_size,
int
index);
84
}}}
85
86
namespace
Gecode {
88
template
<>
89
class
ArrayTraits
<
ArgArray
<
VarImpBase
*> > {
90
public
:
91
typedef
ArgArray<VarImpBase*>
StorageType
;
92
typedef
VarImpBase
*
ValueType
;
93
typedef
ArgArray<VarImpBase*>
ArgsType
;
94
};
95
97
typedef
ArgArray<Int::LDSB::Literal>
LiteralArgs
;
99
template
<>
100
class
ArrayTraits
<
LiteralArgs
> {
101
public
:
102
typedef
LiteralArgs
StorageType
;
103
typedef
Int::LDSB::Literal
ValueType
;
104
typedef
LiteralArgs
ArgsType
;
105
};
106
}
107
108
namespace
Gecode {
namespace
Int {
namespace
LDSB {
110
class
GECODE_INT_EXPORT
SymmetryObject
{
111
public
:
113
int
nrefs
;
115
SymmetryObject
(
void
);
117
virtual
~
SymmetryObject
(
void
);
118
};
120
class
GECODE_INT_EXPORT
VariableSymmetryObject
:
public
SymmetryObject
{
121
public
:
123
VarImpBase
**
xs
;
125
int
nxs
;
127
VariableSymmetryObject
(
ArgArray<VarImpBase*>
vars);
129
~
VariableSymmetryObject
(
void
);
130
};
132
class
GECODE_INT_EXPORT
ValueSymmetryObject
:
public
SymmetryObject
{
133
public
:
135
IntSet
values
;
137
ValueSymmetryObject
(
IntSet
vs);
138
};
140
class
GECODE_INT_EXPORT
VariableSequenceSymmetryObject
:
public
SymmetryObject
{
141
public
:
143
VarImpBase
**
xs
;
145
int
nxs
;
147
int
seq_size
;
149
VariableSequenceSymmetryObject
(
ArgArray<VarImpBase*>
vars,
int
ss);
151
~
VariableSequenceSymmetryObject
();
152
};
154
class
GECODE_INT_EXPORT
ValueSequenceSymmetryObject
:
public
SymmetryObject
{
155
public
:
157
IntArgs
values
;
159
int
seq_size
;
161
ValueSequenceSymmetryObject
(
IntArgs
vs,
int
ss);
162
};
163
165
template
<
class
View>
166
class
SymmetryImp
{
167
public
:
169
virtual
ArgArray<Literal>
symmetric
(
Literal
,
const
ViewArray<View>
&)
const
= 0;
171
virtual
void
update
(
Literal
) = 0;
173
virtual
SymmetryImp<View>
*
copy
(
Space
& home,
bool
share)
const
= 0;
175
virtual
size_t
dispose
(
Space
& home) = 0;
177
static
void
*
operator
new
(
size_t
s,
Space
& home);
179
static
void
operator
delete
(
void
*,
Space
&);
181
static
void
operator
delete
(
void
*);
182
};
184
template
<
class
View>
185
class
VariableSymmetryImp
:
public
SymmetryImp
<View> {
186
protected
:
188
Support::BitSetOffset<Space>
indices
;
189
public
:
191
VariableSymmetryImp<View>
(
Space
& home,
int
* vs,
unsigned
int
n
);
193
VariableSymmetryImp<View>
(
Space
& home,
const
VariableSymmetryImp<View>
& other);
195
virtual
size_t
dispose
(
Space
& home);
197
void
update
(
Literal
);
199
virtual
ArgArray<Literal>
symmetric
(
Literal
,
const
ViewArray<View>
&)
const
;
201
SymmetryImp<View>
*
copy
(
Space
& home,
bool
share)
const
;
202
};
204
template
<
class
View>
205
class
ValueSymmetryImp
:
public
SymmetryImp
<View>
206
{
207
public
:
209
Support::BitSetOffset<Space>
values
;
211
ValueSymmetryImp<View>
(
Space
& home,
int
* vs,
unsigned
int
n
);
213
ValueSymmetryImp<View>
(
Space
& home,
const
ValueSymmetryImp<View>
& other);
215
virtual
size_t
dispose
(
Space
& home);
217
void
update
(
Literal
);
219
virtual
ArgArray<Literal>
symmetric
(
Literal
,
const
ViewArray<View>
&)
const
;
221
SymmetryImp<View>
*
copy
(
Space
& home,
bool
share)
const
;
222
};
224
template
<
class
View>
225
class
VariableSequenceSymmetryImp
:
public
SymmetryImp
<View>
226
{
227
protected
:
229
unsigned
int
*
indices
;
231
unsigned
int
n_indices
;
233
unsigned
int
seq_size
;
235
unsigned
int
n_seqs
;
236
238
// e.g. lookup[2] == 10 indicates that the variable with index 2
239
// occurs at position 10 in the "indices" array.
240
// If a variable occurs more than once, only the first occurrence
241
// is recorded.
242
// A value of -1 indicates that the variable does not occur in
243
// "indices".
244
int
*
lookup
;
246
unsigned
int
lookup_size
;
247
250
int
getVal
(
unsigned
int
sequence
,
unsigned
int
position
)
const
;
251
public
:
253
VariableSequenceSymmetryImp<View>
(
Space
& home,
int
*_indices,
unsigned
int
n
,
unsigned
int
seqsize);
255
VariableSequenceSymmetryImp<View>
(
Space
& home,
bool
share,
const
VariableSequenceSymmetryImp<View>
& s);
257
virtual
size_t
dispose
(
Space
& home);
259
void
update
(
Literal
);
261
virtual
ArgArray<Literal>
symmetric
(
Literal
,
const
ViewArray<View>
&)
const
;
263
SymmetryImp<View>
*
copy
(
Space
& home,
bool
share)
const
;
264
};
266
template
<
class
View>
267
class
ValueSequenceSymmetryImp
:
public
SymmetryImp
<View>
268
{
269
protected
:
271
int
*
values
;
273
unsigned
int
n_values
;
275
unsigned
int
seq_size
;
277
unsigned
int
n_seqs
;
279
Support::BitSet<Space>
dead_sequences
;
282
int
getVal
(
unsigned
int
sequence
,
unsigned
int
position
)
const
;
283
private
:
284
ValueSequenceSymmetryImp<View>
(
const
ValueSequenceSymmetryImp<View>
&);
285
public
:
287
ValueSequenceSymmetryImp<View>
(
Space
& home,
int
* _values,
unsigned
int
n
,
unsigned
int
seqsize);
289
ValueSequenceSymmetryImp<View>
(
Space
& home,
const
ValueSequenceSymmetryImp<View>
& vss);
291
virtual
size_t
dispose
(
Space
& home);
293
void
update
(
Literal
);
295
virtual
ArgArray<Literal>
symmetric
(
Literal
,
const
ViewArray<View>
&)
const
;
297
SymmetryImp<View>
*
copy
(
Space
& home,
bool
share)
const
;
298
};
299
302
template
<
class
Val>
303
class
GECODE_VTABLE_EXPORT
LDSBChoice
:
public
PosValChoice
<Val> {
304
private
:
306
const
Literal
*
const
_literals;
308
const
int
_nliterals;
309
public
:
312
LDSBChoice
(
const
Brancher
&
b
,
unsigned
int
a
,
const
Pos
&
p
,
const
Val&
n
,
313
const
Literal
* literals,
int
nliterals);
315
~
LDSBChoice
(
void
);
317
const
Literal
* literals(
void
)
const
;
319
int
nliterals(
void
)
const
;
321
virtual
size_t
size
(
void
)
const
;
323
virtual
void
archive(
Archive
& e)
const
;
324
};
325
334
template
<
class
View,
int
n,
class
Val,
unsigned
int
a>
335
class
LDSBBrancher
:
public
ViewValBrancher
<View,n,Val,a> {
336
typedef
typename
ViewBrancher<View,n>::BranchFilter
BranchFilter;
337
public
:
339
SymmetryImp<View>
**
_syms
;
341
int
_nsyms
;
342
// Position of variable that last choice was created for
343
int
_prevPos
;
344
protected
:
346
typedef
void (*
VarValPrint
)(
const
Space
& home,
const
BrancherHandle
&
bh
,
347
unsigned
int
b
,
348
typename
View::VarType
x
,
int
i
,
349
const
Val& m,
350
std::ostream& o);
352
LDSBBrancher
(
Space
& home,
bool
share,
LDSBBrancher
&
b
);
354
LDSBBrancher
(
Home
home,
355
ViewArray<View>
&
x
,
356
ViewSel<View>
*
vs
[
n
],
357
ValSelCommitBase<View,Val>
*
vsc
,
358
SymmetryImp<View>
** syms,
int
nsyms,
359
BranchFilter
bf
,
360
VarValPrint
vvp
);
361
public
:
363
virtual
const
Choice
*
choice
(
Space
& home);
365
virtual
const
Choice
*
choice
(
const
Space
& home,
Archive
& e);
367
virtual
ExecStatus
commit
(
Space
& home,
const
Choice
&
c
,
unsigned
int
b
);
369
virtual
Actor
*
copy
(
Space
& home,
bool
share);
371
virtual
size_t
dispose
(
Space
& home);
373
static
BrancherHandle
post
(
Home
home,
374
ViewArray<View>
&
x
,
375
ViewSel<View>
*
vs
[
n
],
376
ValSelCommitBase<View,Val>
*
vsc
,
377
SymmetryImp<View>
** syms,
378
int
nsyms,
379
BranchFilter
bf
,
380
VarValPrint
vvp
);
381
};
382
384
template
<
class
View>
385
ModEvent
prune
(
Space
& home, View
x
,
int
v
);
386
387
}}}
388
389
#include <
gecode/int/ldsb/brancher.hpp
>
390
#include <
gecode/int/ldsb/sym-imp.hpp
>
391
392
#endif
393
394
// STATISTICS: int-branch
395