
lexicon
lexicon
#include <iostream>
using namespace std;
class lexicon{
protected:
string *key;
int freq;
lexicon *left, *right;
bool isempty() const
{
return key == 0;
}
void del()
{
if(isempty()) return;
if((*left).isempty() && (*right).isempty())
{
key = 0;
}
else if(!(*left).isempty() && (*right).isempty())
{
string * tempkey = key;
lexicon * tempright = right;
key = left->key;
freq = left->freq;
right = left->right;
left = left->left;
}
else if((*left).isempty() && !(*right).isempty())
{
string *tempkey = key;
lexicon *templeft = left;
key = right->key;
freq = right->freq;
left = right->left;
right = right->right;
}
else if(!(*left).isempty() && !(*right).isempty())
{
lexicon *p = left;
while(!(*(p->right)).isempty()) p = p->right;
*key = *(p->key); /* copy to root */
freq = p->freq;
(*p).del();
}
}
lexicon * find(const string &s)
{
if(isempty()) return new lexicon;
string tempstring = s;
if(tempstring.compare(*key) == 0)
{
return this;
}
else if(tempstring.compare(*key) < 0)
{
return (*left).find(tempstring);
}
else
{
return (*right).find(tempstring);
}
}
public:
lexicon() :
key(0),
freq(0),
left(0),
right(0)
{}
~lexicon()
{
delete key;
delete left;
delete right;
}
void insert(const string &s)
{
string tempstring = s;
if(isempty())
{
key = new string;
*key = tempstring;
freq = 1;
left = new lexicon;
right = new lexicon;
}
else
{
if(tempstring == *key)
{
freq++;
}
else if(tempstring < *key)
{
(*left).insert(tempstring);
}
else
{
(*right).insert(tempstring);
}
}
}
int lookup(const string &s)
{
if(isempty())
{
return 0;
}
string tempstring = s;
if(tempstring.compare(*key) == 0)
{
return freq;
}
else if(tempstring.compare(*key) < 0)
{
return (*left).lookup(tempstring);
}
else
{
return (*right).lookup(tempstring);
}
}
int depth(const string &s)
{
if(isempty()) return 0;
string tempstring = s;
if(tempstring.compare(*key) == 0)
{
return 1;
}
else if(tempstring.compare(*key) < 0)
{
if((*left).depth(tempstring) == 0) return 0;
else return (*left).depth(tempstring) + 1;
}
else
{
if((*right).depth(tempstring) == 0) return 0;
else return (*right).depth(tempstring) + 1;
}
}
void replace(const string &s1, const string &s2)
{
lexicon *p = find(s1);
if((*p).isempty()) return;
int saved_freq = p->freq;
(*p).del();
/* find s2*/
lexicon *target = find(s2);
if((*target).isempty()) /* if s2 was not found */
{
insert(s2);
target = find(s2);
target->freq += saved_freq - 1; /* It is already increased by 1 when inserted */
}
else
{
target->freq += saved_freq;
}
}
friend ostream & operator << (ostream &out, const lexicon &l)
{
if(l.isempty())
{
return out;
}
if( (*(l.left)).isempty() && (*(l.right)).isempty())
{
out << *(l.key) << " " << l.freq << endl;
}
else if( !(*(l.left)).isempty() && (*(l.right)).isempty() )
{
out << *(l.left);
out << *(l.key) << " " << l.freq << endl;
}
else if( (*(l.left)).isempty() && !(*(l.right)).isempty() )
{
out << *(l.key) << " " << l.freq << endl;
out << *(l.right);
}
else
{
out << *(l.left);
out << *(l.key) << " " << l.freq << endl;
out << *(l.right);
}
return out;
}
};
// this is not part of the solution
// it is imported in case you want to check your code
int main()
{
lexicon l;
l.insert("the");
l.insert("boy");
l.insert("and");
l.insert("the");
l.insert("wolf");
cout << l;
cout << "The word 'and' is found " << l.lookup("and") << " time(s) at depth " << l.depth("and") << endl;
cout << "The word 'boy' is found " << l.lookup("boy") << " time(s) at depth " << l.depth("boy") << endl;
cout << "The word 'the' is found " << l.lookup("the") << " time(s) at depth " << l.depth("the") << endl;
cout << "The word 'wolf' is found " << l.lookup("wolf") << " time(s) at depth " << l.depth("wolf") << endl;
cout << "The word 'dummy' is found " << l.lookup("dummy") << " time(s) at depth " << l.depth("dummy") << endl;
l.replace("and", "dummy");
cout << "The word 'wolf' is now found " << l.lookup("wolf") << " time(s) at depth " << l.depth("wolf") << endl;
cout << "The word 'dummy' is now found " << l.lookup("dummy") << " time(s) at depth " << l.depth("dummy") << endl;
l.replace("boy", "dummy");
cout << "The word 'wolf' is now found " << l.lookup("wolf") << " time(s) at depth " << l.depth("wolf") << endl;
cout << "The word 'dummy' is now found " << l.lookup("dummy") << " time(s) at depth " << l.depth("dummy") << endl;
l.replace("the", "dummy");
cout << "The word 'wolf' is now found " << l.lookup("wolf") << " time(s) at depth " << l.depth("wolf") << endl;
cout << "The word 'dummy' is now found " << l.lookup("dummy") << " time(s) at depth " << l.depth("dummy") << endl;
l.replace("wolf", "dummy");
cout << "The word 'wolf' is now found " << l.lookup("wolf") << " time(s) at depth " << l.depth("wolf") << endl;
cout << "The word 'dummy' is now found " << l.lookup("dummy") << " time(s) at depth " << l.depth("dummy") << endl;
cout << l << endl;
cout << "#end#" << endl;
return 0;
}