src/jalview/datamodel/BinaryNode.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.datamodel;
  22
  23 import java.awt.Color;
  24
  25 /**
  26  * Represent a node in a binary tree
  27  *
  28  * @author $mclamp (probably!)$
  29  * @version $Revision$
  30  */
  31 public class BinaryNode<T>
  32 {
  33   T element;
  34
  35   String name;
  36
  37   BinaryNode<T> left;
  38
  39   BinaryNode<T> right;
  40
  41   BinaryNode<T> parent;
  42
  43   /** Bootstrap value */
  44   public int bootstrap;
  45
  46   /** DOCUMENT ME!! */
  47   public double dist;
  48
  49   /** DOCUMENT ME!! */
  50   public int count;
  51
  52   /** DOCUMENT ME!! */
  53   public double height;
  54
  55   /** DOCUMENT ME!! */
  56   public float ycount;
  57
  58   /** DOCUMENT ME!! */
  59   public Color color = Color.black;
  60
  61   /**
  62    * if true, node is created to simulate polytomy between parent and its 3 or
  63    * more children
  64    */
  65   public boolean dummy = false;
  66
  67   /**
  68    * Creates a new BinaryNode object.
  69    */
  70   public BinaryNode()
  71   {
  72     left = right = parent = null;
  73     bootstrap = 0;
  74     dist = 0;
  75   }
  76
  77   /**
  78    * Creates a new BinaryNode object.
  79    *
  80    * @param element
  81    *          DOCUMENT ME!
  82    * @param parent
  83    *          DOCUMENT ME!
  84    * @param name
  85    *          DOCUMENT ME!
  86    */
  87   public BinaryNode(T element, BinaryNode<T> parent, String name,
  88           double dist)
  89   {
  90     this();
  91     this.element = element;
  92     this.parent = parent;
  93     this.name = name;
  94     this.dist = dist;
  95   }
  96
  97   public BinaryNode(T element, BinaryNode<T> parent, String name,
  98           double dist, int bootstrap)
  99   {
 100     this(element, parent, name, dist);
 101     this.bootstrap = bootstrap;
 102   }
 103
 104   public BinaryNode(T val, BinaryNode<T> parent, String name, double dist,
 105           int bootstrap, boolean dummy)
 106   {
 107     this(val, parent, name, dist, bootstrap);
 108     this.dummy = dummy;
 109   }
 110
 111   /**
 112    * DOCUMENT ME!
 113    *
 114    * @return DOCUMENT ME!
 115    */
 116   public T element()
 117   {
 118     return element;
 119   }
 120
 121   /**
 122    * DOCUMENT ME!
 123    *
 124    * @param v
 125    *          DOCUMENT ME!
 126    *
 127    * @return DOCUMENT ME!
 128    */
 129   public T setElement(T v)
 130   {
 131     return element = v;
 132   }
 133
 134   /**
 135    * DOCUMENT ME!
 136    *
 137    * @return DOCUMENT ME!
 138    */
 139   public BinaryNode<T> left()
 140   {
 141     return left;
 142   }
 143
 144   /**
 145    * DOCUMENT ME!
 146    *
 147    * @param n
 148    *          DOCUMENT ME!
 149    *
 150    * @return DOCUMENT ME!
 151    */
 152   public BinaryNode<T> setLeft(BinaryNode<T> n)
 153   {
 154     return left = n;
 155   }
 156
 157   /**
 158    * DOCUMENT ME!
 159    *
 160    * @return DOCUMENT ME!
 161    */
 162   public BinaryNode<T> right()
 163   {
 164     return right;
 165   }
 166
 167   /**
 168    * DOCUMENT ME!
 169    *
 170    * @param n
 171    *          DOCUMENT ME!
 172    *
 173    * @return DOCUMENT ME!
 174    */
 175   public BinaryNode<T> setRight(BinaryNode<T> n)
 176   {
 177     return right = n;
 178   }
 179
 180   /**
 181    * DOCUMENT ME!
 182    *
 183    * @return DOCUMENT ME!
 184    */
 185   public BinaryNode<T> parent()
 186   {
 187     return parent;
 188   }
 189
 190   /**
 191    * DOCUMENT ME!
 192    *
 193    * @param n
 194    *          DOCUMENT ME!
 195    *
 196    * @return DOCUMENT ME!
 197    */
 198   public BinaryNode<T> setParent(BinaryNode<T> n)
 199   {
 200     return parent = n;
 201   }
 202
 203   /**
 204    * DOCUMENT ME!
 205    *
 206    * @return DOCUMENT ME!
 207    */
 208   public boolean isLeaf()
 209   {
 210     return (left == null) && (right == null);
 211   }
 212
 213   /**
 214    * attaches FIRST and SECOND node arguments as the LEFT and RIGHT children of
 215    * this node (removing any old references) a null parameter DOES NOT mean that
 216    * the pointer to the corresponding child node is set to NULL - you should use
 217    * setChild(null), or detach() for this.
 218    *
 219    */
 220   public void SetChildren(BinaryNode<T> leftchild, BinaryNode<T> rightchild)
 221   {
 222     if (leftchild != null)
 223     {
 224       this.setLeft(leftchild);
 225       leftchild.detach();
 226       leftchild.setParent(this);
 227     }
 228
 229     if (rightchild != null)
 230     {
 231       this.setRight(rightchild);
 232       rightchild.detach();
 233       rightchild.setParent(this);
 234     }
 235   }
 236
 237   /**
 238    * Detaches the node from the binary tree, along with all its child nodes.
 239    *
 240    * @return BinaryNode The detached node.
 241    */
 242   public BinaryNode<T> detach()
 243   {
 244     if (this.parent != null)
 245     {
 246       if (this.parent.left == this)
 247       {
 248         this.parent.left = null;
 249       }
 250       else
 251       {
 252         if (this.parent.right == this)
 253         {
 254           this.parent.right = null;
 255         }
 256       }
 257     }
 258
 259     this.parent = null;
 260
 261     return this;
 262   }
 263
 264   /**
 265    * Traverses up through the tree until a node with a free leftchild is
 266    * discovered.
 267    *
 268    * @return BinaryNode
 269    */
 270   public BinaryNode<T> ascendLeft()
 271   {
 272     BinaryNode<T> c = this;
 273
 274     do
 275     {
 276       c = c.parent();
 277     } while ((c != null) && (c.left() != null) && !c.left().isLeaf());
 278
 279     return c;
 280   }
 281
 282   /**
 283    * Traverses up through the tree until a node with a free rightchild is
 284    * discovered. Jalview builds trees by descent on the left, so this may be
 285    * unused.
 286    *
 287    * @return BinaryNode
 288    */
 289   public BinaryNode<T> ascendRight()
 290   {
 291     BinaryNode<T> c = this;
 292
 293     do
 294     {
 295       c = c.parent();
 296     } while ((c != null) && (c.right() != null) && !c.right().isLeaf());
 297
 298     return c;
 299   }
 300
 301   /**
 302    *
 303    * set the display name
 304    *
 305    * @param new
 306    *          name
 307    */
 308   public void setName(String name)
 309   {
 310     this.name = name;
 311   }
 312
 313   /**
 314    *
 315    *
 316    * @return the display name for this node
 317    */
 318   public String getName()
 319   {
 320     return this.name;
 321   }
 322
 323   /**
 324    * set integer bootstrap value
 325    *
 326    * @param boot
 327    */
 328   public void setBootstrap(int boot)
 329   {
 330     this.bootstrap = boot;
 331   }
 332
 333   /**
 334    * get bootstrap
 335    *
 336    * @return integer value
 337    */
 338   public int getBootstrap()
 339   {
 340     return bootstrap;
 341   }
 342
 343   /**
 344    * @param dummy
 345    *          true if node is created for the representation of polytomous trees
 346    */
 347   public boolean isDummy()
 348   {
 349     return dummy;
 350   }
 351
 352   /**
 353    * DOCUMENT ME!
 354    *
 355    * @param newstate
 356    *          DOCUMENT ME!
 357    *
 358    * @return DOCUMENT ME!
 359    */
 360   public boolean setDummy(boolean newstate)
 361   {
 362     boolean oldstate = dummy;
 363     dummy = newstate;
 364
 365     return oldstate;
 366   }
 367
 368   /**
 369    * ascends the tree but doesn't stop until a non-dummy node is discovered.
 370    *
 371    */
 372   public BinaryNode<T> AscendTree()
 373   {
 374     BinaryNode<T> c = this;
 375
 376     do
 377     {
 378       c = c.parent();
 379     } while ((c != null) && c.dummy);
 380
 381     return c;
 382   }
 383 }