Lior Vernia has uploaded a new change for review. Change subject: core: Added LexoNumericComparator utility ......................................................................
core: Added LexoNumericComparator utility This utility helps to sort strings which include numeric subsequences according to sensible ordering - sorting numeric subsequences numerically, and the rest lexicographically. A corresponding test class is added. Change-Id: I8c68446ea6f1865a51455a0a359df339bfb15bba Signed-off-by: Lior Vernia <[email protected]> --- A backend/manager/modules/common/src/main/java/org/ovirt/engine/core/common/utils/LexoNumericComparator.java A backend/manager/modules/common/src/test/java/org/ovirt/engine/core/common/utils/LexoNumericComparatorTest.java 2 files changed, 178 insertions(+), 0 deletions(-) git pull ssh://gerrit.ovirt.org:29418/ovirt-engine refs/changes/96/11996/1 diff --git a/backend/manager/modules/common/src/main/java/org/ovirt/engine/core/common/utils/LexoNumericComparator.java b/backend/manager/modules/common/src/main/java/org/ovirt/engine/core/common/utils/LexoNumericComparator.java new file mode 100644 index 0000000..cc4136e --- /dev/null +++ b/backend/manager/modules/common/src/main/java/org/ovirt/engine/core/common/utils/LexoNumericComparator.java @@ -0,0 +1,94 @@ +package org.ovirt.engine.core.common.utils; + +import java.util.Comparator; + +/** + * This class may be used to sort strings that have numeric sequences in them. <br> + * <br> + * A common problem is that sorting such strings lexicographically (as any other string) results in an order that may be + * considered counter-intuitive, e.g. "Example10" will appear before "Example2" since '1' is lexicographically less than + * '2'. <br> + * <br> + * The method compare() deals with these strings by splitting them into alternating subsequences of digits and + * nondigits, sorting the digit sequences numerically and the nondigit sequences lexicographically. <br> + * <br> + * It is assumed that a string always begins with a nondigit sequence; if it actually begins with a digit sequence, the + * behaviour is as if it started with an empty nondigit sequence. + */ +public class LexoNumericComparator implements Comparator<String> { + + @Override + public int compare(String str1, String str2) { + return comp(str1, str2); + } + + public static int comp(String str1, String str2) { + if (str1 == null) { + return (str2 == null) ? 0 : -1; + } else if (str2 == null) { + return 1; + } + + boolean isDigitTurn = false; + int begSeq1 = 0, begSeq2 = 0, endSeq1, endSeq2; + + while ((endSeq1 = findEndOfSequence(str1, begSeq1, isDigitTurn)) != begSeq1) { + if ((endSeq2 = findEndOfSequence(str2, begSeq2, isDigitTurn)) == begSeq2) { + return 1; // str1 and str2 have the same prefix but str1 has an extra sequence => str1 > str2 + } + + String seq1 = str1.substring(begSeq1, endSeq1); + String seq2 = str2.substring(begSeq2, endSeq2); + int compRes = compareSequence(seq1, seq2, isDigitTurn); + if (compRes != 0) { + return compRes; // found a difference + } + + isDigitTurn = !isDigitTurn; + begSeq1 = endSeq1; + begSeq2 = endSeq2; + } + + if (begSeq2 != str2.length()) { + return -1; // str1 and str2 have the same prefix but str2 has an extra sequence => str1 < str2 + } + + return 0; // we arrive here only if the strings were equal all along + } + + private static int compareSequence(String seq1, String seq2, boolean isDigitSequence) { + return isDigitSequence ? compDigitSequence(seq1, seq2) : compNonDigitSequence(seq1, seq2); + } + + private static int compDigitSequence(String seq1, String seq2) { + int compRes = ((Integer) Integer.parseInt(seq1)).compareTo(Integer.parseInt(seq2)); + return compRes != 0 ? compRes : compNonDigitSequence(seq1, seq2); + } + + private static int compNonDigitSequence(String seq1, String seq2) { + return seq1.compareTo(seq2); + } + + private static int findEndOfSequence(String seq, int startIndex, boolean isDigitSequence) { + return isDigitSequence ? findEndOfDigitSequence(seq, startIndex) : findEndOfNonDigitSequence(seq, startIndex); + } + + private static int findEndOfDigitSequence(String seq, int startIndex) { + for (int i = startIndex; i < seq.length(); ++i) { + if (!Character.isDigit(seq.charAt(i))) { + return i; + } + } + return seq.length(); + } + + private static int findEndOfNonDigitSequence(String seq, int startIndex) { + for (int i = startIndex; i < seq.length(); ++i) { + if (Character.isDigit(seq.charAt(i))) { + return i; + } + } + return seq.length(); + } + +} diff --git a/backend/manager/modules/common/src/test/java/org/ovirt/engine/core/common/utils/LexoNumericComparatorTest.java b/backend/manager/modules/common/src/test/java/org/ovirt/engine/core/common/utils/LexoNumericComparatorTest.java new file mode 100644 index 0000000..8dcac23 --- /dev/null +++ b/backend/manager/modules/common/src/test/java/org/ovirt/engine/core/common/utils/LexoNumericComparatorTest.java @@ -0,0 +1,84 @@ +package org.ovirt.engine.core.common.utils; + +import static org.junit.Assert.assertEquals; + +import org.junit.Test; + +public class LexoNumericComparatorTest { + private final String DIGIT = "012"; + private final String DIGIT_OTHER = "02"; + private final String DIGIT_NO_LEADING_ZEROS = "12"; + private final String NONDIGIT = "abc"; + private final String NONDIGIT_OTHER = "def"; + private LexoNumericComparator comparator = new LexoNumericComparator(); + + private void verifyResult(String str1, String str2, int expectedResult) { + assertEquals(Integer.signum(expectedResult), Integer.signum(comparator.compare(str1, str2))); + assertEquals(-Integer.signum(expectedResult), Integer.signum(comparator.compare(str2, str1))); + } + + @Test + public void twoNullStrings() { + verifyResult(null, null, 0); + } + + @Test + public void oneNullString() { + verifyResult(null, "", -1); + } + + @Test + public void twoEmptyStrings() { + verifyResult("", "", 0); + } + + @Test + public void oneEmptyString() { + verifyResult("", NONDIGIT, -1); + } + + @Test + public void digitToNonDigit() { + verifyResult(DIGIT, NONDIGIT, -1); + } + + @Test + public void sameStringOneLevel() { + verifyResult(NONDIGIT, NONDIGIT, 0); + } + + @Test + public void SameStringTwoLevels() { + verifyResult(NONDIGIT + DIGIT, NONDIGIT + DIGIT, 0); + } + + @Test + public void sameStringLeadingZeros() { + verifyResult(NONDIGIT + DIGIT, NONDIGIT + DIGIT_NO_LEADING_ZEROS, -1); + } + + @Test + public void SameStringThreeLevels() { + verifyResult(NONDIGIT + DIGIT + NONDIGIT, NONDIGIT + DIGIT + NONDIGIT, 0); + } + + @Test + public void differentFirstLevel() { + verifyResult(NONDIGIT + DIGIT + NONDIGIT, NONDIGIT_OTHER + DIGIT + NONDIGIT, -1); + } + + @Test + public void differentSecondLevel() { + verifyResult(NONDIGIT + DIGIT + NONDIGIT, NONDIGIT + DIGIT_OTHER + NONDIGIT, 1); + } + + @Test + public void differentFirstAndSecondLevels() { + verifyResult(NONDIGIT + DIGIT, NONDIGIT_OTHER + DIGIT_OTHER, -1); + } + + @Test + public void differentThirdLevel() { + verifyResult(NONDIGIT + DIGIT + NONDIGIT, NONDIGIT + DIGIT + NONDIGIT_OTHER, -1); + } +} -- To view, visit http://gerrit.ovirt.org/11996 To unsubscribe, visit http://gerrit.ovirt.org/settings Gerrit-MessageType: newchange Gerrit-Change-Id: I8c68446ea6f1865a51455a0a359df339bfb15bba Gerrit-PatchSet: 1 Gerrit-Project: ovirt-engine Gerrit-Branch: master Gerrit-Owner: Lior Vernia <[email protected]> _______________________________________________ Engine-patches mailing list [email protected] http://lists.ovirt.org/mailman/listinfo/engine-patches
