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