Efficient way to compare version strings in Java [duplicate]
Requires commons-lang3-3.8.1.jar for string operations.
/**
* Compares two version strings.
*
* Use this instead of String.compareTo() for a non-lexicographical
* comparison that works for version strings. e.g. "1.10".compareTo("1.6").
*
* @param v1 a string of alpha numerals separated by decimal points.
* @param v2 a string of alpha numerals separated by decimal points.
* @return The result is 1 if v1 is greater than v2.
* The result is 2 if v2 is greater than v1.
* The result is -1 if the version format is unrecognized.
* The result is zero if the strings are equal.
*/
public int VersionCompare(String v1,String v2)
{
int v1Len=StringUtils.countMatches(v1,".");
int v2Len=StringUtils.countMatches(v2,".");
if(v1Len!=v2Len)
{
int count=Math.abs(v1Len-v2Len);
if(v1Len>v2Len)
for(int i=1;i<=count;i++)
v2+=".0";
else
for(int i=1;i<=count;i++)
v1+=".0";
}
if(v1.equals(v2))
return 0;
String[] v1Str=StringUtils.split(v1, ".");
String[] v2Str=StringUtils.split(v2, ".");
for(int i=0;i<v1Str.length;i++)
{
String str1="",str2="";
for (char c : v1Str[i].toCharArray()) {
if(Character.isLetter(c))
{
int u=c-'a'+1;
if(u<10)
str1+=String.valueOf("0"+u);
else
str1+=String.valueOf(u);
}
else
str1+=String.valueOf(c);
}
for (char c : v2Str[i].toCharArray()) {
if(Character.isLetter(c))
{
int u=c-'a'+1;
if(u<10)
str2+=String.valueOf("0"+u);
else
str2+=String.valueOf(u);
}
else
str2+=String.valueOf(c);
}
v1Str[i]="1"+str1;
v2Str[i]="1"+str2;
int num1=Integer.parseInt(v1Str[i]);
int num2=Integer.parseInt(v2Str[i]);
if(num1!=num2)
{
if(num1>num2)
return 1;
else
return 2;
}
}
return -1;
}
As others have pointed out, String.split() is a very easy way to do the comparison you want, and Mike Deck makes the excellent point that with such (likely) short strings, it probably won't matter much, but what the hey! If you want to make the comparison without manually parsing the string, and have the option of quitting early, you could try the java.util.Scanner class.
public static int versionCompare(String str1, String str2) {
try ( Scanner s1 = new Scanner(str1);
Scanner s2 = new Scanner(str2);) {
s1.useDelimiter("\\.");
s2.useDelimiter("\\.");
while (s1.hasNextInt() && s2.hasNextInt()) {
int v1 = s1.nextInt();
int v2 = s2.nextInt();
if (v1 < v2) {
return -1;
} else if (v1 > v2) {
return 1;
}
}
if (s1.hasNextInt() && s1.nextInt() != 0)
return 1; //str1 has an additional lower-level version number
if (s2.hasNextInt() && s2.nextInt() != 0)
return -1; //str2 has an additional lower-level version
return 0;
} // end of try-with-resources
}
This is almost certainly not the most efficient way to do it, but given that version number strings will almost always be only a few characters long I don't think it's worth optimizing further:
public static int compareVersions(String v1, String v2) {
String[] components1 = v1.split("\\.");
String[] components2 = v2.split("\\.");
int length = Math.min(components1.length, components2.length);
for(int i = 0; i < length; i++) {
int result = new Integer(components1[i]).compareTo(Integer.parseInt(components2[i]));
if(result != 0) {
return result;
}
}
return Integer.compare(components1.length, components2.length);
}
I was looking to do this myself and I see three different approaches to doing this, and so far pretty much everyone is splitting the version strings. I do not see doing that as being efficient, though code size wise it reads well and looks good.
Approaches:
- Assume an upper limit to the number of sections (ordinals) in a version string as well as a limit to the value represented there. Often 4 dots max, and 999 maximum for any ordinal. You can see where this is going, and it's going towards transforming the version to fit into a string like: "1.0" => "001000000000" with string format or some other way to pad each ordinal. Then do a string compare.
- Split the strings on the ordinal separator ('.') and iterate over them and compare a parsed version. This is the approach demonstrated well by Alex Gitelman.
- Comparing the ordinals as you parse them out of the version strings in question. If all strings were really just pointers to arrays of characters as in C then this would be the clear approach (where you'd replace a '.' with a null terminator as it's found and move some 2 or 4 pointers around.
Thoughts on the three approaches:
- There was a blog post linked that showed how to go with 1. The limitations are in version string length, number of sections and maximum value of the section. I don't think it's crazy to have such a string that breaks 10,000 at one point. Additionally most implementations still end up splitting the string.
- Splitting the strings in advance is clear to read and think about, but we are going through each string about twice to do this. I'd like to compare how it times with the next approach.
- Comparing the string as you split it give you the advantage of being able to stop splitting very early in a comparison of: "2.1001.100101.9999998" to "1.0.0.0.0.0.1.0.0.0.1". If this were C and not Java the advantages could go on to limit the amount of memory allocated for new strings for each section of each version, but it is not.
I didn't see anyone giving an example of this third approach, so I'd like to add it here as an answer going for efficiency.
public class VersionHelper {
/**
* Compares one version string to another version string by dotted ordinals.
* eg. "1.0" > "0.09" ; "0.9.5" < "0.10",
* also "1.0" < "1.0.0" but "1.0" == "01.00"
*
* @param left the left hand version string
* @param right the right hand version string
* @return 0 if equal, -1 if thisVersion < comparedVersion and 1 otherwise.
*/
public static int compare(@NotNull String left, @NotNull String right) {
if (left.equals(right)) {
return 0;
}
int leftStart = 0, rightStart = 0, result;
do {
int leftEnd = left.indexOf('.', leftStart);
int rightEnd = right.indexOf('.', rightStart);
Integer leftValue = Integer.parseInt(leftEnd < 0
? left.substring(leftStart)
: left.substring(leftStart, leftEnd));
Integer rightValue = Integer.parseInt(rightEnd < 0
? right.substring(rightStart)
: right.substring(rightStart, rightEnd));
result = leftValue.compareTo(rightValue);
leftStart = leftEnd + 1;
rightStart = rightEnd + 1;
} while (result == 0 && leftStart > 0 && rightStart > 0);
if (result == 0) {
if (leftStart > rightStart) {
return containsNonZeroValue(left, leftStart) ? 1 : 0;
}
if (leftStart < rightStart) {
return containsNonZeroValue(right, rightStart) ? -1 : 0;
}
}
return result;
}
private static boolean containsNonZeroValue(String str, int beginIndex) {
for (int i = beginIndex; i < str.length(); i++) {
char c = str.charAt(i);
if (c != '0' && c != '.') {
return true;
}
}
return false;
}
}
Unit test demonstrating expected output.
public class VersionHelperTest {
@Test
public void testCompare() throws Exception {
assertEquals(1, VersionHelper.compare("1", "0.9"));
assertEquals(1, VersionHelper.compare("0.0.0.2", "0.0.0.1"));
assertEquals(1, VersionHelper.compare("1.0", "0.9"));
assertEquals(1, VersionHelper.compare("2.0.1", "2.0.0"));
assertEquals(1, VersionHelper.compare("2.0.1", "2.0"));
assertEquals(1, VersionHelper.compare("2.0.1", "2"));
assertEquals(1, VersionHelper.compare("0.9.1", "0.9.0"));
assertEquals(1, VersionHelper.compare("0.9.2", "0.9.1"));
assertEquals(1, VersionHelper.compare("0.9.11", "0.9.2"));
assertEquals(1, VersionHelper.compare("0.9.12", "0.9.11"));
assertEquals(1, VersionHelper.compare("0.10", "0.9"));
assertEquals(0, VersionHelper.compare("0.10", "0.10"));
assertEquals(-1, VersionHelper.compare("2.10", "2.10.1"));
assertEquals(-1, VersionHelper.compare("0.0.0.2", "0.1"));
assertEquals(1, VersionHelper.compare("1.0", "0.9.2"));
assertEquals(1, VersionHelper.compare("1.10", "1.6"));
assertEquals(0, VersionHelper.compare("1.10", "1.10.0.0.0.0"));
assertEquals(1, VersionHelper.compare("1.10.0.0.0.1", "1.10"));
assertEquals(0, VersionHelper.compare("1.10.0.0.0.0", "1.10"));
assertEquals(1, VersionHelper.compare("1.10.0.0.0.1", "1.10"));
}
}