JAL-2788 possible adjustments to sequence accesses
[jalview.git] / src / jalview / datamodel / HiddenColumns.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.util.Comparison;
24 import jalview.util.ShiftList;
25
26 import java.util.ArrayList;
27 import java.util.BitSet;
28 import java.util.Collections;
29 import java.util.List;
30 import java.util.Vector;
31 import java.util.concurrent.locks.ReentrantReadWriteLock;
32
33 public class HiddenColumns
34 {
35   private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
36
37   /*
38    * list of hidden column [start, end] ranges; the list is maintained in
39    * ascending start column order
40    */
41   private ArrayList<int[]> hiddenColumns;
42
43   /**
44    * Constructor
45    */
46   public HiddenColumns()
47   {
48   }
49
50   /**
51    * Copy constructor
52    * 
53    * @param copy
54    */
55   public HiddenColumns(HiddenColumns copy)
56   {
57     try
58     {
59       LOCK.writeLock().lock();
60       if (copy != null)
61       {
62         if (copy.hiddenColumns != null)
63         {
64           hiddenColumns = copy.copyHiddenRegionsToArrayList();
65         }
66       }
67     } finally
68     {
69       LOCK.writeLock().unlock();
70     }
71   }
72
73   /**
74    * This method is used to return all the HiddenColumn regions and is intended
75    * to remain private. External callers which need a copy of the regions can
76    * call getHiddenColumnsCopyAsList.
77    * 
78    * @return empty list or List of hidden column intervals
79    */
80   private List<int[]> getHiddenRegions()
81   {
82     return hiddenColumns == null ? Collections.<int[]> emptyList()
83             : hiddenColumns;
84   }
85
86   /**
87    * Output regions data as a string. String is in the format:
88    * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
89    * 
90    * @param delimiter
91    *          string to delimit regions
92    * @param betweenstring
93    *          to put between start and end region values
94    * @return regions formatted according to delimiter and between strings
95    */
96   public String regionsToString(String delimiter, String between)
97   {
98     try
99     {
100       LOCK.readLock().lock();
101       StringBuilder regionBuilder = new StringBuilder();
102       if (hiddenColumns != null)
103       {
104         for (int[] range : hiddenColumns)
105         {
106           regionBuilder.append(delimiter).append(range[0]).append(between)
107                   .append(range[1]);
108         }
109
110         regionBuilder.deleteCharAt(0);
111       }
112       return regionBuilder.toString();
113     } finally
114     {
115       LOCK.readLock().unlock();
116     }
117   }
118
119   /**
120    * Find the number of hidden columns
121    * 
122    * @return number of hidden columns
123    */
124   public int getSize()
125   {
126     try
127     {
128       LOCK.readLock().lock();
129       int size = 0;
130       if (hasHiddenColumns())
131       {
132         for (int[] range : hiddenColumns)
133         {
134           size += range[1] - range[0] + 1;
135         }
136       }
137       return size;
138     } finally
139     {
140       LOCK.readLock().unlock();
141     }
142   }
143
144   @Override
145   public boolean equals(Object obj)
146   {
147     try
148     {
149       LOCK.readLock().lock();
150
151       if (!(obj instanceof HiddenColumns))
152       {
153         return false;
154       }
155       HiddenColumns that = (HiddenColumns) obj;
156
157       /*
158        * check hidden columns are either both null, or match
159        */
160       if (this.hiddenColumns == null)
161       {
162         return (that.hiddenColumns == null);
163       }
164       if (that.hiddenColumns == null
165               || that.hiddenColumns.size() != this.hiddenColumns.size())
166       {
167         return false;
168       }
169       int i = 0;
170       for (int[] thisRange : hiddenColumns)
171       {
172         int[] thatRange = that.hiddenColumns.get(i++);
173         if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
174         {
175           return false;
176         }
177       }
178       return true;
179     } finally
180     {
181       LOCK.readLock().unlock();
182     }
183   }
184
185   /**
186    * Return absolute column index for a visible column index
187    * 
188    * @param column
189    *          int column index in alignment view (count from zero)
190    * @return alignment column index for column
191    */
192   public int adjustForHiddenColumns(int column)
193   {
194     try
195     {
196       LOCK.readLock().lock();
197       int result = column;
198       if (hiddenColumns != null)
199       {
200         for (int i = 0; i < hiddenColumns.size(); i++)
201         {
202           int[] region = hiddenColumns.get(i);
203           if (result >= region[0])
204           {
205             result += region[1] - region[0] + 1;
206           }
207         }
208       }
209       return result;
210     } finally
211     {
212       LOCK.readLock().unlock();
213     }
214   }
215
216   /**
217    * Use this method to find out where a column will appear in the visible
218    * alignment when hidden columns exist. If the column is not visible, then the
219    * left-most visible column will always be returned.
220    * 
221    * @param hiddenColumn
222    *          the column index in the full alignment including hidden columns
223    * @return the position of the column in the visible alignment
224    */
225   public int findColumnPosition(int hiddenColumn)
226   {
227     try
228     {
229       LOCK.readLock().lock();
230       int result = hiddenColumn;
231       if (hiddenColumns != null)
232       {
233         int index = 0;
234         int[] region;
235         do
236         {
237           region = hiddenColumns.get(index++);
238           if (hiddenColumn > region[1])
239           {
240             result -= region[1] + 1 - region[0];
241           }
242         } while ((hiddenColumn > region[1])
243                 && (index < hiddenColumns.size()));
244
245         if (hiddenColumn >= region[0] && hiddenColumn <= region[1])
246         {
247           // Here the hidden column is within a region, so
248           // we want to return the position of region[0]-1, adjusted for any
249           // earlier hidden columns.
250           // Calculate the difference between the actual hidden col position
251           // and region[0]-1, and then subtract from result to convert result
252           // from
253           // the adjusted hiddenColumn value to the adjusted region[0]-1 value
254
255           // However, if the region begins at 0 we cannot return region[0]-1
256           // just return 0
257           if (region[0] == 0)
258           {
259             return 0;
260           }
261           else
262           {
263             return result - (hiddenColumn - region[0] + 1);
264           }
265         }
266       }
267       return result; // return the shifted position after removing hidden
268                      // columns.
269     } finally
270     {
271       LOCK.readLock().unlock();
272     }
273   }
274
275   /**
276    * Find the visible column which is a given visible number of columns to the
277    * left of another visible column. i.e. for a startColumn x, the column which
278    * is distance 1 away will be column x-1.
279    * 
280    * @param visibleDistance
281    *          the number of visible columns to offset by
282    * @param startColumn
283    *          the column to start from
284    * @return the position of the column in the visible alignment
285    */
286   public int subtractVisibleColumns(int visibleDistance, int startColumn)
287   {
288     try
289     {
290
291       LOCK.readLock().lock();
292       int distance = visibleDistance;
293
294       // in case startColumn is in a hidden region, move it to the left
295       int start = adjustForHiddenColumns(findColumnPosition(startColumn));
296
297       // get index of hidden region to left of start
298       int index = getHiddenIndexLeft(start);
299       if (index == -1)
300       {
301         // no hidden regions to left of startColumn
302         return start - distance;
303       }
304
305       // walk backwards through the alignment subtracting the counts of visible
306       // columns from distance
307       int[] region;
308       int gap = 0;
309       int nextstart = start;
310
311       while ((index > -1) && (distance - gap > 0))
312       {
313         // subtract the gap to right of region from distance
314         distance -= gap;
315         start = nextstart;
316
317         // calculate the next gap
318         region = hiddenColumns.get(index);
319         gap = start - region[1];
320
321         // set start to just to left of current region
322         nextstart = region[0] - 1;
323         index--;
324       }
325
326       if (distance - gap > 0)
327       {
328         // fell out of loop because there are no more hidden regions
329         distance -= gap;
330         return nextstart - distance;
331       }
332       return start - distance;
333     } finally
334     {
335       LOCK.readLock().unlock();
336     }
337
338   }
339
340   /**
341    * Use this method to determine the set of hiddenRegion start positions
342    * 
343    * @return list of column number in visible view where hidden regions start
344    */
345   public List<Integer> findHiddenRegionPositions()
346   {
347     try
348     {
349       LOCK.readLock().lock();
350       List<Integer> positions = null;
351
352       if (hiddenColumns != null)
353       {
354         positions = new ArrayList<>(hiddenColumns.size());
355
356         positions.add(hiddenColumns.get(0)[0]);
357         for (int i = 1; i < hiddenColumns.size(); ++i)
358         {
359
360           int result = 0;
361           if (hiddenColumns != null)
362           {
363             int index = 0;
364             int gaps = 0;
365             do
366             {
367               int[] region = hiddenColumns.get(index);
368               gaps += region[1] + 1 - region[0];
369               result = region[1] + 1;
370               index++;
371             } while (index <= i);
372
373             result -= gaps;
374           }
375           positions.add(result);
376         }
377       }
378       else
379       {
380         positions = new ArrayList<>();
381       }
382
383       return positions;
384     } finally
385     {
386       LOCK.readLock().unlock();
387     }
388   }
389
390   /**
391    * This method returns the rightmost limit of a region of an alignment with
392    * hidden columns. In otherwords, the next hidden column.
393    * 
394    * @param index
395    *          int
396    */
397   public int getHiddenBoundaryRight(int alPos)
398   {
399     try
400     {
401       LOCK.readLock().lock();
402       if (hiddenColumns != null)
403       {
404         int index = 0;
405         do
406         {
407           int[] region = hiddenColumns.get(index);
408           if (alPos < region[0])
409           {
410             return region[0];
411           }
412
413           index++;
414         } while (index < hiddenColumns.size());
415       }
416
417       return alPos;
418     } finally
419     {
420       LOCK.readLock().unlock();
421     }
422
423   }
424
425   /**
426    * This method returns the leftmost limit of a region of an alignment with
427    * hidden columns. In otherwords, the previous hidden column.
428    * 
429    * @param index
430    *          int
431    */
432   public int getHiddenBoundaryLeft(int alPos)
433   {
434     try
435     {
436       LOCK.readLock().lock();
437
438       if (hiddenColumns != null)
439       {
440         int index = hiddenColumns.size() - 1;
441         do
442         {
443           int[] region = hiddenColumns.get(index);
444           if (alPos > region[1])
445           {
446             return region[1];
447           }
448
449           index--;
450         } while (index > -1);
451       }
452
453       return alPos;
454     } finally
455     {
456       LOCK.readLock().unlock();
457     }
458   }
459
460   /**
461    * This method returns the index of the hidden region to the left of a column
462    * position. If the column is in a hidden region it returns the index of the
463    * region to the left. If there is no hidden region to the left it returns -1.
464    * 
465    * @param pos
466    *          int
467    */
468   private int getHiddenIndexLeft(int pos)
469   {
470     try
471     {
472
473       LOCK.readLock().lock();
474       if (hiddenColumns != null)
475       {
476         int index = hiddenColumns.size() - 1;
477         do
478         {
479           int[] region = hiddenColumns.get(index);
480           if (pos > region[1])
481           {
482             return index;
483           }
484
485           index--;
486         } while (index > -1);
487       }
488
489       return -1;
490     } finally
491     {
492       LOCK.readLock().unlock();
493     }
494
495   }
496
497   /**
498    * Adds the specified column range to the hidden columns
499    * 
500    * @param start
501    * @param end
502    */
503   public void hideColumns(int start, int end)
504   {
505     boolean wasAlreadyLocked = false;
506     try
507     {
508       // check if the write lock was already locked by this thread,
509       // as this method can be called internally in loops within HiddenColumns
510       if (!LOCK.isWriteLockedByCurrentThread())
511       {
512         LOCK.writeLock().lock();
513       }
514       else
515       {
516         wasAlreadyLocked = true;
517       }
518
519       if (hiddenColumns == null)
520       {
521         hiddenColumns = new ArrayList<>();
522       }
523
524       /*
525        * traverse existing hidden ranges and insert / amend / append as
526        * appropriate
527        */
528       for (int i = 0; i < hiddenColumns.size(); i++)
529       {
530         int[] region = hiddenColumns.get(i);
531
532         if (end < region[0] - 1)
533         {
534           /*
535            * insert discontiguous preceding range
536            */
537           hiddenColumns.add(i, new int[] { start, end });
538           return;
539         }
540
541         if (end <= region[1])
542         {
543           /*
544            * new range overlaps existing, or is contiguous preceding it - adjust
545            * start column
546            */
547           region[0] = Math.min(region[0], start);
548           return;
549         }
550
551         if (start <= region[1] + 1)
552         {
553           /*
554            * new range overlaps existing, or is contiguous following it - adjust
555            * start and end columns
556            */
557           region[0] = Math.min(region[0], start);
558           region[1] = Math.max(region[1], end);
559
560           /*
561            * also update or remove any subsequent ranges 
562            * that are overlapped
563            */
564           while (i < hiddenColumns.size() - 1)
565           {
566             int[] nextRegion = hiddenColumns.get(i + 1);
567             if (nextRegion[0] > end + 1)
568             {
569               /*
570                * gap to next hidden range - no more to update
571                */
572               break;
573             }
574             region[1] = Math.max(nextRegion[1], end);
575             hiddenColumns.remove(i + 1);
576           }
577           return;
578         }
579       }
580
581       /*
582        * remaining case is that the new range follows everything else
583        */
584       hiddenColumns.add(new int[] { start, end });
585     } finally
586     {
587       if (!wasAlreadyLocked)
588       {
589         LOCK.writeLock().unlock();
590       }
591     }
592   }
593
594   public boolean isVisible(int column)
595   {
596     try
597     {
598       LOCK.readLock().lock();
599
600       if (hiddenColumns != null)
601       {
602         for (int[] region : hiddenColumns)
603         {
604           if (column >= region[0] && column <= region[1])
605           {
606             return false;
607           }
608         }
609       }
610
611       return true;
612     } finally
613     {
614       LOCK.readLock().unlock();
615     }
616   }
617
618   private ArrayList<int[]> copyHiddenRegionsToArrayList()
619   {
620     int size = 0;
621     if (hiddenColumns != null)
622     {
623       size = hiddenColumns.size();
624     }
625     ArrayList<int[]> copy = new ArrayList<>(size);
626
627     for (int i = 0, j = size; i < j; i++)
628     {
629       int[] rh;
630       int[] cp;
631       rh = hiddenColumns.get(i);
632       if (rh != null)
633       {
634         cp = new int[rh.length];
635         System.arraycopy(rh, 0, cp, 0, rh.length);
636         copy.add(cp);
637       }
638     }
639
640     return copy;
641   }
642
643   /**
644    * Returns a copy of the vector of hidden regions, as an ArrayList. Before
645    * using this method please consider if you really need access to the hidden
646    * regions - a new (or existing!) method on HiddenColumns might be more
647    * appropriate.
648    * 
649    * @return hidden regions as an ArrayList of [start,end] pairs
650    */
651   public ArrayList<int[]> getHiddenColumnsCopy()
652   {
653     try
654     {
655       LOCK.readLock().lock();
656       return copyHiddenRegionsToArrayList();
657     } finally
658     {
659       LOCK.readLock().unlock();
660     }
661   }
662
663   /**
664    * propagate shift in alignment columns to column selection
665    * 
666    * @param start
667    *          beginning of edit
668    * @param left
669    *          shift in edit (+ve for removal, or -ve for inserts)
670    */
671   public List<int[]> compensateForEdit(int start, int change,
672           ColumnSelection sel)
673   {
674     try
675     {
676       LOCK.writeLock().lock();
677       List<int[]> deletedHiddenColumns = null;
678
679       if (hiddenColumns != null)
680       {
681         deletedHiddenColumns = new ArrayList<>();
682         int hSize = hiddenColumns.size();
683         for (int i = 0; i < hSize; i++)
684         {
685           int[] region = hiddenColumns.get(i);
686           if (region[0] > start && start + change > region[1])
687           {
688             deletedHiddenColumns.add(region);
689
690             hiddenColumns.remove(i);
691             i--;
692             hSize--;
693             continue;
694           }
695
696           if (region[0] > start)
697           {
698             region[0] -= change;
699             region[1] -= change;
700           }
701
702           if (region[0] < 0)
703           {
704             region[0] = 0;
705           }
706
707         }
708
709         this.revealHiddenColumns(0, sel);
710       }
711
712       return deletedHiddenColumns;
713     } finally
714     {
715       LOCK.writeLock().unlock();
716     }
717   }
718
719   /**
720    * propagate shift in alignment columns to column selection special version of
721    * compensateForEdit - allowing for edits within hidden regions
722    * 
723    * @param start
724    *          beginning of edit
725    * @param left
726    *          shift in edit (+ve for removal, or -ve for inserts)
727    */
728   public void compensateForDelEdits(int start, int change)
729   {
730     try
731     {
732       LOCK.writeLock().lock();
733       if (hiddenColumns != null)
734       {
735         for (int i = 0; i < hiddenColumns.size(); i++)
736         {
737           int[] region = hiddenColumns.get(i);
738           if (region[0] >= start)
739           {
740             region[0] -= change;
741           }
742           if (region[1] >= start)
743           {
744             region[1] -= change;
745           }
746           if (region[1] < region[0])
747           {
748             hiddenColumns.remove(i--);
749           }
750
751           if (region[0] < 0)
752           {
753             region[0] = 0;
754           }
755           if (region[1] < 0)
756           {
757             region[1] = 0;
758           }
759         }
760       }
761     } finally
762     {
763       LOCK.writeLock().unlock();
764     }
765   }
766
767   /**
768    * return all visible segments between the given start and end boundaries
769    * 
770    * @param start
771    *          (first column inclusive from 0)
772    * @param end
773    *          (last column - not inclusive)
774    * @return int[] {i_start, i_end, ..} where intervals lie in
775    *         start<=i_start<=i_end<end
776    */
777   public int[] getVisibleContigs(int start, int end)
778   {
779     try
780     {
781       LOCK.readLock().lock();
782       if (hiddenColumns != null && hiddenColumns.size() > 0)
783       {
784         List<int[]> visiblecontigs = new ArrayList<>();
785         List<int[]> regions = getHiddenRegions();
786
787         int vstart = start;
788         int[] region;
789         int hideStart;
790         int hideEnd;
791
792         for (int j = 0; vstart < end && j < regions.size(); j++)
793         {
794           region = regions.get(j);
795           hideStart = region[0];
796           hideEnd = region[1];
797
798           if (hideEnd < vstart)
799           {
800             continue;
801           }
802           if (hideStart > vstart)
803           {
804             visiblecontigs.add(new int[] { vstart, hideStart - 1 });
805           }
806           vstart = hideEnd + 1;
807         }
808
809         if (vstart < end)
810         {
811           visiblecontigs.add(new int[] { vstart, end - 1 });
812         }
813         int[] vcontigs = new int[visiblecontigs.size() * 2];
814         for (int i = 0, j = visiblecontigs.size(); i < j; i++)
815         {
816           int[] vc = visiblecontigs.get(i);
817           visiblecontigs.set(i, null);
818           vcontigs[i * 2] = vc[0];
819           vcontigs[i * 2 + 1] = vc[1];
820         }
821         visiblecontigs.clear();
822         return vcontigs;
823       }
824       else
825       {
826         return new int[] { start, end - 1 };
827       }
828     } finally
829     {
830       LOCK.readLock().unlock();
831     }
832   }
833
834   public String[] getVisibleSequenceStrings(int start, int end,
835           SequenceI[] seqs)
836   {
837     try
838     {
839       LOCK.readLock().lock();
840       int iSize = seqs.length;
841       String[] selections = new String[iSize];
842       if (hiddenColumns != null && hiddenColumns.size() > 0)
843       {
844         for (int i = 0; i < iSize; i++)
845         {
846           StringBuffer visibleSeq = new StringBuffer();
847           List<int[]> regions = getHiddenRegions();
848
849           int blockStart = start;
850           int blockEnd = end;
851           int[] region;
852           int hideStart;
853           int hideEnd;
854
855           for (int j = 0; j < regions.size(); j++)
856           {
857             region = regions.get(j);
858             hideStart = region[0];
859             hideEnd = region[1];
860
861             if (hideStart < start)
862             {
863               continue;
864             }
865
866             blockStart = Math.min(blockStart, hideEnd + 1);
867             blockEnd = Math.min(blockEnd, hideStart);
868
869             if (blockStart > blockEnd)
870             {
871               break;
872             }
873
874             visibleSeq.append(seqs[i].getSequence(blockStart, blockEnd));
875
876             blockStart = hideEnd + 1;
877             blockEnd = end;
878           }
879
880           if (end > blockStart)
881           {
882             visibleSeq.append(seqs[i].getSequence(blockStart, end));
883           }
884
885           selections[i] = visibleSeq.toString();
886         }
887       }
888       else
889       {
890         for (int i = 0; i < iSize; i++)
891         {
892           selections[i] = seqs[i].getSequenceAsString(start, end);
893         }
894       }
895
896       return selections;
897     } finally
898     {
899       LOCK.readLock().unlock();
900     }
901   }
902
903   /**
904    * Locate the first and last position visible for this sequence. if seq isn't
905    * visible then return the position of the left and right of the hidden
906    * boundary region, and the corresponding alignment column indices for the
907    * extent of the sequence
908    * 
909    * @param seq
910    * @return int[] { visible start, visible end, first seqpos, last seqpos,
911    *         alignment index for seq start, alignment index for seq end }
912    */
913   public int[] locateVisibleBoundsOfSequence(SequenceI seq)
914   {
915     try
916     {
917       LOCK.readLock().lock();
918       int fpos = seq.getStart();
919       int lpos = seq.getEnd();
920       int start = 0;
921
922       if (hiddenColumns == null || hiddenColumns.size() == 0)
923       {
924         int ifpos = seq.findIndex(fpos) - 1;
925         int ilpos = seq.findIndex(lpos) - 1;
926         return new int[] { ifpos, ilpos, fpos, lpos, ifpos, ilpos };
927       }
928
929       // Simply walk along the sequence whilst watching for hidden column
930       // boundaries
931       List<int[]> regions = getHiddenRegions();
932       int spos = fpos;
933       int lastvispos = -1;
934       int rcount = 0;
935       int hideStart = seq.getLength();
936       int hideEnd = -1;
937       int visPrev = 0;
938       int visNext = 0;
939       int firstP = -1;
940       int lastP = -1;
941       boolean foundStart = false;
942       for (int p = 0, pLen = seq.getLength(); spos <= seq.getEnd()
943               && p < pLen; p++)
944       {
945         if (!Comparison.isGap(seq.getCharAt(p)))
946         {
947           // keep track of first/last column
948           // containing sequence data regardless of visibility
949           if (firstP == -1)
950           {
951             firstP = p;
952           }
953           lastP = p;
954           // update hidden region start/end
955           while (hideEnd < p && rcount < regions.size())
956           {
957             int[] region = regions.get(rcount++);
958             visPrev = visNext;
959             visNext += region[0] - visPrev;
960             hideStart = region[0];
961             hideEnd = region[1];
962           }
963           if (hideEnd < p)
964           {
965             hideStart = seq.getLength();
966           }
967           // update visible boundary for sequence
968           if (p < hideStart)
969           {
970             if (!foundStart)
971             {
972               fpos = spos;
973               start = p;
974               foundStart = true;
975             }
976             lastvispos = p;
977             lpos = spos;
978           }
979           // look for next sequence position
980           spos++;
981         }
982       }
983       if (foundStart)
984       {
985         return new int[] { findColumnPosition(start),
986             findColumnPosition(lastvispos), fpos, lpos, firstP, lastP };
987       }
988       // otherwise, sequence was completely hidden
989       return new int[] { visPrev, visNext, 0, 0, firstP, lastP };
990     } finally
991     {
992       LOCK.readLock().unlock();
993     }
994   }
995
996   /**
997    * delete any columns in alignmentAnnotation that are hidden (including
998    * sequence associated annotation).
999    * 
1000    * @param alignmentAnnotation
1001    */
1002   public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
1003   {
1004     makeVisibleAnnotation(-1, -1, alignmentAnnotation);
1005   }
1006
1007   /**
1008    * delete any columns in alignmentAnnotation that are hidden (including
1009    * sequence associated annotation).
1010    * 
1011    * @param start
1012    *          remove any annotation to the right of this column
1013    * @param end
1014    *          remove any annotation to the left of this column
1015    * @param alignmentAnnotation
1016    *          the annotation to operate on
1017    */
1018   public void makeVisibleAnnotation(int start, int end,
1019           AlignmentAnnotation alignmentAnnotation)
1020   {
1021     try
1022     {
1023       LOCK.readLock().lock();
1024       if (alignmentAnnotation.annotations == null)
1025       {
1026         return;
1027       }
1028       if (start == end && end == -1)
1029       {
1030         start = 0;
1031         end = alignmentAnnotation.annotations.length;
1032       }
1033       if (hiddenColumns != null && hiddenColumns.size() > 0)
1034       {
1035         // then mangle the alignmentAnnotation annotation array
1036         Vector<Annotation[]> annels = new Vector<>();
1037         Annotation[] els = null;
1038         List<int[]> regions = getHiddenRegions();
1039         int blockStart = start;
1040         int blockEnd = end;
1041         int[] region;
1042         int hideStart;
1043         int hideEnd;
1044         int w = 0;
1045
1046         for (int j = 0; j < regions.size(); j++)
1047         {
1048           region = regions.get(j);
1049           hideStart = region[0];
1050           hideEnd = region[1];
1051
1052           if (hideStart < start)
1053           {
1054             continue;
1055           }
1056
1057           blockStart = Math.min(blockStart, hideEnd + 1);
1058           blockEnd = Math.min(blockEnd, hideStart);
1059
1060           if (blockStart > blockEnd)
1061           {
1062             break;
1063           }
1064
1065           annels.addElement(els = new Annotation[blockEnd - blockStart]);
1066           System.arraycopy(alignmentAnnotation.annotations, blockStart, els,
1067                   0, els.length);
1068           w += els.length;
1069           blockStart = hideEnd + 1;
1070           blockEnd = end;
1071         }
1072
1073         if (end > blockStart)
1074         {
1075           annels.addElement(els = new Annotation[end - blockStart + 1]);
1076           if ((els.length
1077                   + blockStart) <= alignmentAnnotation.annotations.length)
1078           {
1079             // copy just the visible segment of the annotation row
1080             System.arraycopy(alignmentAnnotation.annotations, blockStart,
1081                     els, 0, els.length);
1082           }
1083           else
1084           {
1085             // copy to the end of the annotation row
1086             System.arraycopy(alignmentAnnotation.annotations, blockStart,
1087                     els, 0,
1088                     (alignmentAnnotation.annotations.length - blockStart));
1089           }
1090           w += els.length;
1091         }
1092         if (w == 0)
1093         {
1094           return;
1095         }
1096
1097         alignmentAnnotation.annotations = new Annotation[w];
1098         w = 0;
1099
1100         for (Annotation[] chnk : annels)
1101         {
1102           System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
1103                   chnk.length);
1104           w += chnk.length;
1105         }
1106       }
1107       else
1108       {
1109         alignmentAnnotation.restrict(start, end);
1110       }
1111     } finally
1112     {
1113       LOCK.readLock().unlock();
1114     }
1115   }
1116
1117   /**
1118    * 
1119    * @return true if there are columns hidden
1120    */
1121   public boolean hasHiddenColumns()
1122   {
1123     try
1124     {
1125       LOCK.readLock().lock();
1126       return hiddenColumns != null && hiddenColumns.size() > 0;
1127     } finally
1128     {
1129       LOCK.readLock().unlock();
1130     }
1131   }
1132
1133   /**
1134    * 
1135    * @return true if there are more than one set of columns hidden
1136    */
1137   public boolean hasManyHiddenColumns()
1138   {
1139     try
1140     {
1141       LOCK.readLock().lock();
1142       return hiddenColumns != null && hiddenColumns.size() > 1;
1143     } finally
1144     {
1145       LOCK.readLock().unlock();
1146     }
1147   }
1148
1149   /**
1150    * mark the columns corresponding to gap characters as hidden in the column
1151    * selection
1152    * 
1153    * @param sr
1154    */
1155   public void hideInsertionsFor(SequenceI sr)
1156   {
1157     try
1158     {
1159       LOCK.writeLock().lock();
1160       List<int[]> inserts = sr.getInsertions();
1161       for (int[] r : inserts)
1162       {
1163         hideColumns(r[0], r[1]);
1164       }
1165     } finally
1166     {
1167       LOCK.writeLock().unlock();
1168     }
1169   }
1170
1171   /**
1172    * Unhides, and adds to the selection list, all hidden columns
1173    */
1174   public void revealAllHiddenColumns(ColumnSelection sel)
1175   {
1176     try
1177     {
1178       LOCK.writeLock().lock();
1179       if (hiddenColumns != null)
1180       {
1181         for (int i = 0; i < hiddenColumns.size(); i++)
1182         {
1183           int[] region = hiddenColumns.get(i);
1184           for (int j = region[0]; j < region[1] + 1; j++)
1185           {
1186             sel.addElement(j);
1187           }
1188         }
1189       }
1190
1191       hiddenColumns = null;
1192     } finally
1193     {
1194       LOCK.writeLock().unlock();
1195     }
1196   }
1197
1198   /**
1199    * Reveals, and marks as selected, the hidden column range with the given
1200    * start column
1201    * 
1202    * @param start
1203    */
1204   public void revealHiddenColumns(int start, ColumnSelection sel)
1205   {
1206     try
1207     {
1208       LOCK.writeLock().lock();
1209       for (int i = 0; i < hiddenColumns.size(); i++)
1210       {
1211         int[] region = hiddenColumns.get(i);
1212         if (start == region[0])
1213         {
1214           for (int j = region[0]; j < region[1] + 1; j++)
1215           {
1216             sel.addElement(j);
1217           }
1218
1219           hiddenColumns.remove(region);
1220           break;
1221         }
1222       }
1223       if (hiddenColumns.size() == 0)
1224       {
1225         hiddenColumns = null;
1226       }
1227     } finally
1228     {
1229       LOCK.writeLock().unlock();
1230     }
1231   }
1232
1233   /**
1234    * removes intersection of position,length ranges in deletions from the
1235    * start,end regions marked in intervals.
1236    * 
1237    * @param shifts
1238    * @param intervals
1239    * @return
1240    */
1241   private boolean pruneIntervalList(final List<int[]> shifts,
1242           ArrayList<int[]> intervals)
1243   {
1244     boolean pruned = false;
1245     int i = 0;
1246     int j = intervals.size() - 1;
1247     int s = 0;
1248     int t = shifts.size() - 1;
1249     int[] hr = intervals.get(i);
1250     int[] sr = shifts.get(s);
1251     while (i <= j && s <= t)
1252     {
1253       boolean trailinghn = hr[1] >= sr[0];
1254       if (!trailinghn)
1255       {
1256         if (i < j)
1257         {
1258           hr = intervals.get(++i);
1259         }
1260         else
1261         {
1262           i++;
1263         }
1264         continue;
1265       }
1266       int endshift = sr[0] + sr[1]; // deletion ranges - -ve means an insert
1267       if (endshift < hr[0] || endshift < sr[0])
1268       { // leadinghc disjoint or not a deletion
1269         if (s < t)
1270         {
1271           sr = shifts.get(++s);
1272         }
1273         else
1274         {
1275           s++;
1276         }
1277         continue;
1278       }
1279       boolean leadinghn = hr[0] >= sr[0];
1280       boolean leadinghc = hr[0] < endshift;
1281       boolean trailinghc = hr[1] < endshift;
1282       if (leadinghn)
1283       {
1284         if (trailinghc)
1285         { // deleted hidden region.
1286           intervals.remove(i);
1287           pruned = true;
1288           j--;
1289           if (i <= j)
1290           {
1291             hr = intervals.get(i);
1292           }
1293           continue;
1294         }
1295         if (leadinghc)
1296         {
1297           hr[0] = endshift; // clip c terminal region
1298           leadinghn = !leadinghn;
1299           pruned = true;
1300         }
1301       }
1302       if (!leadinghn)
1303       {
1304         if (trailinghc)
1305         {
1306           if (trailinghn)
1307           {
1308             hr[1] = sr[0] - 1;
1309             pruned = true;
1310           }
1311         }
1312         else
1313         {
1314           // sr contained in hr
1315           if (s < t)
1316           {
1317             sr = shifts.get(++s);
1318           }
1319           else
1320           {
1321             s++;
1322           }
1323           continue;
1324         }
1325       }
1326     }
1327     return pruned; // true if any interval was removed or modified by
1328     // operations.
1329   }
1330
1331   /**
1332    * remove any hiddenColumns or selected columns and shift remaining based on a
1333    * series of position, range deletions.
1334    * 
1335    * @param deletions
1336    */
1337   public void pruneDeletions(List<int[]> shifts)
1338   {
1339     try
1340     {
1341       LOCK.writeLock().lock();
1342       // delete any intervals intersecting.
1343       if (hiddenColumns != null)
1344       {
1345         pruneIntervalList(shifts, hiddenColumns);
1346         if (hiddenColumns != null && hiddenColumns.size() == 0)
1347         {
1348           hiddenColumns = null;
1349         }
1350       }
1351     } finally
1352     {
1353       LOCK.writeLock().unlock();
1354     }
1355   }
1356
1357   /**
1358    * Add gaps into the sequences aligned to profileseq under the given
1359    * AlignmentView
1360    * 
1361    * @param profileseq
1362    * @param al
1363    *          - alignment to have gaps inserted into it
1364    * @param input
1365    *          - alignment view where sequence corresponding to profileseq is
1366    *          first entry
1367    * @return new HiddenColumns for new alignment view, with insertions into
1368    *         profileseq marked as hidden.
1369    */
1370   public static HiddenColumns propagateInsertions(SequenceI profileseq,
1371           AlignmentI al, AlignmentView input)
1372   {
1373     int profsqpos = 0;
1374
1375     char gc = al.getGapCharacter();
1376     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1377     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1378     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1379     nview.propagateInsertions(profileseq, al, origseq);
1380     return nview;
1381   }
1382
1383   /**
1384    * 
1385    * @param profileseq
1386    *          - sequence in al which corresponds to origseq
1387    * @param al
1388    *          - alignment which is to have gaps inserted into it
1389    * @param origseq
1390    *          - sequence corresponding to profileseq which defines gap map for
1391    *          modifying al
1392    */
1393   private void propagateInsertions(SequenceI profileseq, AlignmentI al,
1394           SequenceI origseq)
1395   {
1396     char gc = al.getGapCharacter();
1397     // recover mapping between sequence's non-gap positions and positions
1398     // mapping to view.
1399     pruneDeletions(ShiftList.parseMap(origseq.gapMap()));
1400     int[] viscontigs = getVisibleContigs(0, profileseq.getLength());
1401     int spos = 0;
1402     int offset = 0;
1403
1404     // add profile to visible contigs
1405     for (int v = 0; v < viscontigs.length; v += 2)
1406     {
1407       if (viscontigs[v] > spos)
1408       {
1409         StringBuffer sb = new StringBuffer();
1410         for (int s = 0, ns = viscontigs[v] - spos; s < ns; s++)
1411         {
1412           sb.append(gc);
1413         }
1414         for (int s = 0, ns = al.getHeight(); s < ns; s++)
1415         {
1416           SequenceI sqobj = al.getSequenceAt(s);
1417           if (sqobj != profileseq)
1418           {
1419             String sq = al.getSequenceAt(s).getSequenceAsString();
1420             if (sq.length() <= spos + offset)
1421             {
1422               // pad sequence
1423               int diff = spos + offset - sq.length() - 1;
1424               if (diff > 0)
1425               {
1426                 // pad gaps
1427                 sq = sq + sb;
1428                 while ((diff = spos + offset - sq.length() - 1) > 0)
1429                 {
1430                   // sq = sq
1431                   // + ((diff >= sb.length()) ? sb.toString() : sb
1432                   // .substring(0, diff));
1433                   if (diff >= sb.length())
1434                   {
1435                     sq += sb.toString();
1436                   }
1437                   else
1438                   {
1439                     char[] buf = new char[diff];
1440                     sb.getChars(0, diff, buf, 0);
1441                     sq += buf.toString();
1442                   }
1443                 }
1444               }
1445               sq += sb.toString();
1446             }
1447             else
1448             {
1449               al.getSequenceAt(s).setSequence(sq.substring(0, spos + offset)
1450                       + sb.toString() + sq.substring(spos + offset));
1451             }
1452           }
1453         }
1454         // offset+=sb.length();
1455       }
1456       spos = viscontigs[v + 1] + 1;
1457     }
1458     if ((offset + spos) < profileseq.getLength())
1459     {
1460       // pad the final region with gaps.
1461       StringBuffer sb = new StringBuffer();
1462       for (int s = 0, ns = profileseq.getLength() - spos
1463               - offset; s < ns; s++)
1464       {
1465         sb.append(gc);
1466       }
1467       for (int s = 0, ns = al.getHeight(); s < ns; s++)
1468       {
1469         SequenceI sqobj = al.getSequenceAt(s);
1470         if (sqobj == profileseq)
1471         {
1472           continue;
1473         }
1474         String sq = sqobj.getSequenceAsString();
1475         // pad sequence
1476         int diff = origseq.getLength() - sq.length();
1477         while (diff > 0)
1478         {
1479           // sq = sq
1480           // + ((diff >= sb.length()) ? sb.toString() : sb
1481           // .substring(0, diff));
1482           if (diff >= sb.length())
1483           {
1484             sq += sb.toString();
1485           }
1486           else
1487           {
1488             char[] buf = new char[diff];
1489             sb.getChars(0, diff, buf, 0);
1490             sq += buf.toString();
1491           }
1492           diff = origseq.getLength() - sq.length();
1493         }
1494       }
1495     }
1496   }
1497
1498   /**
1499    * remove any hiddenColumns or selected columns and shift remaining based on a
1500    * series of position, range deletions.
1501    * 
1502    * @param deletions
1503    */
1504   private void pruneDeletions(ShiftList deletions)
1505   {
1506     if (deletions != null)
1507     {
1508       final List<int[]> shifts = deletions.getShifts();
1509       if (shifts != null && shifts.size() > 0)
1510       {
1511         pruneDeletions(shifts);
1512
1513         // and shift the rest.
1514         this.compensateForEdits(deletions);
1515       }
1516     }
1517   }
1518
1519   /**
1520    * Adjust hidden column boundaries based on a series of column additions or
1521    * deletions in visible regions.
1522    * 
1523    * @param shiftrecord
1524    * @return
1525    */
1526   private ShiftList compensateForEdits(ShiftList shiftrecord)
1527   {
1528     if (shiftrecord != null)
1529     {
1530       final List<int[]> shifts = shiftrecord.getShifts();
1531       if (shifts != null && shifts.size() > 0)
1532       {
1533         int shifted = 0;
1534         for (int i = 0, j = shifts.size(); i < j; i++)
1535         {
1536           int[] sh = shifts.get(i);
1537           compensateForDelEdits(shifted + sh[0], sh[1]);
1538           shifted -= sh[1];
1539         }
1540       }
1541       return shiftrecord.getInverse();
1542     }
1543     return null;
1544   }
1545
1546   /**
1547    * Returns a hashCode built from hidden column ranges
1548    */
1549   @Override
1550   public int hashCode()
1551   {
1552     try
1553     {
1554       LOCK.readLock().lock();
1555       int hashCode = 1;
1556       if (hiddenColumns != null)
1557       {
1558         for (int[] hidden : hiddenColumns)
1559         {
1560           hashCode = 31 * hashCode + hidden[0];
1561           hashCode = 31 * hashCode + hidden[1];
1562         }
1563       }
1564       return hashCode;
1565     } finally
1566     {
1567       LOCK.readLock().unlock();
1568     }
1569   }
1570
1571   /**
1572    * Hide columns corresponding to the marked bits
1573    * 
1574    * @param inserts
1575    *          - columns map to bits starting from zero
1576    */
1577   public void hideMarkedBits(BitSet inserts)
1578   {
1579     try
1580     {
1581       LOCK.writeLock().lock();
1582       for (int firstSet = inserts
1583               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1584                       .nextSetBit(lastSet))
1585       {
1586         lastSet = inserts.nextClearBit(firstSet);
1587         hideColumns(firstSet, lastSet - 1);
1588       }
1589     } finally
1590     {
1591       LOCK.writeLock().unlock();
1592     }
1593   }
1594
1595   /**
1596    * 
1597    * @param inserts
1598    *          BitSet where hidden columns will be marked
1599    */
1600   public void markHiddenRegions(BitSet inserts)
1601   {
1602     try
1603     {
1604       LOCK.readLock().lock();
1605       if (hiddenColumns == null)
1606       {
1607         return;
1608       }
1609       for (int[] range : hiddenColumns)
1610       {
1611         inserts.set(range[0], range[1] + 1);
1612       }
1613     } finally
1614     {
1615       LOCK.readLock().unlock();
1616     }
1617   }
1618
1619   /**
1620    * Calculate the visible start and end index of an alignment.
1621    * 
1622    * @param width
1623    *          full alignment width
1624    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1625    */
1626   public int[] getVisibleStartAndEndIndex(int width)
1627   {
1628     try
1629     {
1630       LOCK.readLock().lock();
1631       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1632       int startPos = alignmentStartEnd[0];
1633       int endPos = alignmentStartEnd[1];
1634
1635       int[] lowestRange = new int[] { -1, -1 };
1636       int[] higestRange = new int[] { -1, -1 };
1637
1638       if (hiddenColumns == null)
1639       {
1640         return new int[] { startPos, endPos };
1641       }
1642
1643       for (int[] hiddenCol : hiddenColumns)
1644       {
1645         lowestRange = (hiddenCol[0] <= startPos) ? hiddenCol : lowestRange;
1646         higestRange = (hiddenCol[1] >= endPos) ? hiddenCol : higestRange;
1647       }
1648
1649       if (lowestRange[0] == -1 && lowestRange[1] == -1)
1650       {
1651         startPos = alignmentStartEnd[0];
1652       }
1653       else
1654       {
1655         startPos = lowestRange[1] + 1;
1656       }
1657
1658       if (higestRange[0] == -1 && higestRange[1] == -1)
1659       {
1660         endPos = alignmentStartEnd[1];
1661       }
1662       else
1663       {
1664         endPos = higestRange[0] - 1;
1665       }
1666       return new int[] { startPos, endPos };
1667     } finally
1668     {
1669       LOCK.readLock().unlock();
1670     }
1671
1672   }
1673
1674   /**
1675    * Finds the hidden region (if any) which starts or ends at res
1676    * 
1677    * @param res
1678    *          visible residue position, unadjusted for hidden columns
1679    * @return region as [start,end] or null if no matching region is found
1680    */
1681   public int[] getRegionWithEdgeAtRes(int res)
1682   {
1683     try
1684     {
1685       LOCK.readLock().lock();
1686       int adjres = adjustForHiddenColumns(res);
1687
1688       int[] reveal = null;
1689       if (hiddenColumns != null)
1690       {
1691         for (int[] region : hiddenColumns)
1692         {
1693           if (adjres + 1 == region[0] || adjres - 1 == region[1])
1694           {
1695             reveal = region;
1696             break;
1697           }
1698         }
1699       }
1700       return reveal;
1701     } finally
1702     {
1703       LOCK.readLock().unlock();
1704     }
1705   }
1706
1707 }