///////////////////////////////////////////////////////////////////////////////
//                                                         
// CegoBTreeNode.cc
// -----------------
// Cego btree node class implementation
//     
// Design and Implementation by Bjoern Lemke               
//     
// (C)opyright 2000-2013 Bjoern Lemke
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2, or (at your option)
// any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330,
// Boston, MA 02111-1307, USA.
//
// IMPLEMENTATION MODULE
//
// Class: CegoBTreeNode
// 
// Description: This class handles operations on btree elements.
//              These elements either can be nodes or leafs and depending on the type, the corresponding methods are available.
//
// Status: 2.16
//
///////////////////////////////////////////////////////////////////////////////

// base includes
#include <lfc/Exception.h>

// cego includes
#include "CegoBTreeNode.h"
#include "CegoDataPointer.h"

#include <string.h>
#include <stdlib.h>

// must match the value of method CegoDataPointer.getEncodingLenth 
#define DPENCODINGLENGTH 3*sizeof(int)

CegoBTreeNode::CegoBTreeNode()
{
    _pI = 0;
    _len = 0;
    _keyLen = 0;
    _fileId = 0;
    _pageId = 0;
    _nextFileId = 0;
    _nextPageId = 0;
    _pNextChild = 0;
}

CegoBTreeNode::~CegoBTreeNode()
{
}

void CegoBTreeNode::setType(NodeType nt)
{
    _nt = nt;
}

const CegoBTreeNode::NodeType CegoBTreeNode::getType()
{
    return _nt;
}

void CegoBTreeNode::setPtr(void* p, int len)
{
    _pI = p;
    _len = len;
}

void* CegoBTreeNode::getPtr()
{
    return _pI;
}

int CegoBTreeNode::getLen() const
{
    return _len;
}

void CegoBTreeNode::setFileId(int fileId)
{
    _fileId = fileId;
}

int CegoBTreeNode::getFileId() const
{
    return _fileId;
}

void CegoBTreeNode::setPageId(int pageId)
{
    _pageId = pageId;
}

int CegoBTreeNode::getPageId() const
{
    return _pageId;
}

void CegoBTreeNode::setNextFileId(int fileId)
{
    _nextFileId = fileId;
}

int CegoBTreeNode::getNextFileId() const
{
    return _nextFileId;
}

void CegoBTreeNode::setNextPageId(int pageId)
{
    _nextPageId = pageId;
}

int CegoBTreeNode::getNextPageId() const
{
    return _nextPageId;
}

void CegoBTreeNode::initNode()
{
    if ( _pI )
    {
	int numEntry = 0;
	memcpy(_pI, &numEntry, sizeof(int));
	return;
    }
    throw Exception(EXLOC, Chain("BTree node not set up"));
}

int CegoBTreeNode::numEntries()
{
    if ( _pI )
    {
	int n;
	memcpy(&n, _pI, sizeof(int));
	return n;
    }
    throw Exception(EXLOC, Chain("BTree node not set up"));
}

void CegoBTreeNode::incEntries()
{
    if ( _pI )
    {
	int n;
	memcpy(&n, _pI, sizeof(int));
	n++;
	memcpy(_pI, &n, sizeof(int));
	return;
    }
    throw Exception(EXLOC, Chain("BTree node not set up"));
}

void CegoBTreeNode::decEntries()
{
    if ( _pI )
    {
	int n;
	memcpy(&n, _pI, sizeof(int));
	n--;
	memcpy(_pI, &n, sizeof(int));
	return;
    }
    throw Exception(EXLOC, Chain("BTree node not set up"));
}

int CegoBTreeNode::maxEntries()
{
    if ( _nt == LEAF )
    {
	return ( _len - sizeof(int) )  / ( _keyLen + DPENCODINGLENGTH );
    }
    else if ( _nt == NODE )
    {	
	return ( _len - sizeof(int) - 2 * sizeof(int) )  / ( _keyLen + 2 * sizeof(int) );
    }
    else
    {
	throw Exception(EXLOC, Chain("Unknown btree node type"));
    }
}

