/* implementace tridy btree.h */

#include "btree.h"
#include <stdio.h>

// konstruktor tridy CBTree
CBTree::CBTree(CBTree *p_next, CBTree *p_prev)
{
	CBTree::p_prev = p_prev; // ulozeni predchoziho
	if (p_next) // pokud je dalsi, vytvorime novy list
	{
		p_next->p_prev = this;
		p_p_next = new P_CBTREE[N * 2 + 1]; // alokace noveho listu
		p_p_next[0] = p_next;
	}
	else // jinak nic
		p_p_next = NULL;
	p_data = new int[N * 2]; //naalokovani klicu
	no_data = 0; // vynulovani citace klicu
}

// destruktor tridy CBTree aneb vse rusime
CBTree::~CBTree()
{
	int i;
	if (p_p_next != NULL)
	{
		for (i = 0; i <= no_data; i++)
			if (p_p_next[i] != NULL)
				delete p_p_next[i];
		delete p_p_next;
	}
	delete p_data;
}

// vlozeni noveho klice...
int CBTree::insert_num(int number)
{
	int i;
	int middle_key;	
	P_CBTREE p_new;
	
	int pos = find_pos(number); // je klic teto hodnoty ulozen ?
	if ((pos < no_data) && (p_data[pos] == number))  {
		//ano, jiz nevkladame
		return 0;
	}
	
	if (p_p_next == NULL) // jsme v listu
	{
		if (no_data < 2 * N) // je dostatek mista ???
		{   // pokud ano, vlozime na predem zjistenou pozici
			for (i = no_data; i > pos; i--)
				p_data[i] = p_data[i - 1];
			p_data[pos] = number;
			no_data++;
		}
		else
		// pokud je v listu plno
		{
			if (p_prev == NULL)
			//jsme v koreni - pridame novy
			{
				p_prev = new CBTree(this, NULL);
				p_root = p_prev;  // novy koren
			}
			p_new = new CBTree(NULL, p_prev);
			if (pos <= N)
			{
				if (pos == N)
					middle_key = number; // prvek je prostredni
				else
				{ //pokud neni, je nutne vybrat prostredni a pak 
					i = N - 1; // vsechny nasledujici posunout
					middle_key = p_data[i]; // to je prostredni prvek
					while (i > pos)
					{
						p_data[i] = p_data[i - 1];
						i--;
					}
					p_data[i] = number; // a vlozit na pozadovanou pozici
				}
				p_new->insert_num(p_data[N]);  // vlozime cislo rovnajici se radu 
						//(do noveho listu)
			}
			else
			//nejsme v koreni - pridame novy koren -> rozdeleni
			{
				middle_key = p_data[N];  // ulozime prostredni prvek
				p_new->insert_num(number);  // vlozime cislo
			}
			for (i = N + 1; i < N * 2; i++) // nasledujici cisla presuneme
				p_new->insert_num(p_data[i]); // jednotliva cisla vlozime
			no_data = N; // pocet dat odpovida radu
			p_prev->insert_split(middle_key, p_new); // rozdelime dle stredniho prvku
		}
		return 1; // vratime ok
	}
	else
		return p_p_next[pos]->insert_num(number); // pokracujeme
}

// vyjmuti cisla ze stromu
int CBTree::delete_num(int number)
{
	int pos = find_pos(number);
	int i;

	if (p_p_next == NULL)
	//jsme v listu
	{
		if ((pos >= no_data) || (p_data[pos] != number))
		// cislo neni v prislusnem listu
			return 0;
		// cislo je v prislusnem listu
		for (i = pos + 1; i < no_data; i++)
			p_data[i - 1] = p_data[i];
		no_data--;
		if ((no_data < N) && (p_prev != NULL))
		//nezustalo dost dat a nejsme v koreni
			p_prev->leaf_underflow(p_data[0]);
		return 1;
	}
	else
	//nejsme v listu
	{
		if ((pos >= no_data) || (p_data[pos] != number))
		//cislo neni v prislusnem listu
			return p_p_next[pos]->delete_num(number);
		else
		//cislo je v prislusnem listu - nahradime ho nejblizsim vetsim a to smazeme
		{
			p_data[pos] = p_p_next[pos + 1]->find_smallest();
			return p_p_next[pos + 1]->delete_num(p_data[pos]);
		}
	}
}

// vypis vytvoreneho stromu ve formatu jaky hruzovladce naridil
// nakonec jsem stejne zjistil, ze to neni potreba :))))
void CBTree::dump_structure(int n, FILE *file_out)
{
	int i;
	int j;

	for (j=0; j<n; j++) {
		fprintf(file_out, " ");
	}	
	
	fprintf(file_out,"(\n");
	
	for (i = 0; i < no_data; i++){
	
		if (p_p_next != NULL)	
			p_p_next[i]->dump_structure(n + 1, file_out);

		for (j=0; j<n; j++) {
			fprintf(file_out, " ");
		}		
		fprintf(file_out, "%d\n", p_data[i]);
	
	}

		if (p_p_next != NULL)	
			p_p_next[i]->dump_structure(n + 1, file_out);
	
		for (j=0; j<n; j++) {
			fprintf(file_out, " ");
		}		
	
	fprintf(file_out,")\n");
}

