//  Made by  Levy  Michael i.d. 306047036.
//  This   work    took from me two days of my life.


#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream.h>

#define MS 257

typedef struct string_tree_node
{
   int len;
   char string[256];
   struct string_tree_node* ge;  // greater or equal length
   struct string_tree_node* lt; //  less length
} STNODE;

void    st_print( STNODE* tree);
STNODE* st_insert( STNODE* tree, char* str);
int     st_lookup_len( STNODE* tree, int ln);
int     st_lookup_string( STNODE* tree, char* str);
STNODE* st_remove_len( STNODE* tree, int ln);
STNODE* st_remove_string(STNODE* ,char* str);
STNODE* detach_min( STNODE* node,STNODE prev0 );

int main()
{
     clrscr();
     static char* strings[] =
      {
	   "etc. etc. etc.",
	   "bbbb",
	   "ccc",
	   "I love long strings",
	   "i love long strings",
	   "I hate short strings",
	   "aaa",
	   "whatever you want ",
	   "123456789012345678901234567",
	   "string with the same length",
	   "string with the same length",
	   "etc, etc, etc.",
	   "I like C,but more C++",
	   "I love you baby  ! " ,
	   "nnn",
	   "I am a happy woman" ,
	   NULL
      };
      STNODE* tree = NULL;
      int i,n;

      for(i=0;strings[i]!=NULL; i++)
	{    tree = st_insert(tree,strings[i]);    }
	     st_print( tree );

      printf( "[%d]\n", st_lookup_len( tree,3));
      printf( "[%d]\n", st_lookup_len( tree,4));
      printf( "[%d]\n", st_lookup_len( tree,5));
      printf( "[%d]\n", st_lookup_string( tree, strings[5]));
      printf( "[%d]\n", st_lookup_string( tree,"no such"));
getch();

/*      tree = st_remove_len(tree,27);
      st_print(tree);
      cout<<"\n";
getch();
       tree = st_remove_len(tree,3);
       st_print(tree);
       cout<<"\n";
getch();
	tree = st_remove_len(tree,19);
	st_print(tree);
	cout<<"\n";
getch();
	tree = st_remove_len(tree,14);
	st_print(tree);
	cout<<"\n";
getch();
      tree = st_remove_len(tree,0);
      st_print(tree);
      cout<<"\n";                          */
      getch();
      tree = st_remove_string( tree,strings[8]);
      st_print(tree);
      return(0);
}


STNODE* detach_min( STNODE* node,STNODE* prev0 )
{
   STNODE *n;
   STNODE *prev = prev0;

   for(n=node; n->lt != NULL ; n=n->lt)
       prev=n;
   if( prev ==prev0 )
	prev->ge = prev->ge->ge;
   else
       prev->lt = n->ge;
   return(n);
}


STNODE* st_remove_len( STNODE* tree, int ln)
{
   STNODE* temp;

   if(tree == NULL)
       return (NULL);
   if(tree->len > ln)
       tree->lt = st_remove_len(tree->lt,ln);
   else if(tree->len < ln)
       tree->ge = st_remove_len(tree->ge,ln);
	else    // when  :  len==ln;
	   {
 lable1:    if(tree->ge == NULL)
	    {
	       temp=tree;
	       tree=tree->lt;
	       free(temp);
	    }


	    else
	       {
		if(tree->lt == NULL)
		{
		  do
		  {
		     temp=tree;
		     tree=tree->ge;
		     free(temp);

		}
		   while( (tree != NULL) && (tree->len == ln));
		}
		else
		    {

		       do
		       {
			 temp = detach_min(tree->ge,tree);
			 temp->ge=tree->ge;
			 temp->lt=tree->lt;
			 free(tree);
			 tree=temp;
		       }
			while((tree->len == ln)&&(tree->ge!=NULL)  );
			if(tree->ge == NULL)  goto lable1;
		    }
	       }
	 }
return(tree);
}


STNODE* st_remove_string(STNODE* tree,char* str)
{
    int ln;
    ln=strlen(str);
    STNODE* temp;

   if(tree == NULL)
       return (NULL);
   if(tree->len > ln)
       tree->lt = st_remove_len(tree->lt,ln);
   else if(tree->len < ln)
       tree->ge = st_remove_len(tree->ge,ln);
	else    // when  :  len==ln;
	   {
 lable1:    if(tree->ge == NULL)
	    {
	       if ((strcmp(tree->string,str) == 0))
		{
		  temp=tree;
		  tree=tree->lt;
		  free(temp);
		}
	    }


	    else
	       {
		if(tree->lt == NULL)
		{
		  do
		  {
		    if ((strcmp(tree->string,str) == 0))
		     {
		       temp=tree;
		       tree=tree->ge;
		       free(temp);
		     }
		  }
		   while( (tree != NULL) && (tree->len == ln));
		}
		else
		    {

		       do
		       {
			  if (strcmp(tree->string,str) == 0)
			  {
			   temp = detach_min(tree->ge,tree);
			   temp->ge=tree->ge;
			   temp->lt=tree->lt;
			   free(tree);
			   tree=temp;
			  }
		       }
			while((tree->len == ln)&&(tree->ge!=NULL)  );
			if(tree->ge == NULL)  goto lable1;
		    }
	       }
	 }
return(tree);
}



void    st_print( STNODE* tree)
{
  if( tree == NULL)
	return;
  st_print(tree->lt);
  printf("[%d] - [%s]\n",tree->len,tree->string);
  st_print(tree->ge);
}


STNODE* st_insert( STNODE* tree, char* str)
{
   STNODE* temp;   STNODE* root;
   int a;
   a=strlen(str);
   if(tree == NULL)
   {


     tree = ( STNODE* )  malloc(sizeof(STNODE));
     tree->len=a;
     strcpy(tree->string,str);
     tree->ge=tree->lt=NULL;

   }
   else if( tree->len == a)
	{

	 temp=( STNODE* ) malloc(sizeof(STNODE));
	 temp->len=a;
	 strcpy(temp->string,str);
	 temp->ge=tree->ge;
	 tree->ge=temp;
	 temp->lt=NULL;
     /*	 temp->ge=tree->ge;
	 temp->lt=tree->lt;
	 tree->ge=NULL;
	 tree->lt=NULL;
	 tree->ge=temp;     */

	}
     else if( tree->len > a )
	    tree->lt=st_insert(tree->lt, str);
     else if( tree->len < a )
	    tree->ge=st_insert(tree->ge, str);

   return(tree);
}



int  st_lookup_string( STNODE* tree, char* str)
{
   int ln;
   ln = strlen(str);
   if( tree == NULL )       return(0);
   if( tree->len == ln )
   {
       while(tree->len==ln)
       {
	  if(strcmp(tree->string,str) == 0)
		 return(1);
	  else
	    tree=tree->ge;
       }
	 return(0);
   }

   if( tree->len > ln)
	return( st_lookup_len(tree->lt,ln));
   else
	return( st_lookup_len(tree->ge,ln));

}


int  st_lookup_len( STNODE* tree, int ln)
{
   if( tree == NULL )       return(0);
   if( tree->len == ln )    return(1);
   if( tree->len > ln)
	return( st_lookup_len(tree->lt,ln));
   else
	return( st_lookup_len(tree->ge,ln));

}

/*   if( strcmp( tree->string, str) == 0 )    return(1);
   else {
	     if( st_lookup_string(tree->lt, str) == 1) return (1);
	     if( st_lookup_string(tree->ge, str) == 1);
	}             */