Generics.java

package pl.lamvak.examples;

import com.google.common.collect.ImmutableList;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;

import static com.google.common.collect.ImmutableList.of;
import static org.junit.Assert.assertEquals;

public class Generics {

	private final ImmutableList<Integer> immutableList = of(1, 4, 8, 20, 21);
	private final ArrayList<Integer> arrayList = new ArrayList<>(immutableList);
	private final LinkedList<Integer> linkedList = new LinkedList<>(immutableList);
	private final Comparator<Integer> cmp = Integer::compareTo;

	@Test
	public void binarySearchFindExact() {
		assertEquals(1, binarySearch(4, immutableList, cmp));
		assertEquals(1, binarySearch(4, arrayList, cmp));
//		This should not compile:
//		assertEquals(1, binarySearch(4, linkedList));
	}

	@Test
	public void binarySearchGreaterEqualFindExact() {
		assertEquals(1, binarySearchGreaterEqual(4, immutableList, cmp));
		assertEquals(1, binarySearchGreaterEqual(4, arrayList, cmp));
//		This should not compile:
//		assertEquals(1, binarySearchGreaterEqual(4, linkedList));
	}

	@Test
	public void binarySearchFindExactOnBorder() {
		assertEquals(0, binarySearch(1, immutableList, cmp));
		assertEquals(4, binarySearch(21, immutableList, cmp));
		assertEquals(0, binarySearch(1, arrayList, cmp));
		assertEquals(4, binarySearch(21, arrayList, cmp));
//		This should not compile:
//		assertEquals(0, binarySearch(1, linkedList));
//		assertEquals(4, binarySearch(21, linkedList));
	}

	@Test
	public void binarySearchFindGreater() {
		assertEquals(-1, binarySearch(5, immutableList, cmp));
		assertEquals(-1, binarySearch(5, arrayList, cmp));

		assertEquals(-1, binarySearch(0, immutableList, cmp));
		assertEquals(-1, binarySearch(0, arrayList, cmp));

		assertEquals(2, binarySearchGreaterEqual(5, immutableList, cmp));
		assertEquals(2, binarySearchGreaterEqual(5, arrayList, cmp));

		assertEquals(0, binarySearchGreaterEqual(0, immutableList, cmp));
		assertEquals(0, binarySearchGreaterEqual(0, arrayList, cmp));

//		This should not compile:
//		assertEquals(-1, binarySearch(5, linkedList));
//		assertEquals(2, binarySearchGreaterEqual(5, linkedList));
//		assertEquals(-1, binarySearch(0, linkedList));
//		assertEquals(0, binarySearchGreaterEqual(0, linkedList));
	}

	@Test
	public void binaryNotFound() {
		assertEquals(-1, binarySearch(22, immutableList, cmp));
		assertEquals(-1, binarySearch(22, arrayList, cmp));

		assertEquals(-1, binarySearchGreaterEqual(22, immutableList, cmp));
		assertEquals(-1, binarySearchGreaterEqual(22, arrayList, cmp));

//		This should not compile:
//		assertEquals(-1, binarySearch(22, linkedList));
//		assertEquals(-1, binarySearchGreaterEqual(22, linkedList));
	}

	private <T, C extends Comparator<? super T>, U extends List<? extends T>>
	int binSearchLeft(T element, U list, C comparator) {
		int leftLimit = 0;
		int rightLimit = list.size() - 1;
		while (leftLimit < rightLimit) {
			int mid = leftLimit + (rightLimit - leftLimit) / 2;
			int midComparison = comparator.compare(element, list.get(mid));
			if (midComparison == 0) {
				return mid;
			} else if (midComparison < 1) {
				rightLimit = mid - 1;
			} else {
				leftLimit = mid + 1;
			}
		}
		return leftLimit;
	}

	public <T, C extends Comparator<? super T>, U extends List<? extends T> & RandomAccess> int
	binarySearch(
			T element, U list, C comparator) {
		int idx = binarySearchGreaterEqual(element, list, comparator);
		if (idx > -1 && !element.equals(list.get(idx))) {
			idx = -1;
		}
		return idx;
	}

	public <T, C extends Comparator<? super T>, U extends List<? extends T> & RandomAccess>
	int binarySearchGreaterEqual(T element, U list, C comparator) {
		if (list.isEmpty() || element == null) {
			return -1;
		}
		int leftLimit = binSearchLeft(element, list, comparator);
		if (comparator.compare(element, list.get(leftLimit)) < 1) {
			return leftLimit;
		}
		if (leftLimit + 1 < list.size() && comparator.compare(element, list.get(leftLimit + 1)) < 1) {
			return leftLimit + 1;
		}
		return -1;
	}

}