Fix CommonUtils.STRING_ASCENDING_COMPARATOR issues

The comparator provides the means to sort a list of strings using a
natural sort order (i.e. "2" before "10"). It had two problems.

The first one was that it could not handle strings that contained many
numbers (when all the numbers concatenated exceeded Integer.MAX_VALUE).
This lead to a NumberFormatException. Because the comparator is used in
CreateBranchPage, it was impossible to create a branch in a repository
that had a ref with such a name (e.g. stable-1-0-0_2011-05-25).

The second one was that it resulted in the wrong order for some inputs.
For example, the following inputs would not be sorted as listed here:

  project-1-0-0-final
  project-1-0-1-beta

With the implementation of this change, it behaves correctly for these
two problems.

Change-Id: Ie5edf268889f43c2a4497669aa1700f790cd2cdd
Signed-off-by: Robin Stocker <robin@nibor.org>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

2 files changed, 109 insertions, 19 deletions

diff --git a/org.eclipse.egit.ui.test/src/org/eclipse/egit/ui/internal/CommonUtilsTest.java b/org.eclipse.egit.ui.test/src/org/eclipse/egit/ui/internal/CommonUtilsTest.java
new file mode 100644
index 0000000000..94b6555f29
--- /dev/null
+++ b/org.eclipse.egit.ui.test/src/org/eclipse/egit/ui/internal/CommonUtilsTest.java
@@ -0,0 +1,72 @@
+/*******************************************************************************
+ * Copyright (C) 2011, Robin Stocker <robin@nibor.org>
+ *
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+package org.eclipse.egit.ui.internal;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+
+import org.junit.Test;
+
+/**
+ * Tests for {@link CommonUtils}.
+ */
+public class CommonUtilsTest {
+	@Test
+	public void sortingShouldWorkForEasyStrings() {
+		assertSortedLike("", "");
+		assertSortedLike("", "a");
+		assertSortedLike("a", "asdf");
+		assertSortedLike("aaa", "bbb");
+		assertSortedLike("1", "2");
+	}
+
+	@Test
+	public void sortingShouldWorkForNumbers() {
+		assertSortedLike("2", "10", "100");
+	}
+
+	@Test
+	public void sortingShouldWorkForMixedParts() {
+		assertSortedLike("v1c", "v2b", "v10a");
+		assertSortedLike("asdf", "asdf2", "asdf10");
+		assertSortedLike("1_1", "1_10");
+		assertSortedLike("project-1-0-0-final", "project-1-0-1-beta");
+		assertSortedLike("1-a", "01-b");
+		assertSortedLike("1", "asdf-2", "asdf-10", "b20");
+	}
+
+	@Test
+	public void sortingShouldWorkForBigNumbers() {
+		assertSortedLike("100000000", "100000000000", "100000000000");
+	}
+
+	@Test
+	public void sortingShouldIgnoreLeadingZeros() {
+		assertSortedLike("00001", "2", "3");
+		assertSortedLike("a-01", "a-002");
+	}
+
+	/**
+	 * Assert that sorting the given strings keeps the same order as passed.
+	 *
+	 * @param inputs
+	 */
+	private void assertSortedLike(String... inputs) {
+		List<String> expected = Arrays.asList(inputs);
+		List<String> tmp = new ArrayList<String>(expected);
+		Collections.shuffle(tmp, new Random(1));
+		Collections.sort(tmp, CommonUtils.STRING_ASCENDING_COMPARATOR);
+		assertEquals(expected, tmp);
+	}
+}
diff --git a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/CommonUtils.java b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/CommonUtils.java
index 8d431ca985..38c15d370f 100644
--- a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/CommonUtils.java
+++ b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/CommonUtils.java
@@ -1,5 +1,6 @@
 /*******************************************************************************
  * Copyright (C) 2011, Dariusz Luksza <dariusz@luksza.org>
+ * Copyright (C) 2011, Robin Stocker <robin@nibor.org>
  *
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
@@ -22,38 +23,55 @@ public class CommonUtils {
 		// non-instantiable utility class
 	}
 
-	private static final Pattern NUMBERS = Pattern.compile("[\\d]*"); //$NON-NLS-1$
+	private static final Pattern BETWEEN_PARTS =
+			Pattern.compile("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)"); //$NON-NLS-1$
 
-	private static final Pattern CHARS = Pattern.compile("[^0-9]*"); //$NON-NLS-1$
+	private static final Pattern LEADING_ZEROS = Pattern.compile("^0*"); //$NON-NLS-1$
 
 	/**
 	 * Instance of comparator that sorts strings in ascending alphabetical and
-	 * numerous order.
+	 * numerous order (also known as natural order).
 	 */
 	public static final Comparator<String> STRING_ASCENDING_COMPARATOR = new Comparator<String>() {
 		public int compare(String o1, String o2) {
-			String o1Chars = NUMBERS.matcher(o1).replaceAll(""); //$NON-NLS-1$
-			String o2Chars = NUMBERS.matcher(o2).replaceAll(""); //$NON-NLS-1$
-			int charCompare = o1Chars.compareTo(o2Chars);
-
-			if (charCompare == 0) {
-				String o1Numbers = CHARS.matcher(o1).replaceAll(""); //$NON-NLS-1$
-				String o2Numbers = CHARS.matcher(o2).replaceAll(""); //$NON-NLS-1$
-				if (o1Numbers.length() == 0)
-					o1Numbers = "0"; //$NON-NLS-1$
-				if (o2Numbers.length() == 0)
-					o2Numbers = "0"; //$NON-NLS-1$
-
-				return Integer.parseInt(o2Numbers)
-						- Integer.parseInt(o1Numbers);
+			if (o1.length() == 0)
+				return -1;
+			if (o2.length() == 0)
+				return 1;
+
+			String[] o1Parts = BETWEEN_PARTS.split(o1);
+			String[] o2Parts = BETWEEN_PARTS.split(o2);
+
+			for (int i = 0; i < o1Parts.length; i++) {
+				if (i >= o2Parts.length)
+					return 1;
+
+				String o1Part = o1Parts[i];
+				String o2Part = o2Parts[i];
+
+				int result;
+
+				if (Character.isDigit(o1Part.charAt(0)) && Character.isDigit(o2Part.charAt(0))) {
+					o1Part = LEADING_ZEROS.matcher(o1Part).replaceFirst(""); //$NON-NLS-1$
+					o2Part = LEADING_ZEROS.matcher(o2Part).replaceFirst(""); //$NON-NLS-1$
+					result = o1Part.length() - o2Part.length();
+					if (result == 0)
+						result = o1Part.compareTo(o2Part);
+				} else {
+					result = o1Part.compareTo(o2Part);
+				}
+
+				if (result != 0)
+					return result;
 			}
 
-			return charCompare;
+			return -1;
 		}
 	};
 
 	/**
-	 *
+	 * Instance of comparator which sorts {@link Ref} names using
+	 * {@link CommonUtils#STRING_ASCENDING_COMPARATOR}.
 	 */
 	public static final Comparator<Ref> REF_ASCENDING_COMPARATOR = new Comparator<Ref>() {
 		public int compare(Ref o1, Ref o2) {