#define lvalidate(a) assert( (a)>=0 && (a)<_keys)
#define LEAFKEYS ( (BLOCKSIZE - sizeof(long))/(sizeof(KEY)+sizeof(long)) )

template <class KEY>
class leaf : public fileblock
{
protected:
	KEY *			_key;
	long *			_data;
	long &			_next;
	int				_keys;
	
	void initdata();
	void markdata();
		
public:
	static fileobject * pindexfile;

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

	int		keycount() const			{ return _keys; };
	int		find(const KEY &) const;
	KEY		key(int pos) const		{ lvalidate(pos); return _key[pos]; };
	long	data(int pos) const		{ lvalidate(pos); return _data[pos]; };
	long	next() const			{ return _next; };
	bool	has_room() const		{ return _keys!=LEAFKEYS; };
	bool	is_rich() const			{ return _keys>LEAFKEYS/2; };
	bool	is_half_full() const	{ return _keys>=LEAFKEYS/2; };
	void	insert(const KEY &,long);
	void	splitto(leaf &,const KEY &,long);
	long	removekey(int);
	void	append(const leaf &);
	void	operator=(leaf &){ assert(false); };
};
template <class KEY> fileobject * leaf<KEY>::pindexfile = 0;

template <class KEY>
leaf<KEY>::leaf(long pos,fileobject *pfile):fileblock(pfile,pos),_next(* (long *)_block)
{
	_key = (KEY *) (_block+sizeof(long));
	_data = (long *) (_block+sizeof(long)+sizeof(KEY)*LEAFKEYS);
	initdata();
}
				
template <class KEY>					   
leaf<KEY>::leaf(fileobject *pfile):fileblock(pfile,invalidpos),_next(* (long *)_block)
{
	_key = (KEY *) (_block+sizeof(long));
	_data = (long *) (_block+sizeof(long)+sizeof(KEY)*LEAFKEYS);
}

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

template <class KEY>
void leaf<KEY>::initdata()
{
	for(_keys=0;_keys<LEAFKEYS && _data[_keys];_keys++)
		;
}

template <class KEY>
void leaf<KEY>::markdata()
{
	if ( _keys<LEAFKEYS )
		_data[_keys] = 0;
}

template <class KEY>
int leaf<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;
		else if ( key < _key[mid] )
			last = mid-1;
		else 
			first = mid+1;

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

	return -1;
}

template <class KEY>
void leaf<KEY>::insert(const KEY &key,long datapos)
{
	int i;
	for (i=0;i<_keys && _key[i]<key;i++)
		;

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

template <class KEY>
void leaf<KEY>::splitto(leaf &lf,const KEY &key,long datapos)
{
	int median = _keys/2;
	if ( key<_key[median] )
	{
		int j=0;
		for (int i=median;i<_keys;i++,j++)
		{
			lf._data[j] = _data[i];
			lf._key[j] = _key[i];
		}
		lf._keys = j;
		_keys = median;
		lf._next = _next;
		_next = lf.pos();
		insert(key,datapos);
	}
	else
	{
		int j=0;
		for (int i=median+1;i<_keys;i++,j++)
		{
			lf._data[j] = _data[i];
			lf._key[j] = _key[i];
		}
		lf._keys = j;
		_keys = median+1;
		lf._next = _next;
		_next = lf.pos();
		lf.insert(key,datapos);
	}
	setmodified();
}

template <class KEY>
long leaf<KEY>::removekey(int i)
{
	long datapos = _data[i];

	for (;i<_keys-1;i++)
	{
		_key[i] = _key[i+1];
		_data[i] = _data[i+1];
	}
	--_keys;
	setmodified();
	return datapos;
}

template <class KEY>
void leaf<KEY>::append(const leaf &add)
{
	assert( _keys + add._keys < LEAFKEYS );
	
	for (int i=_keys,j=0;j<add._keys;i++,j++)
	{
		_key[i] = add._key[j];
		_data[i] = add._data[j];
	}
	_keys+=add._keys;
	setmodified();
}
