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