// -*- c++ -*-
//------------------------------------------------------------------------------
// $Id: pq_test.cpp,v 1.4 2006/07/20 02:30:56 vlg Exp $
//------------------------------------------------------------------------------
//                            pqtest.C
//------------------------------------------------------------------------------
//
// When      Who  What
// --------- ---- --------------------------
// 09/17/99  VLG  Created
//
//------------------------------------------------------------------------------


// System
#include <sys/time.h>		// gettimeofday(3)
#include <stdlib.h>		// drand48(3), abs(3), getopt(3)
#include <limits.h>		// INT_MIN
#include <unistd.h>		// gettimeofday(3)
#include <stdio.h>

#include <fstream>
#include <iostream>
using namespace std;

#ifdef sun
#  include <stdio.h>				// getopt
#endif

#ifdef linux
#  include <getopt.h>
#endif

extern char *optarg;
extern int optind, opterr, optopt;

// ASSA
#include "assa/PriorityQueue.h"
#include "assa/TimeVal.h"
using namespace ASSA;

ofstream logger;

/*******************************************************************************
 Class Timer
*******************************************************************************/

class Timer {
private:
    int m_i;
	
    friend ostream& operator<< (ostream&, Timer&);
public:
    Timer (int i_) : m_i (i_) { }
    
    bool operator< (const Timer& t_) const { return m_i < t_.m_i; }
    bool operator==(const Timer& t_) const { return m_i == t_.m_i; }
};

struct TimerCompare
{
    bool operator() (const Timer* t1_, const Timer* t2_) const
	{
	    return *t1_ < *t2_;
	}
};

ostream& 
operator<< (ostream& os_, Timer& t_)
{
    return os_ << t_.m_i;
}

//-----------------------------------------------------------------------------
// Name: random_generator
//
// Description:
//    Generate random integer number in limits [ -LIMIT; LIMIT ]
//
// Notes:
//     Following formula comes from the observation that since drand48()
//     returns values in range [0; 1.0] and we have to map them into 
//     range [-LIMIT; LIMIT ]. Clearly, .5 maps into 0, so that we only 
//     have to map y - [.5; 1.0] into x - [0; LIMIT]. To do so, we use
//      x = f(y) = (2y - 1) * (LIMIT). Negative part is just -x.
//
//-----------------------------------------------------------------------------
int
random_generator (u_int limit_)
{
    double y;
    int x;
	TimeVal tv (TimeVal::gettimeofday ());

	/** Use usecs as seed number
	 */
#if !defined (WIN32)
    srand48 (tv.msec ());
    y = drand48 ();
#else
	srand (tv.msec ());
	y = rand ();
#endif

    if (y >= .5) {
		x = int ((2*y - 1) * limit_);
    }
    else {
		y += .5;
		x = - int( (2*y - 1) * limit_ );
    }
    return x;
};

void usage (int exitcode_) 
{
    cerr << "\n\nUsage: pq_test [options]\n"
		 << '\n'
		 << " OPTIONS:\n"
		 << '\n'
		 << "   -r <number> MIN/MAX range of random numbers"
		 << '\n'
		 << "   -f <filename> Name of random nums file"
		 << '\n'
		 << "   -n <number> How many random numbers to generate"
		 << '\n'
		 << "   -h Print help message\n"
		 << "\n\n";

    exit (exitcode_);
}

const char psep[] = 
"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";
const char ssep[] =
"*****************************************************************************";
const char msep[] =
"-----------------------------------------------------------------------------";

void dump_queue (PriorityQueue<Timer*, TimerCompare>& pq_)
{
    register int cnt;
    register size_t i;

    for ( i=0, cnt=0; i<pq_.size(); i++,cnt++) {
		if (cnt == 9) { 
			logger << endl; cnt=0;
		}
		logger.width (8);
		logger << *pq_[i];
    }
    logger << endl;
}
		
