// struktura wezla B-drzewa i przyklad zapisu i odczytu na plik
// budowanie B-drzewa o zadanej wysokosci i drukowanie
//                                     pmp@inf.ug.edu.pl 2007

#include <stdio.h>
#define T 3

typedef struct
  {
  short n;
  short leaf;
  int k[2*T-1];
  int c[2*T];
  int info[2*T-1];
  } Wezel;

int rozmiarw = sizeof(Wezel);
FILE *drzewo;

void zapisz(int i,Wezel *w)
  {
  fseek(drzewo,(long)i*rozmiarw,SEEK_SET);
  fwrite(w,rozmiarw,1,drzewo);
  }

void odczytaj(int i,Wezel *w)
  {
  fseek(drzewo,(long)i*rozmiarw,SEEK_SET);
  fread(w,rozmiarw,1,drzewo);
  }

void usun(int i)
  {
  Wezel w;
  odczytaj(i,&w);
  w.n=-1;
  zapisz(i,&w);
  }

int budujB(int g, int n)
  {
  static int klucz=0;
  static int pozycja=0;
  Wezel w;
  w.n=n;
  int i;
  if (g==0)
	{
    	for (i=0;i<n;i++)
		{
      		w.c[i]= -1;
      		w.k[i]= klucz++;
    		}
    	w.c[n]= -1;
    	w.leaf=1;
   	}
   else
	{
    	for (i=0;i<n;i++)
		{
      		w.c[i]= budujB(g-1,n);
      		w.k[i]= klucz++;
    		}
   	w.c[n]= budujB(g-1,n);;
    	w.leaf=0;
  	}
  zapisz(pozycja++,&w);
  return pozycja-1;
  }

drukujB(int r, int p)
  {
  Wezel w;
  int i,j;
  odczytaj(r,&w);
  if (w.leaf)
    	{
    	for (i=0;i<p;i++) printf(" ");
    	for (i=0;i<w.n;i++) printf("%d ",w.k[i]);
    	printf("\n");
    	}
  else
    	{
    	drukujB(w.c[w.n],p+4);
    	for (i=w.n-1;i>=0;i--)
      		{
      		for (j=0;j<p;j++) printf(" ");
      			printf("%d\n",w.k[i]);
      		drukujB(w.c[i],p+4);
      		}
    	}
   }

int rozbij(int r, int t, int s)
  {
  Wezel w1,w2,w3,pm;
  int i, j=0, k;
  odczytaj(s, &w1);
  odczytaj(t, &w2);
  w3.leaf=w1.leaf;
  w3.n=(2*T-1)/2;
  while(w2.k[j]<w1.k[w3.n] && j<w2.n)
	j++;;
  for(i=0; i<w3.n; i++)
	w3.k[i]=w1.k[i+w3.n+1];
  if(w1.leaf==0)
	for(i=0; i<w3.n+1; i++)
		w3.c[i]=w1.c[i+w3.n+1]+1;
  else
	for(i=0; i<w3.n+1; i++)
		w3.c[i]=-1;
  w3.leaf=w1.leaf;
  w3.n=(2*T-1)/2;
  w1.n=w3.n;
  for(i=w2.n; i>j; i--)
	w2.k[i]=w2.k[i-1];
  for(i=w2.n+1; i>j; i--)
	w2.c[i]=w2.c[i-1]+1;
  w2.c[j]=s;
  w2.k[j]=w1.k[w3.n];
  w2.n++;
  for(i=r; i>s; i--)
	{
	odczytaj(i, &pm);
	for(k=pm.n+1; k>=0; k--)
		if(pm.c[k]>s && pm.leaf==0)
			pm.c[k]++;
	zapisz(i+1, &pm);
	}
  zapisz(s, &w1);
  odczytaj(s, &w1);
  zapisz(s+1, &w3);
  zapisz(t+1, &w2);
  r++;
  return r;
  }

szukaj(int r, int l)
  {
  Wezel w;
  odczytaj(r,&w);
  int inf=0, i=0;
  while(inf==0)
	{
	i=0;
	while(w.k[i]<l && i<w.n)
		i++;
	if(w.k[i]==l)
		inf=1;
	else if(w.leaf==0)
  		odczytaj(w.c[i],&w);
	else
	    	inf=2;
	}
  if(inf==1)
	printf("Element %i znajduje sie w drzewie.\n", l);
  else
	printf("Element %i nie znajduje sie w drzewie.\n", l);
  }

int wstaw(int r, int l)
  {
  Wezel w;
  odczytaj(r,&w);
  int i=0, j=0, k;
  while(w.leaf==0)
	{
	i=0;
	while(w.k[i]<l && i<w.n)
		i++;
	k=j;
	j=w.c[i];
  	odczytaj(j,&w);
	}
  i=0;
  if(w.n==2*T-1)
	{
	r=rozbij(r, k, j);
	odczytaj(k, &w);
	int k2=k+1;
	while(w.n==2*T-1)
		{
  		while(j!=k)
			{
			i=0;
			while(w.k[i]<l && i<w.n)
				i++;
			k2=j;
			j=w.c[i];
  			odczytaj(j,&w);
			}
		k=k2;
		r=rozbij(r, k, j);
		odczytaj(k, &w);
		}
	j+=1;
  	odczytaj(j,&w);
	if(w.k[0]>l)
		{
		j--;
		odczytaj(j,&w);
		}
	}
  while(w.k[i]<l && i<w.n)
	i++;
  if(i==w.n)
	{
	w.k[w.n]=l;
	w.n++;
  	zapisz(j,&w);
	}
  else
	{
	k=w.n;
	while(w.k[k-1]!=w.k[i])
		{
		w.k[k]=w.k[k-1];
		k--;
		}
	while(w.k[k-1]==w.k[i])
		{
		w.k[k]=w.k[i];
		k--;
		}
	w.k[k]=l;
	w.n++;
  	zapisz(j,&w);
	}
  return r;
  }

main()
   {
   int i;
   drzewo = fopen("bdrzewo","w+");
   int root;
   root=budujB(2,2);
   printf("\n");
   drukujB(root,0);
   printf("\n");
   szukaj(root, 2);
   szukaj(root, 12);
   szukaj(root, 25);
   szukaj(root, 26);
   szukaj(root, 122);
   root=wstaw(root, -22);
   root=wstaw(root, -10);
   root=wstaw(root, 2);
   root=wstaw(root, -2);
   root=wstaw(root, 6);
   root=wstaw(root, 17);
   root=wstaw(root, 17);
   root=wstaw(root, 17);
   root=wstaw(root, 17);
   root=wstaw(root, 123);
   root=wstaw(root, 200);
   root=wstaw(root, 201);
   root=wstaw(root, 202);
   printf("\n");
   printf("WSTAWIANIE\n");
   drukujB(root,0);
   printf("\n");
   szukaj(root, -22);
   szukaj(root, -8);
   szukaj(root, 0);
   szukaj(root, 111);
   szukaj(root, 123);
   fclose(drzewo);
   }