/*

 * Copyright (c) 2016, 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.IOException;

import java.io.InvalidObjectException;

import java.io.ObjectInputStream;

import java.io.ObjectOutputStream;

import java.io.ObjectStreamException;

import java.io.Serializable;

import java.util.function.BiFunction;

import java.util.function.Function;

import java.util.function.Predicate;

import java.util.function.UnaryOperator;

import jdk.internal.misc.SharedSecrets;

import jdk.internal.vm.annotation.Stable;

/**

 * Container class for immutable collections. Not part of the public API.

 * Mainly for namespace management and shared infrastructure.

 *

 * Serial warnings are suppressed throughout because all implementation

 * classes use a serial proxy and thus have no need to declare serialVersionUID.

 */

@SuppressWarnings("serial")

class ImmutableCollections {

    /**

     * A "salt" value used for randomizing iteration order. This is initialized once

     * and stays constant for the lifetime of the JVM. It need not be truly random, but

     * it needs to vary sufficiently from one run to the next so that iteration order

     * will vary between JVM runs.

     */

    static final int SALT;

    static {

        long nt = System.nanoTime();

        SALT = (int)((nt >>> 32) ^ nt);

    }

    /** No instances. */

    private ImmutableCollections() { }

    /**

     * The reciprocal of load factor. Given a number of elements

     * to store, multiply by this factor to get the table size.

     */

    static final int EXPAND_FACTOR = 2;

