1 /*
2  * BNode.java
3  * This file is part of JaCoP.
4  * <p>
5  * JaCoP is a Java Constraint Programming solver.
6  * <p>
7  * Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
8  * <p>
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU Affero General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  * <p>
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU Affero General Public License for more details.
18  * <p>
19  * Notwithstanding any other provision of this License, the copyright
20  * owners of this work supplement the terms of this License with terms
21  * prohibiting misrepresentation of the origin of this work and requiring
22  * that modified versions of this work be marked in reasonable ways as
23  * different from the original version. This supplement of the license
24  * terms is in accordance with Section 7 of GNU Affero General Public
25  * License version 3.
26  * <p>
27  * You should have received a copy of the GNU Affero General Public License
28  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
29  */
30 
31 package org.jacop.floats.constraints.linear;
32 
33 /**
34  * Binary Node of the tree representing linear constraint.
35  *
36  * @author Krzysztof Kuchcinski
37  * @version 4.8
38  */
39 
40 import org.jacop.core.Store;
41 import org.jacop.floats.core.FloatDomain;
42 
43 public class BNode extends BinaryNode {
44 
45     // bounds for this node
46     BoundsVar bound;
47 
BNode(Store store)48     public BNode(Store store) {
49         id = n.incrementAndGet();
50         bound = new BoundsVar(store);
51     }
52 
BNode(Store store, double min, double max)53     public BNode(Store store, double min, double max) {
54         id = n.incrementAndGet();
55         bound = new BoundsVar(store, min, max);
56     }
57 
BNode(Store store, double min, double max, double lb, double ub)58     public BNode(Store store, double min, double max, double lb, double ub) {
59         id = n.incrementAndGet();
60         bound = new BoundsVar(store, min, max, lb, ub);
61     }
62 
63 
propagate()64     void propagate() {
65 
66         FloatDomain d = FloatDomain.addBounds(left.min(), left.max(), right.min(), right.max());
67         double min = d.min();
68         double max = d.max();
69 
70         d = FloatDomain.addBounds(left.lb(), left.ub(), right.lb(), right.ub());
71         double lb = d.min();
72         double ub = d.max();
73 
74         double node_min = min();
75         double node_max = max();
76 
77         if (min > node_min)
78             if (max < node_max) {
79 
80                 if (min > max)
81                     throw Store.failException;
82 
83                 updateBounds(min, max, lb, ub);
84 
85                 parent.propagate();
86 
87             } else {
88 
89                 if (min > node_max)
90                     throw Store.failException;
91 
92                 updateBounds(min, node_max, lb, ub);
93 
94                 parent.propagate();
95 
96             }
97         else if (max < node_max) {
98 
99             if (node_min > max)
100                 throw Store.failException;
101 
102             updateBounds(node_min, max, lb, ub);
103 
104             parent.propagate();
105 
106         } else {  // no change in the domain but it was called since the children have been changed;
107             // do prune and do not contine to propagate
108 
109             return;
110         }
111     }
112 
propagateAndPrune()113     void propagateAndPrune() {
114 
115         FloatDomain d = FloatDomain.addBounds(left.min(), left.max(), right.min(), right.max());
116         double min = d.min();
117         double max = d.max();
118 
119         double node_min = min();
120         double node_max = max();
121 
122         d = FloatDomain.addBounds(left.lb(), left.ub(), right.lb(), right.ub());
123         double lb = d.min();
124         double ub = d.max();
125 
126         if (min > node_min)
127             if (max < node_max) {
128 
129                 if (min > max)
130                     throw Store.failException;
131 
132                 updateBounds(min, max, lb, ub);
133 
134                 prune(min, max);
135 
136                 parent.propagateAndPrune();
137 
138             } else {
139 
140                 if (min > node_max)
141                     throw Store.failException;
142 
143                 updateBounds(min, node_max, lb, ub);
144 
145                 prune(min, node_max);
146 
147                 parent.propagateAndPrune();
148 
149             }
150         else if (max < node_max) {
151 
152             if (node_min > max)
153                 throw Store.failException;
154 
155             updateBounds(node_min, max, lb, ub);
156 
157             prune(node_min, max);
158 
159             parent.propagateAndPrune();
160 
161         } else {  // no change in the domain but it was called since the children have been changed;
162             // do prune and do not contine to propagate
163 
164             prune(node_min, node_max);
165 
166             return;
167         }
168 
169     }
170 
prune()171     void prune() {
172 
173         double min = min();
174         double max = max();
175 
176         prune(min, max);
177 
178     }
179 
prune(double min, double max)180     void prune(double min, double max) {
181 
182         boolean left_changed = false, right_changed = false;
183 
184         left_changed = pruneNode(min, max, left, right);
185 
186         right_changed = pruneNode(min, max, right, left);
187 
188         if (left_changed)
189             left.prune();
190         if (right_changed)
191             right.prune();
192     }
193 
pruneNode(double min, double max, BinaryNode node, BinaryNode sibling)194     boolean pruneNode(double min, double max, BinaryNode node, BinaryNode sibling) {
195 
196         double node_min = node.min();
197         double node_max = node.max();
198 
199         double sibling_min = sibling.min();
200         double sibling_max = sibling.max();
201 
202         FloatDomain bound = FloatDomain.subBounds(min, max, sibling_min, sibling_max);
203         double new_node_min = bound.min();
204         double new_node_max = bound.max();
205 
206         double lb = node.lb();
207         double ub = node.ub();
208 
209         if (new_node_min > node_min)
210             if (new_node_max < node_max) {
211 
212                 if (new_node_min > new_node_max)
213                     throw Store.failException;
214 
215                 node.updateBounds(new_node_min, new_node_max, lb, ub);
216 
217                 return true;
218             } else {
219 
220                 if (new_node_min > node_max)
221                     throw Store.failException;
222 
223                 node.updateBounds(new_node_min, node_max, lb, ub);
224 
225                 return true;
226             }
227         else if (new_node_max < node_max) {
228 
229             if (node_min > new_node_max)
230                 throw Store.failException;
231 
232             node.updateBounds(node_min, new_node_max, lb, ub);
233 
234             return true;
235         } else {
236 
237             return false;
238         }
239     }
240 
min()241     double min() {
242         return ((BoundsVarValue) bound.value()).min;
243     }
244 
max()245     double max() {
246         return ((BoundsVarValue) bound.value()).max;
247     }
248 
lb()249     double lb() {
250         return ((BoundsVarValue) bound.value()).lb;
251     }
252 
ub()253     double ub() {
254         return ((BoundsVarValue) bound.value()).ub;
255     }
256 
updateBounds(double min, double max, double lb, double ub)257     void updateBounds(double min, double max, double lb, double ub) {
258         bound.update(min, max, lb, ub);
259     }
260 
toString()261     public String toString() {
262         return super.toString() + "(" + bound.stamp() + ")" + " : " + bound;
263     }
264 
265 }
266