Signum Framework Principles

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Reflection;
using System.Linq;
using Signum.Utilities.Properties;
using Signum.Utilities;

namespace Signum.Utilities.DataStructures
{
    [Serializable]
    public class IntervalDictionary<K,V>: IEnumerable<KeyValuePair<Interval<K>, V>> 
        where K: struct, IComparable<K>, IEquatable<K>
    {
        SortedList<Interval<K>, V> dic = new SortedList<Interval<K>, V>();

        public IntervalDictionary()
        {
        }

        public IntervalDictionary(IEnumerable<Tuple<Interval<K>,V>> pairs)
        {
            foreach (var item in pairs)
            {
                Add(item.First, item.Second);
            }
        }

        public IList<Interval<K>> Intervals
        {
            get { return dic.Keys; }
        }

        public int Count
        {
            get { return dic.Count; }
        }

        public void Add(Interval<K> interval, V value)
        {
            if (dic.Count != 0) // no vac�o
            {
                int index = BinarySearch(interval.Min);

                if (index >= 0)
                    throw new ArgumentException(Resources.Intervalo0OverlapsWithExistingOne1Value2.Formato(interval, dic.Keys[index], value));

                index = ~index;

                int previous = index - 1;
                if (0 < previous)
                {
                    Interval<K> previousInt = dic.Keys[previous];
                    if (previousInt.Overlap(interval))
                        throw new ArgumentException(Resources.Intervalo0OverlapsWithExistingOne1Value2.Formato(interval, previousInt, value));
                }

                int next = index;
                if (next < dic.Count)
                {
                    Interval<K> nextInt = dic.Keys[next];
                    if (nextInt.Overlap(interval))
                        throw new ArgumentException(String.Format(Resources.Interval0OverlapsWithTheExisting1, interval, nextInt));
                }
            }

            dic.Add(interval, value);
        }

        public void Add(K min, K max, V value)
        {
            Add(new Interval<K>(min, max), value); 
        }

        public V this[K key]
        {
            get
            {
                int index = BinarySearch(key);
                if (index == ~0)
                    throw new KeyNotFoundException(Resources.DictionaryEmpty);

                if (index < 0) // not found
                {
                    index = ~index;
                    index--;
                }

                if (0 <= index && index < dic.Count && dic.Keys[index].Contains(key))
                    return dic.Values[index];

                throw new KeyNotFoundException(Resources.NoIntervalFound);
            }
            
        }

        public bool TryGetValue(K key, out V value)
        {
            value = default(V); 

            int index = BinarySearch(key);
            if (index == ~0)
                return false;

            if (index < 0) // not found
            {
                //si no se encuentra solo puede ser del intervalo anterior
                index = ~index;
                index--;
            }

            if (0 <= index && index < dic.Count && dic.Keys[index].Contains(key))
            {
                value = dic.Values[index];
                return true;
            }

            return false;
        }

        public IntervalValue<V> TryGetValue(K key)
        {
            V val;
            if(TryGetValue(key, out val))
                return new IntervalValue<V>(val);

            return new IntervalValue<V>();
        }

        public bool Remove(Interval<K> interval)
        {
            return dic.Remove(interval); 
        }

        int BinarySearch(K value)
        {
            int min = 0;
            int max = dic.Count - 1;
            while (min <= max)
            {
                int privot = min + ((max - min) >> 1);

                int comp = dic.Keys[privot].Min.CompareTo(value);
                if (comp == 0)
                {
                    return privot;
                }
                if (comp < 0)
                {
                    min = privot + 1;
                }
                else
                {
                    max = privot - 1;
                }
            }
            return ~min;
        }

        internal Interval<int> FindIntervalIndex(Interval<K> interval)
        {
            int min = BinarySearch(interval.Min);
            int max = BinarySearch(interval.Max);
            if (max == ~Count) max = ~max;

            if (min < 0 || max < 0)
                throw new InvalidOperationException(Resources.IntervalLimitsDoNotExistOnDictionary);

            return new Interval<int>(min, max);
        }

        public K? TotalMin
        {
            get
            {
                if (dic.Count == 0)
                    return null;

                return dic.First().Key.Min;
            }
        }

        public K? TotalMax
        {
            get
            {
                if (dic.Count == 0)
                    return null;
                return dic.Last().Key.Max;
            }
        }

        public IEnumerator<KeyValuePair<Interval<K>, V>> GetEnumerator()
        {
            return dic.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public override string ToString()
        {
            return dic.ToString(a => "[{0},{1}] -> {2}".Formato(a.Key.Min, a.Key.Max, a.Value), "\r\n");
        }
    }    

    public struct IntervalValue<T>
    {
        public readonly bool HasInterval;
        public readonly T Value;

        public IntervalValue(T value):this()
        {
            this.Value = value;
            this.HasInterval = true;
        }
    }

    public static class IntervalDictionaryExtensions
    {
        public static IntervalDictionary<K, VR> Mix<K, V1, V2, VR>(this IntervalDictionary<K, V1> me, IntervalDictionary<K, V2> other, Func<Interval<K>, IntervalValue<V1>, IntervalValue<V2>, IntervalValue<VR>> mixer)
            where K : struct, IComparable<K>, IEquatable<K>
        {
            Interval<K>[] keys = me.Intervals.Concat(other.Intervals).SelectMany(a => a.Elements()).Distinct().Order().BiSelect((min, max) => new Interval<K>(min, max)).ToArray();
            return new IntervalDictionary<K, VR>(keys
                .Select(k => new { Intervalo = k, Valor = mixer(k, me.TryGetValue(k.Min), other.TryGetValue(k.Min)) })
                .Where(a => a.Valor.HasInterval).Select(a => new Tuple<Interval<K>, VR>(a.Intervalo, a.Valor.Value)));
        }

        public static IntervalDictionary<K, VR> Collapse<K, V, VR>(this IEnumerable<IntervalDictionary<K, V>> collection, Func<Interval<K>, IEnumerable<V>, VR> mixer)
            where K : struct, IComparable<K>, IEquatable<K>
        {
            Interval<K>[] keys = collection.SelectMany(a => a).SelectMany(a => a.Key.Elements()).Distinct().Order().BiSelect((min, max) => new Interval<K>(min, max)).ToArray();
            return new IntervalDictionary<K, VR>(keys.Select(k => new Tuple<Interval<K>, VR>(k, mixer(k, collection.Select(intDic => intDic.TryGetValue(k.Min)).Where(vi => vi.HasInterval).Select(vi => vi.Value)))));
        }

        public static IntervalDictionary<K, VR> AggregateIntervalDictionary<K, V, VR>(this IEnumerable<Tuple<Interval<K>, V>> collection, Func<Interval<K>, IEnumerable<V>, VR> mixer)
           where K : struct, IComparable<K>, IEquatable<K>
        {
            Interval<K>[] keys = collection.SelectMany(a => a.First.Elements()).Distinct().Order().BiSelect((min, max) => new Interval<K>(min, max)).ToArray();
            return new IntervalDictionary<K, VR>(keys.Select(k => new Tuple<Interval<K>, VR>(k, mixer(k, collection.Where(a => a.First.Subset(k)).Select(a => a.Second)))));
        }

        public static IntervalDictionary<K, VR> Filter<K, V, VR>(this IntervalDictionary<K, V> me, Interval<K> filter, Func<Interval<K>, V, VR> mapper)
                 where K : struct, IComparable<K>, IEquatable<K>
        {
            IntervalDictionary<K, VR> result  = new IntervalDictionary<K,VR>(); 
            foreach (var item in me)
	        {
                var intersection = item.Key.Intersection(filter);
                if(intersection != null)
                    result.Add(intersection.Value, mapper(intersection.Value, item.Value)); 
	        }
            return result; 
        }

        public static IntervalDictionary<K, V> ToIntervalDictionary<K, V, T>(this IEnumerable<T> collection, Func<T, Interval<K>> intervalSelector, Func<T, V> valueSelector)
           where K : struct, IEquatable<K>, IComparable<K>
        {
            return new IntervalDictionary<K, V>(collection.Select(p => new Tuple<Interval<K>, V>(intervalSelector(p), valueSelector(p))));
        }

        internal static IntervalDictionary<K, int> ToIndexIntervalDictinary<Q, K>(this IEnumerable<Q> squares, Func<Q, IEnumerable<K>> func)
          where K : struct, IComparable<K>, IEquatable<K>
        {
            List<K> list = squares.SelectMany(func).Distinct().ToList();
            list.Sort();

            IntervalDictionary<K, int> result = new IntervalDictionary<K, int>();
            for (int i = 0; i < list.Count - 1; i++)
                result.Add(new Interval<K>(list[i], list[i + 1]), i);

            return result;
        }
    }
}