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

public static class IEnumerableExtensions
{
	public static IEnumerable<TSource> Empty<TSource>()
	{
		yield break;
	}
	
	public static IEnumerable<int> Range(int start, int count)
	{
		int end = start + count;
		for (int i = start; i < end; ++i)
		{
			yield return i;
		}
	}
	
	public static IEnumerable<T> Enumerate<T>()
	{
		Util.AssertTrue(typeof(T).IsEnum, "Generic Type 'T' must be an Enum");
		return (T[])Enum.GetValues(typeof(T));
	}
	
	public static IEnumerable<TSource> Repeat<TSource>(TSource item, int times)
	{
		while (times-- > 0)
		{
			yield return item;
		}
	}
	
    public static bool IsEmpty<TSource>(this IEnumerable<TSource> collection)
    {
		#pragma warning disable 0168
        foreach (var item in collection)
        {
            return false;
        }
		#pragma warning restore 0168
        return true;
    }
	
	public static TSource[] ToArray<TSource>(this IEnumerable<TSource> collection)
	{
		TSource[] array = null;
		if (collection is ICollection)
		{
			ICollection c = (ICollection)collection;
			array = new TSource[c.Count];
			c.CopyTo(array, 0);
		}
		else
		{
			array = new TSource[collection.Count()];
			int idx = 0;
			foreach (TSource t in collection)
			{
				array[idx++] = t;
			}
		}
		return array;
	}
	
	public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(this IEnumerable<TSource> collection,
		Func<TSource, TKey> keySelector)
	{
		Dictionary<TKey, TSource> result;
		if (collection is ICollection<TSource>)
		{
			result = new Dictionary<TKey, TSource>(((ICollection<TSource>)collection).Count);
		}
		else
		{
			result = new Dictionary<TKey, TSource>();
		}
		collection.ForEach(item => result.Add (keySelector(item), item));
		return result;
	}
	
	public static Dictionary<TKey, TValue> ToDictionary<TSource, TKey, TValue>(this IEnumerable<TSource> collection,
		Func<TSource, TKey> keySelector, Func<TSource, TValue> valueSelector)
	{
		Dictionary<TKey, TValue> result;
		if (collection is ICollection<TSource>)
		{
			result = new Dictionary<TKey, TValue>(((ICollection<TSource>)collection).Count);
		}
		else
		{
			result = new Dictionary<TKey, TValue>();
		}
		collection.ForEach(item => result.Add (keySelector(item), valueSelector(item)));
		return result;
	}
	
	public static IEnumerable<TSource> Reverse<TSource>(this IEnumerable<TSource> collection)
	{
		if (collection is IList<TSource>)
		{
			IList<TSource> l = (IList<TSource>)collection;
			for (int i = l.Count - 1; i >= 0; --i)
			{ // Iterates backwards
				yield return l[i];
			}
		}
		else
		{
			TSource[] array;
			if (collection is ICollection<TSource>)
			{
				ICollection<TSource> c = (ICollection<TSource>)collection;
				array = new TSource[c.Count];
				c.CopyTo(array, 0);
			}
			else
			{
				array = collection.ToArray();
			}
			for (int i = array.Length - 1; i >= 0; --i)
			{
				yield return array[i];
			}
		}
	}

    public static int Count<TSource>(this IEnumerable<TSource> collection)
    {
		if (collection is ICollection<TSource>)
		{
			return ((ICollection<TSource>)collection).Count;
		}
		int count = 0;
		using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
		{
			for (; enumerator.MoveNext(); ++count) ;
		}
		return count;
    }

    public static int Count<TSource>(this IEnumerable<TSource> collection, TSource element)
    {
        int count = 0;
        foreach (TSource t in collection)
        {
            if (t.Equals(element))
            {
                count++;
            }
        }
        return count;
    }
	
	public static TResult Min<TSource, TResult>(this IEnumerable<TSource> collection, Converter<TSource, TResult> converter, Comparison<TResult> comparison)
	{
		using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
		{
			if (enumerator.MoveNext())
			{
				TResult min = converter(enumerator.Current);
				
				do
				{
					TResult value = converter(enumerator.Current);
					if (comparison(value, min) < 0)
					{ // value < min
						min = value;
					}
				}
				while (enumerator.MoveNext());
				return min;
			}
			else
			{ // Sequencia vazia
				throw new ArgumentException("Sequence must be non-empty", "collection");
			}
		}
	}
	
