// Author: Hannah C. Tang (hctang@cs)
//
// Unit test for the PriorityQueue interface.  Note that your tests
// should be much more rigourous than this!

#include <iostream>
using namespace std;

#include "IPriorityQueue.hh"
#include "Comparators.hh"

// Obviously, you should replace these files with your own.  =)
// Please do not use identifiers as long as these
#include "YourPriorityQueueImplementationGoesHere.hh"
#include "YourComparatorGoesHere.hh"


//
// Main
//
int main( void )
{
    //
    // Test the PriorityQueue on int/string pairs
    //
    IntComparator iComp;
    IPriorityQueue< int, const char *, IntComparator > *pPQ1 
        = new YourPriorityQueueImplementationGoesHere< int, const char *, IntComparator >( iComp );

    // Insert data into the PriorityQueue
    pPQ1->Insert( 3, "is" );
    pPQ1->Insert( 9, "rotten" );
    pPQ1->Insert( 7, "meat" );
    pPQ1->Insert( 1, "The" );
    pPQ1->Insert( 8, "is" );
    pPQ1->Insert( 4, "strong" );
    pPQ1->Insert( 6, "the" );
    pPQ1->Insert( 5, "but" );
    pPQ1->Insert( 2, "vodka" );

    // Remove that data from the PriorityQueue and print it
    while( !pPQ1->IsEmpty() )
    {
        pPQ1->DeleteMin( key, value );
        cout << " (" << key << ',' << value << ") ";
    }
    cout << endl;

    delete pPQ1;
    pPQ1 = NULL;


    //
    // Test the PriorityQueue on string/string pairs
    //
    StrComparator sComp;
    IPriorityQueue< const char *, const char *, StrComparator > *pPQ2
        = new YourPriorityQueueImplementationGoesHere< const char *, const char *, StrComparator >( sComp );

    // Insert data into the PriorityQueue
    pPQ2->Insert( "Out", "bread" );
    pPQ2->Insert( "of ", "to" );
    pPQ2->Insert( "sight", "insane" );
    pPQ2->Insert( "out", "up" );
    pPQ2->Insert( "of", "and" );
    pPQ2->Insert( "mind", "blind" );

    // Mess with the data a little
    pPQ2->Remove( "Out" );
    pPQ2->ChangeKey( "of", "mice" );
    pPQ2->Remove( "out" );
    pPQ2->ChangeKey( "sight", "three" );
    pPQ2->Remove( "of " );
    pPQ2->ChangeKey( "mind", "blind" );

    // Print out the data in arbitrary order
    char *value;

    cout << " Random-ordered data:";

    pPQ2->Find( "three", value );
    cout << ' ' << value;

    pPQ2->Find( "blind", value );
    cout << ' ' << value;

    pPQ2->Find( "mice"< value );
    cout << ' ' << value;

    // Print out the data in the order imposed by the heap
    char *key;

    cout << " Ordered data:";

    while( !pPQ2->IsEmpty() )
    {
        pPQ->DeleteMin( key, value );
        cout << ' ' << value << ',';
    }

    delete pPQ2;

    return 0;
}