Get rid of regexps in STRING_ASCENDING_COMPARATOR

This makes the code both faster and easier to read (no complicated
lookahead/lookbehind pattern).

In a real-world use case for sorting 755 refs (a great number of tags),
the result is:

before: 22 ms
after: 3 ms

Using a list of 10000 elements also shows a factor of about 8.

Change-Id: Ide3f04ce4f13dd974c81e47f6f3c45abfaa15261
Signed-off-by: Robin Stocker <robin@nibor.org>

1 files changed, 33 insertions, 14 deletions

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 38c15d370f..b28c00317a 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
@@ -10,7 +10,8 @@
 package org.eclipse.egit.ui.internal;
 
 import java.util.Comparator;
-import java.util.regex.Pattern;
+import java.util.Iterator;
+import java.util.LinkedList;
 
 import org.eclipse.jgit.lib.Ref;
 
@@ -23,11 +24,6 @@ public class CommonUtils {
 		// non-instantiable utility class
 	}
 
-	private static final Pattern BETWEEN_PARTS =
-			Pattern.compile("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)"); //$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 (also known as natural order).
@@ -39,21 +35,22 @@ public class CommonUtils {
 			if (o2.length() == 0)
 				return 1;
 
-			String[] o1Parts = BETWEEN_PARTS.split(o1);
-			String[] o2Parts = BETWEEN_PARTS.split(o2);
+			LinkedList<String> o1Parts = splitIntoDigitAndNonDigitParts(o1);
+			LinkedList<String> o2Parts = splitIntoDigitAndNonDigitParts(o2);
 
-			for (int i = 0; i < o1Parts.length; i++) {
-				if (i >= o2Parts.length)
+			Iterator<String> o2PartsIterator = o2Parts.iterator();
+
+			for (String o1Part : o1Parts) {
+				if (!o2PartsIterator.hasNext())
 					return 1;
 
-				String o1Part = o1Parts[i];
-				String o2Part = o2Parts[i];
+				String o2Part = o2PartsIterator.next();
 
 				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$
+					o1Part = stripLeadingZeros(o1Part);
+					o2Part = stripLeadingZeros(o2Part);
 					result = o1Part.length() - o2Part.length();
 					if (result == 0)
 						result = o1Part.compareTo(o2Part);
@@ -79,4 +76,26 @@ public class CommonUtils {
 		}
 	};
 
+	private static LinkedList<String> splitIntoDigitAndNonDigitParts(String input) {
+		LinkedList<String> parts = new LinkedList<String>();
+		int partStart = 0;
+		boolean previousWasDigit = Character.isDigit(input.charAt(0));
+		for (int i = 1; i < input.length(); i++) {
+			boolean isDigit = Character.isDigit(input.charAt(i));
+			if (isDigit != previousWasDigit) {
+				parts.add(input.substring(partStart, i));
+				partStart = i;
+				previousWasDigit = isDigit;
+			}
+		}
+		parts.add(input.substring(partStart));
+		return parts;
+	}
+
+	private static String stripLeadingZeros(String input) {
+		for (int i = 0; i < input.length(); i++)
+			if (input.charAt(i) != '0')
+				return input.substring(i);
+		return ""; //$NON-NLS-1$
+	}
 }