src/jalview/datamodel/Alignment.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.2)
   3  * Copyright (C) 2014 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.io.FastaFile;
  25 import jalview.util.MessageManager;
  26
  27 import java.util.ArrayList;
  28 import java.util.Enumeration;
  29 import java.util.HashSet;
  30 import java.util.Hashtable;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Set;
  34 import java.util.Vector;
  35
  36 /**
  37  * Data structure to hold and manipulate a multiple sequence alignment
  38  */
  39 /**
  40  * @author JimP
  41  *
  42  */
  43 public class Alignment implements AlignmentI
  44 {
  45   protected Alignment dataset;
  46
  47   protected List<SequenceI> sequences;
  48
  49   protected List<SequenceGroup> groups = java.util.Collections
  50           .synchronizedList(new ArrayList<SequenceGroup>());
  51
  52   protected char gapCharacter = '-';
  53
  54   protected int type = NUCLEOTIDE;
  55
  56   public static final int PROTEIN = 0;
  57
  58   public static final int NUCLEOTIDE = 1;
  59
  60   public boolean hasRNAStructure = false;
  61
  62   /** DOCUMENT ME!! */
  63   public AlignmentAnnotation[] annotations;
  64
  65   HiddenSequences hiddenSequences = new HiddenSequences(this);
  66
  67   public Hashtable alignmentProperties;
  68
  69   private void initAlignment(SequenceI[] seqs)
  70   {
  71     int i = 0;
  72
  73     if (jalview.util.Comparison.isNucleotide(seqs))
  74     {
  75       type = NUCLEOTIDE;
  76     }
  77     else
  78     {
  79       type = PROTEIN;
  80     }
  81
  82     sequences = java.util.Collections
  83             .synchronizedList(new ArrayList<SequenceI>());
  84
  85     for (i = 0; i < seqs.length; i++)
  86     {
  87       sequences.add(seqs[i]);
  88     }
  89
  90   }
  91
  92   /**
  93    * Make an alignment from an array of Sequences.
  94    *
  95    * @param sequences
  96    */
  97   public Alignment(SequenceI[] seqs)
  98   {
  99     initAlignment(seqs);
 100   }
 101
 102   /**
 103    * Make a new alignment from an array of SeqCigars
 104    *
 105    * @param seqs
 106    *          SeqCigar[]
 107    */
 108   public Alignment(SeqCigar[] alseqs)
 109   {
 110     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
 111             gapCharacter, new ColumnSelection(), null);
 112     initAlignment(seqs);
 113   }
 114
 115   /**
 116    * Make a new alignment from an CigarArray JBPNote - can only do this when
 117    * compactAlignment does not contain hidden regions. JBPNote - must also check
 118    * that compactAlignment resolves to a set of SeqCigars - or construct them
 119    * appropriately.
 120    *
 121    * @param compactAlignment
 122    *          CigarArray
 123    */
 124   public static AlignmentI createAlignment(CigarArray compactAlignment)
 125   {
 126     throw new Error(MessageManager.getString("error.alignment_cigararray_not_implemented"));
 127     // this(compactAlignment.refCigars);
 128   }
 129
 130   /**
 131    * DOCUMENT ME!
 132    *
 133    * @return DOCUMENT ME!
 134    */
 135   @Override
 136   public List<SequenceI> getSequences()
 137   {
 138     return sequences;
 139   }
 140
 141   @Override
 142   public List<SequenceI> getSequences(
 143           Map<SequenceI, SequenceCollectionI> hiddenReps)
 144   {
 145     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to
 146     // work on this.
 147     return sequences;
 148   }
 149
 150   @Override
 151   public SequenceI[] getSequencesArray()
 152   {
 153     if (sequences == null)
 154     {
 155       return null;
 156     }
 157     synchronized (sequences)
 158     {
 159       return sequences.toArray(new SequenceI[sequences.size()]);
 160     }
 161   }
 162
 163   /**
 164    * Returns a map of lists of sequences keyed by sequence name.
 165    *
 166    * @return
 167    */
 168   @Override
 169   public Map<String, List<SequenceI>> getSequencesByName()
 170   {
 171     return AlignmentUtils.getSequencesByName(this);
 172   }
 173
 174   /**
 175    * DOCUMENT ME!
 176    *
 177    * @param i
 178    *          DOCUMENT ME!
 179    *
 180    * @return DOCUMENT ME!
 181    */
 182   @Override
 183   public SequenceI getSequenceAt(int i)
 184   {
 185     synchronized (sequences)
 186     {
 187       if (i > -1 && i < sequences.size())
 188       {
 189         return sequences.get(i);
 190       }
 191     }
 192     return null;
 193   }
 194
 195   /**
 196    * Adds a sequence to the alignment. Recalculates maxLength and size.
 197    *
 198    * @param snew
 199    */
 200   @Override
 201   public void addSequence(SequenceI snew)
 202   {
 203     if (dataset != null)
 204     {
 205       // maintain dataset integrity
 206       if (snew.getDatasetSequence() != null)
 207       {
 208         getDataset().addSequence(snew.getDatasetSequence());
 209       }
 210       else
 211       {
 212         // derive new sequence
 213         SequenceI adding = snew.deriveSequence();
 214         getDataset().addSequence(adding.getDatasetSequence());
 215         snew = adding;
 216       }
 217     }
 218     if (sequences == null)
 219     {
 220       initAlignment(new SequenceI[]
 221       { snew });
 222     }
 223     else
 224     {
 225       synchronized (sequences)
 226       {
 227         sequences.add(snew);
 228       }
 229     }
 230     if (hiddenSequences != null)
 231     {
 232       hiddenSequences.adjustHeightSequenceAdded();
 233     }
 234   }
 235
 236   /**
 237    * Adds a sequence to the alignment. Recalculates maxLength and size.
 238    *
 239    * @param snew
 240    */
 241   @Override
 242   public void setSequenceAt(int i, SequenceI snew)
 243   {
 244     SequenceI oldseq = getSequenceAt(i);
 245     deleteSequence(i);
 246     synchronized (sequences)
 247     {
 248       sequences.set(i, snew);
 249     }
 250   }
 251
 252   /**
 253    * DOCUMENT ME!
 254    *
 255    * @return DOCUMENT ME!
 256    */
 257   @Override
 258   public List<SequenceGroup> getGroups()
 259   {
 260     return groups;
 261   }
 262
 263   @Override
 264   public void finalize()
 265   {
 266     if (getDataset() != null)
 267     {
 268       getDataset().removeAlignmentRef();
 269     }
 270
 271     dataset = null;
 272     sequences = null;
 273     groups = null;
 274     annotations = null;
 275     hiddenSequences = null;
 276   }
 277
 278   /**
 279    * decrement the alignmentRefs counter by one and call finalize if it goes to
 280    * zero.
 281    */
 282   private void removeAlignmentRef()
 283   {
 284     if (--alignmentRefs == 0)
 285     {
 286       finalize();
 287     }
 288   }
 289
 290   /**
 291    * DOCUMENT ME!
 292    *
 293    * @param s
 294    *          DOCUMENT ME!
 295    */
 296   @Override
 297   public void deleteSequence(SequenceI s)
 298   {
 299     deleteSequence(findIndex(s));
 300   }
 301
 302   /**
 303    * DOCUMENT ME!
 304    *
 305    * @param i
 306    *          DOCUMENT ME!
 307    */
 308   @Override
 309   public void deleteSequence(int i)
 310   {
 311     if (i > -1 && i < getHeight())
 312     {
 313       synchronized (sequences)
 314       {
 315         sequences.remove(i);
 316       }
 317       hiddenSequences.adjustHeightSequenceDeleted(i);
 318     }
 319   }
 320
 321   /*
 322    * (non-Javadoc)
 323    *
 324    * @see jalview.datamodel.AlignmentI#findGroup(jalview.datamodel.SequenceI)
 325    */
 326   @Override
 327   public SequenceGroup findGroup(SequenceI s)
 328   {
 329     synchronized (groups)
 330     {
 331       for (int i = 0; i < this.groups.size(); i++)
 332       {
 333         SequenceGroup sg = groups.get(i);
 334
 335         if (sg.getSequences(null).contains(s))
 336         {
 337           return sg;
 338         }
 339       }
 340     }
 341     return null;
 342   }
 343
 344   /*
 345    * (non-Javadoc)
 346    *
 347    * @see
 348    * jalview.datamodel.AlignmentI#findAllGroups(jalview.datamodel.SequenceI)
 349    */
 350   @Override
 351   public SequenceGroup[] findAllGroups(SequenceI s)
 352   {
 353     ArrayList<SequenceGroup> temp = new ArrayList<SequenceGroup>();
 354
 355     synchronized (groups)
 356     {
 357       int gSize = groups.size();
 358       for (int i = 0; i < gSize; i++)
 359       {
 360         SequenceGroup sg = groups.get(i);
 361         if (sg == null || sg.getSequences(null) == null)
 362         {
 363           this.deleteGroup(sg);
 364           gSize--;
 365           continue;
 366         }
 367
 368         if (sg.getSequences(null).contains(s))
 369         {
 370           temp.add(sg);
 371         }
 372       }
 373     }
 374     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 375     return temp.toArray(ret);
 376   }
 377
 378   /**    */
 379   @Override
 380   public void addGroup(SequenceGroup sg)
 381   {
 382     synchronized (groups)
 383     {
 384       if (!groups.contains(sg))
 385       {
 386         if (hiddenSequences.getSize() > 0)
 387         {
 388           int i, iSize = sg.getSize();
 389           for (i = 0; i < iSize; i++)
 390           {
 391             if (!sequences.contains(sg.getSequenceAt(i)))
 392             {
 393               sg.deleteSequence(sg.getSequenceAt(i), false);
 394               iSize--;
 395               i--;
 396             }
 397           }
 398
 399           if (sg.getSize() < 1)
 400           {
 401             return;
 402           }
 403         }
 404         sg.setContext(this);
 405         groups.add(sg);
 406       }
 407     }
 408   }
 409
 410   /**
 411    * remove any annotation that references gp
 412    *
 413    * @param gp
 414    *          (if null, removes all group associated annotation)
 415    */
 416   private void removeAnnotationForGroup(SequenceGroup gp)
 417   {
 418     if (annotations == null || annotations.length == 0)
 419     {
 420       return;
 421     }
 422     // remove annotation very quickly
 423     AlignmentAnnotation[] t, todelete = new AlignmentAnnotation[annotations.length], tokeep = new AlignmentAnnotation[annotations.length];
 424     int i, p, k;
 425     if (gp == null)
 426     {
 427       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 428       {
 429         if (annotations[i].groupRef != null)
 430         {
 431           todelete[p++] = annotations[i];
 432         }
 433         else
 434         {
 435           tokeep[k++] = annotations[i];
 436         }
 437       }
 438     }
 439     else
 440     {
 441       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 442       {
 443         if (annotations[i].groupRef == gp)
 444         {
 445           todelete[p++] = annotations[i];
 446         }
 447         else
 448         {
 449           tokeep[k++] = annotations[i];
 450         }
 451       }
 452     }
 453     if (p > 0)
 454     {
 455       // clear out the group associated annotation.
 456       for (i = 0; i < p; i++)
 457       {
 458         unhookAnnotation(todelete[i]);
 459         todelete[i] = null;
 460       }
 461       t = new AlignmentAnnotation[k];
 462       for (i = 0; i < k; i++)
 463       {
 464         t[i] = tokeep[i];
 465       }
 466       annotations = t;
 467     }
 468   }
 469
 470   @Override
 471   public void deleteAllGroups()
 472   {
 473     synchronized (groups)
 474     {
 475       if (annotations != null)
 476       {
 477         removeAnnotationForGroup(null);
 478       }
 479       for (SequenceGroup sg : groups)
 480       {
 481         sg.setContext(null);
 482       }
 483       groups.clear();
 484     }
 485   }
 486
 487   /**    */
 488   @Override
 489   public void deleteGroup(SequenceGroup g)
 490   {
 491     synchronized (groups)
 492     {
 493       if (groups.contains(g))
 494       {
 495         removeAnnotationForGroup(g);
 496         groups.remove(g);
 497         g.setContext(null);
 498       }
 499     }
 500   }
 501
 502   /**    */
 503   @Override
 504   public SequenceI findName(String name)
 505   {
 506     return findName(name, false);
 507   }
 508
 509   /*
 510    * (non-Javadoc)
 511    *
 512    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 513    */
 514   @Override
 515   public SequenceI findName(String token, boolean b)
 516   {
 517     return findName(null, token, b);
 518   }
 519
 520   /*
 521    * (non-Javadoc)
 522    *
 523    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 524    * boolean)
 525    */
 526   @Override
 527   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 528   {
 529
 530     int i = 0;
 531     SequenceI sq = null;
 532     String sqname = null;
 533     if (startAfter != null)
 534     {
 535       // try to find the sequence in the alignment
 536       boolean matched = false;
 537       while (i < sequences.size())
 538       {
 539         if (getSequenceAt(i++) == startAfter)
 540         {
 541           matched = true;
 542           break;
 543         }
 544       }
 545       if (!matched)
 546       {
 547         i = 0;
 548       }
 549     }
 550     while (i < sequences.size())
 551     {
 552       sq = getSequenceAt(i);
 553       sqname = sq.getName();
 554       if (sqname.equals(token) // exact match
 555               || (b && // allow imperfect matches - case varies
 556               (sqname.equalsIgnoreCase(token))))
 557       {
 558         return getSequenceAt(i);
 559       }
 560
 561       i++;
 562     }
 563
 564     return null;
 565   }
 566
 567   @Override
 568   public SequenceI[] findSequenceMatch(String name)
 569   {
 570     Vector matches = new Vector();
 571     int i = 0;
 572
 573     while (i < sequences.size())
 574     {
 575       if (getSequenceAt(i).getName().equals(name))
 576       {
 577         matches.addElement(getSequenceAt(i));
 578       }
 579       i++;
 580     }
 581
 582     SequenceI[] result = new SequenceI[matches.size()];
 583     for (i = 0; i < result.length; i++)
 584     {
 585       result[i] = (SequenceI) matches.elementAt(i);
 586     }
 587
 588     return result;
 589
 590   }
 591
 592   /*
 593    * (non-Javadoc)
 594    *
 595    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 596    */
 597   @Override
 598   public int findIndex(SequenceI s)
 599   {
 600     int i = 0;
 601
 602     while (i < sequences.size())
 603     {
 604       if (s == getSequenceAt(i))
 605       {
 606         return i;
 607       }
 608
 609       i++;
 610     }
 611
 612     return -1;
 613   }
 614
 615   /*
 616    * (non-Javadoc)
 617    *
 618    * @see
 619    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 620    */
 621   @Override
 622   public int findIndex(SearchResults results)
 623   {
 624     int i = 0;
 625
 626     while (i < sequences.size())
 627     {
 628       if (results.involvesSequence(getSequenceAt(i)))
 629       {
 630         return i;
 631       }
 632       i++;
 633     }
 634     return -1;
 635   }
 636
 637   /**
 638    * DOCUMENT ME!
 639    *
 640    * @return DOCUMENT ME!
 641    */
 642   @Override
 643   public int getHeight()
 644   {
 645     return sequences.size();
 646   }
 647
 648   /**
 649    * DOCUMENT ME!
 650    *
 651    * @return DOCUMENT ME!
 652    */
 653   @Override
 654   public int getWidth()
 655   {
 656     int maxLength = -1;
 657
 658     for (int i = 0; i < sequences.size(); i++)
 659     {
 660       if (getSequenceAt(i).getLength() > maxLength)
 661       {
 662         maxLength = getSequenceAt(i).getLength();
 663       }
 664     }
 665
 666     return maxLength;
 667   }
 668
 669   /**
 670    * DOCUMENT ME!
 671    *
 672    * @param gc
 673    *          DOCUMENT ME!
 674    */
 675   @Override
 676   public void setGapCharacter(char gc)
 677   {
 678     gapCharacter = gc;
 679     synchronized (sequences)
 680     {
 681       for (SequenceI seq : sequences)
 682       {
 683         seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 684                 .replace('-', gc).replace(' ', gc));
 685       }
 686     }
 687   }
 688
 689   /**
 690    * DOCUMENT ME!
 691    *
 692    * @return DOCUMENT ME!
 693    */
 694   @Override
 695   public char getGapCharacter()
 696   {
 697     return gapCharacter;
 698   }
 699
 700   /*
 701    * (non-Javadoc)
 702    *
 703    * @see jalview.datamodel.AlignmentI#isAligned()
 704    */
 705   @Override
 706   public boolean isAligned()
 707   {
 708     return isAligned(false);
 709   }
 710
 711   /*
 712    * (non-Javadoc)
 713    *
 714    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 715    */
 716   @Override
 717   public boolean isAligned(boolean includeHidden)
 718   {
 719     int width = getWidth();
 720     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 721     {
 722       includeHidden = true; // no hidden sequences to check against.
 723     }
 724     for (int i = 0; i < sequences.size(); i++)
 725     {
 726       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 727       {
 728         if (getSequenceAt(i).getLength() != width)
 729         {
 730           return false;
 731         }
 732       }
 733     }
 734
 735     return true;
 736   }
 737
 738   /*
 739    * (non-Javadoc)
 740    *
 741    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 742    * AlignmentAnnotation)
 743    */
 744   @Override
 745   public boolean deleteAnnotation(AlignmentAnnotation aa)
 746   {
 747     return deleteAnnotation(aa, true);
 748   }
 749
 750   @Override
 751   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 752   {
 753     int aSize = 1;
 754
 755     if (annotations != null)
 756     {
 757       aSize = annotations.length;
 758     }
 759
 760     if (aSize < 1)
 761     {
 762       return false;
 763     }
 764
 765     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 766
 767     boolean swap = false;
 768     int tIndex = 0;
 769
 770     for (int i = 0; i < aSize; i++)
 771     {
 772       if (annotations[i] == aa)
 773       {
 774         swap = true;
 775         continue;
 776       }
 777       if (tIndex < temp.length)
 778       {
 779         temp[tIndex++] = annotations[i];
 780       }
 781     }
 782
 783     if (swap)
 784     {
 785       annotations = temp;
 786       if (unhook)
 787       {
 788         unhookAnnotation(aa);
 789       }
 790     }
 791     return swap;
 792   }
 793
 794   /**
 795    * remove any object references associated with this annotation
 796    *
 797    * @param aa
 798    */
 799   private void unhookAnnotation(AlignmentAnnotation aa)
 800   {
 801     if (aa.sequenceRef != null)
 802     {
 803       aa.sequenceRef.removeAlignmentAnnotation(aa);
 804     }
 805     if (aa.groupRef != null)
 806     {
 807       // probably need to do more here in the future (post 2.5.0)
 808       aa.groupRef = null;
 809     }
 810   }
 811
 812   /*
 813    * (non-Javadoc)
 814    *
 815    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 816    * AlignmentAnnotation)
 817    */
 818   @Override
 819   public void addAnnotation(AlignmentAnnotation aa)
 820   {
 821     addAnnotation(aa, -1);
 822   }
 823
 824   /*
 825    * (non-Javadoc)
 826    *
 827    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 828    * AlignmentAnnotation, int)
 829    */
 830   @Override
 831   public void addAnnotation(AlignmentAnnotation aa, int pos)
 832   {
 833     if (aa.getRNAStruc() != null)
 834     {
 835       hasRNAStructure = true;
 836     }
 837
 838     int aSize = 1;
 839     if (annotations != null)
 840     {
 841       aSize = annotations.length + 1;
 842     }
 843
 844     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 845     int i = 0;
 846     if (pos == -1 || pos >= aSize)
 847     {
 848       temp[aSize - 1] = aa;
 849     }
 850     else
 851     {
 852       temp[pos] = aa;
 853     }
 854     if (aSize > 1)
 855     {
 856       int p = 0;
 857       for (i = 0; i < (aSize - 1); i++, p++)
 858       {
 859         if (p == pos)
 860         {
 861           p++;
 862         }
 863         if (p < temp.length)
 864         {
 865           temp[p] = annotations[i];
 866         }
 867       }
 868     }
 869
 870     annotations = temp;
 871   }
 872
 873   @Override
 874   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 875   {
 876     if (aa == null || annotations == null || annotations.length - 1 < index)
 877     {
 878       return;
 879     }
 880
 881     int aSize = annotations.length;
 882     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 883
 884     temp[index] = aa;
 885
 886     for (int i = 0; i < aSize; i++)
 887     {
 888       if (i == index)
 889       {
 890         continue;
 891       }
 892
 893       if (i < index)
 894       {
 895         temp[i] = annotations[i];
 896       }
 897       else
 898       {
 899         temp[i] = annotations[i - 1];
 900       }
 901     }
 902
 903     annotations = temp;
 904   }
 905
 906   @Override
 907   /**
 908    * returns all annotation on the alignment
 909    */
 910   public AlignmentAnnotation[] getAlignmentAnnotation()
 911   {
 912     return annotations;
 913   }
 914
 915   @Override
 916   public void setNucleotide(boolean b)
 917   {
 918     if (b)
 919     {
 920       type = NUCLEOTIDE;
 921     }
 922     else
 923     {
 924       type = PROTEIN;
 925     }
 926   }
 927
 928   @Override
 929   public boolean isNucleotide()
 930   {
 931     if (type == NUCLEOTIDE)
 932     {
 933       return true;
 934     }
 935     else
 936     {
 937       return false;
 938     }
 939   }
 940
 941   @Override
 942   public boolean hasRNAStructure()
 943   {
 944     // TODO can it happen that structure is removed from alignment?
 945     return hasRNAStructure;
 946   }
 947
 948   @Override
 949   public void setDataset(Alignment data)
 950   {
 951     if (dataset == null && data == null)
 952     {
 953       // Create a new dataset for this alignment.
 954       // Can only be done once, if dataset is not null
 955       // This will not be performed
 956       SequenceI[] seqs = new SequenceI[getHeight()];
 957       SequenceI currentSeq;
 958       for (int i = 0; i < getHeight(); i++)
 959       {
 960         currentSeq = getSequenceAt(i);
 961         if (currentSeq.getDatasetSequence() != null)
 962         {
 963           seqs[i] = currentSeq.getDatasetSequence();
 964         }
 965         else
 966         {
 967           seqs[i] = currentSeq.createDatasetSequence();
 968         }
 969       }
 970
 971       dataset = new Alignment(seqs);
 972     }
 973     else if (dataset == null && data != null)
 974     {
 975       dataset = data;
 976       for (int i = 0; i < getHeight(); i++)
 977       {
 978         SequenceI currentSeq = getSequenceAt(i);
 979         SequenceI dsq = currentSeq.getDatasetSequence();
 980         if (dsq == null)
 981         {
 982           dsq = currentSeq.createDatasetSequence();
 983           dataset.addSequence(dsq);
 984         }
 985         else
 986         {
 987           while (dsq.getDatasetSequence() != null)
 988           {
 989             dsq = dsq.getDatasetSequence();
 990           }
 991           if (dataset.findIndex(dsq) == -1)
 992           {
 993             dataset.addSequence(dsq);
 994           }
 995         }
 996       }
 997     }
 998     dataset.addAlignmentRef();
 999   }
