main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 5 2013 22:37:21 for Gecode by
doxygen
1.8.3.1
gecode
int
extensional.hh
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Mikael Lagerkvist <lagerkvist@gecode.org>
5
* Christian Schulte <schulte@gecode.org>
6
*
7
* Copyright:
8
* Mikael Lagerkvist, 2007
9
* Christian Schulte, 2004
10
*
11
* Last modified:
12
* $Date: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
13
* $Revision: 11192 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
#ifndef __GECODE_INT_EXTENSIONAL_HH__
41
#define __GECODE_INT_EXTENSIONAL_HH__
42
43
#include <
gecode/int.hh
>
44
45
#include <
gecode/int/rel.hh
>
46
52
namespace
Gecode {
namespace
Int {
namespace
Extensional {
53
68
template
<
class
View,
class
Val,
class
Degree,
class
StateIdx>
69
class
LayeredGraph
:
public
Propagator
{
70
protected
:
72
class
State
{
73
public
:
74
Degree
i_deg
;
75
Degree
o_deg
;
76
77
void
init
(
void
);
78
};
80
class
Edge
{
81
public
:
82
StateIdx
i_state
;
83
StateIdx
o_state
;
84
};
86
class
Support
{
87
public
:
88
Val
val
;
89
Degree
n_edges
;
90
Edge
*
edges
;
91
};
93
typedef
typename
Gecode::Support::IntTypeTraits<Val>::utype
ValSize
;
95
class
Layer
{
96
public
:
97
View
x
;
98
StateIdx
n_states
;
99
ValSize
size
;
100
State
*
states
;
101
Support
*
support
;
102
};
104
class
LayerValues
{
105
private
:
106
const
Support
* s1;
107
const
Support
* s2;
108
public
:
110
LayerValues
(
void
);
112
LayerValues
(
const
Layer
& l);
114
void
init
(
const
Layer
& l);
116
bool
operator ()
(
void
)
const
;
118
void
operator ++
(
void
);
120
int
val
(
void
)
const
;
121
};
123
class
Index
:
public
Advisor
{
124
public
:
126
int
i
;
128
Index
(
Space
& home,
Propagator
& p,
Council<Index>
&
c
,
int
i
);
130
Index
(
Space
& home,
bool
share,
Index
&
a
);
131
};
133
class
IndexRange
{
134
private
:
135
int
_fst;
136
int
_lst;
137
public
:
139
IndexRange
(
void
);
141
void
reset
(
void
);
143
void
add
(
int
i
);
145
void
add
(
const
IndexRange
& ir);
147
void
lshift
(
int
n
);
149
bool
empty
(
void
)
const
;
151
int
fst
(
void
)
const
;
153
int
lst
(
void
)
const
;
154
};
156
Council<Index>
c
;
158
int
n
;
160
Layer
*
layers
;
162
StateIdx
max_states
;
164
unsigned
int
n_states
;
166
unsigned
int
n_edges
;
168
IndexRange
i_ch
;
170
IndexRange
o_ch
;
172
IndexRange
a_ch
;
174
State
&
i_state
(
int
i
, StateIdx is);
176
State
&
i_state
(
int
i
,
const
Edge
& e);
178
bool
i_dec
(
int
i
,
const
Edge
& e);
180
State
&
o_state
(
int
i
, StateIdx os);
182
State
&
o_state
(
int
i
,
const
Edge
& e);
184
bool
o_dec
(
int
i
,
const
Edge
& e);
186
void
audit
(
void
);
188
template
<
class
Var>
189
ExecStatus
initialize
(
Space
& home,
190
const
VarArgArray<Var>
& x,
const
DFA
& dfa);
192
LayeredGraph
(
Space
& home,
bool
share,
193
LayeredGraph<View,Val,Degree,StateIdx>
& p);
194
public
:
196
template
<
class
Var>
197
LayeredGraph
(
Home
home,
198
const
VarArgArray<Var>
& x,
const
DFA
& dfa);
200
virtual
Actor
*
copy
(
Space
& home,
bool
share);
202
virtual
PropCost
cost
(
const
Space
& home,
const
ModEventDelta
&
med
)
const
;
204
virtual
ExecStatus
advise
(
Space
& home,
Advisor
&
a
,
const
Delta
&
d
);
206
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
208
virtual
size_t
dispose
(
Space
& home);
210
template
<
class
Var>
211
static
ExecStatus
post
(
Home
home,
212
const
VarArgArray<Var>
& x,
const
DFA
& dfa);
213
};
214
216
template
<
class
Var>
217
ExecStatus
post_lgp
(
Home
home,
218
const
VarArgArray<Var>
& x,
const
DFA
& dfa);
219
220
}}}
221
222
#include <
gecode/int/extensional/layered-graph.hpp
>
223
224
225
namespace
Gecode {
namespace
Int {
namespace
Extensional {
226
227
typedef
TupleSet::Tuple
Tuple
;
228
typedef
Support::BitSetBase
BitSet
;
229
typedef
Support::BitSetBase
*
Domain
;
230
241
template
<
class
View,
bool
subscribe = true>
242
class
Base
:
public
Propagator
{
243
protected
:
244
ViewArray<View>
x
;
245
TupleSet
tupleSet
;
246
Tuple
**
last_data
;
247
248
TupleSet::TupleSetI
*
ts
(
void
);
249
251
Base
(
Space
& home,
bool
share,
Base<View,subscribe>
& p);
253
Base
(
Home
home,
ViewArray<View>
&
x
,
const
TupleSet
& t);
255
void
init_last
(
Space
& home,
Tuple
** source);
257
Tuple
last
(
int
i
,
int
n);
259
Tuple
last_next
(
int
i
,
int
n);
261
void
init_dom
(
Space
& home,
Domain
dom
);
263
bool
valid
(
Tuple
t,
Domain
dom
);
265
Tuple
find_support
(
Domain
dom
,
int
i
,
int
n);
266
public
:
268
virtual
PropCost
cost
(
const
Space
& home,
const
ModEventDelta
&
med
)
const
;
270
virtual
size_t
dispose
(
Space
& home);
271
protected
:
273
virtual
~Base
(
void
) {}
274
};
275
}}}
276
277
#include <
gecode/int/extensional/base.hpp
>
278
279
280
namespace
Gecode {
namespace
Int {
namespace
Extensional {
281
294
template
<
class
View,
bool
shared>
295
class
Basic
:
public
Base
<View> {
296
protected
:
297
using
Base<View>::x
;
298
using
Base<View>::tupleSet
;
299
using
Base<View>::ts
;
300
using
Base<View>::last
;
301
using
Base<View>::last_next
;
302
using
Base<View>::init_last
;
303
using
Base<View>::init_dom
;
304
using
Base<View>::find_support
;
305
307
Basic
(
Space
& home,
bool
share,
Basic<View,shared>
& p);
309
Basic
(
Home
home,
ViewArray<View>
&
x
,
const
TupleSet
& t);
310
311
public
:
313
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
320
virtual
PropCost
cost
(
const
Space
& home,
const
ModEventDelta
& med)
const
;
322
virtual
Actor
*
copy
(
Space
& home,
bool
share);
324
static
ExecStatus
post
(
Home
home,
ViewArray<View>
& x,
const
TupleSet
& t);
325
};
326
327
}}}
328
329
#include <
gecode/int/extensional/basic.hpp
>
330
331
332
namespace
Gecode {
namespace
Int {
namespace
Extensional {
342
template
<
class
View>
343
class
Incremental
:
public
Base
<View, false> {
344
protected
:
345
using
Base<View, false>::x
;
346
using
Base<View, false>::tupleSet
;
347
using
Base<View, false>::ts
;
348
using
Base<View, false>::last
;
349
using
Base<View, false>::last_next
;
350
using
Base<View, false>::init_last
;
351
using
Base<View, false>::init_dom
;
353
class
SupportEntry
:
public
FreeList
{
354
public
:
356
Tuple
t
;
357
359
360
361
SupportEntry
*
next
(
void
)
const
;
363
SupportEntry
**
nextRef
(
void
);
365
367
368
369
SupportEntry
(
Tuple
t
);
371
SupportEntry
(
Tuple
t
,
SupportEntry
* n);
373
375
376
377
void
dispose
(
Space
& home,
SupportEntry
* l);
379
void
dispose
(
Space
& home);
380
382
static
void
*
operator
new
(
size_t
s,
Space
& home);
384
static
void
operator
delete
(
void
* p);
386
static
void
operator
delete
(
void
* p,
Space
& home);
388
};
390
class
WorkEntry
:
public
FreeList
{
391
public
:
393
int
i
;
395
int
n
;
396
398
399
400
WorkEntry
(
int
i
,
int
n
,
WorkEntry
* ne);
402
404
405
406
WorkEntry
*
next
(
void
)
const
;
408
void
next
(
WorkEntry
*
n
);
410
412
413
414
void
dispose
(
Space
& home);
415
417
static
void
*
operator
new
(
size_t
s,
Space
& home);
419
static
void
operator
delete
(
void
* p);
421
static
void
operator
delete
(
void
* p,
Space
& home);
423
};
425
class
Work
{
426
private
:
428
WorkEntry
* we;
429
public
:
431
Work
(
void
);
433
bool
empty
(
void
)
const
;
435
void
push
(
Space
& home,
int
i
,
int
n);
437
void
pop
(
Space
& home,
int
& i,
int
& n);
438
};
440
Work
w_support
;
442
Work
w_remove
;
443
445
SupportEntry
**
support_data
;
447
int
unassigned
;
448
450
Incremental
(
Space
& home,
bool
share,
Incremental<View>
& p);
452
Incremental
(
Home
home,
ViewArray<View>
&
x
,
const
TupleSet
& t);
454
void
init_support
(
Space
& home);
456
void
find_support
(
Space
& home,
Domain
dom
,
int
i
,
int
n);
458
void
add_support
(
Space
& home,
Tuple
l);
460
void
remove_support
(
Space
& home,
Tuple
l,
int
i
,
int
n);
462
SupportEntry
*
support
(
int
i
,
int
n);
463
public
:
465
virtual
ExecStatus
propagate
(
Space
& home,
const
ModEventDelta
&
med
);
472
virtual
PropCost
cost
(
const
Space
& home,
const
ModEventDelta
&
med
)
const
;
474
virtual
Actor
*
copy
(
Space
& home,
bool
share);
476
static
ExecStatus
post
(
Home
home,
ViewArray<View>
&
x
,
const
TupleSet
& t);
478
size_t
dispose
(
Space
& home);
479
private
:
481
class
SupportAdvisor :
public
Advisor
{
482
public
:
484
int
i
;
486
SupportAdvisor(
Space
& home,
Propagator
& p,
Council<SupportAdvisor>
&
c
,
487
int
i
);
489
SupportAdvisor(
Space
& home,
bool
share, SupportAdvisor&
a
);
491
void
dispose
(
Space
& home,
Council<SupportAdvisor>
&
c
);
492
};
494
Council<SupportAdvisor>
ac;
495
public
:
497
virtual
ExecStatus
advise
(
Space
& home,
Advisor
&
a
,
const
Delta
&
d
);
498
};
499
500
}}}
501
502
#include <
gecode/int/extensional/incremental.hpp
>
503
504
505
#endif
506
507
// STATISTICS: int-prop
508