001package org.unix4j.util.sort;
002
003import org.unix4j.util.StringUtil;
004
005import java.util.Comparator;
006
007/**
008 * A comparator for version strings similar to "V1.34.123" consisting of optional blanks.
009 * The characters '.', '-' and ':' are treated as group delimiters. Each group is sorted
010 * numerically if possible. If two values are non-numeric, the string are compared instead.
011 * If one value is non-numeric, it comes first.
012 */
013public class VersionStringComparator implements Comparator<CharSequence> {
014
015        /**
016         * The singelton instance.
017         */
018        public static final VersionStringComparator INSTANCE = new VersionStringComparator();
019
020        /**
021         * Private constructor used to create the singleton {@link #INSTANCE}.
022         */
023        private VersionStringComparator() {
024                super();
025        }
026
027        @Override
028        public int compare(CharSequence s1, CharSequence s2) {
029                final int start1 = StringUtil.findStartTrimWhitespace(s1);
030                final int end1 = StringUtil.findEndTrimWhitespace(s1);
031                final int start2 = StringUtil.findStartTrimWhitespace(s2);
032                final int end2 = StringUtil.findEndTrimWhitespace(s2);
033                int grpStart1 = start1;
034                int grpStart2 = start2;
035                int grpEnd1 = findGroupEnd(s1, start1, end1);
036                int grpEnd2= findGroupEnd(s2, start2, end2);
037                while (grpStart1 < grpEnd1 && grpStart2 < grpEnd2) {
038                        final char ch1 = s1.charAt(grpStart1);
039                        final char ch2 = s2.charAt(grpStart2);
040                        int cmp;
041                        if (Character.isDigit(ch1) && Character.isDigit(ch2)) {
042                                cmp = compareGroupNumerically(s1, grpStart1, grpEnd1, s2, grpStart2, grpEnd2);
043                        } else {
044                                cmp = compareGroupLiterally(s1, grpStart1, grpEnd1, s2, grpStart2, grpEnd2);
045                        }
046                        if (cmp != 0) {
047                                return cmp;
048                        }
049                        grpStart1 = grpEnd1;
050                        grpStart2 = grpEnd2;
051                        grpEnd1 = findGroupEnd(s1, grpStart1, end1);
052                        grpEnd2= findGroupEnd(s2, grpStart2, end2);
053                }
054                return grpStart1 < grpEnd1 ? 1 : grpStart2 < grpEnd2 ? -1 : 0;
055        }
056
057        //PREDONDITION: end1 > start1 && end2 > start2
058        private static int compareGroupNumerically(CharSequence s1, int start1, int end1,
059                                                                                           CharSequence s2, int start2, int end2) {
060                final int len1 = end1 - start1;
061                final int len2 = end2 - start2;
062                final int maxlen = Math.max(len1, len2);
063                final int pad1 = maxlen - len1;
064                final int pad2 = maxlen - len2;
065                int cmp = 0;
066                for (int i = 0; i < maxlen; i++) {
067                        final char ch1 = i < pad1 ? '0' : s1.charAt(start1 + i - pad1);
068                        final char ch2 = i < pad2 ? '0' : s2.charAt(start2 + i - pad2);
069                        if (cmp == 0) {
070                                cmp = ch1 < ch2 ? -1 : ch1 > ch2 ? 1 : 0;
071                        }
072                }
073                if (cmp == 0) {
074                        //e.g. s1="123" < s2="0123"
075                        return pad1 < pad2 ? -1 : pad1 > pad2 ? 1 : 0;
076                }
077                return cmp;
078        }
079
080        private static int compareGroupLiterally(CharSequence s1, int start1, int end1,
081                                                                                         CharSequence s2, int start2, int end2) {
082                final int len1 = end1 - start1;
083                final int len2 = end2 - start2;
084                final int minlen = Math.min(len1, len2);
085                for (int i = 0; i < minlen; i++) {
086                        final char ch1 = s1.charAt(start1 + i);
087                        final char ch2 = s2.charAt(start2 + i);
088                        if (ch1 < ch2) return -1;
089                        if (ch1 > ch2) return +1;
090                }
091                //shorter string comes first
092                return len1 > minlen ? 1 : len2 > minlen ? -1 : 0;
093        }
094
095        private static int findGroupEnd(CharSequence s, int start, int end) {
096                Boolean isNumeric = null;
097                for (int i = start; i < end; i++) {
098                        final boolean isDigit = Character.isDigit(s.charAt(i));
099                        if (isNumeric == null) {
100                                isNumeric = isDigit;
101                        } else {
102                                if (isNumeric.booleanValue() != isDigit) {
103                                        return i;
104                                }
105                        }
106                }
107                return end;
108        }
109}