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>
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 6f4292c..651245a 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.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 void testEmpty_SpecificCapacity() {
}
@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 void testContains() {
}
@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 void testToString() {
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);
+ }
+ }
}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
index de8777f..cc4f0a4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
@@ -37,6 +37,24 @@ public IntList(int capacity) {
}
/**
+ * Create a list initialized with the values of the given range.
+ *
+ * @param start
+ * the beginning of the range, inclusive
+ * @param end
+ * the end of the range, exclusive
+ * @return the list initialized with the given range
+ * @since 6.6
+ */
+ public static IntList filledWithRange(int start, int end) {
+ IntList list = new IntList(end - start);
+ for (int val = start; val < end; val++) {
+ list.add(val);
+ }
+ return list;
+ }
+
+ /**
* Get number of entries in this list.
*
* @return number of entries in this list.
@@ -126,6 +144,60 @@ public void fillTo(int toIndex, int val) {
add(val);
}
+ /**
+ * Sort the entries of the list in-place, according to the comparator.
+ *
+ * @param comparator
+ * provides the comparison values for sorting the entries
+ * @since 6.6
+ */
+ public void sort(IntComparator comparator) {
+ quickSort(0, count - 1, comparator);
+ }
+
+ /**
+ * Quick sort has average time complexity of O(n log n) and O(log n) space
+ * complexity (for recursion on the stack).
+ * <p>
+ * Implementation based on https://www.baeldung.com/java-quicksort.
+ *
+ * @param begin
+ * the index to begin partitioning at, inclusive
+ * @param end
+ * the index to end partitioning at, inclusive
+ * @param comparator
+ * provides the comparison values for sorting the entries
+ */
+ private void quickSort(int begin, int end, IntComparator comparator) {
+ if (begin < end) {
+ int partitionIndex = partition(begin, end, comparator);
+
+ quickSort(begin, partitionIndex - 1, comparator);
+ quickSort(partitionIndex + 1, end, comparator);
+ }
+ }
+
+ private int partition(int begin, int end, IntComparator comparator) {
+ int pivot = entries[end];
+ int writeSmallerIdx = (begin - 1);
+
+ for (int findSmallerIdx = begin; findSmallerIdx < end; findSmallerIdx++) {
+ if (comparator.compare(entries[findSmallerIdx], pivot) <= 0) {
+ writeSmallerIdx++;
+
+ int biggerVal = entries[writeSmallerIdx];
+ entries[writeSmallerIdx] = entries[findSmallerIdx];
+ entries[findSmallerIdx] = biggerVal;
+ }
+ }
+
+ int pivotIdx = writeSmallerIdx + 1;
+ entries[end] = entries[pivotIdx];
+ entries[pivotIdx] = pivot;
+
+ return pivotIdx;
+ }
+
private void grow() {
final int[] n = new int[(entries.length + 16) * 3 / 2];
System.arraycopy(entries, 0, n, 0, count);
@@ -145,4 +217,22 @@ public String toString() {
r.append(']');
return r.toString();
}
+
+ /**
+ * A comparator of primitive ints.
+ */
+ public interface IntComparator {
+
+ /**
+ * Compares the two int arguments for order.
+ *
+ * @param first
+ * the first int to compare
+ * @param second
+ * the second int to compare
+ * @return a negative number if first < second, 0 if first == second, or
+ * a positive number if first > second
+ */
+ int compare(int first, int second);
+ }
}
