//HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "../../List/include/List.h"

/**
 * Implementation of a Hashtable based on bucket lists made with Linkedlist
 */

template<typename K, typename V> class HashList;

template<typename K, typename V>
class HashPair
{
    private:

        friend class HashList<K,V>;
        K key;
        V value;

    public:

        HashPair();
        // Default constructor

        HashPair(const K key,const V value);
        // constructs a new hash pair given a key and a value

        K getKey() const;
        // returns the key

        void setKey(const K key);
        // sets the key

        V getValue() const;
        // returns the value

        void setValue(const V v);
        // sets the value

};

template<typename K, typename V>
class HashList
{
    private:

        List<HashPair<K,V>> l;

    public:

        List_iterator<HashPair<K,V>> find(const K key) const;
        // Returns an HashPair given a key if present, null if absent

        void insert(const K key,const V value) const;
        // Inserts a key-value pair in the HashList

        V lookup(const K key) const;
        // Returns a reference to an HashPair value given a key if present; null otherwise

        void remove(const K key) const;
        // Removes an element given a key

        bool empty() const;
        // Returns true if the list is empty, false otherwise

        List_iterator<HashPair<K,V>> begin() const;

        List_iterator<HashPair<K,V>> end() const;

        bool finished(List_iterator<HashPair<K,V>> const p) const;

};

template<typename K, typename V>
class HashTable;

template<typename K, typename V>
class hash_iterator;

template<typename K, typename V>
bool operator ==(const hash_iterator<K,V> it, const hash_iterator<K,V> it2);

template<typename K, typename V>
bool operator !=(const hash_iterator<K,V> it, const hash_iterator<K,V> it2);

template<typename K, typename V>
class hash_iterator
{
    private:

        HashTable<K,V>* baseTable;
        int i;
        List_iterator<HashPair<K,V>> it;
        List_iterator<HashPair<K,V>> nextOccurrence();

    public:

        hash_iterator();

        hash_iterator(HashTable<K,V>* table);

        hash_iterator(const hash_iterator& it2);

        friend bool operator == <>(const hash_iterator it, const hash_iterator it2);

        friend bool operator != <>(const hash_iterator it, const hash_iterator it2);

        hash_iterator begin();

        hash_iterator end();

        hash_iterator operator ++(); //prefix

        hash_iterator operator ++( int ); //postfix

        HashPair<K,V> operator *() const;
};

template<typename K, typename V>
class HashTable
{
    protected:

        HashList<K,V>* entries;
        int m;  //table dimension
        friend class hash_iterator<K,V>;

    public:

        HashTable(const int capacity);
        //Creates a new hash table with given dimension

        ~HashTable();
        //Destructor

        bool contains(const K k) const;
        //Returns true if the hashtable contains k

        V lookup(const K k) const;
        //returns the value being searched if present, nil otherwise

        V operator [](const K k) const;
        // same as lookup, with a array like notation

        void insert(const K key,const V value) const;
        //Inserts the key-value pair into the table

        void remove(const K key) const;
        //Given a key, it removes the key-pair value, if present

        int Hash(const long int key) const;
        //Hash function

        hash_iterator<K,V> begin();

        hash_iterator<K,V> end();
};

namespace keyOnly
{

    template<typename K>
    class HashList
    {
        private:

            List<K> l;

        public:

            List_iterator<K> find(const K key) const;
            // Returns an HashPair given a key if present, null if absent

            void insert(const K key) const;
            // Inserts a key-value pair in the HashList

            void remove(const K key) const;
            // Removes an element given a key

            bool empty() const;
            // Returns true if the list is empty, false otherwise

            List_iterator<K> begin() const;

            List_iterator<K> end() const;

            bool finished(List_iterator<K> const p) const;

    };

    template<typename K>
    class HashTable;

    template<typename K>
    class hash_iterator;

    template<typename K>
    bool operator ==(const hash_iterator<K> it, const hash_iterator<K> it2);

    template<typename K>
    bool operator !=(const hash_iterator<K> it, const hash_iterator<K> it2);

    template<typename K>
    class hash_iterator
    {
        protected:

            HashTable<K>* baseTable;
            int i;
            List_iterator<K> it;
            List_iterator<K> nextOccurrence();

        public:

            hash_iterator();

            hash_iterator(HashTable<K>* table);

