using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Test
{
    public static void Main()
    {
		List<int> results;
		List<int> m;
		List<int> n;
        int x;
        Stopwatch sw;
        
        // warmup
        results = new List<int>(200);
        for(x = 0; x < 100; x++) {
        	results.Add(SortedExcept(Make(10, 13), Make(100, 7)).Count);
        	results.Add(SortedExcept(Make(10, 13), Make(100, 7)).Count);
        }

        // test M * Ln(N)
        sw = new Stopwatch();
        results = new List<int>(200);
        m = Make(50, 3);
        n = Make(10000000, 2);
        sw.Start();
        for(x = 0; x < 100; x++) {
        	results.Add(SortedExcept(m, n).Count);
        	results.Add(SortedExcept(m, n).Count);
        }
        sw.Stop();
        Console.WriteLine("M * LN( N ) : " + results[0]);
        Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
		
		// test N * Ln(M)
        sw = new Stopwatch();
        results = new List<int>(200);
        m = Make(10000000, 2);
        n = Make(50, 3);
        sw.Start();
        for(x = 0; x < 100; x++) {
        	results.Add(SortedExcept(n, m).Count);
        	results.Add(SortedExcept(n, m).Count);
        }
        sw.Stop();
        Console.WriteLine("N * LN( M ) : " + results[0]);
        Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
		
		// test M + N
		sw = new Stopwatch();
        results = new List<int>(200);
        m = Make(50, 3);
        n = Make(10000000, 2);
        sw.Start();
        for(x = 0; x < 100; x++) {
        	results.Add(SortedExcept2(m, n).Count);
        	results.Add(SortedExcept2(m, n).Count);
        }
        sw.Stop();
        Console.WriteLine("M + N : " + results[0]);
        Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
    }
    
    public static List<int> Make(int size, int stride) {
    	List<int> result = new List<int>();
    	for(int i = 0, x = 0; x < size; i+=stride, x++) { 
            result.Add(i);
        }
        return result;
    }

    public static List<T> SortedExcept<T>(List<T> m, List<T> n) {
        var result = new List<T>();
        int i, index;
        for(i = 0; i < m.Count; i++) {
            index = n.BinarySearch(m[i]);
            if(index < 0) { 
                result.Add(m[i]); 
            }
        }
        return result;
    }
    
    public static List<T> SortedExcept2<T>(List<T> m, List<T> n) where T : IComparable<T> {
        var result = new List<T>();
        int i = 0, j = 0;
        if(n.Count == 0) {
        	result.AddRange(m);
        	return result;
        }
        while(i < m.Count) {
        	if(m[i].CompareTo(n[j]) < 0) {
        		result.Add(m[i]);
        		i++;
        	} else if(m[i].CompareTo(n[j]) > 0) {
        		j++;
        	} else {
        		i++;
        	}
        	if(j >= n.Count) {
        		for(; i < m.Count; i++) { 
        			result.Add(m[i]); 
        		}
				break;
        	}
        }
        return result;
    }
}