Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Лабораторная работа 21 / Sketcher05 / Hash
.h#if !defined(HASH_H)
#define HASH_H
#include "stdafx.h"
#include "HashElem.h"
#include "utils.h"
#include <iostream>
using namespace std;
/*
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
pair();
pair(const T1& x, const T2& y): first(x), second(y) {}
template<class U, class V>
pair(const pair<U, V> &p);
};
*/
template<class K, class V>
class Hash {
private:
static unsigned long int count;
static unsigned long int total;
const unsigned long int id;
int maxSize;
int size;
HashElem<K, V>* t;
int h(const K& key);
int r(const K& key, int i);
int getPos(const K& key);
int rehash();
public:
class iterator;
friend class iterator;
Hash(int n = 8);
virtual ~Hash();
pair<iterator, bool> put(K key, V value);
pair<pair<K, V>, bool> remove(K key);
/*
template <class K, class V>
friend ostream& operator<< (ostream& os, const Hash<K, V>& o);
*/
/*
HashElem<K, V>& operator[](const K& key);
*/
unsigned long int getObjectId() const{
return id;
}
static unsigned long int getNumberOfObjects(){ //const
return count;
}
class iterator {
private:
Hash<K, V>* hash;
int index;
int findFirstElemPos(){
return findNextElemPos(-1);
}
int findNextElemPos(int pos){
int i = pos + 1;
bool found = false;
while (i < hash->maxSize && !found){
if (!hash->t[i].isNull())
found = true;
else
i++;
}
return i;
}
int findPrevElemPos(int pos){
int i = pos - 1;
bool found = false;
while (i > 0 && !found){
if (!hash->t[i].isNull())
found = true;
else
i--;
}
return i;
}
int findLastElemPos(){
return findNextElemPos(hash->maxSize);
}
public:
iterator(Hash<K, V>* h): hash(h), index(findFirstElemPos()) {
}
iterator(Hash<K, V>* h, int pos): hash(h), index(pos) {
}
pair<K, V> operator*() {
try {
if (index >= hash->maxSize && hash->t[hash->maxSize - 1].isNull())
index = findLastElemPos();
else if (index == 0 && hash->t[index].isNull())
index = findFirstElemPos();
else if (index >= hash->maxSize || index < 0)
throw HashException("Out of bounds");
HashElem<K, V>& el = hash->t[index];
return pair<K, V>(el.getKey(), el.getValue());
} catch(HashException e){
cout << "Hash exception thrown: " << e.what() << endl;
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
} catch(exception e) {
cout << "Exception thrown: " << e.what() << endl;
cout << "last element will be returned" << endl;
// return last element
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
}
}
pair<K, V> operator++() { // Prefix form
try {
index = findNextElemPos(index);
if (index >= hash->maxSize)
throw HashException("Out of bounds");
HashElem<K, V>& el = hash->t[index];
return pair<K, V>(el.getKey(), el.getValue());
} catch(HashException e){
cout << "Hash exception thrown: " << e.what() << endl;
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
} catch(exception e) {
cout << "Exception thrown: " << e.what() << endl;
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
}
}
pair<K, V> operator++(int) { // Postfix form
try {
int i = index;
index = findNextElemPos(index);
if (i >= hash->maxSize)
throw HashException("Out of bounds");
HashElem<K, V>& e = hash->t[i];
return pair<K, V>(e.getKey(), e.getValue());
} catch(HashException e){
// cout << "Hash exception thrown: " << e.what() << endl;
AfxMessageBox(string("Hash exception thrown: " + e.what()).c_str(), MB_OK);
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
} catch(exception e) {
cout << "Exception thrown: " << e.what() << endl;
HashElem<K, V>& el = hash->t[hash->maxSize - 1];
return pair<K, V>(el.getKey(), el.getValue());
}
}
pair<K, V> operator--(int) { // Postfix form
try {
int i = index;
index = findPrevElemPos(index);
if (i < 0)
throw HashException("Out of bounds");
HashElem<K, V>& e = hash->t[i];
return pair<K, V>(e.getKey(), e.getValue());
} catch(HashException e){
// cout << "Hash exception thrown: " << e.what() << endl;
AfxMessageBox(string("Hash exception thrown: " + e.what()).c_str(), MB_OK);
HashElem<K, V>& el = hash->t[0];
return pair<K, V>(el.getKey(), el.getValue());
} catch(exception e) {
cout << "Exception thrown: " << e.what() << endl;
HashElem<K, V>& el = hash->t[0];
return pair<K, V>(el.getKey(), el.getValue());
}
}
// To see if you're at the end:
bool operator==(const iterator& it) const {
return index == it.index;
}
bool operator!=(const iterator& it) const {
return index != it.index;
}
friend ostream& operator<<(ostream& os, const iterator& it) {
return os << *it;
}
};
class HashException{
private:
string str;
public:
HashException(string s): str(s) {}
string what(){
return str;
}
};
iterator begin() {
return iterator(this);
}
iterator end() {
return iterator(this, maxSize);
}
iterator find(const K& key) {
int p = getPos(key);
return iterator(this, (p >= 0)? p: maxSize);
}
bool empty(){
return (size == 0);
}
int getSize() {
return size;
}
int getMaxSize() {
return maxSize;
}
void Serialize(CArchive& ar);
private:
iterator it;
public:
iterator& getIterator(){
return it;
};
};
/*
template <class K, class V>
ostream& operator<<(ostream& os, const Hash<K, V>& o){
os << "size: " << o.size << endl;
os << "array:" << endl;
for (int i = 0; i < o.size; i++){
os << o.t[i] << endl;
}
return os;
}
*/
template<class K, class V>
unsigned long int Hash<K, V>::count = 0;
template<class K, class V>
unsigned long int Hash<K, V>::total = 0;
template<class K, class V>
Hash<K, V>::Hash(int n): id(++total), it(this, 0){
count++;
cout << "create Hash#" << id << endl;
maxSize = n;
size = 0;
t = new HashElem<K, V>[maxSize];
}
template<class K, class V>
Hash<K, V>::~Hash() {
count--;
cout << "destroy Hash#" << id << endl;
delete[] t;
t = NULL;
}
template<class K, class V>
int Hash<K, V>::h(const K& key) {
return key.hashCode() % maxSize;
}
template<class K, class V>
int Hash<K, V>::r(const K& key, int i) {
return (key.hashCode() + i) % maxSize;
}
template<class K, class V>
int Hash<K, V>::getPos(const K& key) {
int i = 0;
int p = h(key);
if (t[p].isNull())
return -1;
if (t[p].getKey() == key)
return p;
i = 1;
int p1;
do{
p1 = r(key, i);
if (t[p1].isNull() || p == p1)
return -1;
if (t[p1].getKey() == key)
return p1;
i++;
}while(1);
}
template<class K, class V>
int Hash<K, V>::rehash() {
try{
int newSize = maxSize*2;
HashElem<K, V>* t2 = new HashElem<K, V>[newSize];
for(int i = 0; i < this->maxSize; i++)
t2[i].set(t[i].getKey(), t[i].getValue());
delete[] t;
t = t2;
this->maxSize = newSize;
return 1;
} catch(exception e) {
cout << "Rehash failed" << endl;
cout << "Exception thrown: " << e.what() << endl;
return 0;
}
}
template<class K, class V>
pair<Hash<K, V>::iterator, bool> Hash<K, V>::put(K key, V value) {
int i = 0;
int p = h(key);
int keyPos = getPos(key);
if (keyPos >= 0){
//pair = new Pair<K, V>(&t[p].getKey(), t[p].getValue());
//t[keyPos].set(key, value);
return pair<iterator, bool>(end(), false);
}
if (size + 1 > maxSize){
cout << "rehash needed" << endl;
int s = rehash();
if (s == 0)
return pair<iterator, bool>(end(), false);
}
if (t[p].isNull()){
t[p].set(key, value);
size++;
return pair<iterator, bool>(iterator(this, p), true);
}
i = 1;
int p1;
do{
p1 = r(key, i);
if (t[p1].isNull()){
t[p1].set(key, value);
size++;
return pair<iterator, bool>(iterator(this, p1), true);
}
if (p == p1){
cout << "shit happened" << endl;
return pair<iterator, bool>(end(), false);
}
i++;
}while(1);
}
template<class K, class V>
pair<pair<K, V>, bool> Hash<K, V>::remove(K key) {
pair<pair<K, V>, bool> res(pair<K, V>(), false);
int pos = getPos(key);
if (pos >= 0){
if (&t[pos].getValue() != NULL){
size--;
t[pos].setNull();
res.first = pair<K, V>(t[pos].getKey(), t[pos].getValue());
res.second = true;
}
}
return res;
}
template<class K, class V>
void Hash<K, V>::Serialize(CArchive& ar)
{
if (ar.IsStoring()){
ar << maxSize
<< size;
// save only not null elements
// it'll look like this:
// 1 << {HashElem} << 4 << {HashElem} ...
for (int i = 0; i < maxSize; i++){
if (!t[i].isNull()){
ar << i;
t[i].Serialize(ar);
}
}
}
else{
ar >> maxSize
>> size;
// allocate storage
t = new HashElem<K, V>[maxSize];
// make em null
for (int i = 0; i < size; i++){
t[i].setNull();
}
// now load all HashElements
for (int j = 0; j < size; j++){
int n;
ar >> n;
t[n].Serialize(ar);
}
}
//TODO: save iterator
}
/*
template<class K, class V>
HashElem<K, V>& Hash<K, V>::operator[](const K& key) {
int p = getPos(key);
HashElem<K, V>* el = (p >= 0)? &t[p]: NULL;
return *el;
}
*/
#endif
Соседние файлы в папке Sketcher05