#include <iostream>
using namespace std;
const int b=1000;
struct chitatel
	{
		char bilet[8];//«ANNNN-YY», 
		char fio[30];
		int god;
		char adres[30];
		char mesta[30];
	};
struct chitatel chit[b];
struct kniga
	{
		char shifr[7];
		char afftor[30];
		char nazvanie[30];
		char izdatelstvo[30];
		int god;
		int	kolvovsego;
		int	kolvoest;
		//struct kniga* left;
	//	struct kniga* right;
	};
struct vidacha
	{
		char bilet[8];
		char shifr[7];
		char dacha[30];
		char vidat[30];
	};
struct spisok
	{
		struct vidacha dat;
		struct spisok *next;
	};

struct bmslovo
	{
		char bukva;
		int line;
	};
struct tree {
    struct kniga book;
    int balance;
    tree *right;
    tree *left;
};
struct stack_elem{
 tree *vert;
 char pos;
 //stack_elem* next;
} stack[100];
int stack_len=0;

//шаг первый-Хэширование
//__________________________________________________________________

int heshnomer(char *nomer)//создание хэш номера
{
	int h,g=0;
	int hh[10];
	h=(nomer[0]+3*nomer[1]+9*nomer[2]+27*nomer[3]+81*nomer[4]+243*nomer[5]+81*nomer[6]+27*nomer[7]);
	h=h*h;
	int i=1,p=1;
	for(int n=9;n>=0;n--)
	{
		p=10*p;
		hh[n]=(h%p-g)/(p/10);
		g=h%p;
		i++;
	}
	h=hh[9]*1000+hh[3]*100+hh[2]*10+hh[6];
	h=h%b;
	return h;
}
bool heshpoisk(struct chitatel chit[b],char *nomer,int &nom)// поиск ключа в хэш таблице
{
	bool tyt;
	int p,i=2;
	nom=heshnomer(nomer);
	p=nom;
	while(p<b)
	{
		if (!strcmp(chit[p].bilet,""))
		{
			nom=p;
			return false;
		}
		else
		{
				if(!strcmp(nomer,chit[p].bilet))
				{
					nom=p;// посмотреть баг, что будет если рпревысит 1000.
					return true;
				}
				p=p+i;
				i=i*2;
		}
	}
	cout<<"MECTA HET!!!";
return tyt;
}
bool heshdabavka(char *nomer,int &nom)//добавление клиента в хэштааблицу
{
	if(heshpoisk(chit,nomer,nom))
		return false;
	else
	{
		strcpy(chit[nom].bilet,nomer);
		cout<<"BBEDUTE FIO: ";
		cin>>chit[nom].fio;//>>'\n';
		cout<<"BBEDUTE ADPEC: ";
		cin>>chit[nom].adres;//>>'\n';
		cout<<"BBEDUTE MECTO Y4Ebi/PAbOTi: ";
		cin>>chit[nom].mesta;//>>'\n';
		cout<<"BBEDUTE GOD ROJDEHUIA:  ";
		cin>>chit[nom].god;//>>'\n';
		cout<<"\n";
	}
}

void delallklient(struct chitatel chit[b])//очистка хэштааблицы
{
	int i=0;
    while(i<b)
	{
		strcpy(chit[i].bilet,"");
		strcpy(chit[i].fio,"");
		strcpy(chit[i].adres,"");
		strcpy(chit[i].mesta,"");
		chit[i].god=0;
		i++;
	}
}

