#define nvalidatekey(a)		assert( (a)>=0 && (a)<_keys)
#define nvalidatebranch(a)	assert( (a)>=0 && (a)<_keys+1)
#define NODEKEYS ((BLOCKSIZE - sizeof(long))/(sizeof(KEY)+sizeof(long)))
#define NODEBRANCHES NODEKEYS+1

template <class KEY>
class node : public fileblock
{
protected:
	KEY	*			_key;
	long *			_branch;
	int				_keys;

protected:
	void initdata();
	void markdata();


public:
	static fileobject * pindexfile;

	node(fileobject *pfile=pindexfile);
	node(long,fileobject *pfile=pindexfile);
	~node();

	int		keycount() const				{ return _keys; };
	int		find(const KEY &) const;
	KEY		key(int pos) const				{ nvalidatekey(pos); return _key[pos]; };
	long	branch(int pos) const			{ nvalidatebranch(pos); return _branch[pos]; };
	bool	has_room() const				{ return _keys!=NODEKEYS; };
	bool	is_rich() const					{ return _keys>NODEKEYS/2; };
	bool	is_half_full() const			{ return _keys>=NODEKEYS/2; };
	void	setkey(int,const KEY &);
	void	insert(const KEY &,long);
	void	setroot(long,const KEY &,long);
	KEY		splitto(node &,const KEY &,long);
	void	removekey(int);
	void	remove_leftmost_pair(KEY &,long &);
	void	remove_rightmost_pair(KEY &,long &);
	void	insert_rightmost(const KEY &,long);
	void	insert_leftmost(const KEY &,long);
	void	append(node &,const KEY &);
	void	assign(node &);
	void	operator=(node &){ assert(false); };

};
template <class KEY> fileobject * node<KEY>::pindexfile = 0;


//at the constructor the node is automatically loaded from fileblock class,
//as long as i pass into the constructor a valid file posisition.
//If i pass a "newpos" position then fileblock will get a new block into file.
template <class KEY>
node<KEY>::node(long pos,fileobject *pfile):fileblock(pfile,pos)
{
	_key = (KEY *) _block;
	_branch = (long *) (_block+sizeof(KEY)*NODEKEYS);
	initdata();
}

//this constructor is used when i need a temporary node where i will copy another one.
//in that situation i don't want the this node to have a valid file position, because 
//it will take the position of its loader.
template <class KEY>
node<KEY>::node(fileobject *pfile):fileblock(pfile,invalidpos)
{
	_key = (KEY *) _block;
	_branch = (long *) (_block+sizeof(KEY)*NODEKEYS);
}

template <class KEY>
node<KEY>::~node()
{
	if ( modified() )
		markdata();
}

template <class KEY>
void node<KEY>::initdata()
{
	for (_keys=0;_keys<NODEKEYS && _branch[_keys+1];_keys++)
		;
}

template <class KEY>
void node<KEY>::markdata()
{
	//this might be wrong!!
	_branch[_keys+1] = 0;
}

template <class KEY>
int node<KEY>::find(const KEY &key) const
{
/*	int first = 0;
	int last = _keys-1;
	int mid = _keys/2;

	while( first < last )
	{
		if ( key == _key[mid] )
			return mid+1;
		else if ( key < _key[mid] )
			last = mid-1;
		else 
			first = mid+1;

		mid = first + ( last - first )/2;
	}

	if ( key > _key[mid] && mid<_keys)
		return mid+1;
	
	return mid;
*/
	int i;
	for (i=0;i<_keys && key>=_key[i];i++)
		;
	
	return i;
}

template <class KEY>
void node<KEY>::setkey(int pos,const KEY &key)
{ 
	nvalidatekey(pos); 
	_key[pos]=key; 
	setmodified();
}

template <class KEY>
void node<KEY>::insert(const KEY &key,long pos)
{
	int i = find(key);

	for (int j=_keys;j>i;j--)
	{
		_key[j] = _key[j-1];
		_branch[j+1] = _branch[j];
	}
	
	_key[i] = key;
	_branch[i+1] = pos;
	++_keys;
	setmodified();
}

template <class KEY>
void node<KEY>::insert_leftmost(const KEY &key,long pos)
{
	for (int j=_keys;j>0;j--)
	{
		_key[j] = _key[j-1];
		_branch[j+1] = _branch[j];
	}
	_branch[1] = _branch[0];
	_key[0] = key;
	_branch[0] = pos;
	++_keys;
	setmodified();
}

template <class KEY>
void node<KEY>::insert_rightmost(const KEY &key,long pos)
{
	_branch[_keys+1] = pos;
	_key[_keys] = key;
	++_keys;
	setmodified();
}

template <class KEY>
KEY	node<KEY>::splitto(node &nd,const KEY &key,long branch)
{
	int median = _keys/2;
	bool addtonew = true;
	if ( key<_key[median] )
	{
		addtonew = false;
		median = median-1;
	}

	int j=0;
	for (int i=median+1;i<_keys;i++,j++)
	{
		nd._branch[j+1] = _branch[i+1];
		nd._key[j] = _key[i];
	}

	nd._keys = j;
	_keys = median+1;
	
	if ( addtonew )
		nd.insert(key,branch);
	else
		insert(key,branch);

	KEY ret = _key[_keys-1];
	nd._branch[0] = _branch[_keys];
	--_keys;

	setmodified();
	return ret;
}

template <class KEY>
void node<KEY>::setroot(long leftpos,const KEY &key,long rightpos)
{
	_key[0] = key;
	_branch[0] = leftpos;
	_branch[1] = rightpos;
	_keys = 1;
	setmodified();
}

template <class KEY>
void node<KEY>::removekey(int i)
{
	//removes key i and its next branch
	nvalidatekey(i);

	for (;i<_keys-1;i++)
	{
		_key[i] = _key[i+1];
		_branch[i+1] = _branch[i+2];
	}

	--_keys;
	setmodified();
}

template <class KEY>
void node<KEY>::remove_leftmost_pair(KEY &key,long &branch)
{
	key  = _key[0];
	branch = _branch[0];

	_branch[0] = _branch[1];
	for (int i=0;i<_keys-1;i++)
	{
		_key[i] = _key[i+1];
		_branch[i+1] = _branch[i+2];
	}
	--_keys;
	setmodified();
}

template <class KEY>
void node<KEY>::remove_rightmost_pair(KEY &key,long &branch)
{
	key  = _key[_keys-1];
	branch = _branch[_keys];
	--_keys;
	setmodified();
}

template <class KEY>
void node<KEY>::append(node &add,const KEY &key)
{
	assert( _keys + add._keys + 1 < NODEKEYS );
	
	int i=_keys+1,j=0;
	for (;j<add._keys;i++,j++)
	{
		_key[i] = add._key[j];
		_branch[i] = add._branch[j];
	}
	_branch[i] = add._branch[j];
	_key[_keys] = key;

	_keys+=add._keys+1;
	setmodified();
}

template <class KEY>
void node<KEY>::assign(node &nd)
{
	_keys = nd._keys;
	
	fileblock::assign(&nd);
}
