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