Created
January 16, 2020 17:37
-
-
Save adamcbuckley/8ccae8b1ede0a65edb1756ea39bb6f2a to your computer and use it in GitHub Desktop.
A java.util.Comparator for version (or chapter) numbers, which have an arbitrary number of decimal points.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.hebdensoft; | |
import java.util.Comparator; | |
/** | |
* <p>A java.util.Comparator for version (or chapter) numbers, which have an arbitrary number of decimal points.</p> | |
* <p>The code was taken from https://bugs.openjdk.java.net/browse/JDK-8134512 and http://cr.openjdk.java.net/~igerasim/8134512/04/webrev/index.html</p> | |
* <p>How to use:</p> | |
* <p><code>myListOfVersionNumbers.sort(VersionNumberComparator.getInstance());</code></p> | |
* <p>The code snippet would convert this list:</p> | |
* <ul> | |
* <li>1.1</li> | |
* <li>1.2</li> | |
* <li>1</li> | |
* <li>1.3</li> | |
* <li>1.1.1</li> | |
* <li>5.6</li> | |
* <li>1.1.10</li> | |
* <li>4</li> | |
* <li>1.1.9</li> | |
* <li>1.2.1.10</li> | |
* <li>2.1.1.4.5</li> | |
* <li>1.2.1.9</li> | |
* <li>1.2.1</li> | |
* <li>2.2.2</li> | |
* <li>1.2.1.11</li> | |
* </ul> | |
* <p>Into this list</p> | |
* <ul> | |
* <li>1</li> | |
* <li>1.1</li> | |
* <li>1.1.1</li> | |
* <li>1.1.9</li> | |
* <li>1.1.10</li> | |
* <li>1.2</li> | |
* <li>1.2.1</li> | |
* <li>1.2.1.9</li> | |
* <li>1.2.1.10</li> | |
* <li>1.2.1.11</li> | |
* <li>1.3</li> | |
* <li>2.1.1.4.5</li> | |
* <li>2.2.2</li> | |
* <li>4</li> | |
* <li>5.6</li> | |
* </ul> | |
*/ | |
public class VersionNumberComparator { | |
public static VersionNumberComparator.AlphaDecimalComparator<String> getInstance() { | |
return new VersionNumberComparator.AlphaDecimalComparator<>(Comparator.comparing(CharSequence::toString, Comparator.naturalOrder()), false); | |
} | |
/** | |
* Compares char sequences, taking into account their numeric part if one exists. | |
*/ | |
public static class AlphaDecimalComparator<T extends CharSequence> implements Comparator<T> { | |
private final Comparator<? super CharSequence> alphaComparator; | |
private final Comparator<CharSequence> decimalComparator; | |
AlphaDecimalComparator(Comparator<? super CharSequence> alphaComparator, boolean leadingZeroesFirst) { | |
this(alphaComparator, DecimalComparator.getInstance(leadingZeroesFirst)); | |
} | |
private AlphaDecimalComparator(Comparator<? super CharSequence> alphaComparator, Comparator<CharSequence> decimalComparator) { | |
this.alphaComparator = alphaComparator; | |
this.decimalComparator = decimalComparator; | |
} | |
@Override | |
public Comparator<T> reversed() { | |
return new AlphaDecimalComparator<>(alphaComparator.reversed(), | |
decimalComparator.reversed()); | |
} | |
@Override | |
public int compare(T cs1, T cs2) { | |
Decomposer d1 = new Decomposer(cs1); | |
Decomposer d2 = new Decomposer(cs2); | |
for (; ; ) { | |
int cmp; | |
if ((cmp = alphaComparator.compare(d1.get(), d2.get())) != 0 || | |
(cmp = decimalComparator.compare(d1.get(), d2.get())) != 0) { | |
return cmp; | |
} | |
if (d1.eos() && d2.eos()) return 0; | |
} | |
} | |
/** | |
* Given a CharSequence, splits it into a series of subsequences so that | |
* every character of the very first subsequence (possibly empty) is | |
* not a decimal digit; then every character of the second subsequence | |
* is a decimal digit, and so on. | |
*/ | |
private static class Decomposer { | |
private final CharSequence sequence; | |
private boolean expectingDecimal = false; | |
private int index = 0; | |
Decomposer(CharSequence sequence) { | |
this.sequence = sequence; | |
} | |
CharSequence get() { | |
int start = index, end = start, len = sequence.length() - start; | |
while (len > 0) { | |
int cp = Character.codePointAt(sequence, end); | |
int ct = Character.getType(cp); | |
boolean isDecimal = (ct == Character.DECIMAL_DIGIT_NUMBER); | |
if (isDecimal ^ expectingDecimal) { | |
break; | |
} | |
int cpWidth = Character.charCount(cp); | |
end += cpWidth; | |
len -= cpWidth; | |
} | |
expectingDecimal = !expectingDecimal; | |
return sequence.subSequence(start, index = end); | |
} | |
boolean eos() { | |
return index >= sequence.length(); | |
} | |
} | |
} | |
/** | |
* The comparator for comparing character sequences that consist solely | |
* of decimal digits. The result of comparing is as if the values were | |
* compared numerically. | |
*/ | |
public static class DecimalComparator implements Comparator<CharSequence> { | |
private static final Comparator<CharSequence> | |
DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST = | |
new DecimalComparator(true) { | |
@Override | |
public Comparator<CharSequence> reversed() { | |
return DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST_REVERSED; | |
} | |
}; | |
private static final Comparator<CharSequence> | |
DECIMAL_COMPARATOR_LEADING_ZEROES_LAST = | |
new DecimalComparator(false) { | |
@Override | |
public Comparator<CharSequence> reversed() { | |
return DECIMAL_COMPARATOR_LEADING_ZEROES_LAST_REVERSED; | |
} | |
}; | |
private static final Comparator<CharSequence> | |
DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST_REVERSED = | |
new DecimalComparator(true) { | |
@Override | |
public Comparator<CharSequence> reversed() { | |
return DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST; | |
} | |
@Override | |
public int compare(CharSequence cs1, CharSequence cs2) { | |
return super.compare(cs2, cs1); | |
} | |
}; | |
private static final Comparator<CharSequence> | |
DECIMAL_COMPARATOR_LEADING_ZEROES_LAST_REVERSED = | |
new DecimalComparator(false) { | |
@Override | |
public Comparator<CharSequence> reversed() { | |
return DECIMAL_COMPARATOR_LEADING_ZEROES_LAST; | |
} | |
@Override | |
public int compare(CharSequence cs1, CharSequence cs2) { | |
return super.compare(cs2, cs1); | |
} | |
}; | |
private final boolean leadingZeroesFirst; | |
public DecimalComparator(boolean leadingZeroesFirst) { | |
this.leadingZeroesFirst = leadingZeroesFirst; | |
} | |
static Comparator<CharSequence> getInstance(boolean leadingZeroesFirst) { | |
return leadingZeroesFirst ? DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST | |
: DECIMAL_COMPARATOR_LEADING_ZEROES_LAST; | |
} | |
private boolean canSkipLeadingZeroes(CharSequence s, int len) { | |
for (int i = 0; i < len; ) { | |
int cp = Character.codePointAt(s, i); | |
if (Character.digit(cp, 10) != 0) | |
return false; | |
i += Character.charCount(cp); | |
} | |
return true; | |
} | |
@Override | |
public int compare(CharSequence cs1, CharSequence cs2) { | |
int len1 = Character.codePointCount(cs1, 0, cs1.length()); | |
int len2 = Character.codePointCount(cs2, 0, cs2.length()); | |
int dlen = len1 - len2; | |
if (len1 == 0 || len2 == 0) { | |
return dlen; | |
} else if (dlen > 0) { | |
if (!canSkipLeadingZeroes(cs1, dlen)) | |
return 1; | |
int off = Character.offsetByCodePoints(cs1, 0, dlen); | |
cs1 = cs1.subSequence(off, cs1.length()); | |
} else if (dlen < 0) { | |
if (!canSkipLeadingZeroes(cs2, -dlen)) | |
return -1; | |
int off = Character.offsetByCodePoints(cs2, 0, -dlen); | |
cs2 = cs2.subSequence(off, cs2.length()); | |
} | |
int cmp = 0; | |
for (int i1 = 0, i2 = 0; i1 < cs1.length(); ) { | |
int cp1 = Character.codePointAt(cs1, i1); | |
int cp2 = Character.codePointAt(cs2, i2); | |
if (cp1 != cp2) { | |
if (cmp == 0) { | |
cmp = cp1 - cp2; | |
} | |
int cmpNum = Character.digit(cp1, 10) - | |
Character.digit(cp2, 10); | |
if (cmpNum != 0) { | |
return cmpNum; | |
} | |
} | |
i1 += Character.charCount(cp1); | |
i2 += Character.charCount(cp2); | |
} | |
return dlen == 0 ? cmp : (leadingZeroesFirst ^ (dlen < 0) ? -1 : 1); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This doesn't support the Semantic Versioning rules of precedence. Using the VersionNumberComparator referred to in this answer when we want
[1.0.0-alpha, 1.0.0-alpha.1, 1.0.0-alpha.beta, 1.0.0-beta, 1.0.0-beta.2, 1.0.0-beta.11, 1.0.0-rc.1, 1, 1.0, 1.0.0, 2.0.0, 2.2.0, 2.10.0]
we instead get[1, 1.0, 1.0.0, 1.0.0-alpha, 1.0.0-alpha.1, 1.0.0-alpha.beta, 1.0.0-beta, 1.0.0-beta.2, 1.0.0-beta.11, 1.0.0-rc.1, 2.0.0, 2.2.0, 2.10.0]