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

namespace LinqToObjects
{
    public static class Enumerable
    {
        public static IEnumerable<int> Range(int from, int to)
        {
            for (int i = from; i <= to; i++)
                yield return i;
        }

        public static T Aggregate<T>(this IEnumerable<T> source, Func<T, T, T> func)
        {
            Preconditions.CheckNotNull(source,"source");
            Preconditions.CheckNotNull(func,"func");

            T current;
            using (IEnumerator<T> iterator = source.GetEnumerator())
            {
                iterator.MoveNext();
                current = iterator.Current;

                while (iterator.MoveNext())
                {
                    current = func(current, iterator.Current);
                }
            }
            return current;
        }

        public static TAccumulate Aggregate<T, TAccumulate>(this IEnumerable<T> source, TAccumulate seed,
            Func<TAccumulate, T, TAccumulate> func)
        {
            Preconditions.CheckNotNull(source, "source");
            Preconditions.CheckNotNull(func, "func");

            TAccumulate current = seed;
            using (IEnumerator<T> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    current = func(current, iterator.Current);
                }
            }
            return current;
        }

        public static TResult Aggregate<TSource, TAccumulate, TResult>(
            this IEnumerable<TSource> source,
            TAccumulate seed,
            Func<TAccumulate, TSource, TAccumulate> func,
            Func<TAccumulate, TResult> resultSelector)
        {
            Preconditions.CheckNotNull(source, "source");
            Preconditions.CheckNotNull(func, "func");
            Preconditions.CheckNotNull(resultSelector,"resultSelector");

            return resultSelector(source.Aggregate(seed, func));
        }