1000
1001   /**
1002    * reference count for number of alignments referencing this one.
1003    */
1004   int alignmentRefs = 0;
1005
1006   /**
1007    * increase reference count to this alignment.
1008    */
1009   private void addAlignmentRef()
1010   {
1011     alignmentRefs++;
1012   }
1013
1014   @Override
1015   public Alignment getDataset()
1016   {
1017     return dataset;
1018   }
1019
1020   @Override
1021   public boolean padGaps()
1022   {
1023     boolean modified = false;
1024
1025     // Remove excess gaps from the end of alignment
1026     int maxLength = -1;
1027
1028     SequenceI current;
1029     for (int i = 0; i < sequences.size(); i++)
1030     {
1031       current = getSequenceAt(i);
1032       for (int j = current.getLength(); j > maxLength; j--)
1033       {
1034         if (j > maxLength
1035                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
1036         {
1037           maxLength = j;
1038           break;
1039         }
1040       }
1041     }
1042
1043     maxLength++;
1044
1045     int cLength;
1046     for (int i = 0; i < sequences.size(); i++)
1047     {
1048       current = getSequenceAt(i);
1049       cLength = current.getLength();
1050
1051       if (cLength < maxLength)
1052       {
1053         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
1054         modified = true;
1055       }
1056       else if (current.getLength() > maxLength)
1057       {
1058         current.deleteChars(maxLength, current.getLength());
1059       }
1060     }
1061     return modified;
1062   }
1063
1064   /**
1065    * Justify the sequences to the left or right by deleting and inserting gaps
1066    * before the initial residue or after the terminal residue
1067    *
1068    * @param right
1069    *          true if alignment padded to right, false to justify to left
1070    * @return true if alignment was changed
1071    */
1072   @Override
1073   public boolean justify(boolean right)
1074   {
1075     boolean modified = false;
1076
1077     // Remove excess gaps from the end of alignment
1078     int maxLength = -1;
1079     int ends[] = new int[sequences.size() * 2];
1080     SequenceI current;
1081     for (int i = 0; i < sequences.size(); i++)
1082     {
1083       current = getSequenceAt(i);
1084       // This should really be a sequence method
1085       ends[i * 2] = current.findIndex(current.getStart());
1086       ends[i * 2 + 1] = current.findIndex(current.getStart()
1087               + current.getLength());
1088       boolean hitres = false;
1089       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1090       {
1091         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1092         {
1093           if (!hitres)
1094           {
1095             ends[i * 2] = j;
1096             hitres = true;
1097           }
1098           else
1099           {
1100             ends[i * 2 + 1] = j;
1101             if (j - ends[i * 2] > maxLength)
1102             {
1103               maxLength = j - ends[i * 2];
1104             }
1105           }
1106         }
1107       }
1108     }
1109
1110     maxLength++;
1111     // now edit the flanking gaps to justify to either left or right
1112     int cLength, extent, diff;
1113     for (int i = 0; i < sequences.size(); i++)
1114     {
1115       current = getSequenceAt(i);
1116
1117       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1118       diff = maxLength - cLength; // number of gaps to indent
1119       extent = current.getLength();
1120       if (right)
1121       {
1122         // right justify
1123         if (extent > ends[i * 2 + 1])
1124         {
1125           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1126           modified = true;
1127         }
1128         if (ends[i * 2] > diff)
1129         {
1130           current.deleteChars(0, ends[i * 2] - diff);
1131           modified = true;
1132         }
1133         else
1134         {
1135           if (ends[i * 2] < diff)
1136           {
1137             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1138             modified = true;
1139           }
1140         }
1141       }
1142       else
1143       {
1144         // left justify
1145         if (ends[i * 2] > 0)
1146         {
1147           current.deleteChars(0, ends[i * 2]);
1148           modified = true;
1149           ends[i * 2 + 1] -= ends[i * 2];
1150           extent -= ends[i * 2];
1151         }
1152         if (extent > maxLength)
1153         {
1154           current.deleteChars(maxLength + 1, extent);
1155           modified = true;
1156         }
1157         else
1158         {
1159           if (extent < maxLength)
1160           {
1161             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1162             modified = true;
1163           }
1164         }
1165       }
1166     }
1167     return modified;
1168   }
1169
1170   @Override
1171   public HiddenSequences getHiddenSequences()
1172   {
1173     return hiddenSequences;
1174   }
1175
1176   @Override
1177   public CigarArray getCompactAlignment()
1178   {
1179     synchronized (sequences)
1180     {
1181       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1182       int i = 0;
1183       for (SequenceI seq : sequences)
1184       {
1185         alseqs[i++] = new SeqCigar(seq);
1186       }
1187       CigarArray cal = new CigarArray(alseqs);
1188       cal.addOperation(CigarArray.M, getWidth());
1189       return cal;
1190     }
1191   }
1192
1193   @Override
1194   public void setProperty(Object key, Object value)
1195   {
1196     if (alignmentProperties == null)
1197     {
1198       alignmentProperties = new Hashtable();
1199     }
1200
1201     alignmentProperties.put(key, value);
1202   }
1203
1204   @Override
1205   public Object getProperty(Object key)
1206   {
1207     if (alignmentProperties != null)
1208     {
1209       return alignmentProperties.get(key);
1210     }
1211     else
1212     {
1213       return null;
1214     }
1215   }
1216
1217   @Override
1218   public Hashtable getProperties()
1219   {
1220     return alignmentProperties;
1221   }
1222
1223   AlignedCodonFrame[] codonFrameList = null;
1224
1225   /*
1226    * (non-Javadoc)
1227    *
1228    * @see
1229    * jalview.datamodel.AlignmentI#addCodonFrame(jalview.datamodel.AlignedCodonFrame
1230    * )
1231    */
1232   @Override
1233   public void addCodonFrame(AlignedCodonFrame codons)
1234   {
1235     if (codons == null)
1236     {
1237       return;
1238     }
1239     if (codonFrameList == null)
1240     {
1241       codonFrameList = new AlignedCodonFrame[]
1242       { codons };
1243       return;
1244     }
1245     AlignedCodonFrame[] t = new AlignedCodonFrame[codonFrameList.length + 1];
1246     System.arraycopy(codonFrameList, 0, t, 0, codonFrameList.length);
1247     t[codonFrameList.length] = codons;
1248     codonFrameList = t;
1249   }
1250
1251   /*
1252    * (non-Javadoc)
1253    *
1254    * @see jalview.datamodel.AlignmentI#getCodonFrame(int)
1255    */
1256   @Override
1257   public AlignedCodonFrame getCodonFrame(int index)
1258   {
1259     return codonFrameList[index];
1260   }
1261
1262   /*
1263    * (non-Javadoc)
1264    *
1265    * @see
1266    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1267    */
1268   @Override
1269   public AlignedCodonFrame[] getCodonFrame(SequenceI seq)
1270   {
1271     if (seq == null || codonFrameList == null)
1272     {
1273       return null;
1274     }
1275     Vector cframes = new Vector();
1276     for (int f = 0; f < codonFrameList.length; f++)
1277     {
1278       if (codonFrameList[f].involvesSequence(seq))
1279       {
1280         cframes.addElement(codonFrameList[f]);
1281       }
1282     }
1283     if (cframes.size() == 0)
1284     {
1285       return null;
1286     }
1287     AlignedCodonFrame[] cfr = new AlignedCodonFrame[cframes.size()];
1288     cframes.copyInto(cfr);
1289     return cfr;
1290   }
1291
1292   /*
1293    * (non-Javadoc)
1294    *
1295    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1296    */
1297   @Override
1298   public AlignedCodonFrame[] getCodonFrames()
1299   {
1300     return codonFrameList;
1301   }
1302
1303   /*
1304    * (non-Javadoc)
1305    *
1306    * @seejalview.datamodel.AlignmentI#removeCodonFrame(jalview.datamodel.
1307    * AlignedCodonFrame)
1308    */
1309   @Override
1310   public boolean removeCodonFrame(AlignedCodonFrame codons)
1311   {
1312     if (codons == null || codonFrameList == null)
1313     {
1314       return false;
1315     }
1316     boolean removed = false;
1317     int i = 0, iSize = codonFrameList.length;
1318     while (i < iSize)
1319     {
1320       if (codonFrameList[i] == codons)
1321       {
1322         removed = true;
1323         if (i + 1 < iSize)
1324         {
1325           System.arraycopy(codonFrameList, i + 1, codonFrameList, i, iSize
1326                   - i - 1);
1327         }
1328         iSize--;
1329       }
1330       else
1331       {
1332         i++;
1333       }
1334     }
1335     return removed;
1336   }
1337
1338   @Override
1339   public void append(AlignmentI toappend)
1340   {
1341     if (toappend == this)
1342     {
1343       System.err.println("Self append may cause a deadlock.");
1344     }
1345     // TODO test this method for a future 2.5 release
1346     // currently tested for use in jalview.gui.SequenceFetcher
1347     boolean samegap = toappend.getGapCharacter() == getGapCharacter();
1348     char oldc = toappend.getGapCharacter();
1349     boolean hashidden = toappend.getHiddenSequences() != null
1350             && toappend.getHiddenSequences().hiddenSequences != null;
1351     // get all sequences including any hidden ones
1352     List<SequenceI> sqs = (hashidden) ? toappend.getHiddenSequences()
1353             .getFullAlignment().getSequences() : toappend.getSequences();
1354     if (sqs != null)
1355     {
1356       synchronized (sqs)
1357       {
1358         for (SequenceI addedsq : sqs)
1359         {
1360           if (!samegap)
1361           {
1362             char[] oldseq = addedsq.getSequence();
1363             for (int c = 0; c < oldseq.length; c++)
1364             {
1365               if (oldseq[c] == oldc)
1366               {
1367                 oldseq[c] = gapCharacter;
1368               }
1369             }
1370           }
1371           addSequence(addedsq);
1372         }
1373       }
1374     }
1375     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1376     for (int a = 0; alan != null && a < alan.length; a++)
1377     {
1378       addAnnotation(alan[a]);
1379     }
1380     AlignedCodonFrame[] acod = toappend.getCodonFrames();
1381     for (int a = 0; acod != null && a < acod.length; a++)
1382     {
1383       this.addCodonFrame(acod[a]);
1384     }
1385     List<SequenceGroup> sg = toappend.getGroups();
1386     if (sg != null)
1387     {
1388       for (SequenceGroup _sg : sg)
1389       {
1390         addGroup(_sg);
1391       }
1392     }
1393     if (toappend.getHiddenSequences() != null)
1394     {
1395       HiddenSequences hs = toappend.getHiddenSequences();
1396       if (hiddenSequences == null)
1397       {
1398         hiddenSequences = new HiddenSequences(this);
1399       }
1400       if (hs.hiddenSequences != null)
1401       {
1402         for (int s = 0; s < hs.hiddenSequences.length; s++)
1403         {
1404           // hide the newly appended sequence in the alignment
1405           if (hs.hiddenSequences[s] != null)
1406           {
1407             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1408           }
1409         }
1410       }
1411     }
1412     if (toappend.getProperties() != null)
1413     {
1414       // we really can't do very much here - just try to concatenate strings
1415       // where property collisions occur.
1416       Enumeration key = toappend.getProperties().keys();
1417       while (key.hasMoreElements())
1418       {
1419         Object k = key.nextElement();
1420         Object ourval = this.getProperty(k);
1421         Object toapprop = toappend.getProperty(k);
1422         if (ourval != null)
1423         {
1424           if (ourval.getClass().equals(toapprop.getClass())
1425                   && !ourval.equals(toapprop))
1426           {
1427             if (ourval instanceof String)
1428             {
1429               // append strings
1430               this.setProperty(k, ((String) ourval) + "; "
1431                       + ((String) toapprop));
1432             }
1433             else
1434             {
1435               if (ourval instanceof Vector)
1436               {
1437                 // append vectors
1438                 Enumeration theirv = ((Vector) toapprop).elements();
1439                 while (theirv.hasMoreElements())
1440                 {
1441                   ((Vector) ourval).addElement(theirv);
1442                 }
1443               }
1444             }
1445           }
1446         }
1447         else
1448         {
1449           // just add new property directly
1450           setProperty(k, toapprop);
1451         }
1452
1453       }
1454     }
1455   }
1456
1457   @Override
1458   public AlignmentAnnotation findOrCreateAnnotation(String name,
1459           String calcId, boolean autoCalc, SequenceI seqRef,
1460           SequenceGroup groupRef)
1461   {
1462     assert (name != null);
1463     if (annotations != null)
1464     {
1465       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1466       {
1467         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1468                 && (calcId == null || annot.getCalcId().equals(calcId))
1469                 && annot.sequenceRef == seqRef
1470                 && annot.groupRef == groupRef)
1471         {
1472           return annot;
1473         }
1474       }
1475     }
1476     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1477             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1478     annot.hasText = false;
1479     annot.setCalcId(new String(calcId));
1480     annot.autoCalculated = autoCalc;
1481     if (seqRef != null)
1482     {
1483       annot.setSequenceRef(seqRef);
1484     }
1485     annot.groupRef = groupRef;
1486     addAnnotation(annot);
1487
1488     return annot;
1489   }
1490
1491   @Override
1492   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1493   {
1494     ArrayList<AlignmentAnnotation> aa = new ArrayList<AlignmentAnnotation>();
1495     for (AlignmentAnnotation a : getAlignmentAnnotation())
1496     {
1497       if (a.getCalcId() == calcId
1498               || (a.getCalcId() != null && calcId != null && a.getCalcId()
1499                       .equals(calcId)))
1500       {
1501         aa.add(a);
1502       }
1503     }
1504     return aa;
1505   }
1506
1507   /**
1508    * Returns an iterable collection of any annotations that match on given
1509    * sequence ref, calcId and label (ignoring null values).
1510    */
1511   @Override
1512   public Iterable<AlignmentAnnotation> findAnnotations(SequenceI seq,
1513           String calcId, String label)
1514   {
1515     ArrayList<AlignmentAnnotation> aa = new ArrayList<AlignmentAnnotation>();
1516     for (AlignmentAnnotation ann : getAlignmentAnnotation())
1517     {
1518       if (ann.getCalcId() != null && ann.getCalcId().equals(calcId)
1519               && ann.sequenceRef != null && ann.sequenceRef == seq
1520               && ann.label != null && ann.label.equals(label))
1521       {
1522         aa.add(ann);
1523       }
1524     }
1525     return aa;
1526   }
1527
1528   @Override
1529   public void moveSelectedSequencesByOne(SequenceGroup sg,
1530           Map<SequenceI, SequenceCollectionI> map, boolean up)
1531   {
1532     synchronized (sequences)
1533     {
1534       if (up)
1535       {
1536
1537         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1538         {
1539           SequenceI seq = sequences.get(i);
1540           if (!sg.getSequences(map).contains(seq))
1541           {
1542             continue;
1543           }
1544
1545           SequenceI temp = sequences.get(i - 1);
1546           if (sg.getSequences(null).contains(temp))
1547           {
1548             continue;
1549           }
1550
1551           sequences.set(i, temp);
1552           sequences.set(i - 1, seq);
1553         }
1554       }
1555       else
1556       {
1557         for (int i = sequences.size() - 2; i > -1; i--)
1558         {
1559           SequenceI seq = sequences.get(i);
1560           if (!sg.getSequences(map).contains(seq))
1561           {
1562             continue;
1563           }
1564
1565           SequenceI temp = sequences.get(i + 1);
1566           if (sg.getSequences(map).contains(temp))
1567           {
1568             continue;
1569           }
1570
1571           sequences.set(i, temp);
1572           sequences.set(i + 1, seq);
1573         }
1574       }
1575
1576     }
1577   }
1578
1579   @Override
1580   public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1581   {
1582     alignmentAnnotation.validateRangeAndDisplay();
1583     if (isNucleotide() && alignmentAnnotation.isValidStruc())
1584     {
1585       hasRNAStructure = true;
1586     }
1587   }
1588
1589   @Override
1590   public int getEndRes()
1591   {
1592     return getWidth() - 1;
1593   }
1594
1595   @Override
1596   public int getStartRes()
1597   {
1598     return 0;
1599   }
1600
1601   /*
1602    * In the case of AlignmentI - returns the dataset for the alignment, if set
1603    * (non-Javadoc)
1604    *
1605    * @see jalview.datamodel.AnnotatedCollectionI#getContext()
1606    */
1607   @Override
1608   public AnnotatedCollectionI getContext()
1609   {
1610     return dataset;
1611   }
1612
1613   @Override
1614   public int alignAs(AlignmentI al)
1615   {
1616     return alignAs(al, true, true);
1617   }
1618
1619   /**
1620    * Align this alignment 'the same as' the given one. Mapped sequences only are
1621    * realigned. If both of the same type (nucleotide/protein) then align both
1622    * identically. If this is nucleotide and the other is protein, make 3 gaps
1623    * for each gap in the protein sequences. If this is protein and the other is
1624    * nucleotide, insert a gap for each 3 gaps (or part thereof) between
1625    * nucleotide bases. Does nothing if alignment of protein from cDNA is
1626    * requested (not yet implemented).
1627    *
1628    * @param al
1629    */
1630 //  @Override
1631   public int alignAs(AlignmentI al, boolean preserveMappedGaps,
1632           boolean preserveUnmappedGaps)
1633   {
1634     // TODO should this method signature be the one in the interface?
1635     int count = 0;
1636     boolean thisIsNucleotide = this.isNucleotide();
1637     boolean thatIsProtein = !al.isNucleotide();
1638     if (!thatIsProtein && !thisIsNucleotide)
1639     {
1640       System.err
1641               .println("Alignment of protein from cDNA not yet implemented");
1642       return 0;
1643       // todo: build it - a variant of Dna.CdnaTranslate()
1644     }
1645
1646     char thisGapChar = this.getGapCharacter();
1647     String gap = thisIsNucleotide && thatIsProtein ? String
1648             .valueOf(new char[]
1649             { thisGapChar, thisGapChar, thisGapChar }) : String
1650             .valueOf(thisGapChar);
1651
1652     /*
1653      * Get mappings from 'that' alignment's sequences to this.
1654      */
1655     for (SequenceI alignTo : getSequences())
1656     {
1657       count += AlignmentUtils.alignSequenceAs(alignTo, al, gap, preserveMappedGaps,
1658               preserveUnmappedGaps) ? 1 : 0;
1659     }
1660     return count;
1661   }
1662
1663   /**
1664    * Returns the alignment in Fasta format. Behaviour of this method is not
1665    * guaranteed between versions.
1666    */
1667   @Override
1668   public String toString()
1669   {
1670     return new FastaFile().print(getSequencesArray());
1671   }
1672
1673   /**
1674    * Returns the set of distinct sequence names. No ordering is guaranteed.
1675    */
1676   @Override
1677   public Set<String> getSequenceNames()
1678   {
1679     Set<String> names = new HashSet<String>();
1680     for (SequenceI seq : getSequences())
1681     {
1682       names.add(seq.getName());
1683     }
1684     return names;
1685   }
1686 }