*/
private EventBlock findEventBlock(
final ReadAnchoring anchoring, final boolean backwards,
final MultiDeBruijnVertex leftVertex, final MultiDeBruijnVertex rightVertex) {
MultiDeBruijnVertex currentVertex = backwards ? rightVertex : leftVertex;
boolean foundEvent = false;
final CountSet pathSizes = new CountSet(10); // typically more than enough.
pathSizes.setTo(0);
// Map between reference vertices where there is some expected open alternative path rejoining and the
// predicted length of paths rejoining at that point counting from the beginning of the block.
final Map<MultiDeBruijnVertex, CountSet> expectedAlternativePathRejoins = new HashMap<>(4);
// Keeps record of possible left-clipping veritces; those that are located before any event path furcation
// has been found. The value indicates the blockLength at the time we traverse that node.
final Deque<Pair<MultiDeBruijnVertex, Integer>> possibleClippingPoints = new LinkedList<>();
// We keep the distance from the beggining of the block (leftVertex).
int blockLength = 0;
while (currentVertex != null) {
int openingDegree = backwards ? graph.outDegreeOf(currentVertex) : graph.inDegreeOf(currentVertex);
if (openingDegree > 1) {
final CountSet joiningPathLengths = expectedAlternativePathRejoins.remove(currentVertex);
if (joiningPathLengths != null)
pathSizes.addAll(joiningPathLengths);
}
final boolean isValidBlockEnd = isValidBlockEnd(anchoring, currentVertex, expectedAlternativePathRejoins);
if (foundEvent && isValidBlockEnd) // !gotcha we found a valid block end.
break;
else if (!foundEvent && isValidBlockEnd) // if no event has been found yet, still is a good clipping point.
possibleClippingPoints.addLast(new Pair<>(currentVertex, blockLength));
// We reached the end:
if (currentVertex == (backwards ? leftVertex : rightVertex))
break;
// process next vertices, the next one on the reference and also possible start of alternative paths,
// updates traversal structures accordingly.
currentVertex = advanceOnReferencePath(anchoring, backwards, currentVertex, pathSizes, expectedAlternativePathRejoins);
foundEvent |= expectedAlternativePathRejoins.size() > 0;
pathSizes.incAll(1);
blockLength++;
}
// we have not found an event, thus there is no block to report:
if (!foundEvent)
return null;
// We try to clip off as much as we can from the beginning of the block before any event, but at least
// leaving enough block length to meet the shortest path unless all paths have the same size (SNPs only)
final int maxClipping = pathSizes.size() <= 1 ? blockLength : pathSizes.min();
MultiDeBruijnVertex clippingEnd = backwards ? anchoring.rightAnchorVertex : anchoring.leftAnchorVertex;
while (!possibleClippingPoints.isEmpty()) {
final Pair<MultiDeBruijnVertex, Integer> candidate = possibleClippingPoints.removeLast();
if (candidate.getSecond() <= maxClipping) {
clippingEnd = candidate.getFirst();
break;