/*
Use of included script samples are subject to the terms specified at http://www.microsoft.com/resources/sharedsource/licensingbasics/permissivelicense.mspx
Written by Jomo Fisher
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

namespace FastSwitch {

    static class SwitchCompiler {
        public static Func<string, TR> CreateSwitch<TR>(IDictionary<string, TR> caseDict) {
            var cases = new List<Case<TR>>(caseDict.Count);
            foreach (var kv in caseDict)
                cases.Add(new Case<TR> { C = kv.Key, R = kv.Value });
            var p = Expression.Parameter(typeof(string), "p");
            var expr = Expression.Lambda<Func<string, TR>>(
                BuildStringLength(p, cases.ToOrderedArray(s => s.C.Length), 0, cases.Count - 1),
                new ParameterExpression[] { p }
            );
            var del = expr.Compile();
            return del;
        }
        static Expression BuildStringLength<TR>(ParameterExpression p, Case<TR>[] pairs, int lower, int upper) {
            int middle = MidPoint(lower, upper);
            if (pairs[lower].C.Length == pairs[middle].C.Length)
                return BuildStringChar(p, pairs.TakePage(lower, upper).ToOrderedArray(c => c.C), 0, 0, upper - lower);
            middle = pairs.FirstDifferentDown(middle, (c) => c.C.Length);
            return Expression.Condition(
                Expression.LessThan(Expression.Call(p, StringLength), Expression.Constant(pairs[middle + 1].C.Length)),
                BuildStringLength(p, pairs, lower, middle),
                BuildStringLength(p, pairs, middle + 1, upper)
            );
        }
        static Expression BuildStringChar<TR>(ParameterExpression p, Case<TR>[] pairs, int index, int lower, int upper) {
            if (pairs.TakePage(lower, upper).All(c => c.R.Equals(pairs[lower].R)))
                return Expression.Constant(pairs[lower].R);
            int middle = MidPoint(lower, upper);
            if (pairs[middle].C[index] == pairs[lower].C[index])
                return BuildStringChar(p, pairs, index + 1, lower, upper);
            middle = pairs.FirstDifferentDown(middle, (c) => c.C[index]);
            return Expression.Condition(
                Expression.LessThan(Expression.Call(p, StringIndex, Expression.Constant(index)),
                    Expression.Constant(pairs[middle + 1].C[index])),
                BuildStringChar(p, pairs, index, lower, middle),
                BuildStringChar(p, pairs, index, middle + 1, upper)
            );

        }
        struct Case<TR> {
            public string C { get; set; }
            public TR R { get; set; }
            public override string ToString() {
                return C.ToString() + " " + R.ToString();
            }
        }
        static int MidPoint(int lower, int upper) {
            return ((upper - lower + 1) / 2) + lower;
        }
        static MethodInfo StringLength = typeof(string).GetMethod("get_Length");
        static MethodInfo StringIndex = typeof(string).GetMethod("get_Chars");
    }

    static class Helpers {
        internal static T[] ToOrderedArray<T, TKey>(this IEnumerable<T> seq, Func<T, TKey> keySelector) {
            return seq.OrderBy(keySelector).ToArray();
        }
        internal static IEnumerable<T> TakePage<T>(this IEnumerable<T> seq, int first, int last) {
            return seq.Skip(first).Take(last - first + 1);
        }
        internal static int FirstDifferentDown<T, TV>(this T[] arr, int searchFrom, Func<T, TV> selector)
            where TV : IComparable<TV> {
            TV tvfrom = selector(arr[searchFrom]);
            for (int i = searchFrom - 1; i >= 0; --i)
                if (tvfrom.CompareTo(selector(arr[i])) != 0)
                    return i;
            throw new Exception("No match");
        }
    }
}