Created
May 14, 2012 20:25
-
-
Save kdungs/2696527 to your computer and use it in GitHub Desktop.
I just found this among my backups. I implemented this in year 2008 as a high school student attending a lecture at university. It's an English-German-dictionary implemented through a skiplist. I don't know if this works, but it might have back then...
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "Skiplist.h" | |
#include <iostream> | |
#include <fstream> | |
using namespace std; | |
int main(int argc, char ** argv) | |
{ | |
Dictionary dict; | |
static char QUIT = 'q'; | |
string line; | |
if(!dict.loadFromFile("english-german.txt")) | |
{ | |
cout << "File could not be load!" << endl; | |
return -1; | |
} | |
getline(cin, line); | |
while(line[0] != QUIT) | |
{ | |
if(line[0] == 'l' && line.size() > 2) | |
{ | |
// lookup | |
string s = line.substr(2); | |
dict.output(s); | |
} | |
else if(line[0] == 'i' && line.size() > 2) | |
{ | |
// insert | |
string *eng, *ger; | |
int space; | |
eng = new string(); | |
ger = new string(); | |
line = line.substr(2); | |
space = line.find(" "); | |
if(space > 2) | |
{ | |
*eng = line.substr(0, space); | |
*ger = line.substr(space+1); | |
//cout << *eng << " + " << *ger << endl; | |
dict.insert(eng, ger); | |
} | |
else | |
cout << "Word could not be inserted." << endl; | |
} | |
else if(line[0] == 'd' && line.size() > 2) | |
{ | |
// delete | |
string eng = line.substr(2); | |
dict.remove(eng); | |
} | |
else if(line[0] == 'o') | |
dict.outputAll(); | |
getline(cin, line); | |
} | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <fstream> | |
#include <string> | |
#include <list> | |
using namespace std; | |
const string INFIN = "zzzzzzzzzz"; | |
// Declaration of the container class for an element of the skiplist | |
class Translation | |
{ | |
friend class Dictionary; | |
private: | |
string eng; | |
list<string> ger; | |
Translation **next; | |
int height; | |
public: | |
Translation(string, string, int); | |
~Translation(); | |
void output(); | |
}; | |
// Declaration of the skiplist class, specified as Dictionary | |
class Dictionary | |
{ | |
private: | |
Translation *head, *tail; | |
int height; | |
int randomHeight(); | |
Translation **resizeArray(Translation**, int, int); | |
public: | |
Dictionary(); | |
~Dictionary(); | |
Translation *search(string); | |
void insert(string*, string*); | |
void remove(string); | |
void output(string); | |
void outputAll(); | |
bool loadFromFile(const char*); | |
}; | |
// Implementation of classes methods | |
Translation::Translation(string e, string g, int h) | |
{ | |
eng = e; | |
ger.push_front(g); | |
next = new Translation*[h]; | |
height = h; | |
} | |
Translation::~Translation() | |
{ | |
delete [] next; | |
} | |
void Translation::output() | |
{ | |
cout << eng << " = "; | |
cout << ger.front(); | |
if(ger.size() > 1) | |
{ | |
list<string>::iterator g; | |
for(g = ++ger.begin(); g != ger.end(); g++) | |
cout << ", " << *g; | |
} | |
cout << endl; | |
} | |
int Dictionary::randomHeight() | |
{ | |
int h = 1; | |
while(rand() % 2 != 0) | |
h++; | |
return h; | |
} | |
Translation **Dictionary::resizeArray(Translation** l, int hOld, int hNew) | |
{ | |
Translation **help = new Translation*[hNew]; | |
for(int i=0; i<hOld; i++) | |
help[i] = l[i]; | |
return help; | |
} | |
Dictionary::Dictionary() | |
{ | |
head = new Translation("", "", 1); | |
tail = new Translation(INFIN, INFIN, 1); | |
head->next[0] = tail; | |
height = 1; | |
} | |
Dictionary::~Dictionary() | |
{ | |
Translation *p, *t; | |
p = head->next[0]; | |
t = head->next[0]; | |
while(t != tail) | |
{ | |
p = t; | |
t = p->next[0]; | |
delete p; | |
} | |
delete head; | |
delete tail; | |
} | |
Translation *Dictionary::search(string s) | |
{ | |
Translation *p; | |
p = head; | |
for(int i=height-1; i>=0; i--) | |
while(p->next[i]->eng.compare(s) < 0) | |
p = p->next[i]; | |
p = p->next[0]; | |
if(p->eng.compare(s) == 0) | |
return p; | |
else | |
return tail; | |
} | |
void Dictionary::insert(string *e, string *g) | |
{ | |
Translation **update = new Translation*[height]; | |
Translation *p; | |
p = head; | |
for(int i = height-1; i >= 0; i--) | |
{ | |
while(p->next[i]->eng.compare(*e) < 0) | |
{ | |
p = p->next[i]; | |
} | |
update[i] = p; | |
} | |
p = p->next[0]; | |
if(p->eng.compare(*e) == 0) | |
p->ger.push_front(*g); | |
else | |
{ | |
int h = randomHeight(); | |
if(h > height) | |
{ | |
update = resizeArray(update, height, h); | |
head->next = resizeArray(head->next, height, h); | |
for(int i=height; i<h; i++) | |
{ | |
update[i] = head; | |
head->next[i] = tail; | |
} | |
height = h; | |
} | |
p = new Translation(*e,*g,h); | |
for(int i=0; i<h; i++) | |
{ | |
p->next[i] = update[i]->next[i]; | |
update[i]->next[i] = p; | |
} | |
} | |
delete [] update; | |
} | |
void Dictionary::remove(string s) | |
{ | |
Translation **update = new Translation*[height]; | |
Translation *p; | |
p = head; | |
for(int i = height-1; i >= 0; i--) | |
{ | |
while(p->next[i]->eng.compare(s) < 0) | |
{ | |
p = p->next[i]; | |
} | |
update[i] = p; | |
} | |
p = p->next[0]; | |
if(p->eng.compare(s) == 0) | |
{ | |
for(int i=0; i<p->height; i++) | |
update[i]->next[i] = p->next[i]; | |
while(height >= 0 && head->next[height-1]->eng.compare(INFIN) == 0) | |
height = height-1; | |
delete p; | |
} | |
delete [] update; | |
} | |
void Dictionary::output(string s) | |
{ | |
Translation *t = search(s); | |
if(t == tail) | |
cout << s << " could not be found." << endl; | |
else | |
t->output(); | |
} | |
void Dictionary::outputAll() | |
{ | |
Translation *p; | |
p = head; | |
p = p->next[0]; | |
while(p->eng.compare(tail->eng) != 0) | |
{ | |
if(p->eng != "") | |
p->output(); | |
p = p->next[0]; | |
} | |
} | |
bool Dictionary::loadFromFile(const char* filename) | |
{ | |
ifstream f; | |
string s, e, g; | |
int i = 0; | |
f.open(filename); | |
if(f.bad()) | |
return false; | |
while(!f.eof()) | |
{ | |
getline(f,s); | |
i = s.find("\t"); | |
//cout << i << endl; | |
e = s.substr(0, i); | |
//cout << e << endl; | |
while(i < s.size()) | |
{ | |
i++; | |
if(s[i] == ',' || s[i] == ';') | |
{ | |
insert(&e,&g); | |
g = ""; | |
i++; | |
} | |
else | |
g += s[i]; | |
} | |
//cout << g << endl; | |
insert(&e,&g); | |
e = g = s = ""; | |
} | |
f.close(); | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment