IntervalNode<T> (@NotNull IntervalNode<T> root) { assert root.isValid() : root; int delta = deltaUpToRootExclusive + root.delta; int myMaxEnd = maxEndOf(root, deltaUpToRootExclusive); if (startOffset > myMaxEnd) return null; // tree changed // try to go right down IntervalNode<T> right = root.getRight(); if (right != null) { int rightMaxEnd = maxEndOf(right, delta); if (startOffset <= rightMaxEnd) { int rightDelta = delta + right.delta; IntervalNode<T> left; while ((left = right.getLeft()) != null && startOffset <= maxEndOf(left, rightDelta)) { right = left; rightDelta += right.delta; } deltaUpToRootExclusive = rightDelta - right.delta; return right; } } // go up while (true) { IntervalNode<T> parent = root.getParent(); if (parent == null) return null; if (parent.intervalStart() + deltaUpToRootExclusive > endOffset) return null; // can't move right deltaUpToRootExclusive -= parent.delta; if (parent.getLeft() == root) { return parent; } root = parent; } }