int CegoBTreeNode::getEntrySize() const
{
    if ( _nt == LEAF )
    {
	return _keyLen + DPENCODINGLENGTH;
    }
    else if ( _nt == NODE )
    {	
	return _keyLen + 2 * sizeof(int);
    }
    else
    {
	throw Exception(EXLOC, Chain("Unknown btree node type"));
    }
}

void CegoBTreeNode::getChildPage(const CegoBTreeValue& iv, int& fileId, int& pageId)
{
    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    int ne = numEntries();

    if ( ne == 0 )
	throw Exception(EXLOC, "No child entries avaiable");

    bool posFound=false;
    int i=0;
    while ( i < ne && posFound == false)
    {

	char* pKey = (char*)((long)_pI + sizeof(int)) + 2 * sizeof(int) + i * getEntrySize();
	CegoBTreeValue nv;
	nv.setPtr(pKey);

	if ( iv.isHigher(nv, _pSchema) )
	{
	    i++;
	}
	else
	{
	    posFound = true;
	}
    }

    /*
    cout << "Offset is " <<  sizeof(int) + 2 * sizeof(int) + i * getEntrySize() << endl;
    cout << "Position is " << i << endl;
    cout << "NumEntries are " << ne << endl;
    */

    char* p = (char*)((long)_pI + sizeof(int)) + i * getEntrySize();
    
    memcpy(&fileId, p, sizeof(int));
    p+=sizeof(int);
    memcpy(&pageId, p, sizeof(int));
    return;
    
}


void CegoBTreeNode::setSchema(ListT<CegoField>* pSchema, int keyLen)
{
    _pSchema = pSchema;

    _keyLen = keyLen;

    /*
    CegoField *pF = _schema.First();
    while ( pF )
    {
	_keyLen += pF->getLength();
	pF = _schema.Next();
    }
    */
}

/* addValue - old version */

/*
bool CegoBTreeNode::addValue(const CegoBTreeValue& iv, const CegoDataPointer& dp, const Chain& btreeName, bool isUnique)
{

    if ( _nt == NODE )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    int ne = numEntries();

    if ( ne == maxEntries() )
	return false;

    char* pKey = (char*)((long)_pI + sizeof(int));

    CegoBTreeValue nv;

    bool isInserted = false;
    
    int i=0;
    while ( i < ne )
    {
	nv.setPtr(pKey);
	
	if ( isUnique )
	{
	    if ( nv.isEqual(iv, _pSchema))
	    {
		Chain msg = Chain("Duplicate key on unique btree ") + btreeName;
		throw Exception(EXLOC, msg);
	    }
	}
	if ( nv.isHigher(iv, _pSchema) )
	{
	    shiftEntries(i, 1);
	    
            // copy iv to free slot
	    memcpy(pKey, iv.getPtr(), _keyLen);
	    char* pDP = (char*)((long)pKey + _keyLen);
	    dp.encode(pDP);

	    incEntries();

	    return true; 	    
	}
	pKey += getEntrySize();
	i++;
    }

    // adding value at the end
    memcpy(pKey, iv.getPtr(), _keyLen);
    char* pDP = (char*)((long)pKey + _keyLen);
    dp.encode(pDP);

    incEntries();

    return true;
}
*/


/* add value - new version */

