import static org.junit.Assert.assertEquals;

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

import org.junit.Test;

public class LexicographicListComparator {

	static class LexicographicComparator<T extends Comparable<T>> implements Comparator<List<T>> {

		private final Comparator<T> elementComparator;

		public LexicographicComparator(final Comparator<T> elementComparator) {
			this.elementComparator = elementComparator;
		}

		public LexicographicComparator() {
			this(new Comparator<T>() {
				@Override
				public int compare(T o1, T o2) {
					return o1.compareTo(o2);
				}
			});
		}

		@Override
		public int compare(List<T> l1, List<T> l2) {
			final Iterator<T> i1 = l1.iterator(), i2 = l2.iterator();
			while (i1.hasNext() && i2.hasNext()) {
				final int cmp = elementComparator.compare(i1.next(),i2.next());
				if (cmp != 0) return cmp;
			}
			if (i1.hasNext() && !i2.hasNext()) return 1;
			if (!i1.hasNext() && i2.hasNext()) return -1;
			return 0;
		}
	}

	final static Comparator<Integer> DESCENDING_INTEGER_COMPARATOR = new Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return -o1.compareTo(o2);
		}
	};

	@Test
	public void equal() {
		final List<Integer> l1 = Arrays.asList(1, 2, 3);
		final List<Integer> l2 = Arrays.asList(1, 2, 3);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>();
		assertEquals(0,c.compare(l1, l2));
	}

	@Test
	public void sameLengthAscending() {
		final List<Integer> l1 = Arrays.asList(1, 2, 3);
		final List<Integer> l2 = Arrays.asList(1, 2, 4);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>();
		assertEquals(-1,c.compare(l1, l2));
	}

	@Test
	public void sameLengthDescending() {
		final List<Integer> l1 = Arrays.asList(1, 2, 3);
		final List<Integer> l2 = Arrays.asList(1, 2, 4);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>(DESCENDING_INTEGER_COMPARATOR);
		assertEquals(1,c.compare(l1, l2));
	}

	@Test
	public void differentLengthAscending() {
		final List<Integer> l1 = Arrays.asList(1, 2, 3);
		final List<Integer> l2 = Arrays.asList(1, 2);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>();
		assertEquals(1,c.compare(l1, l2));
	}

	@Test
	public void differentLengthAndValuesDescending() {
		final List<Integer> l1 = Arrays.asList(1, 3, 3); // we need different values, the shorter will always come first otherwise
		final List<Integer> l2 = Arrays.asList(1, 2);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>(DESCENDING_INTEGER_COMPARATOR);
		assertEquals(-1,c.compare(l1, l2));
	}

	@Test
	public void differentLengthDescending() {
		final List<Integer> l1 = Arrays.asList(1, 2, 3);
		final List<Integer> l2 = Arrays.asList(1, 2);
		final LexicographicComparator<Integer> c = new LexicographicComparator<Integer>(DESCENDING_INTEGER_COMPARATOR);
		assertEquals(1,c.compare(l1, l2)); // this is counterintuitive: the shortest comes first event in this case!
	}

}