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