    static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }

    static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> {

        // all mutating methods throw UnsupportedOperationException

        @Override public boolean add(E e) { throw uoe(); }

        @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }

        @Override public void    clear() { throw uoe(); }

        @Override public boolean remove(Object o) { throw uoe(); }

        @Override public boolean removeAll(Collection<?> c) { throw uoe(); }

        @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }

        @Override public boolean retainAll(Collection<?> c) { throw uoe(); }

    }

    // ---------- List Implementations ----------

    @SuppressWarnings("unchecked")

    static <E> List<E> emptyList() {

        return (List<E>) ListN.EMPTY_LIST;

    }

    static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E>

            implements List<E>, RandomAccess {

        // all mutating methods throw UnsupportedOperationException

        @Override public void    add(int index, E element) { throw uoe(); }

        @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }

        @Override public E       remove(int index) { throw uoe(); }

        @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }

        @Override public E       set(int index, E element) { throw uoe(); }

        @Override public void    sort(Comparator<? super E> c) { throw uoe(); }

        @Override

        public List<E> subList(int fromIndex, int toIndex) {

            int size = size();

            subListRangeCheck(fromIndex, toIndex, size);

            return SubList.fromList(this, fromIndex, toIndex);

        }

        static void subListRangeCheck(int fromIndex, int toIndex, int size) {

            if (fromIndex < 0)

                throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);

            if (toIndex > size)

                throw new IndexOutOfBoundsException("toIndex = " + toIndex);

            if (fromIndex > toIndex)

                throw new IllegalArgumentException("fromIndex(" + fromIndex +

                        ") > toIndex(" + toIndex + ")");

        }

        @Override

        public Iterator<E> iterator() {

            return new ListItr<E>(this, size());

        }

        @Override

        public ListIterator<E> listIterator() {

            return listIterator(0);

        }

        @Override

        public ListIterator<E> listIterator(final int index) {

            int size = size();

            if (index < 0 || index > size) {

                throw outOfBounds(index);

            }

            return new ListItr<E>(this, size, index);

        }

        @Override

        public boolean equals(Object o) {

            if (o == this) {

                return true;

            }

            if (!(o instanceof List)) {

                return false;

            }

            Iterator<?> oit = ((List<?>) o).iterator();

            for (int i = 0, s = size(); i < s; i++) {

                if (!oit.hasNext() || !get(i).equals(oit.next())) {

                    return false;

                }

            }

            return !oit.hasNext();

        }

        @Override

        public int indexOf(Object o) {

            Objects.requireNonNull(o);

            for (int i = 0, s = size(); i < s; i++) {

                if (o.equals(get(i))) {

                    return i;

                }

            }

            return -1;

        }

        @Override

        public int lastIndexOf(Object o) {

            Objects.requireNonNull(o);

            for (int i = size() - 1; i >= 0; i--) {

                if (o.equals(get(i))) {

                    return i;

                }

            }

            return -1;

        }

        @Override

        public int hashCode() {

            int hash = 1;

            for (int i = 0, s = size(); i < s; i++) {

                hash = 31 * hash + get(i).hashCode();

            }

            return hash;

        }

        @Override

        public boolean contains(Object o) {

            return indexOf(o) >= 0;

        }

        IndexOutOfBoundsException outOfBounds(int index) {

            return new IndexOutOfBoundsException("Index: " + index + " Size: " + size());

        }

    }

    static final class ListItr<E> implements ListIterator<E> {

        @Stable

        private final List<E> list;

        @Stable

        private final int size;

        private int cursor;

        ListItr(List<E> list, int size) {

            this(list, size, 0);

        }

        ListItr(List<E> list, int size, int index) {

            this.list = list;

            this.size = size;

            this.cursor = index;

        }

        public boolean hasNext() {

            return cursor != size;

        }

        public E next() {

            try {

                int i = cursor;

                E next = list.get(i);

                cursor = i + 1;

                return next;

            } catch (IndexOutOfBoundsException e) {

                throw new NoSuchElementException();

            }

        }

        public void remove() {

            throw uoe();

        }

        public boolean hasPrevious() {

            return cursor != 0;

        }

        public E previous() {

            try {

                int i = cursor - 1;

                E previous = list.get(i);

                cursor = i;

                return previous;

            } catch (IndexOutOfBoundsException e) {

                throw new NoSuchElementException();

            }

        }

        public int nextIndex() {

            return cursor;

        }

        public int previousIndex() {

            return cursor - 1;

        }

        public void set(E e) {

            throw uoe();

        }

        public void add(E e) {

            throw uoe();

        }

    }

    static final class SubList<E> extends AbstractImmutableList<E>

            implements RandomAccess {

        @Stable

        private final List<E> root;

        @Stable

        private final int offset;

        @Stable

        private final int size;

        private SubList(List<E> root, int offset, int size) {

            this.root = root;

            this.offset = offset;

            this.size = size;

        }

        /**

         * Constructs a sublist of another SubList.

         */

        static <E> SubList<E> fromSubList(SubList<E> parent, int fromIndex, int toIndex) {

            return new SubList<>(parent.root, parent.offset + fromIndex, toIndex - fromIndex);

        }

        /**

         * Constructs a sublist of an arbitrary AbstractImmutableList, which is

         * not a SubList itself.

         */

        static <E> SubList<E> fromList(List<E> list, int fromIndex, int toIndex) {

            return new SubList<>(list, fromIndex, toIndex - fromIndex);

        }

        public E get(int index) {

            Objects.checkIndex(index, size);

            return root.get(offset + index);

        }

        public int size() {

            return size;

        }

        public Iterator<E> iterator() {

            return new ListItr<>(this, size());

        }

        public ListIterator<E> listIterator(int index) {

            rangeCheck(index);

            return new ListItr<>(this, size(), index);

        }

        public List<E> subList(int fromIndex, int toIndex) {

            subListRangeCheck(fromIndex, toIndex, size);

            return SubList.fromSubList(this, fromIndex, toIndex);

        }

        private void rangeCheck(int index) {

            if (index < 0 || index > size) {

                throw outOfBounds(index);

            }

        }

    }

    static final class List12<E> extends AbstractImmutableList<E>

            implements Serializable {

        @Stable

        private final E e0;

        @Stable

        private final E e1;

        List12(E e0) {

            this.e0 = Objects.requireNonNull(e0);

            this.e1 = null;

        }

        List12(E e0, E e1) {

            this.e0 = Objects.requireNonNull(e0);

            this.e1 = Objects.requireNonNull(e1);

        }

        @Override

        public int size() {

            return e1 != null ? 2 : 1;

        }

        @Override

        public E get(int index) {

            if (index == 0) {

                return e0;

            } else if (index == 1 && e1 != null) {

                return e1;

            }

            throw outOfBounds(index);

        }

        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {

            throw new InvalidObjectException("not serial proxy");

        }

        private Object writeReplace() {

            if (e1 == null) {

                return new CollSer(CollSer.IMM_LIST, e0);

            } else {

                return new CollSer(CollSer.IMM_LIST, e0, e1);

            }

        }

    }

    static final class ListN<E> extends AbstractImmutableList<E>

            implements Serializable {

        static final List<?> EMPTY_LIST = new ListN<>();

        @Stable

        private final E[] elements;

        @SafeVarargs

        ListN(E... input) {

            // copy and check manually to avoid TOCTOU

            @SuppressWarnings("unchecked")

            E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input

            for (int i = 0; i < input.length; i++) {

                tmp[i] = Objects.requireNonNull(input[i]);

            }

            elements = tmp;

        }

        @Override

        public boolean isEmpty() {

            return size() == 0;

        }

        @Override

        public int size() {

            return elements.length;

        }

        @Override

        public E get(int index) {

            return elements[index];

        }

        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {

            throw new InvalidObjectException("not serial proxy");

        }

        private Object writeReplace() {

            return new CollSer(CollSer.IMM_LIST, elements);

        }

    }

    // ---------- Set Implementations ----------

    static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E>

            implements Set<E> {

        @Override

        public boolean equals(Object o) {

            if (o == this) {

                return true;

            } else if (!(o instanceof Set)) {

                return false;

            }

            Collection<?> c = (Collection<?>) o;

            if (c.size() != size()) {

                return false;

            }

            for (Object e : c) {

                if (e == null || !contains(e)) {

                    return false;

                }

            }

            return true;

        }

        @Override

        public abstract int hashCode();

    }

    @SuppressWarnings("unchecked")

    static <E> Set<E> emptySet() {

        return (Set<E>) SetN.EMPTY_SET;

    }

    static final class Set12<E> extends AbstractImmutableSet<E>

            implements Serializable {

        @Stable

        final E e0;

        @Stable

        final E e1;

        Set12(E e0) {

            this.e0 = Objects.requireNonNull(e0);

            this.e1 = null;

        }

        Set12(E e0, E e1) {

            if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0

                throw new IllegalArgumentException("duplicate element: " + e0);

            }

            this.e0 = e0;

            this.e1 = e1;

        }

        @Override

        public int size() {

            return (e1 == null) ? 1 : 2;

        }

        @Override

        public boolean contains(Object o) {

            return o.equals(e0) || o.equals(e1); // implicit nullcheck of o

        }

        @Override