src/NetStandard/Collections/Algorithms/src/Algorithms/Modifications/AfterDeviationDeferredCollectionModifications.cs
/// <summary>
/// The algorithm creates modifications that can transform one collection into another collection.
/// The collection modifications may be used to transform <paramref name="leftItems"/>.
/// The collection is not assumed to be in any order.
/// Sorted duplications are allowed.
/// </summary>
/// <typeparam name="TLeftItem">The type of left items.</typeparam>
/// <typeparam name="TRightItem">The type of right items.</typeparam>
/// <typeparam name="TComparablePart">The type of the comparable part of left item and right item.</typeparam>
/// <param name="leftItems">The collection you want to have transformed.</param>
/// <param name="getComparablePartOfLeftItem">The part of left item that is comparable with part of right item.</param>
/// <param name="rightItems">The collection in which <paramref name="leftItems"/> could be transformed.</param>
/// <param name="getComparablePartOfRightItem">The part of right item that is comparable with part of left item.</param>
/// <param name="equalityComparer"></param>
/// <returns>For <paramref name="leftItems"/> the collection modifications between <paramref name="leftItems"/> and <paramref name="rightItems"/></returns>
The algorithm creates modifications that can transform one collection into another collection.
The collection modifications may be used to transform .
The collection is not assumed to be in any order.
Sorted duplications are allowed.
The algorithm creates modifications that can transform one collection into another collection . The collection modifications may be used to transform . The collection is not assumed to be in any order . Sorted duplications are allowed .
public static IEnumerable<CollectionModification<TRightItem, TLeftItem>> YieldCollectionModifications<TLeftItem, TRightItem, TComparablePart>(
            IEnumerable<TLeftItem> leftItems,
            Func<TLeftItem, TComparablePart> getComparablePartOfLeftItem,
            IEnumerable<TRightItem> rightItems,
            Func<TRightItem, TComparablePart> getComparablePartOfRightItem,
            IEqualityComparer<TComparablePart> equalityComparer)
        {
            var comparablePartEqualityComparer = new CommonValueContainerEqualityComparer<TComparablePart>(equalityComparer);
            var leftItemEnumerator = leftItems.GetEnumerator();
            var rightItemEnumerator = rightItems.GetEnumerator();
            var hasLeftItem = true;
            var hasRightItem = true;
            var earlyIterationCount = 0;
            var earlyLeftValueIndex = 0;
            var earlyRightValueIndex = 0;
            var earlyIterationModifications = new List<CollectionModification<TRightItem, TLeftItem>>();
            var leftItemIndexShifter = new ObjectEventDispatcher<CollectionModification<TRightItem, TLeftItem>>();
            ILinkedBucketList<CommonValueContainer<TComparablePart>, LeftItemContainer<TLeftItem, TRightItem, TComparablePart>> lateLeftItemContainers = new LinkedBucketList<CommonValueContainer<TComparablePart>, LeftItemContainer<TLeftItem, TRightItem, TComparablePart>>(comparablePartEqualityComparer);
            var lateRightItemContainers = new LinkedBucketList<CommonValueContainer<TComparablePart>, RightItemContainer<TLeftItem, TRightItem, TComparablePart>>(comparablePartEqualityComparer);
            var areEarlyIterationValuesEqual = true;
            while ((hasLeftItem && (hasLeftItem = leftItemEnumerator.MoveNext()))
                | (hasRightItem && (hasRightItem = rightItemEnumerator.MoveNext()))) {
                if (!(hasLeftItem || hasRightItem)) {
                    break;
                }
                var leftItem = hasLeftItem ? leftItemEnumerator.Current : default;
                var leftCommonValue = hasLeftItem ? getComparablePartOfLeftItem(leftItem!) : default;
                var rightItem = hasRightItem ? rightItemEnumerator.Current : default;
                var rightCommonValue = hasRightItem ? getComparablePartOfRightItem(rightItem!) : default;
                CollectionModification<TRightItem, TLeftItem>? syncedIterationModification = default;
                LeftItemContainer<TLeftItem, TRightItem, TComparablePart> createLeftItemContainer()
                    => new LeftItemContainer<TLeftItem, TRightItem, TComparablePart>(leftItem, leftCommonValue, earlyLeftValueIndex, leftItemIndexShifter);
                RightItemContainer<TLeftItem, TRightItem, TComparablePart> createRightItemContainer()
                    => new RightItemContainer<TLeftItem, TRightItem, TComparablePart>(rightItem, rightCommonValue, earlyRightValueIndex);
                if (hasLeftItem && hasRightItem) {
                    var leftItemContainer = createLeftItemContainer();
                    var rightItemContainer = createRightItemContainer();
                    if (equalityComparer.Equals(leftCommonValue!, rightCommonValue!)
                        && ((lateRightItemContainers.Buckets.TryGetValue(rightItemContainer).Item2?.All(x => x.CachedLeftItem != null)) ?? false)) {
                        syncedIterationModification = CollectionModification.ForReplace(earlyLeftValueIndex, leftItem!,  rightItem!);
                        rightItemContainer.CachedLeftItem = leftItemContainer;
                        lateRightItemContainers.AddLast(rightItemContainer);
                    } else {
                        lateLeftItemContainers.AddLast(leftItemContainer);
                        lateRightItemContainers.AddLast(rightItemContainer);
                        areEarlyIterationValuesEqual = false;
                    }
                    earlyIterationCount++;
                    earlyLeftValueIndex = earlyIterationCount;
                    earlyRightValueIndex = earlyIterationCount;
                } else if (hasLeftItem) {
                    if (areEarlyIterationValuesEqual) {
                        var newLeftValueIndex = earlyLeftValueIndex - (earlyLeftValueIndex - earlyRightValueIndex);
                        syncedIterationModification = CollectionModification.ForRemove<TRightItem, TLeftItem>(newLeftValueIndex, leftItem!);
                    } else {
                        lateLeftItemContainers.AddLast(createLeftItemContainer());
                    }
                    earlyLeftValueIndex++;
                } else {
                    if (areEarlyIterationValuesEqual) {
                        syncedIterationModification = CollectionModification.ForAdd<TRightItem, TLeftItem>(earlyRightValueIndex, rightItem!);
                    } else {
                        lateRightItemContainers.AddLast(createRightItemContainer());
                    }
                    earlyRightValueIndex++;
                }
                if (syncedIterationModification != null) {
                    earlyIterationModifications.Add(syncedIterationModification);
                }
            }
            foreach (var modification in earlyIterationModifications) {
                yield return modification;
            }
            if (areEarlyIterationValuesEqual) {
                yield break;
            }
            foreach (var rightItemContainer in lateRightItemContainers) {
                var rightValueIndex = rightItemContainer.ShiftedIndex;
                var rightValue = rightItemContainer.CommonValue;
                var hasCachedLeftItem = rightItemContainer.CachedLeftItem != null;
                LeftItemContainer<TLeftItem, TRightItem, TComparablePart>? foundLeftItemContainer;
                if (hasCachedLeftItem) {
                    foundLeftItemContainer = rightItemContainer.CachedLeftItem;
                } else {
                    if (lateLeftItemContainers.TryGetBucket(CommonValueContainer<TComparablePart>.CreateEqualComparableItem(rightValue), out var bucket) && bucket.Count != 0) {
                        var firstNode = bucket.First!;
                        foundLeftItemContainer = firstNode.Value;
                        lateLeftItemContainers.Remove(firstNode);
                    } else {
                        foundLeftItemContainer = null;
                    }
                }
                var rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount = rightValueIndex;
                if (foundLeftItemContainer == null) {
                    var modification = CollectionModification.ForAdd<TRightItem, TLeftItem>(rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount, rightItemContainer.RightItem!);
                    yield return modification;
                    leftItemIndexShifter.DispatchObject(modification);
                } else {
                    var foundLeftIndex = foundLeftItemContainer.ShiftedIndex;
                    if (foundLeftIndex != rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount) {
                        if (foundLeftIndex < rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount) {
                            continue;
                        }
                        var modification = CollectionModification.ForMove<TRightItem, TLeftItem>(foundLeftIndex, foundLeftItemContainer.LeftItem!, rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount);
                        yield return modification;
                        leftItemIndexShifter.DispatchObject(modification);
                    }
                    if (!hasCachedLeftItem) {
                        yield return CollectionModification.ForReplace(rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount, foundLeftItemContainer.LeftItem!, rightItemContainer.RightItem!);
                    }
                }
            }
            if (!(lateLeftItemContainers.Last is null)) {
                foreach (var leftValueIndexPair in lateLeftItemContainers.Last.ListPart.GetEnumerableButReversed()) {
                    yield return CollectionModification.ForRemove<TRightItem, TLeftItem>(leftValueIndexPair.Value.ShiftedIndex, leftValueIndexPair.Value.LeftItem!);
                }
            }
        }
