//oxi anadromh gia na ...
//a)mporo na feygo apo ton alrgotithmo opote thelo
//b)na mporo na xrhsimopoio na spao to problhma se synarthseis xoris problhma
//g)epidh se anadromh tha apothikevontan ta nodes kai leafs kai tha htan dyskolo na elextoyn
class bptreeexcept : public except
{
public:
	bptreeexcept(const char *szdesc=0):except("B+ tree exception",szdesc){};
	~bptreeexcept(){};
};

template <class KEY,class DATA>
class bptree
{
public:
	struct INFO
	{
		int		blocksize;
		int		keysize;
		int		datasize;
		int		leafkeys;
		int		nodekeys;
		long	root;
		int		keys;
		int		depth;
		int		leafs;
		INFO():root(sizeof(INFO)),keys(0),depth(0),leafs(0),
			blocksize(BLOCKSIZE),keysize(sizeof(KEY)),datasize(sizeof(DATA)),
		leafkeys(LEAFKEYS),nodekeys(NODEKEYS){};
		~INFO(){};
	};

private:
	struct ROUTE
	{
		long	pos;
		int		index;
		ROUTE(long p,int i):pos(p),index(i){};
		ROUTE(){};
	};

	INFO _info;

	long			_treepos;
	fileobject		&_indexf;
	datafile<DATA>	&_dataf;

//	long		locate(const KEY &);
//	long		locate(const KEY &,stack<long> &);
	long		locate(const KEY &,stack<ROUTE> &);

	void		insert_to_index(stack<ROUTE> &,KEY,long);
	void		validate_index(stack<ROUTE> &,node<KEY> &);
	bool		validate_leaf(node<KEY> &,leaf<KEY> &,int);


public:
	bptree(fileobject &,datafile<DATA> &,long);
	virtual ~bptree();

	const INFO & info() const { return _info; };

	const char * indexpath() const	{	return _indexf.path(); };
	const char * datapath() const	{	return _dataf.path(); };
	datafile<DATA> &		getdatafile()		{ return _dataf; };

	void	close();
	
	bool	find(const KEY &,long &);
	void	insert(KEY,DATA);
	bool	del(const KEY &);
	void	clear();
	
	static long createbtree(fileobject &);
//	static void createfiles(const char *,const char *);
};

template <class KEY,class DATA>
bptree<KEY,DATA>::bptree(fileobject &indexfile,datafile<DATA> &datfile,long treepos):
_indexf(indexfile),_dataf(datfile)
{
	_treepos = treepos;
	_indexf.read(&_info,_treepos,sizeof(INFO));

	if ( _info.blocksize != BLOCKSIZE )
		throw new bptreeexcept("The specified index file has different block size than specified");
	if ( _info.keysize != sizeof(KEY) )
		throw new bptreeexcept("The specified index file has different key type than specified");
	if ( _info.datasize != sizeof(DATA) )
		throw new bptreeexcept("The specified index file has different data type than specified");

	leaf<KEY>::pindexfile = &_indexf;
	node<KEY>::pindexfile = &_indexf;
}

template <class KEY,class DATA>
bptree<KEY,DATA>::~bptree()
{
	close(); 
};

template <class KEY,class DATA>
void bptree<KEY,DATA>::close()
{
	_indexf.write(&_info,_treepos,sizeof(INFO));
}

template <class KEY,class DATA>
void bptree<KEY,DATA>::clear()
{
	/*
	string szindex(_indexf.path());
	string szdata(_dataf.path());
	close();
	
	createfiles(szindex,szdata);
	open(szindex,szdata);*/
}

template <class KEY,class DATA>
long bptree<KEY,DATA>::locate(const KEY &key,stack<ROUTE> &route)
{
	long pos = _info.root;
	
	int depth = 0;
	while ( depth++<_info.depth )
	{
		node<KEY> temp(pos);
		int i = temp.find(key);
		route.push( ROUTE(pos,i) );
		pos = temp.branch(i);
	}

	return pos;
}

template <class KEY,class DATA>
bool bptree<KEY,DATA>::find(const KEY &key,long &pos)
{
	stack<ROUTE> route;
	leaf<KEY> temp( locate(key,route) );
	pos = temp.find(key);

	if ( pos == -1)
		return false;
	return true;
}

template <class KEY,class DATA>
void bptree<KEY,DATA>::insert(KEY key,DATA data)
{
	stack<ROUTE> route;
	leaf<KEY> lf( locate(key,route) );

	int ifound = lf.find(key);
	if ( ifound !=-1 )
	{
		//append data to the existing
		_dataf.append_data( lf.data(ifound) , data );
		return;
	}
	
	++_info.keys;

	//add the new data to a file and get the pointer to that record 
	long datapos = _dataf.add_data(data);
	if ( lf.has_room() )
	{
		lf.insert(key,datapos);
		return;
	}
	
	//split leaf
	++_info.leafs;

	leaf<KEY> newlf( fileblock::newpos );
	lf.splitto(newlf,key,datapos);
	
	long newpos = newlf.pos();
	lf.flush();
	newlf.flush();

	insert_to_index( route , newlf.key(0) , newpos );
}

template <class KEY,class DATA>
void bptree<KEY,DATA>::insert_to_index(stack<ROUTE> &route,KEY newk,long newb)
{
	long curpos = _info.root;
	while( !route.empty() )
	{
		curpos = route.pop().pos;
		node<KEY> temp( curpos );

		if ( temp.has_room() )
		{
			temp.insert(newk,newb);
			return;
		}

		//split node
		node<KEY> nnew( fileblock::newpos );
		newk = temp.splitto(nnew,newk,newb);
		newb = nnew.pos();
	}
	
	//new root will be created
	node<KEY> root( fileblock::newpos );
	root.setroot(curpos,newk,newb);
	_info.root = root.pos();
	++_info.depth;
}