            hash_iterator(const hash_iterator& it2);

            friend bool operator == <>(const hash_iterator it, const hash_iterator it2);

            friend bool operator != <>(const hash_iterator it, const hash_iterator it2);

            hash_iterator begin();

            hash_iterator end() const;

            hash_iterator operator ++(); //prefix

            hash_iterator operator ++( int ); //postfix

            K operator *() const;
    };

    template<typename K>
    class HashTable
    {
        protected:

            HashList<K>* entries;
            int m;  //table dimension
            friend class hash_iterator<K>;

        public:

            HashTable();
            //Default constructor

            HashTable(const int capacity);
            //Creates a new hash table with given dimension

            ~HashTable();
            //Destructor

            bool contains(const K k) const;
            // Returns true if the table contains k

            void insert(const K key) const;
            //Inserts the key-value pair into the table

            void remove(const K key) const;
            //Given a key, it removes the key-pair value, if present

            int Hash(const long int key) const;
            //Hash function
    };

}

#include "../src/HashTable.cpp"
#endif

// HashTable.cpp
#ifndef HASHTABLE_CPP
#define HASHTABLE_CPP
#include "../include/HashTable.h"
#include <cmath>

using namespace std;

template<typename K, typename V>
HashPair<K,V>::HashPair()
{
    key = K();
    value = V();
}

template<typename K, typename V>
HashPair<K,V>::HashPair(const K key,const V value):key(key), value(value)
{
}

template<typename K, typename V>
K HashPair<K,V>::getKey() const
{
    return key;
}
// returns the key

template<typename K, typename V>
void HashPair<K,V>::setKey(const K key)
{
    this->key = key;
}
// sets the key

template<typename K, typename V>
V HashPair<K,V>::getValue() const
{
    return value;
}
// returns the value

template<typename K, typename V>
void HashPair<K,V>::setValue(const V v)
{
    this->value = value;
}
// sets the value

template<typename K, typename V>
List_iterator<HashPair<K,V>> HashList<K,V>::find(const K key) const
{
    bool found = false;
    List_iterator<HashPair<K,V>> e(nullptr);
    List_iterator<HashPair<K,V>> i = l.begin();

    while(!l.finished(i) && !found)
    {
        if((*i).key == key)
        {
            e = i;
            found = true;
        }

        i++;
    }

    return e;
}
// Returns an HashPair given a key if present, null if absent

template<typename K, typename V>
void HashList<K,V>::insert(const K key,const V value) const
{
    List_iterator<HashPair<K,V>> kv = find(key);
    HashPair<K,V> k(key,value);

    if (kv != List_iterator<HashPair<K,V>>(nullptr))
    {
        l.write(kv,k);
    }
    else
    {
        l.insert(k);
    }
}
// Inserts a key-value pair in the HashList

template<typename K, typename V>
V HashList<K,V>::lookup(const K key) const
{
    List_iterator<HashPair<K,V>> kv = find(key);
    V e = V();

    if (kv != List_iterator<HashPair<K,V>>(nullptr))
    {
        e = (*kv).value;
    }

    return e;
}
// Returns a reference to an HashPair value given a key if present; null otherwise

template<typename K, typename V>
void HashList<K,V>::remove(const K key) const
{
    List_iterator<HashPair<K,V>> item = find(key);
    if(item != List_iterator<HashPair<K,V>>(nullptr))
        l.remove(item);
}

template<typename K, typename V>
bool HashList<K,V>::empty() const
{
    return l.empty();
}

template<typename K, typename V>
List_iterator<HashPair<K,V>> HashList<K,V>::begin() const
{
    return l.begin();
}

template<typename K, typename V>
List_iterator<HashPair<K,V>> HashList<K,V>::end() const
{
    return l.end();
}

template<typename K, typename V>
bool HashList<K,V>::finished(List_iterator<HashPair<K,V>> const p) const
{
    return l.finished(p);
}

template<typename K, typename V>
List_iterator<HashPair<K,V>> hash_iterator<K,V>::nextOccurrence()
{
    i++;

    it = List_iterator<HashPair<K,V>>(nullptr);

    while(i < baseTable->m && it == List_iterator<HashPair<K,V>>(nullptr))
    {
        if(baseTable->entries[i].empty())
            i++;
        else
            it = baseTable->entries[i].begin();
    }

    return it;
}

