IntList: add #sort using quick sort for O(n log n) runtime.

IntList is a class for working with lists of primitive ints without
boxing them into Integers. For writing the reverse index file format,
sorting ints will be needed but IntList doesn't provide a sorting
method yet.

Add the #sort method to sort an IntList by an IntComparator, using
quicksort, which has a average runtime of O(n log n) and sorts in-place
by using O(log n) stack frames for recursive calls.

Change-Id: Id69a687c8a16d46b13b28783b194a880f3f4c437
Signed-off-by: Anna Papitto <annapapitto@google.com>

1 files changed, 34 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/IntListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/IntListTest.java
index 6f4292c05e..651245a083 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/IntListTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/IntListTest.java
@@ -15,6 +15,7 @@ import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
+import org.eclipse.jgit.util.IntList.IntComparator;
 import org.junit.Test;
 
 public class IntListTest {
@@ -43,6 +44,15 @@ public class IntListTest {
 	}
 
 	@Test
+	public void testFilledWithRange() {
+		IntList list = IntList.filledWithRange(-2, 13);
+		assertEquals(15, list.size());
+		for (int i = 0; i < list.size(); i++) {
+			assertEquals(i - 2, list.get(i));
+		}
+	}
+
+	@Test
 	public void testAdd_SmallGroup() {
 		final IntList i = new IntList();
 		final int n = 5;
@@ -164,6 +174,22 @@ public class IntListTest {
 	}
 
 	@Test
+	public void testSort_byAbs() {
+		IntList list = new IntList();
+		list.add(-3);
+		list.add(-2);
+		list.add(0);
+		list.add(1);
+		list.add(4);
+		list.add(1);
+		list.sort(new AbsIntComparator());
+		int[] expected = { 0, 1, 1, -2, -3, 4 };
+		for (int i = 0; i < list.size(); i++) {
+			assertEquals(expected[i], list.get(i));
+		}
+	}
+
+	@Test
 	public void testToString() {
 		final IntList i = new IntList();
 		i.add(1);
@@ -173,4 +199,12 @@ public class IntListTest {
 		assertEquals("[1, 13, 5]", i.toString());
 	}
 
+	private static class AbsIntComparator implements IntComparator {
+		private AbsIntComparator() {
+		}
+
+		public int compare(int a, int b) {
+			return Math.abs(a) - Math.abs(b);
+		}
+	}
 }