        public static bool All<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, bool> predicate
            )
        {
            foreach (var item in source)
            {
                if (!predicate(item))
                    return false;
            }
            return true;
        }

        public static bool Any<TSource>(this IEnumerable<TSource> source)
        {
            return source.Count() != 0;
        }

        public static bool Any<TSource>(this IEnumerable<TSource> source,Func<TSource, bool> predicate)
        {
            foreach (var item in source)
            {
                if (predicate(item)) return true;
            }
            return false;
        }

        public static IEnumerable<TSource> AsEnumerable<TSource>(this IEnumerable<TSource> source)
        {
            return source;
        }

        public static int Count<TSource>(this IEnumerable<TSource> source)
        {
            if (source is IList<TSource>) return ((IList<TSource>) source).Count;
            if (source is ICollection<TSource>) return ((ICollection<TSource>) source).Count;

            int count = 0;

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext()) count++;
            }

            return count;
        }

        public static int Count<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, bool> predicate)
        {
            int count = 0;

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    if (predicate(iterator.Current))
                    {
                        count++;
                    }
                }
            }

            return count;
        }

        public static long LongCount<TSource>(this IEnumerable<TSource> source)
        {
            if (source is IList<TSource>) return ((IList<TSource>)source).Count;
            if (source is ICollection<TSource>) return ((ICollection<TSource>)source).Count;

            long count = 0;

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext()) count++;
            }

            return count;
        }

        public static IEnumerable<TResult> Cast<TResult>(this IEnumerable source)
        {
            foreach (var item in source)
                yield return (TResult) item;
        }

        public static IEnumerable<TSource> Concat<TSource>(
            this IEnumerable<TSource> first,
            IEnumerable<TSource> second)
        {
            foreach (var item in first)
                yield return item;

            foreach (var item in second)
                yield return item;
        }

        public static bool Contains<TSource>(
            this IEnumerable<TSource> source,
            TSource value)
        {
            foreach (var item in source)
            {
                if (item.Equals(value))
                    return true;
            }
            return false;
        }

        public static bool Contains<TSource>(
            this IEnumerable<TSource> source,
            TSource value,
            IEqualityComparer<TSource> comparer)
        {
            foreach (var item in source)
            {
                if (comparer.Equals(item, value))
                    return true;
            }
            return false;
        }

        public static IEnumerable<TSource> DefaultIfEmpty<TSource>(this IEnumerable<TSource> source)
        {
            return source.DefaultIfEmpty(default(TSource));
        }

        public static IEnumerable<TSource> DefaultIfEmpty<TSource>(
            this IEnumerable<TSource> source,
            TSource defaultValue)
        {
            Preconditions.CheckNotNull(source,"source");

            if (!source.Any())
            {
                return new[] {defaultValue};
            }

            return source;
        }

        public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source)
        {
            HashSet<TSource> hash = new HashSet<TSource>();

            foreach (var item in source)
            {
                if (hash.Add(item)) yield return item;
            }
        }

        public static IEnumerable<TSource> Distinct<TSource>(
            this IEnumerable<TSource> source,
            IEqualityComparer<TSource> comparer)
        {
            HashSet<TSource> hash = new HashSet<TSource>(comparer);

            foreach (var item in source)
            {
                if (hash.Add(item)) yield return item;
            }
        }

        public static TSource ElementAt<TSource>(
            this IEnumerable<TSource> source, int index)
        {
            Preconditions.CheckNotNull(source, "source");
            Preconditions.CheckNotOutOfBounds(index);

            if (source is IList<TSource>) return ((IList<TSource>) source)[index];

            int count = 0;

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    if (count == index)
                    {
                        return iterator.Current;
                    }

                    count++;
                }
            }

            throw new IndexOutOfRangeException();
        }

        public static TSource ElementAtOrDefault<TSource>(
            this IEnumerable<TSource> source,
            int index)
        {
            Preconditions.CheckNotNull(source, "source");
            Preconditions.CheckNotOutOfBounds(index);

            if (source is IList<TSource>) return ((IList<TSource>)source)[index];

            int count = 0;

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    if (count == index)
                    {
                        return iterator.Current;
                    }

                    count++;
                }
            }

            return default(TSource);
        }

        public static IEnumerable<TSource> Except<TSource>(
            this IEnumerable<TSource> first,
            IEnumerable<TSource> second)
        {
            HashSet<TSource> hash = new HashSet<TSource>(second);

            foreach(var item in first)
                if (hash.Add(item)) yield return item;
        }

        public static IEnumerable<TSource> Except<TSource>(
            this IEnumerable<TSource> first,
            IEnumerable<TSource> second,
            IEqualityComparer<TSource> comparer)
        {
            HashSet<TSource> hash = new HashSet<TSource>(second,comparer);

            foreach(var item in first)
                if (hash.Add(item)) yield return item;
        }

        public static TSource First<TSource>(this IEnumerable<TSource> source)
        {
            Preconditions.CheckNotNull(source, "source");

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                if (iterator.MoveNext())
                {
                    return iterator.Current;
                }
                else
                {
                    throw new InvalidOperationException("source sequence was empty");
                }
            }
        }

        public static TSource First<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, bool> predicate)
        {
            Preconditions.CheckNotNull(source, "source");
            Preconditions.CheckNotNull(predicate, "predicate");
            Preconditions.CheckNotEmpty(source);

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    if (predicate(iterator.Current))
                    {
                        return iterator.Current;
                    }
                }
            }

            throw new InvalidOperationException("No element satisfies the condition in predicate");
        }

        public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source)
        {
            Preconditions.CheckNotNull(source, "source");

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                if (iterator.MoveNext())
                {
                    return iterator.Current;
                }
                else
                {
                    return default(TSource);
                }
            }
        }

        public static TSource FirstOrDefault<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, bool> predicate)
        {
            Preconditions.CheckNotNull(source, "source");

            using (IEnumerator<TSource> iterator = source.GetEnumerator())
            {
                while (iterator.MoveNext())
                {
                    if (predicate(iterator.Current))
                    {
                        return iterator.Current;
                    }
                }
            }

            return default(TSource);
        }

        public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector)
        {
            var dictionary = new Dictionary<TKey, Grouping<TKey, TSource>>();

            foreach (var item in source)
            {
                TKey key = keySelector(item);
                if (!dictionary.ContainsKey(key))
                {
                    var grouping = new Grouping<TKey, TSource>(key);
                    grouping.Add(item);
                    dictionary[key] = grouping;
                }
                else
                {
                    dictionary[key].Add(item);
                }
            }

            return dictionary.Values;
        }

        public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IEqualityComparer<TKey> comparer)
        {
            var dictionary = new Dictionary<TKey, Grouping<TKey, TSource>>(comparer);

            foreach (var item in source)
            {
                TKey key = keySelector(item);
                if (!dictionary.ContainsKey(key))
                {
                    var grouping = new Grouping<TKey, TSource>(key);
                    grouping.Add(item);
                    dictionary[key] = grouping;
                }
                else
                {
                    dictionary[key].Add(item);
                }
            }

            return dictionary.Values;
        }


        public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TSource, TElement> elementSelector)
        {
            var dictionary = new Dictionary<TKey, Grouping<TKey, TElement>>();

            foreach (var item in source)
            {
                TKey key = keySelector(item);
                if (!dictionary.ContainsKey(key))
                {
                    var grouping = new Grouping<TKey, TElement>(key);
                    grouping.Add(elementSelector(item));
                    dictionary[key] = grouping;
                }
                else
                {
                    dictionary[key].Add(elementSelector(item));
                }
            }

            return dictionary.Values;
        }

        public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TKey, IEnumerable<TSource>, TResult> resultSelector)
        {
            return source.GroupBy(keySelector).Select(x => resultSelector(x.Key,x));
        }

        public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TSource, TElement> elementSelector,
            IEqualityComparer<TKey> comparer
            )
        {
            var dictionary = new Dictionary<TKey, Grouping<TKey, TElement>>(comparer);

            foreach (var item in source)
            {
                TKey key = keySelector(item);
                if (!dictionary.ContainsKey(key))
                {
                    var grouping = new Grouping<TKey, TElement>(key);
                    grouping.Add(elementSelector(item));
                    dictionary[key] = grouping;
                }
                else
                {
                    dictionary[key].Add(elementSelector(item));
                }
            }

            return dictionary.Values;
        }

        public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TKey, IEnumerable<TSource>, TResult> resultSelector,
            IEqualityComparer<TKey> comparer)
        {
            return source.GroupBy(keySelector,comparer).Select(x => resultSelector(x.Key, x));
        }

        public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TSource, TElement> elementSelector,
            Func<TKey, IEnumerable<TElement>, TResult> resultSelector)
        {
            return source.GroupBy(keySelector, elementSelector).Select(x => resultSelector(x.Key, x));
        }

        public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            Func<TSource, TElement> elementSelector,
            Func<TKey, IEnumerable<TElement>, TResult> resultSelector,
            IEqualityComparer<TKey> comparer)
        {
            return source.GroupBy(keySelector, elementSelector,comparer).Select(x => resultSelector(x.Key, x));
        }


        public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source,
            Func<TSource, TResult> selector)
        {
            foreach (var item in source)
                yield return selector(item);
        }

        public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source,
            Func<TSource, bool> predicate)
        {
            foreach (var item in source)
                if (predicate(item))
                    yield return item;
        }
    }

    public interface IGrouping<out TKey, out TElement> : IEnumerable<TElement>,IEnumerable
    {
        TKey Key { get; }
    }

    public class Grouping<TKey, TValue> : IGrouping<TKey, TValue>
    {
        private List<TValue> values = new List<TValue>();

        public Grouping(TKey key)
        {
            Key = key;
        }

        public IEnumerator<TValue> GetEnumerator()
        {
            return values.GetEnumerator();
        }

        public void Add(TValue value)
        {
            values.Add(value);
        }

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

        public TKey Key { get; private set; }
    }
}