main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:44 for Gecode by
doxygen
1.8.3.1
gecode
kernel
brancher-tiebreak.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main author:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2008
8
*
9
* Last modified:
10
* $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11
* $Revision: 12001 $
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
namespace
Gecode {
39
49
template
<
class
A,
class
B>
50
class
ViewSelTieBreakStatic
{
51
protected
:
53
A
a
;
55
B
b
;
56
public
:
58
typedef
typename
A::View
View
;
60
class
Choice
{
61
public
:
63
typename
A::Choice
a
;
65
typename
B::Choice
b
;
67
Choice
(
const
typename
A::Choice&
a
,
const
typename
B::Choice&
b
);
69
size_t
size
(
void
)
const
;
71
void
archive
(
Archive
& e)
const
;
72
};
74
ViewSelTieBreakStatic
(
void
);
76
ViewSelTieBreakStatic
(
Space
& home, A&
a
, B&
b
);
78
ViewSelStatus
init
(
Space
& home,
typename
A::View x);
80
ViewSelStatus
select
(
Space
& home,
typename
A::View x);
82
Choice
choice
(
Space
& home);
84
Choice
choice
(
const
Space
& home,
Archive
& e);
86
void
commit
(
Space
& home,
const
Choice
&
c
,
unsigned
int
a
);
88
void
update
(
Space
& home,
bool
share,
ViewSelTieBreakStatic
& vs);
90
void
dispose
(
Space
& home);
91
};
92
96
class
ChoiceVirtualBase
{
97
public
:
99
virtual
ChoiceVirtualBase
*
copy
(
void
)
const
= 0;
101
virtual
size_t
size
(
void
)
const
= 0;
103
GECODE_KERNEL_EXPORT
virtual
~ChoiceVirtualBase
(
void
);
105
virtual
void
archive
(
Archive
& e)
const
= 0;
107
108
109
static
void
*
operator
new
(
size_t
s);
111
static
void
operator
delete
(
void
*);
113
};
114
118
template
<
class
View>
119
class
ViewSelVirtualBase
{
120
public
:
122
virtual
ViewSelStatus
init
(
Space
& home, View x) = 0;
124
virtual
ViewSelStatus
select
(
Space
& home, View x) = 0;
126
virtual
ChoiceVirtualBase
*
choice
(
Space
& home) = 0;
128
virtual
ChoiceVirtualBase
*
choice
(
const
Space
& home,
Archive
& e) = 0;
130
virtual
void
commit
(
Space
& home,
const
ChoiceVirtualBase
*
c
,
131
unsigned
int
a
) = 0;
133
virtual
ViewSelVirtualBase<View>
*
copy
(
Space
& home,
bool
share) = 0;
135
virtual
size_t
dispose
(
Space
& home) = 0;
137
138
139
static
void
*
operator
new
(
size_t
s,
Space
& home);
141
static
void
operator
delete
(
void
* p,
Space
& home);
143
static
void
operator
delete
(
void
*);
145
};
146
150
template
<
class
Choice>
151
class
ChoiceVirtual
:
public
ChoiceVirtualBase
{
152
public
:
154
Choice
choice
;
156
ChoiceVirtual
(
const
Choice
&
c
);
158
virtual
ChoiceVirtualBase
*
copy
(
void
)
const
;
160
virtual
size_t
size
(
void
)
const
;
162
virtual
~ChoiceVirtual
(
void
);
164
virtual
void
archive
(
Archive
& e)
const
;
165
};
166
170
template
<
class
ViewSel>
171
class
ViewSelVirtual
:
public
ViewSelVirtualBase
<typename ViewSel::View> {
172
protected
:
174
ViewSel
viewsel
;
175
public
:
177
ViewSelVirtual
(
Space
& home,
const
VarBranchOptions
& vbo);
179
ViewSelVirtual
(
Space
& home,
bool
share,
ViewSelVirtual
& vsv);
181
virtual
ViewSelStatus
init
(
Space
& home,
typename
ViewSel::View x);
183
virtual
ViewSelStatus
select
(
Space
& home,
typename
ViewSel::View x);
185
virtual
ChoiceVirtualBase
*
choice
(
Space
& home);
187
virtual
ChoiceVirtualBase
*
choice
(
const
Space
& home,
Archive
& e);
189
virtual
void
commit
(
Space
& home,
const
ChoiceVirtualBase
*
d
,
190
unsigned
int
a
);
192
virtual
ViewSelVirtualBase<typename ViewSel::View>
*
193
copy
(
Space
& home,
bool
share);
195
virtual
size_t
dispose
(
Space
& home);
196
};
197
201
template
<
class
_View>
202
class
ViewSelTieBreakDynamic
{
203
protected
:
205
int
n
;
207
ViewSelVirtualBase<_View>
**
tb
;
208
public
:
210
typedef
_View
View
;
212
class
Choice
{
213
public
:
215
int
n
;
217
ChoiceVirtualBase
**
c
;
219
Choice
(
Space
& home,
ViewSelVirtualBase<_View>
**
tb
,
int
n0);
221
Choice
(
const
Space
& home,
Archive
& e,
222
ViewSelVirtualBase<_View>
**
tb
,
int
n0);
224
Choice
(
const
Choice
& ce);
226
const
Choice
&
operator =
(
const
Choice
& ce);
228
void
commit
(
Space
& home,
unsigned
int
a
,
229
ViewSelVirtualBase<_View>
**
tb
)
const
;
231
size_t
size
(
void
)
const
;
233
~Choice
(
void
);
235
void
archive
(
Archive
& e)
const
;
236
};
238
ViewSelTieBreakDynamic
(
void
);
240
ViewSelTieBreakDynamic
(
Space
& home,
ViewSelVirtualBase<_View>
** vsv,
241
int
n
);
243
ViewSelStatus
init
(
Space
& home, _View x);
245
ViewSelStatus
select
(
Space
& home, _View x);
247
Choice
choice
(
Space
& home);
249
Choice
choice
(
const
Space
& home,
Archive
& e);
251
void
commit
(
Space
& home,
252
const
typename
ViewSelTieBreakDynamic<_View>::Choice
&
c
,
253
unsigned
int
a
);
255
void
update
(
Space
& home,
bool
share,
ViewSelTieBreakDynamic
& vs);
257
void
dispose
(
Space
& home);
258
};
260
261
262
// Select variable with static tie breaking
263
template
<
class
A,
class
B>
264
forceinline
265
ViewSelTieBreakStatic<A,B>::Choice::Choice
(
const
typename
A::Choice& a0,
266
const
typename
B::Choice& b0)
267
:
a
(a0),
b
(b0) {}
268
template
<
class
A,
class
B>
269
forceinline
size_t
270
ViewSelTieBreakStatic<A,B>::Choice::size
(
void
)
const
{
271
return
a
.size() +
b
.size();
272
}
273
template
<
class
A,
class
B>
274
forceinline
void
275
ViewSelTieBreakStatic<A,B>::Choice::archive
(
Archive
& e)
const
{
276
a
.archive(e);
277
b
.archive(e);
278
}
279
280
template
<
class
A,
class
B>
281
forceinline
282
ViewSelTieBreakStatic<A,B>::ViewSelTieBreakStatic
(
void
) {}
283
template
<
class
A,
class
B>
284
forceinline
285
ViewSelTieBreakStatic<A,B>::
286
ViewSelTieBreakStatic
(
Space
&, A& a0, B& b0)
287
:
a
(a0),
b
(b0) {}
288
template
<
class
A,
class
B>
289
forceinline
ViewSelStatus
290
ViewSelTieBreakStatic<A,B>::init
(
Space
& home,
typename
A::View x) {
291
ViewSelStatus
s =
a
.init(home,x);
292
return
(
b
.init(home,x) !=
VSS_BEST
) ?
VSS_BETTER
: s;
293
}
294
template
<
class
A,
class
B>
295
forceinline
ViewSelStatus
296
ViewSelTieBreakStatic<A,B>::select
(
Space
& home,
typename
A::View x) {
297
switch
(
a
.select(home,x)) {
298
case
VSS_BEST
:
299
return
(
b
.init(home,x) !=
VSS_BEST
) ?
VSS_BETTER
:
VSS_BEST
;
300
case
VSS_BETTER
:
301
(void)
b
.init(home,x);
302
return
VSS_BETTER
;
303
case
VSS_WORSE
:
304
return
VSS_WORSE
;
305
case
VSS_TIE
:
306
switch
(
b
.select(home,x)) {
307
case
VSS_BEST
:
return
VSS_BETTER
;
308
case
VSS_BETTER
:
return
VSS_BETTER
;
309
case
VSS_TIE
:
return
VSS_TIE
;
310
case
VSS_WORSE
:
return
VSS_WORSE
;
311
default
:
GECODE_NEVER
;
312
}
313
default
:
GECODE_NEVER
;
314
return
VSS_WORSE
;
315
}
316
}
317
template
<
class
A,
class
B>
318
inline
typename
ViewSelTieBreakStatic<A,B>::Choice
319
ViewSelTieBreakStatic<A,B>::choice
(
Space
& home) {
320
typename
ViewSelTieBreakStatic<A,B>::Choice
c
(
a
.choice(home),
321
b
.choice(home));
322
return
c
;
323
}
324
template
<
class
A,
class
B>
325
inline
typename
ViewSelTieBreakStatic<A,B>::Choice
326
ViewSelTieBreakStatic<A,B>::choice
(
const
Space
& home,
Archive
& e) {
327
typename
ViewSelTieBreakStatic<A,B>::Choice
c
(
a
.choice(home,e),
328
b
.choice(home,e));
329
return
c
;
330
}
331
template
<
class
A,
class
B>
332
forceinline
void
333
ViewSelTieBreakStatic<A,B>::commit
(
Space
& home,
const
Choice
&
c
,
334
unsigned
int
al) {
335
a
.commit(home, c.
a
, al);
336
b
.commit(home, c.
b
, al);
337
}
338
template
<
class
A,
class
B>
339
forceinline
void
340
ViewSelTieBreakStatic<A,B>::update
(
Space
& home,
bool
share,
341
ViewSelTieBreakStatic<A,B>
& vstb) {
342
a
.
update
(home,share,vstb.
a
);
343
b
.
update
(home,share,vstb.
b
);
344
}
345
template
<
class
A,
class
B>
346
forceinline
void
347
ViewSelTieBreakStatic<A,B>::dispose
(
Space
& home) {
348
a
.dispose(home);
349
b
.dispose(home);
350
}
351
352
353
// Virtualized view selection
354
template
<
class
View>
355
forceinline
void
356
ViewSelVirtualBase<View>::operator
delete
(
void
*) {}
357
template
<
class
View>
358
forceinline
void
359
ViewSelVirtualBase<View>::operator
delete
(
void
*,
Space
&) {}
360
template
<
class
View>
361
forceinline
void
*
362
ViewSelVirtualBase<View>::operator
new
(
size_t
s,
Space
& home) {
363
return
home.ralloc(s);
364
}
365
366
// Virtualized choice
367
forceinline
void
368
ChoiceVirtualBase::operator
delete
(
void
* p) {
369
heap
.
rfree
(p);
370
}
371
forceinline
void
*
372
ChoiceVirtualBase::operator
new
(
size_t
s) {
373
return
heap
.
ralloc
(s);
374
}
375
forceinline
376
ChoiceVirtualBase::~ChoiceVirtualBase
(
void
) {
377
}
378
379
380
template
<
class
Choice>
381
forceinline
382
ChoiceVirtual<Choice>::ChoiceVirtual
(
const
Choice
&
c
)
383
: choice(c) {}
384
template
<
class
Choice>
385
forceinline
ChoiceVirtualBase
*
386
ChoiceVirtual<Choice>::copy
(
void
)
const
{
387
return
new
ChoiceVirtual<Choice>
(choice);
388
}
389
template
<
class
Choice>
390
forceinline
size_t
391
ChoiceVirtual<Choice>::size
(
void
)
const
{
392
return
sizeof
(
ChoiceVirtual<Choice>
);
393
}
394
template
<
class
Choice>
395
ChoiceVirtual<Choice>::~ChoiceVirtual
(
void
) {}
396
template
<
class
Choice>
void
397
ChoiceVirtual<Choice>::archive
(
Archive
& e)
const
{
398
choice.archive(e);
399
}
400
401
template
<
class
ViewSel>
402
forceinline
403
ViewSelVirtual<ViewSel>::ViewSelVirtual
(
Space
& home,
404
const
VarBranchOptions
& vbo)
405
: viewsel(home,vbo) {}
406
template
<
class
ViewSel>
407
forceinline
408
ViewSelVirtual<ViewSel>::ViewSelVirtual
(
Space
& home,
bool
share,
409
ViewSelVirtual<ViewSel>
& vsv) {
410
viewsel.update(home,share,vsv.
viewsel
);
411
}
412
template
<
class
ViewSel>
413
ViewSelStatus
414
ViewSelVirtual<ViewSel>::init
(
Space
& home,
typename
ViewSel::View x) {
415
return
viewsel.init(home,x);
416
}
417
template
<
class
ViewSel>
418
ViewSelStatus
419
ViewSelVirtual<ViewSel>::select
(
Space
& home,
typename
ViewSel::View x) {
420
return
viewsel.select(home,x);
421
}
422
template
<
class
ViewSel>
423
ChoiceVirtualBase
*
424
ViewSelVirtual<ViewSel>::choice
(
Space
& home) {
425
return
new
ChoiceVirtual<typename ViewSel::Choice>
(viewsel.choice(home));
426
}
427
template
<
class
ViewSel>
428
ChoiceVirtualBase
*
429
ViewSelVirtual<ViewSel>::choice
(
const
Space
& home,
Archive
& e) {
430
return
new
ChoiceVirtual<typename ViewSel::Choice>
(viewsel.choice(home,e));
431
}
432
template
<
class
ViewSel>
433
void
434
ViewSelVirtual<ViewSel>::commit
(
Space
& home,
const
ChoiceVirtualBase
*
_c
,
435
unsigned
int
a
) {
436
const
ChoiceVirtual<typename ViewSel::Choice>
*
c
=
437
static_cast<
const
ChoiceVirtual<typename ViewSel::Choice>
*
>
(
_c
);
438
viewsel.commit(home, c->
choice
, a);
439
}
440
template
<
class
ViewSel>
441
ViewSelVirtualBase<typename ViewSel::View>
*
442
ViewSelVirtual<ViewSel>::copy
(
Space
& home,
bool
share) {
443
return
new
(home)
ViewSelVirtual<ViewSel>
(home,share,*
this
);
444
}
445
template
<
class
ViewSel>
446
size_t
447
ViewSelVirtual<ViewSel>::dispose
(
Space
& home) {
448
viewsel.dispose(home);
449
return
sizeof
(
ViewSelVirtual<ViewSel>
);
450
}
451
452
453
// Choice for dynamic tie breaking
454
template
<
class
View>
455
forceinline
456
ViewSelTieBreakDynamic<View>::Choice::Choice
457
(
Space
& home,
ViewSelVirtualBase<View>
** tb,
int
n0)
458
: n(n0),
c
(
heap
.
alloc
<
ChoiceVirtualBase
*>(n)) {
459
for
(
int
i
=n;
i
--; )
460
c
[
i
] = tb[
i
]->choice(home);
461
}
462
template
<
class
View>
463
forceinline
464
ViewSelTieBreakDynamic<View>::Choice::Choice
465
(
const
Space
& home,
Archive
& e,
ViewSelVirtualBase<View>
** tb,
466
int
n0)
467
: n(n0),
c
(
heap
.
alloc
<
ChoiceVirtualBase
*>(n)) {
468
for
(
int
i
=n;
i
--; )
469
c
[
i
] = tb[
i
]->choice(home,e);
470
}
471
template
<
class
View>
472
forceinline
473
ViewSelTieBreakDynamic<View>::Choice::Choice
(
const
Choice
& ce)
474
: n(ce.n),
c
(
heap
.alloc<
ChoiceVirtualBase
*>(n)) {
475
for
(
int
i
=
n
;
i
--; )
476
c
[
i
] = ce.
c
[
i
]->
copy
();
477
}
478
template
<
class
View>
479
forceinline
const
typename
ViewSelTieBreakDynamic<View>::Choice
&
480
ViewSelTieBreakDynamic<View>::Choice::operator =
(
const
Choice
& ce) {
481
if
(&ce !=
this
) {
482
assert(ce.
n
==
n
);
483
for
(
int
i
=
n
;
i
--; ) {
484
delete
c
[
i
];
c
[
i
] = ce.
c
[
i
]->
copy
();
485
}
486
}
487
return
*
this
;
488
}
489
template
<
class
View>
490
forceinline
void
491
ViewSelTieBreakDynamic<View>::Choice::commit
492
(
Space
& home,
unsigned
int
a
,
ViewSelVirtualBase<View>
** tb)
const
{
493
for
(
int
i
=
n
;
i
--; )
494
tb[
i
]->
commit
(home,
c
[
i
], a);
495
}
496
template
<
class
View>
497
forceinline
size_t
498
ViewSelTieBreakDynamic<View>::Choice::size
(
void
)
const
{
499
size_t
s = (
sizeof
(
typename
ViewSelTieBreakDynamic<View>::Choice
) +
500
n
*
sizeof
(
ChoiceVirtualBase
*));
501
for
(
int
i
=
n
;
i
--; )
502
s +=
c
[
i
]->
size
();
503
return
s;
504
}
505
template
<
class
View>
506
forceinline
507
ViewSelTieBreakDynamic<View>::Choice::~Choice
(
void
) {
508
for
(
int
i
=
n
;
i
--; )
509
delete
c
[
i
];
510
heap
.
free
(
c
,
n
);
511
}
512
template
<
class
View>
513
forceinline
void
514
ViewSelTieBreakDynamic<View>::Choice::archive
(
Archive
& e)
const
515
{
516
for
(
int
i
=0;
i
<
n
;
i
++)
517
c
[
i
]->archive(e);
518
}
519
520
521
// Select variable with dynamic tie breaking
522
template
<
class
View>
523
forceinline
524
ViewSelTieBreakDynamic<View>::ViewSelTieBreakDynamic
(
void
) {}
525
template
<
class
View>
526
forceinline
527
ViewSelTieBreakDynamic<View>::
528
ViewSelTieBreakDynamic
(
Space
& home,
ViewSelVirtualBase<View>
** vsv,
int
n0)
529
:
n
(n0), tb(home.alloc<
ViewSelVirtualBase
<
View
>*>(
n
)) {
530
for
(
int
i
=0;
i
<
n
;
i
++)
531
tb[
i
]=vsv[
i
];
532
assert(n > 0);
533
}
534
template
<
class
View>
535
forceinline
ViewSelStatus
536
ViewSelTieBreakDynamic<View>::init
(
Space
& home,
View
x) {
537
ViewSelStatus
s =
VSS_BEST
;
538
for
(
int
i
=0;
i
<n;
i
++)
539
if
(tb[
i
]->init(home,x) !=
VSS_BEST
)
540
s =
VSS_BETTER
;
541
return
s;
542
}
543
template
<
class
View>
544
forceinline
ViewSelStatus
545
ViewSelTieBreakDynamic<View>::select
(
Space
& home,
View
x) {
546
switch
(tb[0]->select(home,x)) {
547
case
VSS_BEST
:
548
{
549
ViewSelStatus
s =
VSS_BEST
;
550
for
(
int
i
=1;
i
<n;
i
++)
551
if
(tb[
i
]->init(home,x) !=
VSS_BEST
)
552
s =
VSS_BETTER
;
553
return
s;
554
}
555
case
VSS_BETTER
:
556
for
(
int
i
=1;
i
<n;
i
++)
557
(
void
) tb[
i
]->
init
(home,x);
558
return
VSS_BETTER
;
559
case
VSS_WORSE
:
560
return
VSS_WORSE
;
561
case
VSS_TIE
:
562
for
(
int
i
=1;
i
<n;
i
++)
563
switch
(tb[
i
]->select(home,x)) {
564
case
VSS_BEST
:
case
VSS_BETTER
:
565
for
(
int
j=
i
+1; j<n; j++)
566
(
void
) tb[j]->
init
(home,x);
567
return
VSS_BETTER
;
568
case
VSS_TIE
:
break
;
569
case
VSS_WORSE
:
return
VSS_WORSE
;
570
default
:
GECODE_NEVER
;
571
}
572
return
VSS_TIE
;
573
default
:
GECODE_NEVER
;
574
return
VSS_WORSE
;
575
}
576
}
577
template
<
class
_View>
578
inline
typename
ViewSelTieBreakDynamic<_View>::Choice
579
ViewSelTieBreakDynamic<_View>::choice
(
Space
& home) {
580
Choice
c
(home,tb,n);
581
return
c
;
582
}
583
template
<
class
_View>
584
inline
typename
ViewSelTieBreakDynamic<_View>::Choice
585
ViewSelTieBreakDynamic<_View>::choice
(
const
Space
& home,
Archive
& e) {
586
Choice
c
(home,e,tb,n);
587
return
c
;
588
}
589
template
<
class
_View>
590
forceinline
void
591
ViewSelTieBreakDynamic<_View>::commit
592
(
Space
& home,
const
typename
ViewSelTieBreakDynamic<_View>::Choice
&
c
,
593
unsigned
int
a) {
594
c.
commit
(home,a,tb);
595
}
596
template
<
class
_View>
597
forceinline
void
598
ViewSelTieBreakDynamic<_View>::update
(
Space
& home,
bool
share,
599
ViewSelTieBreakDynamic<_View>
& vstb) {
600
n = vstb.
n
;
601
tb = home.
alloc
<
ViewSelVirtualBase<View>
*>(n);
602
for
(
int
i
=0;
i
<n;
i
++)
603
tb[
i
] = vstb.
tb
[
i
]->
copy
(home,share);
604
}
605
template
<
class
_View>
606
forceinline
void
607
ViewSelTieBreakDynamic<_View>::dispose
(
Space
& home) {
608
for
(
int
i
=0;
i
<n;
i
++)
609
home.
rfree
(tb[
i
],tb[i]->
dispose
(home));
610
home.
free
<
ViewSelVirtualBase<_View>
*>(tb,n);
611
}
612
613
}
614
615
// STATISTICS: kernel-branch