package ivan;

import java.io.Serializable;
import java.util.Comparator;

public class NumericComparator<T extends CharSequence> implements Comparator<T>, Serializable {

    private static final long serialVersionUID = 0x77164074580FAC97L;

    public static final Comparator<CharSequence> INSTANCE_LEADING_ZEROS_FIRST_NATURAL =
        new NumericComparator<CharSequence>(true) {
            @Override
            @SuppressWarnings("unchecked")
            public Comparator<CharSequence> reversed() {
                return (Comparator<CharSequence>) INSTANCE_LEADING_ZEROS_FIRST_REVERSED;
            }
        };

    public static final Comparator<CharSequence> INSTANCE_LEADING_ZEROS_FIRST_REVERSED =
        new NumericComparator<CharSequence>(true) {
            @Override
            public int compare(CharSequence o1, CharSequence o2) {
                return super.compare(o2, o1);
            }

            @Override
            @SuppressWarnings("unchecked")
            public Comparator<CharSequence> reversed() {
                return (Comparator<CharSequence>) INSTANCE_LEADING_ZEROS_FIRST_NATURAL;
            }
        };

    public static final Comparator<CharSequence> INSTANCE_LEADING_ZEROS_LAST_NATURAL =
        new NumericComparator<CharSequence>(false) {
            @Override
            @SuppressWarnings("unchecked")
            public Comparator<CharSequence> reversed() {
                return (Comparator<CharSequence>) INSTANCE_LEADING_ZEROS_LAST_REVERSED;
            }
        };

    public static final Comparator<CharSequence> INSTANCE_LEADING_ZEROS_LAST_REVERSED =
        new NumericComparator<CharSequence>(false) {
            @Override
            public int compare(CharSequence o1, CharSequence o2) {
                return super.compare(o2, o1);
            }

            @Override
            @SuppressWarnings("unchecked")
            public Comparator<CharSequence> reversed() {
                return (Comparator<CharSequence>) INSTANCE_LEADING_ZEROS_LAST_NATURAL;
            }
        };

    /**
     * If true, the string representation of a number with
     * more leading zeros will be treated as smaller.
     * E.g.: "0001" < "001" < "1".
     */
    private final boolean leadingZerosFirst;

    /**
     * Constructs a new comparator with possibility to specify
     * how it should deal with leading zeros in numbers.
     *
     * @param leadingZerosFirst if {@code true}, numbers with
     *                          more leading zeros are treated as smaller.
     */
    private NumericComparator(boolean leadingZerosFirst) {
        this.leadingZerosFirst = leadingZerosFirst;
    }

    /**
     * Counts how many consequtive characters in the string {@code o}
     * are digits, starting from the position {@code from}.
     */
    private int countDigits(CharSequence o, int from) {
        for (int i = from, len = o.length(); ; ++i) {
            if (i == len || !Character.isDigit(o.charAt(i))) {
                return i - from;
            }
        }
    }

    /**
     * Checks if all {@code cnt} chars of the sequence {@code o},
     * starting with {@code pos} are zeros.
     *
     * @param pos position of the first digit of numeric part.
     * @param cnt number of digits to check;  must be > 0.
     * @return {@code true} if the numeric part of the string {@code o}
     * can be reduced in length by {@code cnt} without changing its
     * numerical value.
     */
    private boolean skipLeadingZeros(CharSequence o, int pos, int cnt) {
        do {
            if (Character.digit(o.charAt(pos++), 10) != 0) {
                // Leading digit of numeric part of o isn't zero
                return false;
            }
        } while (--cnt > 0);
        return true;
    }

    @Override
    public int compare(T o1, T o2) {
        int minLen = Math.min(o1.length(), o2.length());
        int numStart1 = 0;
        int index = 0;
        int res0 = 0;

        // Skip common prefix of the arguments
        char ch;
        while (index < minLen &&
               (res0 = Character.compare(ch = o1.charAt(index),
                                         o2.charAt(index))) == 0) {
            ++index;
            if (!Character.isDigit(ch)) {
                numStart1 = index;
            }
        }

        int numLen1 = index - numStart1;
        if (numLen1 > 0 ||
            (index < minLen &&
             Character.isDigit(o1.charAt(index)) &&
             Character.isDigit(o2.charAt(index)))) {
            // The difference is inside or at the boundary of
            // numerical part
            int numLen2 = numLen1;
            int numStart2 = numStart1;

            numLen1 += countDigits(o1, index);
            numLen2 += countDigits(o2, index);

            int diffNumLen = numLen2 - numLen1;

            if (diffNumLen > 0) {
                if (!skipLeadingZeros(o2, numStart2, diffNumLen)) {
                    // Length of numeric part of o2 is greater
                    return -1;
                }
                numStart2 += diffNumLen;
                numLen2 = numLen1;
            } else if (diffNumLen < 0) {
                if (!skipLeadingZeros(o1, numStart1, -diffNumLen)) {
                    // Length of numeric part of o1 is greater
                    return 1;
                }
                numStart1 -= diffNumLen;
                numLen1 = numLen2;
            }

            // Numeric parts are of the same length, so they can
            // be compared literally
            while (numLen1-- > 0) {
                int res1 = Character.compare(o1.charAt(numStart1++),
                                             o2.charAt(numStart2++));
                if (res1 != 0) {
                    return res1;
                }
            }

            // Numeric parts are numerically equal
            if (diffNumLen != 0) {
                // If leadingZerosFirst == true, treat the number
                // with more leading zeros as smaller
                return (leadingZerosFirst ^ (diffNumLen > 0)) ? -1 : 1;
            }
        }

        // Otherwise, compare literally
        return (index < o1.length())
               ? ((index < o2.length()) ? res0 : 1)
               : ((index < o2.length()) ? -1 : 0);
    }
}