bool CegoBTreeNode::addValue(const CegoBTreeValue& iv, const CegoDataPointer& dp, const Chain& btreeName, bool isUnique)
{

    // cout << "Adding value " << iv.toChain(_pSchema) << endl;

    if ( _nt == NODE )
	throw Exception(EXLOC, Chain("Invalid method for node type"));
    
    int ne = numEntries();
    
    if ( ne == maxEntries() )
	return false;
   
    if ( ne == 0 )
    {

	char* pKey = (char*)((long)_pI + sizeof(int));
	memcpy(pKey, iv.getPtr(), _keyLen);
	char* pDP = (char*)((long)pKey + _keyLen);
	dp.encode(pDP);
	
	incEntries();
	return true;
	
    }

    bool isInserted = false;
    
    
    int lb=0;
    int rb=ne;

    int i = (lb+rb) / 2;
    
    bool posFound=false;

    while ( posFound == false )
    {
	
	// cout << "lb=" << lb << " rb=" << rb << endl;

	i = (lb+rb) / 2;

	// cout << "Checking position " << i << endl;

	CegoBTreeValue nv1;
	CegoBTreeValue nv2;
	

	nv1.setPtr((char*)((long)_pI + sizeof(int)) + i * getEntrySize());
	CegoBTreeValue::Comparison valueComp1 = iv.comp(nv1, _pSchema);
	CegoBTreeValue::Comparison valueComp2;

	if ( i+1 == ne )
	{
	    // cout << "XXXX Fixing v2 to less .." << endl;
	    valueComp2 = CegoBTreeValue::LESS;
	}
	else
	{
	    nv2.setPtr((char*)((long)_pI + sizeof(int)) + (i+1)*getEntrySize());
	    valueComp2 = iv.comp(nv2, _pSchema);
	}
	
	
	
	// cout << "VC1=" << valueComp1 << endl;
	// cout << "VC2=" << valueComp2 << endl;
	

	if ( isUnique && ( valueComp1 == CegoBTreeValue::EQUAL || valueComp2 == CegoBTreeValue::EQUAL ))
	{
	    Chain msg = Chain("Duplicate key on unique btree ") + btreeName;
	    throw Exception(EXLOC, msg);
	}

	if ( ( valueComp1 == CegoBTreeValue::MORE || valueComp1 == CegoBTreeValue::EQUAL )
	     && ( valueComp2 == CegoBTreeValue::LESS || valueComp2 == CegoBTreeValue::EQUAL ) )
	{
	    // cout << "CASE-A" << endl;
	    i++;
	    posFound=true;
	}
	else if ( valueComp2 == CegoBTreeValue::MORE )
	{
	    // cout << "CASE-B" << endl;
	    if ( i == ne )
		posFound = true;
	    else
		lb=i;	    	    	    
	}
	else
	{
	    // cout << "CASE-C" << endl;
	    if ( i == 0 )
		posFound = true;
	    else
		rb=i;
	}
	// sleep(1);
    }

    // cout << "Position found at : " << i << endl;

    if ( i < ne )
    {
	shiftEntries(i, 1);
    }

    char* pKey = (char*)((long)_pI + sizeof(int) + i* getEntrySize());    
    memcpy(pKey, iv.getPtr(), _keyLen);
    char* pDP = (char*)((long)pKey + _keyLen);
    dp.encode(pDP);
	
    incEntries();
    return true;
}


bool CegoBTreeNode::deleteValue(const CegoBTreeValue& iv, const CegoDataPointer& dp)
{

    if ( _nt == NODE )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    int ne = numEntries();

    if ( ne == 0 )
	return false;

    char* pKey = (char*)((long)_pI + sizeof(int));

    CegoBTreeValue lv;

    bool isInserted = false;
    
    int i=0;
    while ( i < ne )
    {
	lv.setPtr(pKey);

	CegoDataPointer ldp;
	ldp.decode(pKey + _keyLen);

	if ( lv.isEqual(iv, _pSchema) && ldp == dp)
	{
	    shiftEntries(i+1, -1);	    
	    decEntries();
	    return true; 	    
	}
	pKey += getEntrySize();
	i++;
    }

    return false;
}


bool CegoBTreeNode::addNode(const CegoBTreeValue& iv, const CegoBTreeNode& node)
{
    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));
    
    int ne = numEntries();       	
    if ( ne == maxEntries() || ne == 0 )
	return false;
    
    bool posFound=false;
    char* p = 0;
    int i=0;	    
    
    while ( i < ne && posFound == false)
    {
	p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + i * getEntrySize());
	CegoBTreeValue nv(p);
	if ( nv.isHigher(iv, _pSchema) )
	{
	    shiftEntries(i, 1);
	    posFound=true;
	}
	else
	{	    
	    i++;
	}
    }
    
    p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + i * getEntrySize());
    
    // put index value
    memcpy(p, iv.getPtr(), _keyLen);
    p+=_keyLen;
    
    // put child pointer
    int fileId = node.getFileId();
    memcpy(p, &fileId, sizeof(int));
    p+=sizeof(int);
    int pageId = node.getPageId();
    memcpy(p, &pageId, sizeof(int));
    p+=sizeof(int);
    
    incEntries();
    
    return true;

}

