#define IST_REPS_REP_BLOCK int(floor((BLOCKSIZE/(sizeof(REP_TYPE)+sizeof(long)))))

//#define IST_NODE_SIZE (BLOCKSIZE/(sizeof(REP_TYPE)+sizeof(long)))
struct KEY_BRANCH_PAIR
{
	REP_TYPE key;
	long branch;
};

struct LIMITS
{
	REP_TYPE a;
	REP_TYPE b;
};

struct RIGHT_LIMIT
{
	long		lnextblockpos;
	REP_TYPE	parent_b;
	bool bhasnextblock;
};

class istnode
{
protected:
	long	_firstblock;//refers to the first istnode_block position

private:
	long get_block_branch(int i) { return _firstblock+(BLOCKSIZE*i); };

public:
	istnode(long firstblock);
	~istnode();

	long pos() { return _firstblock; };
	void build_node(KEY_BRANCH_PAIR *pkey_branch,int firstIndex,int lastindex);
	bool find_btree(const REP_TYPE &,long &,int,LIMITS,bool);
};


class istnode_block : public fileblock
{
protected:
	REP_TYPE *	_reps;//representatives
	long *		_branches;//children
	int			_size;


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

public:
	static fileobject * pindexfile;

	istnode_block(long pos,fileobject *pfile=pindexfile);
	~istnode_block();

	int build_block(KEY_BRANCH_PAIR *pkey_branch,int firstIndex,int lastindex,int step);
	int fill_single_keys(KEY_BRANCH_PAIR *,int,int);
	bool find_btree_incerementaly(const REP_TYPE &,long &,int,RIGHT_LIMIT,bool &,bool);
	bool find_btree(const REP_TYPE &,long &,RIGHT_LIMIT,bool &);
	long get_first_branch() { return _branches[0]; };
	REP_TYPE get_first_representative() { assert(_size>0); return _reps[0]; };

};
fileobject * istnode_block::pindexfile = 0;


istnode::istnode(long firstblock)
{
	_firstblock = firstblock;
}

istnode::~istnode()
{
}

bool istnode::find_btree(const REP_TYPE &key,long &pos,int node_keys,LIMITS limits,bool bexistnext)
{
	int reps= floor(pow(node_keys , (double(IST_REPS_REP_BLOCK) - double(1))/double(IST_REPS_REP_BLOCK)));
	int step = floor( double(node_keys)/double(reps) );
	reps += ceil( double(node_keys-reps*step)/step );

	int nodeblocks = ceil(double(reps)/double(IST_REPS_REP_BLOCK));

	bool b_use_reps = (nodeblocks>1);
	if ( !b_use_reps )
	{
		//recalculate needed blocks according to node_keys not according to reps ...
		reps = node_keys;
		nodeblocks = ceil(double(reps)/double(IST_REPS_REP_BLOCK));
	}

	//make an ist gussing
	int guessindex = ToInt((double(key-limits.a)/double(limits.b-limits.a))*double(reps));
	int guessblock = floor(double(guessindex)/IST_REPS_REP_BLOCK);
	bool b_go_next;
	int curblock =  guessblock<nodeblocks?guessblock:nodeblocks-1;

	while( curblock>=0 && curblock<nodeblocks )
	{
		bool bhasnext = true;
		//load the block ....
		istnode_block searchblock( get_block_branch(curblock) );
		
		//create the limit structure, so that i can pass node limits to deeper istnodes...
		RIGHT_LIMIT lim;
		if ( curblock<nodeblocks-1 )
		{
			lim.bhasnextblock = true;
			lim.lnextblockpos = get_block_branch(curblock+1);
		}
		else
		{
			lim.bhasnextblock = false;
			lim.parent_b = limits.b;

			bhasnext = bexistnext;
		}

		if ( b_use_reps )
		{
			//search inside the block incrementally which means that it will traver deeper to find
			//the btree
			//b_go_next is a return value meaning the direction where i should go next
			//bhasnext is value which says if there is another block which could have the key i need
			//this is used so that if a key is greater than the greater key of my ist tree
			//i will now that there are no more blocks and o i should return the 
			//rightmost btree i find!
			//lim has information about the sistuation of the current block (if there exeist another block
			//next and aother)
			if ( searchblock.find_btree_incerementaly(key,pos,step,lim,b_go_next,bhasnext) )
			{
				printf("Key %d interpolation SUCCESS!!!!\n",key);
				successcouner ++;
				return true;
			}

			//if it come here then either there is not any representative less than my key
			//or the last representative is less than my key and the first representative of
			//the next block is also less than my key, this means
			//that the current block isn't the wright choise...
			printf("Key %d interpolation error\n",key);
			errorcouner++;
		}
		else
		{
			//search inside the block not incrementally which means that it will only travel this level
			//as this level has the actual bptrees ...
			if ( searchblock.find_btree(key,pos,lim,b_go_next) )
			{
				printf("Key %d single keys interpolation SUCCESS!!!!\n",key);
				successcouner ++;
				return true;
			}

			printf("Key %d single keys interpolation error\n",key);
			errorcouner++;
		}

		if ( b_go_next )
			curblock++;
		else
			curblock--;
	}
	
	//if i use the node keys then it must be found or else everything is wrong!
	if ( !b_use_reps )
		assert(false);

	return false;
}

