ListResult (@NotNull FSRecordsImpl vfs, @NotNull List<? extends ChildInfo> newChildren, boolean isCaseSensitive) { ListResult newList = new ListResult(vfs, newChildren, parentId); // assume the list is sorted if (children.isEmpty()) return newList; List<? extends ChildInfo> oldChildren = children; // Both `newChildren` and `oldChildren` are sorted by id, but not `nameId`, so plain O(N) merging is not possible. // Instead, try to eliminate entries with the same id from both lists first (since they have the same `nameId`), // and compare the rest by (slower) `nameId`. // Typically, when `newChildren` contains 5K entries + a couple absent from `oldChildren`, and `oldChildren` contains 5K + a couple entries, // these maps will contain just a couple of entries absent from each other, not thousands. int size = Math.max(oldChildren.size(), newChildren.size()); Object2IntMap<CharSequence> nameToIndex = new Object2IntOpenCustomHashMap<>(size, FastUtilHashingStrategies.getCharSequenceStrategy(isCaseSensitive)); // distinguish between absence and the 0th index nameToIndex.defaultReturnValue(-1); boolean needToSortResult = false; List<ChildInfo> result = new ArrayList<>(size); for (int i = 0, j = 0; i < newChildren.size() || j < oldChildren.size(); ) { ChildInfo newChild = i == newChildren.size() ? null : newChildren.get(i); ChildInfo oldChild = j == oldChildren.size() ? null : oldChildren.get(j); int newId = newChild == null ? Integer.MAX_VALUE : newChild.getId(); int oldId = oldChild == null ? Integer.MAX_VALUE : oldChild.getId(); if (newId == oldId) { i++; j++; result.add(oldChild); } else if (newId < oldId) { // `newId` is absent from `oldChildren` CharSequence name = newChild.getName(); int dupI = nameToIndex.put(name, result.size()); if (dupI == -1) { result.add(newChild); } else { // aha, found entry in `result` with the same name. // That previous entry must come from the `oldChildren` // so replace just the name (the new name must have changed its case), leave id the same ChildInfo oldDup = result.get(dupI); int nameId = newChild.getNameId(); assert nameId > 0 : newChildren; ChildInfo replaced = ((ChildInfoImpl)oldDup).withNameId(nameId); result.set(dupI, replaced); needToSortResult = true; } i++; } else { // oldId is absent from `newChildren` CharSequence name = oldChild.getName(); int dupI = nameToIndex.put(name, result.size()); if (dupI == -1) { result.add(oldChild); } else { // Aha, found an entry in `result` with the same name. // That previous entry must come from the `newChildren`, // so leave the new name (which must have changed its case) and replace the ID. ChildInfo dup = result.get(dupI); int nameId = dup.getNameId(); assert nameId > 0 : this; ChildInfo replaced = ((ChildInfoImpl)dup).withId(oldChild.getId()); result.set(dupI, replaced); needToSortResult = true; } j++; } } if (needToSortResult) { result.sort(ChildInfo.BY_ID); } List<? extends ChildInfo> newRes = nameToIndex.isEmpty() ? newChildren : result; return new ListResult(parentModStamp, newRes, parentId); }