MergerTest

MergerTest.java

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;

class Merger {
	public static <T extends Comparable<T>> List<T> merge(List<T> left, List<T> right) {

		int mergedSize = left.size() + right.size();
		List<T> mergedList = new ArrayList<T>(mergedSize);

		Iterator<T> leftIterator = left.iterator();
		Iterator<T> rightIterator = right.iterator();

		T topLeft = null;
		T topRight = null;

		if (!leftIterator.hasNext()) {
			return right;
		}
		if (!rightIterator.hasNext()) {
			return left;
		}

		boolean reloadLeft = true;
		boolean reloadRight = true;

		while (leftIterator.hasNext() && rightIterator.hasNext()) {
			if (reloadLeft) {
				topLeft = leftIterator.next();
				reloadLeft = false;
			}
			if (reloadRight) {
				topRight = rightIterator.next();
				reloadRight = false;
			}

			int comparison = topLeft.compareTo(topRight);
			if (comparison <= 0) {
				mergedList.add(topLeft);
				reloadLeft = true;
			} else if (comparison > 0) {
				mergedList.add(topRight);
				reloadRight = true;
			}
		}
		// one of these iterators has run out of elements
		// it must be the one that is set to reload, add the top element of the
		// other one
		if (reloadLeft) {
			mergedList.add(topRight);
		} else {
			mergedList.add(topLeft);
		}
		// one of these iterators might still have elements left
		while (leftIterator.hasNext()) {
			topLeft = leftIterator.next();
			mergedList.add(topLeft);
		}

		while (rightIterator.hasNext()) {
			topRight = rightIterator.next();
			mergedList.add(topRight);
		}

		return mergedList;

	}
}

public class MergerTest {

	@Test
	public void merge() {

		List<Integer> list1 = Arrays.asList(new Integer[] {});
		List<Integer> list2 = Arrays.asList(new Integer[] {});
		List<Integer> target_list = Arrays.asList(new Integer[] {});

		List<Integer> mergedList = Merger.merge(list1, list2);
		assertEquals(target_list, mergedList);

		list1 = Arrays.asList(new Integer[] { 0 });
		list2 = Arrays.asList(new Integer[] {});
		target_list = Arrays.asList(new Integer[] { 0 });

		mergedList = Merger.merge(list1, list2);
		assertEquals(target_list, mergedList);

		list1 = Arrays.asList(new Integer[] {});
		list2 = Arrays.asList(new Integer[] { -1 });
		target_list = Arrays.asList(new Integer[] { -1 });

		mergedList = Merger.merge(list1, list2);
		assertEquals(target_list, mergedList);

		list1 = Arrays.asList(new Integer[] { 0, 2, 5, 7, 9 });
		list2 = Arrays.asList(new Integer[] { -1, 3, 6, 7, 10, 11 });
		target_list = Arrays.asList(new Integer[] { -1, 0, 2, 3, 5, 6, 7, 7, 9, 10, 11 });

		mergedList = Merger.merge(list1, list2);
		assertEquals(target_list, mergedList);

	}

}