Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:12пми / Template / PM1 / Разреженный массив / HashSparseArray
.h
#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_ */
Соседние файлы в папке Разреженный массив