template<typename K, typename V>
hash_iterator<K,V>::hash_iterator()
{
    baseTable = nullptr;
    i = -1;
    it = List_iterator<HashPair<K,V>>(nullptr);
}

template<typename K, typename V>
hash_iterator<K,V>::hash_iterator(HashTable<K,V>* table)
{
    baseTable = table;
    i = -1;
    it = List_iterator<HashPair<K,V>>(nullptr);
}

template<typename K, typename V>
hash_iterator<K,V>::hash_iterator(const hash_iterator& it2)
{
    baseTable = it2.baseTable;
    i = it2.i;
    it = it2.it;
}

template<typename K, typename V>
bool operator ==(const hash_iterator<K,V> it, const hash_iterator<K,V> it2)
{
    return (it.baseTable == it2.baseTable && it.it == it2.it);
}

template<typename K, typename V>
bool operator !=(const hash_iterator<K,V> it, const hash_iterator<K,V> it2)
{
    return !(it == it2);
}

template<typename K, typename V>
hash_iterator<K,V> hash_iterator<K,V>::begin()
{
    if(i != 0)
        i = -1;

    hash_iterator<K,V> ret(*this);

    ret.nextOccurrence();

    return ret;
}

template<typename K, typename V>
hash_iterator<K,V> hash_iterator<K,V>::end()
{
    hash_iterator<K,V> ret(*this);
    ret.i = baseTable->m;
    ret.it = List_iterator<HashPair<K,V>>(nullptr);
    return ret;
}

template<typename K, typename V>
hash_iterator<K,V> hash_iterator<K,V>::operator ++() //prefix
{
    it++;

    if (baseTable->entries[i].finished(it))
    {
        it = nextOccurrence();
    }

    return *this;
}

template<typename K, typename V>
hash_iterator<K,V> hash_iterator<K,V>::operator ++( int ) //postfix
{
    hash_iterator<K,V> oldit(*this);

    ++(*this);

    return oldit;
}

template<typename K, typename V>
HashPair<K,V> hash_iterator<K,V>::operator *() const
{
    return *it;
}

template<typename K, typename V>
HashTable<K,V>::HashTable(const int capacity)
{
    entries = new HashList<K,V> [capacity];
    m = capacity;
}
//Creates a new hash table with given dimension

template<typename K, typename V>
HashTable<K,V>::~HashTable()
{
    delete [] entries;
}
//Destructor

template<typename K, typename V>
V HashTable<K,V>::lookup(const K k) const
{
    int i = Hash(hash<K>()(k));
    V value = V();

    if (!entries[i].empty())
        value = entries[i].lookup(k);

    return value;
}
//returns the value being searched if present, nil otherwise

template<typename K,typename V>
bool HashTable<K,V>::contains(const K k) const
{
    int i = Hash(hash<K>()(k));
    if(entries[i].empty())
        return false;
    else
    {
        if(entries[i].find(k) == List_iterator<HashPair<K,V>>(nullptr))
            return false;
        else
            return true;
    }
}
//

template<typename K,typename V>
V HashTable<K,V>::operator [](const K k) const
{
    return lookup(k);
}

template<typename K, typename V>
void HashTable<K,V>::insert(const K key,const V value) const
{
    int i = Hash(hash<K>()(key));

    entries[i].insert(key,value);
}
//Inserts the key-value pair into the table

template<typename K, typename V>
void HashTable<K,V>::remove(const K key) const
{
    int k = Hash(hash<K>()(key));

    if (!entries[k].empty())
        entries[k].remove(key);

}
//Given a key, it removes the key-pair value, if present

template<typename K, typename V>
int HashTable<K,V>::Hash(const long int key) const
{
    return abs(key) % m;
}
//Hash function

template<typename K, typename V>
hash_iterator<K,V> HashTable<K,V>::begin()
{
    hash_iterator<K,V> ret(this);

    return ret.begin();
}

template<typename K, typename V>
hash_iterator<K,V> HashTable<K,V>::end()
{
    hash_iterator<K,V> ret(this);

    return ret.end();
}

namespace keyOnly
{

    template<typename K>
    List_iterator<K> HashList<K>::find(const K key) const
    {
        bool found = false;
        List_iterator<K> e = List_iterator<K>(nullptr);

        if(!l.empty())
        {
            List_iterator<K> i = l.begin();

            while(!l.finished(i) && !found)
            {
                if(*i == key)
                {
                    e = i;
                    found = true;
                }

                i++;
            }
        }

        return e;
    }
    // Returns an HashPair given a key if present, null if absent

