Exclusion tree

gistfile1.txt

import org.junit.Assert;
import org.junit.Test;

public class Sandbox {
	public static void main(final String[] args) {

	}

	@Test
	public void test() {
		final ExclusionTree tree = new ExclusionTree(0, 20);
		tree.exclude(2);
		tree.exclude(5);
		tree.exclude(6);
		tree.exclude(10);
		tree.exclude(18);

		Assert.assertEquals(0, tree.excludedLessThan(1));
		Assert.assertEquals(0, tree.excludedLessThan(2));
		Assert.assertEquals(1, tree.excludedLessThan(4));
		Assert.assertEquals(3, tree.excludedLessThan(8));
		Assert.assertEquals(4, tree.excludedLessThan(18));
	}

	@Test
	public void testCorner() {
		final ExclusionTree tree = new ExclusionTree(0, 20);
		tree.exclude(0);
		tree.exclude(20);

		Assert.assertEquals(0, tree.excludedLessThan(-1));
		Assert.assertEquals(0, tree.excludedLessThan(0));
		Assert.assertEquals(1, tree.excludedLessThan(1));
		Assert.assertEquals(1, tree.excludedLessThan(20));
		Assert.assertEquals(2, tree.excludedLessThan(21));
	}

	@Test(expected = NullPointerException.class)
	public void testFail1() {
		final ExclusionTree tree = new ExclusionTree(0, 20);
		tree.exclude(-1);
	}

	@Test(expected = NullPointerException.class)
	public void testFail2() {
		final ExclusionTree tree = new ExclusionTree(0, 20);
		tree.exclude(21);
	}
}

class ExclusionTree {
	public int value;
	public int excluded;
	public ExclusionTree left, right;
	public int exclusionCount;

	public ExclusionTree(final int start, final int end) {
		this.value = (end + start) / 2;

		if (start < this.value) {
			this.left = new ExclusionTree(start, this.value - 1);
		}

		if (this.value < end) {
			this.right = new ExclusionTree(this.value + 1, end);
		}
	}

	public void exclude(final int n) {
		if (this.value == n) {
			this.excluded = 1;
		} else if (n < this.value) {
			this.left.exclude(n);
		} else {
			this.right.exclude(n);
		}

		++this.exclusionCount;
	}

	public int excludedLessThan(final int n) {
		if (n < this.value) {
			return this.left == null ? 0 : this.left.excludedLessThan(n);
		}

		int result = this.left == null ? 0 : this.left.exclusionCount;

		if (n > this.value) {
			result += this.excluded + (this.right == null ? 0 : this.right.excludedLessThan(n));
		}

		return result;
	}
}