Skip to content

Instantly share code, notes, and snippets.

@kdungs
Created May 14, 2012 20:25
Show Gist options
  • Save kdungs/2696527 to your computer and use it in GitHub Desktop.
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...
#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;
}
#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