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