public static IEnumerable < CollectionModification < TRightItem , TLeftItem > > YieldCollectionModifications < TLeftItem , TRightItem , TComparablePart > ( IEnumerable < TLeftItem > leftItems , Func < TLeftItem , TComparablePart > getComparablePartOfLeftItem , IEnumerable < TRightItem > rightItems , Func < TRightItem , TComparablePart > getComparablePartOfRightItem , IEqualityComparer < TComparablePart > equalityComparer ) { var comparablePartEqualityComparer = new CommonValueContainerEqualityComparer < TComparablePart > ( equalityComparer ) ; var leftItemEnumerator = leftItems . GetEnumerator ( ) ; var rightItemEnumerator = rightItems . GetEnumerator ( ) ; var hasLeftItem = true ; var hasRightItem = true ; var earlyIterationCount = 0 ; var earlyLeftValueIndex = 0 ; var earlyRightValueIndex = 0 ; var earlyIterationModifications = new List < CollectionModification < TRightItem , TLeftItem > > ( ) ; var leftItemIndexShifter = new ObjectEventDispatcher < CollectionModification < TRightItem , TLeftItem > > ( ) ; ILinkedBucketList < CommonValueContainer < TComparablePart > , LeftItemContainer < TLeftItem , TRightItem , TComparablePart > > lateLeftItemContainers = new LinkedBucketList < CommonValueContainer < TComparablePart > , LeftItemContainer < TLeftItem , TRightItem , TComparablePart > > ( comparablePartEqualityComparer ) ; var lateRightItemContainers = new LinkedBucketList < CommonValueContainer < TComparablePart > , RightItemContainer < TLeftItem , TRightItem , TComparablePart > > ( comparablePartEqualityComparer ) ; var areEarlyIterationValuesEqual = true ; while ( ( hasLeftItem && ( hasLeftItem = leftItemEnumerator . MoveNext ( ) ) ) | ( hasRightItem && ( hasRightItem = rightItemEnumerator . MoveNext ( ) ) ) ) { if ( ! ( hasLeftItem || hasRightItem ) ) { break ; } var leftItem = hasLeftItem ? leftItemEnumerator . Current : default ; var leftCommonValue = hasLeftItem ? getComparablePartOfLeftItem ( leftItem ! ) : default ; var rightItem = hasRightItem ? rightItemEnumerator . Current : default ; var rightCommonValue = hasRightItem ? getComparablePartOfRightItem ( rightItem ! ) : default ; CollectionModification < TRightItem , TLeftItem > ? syncedIterationModification = default ; LeftItemContainer < TLeftItem , TRightItem , TComparablePart > createLeftItemContainer ( ) => new LeftItemContainer < TLeftItem , TRightItem , TComparablePart > ( leftItem , leftCommonValue , earlyLeftValueIndex , leftItemIndexShifter ) ; RightItemContainer < TLeftItem , TRightItem , TComparablePart > createRightItemContainer ( ) => new RightItemContainer < TLeftItem , TRightItem , TComparablePart > ( rightItem , rightCommonValue , earlyRightValueIndex ) ; if ( hasLeftItem && hasRightItem ) { var leftItemContainer = createLeftItemContainer ( ) ; var rightItemContainer = createRightItemContainer ( ) ; if ( equalityComparer . Equals ( leftCommonValue ! , rightCommonValue ! ) && ( ( lateRightItemContainers . Buckets . TryGetValue ( rightItemContainer ) . Item2 ? . All ( x => x . CachedLeftItem != null ) ) ?? false ) ) { syncedIterationModification = CollectionModification . ForReplace ( earlyLeftValueIndex , leftItem ! , rightItem ! ) ; rightItemContainer . CachedLeftItem = leftItemContainer ; lateRightItemContainers . AddLast ( rightItemContainer ) ; } else { lateLeftItemContainers . AddLast ( leftItemContainer ) ; lateRightItemContainers . AddLast ( rightItemContainer ) ; areEarlyIterationValuesEqual = false ; } earlyIterationCount ++ ; earlyLeftValueIndex = earlyIterationCount ; earlyRightValueIndex = earlyIterationCount ; } else if ( hasLeftItem ) { if ( areEarlyIterationValuesEqual ) { var newLeftValueIndex = earlyLeftValueIndex - ( earlyLeftValueIndex - earlyRightValueIndex ) ; syncedIterationModification = CollectionModification . ForRemove < TRightItem , TLeftItem > ( newLeftValueIndex , leftItem ! ) ; } else { lateLeftItemContainers . AddLast ( createLeftItemContainer ( ) ) ; } earlyLeftValueIndex ++ ; } else { if ( areEarlyIterationValuesEqual ) { syncedIterationModification = CollectionModification . ForAdd < TRightItem , TLeftItem > ( earlyRightValueIndex , rightItem ! ) ; } else { lateRightItemContainers . AddLast ( createRightItemContainer ( ) ) ; } earlyRightValueIndex ++ ; } if ( syncedIterationModification != null ) { earlyIterationModifications . Add ( syncedIterationModification ) ; } } foreach ( var modification in earlyIterationModifications ) { yield return modification ; } if ( areEarlyIterationValuesEqual ) { yield break ; } foreach ( var rightItemContainer in lateRightItemContainers ) { var rightValueIndex = rightItemContainer . ShiftedIndex ; var rightValue = rightItemContainer . CommonValue ; var hasCachedLeftItem = rightItemContainer . CachedLeftItem != null ; LeftItemContainer < TLeftItem , TRightItem , TComparablePart > ? foundLeftItemContainer ; if ( hasCachedLeftItem ) { foundLeftItemContainer = rightItemContainer . CachedLeftItem ; } else { if ( lateLeftItemContainers . TryGetBucket ( CommonValueContainer < TComparablePart > . CreateEqualComparableItem ( rightValue ) , out var bucket ) && bucket . Count != 0 ) { var firstNode = bucket . First ! ; foundLeftItemContainer = firstNode . Value ; lateLeftItemContainers . Remove ( firstNode ) ; } else { foundLeftItemContainer = null ; } } var rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount = rightValueIndex ; if ( foundLeftItemContainer == null ) { var modification = CollectionModification . ForAdd < TRightItem , TLeftItem > ( rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount , rightItemContainer . RightItem ! ) ; yield return modification ; leftItemIndexShifter . DispatchObject ( modification ) ; } else { var foundLeftIndex = foundLeftItemContainer . ShiftedIndex ; if ( foundLeftIndex != rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount ) { if ( foundLeftIndex < rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount ) { continue ; } var modification = CollectionModification . ForMove < TRightItem , TLeftItem > ( foundLeftIndex , foundLeftItemContainer . LeftItem ! , rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount ) ; yield return modification ; leftItemIndexShifter . DispatchObject ( modification ) ; } if ( ! hasCachedLeftItem ) { yield return CollectionModification . ForReplace ( rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount , foundLeftItemContainer . LeftItem ! , rightItemContainer . RightItem ! ) ; } } } if ( ! ( lateLeftItemContainers . Last is null ) ) { foreach ( var leftValueIndexPair in lateLeftItemContainers . Last . ListPart . GetEnumerableButReversed ( ) ) { yield return CollectionModification . ForRemove < TRightItem , TLeftItem > ( leftValueIndexPair . Value . ShiftedIndex , leftValueIndexPair . Value . LeftItem ! ) ; } } }
The algorithm creates modifications that can transform one collection into another collection.
The algorithm creates modifications that can transform one collection into another collection .
// It will only count until a left or right item is not found // Early modifications that are synchronized or are synchronized but having // removing or adding modifications at the end can be returned all at once. // This list represents the cache for it. /* Cache left and right items */ // Cancel if not a left and right value is available // Check if: "Both items are equal" => (true supports [1,..] <-> [1,..]) //       AND "Left and right buckets are empty"  (false supports [1,1,2,..] <-> [2,1,..]) /*earlyRightValueIndex,*/ // We only move forward to back, but never back to forward, so this item, even when  // it's now well positioned, needs to be checked, if it is still well positioned. //var rightItemContainer = createRightItemContainer(); // We take use of a cache, so that we don't have to search for left item and don't replace it twice // When early iterations are synchronized, then we always need to delete // the left value at index of the greatest right value index plus one // Exit only if both lists were synchronized from early on // This index represents the current index of the right value collection. // Indexes can be equal, when not processed items are before the moved item // Here we deny the forward to backward move, so we have to process already replaced items,  // and move them forward, because they could be now behind those skipped items, but need to // be moved before them // .. CollectionModification.ForMove(foundLeftIndex, foundLeftItemContainer.LeftItem, rightValueIndexWithNotProcessedItemsBeforeRightValueIndexCount, rightItemContainer.RightItem); // We move the old existing item // Then we replace the left item by moved item at the destination index of the moved item // We remove all left left-value-index-pairs, because they did not match any condition above and have to be removed in REVERSED order
For  the collection modifications between  and
For the collection modifications between and
leftItems
IEnumerable<TLeftItem>
The collection you want to have transformed.
The collection you want to have transformed .
getComparablePartOfLeftItem
Func<TLeftItem, TComparablePart>
The part of left item that is comparable with part of right item.
The part of left item that is comparable with part of right item .
rightItems
IEnumerable<TRightItem>
The collection in which  could be transformed.
The collection in which could be transformed .
getComparablePartOfRightItem
Func<TRightItem, TComparablePart>
The part of right item that is comparable with part of left item.
The part of right item that is comparable with part of left item .
equalityComparer
IEqualityComparer<TComparablePart>
None
typeparam
The type of left items.
The type of left items .
typeparam
The type of right items.
The type of right items .
typeparam
The type of the comparable part of left item and right item.
The type of the comparable part of left item and right item .