X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2FHiddenColumns.java;h=8a67741dc2e36d3db8b4ca1e5524d5776530bbbf;hb=327368a55095d5610b71d03e4dcefeaf6131d300;hp=88af9faf5dbba43cd4eeb8512400f3210668ac54;hpb=c2e16e95b564932deda33dc59ecaea367e7b33b0;p=jalview.git diff --git a/src/jalview/datamodel/HiddenColumns.java b/src/jalview/datamodel/HiddenColumns.java index 88af9fa..8a67741 100644 --- a/src/jalview/datamodel/HiddenColumns.java +++ b/src/jalview/datamodel/HiddenColumns.java @@ -20,14 +20,10 @@ */ package jalview.datamodel; -import jalview.util.Comparison; - import java.util.ArrayList; import java.util.BitSet; -import java.util.Collections; import java.util.Iterator; import java.util.List; -import java.util.Vector; import java.util.concurrent.locks.ReentrantReadWriteLock; public class HiddenColumns @@ -36,6 +32,8 @@ public class HiddenColumns private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock(); + private HiddenColumnsCursor cursor = new HiddenColumnsCursor(); + /* * list of hidden column [start, end] ranges; the list is maintained in * ascending start column order @@ -63,7 +61,13 @@ public class HiddenColumns { if (copy.hiddenColumns != null) { - hiddenColumns = copy.copyHiddenRegionsToArrayList(0); + hiddenColumns = new ArrayList<>(); + Iterator it = copy.iterator(); + while (it.hasNext()) + { + hiddenColumns.add(it.next()); + } + cursor.resetCursor(hiddenColumns); } } } finally @@ -73,16 +77,47 @@ public class HiddenColumns } /** - * This method is used to return all the HiddenColumn regions and is intended - * to remain private. External callers which need a copy of the regions can - * call getHiddenColumnsCopyAsList. + * Copy constructor within bounds and with offset. Copies hidden column + * regions fully contained between start and end, and offsets positions by + * subtracting offset. + * + * @param copy + * HiddenColumns instance to copy from + * @param start + * lower bound to copy from + * @param end + * upper bound to copy to + * @param offset + * offset to subtract from each region boundary position * - * @return empty list or List of hidden column intervals */ - private List getHiddenRegions() + public HiddenColumns(HiddenColumns copy, int start, int end, int offset) { - return hiddenColumns == null ? Collections. emptyList() - : hiddenColumns; + try + { + LOCK.writeLock().lock(); + if (copy != null) + { + hiddenColumns = new ArrayList<>(); + Iterator it = copy.getBoundedIterator(start, end); + while (it.hasNext()) + { + int[] region = it.next(); + // still need to check boundaries because iterator returns + // all overlapping regions and we need contained regions + if (region[0] >= start && region[1] <= end) + { + hiddenColumns.add( + new int[] + { region[0] - offset, region[1] - offset }); + } + } + cursor.resetCursor(hiddenColumns); + } + } finally + { + LOCK.writeLock().unlock(); + } } /** @@ -103,13 +138,17 @@ public class HiddenColumns StringBuilder regionBuilder = new StringBuilder(); if (hiddenColumns != null) { - for (int[] range : hiddenColumns) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { + int[] range = it.next(); regionBuilder.append(delimiter).append(range[0]).append(between) .append(range[1]); + if (!it.hasNext()) + { + regionBuilder.deleteCharAt(0); + } } - - regionBuilder.deleteCharAt(0); } return regionBuilder.toString(); } finally @@ -129,10 +168,12 @@ public class HiddenColumns { LOCK.readLock().lock(); int size = 0; - if (hasHiddenColumns()) + if (hiddenColumns != null) { - for (int[] range : hiddenColumns) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { + int[] range = it.next(); size += range[1] - range[0] + 1; } } @@ -143,6 +184,28 @@ public class HiddenColumns } } + /** + * Get the number of distinct hidden regions + * + * @return number of regions + */ + public int getNumberOfRegions() + { + try + { + LOCK.readLock().lock(); + int num = 0; + if (hasHiddenColumns()) + { + num = hiddenColumns.size(); + } + return num; + } finally + { + LOCK.readLock().unlock(); + } + } + @Override public boolean equals(Object obj) { @@ -168,10 +231,13 @@ public class HiddenColumns { return false; } - int i = 0; - for (int[] thisRange : hiddenColumns) + + Iterator it = hiddenColumns.iterator(); + Iterator thatit = that.iterator(); + while (it.hasNext()) { - int[] thatRange = that.hiddenColumns.get(i++); + int[] thisRange = it.next(); + int[] thatRange = thatit.next(); if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1]) { return false; @@ -197,17 +263,12 @@ public class HiddenColumns { LOCK.readLock().lock(); int result = column; + if (hiddenColumns != null) { - for (int i = 0; i < hiddenColumns.size(); i++) - { - int[] region = hiddenColumns.get(i); - if (result >= region[0]) - { - result += region[1] - region[0] + 1; - } - } + result += cursor.getHiddenOffset(column); } + return result; } finally { @@ -228,32 +289,33 @@ public class HiddenColumns { try { - LOCK.readLock().lock(); + /* LOCK.readLock().lock(); int result = hiddenColumn; + int[] region = null; if (hiddenColumns != null) { - int index = 0; - int[] region; - do + Iterator it = new RegionsIterator(0, hiddenColumn, + hiddenColumns, cursor); + while (it.hasNext()) { - region = hiddenColumns.get(index++); + region = it.next(); if (hiddenColumn > region[1]) { result -= region[1] + 1 - region[0]; } - } while ((hiddenColumn > region[1]) - && (index < hiddenColumns.size())); - - if (hiddenColumn >= region[0] && hiddenColumn <= region[1]) + } + + if (region != null && hiddenColumn >= region[0] + && hiddenColumn <= region[1]) { // Here the hidden column is within a region, so // we want to return the position of region[0]-1, adjusted for any // earlier hidden columns. // Calculate the difference between the actual hidden col position // and region[0]-1, and then subtract from result to convert result - // from - // the adjusted hiddenColumn value to the adjusted region[0]-1 value - + // from the adjusted hiddenColumn value to the adjusted region[0]-1 + // value. + // However, if the region begins at 0 we cannot return region[0]-1 // just return 0 if (region[0] == 0) @@ -268,6 +330,46 @@ public class HiddenColumns } return result; // return the shifted position after removing hidden // columns. + } finally + { + LOCK.readLock().unlock(); + }*/ + + LOCK.readLock().lock(); + int result = hiddenColumn; + // int[] region = null; + if (hiddenColumns != null) + { + int index = cursor.findRegionForColumn(hiddenColumn); + int hiddenBeforeCol = cursor.getHiddenSoFar(); + + // just subtract hidden cols count - this works fine if column is + // visible + result = hiddenColumn - hiddenBeforeCol; + + // now check in case column is hidden - it will be in the returned + // hidden region + if (index < hiddenColumns.size()) + { + int[] region = hiddenColumns.get(index); + if (hiddenColumn >= region[0] && hiddenColumn <= region[1]) + { + // actually col is hidden, return region[0]-1 + // unless region[0]==0 in which case return 0 + if (region[0] == 0) + { + result = 0; + } + else + { + result = region[0] - 1 - hiddenBeforeCol; + } + } + } + } + System.out.println(hiddenColumn + " " + result); + return result; // return the shifted position after removing hidden + // columns. } finally { LOCK.readLock().unlock(); @@ -289,106 +391,37 @@ public class HiddenColumns { try { - LOCK.readLock().lock(); int distance = visibleDistance; // in case startColumn is in a hidden region, move it to the left int start = adjustForHiddenColumns(findColumnPosition(startColumn)); - // get index of hidden region to left of start - int index = getHiddenIndexLeft(start); - if (index == -1) - { - // no hidden regions to left of startColumn - return start - distance; - } - - // walk backwards through the alignment subtracting the counts of visible - // columns from distance - int[] region; - int gap = 0; - int nextstart = start; - - while ((index > -1) && (distance - gap > 0)) - { - // subtract the gap to right of region from distance - distance -= gap; - start = nextstart; - - // calculate the next gap - region = hiddenColumns.get(index); - gap = start - region[1]; - - // set start to just to left of current region - nextstart = region[0] - 1; - index--; - } - - if (distance - gap > 0) - { - // fell out of loop because there are no more hidden regions - distance -= gap; - return nextstart - distance; - } - return start - distance; - } finally - { - LOCK.readLock().unlock(); - } - - } - - /** - * Use this method to determine the set of hiddenRegion start positions - * between absolute position and absolute position - * - * @param start - * absolute residue to start from - * @param end - * absolute residue to end at - * - * @return list of column numbers in *visible* view where hidden regions start - */ - public List findHiddenRegionPositions(int start, int end) - { - try - { - LOCK.readLock().lock(); - List positions = null; + Iterator it = new ReverseRegionsIterator(0, start, + hiddenColumns); - if (hiddenColumns != null) + while (it.hasNext() && (distance > 0)) { - positions = new ArrayList<>(hiddenColumns.size()); + int[] region = it.next(); - // navigate to start, keeping count of hidden columns - int i = 0; - int hiddenSoFar = 0; - while ((i < hiddenColumns.size()) - && (hiddenColumns.get(i)[0] < start)) + if (start > region[1]) { - int[] region = hiddenColumns.get(i); - hiddenSoFar += region[1] - region[0] + 1; - i++; - } - - // iterate from start to end, adding start positions of each - // hidden region. Positions are visible columns count, not absolute - while (i < hiddenColumns.size() - && (hiddenColumns.get(i)[0] < end)) - { - int[] region = hiddenColumns.get(i); - positions.add(region[0] - hiddenSoFar); - hiddenSoFar += region[1] - region[0] + 1; - i++; + // subtract the gap to right of region from distance + if (start - region[1] <= distance) + { + distance -= start - region[1]; + start = region[0] - 1; + } + else + { + start = start - distance; + distance = 0; + } } } - else - { - positions = new ArrayList<>(); - } - return positions; + return start - distance; + } finally { LOCK.readLock().unlock(); @@ -399,8 +432,9 @@ public class HiddenColumns * This method returns the rightmost limit of a region of an alignment with * hidden columns. In otherwords, the next hidden column. * - * @param index - * int + * @param alPos + * the absolute (visible) alignmentPosition to find the next hidden + * column for */ public int getHiddenBoundaryRight(int alPos) { @@ -409,33 +443,38 @@ public class HiddenColumns LOCK.readLock().lock(); if (hiddenColumns != null) { - int index = 0; - do + int index = cursor.findRegionForColumn(alPos); + if (index < hiddenColumns.size()) { int[] region = hiddenColumns.get(index); if (alPos < region[0]) { return region[0]; } - - index++; - } while (index < hiddenColumns.size()); + else if ((alPos <= region[1]) + && (index + 1 < hiddenColumns.size())) + { + // alPos is within a hidden region, return the next one + // if there is one + region = hiddenColumns.get(index + 1); + return region[0]; + } + } } - return alPos; } finally { LOCK.readLock().unlock(); } - } /** * This method returns the leftmost limit of a region of an alignment with * hidden columns. In otherwords, the previous hidden column. * - * @param index - * int + * @param alPos + * the absolute (visible) alignmentPosition to find the previous + * hidden column for */ public int getHiddenBoundaryLeft(int alPos) { @@ -445,68 +484,28 @@ public class HiddenColumns if (hiddenColumns != null) { - int index = hiddenColumns.size() - 1; - do - { - int[] region = hiddenColumns.get(index); - if (alPos > region[1]) - { - return region[1]; - } - - index--; - } while (index > -1); - } - - return alPos; - } finally - { - LOCK.readLock().unlock(); - } - } + int index = cursor.findRegionForColumn(alPos); - /** - * This method returns the index of the hidden region to the left of a column - * position. If the column is in a hidden region it returns the index of the - * region to the left. If there is no hidden region to the left it returns -1. - * - * @param pos - * int - */ - private int getHiddenIndexLeft(int pos) - { - try - { - - LOCK.readLock().lock(); - if (hiddenColumns != null) - { - int index = hiddenColumns.size() - 1; - do + if (index > 0) { - int[] region = hiddenColumns.get(index); - if (pos > region[1]) - { - return index; - } - - index--; - } while (index > -1); + int[] region = hiddenColumns.get(index - 1); + return region[1]; + } } - - return -1; + return alPos; } finally { LOCK.readLock().unlock(); } - } /** - * Adds the specified column range to the hidden columns + * Adds the specified column range to the hidden columns collection * * @param start + * start of range to add (absolute position in alignment) * @param end + * end of range to add (absolute position in alignment) */ public void hideColumns(int start, int end) { @@ -530,66 +529,29 @@ public class HiddenColumns } /* - * traverse existing hidden ranges and insert / amend / append as - * appropriate + * new range follows everything else; check first to avoid looping over whole hiddenColumns collection */ - for (int i = 0; i < hiddenColumns.size(); i++) + if (hiddenColumns.isEmpty() + || start > hiddenColumns.get(hiddenColumns.size() - 1)[1]) { - int[] region = hiddenColumns.get(i); - - if (end < region[0] - 1) - { - /* - * insert discontiguous preceding range - */ - hiddenColumns.add(i, new int[] { start, end }); - return; - } - - if (end <= region[1]) - { - /* - * new range overlaps existing, or is contiguous preceding it - adjust - * start column - */ - region[0] = Math.min(region[0], start); - return; - } - - if (start <= region[1] + 1) + hiddenColumns.add(new int[] { start, end }); + } + else + { + /* + * traverse existing hidden ranges and insert / amend / append as + * appropriate + */ + boolean added = false; + for (int i = 0; !added && i < hiddenColumns.size(); i++) { - /* - * new range overlaps existing, or is contiguous following it - adjust - * start and end columns - */ - region[0] = Math.min(region[0], start); - region[1] = Math.max(region[1], end); - - /* - * also update or remove any subsequent ranges - * that are overlapped - */ - while (i < hiddenColumns.size() - 1) - { - int[] nextRegion = hiddenColumns.get(i + 1); - if (nextRegion[0] > end + 1) - { - /* - * gap to next hidden range - no more to update - */ - break; - } - region[1] = Math.max(nextRegion[1], end); - hiddenColumns.remove(i + 1); - } - return; - } + added = insertRangeAtRegion(i, start, end); + } // for + } + if (!wasAlreadyLocked) + { + cursor.resetCursor(hiddenColumns); } - - /* - * remaining case is that the new range follows everything else - */ - hiddenColumns.add(new int[] { start, end }); } finally { if (!wasAlreadyLocked) @@ -599,153 +561,113 @@ public class HiddenColumns } } - public boolean isVisible(int column) + /** + * Insert [start, range] at the region at index i in hiddenColumns, if + * feasible + * + * @param i + * index to insert at + * @param start + * start of range to insert + * @param end + * end of range to insert + * @return true if range was successfully inserted + */ + private boolean insertRangeAtRegion(int i, int start, int end) { - try - { - LOCK.readLock().lock(); - - if (hiddenColumns != null) - { - for (int[] region : hiddenColumns) - { - if (column >= region[0] && column <= region[1]) - { - return false; - } - } - } + boolean added = false; - return true; - } finally + int[] region = hiddenColumns.get(i); + if (end < region[0] - 1) { - LOCK.readLock().unlock(); + /* + * insert discontiguous preceding range + */ + hiddenColumns.add(i, new int[] { start, end }); + added = true; } - } - - private ArrayList copyHiddenRegionsToArrayList(int startIndex) - { - int size = 0; - if (hiddenColumns != null) + else if (end <= region[1]) { - size = hiddenColumns.size(); + /* + * new range overlaps existing, or is contiguous preceding it - adjust + * start column + */ + region[0] = Math.min(region[0], start); + added = true; } - ArrayList copy = new ArrayList<>(size); - - for (int i = startIndex, j = size; i < j; i++) + else if (start <= region[1] + 1) { - int[] rh; - int[] cp; - rh = hiddenColumns.get(i); - if (rh != null) + /* + * new range overlaps existing, or is contiguous following it - adjust + * start and end columns + */ + region[0] = Math.min(region[0], start); + region[1] = Math.max(region[1], end); + + /* + * also update or remove any subsequent ranges + * that are overlapped + */ + while (i < hiddenColumns.size() - 1) { - cp = new int[rh.length]; - System.arraycopy(rh, 0, cp, 0, rh.length); - copy.add(cp); + int[] nextRegion = hiddenColumns.get(i + 1); + if (nextRegion[0] > end + 1) + { + /* + * gap to next hidden range - no more to update + */ + break; + } + region[1] = Math.max(nextRegion[1], end); + hiddenColumns.subList(i + 1, i + 2).clear(); } + added = true; } - - return copy; + return added; } /** - * Returns a copy of the vector of hidden regions, as an ArrayList. Before - * using this method please consider if you really need access to the hidden - * regions - a new (or existing!) method on HiddenColumns might be more - * appropriate. + * Answers if a column in the alignment is visible * - * @return hidden regions as an ArrayList of [start,end] pairs + * @param column + * absolute position of column in the alignment + * @return true if column is visible */ - public ArrayList getHiddenColumnsCopy() + public boolean isVisible(int column) { try { LOCK.readLock().lock(); - return copyHiddenRegionsToArrayList(0); - } finally - { - LOCK.readLock().unlock(); - } - } - /** - * return all visible segments between the given start and end boundaries - * - * @param start - * (first column inclusive from 0) - * @param end - * (last column - not inclusive) - * @return int[] {i_start, i_end, ..} where intervals lie in - * start<=i_start<=i_end 0) + Iterator it = new RegionsIterator(column, column, + hiddenColumns, cursor); + while (it.hasNext()) { - // max limit on number of visible contigs - // so we can dimension array - int maxcontigs = end - start + 1; - if (maxcontigs > (hiddenColumns.size() + 1) * 2) - { - maxcontigs = (hiddenColumns.size() + 1) * 2; - } - int[] vcontigs = new int[maxcontigs]; - int vstart = start; - int hideStart; - int hideEnd; - int i = 0; - - for (int[] region : hiddenColumns) - { - hideStart = region[0]; - hideEnd = region[1]; - - // navigate to start - if (hideEnd < vstart) - { - continue; - } - if (hideStart > vstart) - { - vcontigs[i * 2] = vstart; - vcontigs[i * 2 + 1] = hideStart - 1; - i++; - } - vstart = hideEnd + 1; - - // exit if we're past the end - if (vstart >= end) - { - break; - } - } - - if (vstart < end) + int[] region = it.next(); + if (column >= region[0] && column <= region[1]) { - vcontigs[i * 2] = vstart; - vcontigs[i * 2 + 1] = end - 1; - i++; + return false; } - - // copy final array into array of correct size - int[] trimmmedContigs = new int[i * 2]; - System.arraycopy(vcontigs, 0, trimmmedContigs, 0, i * 2); - - return trimmmedContigs; - } - else - { - return new int[] { start, end - 1 }; } + + return true; } finally { LOCK.readLock().unlock(); } } + /** + * Get the visible sections of a set of sequences + * + * @param start + * sequence position to start from + * @param end + * sequence position to end at + * @param seqs + * an array of sequences + * @return an array of strings encoding the visible parts of each sequence + */ public String[] getVisibleSequenceStrings(int start, int end, SequenceI[] seqs) { @@ -760,38 +682,22 @@ public class HiddenColumns { StringBuffer visibleSeq = new StringBuffer(); - int blockStart = start; - int blockEnd = end; - int hideStart; - int hideEnd; + Iterator blocks = new VisibleContigsIterator(start, + end + 1, hiddenColumns); - for (int[] region : hiddenColumns) + while (blocks.hasNext()) { - hideStart = region[0]; - hideEnd = region[1]; - - if (hideStart < start) + int[] block = blocks.next(); + if (blocks.hasNext()) { - continue; + visibleSeq + .append(seqs[i].getSequence(block[0], block[1] + 1)); } - - blockStart = Math.min(blockStart, hideEnd + 1); - blockEnd = Math.min(blockEnd, hideStart); - - if (blockStart > blockEnd) + else { - break; + visibleSeq + .append(seqs[i].getSequence(block[0], block[1])); } - - visibleSeq.append(seqs[i].getSequence(blockStart, blockEnd)); - - blockStart = hideEnd + 1; - blockEnd = end; - } - - if (end > blockStart) - { - visibleSeq.append(seqs[i].getSequence(blockStart, end)); } selections[i] = visibleSeq.toString(); @@ -813,89 +719,67 @@ public class HiddenColumns } /** - * Locate the first and last position visible for this sequence. if seq isn't - * visible then return the position of the left and right of the hidden - * boundary region, and the corresponding alignment column indices for the - * extent of the sequence + * Locate the first position visible for this sequence. If seq isn't visible + * then return the position of the left side of the hidden boundary region. * * @param seq - * @return int[] { visible start, visible end, first seqpos, last seqpos, - * alignment index for seq start, alignment index for seq end } + * sequence to find position for + * @return visible start position */ - public int[] locateVisibleBoundsOfSequence(SequenceI seq) + public int locateVisibleStartOfSequence(SequenceI seq) { try { LOCK.readLock().lock(); - int fpos = seq.getStart(); - int lpos = seq.getEnd(); int start = 0; if (hiddenColumns == null || hiddenColumns.size() == 0) { - int ifpos = seq.findIndex(fpos) - 1; - int ilpos = seq.findIndex(lpos) - 1; - return new int[] { ifpos, ifpos, ilpos }; + return seq.findIndex(seq.getStart()) - 1; } // Simply walk along the sequence whilst watching for hidden column // boundaries - List regions = getHiddenRegions(); - int spos = fpos; - int rcount = 0; + Iterator regions = hiddenColumns.iterator(); int hideStart = seq.getLength(); int hideEnd = -1; int visPrev = 0; int visNext = 0; - int firstP = -1; - int lastP = -1; boolean foundStart = false; - for (int p = 0, pLen = seq.getLength(); spos <= seq.getEnd() - && p < pLen; p++) + + // step through the non-gapped positions of the sequence + for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++) { - if (!Comparison.isGap(seq.getCharAt(p))) + // get alignment position of this residue in the sequence + int p = seq.findIndex(i) - 1; + + // update hidden region start/end + while (hideEnd < p && regions.hasNext()) { - // keep track of first/last column - // containing sequence data regardless of visibility - if (firstP == -1) - { - firstP = p; - } - lastP = p; - // update hidden region start/end - while (hideEnd < p && rcount < regions.size()) - { - int[] region = regions.get(rcount++); - visPrev = visNext; - visNext += region[0] - visPrev; - hideStart = region[0]; - hideEnd = region[1]; - } - if (hideEnd < p) - { - hideStart = seq.getLength(); - } - // update visible boundary for sequence - if (p < hideStart) - { - if (!foundStart) - { - fpos = spos; - start = p; - foundStart = true; - } - lpos = spos; - } - // look for next sequence position - spos++; + int[] region = regions.next(); + visPrev = visNext; + visNext += region[0] - visPrev; + hideStart = region[0]; + hideEnd = region[1]; + } + if (hideEnd < p) + { + hideStart = seq.getLength(); + } + // update visible boundary for sequence + if (p < hideStart) + { + start = p; + foundStart = true; } } + if (foundStart) { - return new int[] { findColumnPosition(start), firstP, lastP }; + return findColumnPosition(start); } // otherwise, sequence was completely hidden - return new int[] { visPrev, firstP, lastP }; + return visPrev; } finally { LOCK.readLock().unlock(); @@ -910,7 +794,8 @@ public class HiddenColumns */ public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation) { - makeVisibleAnnotation(-1, -1, alignmentAnnotation); + makeVisibleAnnotation(0, alignmentAnnotation.annotations.length, + alignmentAnnotation); } /** @@ -930,95 +815,83 @@ public class HiddenColumns try { LOCK.readLock().lock(); - if (alignmentAnnotation.annotations == null) - { - return; - } - if (start == end && end == -1) - { - start = 0; - end = alignmentAnnotation.annotations.length; - } - if (hiddenColumns != null && hiddenColumns.size() > 0) - { - // then mangle the alignmentAnnotation annotation array - Vector annels = new Vector<>(); - Annotation[] els = null; - int blockStart = start; - int blockEnd = end; - int hideStart; - int hideEnd; - int w = 0; - - for (int[] region : hiddenColumns) - { - hideStart = region[0]; - hideEnd = region[1]; - - if (hideStart < start) - { - continue; - } - - blockStart = Math.min(blockStart, hideEnd + 1); - blockEnd = Math.min(blockEnd, hideStart); - - if (blockStart > blockEnd) - { - break; - } - els = new Annotation[blockEnd - blockStart]; - annels.addElement(els); - System.arraycopy(alignmentAnnotation.annotations, blockStart, els, - 0, els.length); - w += els.length; - blockStart = hideEnd + 1; - blockEnd = end; - } + int startFrom = start; + int endAt = end; - if (end > blockStart) + if (alignmentAnnotation.annotations != null) + { + if (hiddenColumns != null && hiddenColumns.size() > 0) { - els = new Annotation[end - blockStart + 1]; - annels.addElement(els); - if ((els.length - + blockStart) <= alignmentAnnotation.annotations.length) - { - // copy just the visible segment of the annotation row - System.arraycopy(alignmentAnnotation.annotations, blockStart, - els, 0, els.length); - } - else - { - // copy to the end of the annotation row - System.arraycopy(alignmentAnnotation.annotations, blockStart, - els, 0, - (alignmentAnnotation.annotations.length - blockStart)); - } - w += els.length; + removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation); } - if (w == 0) + else { - return; + alignmentAnnotation.restrict(startFrom, endAt); } + } + } finally + { + LOCK.readLock().unlock(); + } + } - alignmentAnnotation.annotations = new Annotation[w]; - w = 0; - - for (Annotation[] chnk : annels) - { - System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w, - chnk.length); - w += chnk.length; - } + private void removeHiddenAnnotation(int start, int end, + AlignmentAnnotation alignmentAnnotation) + { + // mangle the alignmentAnnotation annotation array + ArrayList annels = new ArrayList<>(); + Annotation[] els = null; + + int w = 0; + + Iterator blocks = new VisibleContigsIterator(start, end + 1, + hiddenColumns); + + int copylength; + int annotationLength; + while (blocks.hasNext()) + { + int[] block = blocks.next(); + annotationLength = block[1] - block[0] + 1; + + if (blocks.hasNext()) + { + // copy just the visible segment of the annotation row + copylength = annotationLength; } else { - alignmentAnnotation.restrict(start, end); + if (annotationLength + block[0] <= alignmentAnnotation.annotations.length) + { + // copy just the visible segment of the annotation row + copylength = annotationLength; + } + else + { + // copy to the end of the annotation row + copylength = alignmentAnnotation.annotations.length - block[0]; + } } - } finally + + els = new Annotation[annotationLength]; + annels.add(els); + System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0, + copylength); + w += annotationLength; + } + + if (w != 0) { - LOCK.readLock().unlock(); + alignmentAnnotation.annotations = new Annotation[w]; + + w = 0; + for (Annotation[] chnk : annels) + { + System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w, + chnk.length); + w += chnk.length; + } } } @@ -1070,6 +943,7 @@ public class HiddenColumns { hideColumns(r[0], r[1]); } + cursor.resetCursor(hiddenColumns); } finally { LOCK.writeLock().unlock(); @@ -1086,17 +960,18 @@ public class HiddenColumns LOCK.writeLock().lock(); if (hiddenColumns != null) { - for (int i = 0; i < hiddenColumns.size(); i++) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { - int[] region = hiddenColumns.get(i); + int[] region = it.next(); for (int j = region[0]; j < region[1] + 1; j++) { sel.addElement(j); } } + hiddenColumns = null; + cursor.resetCursor(hiddenColumns); } - - hiddenColumns = null; } finally { LOCK.writeLock().unlock(); @@ -1114,24 +989,31 @@ public class HiddenColumns try { LOCK.writeLock().lock(); - for (int i = 0; i < hiddenColumns.size(); i++) + Iterator it = new RegionsIterator(start, start, hiddenColumns, + cursor); + while (it.hasNext()) { - int[] region = hiddenColumns.get(i); + int[] region = it.next(); if (start == region[0]) { for (int j = region[0]; j < region[1] + 1; j++) { sel.addElement(j); } - - hiddenColumns.remove(region); + it.remove(); break; } + else if (start < region[0]) + { + break; // passed all possible matching regions + } } + if (hiddenColumns.size() == 0) { hiddenColumns = null; } + cursor.resetCursor(hiddenColumns); } finally { LOCK.writeLock().unlock(); @@ -1177,59 +1059,70 @@ public class HiddenColumns private void propagateInsertions(SequenceI profileseq, AlignmentI al, SequenceI origseq) { - char gc = al.getGapCharacter(); + try + { + LOCK.writeLock().lock(); + + char gc = al.getGapCharacter(); + + // take the set of hidden columns, and the set of gaps in origseq, + // and remove all the hidden gaps from hiddenColumns + + // first get the gaps as a Bitset + BitSet gaps = origseq.gapBitset(); - // take the set of hidden columns, and the set of gaps in origseq, - // and remove all the hidden gaps from hiddenColumns - - // first get the gaps as a Bitset - BitSet gaps = origseq.gapBitset(); - - // now calculate hidden ^ not(gap) - BitSet hidden = new BitSet(); - markHiddenRegions(hidden); - hidden.andNot(gaps); - hiddenColumns = null; - this.hideMarkedBits(hidden); - - // for each sequence in the alignment, except the profile sequence, - // insert gaps corresponding to each hidden region - // but where each hidden column region is shifted backwards by the number of - // preceding visible gaps - // update hidden columns at the same time - ArrayList regions = getHiddenColumnsCopy(); - ArrayList newhidden = new ArrayList<>(); - - int numGapsBefore = 0; - int gapPosition = 0; - for (int[] region : regions) - { - // get region coordinates accounting for gaps - // we can rely on gaps not being *in* hidden regions because we already - // removed those - while (gapPosition < region[0]) + // now calculate hidden ^ not(gap) + BitSet hidden = new BitSet(); + markHiddenRegions(hidden); + hidden.andNot(gaps); + hiddenColumns = null; + this.hideMarkedBits(hidden); + + // for each sequence in the alignment, except the profile sequence, + // insert gaps corresponding to each hidden region + // but where each hidden column region is shifted backwards by the number + // of + // preceding visible gaps + // update hidden columns at the same time + Iterator regions = hiddenColumns.iterator(); + ArrayList newhidden = new ArrayList<>(); + + int numGapsBefore = 0; + int gapPosition = 0; + while (regions.hasNext()) { - gapPosition++; - if (gaps.get(gapPosition)) + // get region coordinates accounting for gaps + // we can rely on gaps not being *in* hidden regions because we already + // removed those + int[] region = regions.next(); + while (gapPosition < region[0]) { - numGapsBefore++; + gapPosition++; + if (gaps.get(gapPosition)) + { + numGapsBefore++; + } } - } - int left = region[0] - numGapsBefore; - int right = region[1] - numGapsBefore; - newhidden.add(new int[] { left, right }); + int left = region[0] - numGapsBefore; + int right = region[1] - numGapsBefore; + newhidden.add(new int[] { left, right }); - // make a string with number of gaps = length of hidden region - StringBuffer sb = new StringBuffer(); - for (int s = 0; s < right - left + 1; s++) - { - sb.append(gc); - } - padGaps(sb, left, profileseq, al); + // make a string with number of gaps = length of hidden region + StringBuffer sb = new StringBuffer(); + for (int s = 0; s < right - left + 1; s++) + { + sb.append(gc); + } + padGaps(sb, left, profileseq, al); + } + hiddenColumns = newhidden; + cursor.resetCursor(hiddenColumns); + } finally + { + LOCK.writeLock().unlock(); } - hiddenColumns = newhidden; } /** @@ -1297,13 +1190,12 @@ public class HiddenColumns { LOCK.readLock().lock(); int hashCode = 1; - if (hiddenColumns != null) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { - for (int[] hidden : hiddenColumns) - { - hashCode = HASH_MULTIPLIER * hashCode + hidden[0]; - hashCode = HASH_MULTIPLIER * hashCode + hidden[1]; - } + int[] hidden = it.next(); + hashCode = HASH_MULTIPLIER * hashCode + hidden[0]; + hashCode = HASH_MULTIPLIER * hashCode + hidden[1]; } return hashCode; } finally @@ -1330,6 +1222,7 @@ public class HiddenColumns lastSet = inserts.nextClearBit(firstSet); hideColumns(firstSet, lastSet - 1); } + cursor.resetCursor(hiddenColumns); } finally { LOCK.writeLock().unlock(); @@ -1350,8 +1243,10 @@ public class HiddenColumns { return; } - for (int[] range : hiddenColumns) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { + int[] range = it.next(); inserts.set(range[0], range[1] + 1); } } finally @@ -1384,10 +1279,12 @@ public class HiddenColumns return new int[] { startPos, endPos }; } - for (int[] hiddenCol : hiddenColumns) + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) { - lowestRange = (hiddenCol[0] <= startPos) ? hiddenCol : lowestRange; - higestRange = (hiddenCol[1] >= endPos) ? hiddenCol : higestRange; + int[] range = it.next(); + lowestRange = (range[0] <= startPos) ? range : lowestRange; + higestRange = (range[1] >= endPos) ? range : higestRange; } if (lowestRange[0] == -1 && lowestRange[1] == -1) @@ -1412,7 +1309,6 @@ public class HiddenColumns { LOCK.readLock().unlock(); } - } /** @@ -1430,238 +1326,277 @@ public class HiddenColumns int adjres = adjustForHiddenColumns(res); int[] reveal = null; + if (hiddenColumns != null) { - for (int[] region : hiddenColumns) + int regionindex = cursor.findRegionForColumn(adjres - 1); + if (hiddenColumns.get(regionindex)[1] == adjres - 1) + { + reveal = hiddenColumns.get(regionindex); + } + else { - if (adjres + 1 == region[0] || adjres - 1 == region[1]) + regionindex = cursor.findRegionForColumn(adjres + 1); + if (hiddenColumns.get(regionindex)[0] == adjres + 1) { - reveal = region; - break; + reveal = hiddenColumns.get(regionindex); } } } return reveal; + } finally { LOCK.readLock().unlock(); } } + /** + * Return an iterator over the hidden regions + */ public Iterator iterator() { - if (hiddenColumns != null) + try { - return new BoundedHiddenColsIterator(0, hiddenColumns.size(), true); - } - else + LOCK.readLock().lock(); + return new BoundedHiddenColsIterator(hiddenColumns); + } finally { - return new BoundedHiddenColsIterator(0, 0, true); + LOCK.readLock().unlock(); } } - public Iterator getBoundedIterator(int start, int end, - boolean useCopy) + /** + * Return a bounded iterator over the hidden regions + * + * @param start + * position to start from (inclusive, absolute column position) + * @param end + * position to end at (inclusive, absolute column position) + * @return + */ + public Iterator getBoundedIterator(int start, int end) { - return new BoundedHiddenColsIterator(start, end, useCopy); + try + { + LOCK.readLock().lock(); + return new BoundedHiddenColsIterator(start, end, hiddenColumns); + } finally + { + LOCK.readLock().unlock(); + } } - public Iterator getBoundedStartIterator(int start, int end, - boolean useCopy) + /** + * Return a bounded iterator over the *visible* start positions of hidden + * regions + * + * @param start + * position to start from (inclusive, visible column position) + * @param end + * position to end at (inclusive, visible column position) + */ + public Iterator getBoundedStartIterator(int start, int end) { - return new BoundedStartRegionIterator(start, end, useCopy); + try + { + LOCK.readLock().lock(); + return new BoundedStartRegionIterator(start, end, hiddenColumns); + } finally + { + LOCK.readLock().unlock(); + } } /** - * An iterator which iterates over hidden column regions in a range. + * Return an iterator over visible *columns* (not regions) between the given + * start and end boundaries * - * @author kmourao - * + * @param start + * first column (inclusive) + * @param end + * last column (inclusive) */ - - - class BoundedHiddenColsIterator implements Iterator + public Iterator getVisibleColsIterator(int start, int end) { - - private int start; // start position to iterate from - - private int end; // end position to iterate to - - // current index in hiddenColumns - private int currentPosition = 0; - - // current column in hiddenColumns - private int[] currentRegion; - - // whether to make a local copy of hiddenColumns - private final boolean useCopy; - - // local copy or reference to hiddenColumns - private List localHidden; - - /** - * Construct an iterator over hiddenColums bounded at - * [lowerBound,upperBound] - * - * @param lowerBound - * lower bound to iterate from - * @param upperBound - * upper bound to iterate to - * @param opt - * Option.OVERLAP: regions which overlap [lowerBound,upperBound] - * are included Option.START: regions which start in - * [lowerBound,upperBound] are included - * @param useAbsolutePos - * have bounds and return values with reference to absolute indices - * (if false, use indices for visible columns) - * @param useCopyCols - * whether to make a local copy of hiddenColumns for iteration (set - * to true if calling from outwith the HiddenColumns class) - */ - BoundedHiddenColsIterator(int lowerBound, int upperBound, - boolean useCopyCols) + try { - start = lowerBound; - end = upperBound; - useCopy = useCopyCols; - - try - { - if (useCopy) - { - // assume that if useCopy is false the calling code has locked - // hiddenColumns - LOCK.readLock().lock(); - } - - if (hiddenColumns != null) - { - localHidden = new ArrayList<>(); - - // iterate until a region overlaps with [start,end] - int i = 0; - while ((i < hiddenColumns.size()) - && (hiddenColumns.get(i)[1] < start)) - { - i++; - } - - // iterate from start to end, adding each hidden region. Positions are - // absolute, and all regions which *overlap* [start,end] are added. - while (i < hiddenColumns.size() - && (hiddenColumns.get(i)[0] <= end)) - { - int[] rh; - int[] cp; - rh = hiddenColumns.get(i); - if (rh != null) - { - cp = new int[rh.length]; - System.arraycopy(rh, 0, cp, 0, rh.length); - localHidden.add(cp); - } - i++; - } - } - } - finally - { - if (useCopy) - { - LOCK.readLock().unlock(); - } - } + LOCK.readLock().lock(); + return new VisibleColsIterator(start, end, hiddenColumns); + } finally + { + LOCK.readLock().unlock(); } + } - @Override - public boolean hasNext() + /** + * return an iterator over visible segments between the given start and end + * boundaries + * + * @param start + * (first column inclusive from 0) + * @param end + * (last column - not inclusive) + */ + public Iterator getVisContigsIterator(int start, int end) + { + try { - return (localHidden != null) - && (currentPosition < localHidden.size()); + LOCK.readLock().lock(); + return new VisibleContigsIterator(start, end, hiddenColumns); + } finally + { + LOCK.readLock().unlock(); } + } - @Override - public int[] next() + /** + * return an iterator over visible segments between the given start and end + * boundaries + * + * @param start + * (first column - inclusive from 0) + * @param end + * (last column - inclusive) + * @param useVisibleCoords + * if true, start and end are visible column positions, not absolute + * positions + */ + public Iterator getVisibleBlocksIterator(int start, int end, + boolean useVisibleCoords) + { + if (useVisibleCoords) + { + // TODO + // we should really just convert start and end here with + // adjustForHiddenColumns + // and then create a VisibleContigsIterator + // but without a cursor this will be horribly slow in some situations + // ... so until then... + return new VisibleBlocksVisBoundsIterator(start, end, true); + } + else { - currentRegion = localHidden.get(currentPosition); - currentPosition++; - return currentRegion; + try + { + LOCK.readLock().lock(); + return new VisibleContigsIterator(start, end + 1, hiddenColumns); + } finally + { + LOCK.readLock().unlock(); + } } } - class BoundedStartRegionIterator implements Iterator + /** + * An iterator which iterates over visible regions in a range. The range is + * specified in terms of visible column positions. Provides a special + * "endsAtHidden" indicator to allow callers to determine if the final visible + * column is adjacent to a hidden region. + */ + public class VisibleBlocksVisBoundsIterator implements Iterator { + private List vcontigs = new ArrayList<>(); - private int start; // start position to iterate from - - private int end; // end position to iterate to - - // current index in hiddenColumns private int currentPosition = 0; - // local copy or reference to hiddenColumns - private List positions = null; + private boolean endsAtHidden = false; /** - * Construct an iterator over hiddenColums bounded at - * [lowerBound,upperBound] + * Constructor for iterator over visible regions in a range. * - * @param lowerBound - * lower bound to iterate from - * @param upperBound - * upper bound to iterate to - * @param useCopyCols - * whether to make a local copy of hiddenColumns for iteration (set - * to true if calling from outwith the HiddenColumns class) + * @param start + * start position in terms of visible column position + * @param end + * end position in terms of visible column position + * @param usecopy + * whether to use a local copy of hidden columns */ - BoundedStartRegionIterator(int lowerBound, int upperBound, - boolean useCopy) + VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy) { - start = lowerBound; - end = upperBound; - + /* actually this implementation always uses a local copy but this may change in future */ try { - if (useCopy) + if (usecopy) { - // assume that if useCopy is false the calling code has locked - // hiddenColumns LOCK.readLock().lock(); } - if (hiddenColumns != null) + if (hiddenColumns != null && hiddenColumns.size() > 0) { - positions = new ArrayList<>(hiddenColumns.size()); + int blockStart = start; + int blockEnd = end; + int hiddenSoFar = 0; + int visSoFar = 0; - // navigate to start, keeping count of hidden columns + // iterate until a region begins within (start,end] int i = 0; - int hiddenSoFar = 0; while ((i < hiddenColumns.size()) - && (hiddenColumns.get(i)[0] < start + hiddenSoFar)) + && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar)) { - int[] region = hiddenColumns.get(i); - hiddenSoFar += region[1] - region[0] + 1; + hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0] + + 1; i++; } - // iterate from start to end, adding start positions of each - // hidden region. Positions are visible columns count, not absolute + blockStart += hiddenSoFar; // convert start to absolute position + blockEnd += hiddenSoFar; // convert end to absolute position + + // iterate from start to end, adding each visible region. Positions + // are + // absolute, and all hidden regions which overlap [start,end] are + // used. while (i < hiddenColumns.size() - && (hiddenColumns.get(i)[0] <= end + hiddenSoFar)) + && (hiddenColumns.get(i)[0] <= blockEnd)) { int[] region = hiddenColumns.get(i); - positions.add(region[0] - hiddenSoFar); + + // end position of this visible region is either just before the + // start of the next hidden region, or the absolute position of + // 'end', whichever is lowest + blockEnd = Math.min(blockEnd, region[0] - 1); + + vcontigs.add(new int[] { blockStart, blockEnd }); + + visSoFar += blockEnd - blockStart + 1; + + // next visible region starts after this hidden region + blockStart = region[1] + 1; + hiddenSoFar += region[1] - region[0] + 1; + + // reset blockEnd to absolute position of 'end', assuming we've now + // passed all hidden regions before end + blockEnd = end + hiddenSoFar; + i++; } + if (visSoFar < end - start + 1) + { + // the number of visible columns we've accounted for is less than + // the number specified by end-start; work out the end position of + // the last visible region + blockEnd = blockStart + end - start - visSoFar; + vcontigs.add(new int[] { blockStart, blockEnd }); + + // if the last visible region ends at the next hidden region, set + // endsAtHidden=true + if (i < hiddenColumns.size() + && hiddenColumns.get(i)[0] - 1 == blockEnd) + { + endsAtHidden = true; + } + } } else { - positions = new ArrayList<>(); + // there are no hidden columns, return a single visible contig + vcontigs.add(new int[] { start, end }); + endsAtHidden = false; } } finally { - if (useCopy) + if (usecopy) { LOCK.readLock().unlock(); } @@ -1671,15 +1606,20 @@ public class HiddenColumns @Override public boolean hasNext() { - return (currentPosition < positions.size()); + return (currentPosition < vcontigs.size()); } @Override - public Integer next() + public int[] next() { - int result = positions.get(currentPosition); + int[] result = vcontigs.get(currentPosition); currentPosition++; return result; } + + public boolean endsAtHidden() + { + return endsAtHidden; + } } }