// intpower.cpp

#include "cmpt_error.h"
#include <iostream>
#include <cassert>

using namespace std;

// regular iterative
int pow1(int base, int n) {
	// first handle base cases
	if (n < 0) cmpt::error("exponent must be >= 0");
	if (base == 0 && n == 0) return 1;
	if (base == 0) return 0;
	if (n == 0) return 1;

	int result = base;
	for(int i = 1; i < n; i++) {
		result *= base;
	}
	return result;
}

// regular recursive
int pow2(int base, int n) {
	// first handle base cases
	if (n < 0) cmpt::error("exponent must be >= 0");
	if (base == 0 && n == 0) return 1;
	if (base == 0) return 0;
	if (n == 0) return 1;

	return base * pow2(base, n-1);
}

// fast recursive
// (other implementations are possible)
int pow3(int base, int n) {
	// first handle base cases
	if (n < 0) cmpt::error("exponent must be >= 0");
	if (base == 0 && n == 0) return 1;
	if (base == 0) return 0;
	if (n == 0) return 1;

	if (n % 2 == 0) {
		int half = pow3(base, n / 2);
		return half * half;
	} else {
		int half = pow3(base, (n-1) / 2);
		return base * half * half;
	}
}

// This version of the fast recursive algorithm prints 0 and 1 to cout
// depending upon whether n is even or odd. The resulting pattern of 0s and 1s
// is interesting.
int pow3_traced(int base, int n) {
	// first handle base cases
	if (n < 0) cmpt::error("exponent must be >= 0");
	if (base == 0 && n == 0) return 1;
	if (base == 0) return 0;
	if (n == 0) return 1;

	if (n % 2 == 0) {
		int half = pow3_traced(base, n / 2);
		cout << 0;
		return half * half;
	} else {
		int half = pow3_traced(base, (n-1) / 2);
		cout << 1;
		return base * half * half;
	}
}

void test1() {
	assert(pow1(0, 0) == 1);
	assert(pow1(0, 1) == 0);
	assert(pow1(0, 2) == 0);
	assert(pow1(1, 0) == 1);
	assert(pow1(1, 1) == 1);
	assert(pow1(1, 2) == 1);
	assert(pow1(2, 0) == 1);
	assert(pow1(2, 1) == 2);
	assert(pow1(2, 2) == 4);
	assert(pow1(2, 3) == 8);
	assert(pow1(2, 4) == 16);
	assert(pow1(2, 5) == 32);
	assert(pow1(2, 6) == 64);
	assert(pow1(2, 7) == 128);
	cout << "... all pow1 tests passsed\n";
}

void test2() {
	assert(pow2(0, 0) == 1);
	assert(pow2(0, 1) == 0);
	assert(pow2(0, 2) == 0);
	assert(pow2(1, 0) == 1);
	assert(pow2(1, 1) == 1);
	assert(pow2(1, 2) == 1);
	assert(pow2(2, 0) == 1);
	assert(pow2(2, 1) == 2);
	assert(pow2(2, 2) == 4);
	assert(pow2(2, 3) == 8);
	assert(pow2(2, 4) == 16);
	assert(pow2(2, 5) == 32);
	assert(pow2(2, 6) == 64);
	assert(pow2(2, 7) == 128);
	cout << "... all pow2 tests passsed\n";
}

void test3() {
	assert(pow3(0, 0) == 1);
	assert(pow3(0, 1) == 0);
	assert(pow3(0, 2) == 0);
	assert(pow3(1, 0) == 1);
	assert(pow3(1, 1) == 1);
	assert(pow3(1, 2) == 1);
	assert(pow3(2, 0) == 1);
	assert(pow3(2, 1) == 2);
	assert(pow3(2, 2) == 4);
	assert(pow3(2, 3) == 8);
	assert(pow3(2, 4) == 16);
	assert(pow3(2, 5) == 32);
	assert(pow3(2, 6) == 64);
	assert(pow3(2, 7) == 128);
	assert(pow3(2, 8) == 256);
	assert(pow3(2, 9) == 512);
	assert(pow3(2, 10) == 1024);
	cout << "... all pow3 tests passsed\n";
}

void test4() {
	assert(pow3_traced(0, 0) == 1);
	assert(pow3_traced(0, 1) == 0);
	assert(pow3_traced(0, 2) == 0);
	assert(pow3_traced(1, 0) == 1);
	assert(pow3_traced(1, 1) == 1);
	assert(pow3_traced(1, 2) == 1);
	assert(pow3_traced(2, 0) == 1);
	assert(pow3_traced(2, 1) == 2);
	assert(pow3_traced(2, 2) == 4);
	assert(pow3_traced(2, 3) == 8);
	assert(pow3_traced(2, 4) == 16);
	assert(pow3_traced(2, 5) == 32);
	assert(pow3_traced(2, 6) == 64);
	assert(pow3_traced(2, 7) == 128);
	assert(pow3_traced(2, 8) == 256);
	assert(pow3_traced(2, 9) == 512);
	assert(pow3_traced(2, 10) == 1024);
	cout << "... all pow3_traced tests passsed\n";
}

void test5() {
	for(int n = 1; n <= 20; n++) {
		cout << "pow3(2, " << n << ") = " << pow3(2, n) << "\n";
	}
}

void test6() {
	cout << "\n";
	for(int n = 1; n <= 20; n++) {
		cout << "pow3(2, " << n << ") trace: ";
		pow3_traced(2, n);
		cout << "\n";
	}
}

int main() {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
}