12пми / MyHashTable / hash простой_remove(key) / MyHashTable

#ifndef MYHASHTABLE_H_
#define MYHASHTABLE_H_

#include <iostream>
#include <climits>
using namespace std;

template <typename T>
class MyHashTable
{
public:
    MyHashTable(const unsigned size);
    virtual ~MyHashTable();
    void clear();
	bool remove(const string& key);
    bool empty();
    unsigned size();
    unsigned maxSize();
    bool get(const string& key, T& value);
    bool set(const string& key, const T value);
    void printLog();
private:
    class Element
    {
    public:
        Element(const string& key, const T value);
        virtual ~Element();
        string key;
        T value;
        Element *next;
    };

    unsigned mSize; // size of the hash table
    unsigned mCount; // number elements which are contained in the hash table
    Element **mArray;
    unsigned hashFunction(const string& key);
};

template <typename T>
MyHashTable<T>::MyHashTable(const unsigned size)
{
    mSize = size;
    //Create table of pointers
    mArray = new Element*[mSize];
    mCount = 0;
	for(unsigned i=0; i<mSize; i++)
	{
		mArray[i]=NULL;
	}
}

template <typename T>
MyHashTable<T>::~MyHashTable()
{
    if (mArray != NULL)
    {
        //Clean the hash table
        clear();
        //Erase table of pointers
        delete[] mArray;
        mArray = NULL;
    }
}

template <typename T>
bool MyHashTable<T>::remove(const string& key)
{
    const unsigned index = hashFunction(key);
	if (mArray[index] != NULL)
	{
		if (mArray[index]->key == key)
		{
			Element* del = mArray[index];
			mArray[index] = mArray[index]->next;
			delete del;
			del = NULL;
			--mCount;
			return true;
		}
		Element* el = mArray[index];
		while (el->next != NULL)
		{
			if (el->next->key == key)
			{
				Element* del = el->next;
				el->next = el->next->next;
				delete del;
				del = NULL;
				--mCount;
				return true;
			}
			el = el->next;
		}
	}
    return false;
}

template <typename T>
bool MyHashTable<T>::empty()
{
    return (!mSize);
}

template <typename T>
unsigned MyHashTable<T>::size()
{
    return mCount;
}

template <typename T>
unsigned MyHashTable<T>::maxSize()
{
    return UINT_MAX;
}

template <typename T>
void MyHashTable<T>::clear()
{
    if (mArray != NULL)
    {
        //Clean the hash table
        for (int i = 0; i < mSize; i++)
        {
            cout << "delete index " << i << endl;
            //Delete the current chain
            while (mArray[i] != NULL)
            {
                // Delete the first element
                Element* deletedElement = mArray[i];
                mArray[i] = mArray[i]->next;
                cout << "delete element key = " << (deletedElement->key);
                cout << endl;
                delete deletedElement;
                deletedElement = NULL;
            }
        }
    }
	mCount = 0;
}

template <typename T>
bool MyHashTable<T>::set(const string& key, const T value)
{
    if (mCount == maxSize())
    {
        return false;
    }

    const unsigned index = hashFunction(key);

    if (mArray[index] == NULL)
    {
        mArray[index] = new Element(key, value);
        if (mArray[index] == NULL)
		{
			return false;
		}
		mCount++;
    } else
    {
        Element *el = mArray[index];
		do
        {
            if (el->key == key)
            {
                el->value = value;
                break;
            }
            if (el->next == NULL)
            {
                el->next = new Element(key, value);
				if (el->next == NULL)
				{
					return false;
				}
                mCount++;
                break;
            }
            el = el->next;
        } while (el != NULL);
    }
    return true;
}

template <typename T>
bool MyHashTable<T>::get(const string& key, T& value)
{
    const unsigned index = hashFunction(key);

    Element* el = mArray[index];
    while(el != NULL)
    {
        if (el->key == key)
        {
            value = el->value;
            return true;
        }
        el = el->next;
    }
    return false;
}

template <typename T>
void MyHashTable<T>::printLog()
{
    if (mArray != NULL)
    {
        for (int i = 0; i < mSize; i++)
        {
            cout << "printLog index " << i << endl;
            Element* el = mArray[i];
            while(el != NULL)
            {
                cout << "printLog key = " << el->key;
                cout << endl;
                el = el->next;
            }
        }
    }
}

template <typename T>
unsigned MyHashTable<T>::hashFunction(const string& key)
{
    unsigned value = 0;
    for(string::const_iterator cit = key.begin(); cit != key.end(); ++cit)
    {
        value += *cit;
        value %= mSize;
    }
    return value;
}

template <typename T>
MyHashTable<T>::Element::Element(const string& newKey, const T newValue):key(newKey), value(newValue), next(NULL)
{
}

template <typename T>
MyHashTable<T>::Element::~Element()
{
    cout << "delete key " << key << endl;
}

#endif /* MYHASHTABLE_H_ */