MergeFragment (int leftChild, int rightChild, int parent) { MergeFragment fragment = new MergeFragment(parent, leftChild, rightChild); int leftLi = myGraphLayout.getLayoutIndex(leftChild); int rightLi = myGraphLayout.getLayoutIndex(rightChild); int rowsCount = 1; int blockSize = 1; PriorityQueue<GraphEdge> queue = new PriorityQueue<>(MAX_BLOCK_SIZE, new GraphEdgeComparator()); queue.addAll(myLinearBekGraph.getAdjacentEdges(rightChild, EdgeFilter.NORMAL_DOWN)); @Nullable Set<Integer> magicSet = null; while (!queue.isEmpty()) { GraphEdge nextEdge = queue.poll(); Integer next = nextEdge.getDownNodeIndex(); Integer upNodeIndex = nextEdge.getUpNodeIndex(); assert upNodeIndex != null; // can not happen if (next == null) { fragment.addTail(upNodeIndex); continue; // allow very long edges down } if (next == leftChild) { // found first child fragment.addTail(upNodeIndex); fragment.setMergeWithOldCommit(true); } else if (next == rightChild + rowsCount) { // all is fine, continuing rowsCount++; blockSize++; queue.addAll(myLinearBekGraph.getAdjacentEdges(next, EdgeFilter.NORMAL_DOWN)); fragment.addBody(upNodeIndex); } else if (next > rightChild + rowsCount && next < leftChild) { rowsCount = next - rightChild + 1; blockSize++; queue.addAll(myLinearBekGraph.getAdjacentEdges(next, EdgeFilter.NORMAL_DOWN)); fragment.addBody(upNodeIndex); } else if (next > leftChild) { int li = myGraphLayout.getLayoutIndex(next); if (leftLi > rightLi && !fragment.isMergeWithOldCommit()) { if (next > leftChild + MAGIC_SET_SIZE) { return null; } if (magicSet == null) { magicSet = calculateMagicSet(leftChild); } if (magicSet.contains(next)) { fragment.addTailEdge(upNodeIndex, next); } else { return null; } } else { if ((li > leftLi && li < rightLi) || (li == leftLi)) { fragment.addTailEdge(upNodeIndex, next); } else { if (li >= rightLi) { return null; } else { if (next > leftChild + MAGIC_SET_SIZE) { if (!fragment.hasTailEdge(upNodeIndex) && !fragment.isBody(upNodeIndex)) return null; } else { if (magicSet == null) { magicSet = calculateMagicSet(leftChild); } if (magicSet.contains(next)) { fragment.addTailEdge(upNodeIndex, next); } else { return null; } } } } } } if (blockSize >= MAX_BLOCK_SIZE) { return null; } } if (fragment.getTails().isEmpty()) { return null; // this can happen if we ran into initial import } return fragment; }