void istnode::build_node(KEY_BRANCH_PAIR *pkey_branch,int firstIndex,int lastindex)
{
	assert( _firstblock == fileblock::newpos);

	int node_keys = lastindex-firstIndex+1;
	int reps= floor(pow( node_keys , (double(IST_REPS_REP_BLOCK) - double(1))/double(IST_REPS_REP_BLOCK)));
	int step = floor( double(node_keys)/double(reps) );
	
	//recalculate resp so that it will eat the error of step ...
	reps += ceil( double(node_keys-reps*step)/step );

	//i use ceil for neededblocks so that every reps or key will be inserted ...
	int needeblocks = ceil(double(reps)/double(IST_REPS_REP_BLOCK));

	//if neededblock is less than 1 block then i must add the btrees ...
	//but if step is greater than 1 (eg 2) then it will insert only the first ones ...
	//that's why here i change the step to 1 so that every btree will be inserted, also i re calculate the 
	//needed block according to all the keys now
	bool b_use_reps = (needeblocks>1);
	if ( !b_use_reps )
	{
		//recalculate needed blocks according to node_keys not according to reps ...
		needeblocks = ceil(double(node_keys)/double(IST_REPS_REP_BLOCK));
	}

	//Get the needed blocks ...
	for (int i=0;i<needeblocks;i++)
	{
		istnode_block newblock(fileblock::newpos);
		if ( i==0 )
			_firstblock = newblock.pos();
	}

	//recursively fill the blocks and create and their chlidren 
	for (i=0;i<needeblocks;i++)
	{
		if ( b_use_reps )
		{
			istnode_block newblock( get_block_branch(i) );
			firstIndex = newblock.build_block(pkey_branch,firstIndex,lastindex,step);
		}
		else 
		{
			istnode_block newblock( get_block_branch(i) );
			firstIndex = newblock.fill_single_keys(pkey_branch,firstIndex,lastindex);
		}
	}
	
	//verify now that all reps have been inserted
	assert( firstIndex>lastindex );

/*

		//Get 1 single block and fill it with the keys, pointing at b-trees
		istnode_block newblock(fileblock::newpos);
		_firstblock = newblock.pos();
		newblock.fill_single_keys(pkey_branch,firstIndex,lastindex,step);
*/
}

istnode_block::istnode_block(long pos,fileobject *pfile):fileblock(pfile,pos)
{
	_reps = (REP_TYPE *) _block;
	_branches = (long *) (_block+sizeof(REP_TYPE)*IST_REPS_REP_BLOCK);
	initdata();
}

istnode_block::~istnode_block()
{
	if ( modified() )
		markdata();
}

