2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
21 package jalview.datamodel;
23 import java.util.ArrayList;
24 import java.util.BitSet;
25 import java.util.Iterator;
26 import java.util.List;
27 import java.util.NoSuchElementException;
28 import java.util.concurrent.locks.ReentrantReadWriteLock;
30 public class HiddenColumns
32 private static final int HASH_MULTIPLIER = 31;
34 private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
37 * list of hidden column [start, end] ranges; the list is maintained in
38 * ascending start column order
40 private ArrayList<int[]> hiddenColumns;
45 public HiddenColumns()
54 public HiddenColumns(HiddenColumns copy)
58 LOCK.writeLock().lock();
61 if (copy.hiddenColumns != null)
63 hiddenColumns = new ArrayList<>();
64 Iterator<int[]> it = copy.iterator();
67 hiddenColumns.add(it.next());
73 LOCK.writeLock().unlock();
78 * Copy constructor within bounds and with offset. Copies hidden column
79 * regions fully contained between start and end, and offsets positions by
83 * HiddenColumns instance to copy from
85 * lower bound to copy from
87 * upper bound to copy to
89 * offset to subtract from each region boundary position
92 public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
96 LOCK.writeLock().lock();
99 hiddenColumns = new ArrayList<>();
100 Iterator<int[]> it = copy.getBoundedIterator(start, end);
103 int[] region = it.next();
104 // still need to check boundaries because iterator returns
105 // all overlapping regions and we need contained regions
106 if (region[0] >= start && region[1] <= end)
110 { region[0] - offset, region[1] - offset });
116 LOCK.writeLock().unlock();
121 * Output regions data as a string. String is in the format:
122 * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
125 * string to delimit regions
126 * @param betweenstring
127 * to put between start and end region values
128 * @return regions formatted according to delimiter and between strings
130 public String regionsToString(String delimiter, String between)
134 LOCK.readLock().lock();
135 StringBuilder regionBuilder = new StringBuilder();
136 Iterator<int[]> it = new RegionsIterator();
139 int[] range = it.next();
140 regionBuilder.append(delimiter).append(range[0]).append(between)
144 regionBuilder.deleteCharAt(0);
147 return regionBuilder.toString();
150 LOCK.readLock().unlock();
155 * Find the number of hidden columns
157 * @return number of hidden columns
163 LOCK.readLock().lock();
165 Iterator<int[]> it = new RegionsIterator();
168 int[] range = it.next();
169 size += range[1] - range[0] + 1;
175 LOCK.readLock().unlock();
180 * Get the number of distinct hidden regions
182 * @return number of regions
184 public int getNumberOfRegions()
188 LOCK.readLock().lock();
190 if (hasHiddenColumns())
192 num = hiddenColumns.size();
197 LOCK.readLock().unlock();
202 public boolean equals(Object obj)
206 LOCK.readLock().lock();
208 if (!(obj instanceof HiddenColumns))
212 HiddenColumns that = (HiddenColumns) obj;
215 * check hidden columns are either both null, or match
217 if (this.hiddenColumns == null)
219 return (that.hiddenColumns == null);
221 if (that.hiddenColumns == null
222 || that.hiddenColumns.size() != this.hiddenColumns.size())
227 Iterator<int[]> it = new RegionsIterator();
228 Iterator<int[]> thatit = that.iterator();
231 int[] thisRange = it.next();
232 int[] thatRange = thatit.next();
233 if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
241 LOCK.readLock().unlock();
246 * Return absolute column index for a visible column index
249 * int column index in alignment view (count from zero)
250 * @return alignment column index for column
252 public int adjustForHiddenColumns(int column)
256 LOCK.readLock().lock();
259 Iterator<int[]> it = new RegionsIterator();
262 int[] region = it.next();
263 if (result >= region[0])
265 result += region[1] - region[0] + 1;
272 LOCK.readLock().unlock();
277 * Use this method to find out where a column will appear in the visible
278 * alignment when hidden columns exist. If the column is not visible, then the
279 * left-most visible column will always be returned.
281 * @param hiddenColumn
282 * the column index in the full alignment including hidden columns
283 * @return the position of the column in the visible alignment
285 public int findColumnPosition(int hiddenColumn)
289 LOCK.readLock().lock();
290 int result = hiddenColumn;
292 if (hiddenColumns != null)
294 Iterator<int[]> it = new RegionsIterator(0,
299 if (hiddenColumn > region[1])
301 result -= region[1] + 1 - region[0];
305 if (region != null && hiddenColumn >= region[0]
306 && hiddenColumn <= region[1])
308 // Here the hidden column is within a region, so
309 // we want to return the position of region[0]-1, adjusted for any
310 // earlier hidden columns.
311 // Calculate the difference between the actual hidden col position
312 // and region[0]-1, and then subtract from result to convert result
313 // from the adjusted hiddenColumn value to the adjusted region[0]-1
316 // However, if the region begins at 0 we cannot return region[0]-1
324 return result - (hiddenColumn - region[0] + 1);
328 return result; // return the shifted position after removing hidden
332 LOCK.readLock().unlock();
337 * Find the visible column which is a given visible number of columns to the
338 * left of another visible column. i.e. for a startColumn x, the column which
339 * is distance 1 away will be column x-1.
341 * @param visibleDistance
342 * the number of visible columns to offset by
344 * the column to start from
345 * @return the position of the column in the visible alignment
347 public int subtractVisibleColumns(int visibleDistance, int startColumn)
351 LOCK.readLock().lock();
352 int distance = visibleDistance;
354 // in case startColumn is in a hidden region, move it to the left
355 int start = adjustForHiddenColumns(findColumnPosition(startColumn));
357 Iterator<int[]> it = new ReverseRegionsIterator(0, start);
359 while (it.hasNext() && (distance > 0))
361 int[] region = it.next();
363 if (start > region[1])
365 // subtract the gap to right of region from distance
366 if (start - region[1] <= distance)
368 distance -= start - region[1];
369 start = region[0] - 1;
373 start = start - distance;
379 return start - distance;
383 LOCK.readLock().unlock();
388 * This method returns the rightmost limit of a region of an alignment with
389 * hidden columns. In otherwords, the next hidden column.
392 * the (visible) alignmentPosition to find the next hidden column for
394 public int getHiddenBoundaryRight(int alPos)
398 LOCK.readLock().lock();
399 if (hiddenColumns != null)
401 Iterator<int[]> it = new RegionsIterator();
404 int[] region = it.next();
405 if (alPos < region[0])
414 LOCK.readLock().unlock();
419 * This method returns the leftmost limit of a region of an alignment with
420 * hidden columns. In otherwords, the previous hidden column.
423 * the (visible) alignmentPosition to find the previous hidden column
426 public int getHiddenBoundaryLeft(int alPos)
430 LOCK.readLock().lock();
432 Iterator<int[]> it = new ReverseRegionsIterator(0, alPos);
435 int[] region = it.next();
436 if (alPos > region[1])
445 LOCK.readLock().unlock();
450 * Adds the specified column range to the hidden columns collection
453 * start of range to add (absolute position in alignment)
455 * end of range to add (absolute position in alignment)
457 public void hideColumns(int start, int end)
459 boolean wasAlreadyLocked = false;
462 // check if the write lock was already locked by this thread,
463 // as this method can be called internally in loops within HiddenColumns
464 if (!LOCK.isWriteLockedByCurrentThread())
466 LOCK.writeLock().lock();
470 wasAlreadyLocked = true;
473 if (hiddenColumns == null)
475 hiddenColumns = new ArrayList<>();
479 * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
481 if (hiddenColumns.isEmpty()
482 || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
484 hiddenColumns.add(new int[] { start, end });
489 * traverse existing hidden ranges and insert / amend / append as
492 boolean added = false;
493 for (int i = 0; !added && i < hiddenColumns.size(); i++)
495 added = insertRangeAtRegion(i, start, end);
500 if (!wasAlreadyLocked)
502 LOCK.writeLock().unlock();
507 private boolean insertRangeAtRegion(int i, int start, int end)
509 boolean added = false;
511 int[] region = hiddenColumns.get(i);
512 if (end < region[0] - 1)
515 * insert discontiguous preceding range
517 hiddenColumns.add(i, new int[] { start, end });
520 else if (end <= region[1])
523 * new range overlaps existing, or is contiguous preceding it - adjust
526 region[0] = Math.min(region[0], start);
529 else if (start <= region[1] + 1)
532 * new range overlaps existing, or is contiguous following it - adjust
533 * start and end columns
535 region[0] = Math.min(region[0], start);
536 region[1] = Math.max(region[1], end);
539 * also update or remove any subsequent ranges
540 * that are overlapped
542 while (i < hiddenColumns.size() - 1)
544 int[] nextRegion = hiddenColumns.get(i + 1);
545 if (nextRegion[0] > end + 1)
548 * gap to next hidden range - no more to update
552 region[1] = Math.max(nextRegion[1], end);
553 hiddenColumns.remove(i + 1);
561 * Answers if a column in the alignment is visible
564 * absolute position of column in the alignment
565 * @return true if column is visible
567 public boolean isVisible(int column)
571 LOCK.readLock().lock();
573 Iterator<int[]> it = new RegionsIterator();
576 int[] region = it.next();
577 if (column >= region[0] && column <= region[1])
586 LOCK.readLock().unlock();
591 * Get the visible sections of a set of sequences
594 * sequence position to start from
596 * sequence position to end at
598 * an array of sequences
599 * @return an array of strings encoding the visible parts of each sequence
601 public String[] getVisibleSequenceStrings(int start, int end,
606 LOCK.readLock().lock();
607 int iSize = seqs.length;
608 String[] selections = new String[iSize];
609 if (hiddenColumns != null && hiddenColumns.size() > 0)
611 for (int i = 0; i < iSize; i++)
613 StringBuffer visibleSeq = new StringBuffer();
615 Iterator<int[]> blocks = new VisibleContigsIterator(start,
618 while (blocks.hasNext())
620 int[] block = blocks.next();
621 if (blocks.hasNext())
624 .append(seqs[i].getSequence(block[0], block[1] + 1));
629 .append(seqs[i].getSequence(block[0], block[1]));
633 selections[i] = visibleSeq.toString();
638 for (int i = 0; i < iSize; i++)
640 selections[i] = seqs[i].getSequenceAsString(start, end);
647 LOCK.readLock().unlock();
652 * Locate the first position visible for this sequence. If seq isn't visible
653 * then return the position of the left side of the hidden boundary region.
656 * sequence to find position for
657 * @return visible start position
659 public int locateVisibleStartOfSequence(SequenceI seq)
663 LOCK.readLock().lock();
666 if (hiddenColumns == null || hiddenColumns.size() == 0)
668 return seq.findIndex(seq.getStart()) - 1;
671 // Simply walk along the sequence whilst watching for hidden column
673 Iterator<int[]> regions = new RegionsIterator();
674 int hideStart = seq.getLength();
678 boolean foundStart = false;
680 // step through the non-gapped positions of the sequence
681 for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
683 // get alignment position of this residue in the sequence
684 int p = seq.findIndex(i) - 1;
686 // update hidden region start/end
687 while (hideEnd < p && regions.hasNext())
689 int[] region = regions.next();
691 visNext += region[0] - visPrev;
692 hideStart = region[0];
697 hideStart = seq.getLength();
699 // update visible boundary for sequence
709 return findColumnPosition(start);
711 // otherwise, sequence was completely hidden
715 LOCK.readLock().unlock();
720 * delete any columns in alignmentAnnotation that are hidden (including
721 * sequence associated annotation).
723 * @param alignmentAnnotation
725 public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
727 makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
728 alignmentAnnotation);
732 * delete any columns in alignmentAnnotation that are hidden (including
733 * sequence associated annotation).
736 * remove any annotation to the right of this column
738 * remove any annotation to the left of this column
739 * @param alignmentAnnotation
740 * the annotation to operate on
742 public void makeVisibleAnnotation(int start, int end,
743 AlignmentAnnotation alignmentAnnotation)
747 LOCK.readLock().lock();
749 int startFrom = start;
752 if (alignmentAnnotation.annotations != null)
754 if (hiddenColumns != null && hiddenColumns.size() > 0)
756 removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
760 alignmentAnnotation.restrict(startFrom, endAt);
765 LOCK.readLock().unlock();
769 private void removeHiddenAnnotation(int start, int end,
770 AlignmentAnnotation alignmentAnnotation)
772 // mangle the alignmentAnnotation annotation array
773 ArrayList<Annotation[]> annels = new ArrayList<>();
774 Annotation[] els = null;
778 Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
782 int annotationLength;
783 while (blocks.hasNext())
785 int[] block = blocks.next();
786 annotationLength = block[1] - block[0] + 1;
788 if (blocks.hasNext())
790 // copy just the visible segment of the annotation row
791 copylength = annotationLength;
795 if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
797 // copy just the visible segment of the annotation row
798 copylength = annotationLength;
802 // copy to the end of the annotation row
803 copylength = alignmentAnnotation.annotations.length - block[0];
807 els = new Annotation[annotationLength];
809 System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
811 w += annotationLength;
816 alignmentAnnotation.annotations = new Annotation[w];
819 for (Annotation[] chnk : annels)
821 System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
830 * @return true if there are columns hidden
832 public boolean hasHiddenColumns()
836 LOCK.readLock().lock();
837 return hiddenColumns != null && hiddenColumns.size() > 0;
840 LOCK.readLock().unlock();
846 * @return true if there are more than one set of columns hidden
848 public boolean hasManyHiddenColumns()
852 LOCK.readLock().lock();
853 return hiddenColumns != null && hiddenColumns.size() > 1;
856 LOCK.readLock().unlock();
861 * mark the columns corresponding to gap characters as hidden in the column
866 public void hideInsertionsFor(SequenceI sr)
870 LOCK.writeLock().lock();
871 List<int[]> inserts = sr.getInsertions();
872 for (int[] r : inserts)
874 hideColumns(r[0], r[1]);
878 LOCK.writeLock().unlock();
883 * Unhides, and adds to the selection list, all hidden columns
885 public void revealAllHiddenColumns(ColumnSelection sel)
889 LOCK.writeLock().lock();
890 Iterator<int[]> it = new RegionsIterator();
893 int[] region = it.next();
894 for (int j = region[0]; j < region[1] + 1; j++)
900 hiddenColumns = null;
903 LOCK.writeLock().unlock();
908 * Reveals, and marks as selected, the hidden column range with the given
913 public void revealHiddenColumns(int start, ColumnSelection sel)
917 LOCK.writeLock().lock();
918 Iterator<int[]> it = new RegionsIterator();
921 int[] region = it.next();
922 if (start == region[0])
924 for (int j = region[0]; j < region[1] + 1; j++)
929 hiddenColumns.remove(region);
932 else if (start < region[0])
934 break; // passed all possible matching regions
938 if (hiddenColumns.size() == 0)
940 hiddenColumns = null;
944 LOCK.writeLock().unlock();
949 * Add gaps into the sequences aligned to profileseq under the given
954 * - alignment to have gaps inserted into it
956 * - alignment view where sequence corresponding to profileseq is
958 * @return new HiddenColumns for new alignment view, with insertions into
959 * profileseq marked as hidden.
961 public static HiddenColumns propagateInsertions(SequenceI profileseq,
962 AlignmentI al, AlignmentView input)
966 char gc = al.getGapCharacter();
967 Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
968 HiddenColumns nview = (HiddenColumns) alandhidden[1];
969 SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
970 nview.propagateInsertions(profileseq, al, origseq);
977 * - sequence in al which corresponds to origseq
979 * - alignment which is to have gaps inserted into it
981 * - sequence corresponding to profileseq which defines gap map for
984 private void propagateInsertions(SequenceI profileseq, AlignmentI al,
989 LOCK.writeLock().lock();
991 char gc = al.getGapCharacter();
993 // take the set of hidden columns, and the set of gaps in origseq,
994 // and remove all the hidden gaps from hiddenColumns
996 // first get the gaps as a Bitset
997 BitSet gaps = origseq.gapBitset();
999 // now calculate hidden ^ not(gap)
1000 BitSet hidden = new BitSet();
1001 markHiddenRegions(hidden);
1002 hidden.andNot(gaps);
1003 hiddenColumns = null;
1004 this.hideMarkedBits(hidden);
1006 // for each sequence in the alignment, except the profile sequence,
1007 // insert gaps corresponding to each hidden region
1008 // but where each hidden column region is shifted backwards by the number
1010 // preceding visible gaps
1011 // update hidden columns at the same time
1012 Iterator<int[]> regions = new RegionsIterator();
1013 ArrayList<int[]> newhidden = new ArrayList<>();
1015 int numGapsBefore = 0;
1016 int gapPosition = 0;
1017 while (regions.hasNext())
1019 // get region coordinates accounting for gaps
1020 // we can rely on gaps not being *in* hidden regions because we already
1022 int[] region = regions.next();
1023 while (gapPosition < region[0])
1026 if (gaps.get(gapPosition))
1032 int left = region[0] - numGapsBefore;
1033 int right = region[1] - numGapsBefore;
1034 newhidden.add(new int[] { left, right });
1036 // make a string with number of gaps = length of hidden region
1037 StringBuffer sb = new StringBuffer();
1038 for (int s = 0; s < right - left + 1; s++)
1042 padGaps(sb, left, profileseq, al);
1045 hiddenColumns = newhidden;
1048 LOCK.writeLock().unlock();
1053 * Pad gaps in all sequences in alignment except profileseq
1056 * gap string to insert
1058 * position to insert at
1060 * sequence not to pad
1062 * alignment to pad sequences in
1064 private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
1067 // loop over the sequences and pad with gaps where required
1068 for (int s = 0, ns = al.getHeight(); s < ns; s++)
1070 SequenceI sqobj = al.getSequenceAt(s);
1071 if (sqobj != profileseq)
1073 String sq = al.getSequenceAt(s).getSequenceAsString();
1074 if (sq.length() <= pos)
1077 int diff = pos - sq.length() - 1;
1082 while ((diff = pos - sq.length() - 1) > 0)
1084 if (diff >= sb.length())
1086 sq += sb.toString();
1090 char[] buf = new char[diff];
1091 sb.getChars(0, diff, buf, 0);
1092 sq += buf.toString();
1096 sq += sb.toString();
1100 al.getSequenceAt(s).setSequence(
1101 sq.substring(0, pos) + sb.toString() + sq.substring(pos));
1108 * Returns a hashCode built from hidden column ranges
1111 public int hashCode()
1115 LOCK.readLock().lock();
1117 Iterator<int[]> it = new RegionsIterator();
1118 while (it.hasNext())
1120 int[] hidden = it.next();
1121 hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1122 hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1127 LOCK.readLock().unlock();
1132 * Hide columns corresponding to the marked bits
1135 * - columns map to bits starting from zero
1137 public void hideMarkedBits(BitSet inserts)
1141 LOCK.writeLock().lock();
1142 for (int firstSet = inserts
1143 .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1144 .nextSetBit(lastSet))
1146 lastSet = inserts.nextClearBit(firstSet);
1147 hideColumns(firstSet, lastSet - 1);
1151 LOCK.writeLock().unlock();
1158 * BitSet where hidden columns will be marked
1160 public void markHiddenRegions(BitSet inserts)
1164 LOCK.readLock().lock();
1165 if (hiddenColumns == null)
1169 Iterator<int[]> it = new RegionsIterator();
1170 while (it.hasNext())
1172 int[] range = it.next();
1173 inserts.set(range[0], range[1] + 1);
1177 LOCK.readLock().unlock();
1182 * Calculate the visible start and end index of an alignment.
1185 * full alignment width
1186 * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1188 public int[] getVisibleStartAndEndIndex(int width)
1192 LOCK.readLock().lock();
1193 int[] alignmentStartEnd = new int[] { 0, width - 1 };
1194 int startPos = alignmentStartEnd[0];
1195 int endPos = alignmentStartEnd[1];
1197 int[] lowestRange = new int[] { -1, -1 };
1198 int[] higestRange = new int[] { -1, -1 };
1200 if (hiddenColumns == null)
1202 return new int[] { startPos, endPos };
1205 Iterator<int[]> it = new RegionsIterator();
1206 while (it.hasNext())
1208 int[] range = it.next();
1209 lowestRange = (range[0] <= startPos) ? range : lowestRange;
1210 higestRange = (range[1] >= endPos) ? range : higestRange;
1213 if (lowestRange[0] == -1 && lowestRange[1] == -1)
1215 startPos = alignmentStartEnd[0];
1219 startPos = lowestRange[1] + 1;
1222 if (higestRange[0] == -1 && higestRange[1] == -1)
1224 endPos = alignmentStartEnd[1];
1228 endPos = higestRange[0] - 1;
1230 return new int[] { startPos, endPos };
1233 LOCK.readLock().unlock();
1239 * Finds the hidden region (if any) which starts or ends at res
1242 * visible residue position, unadjusted for hidden columns
1243 * @return region as [start,end] or null if no matching region is found
1245 public int[] getRegionWithEdgeAtRes(int res)
1249 LOCK.readLock().lock();
1250 int adjres = adjustForHiddenColumns(res);
1252 int[] reveal = null;
1253 Iterator<int[]> it = new RegionsIterator(adjres - 2,
1255 while (it.hasNext())
1257 int[] region = it.next();
1258 if (adjres + 1 == region[0] || adjres - 1 == region[1])
1267 LOCK.readLock().unlock();
1272 * Return an iterator over the hidden regions
1274 public Iterator<int[]> iterator()
1276 return new BoundedHiddenColsIterator();
1280 * Return a bounded iterator over the hidden regions
1283 * position to start from (inclusive, absolute column position)
1285 * position to end at (inclusive, absolute column position)
1288 public Iterator<int[]> getBoundedIterator(int start, int end)
1290 return new BoundedHiddenColsIterator(start, end);
1294 * Return a bounded iterator over the *visible* start positions of hidden
1298 * position to start from (inclusive, visible column position)
1300 * position to end at (inclusive, visible column position)
1302 public Iterator<Integer> getBoundedStartIterator(int start, int end)
1304 return new BoundedStartRegionIterator(start, end, true);
1308 * Return an iterator over visible *columns* (not regions) between the given
1309 * start and end boundaries
1312 * first column (inclusive)
1314 * last column (inclusive)
1316 public Iterator<Integer> getVisibleColsIterator(int start, int end)
1318 return new VisibleColsIterator(start, end);
1322 * return an iterator over visible segments between the given start and end
1326 * (first column inclusive from 0)
1328 * (last column - not inclusive)
1330 public Iterator<int[]> getVisContigsIterator(int start, int end)
1332 // return new VisibleBlocksIterator(start, end, true)
1333 return new VisibleContigsIterator(start, end, true);
1337 * return an iterator over visible segments between the given start and end
1341 * (first column - inclusive from 0)
1343 * (last column - inclusive)
1344 * @param useVisibleCoords
1345 * if true, start and end are visible column positions, not absolute
1348 public Iterator<int[]> getVisibleBlocksIterator(int start, int end,
1349 boolean useVisibleCoords)
1351 if (useVisibleCoords)
1354 // we should really just convert start and end here with
1355 // adjustForHiddenColumns
1356 // and then create a VisibleContigsIterator
1357 // but without a cursor this will be horribly slow in some situations
1358 // ... so until then...
1359 return new VisibleBlocksVisBoundsIterator(start, end, true);
1363 return new VisibleContigsIterator(start, end - 1, true);
1368 * A local iterator which iterates over hidden column regions in a range.
1369 * Intended for use ONLY within the HiddenColumns class, because it works
1370 * directly with the hiddenColumns collection without locking (callers should
1371 * lock hiddenColumns).
1373 private class RegionsIterator implements Iterator<int[]>
1375 // start position to iterate from
1378 // end position to iterate to
1381 // current index in hiddenColumns
1382 private int currentPosition = 0;
1384 // current column in hiddenColumns
1385 private int[] nextRegion = null;
1387 // Constructor with bounds
1388 RegionsIterator(int lowerBound, int upperBound)
1390 init(lowerBound, upperBound);
1393 // Unbounded constructor
1396 if (hiddenColumns != null)
1398 // iterator over full hiddenColumns collection
1399 int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
1410 * Construct an iterator over hiddenColums bounded at
1411 * [lowerBound,upperBound]
1414 * lower bound to iterate from
1416 * upper bound to iterate to
1418 private void init(int lowerBound, int upperBound)
1423 if (hiddenColumns != null)
1425 // iterate until a region overlaps with [start,end]
1426 currentPosition = 0;
1427 while ((currentPosition < hiddenColumns.size())
1428 && (hiddenColumns.get(currentPosition)[1] < start))
1432 if (currentPosition < hiddenColumns.size())
1434 nextRegion = hiddenColumns.get(currentPosition);
1440 public boolean hasNext()
1442 return (hiddenColumns != null) && (nextRegion != null)
1443 && (nextRegion[0] <= end);
1449 int[] region = nextRegion;
1451 if (currentPosition < hiddenColumns.size())
1453 nextRegion = hiddenColumns.get(currentPosition);
1465 * A local iterator which reverse iterates over hidden column regions in a
1466 * range. Intended for use ONLY within the HiddenColumns class, because it
1467 * works directly with the hiddenColumns collection without locking (callers
1468 * should lock hiddenColumns).
1470 private class ReverseRegionsIterator implements Iterator<int[]>
1472 // start position to iterate to
1475 // end position to iterate from
1478 // current index in hiddenColumns
1479 private int currentPosition = 0;
1481 // current column in hiddenColumns
1482 private int[] nextRegion = null;
1484 // Constructor with bounds
1485 ReverseRegionsIterator(int lowerBound, int upperBound)
1487 init(lowerBound, upperBound);
1491 * Construct an iterator over hiddenColums bounded at
1492 * [lowerBound,upperBound]
1495 * lower bound to iterate to
1497 * upper bound to iterate from
1499 private void init(int lowerBound, int upperBound)
1504 if (hiddenColumns != null)
1506 // iterate until a region overlaps with [start,end]
1507 currentPosition = hiddenColumns.size() - 1;
1508 while (currentPosition >= 0
1509 && hiddenColumns.get(currentPosition)[1] > end)
1513 if (currentPosition >= 0)
1515 nextRegion = hiddenColumns.get(currentPosition);
1521 public boolean hasNext()
1523 return (hiddenColumns != null) && (nextRegion != null)
1524 && (nextRegion[1] >= start);
1530 int[] region = nextRegion;
1532 if (currentPosition >= 0)
1534 nextRegion = hiddenColumns.get(currentPosition);
1546 * An iterator which iterates over hidden column regions in a range. Works
1547 * with a copy of the hidden columns collection. Intended to be used by
1548 * callers OUTSIDE of HiddenColumns.
1550 private class BoundedHiddenColsIterator implements Iterator<int[]>
1552 // start position to iterate from
1555 // end position to iterate to
1558 // current index in hiddenColumns
1559 private int currentPosition = 0;
1561 // current column in hiddenColumns
1562 private int[] currentRegion;
1564 // local copy or reference to hiddenColumns
1565 private List<int[]> localHidden;
1568 * Unbounded constructor
1570 BoundedHiddenColsIterator()
1572 if (hiddenColumns != null)
1574 int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
1584 * Construct an iterator over hiddenColums bounded at
1585 * [lowerBound,upperBound]
1588 * lower bound to iterate from
1590 * upper bound to iterate to
1592 BoundedHiddenColsIterator(int lowerBound, int upperBound)
1594 init(lowerBound, upperBound);
1598 * Construct an iterator over hiddenColums bounded at
1599 * [lowerBound,upperBound]
1602 * lower bound to iterate from
1604 * upper bound to iterate to
1606 private void init(int lowerBound, int upperBound)
1613 LOCK.readLock().lock();
1615 if (hiddenColumns != null)
1617 localHidden = new ArrayList<>();
1619 // iterate until a region overlaps with [start,end]
1621 while ((i < hiddenColumns.size())
1622 && (hiddenColumns.get(i)[1] < start))
1627 // iterate from start to end, adding each hidden region. Positions are
1628 // absolute, and all regions which *overlap* [start,end] are added.
1629 while (i < hiddenColumns.size()
1630 && (hiddenColumns.get(i)[0] <= end))
1632 int[] rh = hiddenColumns.get(i);
1633 int[] cp = new int[2];
1634 System.arraycopy(rh, 0, cp, 0, rh.length);
1635 localHidden.add(cp);
1642 LOCK.readLock().unlock();
1647 public boolean hasNext()
1649 return (localHidden != null)
1650 && (currentPosition < localHidden.size());
1656 currentRegion = localHidden.get(currentPosition);
1658 return currentRegion;
1663 * An iterator which iterates over visible start positions of hidden column
1664 * regions in a range.
1666 private class BoundedStartRegionIterator implements Iterator<Integer>
1668 // start position to iterate from
1671 // end position to iterate to
1674 // current index in hiddenColumns
1675 private int currentPosition = 0;
1677 // local copy or reference to hiddenColumns
1678 private List<Integer> positions = null;
1681 * Construct an iterator over hiddenColums bounded at
1682 * [lowerBound,upperBound]
1685 * lower bound to iterate from
1687 * upper bound to iterate to
1688 * @param useCopyCols
1689 * whether to make a local copy of hiddenColumns for iteration (set
1690 * to true if calling from outwith the HiddenColumns class)
1692 BoundedStartRegionIterator(int lowerBound, int upperBound,
1702 // assume that if useCopy is false the calling code has locked
1704 LOCK.readLock().lock();
1707 if (hiddenColumns != null)
1709 positions = new ArrayList<>(hiddenColumns.size());
1711 // navigate to start, keeping count of hidden columns
1713 int hiddenSoFar = 0;
1714 while ((i < hiddenColumns.size())
1715 && (hiddenColumns.get(i)[0] < start + hiddenSoFar))
1717 int[] region = hiddenColumns.get(i);
1718 hiddenSoFar += region[1] - region[0] + 1;
1722 // iterate from start to end, adding start positions of each
1723 // hidden region. Positions are visible columns count, not absolute
1724 while (i < hiddenColumns.size()
1725 && (hiddenColumns.get(i)[0] <= end + hiddenSoFar))
1727 int[] region = hiddenColumns.get(i);
1728 positions.add(region[0] - hiddenSoFar);
1729 hiddenSoFar += region[1] - region[0] + 1;
1735 positions = new ArrayList<>();
1741 LOCK.readLock().unlock();
1747 public boolean hasNext()
1749 return (currentPosition < positions.size());
1753 * Get next hidden region start position
1755 * @return the start position in *visible* coordinates
1758 public Integer next()
1760 int result = positions.get(currentPosition);
1767 * Iterator over the visible *columns* (not regions) as determined by the set
1768 * of hidden columns. Uses a local copy of hidden columns.
1773 private class VisibleColsIterator implements Iterator<Integer>
1777 private int current;
1781 private List<int[]> localHidden = new ArrayList<>();
1783 private int nexthiddenregion;
1785 VisibleColsIterator(int firstcol, int lastcol)
1790 nexthiddenregion = 0;
1792 LOCK.readLock().lock();
1794 if (hiddenColumns != null)
1797 for (i = 0; i < hiddenColumns.size()
1798 && (current <= hiddenColumns.get(i)[0]); ++i)
1800 if (current >= hiddenColumns.get(i)[0]
1801 && current <= hiddenColumns.get(i)[1])
1803 // current is hidden, move to right
1804 current = hiddenColumns.get(i)[1] + 1;
1806 nexthiddenregion = i + 1;
1810 for (i = hiddenColumns.size() - 1; i >= 0
1811 && (last >= hiddenColumns.get(i)[1]); --i)
1813 if (last >= hiddenColumns.get(i)[0]
1814 && last <= hiddenColumns.get(i)[1])
1816 // last is hidden, move to left
1817 last = hiddenColumns.get(i)[0] - 1;
1821 // make a local copy of the bit we need
1822 i = nexthiddenregion;
1823 while (i < hiddenColumns.size() && hiddenColumns.get(i)[0] <= last)
1825 int[] region = new int[] { hiddenColumns.get(i)[0],
1826 hiddenColumns.get(i)[1] };
1827 localHidden.add(region);
1832 LOCK.readLock().unlock();
1836 public boolean hasNext()
1838 return next <= last;
1842 public Integer next()
1846 throw new NoSuchElementException();
1849 if ((localHidden != null)
1850 && (nexthiddenregion < localHidden.size()))
1852 // still some more hidden regions
1853 if (next + 1 < localHidden.get(nexthiddenregion)[0])
1855 // next+1 is still before the next hidden region
1858 else if ((next + 1 >= localHidden.get(nexthiddenregion)[0])
1859 && (next + 1 <= localHidden.get(nexthiddenregion)[1]))
1861 // next + 1 is in the next hidden region
1862 next = localHidden.get(nexthiddenregion)[1] + 1;
1868 // finished with hidden regions, just increment normally
1875 public void remove()
1877 throw new UnsupportedOperationException();
1882 * An iterator which iterates over visible regions in a range.
1884 private class VisibleContigsIterator implements Iterator<int[]>
1886 private List<int[]> vcontigs = new ArrayList<>();
1888 private int currentPosition = 0;
1890 VisibleContigsIterator(int start, int end, boolean usecopy)
1896 LOCK.readLock().lock();
1899 if (hiddenColumns != null && hiddenColumns.size() > 0)
1905 for (int[] region : hiddenColumns)
1907 hideStart = region[0];
1908 hideEnd = region[1];
1910 // navigate to start
1911 if (hideEnd < vstart)
1915 if (hideStart > vstart)
1917 int[] contig = new int[] { vstart, hideStart - 1 };
1918 vcontigs.add(contig);
1920 vstart = hideEnd + 1;
1922 // exit if we're past the end
1931 int[] contig = new int[] { vstart, end - 1 };
1932 vcontigs.add(contig);
1937 int[] contig = new int[] { start, end - 1 };
1938 vcontigs.add(contig);
1944 LOCK.readLock().unlock();
1950 public boolean hasNext()
1952 return (currentPosition < vcontigs.size());
1958 int[] result = vcontigs.get(currentPosition);
1965 * An iterator which iterates over visible regions in a range. The range is
1966 * specified in terms of visible column positions. Provides a special
1967 * "endsAtHidden" indicator to allow callers to determine if the final visible
1968 * column is adjacent to a hidden region.
1970 public class VisibleBlocksVisBoundsIterator implements Iterator<int[]>
1972 private List<int[]> vcontigs = new ArrayList<>();
1974 private int currentPosition = 0;
1976 private boolean endsAtHidden = false;
1979 * Constructor for iterator over visible regions in a range.
1982 * start position in terms of visible column position
1984 * end position in terms of visible column position
1986 * whether to use a local copy of hidden columns
1988 VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy)
1990 /* actually this implementation always uses a local copy but this may change in future */
1995 LOCK.readLock().lock();
1998 if (hiddenColumns != null && hiddenColumns.size() > 0)
2000 int blockStart = start;
2002 int hiddenSoFar = 0;
2005 // iterate until a region begins within (start,end]
2007 while ((i < hiddenColumns.size())
2008 && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar))
2010 hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0]
2015 blockStart += hiddenSoFar; // convert start to absolute position
2016 blockEnd += hiddenSoFar; // convert end to absolute position
2018 // iterate from start to end, adding each visible region. Positions
2020 // absolute, and all hidden regions which overlap [start,end] are
2022 while (i < hiddenColumns.size()
2023 && (hiddenColumns.get(i)[0] <= blockEnd))
2025 int[] region = hiddenColumns.get(i);
2027 // end position of this visible region is either just before the
2028 // start of the next hidden region, or the absolute position of
2029 // 'end', whichever is lowest
2030 blockEnd = Math.min(blockEnd, region[0] - 1);
2032 vcontigs.add(new int[] { blockStart, blockEnd });
2034 visSoFar += blockEnd - blockStart + 1;
2036 // next visible region starts after this hidden region
2037 blockStart = region[1] + 1;
2039 hiddenSoFar += region[1] - region[0] + 1;
2041 // reset blockEnd to absolute position of 'end', assuming we've now
2042 // passed all hidden regions before end
2043 blockEnd = end + hiddenSoFar;
2047 if (visSoFar < end - start)
2049 // the number of visible columns we've accounted for is less than
2050 // the number specified by end-start; work out the end position of
2051 // the last visible region
2052 blockEnd = blockStart + end - start - visSoFar;
2053 vcontigs.add(new int[] { blockStart, blockEnd });
2055 // if the last visible region ends at the next hidden region, set
2056 // endsAtHidden=true
2057 if (i < hiddenColumns.size()
2058 && hiddenColumns.get(i)[0] - 1 == blockEnd)
2060 endsAtHidden = true;
2066 // there are no hidden columns, return a single visible contig
2067 vcontigs.add(new int[] { start, end });
2068 endsAtHidden = false;
2074 LOCK.readLock().unlock();
2080 public boolean hasNext()
2082 return (currentPosition < vcontigs.size());
2088 int[] result = vcontigs.get(currentPosition);
2093 public boolean endsAtHidden()
2095 return endsAtHidden;