/*
 * 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());
        }
    }

    /**
     * The comparator for comparing character sequences that consist solely
     * of decimal digits.  The result of comparing is as if the values were
     * compared numerically.
     */
    private static class DecimalComparator implements Comparator<CharSequence>,
            Serializable {

        private static final long serialVersionUID = 0x661e8cc550c7704dL;

        private static final Comparator<CharSequence>
                DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST =
                new DecimalComparator(true) {
                    @Override
                    public Comparator<CharSequence> reversed() {
                        return DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST_REVERSED;
                    }
                };

        private static final Comparator<CharSequence>
                DECIMAL_COMPARATOR_LEADING_ZEROES_LAST =
                new DecimalComparator(false) {
                    @Override
                    public Comparator<CharSequence> reversed() {
                        return DECIMAL_COMPARATOR_LEADING_ZEROES_LAST_REVERSED;
                    }
                };

        private static final Comparator<CharSequence>
                DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST_REVERSED =
                new DecimalComparator(true) {
                    @Override
                    public Comparator<CharSequence> reversed() {
                        return DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST;
                    }
                    @Override
                    public int compare(CharSequence cs1, CharSequence cs2) {
                        return super.compare(cs2, cs1);
                    }
                };

        private static final Comparator<CharSequence>
                DECIMAL_COMPARATOR_LEADING_ZEROES_LAST_REVERSED =
                new DecimalComparator(false) {
                    @Override
                    public Comparator<CharSequence> reversed() {
                        return DECIMAL_COMPARATOR_LEADING_ZEROES_LAST;
                    }
                    @Override
                    public int compare(CharSequence cs1, CharSequence cs2) {
                        return super.compare(cs2, cs1);
                    }
                };

        private final boolean leadingZeroesFirst;

        private DecimalComparator(boolean leadingZeroesFirst) {
            this.leadingZeroesFirst = leadingZeroesFirst;
        }

        static Comparator<CharSequence> getInstance(boolean leadingZeroesFirst) {
            return leadingZeroesFirst ? DECIMAL_COMPARATOR_LEADING_ZEROES_FIRST
                    : DECIMAL_COMPARATOR_LEADING_ZEROES_LAST;
        }

        private boolean canSkipLeadingZeroes(CharSequence s, int len) {
            for (int i = 0; i < len;) {
                int cp = Character.codePointAt(s, i);
                if (Character.digit(cp, 10) != 0)
                    return false;
                i += Character.charCount(cp);
            }
            return true;
        }

        @Override
        public int compare(CharSequence cs1, CharSequence cs2) {
            int len1 = Character.codePointCount(cs1, 0, cs1.length());
            int len2 = Character.codePointCount(cs2, 0, cs2.length());
            int dlen = len1 - len2;
            if (len1 == 0 || len2 == 0) {
                return dlen;
            } else if (dlen > 0) {
                if (!canSkipLeadingZeroes(cs1, dlen))
                    return 1;
                int off = Character.offsetByCodePoints(cs1, 0, dlen);
                cs1 = cs1.subSequence(off, cs1.length());
            } else if (dlen < 0) {
                if (!canSkipLeadingZeroes(cs2, -dlen))
                    return -1;
                int off = Character.offsetByCodePoints(cs2, 0, -dlen);
                cs2 = cs2.subSequence(off, cs2.length());
            }
            int cmp = 0;
            for (int i1 = 0, i2 = 0; i1 < cs1.length(); ) {
                int cp1 = Character.codePointAt(cs1, i1);
                int cp2 = Character.codePointAt(cs2, i2);
                if (cp1 != cp2) {
                    if (cmp == 0) {
                        cmp = cp1 - cp2;
                    }
                    int cmpNum = Character.digit(cp1, 10) -
                            Character.digit(cp2, 10);
                    if (cmpNum != 0) {
                        return cmpNum;
                    }
                }
                i1 += Character.charCount(cp1);
                i2 += Character.charCount(cp2);
            }
            return dlen == 0 ? cmp : (leadingZeroesFirst ^ (dlen < 0) ? -1 : 1);
        }
    }

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

        private static final long serialVersionUID = 0xd7a7129b9ca1056dL;

        private final Comparator<? super CharSequence> alphaComparator;
        private final Comparator<CharSequence> decimalComparator;

        AlphaDecimalComparator(Comparator<? super CharSequence> alphaComparator,
                               boolean leadingZeroesFirst) {
            this(alphaComparator, DecimalComparator.getInstance(leadingZeroesFirst));
        }

        private AlphaDecimalComparator(Comparator<? super CharSequence> alphaComparator,
                                       Comparator<CharSequence> decimalComparator) {
            this.alphaComparator = alphaComparator;
            this.decimalComparator = decimalComparator;
        }

        @Override
        public Comparator<T> reversed() {
            return new AlphaDecimalComparator<>(alphaComparator.reversed(),
                    decimalComparator.reversed());
        }

        @Override
        public int compare(T cs1, T cs2) {
            Decomposer d1 = new Decomposer(cs1);
            Decomposer d2 = new Decomposer(cs2);
            for (;;) {
                int cmp;
                if ((cmp = alphaComparator.compare(d1.get(), d2.get())) != 0 ||
                    (cmp = decimalComparator.compare(d1.get(), d2.get())) != 0)
                {
                    return cmp;
                }
                if (d1.eos() && d2.eos()) return 0;
            }
        }

        /**
         * Given a CharSequence, splits it into a series of subsequences so that
         * every character of the very first subsequence (possibly empty) is
         * not a decimal digit;  then every character of the second subsequence
         * is a decimal digit, and so on.
         */
        private static class Decomposer {
            private final CharSequence sequence;
            private boolean expectingDecimal = false;
            private int index = 0;

            Decomposer(CharSequence sequence) {
                this.sequence = sequence;
            }

            CharSequence get() {
                int start = index, end = start, len = sequence.length() - start;
                while (len > 0) {
                    int cp = Character.codePointAt(sequence, end);
                    int ct = Character.getType(cp);
                    boolean isDecimal = (ct == Character.DECIMAL_DIGIT_NUMBER);
                    if (isDecimal ^ expectingDecimal) {
                        break;
                    }
                    int cpWidth = Character.charCount(cp);
                    end += cpWidth;
                    len -= cpWidth;
                }
                expectingDecimal = !expectingDecimal;
                return sequence.subSequence(start, index = end);
            }

            boolean eos() {
                return index >= sequence.length();
            }
        }
    }
}