bool ydalenieodnogo(char *nomer)//удаление клиента
{
	int i=-1;
	if(heshpoisk(chit,nomer,i))
	{
		strcpy(chit[i].bilet,"");
		strcpy(chit[i].fio,"");
		strcpy(chit[i].adres,"");
		strcpy(chit[i].mesta,"");
		chit[i].god=0;
		return true;
	}		
	return false;
}
int prosmotrall(struct chitatel chit[b])//просмотр всех зарегистрированных читателей;
{
	int i=0,l=0;
	while (i<b)
	{
		if(strcmp(chit[i].bilet,""))
		{
			cout<<i<<")  "<<"bU/\ET #  "<<chit[i].bilet<<'\n';
			cout<<"FIO: "<<chit[i].fio<<'\n';
			cout<<" ADPEC: "<<chit[i].adres<<'\n';
			cout<<"MECTO Y4Ebi/PAbOTi: "<<chit[i].mesta<<'\n';
			cout<<"GOD ROJDEHUIA:  "<<chit[i].god<<'\n';
			cout<<"\n";
			i++;
			l++;
		}
		else
		i++;
	}
	cout<<"BCEGO "<<l<<"  K/\UEHTOB";
	return l;
}
//_____________________________________________________________________

//шаг второй АВЛ деревья.

struct tree *maloepravoe(struct tree *a)//малое правое
{
	struct tree* h;
	struct kniga adata,hdata;
	int v=0,w,f;
	h=a->right;
	adata=a->book;
	hdata=h->book;
	w=h->balance;
	f=(max(v,w)+1)-a->balance;
	a->book=hdata;
	h->book=adata;
	a->right=h->right;
	h->right=h->left;
	h->left=a->left;
	a->left=h;
	h->balance=v-f;
	a->balance=w-(max(f,v)+1);
	return a;
}

struct tree *maloelevoe(struct tree *a)//малое левое
{
	struct tree* h;
	struct kniga adata,hdata;
	int v=0,w,f;
	h=a->left;
	adata=a->book;
	hdata=h->book;
	w=h->balance;
	f=(max(v,w)+1)-a->balance;
	a->book=hdata;
	h->book=adata;
	a->left=h->left;
	h->left=h->right;
	h->right=a->right;
	a->right=h;
	h->balance=v-f;
	a->balance=w-(max(f,v)+1);
	return a;
}

struct tree *bolshoepravoe(struct tree *a)//большое правое
{
	struct tree* b;
	struct tree* c;
	struct kniga adata,bdata,cdata;
	int v,w=0,f,p;
	b=a->right;
	c=b->left;
	adata=a->book;
	bdata=b->book;
	cdata=c->book;
	f=c->balance;
	p=(max(w,f)+1)+b->balance;
	v=1+max(p,p-b->balance)-a->balance;
	a->book=cdata;
	c->book=adata;
	b->left=c->right;
	c->right=c->left;
	c->left=a->left;
	a->left=c;
	b->balance=p-f;
	c->balance=w-v;
	a->balance=max(p,f)-max(v,w);
	return a;
}

struct tree *bolshoelevoe(struct tree *a)//большое левое
{
	struct tree* b;
	struct tree* c;
	struct kniga adata,bdata,cdata;
	int v,w=0,f,p;
	b=a->left;
	c=b->right;
	adata=a->book;
	bdata=b->book;
	cdata=c->book;
	f=c->balance;
	p=(max(w,f)+1)+b->balance;
	v=1+max(p,p-b->balance)-a->balance;
	a->book=cdata;
	c->book=adata;
	b->right=c->left;
	c->left=c->right;
	c->right=a->right;
	a->right=c;
	b->balance=p-f;
	c->balance=w-v;
	a->balance=max(p,f)-max(v,w);
	return a;
}

