main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:19 for Gecode by
doxygen
1.8.1.1
gecode
set
var-imp.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
*
6
* Contributing authors:
7
* Christian Schulte <schulte@gecode.org>
8
* Gabor Szokoli <szokoli@gecode.org>
9
*
10
* Copyright:
11
* Guido Tack, 2004
12
* Christian Schulte, 2004
13
* Gabor Szokoli, 2004
14
*
15
* Last modified:
16
* $Date: 2011-09-06 18:22:20 +1000 (Tue, 06 Sep 2011) $ by $Author: tack $
17
* $Revision: 12392 $
18
*
19
* This file is part of Gecode, the generic constraint
20
* development environment:
21
* http://www.gecode.org
22
*
23
* Permission is hereby granted, free of charge, to any person obtaining
24
* a copy of this software and associated documentation files (the
25
* "Software"), to deal in the Software without restriction, including
26
* without limitation the rights to use, copy, modify, merge, publish,
27
* distribute, sublicense, and/or sell copies of the Software, and to
28
* permit persons to whom the Software is furnished to do so, subject to
29
* the following conditions:
30
*
31
* The above copyright notice and this permission notice shall be
32
* included in all copies or substantial portions of the Software.
33
*
34
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41
*
42
*/
43
44
#include <iostream>
45
46
namespace
Gecode {
namespace
Set {
47
48
class
SetVarImp;
49
class
LUBndSet;
50
class
GLBndSet;
51
56
class
SetDelta
:
public
Delta
{
57
friend
class
SetVarImp
;
58
friend
class
LUBndSet
;
59
friend
class
GLBndSet
;
60
private
:
61
int
_glbMin;
62
int
_glbMax;
63
int
_lubMin;
64
int
_lubMax;
65
public
:
67
SetDelta
(
void
);
69
SetDelta
(
int
glbMin
,
int
glbMax
,
int
lubMin
,
int
lubMax
);
71
int
glbMin
(
void
)
const
;
73
int
glbMax
(
void
)
const
;
75
int
lubMin
(
void
)
const
;
77
int
lubMax
(
void
)
const
;
79
bool
glbAny
(
void
)
const
;
81
bool
lubAny
(
void
)
const
;
82
};
83
84
}}
85
86
#include <
gecode/set/var-imp/delta.hpp
>
87
88
namespace
Gecode {
namespace
Set {
89
93
class
BndSet
{
94
private
:
95
RangeList
* first;
96
RangeList
* last;
97
protected
:
99
unsigned
int
_size
;
101
unsigned
int
_card
;
103
void
fst
(
RangeList
*
r
);
105
void
lst
(
RangeList
*
r
);
106
108
RangeList
*
fst
(
void
)
const
;
110
RangeList
*
lst
(
void
)
const
;
111
112
public
:
114
static
const
int
MAX_OF_EMPTY
=
Limits::min
-1;
116
static
const
int
MIN_OF_EMPTY
=
Limits::max
+1;
117
119
120
121
BndSet
(
void
);
123
BndSet
(
Space
& home,
int
i
,
int
j);
125
GECODE_SET_EXPORT
BndSet
(
Space
& home,
const
IntSet
& s);
127
129
130
131
void
dispose
(
Space
& home);
133
135
136
137
int
min
(
void
)
const
;
139
int
max
(
void
)
const
;
141
int
minN
(
unsigned
int
n)
const
;
143
unsigned
int
size
(
void
)
const
;
145
unsigned
int
card
(
void
)
const
;
147
void
card
(
unsigned
int
c
);
149
151
152
153
bool
empty
(
void
)
const
;
155
bool
in
(
int
i
)
const
;
157
159
160
161
void
become
(
Space
& home,
const
BndSet
& s);
163
165
166
167
RangeList
*
ranges
(
void
)
const
;
169
170
protected
:
172
template
<
class
I>
bool
overwrite
(
Space
& home,I&
i
);
173
174
public
:
176
177
178
void
update
(
Space
& home,
BndSet
& x);
180
182
GECODE_SET_EXPORT
bool
isConsistent
(
void
)
const
;
183
};
184
189
class
BndSetRanges
:
public
Iter::Ranges::RangeList
{
190
public
:
192
193
194
BndSetRanges
(
void
);
196
BndSetRanges
(
const
BndSet
& s);
198
void
init
(
const
BndSet
& s);
200
};
201
209
class
GLBndSet
:
public
BndSet
{
210
private
:
212
GECODE_SET_EXPORT
bool
include_full(
Space
& home,
int
,
int
,
SetDelta
&);
213
public
:
215
216
217
GLBndSet
(
void
);
219
GLBndSet
(
Space
&);
221
GLBndSet
(
Space
& home,
int
i
,
int
j);
223
GLBndSet
(
Space
& home,
const
IntSet
& s);
225
void
init
(
Space
& home);
227
229
230
231
bool
include
(
Space
& home,
int
i,
int
j,
SetDelta
&
d
);
233
template
<
class
I>
bool
includeI
(
Space
& home,I& i);
235
private
:
236
GLBndSet
(
const
GLBndSet
&);
237
const
GLBndSet
& operator =(
const
GLBndSet
&);
238
};
239
247
class
LUBndSet
:
public
BndSet
{
248
private
:
249
GECODE_SET_EXPORT
bool
exclude_full(
Space
& home,
int
,
int
,
SetDelta
&);
250
GECODE_SET_EXPORT
bool
intersect_full(
Space
& home,
int
i
,
int
j);
251
public
:
253
254
255
LUBndSet
(
void
);
257
LUBndSet
(
Space
& home);
259
LUBndSet
(
Space
& home,
int
i,
int
j);
261
LUBndSet
(
Space
& home,
const
IntSet
& s);
263
void
init
(
Space
& home);
265
267
268
269
bool
exclude
(
Space
& home,
int
i,
int
j,
SetDelta
&
d
);
271
bool
intersect
(
Space
& home,
int
i,
int
j);
273
template
<
class
I>
bool
intersectI
(
Space
& home, I& i);
275
template
<
class
I>
bool
excludeI
(
Space
& home, I& i);
277
void
excludeAll
(
Space
& home);
279
private
:
280
LUBndSet
(
const
LUBndSet
&);
281
const
LUBndSet
& operator =(
const
LUBndSet
&);
282
};
283
284
/*
285
* Iterators
286
*
287
*/
288
289
295
template
<
class
I>
296
class
RangesCompl
:
297
public
Iter::Ranges::Compl
<Limits::min, Limits::max, I> {
298
public
:
300
301
302
RangesCompl
(
void
);
304
RangesCompl
(I&
i
);
306
void
init
(I& i);
308
};
309
321
template
<
class
T>
class
LubRanges
{
322
public
:
324
325
326
LubRanges
(
void
);
328
LubRanges
(
const
T& x);
330
void
init
(
const
T& x);
332
334
335
336
bool
operator ()
(
void
)
const
;
338
void
operator ++
(
void
);
340
342
343
344
int
min
(
void
)
const
;
346
int
max
(
void
)
const
;
348
unsigned
int
width
(
void
)
const
;
350
};
351
363
template
<
class
T>
class
GlbRanges
{
364
public
:
366
367
368
GlbRanges
(
void
);
370
GlbRanges
(
const
T& x);
372
void
init
(
const
T& x);
374
376
377
378
bool
operator ()
(
void
)
const
;
380
void
operator ++
(
void
);
382
384
385
386
int
min
(
void
)
const
;
388
int
max
(
void
)
const
;
390
unsigned
int
width
(
void
)
const
;
392
};
393
405
template
<
class
T>
406
class
UnknownRanges
:
public
Iter::Ranges::Diff
<LubRanges<T>, GlbRanges<T> >{
407
private
:
408
LubRanges<T>
i1;
409
GlbRanges<T>
i2;
410
public
:
412
413
414
UnknownRanges
(
void
);
416
UnknownRanges
(
const
T& x);
418
void
init
(
const
T& x);
420
};
421
422
}}
423
424
#include <
gecode/set/var-imp/integerset.hpp
>
425
#include <
gecode/set/var-imp/iter.hpp
>
426
427
namespace
Gecode {
namespace
Set {
428
434
class
SetVarImp
:
public
SetVarImpBase
{
435
friend
class
LubRanges
<
SetVarImp
*>;
436
friend
class
GlbRanges
<
SetVarImp
*>;
437
private
:
439
LUBndSet
lub;
441
GLBndSet
glb;
442
443
protected
:
445
SetVarImp
(
Space
& home,
bool
share,
SetVarImp
& x);
446
public
:
448
449
450
SetVarImp
(
Space
& home);
459
SetVarImp
(
Space
& home,
int
glbMin
,
int
glbMax
,
int
lubMin
,
int
lubMax
,
460
unsigned
int
cardMin
= 0,
461
unsigned
int
cardMax
=
Limits::card
);
470
SetVarImp
(
Space
& home,
const
IntSet
& glbD,
int
lubMin
,
int
lubMax
,
471
unsigned
int
cardMin
,
unsigned
int
cardMax
);
480
SetVarImp
(
Space
& home,
int
glbMin
,
int
glbMax
,
const
IntSet
& lubD,
481
unsigned
int
cardMin
,
unsigned
int
cardMax
);
490
SetVarImp
(
Space
& home,
const
IntSet
& glbD,
const
IntSet
& lubD,
491
unsigned
int
cardMin
,
unsigned
int
cardMax
);
493
495
496
497
unsigned
int
cardMin
(
void
)
const
;
499
unsigned
int
cardMax
(
void
)
const
;
501
int
lubMin
(
void
)
const
;
503
int
lubMax
(
void
)
const
;
505
int
lubMinN
(
unsigned
int
n)
const
;
507
int
glbMin
(
void
)
const
;
509
int
glbMax
(
void
)
const
;
511
unsigned
int
glbSize
(
void
)
const
;
513
unsigned
int
lubSize
(
void
)
const
;
515
517
518
519
bool
assigned
(
void
)
const
;
521
bool
knownIn
(
int
n)
const
;
523
bool
knownOut
(
int
)
const
;
525
526
private
:
528
529
530
template
<
class
I>
ModEvent
includeI_full(
Space
& home,
int
mi,
int
ma, I&
i
);
532
template
<
class
I>
ModEvent
excludeI_full(
Space
& home,
int
mi,
int
ma, I&
i
);
534
template
<
class
I>
ModEvent
intersectI_full(
Space
& home,
int
mi,
int
ma, I&
i
);
536
537
GECODE_SET_EXPORT
ModEvent
processLubChange(
Space
& home,
SetDelta
&
d
);
538
GECODE_SET_EXPORT
ModEvent
processGlbChange(
Space
& home,
SetDelta
&
d
);
539
541
542
543
GECODE_SET_EXPORT
ModEvent
cardMin_full(
Space
& home);
545
GECODE_SET_EXPORT
ModEvent
cardMax_full(
Space
& home);
547
548
public
:
549
551
552
553
ModEvent
include
(
Space
& home,
int
n);
555
ModEvent
include
(
Space
& home,
int
i
,
int
j);
557
ModEvent
exclude
(
Space
& home,
int
n);
559
ModEvent
exclude
(
Space
& home,
int
i
,
int
j);
561
ModEvent
intersect
(
Space
& home,
int
n);
563
ModEvent
intersect
(
Space
& home,
int
i
,
int
j);
565
ModEvent
cardMin
(
Space
& home,
unsigned
int
n);
567
ModEvent
cardMax
(
Space
& home,
unsigned
int
n);
569
571
572
573
template
<
class
I>
ModEvent
includeI
(
Space
& home,I&
i
);
575
template
<
class
I>
ModEvent
excludeI
(
Space
& home,I&
i
);
577
template
<
class
I>
ModEvent
intersectI
(
Space
& home,I&
i
);
579
580
public
:
582
583
590
void
subscribe
(
Space
& home,
Propagator
& p,
PropCond
pc,
bool
schedule
=
true
);
592
void
cancel
(
Space
& home,
Propagator
& p,
PropCond
pc);
594
void
subscribe
(
Space
& home,
Advisor
&
a
);
596
void
cancel
(
Space
& home,
Advisor
&
a
);
598
599
private
:
601
GECODE_SET_EXPORT
SetVarImp
* perform_copy(
Space
& home,
bool
share);
602
603
public
:
605
606
607
SetVarImp
*
copy
(
Space
& home,
bool
share);
609
611
612
613
static
int
glbMin
(
const
Delta
&
d
);
615
static
int
glbMax
(
const
Delta
&
d
);
617
static
bool
glbAny
(
const
Delta
&
d
);
619
static
int
lubMin
(
const
Delta
&
d
);
621
static
int
lubMax
(
const
Delta
&
d
);
623
static
bool
lubAny
(
const
Delta
&
d
);
625
626
};
627
628
class
SetView
;
629
630
}}
631
632
#include <
gecode/set/var-imp/set.hpp
>
633
634
// STATISTICS: set-var