bool istnode_block::find_btree_incerementaly(const REP_TYPE &key,long &pos,int node_keys,
											RIGHT_LIMIT limitinfo,bool &b_go_next,bool bexistnextnode)
{
	assert( _size!= 0 );

	b_go_next = false;

	for (int i=_size-1;(i>=0 && key<_reps[i]);i--)
		;

	if ( i>=0)
	{
		LIMITS childlimits;
		childlimits.a = _reps[i];

		if ( i<_size-1 )
			childlimits.b = _reps[i+1];
		else
		{
			b_go_next = true;

			//the key is bigger than the last item so, it may be valid
			//To ensure this i will have to look into the next block and make sure that the first
			//key of it is bigger than my key.
			//If the guessing is wrong then this node could be much far away to the left of
			//the actual block

			if ( !limitinfo.bhasnextblock )
			{
				childlimits.b = limitinfo.parent_b;

				if ( bexistnextnode && key>childlimits.b )
					return false;
			}
			else
			{
				istnode_block nextblock( limitinfo.lnextblockpos );
				childlimits.b = nextblock.get_first_representative();

				if ( key >= childlimits.b )
					return false;
			}

		}

		istnode newnode(_branches[i]);
		return newnode.find_btree(key,pos,node_keys,childlimits,bexistnextnode);
	}

	return false;
}

bool istnode_block::find_btree(const REP_TYPE &key,long &pos,RIGHT_LIMIT limitinfo,bool &b_go_next)
{
	assert( _size!= 0 );

	b_go_next = false;

	for (int i=_size-1;(i>=0 && key<_reps[i]);i--)
		;

	if ( i>=0 )
	{
		if ( i == _size-1)
		{
			b_go_next = true;

			//the key is bigger than the last item so, it may be valid
			//To ensure this i will have to look into the next block and make sure that the first
			//key of it is bigger than my key.
			//If the guessing is wrong then this node could be much far away to the left of
			//the actual block

			if ( !limitinfo.bhasnextblock )
			{
				if ( key>=limitinfo.parent_b )
					return false;
			}
			else
			{
				istnode_block nextblock( limitinfo.lnextblockpos );
				REP_TYPE testkey = nextblock.get_first_representative();

				if ( key >= testkey )
					return false;
			}
		}
		
		//found it!
		pos = _branches[i];
		return true;
	}

	return false;
}

///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
//START OF BUILDING ROUTINES

int istnode_block::build_block(KEY_BRANCH_PAIR *pkey_branch,int curIndex,int lastindex,int step)
{
	assert(_size == 0);

	while( (_size<IST_REPS_REP_BLOCK) && (curIndex<=lastindex) )
	{
		_reps[_size] = pkey_branch[curIndex].key;

		istnode newnode(fileblock::newpos);
		newnode.build_node(pkey_branch,curIndex,curIndex+step-1);
		//fill the child with keys from the current key until the most previous of the next key of this node
		_branches[_size] = newnode.pos();

		_size++;

		curIndex += step;
	}

	assert( _size!= 0 );

	setmodified();

	return curIndex;
}

int istnode_block::fill_single_keys(KEY_BRANCH_PAIR *pkey_branch,int firstIndex,int lastindex)
{
	assert( _size==0 );

	for (int i=firstIndex;(i<=lastindex && _size<IST_REPS_REP_BLOCK);i++)
	{
		_reps[_size] = pkey_branch[i].key;
		_branches[_size] = pkey_branch[i].branch;

		_size++;
	}

	assert( _size!= 0 );
	setmodified();

	return i;
}

//END OF BUILDING ROUTINES
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////


void istnode_block::initdata()
{
	for (_size=0;_size<IST_REPS_REP_BLOCK && _branches[_size];_size++)
		;
}

void istnode_block::markdata()
{
	if ( _size<IST_REPS_REP_BLOCK )
		_branches[_size] = filewrapper::NO_BRANCH;
}
