// max.cpp

#include "cmpt_error.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdlib> // rand and srand
#include <ctime>   // time

using namespace std;

// Pre-condition:
//    v is not empty
// Post-condition:
//    returns the largest value in v
int max_iter(const vector<int>& v) {
	if (v.empty()) cmpt::error("v is empty");
	int result = v[0];
	for(int i = 1; i < v.size(); i++) {
		if (v[i] > result) {
			result = v[i];
		}
	}
	return result;
}

// Pre-condition:
//    begin < v.size()
// Post-condition:
//    returns the largest value in v[begin], v[begin+1], ..., v[n]
int max_rec(const vector<int>& v, int begin) {
	int n = v.size();
	if (begin >= n) cmpt::error("v is empty");
	if (begin == n-1) return v[begin];
	return max(v[begin], max_rec(v, begin+1));
}

// Pre-condition:
//    v is not empty
// Post-condition:
//    returns the largest value in v
int max_rec(const vector<int>& v) {
	return max_rec(v, 0);
}

vector<int> make_rand_vec(int n) {
	vector<int> result(n);
	for(int i = 0; i < n; i++) {
		result[i] = i;
	}
	random_shuffle(result.begin(), result.end());
	return result;
}

// Same as max_iter, but instead of returning the max of v, it returns the
// count of how many times result = v[i] is called.
int max_iter_counted(const vector<int>& v) {
	if (v.empty()) cmpt::error("v is empty");
	int count = 0;
	int result = v[0];
	for(int i = 1; i < v.size(); i++) {
		if (v[i] > result) {
			result = v[i];
			count++;
		}
	}
	// return result;
	return count;
}

void test1() {
	vector<int> v = {3};
	assert(max_iter(v) == 3);
	v = {3, 1};
	assert(max_iter(v) == 3);
	v = {1, 3};
	assert(max_iter(v) == 3);
	v = {2, 1, 3};
	assert(max_iter(v) == 3);
	v = {1, 2, 3};
	assert(max_iter(v) == 3);
	v = {2, 3, 1};
	assert(max_iter(v) == 3);
	cout << "all max_iter tests passed\n";
}

void test2() {
	vector<int> v = {3};
	assert(max_rec(v) == 3);
	v = {3, 1};
	assert(max_rec(v) == 3);
	v = {1, 3};
	assert(max_rec(v) == 3);
	v = {2, 1, 3};
	assert(max_rec(v) == 3);
	v = {1, 2, 3};
	assert(max_rec(v) == 3);
	v = {2, 3, 1};
	assert(max_rec(v) == 3);
	cout << "all max_rec tests passed\n";
}

void test3() {
	// seed rand number generator with current time
	srand(unsigned(time(0)));
	for(int n = 10; n <= 1000000000; n *= 10) {
		vector<int> v = make_rand_vec(n);
		cout << "n=" << n << ": " << max_iter_counted(v) 
		     << "\n";
	}

}

int main() {
	test1();
	test2();
	test3();
}