template <class KEY,class DATA>
bool bptree<KEY,DATA>::del(const KEY &key)
{
	stack<ROUTE> route;
	leaf<KEY> remlf( locate(key,route) );

	int i = remlf.find(key);
	if ( i==-1 )
		return false;

	long datapos = remlf.removekey(i);
	
	//remove all data starting from datapos...
	_dataf.remove_data( datapos );
	
	--_info.keys;

	if ( remlf.is_half_full() )
		return true;

	//leaf borrowing or merge needed here
	//first search for a sibling spare key
	if ( route.empty() )
	{
		//no parent so it is the roor
		//now there is a root with no data,
		//just leave ....
		return true;
	}

	ROUTE rt = route.pop();
	node<KEY> parent( rt.pos );

	if ( !validate_leaf(parent,remlf,rt.index) )
		validate_index(route,parent);

	return true;
}

template <class KEY,class DATA>
bool bptree<KEY,DATA>::validate_leaf(node<KEY> &parent,leaf<KEY> &lf,int lfpos)
{
	leaf<KEY> prev;
	if ( lfpos>0 )
	{
		prev.loadpos( parent.branch(lfpos-1) );
		if ( prev.is_rich() )
		{
			//rotate right
			KEY tempkey = prev.key( prev.keycount()-1 );
			long tempdata = prev.removekey(prev.keycount()-1);
			lf.insert(tempkey,tempdata);
			parent.setkey(lfpos-1,tempkey);
			return true;
		}
	}

	leaf<KEY> next;
	if ( lfpos<parent.keycount() )
	{
		next.loadpos( parent.branch(lfpos+1) );
		if ( next.is_rich() )
		{
			//rotate left
			KEY tempkey = next.key( 0 );
			long tempdata = next.removekey(0);
			lf.insert(tempkey,tempdata);
			
			tempkey = next.key( 0 );
			parent.setkey(lfpos,tempkey);
					
			return true;
		}
	}

	if ( lfpos>0 )//prev is valid
	{
		prev.append(lf);
		lf.del();
		parent.removekey(lfpos-1);
	}
	else
	{
		lf.append(next);
		next.del();
		parent.removekey(lfpos);
	}

	return false;
}

template <class KEY,class DATA>
void bptree<KEY,DATA>::validate_index(stack<ROUTE> &route,node<KEY> &nd)
{
	node<KEY> temp;
	temp.assign(nd);
	while ( !route.empty() )
	{
		if ( temp.is_half_full() )
			return;
		

		ROUTE rt = route.pop();
		node<KEY> parent( rt.pos );

		node<KEY> prev;
		if ( rt.index>0 )
		{
			prev.loadpos( parent.branch(rt.index-1) );
			if ( prev.is_rich() )
			{
				//right shift
				KEY leftkey;
				long leftbranch;

				prev.remove_rightmost_pair(leftkey,leftbranch);
				KEY parkey = parent.key( rt.index-1 );
				temp.insert_leftmost(parkey,leftbranch);
				parent.setkey(rt.index-1,leftkey);
				
				return;
			}
		}

		node<KEY> next;
		if ( rt.index<parent.keycount() )
		{
			next.loadpos( parent.branch(rt.index+1) );
			if ( next.is_rich() )
			{
				//left shift
				KEY rightkey;
				long rightbranch;

				next.remove_leftmost_pair(rightkey,rightbranch);
				KEY parkey = parent.key( rt.index );
				temp.insert_rightmost(parkey,rightbranch);
				parent.setkey(rt.index,rightkey);

				return;
			}
		}

		if ( rt.index>0 )//prev is valid
		{
			prev.append( temp,parent.key(rt.index-1));
			temp.del();
			parent.removekey(rt.index-1);
			temp.assign(parent);
		}
		else//next is valid
		{
			temp.append( next,parent.key(rt.index) );
			next.del();
			parent.removekey(rt.index);
			temp.flush();
			temp.assign(parent);
		}
	}

	//temp now must be the root
	assert( temp.pos() == _info.root );
	if ( !temp.keycount() )
	{
		//we must delete the previous root as long as it has only 1 branch
		_info.root = temp.branch(0);//the only branh it has
		temp.del();
		--_info.depth;
	}
}

template <class KEY,class DATA>
long bptree<KEY,DATA>::createbtree(fileobject &indexfile)
{
	INFO info;
	long treepos = indexfile.size();
	indexfile.append(&info,sizeof(INFO));
	int i =  sizeof(INFO);

	leaf<KEY> root( fileblock::newpos , &indexfile);

	info.root = root.pos();
	root.flush();								//must flush or else store will be aplyied after file is closed !
	indexfile.write(&info,treepos,sizeof(INFO));//need to write again so that changes of INFO will be saved

	return treepos;
}

/*
template <class KEY,class DATA>
void bptree<KEY,DATA>::createfiles(const char *szindex,const char *szdata)
{
	fileobject index;
	index.create(szindex);
	INFO info;
	index.append(&info,sizeof(INFO));
	leaf<KEY> root( fileblock::newpos , &index );
	info.root = root.pos();
	root.flush();//must flush or else store will be aplyied after file is closed !
	index.write(&info,0,sizeof(INFO));
	index.close();

	datafile<DATA> data;
	data.create(szdata);
	char dump;
	data.append(&dump,1);//just move to pos 1, as 0 is used to mark the size
	data.close();
}
*/