void test_random_deletion (PriorityQueue<Timer*, TimerCompare>& pq_)
{
    register int r;
    register size_t i;
    PriorityQueue<Timer*, TimerCompare> clone;

    for (i = 0; i < pq_.size(); i++) {
		clone.insert(pq_[i]);
    }
    logger << "Delete random element and dump queue after each deletion:"
		 << "\n\nInitial queue:\n";
    dump_queue (clone);

    while ( clone.size() ) {
		r = abs (random_generator (clone.size()));
		logger << "\nRemoving element: [ " << *(clone[r]) << " ] "
			 << '(' << r << '/' << clone.size() << ")\n";
		clone.remove (clone[r]);
		dump_queue (clone);
		logger << endl << msep;
    }
}

int main (int argc, char* argv[])
{
    char c;
    int rand_limit = 200;
    int rand_nm = 25;
    char buf[128];
    string rand_fname;
    string logfile ("pq_test.log");
    register int i;

	std::cout << "= Running pq_test Test =\n";

    // Parse command-line arguments

    int errflg = 0;
    opterr = 0;

    while ((c = getopt (argc, argv, "hf:r:n:")) != -1) {
		switch (c) {
		case 'h': usage (0); break;
		case 'f': rand_fname = optarg; break;
		case 'r': rand_limit = atoi(optarg); break;
		case 'n': rand_nm = atoi(optarg); break;
		case '?': errflg++; break;
		}
    }

    if (errflg) {
		usage (1);
    }

#if 0
    if (logfile.size() ) {
		Log::open_log_file (logfile.c_str());
		Log::disable_timestamp ();
    }
#endif

	::unlink (logfile.c_str ());
	logger.open (logfile.c_str ());
	
    // If external random number file was not specified, first
    // create one
    
    logger << "Random file name: [" << rand_fname << "]\n\n\n";
    
    if ( rand_fname.size() == 0 ) {
		sprintf(buf, "rand_%d_%d.dat", rand_nm, rand_limit);
		rand_fname = buf;
		logger << "Random numbers file is set to default name: " 
			 << rand_fname << endl;

		ofstream out_file (rand_fname.c_str());
		int rd;
		int j=1;
	
		for (i=0; i<rand_nm; i++,j++) {
			rd = random_generator (rand_limit);
			out_file << rd << " ";
		
			if (j == 8) {
				out_file.width(8);
				out_file << endl;
				j = 0;
			}
		}
		out_file.close ();
    }
    //------------------------------------------------------------------
    // Either way, we have file full of random numbers to work with.
    //
    
    PriorityQueue<Timer*, TimerCompare> pq;
    
    ifstream in_file (rand_fname.c_str());
    int count=0;

    logger << ssep << "\nTest 1:\n" 
		 << "a) Inserted " << count 
		 << " random elements ... \n";
    
    while ( in_file >> i ) {
		pq.insert (new Timer (i));
		count++;
		logger << "[";
		logger.width(4);
		logger << count;
		logger << " ], inserting element >> ";
		logger.width(6);
		logger << i << endl;
    }
    in_file.close ();
    
    logger << "done\n";
    
    logger << "\nb) Dump queue:\n";
    dump_queue(pq);
    
    logger << "\n\nc) Clone queue and test random deletion:\n";
    test_random_deletion (pq);
    
    logger << endl << ssep << "\nd) Extract each element and ensure that \n"
		 << "priority ordering is correct:\n";
    
    logger << "\nInitial queue:\n";
    dump_queue(pq);
    logger << endl;
	
    register Timer* prev = new Timer(INT_MIN);
    register Timer* curr;	// current element

    count = 1;

    while (pq.size ()) {
		logger << ssep << endl << "*  Extracting next element # " << count;
		curr = pq.top ();
		if (*curr < *prev) {
			logger << endl <<	ssep << endl
				 << "*          Found discrepancy!!!          *\n"
				 << ssep << endl
				 << "* previous = " << *prev 
				 << " > current = " << *curr << " !\n"
				 << ssep << endl;
			std::cout << "Test failed.\n";
			return 1;
		}
		logger << "  ... Extracted = " << *curr << "\n\n";
		delete prev;
		prev = curr;
		pq.pop ();
		count++;
		dump_queue(pq);
		logger << endl;
    }
	logger.close ();
	std::cout << "Test passed\n";

    return 0;
}