using System;

​

using System.Collections;

using System.Collections.Generic;

​

using System.Linq;

using System.Linq.Expressions;

​

public record Operation(string Url);

public record Add(string Url): Operation(Url);

public record Remove(string Url): Operation(Url);               

​

​

public class Program

{

    public static void Main()

    {

        var test1e = new[] { "a", "b", "c" };

        var test1d = new[] { "a", "b", "c" };           // same => noop

​

        var ops1g = ReconcileImagesGeroge(test1e, test1d);

        Test("Test 1 - George", test1e, test1d, ops1g.ToList());

​

        var ops1o = ReconcileImagesOndrej(test1e, test1d);

        Test("Test 1 - Ondrej", test1e, test1d, ops1o.ToList());

​

        var test2e = new[] { "a", "b", "c" };

        var test2d = new[] { "a", "c" };                // b deleted

​

        var ops2g = ReconcileImagesGeroge(test2e, test2d);

        Test("Test 2 - George", test2e, test2d, ops2g.ToList());

​

        var ops2o = ReconcileImagesOndrej(test2e, test2d);

        Test("Test 2 - Ondrej", test2e, test2d, ops2o.ToList());

​

        var test3e = new[] { "a", "b", "c" };

        var test3d = new[] { "c", "a", "b", };          // last moved to first

​

        var ops3g = ReconcileImagesGeroge(test3e, test3d);

        Test("Test 3 - George", test1e, test3d, ops3g.ToList());

​

        var ops3o = ReconcileImagesOndrej(test3e, test3d);

        Test("Test 3 - Ondrej", test1e, test3d, ops3o.ToList());

​

        var test4e = new[] { "a", "b", "c" };

        var test4d = new[] { "a", "b", "c", "d" };      // one added

​

        var ops4g = ReconcileImagesGeroge(test4e, test4d);

        Test("Test 4 - George", test4e, test4d, ops4g.ToList());

​

        var ops4o = ReconcileImagesOndrej(test4e, test4d);

        Test("Test 4 - Ondrej", test4e, test4d, ops4o.ToList());

​

        var test5e = new[] { "a", "b", "c" };

        var test5d = new[] { "b", "a", "c", };          // second moved first

​

        var ops5g = ReconcileImagesGeroge(test5e, test5d);

        Test("Test 5 - George", test5e, test5d, ops5g.ToList());

​

        var ops5o = ReconcileImagesOndrej(test5e, test5d);

        Test("Test 5 - Ondrej", test5e, test5d, ops5o.ToList());

​

        var test6e = new[] { "a", "b", "c" };

        var test6d = new[] { "b", "c", "a" };           // first moved last

​

        var ops6g = ReconcileImagesGeroge(test6e, test6d);

        Test("Test 6 - George", test6e, test6d, ops6g.ToList());

​

        var ops6o = ReconcileImagesOndrej(test6e, test6d);

        Test("Test 6 - Ondrej", test6e, test6d, ops6o.ToList());

​

        var test7e = new[] { "a", "b", "c" };

        var test7d = new[] { "a", "c", "d", "e" };      // second removed, two added

​

        var ops7g = ReconcileImagesGeroge(test7e, test7d);

        Test("Test 7 - George", test7e, test7d, ops7g.ToList());

​

        var ops7o = ReconcileImagesOndrej(test7e, test7d);

        Test("Test 7 - Ondrej", test7e, test7d, ops7o.ToList());

        var test8e = new[] { "a", "b", "c", "d", "e" };

        var test8d = new[] { "a", "c", "e", "f", "g" };      // 2nd and 4th removed, two added

​

        var ops8g = ReconcileImagesGeroge(test8e, test8d);

        Test("Test 8 - George", test8e, test8d, ops8g.ToList());

​

        var ops8o = ReconcileImagesOndrej(test8e, test7d);

        Test("Test 8 - Ondrej", test8e, test8d, ops8o.ToList());

​

    }

​

​

    public static IEnumerable<Operation> ReconcileImagesGeroge(

        string[] existingImages,

        string[] desiredImages)

    {

        var reconciledImageIndex = 0;

        var existingImageIndex = 0;

        List<string> removeImageUrls = new List<string>();

        List<string> addImageUrls = new List<string>();

        HashSet<string> existingImageUrlsFound = new HashSet<string>();

​

        while (reconciledImageIndex < desiredImages.Length)

        {

            var reconcileImage = desiredImages[reconciledImageIndex];

            while (existingImageIndex < existingImages.Length)

            {

                var existingImage = existingImages[existingImageIndex];

                existingImageIndex++;

                if (reconcileImage != existingImage)

                {

                    if (!existingImageUrlsFound.Contains(existingImage))

                        removeImageUrls.Add(existingImage);

                }

                else

                {

                    existingImageUrlsFound.Add(existingImage);

                    break;

                }

            }

​

            if (existingImageIndex >= existingImages.Length)

            {

                addImageUrls.Add(reconcileImage);

            }

            reconciledImageIndex++;

        }

​

        // remove items

        foreach(var img in removeImageUrls) {

            yield return new Remove(img);

        }

​

        // items in list

        foreach (var img in addImageUrls)

        {

            yield return new Add(img);

        }

    }

​

    public static IEnumerable<Operation> ReconcileImagesOndrej(

        string[] existingImages,

        string[] desiredImages)

    {

        var di = 0;

        var ei = 0;

​

        while (di < desiredImages.Length)

        {

            var desiredImage = desiredImages[di];

            var found = false;

            while (ei < existingImages.Length)

            {

                var existingImage = existingImages[ei];

                ei++;

                if (desiredImage == existingImage)

                {

                    found = true;

                    break;

                }

                else

                {

                    yield return new Remove(existingImage);

                }

            }

​

            if (!found)

            {

                yield return new Add(desiredImage);

            }

            di++;

        }

    }

​

    public static void Test(

        string TestName,

        string[] existingImages,

        string[] desiredImages,

        List<Operation> operations) {

​

        Console.WriteLine($"TEST: {TestName}");

​

        var work = existingImages.ToList();

        foreach (var operation in operations)

        {

            switch (operation)

            {

                case Remove:

                    Console.WriteLine($"  Removing image {operation.Url}");

                    work.Remove(operation.Url);

                    break;

                case Add:

                    Console.WriteLine($"  Adding image {operation.Url}");

                    work.Add(operation.Url);

                break;

            }

        }

​

        var expected = string.Join(", ", desiredImages);

        var result = string.Join(", ", work);

​

        if (expected == result) {

            Console.WriteLine("PASS");

        } else {

            Console.WriteLine("FAIL");

            Console.WriteLine($"  Expected: {expected}");

            Console.WriteLine($"  But got : {result}");

        }

​

        Console.WriteLine();

​

    }

​

}