    template<typename K>
    void HashList<K>::insert(const K key) const
    {
        List_iterator<K> k = find(key);

        if (k == List_iterator<K>(nullptr))
        {
            l.insert(key);
        }
        else
        {
            l.write(k,key);
        }

    }
    // Inserts a key-value pair in the HashList

    /*
    template<typename K>
    K HashList<K>::lookup(K key)
    {
        List_iterator<K> k = find(key);
        K e;

        if (k != List_iterator<K>(nullptr))
            e = *k;

        return e;
    }
    // Returns a reference to an HashPair value given a key if present; null otherwise
*/
    template<typename K>
    void HashList<K>::remove(const K key) const
    {
        List_iterator<K> item = find(key);
        if(item != List_iterator<K>(nullptr))
            l.remove(item);
    }

    template<typename K>
    bool HashList<K>::empty() const
    {
        return l.empty();
    }

    template<typename K>
    List_iterator<K> HashList<K>::begin() const
    {
        return l.begin();
    }

    template<typename K>
    List_iterator<K> HashList<K>::end() const
    {
        return l.end();
    }

    template<typename K>
    bool HashList<K>::finished(const List_iterator<K> p) const
    {
        return l.finished(p);
    }

    template<typename K>
    List_iterator<K> hash_iterator<K>::nextOccurrence()
    {
        i++;

        it = List_iterator<K>(nullptr);

        while(i < baseTable->m && it == List_iterator<K>(nullptr))
        {
            if(baseTable->entries[i].empty())
                i++;
            else
                it = baseTable->entries[i].begin();
        }

        return it;
    }

    template<typename K>
    hash_iterator<K>::hash_iterator()
    {
        baseTable = nullptr;
        i = -1;
        it = List_iterator<K>(nullptr);
    }

    template<typename K>
    hash_iterator<K>::hash_iterator(HashTable<K>* table)
    {
        baseTable = table;
        i = -1;
        it = List_iterator<K>(nullptr);
    }

    template<typename K>
    hash_iterator<K>::hash_iterator(const hash_iterator& it2)
    {
        baseTable = it2.baseTable;
        i = it2.i;
        it = it2.it;
    }

    template<typename K>
    bool operator ==(const hash_iterator<K> it, const hash_iterator<K> it2)
    {
        return (it.baseTable == it2.baseTable && it.it == it2.it);
    }

    template<typename K>
    bool operator !=(const hash_iterator<K> it, const hash_iterator<K> it2)
    {
        return !(it == it2);
    }

    template<typename K>
    hash_iterator<K> hash_iterator<K>::begin()
    {
        if(i != 0)
            i = -1;

        hash_iterator<K> ret(*this);

        ret.nextOccurrence();

        return ret;
    }

    template<typename K>
    hash_iterator<K> hash_iterator<K>::end() const
    {
        hash_iterator<K> ret(*this);
        ret.i = baseTable->m;
        ret.it = List_iterator<K>(nullptr);
        return ret;
    }

    template<typename K>
    hash_iterator<K> hash_iterator<K>::operator ++() //prefix
    {
        it++;

        if (baseTable->entries[i].finished(it))
        {
            it = nextOccurrence();
        }

        return *this;
    }

    template<typename K>
    hash_iterator<K> hash_iterator<K>::operator ++( int ) //postfix
    {
        hash_iterator<K> oldit(*this);

        ++(*this);

        return oldit;
    }

    template<typename K>
    K hash_iterator<K>::operator *() const
    {

        return *it;
    }

    template<typename K>
    HashTable<K>::HashTable(const int capacity)
    {
        entries = new HashList<K> [capacity];
        m = capacity;
    }
    //Creates a new hash table with given dimension

    template<typename K>
    HashTable<K>::~HashTable()
    {
        delete [] entries;
    }
    //Destructor

    template<typename K>
    HashTable<K>::HashTable()
    {
        entries = nullptr;
        m = -1;
    }

    /*
    template<typename K>
    K HashTable<K>::lookup(K k)
    {
        K key = K();
        int i = Hash(hash<K>()(k));

        if (!entries[i].empty())
            key = entries[i].lookup(k);

        return key;
    }
    //returns the value being searched if present, nil otherwise
    */

