this repo has no description
dekker.one
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Search {
35
36 forceinline
37 NoNGL::NoNGL(void) {}
38
39 forceinline
40 NoNGL::NoNGL(Space& home)
41 : NGL(home) {}
42
43 forceinline
44 NoNGL::NoNGL(Space& home, NoNGL& ngl)
45 : NGL(home,ngl) {}
46
47
48
49 forceinline
50 NoGoodsProp::NoGoodsProp(Space& home, NGL* root0)
51 : Propagator(Home(home)), root(root0), n(0U) {
52 // Create subscriptions
53 root->subscribe(home,*this); n++;
54 bool notice = root->notice();
55 NGL* l = root->next();
56 while ((l != nullptr) && l->leaf()) {
57 l->subscribe(home,*this); n++;
58 notice = notice || l->notice();
59 l = l->next();
60 }
61 if (l != nullptr) {
62 l->subscribe(home,*this); n++;
63 }
64 while (!notice && (l != nullptr)) {
65 notice = notice || l->notice();
66 l = l->next();
67 }
68 if (notice)
69 home.notice(*this,AP_DISPOSE);
70 }
71
72 forceinline
73 NoGoodsProp::NoGoodsProp(Space& home, NoGoodsProp& p)
74 : Propagator(home,p), n(p.n) {
75 assert(p.root != nullptr);
76 NoNGL s;
77 NGL* c = &s;
78 for (NGL* pc = p.root; pc != nullptr; pc = pc->next()) {
79 NGL* n = pc->copy(home);
80 n->leaf(pc->leaf());
81 c->next(n); c=n;
82 }
83 root = s.next();
84 }
85
86
87
88 template<class Path>
89 forceinline ExecStatus
90 NoGoodsProp::post(Space& home, const Path& p) {
91 int s = 0;
92 int n = std::min(p.ds.entries(),static_cast<int>(p.ngdl()));
93
94 unsigned long int n_nogood = 0;
95
96 // Eliminate the alternatives which are not no-goods at the end
97 while ((n > s) && (p.ds[n-1].truealt() == 0U))
98 n--;
99
100 // A sentinel element
101 NoNGL nn;
102 // Current no-good literal
103 NGL* c = &nn;
104
105 // Commit no-goods at the beginning
106 while ((s < n) && (p.ds[s].truealt() > 0U))
107 // Try whether this is a rightmost alternative
108 if (p.ds[s].rightmost()) {
109 // No literal needed, directly try to commit
110 home.trycommit(*p.ds[s].choice(),p.ds[s].truealt());
111 s++;
112 } else {
113 // Prune using no-good literals
114 for (unsigned int a=0U; a<p.ds[s].truealt(); a++) {
115 NGL* l = home.ngl(*p.ds[s].choice(),a);
116 // Does the brancher support no-good literals?
117 if (l == nullptr)
118 return ES_OK;
119 GECODE_ES_CHECK(l->prune(home));
120 }
121 // Add literal as root if needed and stop
122 if (NGL* l = home.ngl(*p.ds[s].choice(),p.ds[s].truealt())) {
123 c = c->add(l,false);
124 s++; break;
125 }
126 }
127
128 // There are no literals
129 if (home.failed())
130 return ES_FAILED;
131 if (s >= n)
132 return ES_OK;
133
134 // There must be at least two literals
135 assert((n-s > 1) ||
136 ((n-s == 1) && (c != &nn)));
137
138 // Remember the last leaf
139 NGL* ll = nullptr;
140
141 // Create literals
142 for (int i=s; i<n; i++) {
143 // Add leaves
144 for (unsigned int a=0U; a<p.ds[i].truealt(); a++) {
145 NGL* l = home.ngl(*p.ds[i].choice(),a);
146 if (l == nullptr) {
147 // The brancher does not support no-goods
148 if (ll == nullptr)
149 return ES_OK;
150 ll->next(nullptr);
151 break;
152 }
153 c = c->add(l,true); ll = c;
154 n_nogood++;
155 }
156 // Check whether to add an additional subtree
157 if (NGL* l = home.ngl(*p.ds[i].choice(),p.ds[i].truealt())) {
158 c = c->add(l,false);
159 } else if (!p.ds[i].rightmost()) {
160 // The brancher does not support no-goods
161 if (ll == nullptr)
162 return ES_OK;
163 ll->next(nullptr);
164 break;
165 }
166 }
167
168 const_cast<Path&>(p).ng(n_nogood);
169
170 (void) new (home) NoGoodsProp(home,nn.next());
171 return ES_OK;
172 }
173
174}}
175
176// STATISTICS: search-other