using System;

using System.Collections; 

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics; 

​

//CHALLENGE - Get difference between two unorderd, not unique lists, duplicates allowed within a list and across both lists.

//SOLUTION - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-aka-duplicates-allowed-within-a-list-and-across-both-lists.html

//OPTIMIZE - THIS IS IT using BitArray - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-lightning-fast-optimized.html

public class Program

{

    public static int loopcnt = 0;

    public static void Main()

    {

            Stopwatch sw = new Stopwatch();

            sw.Start(); 

            //RANDOM case - typical use ~ 78 ticks 

            string[] arrA = new string[] { "7", "1", "2", "3", "4", "5", "9", "7", "7", "1" };

            string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

​

            //WANT           2,5,5,5,9,7,7,7

            //WORST case - entirely different, but have 1 value in common to make it interesting ~ 88 ticks

            //string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list

            //string[] arrB = new string[] { "8", "9", "10", "12", "1", "14", "15", "15", "11", "9" };//2nd list

            //BEST case - identical ~ 24 ticks

            //string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list

            //string[] arrB = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//2nd list

            sw.Stop();

            Console.WriteLine("RANDOM CASE -two unorderd, not unique lists ");

            Console.WriteLine("A  = " + string.Join(",", arrA));

            Console.WriteLine("B  = " + string.Join(",", arrB));

            sw.Restart();

            string[] diffAminusB = new string[arrA.Length];      

            string[] diffBminusA = new string[arrB.Length];

            BitArray bitarrRemoveA = new BitArray(arrA.Length); 

            int d = 0; //index for diff list

            int a = 0; 

            bool nf = true; //not found 

​

            //bitarrRemove.Set(a, true);  version -> 13 ticks blazing fast, 19 ticks for worst case identical sets on my computer!

            for (int b = 0; b < arrB.Length; b++)

            {

                nf = true;

​

                for (a = 0; a < arrA.Length; a++)

                {

                    loopcnt++; //not require for metrics

                    //diffAminusB[a] = arrA[a]; //Tried to preload this array, and remove items using speedy BitArray, but slow             

​

                    if (!bitarrRemoveA[a] && arrA[a] == arrB[b])

                    {

                        nf = false;

                        bitarrRemoveA.Set(a, true); //magic - A-B = diffsA - flag removals for post processing

                        break;

​

                    }

                }

​

                if (nf) //not found in set B 

                    diffBminusA[d++] = arrB[b]; //diffs B not found in A, mathematically B-A = diffsB (order important here, driven by B, so those results appear)

            }

            //Get A-B = diffsA, some memory savings (but very slight) here since it's a sized array

            int idx = 0;

            for (a = 0; a < arrA.Length; a++)

            {

                if (!bitarrRemoveA[a])

                    diffAminusB[idx++] = arrA[a];

            }

​

           sw.Stop();

​

           Console.WriteLine("(A-B) Result = " + string.Join(",", diffAminusB).Trim(','));

           //Console.WriteLine("D  = " + string.Join(",", D));

           //Console.WriteLine("E  = " + string.Join(",", E)); 

​

           Console.WriteLine("(B-A) Result = " + string.Join(",", diffBminusA).TrimEnd(','));

​

           Console.WriteLine("No. of loops = " + loopcnt);

           Console.WriteLine("No. of loops = " + arrA.Length + " - Post copy using BitArray to a sized array");

​

           //Un 

           Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", diffAminusB)).Trim(',') + "," + string.Join(",", diffBminusA).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");

           Console.WriteLine("Result Unorderd Final B then A = " + (string.Join(",",  diffBminusA)).Trim(',') + "," + string.Join(",",diffAminusB).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");

​

           List<string> C = diffBminusA.ToList();

​

           List<string> D = diffBminusA.ToList().Concat(diffAminusB.ToList()).ToList();

           D.Sort();

​

           Console.WriteLine("Result  Ordered Final = " + string.Join(",", D).TrimStart(','));

           Console.WriteLine("Result  O(n^2) but very fast - can you beat it?"); 

    }

}