// HashSet.hpp
//
// ICS 46 Spring 2015
// Project #3: Set the Controls for the Heart of the Sun
//
// A HashSet is an implementation of a Set that is a separately-chained
// hash table, implemented as a dynamically-allocated array of linked
// lists.  At any given time, the HashSet has a "size" indicating
// how many elements are stored within it, along with a "capacity"
// indicating the size of the array.
//
// As elements are added to the HashSet and the proportion of the HashSet's
// size to its capacity exceeds 0.8 (i.e., there are more than 80% as many
// elements as there are array cells), the HashSet should be resized so
// that it is twice as large as it was before.
//
// You are not permitted to use the containers in the C++ Standard Library
// (such as std::vector, std::list, or std::array).  Instead, you'll need
// to use a dynamically-allocated array and your own linked list
// implementation; the linked list doesn't have to be its own class,
// though you can do that, if you'd like.

#ifndef HASHSET_HPP
#define HASHSET_HPP

#include <functional>
#include "Set.hpp"



template <typename T>
class HashSet : public Set<T>
{
public:
    // The default capacity of the HashSet before anything has been
    // added to it.
    static constexpr unsigned int DEFAULT_CAPACITY = 10;

    // A HashFunction
    typedef std::function<unsigned int(const T&)> HashFunction;

public:
    // Initializes a HashSet to be empty, so that it will use the given
    // hash function whenever it needs to hash an element.
    HashSet(HashFunction hashFunction);

    // Cleans up the HashSet so that it leaks no memory.
    virtual ~HashSet();

    // Initializes a new HashSet to be a copy of an existing one.
    HashSet(const HashSet& s);

    // Assigns an existing HashSet into another.
    HashSet& operator=(const HashSet& s);


    // isImplemented() should be modified to return true if you've
    // decided to implement a HashSet, false otherwise.
    virtual bool isImplemented() const;


    // add() adds an element to the set.  If the element is already in the set,
    // this function has no effect.  This function triggers a resizing of the
    // array when the ratio of size to capacity would exceed 0.8.  In the case
    // where the array is resized, this function runs in linear time (with
    // respect to the number of elements, assuming a good hash function);
    // otherwise, it runs in constant time (again, assuming a good hash
    // function).
    virtual void add(const T& element);


    // contains() returns true if the given element is already in the set,
    // false otherwise.  This function runs in constant time (with respect
    // to the number of elements, assuming a good hash function).
    virtual bool contains(const T& element) const;


    // size() returns the number of elements in the set.
    virtual unsigned int size() const;

    struct elementLink{
        T item;
        T name;
        elementLink* next;
    };

private:
    HashFunction hashFunction;

    //lam
    unsigned int currentCap;
    elementLink** storage; //array that stores pointer to elementLink
    void resize(); //resize storage


};

template <typename T>
int HashSet<T>::counter = 0;

template <typename T>
HashSet<T>::HashSet(HashFunction hashFunction)
    : hashFunction{hashFunction}
{
    //lam
    currentCap = DEFAULT_CAPACITY;
    storage = new elementLink*[currentCap];
}


template <typename T>
HashSet<T>::~HashSet()
{
    delete hashTable[];
}


template <typename T>
HashSet<T>::HashSet(const HashSet& s)
    : hashFunction{s.hashFunction}
{
    currentCap = s.currentCap;
    storage = s.storage;
}


template <typename T>
HashSet<T>& HashSet<T>::operator=(const HashSet& s)
{
    if (this != &s)
    {
        hashFunction = s.hashFunction;
    }

    return *this;
}


template <typename T>
bool HashSet<T>::isImplemented() const
{
    return false;
}


template <typename T>
void HashSet<T>::add(const T& element)
{
    //lam
    unsigned int hashResult = hashFunction(element);
    if(storage[hashResult] != NULL) //something is there already
    {
        if(contains(element)) //the same one
        {
            return; //nothing happen
        }
        else //not the same
        {
            resize();

            unsigned int index = hashResult;
            while(storage[index]->next != NULL) //keep looking until find an empty cell, empty cell being storage[index]->next
            {
                index++;
                index = index%currentCap; //will loop back to 0 if index = currentCap
            }
            storage[(index+1)%currentCap] = &element; //put element into empty cell
            storage[index]->next = &element; //adjust previous cell's next pointer to correctly point at newly added element, maybe not needed
            element->next = storage[(index+2)%currentCap; //newly added element's next pointer points to next cell
        }
    }
    else //nothing there, add like normal
    {
        resize();

        storage[hashResult] = &element;
        element.next = storage[(hashResult+1)%currentCap];
        if(storage[(hashResult-1)%currentCap] != NULL) //if previous node exists then change its next pointer accordingly
            storage[(hashResult-1)%currentCap]->next = &element;
    }
}


template <typename T>
bool HashSet<T>::contains(const T& element) const
{
    //lam
    unsigned int hashResult = hashFunction(element);
    if(storage[hashResult] != NULL) //something is there already
    {
        if(storage[hashResult]->item == element.item && storage[hashResult]->name == element.name) //the same one
        {
            return true;
        }
        else
        {
            unsigned int index = (hashResult+1)%currentCap;
            while(storage[index] != NULL)
            {
                if(storage[index]->item == element.item && storage[index]->name == element.name)
                    return true;
                else
                {
                    index++;
                    index = index%currentCap;
                }
            }
            return false;
        }
    }
    else
    {
        return false;
    }
}

template <typename T>
unsigned int HashSet<T>::size() const
{
    unsigned int count = 0;
    int i = 0;
    while(i < currentCap)
    {
        if(storage[i] != NULL) count++;
        i++;
    }
    return count;
}

//lam
template <typename T>
void HashSet<T>::resize()
{
    currentCap = currentCap*2;
    elementLink** newStorage;
    newStorage = new elementLink*[currentCap];

    int i = 0;
    while(i < currentCap/2)
    {
        newStorage[i] = storage[i];
        i++;
    }
    delete[] storage;
    storage = newStorage;
}

#endif // HASHSET_HPP