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