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