uups, sorry, habe es gar nicht gesehen.
anbei dynamic_hashing.h
#define ulint unsigned long long int
#define uint unsigned int
#include <string>
#include <fstream>
#include <cstdio>
#include "Bucket.h"
#include "RadixTrie.h"
#include "Article.h"
#include "Dynamic_Hashing_Exception.h"
using namespace std;
template <uint size, uint modFac>
class Dynamic_Hashing
{
private:
string fileName;
fstream fileStream;
Bucket<size> buck;
RadixTrie radi;
int hash(int a)
{
return a % modFac;
}
ulint getBucketPos(ulint bucketNumber)
{
return size * Article::getSize() * bucketNumber;
}
public:
Dynamic_Hashing(string name)
{
fileName = name;
fileStream.open(fileName.c_str(), ios::in | ios::out | ios::binary | ios::ate);
if (!fileStream.is_open())
{
fstream createFile;
createFile.open(fileName.c_str(), fstream::out |fstream::binary);
try
{
buck.write(createFile,0);
}
catch (Dynamic_Hashing_Exception ex)
{
cout << ex.getMessage() << " " << ex.getCause() << endl;
}
createFile.flush();
createFile.close();
}
else
{
// getting the file size
uint fileSize = fileStream.tellg();
// getting number of article
int artNum = fileSize/Article::getSize();
Article * arti[artNum];
// resetting filePointer
fileStream.seekg(ios::beg);
// getting articles
for (int i = 0; i < artNum; i++)
{
Article * a = new Article(fileStream);
arti[i] = a;
}
fileStream.close();
remove(fileName.c_str());
fstream createFile;
createFile.open(fileName.c_str(), fstream::out |fstream::binary);
buck.write(createFile,0);
createFile.flush();
createFile.close();
//writin' all 'em real ones back
for (int i = 0; i < artNum; i++)
{
if (arti[i]->getArticleNumber() != 0)
{
insert(arti[i]);
}
}
}
fileStream.flush();
fileStream.close();
}
void insert(Article * art);
Article * retrieve(int artNum);
void display();
};
template <uint size, uint modFac>
void Dynamic_Hashing<size,modFac>::insert (Article * a)
{
if (retrieve(a->getArticleNumber()) != NULL)
{
cout << "Article with Article Number " << a->getArticleNumber() << " already exists!" << endl;
return;
}
cout << "inserting Article with Hash " << hash(a->getArticleNumber()) << endl;
if (a->getArticleNumber() == 0)
{
throw Dynamic_Hashing_Exception("Article Number musst not be 0!");
}
fileStream.open(fileName.c_str(), ios::in | ios::out | ios::binary);
if (!fileStream.is_open())
{
throw Dynamic_Hashing_Exception("i/o exception while opening file");
}
int buckNum;
//retrieving bucket
if (radi.getExtNodeCount() == 1)
{
buckNum = 0;
}
else
{
buckNum = radi.retrieve(hash(a->getArticleNumber()));
}
int curDepth = radi.getSearchDepth();
// get the bucket
buck.read(fileStream,getBucketPos(buckNum));
//ist the bucket full?
if (!buck.isFull())
{
//no
//insert adress in bucket->done
buck.addArticle(a);
try
{
buck.write(fileStream, getBucketPos(buckNum));
}
catch (Dynamic_Hashing_Exception e)
{
//todo
cout << "Dynamic_Hashing_Exception: writing bucket" << endl;
}
}
else
{
//yes
Bucket<size> newBuc;
Bucket<size> oldBuc;
//split buckets
for (int i = 0; i < size; ++i)
{
Article * art = buck.getArticle(i);
if ((hash(art->getArticleNumber()) >> curDepth) & 1 == 1)
{
newBuc.addArticle(art);
}
else
{
oldBuc.addArticle(art);
}
}
bool wasFull = false;
// add new article to right bucket
if ((hash(a->getArticleNumber()) >> curDepth) & 1 == 1)
{
if(!newBuc.isFull())
{
newBuc.addArticle(a);
}
else
{
wasFull = true;
}
}
else
{
if(!oldBuc.isFull())
{
oldBuc.addArticle(a);
}
else
{
wasFull = true;
}
}
int newBuckNum = radi.getExtNodeCount();
oldBuc.write(fileStream, getBucketPos(buckNum));
newBuc.write(fileStream, getBucketPos(newBuckNum));
if(wasFull)
{
if ((hash(a->getArticleNumber()) >> curDepth + 1) & 1 == 1) {
radi.insert(hash(a->getArticleNumber()),buckNum);
} else {
radi.insert(hash(a->getArticleNumber()),newBuckNum);
}
this->insert(a);
}
else
{
radi.insert(hash(newBuc.getArticle(0)->getArticleNumber()),newBuckNum);
}
}
fileStream.flush();
fileStream.close();
};
template <uint size, uint modFac>
Article * Dynamic_Hashing<size,modFac>::retrieve (int artNum)
{
int buckNum = radi.retrieve(hash(artNum));
fileStream.open(fileName.c_str() ,ios::binary | ios::in | ios::out);
if (!fileStream.is_open())
{
throw Dynamic_Hashing_Exception("i/o exception while opening file");
}
buck.read(fileStream,getBucketPos(buckNum));
fileStream.flush();
fileStream.close();
for (int i = 0; i < buck.getCurrentArticles(); ++i)
{
Article * a = buck.getArticle(i);
if (a->getArticleNumber() == artNum)
{
return a;
}
}
return NULL;
}
template<uint size, uint modFac>
void Dynamic_Hashing<size,modFac>::display()
{
fileStream.open(fileName.c_str() ,ios::binary | ios::in | ios::ate);
// getting the file size
ulint fileSize = fileStream.tellg();
// getting number of article
int artNum = fileSize/Article::getSize();
// resetting filePointer
fileStream.seekg(ios::beg);
// getting articles
for (ulint i = 0; i < artNum; i++)
{
if( i == 0) {
cout << "Bucket " << i << endl;
}
else if(i % size == 0) {
cout << "Bucket " << i / size << endl;
}
Article * a = new Article(fileStream);
a->display();
}
fileStream.close();
}
bucket.h
/**
* This is the Bucket class for the Dynamic_Hashing Project.
*
*/
#ifndef _BUCKET_H_
#define _BUCKET_H_
#include <string>
#include <fstream>
#include <sstream>
#include "Article.h"
#include "Dynamic_Hashing_Exception.h"
template<uint size>
class Bucket
{
private:
Article *articles[size];
uint currentArticles;
public:
Bucket()
{
currentArticles = 0;
}
void read(std::fstream & inputStream, ulint pos) ;
void addArticle(Article *art) ;
Article* getArticle(uint i);
void write(std::fstream & stream, ulint pos) ;
uint getCurrentArticles()
{
return currentArticles;
}
bool isFull()
{
return currentArticles == size;
}
};
template <uint size>
void Bucket<size>::addArticle(Article *art)
{
if (currentArticles == size)
{
throw Dynamic_Hashing_Exception("Bucket is full.");
}
articles[currentArticles] = art;
++currentArticles;
}
template<uint size>
Article* Bucket<size>::getArticle(uint i)
{
if (i >= currentArticles)
{
throw Dynamic_Hashing_Exception("Article index out of bounds.");
}
return articles[i];
}
template<uint size>
void Bucket<size>::read(std::fstream & stream, ulint pos)
{
stream.seekg(pos);
currentArticles = 0;
for (int art = 0; art < size; ++art)
{
articles[art] = new Article(stream);
if (articles[art]->getArticleNumber() != 0)
{
++currentArticles;
}
}
}
template<uint size>
void Bucket<size>::write(std::fstream & stream, ulint pos)
{
if (!stream.is_open())
{
throw Dynamic_Hashing_Exception("Stream is not open.");
}
stream.seekp(pos);
if (stream.fail())
{
throw Dynamic_Hashing_Exception("Position seems out of bounds. Stream in fail state.");
}
Article* nullArticle = new Article(0,"",0);
for (uint art = 0; art < size; ++art)
{
if (art < currentArticles)
{
articles[art]->write(stream);
}
else
{
nullArticle->write(stream);
}
}
}
#endif /* _BUCKET_H_ */
