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

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

	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;
		}
	}

	private void addAndRemoveHelper (int d, int N) {
		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.assertTrue(heap.removeLargest().equals(i));
		}
	}

	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);
		}
		Assert.assertTrue(heap.size() == N);
	}

	private void addAndContainsHelper (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 testAddAndContains () {
		for (int d = 3; d < 8;  d++) {
			addAndContainsHelper(d, 1000);
		}
		System.out.println("\n+1 points (testAddAndContains)\n");
	}

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

	@Test public void testAddAndRemove2 () {
		for (int d = 3; d < 8;  d++) {
			addAndRemoveHelper(d, 1000);
		}
		System.out.println("\n+1 points (testAddAndRemove2)\n");
	}

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

		HeapImpl12<Integer> heap = new HeapImpl12<Integer>(2);
		int currentMax = numbers[0];
		for (int i = 0; i < N; i++) {
			heap.add(numbers[i]);
			if (numbers[i] > currentMax) {
				currentMax = numbers[i];
			}
			Assert.assertEquals(heap.peekLargest(), new Integer(currentMax));
		}
		System.out.println("\n+1 points (testFindLargest)\n");
	}

	@Test public void testAddAndRemove1 () {
		addAndRemoveHelper(2, 6);
		System.out.println("\n+2 points (testAddAndRemove1)\n");
	}

	@Test public void testDepth () {
		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.depth(2), 0);
			Assert.assertEquals(heap.depth(0), L-1);
		}
		System.out.println("\n+1 point (testDepth)\n");
	}

	@Test public void testException () {
		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(3);
		heap.add(5);
		try {
			heap.remove(4);
			Assert.assertTrue(false);
		} catch (NoSuchElementException nsee) {
			Assert.assertTrue(true);
		}
		System.out.println("\n+1 point (testException)\n");
	}

	@Test public void testRemove () {
		final int N = 100;
		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>(2);
		for (int i = 0; i < N; i++) {
			heap.add(numbers[i]);
		}
		for (int i = 0; i < N; i += 2) {
			heap.remove(i);
		}
		for (int i = 1; i < N; i+= 2) {
			Assert.assertEquals(heap.removeLargest(), new Integer(N - i));
		}
		System.out.println("\n+2 point (testRemove)\n");
	}

	@Test public void testSizeClear () {
		final HeapImpl12<Integer> heap = new HeapImpl12<Integer>(3);
		final int N = 25;
		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++) {
			Assert.assertEquals(N - i, heap.size());
			heap.removeLargest();
		}
		
		System.out.println("\n+1 point (testSizeClear)\n");
	}
}