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

namespace HashTablesAndSets
{
    public class Test
    {
        static void Main()
        {
            HashTable<char, int> ht = new HashTable<char, int>();
            ht['a'] = 1;
            ht['b'] = 2;
            ht['d'] = 3;
            ht['f'] = 4;
            ht['n'] = 5;
            foreach (var i in ht)
            {
                Console.WriteLine(ht[i.key]+" ");
            }


        }
    }

    partial class HashTable<TKey, TValue> : IEnumerable<Pair<TKey, TValue>>
    {
        int capacity;
        int count = 0;
        LinkedList<Pair<TKey, TValue>>[] entries;

        public HashTable()
        {
            capacity = 16;
            entries = new LinkedList<Pair<TKey, TValue>>[capacity];
            for (int i = 0; i < entries.Length; i++)
            {
                entries[i] = new LinkedList<Pair<TKey, TValue>>();
            }
        }

        IEnumerator<Pair<TKey, TValue>> IEnumerable<Pair<TKey, TValue>>.GetEnumerator()
        {
            return new HashTable<TKey, TValue>.Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new HashTable<TKey, TValue>.Enumerator(this);
        }

        public void Add(TKey key, TValue value)
        {
            int index = key.GetHashCode() % capacity;
            Pair<TKey, TValue> localPair = entries[index].FirstOrDefault(x => x.key.Equals(key));

            if (localPair == null)
            {
                entries[index].AddLast(
                    new LinkedListNode<Pair<TKey, TValue>>(
                        new Pair<TKey, TValue>(key, value)));
                count++;
                TryResize();
            }
            else
            {
                throw new ArgumentException("An item with the same key has already been added.");
            }
        }

        public void ChangeValue(TKey key, TValue value)
        {
            int index = key.GetHashCode() % capacity;
            LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
            while (iterator != null && !iterator.Value.key.Equals(key))
            {
                iterator = iterator.Next;
            }

            if (iterator == null)
            {
                entries[index].AddLast(
                    new LinkedListNode<Pair<TKey, TValue>>(
                        new Pair<TKey, TValue>(key, value)));
                count++;
                TryResize();
            }
            else
            {
                iterator.Value.value = value;
            }
        }

        private void TryResize()
        {
            if (count > capacity * 0.75)
            {
                capacity = capacity * 2;
                count = 0;
                var oldEntries = entries;
                entries = new LinkedList<Pair<TKey, TValue>>[capacity];
                for (int i = 0; i < entries.Length; i++)
                {
                    entries[i] = new LinkedList<Pair<TKey, TValue>>();
                }
                for (int i = 0; i < oldEntries.Length; i++)
                {
                    foreach (var j in oldEntries[i])
                    {
                        Add(j.key, j.value);
                    }
                }
            }
        }

        public void Remove(TKey key)
        {
            int index = key.GetHashCode() % capacity;
            LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
            while (iterator != null && !iterator.Value.key.Equals(key))
            {
                iterator = iterator.Next;
            }
            if (iterator == null)
            {
                throw new ArgumentException("An item with this key does not exist.");
            }
            else
            {
                entries[index].Remove(iterator);
                count--;
            }
        }

        public int Count
        {
            get
            {
                return count;
            }
        }

        public void Clear()
        {
            for (int i = 0; i < entries.Length; i++)
            {
                entries[i].Clear();
            }
            count = 0;
        }

        public TValue Find(TKey key)
        {
            int index = key.GetHashCode() % capacity;
            LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
            while (iterator != null && !iterator.Value.key.Equals(key))
            {
                iterator = iterator.Next;
            }
            if (iterator == null)
            {
                throw new ArgumentException("Key does not exist.");
            }
            else
            {
                return iterator.Value.value;
            }
        }
        public TValue this[TKey key]
        {
            get
            {
                return Find(key);
            }
            set
            {
                ChangeValue(key, value);
            }
        }
    }
}