using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SpeedCompare
{
    class Program
    {
        static Random random = new Random();
        // static Random random = new Random(18347343);

        static String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToLower() + "0123456789";

        static String generateRandomString(int n)
        {
            return new String(Enumerable.Range(0, n).Select(_ => alphabet[random.Next(alphabet.Length)]).ToArray());
        }

        static List<Tuple<String, String>> generateTestCase(int from, int to, int step, bool isSubstring, bool isRatioSize)
        {
            var res = new List<Tuple<String, String>>();
            for (; from < to; from += step)
            {
                int substringSize = isRatioSize ? from / 1000 : 1000;
                String longString = generateRandomString(from);
                String shortString = isSubstring
                    // If short string should be a substring of a long string
                    ? longString.Substring(random.Next(from - substringSize), substringSize)
                    // othervise
                    : generateRandomString(substringSize);

                res.Add(new Tuple<String, String>(longString, shortString));
            }
            return res;
        }

        static void PrintTestCase(List<Tuple<String, String>> testcase)
        {
            testcase.ForEach(t => Console.WriteLine(t.Item1 + "\t" + t.Item2));
        }

        static List<R> printAlgorithmTimings<R, T>(List<Tuple<T, T>> testcase, Func<T, T, R> algorithm)
        {
            // Warmup cache
            testcase.ForEach(arg => algorithm(arg.Item1, arg.Item2));
            List<R> results = new List<R>(testcase.Count);
            foreach(var arg in testcase)
            {
                var watch = System.Diagnostics.Stopwatch.StartNew();
                var res = algorithm(arg.Item1, arg.Item2);
                watch.Stop();
                results.Add(res);
                Console.WriteLine(watch.Elapsed);
            }
            return results;
        }

        static void compareTwoAlgorithms<R, T>(List<Tuple<T, T>> testcase, Func<T, T, R> first, Func<T, T, R> second)
            where T: ICloneable
        {
            Console.WriteLine("First Algorithm Timings:");
            List<R> firstResults = printAlgorithmTimings(testcase, first);

            Console.WriteLine("Second Algorithm Timings:");
            List<R> secondResults = printAlgorithmTimings(testcase, first);

            // Compare, if two algorithms had the same output
            if (!firstResults.Zip(secondResults, (x, y) => x.Equals(y)).Aggregate(true, (x, y) => x && y))
            {
                throw new Exception("Algorithms had different output! Abort... ");
            }
        }

        static Boolean isSubstring1(String longString, String shortString)
        {
            return longString.Contains(shortString);
        }

        static Boolean isSubstring2(String longString, String shortString)
        {
            /*
             * Replace the string below with your code
             */
            return longString.Contains(shortString);
        }

        static void compareSubstringAlgorithms(List<Tuple<String, String>> testcase)
        {
            compareTwoAlgorithms(testcase, isSubstring1, isSubstring2);
        }

        static void Main(string[] args)
        {
            // var testcase = generateTestCase(30, 100, 10, isSubstring: false, isRatioSize: true);
            // PrintTestCase(testcase);

            Console.WriteLine("######## isSubstring: false, isRatioSize: false ########");
            compareSubstringAlgorithms(generateTestCase((int)10e6, (int)50e6, (int)5e6, isSubstring: false, isRatioSize: false));
            Console.WriteLine("######## isSubstring: true, isRatioSize: false ########");
            compareSubstringAlgorithms(generateTestCase((int)10e6, (int)50e6, (int)5e6, isSubstring: true, isRatioSize: false));
            Console.WriteLine("######## isSubstring: false, isRatioSize: true ########");
            compareSubstringAlgorithms(generateTestCase((int)10e6, (int)50e6, (int)5e6, isSubstring: false, isRatioSize: true));
            Console.WriteLine("######## isSubstring: true, isRatioSize: true ########");
            compareSubstringAlgorithms(generateTestCase((int)10e6, (int)50e6, (int)5e6, isSubstring: true, isRatioSize: true));

            Console.ReadKey();
        }
    }
}