src/jalview/datamodel/Alignment.java

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