import org.junit.*;
import org.junit.Assert.*;
import java.util.*;

public class HeapTester {
	@Test public void testHeight () {
		for (int d = 2; d < 8; d++) {
			final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(d);
			final int L = 5;  // 5 levels deep
			final int N = (int) ((1 - Math.pow(d, L)) / (1 - d));  // formula for num nodes in d-ary tree of height L
			heap.add(2);
			for (int i = 1; i < N - 1; i++) {
				heap.add(1);
			}
			heap.add(0);
		
			Assert.assertEquals(heap.height(2), 0);
			Assert.assertEquals(heap.height(0), L-1);
		}
		System.out.println("\n+1 point (testHeight)\n");
	}

	private void permute (int[] array) {
		final Random random = new Random();
		for (int i = array.length - 1; i >= 0; i--) {
			final int j = random.nextInt(i+1);
			final int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}

	@Test public void testRemove () {
		final int N = 500;
		final int[] numbers = new int[N];
		for (int i = 0; i < N; i++) {
			numbers[i] = i;
		}
		permute(numbers);

		for (int d = 2; d < 8; d++) {
			final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(d);
			for (int i = 0; i < N; i++) {
				heap.add(i);
			}

			permute(numbers);
			for (int i = 0; i < N; i++) {
				final int trueLargest = findLargest(numbers, i);
				final int predictedLargest = heap.peekLargest();
				Assert.assertEquals(trueLargest, predictedLargest);
				heap.remove(numbers[i]);
				Assert.assertEquals(N - i - 1, heap.size());
			}
		}

		System.out.println("\n+1 point (testRemove)\n");
	}

	int findLargest (int[] numbers, int startIdx) {
		int largest = - Integer.MAX_VALUE;
		for (int i = startIdx; i < numbers.length; i++) {
			if (numbers[i] > largest) {
				largest = numbers[i];
			}
		}
		return largest;
	}

	@Test public void testRemoveLargest2 () {
		for (int d = 2; d < 8; d++) {
			removeLargestHelper(d);
		}
		System.out.println("\n+1 point (testRemoveLargest2)\n");
	}
	
	@Test public void testRemoveLargest1 () {
		removeLargestHelper(2);
		System.out.println("\n+2 points (testRemoveLargest)\n");
	}
	
	private void removeLargestHelper (int d) {
		final int N = 1000;
		final int[] numbers = new int[N];
		for (int i = 0; i < N; i++) {
			numbers[i] = i;
		}
		permute(numbers);

		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(d);
		for (int i = 0; i < N; i++) {
			heap.add(numbers[i]);
		}
		for (int i = N-1; i >= 0; i--) {
			Assert.assertEquals((Integer) i, heap.removeLargest());
		}
	}

	@Test public void testSizeClear () {
		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(3);
		final int N = 100;
		for (int i = 0; i < N; i++) {
			heap.add(i);
		}
		Assert.assertEquals(N, heap.size());
		heap.remove(0);
		Assert.assertEquals(N-1, heap.size());
		heap.clear();
		Assert.assertEquals(0, heap.size());
		heap.add(0);
		Assert.assertEquals(1, heap.size());

		heap.clear();
		for (int i = 0; i < N; i++) {
			heap.add(i);
		}
		for (int i = 0; i < N; i++) {
			heap.peekLargest();
			Assert.assertEquals(N - i, heap.size());
			heap.removeLargest();
		}
		
		System.out.println("\n+1 point (testSizeClear)\n");
	}

	private void addHelper (int d, int N) {
		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(d);
		for (int i = 0; i < N; i++) {
			heap.add(i);
		}
		for (int i = 0; i < N; i++) {
			Assert.assertTrue(heap.contains(i));
		}
		Assert.assertFalse(heap.contains(-1));
		Assert.assertFalse(heap.contains(N));
	}

	@Test public void testAdd2 () {
		for (int d = 2; d < 8;  d++) {
			addHelper(d, 125);
		}
		System.out.println("\n+1 point (testAdd2)\n");
	}

	@Test public void testSuperEasy () {
		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(2);
		for (int i = 1; i <= 5; i++) {
			heap.add(i);
		}
		Assert.assertEquals((Integer) 5, heap.removeLargest());
		System.out.println("\n+MIN testSuperEasy\n");
	}

	@Test public void testAdd1 () {
		addHelper(2, 125);
		System.out.println("\n+1 point (testAdd1)\n");
	}

	private static double log (double x, double b) {
		return Math.log(x) / Math.log(b);
	}
}