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