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;
}