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.HashSet;
  36 import java.util.Hashtable;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.Map;
  40 import java.util.Set;
  41 import java.util.Vector;
  42
  43 /**
  44  * Data structure to hold and manipulate a multiple sequence alignment
  45  */
  46 /**
  47  * @author JimP
  48  *
  49  */
  50 public class Alignment implements AlignmentI
  51 {
  52   private Alignment dataset;
  53
  54   private List<SequenceI> sequences;
  55
  56   protected List<SequenceGroup> groups;
  57
  58   protected char gapCharacter = '-';
  59
  60   private boolean nucleotide = true;
  61
  62   public boolean hasRNAStructure = false;
  63
  64   public AlignmentAnnotation[] annotations;
  65
  66   HiddenSequences hiddenSequences;
  67
  68   HiddenColumns hiddenCols;
  69
  70   public Hashtable alignmentProperties;
  71
  72   private List<AlignedCodonFrame> codonFrameList;
  73
  74   private void initAlignment(SequenceI[] seqs)
  75   {
  76     groups = Collections.synchronizedList(new ArrayList<SequenceGroup>());
  77     hiddenSequences = new HiddenSequences(this);
  78     hiddenCols = new HiddenColumns();
  79     codonFrameList = new ArrayList<>();
  80
  81     nucleotide = Comparison.isNucleotide(seqs);
  82
  83     sequences = Collections.synchronizedList(new ArrayList<SequenceI>());
  84
  85     for (int i = 0; i < seqs.length; i++)
  86     {
  87       sequences.add(seqs[i]);
  88     }
  89
  90   }
  91
  92   /**
  93    * Make a 'copy' alignment - sequences have new copies of features and
  94    * annotations, but share the original dataset sequences.
  95    */
  96   public Alignment(AlignmentI al)
  97   {
  98     SequenceI[] seqs = al.getSequencesArray();
  99     for (int i = 0; i < seqs.length; i++)
 100     {
 101       seqs[i] = new Sequence(seqs[i]);
 102     }
 103
 104     initAlignment(seqs);
 105
 106     /*
 107      * Share the same dataset sequence mappings (if any).
 108      */
 109     if (dataset == null && al.getDataset() == null)
 110     {
 111       this.setCodonFrames(al.getCodonFrames());
 112     }
 113   }
 114
 115   /**
 116    * Make an alignment from an array of Sequences.
 117    *
 118    * @param sequences
 119    */
 120   public Alignment(SequenceI[] seqs)
 121   {
 122     initAlignment(seqs);
 123   }
 124
 125   /**
 126    * Make a new alignment from an array of SeqCigars
 127    *
 128    * @param alseqs
 129    */
 130   public Alignment(SeqCigar[] alseqs)
 131   {
 132     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
 133             gapCharacter, new HiddenColumns(), null);
 134     initAlignment(seqs);
 135   }
 136
 137   /**
 138    * Make a new alignment from an CigarArray JBPNote - can only do this when
 139    * compactAlignment does not contain hidden regions. JBPNote - must also check
 140    * that compactAlignment resolves to a set of SeqCigars - or construct them
 141    * appropriately.
 142    *
 143    * @param compactAlignment
 144    *          CigarArray
 145    */
 146   public static AlignmentI createAlignment(CigarArray compactAlignment)
 147   {
 148     throw new Error(MessageManager
 149             .getString("error.alignment_cigararray_not_implemented"));
 150     // this(compactAlignment.refCigars);
 151   }
 152
 153   @Override
 154   public List<SequenceI> getSequences()
 155   {
 156     return sequences;
 157   }
 158
 159   @Override
 160   public List<SequenceI> getSequences(
 161           Map<SequenceI, SequenceCollectionI> hiddenReps)
 162   {
 163     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to
 164     // work on this.
 165     return sequences;
 166   }
 167
 168   @Override
 169   public SequenceI[] getSequencesArray()
 170   {
 171     if (sequences == null)
 172     {
 173       return null;
 174     }
 175     synchronized (sequences)
 176     {
 177       return sequences.toArray(new SequenceI[sequences.size()]);
 178     }
 179   }
 180
 181   /**
 182    * Returns a map of lists of sequences keyed by sequence name.
 183    *
 184    * @return
 185    */
 186   @Override
 187   public Map<String, List<SequenceI>> getSequencesByName()
 188   {
 189     return AlignmentUtils.getSequencesByName(this);
 190   }
 191
 192   @Override
 193   public SequenceI getSequenceAt(int i)
 194   {
 195     synchronized (sequences)
 196     {
 197
 198       if (i > -1 && i < sequences.size())
 199       {
 200         return sequences.get(i);
 201       }
 202     }
 203
 204     return null;
 205   }
 206
 207   @Override
 208   public SequenceI getSequenceAtAbsoluteIndex(int i)
 209   {
 210     SequenceI seq = null;
 211     if (getHiddenSequences().getSize() > 0)
 212     {
 213       seq = getHiddenSequences().getHiddenSequence(i);
 214       if (seq == null)
 215       {
 216         // didn't find the sequence in the hidden sequences, get it from the
 217         // alignment
 218         int index = getHiddenSequences().findIndexWithoutHiddenSeqs(i);
 219         seq = getSequenceAt(index);
 220       }
 221     }
 222     else
 223     {
 224       seq = getSequenceAt(i);
 225     }
 226     return seq;
 227   }
 228
 229   /**
 230    * Adds a sequence to the alignment. Recalculates maxLength and size. Note
 231    * this currently does not recalculate whether or not the alignment is
 232    * nucleotide, so mixed alignments may have undefined behaviour.
 233    *
 234    * @param snew
 235    */
 236   @Override
 237   public void addSequence(SequenceI snew)
 238   {
 239     if (dataset != null)
 240     {
 241
 242       // maintain dataset integrity
 243       SequenceI dsseq = snew.getDatasetSequence();
 244       if (dsseq == null)
 245       {
 246         // derive new sequence
 247         SequenceI adding = snew.deriveSequence();
 248         snew = adding;
 249         dsseq = snew.getDatasetSequence();
 250       }
 251       if (getDataset().findIndex(dsseq) == -1)
 252       {
 253         getDataset().addSequence(dsseq);
 254       }
 255
 256     }
 257     if (sequences == null)
 258     {
 259       initAlignment(new SequenceI[] { snew });
 260     }
 261     else
 262     {
 263       synchronized (sequences)
 264       {
 265         sequences.add(snew);
 266       }
 267     }
 268     if (hiddenSequences != null)
 269     {
 270       hiddenSequences.adjustHeightSequenceAdded();
 271     }
 272   }
 273
 274   @Override
 275   public SequenceI replaceSequenceAt(int i, SequenceI snew)
 276   {
 277     synchronized (sequences)
 278     {
 279       if (sequences.size() > i)
 280       {
 281         return sequences.set(i, snew);
 282
 283       }
 284       else
 285       {
 286         sequences.add(snew);
 287         hiddenSequences.adjustHeightSequenceAdded();
 288       }
 289       return null;
 290     }
 291   }
 292
 293   /**
 294    * DOCUMENT ME!
 295    *
 296    * @return DOCUMENT ME!
 297    */
 298   @Override
 299   public List<SequenceGroup> getGroups()
 300   {
 301     return groups;
 302   }
 303
 304   @Override
 305   public void finalize() throws Throwable
 306   {
 307     if (getDataset() != null)
 308     {
 309       getDataset().removeAlignmentRef();
 310     }
 311
 312     nullReferences();
 313     super.finalize();
 314   }
 315
 316   /**
 317    * Defensively nulls out references in case this object is not garbage
 318    * collected
 319    */
 320   void nullReferences()
 321   {
 322     dataset = null;
 323     sequences = null;
 324     groups = null;
 325     annotations = null;
 326     hiddenSequences = null;
 327   }
 328
 329   /**
 330    * decrement the alignmentRefs counter by one and null references if it goes
 331    * to zero.
 332    *
 333    * @throws Throwable
 334    */
 335   private void removeAlignmentRef() throws Throwable
 336   {
 337     if (--alignmentRefs == 0)
 338     {
 339       nullReferences();
 340     }
 341   }
 342
 343   @Override
 344   public void deleteSequence(SequenceI s)
 345   {
 346     synchronized (sequences)
 347     {
 348       deleteSequence(findIndex(s));
 349     }
 350   }
 351
 352   @Override
 353   public void deleteSequence(int i)
 354   {
 355     synchronized (sequences)
 356     {
 357       if (i > -1 && i < getHeight())
 358       {
 359         sequences.remove(i);
 360         hiddenSequences.adjustHeightSequenceDeleted(i);
 361       }
 362     }
 363   }
 364
 365   @Override
 366   public void deleteHiddenSequence(int i)
 367   {
 368     synchronized (sequences)
 369     {
 370       if (i > -1 && i < getHeight())
 371       {
 372         sequences.remove(i);
 373       }
 374     }
 375   }
 376
 377   /*
 378    * (non-Javadoc)
 379    *
 380    * @see jalview.datamodel.AlignmentI#findGroup(jalview.datamodel.SequenceI)
 381    */
 382   @Override
 383   public SequenceGroup findGroup(SequenceI seq, int position)
 384   {
 385     synchronized (groups)
 386     {
 387       for (SequenceGroup sg : groups)
 388       {
 389         if (sg.getSequences(null).contains(seq))
 390         {
 391           if (position >= sg.getStartRes() && position <= sg.getEndRes())
 392           {
 393             return sg;
 394           }
 395         }
 396       }
 397     }
 398     return null;
 399   }
 400
 401   /*
 402    * (non-Javadoc)
 403    *
 404    * @see
 405    * jalview.datamodel.AlignmentI#findAllGroups(jalview.datamodel.SequenceI)
 406    */
 407   @Override
 408   public SequenceGroup[] findAllGroups(SequenceI s)
 409   {
 410     ArrayList<SequenceGroup> temp = new ArrayList<>();
 411
 412     synchronized (groups)
 413     {
 414       int gSize = groups.size();
 415       for (int i = 0; i < gSize; i++)
 416       {
 417         SequenceGroup sg = groups.get(i);
 418         if (sg == null || sg.getSequences() == null)
 419         {
 420           this.deleteGroup(sg);
 421           gSize--;
 422           continue;
 423         }
 424
 425         if (sg.getSequences().contains(s))
 426         {
 427           temp.add(sg);
 428         }
 429       }
 430     }
 431     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 432     return temp.toArray(ret);
 433   }
 434
 435   /**    */
 436   @Override
 437   public void addGroup(SequenceGroup sg)
 438   {
 439     synchronized (groups)
 440     {
 441       if (!groups.contains(sg))
 442       {
 443         if (hiddenSequences.getSize() > 0)
 444         {
 445           int i, iSize = sg.getSize();
 446           for (i = 0; i < iSize; i++)
 447           {
 448             if (!sequences.contains(sg.getSequenceAt(i)))
 449             {
 450               sg.deleteSequence(sg.getSequenceAt(i), false);
 451               iSize--;
 452               i--;
 453             }
 454           }
 455
 456           if (sg.getSize() < 1)
 457           {
 458             return;
 459           }
 460         }
 461         sg.setContext(this, true);
 462         groups.add(sg);
 463       }
 464     }
 465   }
 466
 467   /**
 468    * remove any annotation that references gp
 469    *
 470    * @param gp
 471    *          (if null, removes all group associated annotation)
 472    */
 473   private void removeAnnotationForGroup(SequenceGroup gp)
 474   {
 475     if (annotations == null || annotations.length == 0)
 476     {
 477       return;
 478     }
 479     // remove annotation very quickly
 480     AlignmentAnnotation[] t,
 481             todelete = new AlignmentAnnotation[annotations.length],
 482             tokeep = new AlignmentAnnotation[annotations.length];
 483     int i, p, k;
 484     if (gp == null)
 485     {
 486       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 487       {
 488         if (annotations[i].groupRef != null)
 489         {
 490           todelete[p++] = annotations[i];
 491         }
 492         else
 493         {
 494           tokeep[k++] = annotations[i];
 495         }
 496       }
 497     }
 498     else
 499     {
 500       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 501       {
 502         if (annotations[i].groupRef == gp)
 503         {
 504           todelete[p++] = annotations[i];
 505         }
 506         else
 507         {
 508           tokeep[k++] = annotations[i];
 509         }
 510       }
 511     }
 512     if (p > 0)
 513     {
 514       // clear out the group associated annotation.
 515       for (i = 0; i < p; i++)
 516       {
 517         unhookAnnotation(todelete[i]);
 518         todelete[i] = null;
 519       }
 520       t = new AlignmentAnnotation[k];
 521       for (i = 0; i < k; i++)
 522       {
 523         t[i] = tokeep[i];
 524       }
 525       annotations = t;
 526     }
 527   }
 528
 529   @Override
 530   public void deleteAllGroups()
 531   {
 532     synchronized (groups)
 533     {
 534       if (annotations != null)
 535       {
 536         removeAnnotationForGroup(null);
 537       }
 538       for (SequenceGroup sg : groups)
 539       {
 540         sg.setContext(null, false);
 541       }
 542       groups.clear();
 543     }
 544   }
 545
 546   /**    */
 547   @Override
 548   public void deleteGroup(SequenceGroup g)
 549   {
 550     synchronized (groups)
 551     {
 552       if (groups.contains(g))
 553       {
 554         removeAnnotationForGroup(g);
 555         groups.remove(g);
 556         g.setContext(null, false);
 557       }
 558     }
 559   }
 560
 561   /**    */
 562   @Override
 563   public SequenceI findName(String name)
 564   {
 565     return findName(name, false);
 566   }
 567
 568   /*
 569    * (non-Javadoc)
 570    *
 571    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 572    */
 573   @Override
 574   public SequenceI findName(String token, boolean b)
 575   {
 576     return findName(null, token, b);
 577   }
 578
 579   /*
 580    * (non-Javadoc)
 581    *
 582    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 583    * boolean)
 584    */
 585   @Override
 586   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 587   {
 588
 589     int i = 0;
 590     SequenceI sq = null;
 591     String sqname = null;
 592     int nseq = sequences.size();
 593     if (startAfter != null)
 594     {
 595       // try to find the sequence in the alignment
 596       boolean matched = false;
 597       while (i < nseq)
 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 < nseq)
 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     int nseq = sequences.size();
1193     for (int i = 0; i < nseq; i++)
1194     {
1195       current = getSequenceAt(i);
1196       for (int j = current.getLength(); j > maxLength; j--)
1197       {
1198         if (j > maxLength
1199                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
1200         {
1201           maxLength = j;
1202           break;
1203         }
1204       }
1205     }
1206
1207     maxLength++;
1208
1209     int cLength;
1210     for (int i = 0; i < nseq; i++)
1211     {
1212       current = getSequenceAt(i);
1213       cLength = current.getLength();
1214
1215       if (cLength < maxLength)
1216       {
1217         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
1218         modified = true;
1219       }
1220       else if (current.getLength() > maxLength)
1221       {
1222         current.deleteChars(maxLength, current.getLength());
1223       }
1224     }
1225     return modified;
1226   }
1227
1228   /**
1229    * Justify the sequences to the left or right by deleting and inserting gaps
1230    * before the initial residue or after the terminal residue
1231    *
1232    * @param right
1233    *          true if alignment padded to right, false to justify to left
1234    * @return true if alignment was changed
1235    */
1236   @Override
1237   public boolean justify(boolean right)
1238   {
1239     boolean modified = false;
1240
1241     // Remove excess gaps from the end of alignment
1242     int maxLength = -1;
1243     int ends[] = new int[sequences.size() * 2];
1244     SequenceI current;
1245     for (int i = 0; i < sequences.size(); i++)
1246     {
1247       current = getSequenceAt(i);
1248       // This should really be a sequence method
1249       ends[i * 2] = current.findIndex(current.getStart());
1250       ends[i * 2 + 1] = current
1251               .findIndex(current.getStart() + current.getLength());
1252       boolean hitres = false;
1253       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1254       {
1255         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1256         {
1257           if (!hitres)
1258           {
1259             ends[i * 2] = j;
1260             hitres = true;
1261           }
1262           else
1263           {
1264             ends[i * 2 + 1] = j;
1265             if (j - ends[i * 2] > maxLength)
1266             {
1267               maxLength = j - ends[i * 2];
1268             }
1269           }
1270         }
1271       }
1272     }
1273
1274     maxLength++;
1275     // now edit the flanking gaps to justify to either left or right
1276     int cLength, extent, diff;
1277     for (int i = 0; i < sequences.size(); i++)
1278     {
1279       current = getSequenceAt(i);
1280
1281       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1282       diff = maxLength - cLength; // number of gaps to indent
1283       extent = current.getLength();
1284       if (right)
1285       {
1286         // right justify
1287         if (extent > ends[i * 2 + 1])
1288         {
1289           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1290           modified = true;
1291         }
1292         if (ends[i * 2] > diff)
1293         {
1294           current.deleteChars(0, ends[i * 2] - diff);
1295           modified = true;
1296         }
1297         else
1298         {
1299           if (ends[i * 2] < diff)
1300           {
1301             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1302             modified = true;
1303           }
1304         }
1305       }
1306       else
1307       {
1308         // left justify
1309         if (ends[i * 2] > 0)
1310         {
1311           current.deleteChars(0, ends[i * 2]);
1312           modified = true;
1313           ends[i * 2 + 1] -= ends[i * 2];
1314           extent -= ends[i * 2];
1315         }
1316         if (extent > maxLength)
1317         {
1318           current.deleteChars(maxLength + 1, extent);
1319           modified = true;
1320         }
1321         else
1322         {
1323           if (extent < maxLength)
1324           {
1325             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1326             modified = true;
1327           }
1328         }
1329       }
1330     }
1331     return modified;
1332   }
1333
1334   @Override
1335   public HiddenSequences getHiddenSequences()
1336   {
1337     return hiddenSequences;
1338   }
1339
1340   @Override
1341   public HiddenColumns getHiddenColumns()
1342   {
1343     return hiddenCols;
1344   }
1345
1346   @Override
1347   public CigarArray getCompactAlignment()
1348   {
1349     synchronized (sequences)
1350     {
1351       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1352       int i = 0;
1353       for (SequenceI seq : sequences)
1354       {
1355         alseqs[i++] = new SeqCigar(seq);
1356       }
1357       CigarArray cal = new CigarArray(alseqs);
1358       cal.addOperation(CigarArray.M, getWidth());
1359       return cal;
1360     }
1361   }
1362
1363   @Override
1364   public void setProperty(Object key, Object value)
1365   {
1366     if (alignmentProperties == null)
1367     {
1368       alignmentProperties = new Hashtable();
1369     }
1370
1371     alignmentProperties.put(key, value);
1372   }
1373
1374   @Override
1375   public Object getProperty(Object key)
1376   {
1377     if (alignmentProperties != null)
1378     {
1379       return alignmentProperties.get(key);
1380     }
1381     else
1382     {
1383       return null;
1384     }
1385   }
1386
1387   @Override
1388   public Hashtable getProperties()
1389   {
1390     return alignmentProperties;
1391   }
1392
1393   /**
1394    * Adds the given mapping to the stored set. Note this may be held on the
1395    * dataset alignment.
1396    */
1397   @Override
1398   public void addCodonFrame(AlignedCodonFrame codons)
1399   {
1400     List<AlignedCodonFrame> acfs = getCodonFrames();
1401     if (codons != null && acfs != null && !acfs.contains(codons))
1402     {
1403       acfs.add(codons);
1404     }
1405   }
1406
1407   /*
1408    * (non-Javadoc)
1409    *
1410    * @see
1411    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1412    */
1413   @Override
1414   public List<AlignedCodonFrame> getCodonFrame(SequenceI seq)
1415   {
1416     if (seq == null)
1417     {
1418       return null;
1419     }
1420     List<AlignedCodonFrame> cframes = new ArrayList<>();
1421     for (AlignedCodonFrame acf : getCodonFrames())
1422     {
1423       if (acf.involvesSequence(seq))
1424       {
1425         cframes.add(acf);
1426       }
1427     }
1428     return cframes;
1429   }
1430
1431   /**
1432    * Sets the codon frame mappings (replacing any existing mappings). Note the
1433    * mappings are set on the dataset alignment instead if there is one.
1434    *
1435    * @see jalview.datamodel.AlignmentI#setCodonFrames()
1436    */
1437   @Override
1438   public void setCodonFrames(List<AlignedCodonFrame> acfs)
1439   {
1440     if (dataset != null)
1441     {
1442       dataset.setCodonFrames(acfs);
1443     }
1444     else
1445     {
1446       this.codonFrameList = acfs;
1447     }
1448   }
1449
1450   /**
1451    * Returns the set of codon frame mappings. Any changes to the returned set
1452    * will affect the alignment. The mappings are held on (and read from) the
1453    * dataset alignment if there is one.
1454    *
1455    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1456    */
1457   @Override
1458   public List<AlignedCodonFrame> getCodonFrames()
1459   {
1460     // TODO: Fix this method to fix failing AlignedCodonFrame tests
1461     // this behaviour is currently incorrect. method should return codon frames
1462     // for just the alignment,
1463     // selected from dataset
1464     return dataset != null ? dataset.getCodonFrames() : codonFrameList;
1465   }
1466
1467   /**
1468    * Removes the given mapping from the stored set. Note that the mappings are
1469    * held on the dataset alignment if there is one.
1470    */
1471   @Override
1472   public boolean removeCodonFrame(AlignedCodonFrame codons)
1473   {
1474     List<AlignedCodonFrame> acfs = getCodonFrames();
1475     if (codons == null || acfs == null)
1476     {
1477       return false;
1478     }
1479     return acfs.remove(codons);
1480   }
1481
1482   @Override
1483   public void append(AlignmentI toappend)
1484   {
1485     // TODO JAL-1270 needs test coverage
1486     // currently tested for use in jalview.gui.SequenceFetcher
1487     char oldc = toappend.getGapCharacter();
1488     boolean samegap = oldc == getGapCharacter();
1489     boolean hashidden = toappend.getHiddenSequences() != null
1490             && toappend.getHiddenSequences().hiddenSequences != null;
1491     // get all sequences including any hidden ones
1492     List<SequenceI> sqs = (hashidden)
1493             ? toappend.getHiddenSequences().getFullAlignment()
1494                     .getSequences()
1495             : toappend.getSequences();
1496     if (sqs != null)
1497     {
1498       // avoid self append deadlock by
1499       List<SequenceI> toappendsq = new ArrayList<>();
1500       synchronized (sqs)
1501       {
1502         for (SequenceI addedsq : sqs)
1503         {
1504           if (!samegap)
1505           {
1506             addedsq.replace(oldc, gapCharacter);
1507           }
1508           toappendsq.add(addedsq);
1509         }
1510       }
1511       for (SequenceI addedsq : toappendsq)
1512       {
1513         addSequence(addedsq);
1514       }
1515     }
1516     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1517     for (int a = 0; alan != null && a < alan.length; a++)
1518     {
1519       addAnnotation(alan[a]);
1520     }
1521
1522     // use add method
1523     getCodonFrames().addAll(toappend.getCodonFrames());
1524
1525     List<SequenceGroup> sg = toappend.getGroups();
1526     if (sg != null)
1527     {
1528       for (SequenceGroup _sg : sg)
1529       {
1530         addGroup(_sg);
1531       }
1532     }
1533     if (toappend.getHiddenSequences() != null)
1534     {
1535       HiddenSequences hs = toappend.getHiddenSequences();
1536       if (hiddenSequences == null)
1537       {
1538         hiddenSequences = new HiddenSequences(this);
1539       }
1540       if (hs.hiddenSequences != null)
1541       {
1542         for (int s = 0; s < hs.hiddenSequences.length; s++)
1543         {
1544           // hide the newly appended sequence in the alignment
1545           if (hs.hiddenSequences[s] != null)
1546           {
1547             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1548           }
1549         }
1550       }
1551     }
1552     if (toappend.getProperties() != null)
1553     {
1554       // we really can't do very much here - just try to concatenate strings
1555       // where property collisions occur.
1556       Enumeration key = toappend.getProperties().keys();
1557       while (key.hasMoreElements())
1558       {
1559         Object k = key.nextElement();
1560         Object ourval = this.getProperty(k);
1561         Object toapprop = toappend.getProperty(k);
1562         if (ourval != null)
1563         {
1564           if (ourval.getClass().equals(toapprop.getClass())
1565                   && !ourval.equals(toapprop))
1566           {
1567             if (ourval instanceof String)
1568             {
1569               // append strings
1570               this.setProperty(k,
1571                       ((String) ourval) + "; " + ((String) toapprop));
1572             }
1573             else
1574             {
1575               if (ourval instanceof Vector)
1576               {
1577                 // append vectors
1578                 Enumeration theirv = ((Vector) toapprop).elements();
1579                 while (theirv.hasMoreElements())
1580                 {
1581                   ((Vector) ourval).addElement(theirv);
1582                 }
1583               }
1584             }
1585           }
1586         }
1587         else
1588         {
1589           // just add new property directly
1590           setProperty(k, toapprop);
1591         }
1592
1593       }
1594     }
1595   }
1596
1597   @Override
1598   public AlignmentAnnotation findOrCreateAnnotation(String name,
1599           String calcId, boolean autoCalc, SequenceI seqRef,
1600           SequenceGroup groupRef)
1601   {
1602     if (annotations != null)
1603     {
1604       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1605       {
1606         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1607                 && (calcId == null || annot.getCalcId().equals(calcId))
1608                 && annot.sequenceRef == seqRef
1609                 && annot.groupRef == groupRef)
1610         {
1611           return annot;
1612         }
1613       }
1614     }
1615     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1616             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1617     annot.hasText = false;
1618     if (calcId != null)
1619     {
1620       annot.setCalcId(new String(calcId));
1621     }
1622     annot.autoCalculated = autoCalc;
1623     if (seqRef != null)
1624     {
1625       annot.setSequenceRef(seqRef);
1626     }
1627     annot.groupRef = groupRef;
1628     addAnnotation(annot);
1629
1630     return annot;
1631   }
1632
1633   @Override
1634   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1635   {
1636     AlignmentAnnotation[] alignmentAnnotation = getAlignmentAnnotation();
1637     if (alignmentAnnotation != null)
1638     {
1639       return AlignmentAnnotation.findAnnotation(
1640               Arrays.asList(getAlignmentAnnotation()), calcId);
1641     }
1642     return Arrays.asList(new AlignmentAnnotation[] {});
1643   }
1644
1645   @Override
1646   public Iterable<AlignmentAnnotation> findAnnotations(SequenceI seq,
1647           String calcId, String label)
1648   {
1649     return AlignmentAnnotation.findAnnotations(
1650             Arrays.asList(getAlignmentAnnotation()), seq, calcId, label);
1651   }
1652
1653   @Override
1654   public void moveSelectedSequencesByOne(SequenceGroup sg,
1655           Map<SequenceI, SequenceCollectionI> map, boolean up)
1656   {
1657     synchronized (sequences)
1658     {
1659       if (up)
1660       {
1661
1662         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1663         {
1664           SequenceI seq = sequences.get(i);
1665           if (!sg.getSequences(map).contains(seq))
1666           {
1667             continue;
1668           }
1669
1670           SequenceI temp = sequences.get(i - 1);
1671           if (sg.getSequences(null).contains(temp))
1672           {
1673             continue;
1674           }
1675
1676           sequences.set(i, temp);
1677           sequences.set(i - 1, seq);
1678         }
1679       }
1680       else
1681       {
1682         for (int i = sequences.size() - 2; i > -1; i--)
1683         {
1684           SequenceI seq = sequences.get(i);
1685           if (!sg.getSequences(map).contains(seq))
1686           {
1687             continue;
1688           }
1689
1690           SequenceI temp = sequences.get(i + 1);
1691           if (sg.getSequences(map).contains(temp))
1692           {
1693             continue;
1694           }
1695
1696           sequences.set(i, temp);
1697           sequences.set(i + 1, seq);
1698         }
1699       }
1700
1701     }
1702   }
1703
1704   @Override
1705   public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1706   {
1707     alignmentAnnotation.validateRangeAndDisplay();
1708     if (isNucleotide() && alignmentAnnotation.isValidStruc())
1709     {
1710       hasRNAStructure = true;
1711     }
1712   }
1713
1714   private SequenceI seqrep = null;
1715
1716   /**
1717    *
1718    * @return the representative sequence for this group
1719    */
1720   @Override
1721   public SequenceI getSeqrep()
1722   {
1723     return seqrep;
1724   }
1725
1726   /**
1727    * set the representative sequence for this group. Note - this affects the
1728    * interpretation of the Hidereps attribute.
1729    *
1730    * @param seqrep
1731    *          the seqrep to set (null means no sequence representative)
1732    */
1733   @Override
1734   public void setSeqrep(SequenceI seqrep)
1735   {
1736     this.seqrep = seqrep;
1737   }
1738
1739   /**
1740    *
1741    * @return true if group has a sequence representative
1742    */
1743   @Override
1744   public boolean hasSeqrep()
1745   {
1746     return seqrep != null;
1747   }
1748
1749   @Override
1750   public int getEndRes()
1751   {
1752     return getWidth() - 1;
1753   }
1754
1755   @Override
1756   public int getStartRes()
1757   {
1758     return 0;
1759   }
1760
1761   /*
1762    * In the case of AlignmentI - returns the dataset for the alignment, if set
1763    * (non-Javadoc)
1764    *
1765    * @see jalview.datamodel.AnnotatedCollectionI#getContext()
1766    */
1767   @Override
1768   public AnnotatedCollectionI getContext()
1769   {
1770     return dataset;
1771   }
1772
1773   /**
1774    * Align this alignment like the given (mapped) one.
1775    */
1776   @Override
1777   public int alignAs(AlignmentI al)
1778   {
1779     /*
1780      * Currently retains unmapped gaps (in introns), regaps mapped regions
1781      * (exons)
1782      */
1783     return alignAs(al, false, true);
1784   }
1785
1786   /**
1787    * Align this alignment 'the same as' the given one. Mapped sequences only are
1788    * realigned. If both of the same type (nucleotide/protein) then align both
1789    * identically. If this is nucleotide and the other is protein, make 3 gaps
1790    * for each gap in the protein sequences. If this is protein and the other is
1791    * nucleotide, insert a gap for each 3 gaps (or part thereof) between
1792    * nucleotide bases. If this is protein and the other is nucleotide, gaps
1793    * protein to match the relative ordering of codons in the nucleotide.
1794    *
1795    * Parameters control whether gaps in exon (mapped) and intron (unmapped)
1796    * regions are preserved. Gaps that connect introns to exons are treated
1797    * conservatively, i.e. only preserved if both intron and exon gaps are
1798    * preserved. TODO: check caveats below where the implementation fails
1799    *
1800    * @param al
1801    *          - must have same dataset, and sequences in al must have equivalent
1802    *          dataset sequence and start/end bounds under given mapping
1803    * @param preserveMappedGaps
1804    *          if true, gaps within and between mapped codons are preserved
1805    * @param preserveUnmappedGaps
1806    *          if true, gaps within and between unmapped codons are preserved
1807    */
1808   // @Override
1809   public int alignAs(AlignmentI al, boolean preserveMappedGaps,
1810           boolean preserveUnmappedGaps)
1811   {
1812     // TODO should this method signature be the one in the interface?
1813     // JBPComment - yes - neither flag is used, so should be deleted.
1814     boolean thisIsNucleotide = this.isNucleotide();
1815     boolean thatIsProtein = !al.isNucleotide();
1816     if (!thatIsProtein && !thisIsNucleotide)
1817     {
1818       return AlignmentUtils.alignProteinAsDna(this, al);
1819     }
1820     else if (thatIsProtein && thisIsNucleotide)
1821     {
1822       return AlignmentUtils.alignCdsAsProtein(this, al);
1823     }
1824     return AlignmentUtils.alignAs(this, al);
1825   }
1826
1827   /**
1828    * Returns the alignment in Fasta format. Behaviour of this method is not
1829    * guaranteed between versions.
1830    */
1831   @Override
1832   public String toString()
1833   {
1834     return new FastaFile().print(getSequencesArray(), true);
1835   }
1836
1837   /**
1838    * Returns the set of distinct sequence names. No ordering is guaranteed.
1839    */
1840   @Override
1841   public Set<String> getSequenceNames()
1842   {
1843     Set<String> names = new HashSet<>();
1844     for (SequenceI seq : getSequences())
1845     {
1846       names.add(seq.getName());
1847     }
1848     return names;
1849   }
1850
1851   @Override
1852   public boolean hasValidSequence()
1853   {
1854     boolean hasValidSeq = false;
1855     for (SequenceI seq : getSequences())
1856     {
1857       if ((seq.getEnd() - seq.getStart()) > 0)
1858       {
1859         hasValidSeq = true;
1860         break;
1861       }
1862     }
1863     return hasValidSeq;
1864   }
1865
1866   /**
1867    * Update any mappings to 'virtual' sequences to compatible real ones, if
1868    * present in the added sequences. Returns a count of mappings updated.
1869    *
1870    * @param seqs
1871    * @return
1872    */
1873   @Override
1874   public int realiseMappings(List<SequenceI> seqs)
1875   {
1876     int count = 0;
1877     for (SequenceI seq : seqs)
1878     {
1879       for (AlignedCodonFrame mapping : getCodonFrames())
1880       {
1881         count += mapping.realiseWith(seq);
1882       }
1883     }
1884     return count;
1885   }
1886
1887   /**
1888    * Returns the first AlignedCodonFrame that has a mapping between the given
1889    * dataset sequences
1890    *
1891    * @param mapFrom
1892    * @param mapTo
1893    * @return
1894    */
1895   @Override
1896   public AlignedCodonFrame getMapping(SequenceI mapFrom, SequenceI mapTo)
1897   {
1898     for (AlignedCodonFrame acf : getCodonFrames())
1899     {
1900       if (acf.getAaForDnaSeq(mapFrom) == mapTo)
1901       {
1902         return acf;
1903       }
1904     }
1905     return null;
1906   }
1907
1908   @Override
1909   public boolean setHiddenColumns(HiddenColumns cols)
1910   {
1911     boolean changed = cols == null ? hiddenCols != null
1912             : !cols.equals(hiddenCols);
1913     hiddenCols = cols;
1914     return changed;
1915   }
1916
1917   @Override
1918   public void setupJPredAlignment()
1919   {
1920     SequenceI repseq = getSequenceAt(0);
1921     setSeqrep(repseq);
1922     HiddenColumns cs = new HiddenColumns();
1923     cs.hideList(repseq.getInsertions());
1924     setHiddenColumns(cs);
1925   }
1926
1927   @Override
1928   public HiddenColumns propagateInsertions(SequenceI profileseq,
1929           AlignmentView input)
1930   {
1931     int profsqpos = 0;
1932
1933     char gc = getGapCharacter();
1934     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1935     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1936     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1937     return propagateInsertions(profileseq, origseq, nview);
1938   }
1939
1940   /**
1941    *
1942    * @param profileseq
1943    *          sequence in al which corresponds to origseq
1944    * @param al
1945    *          alignment which is to have gaps inserted into it
1946    * @param origseq
1947    *          sequence corresponding to profileseq which defines gap map for
1948    *          modifying al
1949    */
1950   private HiddenColumns propagateInsertions(SequenceI profileseq,
1951           SequenceI origseq, HiddenColumns hc)
1952   {
1953     // take the set of hidden columns, and the set of gaps in origseq,
1954     // and remove all the hidden gaps from hiddenColumns
1955
1956     // first get the gaps as a Bitset
1957     // then calculate hidden ^ not(gap)
1958     BitSet gaps = origseq.gapBitset();
1959     hc.andNot(gaps);
1960
1961     // for each sequence in the alignment, except the profile sequence,
1962     // insert gaps corresponding to each hidden region but where each hidden
1963     // column region is shifted backwards by the number of preceding visible
1964     // gaps update hidden columns at the same time
1965     HiddenColumns newhidden = new HiddenColumns();
1966
1967     int numGapsBefore = 0;
1968     int gapPosition = 0;
1969     Iterator<int[]> it = hc.iterator();
1970     while (it.hasNext())
1971     {
1972       int[] region = it.next();
1973
1974       // get region coordinates accounting for gaps
1975       // we can rely on gaps not being *in* hidden regions because we already
1976       // removed those
1977       while (gapPosition < region[0])
1978       {
1979         gapPosition++;
1980         if (gaps.get(gapPosition))
1981         {
1982           numGapsBefore++;
1983         }
1984       }
1985
1986       int left = region[0] - numGapsBefore;
1987       int right = region[1] - numGapsBefore;
1988
1989       newhidden.hideColumns(left, right);
1990       padGaps(left, right, profileseq);
1991     }
1992     return newhidden;
1993   }
1994
1995   /**
1996    * Pad gaps in all sequences in alignment except profileseq
1997    *
1998    * @param left
1999    *          position of first gap to insert
2000    * @param right
2001    *          position of last gap to insert
2002    * @param profileseq
2003    *          sequence not to pad
2004    */
2005   private void padGaps(int left, int right, SequenceI profileseq)
2006   {
2007     char gc = getGapCharacter();
2008
2009     // make a string with number of gaps = length of hidden region
2010     StringBuilder sb = new StringBuilder();
2011     for (int g = 0; g < right - left + 1; g++)
2012     {
2013       sb.append(gc);
2014     }
2015
2016     // loop over the sequences and pad with gaps where required
2017     for (int s = 0, ns = getHeight(); s < ns; s++)
2018     {
2019       SequenceI sqobj = getSequenceAt(s);
2020       if ((sqobj != profileseq) && (sqobj.getLength() >= left))
2021       {
2022         String sq = sqobj.getSequenceAsString();
2023         sqobj.setSequence(
2024                 sq.substring(0, left) + sb.toString() + sq.substring(left));
2025       }
2026     }
2027   }
2028
2029 }