void CegoBTreeNode::split(CegoBTreeNode& n)
{
    int pos; 

    if ( _nt == LEAF )
    {
	pos = numEntries() / 2;
	char* srcPtr = (char*)((long)_pI + sizeof(int) + pos * getEntrySize());
	char* destPtr = (char*)((long)n._pI + sizeof(int));
	int s =  ( numEntries() - pos ) * getEntrySize();
	memcpy(destPtr, srcPtr, s);
	
    }
    else if ( _nt == NODE )
    {
	pos = numEntries() / 2;
	char* srcPtr = (char*)((long)_pI + sizeof(int) + pos * getEntrySize());
	char* destPtr = (char*)((long)n._pI + sizeof(int));
	int s =  ( numEntries() - pos ) * getEntrySize() + 2 * sizeof(int);
	memcpy(destPtr, srcPtr, s);	
    }

    int s1 = pos;
    int s2 = numEntries() - pos;
    memcpy(_pI, &s1, sizeof(int));
    memcpy(n._pI, &s2, sizeof(int));    

}

void CegoBTreeNode::shiftEntries(int pos, int offset)
{

    if ( _nt == LEAF )
    {
	char* srcPtr = (char*)((long)_pI + sizeof(int) + pos * getEntrySize());
	char* destPtr = (char*)((long)_pI + sizeof(int) + ( pos + offset) * getEntrySize());
	int shiftSize = ( numEntries() - pos ) * getEntrySize();
	memcpy(destPtr, srcPtr, shiftSize);
    }
    else if ( _nt == NODE )
    {
	char* srcPtr = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + pos * getEntrySize());
	char* destPtr = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + ( pos + offset ) * getEntrySize());
	int shiftSize = ( numEntries() - pos ) * getEntrySize();
	memcpy(destPtr, srcPtr, shiftSize);
    }
}


CegoBTreeValue CegoBTreeNode::getMin()
{

    if ( numEntries() == 0 )
	throw Exception(EXLOC, Chain("No index values available in node"));
          
    if ( _nt == LEAF )    
    {
	char* p = (char*)((long)_pI + sizeof(int));
	CegoBTreeValue iv(p);
	return iv;
    }
    else if ( _nt == NODE )
    {
	char* p = (char*)((long)_pI + sizeof(int) + 2*sizeof(int));
	CegoBTreeValue iv(p);
	return iv;
    }
    else
    {
	throw Exception(EXLOC, Chain("Invalid node type"));
    }
}

CegoBTreeValue CegoBTreeNode::getMax()
{
    int pos = numEntries() - 1;

    if ( pos > 0 )
    {
	char* p;
	if ( _nt == LEAF )
	{
	    p = (char*)((long)_pI + sizeof(int) + pos * getEntrySize());
	}
	else
	{
	    p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + pos * getEntrySize());
	}
	CegoBTreeValue iv(p);
	return iv;

    }
    throw Exception(EXLOC, "No index values available in node");
}



/* propagate - old version */

bool CegoBTreeNode::propagate(const CegoBTreeValue& iv, const CegoBTreeNode& leftNode, const CegoBTreeNode& rightNode)
{

    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));
 
    int ne = numEntries();       	
    if ( ne == maxEntries() )
	return false;
    
    if ( ne == 0 )
    {
	// first entry
	
	char* p = (char*)((long)_pI + sizeof(int));
	int fileId, pageId;
	
	// put left child pointer
	fileId = leftNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	
	pageId = leftNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	// put index value
	memcpy(p, iv.getPtr(), _keyLen);
	p+=_keyLen;
	
	// put right child pointer
	fileId = rightNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	pageId = rightNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	incEntries();
	
	return true;
    }
    else
    {


	bool posFound=false;
	char* p = 0;
	int i=0;	    
	
	while ( i < ne && posFound == false)
	{
	    p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + i * getEntrySize());
	    CegoBTreeValue nv(p);
	    if ( iv.isHigher(nv, _pSchema) )
	    {
		i++;
	    }
	    else
	    {
		shiftEntries(i, 1);
		posFound=true;
	    }
	}
	
	p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + i * getEntrySize());
	
	// put index value
	memcpy(p, iv.getPtr(), _keyLen);
	p+=_keyLen;
	
	// put child pointer
	int fileId = rightNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	int pageId = rightNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	incEntries();
	
	return true;


    }
}