// tohle vypise jen serazena cisla...
// tak jak je to pozadovano!!!
void CBTree::dump_numbers(int n, FILE *file_out)
{
	int i;
	
	for (i = 0; i < no_data; i++){
		if (p_p_next != NULL)	
			p_p_next[i]->dump_numbers(n + 1, file_out);	
		
		fprintf(file_out, "%d\n", p_data[i]);	
	}	
	if (p_p_next != NULL)	
		p_p_next[i]->dump_numbers(n + 1, file_out);

}

// ************************
// zde jsou privatni metody

// nalezneme pozici, na ktere je ulozen klic se zadanou hodnotou
int CBTree::find_pos(int number)
{
	int i = 0;
	while ((i < no_data) && (p_data[i] < number))
		i++;
	return i;
}

// rozdeleni listu na dva nove - pri vkladani dat
void CBTree::insert_split(int number, CBTree *p_page)
{
	int pos;
	int i;
	int middle_key;
	P_CBTREE p_new = NULL;

	pos = find_pos(number); // nalezneme cislo
	
	if (no_data < 2 * N)
	{  // dostatek mista pro ulozeni bez deleni
		for (i = no_data; i > pos; i--)
		{
			p_data[i] = p_data[i - 1];
			p_p_next[i + 1] = p_p_next[i];
		}  // posuneme cisla
		p_data[pos] = number; 
		p_page->p_prev = this;
		p_p_next[pos + 1] = p_page;
		no_data++;
	}
	else
	// v listu jiz neni misto
	{
		if (p_prev == NULL)
		//jsme v koreni - vytvorime novy
		{
			p_prev = new CBTree(this, NULL);
			p_root = p_prev;
		}
		if (pos <= N)
		{
			if (pos == N)
			//vkladame doprostred
			{
				middle_key = number;  // prvek je prostredni
				p_new = new CBTree(p_page, p_prev); // vytvorime si novy list
			}
			else
			//vkladame vlevo
			{
				i = N - 1;
				middle_key = p_data[i]; // ulozime prostredni prvek
				p_new = new CBTree(p_p_next[N], p_prev); // vytvorime novy list
				while (i > pos)
				{ // nyni je nutno presunout prvky...
					p_data[i] = p_data[i - 1];
					p_p_next[i + 1] = p_p_next[i];
					i--;
				}
				p_data[i] = number;
				p_p_next[i + 1] = p_page;
			} // pokracujeme
			p_new->insert_split(p_data[N], p_p_next[N + 1]); 
		}
		else
		//vkladame vpravo
		{
			middle_key = p_data[N]; // ulozime si prostredni prvek
			p_new = new CBTree(p_p_next[N + 1], p_prev); // vytvorime dalsi list
			p_new->insert_split(number, p_page); // rozdeleni
		}
		for (i = N + 1; i < N * 2; i++) 
			p_new->insert_split(p_data[i], p_p_next[i + 1]); // probublavani
		no_data = N; // pocet dat
		p_prev->insert_split(middle_key, p_new); // pokracujeme
	}
}

// pokud ma list nedostatek dat a neni to koren,
// pak je treba provest kondenzaci
void CBTree::leaf_underflow(int number)
{
	int extended = find_pos(number);
	int middle;
	int condensed;
	int my_key;
	if (extended == no_data)
	//pokud je prodluzovany posledni
	{
		condensed = extended - 1;
		middle = condensed;
		my_key = p_p_next[condensed]->find_biggest();
	}
	else
	//prodluzovany neni posledni - bereme ten zprava
	{
		condensed = extended + 1;
		my_key = p_p_next[condensed]->find_smallest();
		middle = extended;
	}
	//musime presunout prvek nebo sloucit dva listy
	if (p_p_next[condensed]->no_data > N)
	//zde pouze presunujeme prvky
	{
		p_p_next[extended]->insert_num(p_data[middle]);
		p_data[middle] = my_key;
		p_p_next[condensed]->delete_num(my_key);
	}
	else
	//slucovani
	{
		int i;
		p_p_next[extended]->insert_num(p_data[middle]);
		for (i = 0; i < N; i++)
			p_p_next[extended]->insert_num(p_p_next[condensed]->p_data[i]);
		delete p_p_next[condensed];
		if (extended == no_data)
		//sloucili jsme posledni dve a ulozili je do posledni
			p_p_next[condensed] = p_p_next[extended];
		else
		//odstranena stranka je vpravo od odstranenych dat
			for (i = middle + 1; i < no_data; i++)
			{
				p_data[i - 1] = p_data[i];
				p_p_next[i] = p_p_next[i + 1];
			}
		no_data--;
		if ((no_data < N) && (p_prev != NULL))
		//nezustalo dost dat a nejsme v koreni - musime provest dalsi kroky
		{
			p_prev->page_underflow(p_data[0]);
			return;
		}
		if (no_data == 0)
		//jsme v koreni a ten je prazdny
		{
			p_root = p_p_next[0];
			p_p_next[0] = NULL;
			p_root->p_prev = NULL;
			delete this;
		}
	}
}

