IntervalNode<T> (@Nullable IntervalNode<T> root, @NotNull TextRange interval, int modCountBefore, int deltaUpToRootExclusive) { if (root == null) { return null; } assert root.isValid(); int delta = deltaUpToRootExclusive + root.delta; if (interval.getStartOffset() > maxEndOf(root, deltaUpToRootExclusive)) { return null; // right of the rightmost interval in the subtree } IntervalNode<T> inLeft = findMinOverlappingWith(root.getLeft(), interval, modCountBefore, delta); if (inLeft != null) return inLeft; int myStartOffset = root.intervalStart() + delta; int myEndOffset = root.intervalEnd() + delta; boolean overlaps = Math.max(myStartOffset, interval.getStartOffset()) <= Math.min(myEndOffset, interval.getEndOffset()); if (overlaps) return root; if (getModCount() != modCountBefore) throw new ConcurrentModificationException(); if (interval.getEndOffset() < myStartOffset) { return null; // left of the root, cant be in the right subtree } return findMinOverlappingWith(root.getRight(), interval, modCountBefore, delta); }