StaticStringDictionary

StaticStringDictionary.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

public static class StaticStringDictionary {

    public static StaticStringDictionary<Type> Create<Type>(IEnumerable<KeyValuePair<string, Type>> dict, Func<string, Type> fallback) {
        return new StaticStringDictionary<Type>(dict, fallback);
    }
}

public class StaticStringDictionary<Type> : IDictionary<string, Type> {

    private Func<string, Type> fallback;
    private Func<string, Type> switchFunction;

    public StaticStringDictionary(IEnumerable<KeyValuePair<string, Type>> dict, Func<string, Type> fallback) {
        this.fallback = fallback;
        this.switchFunction = CreateSwitch(dict);
    }

    private struct SwitchCase {
        public readonly string Key;
        public readonly Type Value;
        public SwitchCase(string key, Type value) {
            Key = key;
            Value = value;
        }
        public override string ToString() {
            return Key + " " + Value.ToString();
        }
    }

    private Func<string, Type> CreateSwitch(IEnumerable<KeyValuePair<string, Type>> dict) {
        var cases = dict.Select(pair => new SwitchCase(pair.Key, pair.Value)).ToList();
        ParameterExpression keyParameter = Expression.Parameter(typeof(string), "key");
        var expr = Expression.Lambda<Func<string, Type>>(
            SwitchOnLength(keyParameter, cases.OrderBy(switchCase => switchCase.Key.Length).ToArray(), 0, cases.Count - 1),
            new ParameterExpression[] { keyParameter }
        );
        var del = expr.Compile();
        return del;
    }

    private Expression SwitchOnLength(ParameterExpression keyParameter, SwitchCase[] switchCases, int lower, int upper) {                
        if (switchCases[lower].Key.Length == switchCases[upper].Key.Length) {
            return SwitchOnChar(keyParameter, switchCases.Skip(lower).Take(upper - lower + 1).ToArray(), 0, 0, upper - lower);
        }                
        int middle = GetIndexOfFirstDifferentCaseFromUp(switchCases, lower, MidPoint(lower, upper), upper, switchCase => switchCase.Key.Length);
        if (middle == -1) {
            throw new InvalidOperationException();
        }
        return Expression.Condition(
            Expression.LessThan(Expression.Call(keyParameter, stringLength), Expression.Constant(switchCases[middle + 1].Key.Length)),
            SwitchOnLength(keyParameter, switchCases, lower, middle),
            SwitchOnLength(keyParameter, switchCases, middle + 1, upper));
    }

    private Expression SwitchOnChar(ParameterExpression keyParameter, SwitchCase[] switchCases, int index, int lower, int upper) {
        if (index == switchCases[upper].Key.Length) {
            return null;
        }

        if (lower == upper) {
            return Expression.Condition(
                Expression.Call(stringEquals, keyParameter, Expression.Constant(switchCases[lower].Key)),
                Expression.Convert(Expression.Constant(switchCases[lower].Value), typeof(Type)),
                Expression.Invoke(Expression.Constant(fallback), keyParameter));
        }

        switchCases = switchCases.Skip(lower).Take(upper - lower + 1)
            .OrderBy(switchCase => switchCase.Key, StaticStringDictionaryComparer.For(index)).ToArray();

        upper = upper - lower;
        lower = 0;

        int middle = MidPoint(lower, upper);

        if (switchCases[lower].Key[index] == switchCases[middle].Key[index]) {
            var result = SwitchOnChar(keyParameter, switchCases, index + 1, lower, upper);
            if (result != null) {
                return result;
            }
        }

        middle = GetIndexOfFirstDifferentCaseFromUp(switchCases, lower, middle, upper, switchCase => switchCase.Key[index]);
        if (middle == -1) {
            return null;
        }

        var trueBranch = SwitchOnChar(keyParameter, switchCases, index, lower, middle);
        if (trueBranch == null) {
            return null;
        }
        
        var falseBranch = SwitchOnChar(keyParameter, switchCases, index, middle + 1, upper);
        if (falseBranch == null) {
            return null;
        }

        return Expression.Condition(
            Expression.LessThan(Expression.Call(keyParameter, stringIndex, Expression.Constant(index)),
                Expression.Constant(switchCases[middle + 1].Key[index])),
                trueBranch,
                falseBranch);
    }

    private static int MidPoint(int lower, int upper) {
        return ((upper - lower + 1) / 2) + lower;
    }

    private static int GetIndexOfFirstDifferentCaseFromUp<T>(SwitchCase[] cases, int lower, int middle, int upper, Func<SwitchCase, T> selector) {
        T firstValue = selector(cases[middle]);
        for (int i = middle - 1; i >= lower; --i) {
            if (!firstValue.Equals(selector(cases[i]))) {
                return i;
            }
        }
        for (int i = middle + 1; i <= upper; ++i) {
            if (!firstValue.Equals(selector(cases[i]))) {
                return i - 1;
            }
        }
        return -1;
    }

    private static MethodInfo stringLength = typeof(string).GetMethod("get_Length");
    private static MethodInfo stringIndex = typeof(string).GetMethod("get_Chars");
    private static MethodInfo stringEquals = typeof(string).GetMethod("Equals", new[] { typeof(string), typeof(string) });

    public void Add(string key, Type value) {
        throw new InvalidOperationException();
    }

    public bool ContainsKey(string key) {
        throw new InvalidOperationException();
    }

    public ICollection<string> Keys {
        get { throw new InvalidOperationException(); }
    }

    public bool Remove(string key) {
        throw new InvalidOperationException();
    }

    public bool TryGetValue(string key, out Type value) {
        throw new InvalidOperationException();
    }

    public ICollection<Type> Values {
        get { throw new InvalidOperationException(); }
    }

    public Type this[string key] {
        get { return string.IsNullOrEmpty(key) ? fallback(key) : switchFunction(key); }
        set { throw new InvalidOperationException(); }
    }

    public void Add(KeyValuePair<string, Type> item) {
        throw new InvalidOperationException();
    }

    public void Clear() {
        throw new InvalidOperationException();
    }

    public bool Contains(KeyValuePair<string, Type> item) {
        throw new InvalidOperationException();
    }

    public void CopyTo(KeyValuePair<string, Type>[] array, int arrayIndex) {
        throw new InvalidOperationException();
    }

    public int Count {
        get { throw new InvalidOperationException(); }
    }

    public bool IsReadOnly {
        get { return true; }
    }

    public bool Remove(KeyValuePair<string, Type> item) {
        throw new InvalidOperationException();
    }

    public IEnumerator<KeyValuePair<string, Type>> GetEnumerator() {
        throw new InvalidOperationException();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        throw new InvalidOperationException();
    }
}

internal class StaticStringDictionaryComparer : IComparer<string> {

    private readonly int startIndex;
    public StaticStringDictionaryComparer(int startIndex) {
        this.startIndex = startIndex;
    }

    private static Dictionary<int, IComparer<string>> comparers = new Dictionary<int, IComparer<string>>();

    public static IComparer<string> For(int startIndex) {
        IComparer<string> comparer;
        if (!comparers.TryGetValue(startIndex, out comparer)) {
            comparer = new StaticStringDictionaryComparer(startIndex);
            comparers.Add(startIndex, comparer);
        }
        return comparer;
    }

    public int Compare(string x, string y) {

        if (x.Length != y.Length) {
            throw new InvalidOperationException();
        }

        for (int i = startIndex; i < x.Length; i++) {
            if (x[i] > y[i]) {
                return 1;
            } else if (x[i] < y[i]) {
                return -1;
            }
        }

        return 0;
    }
}