/*
 * Copyright (c) 2012, 2017, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
package java.util;

import java.io.Serializable;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.ToDoubleFunction;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;

/**
 * Package private supporting class for {@link Comparator}.
 */
class Comparators {
    private Comparators() {
        throw new AssertionError("no instances");
    }

    /**
     * Compares {@link Comparable} objects in natural order.
     *
     * @see Comparable
     */
    enum NaturalOrderComparator implements Comparator<Comparable<Object>> {
        INSTANCE;

        @Override
        public int compare(Comparable<Object> c1, Comparable<Object> c2) {
            return c1.compareTo(c2);
        }

        @Override
        public Comparator<Comparable<Object>> reversed() {
            return Comparator.reverseOrder();
        }
    }

    /**
     * Null-friendly comparators
     */
    static final class NullComparator<T> implements Comparator<T>, Serializable {
        private static final long serialVersionUID = -7569533591570686392L;
        private final boolean nullFirst;
        // if null, non-null Ts are considered equal
        private final Comparator<T> real;

        @SuppressWarnings("unchecked")
        NullComparator(boolean nullFirst, Comparator<? super T> real) {
            this.nullFirst = nullFirst;
            this.real = (Comparator<T>) real;
        }

        @Override
        public int compare(T a, T b) {
            if (a == null) {
                return (b == null) ? 0 : (nullFirst ? -1 : 1);
            } else if (b == null) {
                return nullFirst ? 1: -1;
            } else {
                return (real == null) ? 0 : real.compare(a, b);
            }
        }

        @Override
        public Comparator<T> thenComparing(Comparator<? super T> other) {
            Objects.requireNonNull(other);
            return new NullComparator<>(nullFirst, real == null ? other : real.thenComparing(other));
        }

        @Override
        public Comparator<T> reversed() {
            return new NullComparator<>(!nullFirst, real == null ? null : real.reversed());
        }
    }

    /**
     * Compares char sequences, taking into account their numeric part if one exists.
     *
     * @see Comparator.comparingNumerically()
     * @see Comparator.comparingNumericallyLeadingZerosFirst()
     */
    static class NumericComparator<T extends CharSequence> implements Comparator<T>, Serializable {

        private static final long serialVersionUID = 0x77164074580FAC97L;

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

        static final Comparator<?> 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;
            }
        };

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

        static final Comparator<?> 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);
        }
    }
}