/*
 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *   - Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 *   - Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 *   - Neither the name of Oracle nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * This source code is provided to illustrate the usage of a given feature
 * or technique and has been deliberately simplified. Additional steps
 * required for a production-quality application, such as security checks,
 * input validation and proper error handling, might not be present in
 * this sample code.
 */

package comparator;

import java.util.Comparator;

class AlphaNumericStringComparator implements Comparator<String>
{
    final Comparator<Character> charComparator;

    public AlphaNumericStringComparator() {
        this(Character::compare);
    }

    public AlphaNumericStringComparator(Comparator<Character> charComparator) {
        this.charComparator = charComparator;
    }

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

    @Override
    public int compare(String o1, String o2) {
        final int minLength = Integer.min(o1.length(), o2.length());
        int numStart1 = 0;
        int index = 0;

        // skip common prefix of the arguments
        while (index < minLength &&
                charComparator.compare(o1.charAt(index),
                        o2.charAt(index)) == 0)
        {
            if (!Character.isDigit(o1.charAt(index++))) {
                numStart1 = index;
            }
        }

        int numCount1 = index - numStart1;
        if (numCount1 > 0 ||
                (index < minLength &&
                        Character.isDigit(o1.charAt(index)) &&
                        Character.isDigit(o2.charAt(index))))
        {
            // first different character is a digit
            int numCount2 = numCount1;
            int numStart2 = numStart1;

            numCount1 += countDigits(o1, index);
            numCount2 += countDigits(o2, index);

            int numCountWithZeros1 = numCount1;
            int numCountWithZeros2 = numCount2;

            while (numCount1 < numCount2) {
                if (charComparator.compare(o2.charAt(numStart2), '0') != 0) {
                    return -1;
                }
                numStart2++;
                numCount2--;
            }

            while (numCount2 < numCount1) {
                if (charComparator.compare(o1.charAt(numStart1), '0') != 0) {
                    return 1;
                }
                numStart1++;
                numCount1--;
            }

            // here numCount1 == numCount2;
            while (numCount1-- > 0) {
                int res = charComparator.compare(o1.charAt(numStart1++),
                        o2.charAt(numStart2++));
                if (res != 0) {
                    return res;
                }
            }

            if (numCountWithZeros1 != numCountWithZeros2) {
                return (numCountWithZeros1 < numCountWithZeros2) ? -1 : 1;
            }

        }

        // otherwise, compare literally
        for (;; ++index) {
            if (index < o1.length()) {
                if (index < o2.length()) {
                    int res = charComparator.compare(o1.charAt(index),
                            o2.charAt(index));
                    if (res != 0) {
                        return res;
                    }
                } else {
                    return 1;
                }
            } else {
                if (index < o2.length()) {
                    return -1;
                }
                return 0;
            }
        }
    }
}