main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 24 2020 14:04:04 for Gecode by
doxygen
1.8.17
gecode
set
ldsb
sym-imp.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
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
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
#include <
gecode/set/ldsb.hh
>
35
36
namespace
Gecode
{
namespace
Set {
namespace
LDSB {
37
// XXX: implementation of equalValues could be improved?
38
40
bool
41
equalLUB
(
const
Set::SetView
&
x
,
const
Set::SetView
&
y
) {
42
unsigned
int
n
=
x
.
lubSize
();
43
if
(
n
!=
y
.
lubSize
())
return
false
;
44
for
(
unsigned
int
i
= 0 ;
i
<
n
;
i
++)
45
if
(
x
.lubMinN(
i
) !=
y
.lubMinN(
i
))
46
return
false
;
47
return
true
;
48
}
49
}}}
50
51
// Note carefully that this is in the Gecode::Int::LDSB namespace, not
52
// Gecode::Set::LDSB.
53
namespace
Gecode
{
namespace
Int {
namespace
LDSB {
54
template
<>
55
ArgArray<Literal>
56
VariableSymmetryImp<Set::SetView>
57
::symmetric
(
Literal
l
,
const
ViewArray<Set::SetView>
&
x
)
const
{
58
(void)
x
;
59
if
(indices.valid(
l
._variable) && indices.get(
l
._variable)) {
60
int
n
= 0;
61
for
(
Iter::Values::BitSetOffset
<
Support::BitSetOffset<Space>
>
i
(indices) ;
i
() ; ++
i
)
62
n
++;
63
ArgArray<Literal>
lits(
n
);
64
int
j = 0;
65
for
(
Iter::Values::BitSetOffset
<
Support::BitSetOffset<Space>
>
i
(indices) ;
i
() ; ++
i
) {
66
lits[j++] =
Literal
(
i
.val(),
l
._value);
67
}
68
return
lits;
69
}
else
{
70
return
ArgArray<Literal>
(0);
71
}
72
}
73
74
template
<>
75
ArgArray<Literal>
76
ValueSymmetryImp<Set::SetView>
77
::symmetric
(
Literal
l
,
const
ViewArray<Set::SetView>
&
x
)
const
{
78
(void)
x
;
79
if
(
values
.valid(
l
._value) &&
values
.get(
l
._value)) {
80
int
n
= 0;
81
for
(
Iter::Values::BitSetOffset
<
Support::BitSetOffset<Space>
>
i
(
values
) ;
i
() ; ++
i
)
82
n
++;
83
ArgArray<Literal>
lits(
n
);
84
int
j = 0;
85
for
(
Iter::Values::BitSetOffset
<
Support::BitSetOffset<Space>
>
i
(
values
) ;
i
() ; ++
i
) {
86
lits[j++] =
Literal
(
l
._variable,
i
.val());
87
}
88
return
lits;
89
}
else
{
90
return
ArgArray<Literal>
(0);
91
}
92
}
93
94
template
<>
95
ArgArray<Literal>
96
VariableSequenceSymmetryImp<Set::SetView>
97
::symmetric
(
Literal
l
,
const
ViewArray<Set::SetView>
&
x
)
const
{
98
Region
region;
99
Support::DynamicStack<Literal,Region>
s(region);
100
if
(
l
._variable < (
int
)lookup_size) {
101
int
posIt = lookup[
l
._variable];
102
if
(posIt == -1) {
103
return
dynamicStackToArgArray
(s);
104
}
105
unsigned
int
seqNum = posIt / seq_size;
106
unsigned
int
seqPos = posIt % seq_size;
107
for
(
unsigned
int
seq = 0 ; seq < n_seqs ; seq++) {
108
if
(seq == seqNum) {
109
continue
;
110
}
111
if
(
x
[getVal(seq, seqPos)].
assigned
()) {
112
continue
;
113
}
114
bool
active =
true
;
115
const
unsigned
int
*firstSeq = &indices[seqNum*seq_size];
116
const
unsigned
int
*secondSeq = &indices[seq*seq_size];
117
for
(
unsigned
int
i
= 0 ;
i
< seq_size ;
i
++) {
118
const
Set::SetView
& xv =
x
[firstSeq[
i
]];
119
const
Set::SetView
& yv =
x
[secondSeq[
i
]];
120
if
((!xv.
assigned
() && !yv.
assigned
())
121
|| (xv.
assigned
() && yv.
assigned
() &&
Set::LDSB::equalLUB
(xv, yv))) {
122
continue
;
123
}
else
{
124
active =
false
;
125
break
;
126
}
127
}
128
129
if
(active) {
130
s.
push
(
Literal
(secondSeq[seqPos],
l
._value));
131
}
132
}
133
}
134
return
dynamicStackToArgArray
(s);
135
}
136
137
template
<>
138
ArgArray<Literal>
139
ValueSequenceSymmetryImp<Set::SetView>
140
::symmetric
(
Literal
l
,
const
ViewArray<Set::SetView>
&
x
)
const
{
141
(void)
x
;
142
Region
region;
143
Support::DynamicStack<Literal,Region>
s(region);
144
std::pair<int,int> location =
findVar
(
values
, n_values, seq_size,
l
._value);
145
if
(location.first == -1)
return
dynamicStackToArgArray
(s);
146
unsigned
int
seqNum = location.first;
147
unsigned
int
seqPos = location.second;
148
for
(
unsigned
int
seq = 0 ; seq < n_seqs ; seq++) {
149
if
(seq == seqNum)
continue
;
150
if
(dead_sequences.get(seq))
continue
;
151
s.
push
(
Literal
(
l
._variable, getVal(seq,seqPos)));
152
}
153
return
dynamicStackToArgArray
(s);
154
}
155
}}}
156
157
// STATISTICS: set-branch
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
Definition:
aliases.hpp:143
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Set::LDSB::equalLUB
bool equalLUB(const Set::SetView &x, const Set::SetView &y)
Do two set variables have equal least-upper-bounds?
Definition:
sym-imp.cpp:41
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:767
Gecode::VarImpView::assigned
bool assigned(void) const
Test whether view is assigned.
Definition:
view.hpp:516
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:43
Gecode::Int::LDSB::ValueSymmetryImp::symmetric
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Gecode::Int::LDSB::VariableSequenceSymmetryImp::symmetric
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition:
sym-imp.hpp:226
Gecode
Gecode toplevel namespace
Gecode::Support::DynamicStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
dynamic-stack.hpp:140
Gecode::Int::LDSB::ValueSequenceSymmetryImp::symmetric
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Gecode::SetVar::lubSize
unsigned int lubSize(void) const
Return number of elements in the least upper bound.
Definition:
set.hpp:66
Gecode::ArgArray
Argument array for non-primitive types.
Definition:
array.hpp:656
ldsb.hh
Gecode::Iter::Values::BitSetOffset
Value iterator for values in an offset bitset.
Definition:
values-bitsetoffset.hpp:45
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::Int::LDSB::Literal
A Literal is a pair of variable index and value.
Definition:
ldsb.hh:46
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Set::SetView
Set view for set variables
Definition:
view.hpp:56
Gecode::Int::LDSB::VariableSymmetryImp::symmetric
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Gecode::Support::DynamicStack
Stack with arbitrary number of elements.
Definition:
dynamic-stack.hpp:42
Gecode::Int::LDSB::findVar
std::pair< int, int > findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index)
Find the location of an integer in a collection of sequences.
Definition:
ldsb.cpp:42
Gecode::ViewArray
View arrays.
Definition:
array.hpp:253
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Support::BitSetOffset
Bitsets with index offset.
Definition:
bitset-offset.hpp:51
Gecode::Int::LDSB::dynamicStackToArgArray
ArgArray< T > dynamicStackToArgArray(const Support::DynamicStack< T, A > &s)
Convert a DynamicStack<T,A> into an ArgArray<T>
Definition:
sym-imp.hpp:39