main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 13 2014 04:39:32 for Gecode by
doxygen
1.8.1.2
gecode
int
nvalues.hh
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2011
8
*
9
* Last modified:
10
* $Date: 2011-09-08 00:15:16 +1000 (Thu, 08 Sep 2011) $ by $Author: schulte $
11
* $Revision: 12394 $
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_NVALUES_HH__
39
#define __GECODE_INT_NVALUES_HH__
40
41
#include <
gecode/int.hh
>
42
#include <
gecode/int/val-set.hh
>
43
49
namespace
Gecode {
namespace
Int {
namespace
NValues {
50
52
enum
RangeEventType
{
54
RET_FST
= 0,
56
RET_LST
= 1,
58
RET_END
= 2
59
};
60
62
class
RangeEvent
{
63
public
:
65
RangeEventType
ret
;
67
int
val
;
69
int
view
;
71
bool
operator <
(
RangeEvent
re)
const
;
72
};
73
75
class
SymBitMatrix
:
public
Support::BitSet
<Region> {
76
protected
:
78
int
n
;
80
int
pos
(
int
x,
int
y)
const
;
81
public
:
83
SymBitMatrix
(
Region
&
r
,
int
n
);
85
bool
get
(
int
x,
int
y)
const
;
87
void
set
(
int
x,
int
y);
88
};
89
90
}}}
91
92
#include <
gecode/int/nvalues/range-event.hpp
>
93
#include <
gecode/int/nvalues/sym-bit-matrix.hpp
>
94
95
#include <
gecode/int/view-val-graph.hh
>
96
97
namespace
Gecode {
namespace
Int {
namespace
NValues {
98
100
class
Graph
:
public
ViewValGraph::Graph
<IntView> {
101
protected
:
103
int
n_matched
;
104
public
:
106
Graph
(
void
);
108
int
size
(
void
)
const
;
110
void
init
(
Space
& home,
const
ValSet
& vs,
const
ViewArray<IntView>
& x);
112
void
sync
(
Space
& home);
113
/*
114
* \brief Mark all edges used that can appear in some maximal matching
115
*
116
* Return true, if any edge can be in fact pruned.
117
*/
118
bool
mark
(
Space
& home);
120
ExecStatus
prune
(
Space
& home);
121
};
122
123
}}}
124
125
#include <
gecode/int/nvalues/graph.hpp
>
126
127
namespace
Gecode {
namespace
Int {
namespace
NValues {
128
135
template
<
class
VY>
136
class
IntBase
137
:
public
MixNaryOnePropagator
<IntView,PC_INT_DOM,VY,PC_INT_BND> {
138
protected
:
139
using
MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::x
;
140
using
MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::y
;
142
ValSet
vs
;
144
IntBase
(
Home
home,
ValSet
&
vs
,
ViewArray<IntView>
&
x
, VY
y
);
146
IntBase
(
Space
& home,
bool
share,
IntBase<VY>
& p);
148
void
add
(
Space
& home);
154
void
disjoint
(
Space
& home,
Region
&
r
,
int
*& dis,
int
& n_dis);
156
void
eliminate
(
Space
& home);
158
int
size
(
Space
& home)
const
;
160
ExecStatus
all_in_valset
(
Space
& home);
169
ExecStatus
prune_lower
(
Space
& home,
int
* dis,
int
n_dis);
176
ExecStatus
prune_upper
(
Space
& home,
Graph
& g);
177
public
:
179
virtual
PropCost
cost
(
const
Space
&,
const
ModEventDelta
&)
const
;
181
virtual
size_t
dispose
(
Space
& home);
182
};
183
190
template
<
class
VY>
191
class
EqInt
:
public
IntBase
<VY> {
192
protected
:
193
using
IntBase<VY>::x
;
194
using
IntBase<VY>::y
;
195
using
IntBase<VY>::vs
;
196
using
IntBase<VY>::add
;
197
using
IntBase<VY>::all_in_valset
;
198
using
IntBase<VY>::disjoint
;
199
using
IntBase<VY>::prune_lower
;
200
using
IntBase<VY>::prune_upper
;
202
Graph
g
;
204
EqInt
(
Home
home,
ValSet
&
vs
,
ViewArray<IntView>
&
x
, VY
y
);
206
EqInt
(
Space
& home,
bool
share,
EqInt<VY>
& p);
207
public
:
209
virtual
Propagator
*
copy
(
Space
& home,
bool
share);
211
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
213
static
ExecStatus
post
(
Home
home,
ViewArray<IntView>
&
x
, VY
y
);
215
virtual
size_t
dispose
(
Space
& home);
216
};
217
224
template
<
class
VY>
225
class
LqInt
:
public
IntBase
<VY> {
226
protected
:
227
using
IntBase<VY>::x
;
228
using
IntBase<VY>::y
;
229
using
IntBase<VY>::vs
;
230
using
IntBase<VY>::add
;
231
using
IntBase<VY>::all_in_valset
;
232
using
IntBase<VY>::disjoint
;
233
using
IntBase<VY>::prune_lower
;
234
using
IntBase<VY>::prune_upper
;
236
LqInt
(
Home
home,
ValSet
&
vs
,
ViewArray<IntView>
&
x
, VY
y
);
238
LqInt
(
Space
& home,
bool
share,
LqInt<VY>
& p);
239
public
:
241
virtual
Propagator
*
copy
(
Space
& home,
bool
share);
243
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
245
static
ExecStatus
post
(
Home
home,
ViewArray<IntView>
& x, VY y);
247
virtual
size_t
dispose
(
Space
& home);
248
};
249
256
template
<
class
VY>
257
class
GqInt
:
public
IntBase
<VY> {
258
protected
:
259
using
IntBase<VY>::x
;
260
using
IntBase<VY>::y
;
261
using
IntBase<VY>::vs
;
262
using
IntBase<VY>::add
;
263
using
IntBase<VY>::all_in_valset
;
264
using
IntBase<VY>::disjoint
;
265
using
IntBase<VY>::prune_lower
;
266
using
IntBase<VY>::prune_upper
;
267
using
IntBase<VY>::eliminate
;
269
Graph
g
;
271
GqInt
(
Home
home,
ValSet
&
vs
,
ViewArray<IntView>
&
x
, VY
y
);
273
GqInt
(
Space
& home,
bool
share,
GqInt<VY>
& p);
274
public
:
276
virtual
Propagator
*
copy
(
Space
& home,
bool
share);
278
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
280
static
ExecStatus
post
(
Home
home,
ViewArray<IntView>
&
x
, VY
y
);
281
};
282
283
}}}
284
285
#include <
gecode/int/nvalues/int-base.hpp
>
286
#include <
gecode/int/nvalues/int-eq.hpp
>
287
#include <
gecode/int/nvalues/int-lq.hpp
>
288
#include <
gecode/int/nvalues/int-gq.hpp
>
289
290
namespace
Gecode {
namespace
Int {
namespace
NValues {
291
298
template
<
class
VY>
299
class
BoolBase
:
public
Propagator
{
300
protected
:
302
static
const
int
VS_ZERO
= 1 << 0;
304
static
const
int
VS_ONE
= 1 << 1;
306
int
status
;
308
Council<ViewAdvisor<BoolView>
>
c
;
310
VY
y
;
312
BoolBase
(
Home
home,
int
status
,
ViewArray<BoolView>
& x, VY
y
);
314
BoolBase
(
Space
& home,
bool
share,
BoolBase<VY>
& p);
315
public
:
317
virtual
ExecStatus
advise
(
Space
& home,
Advisor
&
a
,
const
Delta
&
d
);
319
virtual
PropCost
cost
(
const
Space
& home,
const
ModEventDelta
&
med
)
const
;
321
virtual
size_t
dispose
(
Space
& home);
322
};
323
330
template
<
class
VY>
331
class
EqBool
:
public
BoolBase
<VY> {
332
protected
:
333
using
BoolBase<VY>::VS_ZERO
;
334
using
BoolBase<VY>::VS_ONE
;
335
using
BoolBase<VY>::status
;
336
using
BoolBase<VY>::c
;
337
using
BoolBase<VY>::y
;
339
EqBool
(
Home
home,
int
status
,
ViewArray<BoolView>
& x, VY
y
);
341
EqBool
(
Space
& home,
bool
share,
EqBool<VY>
& p);
342
public
:
344
virtual
Actor
*
copy
(
Space
& home,
bool
share);
346
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
353
static
ExecStatus
post
(
Home
home,
ViewArray<BoolView>
& x, VY y);
354
};
355
362
template
<
class
VY>
363
class
LqBool
:
public
BoolBase
<VY> {
364
protected
:
365
using
BoolBase<VY>::VS_ZERO
;
366
using
BoolBase<VY>::VS_ONE
;
367
using
BoolBase<VY>::status
;
368
using
BoolBase<VY>::c
;
369
using
BoolBase<VY>::y
;
371
LqBool
(
Home
home,
int
status
,
ViewArray<BoolView>
& x, VY
y
);
373
LqBool
(
Space
& home,
bool
share,
LqBool<VY>
& p);
374
public
:
376
virtual
Actor
*
copy
(
Space
& home,
bool
share);
378
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
385
static
ExecStatus
post
(
Home
home,
ViewArray<BoolView>
& x, VY y);
386
};
387
394
template
<
class
VY>
395
class
GqBool
:
public
BoolBase
<VY> {
396
protected
:
397
using
BoolBase<VY>::VS_ZERO
;
398
using
BoolBase<VY>::VS_ONE
;
399
using
BoolBase<VY>::status
;
400
using
BoolBase<VY>::c
;
401
using
BoolBase<VY>::y
;
403
GqBool
(
Home
home,
int
status
,
ViewArray<BoolView>
& x, VY
y
);
405
GqBool
(
Space
& home,
bool
share,
GqBool<VY>
& p);
406
public
:
408
virtual
Actor
*
copy
(
Space
& home,
bool
share);
410
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
417
static
ExecStatus
post
(
Home
home,
ViewArray<BoolView>
& x, VY y);
418
};
419
420
}}}
421
422
#include <
gecode/int/nvalues/bool-base.hpp
>
423
#include <
gecode/int/nvalues/bool-eq.hpp
>
424
#include <
gecode/int/nvalues/bool-lq.hpp
>
425
#include <
gecode/int/nvalues/bool-gq.hpp
>
426
427
#endif
428
429
// STATISTICS: int-prop