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

namespace miew.Tally
{
	[DebuggerDisplay("{ToString(),nq}")]
	public struct Tally<T>
	{
		public Tally(T item, int count)
		{
			this.Item = item;
			this.Count = count;
		}
		public readonly T Item;
		public int Count;
		public override string ToString()
		{
			return System.String.Format("{0} {1}", Item.ToString(), Count);
		}
	};

	public interface ITallySet<T> : ICollection<T>
	{
		int GetTally(T item);
	};

	[DebuggerDisplay("count={Count}")]
	public class TallySet<T> : ITallySet<T>, IEnumerable<Tally<T>>
	{
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		Dictionary<T, int> tallies = new Dictionary<T, int>();

		public bool Add(T item)
		{
			int i;
			if (tallies.TryGetValue(item, out i))
			{
				tallies[item] = i + 1;
				return false;
			}
			tallies.Add(item, 1);
			return true;
		}

		public bool Remove(T item)
		{
			if (--tallies[item] > 0)
				return false;
			tallies.Remove(item);
			return true;
		}

		public int GetTally(T item)
		{
			return tallies[item];
		}

		void ICollection<T>.Add(T item)
		{
			Add(item);
		}

		public void Clear()
		{
			tallies.Clear();
		}

		public bool Contains(T item)
		{
			return tallies.ContainsKey(item);
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			tallies.Keys.CopyTo(array, arrayIndex);
		}

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

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool IsReadOnly
		{
			get { return false; }
		}

		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{
			return tallies.Keys.GetEnumerator();
		}

		IEnumerator<Tally<T>> IEnumerable<Tally<T>>.GetEnumerator()
		{
			foreach (var kvp in tallies)
				yield return new Tally<T>(kvp.Key, kvp.Value);
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return ((IEnumerable<Tally<T>>)this).GetEnumerator();
		}

#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public Tally<T>[] _items
		{
			get { return ((IEnumerable<Tally<T>>)this).ToArray(); }
		}
#endif
	};

	public static class Ext
	{
		/// <summary>
		/// Determine tallies for each distinct group of source elements
		/// </summary>
		public static IEnumerable<Tally<TSrc>> ToTallies<TSrc>(this IEnumerable<TSrc> seq)
		{
			Dictionary<TSrc, int> d = new Dictionary<TSrc, int>();
			foreach (TSrc t in seq)
			{
				if (d.ContainsKey(t))
					d[t]++;
				else
					d.Add(t, 1);
			}
			foreach (var kvp in d)
				yield return new Tally<TSrc>(kvp.Key, kvp.Value);
		}
		/// <summary>
		/// Determine tallies for each distinct group of source elements
		/// </summary>
		public static IEnumerable<Tally<TSrc>> ToTallies<TSrc>(this IEnumerable<TSrc> seq, IEqualityComparer<TSrc> c)
		{
			Dictionary<TSrc, int> d = new Dictionary<TSrc, int>(c);
			foreach (TSrc t in seq)
			{
				if (d.ContainsKey(t))
					d[t]++;
				else
					d.Add(t, 1);
			}
			foreach (var kvp in d)
				yield return new Tally<TSrc>(kvp.Key, kvp.Value);
		}

		/// <summary>
		/// Return tallies for the distinct groups of source elements, determined according to the key selector. Each group is 
		/// identified by (an arbitrary) one of its source elements
		/// </summary>
		public static IEnumerable<Tally<TSrc>> ToTallies<TSrc, TKey>(this IEnumerable<TSrc> ie, Func<TSrc, TKey> fn, IEqualityComparer<TKey> c)
		{
			Dictionary<TKey, Tally<TSrc>> d = new Dictionary<TKey, Tally<TSrc>>(c);
			foreach (TSrc t in ie)
			{
				Tally<TSrc> tal;
				TKey k = fn(t);
				if (d.TryGetValue(k, out tal))
					d[k] = new Tally<TSrc>(t, tal.Count + 1);
				else
					d.Add(k, new Tally<TSrc>(t, 1));
			}
			return d.Values;
		}

		/// <summary>
		/// Determine tallies for each distinct group of dictionary values
		/// </summary>
		public static IEnumerable<Tally<V>> TallyValues<K, V>(this IDictionary<K, V> dict)
		{
			Dictionary<V, int> td = new Dictionary<V, int>();
			foreach (var kvp in dict)
			{
				if (td.ContainsKey(kvp.Value))
					td[kvp.Value]++;
				else
					td.Add(kvp.Value, 1);
			}
			foreach (var kvp in td)
				yield return new Tally<V>(kvp.Key, kvp.Value);
		}

		/// <summary>
		/// Determine tallies for each distinct group of dictionary values
		/// </summary>
		public static IEnumerable<Tally<V>> TallyValues<K, V>(this IDictionary<K, V> dict, IEqualityComparer<V> c)
		{
			Dictionary<V, int> td = new Dictionary<V, int>(c);
			foreach (var kvp in dict)
			{
				if (td.ContainsKey(kvp.Value))
					td[kvp.Value]++;
				else
					td.Add(kvp.Value, 1);
			}
			foreach (var kvp in td)
				yield return new Tally<V>(kvp.Key, kvp.Value);
		}
	};
}