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         sg.setContext(null);
 453       }
 454       groups.clear();
 455     }
 456   }
 457
 458   /**    */
 459   @Override
 460   public void deleteGroup(SequenceGroup g)
 461   {
 462     synchronized (groups)
 463     {
 464       if (groups.contains(g))
 465       {
 466         removeAnnotationForGroup(g);
 467         groups.remove(g);
 468         g.setContext(null);
 469       }
 470     }
 471   }
 472
 473   /**    */
 474   @Override
 475   public SequenceI findName(String name)
 476   {
 477     return findName(name, false);
 478   }
 479
 480   /*
 481    * (non-Javadoc)
 482    *
 483    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 484    */
 485   @Override
 486   public SequenceI findName(String token, boolean b)
 487   {
 488     return findName(null, token, b);
 489   }
 490
 491   /*
 492    * (non-Javadoc)
 493    *
 494    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 495    * boolean)
 496    */
 497   @Override
 498   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 499   {
 500
 501     int i = 0;
 502     SequenceI sq = null;
 503     String sqname = null;
 504     if (startAfter != null)
 505     {
 506       // try to find the sequence in the alignment
 507       boolean matched = false;
 508       while (i < sequences.size())
 509       {
 510         if (getSequenceAt(i++) == startAfter)
 511         {
 512           matched = true;
 513           break;
 514         }
 515       }
 516       if (!matched)
 517       {
 518         i = 0;
 519       }
 520     }
 521     while (i < sequences.size())
 522     {
 523       sq = getSequenceAt(i);
 524       sqname = sq.getName();
 525       if (sqname.equals(token) // exact match
 526               || (b && // allow imperfect matches - case varies
 527               (sqname.equalsIgnoreCase(token))))
 528       {
 529         return getSequenceAt(i);
 530       }
 531
 532       i++;
 533     }
 534
 535     return null;
 536   }
 537
 538   @Override
 539   public SequenceI[] findSequenceMatch(String name)
 540   {
 541     Vector matches = new Vector();
 542     int i = 0;
 543
 544     while (i < sequences.size())
 545     {
 546       if (getSequenceAt(i).getName().equals(name))
 547       {
 548         matches.addElement(getSequenceAt(i));
 549       }
 550       i++;
 551     }
 552
 553     SequenceI[] result = new SequenceI[matches.size()];
 554     for (i = 0; i < result.length; i++)
 555     {
 556       result[i] = (SequenceI) matches.elementAt(i);
 557     }
 558
 559     return result;
 560
 561   }
 562
 563   /*
 564    * (non-Javadoc)
 565    *
 566    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 567    */
 568   @Override
 569   public int findIndex(SequenceI s)
 570   {
 571     int i = 0;
 572
 573     while (i < sequences.size())
 574     {
 575       if (s == getSequenceAt(i))
 576       {
 577         return i;
 578       }
 579
 580       i++;
 581     }
 582
 583     return -1;
 584   }
 585
 586   /*
 587    * (non-Javadoc)
 588    *
 589    * @see
 590    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 591    */
 592   @Override
 593   public int findIndex(SearchResults results)
 594   {
 595     int i = 0;
 596
 597     while (i < sequences.size())
 598     {
 599       if (results.involvesSequence(getSequenceAt(i)))
 600       {
 601         return i;
 602       }
 603       i++;
 604     }
 605     return -1;
 606   }
 607
 608   /**
 609    * DOCUMENT ME!
 610    *
 611    * @return DOCUMENT ME!
 612    */
 613   @Override
 614   public int getHeight()
 615   {
 616     return sequences.size();
 617   }
 618
 619   /**
 620    * DOCUMENT ME!
 621    *
 622    * @return DOCUMENT ME!
 623    */
 624   @Override
 625   public int getWidth()
 626   {
 627     int maxLength = -1;
 628
 629     for (int i = 0; i < sequences.size(); i++)
 630     {
 631       if (getSequenceAt(i).getLength() > maxLength)
 632       {
 633         maxLength = getSequenceAt(i).getLength();
 634       }
 635     }
 636
 637     return maxLength;
 638   }
 639
 640   /**
 641    * DOCUMENT ME!
 642    *
 643    * @param gc
 644    *          DOCUMENT ME!
 645    */
 646   @Override
 647   public void setGapCharacter(char gc)
 648   {
 649     gapCharacter = gc;
 650     synchronized (sequences)
 651     {
 652       for (SequenceI seq : sequences)
 653       {
 654         seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 655                 .replace('-', gc).replace(' ', gc));
 656       }
 657     }
 658   }
 659
 660   /**
 661    * DOCUMENT ME!
 662    *
 663    * @return DOCUMENT ME!
 664    */
 665   @Override
 666   public char getGapCharacter()
 667   {
 668     return gapCharacter;
 669   }
 670
 671   /*
 672    * (non-Javadoc)
 673    *
 674    * @see jalview.datamodel.AlignmentI#isAligned()
 675    */
 676   @Override
 677   public boolean isAligned()
 678   {
 679     return isAligned(false);
 680   }
 681
 682   /*
 683    * (non-Javadoc)
 684    *
 685    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 686    */
 687   @Override
 688   public boolean isAligned(boolean includeHidden)
 689   {
 690     int width = getWidth();
 691     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 692     {
 693       includeHidden = true; // no hidden sequences to check against.
 694     }
 695     for (int i = 0; i < sequences.size(); i++)
 696     {
 697       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 698       {
 699         if (getSequenceAt(i).getLength() != width)
 700         {
 701           return false;
 702         }
 703       }
 704     }
 705
 706     return true;
 707   }
 708
 709   /*
 710    * (non-Javadoc)
 711    *
 712    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 713    * AlignmentAnnotation)
 714    */
 715   @Override
 716   public boolean deleteAnnotation(AlignmentAnnotation aa)
 717   {
 718     return deleteAnnotation(aa, true);
 719   }
 720
 721   @Override
 722   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 723   {
 724     int aSize = 1;
 725
 726     if (annotations != null)
 727     {
 728       aSize = annotations.length;
 729     }
 730
 731     if (aSize < 1)
 732     {
 733       return false;
 734     }
 735
 736     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 737
 738     boolean swap = false;
 739     int tIndex = 0;
 740
 741     for (int i = 0; i < aSize; i++)
 742     {
 743       if (annotations[i] == aa)
 744       {
 745         swap = true;
 746         continue;
 747       }
 748       if (tIndex < temp.length)
 749         temp[tIndex++] = annotations[i];
 750     }
 751
 752     if (swap)
 753     {
 754       annotations = temp;
 755       if (unhook)
 756       {
 757         unhookAnnotation(aa);
 758       }
 759     }
 760     return swap;
 761   }
 762
 763   /**
 764    * remove any object references associated with this annotation
 765    *
 766    * @param aa
 767    */
 768   private void unhookAnnotation(AlignmentAnnotation aa)
 769   {
 770     if (aa.sequenceRef != null)
 771     {
 772       aa.sequenceRef.removeAlignmentAnnotation(aa);
 773     }
 774     if (aa.groupRef != null)
 775     {
 776       // probably need to do more here in the future (post 2.5.0)
 777       aa.groupRef = null;
 778     }
 779   }
 780
 781   /*
 782    * (non-Javadoc)
 783    *
 784    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 785    * AlignmentAnnotation)
 786    */
 787   @Override
 788   public void addAnnotation(AlignmentAnnotation aa)
 789   {
 790     addAnnotation(aa, -1);
 791   }
 792
 793   /*
 794    * (non-Javadoc)
 795    *
 796    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 797    * AlignmentAnnotation, int)
 798    */
 799   @Override
 800   public void addAnnotation(AlignmentAnnotation aa, int pos)
 801   {
 802     if (aa.getRNAStruc() != null)
 803     {
 804       hasRNAStructure = true;
 805     }
 806
 807     int aSize = 1;
 808     if (annotations != null)
 809     {
 810       aSize = annotations.length + 1;
 811     }
 812
 813     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 814     int i = 0;
 815     if (pos == -1 || pos >= aSize)
 816     {
 817       temp[aSize - 1] = aa;
 818     }
 819     else
 820     {
 821       temp[pos] = aa;
 822     }
 823     if (aSize > 1)
 824     {
 825       int p = 0;
 826       for (i = 0; i < (aSize - 1); i++, p++)
 827       {
 828         if (p == pos)
 829         {
 830           p++;
 831         }
 832         if (p < temp.length)
 833         {
 834           temp[p] = annotations[i];
 835         }
 836       }
 837     }
 838
 839     annotations = temp;
 840   }
 841
 842   @Override
 843   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 844   {
 845     if (aa == null || annotations == null || annotations.length - 1 < index)
 846     {
 847       return;
 848     }
 849
 850     int aSize = annotations.length;
 851     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 852
 853     temp[index] = aa;
 854
 855     for (int i = 0; i < aSize; i++)
 856     {
 857       if (i == index)
 858       {
 859         continue;
 860       }
 861
 862       if (i < index)
 863       {
 864         temp[i] = annotations[i];
 865       }
 866       else
 867       {
 868         temp[i] = annotations[i - 1];
 869       }
 870     }
 871
 872     annotations = temp;
 873   }
 874
 875   @Override
 876   /**
 877    * returns all annotation on the alignment
 878    */
 879   public AlignmentAnnotation[] getAlignmentAnnotation()
 880   {
 881     return annotations;
 882   }
 883
 884   @Override
 885   public void setNucleotide(boolean b)
 886   {
 887     if (b)
 888     {
 889       type = NUCLEOTIDE;
 890     }
 891     else
 892     {
 893       type = PROTEIN;
 894     }
 895   }
 896
 897   @Override
 898   public boolean isNucleotide()
 899   {
 900     if (type == NUCLEOTIDE)
 901     {
 902       return true;
 903     }
 904     else
 905     {
 906       return false;
 907     }
 908   }
 909
 910   @Override
 911   public boolean hasRNAStructure()
 912   {
 913     // TODO can it happen that structure is removed from alignment?
 914     return hasRNAStructure;
 915   }
 916
 917   @Override
 918   public void setDataset(Alignment data)
 919   {
 920     if (dataset == null && data == null)
 921     {
 922       // Create a new dataset for this alignment.
 923       // Can only be done once, if dataset is not null
 924       // This will not be performed
 925       SequenceI[] seqs = new SequenceI[getHeight()];
 926       SequenceI currentSeq;
 927       for (int i = 0; i < getHeight(); i++)
 928       {
 929         currentSeq = getSequenceAt(i);
 930         if (currentSeq.getDatasetSequence() != null)
 931         {
 932           seqs[i] = currentSeq.getDatasetSequence();
 933         }
 934         else
 935         {
 936           seqs[i] = currentSeq.createDatasetSequence();
 937         }
 938       }
 939
 940       dataset = new Alignment(seqs);
 941     }
 942     else if (dataset == null && data != null)
 943     {
 944       dataset = data;
 945     }
 946     dataset.addAlignmentRef();
 947   }
 948
 949   /**
 950    * reference count for number of alignments referencing this one.
 951    */
 952   int alignmentRefs = 0;
 953
 954   /**
 955    * increase reference count to this alignment.
 956    */
 957   private void addAlignmentRef()
 958   {
 959     alignmentRefs++;
 960   }
 961
 962   @Override
 963   public Alignment getDataset()
 964   {
 965     return dataset;
 966   }
 967
 968   @Override
 969   public boolean padGaps()
 970   {
 971     boolean modified = false;
 972
 973     // Remove excess gaps from the end of alignment
 974     int maxLength = -1;
 975
 976     SequenceI current;
 977     for (int i = 0; i < sequences.size(); i++)
 978     {
 979       current = getSequenceAt(i);
 980       for (int j = current.getLength(); j > maxLength; j--)
 981       {
 982         if (j > maxLength
 983                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
 984         {
 985           maxLength = j;
 986           break;
 987         }
 988       }
 989     }
 990
 991     maxLength++;
 992
 993     int cLength;
 994     for (int i = 0; i < sequences.size(); i++)
 995     {
 996       current = getSequenceAt(i);
 997       cLength = current.getLength();
 998
 999       if (cLength < maxLength)
1000       {
1001         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
1002         modified = true;
1003       }
1004       else if (current.getLength() > maxLength)
1005       {
1006         current.deleteChars(maxLength, current.getLength());
1007       }
1008     }
1009     return modified;
1010   }
1011
1012   /**
1013    * Justify the sequences to the left or right by deleting and inserting gaps
1014    * before the initial residue or after the terminal residue
1015    *
1016    * @param right
1017    *          true if alignment padded to right, false to justify to left
1018    * @return true if alignment was changed
1019    */
1020   @Override
1021   public boolean justify(boolean right)
1022   {
1023     boolean modified = false;
1024
1025     // Remove excess gaps from the end of alignment
1026     int maxLength = -1;
1027     int ends[] = new int[sequences.size() * 2];
1028     SequenceI current;
1029     for (int i = 0; i < sequences.size(); i++)
1030     {
1031       current = getSequenceAt(i);
1032       // This should really be a sequence method
1033       ends[i * 2] = current.findIndex(current.getStart());
1034       ends[i * 2 + 1] = current.findIndex(current.getStart()
1035               + current.getLength());
1036       boolean hitres = false;
1037       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1038       {
1039         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1040         {
1041           if (!hitres)
1042           {
1043             ends[i * 2] = j;
1044             hitres = true;
1045           }
1046           else
1047           {
1048             ends[i * 2 + 1] = j;
1049             if (j - ends[i * 2] > maxLength)
1050             {
1051               maxLength = j - ends[i * 2];
1052             }
1053           }
1054         }
1055       }
1056     }
1057
1058     maxLength++;
1059     // now edit the flanking gaps to justify to either left or right
1060     int cLength, extent, diff;
1061     for (int i = 0; i < sequences.size(); i++)
1062     {
1063       current = getSequenceAt(i);
1064
1065       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1066       diff = maxLength - cLength; // number of gaps to indent
1067       extent = current.getLength();
1068       if (right)
1069       {
1070         // right justify
1071         if (extent > ends[i * 2 + 1])
1072         {
1073           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1074           modified = true;
1075         }
1076         if (ends[i * 2] > diff)
1077         {
1078           current.deleteChars(0, ends[i * 2] - diff);
1079           modified = true;
1080         }
1081         else
1082         {
1083           if (ends[i * 2] < diff)
1084           {
1085             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1086             modified = true;
1087           }
1088         }
1089       }
1090       else
1091       {
1092         // left justify
1093         if (ends[i * 2] > 0)
1094         {
1095           current.deleteChars(0, ends[i * 2]);
1096           modified = true;
1097           ends[i * 2 + 1] -= ends[i * 2];
1098           extent -= ends[i * 2];
1099         }
1100         if (extent > maxLength)
1101         {
1102           current.deleteChars(maxLength + 1, extent);
1103           modified = true;
1104         }
1105         else
1106         {
1107           if (extent < maxLength)
1108           {
1109             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1110             modified = true;
1111           }
1112         }
1113       }
1114     }
1115     return modified;
1116   }
1117
1118   @Override
1119   public HiddenSequences getHiddenSequences()
1120   {
1121     return hiddenSequences;
1122   }
1123
1124   @Override
1125   public CigarArray getCompactAlignment()
1126   {
1127     synchronized (sequences)
1128     {
1129       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1130       int i = 0;
1131       for (SequenceI seq : sequences)
1132       {
1133         alseqs[i++] = new SeqCigar(seq);
1134       }
1135       CigarArray cal = new CigarArray(alseqs);
1136       cal.addOperation(CigarArray.M, getWidth());
1137       return cal;
1138     }
1139   }
1140
1141   @Override
1142   public void setProperty(Object key, Object value)
1143   {
1144     if (alignmentProperties == null)
1145       alignmentProperties = new Hashtable();
1146
1147     alignmentProperties.put(key, value);
1148   }
1149
1150   @Override
1151   public Object getProperty(Object key)
1152   {
1153     if (alignmentProperties != null)
1154       return alignmentProperties.get(key);
1155     else
1156       return null;
1157   }
1158
1159   @Override
1160   public Hashtable getProperties()
1161   {
1162     return alignmentProperties;
1163   }
1164
1165   AlignedCodonFrame[] codonFrameList = null;
1166
1167   /*
1168    * (non-Javadoc)
1169    *
1170    * @see
1171    * jalview.datamodel.AlignmentI#addCodonFrame(jalview.datamodel.AlignedCodonFrame
1172    * )
1173    */
1174   @Override
1175   public void addCodonFrame(AlignedCodonFrame codons)
1176   {
1177     if (codons == null)
1178       return;
1179     if (codonFrameList == null)
1180     {
1181       codonFrameList = new AlignedCodonFrame[]
1182       { codons };
1183       return;
1184     }
1185     AlignedCodonFrame[] t = new AlignedCodonFrame[codonFrameList.length + 1];
1186     System.arraycopy(codonFrameList, 0, t, 0, codonFrameList.length);
1187     t[codonFrameList.length] = codons;
1188     codonFrameList = t;
1189   }
1190
1191   /*
1192    * (non-Javadoc)
1193    *
1194    * @see jalview.datamodel.AlignmentI#getCodonFrame(int)
1195    */
1196   @Override
1197   public AlignedCodonFrame getCodonFrame(int index)
1198   {
1199     return codonFrameList[index];
1200   }
1201
1202   /*
1203    * (non-Javadoc)
1204    *
1205    * @see
1206    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1207    */
1208   @Override
1209   public AlignedCodonFrame[] getCodonFrame(SequenceI seq)
1210   {
1211     if (seq == null || codonFrameList == null)
1212       return null;
1213     Vector cframes = new Vector();
1214     for (int f = 0; f < codonFrameList.length; f++)
1215     {
1216       if (codonFrameList[f].involvesSequence(seq))
1217         cframes.addElement(codonFrameList[f]);
1218     }
1219     if (cframes.size() == 0)
1220       return null;
1221     AlignedCodonFrame[] cfr = new AlignedCodonFrame[cframes.size()];
1222     cframes.copyInto(cfr);
1223     return cfr;
1224   }
1225
1226   /*
1227    * (non-Javadoc)
1228    *
1229    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1230    */
1231   @Override
1232   public AlignedCodonFrame[] getCodonFrames()
1233   {
1234     return codonFrameList;
1235   }
1236
1237   /*
1238    * (non-Javadoc)
1239    *
1240    * @seejalview.datamodel.AlignmentI#removeCodonFrame(jalview.datamodel.
1241    * AlignedCodonFrame)
1242    */
1243   @Override
1244   public boolean removeCodonFrame(AlignedCodonFrame codons)
1245   {
1246     if (codons == null || codonFrameList == null)
1247       return false;
1248     boolean removed = false;
1249     int i = 0, iSize = codonFrameList.length;
1250     while (i < iSize)
1251     {
1252       if (codonFrameList[i] == codons)
1253       {
1254         removed = true;
1255         if (i + 1 < iSize)
1256         {
1257           System.arraycopy(codonFrameList, i + 1, codonFrameList, i, iSize
1258                   - i - 1);
1259         }
1260         iSize--;
1261       }
1262       else
1263       {
1264         i++;
1265       }
1266     }
1267     return removed;
1268   }
1269
1270   @Override
1271   public void append(AlignmentI toappend)
1272   {
1273     if (toappend == this)
1274     {
1275       System.err.println("Self append may cause a deadlock.");
1276     }
1277     // TODO test this method for a future 2.5 release
1278     // currently tested for use in jalview.gui.SequenceFetcher
1279     boolean samegap = toappend.getGapCharacter() == getGapCharacter();
1280     char oldc = toappend.getGapCharacter();
1281     boolean hashidden = toappend.getHiddenSequences() != null
1282             && toappend.getHiddenSequences().hiddenSequences != null;
1283     // get all sequences including any hidden ones
1284     List<SequenceI> sqs = (hashidden) ? toappend.getHiddenSequences()
1285             .getFullAlignment().getSequences() : toappend.getSequences();
1286     if (sqs != null)
1287     {
1288       synchronized (sqs)
1289       {
1290         for (SequenceI addedsq : sqs)
1291         {
1292           if (!samegap)
1293           {
1294             char[] oldseq = addedsq.getSequence();
1295             for (int c = 0; c < oldseq.length; c++)
1296             {
1297               if (oldseq[c] == oldc)
1298               {
1299                 oldseq[c] = gapCharacter;
1300               }
1301             }
1302           }
1303           addSequence(addedsq);
1304         }
1305       }
1306     }
1307     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1308     for (int a = 0; alan != null && a < alan.length; a++)
1309     {
1310       addAnnotation(alan[a]);
1311     }
1312     AlignedCodonFrame[] acod = toappend.getCodonFrames();
1313     for (int a = 0; acod != null && a < acod.length; a++)
1314     {
1315       this.addCodonFrame(acod[a]);
1316     }
1317     List<SequenceGroup> sg = toappend.getGroups();
1318     if (sg != null)
1319     {
1320       for (SequenceGroup _sg : sg)
1321       {
1322         addGroup(_sg);
1323       }
1324     }
1325     if (toappend.getHiddenSequences() != null)
1326     {
1327       HiddenSequences hs = toappend.getHiddenSequences();
1328       if (hiddenSequences == null)
1329       {
1330         hiddenSequences = new HiddenSequences(this);
1331       }
1332       if (hs.hiddenSequences != null)
1333       {
1334         for (int s = 0; s < hs.hiddenSequences.length; s++)
1335         {
1336           // hide the newly appended sequence in the alignment
1337           if (hs.hiddenSequences[s] != null)
1338           {
1339             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1340           }
1341         }
1342       }
1343     }
1344     if (toappend.getProperties() != null)
1345     {
1346       // we really can't do very much here - just try to concatenate strings
1347       // where property collisions occur.
1348       Enumeration key = toappend.getProperties().keys();
1349       while (key.hasMoreElements())
1350       {
1351         Object k = key.nextElement();
1352         Object ourval = this.getProperty(k);
1353         Object toapprop = toappend.getProperty(k);
1354         if (ourval != null)
1355         {
1356           if (ourval.getClass().equals(toapprop.getClass())
1357                   && !ourval.equals(toapprop))
1358           {
1359             if (ourval instanceof String)
1360             {
1361               // append strings
1362               this.setProperty(k, ((String) ourval) + "; "
1363                       + ((String) toapprop));
1364             }
1365             else
1366             {
1367               if (ourval instanceof Vector)
1368               {
1369                 // append vectors
1370                 Enumeration theirv = ((Vector) toapprop).elements();
1371                 while (theirv.hasMoreElements())
1372                 {
1373                   ((Vector) ourval).addElement(theirv);
1374                 }
1375               }
1376             }
1377           }
1378         }
1379         else
1380         {
1381           // just add new property directly
1382           setProperty(k, toapprop);
1383         }
1384
1385       }
1386     }
1387   }
1388
1389   @Override
1390   public AlignmentAnnotation findOrCreateAnnotation(String name,
1391           String calcId, boolean autoCalc, SequenceI seqRef,
1392           SequenceGroup groupRef)
1393   {
1394     assert (name != null);
1395     if (annotations != null)
1396     {
1397       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1398       {
1399         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1400                 && (calcId == null || annot.getCalcId().equals(calcId))
1401                 && annot.sequenceRef == seqRef
1402                 && annot.groupRef == groupRef)
1403         {
1404           return annot;
1405         }
1406       }
1407     }
1408     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1409             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1410     annot.hasText = false;
1411     annot.setCalcId(new String(calcId));
1412     annot.autoCalculated = autoCalc;
1413     if (seqRef != null)
1414     {
1415       annot.setSequenceRef(seqRef);
1416     }
1417     annot.groupRef = groupRef;
1418     addAnnotation(annot);
1419
1420     return annot;
1421   }
1422
1423   @Override
1424   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1425   {
1426     ArrayList<AlignmentAnnotation> aa = new ArrayList<AlignmentAnnotation>();
1427     for (AlignmentAnnotation a : getAlignmentAnnotation())
1428     {
1429       if (a.getCalcId() == calcId
1430               || (a.getCalcId() != null && calcId != null && a.getCalcId()
1431                       .equals(calcId)))
1432       {
1433         aa.add(a);
1434       }
1435     }
1436     return aa;
1437   }
1438
1439   @Override
1440   public void moveSelectedSequencesByOne(SequenceGroup sg,
1441           Map<SequenceI, SequenceCollectionI> map, boolean up)
1442   {
1443     synchronized (sequences)
1444     {
1445       if (up)
1446       {
1447
1448         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1449         {
1450           SequenceI seq = sequences.get(i);
1451           if (!sg.getSequences(map).contains(seq))
1452           {
1453             continue;
1454           }
1455
1456           SequenceI temp = sequences.get(i - 1);
1457           if (sg.getSequences(null).contains(temp))
1458           {
1459             continue;
1460           }
1461
1462           sequences.set(i, temp);
1463           sequences.set(i - 1, seq);
1464         }
1465       }
1466       else
1467       {
1468         for (int i = sequences.size() - 2; i > -1; i--)
1469         {
1470           SequenceI seq = sequences.get(i);
1471           if (!sg.getSequences(map).contains(seq))
1472           {
1473             continue;
1474           }
1475
1476           SequenceI temp = sequences.get(i + 1);
1477           if (sg.getSequences(map).contains(temp))
1478           {
1479             continue;
1480           }
1481
1482           sequences.set(i, temp);
1483           sequences.set(i + 1, seq);
1484         }
1485       }
1486
1487     }
1488   }
1489  @Override
1490  public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1491  {
1492    alignmentAnnotation.validateRangeAndDisplay();
1493    if (isNucleotide() && alignmentAnnotation.isValidStruc())
1494    {
1495      hasRNAStructure = true;
1496    }
1497  }
1498  @Override
1499 public int getEndRes()
1500 {
1501   return getWidth()-1;
1502 }@Override
1503 public int getStartRes()
1504 {
1505   return 0;
1506 }
1507
1508 /* In the case of AlignmentI - returns the dataset for the alignment, if set
1509  * (non-Javadoc)
1510  * @see jalview.datamodel.AnnotatedCollectionI#getContext()
1511  */
1512 @Override
1513 public AnnotatedCollectionI getContext()
1514 {
1515   return dataset;
1516 }
1517 }