Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
17
Добавлен:
02.06.2015
Размер:
5.86 Кб
Скачать

#ifndef HASHSPARSEARRAY_H_
#define HASHSPARSEARRAY_H_

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

template <typename T1, typename T2>
class HashSparseArray
{
public:
    HashSparseArray(const unsigned size);
    virtual ~HashSparseArray();
    bool get(const T1 key, T2& value);
    bool set(const T1 key, const T2 value);
	void remove(const T1 key);
    void printLog();
	unsigned getCount();//колич-во элементов типа element
private:
    class Element
    {
    public:
        Element(const string key, const T2 value);
        virtual ~Element();
        bool set(const string key, const T2 value);
        bool get(const string key, T2& value);
		Element * remove(const string key)
		{
		    if (mKey == key)
			{
				Element *tmpPointer = mNext;
				mNext = NULL;
				return tmpPointer;
			} else
			{
				if (mNext == NULL)
				{
					return NULL;
				} else
				{
					Element* tmpPointer = mNext->remove(key);
					if(tmpPointer != mNext)
					{
						delete mNext;
						mNext = tmpPointer;
					}
				}
			}
			return this;
		};
        void printLog();
		unsigned getLength()// длина цепочки
		{
			if (mNext == NULL)
			{
				return 1;
			} else
			{
				return mNext->getLength() + 1;// (*mNext).getLength()
			}
		};
    private:
        string mKey;
        T2 mValue;
        Element *mNext;
    };

    unsigned mSize;
    Element **mArray;
    unsigned hashFunction(const string key);
};

template <typename T1, typename T2>
unsigned HashSparseArray<T1,T2>::getCount()//
{
	unsigned count=0;
	for(unsigned i=0;i<mSize;i++)
	{
		 if (mArray[i]!=NULL)
		 {
		   count += mArray[i]->getLength();
		 }
	}
	return count;
}
template <typename T1, typename T2>
HashSparseArray<T1,T2>::HashSparseArray(const unsigned size)
{
    mSize = size;
    mArray = new HashSparseArray<T1,T2>::Element*[size];
	for(unsigned i=0;i<size;i++)
	{
		mArray[i]=NULL;
	}
}

template <typename T1, typename T2>
HashSparseArray<T1,T2>::~HashSparseArray()
{
    if (mArray != NULL)
    {
        for (unsigned i = 0; i < mSize; i++)
        {
            if (mArray[i] != NULL)
            {
                cout << "delete index " << i << endl;
                delete mArray[i];
                mArray[i] = NULL;
            }
        }
        delete[] mArray;
        mArray = NULL;
    }
}

template <typename T1, typename T2>
bool HashSparseArray<T1,T2>::set(const T1 key, const T2 value)
{
    stringstream ss;
	ss << key;
	string strKey = ss.str();
	const unsigned index = hashFunction(strKey);
    if (mArray[index] == NULL)
    {
        mArray[index] = new Element(strKey, value);
    } else
    {
        return mArray[index]->set(strKey, value);
    }
    return true;
}

template <typename T1, typename T2>
bool HashSparseArray<T1,T2>::get(const T1 key, T2& value)
{
    stringstream ss;
	ss << key;
	string strKey = ss.str();
    const unsigned index = hashFunction(strKey);
    if (mArray[index] == NULL)
    {
        return false;
    } else
    {
        return mArray[index]->get(strKey, value);
    }
}

template <typename T1, typename T2>
void HashSparseArray<T1,T2>::remove(const T1 key)
{
	stringstream ss;
	ss << key;
	string strKey = ss.str();
	const unsigned index = hashFunction(strKey);
	if (mArray[index] == NULL)
    {
        return;
    } else
    {
        Element *tmpPointer = mArray[index]->remove(strKey);
		if(tmpPointer != mArray[index])
		{
			delete mArray[index];
			mArray[index] = tmpPointer;
		}
    }
}

template <typename T1, typename T2>
void HashSparseArray<T1,T2>::printLog()
{
    if (mArray != NULL)
    {
        for (unsigned i = 0; i < mSize; i++)
        {
            if (mArray[i] != NULL)
            {
                cout << "printLog index " << i << endl;
                mArray[i]->printLog();
            }
        }
    }
}

template <typename T1, typename T2>
unsigned HashSparseArray<T1,T2>::hashFunction(const string key)
{
    //return key[key.size()-1]%mSize;
	unsigned hashSum = 0;
	for(string::const_iterator it = key.begin(); it != key.end(); it++)// for() 
	{
		hashSum += *it;
		hashSum %= mSize;
	}
	return hashSum;
}

template <typename T1, typename T2>
HashSparseArray<T1,T2>::Element::Element(const string key, const T2 value):mKey(key), mValue(value), mNext(NULL)
{
}

template <typename T1, typename T2>
HashSparseArray<T1,T2>::Element::~Element()
{
    cout << "delete key " << mKey << endl;
    if (mNext != NULL)
    {
        delete mNext;
        mNext = NULL;
    }
}

template <typename T1, typename T2>
bool HashSparseArray<T1,T2>::Element::set(const string key, const T2 value)
{
    if (mKey == key)
    {
        mValue = value;
    } else
    {
        if (mNext == NULL)
        {
            mNext = new Element(key, value);
        } else
        {
            return mNext->set(key, value);
        }
    }
    return true;
}

template <typename T1, typename T2>
bool HashSparseArray<T1,T2>::Element::get(const string key, T2& value)
{
    if (mKey == key)
    {
        value = mValue;
        return true;
    } else
    {
        if (mNext == NULL)
        {
            return false;
        } else
        {
            return mNext->get(key, value);
        }
    }
}
/*
template <typename T1, typename T2>
HashSparseArray<T1,T2>::Element * HashSparseArray<T1,T2>::Element::remove(const string key)
{
    if (mKey == key)
    {
        return mNext;
    } else
    {
        if (mNext == NULL)
        {
            return NULL;
        } else
        {
            Element* tmpPointer = mNext->remove(key);
			if(tmpPointer != mNext)
			{
				delete mNext;
				mNext = tmpPointer;
			}
        }
    }
	return this;
}*/

template <typename T1, typename T2>
void HashSparseArray<T1,T2>::Element::printLog()
{
    cout << "printLog key " << mKey << endl;
    if (mNext != NULL)
    {
        mNext->printLog();
    }
}
#endif /* HASHSPARSEARRAY_H_ */
Соседние файлы в папке Разреженный массив