    template<typename K>
    bool HashTable<K>::contains(const K k) const
    {
        int i = Hash(hash<K>()(k));
        if(entries[i].empty())
            return false;
        else
        {
            if(entries[i].find(k) == List_iterator<K>(nullptr))
                return false;
            else
                return true;
        }
    }

    template<typename K>
    void HashTable<K>::insert(const K key) const
    {
        int i = Hash(hash<K>()(key));

        entries[i].insert(key);
    }
    //Inserts the key-value pair into the table

    template<typename K>
    void HashTable<K>::remove(const K key) const
    {
        int k = Hash(hash<K>()(key));

        if (!entries[k].empty())
            entries[k].remove(key);

    }
    //Given a key, it removes the key-pair value, if present

    template<typename K>
    int HashTable<K>::Hash(const long int key) const
    {
        return abs(key) % m;
    }
    //Hash function
}

#endif

HashPair   => std::pair
List       => std::list
HashTable  => std::unordered_map

template<typename K, typename V>
HashPair<K,V>::HashPair(const K key,const V value)
                             ^^^^^^       ^^^^^^^   Copy to parameters
    : key(key)        // Copy from parameter to key
    , value(value)    // Copy from parameter to value
{}

template<typename K, typename V>
HashPair<K,V>::HashPair(K const& key, V const& value)
    : key(key)        // Copy from parameter to key
    , value(value)    // Copy from parameter to value
{}

template<typename K, typename V>
HashPair<K,V>::HashPair(K&& key, V&& value)
    : key(std::move(key))
    , value(std::move(value))
{}

template<typename K, typename... Args>
HashPair<K,V>::HashPair(K const& key, Args&&... value)
    : key(key)
    , value(std::forward<Args>(value)...)
{}

template<typename K, typename V>
V HashPair<K,V>::getValue() const
{
    return value;   // here you are returning by value and thus
                    // causing a copy.
}

template<typename K, typename V>
V const& HashPair<K,V>::getValue() const
{
    return value;   // here you are returning by "const" reference and thus
                    // thus allowing users to read the value.
}

List_iterator<HashPair<K,V>> begin() const;
    List_iterator<HashPair<K,V>> end() const;

Using  ValueType       = std::pair<K, V>;
    Using  Container       = std::list<ValueType>;
    Using  iterator        = typename Container::iterator;
    Using  const_iterator  = typename Container::const_iterator;

    Container  list;
    const_iterator   cbegin() const;
    const_iterator   cend()   const;
    const_iterator   begin()  const;
    const_iterator   end()    const;
    iterator         begin();
    iterator         end();

bool finished(List_iterator<HashPair<K,V>> const p) const;

for(auto const& val: container)
{
    std::cout << value << "n";
}

for(auto loop = std::begin(container); loop != std::end(container); ++loop)
{
    auto const& value = *loop;
    std::cout << value << "n";
}

while(!l.finished(i) && !found)
{
    if((*i).key == key)
    {
        e = i;
        found = true;
    }

    i++;
}

while(!l.finished(i))
{
    if((*i).key == key)
    {
        e = i;
        break;   // Note the break here.
    }
    i++;
}

if((*i).key == key)

if (i->key == key)

i++;

HashList<K,V>* entries;

{
     HashTable<int, int>   x;
     HashTable<int, int>   y(x);  // Works even though you
                                  // Did not define a copy constructor
 }
 // Problem is here. You get a double delete
 // As both the destructrs try and destroies `entries` which points
 // at the same thing.

HashList<K,V>* entries;

HashList<K>* entries;

List<HashPair<K,V>> l;

List<K> l;

// Here is the template we are going to specialize.
    template<typename K, typename V>
    struct HashTableType
    {
        using ValueType = HashPair<K,V>;
    };
    // Here is the specialization when the value type is void.
    template<typename K>
    struct HashTableType<K, void>
    {
        using ValueType = K;
    };

    // Now in our main class we can use the above two classes to get
    // the correct types.
    template<typename K, typename V>
    class HashTable
    {
         using ValueType = typename HashTableType<K, V>::ValueType;
         using ListType  = typename HashList<ValueType>;

         ListType entries;
    };
    template<typename K>
    using HashSet = HashTable<K, void>;