void tree_balance(struct tree *a, int &cur_balance)//bolshoepravoe  bolshoelevoe  maloelevoe  maloepravoe
{
    struct tree *b;
    if (a->balance==2)
    {
        b=a->right;
        if (b->balance==-1)
        {
            bolshoepravoe(a);
            cur_balance=-1;
        }
        else
        {
            if (b->balance==0)
            {
                maloepravoe(a);
                cur_balance=0;
            }
            else
            {
                maloepravoe(a);
                cur_balance=-1;
            }
        }
    }
    else
    {
        if (a->balance==-2)
        {
            b=a->left;
            if (b->balance==1)
            {
                bolshoelevoe(a);
                cur_balance=-1;
            }
            else
            {
                if (b->balance==0)
                {
                    maloelevoe(a);
                    cur_balance=0;
                }
                else
                {
                    maloelevoe(a);
                    cur_balance=-1;
                }
            }
        }
        else
        {
            cur_balance=0;
        }
    }
}
/*
bool search(struct tree *a,char *x,int &kolvoshagov)
{
	bool naiden=false;
		if(a)
		{
			if(!strcmp(a->book.shifr,x))
				return true;
			kolvoshagov++;
			if(strcmp(a->book.shifr,x)<0)
				search(a->right,x,kolvoshagov);
			else
				search(a->left,x,kolvoshagov);		
		}
	//return naiden;
}*/
struct tree * search(struct tree *start, char *k, int &steps)
{
    if (start==NULL) return NULL;
    else
    {
		if (!strcmp(start->book.shifr,k)) 
			return start;
        if (strcmp(start->book.shifr,k)==-1) 
			search(start->right, k, ++steps);
        else 
			search(start->left, k, ++steps);
    }
}





void add2(struct kniga k, struct tree *&start)// добавление с балансировкой.
{
    struct tree *newnode, *current;
 stack_len=0;
    int delta=0;
    int change=0;
    int newdelta=0;
 if (start==NULL)
    {
        start=new tree;
		start->book=k;
        start->left=NULL;
        start->right=NULL;
        start->balance=0;
    }
    else
    {
        current=start;
        while (((strcmp(current->book.shifr,k.shifr)==-1)&& current->right!=NULL) 
			||((strcmp(k.shifr,current->book.shifr)==-1) && current->left!=NULL))
			
		
		{
			if (strcmp(k.shifr,current->book.shifr)==1)
            {
                stack[stack_len].pos='r';
                stack[stack_len++].vert=current;
                current=current->right;
            }
            else
            {
                stack[stack_len].pos='l';
                stack[stack_len++].vert=current;
                current=current->left;
            }
  }
        if (strcmp(k.shifr,current->book.shifr))
        {
            newnode=new tree;
            newnode->balance=0;
			newnode->book=k;
            newnode->left=NULL;
            newnode->right=NULL;
            if(strcmp(k.shifr,current->book.shifr)==1)
            {
               stack[stack_len].vert=current;
               stack[stack_len++].pos='r';
               current->right=newnode;
            }
            else
            {
               stack[stack_len].vert=current;
               stack[stack_len++].pos='l';
               current->left=newnode;
            }
            delta=1;
            while (delta!=0 && stack_len!=0)
            {
               if (stack[stack_len-1].pos=='l')
               {
     if (stack[stack_len-1].vert->balance==1) change=0;
                    else change=1;
                    stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
               }
               else
               {
     if (stack[stack_len-1].vert->balance==-1) change=0;
                    else change=1;
                    stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance++;
               }
               tree_balance(stack[stack_len-1].vert, newdelta);
               delta=change+newdelta;
               stack_len--;
            }
        }
    }
}

