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