### Question:
RangeSearchBST extends RedBlackBSTWithNoExtraMemory<Key, Val> { public int size(Key lo, Key hi) { return 0; }  int size(Key lo, Key hi); List<Key> search(Key lo, Key hi);  }### Answer:
@Test public void testSizeBasic() { RangeSearchBST<Integer, Integer> test = new RangeSearchBST<>(); Assert.assertEquals(0, test.size(Integer.MIN_VALUE, Integer.MAX_VALUE)); test.put(1, 1); Assert.assertEquals(1, test.size(Integer.MIN_VALUE, Integer.MAX_VALUE)); Assert.assertEquals(1, test.size(Integer.MIN_VALUE, 1)); Assert.assertEquals(1, test.size(1, Integer.MAX_VALUE)); Assert.assertEquals(1, test.size(1, 1)); Assert.assertEquals(0, test.size(0, 0)); }
@Test(expected = IllegalArgumentException.class) public void testInvalidInput1() { RangeSearchBST<Integer, Integer> test = new RangeSearchBST<>(); test.size(Integer.MAX_VALUE, Integer.MIN_VALUE); }
@Test(expected = IllegalArgumentException.class) public void testInvalidInput2() { RangeSearchBST<Integer, Integer> test = new RangeSearchBST<>(); test.size(null, Integer.MIN_VALUE); }
@Test(expected = IllegalArgumentException.class) public void testInvalidInput3() { RangeSearchBST<Integer, Integer> test = new RangeSearchBST<>(); test.size(0, null); }
@Test public void testSizeRandom() { int N = 10; for (int i = 0; i < 10; i++, N <<= 1) { RangeSearchBST<Integer, Integer> test = new RangeSearchBST<>(); int[] testData = Shuffler.getRandomArray(N, -N, N); for (int data : testData) test.put(data, data); Arrays.sort(testData); for (int j = 0; j < 100; j++) { int a = -N + random.nextInt(2 * N), b = -N + random.nextInt(2 * N); int hi = Math.max(a, b), lo = Math.min(a, b); Assert.assertEquals(expectSize(testData, lo, hi), test.size(lo, hi)); } } }