src/jalview/datamodel/Alignment.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.7)
   3  * Copyright (C) 2011 J Procter, AM Waterhouse, J Engelhardt, LM Lui, G Barton, M Clamp, S Searle
   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 of the License, or (at your option) any later version.
  10  *
  11  * Jalview is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14  * PURPOSE.  See the GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 package jalview.datamodel;
  19
  20 import java.util.*;
  21
  22 import jalview.analysis.*;
  23
  24 /**
  25  * Data structure to hold and manipulate a multiple sequence alignment
  26  */
  27 /**
  28  * @author JimP
  29  *
  30  */
  31 public class Alignment implements AlignmentI
  32 {
  33   protected Alignment dataset;
  34
  35   protected Vector sequences;
  36
  37   protected Vector groups = new Vector();
  38
  39   protected char gapCharacter = '-';
  40
  41   protected int type = NUCLEOTIDE;
  42
  43   public static final int PROTEIN = 0;
  44
  45   public static final int NUCLEOTIDE = 1;
  46
  47   public boolean hasRNAStructure = false;
  48
  49   /** DOCUMENT ME!! */
  50   public AlignmentAnnotation[] annotations;
  51
  52   HiddenSequences hiddenSequences = new HiddenSequences(this);
  53
  54   public Hashtable alignmentProperties;
  55
  56   private void initAlignment(SequenceI[] seqs)
  57   {
  58     int i = 0;
  59
  60     if (jalview.util.Comparison.isNucleotide(seqs))
  61     {
  62       type = NUCLEOTIDE;
  63     }
  64     else
  65     {
  66       type = PROTEIN;
  67     }
  68
  69     sequences = new Vector();
  70
  71     for (i = 0; i < seqs.length; i++)
  72     {
  73       sequences.addElement(seqs[i]);
  74     }
  75
  76   }
  77
  78   /**
  79    * Make an alignment from an array of Sequences.
  80    *
  81    * @param sequences
  82    */
  83   public Alignment(SequenceI[] seqs)
  84   {
  85     initAlignment(seqs);
  86   }
  87
  88   /**
  89    * Make a new alignment from an array of SeqCigars
  90    *
  91    * @param seqs
  92    *          SeqCigar[]
  93    */
  94   public Alignment(SeqCigar[] alseqs)
  95   {
  96     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
  97             gapCharacter, new ColumnSelection(), null);
  98     initAlignment(seqs);
  99   }
 100
 101   /**
 102    * Make a new alignment from an CigarArray JBPNote - can only do this when
 103    * compactAlignment does not contain hidden regions. JBPNote - must also check
 104    * that compactAlignment resolves to a set of SeqCigars - or construct them
 105    * appropriately.
 106    *
 107    * @param compactAlignment
 108    *          CigarArray
 109    */
 110   public static AlignmentI createAlignment(CigarArray compactAlignment)
 111   {
 112     throw new Error("Alignment(CigarArray) not yet implemented");
 113     // this(compactAlignment.refCigars);
 114   }
 115
 116   /**
 117    * DOCUMENT ME!
 118    *
 119    * @return DOCUMENT ME!
 120    */
 121   public Vector getSequences()
 122   {
 123     return sequences;
 124   }
 125   @Override
 126   public List<SequenceI> getSequences(
 127           Map<SequenceI, SequenceCollectionI> hiddenReps)
 128   {
 129     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to work on this.
 130     return sequences;
 131   }
 132
 133   public SequenceI[] getSequencesArray()
 134   {
 135     if (sequences == null)
 136       return null;
 137     SequenceI[] reply = new SequenceI[sequences.size()];
 138     for (int i = 0; i < sequences.size(); i++)
 139     {
 140       reply[i] = (SequenceI) sequences.elementAt(i);
 141     }
 142     return reply;
 143   }
 144
 145   /**
 146    * DOCUMENT ME!
 147    *
 148    * @param i
 149    *          DOCUMENT ME!
 150    *
 151    * @return DOCUMENT ME!
 152    */
 153   public SequenceI getSequenceAt(int i)
 154   {
 155     if (i>-1 && i < sequences.size())
 156     {
 157       return (SequenceI) sequences.elementAt(i);
 158     }
 159
 160     return null;
 161   }
 162
 163   /**
 164    * Adds a sequence to the alignment. Recalculates maxLength and size.
 165    *
 166    * @param snew
 167    */
 168   public void addSequence(SequenceI snew)
 169   {
 170     if (dataset != null)
 171     {
 172       // maintain dataset integrity
 173       if (snew.getDatasetSequence() != null)
 174       {
 175         getDataset().addSequence(snew.getDatasetSequence());
 176       }
 177       else
 178       {
 179         // derive new sequence
 180         SequenceI adding = snew.deriveSequence();
 181         getDataset().addSequence(adding.getDatasetSequence());
 182         snew = adding;
 183       }
 184     }
 185     if (sequences == null)
 186     {
 187       initAlignment(new SequenceI[]
 188       { snew });
 189     }
 190     else
 191     {
 192       sequences.addElement(snew);
 193     }
 194     if (hiddenSequences != null)
 195       hiddenSequences.adjustHeightSequenceAdded();
 196   }
 197
 198   /**
 199    * Adds a sequence to the alignment. Recalculates maxLength and size.
 200    *
 201    * @param snew
 202    */
 203   public void setSequenceAt(int i, SequenceI snew)
 204   {
 205     SequenceI oldseq = getSequenceAt(i);
 206     deleteSequence(oldseq);
 207
 208     sequences.setElementAt(snew, i);
 209   }
 210
 211   /**
 212    * DOCUMENT ME!
 213    *
 214    * @return DOCUMENT ME!
 215    */
 216   public Vector getGroups()
 217   {
 218     return groups;
 219   }
 220
 221   public void finalize()
 222   {
 223     if (getDataset() != null)
 224       getDataset().removeAlignmentRef();
 225
 226     dataset = null;
 227     sequences = null;
 228     groups = null;
 229     annotations = null;
 230     hiddenSequences = null;
 231   }
 232
 233   /**
 234    * decrement the alignmentRefs counter by one and call finalize if it goes to
 235    * zero.
 236    */
 237   private void removeAlignmentRef()
 238   {
 239     if (--alignmentRefs == 0)
 240     {
 241       finalize();
 242     }
 243   }
 244
 245   /**
 246    * DOCUMENT ME!
 247    *
 248    * @param s
 249    *          DOCUMENT ME!
 250    */
 251   public void deleteSequence(SequenceI s)
 252   {
 253     deleteSequence(findIndex(s));
 254   }
 255
 256   /**
 257    * DOCUMENT ME!
 258    *
 259    * @param i
 260    *          DOCUMENT ME!
 261    */
 262   public void deleteSequence(int i)
 263   {
 264     if (i > -1 && i < getHeight())
 265     {
 266       sequences.removeElementAt(i);
 267       hiddenSequences.adjustHeightSequenceDeleted(i);
 268     }
 269   }
 270
 271   /**    */
 272   public SequenceGroup findGroup(SequenceI s)
 273   {
 274     for (int i = 0; i < this.groups.size(); i++)
 275     {
 276       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
 277
 278       if (sg.getSequences(null).contains(s))
 279       {
 280         return sg;
 281       }
 282     }
 283
 284     return null;
 285   }
 286
 287   /**
 288    * DOCUMENT ME!
 289    *
 290    * @param s
 291    *          DOCUMENT ME!
 292    *
 293    * @return DOCUMENT ME!
 294    */
 295   public SequenceGroup[] findAllGroups(SequenceI s)
 296   {
 297     Vector temp = new Vector();
 298
 299     int gSize = groups.size();
 300     for (int i = 0; i < gSize; i++)
 301     {
 302       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
 303       if (sg == null || sg.getSequences(null) == null)
 304       {
 305         this.deleteGroup(sg);
 306         gSize--;
 307         continue;
 308       }
 309
 310       if (sg.getSequences(null).contains(s))
 311       {
 312         temp.addElement(sg);
 313       }
 314     }
 315
 316     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 317
 318     for (int i = 0; i < temp.size(); i++)
 319     {
 320       ret[i] = (SequenceGroup) temp.elementAt(i);
 321     }
 322
 323     return ret;
 324   }
 325
 326   /**    */
 327   public void addGroup(SequenceGroup sg)
 328   {
 329     if (!groups.contains(sg))
 330     {
 331       if (hiddenSequences.getSize() > 0)
 332       {
 333         int i, iSize = sg.getSize();
 334         for (i = 0; i < iSize; i++)
 335         {
 336           if (!sequences.contains(sg.getSequenceAt(i)))
 337           {
 338             sg.deleteSequence(sg.getSequenceAt(i), false);
 339             iSize--;
 340             i--;
 341           }
 342         }
 343
 344         if (sg.getSize() < 1)
 345         {
 346           return;
 347         }
 348       }
 349
 350       groups.addElement(sg);
 351     }
 352   }
 353
 354   /**
 355    * remove any annotation that references gp
 356    *
 357    * @param gp
 358    *          (if null, removes all group associated annotation)
 359    */
 360   private void removeAnnotationForGroup(SequenceGroup gp)
 361   {
 362     if (annotations == null || annotations.length == 0)
 363     {
 364       return;
 365     }
 366     // remove annotation very quickly
 367     AlignmentAnnotation[] t, todelete = new AlignmentAnnotation[annotations.length], tokeep = new AlignmentAnnotation[annotations.length];
 368     int i, p, k;
 369     if (gp == null)
 370     {
 371       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 372       {
 373         if (annotations[i].groupRef != null)
 374         {
 375           todelete[p++] = annotations[i];
 376         }
 377         else
 378         {
 379           tokeep[k++] = annotations[i];
 380         }
 381       }
 382     }
 383     else
 384     {
 385       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 386       {
 387         if (annotations[i].groupRef == gp)
 388         {
 389           todelete[p++] = annotations[i];
 390         }
 391         else
 392         {
 393           tokeep[k++] = annotations[i];
 394         }
 395       }
 396     }
 397     if (p > 0)
 398     {
 399       // clear out the group associated annotation.
 400       for (i = 0; i < p; i++)
 401       {
 402         unhookAnnotation(todelete[i]);
 403         todelete[i] = null;
 404       }
 405       t = new AlignmentAnnotation[k];
 406       for (i = 0; i < k; i++)
 407       {
 408         t[i] = tokeep[i];
 409       }
 410       annotations = t;
 411     }
 412   }
 413
 414   public void deleteAllGroups()
 415   {
 416     if (annotations != null)
 417     {
 418       removeAnnotationForGroup(null);
 419     }
 420     groups.removeAllElements();
 421   }
 422
 423   /**    */
 424   public void deleteGroup(SequenceGroup g)
 425   {
 426     if (groups.contains(g))
 427     {
 428       removeAnnotationForGroup(g);
 429       groups.removeElement(g);
 430     }
 431   }
 432
 433   /**    */
 434   public SequenceI findName(String name)
 435   {
 436     return findName(name, false);
 437   }
 438
 439   /*
 440    * (non-Javadoc)
 441    *
 442    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 443    */
 444   public SequenceI findName(String token, boolean b)
 445   {
 446     return findName(null, token, b);
 447   }
 448
 449   /*
 450    * (non-Javadoc)
 451    *
 452    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 453    * boolean)
 454    */
 455   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 456   {
 457
 458     int i = 0;
 459     SequenceI sq = null;
 460     String sqname = null;
 461     if (startAfter != null)
 462     {
 463       // try to find the sequence in the alignment
 464       boolean matched = false;
 465       while (i < sequences.size())
 466       {
 467         if (getSequenceAt(i++) == startAfter)
 468         {
 469           matched = true;
 470           break;
 471         }
 472       }
 473       if (!matched)
 474       {
 475         i = 0;
 476       }
 477     }
 478     while (i < sequences.size())
 479     {
 480       sq = getSequenceAt(i);
 481       sqname = sq.getName();
 482       if (sqname.equals(token) // exact match
 483               || (b && // allow imperfect matches - case varies
 484               (sqname.equalsIgnoreCase(token))))
 485       {
 486         return getSequenceAt(i);
 487       }
 488
 489       i++;
 490     }
 491
 492     return null;
 493   }
 494
 495   public SequenceI[] findSequenceMatch(String name)
 496   {
 497     Vector matches = new Vector();
 498     int i = 0;
 499
 500     while (i < sequences.size())
 501     {
 502       if (getSequenceAt(i).getName().equals(name))
 503       {
 504         matches.addElement(getSequenceAt(i));
 505       }
 506       i++;
 507     }
 508
 509     SequenceI[] result = new SequenceI[matches.size()];
 510     for (i = 0; i < result.length; i++)
 511     {
 512       result[i] = (SequenceI) matches.elementAt(i);
 513     }
 514
 515     return result;
 516
 517   }
 518
 519   /*
 520    * (non-Javadoc)
 521    *
 522    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 523    */
 524   public int findIndex(SequenceI s)
 525   {
 526     int i = 0;
 527
 528     while (i < sequences.size())
 529     {
 530       if (s == getSequenceAt(i))
 531       {
 532         return i;
 533       }
 534
 535       i++;
 536     }
 537
 538     return -1;
 539   }
 540
 541   /*
 542    * (non-Javadoc)
 543    *
 544    * @see
 545    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 546    */
 547   public int findIndex(SearchResults results)
 548   {
 549     int i = 0;
 550
 551     while (i < sequences.size())
 552     {
 553       if (results.involvesSequence(getSequenceAt(i)))
 554       {
 555         return i;
 556       }
 557       i++;
 558     }
 559     return -1;
 560   }
 561
 562   /**
 563    * DOCUMENT ME!
 564    *
 565    * @return DOCUMENT ME!
 566    */
 567   public int getHeight()
 568   {
 569     return sequences.size();
 570   }
 571
 572   /**
 573    * DOCUMENT ME!
 574    *
 575    * @return DOCUMENT ME!
 576    */
 577   public int getWidth()
 578   {
 579     int maxLength = -1;
 580
 581     for (int i = 0; i < sequences.size(); i++)
 582     {
 583       if (getSequenceAt(i).getLength() > maxLength)
 584       {
 585         maxLength = getSequenceAt(i).getLength();
 586       }
 587     }
 588
 589     return maxLength;
 590   }
 591
 592   /**
 593    * DOCUMENT ME!
 594    *
 595    * @param gc
 596    *          DOCUMENT ME!
 597    */
 598   public void setGapCharacter(char gc)
 599   {
 600     gapCharacter = gc;
 601
 602     for (int i = 0; i < sequences.size(); i++)
 603     {
 604       Sequence seq = (Sequence) sequences.elementAt(i);
 605       seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 606               .replace('-', gc).replace(' ', gc));
 607     }
 608   }
 609
 610   /**
 611    * DOCUMENT ME!
 612    *
 613    * @return DOCUMENT ME!
 614    */
 615   public char getGapCharacter()
 616   {
 617     return gapCharacter;
 618   }
 619
 620   /*
 621    * (non-Javadoc)
 622    *
 623    * @see jalview.datamodel.AlignmentI#isAligned()
 624    */
 625   public boolean isAligned()
 626   {
 627     return isAligned(false);
 628   }
 629
 630   /*
 631    * (non-Javadoc)
 632    *
 633    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 634    */
 635   public boolean isAligned(boolean includeHidden)
 636   {
 637     int width = getWidth();
 638     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 639     {
 640       includeHidden = true; // no hidden sequences to check against.
 641     }
 642     for (int i = 0; i < sequences.size(); i++)
 643     {
 644       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 645       {
 646         if (getSequenceAt(i).getLength() != width)
 647         {
 648           return false;
 649         }
 650       }
 651     }
 652
 653     return true;
 654   }
 655
 656   /*
 657    * (non-Javadoc)
 658    *
 659    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 660    * AlignmentAnnotation)
 661    */
 662   public boolean deleteAnnotation(AlignmentAnnotation aa)
 663   {
 664     return deleteAnnotation(aa, true);
 665   }
 666
 667   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 668   {
 669     int aSize = 1;
 670
 671     if (annotations != null)
 672     {
 673       aSize = annotations.length;
 674     }
 675
 676     if (aSize < 1)
 677     {
 678       return false;
 679     }
 680
 681     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 682
 683     boolean swap = false;
 684     int tIndex = 0;
 685
 686     for (int i = 0; i < aSize; i++)
 687     {
 688       if (annotations[i] == aa)
 689       {
 690         swap = true;
 691         continue;
 692       }
 693       if (tIndex < temp.length)
 694         temp[tIndex++] = annotations[i];
 695     }
 696
 697     if (swap)
 698     {
 699       annotations = temp;
 700       if (unhook) {
 701         unhookAnnotation(aa);
 702       }
 703     }
 704     return swap;
 705   }
 706
 707   /**
 708    * remove any object references associated with this annotation
 709    *
 710    * @param aa
 711    */
 712   private void unhookAnnotation(AlignmentAnnotation aa)
 713   {
 714     if (aa.sequenceRef != null)
 715     {
 716       aa.sequenceRef.removeAlignmentAnnotation(aa);
 717     }
 718     if (aa.groupRef != null)
 719     {
 720       // probably need to do more here in the future (post 2.5.0)
 721       aa.groupRef = null;
 722     }
 723   }
 724
 725   /*
 726    * (non-Javadoc)
 727    *
 728    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 729    * AlignmentAnnotation)
 730    */
 731   public void addAnnotation(AlignmentAnnotation aa)
 732   {
 733     addAnnotation(aa, -1);
 734   }
 735
 736   /*
 737    * (non-Javadoc)
 738    *
 739    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 740    * AlignmentAnnotation, int)
 741    */
 742   public void addAnnotation(AlignmentAnnotation aa, int pos)
 743   {
 744     if(aa.getRNAStruc()!= null){
 745       hasRNAStructure=true;
 746     }
 747
 748     int aSize = 1;
 749     if (annotations != null)
 750     {
 751       aSize = annotations.length + 1;
 752     }
 753
 754     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 755     int i = 0;
 756     if (pos == -1 || pos >= aSize)
 757     {
 758       temp[aSize - 1] = aa;
 759     }
 760     else
 761     {
 762       temp[pos] = aa;
 763     }
 764     if (aSize > 1)
 765     {
 766       int p = 0;
 767       for (i = 0; i < (aSize - 1); i++, p++)
 768       {
 769         if (p == pos)
 770         {
 771           p++;
 772         }
 773         if (p < temp.length)
 774         {
 775           temp[p] = annotations[i];
 776         }
 777       }
 778     }
 779
 780     annotations = temp;
 781   }
 782
 783   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 784   {
 785     if (aa == null || annotations == null || annotations.length - 1 < index)
 786     {
 787       return;
 788     }
 789
 790     int aSize = annotations.length;
 791     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 792
 793     temp[index] = aa;
 794
 795     for (int i = 0; i < aSize; i++)
 796     {
 797       if (i == index)
 798       {
 799         continue;
 800       }
 801
 802       if (i < index)
 803       {
 804         temp[i] = annotations[i];
 805       }
 806       else
 807       {
 808         temp[i] = annotations[i - 1];
 809       }
 810     }
 811
 812     annotations = temp;
 813   }
 814
 815   @Override
 816   /**
 817    * returns all annotation on the alignment
 818    */
 819   public AlignmentAnnotation[] getAlignmentAnnotation()
 820   {
 821     return annotations;
 822   }
 823
 824   public void setNucleotide(boolean b)
 825   {
 826     if (b)
 827     {
 828       type = NUCLEOTIDE;
 829     }
 830     else
 831     {
 832       type = PROTEIN;
 833     }
 834   }
 835
 836   public boolean isNucleotide()
 837   {
 838     if (type == NUCLEOTIDE)
 839     {
 840       return true;
 841     }
 842     else
 843     {
 844       return false;
 845     }
 846   }
 847
 848   public boolean hasRNAStructure(){
 849     //TODO can it happen that structure is removed from alignment?
 850     return hasRNAStructure;
 851   }
 852
 853   public void setDataset(Alignment data)
 854   {
 855     if (dataset == null && data == null)
 856     {
 857       // Create a new dataset for this alignment.
 858       // Can only be done once, if dataset is not null
 859       // This will not be performed
 860       SequenceI[] seqs = new SequenceI[getHeight()];
 861       SequenceI currentSeq;
 862       for (int i = 0; i < getHeight(); i++)
 863       {
 864         currentSeq = getSequenceAt(i);
 865         if (currentSeq.getDatasetSequence() != null)
 866         {
 867           seqs[i] = (Sequence) currentSeq.getDatasetSequence();
 868         }
 869         else
 870         {
 871           seqs[i] = currentSeq.createDatasetSequence();
 872         }
 873       }
 874
 875       dataset = new Alignment(seqs);
 876     }
 877     else if (dataset == null && data != null)
 878     {
 879       dataset = data;
 880     }
 881     dataset.addAlignmentRef();
 882   }
 883
 884   /**
 885    * reference count for number of alignments referencing this one.
 886    */
 887   int alignmentRefs = 0;
 888
 889   /**
 890    * increase reference count to this alignment.
 891    */
 892   private void addAlignmentRef()
 893   {
 894     alignmentRefs++;
 895   }
 896
 897   public Alignment getDataset()
 898   {
 899     return dataset;
 900   }
 901
 902   public boolean padGaps()
 903   {
 904     boolean modified = false;
 905
 906     // Remove excess gaps from the end of alignment
 907     int maxLength = -1;
 908
 909     SequenceI current;
 910     for (int i = 0; i < sequences.size(); i++)
 911     {
 912       current = getSequenceAt(i);
 913       for (int j = current.getLength(); j > maxLength; j--)
 914       {
 915         if (j > maxLength
 916                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
 917         {
 918           maxLength = j;
 919           break;
 920         }
 921       }
 922     }
 923
 924     maxLength++;
 925
 926     int cLength;
 927     for (int i = 0; i < sequences.size(); i++)
 928     {
 929       current = getSequenceAt(i);
 930       cLength = current.getLength();
 931
 932       if (cLength < maxLength)
 933       {
 934         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
 935         modified = true;
 936       }
 937       else if (current.getLength() > maxLength)
 938       {
 939         current.deleteChars(maxLength, current.getLength());
 940       }
 941     }
 942     return modified;
 943   }
 944
 945   /**
 946    * Justify the sequences to the left or right by deleting and inserting gaps
 947    * before the initial residue or after the terminal residue
 948    *
 949    * @param right
 950    *          true if alignment padded to right, false to justify to left
 951    * @return true if alignment was changed
 952    */
 953   public boolean justify(boolean right)
 954   {
 955     boolean modified = false;
 956
 957     // Remove excess gaps from the end of alignment
 958     int maxLength = -1;
 959     int ends[] = new int[sequences.size() * 2];
 960     SequenceI current;
 961     for (int i = 0; i < sequences.size(); i++)
 962     {
 963       current = getSequenceAt(i);
 964       // This should really be a sequence method
 965       ends[i * 2] = current.findIndex(current.getStart());
 966       ends[i * 2 + 1] = current.findIndex(current.getStart()
 967               + current.getLength());
 968       boolean hitres = false;
 969       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
 970       {
 971         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
 972         {
 973           if (!hitres)
 974           {
 975             ends[i * 2] = j;
 976             hitres = true;
 977           }
 978           else
 979           {
 980             ends[i * 2 + 1] = j;
 981             if (j - ends[i * 2] > maxLength)
 982             {
 983               maxLength = j - ends[i * 2];
 984             }
 985           }
 986         }
 987       }
 988     }
 989
 990     maxLength++;
 991     // now edit the flanking gaps to justify to either left or right
 992     int cLength, extent, diff;
 993     for (int i = 0; i < sequences.size(); i++)
 994     {
 995       current = getSequenceAt(i);
 996
 997       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
 998       diff = maxLength - cLength; // number of gaps to indent
 999       extent = current.getLength();
1000       if (right)
1001       {
1002         // right justify
1003         if (extent > ends[i * 2 + 1])
1004         {
1005           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1006           modified = true;
1007         }
1008         if (ends[i * 2] > diff)
1009         {
1010           current.deleteChars(0, ends[i * 2] - diff);
1011           modified = true;
1012         }
1013         else
1014         {
1015           if (ends[i * 2] < diff)
1016           {
1017             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1018             modified = true;
1019           }
1020         }
1021       }
1022       else
1023       {
1024         // left justify
1025         if (ends[i * 2] > 0)
1026         {
1027           current.deleteChars(0, ends[i * 2]);
1028           modified = true;
1029           ends[i * 2 + 1] -= ends[i * 2];
1030           extent -= ends[i * 2];
1031         }
1032         if (extent > maxLength)
1033         {
1034           current.deleteChars(maxLength + 1, extent);
1035           modified = true;
1036         }
1037         else
1038         {
1039           if (extent < maxLength)
1040           {
1041             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1042             modified = true;
1043           }
1044         }
1045       }
1046     }
1047     return modified;
1048   }
1049
1050   public HiddenSequences getHiddenSequences()
1051   {
1052     return hiddenSequences;
1053   }
1054
1055   public CigarArray getCompactAlignment()
1056   {
1057     SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1058     for (int i = 0; i < sequences.size(); i++)
1059     {
1060       alseqs[i] = new SeqCigar((SequenceI) sequences.elementAt(i));
1061     }
1062     CigarArray cal = new CigarArray(alseqs);
1063     cal.addOperation(CigarArray.M, getWidth());
1064     return cal;
1065   }
1066
1067   public void setProperty(Object key, Object value)
1068   {
1069     if (alignmentProperties == null)
1070       alignmentProperties = new Hashtable();
1071
1072     alignmentProperties.put(key, value);
1073   }
1074
1075   public Object getProperty(Object key)
1076   {
1077     if (alignmentProperties != null)
1078       return alignmentProperties.get(key);
1079     else
1080       return null;
1081   }
1082
1083   public Hashtable getProperties()
1084   {
1085     return alignmentProperties;
1086   }
1087
1088   AlignedCodonFrame[] codonFrameList = null;
1089
1090   /*
1091    * (non-Javadoc)
1092    *
1093    * @see
1094    * jalview.datamodel.AlignmentI#addCodonFrame(jalview.datamodel.AlignedCodonFrame
1095    * )
1096    */
1097   public void addCodonFrame(AlignedCodonFrame codons)
1098   {
1099     if (codons == null)
1100       return;
1101     if (codonFrameList == null)
1102     {
1103       codonFrameList = new AlignedCodonFrame[]
1104       { codons };
1105       return;
1106     }
1107     AlignedCodonFrame[] t = new AlignedCodonFrame[codonFrameList.length + 1];
1108     System.arraycopy(codonFrameList, 0, t, 0, codonFrameList.length);
1109     t[codonFrameList.length] = codons;
1110     codonFrameList = t;
1111   }
1112
1113   /*
1114    * (non-Javadoc)
1115    *
1116    * @see jalview.datamodel.AlignmentI#getCodonFrame(int)
1117    */
1118   public AlignedCodonFrame getCodonFrame(int index)
1119   {
1120     return codonFrameList[index];
1121   }
1122
1123   /*
1124    * (non-Javadoc)
1125    *
1126    * @see
1127    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1128    */
1129   public AlignedCodonFrame[] getCodonFrame(SequenceI seq)
1130   {
1131     if (seq == null || codonFrameList == null)
1132       return null;
1133     Vector cframes = new Vector();
1134     for (int f = 0; f < codonFrameList.length; f++)
1135     {
1136       if (codonFrameList[f].involvesSequence(seq))
1137         cframes.addElement(codonFrameList[f]);
1138     }
1139     if (cframes.size() == 0)
1140       return null;
1141     AlignedCodonFrame[] cfr = new AlignedCodonFrame[cframes.size()];
1142     cframes.copyInto(cfr);
1143     return cfr;
1144   }
1145
1146   /*
1147    * (non-Javadoc)
1148    *
1149    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1150    */
1151   public AlignedCodonFrame[] getCodonFrames()
1152   {
1153     return codonFrameList;
1154   }
1155
1156   /*
1157    * (non-Javadoc)
1158    *
1159    * @seejalview.datamodel.AlignmentI#removeCodonFrame(jalview.datamodel.
1160    * AlignedCodonFrame)
1161    */
1162   public boolean removeCodonFrame(AlignedCodonFrame codons)
1163   {
1164     if (codons == null || codonFrameList == null)
1165       return false;
1166     boolean removed = false;
1167     int i = 0, iSize = codonFrameList.length;
1168     while (i < iSize)
1169     {
1170       if (codonFrameList[i] == codons)
1171       {
1172         removed = true;
1173         if (i + 1 < iSize)
1174         {
1175           System.arraycopy(codonFrameList, i + 1, codonFrameList, i, iSize
1176                   - i - 1);
1177         }
1178         iSize--;
1179       }
1180       else
1181       {
1182         i++;
1183       }
1184     }
1185     return removed;
1186   }
1187
1188   public void append(AlignmentI toappend)
1189   {
1190     // TODO test this method for a future 2.5 release
1191     // currently tested for use in jalview.gui.SequenceFetcher
1192     boolean samegap = toappend.getGapCharacter() == getGapCharacter();
1193     char oldc = toappend.getGapCharacter();
1194     boolean hashidden = toappend.getHiddenSequences() != null
1195             && toappend.getHiddenSequences().hiddenSequences != null;
1196     // get all sequences including any hidden ones
1197     Vector sqs = (hashidden) ? toappend.getHiddenSequences()
1198             .getFullAlignment().getSequences() : toappend.getSequences();
1199     if (sqs != null)
1200     {
1201       Enumeration sq = sqs.elements();
1202       while (sq.hasMoreElements())
1203       {
1204         SequenceI addedsq = (SequenceI) sq.nextElement();
1205         if (!samegap)
1206         {
1207           char[] oldseq = addedsq.getSequence();
1208           for (int c = 0; c < oldseq.length; c++)
1209           {
1210             if (oldseq[c] == oldc)
1211             {
1212               oldseq[c] = gapCharacter;
1213             }
1214           }
1215         }
1216         addSequence(addedsq);
1217       }
1218     }
1219     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1220     for (int a = 0; alan != null && a < alan.length; a++)
1221     {
1222       addAnnotation(alan[a]);
1223     }
1224     AlignedCodonFrame[] acod = toappend.getCodonFrames();
1225     for (int a = 0; acod != null && a < acod.length; a++)
1226     {
1227       this.addCodonFrame(acod[a]);
1228     }
1229     List<SequenceGroup> sg = toappend.getGroups();
1230     if (sg != null)
1231     {
1232       for (SequenceGroup _sg:sg)
1233       {
1234         addGroup(_sg);
1235       }
1236     }
1237     if (toappend.getHiddenSequences() != null)
1238     {
1239       HiddenSequences hs = toappend.getHiddenSequences();
1240       if (hiddenSequences == null)
1241       {
1242         hiddenSequences = new HiddenSequences(this);
1243       }
1244       if (hs.hiddenSequences != null)
1245       {
1246         for (int s = 0; s < hs.hiddenSequences.length; s++)
1247         {
1248           // hide the newly appended sequence in the alignment
1249           if (hs.hiddenSequences[s] != null)
1250           {
1251             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1252           }
1253         }
1254       }
1255     }
1256     if (toappend.getProperties() != null)
1257     {
1258       // we really can't do very much here - just try to concatenate strings
1259       // where property collisions occur.
1260       Enumeration key = toappend.getProperties().keys();
1261       while (key.hasMoreElements())
1262       {
1263         Object k = key.nextElement();
1264         Object ourval = this.getProperty(k);
1265         Object toapprop = toappend.getProperty(k);
1266         if (ourval != null)
1267         {
1268           if (ourval.getClass().equals(toapprop.getClass())
1269                   && !ourval.equals(toapprop))
1270           {
1271             if (ourval instanceof String)
1272             {
1273               // append strings
1274               this.setProperty(k, ((String) ourval) + "; "
1275                       + ((String) toapprop));
1276             }
1277             else
1278             {
1279               if (ourval instanceof Vector)
1280               {
1281                 // append vectors
1282                 Enumeration theirv = ((Vector) toapprop).elements();
1283                 while (theirv.hasMoreElements())
1284                 {
1285                   ((Vector) ourval).addElement(theirv);
1286                 }
1287               }
1288             }
1289           }
1290         }
1291         else
1292         {
1293           // just add new property directly
1294           setProperty(k, toapprop);
1295         }
1296
1297       }
1298     }
1299   }
1300
1301   @Override
1302   public AlignmentAnnotation findOrCreateAnnotation(String name, boolean autoCalc,
1303           SequenceI seqRef, SequenceGroup groupRef)
1304   {
1305     for (AlignmentAnnotation annot :
1306             getAlignmentAnnotation())
1307     {
1308       if (annot.autoCalculated == autoCalc
1309               && annot.getCalcId().equals(name)
1310               && annot.sequenceRef == seqRef && annot.groupRef == groupRef)
1311       {
1312         return annot;
1313       }
1314     }
1315     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1316             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1317     annot.hasText = false;
1318     annot.setCalcId(new String(name));
1319     annot.autoCalculated = autoCalc;
1320     if (seqRef != null)
1321     {
1322       annot.setSequenceRef(seqRef);
1323     }
1324     annot.groupRef = groupRef;
1325     addAnnotation(annot);
1326
1327     return annot;
1328   }
1329
1330   @Override
1331   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1332   {
1333     ArrayList<AlignmentAnnotation> aa=new ArrayList<AlignmentAnnotation>();
1334     for (AlignmentAnnotation a:getAlignmentAnnotation())
1335     {
1336       if (a.getCalcId()==calcId || (a.getCalcId()!=null && calcId!=null && a.getCalcId().equals(calcId)))
1337       {
1338         aa.add(a);
1339       }
1340     }
1341     return aa;
1342   }
1343
1344 }