001package org.unix4j.util.sort;
002
003import java.text.DecimalFormatSymbols;
004import java.util.Comparator;
005import java.util.Locale;
006import java.util.Objects;
007
008/**
009 * A comparator for decimal strings consisting of optional blanks, an optional
010 * '-' sign, and zero or more digits possibly separated by thousands separators,
011 * optionally followed by a decimal-point character and zero or more digits. An
012 * empty number is treated as '0'.
013 */
014public class DecimalNumberStringComparator implements Comparator<CharSequence> {
015
016        /**
017         * The instance for the default locale returned by {@link #getInstance()}.
018         */
019        private static final DecimalNumberStringComparator DEFAULT_INSTANCE = new DecimalNumberStringComparator();
020
021        /**
022         * Returns the instance for the default locale.
023         * 
024         * @see Locale#getDefault()
025         */
026        public static DecimalNumberStringComparator getInstance() {
027                return DEFAULT_INSTANCE;
028        }
029
030        /**
031         * Returns an instance for the specified locale.
032         */
033        public static DecimalNumberStringComparator getInstance(Locale locale) {
034                return new DecimalNumberStringComparator(locale);
035        }
036
037        private final DecimalFormatSymbols symbols;
038
039        /**
040         * Private constructor used to create the {@link #DEFAULT_INSTANCE}.
041         */
042        private DecimalNumberStringComparator() {
043                this(DecimalFormatSymbols.getInstance());
044        }
045
046        /**
047         * Private constructor used by {@link #getInstance(Locale)}.
048         */
049        private DecimalNumberStringComparator(Locale locale) {
050                this(DecimalFormatSymbols.getInstance(locale));
051        }
052
053        /**
054         * Constructor with decimal symbols.
055         * 
056         * @param symbols
057         *            the decimal symbols
058         */
059        public DecimalNumberStringComparator(DecimalFormatSymbols symbols) {
060                this.symbols = Objects.requireNonNull(symbols);
061        }
062
063        @Override
064        public int compare(CharSequence s1, CharSequence s2) {
065                final int start1 = TrimBlanksStringComparator.findStartTrimBlanks(s1);
066                final int start2 = TrimBlanksStringComparator.findStartTrimBlanks(s2);
067                return compare(s1, start1, s1.length(), s2, start2, s2.length());
068        }
069
070        int compare(CharSequence s1, int start1, int end1, CharSequence s2, int start2, int end2) {
071                final char decimalSeparator = symbols.getDecimalSeparator();
072                final char groupingSeparator = symbols.getGroupingSeparator();
073                final char zeroDigit = symbols.getZeroDigit();
074                final boolean isNeg1 = start1 < end1 && s1.charAt(start1) == '-';
075                final boolean isNeg2 = start2 < end2 && s2.charAt(start2) == '-';
076                int index1 = skipLeadingZeroChars(s1, isNeg1 ? start1 + 1 : start1, end1, zeroDigit);
077                int index2 = skipLeadingZeroChars(s2, isNeg2 ? start2 + 1 : start2, end2, zeroDigit);
078                int cmp = 0;
079                boolean isZero1 = true;
080                boolean isZero2 = true;
081                while (index1 < end1 || index2 < end2) {
082                        index1 = skipGroupingSeparatorChars(s1, index1, end1, groupingSeparator);
083                        index2 = skipGroupingSeparatorChars(s2, index2, end2, groupingSeparator);
084                        final char ch1 = index1 < end1 ? s1.charAt(index1) : '\n';
085                        final char ch2 = index2 < end2 ? s2.charAt(index2) : '\n';
086                        final boolean isDigit1 = Character.isDigit(ch1);
087                        final boolean isDigit2 = Character.isDigit(ch2);
088                        if (isDigit1 && isDigit2) {
089                                isZero1 &= (isDigit1 && ch1 == zeroDigit);
090                                isZero2 &= (isDigit2 && ch2 == zeroDigit);
091                                if (cmp == 0) {
092                                        cmp = ch1 - ch2;
093                                }
094                                index1++;
095                                index2++;
096                        } else if (ch1 == decimalSeparator || ch2 == decimalSeparator) {
097                                return compareAfterDecimals(s1, index1, end1, ch1, isNeg1, isZero1, s2, index2, end2, ch2, isNeg2, isZero2, cmp);
098                        } else {
099                                if (isDigit1) {
100                                        return applySign(1, isNeg1, isNeg2);
101                                } else if (isDigit2) {
102                                        return applySign(-1, isNeg1, isNeg2);
103                                } else {
104                                        if (cmp == 0) {
105                                                cmp = ch1 - ch2;
106                                        }
107                                        index1++;
108                                        index2++;
109                                }
110                        }
111                }
112                return applySign(cmp, isNeg1 && !isZero1, isNeg2 && !isZero2);
113        }
114        private int compareAfterDecimals(CharSequence s1, int index1, int end1, char ch1, boolean isNeg1, boolean isZero1, CharSequence s2, int index2, int end2, char ch2, boolean isNeg2, boolean isZero2, int cmp) {
115                final char decimalSeparator = symbols.getDecimalSeparator();
116                final char zeroDigit = symbols.getZeroDigit();
117                boolean isDigit1 = Character.isDigit(ch1); 
118                boolean isDigit2 = Character.isDigit(ch2); 
119                final boolean isDecimal1 = ch1 == decimalSeparator; 
120                final boolean isDecimal2 = ch2 == decimalSeparator; 
121                
122                if (isDigit1 && !isDecimal1 && isDecimal2) {
123                        return applySign(1, isNeg1, isNeg2);
124                } else if (isDigit2 && isDecimal1 && !isDecimal2) {
125                        return applySign(-1, isNeg1, isNeg2);
126                }
127                //both integer parts have ended, hence...
128                if (cmp != 0) {
129                        return applySign(cmp, isNeg1 && !isZero1, isNeg2 && !isZero2);
130                }
131                if (isDecimal1) {
132                        index1++;
133                }
134                if (isDecimal2) {
135                        index2++;
136                }
137                while (cmp == 0 && (index1 < end1 || index2 < end2)) {
138                        ch1 = index1 < end1 ? s1.charAt(index1) : '\n';
139                        ch2 = index2 < end2 ? s2.charAt(index2) : '\n';
140                        isDigit1 = Character.isDigit(ch1);
141                        isDigit2 = Character.isDigit(ch2);
142                        if (isDigit1 && isDigit2) {
143                                isZero1 &= (isDigit1 && ch1 == zeroDigit);
144                                isZero2 &= (isDigit2 && ch2 == zeroDigit);
145                                cmp = ch1 - ch2;
146                                index1++;
147                                index2++;
148                        } else {
149                                if (isDigit1) {
150                                        if (ch1 == zeroDigit && isDecimal1) {
151                                                index1++;
152                                        } else {
153                                                return applySign(1, isNeg1, isNeg2);
154                                        }
155                                } else if (isDigit2) {
156                                        if (ch2 == zeroDigit && isDecimal2) {
157                                                index2++;
158                                        } else {
159                                                return applySign(-1, isNeg1, isNeg2);
160                                        }
161                                } else {
162                                        cmp = ch1 - ch2;
163                                        index1++;
164                                        index2++;
165                                }
166                        }
167                }
168                return applySign(cmp, isNeg1 && !isZero1, isNeg2 && !isZero2);
169        }
170
171        private int applySign(int cmp, boolean isNeg1, boolean isNeg2) {
172                if (isNeg1) {
173                        return isNeg2 ? -cmp : -1;
174                } else {
175                        return isNeg2 ? 1 : cmp;
176                }
177        }
178
179        private int skipLeadingZeroChars(CharSequence s, int index, int end, char zeroDigit) {
180                while (index < end) {
181                        final char ch = s.charAt(index);
182                        if (ch == zeroDigit) {
183                                index++;
184                        } else {
185                                return index;
186                        }
187                }
188                return end;
189        }
190        private int skipGroupingSeparatorChars(CharSequence s, int index, int end, char groupingSeparator) {
191                if (index < end && s.charAt(index) == groupingSeparator) {
192                        return index + 1;
193                }
194                return index;
195        }
196}