src/jalview/analysis/NJTree.java

   1 /*\r
   2 * Jalview - A Sequence Alignment Editor and Viewer\r
   3 * Copyright (C) 2005 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   4 *\r
   5 * This program is free software; you can redistribute it and/or\r
   6 * modify it under the terms of the GNU General Public License\r
   7 * as published by the Free Software Foundation; either version 2\r
   8 * of the License, or (at your option) any later version.\r
   9 *\r
  10 * This program is distributed in the hope that it will be useful,\r
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13 * GNU General Public License for more details.\r
  14 *\r
  15 * You should have received a copy of the GNU General Public License\r
  16 * along with this program; if not, write to the Free Software\r
  17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  18 */\r
  19 \r
  20 package jalview.analysis;\r
  21 \r
  22 import jalview.datamodel.*;\r
  23 import jalview.util.*;\r
  24 import jalview.schemes.ResidueProperties;\r
  25 import java.util.*;\r
  26 \r
  27 import jalview.io.NewickFile;\r
  28 \r
  29 public class NJTree {\r
  30 \r
  31   Vector cluster;\r
  32   SequenceI[] sequence;\r
  33 \r
  34   int done[];\r
  35   int noseqs;\r
  36   int noClus;\r
  37 \r
  38   float distance[][];\r
  39 \r
  40   int mini;\r
  41   int minj;\r
  42   float ri;\r
  43   float rj;\r
  44 \r
  45   Vector groups = new Vector();\r
  46   SequenceNode maxdist;\r
  47   SequenceNode top;\r
  48 \r
  49   float maxDistValue;\r
  50   float maxheight;\r
  51 \r
  52   int ycount;\r
  53 \r
  54   Vector node;\r
  55 \r
  56   String type;\r
  57   String pwtype;\r
  58 \r
  59   Object found = null;\r
  60   Object leaves = null;\r
  61 \r
  62   int start;\r
  63   int end;\r
  64 \r
  65   public NJTree(SequenceNode node) {\r
  66     top = node;\r
  67     maxheight = findHeight(top);\r
  68   }\r
  69 \r
  70   public String toString()\r
  71   {\r
  72     jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());\r
  73     return fout.print(false,true); // distances only\r
  74   }\r
  75 \r
  76   public NJTree(SequenceI[] seqs, NewickFile treefile) {\r
  77     top = treefile.getTree();\r
  78     maxheight = findHeight(top);\r
  79     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);\r
  80 \r
  81     Vector leaves = new Vector();\r
  82     findLeaves(top, leaves);\r
  83 \r
  84     int i = 0;\r
  85     int namesleft = seqs.length;\r
  86 \r
  87     SequenceNode j;\r
  88     SequenceI nam;\r
  89     String realnam;\r
  90     while (i < leaves.size())\r
  91     {\r
  92       j = (SequenceNode) leaves.elementAt(i++);\r
  93       realnam = j.getName();\r
  94       nam = null;\r
  95       if (namesleft>-1)\r
  96         nam = algnIds.findIdMatch(realnam);\r
  97       if (nam != null) {\r
  98         j.setElement(nam);\r
  99         namesleft--;\r
 100       } else {\r
 101         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));\r
 102         j.setPlaceholder(true);\r
 103 \r
 104       }\r
 105     }\r
 106   }\r
 107 \r
 108   /**\r
 109    *\r
 110    * used when the alignment associated to a tree has changed.\r
 111    *\r
 112    * @param alignment Vector\r
 113    */\r
 114   public void UpdatePlaceHolders(Vector alignment) {\r
 115     Vector leaves = new Vector();\r
 116     findLeaves(top, leaves);\r
 117     int sz = leaves.size();\r
 118     SequenceIdMatcher seqmatcher=null;\r
 119     int i=0;\r
 120     while (i<sz) {\r
 121       SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
 122       if (alignment.contains(leaf.element()))\r
 123         leaf.setPlaceholder(false);\r
 124       else {\r
 125         if (seqmatcher==null) {\r
 126           // Only create this the first time we need it\r
 127           SequenceI[] seqs = new SequenceI[alignment.size()];\r
 128           for (int j=0; j<seqs.length; j++)\r
 129             seqs[j] = (SequenceI) alignment.elementAt(j);\r
 130           seqmatcher = new SequenceIdMatcher(seqs);\r
 131         }\r
 132         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());\r
 133         if (nam!=null) {\r
 134           leaf.setPlaceholder(false);\r
 135           leaf.setElement(nam);\r
 136         } else {\r
 137           leaf.setPlaceholder(true);\r
 138         }\r
 139       }\r
 140     }\r
 141   }\r
 142 \r
 143   public NJTree(SequenceI[] sequence,int start, int end) {\r
 144     this(sequence,"NJ","BL",start,end);\r
 145   }\r
 146 \r
 147   public NJTree(SequenceI[] sequence,String type,String pwtype,int start, int end ) {\r
 148 \r
 149     this.sequence = sequence;\r
 150     this.node     = new Vector();\r
 151     this.type     = type;\r
 152     this.pwtype   = pwtype;\r
 153     this.start    = start;\r
 154     this.end      = end;\r
 155 \r
 156     if (!(type.equals("NJ"))) {\r
 157       type = "AV";\r
 158     }\r
 159 \r
 160     if (!(pwtype.equals("PID"))) {\r
 161       type = "BL";\r
 162     }\r
 163 \r
 164     int i=0;\r
 165 \r
 166     done = new int[sequence.length];\r
 167 \r
 168 \r
 169     while (i < sequence.length  && sequence[i] != null) {\r
 170       done[i] = 0;\r
 171       i++;\r
 172     }\r
 173 \r
 174     noseqs = i++;\r
 175 \r
 176     distance = findDistances();\r
 177 \r
 178     makeLeaves();\r
 179 \r
 180     noClus = cluster.size();\r
 181 \r
 182     cluster();\r
 183 \r
 184   }\r
 185 \r
 186 \r
 187   public void cluster() {\r
 188 \r
 189     while (noClus > 2) {\r
 190       if (type.equals("NJ")) {\r
 191         float mind = findMinNJDistance();\r
 192       } else {\r
 193         float mind = findMinDistance();\r
 194       }\r
 195 \r
 196       Cluster c = joinClusters(mini,minj);\r
 197 \r
 198 \r
 199       done[minj] = 1;\r
 200 \r
 201       cluster.setElementAt(null,minj);\r
 202       cluster.setElementAt(c,mini);\r
 203 \r
 204       noClus--;\r
 205     }\r
 206 \r
 207     boolean onefound = false;\r
 208 \r
 209     int one = -1;\r
 210     int two = -1;\r
 211 \r
 212     for (int i=0; i < noseqs; i++) {\r
 213       if (done[i] != 1) {\r
 214         if (onefound == false) {\r
 215           two = i;\r
 216           onefound = true;\r
 217         } else {\r
 218           one = i;\r
 219         }\r
 220       }\r
 221     }\r
 222 \r
 223     Cluster c = joinClusters(one,two);\r
 224     top = (SequenceNode)(node.elementAt(one));\r
 225 \r
 226     reCount(top);\r
 227     findHeight(top);\r
 228     findMaxDist(top);\r
 229 \r
 230   }\r
 231 \r
 232   public Cluster joinClusters(int i, int j) {\r
 233 \r
 234     float dist = distance[i][j];\r
 235 \r
 236     int noi = ((Cluster)cluster.elementAt(i)).value.length;\r
 237     int noj = ((Cluster)cluster.elementAt(j)).value.length;\r
 238 \r
 239     int[] value = new int[noi + noj];\r
 240 \r
 241     for (int ii = 0; ii < noi;ii++) {\r
 242       value[ii] =  ((Cluster)cluster.elementAt(i)).value[ii];\r
 243     }\r
 244 \r
 245     for (int ii = noi; ii < noi+ noj;ii++) {\r
 246       value[ii] =  ((Cluster)cluster.elementAt(j)).value[ii-noi];\r
 247     }\r
 248 \r
 249     Cluster c = new Cluster(value);\r
 250 \r
 251     ri = findr(i,j);\r
 252     rj = findr(j,i);\r
 253 \r
 254     if (type.equals("NJ")) {\r
 255       findClusterNJDistance(i,j);\r
 256     } else {\r
 257       findClusterDistance(i,j);\r
 258     }\r
 259 \r
 260     SequenceNode sn = new SequenceNode();\r
 261 \r
 262     sn.setLeft((SequenceNode)(node.elementAt(i)));\r
 263     sn.setRight((SequenceNode)(node.elementAt(j)));\r
 264 \r
 265     SequenceNode tmpi = (SequenceNode)(node.elementAt(i));\r
 266     SequenceNode tmpj = (SequenceNode)(node.elementAt(j));\r
 267 \r
 268     if (type.equals("NJ")) {\r
 269       findNewNJDistances(tmpi,tmpj,dist);\r
 270     } else {\r
 271       findNewDistances(tmpi,tmpj,dist);\r
 272     }\r
 273 \r
 274     tmpi.setParent(sn);\r
 275     tmpj.setParent(sn);\r
 276 \r
 277     node.setElementAt(sn,i);\r
 278     return c;\r
 279   }\r
 280 \r
 281   public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj, float dist) {\r
 282 \r
 283     float ih = 0;\r
 284     float jh = 0;\r
 285 \r
 286     SequenceNode sni = tmpi;\r
 287     SequenceNode snj = tmpj;\r
 288 \r
 289     tmpi.dist = (dist + ri - rj)/2;\r
 290     tmpj.dist = (dist - tmpi.dist);\r
 291 \r
 292     if (tmpi.dist < 0) {\r
 293       tmpi.dist = 0;\r
 294     }\r
 295     if (tmpj.dist < 0) {\r
 296       tmpj.dist = 0;\r
 297     }\r
 298   }\r
 299 \r
 300   public void findNewDistances(SequenceNode tmpi,SequenceNode tmpj,float dist) {\r
 301 \r
 302     float ih = 0;\r
 303     float jh = 0;\r
 304 \r
 305     SequenceNode sni = tmpi;\r
 306     SequenceNode snj = tmpj;\r
 307 \r
 308     while (sni != null) {\r
 309       ih = ih + sni.dist;\r
 310       sni = (SequenceNode)sni.left();\r
 311     }\r
 312 \r
 313     while (snj != null) {\r
 314       jh = jh + snj.dist;\r
 315       snj = (SequenceNode)snj.left();\r
 316     }\r
 317 \r
 318     tmpi.dist = (dist/2 - ih);\r
 319     tmpj.dist = (dist/2 - jh);\r
 320   }\r
 321 \r
 322 \r
 323 \r
 324   public void findClusterDistance(int i, int j) {\r
 325 \r
 326     int noi = ((Cluster)cluster.elementAt(i)).value.length;\r
 327     int noj = ((Cluster)cluster.elementAt(j)).value.length;\r
 328 \r
 329     // New distances from cluster to others\r
 330     float[] newdist = new float[noseqs];\r
 331 \r
 332     for (int l = 0; l < noseqs; l++) {\r
 333       if ( l != i && l != j) {\r
 334         newdist[l] = (distance[i][l] * noi + distance[j][l] * noj)/(noi + noj);\r
 335       } else {\r
 336         newdist[l] = 0;\r
 337       }\r
 338     }\r
 339 \r
 340     for (int ii=0; ii < noseqs;ii++) {\r
 341       distance[i][ii] = newdist[ii];\r
 342       distance[ii][i] = newdist[ii];\r
 343     }\r
 344   }\r
 345 \r
 346   public void findClusterNJDistance(int i, int j) {\r
 347 \r
 348     int noi = ((Cluster)cluster.elementAt(i)).value.length;\r
 349     int noj = ((Cluster)cluster.elementAt(j)).value.length;\r
 350 \r
 351     // New distances from cluster to others\r
 352     float[] newdist = new float[noseqs];\r
 353 \r
 354     for (int l = 0; l < noseqs; l++) {\r
 355       if ( l != i && l != j) {\r
 356         newdist[l] = (distance[i][l] + distance[j][l] - distance[i][j])/2;\r
 357       } else {\r
 358         newdist[l] = 0;\r
 359       }\r
 360     }\r
 361 \r
 362     for (int ii=0; ii < noseqs;ii++) {\r
 363       distance[i][ii] = newdist[ii];\r
 364       distance[ii][i] = newdist[ii];\r
 365     }\r
 366   }\r
 367 \r
 368   public float findr(int i, int j) {\r
 369 \r
 370     float tmp = 1;\r
 371     for (int k=0; k < noseqs;k++) {\r
 372       if (k!= i && k!= j && done[k] != 1) {\r
 373         tmp = tmp + distance[i][k];\r
 374       }\r
 375     }\r
 376 \r
 377     if (noClus > 2) {\r
 378       tmp = tmp/(noClus - 2);\r
 379     }\r
 380 \r
 381     return tmp;\r
 382   }\r
 383 \r
 384   public float findMinNJDistance() {\r
 385 \r
 386     float min = 100000;\r
 387 \r
 388     for (int i=0; i < noseqs-1; i++) {\r
 389       for (int j=i+1;j < noseqs;j++) {\r
 390         if (done[i] != 1 && done[j] != 1) {\r
 391           float tmp = distance[i][j] - (findr(i,j) + findr(j,i));\r
 392           if (tmp < min) {\r
 393 \r
 394             mini = i;\r
 395             minj = j;\r
 396 \r
 397             min = tmp;\r
 398 \r
 399           }\r
 400         }\r
 401       }\r
 402     }\r
 403     return min;\r
 404   }\r
 405 \r
 406   public float findMinDistance() {\r
 407 \r
 408     float min = 100000;\r
 409 \r
 410     for (int i=0; i < noseqs-1;i++) {\r
 411       for (int j = i+1; j < noseqs;j++) {\r
 412         if (done[i] != 1 && done[j] != 1) {\r
 413           if (distance[i][j] < min) {\r
 414             mini = i;\r
 415             minj = j;\r
 416 \r
 417             min = distance[i][j];\r
 418           }\r
 419         }\r
 420       }\r
 421     }\r
 422     return min;\r
 423   }\r
 424 \r
 425   public float[][] findDistances() {\r
 426 \r
 427     float[][] distance = new float[noseqs][noseqs];\r
 428     if (pwtype.equals("PID")) {\r
 429       for (int i = 0; i < noseqs-1; i++) {\r
 430         for (int j = i; j < noseqs; j++) {\r
 431           if (j==i) {\r
 432             distance[i][i] = 0;\r
 433           } else {\r
 434             distance[i][j] = 100-Comparison.PID(sequence[i], sequence[j], start, end);\r
 435             distance[j][i] = distance[i][j];\r
 436           }\r
 437         }\r
 438       }\r
 439     } else if (pwtype.equals("BL")) {\r
 440       int   maxscore = 0;\r
 441 \r
 442       for (int i = 0; i < noseqs-1; i++) {\r
 443         for (int j = i; j < noseqs; j++) {\r
 444           int score = 0;\r
 445           for (int k=start; k < end; k++) {\r
 446             try{\r
 447               score +=\r
 448                   ResidueProperties.getBLOSUM62(sequence[i].getSequence(k,\r
 449                   k + 1),\r
 450                                                 sequence[j].getSequence(k,\r
 451                   k + 1));\r
 452             }catch(Exception ex){System.err.println("err creating BLOSUM62 tree");ex.printStackTrace();}\r
 453           }\r
 454           distance[i][j] = (float)score;\r
 455           if (score > maxscore) {\r
 456             maxscore = score;\r
 457           }\r
 458         }\r
 459       }\r
 460       for (int i = 0; i < noseqs-1; i++) {\r
 461         for (int j = i; j < noseqs; j++) {\r
 462           distance[i][j] =  (float)maxscore - distance[i][j];\r
 463           distance[j][i] = distance[i][j];\r
 464         }\r
 465       }\r
 466     } else if (pwtype.equals("SW")) {\r
 467       float max = -1;\r
 468       for (int i = 0; i < noseqs-1; i++) {\r
 469         for (int j = i; j < noseqs; j++) {\r
 470           AlignSeq as = new AlignSeq(sequence[i],sequence[j],"pep");\r
 471           as.calcScoreMatrix();\r
 472           as.traceAlignment();\r
 473           as.printAlignment();\r
 474           distance[i][j] = (float)as.maxscore;\r
 475           if (max < distance[i][j]) {\r
 476             max = distance[i][j];\r
 477           }\r
 478         }\r
 479       }\r
 480       for (int i = 0; i < noseqs-1; i++) {\r
 481         for (int j = i; j < noseqs; j++) {\r
 482           distance[i][j] =  max - distance[i][j];\r
 483           distance[j][i] = distance[i][j];\r
 484         }\r
 485       }\r
 486     }\r
 487 \r
 488     return distance;\r
 489   }\r
 490 \r
 491   public void makeLeaves() {\r
 492     cluster = new Vector();\r
 493 \r
 494     for (int i=0; i < noseqs; i++) {\r
 495       SequenceNode sn = new SequenceNode();\r
 496 \r
 497       sn.setElement(sequence[i]);\r
 498       sn.setName(sequence[i].getName());\r
 499       node.addElement(sn);\r
 500 \r
 501       int[] value = new int[1];\r
 502       value[0] = i;\r
 503 \r
 504       Cluster c = new Cluster(value);\r
 505       cluster.addElement(c);\r
 506     }\r
 507   }\r
 508 \r
 509   public Vector findLeaves(SequenceNode node, Vector leaves) {\r
 510     if (node == null) {\r
 511       return leaves;\r
 512     }\r
 513 \r
 514     if (node.left() == null && node.right() == null) {\r
 515       leaves.addElement(node);\r
 516       return leaves;\r
 517     } else {\r
 518       findLeaves((SequenceNode)node.left(),leaves);\r
 519       findLeaves((SequenceNode)node.right(),leaves);\r
 520     }\r
 521     return leaves;\r
 522   }\r
 523 \r
 524   public Object findLeaf(SequenceNode node, int count) {\r
 525     found = _findLeaf(node,count);\r
 526 \r
 527     return found;\r
 528   }\r
 529   public Object _findLeaf(SequenceNode node,int count) {\r
 530     if (node == null) {\r
 531       return null;\r
 532     }\r
 533     if (node.ycount == count) {\r
 534       found = node.element();\r
 535       return found;\r
 536     } else {\r
 537       _findLeaf((SequenceNode)node.left(),count);\r
 538       _findLeaf((SequenceNode)node.right(),count);\r
 539     }\r
 540 \r
 541     return found;\r
 542   }\r
 543 \r
 544   /**\r
 545    * printNode is mainly for debugging purposes.\r
 546    *\r
 547    * @param node SequenceNode\r
 548    */\r
 549   public void printNode(SequenceNode node) {\r
 550     if (node == null) {\r
 551       return;\r
 552     }\r
 553     if (node.left() == null && node.right() == null) {\r
 554       System.out.println("Leaf = " + ((SequenceI)node.element()).getName());\r
 555       System.out.println("Dist " + ((SequenceNode)node).dist);\r
 556       System.out.println("Boot " + node.getBootstrap());\r
 557     } else {\r
 558       System.out.println("Dist " + ((SequenceNode)node).dist);\r
 559       printNode((SequenceNode)node.left());\r
 560       printNode((SequenceNode)node.right());\r
 561     }\r
 562   }\r
 563   public void findMaxDist(SequenceNode node) {\r
 564     if (node == null) {\r
 565       return;\r
 566     }\r
 567     if (node.left() == null && node.right() == null) {\r
 568 \r
 569       float dist = ((SequenceNode)node).dist;\r
 570       if (dist > maxDistValue) {\r
 571           maxdist      = (SequenceNode)node;\r
 572           maxDistValue = dist;\r
 573       }\r
 574     } else {\r
 575       findMaxDist((SequenceNode)node.left());\r
 576       findMaxDist((SequenceNode)node.right());\r
 577     }\r
 578   }\r
 579     public Vector getGroups() {\r
 580         return groups;\r
 581     }\r
 582     public float getMaxHeight() {\r
 583         return maxheight;\r
 584     }\r
 585   public void  groupNodes(SequenceNode node, float threshold) {\r
 586     if (node == null) {\r
 587       return;\r
 588     }\r
 589 \r
 590     if (node.height/maxheight > threshold) {\r
 591       groups.addElement(node);\r
 592     } else {\r
 593       groupNodes((SequenceNode)node.left(),threshold);\r
 594       groupNodes((SequenceNode)node.right(),threshold);\r
 595     }\r
 596   }\r
 597 \r
 598   public float findHeight(SequenceNode node) {\r
 599 \r
 600     if (node == null) {\r
 601       return maxheight;\r
 602     }\r
 603 \r
 604     if (node.left() == null && node.right() == null) {\r
 605       node.height = ((SequenceNode)node.parent()).height + node.dist;\r
 606 \r
 607       if (node.height > maxheight) {\r
 608         return node.height;\r
 609       } else {\r
 610         return maxheight;\r
 611       }\r
 612     } else {\r
 613       if (node.parent() != null) {\r
 614         node.height = ((SequenceNode)node.parent()).height + node.dist;\r
 615       } else {\r
 616         maxheight = 0;\r
 617         node.height = (float)0.0;\r
 618       }\r
 619 \r
 620       maxheight = findHeight((SequenceNode)(node.left()));\r
 621       maxheight = findHeight((SequenceNode)(node.right()));\r
 622     }\r
 623     return maxheight;\r
 624   }\r
 625   public SequenceNode reRoot() {\r
 626     if (maxdist != null) {\r
 627       ycount = 0;\r
 628       float tmpdist = maxdist.dist;\r
 629 \r
 630       // New top\r
 631       SequenceNode sn = new SequenceNode();\r
 632       sn.setParent(null);\r
 633 \r
 634       // New right hand of top\r
 635       SequenceNode snr = (SequenceNode)maxdist.parent();\r
 636       changeDirection(snr,maxdist);\r
 637       System.out.println("Printing reversed tree");\r
 638       printN(snr);\r
 639       snr.dist = tmpdist/2;\r
 640       maxdist.dist = tmpdist/2;\r
 641 \r
 642       snr.setParent(sn);\r
 643       maxdist.setParent(sn);\r
 644 \r
 645       sn.setRight(snr);\r
 646       sn.setLeft(maxdist);\r
 647 \r
 648       top = sn;\r
 649 \r
 650       ycount = 0;\r
 651       reCount(top);\r
 652       findHeight(top);\r
 653 \r
 654     }\r
 655     return top;\r
 656   }\r
 657   public static void printN(SequenceNode node) {\r
 658     if (node == null) {\r
 659       return;\r
 660     }\r
 661 \r
 662     if (node.left() != null && node.right() != null) {\r
 663       printN((SequenceNode)node.left());\r
 664       printN((SequenceNode)node.right());\r
 665     } else {\r
 666       System.out.println(" name = " + ((SequenceI)node.element()).getName());\r
 667     }\r
 668     System.out.println(" dist = " + ((SequenceNode)node).dist + " " + ((SequenceNode)node).count + " " + ((SequenceNode)node).height);\r
 669   }\r
 670 \r
 671     public void reCount(SequenceNode node) {\r
 672         ycount = 0;\r
 673         _reCount(node);\r
 674     }\r
 675   public void _reCount(SequenceNode node) {\r
 676     if (node == null) {\r
 677       return;\r
 678     }\r
 679 \r
 680     if (node.left() != null && node.right() != null) {\r
 681       _reCount((SequenceNode)node.left());\r
 682       _reCount((SequenceNode)node.right());\r
 683 \r
 684       SequenceNode l = (SequenceNode)node.left();\r
 685       SequenceNode r = (SequenceNode)node.right();\r
 686 \r
 687       ((SequenceNode)node).count  = l.count + r.count;\r
 688       ((SequenceNode)node).ycount = (l.ycount + r.ycount)/2;\r
 689 \r
 690     } else {\r
 691       ((SequenceNode)node).count = 1;\r
 692       ((SequenceNode)node).ycount = ycount++;\r
 693     }\r
 694 \r
 695   }\r
 696     public void swapNodes(SequenceNode node) {\r
 697         if (node == null) {\r
 698             return;\r
 699         }\r
 700         SequenceNode tmp = (SequenceNode)node.left();\r
 701 \r
 702         node.setLeft(node.right());\r
 703         node.setRight(tmp);\r
 704     }\r
 705   public void changeDirection(SequenceNode node, SequenceNode dir) {\r
 706     if (node == null) {\r
 707       return;\r
 708     }\r
 709     if (node.parent() != top) {\r
 710       changeDirection((SequenceNode)node.parent(), node);\r
 711 \r
 712       SequenceNode tmp = (SequenceNode)node.parent();\r
 713 \r
 714       if (dir == node.left()) {\r
 715         node.setParent(dir);\r
 716         node.setLeft(tmp);\r
 717       } else if (dir == node.right()) {\r
 718         node.setParent(dir);\r
 719         node.setRight(tmp);\r
 720       }\r
 721 \r
 722     } else {\r
 723       if (dir == node.left()) {\r
 724         node.setParent(node.left());\r
 725 \r
 726         if (top.left() == node) {\r
 727           node.setRight(top.right());\r
 728         } else {\r
 729           node.setRight(top.left());\r
 730         }\r
 731       } else {\r
 732         node.setParent(node.right());\r
 733 \r
 734         if (top.left() == node) {\r
 735           node.setLeft(top.right());\r
 736         } else {\r
 737           node.setLeft(top.left());\r
 738         }\r
 739       }\r
 740     }\r
 741   }\r
 742     public void setMaxDist(SequenceNode node) {\r
 743         this.maxdist = maxdist;\r
 744     }\r
 745     public SequenceNode getMaxDist() {\r
 746         return maxdist;\r
 747     }\r
 748     public SequenceNode getTopNode() {\r
 749         return top;\r
 750     }\r
 751 \r
 752 }\r
 753 \r
 754 \r
 755 \r
 756 class Cluster {\r
 757 \r
 758   int[] value;\r
 759 \r
 760   public Cluster(int[] value) {\r
 761     this.value = value;\r
 762   }\r
 763 \r
 764 }\r
 765 \r