	public static int Min<TSource>(this IEnumerable<TSource> collection, Converter<TSource, int> converter)
	{
		int min = int.MaxValue;
		
		foreach (TSource t in collection)
		{
			int value = converter(t);
			if (value < min)
			{
				min = value;
			}
		}
		return min;
	}
	
	public static float Min<TSource>(this IEnumerable<TSource> collection, Converter<TSource, float> converter)
	{
		float min = float.MaxValue;
		
		foreach (TSource t in collection)
		{
			float value = converter(t);
			if (value < min)
			{
				min = value;
			}
		}
		return min;
	}
	
	public static TResult Max<TSource, TResult>(this IEnumerable<TSource> collection, Converter<TSource, TResult> converter, Comparison<TResult> comparison)
	{
		using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
		{
			if (enumerator.MoveNext())
			{
				TResult max = converter(enumerator.Current);
				
				do
				{
					TResult value = converter(enumerator.Current);
					if (comparison(value, max) > 0)
					{ // value > max
						max = value;
					}
				}
				while (enumerator.MoveNext());
				return max;
			}
			else
			{ // Sequencia vazia
				throw new ArgumentException("Sequence must be non-empty", "collection");
			}
		}
	}
	
	public static int Max<TSource>(this IEnumerable<TSource> collection, Converter<TSource, int> converter)
	{
		int max = int.MinValue;
		
		foreach (TSource t in collection)
		{
			int value = converter(t);
			if (value > max)
			{
				max = value;
			}
		}
		return max;
	}
	
	public static float Max<TSource>(this IEnumerable<TSource> collection, Converter<TSource, float> converter)
	{
		float max = float.MinValue;
		
		foreach (TSource t in collection)
		{
			float value = converter(t);
			if (value > max)
			{
				max = value;
			}
		}
		return max;
	}

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

    public static bool ConstainsAny<TSource>(this IEnumerable<TSource> collection, TSource[] elements)
    {
        foreach (var collectionItem in collection)
        {
            foreach (var elementsItem in elements)
            {
                if (collectionItem.Equals(elementsItem))
                {
                    return true;
                }
            }
        }
        return false;
    }
	
    public static bool Contains<TSource>(this IEnumerable<TSource> collection, TSource element, System.Func<TSource, TSource, bool> comparison)
    {
		if (collection is Array)
		{
			return Array.FindIndex((TSource[])collection, (item) => comparison(element, item)) >= 0;
		}
        foreach (var item in collection)
        {
			if (comparison(item, element))
            {
                return true;
            }
        }
        return false;
    }
	
	public static IEnumerable<TSource> Concat<TSource>(this IEnumerable<TSource> first, TSource second)
	{
		foreach (TSource t in first)
		{
			yield return t;
		}
		yield return second;
	}
	
	public static IEnumerable<TSource> Concat<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
	{
		foreach (TSource t in first)
		{
			yield return t;
		}
		foreach (TSource t in second)
		{
			yield return t;
		}
	}
	
	public static void ForEach<TSource>(this IEnumerable<TSource> collection, System.Action<TSource> action)
	{
		if (collection is Array)
		{
			Array.ForEach<TSource>((TSource[])collection, action);
		}
		else
		{
			foreach (TSource t in collection)
			{
				action(t);
			}
		}
	}
	
	public static TSource Single<TSource>(this IEnumerable<TSource> collection)
	{
		using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
		{
			if (enumerator.MoveNext())
			{ // Contains, at least, one element
				TSource value = enumerator.Current;
				if (enumerator.MoveNext())
				{
					throw new InvalidOperationException("The collection does not contain exactly one element");
				}
				return value;
			}
			throw new InvalidOperationException("The collection does not contain exactly one element");
		}
	}
	
	public static IEnumerable<TSource> AsEnumerable<TSource>(TSource item)
	{
		yield return item;
	}

