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, 90 insertions, 0 deletions

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 de8777f592..cc4f0a46fe 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 class IntList {
 	}
 
 	/**
+	 * 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 class IntList {
 			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 class IntList {
 		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);
+	}
 }