// Simple program for testing BST functionality (note that you can
// use it to test your AVL/Splay trees as well!

#include <iostream>
using namespace std;

#include "BinarySearchTree.hh"

//
// Prototypes
//

// Sort the (int, double) pairs by the double keys
void SelectionSort( int values[], double keys[], int numElts );


//
// Main
//
int main( void )
{
    //
    // Once you have implemented your AVL and Splay trees,
    // you can change "new BinarySearchTree" to "new AVLTree", or
    // whatever else derives from your BinarySearchTree class
    //
    BinarySearchTree< int, double > *pBst = 
        new BinarySearchTree< int, double >;

    //
    // Insert some data
    //
    pBst->Insert( 10, -10.5 );
    pBst->Insert( 3, -3.5 );
    pBst->Insert( 15, -15.5 );

    //
    // Print the tree
    //
    cout << " Num elements in BST is " << pBst->GetSize() << endl;
    cout << " Tree is:" << endl;
    pBst->Print();

    //
    // Copy the tree (to make sure the assign op is working)
    //
    BinarySearchTree< int, double > bst;
    bst = *pBst;

    cout << " Copied tree is:" << endl;
    bst.Print();

    //
    // Do some finds in the tree
    //
    double d;

    if( !pBst->Find( 10, d ) )
    {
        cout << " Didn't find 10 in tree" << endl;
    }
    else
    {
        cout << " Found 10, its value was " << d << endl;
    }

    if( !pBst->Find( 15, d ) )
    {
        cout << " Didn't find 15 in tree" << endl;
    }
    else
    {
        cout << " Found 15, its value was " << d << endl;
    }

    if( !pBst->Find( 3, d ) )
    {
        cout << " Didn't find 3 in tree" << endl;
    }
    else
    {
        cout << " Found 3, its value was " << d << endl;
    }

    // This Find() should fail
    if( !pBst->Find( 5, d ) )
    {
        cout << " Didn't find 5 in tree" << endl;
    }
    else
    {
        cout << " Found 5, its value was " << d << endl;
    }

    cout << endl;

    //
    // Insert a lot more data
    //
    pBst->Insert( 5, -5.5 );
    pBst->Insert( 6, -6.5 );
    pBst->Insert( 13, -13.5 );
    pBst->Insert( 2, -2.5 );
    pBst->Insert( 17, -17.5 );
    pBst->Insert( 19, -19.5 );
    pBst->Insert( 91, -91.5 );
    pBst->Insert( -2, 2.5 );
    pBst->Insert( -5, 5.5 );
    pBst->Insert( 12, -12.5 );
    pBst->Insert( -73, 73.5 );
    pBst->Insert( 14, -14.5 );

    //
    // Check the tree
    //
    cout << " Tree is: " << endl;
    pBst->Print();
    
    //
    // Test the GetDataAsArray() method.  What is the asymptotic 
    // runtime of this method?
    //
    int *pKeys;
    double *pValues;

    int numElts = pBst->GetDataAsArray( pKeys, pValues );

    cout << " Num elements in the array: " << numElts << endl;
    cout << " Num elements in the bst (should match num elements in array): " 
         << pBst->GetSize() << endl;

    cout << " Data in array (sorted by key) is: " << endl;
    
    for( int i = 0; i < numElts; i++ )
    {
        cout << "  Key: " << pKeys[ i ] 
             << "  Value: " << pValues[ i ] << endl;
    }

    SelectionSort( pKeys, pValues, numElts );

    cout << " Data in array (sorted by value) is: " << endl;
    
    for( int i = 0; i < numElts; i++ )
    {
        cout << "  Value: " << pValues[ i ]
             << "  Key: " << pKeys[ i ] << endl;

    }

    return 0;
}


// Sort the (int, double) pairs by the double keys
void SelectionSort( int values[], double keys[], int numElts )
{
    if( numElts <= 0 )
    {
        return;
    }

    // For finding the smallest element in a subarray
    double smallestKey;
    int smallestKeyIndex;

    // For swapping
    double tempKey;
    int tempVal;


    for( int i = 0; i < numElts; i++ )
    {
        smallestKeyIndex = i;
        smallestKey = keys[ smallestKeyIndex ];

        // Find the smallest key in the subarray starting at 'i'
        for( int j = i; j < numElts; j++ )
        {
            if( keys[ j ] < smallestKey )
            {
                smallestKeyIndex = j;
                smallestKey = keys[ smallestKeyIndex ];
            }
        }

        // Swap the smallest key *and* value in the subarray starting
        // at 'i' with the element at 'i' itself
        tempKey = keys[ smallestKeyIndex ];
        keys[ smallestKeyIndex ] = keys[ i ];
        keys[ i ] = tempKey;

        tempVal = values[ smallestKeyIndex ];
        values[ smallestKeyIndex ] = values[ i ];
        values[ i ] = tempVal;
    }
}