// stranka ma malo dat
void CBTree::page_underflow(int number)
{
	int extended = find_pos(number);
	int middle;
	int condensed;
	int my_key;
	CBTree *p_next;
	if (extended == no_data)
	//pokud je prodluzovany posledni
	{
		condensed = extended - 1;
		middle = condensed;
		my_key = p_p_next[condensed]->biggest(&p_next);
	}
	else
	//prodluzovany neni posledni - bereme ten zprava
	{
		condensed = extended + 1;
		my_key = p_p_next[condensed]->smallest(&p_next);
		middle = extended;
	}
	// presunout prvku nebo slouceni dvou listy
	if (p_p_next[condensed]->no_data > N)
	// presun prvku
	{
		p_p_next[extended]->insert_split(p_data[middle], p_next);
		if (extended == no_data)
		//presouvame z predposledni do posledni, tedy 
		//musime prohodit prvni dva ukazatele
		{
			p_p_next[extended]->p_p_next[1] = p_p_next[extended]->p_p_next[0];
			p_p_next[extended]->p_p_next[0] = p_next;
		}
		p_data[middle] = my_key;
		p_p_next[condensed]->delete_split(p_next);
	}
	else
	// slucovani
	{
		int i;
		p_p_next[extended]->insert_split(p_data[middle], p_p_next[condensed]->p_p_next[0]);
		if (extended == no_data)
		//prendavame z predposledni do posledni, tedy musime 
		//prohodit prvni dva ukazatele
		{
			p_p_next[extended]->p_p_next[1] = p_p_next[extended]->p_p_next[0];
			p_p_next[extended]->p_p_next[0] = p_p_next[condensed]->p_p_next[0];
		}
		p_p_next[condensed]->p_p_next[0] = NULL;
		for (i = 0; i < N; i++)
		{  // slouceni
			p_p_next[extended]->insert_split(p_p_next[condensed]->p_data[i], p_p_next[condensed]->p_p_next[i + 1]);
			p_p_next[condensed]->p_p_next[i + 1] = NULL;
		}
		delete p_p_next[condensed];
		if (extended == no_data)
		//sloucili jsme posledni dve a ulozili je do posledni
			p_p_next[condensed] = p_p_next[extended];
		else
		//odstranena stranka je vpravo od odstranenych dat
			for (i = middle + 1; i < no_data; i++)
			{
				p_data[i - 1] = p_data[i];
				p_p_next[i] = p_p_next[i + 1];
			}
		no_data--;
		if ((no_data < N) && (p_prev != NULL))
		//nezustalo dost dat a nejsme v koreni
		{
			p_prev->page_underflow(p_data[0]);
			return;
		}
		if (no_data == 0)
		//jsme v koreni a ten je prazdny
		{
			p_root = p_p_next[0];
			p_p_next[0] = NULL;
			p_root->p_prev = NULL;
			delete this;
		}
	}
}

// rozdeleni listu na dva nove - pri vkladani dat
void CBTree::delete_split(CBTree *p_page)
{
	int i;

	if (p_page == p_p_next[0])
	//vyndavame prvni a ostatni pouze posuneme
	{
		for (i = 1; i < no_data; i++)
		{
			p_data[i - 1] = p_data[i];
			p_p_next[i - 1] = p_p_next[i];
		}
		p_p_next[no_data - 1] = p_p_next[no_data];
	}
	no_data--;
}

// nalezne nejmensi hodnotu ve stromu
int CBTree::find_smallest()
{
	if (p_p_next == NULL)
	//pokud jsme v listu
		return p_data[0];
	else
	//pokud nejsme v listu
		return p_p_next[0]->find_smallest();
}

// nalezne nejvetsi hodnotu ve stromu
int CBTree::find_biggest()
{
	if (p_p_next == NULL)
	//pokud jsme v listu
		return p_data[no_data - 1];
	else
	//pokud nejsme v listu
		return p_p_next[no_data - 1]->find_biggest();
}

// vraci nejvetsi hodnotu 
int CBTree::biggest(CBTree **p_p_page)
{
	if (p_p_page != NULL)
	{
		if (p_p_next == NULL)
			*p_p_page = NULL;
		else
			*p_p_page = p_p_next[no_data];
	}
	return p_data[no_data - 1];
}

// vraci nejmensi hodnotu
int CBTree::smallest(CBTree **p_p_page)
{
	if (p_p_page != NULL)
	{
		if (p_p_next == NULL)
			*p_p_page = NULL;
		else
			*p_p_page = p_p_next[0];
	}
	return p_data[0];
}