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