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