#include "cmxcheck.h"

#include <stdlib.h>
#include <time.h>

#include "cmxbtree.h"
#define TEST_SIZE   10000

int Order1[TEST_SIZE];
//int Order2[TEST_SIZE];
void Shuff( int *Order )
{
    srand( (unsigned)time( NULL ) );

    int i = 0;//, nRand;

    for( i = 0; i < TEST_SIZE; i ++ )
    {
        Order[i] = i*10;
    }
    int nRand;
    int tmp;
    i = TEST_SIZE -1;
    while( i > 0 )
    {
        nRand = abs( rand() % (i+1) );
        tmp = Order[i];
        Order[i] = Order[nRand];
        Order[nRand] = tmp;
        i --;
    }
}

void main( void )
{
    SCREEN_REPORT;
    SET_CHECK_LEAK;

    CMXBTree< int > bt;

    //while( true )
    {
    //int l;
    Shuff( Order1 );
    int i;
    
    //bt.DestroyTree();
    
    
    for( i = 0; i < TEST_SIZE; i ++ )
    {
        if( bt.InsertKey( Order1[i] ) < 0 )
        {
            printf(" BTree error \n");
        }
        
    }
    Shuff( Order1 );

    for( i = 0; i < TEST_SIZE; i ++ )
    {
        if( bt.InsertKey( Order1[i] ) < 0 )
        {
            printf(" BTree error \n");
        }
    }

    Shuff( Order1 );

    for( i = 0; i < TEST_SIZE; i ++ )
    {
        if( bt.InsertKey( Order1[i] ) < 0 )
        {
            printf(" BTree error \n");
        }
        
    }

/*
    CMXBTree< int >::GET_KEY cur;
    int *p1;
    p1 = bt.GetLastKey( &cur );
    i = 0;
    while( p1 )
    {
        printf("[%d]", *p1 );
        p1 = bt.GetPrevKey( &cur );
        i ++;
    }
    printf("\nTotal:[%d]\n", i );


    p1 = bt.GetFirstKey( &cur );
    i = 0;
    while( p1 )
    {
        printf("[%d]", *p1 );
        p1 = bt.GetNextKey( &cur );
        i ++;
    }
    printf("\nTotal:[%d]\n", i );
*/

    Shuff( Order1 );
    int *pLess, *pGreat, *pEqual;

    CMXBTree< int >::SEARCH_KEY sk, sk2;
    int *pNext, *pPrev;
    for( i = 0; i < TEST_SIZE; i ++ )
    {
        int key = Order1[i]  ;
        pEqual = bt.SearchKey( key, &sk, &pLess, &pGreat );
        sk2 = sk;
        //if( pEqual != NULL  )
        if( pEqual == NULL || key != *pEqual )
        {
            printf("Error!\n");
            continue;
        }
        pNext = bt.GetNextKey( &sk );
        pPrev = bt.GetPrevKey( &sk2 );

        if( pLess == NULL ) 
        {
            printf("Less:[%d]",Order1[i] );
            if( pGreat == NULL ) printf("Error");
            if( pPrev != NULL ) printf("Error");
            if( *pGreat != *pNext ) printf(" Error ");
        }
        if( pGreat == NULL ) 
        {
            printf("pGreat:[%d]",Order1[i] );
            if( pLess == NULL ) printf("Error");
            if( pNext != NULL ) printf("Error");
            if( *pLess != *pPrev ) printf("Error");
        }
        if( pLess && pGreat )
        {
            //if(*pGreat - *pLess != 10 ) printf("Error");
            if( *pGreat - Order1[i] != 10 ) printf("Error");
            if( Order1[i] - *pLess != 10 ) printf("Error");
            //if( *pGreat != *pNext ) printf("Error ");
            //if( *pLess != *pPrev ) printf("Error");
        }
        
    }

    
    for( i = 0; i < TEST_SIZE; i ++ )
    {
        if( bt.DeleteKey( Order1[i] ) < 0 )
        {
            printf(" BTree error \n");
        }
        
    }


//    printf("GetCount[%d] ", bt.GetCount() );
        printf(" GetCount[%d]\n", bt.GetCount() );
    //bt.DestroyTree();


    }

/*
        int k = 4;
        bt.InsertKey( k );
        bt.InsertKey( k );
*/


/*
        int nArray[TEST_SIZE];
        for( i = 0; i < TEST_SIZE; i++) nArray[i] = i;
        int nTotal = TEST_SIZE;
        
        while( nTotal )
        {
            i = ( 0 + nTotal - 1) / 2;

            if( InsertKey( nArray[i] ) != 0 )
                i = i;
            int l;
            for( l = i+1; l < nTotal; l ++)
                nArray[l-1] = nArray[l];
            nTotal --;
        }
*/

/*
        int *pTmp, nCount = 1;
        pTmp = bt.GetFirstKey();
        printf("[%d]", *pTmp );
        while( pTmp = bt.GetNextKey() )
        {
            printf("[%d]", *pTmp );
            nCount ++;
        }

        bt.SearchKey(k);
        bt.SearchNextKey();
*/




/*
        for( i = 0; i < TEST_SIZE; i ++)
            InsertKey( i );
        for( i = TEST_SIZE - 1; i >= 0; i--)
            DeleteKey( i); 
*/

/*
        l = 0;
        for( i = 0; i < TEST_SIZE; i ++ )
            if( pIndexLeafArr[i] ) l ++;
        if( l ) printf("pIndexLeafArr[%d]\n", l);
        
        l = 0;
        for( i = 0; i < TEST_SIZE; i ++ )
            if( pDataLeafArr[i] ) l ++;
        if( l ) printf("pDataLeafArr[%d]\n", l);

        l = 0;
        for( i = 0; i < TEST_SIZE; i ++ )
            if( pDataContArr[i] ) l ++;
        if( l ) printf("pDataContArr[%d]\n", l);

        l = 0;
        for( i = 0; i < TEST_SIZE; i ++ )
            if( pRecTypeArr[i] ) l ++;
        if( l ) printf("pRecTypeArr[%d]\n", l);
*/

//    }
/*
    for( i = 5000 - 1; i >=0; i -- )
    {
        if( InsertKey( i*10 ) < 0 )
            i = i;
    }

    for( i = 5000 ; i < 10000; i ++ )
    {
        if( InsertKey( i*10 ) < 0 )
            i = i;
    }



    for( i = 0; i < 10000; i ++ )
    {
        pSearchIndexLeaf  = pRoot;
        pSearchDataLeaf   = NULL;
        if( i == 555 )
            i = i;
        int k = i * 10;
        if( GetDataLeaf( k, pSearchIndexLeaf, pSearchDataLeaf ) < 0 )
            i = i;
        if( SeekInDataLeaf( pSearchDataLeaf, k ) == NULL )
            i = i;
    }

        for(i = 0; i < 1000; i++)
        {
            if( InsertKey( i ) != 0)
                i = i;
        }
        for( i = 504; i < 1000; i++)
        {
            if( DeleteKey( i ) != 0 ) 
                i=i;
        }

        for( i = 499; i >= 0 ; i--)
        {
            if( DeleteKey( i ) != 0 ) 
                i=i;
        }
*/
    printf("nNewIndexLeaf[%d],  nDelIndexLeaf[%d]\n",bt.m_nNewIndexLeaf, bt.m_nDelIndexLeaf);
    printf("nNewDataLeaf[%d],   nDelDataLeaf[%d]\n",bt.m_nNewDataLeaf, bt.m_nDelDataLeaf);
    printf("nNewDataCon[%d],    nDelDataCon[%d]\n",  bt.m_nNewDataCon, bt.m_nDelDataCon );
    printf("nNewRecType[%d],    nDelRecType[%d]\n", bt.m_nNewRecType, bt.m_nDelRecType);

}