[1573] | 1 | // SimpleNode.java |
---|
| 2 | // |
---|
| 3 | // (c) 1999-2001 PAL Development Core Team |
---|
| 4 | // |
---|
| 5 | // This package may be distributed under the |
---|
| 6 | // terms of the Lesser GNU General Public License (LGPL) |
---|
| 7 | |
---|
| 8 | |
---|
| 9 | package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; |
---|
| 10 | |
---|
| 11 | |
---|
| 12 | import java.util.ArrayList; |
---|
| 13 | |
---|
| 14 | import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; |
---|
| 15 | import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; |
---|
| 16 | import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.LabelMapping; |
---|
| 17 | |
---|
| 18 | |
---|
| 19 | /** |
---|
| 20 | * data structure for a node (includes branch) in a binary/non-binary |
---|
| 21 | * rooted/unrooted tree |
---|
| 22 | * |
---|
| 23 | * @version $Id: SimpleNode.java,v 1.20 2002/01/14 04:16:53 matt Exp $ |
---|
| 24 | * |
---|
| 25 | * @author Korbinian Strimmer |
---|
| 26 | * @author Alexei Drummond |
---|
| 27 | */ |
---|
| 28 | public class FengDoolittleNode implements Node { |
---|
| 29 | |
---|
| 30 | /** parent node */ |
---|
| 31 | private Node parent; |
---|
| 32 | |
---|
| 33 | /** number of node as displayed */ |
---|
| 34 | private int number; |
---|
| 35 | |
---|
| 36 | /** sequences associated with node */ |
---|
| 37 | private ArrayList<NumberSequence> sequences; |
---|
| 38 | |
---|
| 39 | /** length of branch to parent node */ |
---|
| 40 | private double length; |
---|
| 41 | |
---|
| 42 | /** standard error of length of branch to parent node */ |
---|
| 43 | private double lengthSE; |
---|
| 44 | |
---|
| 45 | /** height of this node */ |
---|
| 46 | private double height; |
---|
| 47 | |
---|
| 48 | /** identifier of node/associated branch */ |
---|
| 49 | private Identifier identifier; |
---|
| 50 | |
---|
| 51 | private Node[] child; |
---|
| 52 | |
---|
| 53 | // the following constructors should eventually become |
---|
| 54 | // "friendly" to prevent anyone calling them directly. |
---|
| 55 | // Instead, the NodeFactory should be used! |
---|
| 56 | |
---|
| 57 | /** constructor default node */ |
---|
| 58 | public FengDoolittleNode() |
---|
| 59 | { |
---|
| 60 | parent = null; |
---|
| 61 | child = null; |
---|
| 62 | length = 0.0; |
---|
| 63 | lengthSE = 0.0; |
---|
| 64 | height = 0.0; |
---|
| 65 | identifier = Identifier.ANONYMOUS; |
---|
| 66 | |
---|
| 67 | number = 0; |
---|
| 68 | sequences = new ArrayList<NumberSequence>(); |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | public FengDoolittleNode(String name, double branchLength) { |
---|
| 72 | this(); |
---|
| 73 | identifier = new Identifier(name); |
---|
| 74 | length = branchLength; |
---|
| 75 | } |
---|
| 76 | |
---|
| 77 | |
---|
| 78 | public void reset() |
---|
| 79 | { |
---|
| 80 | parent = null; |
---|
| 81 | child = null; |
---|
| 82 | length = 0.0; |
---|
| 83 | lengthSE = 0.0; |
---|
| 84 | height = 0.0; |
---|
| 85 | identifier = Identifier.ANONYMOUS; |
---|
| 86 | |
---|
| 87 | number = 0; |
---|
| 88 | sequences = null; |
---|
| 89 | } |
---|
| 90 | |
---|
| 91 | public FengDoolittleNode(Node n, boolean keepIds) { |
---|
| 92 | init(n, keepIds); |
---|
| 93 | for (int i = 0; i < n.getChildCount(); i++) { |
---|
| 94 | addChild(new FengDoolittleNode(n.getChild(i), keepIds)); |
---|
| 95 | } |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | public FengDoolittleNode(Node n, LabelMapping lm) { |
---|
| 99 | init(n, true, lm); |
---|
| 100 | for (int i = 0; i < n.getChildCount(); i++) { |
---|
| 101 | addChild(new FengDoolittleNode(n.getChild(i), lm)); |
---|
| 102 | } |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | |
---|
| 106 | /** constructor used to clone a node and all children */ |
---|
| 107 | public FengDoolittleNode(Node n) |
---|
| 108 | { |
---|
| 109 | this(n, true); |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | |
---|
| 113 | |
---|
| 114 | protected void init(Node n) { |
---|
| 115 | init(n, true); |
---|
| 116 | } |
---|
| 117 | /** |
---|
| 118 | * Initialized node instance variables based on given Node. |
---|
| 119 | * children are ignored. |
---|
| 120 | */ |
---|
| 121 | protected void init(Node n, boolean keepId) { |
---|
| 122 | init(n,keepId,null); |
---|
| 123 | } |
---|
| 124 | /** |
---|
| 125 | * Initialized node instance variables based on given Node. |
---|
| 126 | * children are ignored. |
---|
| 127 | * @param lm - may be null |
---|
| 128 | */ |
---|
| 129 | protected void init(Node n, boolean keepId, LabelMapping lm) { |
---|
| 130 | parent = null; |
---|
| 131 | length = n.getBranchLength(); |
---|
| 132 | lengthSE = n.getBranchLengthSE(); |
---|
| 133 | height = n.getNodeHeight(); |
---|
| 134 | if (keepId) { |
---|
| 135 | if(lm!=null) { |
---|
| 136 | identifier = lm.getLabelIdentifier(n.getIdentifier()); |
---|
| 137 | } else { |
---|
| 138 | identifier = n.getIdentifier(); |
---|
| 139 | } |
---|
| 140 | } else { identifier = Identifier.ANONYMOUS; } |
---|
| 141 | |
---|
| 142 | number = n.getNumber(); |
---|
| 143 | sequences = n.getSequences(); |
---|
| 144 | child = null; |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | /** |
---|
| 148 | * Returns the parent node of this node. |
---|
| 149 | */ |
---|
| 150 | public final Node getParent() { |
---|
| 151 | return parent; |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | /** Set the parent node of this node. */ |
---|
| 155 | public void setParent(Node node) |
---|
| 156 | { |
---|
| 157 | parent = node; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | /** |
---|
| 161 | * removes parent. |
---|
| 162 | */ |
---|
| 163 | public final void removeParent() { |
---|
| 164 | parent = null; |
---|
| 165 | } |
---|
| 166 | |
---|
[1577] | 167 | public void addSequence(NumberSequence s) { |
---|
| 168 | sequences.add(s); |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | |
---|
[1573] | 172 | /** |
---|
| 173 | * Returns the sequence at this node, in the form of a String. |
---|
| 174 | */ |
---|
| 175 | public String getSequenceString(int index) { |
---|
| 176 | return sequences.get(index).getSequence().toString(); |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | /** |
---|
| 180 | * Returns the sequence at this node, in the form of an array of bytes. |
---|
| 181 | */ |
---|
| 182 | public NumberSequence getSequence(int index) { |
---|
| 183 | return sequences.get(index); |
---|
| 184 | } |
---|
| 185 | |
---|
| 186 | /** |
---|
| 187 | * Sets the sequence at this node, in the form of an array of bytes. |
---|
| 188 | */ |
---|
| 189 | public void setSequence(int index,NumberSequence s) { |
---|
| 190 | sequences.set(index, s); |
---|
| 191 | } |
---|
| 192 | |
---|
| 193 | /** |
---|
| 194 | * Get the length of the branch attaching this node to its parent. |
---|
| 195 | */ |
---|
| 196 | public final double getBranchLength() { |
---|
| 197 | return length; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | /** |
---|
| 201 | * Set the length of the branch attaching this node to its parent. |
---|
| 202 | */ |
---|
| 203 | public final void setBranchLength(double value) { |
---|
| 204 | length = value; |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | /** |
---|
| 208 | * Get the length SE of the branch attaching this node to its parent. |
---|
| 209 | */ |
---|
| 210 | public final double getBranchLengthSE() { |
---|
| 211 | return lengthSE; |
---|
| 212 | } |
---|
| 213 | |
---|
| 214 | /** |
---|
| 215 | * Set the length SE of the branch attaching this node to its parent. |
---|
| 216 | */ |
---|
| 217 | public final void setBranchLengthSE(double value) { |
---|
| 218 | lengthSE = value; |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | |
---|
| 222 | /** |
---|
| 223 | * Get the height of this node relative to the most recent node. |
---|
| 224 | */ |
---|
| 225 | public final double getNodeHeight() { |
---|
| 226 | return height; |
---|
| 227 | } |
---|
| 228 | |
---|
| 229 | /** |
---|
| 230 | * Set the height of this node relative to the most recent node. |
---|
| 231 | */ |
---|
| 232 | public final void setNodeHeight(double value) { |
---|
| 233 | height = Math.abs(value); |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | /** |
---|
| 237 | * Returns the identifier for this node. |
---|
| 238 | */ |
---|
| 239 | public final Identifier getIdentifier() { |
---|
| 240 | return identifier; |
---|
| 241 | } |
---|
| 242 | |
---|
| 243 | /** |
---|
| 244 | * Set identifier for this node. |
---|
| 245 | */ |
---|
| 246 | public final Identifier setIdentifier(Identifier id) { |
---|
| 247 | identifier = id; |
---|
| 248 | return identifier; |
---|
| 249 | } |
---|
| 250 | |
---|
| 251 | public void setNumber(int n) { |
---|
| 252 | number = n; |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | public int getNumber() { |
---|
| 256 | return number; |
---|
| 257 | } |
---|
| 258 | |
---|
| 259 | /** |
---|
| 260 | * get child node |
---|
| 261 | * |
---|
| 262 | * @param n number of child |
---|
| 263 | * |
---|
| 264 | * @return child node |
---|
| 265 | */ |
---|
| 266 | public Node getChild(int n) |
---|
| 267 | { |
---|
| 268 | return child[n]; |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | /** |
---|
| 272 | * set child node |
---|
| 273 | * |
---|
| 274 | * @param n number |
---|
| 275 | * @node node new child node |
---|
| 276 | */ |
---|
| 277 | public void setChild(int n, Node node) |
---|
| 278 | { |
---|
| 279 | child[n] = node; |
---|
| 280 | child[n].setParent(this); |
---|
| 281 | } |
---|
| 282 | |
---|
| 283 | /** |
---|
| 284 | * check whether this node is an internal node |
---|
| 285 | * |
---|
| 286 | * @return result (true or false) |
---|
| 287 | */ |
---|
| 288 | public boolean hasChildren() |
---|
| 289 | { |
---|
| 290 | return !isLeaf(); |
---|
| 291 | } |
---|
| 292 | |
---|
| 293 | /** |
---|
| 294 | * check whether this node is an external node |
---|
| 295 | * |
---|
| 296 | * @return result (true or false) |
---|
| 297 | */ |
---|
| 298 | public boolean isLeaf() { |
---|
| 299 | return (getChildCount() == 0); |
---|
| 300 | } |
---|
| 301 | |
---|
| 302 | /** |
---|
| 303 | * check whether this node is a root node |
---|
| 304 | * |
---|
| 305 | * @return result (true or false) |
---|
| 306 | */ |
---|
| 307 | public boolean isRoot() |
---|
| 308 | { |
---|
| 309 | if (parent == null) |
---|
| 310 | { |
---|
| 311 | return true; |
---|
| 312 | } |
---|
| 313 | else |
---|
| 314 | { |
---|
| 315 | return false; |
---|
| 316 | } |
---|
| 317 | } |
---|
| 318 | |
---|
| 319 | |
---|
| 320 | /** |
---|
| 321 | * add new child node |
---|
| 322 | * |
---|
| 323 | * @param n new child node |
---|
| 324 | */ |
---|
| 325 | public void addChild(Node n) |
---|
| 326 | { |
---|
| 327 | insertChild(n, getChildCount()); |
---|
| 328 | } |
---|
| 329 | |
---|
| 330 | /** |
---|
| 331 | * add new child node (insertion at a specific position) |
---|
| 332 | * |
---|
| 333 | * @param n new child node |
---|
| 334 | + @param pos position |
---|
| 335 | */ |
---|
| 336 | public void insertChild(Node n, int pos) |
---|
| 337 | { |
---|
| 338 | int numChildren = getChildCount(); |
---|
| 339 | |
---|
| 340 | Node[] newChild = new Node[numChildren + 1]; |
---|
| 341 | |
---|
| 342 | for (int i = 0; i < pos; i++) |
---|
| 343 | { |
---|
| 344 | newChild[i] = child[i]; |
---|
| 345 | } |
---|
| 346 | newChild[pos] = n; |
---|
| 347 | for (int i = pos; i < numChildren; i++) |
---|
| 348 | { |
---|
| 349 | newChild[i+1] = child[i]; |
---|
| 350 | } |
---|
| 351 | |
---|
| 352 | child = newChild; |
---|
| 353 | |
---|
| 354 | n.setParent(this); |
---|
| 355 | } |
---|
| 356 | |
---|
| 357 | |
---|
| 358 | /** |
---|
| 359 | * remove child |
---|
| 360 | * |
---|
| 361 | * @param n number of child to be removed |
---|
| 362 | */ |
---|
| 363 | public Node removeChild(int n) |
---|
| 364 | { |
---|
| 365 | int numChildren = getChildCount(); |
---|
| 366 | |
---|
| 367 | if (n >= numChildren) |
---|
| 368 | { |
---|
| 369 | throw new IllegalArgumentException("Nonexistent child"); |
---|
| 370 | } |
---|
| 371 | Node[] newChild = new Node[numChildren-1]; |
---|
| 372 | |
---|
| 373 | for (int i = 0; i < n; i++) |
---|
| 374 | { |
---|
| 375 | newChild[i] = child[i]; |
---|
| 376 | } |
---|
| 377 | |
---|
| 378 | for (int i = n; i < numChildren-1; i++) |
---|
| 379 | { |
---|
| 380 | newChild[i] = child[i+1]; |
---|
| 381 | } |
---|
| 382 | |
---|
| 383 | Node removed = child[n]; |
---|
| 384 | |
---|
| 385 | //remove parent link from removed child! |
---|
| 386 | removed.setParent(null); |
---|
| 387 | |
---|
| 388 | child = newChild; |
---|
| 389 | |
---|
| 390 | return removed; |
---|
| 391 | } |
---|
| 392 | |
---|
| 393 | |
---|
| 394 | |
---|
| 395 | /** |
---|
| 396 | * join two children, introducing a new node/branch in the tree |
---|
| 397 | * that replaces the first child |
---|
| 398 | * |
---|
| 399 | * @param n1 number of first child |
---|
| 400 | * @param n2 number of second child |
---|
| 401 | */ |
---|
| 402 | public void joinChildren( int n1, int n2) { |
---|
| 403 | |
---|
| 404 | if (n1 == n2) { |
---|
| 405 | throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT"); |
---|
| 406 | } |
---|
| 407 | |
---|
| 408 | int c1, c2; |
---|
| 409 | if (n2 < n1) |
---|
| 410 | { |
---|
| 411 | c1 = n2; |
---|
| 412 | c2 = n1; |
---|
| 413 | } |
---|
| 414 | else |
---|
| 415 | { |
---|
| 416 | c1 = n1; |
---|
| 417 | c2 = n2; |
---|
| 418 | } |
---|
| 419 | |
---|
| 420 | Node newNode = NodeFactory.createNode(); |
---|
| 421 | |
---|
| 422 | Node child1 = this.getChild(c1); |
---|
| 423 | Node child2 = this.getChild(c2); |
---|
| 424 | |
---|
| 425 | setChild(c1, newNode); |
---|
| 426 | newNode.setParent(this); |
---|
| 427 | this.removeChild(c2); // now parent of child2 = null |
---|
| 428 | |
---|
| 429 | newNode.addChild(child1); |
---|
| 430 | newNode.addChild(child2); |
---|
[1577] | 431 | newNode.setIdentifier(new Identifier(child1.getIdentifier().getName() + " " + child2.getIdentifier().getName())); |
---|
| 432 | System.out.println("Merging " + child1.getIdentifier() + " with " + child2.getIdentifier()); |
---|
[1573] | 433 | |
---|
| 434 | if(newNode instanceof FengDoolittleNode) { |
---|
| 435 | ((FengDoolittleNode) newNode).alignSequences(); |
---|
| 436 | } |
---|
| 437 | |
---|
| 438 | } |
---|
| 439 | |
---|
| 440 | |
---|
| 441 | /** |
---|
| 442 | * Returns the number of children this node has. |
---|
| 443 | */ |
---|
| 444 | public final int getChildCount() { |
---|
| 445 | if (child == null) return 0; |
---|
| 446 | return child.length; |
---|
| 447 | } |
---|
| 448 | |
---|
| 449 | |
---|
| 450 | public ArrayList<NumberSequence> getSequences() { |
---|
| 451 | return sequences; |
---|
| 452 | } |
---|
| 453 | |
---|
| 454 | |
---|
| 455 | private void alignSequences() { |
---|
| 456 | if(this.getChildCount()<3) { |
---|
| 457 | |
---|
| 458 | Node node1 = getChild(0); |
---|
| 459 | Node node2 = getChild(1); |
---|
| 460 | |
---|
| 461 | int seqCount1 = node1.getSequences().size(); |
---|
| 462 | int seqCount2 = node2.getSequences().size(); |
---|
| 463 | |
---|
| 464 | |
---|
| 465 | |
---|
| 466 | } |
---|
| 467 | else { |
---|
| 468 | |
---|
| 469 | } |
---|
| 470 | |
---|
| 471 | } |
---|
| 472 | |
---|
| 473 | |
---|
| 474 | } |
---|