src/jalview/datamodel/Alignment.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.datamodel;
  22
  23 import jalview.analysis.AlignmentUtils;
  24 import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping;
  25 import jalview.io.FastaFile;
  26 import jalview.util.Comparison;
  27 import jalview.util.LinkedIdentityHashSet;
  28 import jalview.util.MessageManager;
  29
  30 import java.util.ArrayList;
  31 import java.util.Arrays;
  32 import java.util.BitSet;
  33 import java.util.Collections;
  34 import java.util.Enumeration;
  35 import java.util.HashMap;
  36 import java.util.HashSet;
  37 import java.util.Hashtable;
  38 import java.util.Iterator;
  39 import java.util.List;
  40 import java.util.Map;
  41 import java.util.Set;
  42 import java.util.Vector;
  43
  44 /**
  45  * Data structure to hold and manipulate a multiple sequence alignment
  46  */
  47 /**
  48  * @author JimP
  49  *
  50  */
  51 public class Alignment implements AlignmentI
  52 {
  53   private Alignment dataset;
  54
  55   private List<SequenceI> sequences;
  56
  57   protected List<SequenceGroup> groups;
  58
  59   protected char gapCharacter = '-';
  60
  61   private boolean nucleotide = true;
  62
  63   public boolean hasRNAStructure = false;
  64
  65   public AlignmentAnnotation[] annotations;
  66
  67   HiddenSequences hiddenSequences;
  68
  69   HiddenColumns hiddenCols;
  70
  71   public Hashtable alignmentProperties;
  72
  73   private List<AlignedCodonFrame> codonFrameList;
  74
  75   private void initAlignment(SequenceI[] seqs)
  76   {
  77     groups = Collections.synchronizedList(new ArrayList<SequenceGroup>());
  78     hiddenSequences = new HiddenSequences(this);
  79     hiddenCols = new HiddenColumns();
  80     codonFrameList = new ArrayList<>();
  81
  82     nucleotide = Comparison.isNucleotide(seqs);
  83
  84     sequences = Collections.synchronizedList(new ArrayList<SequenceI>());
  85
  86     for (int i = 0; i < seqs.length; i++)
  87     {
  88       sequences.add(seqs[i]);
  89     }
  90
  91   }
  92
  93   /**
  94    * Make a 'copy' alignment - sequences have new copies of features and
  95    * annotations, but share the original dataset sequences.
  96    */
  97   public Alignment(AlignmentI al)
  98   {
  99     SequenceI[] seqs = al.getSequencesArray();
 100     for (int i = 0; i < seqs.length; i++)
 101     {
 102       seqs[i] = new Sequence(seqs[i]);
 103     }
 104
 105     initAlignment(seqs);
 106
 107     /*
 108      * Share the same dataset sequence mappings (if any).
 109      */
 110     if (dataset == null && al.getDataset() == null)
 111     {
 112       this.setCodonFrames(al.getCodonFrames());
 113     }
 114   }
 115
 116   /**
 117    * Make an alignment from an array of Sequences.
 118    *
 119    * @param sequences
 120    */
 121   public Alignment(SequenceI[] seqs)
 122   {
 123     initAlignment(seqs);
 124   }
 125
 126   /**
 127    * Make a new alignment from an array of SeqCigars
 128    *
 129    * @param seqs
 130    *          SeqCigar[]
 131    */
 132   public Alignment(SeqCigar[] alseqs)
 133   {
 134     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
 135             gapCharacter, new HiddenColumns(), null);
 136     initAlignment(seqs);
 137   }
 138
 139   /**
 140    * Make a new alignment from an CigarArray JBPNote - can only do this when
 141    * compactAlignment does not contain hidden regions. JBPNote - must also check
 142    * that compactAlignment resolves to a set of SeqCigars - or construct them
 143    * appropriately.
 144    *
 145    * @param compactAlignment
 146    *          CigarArray
 147    */
 148   public static AlignmentI createAlignment(CigarArray compactAlignment)
 149   {
 150     throw new Error(MessageManager
 151             .getString("error.alignment_cigararray_not_implemented"));
 152     // this(compactAlignment.refCigars);
 153   }
 154
 155   @Override
 156   public List<SequenceI> getSequences()
 157   {
 158     return sequences;
 159   }
 160
 161   @Override
 162   public List<SequenceI> getSequences(
 163           Map<SequenceI, SequenceCollectionI> hiddenReps)
 164   {
 165     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to
 166     // work on this.
 167     return sequences;
 168   }
 169
 170   @Override
 171   public SequenceI[] getSequencesArray()
 172   {
 173     if (sequences == null)
 174     {
 175       return null;
 176     }
 177     synchronized (sequences)
 178     {
 179       return sequences.toArray(new SequenceI[sequences.size()]);
 180     }
 181   }
 182
 183   /**
 184    * Returns a map of lists of sequences keyed by sequence name.
 185    *
 186    * @return
 187    */
 188   @Override
 189   public Map<String, List<SequenceI>> getSequencesByName()
 190   {
 191     return AlignmentUtils.getSequencesByName(this);
 192   }
 193
 194   @Override
 195   public SequenceI getSequenceAt(int i)
 196   {
 197     synchronized (sequences)
 198     {
 199       if (i > -1 && i < sequences.size())
 200       {
 201         return sequences.get(i);
 202       }
 203     }
 204
 205     return null;
 206   }
 207
 208   @Override
 209   public SequenceI getSequenceAtAbsoluteIndex(int i)
 210   {
 211     SequenceI seq = null;
 212     if (getHiddenSequences().getSize() > 0)
 213     {
 214       seq = getHiddenSequences().getHiddenSequence(i);
 215       if (seq == null)
 216       {
 217         // didn't find the sequence in the hidden sequences, get it from the
 218         // alignment
 219         int index = getHiddenSequences().findIndexWithoutHiddenSeqs(i);
 220         seq = getSequenceAt(index);
 221       }
 222     }
 223     else
 224     {
 225       seq = getSequenceAt(i);
 226     }
 227     return seq;
 228   }
 229
 230   /**
 231    * Adds a sequence to the alignment. Recalculates maxLength and size. Note
 232    * this currently does not recalculate whether or not the alignment is
 233    * nucleotide, so mixed alignments may have undefined behaviour.
 234    *
 235    * @param snew
 236    */
 237   @Override
 238   public void addSequence(SequenceI snew)
 239   {
 240     if (dataset != null)
 241     {
 242
 243       // maintain dataset integrity
 244       SequenceI dsseq = snew.getDatasetSequence();
 245       if (dsseq == null)
 246       {
 247         // derive new sequence
 248         SequenceI adding = snew.deriveSequence();
 249         snew = adding;
 250         dsseq = snew.getDatasetSequence();
 251       }
 252       if (getDataset().findIndex(dsseq) == -1)
 253       {
 254         getDataset().addSequence(dsseq);
 255       }
 256
 257     }
 258     if (sequences == null)
 259     {
 260       initAlignment(new SequenceI[] { snew });
 261     }
 262     else
 263     {
 264       synchronized (sequences)
 265       {
 266         sequences.add(snew);
 267       }
 268     }
 269     if (hiddenSequences != null)
 270     {
 271       hiddenSequences.adjustHeightSequenceAdded();
 272     }
 273   }
 274
 275   @Override
 276   public SequenceI replaceSequenceAt(int i, SequenceI snew)
 277   {
 278     synchronized (sequences)
 279     {
 280       if (sequences.size() > i)
 281       {
 282         return sequences.set(i, snew);
 283
 284       }
 285       else
 286       {
 287         sequences.add(snew);
 288         hiddenSequences.adjustHeightSequenceAdded();
 289       }
 290       return null;
 291     }
 292   }
 293
 294   /**
 295    * DOCUMENT ME!
 296    *
 297    * @return DOCUMENT ME!
 298    */
 299   @Override
 300   public List<SequenceGroup> getGroups()
 301   {
 302     return groups;
 303   }
 304
 305   @Override
 306   public void finalize() throws Throwable
 307   {
 308     if (getDataset() != null)
 309     {
 310       getDataset().removeAlignmentRef();
 311     }
 312
 313     nullReferences();
 314     super.finalize();
 315   }
 316
 317   /**
 318    * Defensively nulls out references in case this object is not garbage
 319    * collected
 320    */
 321   void nullReferences()
 322   {
 323     dataset = null;
 324     sequences = null;
 325     groups = null;
 326     annotations = null;
 327     hiddenSequences = null;
 328   }
 329
 330   /**
 331    * decrement the alignmentRefs counter by one and null references if it goes
 332    * to zero.
 333    *
 334    * @throws Throwable
 335    */
 336   private void removeAlignmentRef() throws Throwable
 337   {
 338     if (--alignmentRefs == 0)
 339     {
 340       nullReferences();
 341     }
 342   }
 343
 344   @Override
 345   public void deleteSequence(SequenceI s)
 346   {
 347     synchronized (sequences)
 348     {
 349       deleteSequence(findIndex(s));
 350     }
 351   }
 352
 353   @Override
 354   public void deleteSequence(int i)
 355   {
 356     synchronized (sequences)
 357     {
 358       if (i > -1 && i < getHeight())
 359       {
 360         sequences.remove(i);
 361         hiddenSequences.adjustHeightSequenceDeleted(i);
 362       }
 363     }
 364   }
 365
 366   @Override
 367   public void deleteHiddenSequence(int i)
 368   {
 369     synchronized (sequences)
 370     {
 371       if (i > -1 && i < getHeight())
 372       {
 373         sequences.remove(i);
 374       }
 375     }
 376   }
 377
 378   /*
 379    * (non-Javadoc)
 380    *
 381    * @see jalview.datamodel.AlignmentI#findGroup(jalview.datamodel.SequenceI)
 382    */
 383   @Override
 384   public SequenceGroup findGroup(SequenceI seq, int position)
 385   {
 386     synchronized (groups)
 387     {
 388       for (SequenceGroup sg : groups)
 389       {
 390         if (sg.getSequences(null).contains(seq))
 391         {
 392           if (position >= sg.getStartRes() && position <= sg.getEndRes())
 393           {
 394             return sg;
 395           }
 396         }
 397       }
 398     }
 399     return null;
 400   }
 401
 402   /*
 403    * (non-Javadoc)
 404    *
 405    * @see
 406    * jalview.datamodel.AlignmentI#findAllGroups(jalview.datamodel.SequenceI)
 407    */
 408   @Override
 409   public SequenceGroup[] findAllGroups(SequenceI s)
 410   {
 411     ArrayList<SequenceGroup> temp = new ArrayList<>();
 412
 413     synchronized (groups)
 414     {
 415       int gSize = groups.size();
 416       for (int i = 0; i < gSize; i++)
 417       {
 418         SequenceGroup sg = groups.get(i);
 419         if (sg == null || sg.getSequences() == null)
 420         {
 421           this.deleteGroup(sg);
 422           gSize--;
 423           continue;
 424         }
 425
 426         if (sg.getSequences().contains(s))
 427         {
 428           temp.add(sg);
 429         }
 430       }
 431     }
 432     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 433     return temp.toArray(ret);
 434   }
 435
 436   /**    */
 437   @Override
 438   public void addGroup(SequenceGroup sg)
 439   {
 440     synchronized (groups)
 441     {
 442       if (!groups.contains(sg))
 443       {
 444         if (hiddenSequences.getSize() > 0)
 445         {
 446           int i, iSize = sg.getSize();
 447           for (i = 0; i < iSize; i++)
 448           {
 449             if (!sequences.contains(sg.getSequenceAt(i)))
 450             {
 451               sg.deleteSequence(sg.getSequenceAt(i), false);
 452               iSize--;
 453               i--;
 454             }
 455           }
 456
 457           if (sg.getSize() < 1)
 458           {
 459             return;
 460           }
 461         }
 462         sg.setContext(this, true);
 463         groups.add(sg);
 464       }
 465     }
 466   }
 467
 468   /**
 469    * remove any annotation that references gp
 470    *
 471    * @param gp
 472    *          (if null, removes all group associated annotation)
 473    */
 474   private void removeAnnotationForGroup(SequenceGroup gp)
 475   {
 476     if (annotations == null || annotations.length == 0)
 477     {
 478       return;
 479     }
 480     // remove annotation very quickly
 481     AlignmentAnnotation[] t,
 482             todelete = new AlignmentAnnotation[annotations.length],
 483             tokeep = new AlignmentAnnotation[annotations.length];
 484     int i, p, k;
 485     if (gp == null)
 486     {
 487       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 488       {
 489         if (annotations[i].groupRef != null)
 490         {
 491           todelete[p++] = annotations[i];
 492         }
 493         else
 494         {
 495           tokeep[k++] = annotations[i];
 496         }
 497       }
 498     }
 499     else
 500     {
 501       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 502       {
 503         if (annotations[i].groupRef == gp)
 504         {
 505           todelete[p++] = annotations[i];
 506         }
 507         else
 508         {
 509           tokeep[k++] = annotations[i];
 510         }
 511       }
 512     }
 513     if (p > 0)
 514     {
 515       // clear out the group associated annotation.
 516       for (i = 0; i < p; i++)
 517       {
 518         unhookAnnotation(todelete[i]);
 519         todelete[i] = null;
 520       }
 521       t = new AlignmentAnnotation[k];
 522       for (i = 0; i < k; i++)
 523       {
 524         t[i] = tokeep[i];
 525       }
 526       annotations = t;
 527     }
 528   }
 529
 530   @Override
 531   public void deleteAllGroups()
 532   {
 533     synchronized (groups)
 534     {
 535       if (annotations != null)
 536       {
 537         removeAnnotationForGroup(null);
 538       }
 539       for (SequenceGroup sg : groups)
 540       {
 541         sg.setContext(null, false);
 542       }
 543       groups.clear();
 544     }
 545   }
 546
 547   /**    */
 548   @Override
 549   public void deleteGroup(SequenceGroup g)
 550   {
 551     synchronized (groups)
 552     {
 553       if (groups.contains(g))
 554       {
 555         removeAnnotationForGroup(g);
 556         groups.remove(g);
 557         g.setContext(null, false);
 558       }
 559     }
 560   }
 561
 562   /**    */
 563   @Override
 564   public SequenceI findName(String name)
 565   {
 566     return findName(name, false);
 567   }
 568
 569   /*
 570    * (non-Javadoc)
 571    *
 572    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 573    */
 574   @Override
 575   public SequenceI findName(String token, boolean b)
 576   {
 577     return findName(null, token, b);
 578   }
 579
 580   /*
 581    * (non-Javadoc)
 582    *
 583    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 584    * boolean)
 585    */
 586   @Override
 587   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 588   {
 589
 590     int i = 0;
 591     SequenceI sq = null;
 592     String sqname = null;
 593     if (startAfter != null)
 594     {
 595       // try to find the sequence in the alignment
 596       boolean matched = false;
 597       while (i < sequences.size())
 598       {
 599         if (getSequenceAt(i++) == startAfter)
 600         {
 601           matched = true;
 602           break;
 603         }
 604       }
 605       if (!matched)
 606       {
 607         i = 0;
 608       }
 609     }
 610     while (i < sequences.size())
 611     {
 612       sq = getSequenceAt(i);
 613       sqname = sq.getName();
 614       if (sqname.equals(token) // exact match
 615               || (b && // allow imperfect matches - case varies
 616                       (sqname.equalsIgnoreCase(token))))
 617       {
 618         return getSequenceAt(i);
 619       }
 620
 621       i++;
 622     }
 623
 624     return null;
 625   }
 626
 627   @Override
 628   public SequenceI[] findSequenceMatch(String name)
 629   {
 630     Vector matches = new Vector();
 631     int i = 0;
 632
 633     while (i < sequences.size())
 634     {
 635       if (getSequenceAt(i).getName().equals(name))
 636       {
 637         matches.addElement(getSequenceAt(i));
 638       }
 639       i++;
 640     }
 641
 642     SequenceI[] result = new SequenceI[matches.size()];
 643     for (i = 0; i < result.length; i++)
 644     {
 645       result[i] = (SequenceI) matches.elementAt(i);
 646     }
 647
 648     return result;
 649
 650   }
 651
 652   /*
 653    * (non-Javadoc)
 654    *
 655    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 656    */
 657   @Override
 658   public int findIndex(SequenceI s)
 659   {
 660     int i = 0;
 661
 662     while (i < sequences.size())
 663     {
 664       if (s == getSequenceAt(i))
 665       {
 666         return i;
 667       }
 668
 669       i++;
 670     }
 671
 672     return -1;
 673   }
 674
 675   /*
 676    * (non-Javadoc)
 677    *
 678    * @see
 679    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 680    */
 681   @Override
 682   public int findIndex(SearchResultsI results)
 683   {
 684     int i = 0;
 685
 686     while (i < sequences.size())
 687     {
 688       if (results.involvesSequence(getSequenceAt(i)))
 689       {
 690         return i;
 691       }
 692       i++;
 693     }
 694     return -1;
 695   }
 696
 697   @Override
 698   public int getHeight()
 699   {
 700     return sequences.size();
 701   }
 702
 703   @Override
 704   public int getAbsoluteHeight()
 705   {
 706     return sequences.size() + getHiddenSequences().getSize();
 707   }
 708
 709   @Override
 710   public int getWidth()
 711   {
 712     int maxLength = -1;
 713
 714     for (int i = 0; i < sequences.size(); i++)
 715     {
 716       maxLength = Math.max(maxLength, getSequenceAt(i).getLength());
 717     }
 718     return maxLength;
 719   }
 720
 721   @Override
 722   public int getVisibleWidth()
 723   {
 724     int w = getWidth();
 725     if (hiddenCols != null)
 726     {
 727       w -= hiddenCols.getSize();
 728     }
 729     return w;
 730   }
 731
 732   /**
 733    * DOCUMENT ME!
 734    *
 735    * @param gc
 736    *          DOCUMENT ME!
 737    */
 738   @Override
 739   public void setGapCharacter(char gc)
 740   {
 741     gapCharacter = gc;
 742     synchronized (sequences)
 743     {
 744       for (SequenceI seq : sequences)
 745       {
 746         seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 747                 .replace('-', gc).replace(' ', gc));
 748       }
 749     }
 750   }
 751
 752   /**
 753    * DOCUMENT ME!
 754    *
 755    * @return DOCUMENT ME!
 756    */
 757   @Override
 758   public char getGapCharacter()
 759   {
 760     return gapCharacter;
 761   }
 762
 763   /*
 764    * (non-Javadoc)
 765    *
 766    * @see jalview.datamodel.AlignmentI#isAligned()
 767    */
 768   @Override
 769   public boolean isAligned()
 770   {
 771     return isAligned(false);
 772   }
 773
 774   /*
 775    * (non-Javadoc)
 776    *
 777    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 778    */
 779   @Override
 780   public boolean isAligned(boolean includeHidden)
 781   {
 782     int width = getWidth();
 783     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 784     {
 785       includeHidden = true; // no hidden sequences to check against.
 786     }
 787     for (int i = 0; i < sequences.size(); i++)
 788     {
 789       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 790       {
 791         if (getSequenceAt(i).getLength() != width)
 792         {
 793           return false;
 794         }
 795       }
 796     }
 797
 798     return true;
 799   }
 800
 801   @Override
 802   public boolean isHidden(int alignmentIndex)
 803   {
 804     return (getHiddenSequences().getHiddenSequence(alignmentIndex) != null);
 805   }
 806
 807   /**
 808    * Delete all annotations, including auto-calculated if the flag is set true.
 809    * Returns true if at least one annotation was deleted, else false.
 810    *
 811    * @param includingAutoCalculated
 812    * @return
 813    */
 814   @Override
 815   public boolean deleteAllAnnotations(boolean includingAutoCalculated)
 816   {
 817     boolean result = false;
 818     for (AlignmentAnnotation alan : getAlignmentAnnotation())
 819     {
 820       if (!alan.autoCalculated || includingAutoCalculated)
 821       {
 822         deleteAnnotation(alan);
 823         result = true;
 824       }
 825     }
 826     return result;
 827   }
 828
 829   /*
 830    * (non-Javadoc)
 831    *
 832    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 833    * AlignmentAnnotation)
 834    */
 835   @Override
 836   public boolean deleteAnnotation(AlignmentAnnotation aa)
 837   {
 838     return deleteAnnotation(aa, true);
 839   }
 840
 841   @Override
 842   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 843   {
 844     int aSize = 1;
 845
 846     if (annotations != null)
 847     {
 848       aSize = annotations.length;
 849     }
 850
 851     if (aSize < 1)
 852     {
 853       return false;
 854     }
 855
 856     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 857
 858     boolean swap = false;
 859     int tIndex = 0;
 860
 861     for (int i = 0; i < aSize; i++)
 862     {
 863       if (annotations[i] == aa)
 864       {
 865         swap = true;
 866         continue;
 867       }
 868       if (tIndex < temp.length)
 869       {
 870         temp[tIndex++] = annotations[i];
 871       }
 872     }
 873
 874     if (swap)
 875     {
 876       annotations = temp;
 877       if (unhook)
 878       {
 879         unhookAnnotation(aa);
 880       }
 881     }
 882     return swap;
 883   }
 884
 885   /**
 886    * remove any object references associated with this annotation
 887    *
 888    * @param aa
 889    */
 890   private void unhookAnnotation(AlignmentAnnotation aa)
 891   {
 892     if (aa.sequenceRef != null)
 893     {
 894       aa.sequenceRef.removeAlignmentAnnotation(aa);
 895     }
 896     if (aa.groupRef != null)
 897     {
 898       // probably need to do more here in the future (post 2.5.0)
 899       aa.groupRef = null;
 900     }
 901   }
 902
 903   /*
 904    * (non-Javadoc)
 905    *
 906    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 907    * AlignmentAnnotation)
 908    */
 909   @Override
 910   public void addAnnotation(AlignmentAnnotation aa)
 911   {
 912     addAnnotation(aa, -1);
 913   }
 914
 915   /*
 916    * (non-Javadoc)
 917    *
 918    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 919    * AlignmentAnnotation, int)
 920    */
 921   @Override
 922   public void addAnnotation(AlignmentAnnotation aa, int pos)
 923   {
 924     if (aa.getRNAStruc() != null)
 925     {
 926       hasRNAStructure = true;
 927     }
 928
 929     int aSize = 1;
 930     if (annotations != null)
 931     {
 932       aSize = annotations.length + 1;
 933     }
 934
 935     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 936     int i = 0;
 937     if (pos == -1 || pos >= aSize)
 938     {
 939       temp[aSize - 1] = aa;
 940     }
 941     else
 942     {
 943       temp[pos] = aa;
 944     }
 945     if (aSize > 1)
 946     {
 947       int p = 0;
 948       for (i = 0; i < (aSize - 1); i++, p++)
 949       {
 950         if (p == pos)
 951         {
 952           p++;
 953         }
 954         if (p < temp.length)
 955         {
 956           temp[p] = annotations[i];
 957         }
 958       }
 959     }
 960
 961     annotations = temp;
 962   }
 963
 964   @Override
 965   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 966   {
 967     if (aa == null || annotations == null || annotations.length - 1 < index)
 968     {
 969       return;
 970     }
 971
 972     int aSize = annotations.length;
 973     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 974
 975     temp[index] = aa;
 976
 977     for (int i = 0; i < aSize; i++)
 978     {
 979       if (i == index)
 980       {
 981         continue;
 982       }
 983
 984       if (i < index)
 985       {
 986         temp[i] = annotations[i];
 987       }
 988       else
 989       {
 990         temp[i] = annotations[i - 1];
 991       }
 992     }
 993
 994     annotations = temp;
 995   }
 996
 997   @Override
 998   /**
 999    * returns all annotation on the alignment
1000    */
1001   public AlignmentAnnotation[] getAlignmentAnnotation()
1002   {
1003     return annotations;
1004   }
1005
1006   @Override
1007   public boolean isNucleotide()
1008   {
1009     return nucleotide;
1010   }
1011
1012   @Override
1013   public boolean hasRNAStructure()
1014   {
1015     // TODO can it happen that structure is removed from alignment?
1016     return hasRNAStructure;
1017   }
1018
1019   @Override
1020   public void setDataset(AlignmentI data)
1021   {
1022     if (dataset == null && data == null)
1023     {
1024       createDatasetAlignment();
1025     }
1026     else if (dataset == null && data != null)
1027     {
1028       if (data == this)
1029       {
1030         throw new IllegalArgumentException("Circular dataset reference");
1031       }
1032       if (!(data instanceof Alignment))
1033       {
1034         throw new Error(
1035                 "Implementation Error: jalview.datamodel.Alignment does not yet support other implementations of AlignmentI as its dataset reference");
1036       }
1037       dataset = (Alignment) data;
1038       for (int i = 0; i < getHeight(); i++)
1039       {
1040         SequenceI currentSeq = getSequenceAt(i);
1041         SequenceI dsq = currentSeq.getDatasetSequence();
1042         if (dsq == null)
1043         {
1044           dsq = currentSeq.createDatasetSequence();
1045           dataset.addSequence(dsq);
1046         }
1047         else
1048         {
1049           while (dsq.getDatasetSequence() != null)
1050           {
1051             dsq = dsq.getDatasetSequence();
1052           }
1053           if (dataset.findIndex(dsq) == -1)
1054           {
1055             dataset.addSequence(dsq);
1056           }
1057         }
1058       }
1059     }
1060     dataset.addAlignmentRef();
1061   }
1062
1063   /**
1064    * add dataset sequences to seq for currentSeq and any sequences it references
1065    */
1066   private void resolveAndAddDatasetSeq(SequenceI currentSeq,
1067           Set<SequenceI> seqs, boolean createDatasetSequence)
1068   {
1069     SequenceI alignedSeq = currentSeq;
1070     if (currentSeq.getDatasetSequence() != null)
1071     {
1072       currentSeq = currentSeq.getDatasetSequence();
1073     }
1074     else
1075     {
1076       if (createDatasetSequence)
1077       {
1078         currentSeq = currentSeq.createDatasetSequence();
1079       }
1080     }
1081
1082     List<SequenceI> toProcess = new ArrayList<>();
1083     toProcess.add(currentSeq);
1084     while (toProcess.size() > 0)
1085     {
1086       // use a queue ?
1087       SequenceI curDs = toProcess.remove(0);
1088
1089       if (!seqs.add(curDs))
1090       {
1091         continue;
1092       }
1093       // iterate over database references, making sure we add forward referenced
1094       // sequences
1095       if (curDs.getDBRefs() != null)
1096       {
1097         for (DBRefEntry dbr : curDs.getDBRefs())
1098         {
1099           if (dbr.getMap() != null && dbr.getMap().getTo() != null)
1100           {
1101             if (dbr.getMap().getTo() == alignedSeq)
1102             {
1103               /*
1104                * update mapping to be to the newly created dataset sequence
1105                */
1106               dbr.getMap().setTo(currentSeq);
1107             }
1108             if (dbr.getMap().getTo().getDatasetSequence() != null)
1109             {
1110               throw new Error("Implementation error: Map.getTo() for dbref "
1111                       + dbr + " from " + curDs.getName()
1112                       + " is not a dataset sequence.");
1113             }
1114             // we recurse to add all forward references to dataset sequences via
1115             // DBRefs/etc
1116             toProcess.add(dbr.getMap().getTo());
1117           }
1118         }
1119       }
1120     }
1121   }
1122
1123   /**
1124    * Creates a new dataset for this alignment. Can only be done once - if
1125    * dataset is not null this will not be performed.
1126    */
1127   public void createDatasetAlignment()
1128   {
1129     if (dataset != null)
1130     {
1131       return;
1132     }
1133     // try to avoid using SequenceI.equals at this stage, it will be expensive
1134     Set<SequenceI> seqs = new LinkedIdentityHashSet<>();
1135
1136     for (int i = 0; i < getHeight(); i++)
1137     {
1138       SequenceI currentSeq = getSequenceAt(i);
1139       resolveAndAddDatasetSeq(currentSeq, seqs, true);
1140     }
1141
1142     // verify all mappings are in dataset
1143     for (AlignedCodonFrame cf : codonFrameList)
1144     {
1145       for (SequenceToSequenceMapping ssm : cf.getMappings())
1146       {
1147         if (!seqs.contains(ssm.getFromSeq()))
1148         {
1149           resolveAndAddDatasetSeq(ssm.getFromSeq(), seqs, false);
1150         }
1151         if (!seqs.contains(ssm.getMapping().getTo()))
1152         {
1153           resolveAndAddDatasetSeq(ssm.getMapping().getTo(), seqs, false);
1154         }
1155       }
1156     }
1157     // finally construct dataset
1158     dataset = new Alignment(seqs.toArray(new SequenceI[seqs.size()]));
1159     // move mappings to the dataset alignment
1160     dataset.codonFrameList = this.codonFrameList;
1161     this.codonFrameList = null;
1162   }
1163
1164   /**
1165    * reference count for number of alignments referencing this one.
1166    */
1167   int alignmentRefs = 0;
1168
1169   /**
1170    * increase reference count to this alignment.
1171    */
1172   private void addAlignmentRef()
1173   {
1174     alignmentRefs++;
1175   }
1176
1177   @Override
1178   public Alignment getDataset()
1179   {
1180     return dataset;
1181   }
1182
1183   @Override
1184   public boolean padGaps()
1185   {
1186     boolean modified = false;
1187
1188     // Remove excess gaps from the end of alignment
1189     int maxLength = -1;
1190
1191     SequenceI current;
1192     for (int i = 0; i < sequences.size(); i++)
1193     {
1194       current = getSequenceAt(i);
1195       for (int j = current.getLength(); j > maxLength; j--)
1196       {
1197         if (j > maxLength
1198                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
1199         {
1200           maxLength = j;
1201           break;
1202         }
1203       }
1204     }
1205
1206     maxLength++;
1207
1208     int cLength;
1209     for (int i = 0; i < sequences.size(); i++)
1210     {
1211       current = getSequenceAt(i);
1212       cLength = current.getLength();
1213
1214       if (cLength < maxLength)
1215       {
1216         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
1217         modified = true;
1218       }
1219       else if (current.getLength() > maxLength)
1220       {
1221         current.deleteChars(maxLength, current.getLength());
1222       }
1223     }
1224     return modified;
1225   }
1226
1227   /**
1228    * Justify the sequences to the left or right by deleting and inserting gaps
1229    * before the initial residue or after the terminal residue
1230    *
1231    * @param right
1232    *          true if alignment padded to right, false to justify to left
1233    * @return true if alignment was changed
1234    */
1235   @Override
1236   public boolean justify(boolean right)
1237   {
1238     boolean modified = false;
1239
1240     // Remove excess gaps from the end of alignment
1241     int maxLength = -1;
1242     int ends[] = new int[sequences.size() * 2];
1243     SequenceI current;
1244     for (int i = 0; i < sequences.size(); i++)
1245     {
1246       current = getSequenceAt(i);
1247       // This should really be a sequence method
1248       ends[i * 2] = current.findIndex(current.getStart());
1249       ends[i * 2 + 1] = current
1250               .findIndex(current.getStart() + current.getLength());
1251       boolean hitres = false;
1252       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1253       {
1254         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1255         {
1256           if (!hitres)
1257           {
1258             ends[i * 2] = j;
1259             hitres = true;
1260           }
1261           else
1262           {
1263             ends[i * 2 + 1] = j;
1264             if (j - ends[i * 2] > maxLength)
1265             {
1266               maxLength = j - ends[i * 2];
1267             }
1268           }
1269         }
1270       }
1271     }
1272
1273     maxLength++;
1274     // now edit the flanking gaps to justify to either left or right
1275     int cLength, extent, diff;
1276     for (int i = 0; i < sequences.size(); i++)
1277     {
1278       current = getSequenceAt(i);
1279
1280       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1281       diff = maxLength - cLength; // number of gaps to indent
1282       extent = current.getLength();
1283       if (right)
1284       {
1285         // right justify
1286         if (extent > ends[i * 2 + 1])
1287         {
1288           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1289           modified = true;
1290         }
1291         if (ends[i * 2] > diff)
1292         {
1293           current.deleteChars(0, ends[i * 2] - diff);
1294           modified = true;
1295         }
1296         else
1297         {
1298           if (ends[i * 2] < diff)
1299           {
1300             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1301             modified = true;
1302           }
1303         }
1304       }
1305       else
1306       {
1307         // left justify
1308         if (ends[i * 2] > 0)
1309         {
1310           current.deleteChars(0, ends[i * 2]);
1311           modified = true;
1312           ends[i * 2 + 1] -= ends[i * 2];
1313           extent -= ends[i * 2];
1314         }
1315         if (extent > maxLength)
1316         {
1317           current.deleteChars(maxLength + 1, extent);
1318           modified = true;
1319         }
1320         else
1321         {
1322           if (extent < maxLength)
1323           {
1324             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1325             modified = true;
1326           }
1327         }
1328       }
1329     }
1330     return modified;
1331   }
1332
1333   @Override
1334   public HiddenSequences getHiddenSequences()
1335   {
1336     return hiddenSequences;
1337   }
1338
1339   @Override
1340   public HiddenColumns getHiddenColumns()
1341   {
1342     return hiddenCols;
1343   }
1344
1345   @Override
1346   public CigarArray getCompactAlignment()
1347   {
1348     synchronized (sequences)
1349     {
1350       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1351       int i = 0;
1352       for (SequenceI seq : sequences)
1353       {
1354         alseqs[i++] = new SeqCigar(seq);
1355       }
1356       CigarArray cal = new CigarArray(alseqs);
1357       cal.addOperation(CigarArray.M, getWidth());
1358       return cal;
1359     }
1360   }
1361
1362   @Override
1363   public void setProperty(Object key, Object value)
1364   {
1365     if (alignmentProperties == null)
1366     {
1367       alignmentProperties = new Hashtable();
1368     }
1369
1370     alignmentProperties.put(key, value);
1371   }
1372
1373   @Override
1374   public Object getProperty(Object key)
1375   {
1376     if (alignmentProperties != null)
1377     {
1378       return alignmentProperties.get(key);
1379     }
1380     else
1381     {
1382       return null;
1383     }
1384   }
1385
1386   @Override
1387   public Hashtable getProperties()
1388   {
1389     return alignmentProperties;
1390   }
1391
1392   /**
1393    * Adds the given mapping to the stored set. Note this may be held on the
1394    * dataset alignment.
1395    */
1396   @Override
1397   public void addCodonFrame(AlignedCodonFrame codons)
1398   {
1399     List<AlignedCodonFrame> acfs = getCodonFrames();
1400     if (codons != null && acfs != null && !acfs.contains(codons))
1401     {
1402       acfs.add(codons);
1403     }
1404   }
1405
1406   /*
1407    * (non-Javadoc)
1408    *
1409    * @see
1410    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1411    */
1412   @Override
1413   public List<AlignedCodonFrame> getCodonFrame(SequenceI seq)
1414   {
1415     if (seq == null)
1416     {
1417       return null;
1418     }
1419     List<AlignedCodonFrame> cframes = new ArrayList<>();
1420     for (AlignedCodonFrame acf : getCodonFrames())
1421     {
1422       if (acf.involvesSequence(seq))
1423       {
1424         cframes.add(acf);
1425       }
1426     }
1427     return cframes;
1428   }
1429
1430   /**
1431    * Sets the codon frame mappings (replacing any existing mappings). Note the
1432    * mappings are set on the dataset alignment instead if there is one.
1433    *
1434    * @see jalview.datamodel.AlignmentI#setCodonFrames()
1435    */
1436   @Override
1437   public void setCodonFrames(List<AlignedCodonFrame> acfs)
1438   {
1439     if (dataset != null)
1440     {
1441       dataset.setCodonFrames(acfs);
1442     }
1443     else
1444     {
1445       this.codonFrameList = acfs;
1446     }
1447   }
1448
1449   /**
1450    * Returns the set of codon frame mappings. Any changes to the returned set
1451    * will affect the alignment. The mappings are held on (and read from) the
1452    * dataset alignment if there is one.
1453    *
1454    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1455    */
1456   @Override
1457   public List<AlignedCodonFrame> getCodonFrames()
1458   {
1459     // TODO: Fix this method to fix failing AlignedCodonFrame tests
1460     // this behaviour is currently incorrect. method should return codon frames
1461     // for just the alignment,
1462     // selected from dataset
1463     return dataset != null ? dataset.getCodonFrames() : codonFrameList;
1464   }
1465
1466   /**
1467    * Removes the given mapping from the stored set. Note that the mappings are
1468    * held on the dataset alignment if there is one.
1469    */
1470   @Override
1471   public boolean removeCodonFrame(AlignedCodonFrame codons)
1472   {
1473     List<AlignedCodonFrame> acfs = getCodonFrames();
1474     if (codons == null || acfs == null)
1475     {
1476       return false;
1477     }
1478     return acfs.remove(codons);
1479   }
1480
1481   @Override
1482   public void append(AlignmentI toappend)
1483   {
1484     // TODO JAL-1270 needs test coverage
1485     // currently tested for use in jalview.gui.SequenceFetcher
1486     char oldc = toappend.getGapCharacter();
1487     boolean samegap = oldc == getGapCharacter();
1488     boolean hashidden = toappend.getHiddenSequences() != null
1489             && toappend.getHiddenSequences().hiddenSequences != null;
1490     // get all sequences including any hidden ones
1491     List<SequenceI> sqs = (hashidden)
1492             ? toappend.getHiddenSequences().getFullAlignment()
1493                     .getSequences()
1494             : toappend.getSequences();
1495     if (sqs != null)
1496     {
1497       // avoid self append deadlock by
1498       List<SequenceI> toappendsq = new ArrayList<>();
1499       synchronized (sqs)
1500       {
1501         for (SequenceI addedsq : sqs)
1502         {
1503           if (!samegap)
1504           {
1505             addedsq.replace(oldc, gapCharacter);
1506           }
1507           toappendsq.add(addedsq);
1508         }
1509       }
1510       for (SequenceI addedsq : toappendsq)
1511       {
1512         addSequence(addedsq);
1513       }
1514     }
1515     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1516     for (int a = 0; alan != null && a < alan.length; a++)
1517     {
1518       addAnnotation(alan[a]);
1519     }
1520
1521     // use add method
1522     getCodonFrames().addAll(toappend.getCodonFrames());
1523
1524     List<SequenceGroup> sg = toappend.getGroups();
1525     if (sg != null)
1526     {
1527       for (SequenceGroup _sg : sg)
1528       {
1529         addGroup(_sg);
1530       }
1531     }
1532     if (toappend.getHiddenSequences() != null)
1533     {
1534       HiddenSequences hs = toappend.getHiddenSequences();
1535       if (hiddenSequences == null)
1536       {
1537         hiddenSequences = new HiddenSequences(this);
1538       }
1539       if (hs.hiddenSequences != null)
1540       {
1541         for (int s = 0; s < hs.hiddenSequences.length; s++)
1542         {
1543           // hide the newly appended sequence in the alignment
1544           if (hs.hiddenSequences[s] != null)
1545           {
1546             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1547           }
1548         }
1549       }
1550     }
1551     if (toappend.getProperties() != null)
1552     {
1553       // we really can't do very much here - just try to concatenate strings
1554       // where property collisions occur.
1555       Enumeration key = toappend.getProperties().keys();
1556       while (key.hasMoreElements())
1557       {
1558         Object k = key.nextElement();
1559         Object ourval = this.getProperty(k);
1560         Object toapprop = toappend.getProperty(k);
1561         if (ourval != null)
1562         {
1563           if (ourval.getClass().equals(toapprop.getClass())
1564                   && !ourval.equals(toapprop))
1565           {
1566             if (ourval instanceof String)
1567             {
1568               // append strings
1569               this.setProperty(k,
1570                       ((String) ourval) + "; " + ((String) toapprop));
1571             }
1572             else
1573             {
1574               if (ourval instanceof Vector)
1575               {
1576                 // append vectors
1577                 Enumeration theirv = ((Vector) toapprop).elements();
1578                 while (theirv.hasMoreElements())
1579                 {
1580                   ((Vector) ourval).addElement(theirv);
1581                 }
1582               }
1583             }
1584           }
1585         }
1586         else
1587         {
1588           // just add new property directly
1589           setProperty(k, toapprop);
1590         }
1591
1592       }
1593     }
1594   }
1595
1596   @Override
1597   public AlignmentAnnotation findOrCreateAnnotation(String name,
1598           String calcId, boolean autoCalc, SequenceI seqRef,
1599           SequenceGroup groupRef)
1600   {
1601     if (annotations != null)
1602     {
1603       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1604       {
1605         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1606                 && (calcId == null || annot.getCalcId().equals(calcId))
1607                 && annot.sequenceRef == seqRef
1608                 && annot.groupRef == groupRef)
1609         {
1610           return annot;
1611         }
1612       }
1613     }
1614     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1615             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1616     annot.hasText = false;
1617     if (calcId != null)
1618     {
1619       annot.setCalcId(new String(calcId));
1620     }
1621     annot.autoCalculated = autoCalc;
1622     if (seqRef != null)
1623     {
1624       annot.setSequenceRef(seqRef);
1625     }
1626     annot.groupRef = groupRef;
1627     addAnnotation(annot);
1628
1629     return annot;
1630   }
1631
1632   @Override
1633   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1634   {
1635     AlignmentAnnotation[] alignmentAnnotation = getAlignmentAnnotation();
1636     if (alignmentAnnotation != null)
1637     {
1638       return AlignmentAnnotation.findAnnotation(
1639               Arrays.asList(getAlignmentAnnotation()), calcId);
1640     }
1641     return Arrays.asList(new AlignmentAnnotation[] {});
1642   }
1643
1644   @Override
1645   public Iterable<AlignmentAnnotation> findAnnotations(SequenceI seq,
1646           String calcId, String label)
1647   {
1648     return AlignmentAnnotation.findAnnotations(
1649             Arrays.asList(getAlignmentAnnotation()), seq, calcId, label);
1650   }
1651
1652   @Override
1653   public void moveSelectedSequencesByOne(SequenceGroup sg,
1654           Map<SequenceI, SequenceCollectionI> map, boolean up)
1655   {
1656     synchronized (sequences)
1657     {
1658       if (up)
1659       {
1660
1661         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1662         {
1663           SequenceI seq = sequences.get(i);
1664           if (!sg.getSequences(map).contains(seq))
1665           {
1666             continue;
1667           }
1668
1669           SequenceI temp = sequences.get(i - 1);
1670           if (sg.getSequences(null).contains(temp))
1671           {
1672             continue;
1673           }
1674
1675           sequences.set(i, temp);
1676           sequences.set(i - 1, seq);
1677         }
1678       }
1679       else
1680       {
1681         for (int i = sequences.size() - 2; i > -1; i--)
1682         {
1683           SequenceI seq = sequences.get(i);
1684           if (!sg.getSequences(map).contains(seq))
1685           {
1686             continue;
1687           }
1688
1689           SequenceI temp = sequences.get(i + 1);
1690           if (sg.getSequences(map).contains(temp))
1691           {
1692             continue;
1693           }
1694
1695           sequences.set(i, temp);
1696           sequences.set(i + 1, seq);
1697         }
1698       }
1699
1700     }
1701   }
1702
1703   @Override
1704   public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1705   {
1706     alignmentAnnotation.validateRangeAndDisplay();
1707     if (isNucleotide() && alignmentAnnotation.isValidStruc())
1708     {
1709       hasRNAStructure = true;
1710     }
1711   }
1712
1713   private SequenceI seqrep = null;
1714
1715   /**
1716    *
1717    * @return the representative sequence for this group
1718    */
1719   @Override
1720   public SequenceI getSeqrep()
1721   {
1722     return seqrep;
1723   }
1724
1725   /**
1726    * set the representative sequence for this group. Note - this affects the
1727    * interpretation of the Hidereps attribute.
1728    *
1729    * @param seqrep
1730    *          the seqrep to set (null means no sequence representative)
1731    */
1732   @Override
1733   public void setSeqrep(SequenceI seqrep)
1734   {
1735     this.seqrep = seqrep;
1736   }
1737
1738   /**
1739    *
1740    * @return true if group has a sequence representative
1741    */
1742   @Override
1743   public boolean hasSeqrep()
1744   {
1745     return seqrep != null;
1746   }
1747
1748   @Override
1749   public int getEndRes()
1750   {
1751     return getWidth() - 1;
1752   }
1753
1754   @Override
1755   public int getStartRes()
1756   {
1757     return 0;
1758   }
1759
1760   /*
1761    * In the case of AlignmentI - returns the dataset for the alignment, if set
1762    * (non-Javadoc)
1763    *
1764    * @see jalview.datamodel.AnnotatedCollectionI#getContext()
1765    */
1766   @Override
1767   public AnnotatedCollectionI getContext()
1768   {
1769     return dataset;
1770   }
1771
1772   /**
1773    * Align this alignment like the given (mapped) one.
1774    */
1775   @Override
1776   public int alignAs(AlignmentI al)
1777   {
1778     /*
1779      * Currently retains unmapped gaps (in introns), regaps mapped regions
1780      * (exons)
1781      */
1782     return alignAs(al, false, true);
1783   }
1784
1785   /**
1786    * Align this alignment 'the same as' the given one. Mapped sequences only are
1787    * realigned. If both of the same type (nucleotide/protein) then align both
1788    * identically. If this is nucleotide and the other is protein, make 3 gaps
1789    * for each gap in the protein sequences. If this is protein and the other is
1790    * nucleotide, insert a gap for each 3 gaps (or part thereof) between
1791    * nucleotide bases. If this is protein and the other is nucleotide, gaps
1792    * protein to match the relative ordering of codons in the nucleotide.
1793    *
1794    * Parameters control whether gaps in exon (mapped) and intron (unmapped)
1795    * regions are preserved. Gaps that connect introns to exons are treated
1796    * conservatively, i.e. only preserved if both intron and exon gaps are
1797    * preserved. TODO: check caveats below where the implementation fails
1798    *
1799    * @param al
1800    *          - must have same dataset, and sequences in al must have equivalent
1801    *          dataset sequence and start/end bounds under given mapping
1802    * @param preserveMappedGaps
1803    *          if true, gaps within and between mapped codons are preserved
1804    * @param preserveUnmappedGaps
1805    *          if true, gaps within and between unmapped codons are preserved
1806    */
1807   // @Override
1808   public int alignAs(AlignmentI al, boolean preserveMappedGaps,
1809           boolean preserveUnmappedGaps)
1810   {
1811     // TODO should this method signature be the one in the interface?
1812     // JBPComment - yes - neither flag is used, so should be deleted.
1813     boolean thisIsNucleotide = this.isNucleotide();
1814     boolean thatIsProtein = !al.isNucleotide();
1815     if (!thatIsProtein && !thisIsNucleotide)
1816     {
1817       return AlignmentUtils.alignProteinAsDna(this, al);
1818     }
1819     else if (thatIsProtein && thisIsNucleotide)
1820     {
1821       return AlignmentUtils.alignCdsAsProtein(this, al);
1822     }
1823     return AlignmentUtils.alignAs(this, al);
1824   }
1825
1826   /**
1827    * Returns the alignment in Fasta format. Behaviour of this method is not
1828    * guaranteed between versions.
1829    */
1830   @Override
1831   public String toString()
1832   {
1833     return new FastaFile().print(getSequencesArray(), true);
1834   }
1835
1836   /**
1837    * Returns the set of distinct sequence names. No ordering is guaranteed.
1838    */
1839   @Override
1840   public Set<String> getSequenceNames()
1841   {
1842     Set<String> names = new HashSet<>();
1843     for (SequenceI seq : getSequences())
1844     {
1845       names.add(seq.getName());
1846     }
1847     return names;
1848   }
1849
1850   @Override
1851   public boolean hasValidSequence()
1852   {
1853     boolean hasValidSeq = false;
1854     for (SequenceI seq : getSequences())
1855     {
1856       if ((seq.getEnd() - seq.getStart()) > 0)
1857       {
1858         hasValidSeq = true;
1859         break;
1860       }
1861     }
1862     return hasValidSeq;
1863   }
1864
1865   /**
1866    * Update any mappings to 'virtual' sequences to compatible real ones, if
1867    * present in the added sequences. Returns a count of mappings updated.
1868    *
1869    * @param seqs
1870    * @return
1871    */
1872   @Override
1873   public int realiseMappings(List<SequenceI> seqs)
1874   {
1875     int count = 0;
1876     for (SequenceI seq : seqs)
1877     {
1878       for (AlignedCodonFrame mapping : getCodonFrames())
1879       {
1880         count += mapping.realiseWith(seq);
1881       }
1882     }
1883     return count;
1884   }
1885
1886   /**
1887    * Returns the first AlignedCodonFrame that has a mapping between the given
1888    * dataset sequences
1889    *
1890    * @param mapFrom
1891    * @param mapTo
1892    * @return
1893    */
1894   @Override
1895   public AlignedCodonFrame getMapping(SequenceI mapFrom, SequenceI mapTo)
1896   {
1897     for (AlignedCodonFrame acf : getCodonFrames())
1898     {
1899       if (acf.getAaForDnaSeq(mapFrom) == mapTo)
1900       {
1901         return acf;
1902       }
1903     }
1904     return null;
1905   }
1906
1907   @Override
1908   public boolean setHiddenColumns(HiddenColumns cols)
1909   {
1910     boolean changed = cols == null ? hiddenCols != null
1911             : !cols.equals(hiddenCols);
1912     hiddenCols = cols;
1913     return changed;
1914   }
1915
1916   @Override
1917   public void setupJPredAlignment()
1918   {
1919     SequenceI repseq = getSequenceAt(0);
1920     setSeqrep(repseq);
1921     HiddenColumns cs = new HiddenColumns();
1922     cs.hideList(repseq.getInsertions());
1923     setHiddenColumns(cs);
1924   }
1925
1926   @Override
1927   public HiddenColumns propagateInsertions(SequenceI profileseq,
1928           AlignmentView input)
1929   {
1930     int profsqpos = 0;
1931
1932     char gc = getGapCharacter();
1933     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1934     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1935     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1936     return propagateInsertions(profileseq, origseq, nview);
1937   }
1938
1939   /**
1940    *
1941    * @param profileseq
1942    *          sequence in al which corresponds to origseq
1943    * @param al
1944    *          alignment which is to have gaps inserted into it
1945    * @param origseq
1946    *          sequence corresponding to profileseq which defines gap map for
1947    *          modifying al
1948    */
1949   private HiddenColumns propagateInsertions(SequenceI profileseq,
1950           SequenceI origseq, HiddenColumns hc)
1951   {
1952     // take the set of hidden columns, and the set of gaps in origseq,
1953     // and remove all the hidden gaps from hiddenColumns
1954
1955     // first get the gaps as a Bitset
1956     // then calculate hidden ^ not(gap)
1957     BitSet gaps = origseq.gapBitset();
1958     hc.andNot(gaps);
1959
1960     // for each sequence in the alignment, except the profile sequence,
1961     // insert gaps corresponding to each hidden region but where each hidden
1962     // column region is shifted backwards by the number of preceding visible
1963     // gaps update hidden columns at the same time
1964     HiddenColumns newhidden = new HiddenColumns();
1965
1966     int numGapsBefore = 0;
1967     int gapPosition = 0;
1968     Iterator<int[]> it = hc.iterator();
1969     while (it.hasNext())
1970     {
1971       int[] region = it.next();
1972
1973       // get region coordinates accounting for gaps
1974       // we can rely on gaps not being *in* hidden regions because we already
1975       // removed those
1976       while (gapPosition < region[0])
1977       {
1978         gapPosition++;
1979         if (gaps.get(gapPosition))
1980         {
1981           numGapsBefore++;
1982         }
1983       }
1984
1985       int left = region[0] - numGapsBefore;
1986       int right = region[1] - numGapsBefore;
1987
1988       newhidden.hideColumns(left, right);
1989       padGaps(left, right, profileseq);
1990     }
1991     return newhidden;
1992   }
1993
1994   /**
1995    * Pad gaps in all sequences in alignment except profileseq
1996    *
1997    * @param left
1998    *          position of first gap to insert
1999    * @param right
2000    *          position of last gap to insert
2001    * @param profileseq
2002    *          sequence not to pad
2003    */
2004   private void padGaps(int left, int right, SequenceI profileseq)
2005   {
2006     char gc = getGapCharacter();
2007
2008     // make a string with number of gaps = length of hidden region
2009     StringBuilder sb = new StringBuilder();
2010     for (int g = 0; g < right - left + 1; g++)
2011     {
2012       sb.append(gc);
2013     }
2014
2015     // loop over the sequences and pad with gaps where required
2016     for (int s = 0, ns = getHeight(); s < ns; s++)
2017     {
2018       SequenceI sqobj = getSequenceAt(s);
2019       if ((sqobj != profileseq) && (sqobj.getLength() >= left))
2020       {
2021         String sq = sqobj.getSequenceAsString();
2022         sqobj.setSequence(
2023                 sq.substring(0, left) + sb.toString() + sq.substring(left));
2024       }
2025     }
2026   }
2027
2028   /**
2029    * Returns a map from sequence to position (0, 1,...) in the alignment
2030    */
2031   @Override
2032   public Map<SequenceI, Integer> getSequencePositions()
2033   {
2034     Map<SequenceI, Integer> map = new HashMap<>();
2035
2036     synchronized (sequences)
2037     {
2038       int i = sequences.size();
2039       for (int j = 0; j < i; j++)
2040       {
2041         map.put(sequences.get(j), Integer.valueOf(j));
2042       }
2043     }
2044     return map;
2045   }
2046
2047 }