/* propagate - new version - still contains a bug and dows not improve performance */

/*
bool CegoBTreeNode::propagate(const CegoBTreeValue& iv, const CegoBTreeNode& leftNode, const CegoBTreeNode& rightNode)
{

    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));
 
    int ne = numEntries();       	
    if ( ne == maxEntries() )
	return false;
    
    if ( ne == 0 )
    {
	// first entry
	
	char* p = (char*)((long)_pI + sizeof(int));
	int fileId, pageId;
	
	// put left child pointer
	fileId = leftNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	
	pageId = leftNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	// put index value
	memcpy(p, iv.getPtr(), _keyLen);
	p+=_keyLen;
	
	// put right child pointer
	fileId = rightNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	pageId = rightNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	incEntries();
	
	return true;
    }
    else
    {

	int lb=0;
	int rb=ne;
	
	int i = (lb+rb) / 2;
	
	bool posFound=false;
	
	while ( posFound == false )
	{
	    i = (lb+rb) / 2;
	    CegoBTreeValue nv1;
	    CegoBTreeValue nv2;

	    nv1.setPtr((char*)((long)_pI + sizeof(int)) + 2*sizeof(int) + i * getEntrySize());
	    CegoBTreeValue::Comparison valueComp1 = iv.comp(nv1, _pSchema);
	    CegoBTreeValue::Comparison valueComp2;
	    
	    if ( i+1 == ne )
	    {
		valueComp2 = CegoBTreeValue::LESS;
	    }
	    else
	    {
		nv2.setPtr((char*)((long)_pI + sizeof(int)) + 2*sizeof(int) + (i+1)*getEntrySize());
		valueComp2 = iv.comp(nv2, _pSchema);
	    }
	    
	    if ( ( valueComp1 == CegoBTreeValue::MORE || valueComp1 == CegoBTreeValue::EQUAL )
		 && ( valueComp2 == CegoBTreeValue::LESS || valueComp2 == CegoBTreeValue::EQUAL ) )
	    {
		// cout << "Propagation case : A" << endl;
		i++;
		posFound=true;
	    }
	    else if ( valueComp2 == CegoBTreeValue::MORE )
	    {

		// cout << "Propagation case : B" << endl;
		if ( i == ne )
		    posFound = true;
		else
		    lb=i;	    	    	    
	    }
	    else
	    {
		// cout << "Propagation case : C" << endl;
		if ( i == 0 )
		    posFound = true;
		else
		    rb=i;
	    }
	    // sleep(1);
	}


	if ( i < ne )
	{
	    shiftEntries(i, 1);
	}

	char* p = (char*)((long)_pI + sizeof(int) + 2 * sizeof(int) + i * getEntrySize());
	
	// put index value
	memcpy(p, iv.getPtr(), _keyLen);
	p+=_keyLen;
	
	// put child pointer
	int fileId = rightNode.getFileId();
	memcpy(p, &fileId, sizeof(int));
	p+=sizeof(int);
	int pageId = rightNode.getPageId();
	memcpy(p, &pageId, sizeof(int));
	p+=sizeof(int);
	
	incEntries();
	
	return true;

    }
}

*/

 
CegoBTreeNode& CegoBTreeNode::operator = (const CegoBTreeNode& n)
{
    _nt = n._nt;
    _pI = n._pI;
    _len = n._len;
    _fileId = n._fileId;
    _pageId = n._pageId;
    _nextFileId = n._nextFileId;
    _nextPageId = n._nextPageId;
    _keyLen = n._keyLen;
    _pSchema = n._pSchema;
    return (*this);
}

