#include <iostream>
using namespace std;

#include "Heap2.h"
#include "Heap2opt.h"
#include "Heap3.h"
#include "Heap4.h"
#include "Heap5.h"

// Test all the heaps by:
//  1. placing the integers in order from 0 to N - 1 and taking them out,
//  2. placing the integers in reverse order from N - 1 to 0 and taking them out, and
//  3. 1000 times, placing the integers from 0 to N - 1 in random order and taking them out.

int main() {
	int const N = 1000;
	Heap2 h2;
	Heap2opt hT;
	Heap3 h3;
	Heap4 h4;
	Heap5 h5;

	for ( int i = 0; i < N; ++i ) {
		h2.push(i);
		hT.push(i);
		h3.push(i);
		h4.push(i);
		h5.push(i);
	}

	for ( int i = 0; i < N; ++i ) {
		if ( h2.top() != i ) { cout << "bad2" << endl; }
		if ( hT.top() != i ) { cout << "badT" << endl; }
		if ( h3.top() != i ) { cout << "bad3" << endl; }
		if ( h4.top() != i ) { cout << "bad4" << endl; }
		if ( h5.top() != i ) { cout << "bad5" << endl; }
		h2.pop();
		hT.pop();
		h3.pop();
		h4.pop();
		h5.pop();
	}

	for ( int i = N - 1; i >= 0; --i ) {
		h2.push(i);
		hT.push(i);
		h3.push(i);
		h4.push(i);
		h5.push(i);
	}

	for ( int i = 0; i < N; ++i ) {
		if ( h2.top() != i ) { cout << "bad2" << endl; }
		if ( hT.top() != i ) { cout << "badT" << endl; }
		if ( h3.top() != i ) { cout << "bad3" << endl; }
		if ( h4.top() != i ) { cout << "bad4" << endl; }
		if ( h5.top() != i ) { cout << "bad5" << endl; }
		h2.pop();
		hT.pop();
		h3.pop();
		h4.pop();
		h5.pop();
	}

	for ( int j = 0; j < 1000; ++j ) {
		int values[N];

		for ( int k = 0; k < N; ++k ) {
			values[k] = k;
		}

		for ( int k = N; k > 0; --k ) {
			int posn = (lrand48() % k);

			h2.push(values[posn]);
			hT.push(values[posn]);
			h3.push(values[posn]);
			h4.push(values[posn]);
			h5.push(values[posn]);

			if ( posn != k - 1 ) {
				std::swap( values[posn], values[k - 1] );
			}
		}

		for ( int i = 0; i < N; ++i ) {
			if ( h2.top() != i ) { cout << "bad2" << endl; }
			if ( hT.top() != i ) { cout << "badT" << endl; }
			if ( h3.top() != i ) { cout << "bad3" << endl; }
			if ( h4.top() != i ) { cout << "bad4" << endl; }
			if ( h5.top() != i ) { cout << "bad5" << endl; }
			h2.pop();
			hT.pop();
			h3.pop();
			h4.pop();
			h5.pop();
		}
	}

	return 0;
}