bool remove(char *k, struct tree *&start)
{
    struct tree *cur2, *current;
 stack_len=0;
    int delta=0;
    int change=0;
    int newdelta=0;
 int temp=0;
 if (start==NULL || search(start, k, temp)==NULL) return false;
    else
    {
        current=start;
        while (((strcmp(k,current->book.shifr)==1)&& current->right!=NULL)
			||((strcmp(current->book.shifr,k)==-1)&&current->left!=NULL))        
		{
			if (strcmp(k,current->book.shifr)==1)
            {
                stack[stack_len].pos='r';
                stack[stack_len++].vert=current;
                current=current->right;
            }
            else
            {
                stack[stack_len].pos='l';
                stack[stack_len++].vert=current;
                current=current->left;
            }
  }
		if (!strcmp(k,current->book.shifr))
        {
            if (current->left!=NULL && current->right!=NULL)
            {
               stack[stack_len].vert=current;
      stack[stack_len++].pos='r';
      cur2=current->right;
      while (cur2->left!=NULL)
    {
     stack[stack_len].vert=cur2;
     stack[stack_len++].pos='l';
     cur2=cur2->left;
    }
	  strcpy(current->book.shifr,cur2->book.shifr);
      if (stack[stack_len-1].vert!=current) stack[stack_len-1].vert->left=cur2->right;
      else stack[stack_len-1].vert->right=cur2->right;
      delete cur2;
   }
   else
   {
    if (current->left==NULL)
    {
     if (stack_len!=0)
     {
      if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->right;
      else stack[stack_len-1].vert->right=current->right;
     }
     else start=current->right;
    }
    if (current->right==NULL)
    {
     if (stack_len!=0)
     {
      if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->left;
      else stack[stack_len-1].vert->right=current->left;
     }
     else start=current->left;
    }
    delete current;
   } 
            delta=-1;
            while (delta!=0 && stack_len!=0)
            {
               if (stack[stack_len-1].pos=='l')
               {
     if (stack[stack_len-1].vert->balance==-1) change=-1;
                    else change=0;
                    stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance+1;
               }
               else
               {
     if (stack[stack_len-1].vert->balance==1) change=-1;
                    else change=0;
                    stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
               }
               tree_balance(stack[stack_len-1].vert, newdelta);
               delta=change+newdelta;
               stack_len--;
            }
        }
    }
 return true;
}


void preorder(struct tree *bush)
{
	cout<<" ,"<<bush->book.shifr;
	if(bush->left)
	preorder(bush->left);
	if(bush->right)
	preorder(bush->right);
}

void inorder(struct tree *bush)
{
	if (bush->left&&bush->right)
	{
		inorder(bush->left);
		cout<<" ,"<<bush->book.shifr;
		preorder(bush->right);
	}
	else
	{
		cout<<bush->book.shifr;
		if(bush->left)
		{
			inorder(bush->left);
			cout<<bush->book.shifr;
		}
		if(bush->right)
		{
			inorder(bush->right);
			cout<<bush->book.shifr;
		}
	}
}

//_____________________________________________________________________

//шаг третий список.
void spisadd(struct vidacha a,struct spisok *&b)
{
	if(!b)
	{
		b=new struct spisok;
		b->dat=a;
		b->next=b;
	}
	else
	{
		struct spisok *c,*g;
		c=b;
		while (strcmp(b->next->dat.shifr,c->dat.shifr))
			b=b->next;
		g=new struct spisok;
		g->dat=a;
		g->next=c;
		b->next=g;
		
	}
}


//_____________________________________________________________________


//шаг четвертый Алгоритм поиска слова в тексте.Боуера и Мура .

bool bmsearch(char *ward,int position)
{
	int i=0;//индекс начала слова в тексте
	int j=0;//индекс текущего символа
	int z=0,n;
	struct bmslovo alfo[255];
	//char mas[255];
	int m=strlen(ward)-1;  
	int t=m;// t,m-размер слово которое ищем
	//char *ch;
//создать алфовит.
	while(m>0)
	{
		for(n=z;n>=0;n--)
		{
			if (ward[m]==alfo[n].bukva)
				goto mmm;
		}
		alfo[z].bukva=ward[m];
		alfo[z].line=t-m;
		z++;
mmm:	m--;
	}//создание алфовита закончено
	alfo[0].line=1;// расстояние от крайнего правого символа до конца слова.
	z--;//z-размер алфовита.
char slovo[255]="abcafdfmbcabdabcabd";
bool sovpalo=false;
n=strlen(slovo);
i=t;
j=t;
WWW:while((i<n)&&(!sovpalo))
{
	if(j==-1)
		return true;
	if(ward[j]==slovo[i])
	{
		i--;
		j--;
	}
	else
	{
		for(m=0;m<=z;m++)//поиск несовпавшей буквы в алфовите 
		{
			if(slovo[i]==alfo[m].bukva)
			{
				i=i+alfo[m].line;
				j=t;
				goto WWW;
			}
		}
		j=t;
		i=i+(t+1);
	}
	//if(j==0)
	//	return true;
	
}
	return sovpalo;
}