    public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> collection, System.Converter<TSource, TResult> converter)
    {
        // TODO: Fanta- Acrescentar exceptions
        foreach (TSource t in collection)
        {
            yield return converter(t);
        }
    }
	
	public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(
		this IEnumerable<TOuter> outer,
		IEnumerable<TInner> inner,
		Func<TOuter, TKey> outerSelector,
		Func<TInner, TKey> innerSelector,
		Func<TOuter, TInner, TResult> resultSelector)
	{
		foreach (TOuter o in outer)
		{
			foreach (TInner i in inner)
			{
				if (outerSelector(o).Equals(innerSelector(i)))
				{ // Se as keys são iguais
					yield return resultSelector(o, i);
				}
			}
		}
	}

    public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> collection, System.Predicate<TSource> predicate)
    {
        // TODO: Fanta- Acrescentar exceptions
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                yield return t;
            }
        }
    }
	
	public static IEnumerable<TResult> OfType<TSource, TResult>(this IEnumerable<TSource> collection) where TResult : TSource
	{
		foreach (TSource t in collection)
		{
			if (t is TResult)
			{
				yield return (TResult)t;
			}
		}
	}

    public static int Sum<TSource>(this IEnumerable<TSource> collection, System.Func<TSource, int> selector)
    {
        // TODO: Fanta- Acrescentar exceptions
        int sum = 0;
		if (collection is Array)
		{
			Array.ForEach((TSource[])collection, t => sum += selector(t));
			return sum;
		}
        foreach (TSource t in collection)
        {
            sum += selector(t);
        }

        return sum;
    }
	
    public static float Sum<TSource>(this IEnumerable<TSource> collection, System.Func<TSource, float> selector)
    {
        // TODO: Fanta- Acrescentar exceptions
        float sum = 0;
		if (collection is Array)
		{
			Array.ForEach((TSource[])collection, t => sum += selector(t));
			return sum;
		}
        foreach (TSource t in collection)
        {
            sum += selector(t);
        }

        return sum;
    }

    public static IEnumerable<TSource> TakeWhile<TSource>(this IEnumerable<TSource> collection, Predicate<TSource> predicate)
    {
        // TODO: Fanta- Acrescentar exceptions
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                yield return t;
            }
			else
			{
            	break;
			}
        }
    }
	
	public static IEnumerable<TSource> SkipWhile<TSource>(this IEnumerable<TSource> collection, Predicate<TSource> predicate)
	{
		using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
		{
			while (enumerator.MoveNext())
			{ // Skipping
				if (!predicate(enumerator.Current))
				{
					break;
				}
			}
			
			do
			{ // Taking all left
				yield return enumerator.Current;
			}
			while (enumerator.MoveNext());
		}
	}
	
	public static TSource ElementAt<TSource>(this IEnumerable<TSource> collection, int index)
	{
		if (collection is IList<TSource>)
		{
			return ((IList<TSource>)collection)[index];
		}
		
		foreach (var item in collection)
		{
			if (index-- == 0)
			{
				return item;
			}
		}
		throw new ArgumentOutOfRangeException("index");
	}
	
	public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> collection, int count)
	{
		foreach (TSource t in collection)
		{
			if (count > 0)
			{
				yield return t;
			}
			else
			{
				break;
			}
			--count;
		}
	}
	
	public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> collection, int count)
	{
		if (collection is IList<TSource>)
		{
			IList<TSource> l = (IList<TSource>)collection;
			int length = l.Count;
			for (int i = count; i < length; ++i)
			{
				yield return l[i];
			}
		}
		else
		{
			using (IEnumerator<TSource> enumerator = collection.GetEnumerator())
			{
				while (enumerator.MoveNext())
				{ // Skipping
					if (count == 0)
					{
						break;
					}
					--count;
				}
				
				do
				{ // Taking all left
					yield return enumerator.Current;
				}
				while (enumerator.MoveNext());
			}
		}
	}
	
	public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> collection)
	{
		if (collection == null)
		{
			return default(TSource);
		}
		foreach (TSource item in collection)
		{
			return item;
		}
		return default(TSource);
	}

    public static TSource First<TSource>(this IEnumerable<TSource> collection, Predicate<TSource> predicate)
    {
        // TODO: Fanta- Acrescentar exceptions
		if (collection is Array)
		{
			return Array.Find((TSource[])collection, predicate);
		}
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                return t;
            }
        }
		return default(TSource);
    }
	
    public static TSource First<TSource>(this IEnumerable<TSource> collection)
    {
        foreach (TSource t in collection)
        {
			return t;
        }
        throw new InvalidOperationException("No element satisfies the condition in predicate");
    }
	
	public static TSource Last<TSource>(this IEnumerable<TSource> collection, Predicate<TSource> predicate)
	{
		if (collection is Array)
		{
			return Array.FindLast((TSource[])collection, predicate);
		}
		if (collection is IList<TSource>)
		{
			IList<TSource> l = (IList<TSource>)collection;
			for (int i = l.Count - 1; i >= 0; --i)
			{
				TSource t = l[i];
				if (predicate(t))
				{
					return t;
				}
			}
			return default(TSource);
		}
		
		TSource last = default(TSource);
		
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                last = t;
            }
        }
		return last;
	}

    public static bool TrueForAll<TSource>(this IEnumerable<TSource> collection, System.Predicate<TSource> predicate)
    {
        // TODO: Fanta- Acrescentar exceptions
		if (collection is Array)
		{
			return Array.TrueForAll((TSource[])collection, predicate);
		}
        foreach (TSource t in collection)
        {
            if (!predicate(t))
            { // Se não for um match, então não é verdadeiro pra todos
                return false;
            }
        }
        return true;
    }

    public static bool Any<TSource>(this IEnumerable<TSource> collection, System.Predicate<TSource> predicate)
    {
		if (collection is Array)
		{
			return Array.Exists((TSource[])collection, predicate);
		}
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                return true;
            }
        }
        return false;
    }

    public static void RepeatUntil<TSource>(this IEnumerable<TSource> collection, System.Action<TSource> action, System.Predicate<TSource> predicate)
    {
        foreach (TSource t in collection)
        {
            action(t);
            if (predicate(t))
            {
                break;
            }
        }
    }

    public static bool OneAndOnlyOne<TSource>(this IEnumerable<TSource> collection, System.Predicate<TSource> predicate)
    {
        bool onlyOneFlag = false;
        foreach (TSource t in collection)
        {
            if (predicate(t))
            {
                if (!onlyOneFlag)
                {
                    onlyOneFlag = true;
                }
                else
                {
                    return false;
                }
            }
        }
        return onlyOneFlag;
    }
	
	public static bool SequenceEqual<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
	{
		using (IEnumerator<TSource> enumerator1 = first.GetEnumerator(), enumerator2 = second.GetEnumerator())
		{
			bool next1 = false, next2 = false;
			while (true)
			{
				next1 = enumerator1.MoveNext();
				next2 = enumerator2.MoveNext();
				if (next1 && next2)
				{
					if (!enumerator1.Current.Equals(enumerator2.Current))
					{ // Elementos diferentes
						return false;
					}
				}
				else
				{
					break;
				}
			}
			return next1 == next2; // Verifica se ambas as sequencias tem terminaram ao mesmo tempo, ou seja, mesmo comprimento
		}
	}
	
	public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> collection)
	{
		using (GenericReusable<HashSet<TSource>> reusable = GenericReusablePool<HashSet<TSource>>.Instance.Acquire())
		{
			HashSet<TSource> set = reusable.Value;
			set.Clear();
			
			foreach (TSource t in collection)
			{
				if (set.Add(t))
				{
					yield return t;
				}
			}
			set.Clear();
		}
	}
	
	public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, TSource second)
	{
		using (GenericReusable<HashSet<TSource>> reusable = GenericReusablePool<HashSet<TSource>>.Instance.Acquire())
		{
			HashSet<TSource> set = reusable.Value;
			set.Clear();
			
			foreach (TSource t in first)
			{
				if (set.Add(t))
				{
					yield return t;
				}
			}
			if (set.Add(second))
			{
				yield return second;
			}
			set.Clear();
		}
	}
	
	public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
	{
		using (GenericReusable<HashSet<TSource>> reusable = GenericReusablePool<HashSet<TSource>>.Instance.Acquire())
		{
			HashSet<TSource> set = reusable.Value;
			set.Clear();
			
			foreach (TSource t in first)
			{
				if (set.Add(t))
				{
					yield return t;
				}
			}
			foreach (TSource t in second)
			{
				if (set.Add(t))
				{
					yield return t;
				}
			}
			set.Clear();
		}
	}
	
	public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, TSource exclude)
	{
		first = Distinct(first);
		
		foreach (TSource left in first)
		{
			if (left.Equals(exclude))
			{
				continue;
			}
			yield return left;
		}
	}
	
	public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
	{
		first = Distinct(first);
		//second = Distinct(second);
		
		foreach (TSource left in first)
		{
			bool present = false;
			foreach (TSource right in second)
			{
				if (left.Equals(right))
				{ // Elemento existe nas duas sequencias
					present = true;
					break;
				}
			}
			if (!present)
			{ // Elemento presente em first e não presente em second
				yield return left;
			}
		}
	}
	
	public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
	{
		first = Distinct(first);
		second = Distinct(second);
		
		foreach (TSource left in first)
		{
			foreach (TSource right in second)
			{
				if (left.Equals(right))
				{ // Elemento presente em ambas as sequências
					yield return left;
					break;
				}
			}
		}
	}

    public static int IndexOf<TSource>(this IEnumerable<TSource> collection, TSource element)
    {
        int index = 0;
        foreach(TSource t in collection)
        {
            if (t.Equals(element))
            {
                return index;
            }
            index++;
        }
        return -1;
    }
}
