main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:07 for Gecode by
doxygen
1.8.4
gecode
search
meta
nogoods.cpp
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, 2013
8
*
9
* Last modified:
10
* $Date: 2013-07-09 12:24:39 +0200 (Tue, 09 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13832 $
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
#include <
gecode/search/meta/nogoods.hh
>
39
40
namespace
Gecode {
namespace
Search {
namespace
Meta {
41
43
forceinline
NGL
*
44
disposenext
(
NGL
* ngl,
Space
& home,
Propagator
&
p
,
bool
c
) {
45
NGL
*
n
= ngl->
next
();
46
if
(c)
47
ngl->
cancel
(home,p);
48
home.
rfree
(ngl,ngl->
dispose
(home));
49
return
n
;
50
}
51
52
void
53
NoNGL::subscribe
(
Space
&,
Propagator
&) {
54
GECODE_NEVER
;
55
}
56
void
57
NoNGL::cancel
(
Space
&,
Propagator
&) {
58
GECODE_NEVER
;
59
}
60
NGL::Status
61
NoNGL::status
(
const
Space
&)
const
{
62
GECODE_NEVER
;
63
return
NGL::NONE
;
64
}
65
ExecStatus
66
NoNGL::prune
(
Space
&) {
67
GECODE_NEVER
;
68
return
ES_OK
;
69
}
70
NGL
*
71
NoNGL::copy
(
Space
&,
bool
) {
72
GECODE_NEVER
;
73
return
NULL;
74
}
75
76
Actor
*
77
NoGoodsProp::copy
(
Space
& home,
bool
share) {
78
return
new
(home)
NoGoodsProp
(home,share,*
this
);
79
}
80
81
PropCost
82
NoGoodsProp::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
83
return
PropCost::linear
(
PropCost::LO
,
n
);
84
}
85
86
ExecStatus
87
NoGoodsProp::propagate
(
Space
& home,
const
ModEventDelta
&) {
88
restart:
89
// Start with checking the first literal
90
switch
(
root
->
status
(home)) {
91
case
NGL::FAILED
:
92
// All no-goods are dead, let dispose() clean up
93
return
home.
ES_SUBSUMED
(*
this
);
94
case
NGL::SUBSUMED
:
95
{
96
NGL
*
l
=
disposenext
(
root
,home,*
this
,
true
);
n
--;
97
// Prune leaf-literals
98
while
((l != NULL) && l->
leaf
()) {
99
l->
cancel
(home,*
this
);
n
--;
100
GECODE_ES_CHECK
(l->
prune
(home));
101
l =
disposenext
(l,home,*
this
,
false
);
102
}
103
root
=
l
;
104
// Is there anything left?
105
if
(l == NULL)
106
return
home.
ES_SUBSUMED
(*
this
);
107
// Skip literal that already has a subscription
108
l = l->
next
();
109
// Create subscriptions for leafs
110
while
((l != NULL) && l->
leaf
()) {
111
l->
subscribe
(home,*
this
);
n
++;
112
l = l->
next
();
113
}
114
// Create subscription for possible non-leaf literal
115
if
(l != NULL) {
116
l->
subscribe
(home,*
this
);
n
++;
117
}
118
goto
restart;
119
}
120
case
NGL::NONE
:
121
break
;
122
default
:
GECODE_NEVER
;
123
}
124
125
{
126
NGL
*
p
=
root
;
127
NGL
*
l
= p->
next
();
128
129
// Check the leaves
130
while
((l != NULL) && l->
leaf
()) {
131
switch
(l->
status
(home)) {
132
case
NGL::SUBSUMED
:
133
l =
disposenext
(l,home,*
this
,
true
);
n
--;
134
p->
next
(l);
135
GECODE_ES_CHECK
(
root
->
prune
(home));
136
if
(
root
->
status
(home) ==
NGL::FAILED
)
137
return
home.
ES_SUBSUMED
(*
this
);
138
break
;
139
case
NGL::FAILED
:
140
l =
disposenext
(l,home,*
this
,
true
);
n
--;
141
p->
next
(l);
142
break
;
143
case
NGL::NONE
:
144
p =
l
; l = l->
next
();
145
break
;
146
default
:
GECODE_NEVER
;
147
}
148
}
149
150
// Check the next subtree
151
if
(l != NULL) {
152
switch
(l->
status
(home)) {
153
case
NGL::FAILED
:
154
(void)
disposenext
(l,home,*
this
,
true
);
n
--;
155
// Prune entire subtree
156
p->
next
(NULL);
157
break
;
158
case
NGL::SUBSUMED
:
159
{
160
// Unlink node
161
l =
disposenext
(l,home,*
this
,
true
);
n
--;
162
p->
next
(l);
163
// Create subscriptions
164
while
((l != NULL) && l->
leaf
()) {
165
l->
subscribe
(home,*
this
);
n
++;
166
l = l->
next
();
167
}
168
if
(l != NULL) {
169
l->
subscribe
(home,*
this
);
n
++;
170
}
171
}
172
break
;
173
case
NGL::NONE
:
174
break
;
175
default
:
GECODE_NEVER
;
176
}
177
}
178
}
179
return
ES_NOFIX
;
180
}
181
182
size_t
183
NoGoodsProp::dispose
(
Space
& home) {
184
if
(home.
failed
()) {
185
// This will be executed when one ngl returned true for notice()
186
NGL
*
l
=
root
;
187
while
(l != NULL) {
188
NGL
*
t
= l->
next
();
189
(void) l->
dispose
(home);
190
l =
t
;
191
}
192
}
else
if
(
root
!= NULL) {
193
// This will be executed for subsumption
194
NGL
*
l
=
disposenext
(
root
,home,*
this
,
true
);
195
while
((l != NULL) && l->
leaf
())
196
l =
disposenext
(l,home,*
this
,
true
);
197
if
(l != NULL)
198
l =
disposenext
(l,home,*
this
,
true
);
199
while
(l != NULL)
200
l =
disposenext
(l,home,*
this
,
false
);
201
}
202
home.
ignore
(*
this
,
AP_DISPOSE
,
true
);
203
(void)
Propagator::dispose
(home);
204
return
sizeof
(*this);
205
}
206
207
}}}
208
209
// STATISTICS: search-other