void CegoBTreeNode::printNode(int level)
{

    int n = numEntries();

    if ( _nt == LEAF )
    {

	cout << levelIndent(level) << "------- LEAF -------" << endl;
	cout << levelIndent(level) << "FileId=" << _fileId << " PageId=" << _pageId << endl;

	int i = 0;
	while ( i < n )
	{
	    cout << levelIndent(level) << "Entry " << i << " : ";
	    
	    char* srcPtr = (char*)((long)_pI + sizeof(int) + i * getEntrySize());
	    CegoBTreeValue iv;
	    iv.setPtr(srcPtr);
	    srcPtr += _keyLen;
	    CegoDataPointer dp;
	    dp.decode(srcPtr);
	    cout << iv.toChain(_pSchema) << " " << dp << endl;	  
	    i++;
	}
	cout << levelIndent(level) << "Next Page : " << _nextFileId << " " << _nextPageId << endl;

	cout << levelIndent(level) << "--------------------" << endl;
    }
    else if ( _nt == NODE )
    {
	cout << levelIndent(level) << "####### NODE ####### " << endl;
	cout << levelIndent(level) << "FileId=" << _fileId << " PageId=" << _pageId << endl;

	int fileId, pageId;

	char* p = (char*)((long)_pI + sizeof(int));
	
	memcpy(&fileId, p, sizeof(int));
	p+=sizeof(int);
	memcpy(&pageId, p, sizeof(int));
			  
	cout << levelIndent(level) << "Child : " << fileId << "," << pageId << endl;

	int i = 0;
	while ( i < n )
	{
	    cout << levelIndent(level) << "Key " << i << " : ";
	    
	    p = (char*)((long)_pI + sizeof(int) + 2*sizeof(int) + i * getEntrySize());
	    CegoBTreeValue iv;
	    iv.setPtr(p);
	    cout << iv.toChain(_pSchema) << endl;
	    p += _keyLen;
	    
	    memcpy(&fileId, p, sizeof(int));
	    p+=sizeof(int);
	    memcpy(&pageId, p, sizeof(int));
	    
	    cout << levelIndent(level) << "Child : " << fileId << "," << pageId << endl;


	    i++;
	}
	cout << levelIndent(level) << "################## " << endl;
    }
    else
    {
	cout << levelIndent(level) << "??? UNDEFINED ??? " << endl;
    }
}

void CegoBTreeNode::reset()
{
    _pNextChild = (char*)((long)_pI + sizeof(int));
}

bool CegoBTreeNode::nextChildPointer(int &fileId, int &pageId)
{

    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    if ( (long)_pNextChild > (long)_pI + sizeof(int) + numEntries() * getEntrySize() )
	return false;
    
    memcpy(&fileId, _pNextChild, sizeof(int));
    _pNextChild+=sizeof(int);
    memcpy(&pageId, _pNextChild, sizeof(int));
    _pNextChild+=sizeof(int);
    
    _pNextChild+=_keyLen;
    
    return true;

}

bool CegoBTreeNode::rightChild(CegoBTreeValue& val)
{

    if ( _nt == LEAF )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    
    if ( (long)_pNextChild > (long)_pI + sizeof(int) + numEntries() * getEntrySize() )
	return false;
    
    val.setPtr(_pNextChild - _keyLen);
    return true;
}

bool CegoBTreeNode::nextValue(CegoBTreeValue& val, CegoDataPointer& dp)
{
    if ( _nt == NODE )
	throw Exception(EXLOC, Chain("Invalid method for node type"));

    if ( (long)_pNextChild >= (long)_pI + sizeof(int) + numEntries() * getEntrySize() )
	return false;
    
    val.setPtr(_pNextChild);
    _pNextChild +=_keyLen;
    dp.decode(_pNextChild);
    _pNextChild += DPENCODINGLENGTH;
    
    return true;
    
}

Chain CegoBTreeNode::levelIndent(int level)
{
    Chain s;
    while ( level > 0 )
    {
	s += Chain(" ");
	level--;
    }
    return s;
}
