/*
 * Hash Table for CSC 3102 Portfolio
*/

/*
 * --REQUIRED METHODS--
 * HashTable(int numBins)
 * void Add(Htype item)
 * Htype? Remove(Htype item)
 * bool Has(Htype item)
 * --OPTIONAL METHODS--
 * int GetBin(Htype item)
*/

using System.ComponentModel;
using System.Reflection.Metadata.Ecma335;
using System.Runtime.ExceptionServices;

namespace HashTable_3102
{
    public class Item<Htype>
    {
        public Htype? item; //item being stored
        
        public Item<Htype>? next;


        //Item constructoro with no arguments
        Item()
        {
            item = default;  
            next = null;
        }

        //Item constructor with item argument
        public Item(Htype item)
        {
            this.item = item;
            next = null;
        }
    }
    public class SLinkedList<Htype>
    {
        public Item<Htype>? first;


        //Constucts default empty bin for hash table
        public SLinkedList()
        {
            first = null;
        }

    }
    public class HashTable<Htype>
    {
        int numBins;
        SLinkedList<Htype>[] hashTable;


        //default hash table constructor 
        public HashTable(int numBins)
        {
            this.numBins = numBins;
            hashTable =  new SLinkedList<Htype>[numBins];
            for (int i = 0; i < numBins; i++)
            {
                hashTable[i] = new SLinkedList<Htype>();
            }
        }

        /*
         * Adds a new item to the hash table
        */
        public void Add(Htype item)
        {
            Item<Htype> newItem = new Item<Htype>(item);
            int itemHash = item.GetHashCode();
            int itemIndex = Math.Abs(itemHash % numBins);

            if (hashTable[itemIndex].first == null)
            {
                hashTable[itemIndex].first = newItem;
            }
            else
            {
                var temp = hashTable[itemIndex].first;
                
                while (temp.next != null)
                {
                    temp = temp.next;
                }
                temp.next = newItem;
            }
        }

        /*
         * Removes the specified item from the hash table and returns it
        */
        public Htype? Remove(Htype item)
        {
            if (!(Has(item)))
            {
                return default;
            }
            int itemIndex = GetBin(item);
            if(hashTable[itemIndex].first == null)
            {
                return default;
            }
            else if (hashTable[itemIndex].first.item.Equals(item))
            {
                if (hashTable[itemIndex].first.next == null)
                {
                    var temp = hashTable[itemIndex].first;
                    hashTable[itemIndex].first = null;
                    return temp.item;
                }
                else
                {
                    var temp = hashTable[itemIndex].first;
                    hashTable[itemIndex].first = hashTable[itemIndex].first.next;
                    temp.next = null;
                    return temp.item;
                }         
            }
            else
            {
                var temp = hashTable[itemIndex].first;
                while(!(hashTable[itemIndex].first.next.item.Equals(item)))
                {
                    temp = temp.next;
                }
                var returnItem = temp.next;
                temp.next = null;
                return returnItem.item;
            }
        }

        /*
         * checks if the hash table has the item
        */
        public bool Has(Htype item)
        {
            int itemIndex = GetBin(item);
            var temp = hashTable[itemIndex].first;
            while (temp != null)
            {
                if (temp.item.Equals(item))
                {
                    return true;
                }
                else
                {
                    temp = temp.next;
                }
            }
            return false;
        }

        private int GetBin(Htype item)
        {
            int itemHash = item.GetHashCode();
            int itemIndex = Math.Abs(itemHash % numBins);
            return itemIndex;
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        /*
         * Prints the Hash Table
        */
        public void PrintHash()
        {
            for (int i = 0; i < numBins; i++)
            {
                Console.WriteLine("Index #" + i);
                Console.Write("[ ");
                var temp = hashTable[i].first;
                while (temp != null)
                {
                    Console.Write(temp.item + " ");
                    temp = temp.next;
                }
                Console.WriteLine("]");
            }     
        }
    }
}