JAL-3541 removed clover report generation debug flag (utf-8 encoding enforcement...
[jalview.git] / src / jalview / datamodel / Sequence.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.AlignSeq;
24 import jalview.api.DBRefEntryI;
25 import jalview.datamodel.features.SequenceFeatures;
26 import jalview.datamodel.features.SequenceFeaturesI;
27 import jalview.util.Comparison;
28 import jalview.util.DBRefUtils;
29 import jalview.util.MapList;
30 import jalview.util.StringUtils;
31
32 import java.util.ArrayList;
33 import java.util.Arrays;
34 import java.util.BitSet;
35 import java.util.Collections;
36 import java.util.Enumeration;
37 import java.util.Iterator;
38 import java.util.List;
39 import java.util.ListIterator;
40 import java.util.Vector;
41
42 import fr.orsay.lri.varna.models.rna.RNA;
43
44 /**
45  * 
46  * Implements the SequenceI interface for a char[] based sequence object
47  */
48 public class Sequence extends ASequence implements SequenceI
49 {
50   SequenceI datasetSequence;
51
52   String name;
53
54   private char[] sequence;
55
56   String description;
57
58   int start;
59
60   int end;
61
62   Vector<PDBEntry> pdbIds;
63
64   String vamsasId;
65
66   DBRefEntry[] dbrefs;
67
68   RNA rna;
69
70   /**
71    * This annotation is displayed below the alignment but the positions are tied
72    * to the residues of this sequence
73    *
74    * TODO: change to List<>
75    */
76   Vector<AlignmentAnnotation> annotation;
77
78   private SequenceFeaturesI sequenceFeatureStore;
79
80   /*
81    * A cursor holding the approximate current view position to the sequence,
82    * as determined by findIndex or findPosition or findPositions.
83    * Using a cursor as a hint allows these methods to be more performant for
84    * large sequences.
85    */
86   private SequenceCursor cursor;
87
88   /*
89    * A number that should be incremented whenever the sequence is edited.
90    * If the value matches the cursor token, then we can trust the cursor,
91    * if not then it should be recomputed. 
92    */
93   private int changeCount;
94
95   /**
96    * Creates a new Sequence object.
97    * 
98    * @param name
99    *          display name string
100    * @param sequence
101    *          string to form a possibly gapped sequence out of
102    * @param start
103    *          first position of non-gap residue in the sequence
104    * @param end
105    *          last position of ungapped residues (nearly always only used for
106    *          display purposes)
107    */
108   public Sequence(String name, String sequence, int start, int end)
109   {
110     this();
111     initSeqAndName(name, sequence.toCharArray(), start, end);
112   }
113
114   public Sequence(String name, char[] sequence, int start, int end)
115   {
116     this();
117     initSeqAndName(name, sequence, start, end);
118   }
119
120   /**
121    * Stage 1 constructor - assign name, sequence, and set start and end fields.
122    * start and end are updated values from name2 if it ends with /start-end
123    * 
124    * @param name2
125    * @param sequence2
126    * @param start2
127    * @param end2
128    */
129   protected void initSeqAndName(String name2, char[] sequence2, int start2,
130           int end2)
131   {
132     this.name = name2;
133     this.sequence = sequence2;
134     this.start = start2;
135     this.end = end2;
136     parseId();
137     checkValidRange();
138   }
139
140   /**
141    * If 'name' ends in /i-j, where i >= j > 0 are integers, extracts i and j as
142    * start and end respectively and removes the suffix from the name
143    */
144   void parseId()
145   {
146     if (name == null)
147     {
148       System.err.println(
149               "POSSIBLE IMPLEMENTATION ERROR: null sequence name passed to constructor.");
150       name = "";
151     }
152     int slashPos = name.lastIndexOf('/');
153     if (slashPos > -1 && slashPos < name.length() - 1)
154     {
155       String suffix = name.substring(slashPos + 1);
156       String[] range = suffix.split("-");
157       if (range.length == 2)
158       {
159         try
160         {
161           int from = Integer.valueOf(range[0]);
162           int to = Integer.valueOf(range[1]);
163           if (from > 0 && to >= from)
164           {
165             name = name.substring(0, slashPos);
166             setStart(from);
167             setEnd(to);
168             checkValidRange();
169           }
170         } catch (NumberFormatException e)
171         {
172           // leave name unchanged if suffix is invalid
173         }
174       }
175     }
176   }
177
178   /**
179    * Ensures that 'end' is not before the end of the sequence, that is,
180    * (end-start+1) is at least as long as the count of ungapped positions. Note
181    * that end is permitted to be beyond the end of the sequence data.
182    */
183   void checkValidRange()
184   {
185     // Note: JAL-774 :
186     // http://issues.jalview.org/browse/JAL-774?focusedCommentId=11239&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-11239
187     {
188       int endRes = 0;
189       for (int j = 0; j < sequence.length; j++)
190       {
191         if (!Comparison.isGap(sequence[j]))
192         {
193           endRes++;
194         }
195       }
196       if (endRes > 0)
197       {
198         endRes += start - 1;
199       }
200
201       if (end < endRes)
202       {
203         end = endRes;
204       }
205     }
206
207   }
208
209   /**
210    * default constructor
211    */
212   private Sequence()
213   {
214     sequenceFeatureStore = new SequenceFeatures();
215   }
216
217   /**
218    * Creates a new Sequence object.
219    * 
220    * @param name
221    *          DOCUMENT ME!
222    * @param sequence
223    *          DOCUMENT ME!
224    */
225   public Sequence(String name, String sequence)
226   {
227     this(name, sequence, 1, -1);
228   }
229
230   /**
231    * Creates a new Sequence object with new AlignmentAnnotations but inherits
232    * any existing dataset sequence reference. If non exists, everything is
233    * copied.
234    * 
235    * @param seq
236    *          if seq is a dataset sequence, behaves like a plain old copy
237    *          constructor
238    */
239   public Sequence(SequenceI seq)
240   {
241     this(seq, seq.getAnnotation());
242   }
243
244   /**
245    * Create a new sequence object with new features, DBRefEntries, and PDBIds
246    * but inherits any existing dataset sequence reference, and duplicate of any
247    * annotation that is present in the given annotation array.
248    * 
249    * @param seq
250    *          the sequence to be copied
251    * @param alAnnotation
252    *          an array of annotation including some associated with seq
253    */
254   public Sequence(SequenceI seq, AlignmentAnnotation[] alAnnotation)
255   {
256     this();
257     initSeqFrom(seq, alAnnotation);
258   }
259
260   /**
261    * does the heavy lifting when cloning a dataset sequence, or coping data from
262    * dataset to a new derived sequence.
263    * 
264    * @param seq
265    *          - source of attributes.
266    * @param alAnnotation
267    *          - alignment annotation present on seq that should be copied onto
268    *          this sequence
269    */
270   protected void initSeqFrom(SequenceI seq,
271           AlignmentAnnotation[] alAnnotation)
272   {
273     char[] oseq = seq.getSequence(); // returns a copy of the array
274     initSeqAndName(seq.getName(), oseq, seq.getStart(), seq.getEnd());
275
276     description = seq.getDescription();
277     if (seq != datasetSequence)
278     {
279       setDatasetSequence(seq.getDatasetSequence());
280     }
281     
282     /*
283      * only copy DBRefs and seqfeatures if we really are a dataset sequence
284      */
285     if (datasetSequence == null)
286     {
287       if (seq.getDBRefs() != null)
288       {
289         DBRefEntry[] dbr = seq.getDBRefs();
290         for (int i = 0; i < dbr.length; i++)
291         {
292           addDBRef(new DBRefEntry(dbr[i]));
293         }
294       }
295
296       /*
297        * make copies of any sequence features
298        */
299       for (SequenceFeature sf : seq.getSequenceFeatures())
300       {
301         addSequenceFeature(new SequenceFeature(sf));
302       }
303     }
304
305     if (seq.getAnnotation() != null)
306     {
307       AlignmentAnnotation[] sqann = seq.getAnnotation();
308       for (int i = 0; i < sqann.length; i++)
309       {
310         if (sqann[i] == null)
311         {
312           continue;
313         }
314         boolean found = (alAnnotation == null);
315         if (!found)
316         {
317           for (int apos = 0; !found && apos < alAnnotation.length; apos++)
318           {
319             found = (alAnnotation[apos] == sqann[i]);
320           }
321         }
322         if (found)
323         {
324           // only copy the given annotation
325           AlignmentAnnotation newann = new AlignmentAnnotation(sqann[i]);
326           addAlignmentAnnotation(newann);
327         }
328       }
329     }
330     if (seq.getAllPDBEntries() != null)
331     {
332       Vector<PDBEntry> ids = seq.getAllPDBEntries();
333       for (PDBEntry pdb : ids)
334       {
335         this.addPDBId(new PDBEntry(pdb));
336       }
337     }
338   }
339
340   @Override
341   public void setSequenceFeatures(List<SequenceFeature> features)
342   {
343     if (datasetSequence != null)
344     {
345       datasetSequence.setSequenceFeatures(features);
346       return;
347     }
348     sequenceFeatureStore = new SequenceFeatures(features);
349   }
350
351   @Override
352   public synchronized boolean addSequenceFeature(SequenceFeature sf)
353   {
354     if (sf.getType() == null)
355     {
356       System.err.println("SequenceFeature type may not be null: "
357               + sf.toString());
358       return false;
359     }
360
361     if (datasetSequence != null)
362     {
363       return datasetSequence.addSequenceFeature(sf);
364     }
365
366     return sequenceFeatureStore.add(sf);
367   }
368
369   @Override
370   public void deleteFeature(SequenceFeature sf)
371   {
372     if (datasetSequence != null)
373     {
374       datasetSequence.deleteFeature(sf);
375     }
376     else
377     {
378       sequenceFeatureStore.delete(sf);
379     }
380   }
381
382   /**
383    * {@inheritDoc}
384    * 
385    * @return
386    */
387   @Override
388   public List<SequenceFeature> getSequenceFeatures()
389   {
390     if (datasetSequence != null)
391     {
392       return datasetSequence.getSequenceFeatures();
393     }
394     return sequenceFeatureStore.getAllFeatures();
395   }
396
397   @Override
398   public SequenceFeaturesI getFeatures()
399   {
400     return datasetSequence != null ? datasetSequence.getFeatures()
401             : sequenceFeatureStore;
402   }
403
404   @Override
405   public boolean addPDBId(PDBEntry entry)
406   {
407     if (pdbIds == null)
408     {
409       pdbIds = new Vector<>();
410       pdbIds.add(entry);
411       return true;
412     }
413
414     for (PDBEntry pdbe : pdbIds)
415     {
416       if (pdbe.updateFrom(entry))
417       {
418         return false;
419       }
420     }
421     pdbIds.addElement(entry);
422     return true;
423   }
424
425   /**
426    * DOCUMENT ME!
427    * 
428    * @param id
429    *          DOCUMENT ME!
430    */
431   @Override
432   public void setPDBId(Vector<PDBEntry> id)
433   {
434     pdbIds = id;
435   }
436
437   /**
438    * DOCUMENT ME!
439    * 
440    * @return DOCUMENT ME!
441    */
442   @Override
443   public Vector<PDBEntry> getAllPDBEntries()
444   {
445     return pdbIds == null ? new Vector<>() : pdbIds;
446   }
447
448   /**
449    * Answers the sequence name, with '/start-end' appended if jvsuffix is true
450    * 
451    * @return
452    */
453   @Override
454   public String getDisplayId(boolean jvsuffix)
455   {
456     if (!jvsuffix)
457     {
458       return name;
459     }
460     StringBuilder result = new StringBuilder(name);
461     result.append("/").append(start).append("-").append(end);
462
463     return result.toString();
464   }
465
466   /**
467    * Sets the sequence name. If the name ends in /start-end, then the start-end
468    * values are parsed out and set, and the suffix is removed from the name.
469    * 
470    * @param theName
471    */
472   @Override
473   public void setName(String theName)
474   {
475     this.name = theName;
476     this.parseId();
477   }
478
479   /**
480    * DOCUMENT ME!
481    * 
482    * @return DOCUMENT ME!
483    */
484   @Override
485   public String getName()
486   {
487     return this.name;
488   }
489
490   /**
491    * DOCUMENT ME!
492    * 
493    * @param start
494    *          DOCUMENT ME!
495    */
496   @Override
497   public void setStart(int start)
498   {
499     this.start = start;
500   }
501
502   /**
503    * DOCUMENT ME!
504    * 
505    * @return DOCUMENT ME!
506    */
507   @Override
508   public int getStart()
509   {
510     return this.start;
511   }
512
513   /**
514    * DOCUMENT ME!
515    * 
516    * @param end
517    *          DOCUMENT ME!
518    */
519   @Override
520   public void setEnd(int end)
521   {
522     this.end = end;
523   }
524
525   /**
526    * DOCUMENT ME!
527    * 
528    * @return DOCUMENT ME!
529    */
530   @Override
531   public int getEnd()
532   {
533     return this.end;
534   }
535
536   /**
537    * DOCUMENT ME!
538    * 
539    * @return DOCUMENT ME!
540    */
541   @Override
542   public int getLength()
543   {
544     return this.sequence.length;
545   }
546
547   /**
548    * DOCUMENT ME!
549    * 
550    * @param seq
551    *          DOCUMENT ME!
552    */
553   @Override
554   public void setSequence(String seq)
555   {
556     this.sequence = seq.toCharArray();
557     checkValidRange();
558     sequenceChanged();
559   }
560
561   @Override
562   public String getSequenceAsString()
563   {
564     return new String(sequence);
565   }
566
567   @Override
568   public String getSequenceAsString(int start, int end)
569   {
570     return new String(getSequence(start, end));
571   }
572
573   @Override
574   public char[] getSequence()
575   {
576     // return sequence;
577     return sequence == null ? null : Arrays.copyOf(sequence,
578             sequence.length);
579   }
580
581   /*
582    * (non-Javadoc)
583    * 
584    * @see jalview.datamodel.SequenceI#getSequence(int, int)
585    */
586   @Override
587   public char[] getSequence(int start, int end)
588   {
589     if (start < 0)
590     {
591       start = 0;
592     }
593     // JBPNote - left to user to pad the result here (TODO:Decide on this
594     // policy)
595     if (start >= sequence.length)
596     {
597       return new char[0];
598     }
599
600     if (end >= sequence.length)
601     {
602       end = sequence.length;
603     }
604
605     char[] reply = new char[end - start];
606     System.arraycopy(sequence, start, reply, 0, end - start);
607
608     return reply;
609   }
610
611   @Override
612   public SequenceI getSubSequence(int start, int end)
613   {
614     if (start < 0)
615     {
616       start = 0;
617     }
618     char[] seq = getSequence(start, end);
619     if (seq.length == 0)
620     {
621       return null;
622     }
623     int nstart = findPosition(start);
624     int nend = findPosition(end) - 1;
625     // JBPNote - this is an incomplete copy.
626     SequenceI nseq = new Sequence(this.getName(), seq, nstart, nend);
627     nseq.setDescription(description);
628     if (datasetSequence != null)
629     {
630       nseq.setDatasetSequence(datasetSequence);
631     }
632     else
633     {
634       nseq.setDatasetSequence(this);
635     }
636     return nseq;
637   }
638
639   /**
640    * Returns the character of the aligned sequence at the given position (base
641    * zero), or space if the position is not within the sequence's bounds
642    * 
643    * @return
644    */
645   @Override
646   public char getCharAt(int i)
647   {
648     if (i >= 0 && i < sequence.length)
649     {
650       return sequence[i];
651     }
652     else
653     {
654       return ' ';
655     }
656   }
657
658   /**
659    * Sets the sequence description, and also parses out any special formats of
660    * interest
661    * 
662    * @param desc
663    */
664   @Override
665   public void setDescription(String desc)
666   {
667     this.description = desc;
668   }
669
670   @Override
671   public void setGeneLoci(String speciesId, String assemblyId,
672           String chromosomeId, MapList map)
673   {
674     addDBRef(new GeneLocus(speciesId, assemblyId, chromosomeId,
675             new Mapping(map)));
676   }
677
678   /**
679    * Returns the gene loci mapping for the sequence (may be null)
680    * 
681    * @return
682    */
683   @Override
684   public GeneLociI getGeneLoci()
685   {
686     DBRefEntry[] refs = getDBRefs();
687     if (refs != null)
688     {
689       for (final DBRefEntry ref : refs)
690       {
691         if (ref instanceof GeneLociI)
692         {
693           return (GeneLociI) ref;
694         }
695       }
696     }
697     return null;
698   }
699
700   /**
701    * Answers the description
702    * 
703    * @return
704    */
705   @Override
706   public String getDescription()
707   {
708     return this.description;
709   }
710
711   /**
712    * {@inheritDoc}
713    */
714   @Override
715   public int findIndex(int pos)
716   {
717     /*
718      * use a valid, hopefully nearby, cursor if available
719      */
720     if (isValidCursor(cursor))
721     {
722       return findIndex(pos, cursor);
723     }
724
725     int j = start;
726     int i = 0;
727     int startColumn = 0;
728
729     /*
730      * traverse sequence from the start counting gaps; make a note of
731      * the column of the first residue to save in the cursor
732      */
733     while ((i < sequence.length) && (j <= end) && (j <= pos))
734     {
735       if (!Comparison.isGap(sequence[i]))
736       {
737         if (j == start)
738         {
739           startColumn = i;
740         }
741         j++;
742       }
743       i++;
744     }
745
746     if (j == end && j < pos)
747     {
748       return end + 1;
749     }
750
751     updateCursor(pos, i, startColumn);
752     return i;
753   }
754
755   /**
756    * Updates the cursor to the latest found residue and column position
757    * 
758    * @param residuePos
759    *          (start..)
760    * @param column
761    *          (1..)
762    * @param startColumn
763    *          column position of the first sequence residue
764    */
765   protected void updateCursor(int residuePos, int column, int startColumn)
766   {
767     /*
768      * preserve end residue column provided cursor was valid
769      */
770     int endColumn = isValidCursor(cursor) ? cursor.lastColumnPosition : 0;
771
772     if (residuePos == this.end)
773     {
774       endColumn = column;
775     }
776
777     cursor = new SequenceCursor(this, residuePos, column, startColumn,
778             endColumn, this.changeCount);
779   }
780
781   /**
782    * Answers the aligned column position (1..) for the given residue position
783    * (start..) given a 'hint' of a residue/column location in the neighbourhood.
784    * The hint may be left of, at, or to the right of the required position.
785    * 
786    * @param pos
787    * @param curs
788    * @return
789    */
790   protected int findIndex(final int pos, SequenceCursor curs)
791   {
792     if (!isValidCursor(curs))
793     {
794       /*
795        * wrong or invalidated cursor, compute de novo
796        */
797       return findIndex(pos);
798     }
799
800     if (curs.residuePosition == pos)
801     {
802       return curs.columnPosition;
803     }
804
805     /*
806      * move left or right to find pos from hint.position
807      */
808     int col = curs.columnPosition - 1; // convert from base 1 to base 0
809     int newPos = curs.residuePosition;
810     int delta = newPos > pos ? -1 : 1;
811
812     while (newPos != pos)
813     {
814       col += delta; // shift one column left or right
815       if (col < 0)
816       {
817         break;
818       }
819       if (col == sequence.length)
820       {
821         col--; // return last column if we failed to reach pos
822         break;
823       }
824       if (!Comparison.isGap(sequence[col]))
825       {
826         newPos += delta;
827       }
828     }
829
830     col++; // convert back to base 1
831
832     /*
833      * only update cursor if we found the target position
834      */
835     if (newPos == pos)
836     {
837       updateCursor(pos, col, curs.firstColumnPosition);
838     }
839
840     return col;
841   }
842
843   /**
844    * {@inheritDoc}
845    */
846   @Override
847   public int findPosition(final int column)
848   {
849     /*
850      * use a valid, hopefully nearby, cursor if available
851      */
852     if (isValidCursor(cursor))
853     {
854       return findPosition(column + 1, cursor);
855     }
856     
857     // TODO recode this more naturally i.e. count residues only
858     // as they are found, not 'in anticipation'
859
860     /*
861      * traverse the sequence counting gaps; note the column position
862      * of the first residue, to save in the cursor
863      */
864     int firstResidueColumn = 0;
865     int lastPosFound = 0;
866     int lastPosFoundColumn = 0;
867     int seqlen = sequence.length;
868
869     if (seqlen > 0 && !Comparison.isGap(sequence[0]))
870     {
871       lastPosFound = start;
872       lastPosFoundColumn = 0;
873     }
874
875     int j = 0;
876     int pos = start;
877
878     while (j < column && j < seqlen)
879     {
880       if (!Comparison.isGap(sequence[j]))
881       {
882         lastPosFound = pos;
883         lastPosFoundColumn = j;
884         if (pos == this.start)
885         {
886           firstResidueColumn = j;
887         }
888         pos++;
889       }
890       j++;
891     }
892     if (j < seqlen && !Comparison.isGap(sequence[j]))
893     {
894       lastPosFound = pos;
895       lastPosFoundColumn = j;
896       if (pos == this.start)
897       {
898         firstResidueColumn = j;
899       }
900     }
901
902     /*
903      * update the cursor to the last residue position found (if any)
904      * (converting column position to base 1)
905      */
906     if (lastPosFound != 0)
907     {
908       updateCursor(lastPosFound, lastPosFoundColumn + 1,
909               firstResidueColumn + 1);
910     }
911
912     return pos;
913   }
914
915   /**
916    * Answers true if the given cursor is not null, is for this sequence object,
917    * and has a token value that matches this object's changeCount, else false.
918    * This allows us to ignore a cursor as 'stale' if the sequence has been
919    * modified since the cursor was created.
920    * 
921    * @param curs
922    * @return
923    */
924   protected boolean isValidCursor(SequenceCursor curs)
925   {
926     if (curs == null || curs.sequence != this || curs.token != changeCount)
927     {
928       return false;
929     }
930     /*
931      * sanity check against range
932      */
933     if (curs.columnPosition < 0 || curs.columnPosition > sequence.length)
934     {
935       return false;
936     }
937     if (curs.residuePosition < start || curs.residuePosition > end)
938     {
939       return false;
940     }
941     return true;
942   }
943
944   /**
945    * Answers the sequence position (start..) for the given aligned column
946    * position (1..), given a hint of a cursor in the neighbourhood. The cursor
947    * may lie left of, at, or to the right of the column position.
948    * 
949    * @param col
950    * @param curs
951    * @return
952    */
953   protected int findPosition(final int col, SequenceCursor curs)
954   {
955     if (!isValidCursor(curs))
956     {
957       /*
958        * wrong or invalidated cursor, compute de novo
959        */
960       return findPosition(col - 1);// ugh back to base 0
961     }
962
963     if (curs.columnPosition == col)
964     {
965       cursor = curs; // in case this method becomes public
966       return curs.residuePosition; // easy case :-)
967     }
968
969     if (curs.lastColumnPosition > 0 && curs.lastColumnPosition < col)
970     {
971       /*
972        * sequence lies entirely to the left of col
973        * - return last residue + 1
974        */
975       return end + 1;
976     }
977
978     if (curs.firstColumnPosition > 0 && curs.firstColumnPosition > col)
979     {
980       /*
981        * sequence lies entirely to the right of col
982        * - return first residue
983        */
984       return start;
985     }
986
987     // todo could choose closest to col out of column,
988     // firstColumnPosition, lastColumnPosition as a start point
989
990     /*
991      * move left or right to find pos from cursor position
992      */
993     int firstResidueColumn = curs.firstColumnPosition;
994     int column = curs.columnPosition - 1; // to base 0
995     int newPos = curs.residuePosition;
996     int delta = curs.columnPosition > col ? -1 : 1;
997     boolean gapped = false;
998     int lastFoundPosition = curs.residuePosition;
999     int lastFoundPositionColumn = curs.columnPosition;
1000
1001     while (column != col - 1)
1002     {
1003       column += delta; // shift one column left or right
1004       if (column < 0 || column == sequence.length)
1005       {
1006         break;
1007       }
1008       gapped = Comparison.isGap(sequence[column]);
1009       if (!gapped)
1010       {
1011         newPos += delta;
1012         lastFoundPosition = newPos;
1013         lastFoundPositionColumn = column + 1;
1014         if (lastFoundPosition == this.start)
1015         {
1016           firstResidueColumn = column + 1;
1017         }
1018       }
1019     }
1020
1021     if (cursor == null || lastFoundPosition != cursor.residuePosition)
1022     {
1023       updateCursor(lastFoundPosition, lastFoundPositionColumn,
1024               firstResidueColumn);
1025     }
1026
1027     /*
1028      * hack to give position to the right if on a gap
1029      * or beyond the length of the sequence (see JAL-2562)
1030      */
1031     if (delta > 0 && (gapped || column >= sequence.length))
1032     {
1033       newPos++;
1034     }
1035
1036     return newPos;
1037   }
1038
1039   /**
1040    * {@inheritDoc}
1041    */
1042   @Override
1043   public ContiguousI findPositions(int fromColumn, int toColumn)
1044   {
1045     if (toColumn < fromColumn || fromColumn < 1)
1046     {
1047       return null;
1048     }
1049
1050     /*
1051      * find the first non-gapped position, if any
1052      */
1053     int firstPosition = 0;
1054     int col = fromColumn - 1;
1055     int length = sequence.length;
1056     while (col < length && col < toColumn)
1057     {
1058       if (!Comparison.isGap(sequence[col]))
1059       {
1060         firstPosition = findPosition(col++);
1061         break;
1062       }
1063       col++;
1064     }
1065
1066     if (firstPosition == 0)
1067     {
1068       return null;
1069     }
1070
1071     /*
1072      * find the last non-gapped position
1073      */
1074     int lastPosition = firstPosition;
1075     while (col < length && col < toColumn)
1076     {
1077       if (!Comparison.isGap(sequence[col++]))
1078       {
1079         lastPosition++;
1080       }
1081     }
1082
1083     return new Range(firstPosition, lastPosition);
1084   }
1085
1086   /**
1087    * Returns an int array where indices correspond to each residue in the
1088    * sequence and the element value gives its position in the alignment
1089    * 
1090    * @return int[SequenceI.getEnd()-SequenceI.getStart()+1] or null if no
1091    *         residues in SequenceI object
1092    */
1093   @Override
1094   public int[] gapMap()
1095   {
1096     String seq = jalview.analysis.AlignSeq.extractGaps(
1097             jalview.util.Comparison.GapChars, new String(sequence));
1098     int[] map = new int[seq.length()];
1099     int j = 0;
1100     int p = 0;
1101
1102     while (j < sequence.length)
1103     {
1104       if (!jalview.util.Comparison.isGap(sequence[j]))
1105       {
1106         map[p++] = j;
1107       }
1108
1109       j++;
1110     }
1111
1112     return map;
1113   }
1114
1115   /**
1116    * Build a bitset corresponding to sequence gaps
1117    * 
1118    * @return a BitSet where set values correspond to gaps in the sequence
1119    */
1120   @Override
1121   public BitSet gapBitset()
1122   {
1123     BitSet gaps = new BitSet(sequence.length);
1124     int j = 0;
1125     while (j < sequence.length)
1126     {
1127       if (jalview.util.Comparison.isGap(sequence[j]))
1128       {
1129         gaps.set(j);
1130       }
1131       j++;
1132     }
1133     return gaps;
1134   }
1135
1136   @Override
1137   public int[] findPositionMap()
1138   {
1139     int map[] = new int[sequence.length];
1140     int j = 0;
1141     int pos = start;
1142     int seqlen = sequence.length;
1143     while ((j < seqlen))
1144     {
1145       map[j] = pos;
1146       if (!jalview.util.Comparison.isGap(sequence[j]))
1147       {
1148         pos++;
1149       }
1150
1151       j++;
1152     }
1153     return map;
1154   }
1155
1156   @Override
1157   public List<int[]> getInsertions()
1158   {
1159     ArrayList<int[]> map = new ArrayList<>();
1160     int lastj = -1, j = 0;
1161     int pos = start;
1162     int seqlen = sequence.length;
1163     while ((j < seqlen))
1164     {
1165       if (jalview.util.Comparison.isGap(sequence[j]))
1166       {
1167         if (lastj == -1)
1168         {
1169           lastj = j;
1170         }
1171       }
1172       else
1173       {
1174         if (lastj != -1)
1175         {
1176           map.add(new int[] { lastj, j - 1 });
1177           lastj = -1;
1178         }
1179       }
1180       j++;
1181     }
1182     if (lastj != -1)
1183     {
1184       map.add(new int[] { lastj, j - 1 });
1185       lastj = -1;
1186     }
1187     return map;
1188   }
1189
1190   @Override
1191   public BitSet getInsertionsAsBits()
1192   {
1193     BitSet map = new BitSet();
1194     int lastj = -1, j = 0;
1195     int pos = start;
1196     int seqlen = sequence.length;
1197     while ((j < seqlen))
1198     {
1199       if (jalview.util.Comparison.isGap(sequence[j]))
1200       {
1201         if (lastj == -1)
1202         {
1203           lastj = j;
1204         }
1205       }
1206       else
1207       {
1208         if (lastj != -1)
1209         {
1210           map.set(lastj, j);
1211           lastj = -1;
1212         }
1213       }
1214       j++;
1215     }
1216     if (lastj != -1)
1217     {
1218       map.set(lastj, j);
1219       lastj = -1;
1220     }
1221     return map;
1222   }
1223
1224   @Override
1225   public void deleteChars(final int i, final int j)
1226   {
1227     int newstart = start, newend = end;
1228     if (i >= sequence.length || i < 0)
1229     {
1230       return;
1231     }
1232
1233     char[] tmp = StringUtils.deleteChars(sequence, i, j);
1234     boolean createNewDs = false;
1235     // TODO: take a (second look) at the dataset creation validation method for
1236     // the very large sequence case
1237
1238     int startIndex = findIndex(start) - 1;
1239     int endIndex = findIndex(end) - 1;
1240     int startDeleteColumn = -1; // for dataset sequence deletions
1241     int deleteCount = 0;
1242
1243     for (int s = i; s < j && s < sequence.length; s++)
1244     {
1245       if (Comparison.isGap(sequence[s]))
1246       {
1247         continue;
1248       }
1249       deleteCount++;
1250       if (startDeleteColumn == -1)
1251       {
1252         startDeleteColumn = findPosition(s) - start;
1253       }
1254       if (createNewDs)
1255       {
1256         newend--;
1257       }
1258       else
1259       {
1260         if (startIndex == s)
1261         {
1262           /*
1263            * deleting characters from start of sequence; new start is the
1264            * sequence position of the next column (position to the right
1265            * if the column position is gapped)
1266            */
1267           newstart = findPosition(j);
1268           break;
1269         }
1270         else
1271         {
1272           if (endIndex < j)
1273           {
1274             /*
1275              * deleting characters at end of sequence; new end is the sequence
1276              * position of the column before the deletion; subtract 1 if this is
1277              * gapped since findPosition returns the next sequence position
1278              */
1279             newend = findPosition(i - 1);
1280             if (Comparison.isGap(sequence[i - 1]))
1281             {
1282               newend--;
1283             }
1284             break;
1285           }
1286           else
1287           {
1288             createNewDs = true;
1289             newend--;
1290           }
1291         }
1292       }
1293     }
1294
1295     if (createNewDs && this.datasetSequence != null)
1296     {
1297       /*
1298        * if deletion occured in the middle of the sequence,
1299        * construct a new dataset sequence and delete the residues
1300        * that were deleted from the aligned sequence
1301        */
1302       Sequence ds = new Sequence(datasetSequence);
1303       ds.deleteChars(startDeleteColumn, startDeleteColumn + deleteCount);
1304       datasetSequence = ds;
1305       // TODO: remove any non-inheritable properties ?
1306       // TODO: create a sequence mapping (since there is a relation here ?)
1307     }
1308     start = newstart;
1309     end = newend;
1310     sequence = tmp;
1311     sequenceChanged();
1312   }
1313
1314   @Override
1315   public void insertCharAt(int i, int length, char c)
1316   {
1317     char[] tmp = new char[sequence.length + length];
1318
1319     if (i >= sequence.length)
1320     {
1321       System.arraycopy(sequence, 0, tmp, 0, sequence.length);
1322       i = sequence.length;
1323     }
1324     else
1325     {
1326       System.arraycopy(sequence, 0, tmp, 0, i);
1327     }
1328
1329     int index = i;
1330     while (length > 0)
1331     {
1332       tmp[index++] = c;
1333       length--;
1334     }
1335
1336     if (i < sequence.length)
1337     {
1338       System.arraycopy(sequence, i, tmp, index, sequence.length - i);
1339     }
1340
1341     sequence = tmp;
1342     sequenceChanged();
1343   }
1344
1345   @Override
1346   public void insertCharAt(int i, char c)
1347   {
1348     insertCharAt(i, 1, c);
1349   }
1350
1351   @Override
1352   public String getVamsasId()
1353   {
1354     return vamsasId;
1355   }
1356
1357   @Override
1358   public void setVamsasId(String id)
1359   {
1360     vamsasId = id;
1361   }
1362
1363   @Override
1364   public void setDBRefs(DBRefEntry[] dbref)
1365   {
1366     if (dbrefs == null && datasetSequence != null
1367             && this != datasetSequence)
1368     {
1369       datasetSequence.setDBRefs(dbref);
1370       return;
1371     }
1372     dbrefs = dbref;
1373     if (dbrefs != null)
1374     {
1375       DBRefUtils.ensurePrimaries(this);
1376     }
1377   }
1378
1379   @Override
1380   public DBRefEntry[] getDBRefs()
1381   {
1382     if (dbrefs == null && datasetSequence != null
1383             && this != datasetSequence)
1384     {
1385       return datasetSequence.getDBRefs();
1386     }
1387     return dbrefs;
1388   }
1389
1390   @Override
1391   public void addDBRef(DBRefEntry entry)
1392   {
1393     if (datasetSequence != null)
1394     {
1395       datasetSequence.addDBRef(entry);
1396       return;
1397     }
1398
1399     if (dbrefs == null)
1400     {
1401       dbrefs = new DBRefEntry[0];
1402     }
1403
1404     for (DBRefEntryI dbr : dbrefs)
1405     {
1406       if (dbr.updateFrom(entry))
1407       {
1408         /*
1409          * found a dbref that either matched, or could be
1410          * updated from, the new entry - no need to add it
1411          */
1412         return;
1413       }
1414     }
1415
1416     /*
1417      * extend the array to make room for one more
1418      */
1419     // TODO use an ArrayList instead
1420     int j = dbrefs.length;
1421     DBRefEntry[] temp = new DBRefEntry[j + 1];
1422     System.arraycopy(dbrefs, 0, temp, 0, j);
1423     temp[temp.length - 1] = entry;
1424
1425     dbrefs = temp;
1426
1427     DBRefUtils.ensurePrimaries(this);
1428   }
1429
1430   @Override
1431   public void setDatasetSequence(SequenceI seq)
1432   {
1433     if (seq == this)
1434     {
1435       throw new IllegalArgumentException(
1436               "Implementation Error: self reference passed to SequenceI.setDatasetSequence");
1437     }
1438     if (seq != null && seq.getDatasetSequence() != null)
1439     {
1440       throw new IllegalArgumentException(
1441               "Implementation error: cascading dataset sequences are not allowed.");
1442     }
1443     datasetSequence = seq;
1444   }
1445
1446   @Override
1447   public SequenceI getDatasetSequence()
1448   {
1449     return datasetSequence;
1450   }
1451
1452   @Override
1453   public AlignmentAnnotation[] getAnnotation()
1454   {
1455     return annotation == null ? null
1456             : annotation
1457                     .toArray(new AlignmentAnnotation[annotation.size()]);
1458   }
1459
1460   @Override
1461   public boolean hasAnnotation(AlignmentAnnotation ann)
1462   {
1463     return annotation == null ? false : annotation.contains(ann);
1464   }
1465
1466   @Override
1467   public void addAlignmentAnnotation(AlignmentAnnotation annotation)
1468   {
1469     if (this.annotation == null)
1470     {
1471       this.annotation = new Vector<>();
1472     }
1473     if (!this.annotation.contains(annotation))
1474     {
1475       this.annotation.addElement(annotation);
1476     }
1477     annotation.setSequenceRef(this);
1478   }
1479
1480   @Override
1481   public void removeAlignmentAnnotation(AlignmentAnnotation annotation)
1482   {
1483     if (this.annotation != null)
1484     {
1485       this.annotation.removeElement(annotation);
1486       if (this.annotation.size() == 0)
1487       {
1488         this.annotation = null;
1489       }
1490     }
1491   }
1492
1493   /**
1494    * test if this is a valid candidate for another sequence's dataset sequence.
1495    * 
1496    */
1497   private boolean isValidDatasetSequence()
1498   {
1499     if (datasetSequence != null)
1500     {
1501       return false;
1502     }
1503     for (int i = 0; i < sequence.length; i++)
1504     {
1505       if (jalview.util.Comparison.isGap(sequence[i]))
1506       {
1507         return false;
1508       }
1509     }
1510     return true;
1511   }
1512
1513   @Override
1514   public SequenceI deriveSequence()
1515   {
1516     Sequence seq = null;
1517     if (datasetSequence == null)
1518     {
1519       if (isValidDatasetSequence())
1520       {
1521         // Use this as dataset sequence
1522         seq = new Sequence(getName(), "", 1, -1);
1523         seq.setDatasetSequence(this);
1524         seq.initSeqFrom(this, getAnnotation());
1525         return seq;
1526       }
1527       else
1528       {
1529         // Create a new, valid dataset sequence
1530         createDatasetSequence();
1531       }
1532     }
1533     return new Sequence(this);
1534   }
1535
1536   private boolean _isNa;
1537
1538   private int _seqhash = 0;
1539
1540   /**
1541    * Answers false if the sequence is more than 85% nucleotide (ACGTU), else
1542    * true
1543    */
1544   @Override
1545   public boolean isProtein()
1546   {
1547     if (datasetSequence != null)
1548     {
1549       return datasetSequence.isProtein();
1550     }
1551     if (_seqhash != sequence.hashCode())
1552     {
1553       _seqhash = sequence.hashCode();
1554       _isNa = Comparison.isNucleotide(this);
1555     }
1556     return !_isNa;
1557   };
1558
1559   /*
1560    * (non-Javadoc)
1561    * 
1562    * @see jalview.datamodel.SequenceI#createDatasetSequence()
1563    */
1564   @Override
1565   public SequenceI createDatasetSequence()
1566   {
1567     if (datasetSequence == null)
1568     {
1569       Sequence dsseq = new Sequence(getName(),
1570               AlignSeq.extractGaps(jalview.util.Comparison.GapChars,
1571                       getSequenceAsString()),
1572               getStart(), getEnd());
1573
1574       datasetSequence = dsseq;
1575
1576       dsseq.setDescription(description);
1577       // move features and database references onto dataset sequence
1578       dsseq.sequenceFeatureStore = sequenceFeatureStore;
1579       sequenceFeatureStore = null;
1580       dsseq.dbrefs = dbrefs;
1581       dbrefs = null;
1582       // TODO: search and replace any references to this sequence with
1583       // references to the dataset sequence in Mappings on dbref
1584       dsseq.pdbIds = pdbIds;
1585       pdbIds = null;
1586       datasetSequence.updatePDBIds();
1587       if (annotation != null)
1588       {
1589         // annotation is cloned rather than moved, to preserve what's currently
1590         // on the alignment
1591         for (AlignmentAnnotation aa : annotation)
1592         {
1593           AlignmentAnnotation _aa = new AlignmentAnnotation(aa);
1594           _aa.sequenceRef = datasetSequence;
1595           _aa.adjustForAlignment(); // uses annotation's own record of
1596                                     // sequence-column mapping
1597           datasetSequence.addAlignmentAnnotation(_aa);
1598         }
1599       }
1600     }
1601     return datasetSequence;
1602   }
1603
1604   /*
1605    * (non-Javadoc)
1606    * 
1607    * @see
1608    * jalview.datamodel.SequenceI#setAlignmentAnnotation(AlignmmentAnnotation[]
1609    * annotations)
1610    */
1611   @Override
1612   public void setAlignmentAnnotation(AlignmentAnnotation[] annotations)
1613   {
1614     if (annotation != null)
1615     {
1616       annotation.removeAllElements();
1617     }
1618     if (annotations != null)
1619     {
1620       for (int i = 0; i < annotations.length; i++)
1621       {
1622         if (annotations[i] != null)
1623         {
1624           addAlignmentAnnotation(annotations[i]);
1625         }
1626       }
1627     }
1628   }
1629
1630   @Override
1631   public AlignmentAnnotation[] getAnnotation(String label)
1632   {
1633     if (annotation == null || annotation.size() == 0)
1634     {
1635       return null;
1636     }
1637
1638     Vector<AlignmentAnnotation> subset = new Vector<>();
1639     Enumeration<AlignmentAnnotation> e = annotation.elements();
1640     while (e.hasMoreElements())
1641     {
1642       AlignmentAnnotation ann = e.nextElement();
1643       if (ann.label != null && ann.label.equals(label))
1644       {
1645         subset.addElement(ann);
1646       }
1647     }
1648     if (subset.size() == 0)
1649     {
1650       return null;
1651     }
1652     AlignmentAnnotation[] anns = new AlignmentAnnotation[subset.size()];
1653     int i = 0;
1654     e = subset.elements();
1655     while (e.hasMoreElements())
1656     {
1657       anns[i++] = e.nextElement();
1658     }
1659     subset.removeAllElements();
1660     return anns;
1661   }
1662
1663   @Override
1664   public boolean updatePDBIds()
1665   {
1666     if (datasetSequence != null)
1667     {
1668       // TODO: could merge DBRefs
1669       return datasetSequence.updatePDBIds();
1670     }
1671     if (dbrefs == null || dbrefs.length == 0)
1672     {
1673       return false;
1674     }
1675     boolean added = false;
1676     for (DBRefEntry dbr : dbrefs)
1677     {
1678       if (DBRefSource.PDB.equals(dbr.getSource()))
1679       {
1680         /*
1681          * 'Add' any PDB dbrefs as a PDBEntry - add is only performed if the
1682          * PDB id is not already present in a 'matching' PDBEntry
1683          * Constructor parses out a chain code if appended to the accession id
1684          * (a fudge used to 'store' the chain code in the DBRef)
1685          */
1686         PDBEntry pdbe = new PDBEntry(dbr);
1687         added |= addPDBId(pdbe);
1688       }
1689     }
1690     return added;
1691   }
1692
1693   @Override
1694   public void transferAnnotation(SequenceI entry, Mapping mp)
1695   {
1696     if (datasetSequence != null)
1697     {
1698       datasetSequence.transferAnnotation(entry, mp);
1699       return;
1700     }
1701     if (entry.getDatasetSequence() != null)
1702     {
1703       transferAnnotation(entry.getDatasetSequence(), mp);
1704       return;
1705     }
1706     // transfer any new features from entry onto sequence
1707     if (entry.getSequenceFeatures() != null)
1708     {
1709
1710       List<SequenceFeature> sfs = entry.getSequenceFeatures();
1711       for (SequenceFeature feature : sfs)
1712       {
1713        SequenceFeature sf[] = (mp != null) ? mp.locateFeature(feature)
1714                 : new SequenceFeature[] { new SequenceFeature(feature) };
1715         if (sf != null)
1716         {
1717           for (int sfi = 0; sfi < sf.length; sfi++)
1718           {
1719             addSequenceFeature(sf[sfi]);
1720           }
1721         }
1722       }
1723     }
1724
1725     // transfer PDB entries
1726     if (entry.getAllPDBEntries() != null)
1727     {
1728       Enumeration<PDBEntry> e = entry.getAllPDBEntries().elements();
1729       while (e.hasMoreElements())
1730       {
1731         PDBEntry pdb = e.nextElement();
1732         addPDBId(pdb);
1733       }
1734     }
1735     // transfer database references
1736     DBRefEntry[] entryRefs = entry.getDBRefs();
1737     if (entryRefs != null)
1738     {
1739       for (int r = 0; r < entryRefs.length; r++)
1740       {
1741         DBRefEntry newref = new DBRefEntry(entryRefs[r]);
1742         if (newref.getMap() != null && mp != null)
1743         {
1744           // remap ref using our local mapping
1745         }
1746         // we also assume all version string setting is done by dbSourceProxy
1747         /*
1748          * if (!newref.getSource().equalsIgnoreCase(dbSource)) {
1749          * newref.setSource(dbSource); }
1750          */
1751         addDBRef(newref);
1752       }
1753     }
1754   }
1755
1756   @Override
1757   public void setRNA(RNA r)
1758   {
1759     rna = r;
1760   }
1761
1762   @Override
1763   public RNA getRNA()
1764   {
1765     return rna;
1766   }
1767
1768   @Override
1769   public List<AlignmentAnnotation> getAlignmentAnnotations(String calcId,
1770           String label)
1771   {
1772     List<AlignmentAnnotation> result = new ArrayList<>();
1773     if (this.annotation != null)
1774     {
1775       for (AlignmentAnnotation ann : annotation)
1776       {
1777         if (ann.calcId != null && ann.calcId.equals(calcId)
1778                 && ann.label != null && ann.label.equals(label))
1779         {
1780           result.add(ann);
1781         }
1782       }
1783     }
1784     return result;
1785   }
1786
1787   @Override
1788   public String toString()
1789   {
1790     return getDisplayId(false);
1791   }
1792
1793   @Override
1794   public PDBEntry getPDBEntry(String pdbIdStr)
1795   {
1796     if (getDatasetSequence() != null)
1797     {
1798       return getDatasetSequence().getPDBEntry(pdbIdStr);
1799     }
1800     if (pdbIds == null)
1801     {
1802       return null;
1803     }
1804     List<PDBEntry> entries = getAllPDBEntries();
1805     for (PDBEntry entry : entries)
1806     {
1807       if (entry.getId().equalsIgnoreCase(pdbIdStr))
1808       {
1809         return entry;
1810       }
1811     }
1812     return null;
1813   }
1814
1815   @Override
1816   public List<DBRefEntry> getPrimaryDBRefs()
1817   {
1818     if (datasetSequence != null)
1819     {
1820       return datasetSequence.getPrimaryDBRefs();
1821     }
1822     if (dbrefs == null || dbrefs.length == 0)
1823     {
1824       return Collections.emptyList();
1825     }
1826     synchronized (dbrefs)
1827     {
1828       List<DBRefEntry> primaries = new ArrayList<>();
1829       DBRefEntry[] tmp = new DBRefEntry[1];
1830       for (DBRefEntry ref : dbrefs)
1831       {
1832         if (!ref.isPrimaryCandidate())
1833         {
1834           continue;
1835         }
1836         if (ref.hasMap())
1837         {
1838           MapList mp = ref.getMap().getMap();
1839           if (mp.getFromLowest() > start || mp.getFromHighest() < end)
1840           {
1841             // map only involves a subsequence, so cannot be primary
1842             continue;
1843           }
1844         }
1845         // whilst it looks like it is a primary ref, we also sanity check type
1846         if (DBRefUtils.getCanonicalName(DBRefSource.PDB)
1847                 .equals(DBRefUtils.getCanonicalName(ref.getSource())))
1848         {
1849           // PDB dbrefs imply there should be a PDBEntry associated
1850           // TODO: tighten PDB dbrefs
1851           // formally imply Jalview has actually downloaded and
1852           // parsed the pdb file. That means there should be a cached file
1853           // handle on the PDBEntry, and a real mapping between sequence and
1854           // extracted sequence from PDB file
1855           PDBEntry pdbentry = getPDBEntry(ref.getAccessionId());
1856           if (pdbentry != null && pdbentry.getFile() != null)
1857           {
1858             primaries.add(ref);
1859           }
1860           continue;
1861         }
1862         // check standard protein or dna sources
1863         tmp[0] = ref;
1864         DBRefEntry[] res = DBRefUtils.selectDbRefs(!isProtein(), tmp);
1865         if (res != null && res[0] == tmp[0])
1866         {
1867           primaries.add(ref);
1868           continue;
1869         }
1870       }
1871       return primaries;
1872     }
1873   }
1874
1875   /**
1876    * {@inheritDoc}
1877    */
1878   @Override
1879   public List<SequenceFeature> findFeatures(int fromColumn, int toColumn,
1880           String... types)
1881   {
1882     int startPos = findPosition(fromColumn - 1); // convert base 1 to base 0
1883     int endPos = fromColumn == toColumn ? startPos
1884             : findPosition(toColumn - 1);
1885
1886     List<SequenceFeature> result = getFeatures().findFeatures(startPos,
1887             endPos, types);
1888
1889     /*
1890      * if end column is gapped, endPos may be to the right, 
1891      * and we may have included adjacent or enclosing features;
1892      * remove any that are not enclosing, non-contact features
1893      */
1894     boolean endColumnIsGapped = toColumn > 0 && toColumn <= sequence.length
1895             && Comparison.isGap(sequence[toColumn - 1]);
1896     if (endPos > this.end || endColumnIsGapped)
1897     {
1898       ListIterator<SequenceFeature> it = result.listIterator();
1899       while (it.hasNext())
1900       {
1901         SequenceFeature sf = it.next();
1902         int sfBegin = sf.getBegin();
1903         int sfEnd = sf.getEnd();
1904         int featureStartColumn = findIndex(sfBegin);
1905         if (featureStartColumn > toColumn)
1906         {
1907           it.remove();
1908         }
1909         else if (featureStartColumn < fromColumn)
1910         {
1911           int featureEndColumn = sfEnd == sfBegin ? featureStartColumn
1912                   : findIndex(sfEnd);
1913           if (featureEndColumn < fromColumn)
1914           {
1915             it.remove();
1916           }
1917           else if (featureEndColumn > toColumn && sf.isContactFeature())
1918           {
1919             /*
1920              * remove an enclosing feature if it is a contact feature
1921              */
1922             it.remove();
1923           }
1924         }
1925       }
1926     }
1927
1928     return result;
1929   }
1930
1931   /**
1932    * Invalidates any stale cursors (forcing recalculation) by incrementing the
1933    * token that has to match the one presented by the cursor
1934    */
1935   @Override
1936   public void sequenceChanged()
1937   {
1938     changeCount++;
1939   }
1940
1941   /**
1942    * {@inheritDoc}
1943    */
1944   @Override
1945   public int replace(char c1, char c2)
1946   {
1947     if (c1 == c2)
1948     {
1949       return 0;
1950     }
1951     int count = 0;
1952     synchronized (sequence)
1953     {
1954       for (int c = 0; c < sequence.length; c++)
1955       {
1956         if (sequence[c] == c1)
1957         {
1958           sequence[c] = c2;
1959           count++;
1960         }
1961       }
1962     }
1963     if (count > 0)
1964     {
1965       sequenceChanged();
1966     }
1967
1968     return count;
1969   }
1970
1971   @Override
1972   public String getSequenceStringFromIterator(Iterator<int[]> it)
1973   {
1974     StringBuilder newSequence = new StringBuilder();
1975     while (it.hasNext())
1976     {
1977       int[] block = it.next();
1978       if (it.hasNext())
1979       {
1980         newSequence.append(getSequence(block[0], block[1] + 1));
1981       }
1982       else
1983       {
1984         newSequence.append(getSequence(block[0], block[1]));
1985       }
1986     }
1987
1988     return newSequence.toString();
1989   }
1990
1991   @Override
1992   public int firstResidueOutsideIterator(Iterator<int[]> regions)
1993   {
1994     int start = 0;
1995
1996     if (!regions.hasNext())
1997     {
1998       return findIndex(getStart()) - 1;
1999     }
2000
2001     // Simply walk along the sequence whilst watching for region
2002     // boundaries
2003     int hideStart = getLength();
2004     int hideEnd = -1;
2005     boolean foundStart = false;
2006
2007     // step through the non-gapped positions of the sequence
2008     for (int i = getStart(); i <= getEnd() && (!foundStart); i++)
2009     {
2010       // get alignment position of this residue in the sequence
2011       int p = findIndex(i) - 1;
2012
2013       // update region start/end
2014       while (hideEnd < p && regions.hasNext())
2015       {
2016         int[] region = regions.next();
2017         hideStart = region[0];
2018         hideEnd = region[1];
2019       }
2020       if (hideEnd < p)
2021       {
2022         hideStart = getLength();
2023       }
2024       // update boundary for sequence
2025       if (p < hideStart)
2026       {
2027         start = p;
2028         foundStart = true;
2029       }
2030     }
2031
2032     if (foundStart)
2033     {
2034       return start;
2035     }
2036     // otherwise, sequence was completely hidden
2037     return 0;
2038   }
2039 }