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
{
+ private static final int HASH_MULTIPLIER = 31;
+
private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
/*
{
if (copy.hiddenColumns != null)
{
- hiddenColumns = copy.copyHiddenRegionsToArrayList();
+ hiddenColumns = copy.copyHiddenRegionsToArrayList(0);
+ }
+ }
+ } finally
+ {
+ LOCK.writeLock().unlock();
+ }
+ }
+
+ /**
+ * 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
+ *
+ */
+ public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
+ {
+ try
+ {
+ LOCK.writeLock().lock();
+ if (copy != null)
+ {
+ hiddenColumns = new ArrayList<>();
+ Iterator<int[]> it = copy.getBoundedIterator(start, end, true);
+ 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 });
+ }
}
}
} finally
}
}
+ /**
+ * 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)
{
/**
* Use this method to determine the set of hiddenRegion start positions
+ * between absolute position <start> and absolute position <end>
*
- * @return list of column number in visible view where hidden regions start
+ * @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<Integer> findHiddenRegionPositions()
+ public List<Integer> findHiddenRegionPositions(int start, int end)
{
try
{
{
positions = new ArrayList<>(hiddenColumns.size());
- positions.add(hiddenColumns.get(0)[0]);
- for (int i = 1; i < hiddenColumns.size(); ++i)
+ // navigate to start, keeping count of hidden columns
+ int i = 0;
+ int hiddenSoFar = 0;
+ while ((i < hiddenColumns.size())
+ && (hiddenColumns.get(i)[0] < start))
{
+ int[] region = hiddenColumns.get(i);
+ hiddenSoFar += region[1] - region[0] + 1;
+ i++;
+ }
- int result = 0;
- if (hiddenColumns != null)
- {
- int index = 0;
- int gaps = 0;
- do
- {
- int[] region = hiddenColumns.get(index);
- gaps += region[1] + 1 - region[0];
- result = region[1] + 1;
- index++;
- } while (index <= i);
-
- result -= gaps;
- }
- positions.add(result);
+ // 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++;
}
}
else
}
}
- private ArrayList<int[]> copyHiddenRegionsToArrayList()
+ private ArrayList<int[]> copyHiddenRegionsToArrayList(int startIndex)
{
int size = 0;
if (hiddenColumns != null)
}
ArrayList<int[]> copy = new ArrayList<>(size);
- for (int i = 0, j = size; i < j; i++)
+ for (int i = startIndex, j = size; i < j; i++)
{
int[] rh;
int[] cp;
try
{
LOCK.readLock().lock();
- return copyHiddenRegionsToArrayList();
+ return copyHiddenRegionsToArrayList(0);
} finally
{
LOCK.readLock().unlock();
}
/**
- * propagate shift in alignment columns to column selection
- *
- * @param start
- * beginning of edit
- * @param left
- * shift in edit (+ve for removal, or -ve for inserts)
- */
- public List<int[]> compensateForEdit(int start, int change,
- ColumnSelection sel)
- {
- try
- {
- LOCK.writeLock().lock();
- List<int[]> deletedHiddenColumns = null;
-
- if (hiddenColumns != null)
- {
- deletedHiddenColumns = new ArrayList<>();
- int hSize = hiddenColumns.size();
- for (int i = 0; i < hSize; i++)
- {
- int[] region = hiddenColumns.get(i);
- if (region[0] > start && start + change > region[1])
- {
- deletedHiddenColumns.add(region);
-
- hiddenColumns.remove(i);
- i--;
- hSize--;
- continue;
- }
-
- if (region[0] > start)
- {
- region[0] -= change;
- region[1] -= change;
- }
-
- if (region[0] < 0)
- {
- region[0] = 0;
- }
-
- }
-
- this.revealHiddenColumns(0, sel);
- }
-
- return deletedHiddenColumns;
- } finally
- {
- LOCK.writeLock().unlock();
- }
- }
-
- /**
- * propagate shift in alignment columns to column selection special version of
- * compensateForEdit - allowing for edits within hidden regions
- *
- * @param start
- * beginning of edit
- * @param left
- * shift in edit (+ve for removal, or -ve for inserts)
- */
- public void compensateForDelEdits(int start, int change)
- {
- try
- {
- LOCK.writeLock().lock();
- if (hiddenColumns != null)
- {
- for (int i = 0; i < hiddenColumns.size(); i++)
- {
- int[] region = hiddenColumns.get(i);
- if (region[0] >= start)
- {
- region[0] -= change;
- }
- if (region[1] >= start)
- {
- region[1] -= change;
- }
- if (region[1] < region[0])
- {
- hiddenColumns.remove(i--);
- }
-
- if (region[0] < 0)
- {
- region[0] = 0;
- }
- if (region[1] < 0)
- {
- region[1] = 0;
- }
- }
- }
- } finally
- {
- LOCK.writeLock().unlock();
- }
- }
-
- /**
* return all visible segments between the given start and end boundaries
*
* @param start
LOCK.readLock().lock();
if (hiddenColumns != null && hiddenColumns.size() > 0)
{
- List<int[]> visiblecontigs = new ArrayList<>();
- List<int[]> regions = getHiddenRegions();
-
+ // 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[] region;
int hideStart;
int hideEnd;
+ int i = 0;
- for (int j = 0; vstart < end && j < regions.size(); j++)
+ for (int[] region : hiddenColumns)
{
- region = regions.get(j);
hideStart = region[0];
hideEnd = region[1];
+ // navigate to start
if (hideEnd < vstart)
{
continue;
}
if (hideStart > vstart)
{
- visiblecontigs.add(new int[] { vstart, hideStart - 1 });
+ 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)
{
- visiblecontigs.add(new int[] { vstart, end - 1 });
- }
- int[] vcontigs = new int[visiblecontigs.size() * 2];
- for (int i = 0, j = visiblecontigs.size(); i < j; i++)
- {
- int[] vc = visiblecontigs.get(i);
- visiblecontigs.set(i, null);
- vcontigs[i * 2] = vc[0];
- vcontigs[i * 2 + 1] = vc[1];
+ vcontigs[i * 2] = vstart;
+ vcontigs[i * 2 + 1] = end - 1;
+ i++;
}
- visiblecontigs.clear();
- return vcontigs;
+
+ // 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
{
for (int i = 0; i < iSize; i++)
{
StringBuffer visibleSeq = new StringBuffer();
- List<int[]> regions = getHiddenRegions();
int blockStart = start;
int blockEnd = end;
- int[] region;
int hideStart;
int hideEnd;
- for (int j = 0; j < regions.size(); j++)
+ for (int[] region : hiddenColumns)
{
- region = regions.get(j);
hideStart = region[0];
hideEnd = region[1];
// boundaries
List<int[]> regions = getHiddenRegions();
int spos = fpos;
- int lastvispos = -1;
int rcount = 0;
int hideStart = seq.getLength();
int hideEnd = -1;
start = p;
foundStart = true;
}
- lastvispos = p;
lpos = spos;
}
// look for next sequence position
// then mangle the alignmentAnnotation annotation array
Vector<Annotation[]> annels = new Vector<>();
Annotation[] els = null;
- List<int[]> regions = getHiddenRegions();
int blockStart = start;
int blockEnd = end;
- int[] region;
int hideStart;
int hideEnd;
int w = 0;
- for (int j = 0; j < regions.size(); j++)
+ for (int[] region : hiddenColumns)
{
- region = regions.get(j);
hideStart = region[0];
hideEnd = region[1];
break;
}
- annels.addElement(els = new Annotation[blockEnd - blockStart]);
+ els = new Annotation[blockEnd - blockStart];
+ annels.addElement(els);
System.arraycopy(alignmentAnnotation.annotations, blockStart, els,
0, els.length);
w += els.length;
if (end > blockStart)
{
- annels.addElement(els = new Annotation[end - blockStart + 1]);
+ els = new Annotation[end - blockStart + 1];
+ annels.addElement(els);
if ((els.length
+ blockStart) <= alignmentAnnotation.annotations.length)
{
// but where each hidden column region is shifted backwards by the number of
// preceding visible gaps
// update hidden columns at the same time
- ArrayList<int[]> regions = getHiddenColumnsCopy();
+ Iterator<int[]> regions = iterator();
ArrayList<int[]> newhidden = new ArrayList<>();
int numGapsBefore = 0;
int gapPosition = 0;
- for (int[] region : regions)
+ while (regions.hasNext())
{
// 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])
{
gapPosition++;
{
for (int[] hidden : hiddenColumns)
{
- hashCode = 31 * hashCode + hidden[0];
- hashCode = 31 * hashCode + hidden[1];
+ hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
+ hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
}
}
return hashCode;
}
}
+ public Iterator<int[]> iterator()
+ {
+ if (hiddenColumns != null)
+ {
+ int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
+ return new BoundedHiddenColsIterator(0, last, true);
+ }
+ else
+ {
+ return new BoundedHiddenColsIterator(0, 0, true);
+ }
+ }
+
+ public Iterator<int[]> getBoundedIterator(int start, int end,
+ boolean useCopy)
+ {
+ return new BoundedHiddenColsIterator(start, end, useCopy);
+ }
+
+ public Iterator<Integer> getBoundedStartIterator(int start, int end,
+ boolean useCopy)
+ {
+ return new BoundedStartRegionIterator(start, end, useCopy);
+ }
+
+ /**
+ * An iterator which iterates over hidden column regions in a range.
+ *
+ * @author kmourao
+ *
+ */
+
+
+ class BoundedHiddenColsIterator implements Iterator<int[]>
+ {
+
+ 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<int[]> 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 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)
+ {
+ 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();
+ }
+ }
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ return (localHidden != null)
+ && (currentPosition < localHidden.size());
+ }
+
+ @Override
+ public int[] next()
+ {
+ currentRegion = localHidden.get(currentPosition);
+ currentPosition++;
+ return currentRegion;
+ }
+ }
+
+ class BoundedStartRegionIterator implements Iterator<Integer>
+ {
+
+ 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<Integer> positions = null;
+
+ /**
+ * Construct an iterator over hiddenColums bounded at
+ * [lowerBound,upperBound]
+ *
+ * @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)
+ */
+ BoundedStartRegionIterator(int lowerBound, int upperBound,
+ boolean useCopy)
+ {
+ start = lowerBound;
+ end = upperBound;
+
+ try
+ {
+ if (useCopy)
+ {
+ // assume that if useCopy is false the calling code has locked
+ // hiddenColumns
+ LOCK.readLock().lock();
+ }
+
+ if (hiddenColumns != null)
+ {
+ positions = new ArrayList<>(hiddenColumns.size());
+
+ // navigate to start, keeping count of hidden columns
+ int i = 0;
+ int hiddenSoFar = 0;
+ while ((i < hiddenColumns.size())
+ && (hiddenColumns.get(i)[0] < start + hiddenSoFar))
+ {
+ 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 + hiddenSoFar))
+ {
+ int[] region = hiddenColumns.get(i);
+ positions.add(region[0] - hiddenSoFar);
+ hiddenSoFar += region[1] - region[0] + 1;
+ i++;
+ }
+ }
+ else
+ {
+ positions = new ArrayList<>();
+ }
+ } finally
+ {
+ if (useCopy)
+ {
+ LOCK.readLock().unlock();
+ }
+ }
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ return (currentPosition < positions.size());
+ }
+
+ @Override
+ public Integer next()
+ {
+ int result = positions.get(currentPosition);
+ currentPosition++;
+ return result;
+ }
+ }
}