void main()
{	
	//int *klientbase[b];
	int i;
	//for (i=0;i<b;i++)
	//	klientbase[i]=NULL;
	int n=-1;
	int a=heshnomer("X999999");//«ANNNN-YY», 
	//a=heshnomer("Ч123490");//«ANNNN-YY», 
	//a=heshnomer("Ч123390");//«ANNNN-YY», 
	//a=heshnomer("Ч113490");//«ANNNN-YY», 
	strcpy(chit[446].bilet,"Ч222283");
	strcpy(chit[448].bilet,"Ч555583");
	strcpy(chit[452].bilet,"X999999");
	bool b=heshpoisk(chit,"X999999",n);
	//b=heshpoisk(chit,"X997989",n);
	//b=heshdabavka("Ч764587",n);
	prosmotrall(chit);
	//b=heshdabavka("X999999",n);
	//delallklient( chit);
	//ydalenie("Ч764587");
	b=false;
	b=bmsearch("abcabd",0);
	struct tree *nov;
	nov=NULL;
	struct kniga k;
	strcpy(k.afftor,"aaa");
	strcpy(k.izdatelstvo,"aaa");
	strcpy(k.nazvanie,"aaa");
	strcpy(k.shifr,"aaa");
	k.god=1990;
	k.kolvoest=2;
	k.kolvovsego=3;
	add2(k,nov);

	strcpy(k.afftor,"bbb");
	strcpy(k.izdatelstvo,"bbb");
	strcpy(k.nazvanie,"bbb");
	strcpy(k.shifr,"bbb");
	k.god=1991;
	k.kolvoest=12;
	k.kolvovsego=13;
	add2(k,nov);

	strcpy(k.afftor,"ccc");
	strcpy(k.izdatelstvo,"ccc");
	strcpy(k.nazvanie,"ccc");
	strcpy(k.shifr,"ccc");
	k.god=1992;
	k.kolvoest=22;
	k.kolvovsego=33;
	add2(k,nov);

	strcpy(k.afftor,"ddd");
	strcpy(k.izdatelstvo,"ddd");
	strcpy(k.nazvanie,"ddd");
	strcpy(k.shifr,"ddd");
	k.god=1993;
	k.kolvoest=2;
	k.kolvovsego=3;
	add2(k,nov);

	strcpy(k.afftor,"eee1");
	strcpy(k.izdatelstvo,"eee1");
	strcpy(k.nazvanie,"eee1");
	strcpy(k.shifr,"eee1");
	k.god=1994;
	k.kolvoest=2;
	k.kolvovsego=3;
	add2(k,nov);

	strcpy(k.afftor,"fff");
	strcpy(k.izdatelstvo,"fff");
	strcpy(k.nazvanie,"fff");
	strcpy(k.shifr,"fff");
	k.god=1995;
	k.kolvoest=2;
	k.kolvovsego=3;
	add2(k,nov);
	int l=0;
bool pr=true;
struct tree *mma;
	mma=NULL;
	 mma=search(nov,"fff",l);
	 l=7;
	 mma=search(nov,"aaa",l=0);
	 mma=search(nov,"ddd",l=0);
	 mma=search(nov,"eee",l=0);
	 mma=search(nov,"ccc",l=0);
	 mma=search(nov,"bbb",l=0);
	 cout<<"\n";
	 inorder(nov);
	 pr=remove("eee1", nov);
	  cout<<"\n";
	inorder(nov);
	strcpy(k.afftor,"eee1");
	strcpy(k.izdatelstvo,"eee1");
	strcpy(k.nazvanie,"eee1");
	strcpy(k.shifr,"eee1");
	k.god=1994;
	k.kolvoest=2;
	k.kolvovsego=3;
	add2(k,nov);
	cout<<"\n";
	inorder(nov);
}