CompareResult (@NotNull OT oldNode, @NotNull NT newNode, int level, @NotNull DiffTreeChangeBuilder<? super OT, ? super NT> consumer) { if (level == myNewChildrenLists.size()) { myNewChildrenLists.add(new Ref<>()); myOldChildrenLists.add(new Ref<>()); } Ref<OT[]> oldChildrenR = myOldChildrenLists.get(level); int oldChildrenSize = myOldTree.getChildren(oldNode, oldChildrenR); OT[] oldChildren = oldChildrenR.get(); Ref<NT[]> newChildrenR = myNewChildrenLists.get(level); int newChildrenSize = myNewTree.getChildren(newNode, newChildrenR); NT[] newChildren = newChildrenR.get(); CompareResult result; if (Math.abs(oldChildrenSize - newChildrenSize) > CHANGE_PARENT_VERSUS_CHILDREN_THRESHOLD) { consumer.nodeReplaced(oldNode, newNode); result = CompareResult.NOT_EQUAL; } else if (oldChildrenSize == 0 && newChildrenSize == 0) { if (!myComparator.typesEqual(oldNode, newNode) || !myComparator.hashCodesEqual(oldNode, newNode)) { consumer.nodeReplaced(oldNode, newNode); result = CompareResult.NOT_EQUAL; } else { result = CompareResult.EQUAL; } } else { int minSize = Math.min(oldChildrenSize, newChildrenSize); int suffixLength = match(oldChildren, oldChildrenSize - 1, newChildren, newChildrenSize - 1, level, -1, minSize); // for equal size old and new children we have to compare one element less because it was already checked in (unsuccessful) suffix match int maxPrefixLength = minSize - suffixLength - (oldChildrenSize == newChildrenSize && suffixLength < minSize ? 1 : 0); int prefixLength = match(oldChildren, 0, newChildren, 0, level, 1, maxPrefixLength); if (oldChildrenSize == newChildrenSize && suffixLength + prefixLength == oldChildrenSize) { result = CompareResult.EQUAL; } else if (consumer == emptyConsumer()) { result = CompareResult.NOT_EQUAL; } else { int oldIndex = prefixLength; int newIndex = prefixLength; while (oldIndex < oldChildrenSize - suffixLength || newIndex < newChildrenSize - suffixLength) { ThreeElementMatchResult vicinityMatch = matchNext3Children(oldChildren, newChildren, oldIndex, newIndex, oldChildrenSize - suffixLength, newChildrenSize - suffixLength); if (vicinityMatch.hasStartMatch()) { if (vicinityMatch == ThreeElementMatchResult.DRILL_DOWN_START_MATCH) { build(oldChildren[oldIndex], newChildren[newIndex], level + 1, consumer); } else if (vicinityMatch == ThreeElementMatchResult.REPLACE_START) { consumer.nodeReplaced(oldChildren[oldIndex], newChildren[newIndex]); } oldIndex++; newIndex++; } else if (vicinityMatch != ThreeElementMatchResult.NO_MATCH) { for (int i = vicinityMatch.skipOldCount() - 1; i >= 0; i--) { consumer.nodeDeleted(oldNode, oldChildren[oldIndex]); oldIndex++; } for (int i = vicinityMatch.skipNewCount() - 1; i >= 0; i--) { consumer.nodeInserted(oldNode, newChildren[newIndex], newIndex); newIndex++; } } else { // last resort: maybe the last elements are more similar? int suffixMatch = matchLastChildren(level, consumer, oldChildrenSize - suffixLength, oldChildren, oldIndex, newChildrenSize - suffixLength, newChildren, newIndex); if (suffixMatch > 0) { suffixLength += suffixMatch; } else { consumer.nodeReplaced(oldChildren[oldIndex], newChildren[newIndex]); oldIndex++; newIndex++; } } } result = CompareResult.NOT_EQUAL; } } myOldTree.disposeChildren(oldChildren, oldChildrenSize); myNewTree.disposeChildren(newChildren, newChildrenSize); return result; }