using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FunctionalLists
{
    public sealed class Map<TKey, TValue> : IDictionary<TKey, TValue>
    {
        private struct Entry
        {
            public int Next;
            public int HashCode;
            public TKey Key;
            public TValue Value;
        }

        Entry[] entries;
        int[] buckets;

        int entryCount;
        int freeList;
        int freeCount;

        int version;

        public IEqualityComparer<TKey> Comparer { get; private set; }

        public ICollection<TKey> Keys
        {
            get { throw new NotImplementedException(); }
        }

        public ICollection<TValue> Values
        {
            get { throw new NotImplementedException(); }
        }

        public TValue this[TKey key]
        {
            get
            {
                int entryIndex = FindEntry(key);
                if (entryIndex < 0)
                    throw new KeyNotFoundException();

                return entries[entryIndex].Value;
            }
            set { Insert(key, value, false); }
        }

        public int Count
        {
            get { return entryCount - freeCount; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public Map()
            : this(0, EqualityComparer<TKey>.Default)
        {
        }

        public Map(int capacity, IEqualityComparer<TKey> comparer)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException("capacity");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            Comparer = comparer;

            int size = GetPrime(capacity);
            entries = new Entry[size];
            buckets = new int[size];

            for (int i = 0; i < buckets.Length; i++)
            {
                buckets[i] = -1;
            }

            entryCount = 0;
            freeList = -1;
            freeCount = 0;
        }

        private void IncrementVersion()
        {
            version = unchecked(version + 1);
        }

        private int GetPrime(int min)
        {
            if (min % 2 == 0)
                min = checked(min + 1);

            for (int i = Math.Max(min, 3); i < Int32.MaxValue; i += 2)
            {
                bool isPrime = true;
                for (int j = 3; j < i; j++)
                {
                    if (i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    return i;
            }

            return min;
        }

        private void Enlarge()
        {
            // at this point we know that entries
            // array is full and freeList == -1

            int newSize = GetPrime(checked(entries.Length * 2));
            Entry[] newEntries = new Entry[newSize];
            int[] newBuckets = new int[newSize];

            for (int i = 0; i < newBuckets.Length; i++)
            {
                newBuckets[i] = -1;
            }

            Array.Copy(entries, 0, newEntries, 0, entryCount);

            for (int i = 0; i < entryCount; i++)
            {
                int newBucket = newEntries[i].HashCode % newBuckets.Length;
                newEntries[i].Next = newBuckets[newBucket];
                newBuckets[newBucket] = i;
            }

            buckets = newBuckets;
            entries = newEntries;
        }

        private void Insert(TKey key, TValue value, bool add)
        {
            int hash = Math.Abs(Comparer.GetHashCode(key));
            int bucket = hash % buckets.Length;

            for (int i = buckets[bucket]; i >= 0; i = entries[i].Next)
            {
                if (entries[i].HashCode == hash && Comparer.Equals(entries[i].Key, key))
                {
                    if (add)
                        throw new ArgumentException("Item with the same key already present in map.");

                    entries[i].Key = key;
                    entries[i].Value = value;
                    IncrementVersion();
                    return;
                }
            }

            int insertEntryIndex;
            if (freeList >= 0)
            {
                insertEntryIndex = freeList;
                freeList = entries[freeList].Next;
                freeCount--;
            }
            else
            {
                // if entries array is full
                if (entryCount == entries.Length)
                {
                    Enlarge();
                    bucket = hash % buckets.Length;
                }

                insertEntryIndex = entryCount;
                entryCount++;
            }

            entries[insertEntryIndex].HashCode = hash;
            entries[insertEntryIndex].Key = key;
            entries[insertEntryIndex].Value = value;
            entries[insertEntryIndex].Next = buckets[bucket];

            buckets[bucket] = insertEntryIndex;
            IncrementVersion();
        }

        private int FindEntry(TKey key)
        {
            int hash = Math.Abs(Comparer.GetHashCode(key));
            int bucket = hash % buckets.Length;

            for (int i = buckets[bucket]; i >= 0; i = entries[i].Next)
            {
                if (entries[i].HashCode == hash && Comparer.Equals(entries[i].Key, key))
                    return i;
            }

            return -1;
        }

        public void Add(TKey key, TValue value)
        {
            Insert(key, value, true);
        }

        public bool ContainsKey(TKey key)
        {
            return FindEntry(key) >= 0;
        }

        public bool Remove(TKey key)
        {
            int hash = Math.Abs(Comparer.GetHashCode(key));
            int bucket = hash % buckets.Length;

            int lastIndex = -1;
            for (int i = buckets[bucket]; i >= 0; i = entries[i].Next)
            {
                if (entries[i].HashCode == hash && Comparer.Equals(entries[i].Key, key))
                {
                    if (lastIndex >= 0)
                        entries[lastIndex].Next = entries[i].Next;
                    else
                        buckets[bucket] = entries[i].Next;

                    entries[i].HashCode = -1;
                    entries[i].Key = default(TKey);
                    entries[i].Value = default(TValue);
                    entries[i].Next = freeList;
                    freeList = i;
                    freeCount++;

                    IncrementVersion();
                    return true;
                }

                lastIndex = i;
            }

            return false;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int entryIndex = FindEntry(key);
            if (entryIndex >= 0)
            {
                value = entries[entryIndex].Value;
                return true;
            }
            else
            {
                value = default(TValue);
                return false;
            }
        }

        public void Clear()
        {
            if (entryCount == 0)
                return;

            for (int i = 0; i < buckets.Length; i++)
            {
                buckets[i] = -1;
            }

            Array.Clear(entries, 0, entryCount);
            entryCount = 0;
            freeList = -1;
            freeCount = 0;
            IncrementVersion();
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            int lastVersion = this.version;
            for (int i = 0; i < entryCount; i++)
            {
                // if element not removed
                if (entries[i].HashCode >= 0)
                {
                    yield return new KeyValuePair<TKey, TValue>(
                        entries[i].Key, entries[i].Value);

                    if (version != lastVersion)
                        throw new InvalidOperationException("Map was changed during enumeration.");
                }
            }
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
        {
            Insert(item.Key, item.Value, true);
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
        {
            int entryIndex = FindEntry(item.Key);
            return entryIndex >= 0 &&
                EqualityComparer<TValue>.Default.Equals(
                    item.Value, entries[entryIndex].Value);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (array.Length - arrayIndex < Count)
                throw new ArgumentException("Array length is insufficient to hold items.");

            int index = arrayIndex;
            foreach (var pair in this)
            {
                array[index] = pair;
                index++;
            }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
        {
            int entryIndex = FindEntry(item.Key);

            if (entryIndex >= 0 &&
                EqualityComparer<TValue>.Default.Equals(
                    item.Value, entries[entryIndex].Value))
            {
                Remove(item.Key);
                return true;
            }

            return false;
        }

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