/*
 * Copyright (c) 1999, 2013, 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 com.sun.tools.javac.util;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.AbstractCollection;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.function.Function;
import java.util.stream.Collector;

A class for generic linked lists. Links are supposed to be
 immutable, the only exception being the incremental construction of
 lists via ListBuffers.  List is the main container class in
 GJC. Most data structures and algorithms in GJC use lists rather
 than arrays.
 
Lists are always trailed by a sentinel element, whose head and tail
 are both null.
 
This is NOT part of any supported API.
 If you write code that depends on this, you do so at your own risk.
 This code and its internal interfaces are subject to change or
 deletion without notice.
/** A class for generic linked lists. Links are supposed to be
 *  immutable, the only exception being the incremental construction of
 *  lists via ListBuffers.  List is the main container class in
 *  GJC. Most data structures and algorithms in GJC use lists rather
 *  than arrays.
 *
 *  <p>Lists are always trailed by a sentinel element, whose head and tail
 *  are both null.
 *
 *  <p><b>This is NOT part of any supported API.
 *  If you write code that depends on this, you do so at your own risk.
 *  This code and its internal interfaces are subject to change or
 *  deletion without notice.</b>
 */
public class List<A> extends AbstractCollection<A> implements java.util.List<A> {

    
The first element of the list, supposed to be immutable.
/** The first element of the list, supposed to be immutable.
     */
    public A head;

    
The remainder of the list except for its first element, supposed
 to be immutable.
/** The remainder of the list except for its first element, supposed
     *  to be immutable.
     */
    //@Deprecated
    public List<A> tail;

    
Construct a list given its head and tail.
/** Construct a list given its head and tail.
     */
    List(A head, List<A> tail) {
        this.tail = tail;
        this.head = head;
    }

    
Construct an empty list.
/** Construct an empty list.
     */
    @SuppressWarnings("unchecked")
    public static <A> List<A> nil() {
        return (List<A>)EMPTY_LIST;
    }

    private static final List<?> EMPTY_LIST = new List<Object>(null,null) {
        public List<Object> setTail(List<Object> tail) {
            throw new UnsupportedOperationException();
        }
        public boolean isEmpty() {
            return true;
        }
    };

    
Returns the list obtained from 'l' after removing all elements 'elem'
/** Returns the list obtained from 'l' after removing all elements 'elem'
     */
    public static <A> List<A> filter(List<A> l, A elem) {
        Assert.checkNonNull(elem);
        List<A> res = List.nil();
        for (A a : l) {
            if (a != null && !a.equals(elem)) {
                res = res.prepend(a);
            }
        }
        return res.reverse();
    }

    public List<A> intersect(List<A> that) {
        ListBuffer<A> buf = new ListBuffer<>();
        for (A el : this) {
            if (that.contains(el)) {
                buf.append(el);
            }
        }
        return buf.toList();
    }

    public List<A> diff(List<A> that) {
        ListBuffer<A> buf = new ListBuffer<>();
        for (A el : this) {
            if (!that.contains(el)) {
                buf.append(el);
            }
        }
        return buf.toList();
    }

    
Create a new list from the first n elements of this list /**
     * Create a new list from the first {@code n} elements of this list
     */
    public List<A> take(int n) {
        ListBuffer<A> buf = new ListBuffer<>();
        int count = 0;
        for (A el : this) {
            if (count++ == n) break;
            buf.append(el);
        }
        return buf.toList();
    }

    
Construct a list consisting of given element.
/** Construct a list consisting of given element.
     */
    public static <A> List<A> of(A x1) {
        return new List<>(x1, List.nil());
    }

    
Construct a list consisting of given elements.
/** Construct a list consisting of given elements.
     */
    public static <A> List<A> of(A x1, A x2) {
        return new List<>(x1, of(x2));
    }

    
Construct a list consisting of given elements.
/** Construct a list consisting of given elements.
     */
    public static <A> List<A> of(A x1, A x2, A x3) {
        return new List<>(x1, of(x2, x3));
    }

    
Construct a list consisting of given elements.
/** Construct a list consisting of given elements.
     */
    @SuppressWarnings({"varargs", "unchecked"})
    public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
        return new List<>(x1, new List<>(x2, new List<>(x3, from(rest))));
    }

    
Construct a list consisting all elements of given array.
Params:
array – an array; if null return an empty list/**
     * Construct a list consisting all elements of given array.
     * @param array an array; if {@code null} return an empty list
     */
    public static <A> List<A> from(A[] array) {
        List<A> xs = nil();
        if (array != null)
            for (int i = array.length - 1; i >= 0; i--)
                xs = new List<>(array[i], xs);
        return xs;
    }

    public static <A> List<A> from(Iterable<? extends A> coll) {
        ListBuffer<A> xs = new ListBuffer<>();
        for (A a : coll) {
            xs.append(a);
        }
        return xs.toList();
    }

    
Construct a list consisting of a given number of identical elements.
 @param len    The number of elements in the list.
 @param init   The value of each element.
/** Construct a list consisting of a given number of identical elements.
     *  @param len    The number of elements in the list.
     *  @param init   The value of each element.
     */
    @Deprecated
    public static <A> List<A> fill(int len, A init) {
        List<A> l = nil();
        for (int i = 0; i < len; i++) l = new List<>(init, l);
        return l;
    }

    
Does list have no elements?
/** Does list have no elements?
     */
    @Override
    public boolean isEmpty() {
        return tail == null;
    }

    
Does list have elements?
/** Does list have elements?
     */
    //@Deprecated
    public boolean nonEmpty() {
        return tail != null;
    }

    
Return the number of elements in this list.
/** Return the number of elements in this list.
     */
    //@Deprecated
    public int length() {
        List<A> l = this;
        int len = 0;
        while (l.tail != null) {
            l = l.tail;
            len++;
        }
        return len;
    }
    @Override
    public int size() {
        return length();
    }

    public List<A> setTail(List<A> tail) {
        this.tail = tail;
        return tail;
    }

    
Prepend given element to front of list, forming and returning
 a new list.
/** Prepend given element to front of list, forming and returning
     *  a new list.
     */
    public List<A> prepend(A x) {
        return new List<>(x, this);
    }

    
Prepend given list of elements to front of list, forming and returning
 a new list.
/** Prepend given list of elements to front of list, forming and returning
     *  a new list.
     */
    public List<A> prependList(List<A> xs) {
        if (this.isEmpty()) return xs;
        if (xs.isEmpty()) return this;
        if (xs.tail.isEmpty()) return prepend(xs.head);
        // return this.prependList(xs.tail).prepend(xs.head);
        List<A> result = this;
        List<A> rev = xs.reverse();
        Assert.check(rev != xs);
        // since xs.reverse() returned a new list, we can reuse the
        // individual List objects, instead of allocating new ones.
        while (rev.nonEmpty()) {
            List<A> h = rev;
            rev = rev.tail;
            h.setTail(result);
            result = h;
        }
        return result;
    }

    
Reverse list.
If the list is empty or a singleton, then the same list is returned.
Otherwise a new list is formed.
/** Reverse list.
     * If the list is empty or a singleton, then the same list is returned.
     * Otherwise a new list is formed.
     */
    public List<A> reverse() {
        // if it is empty or a singleton, return itself
        if (isEmpty() || tail.isEmpty())
            return this;

        List<A> rev = nil();
        for (List<A> l = this; l.nonEmpty(); l = l.tail)
            rev = new List<>(l.head, rev);
        return rev;
    }

    
Append given element at length, forming and returning
 a new list.
/** Append given element at length, forming and returning
     *  a new list.
     */
    public List<A> append(A x) {
        return of(x).prependList(this);
    }

    
Append given list at length, forming and returning
 a new list.
/** Append given list at length, forming and returning
     *  a new list.
     */
    public List<A> appendList(List<A> x) {
        return x.prependList(this);
    }

    
Append given list buffer at length, forming and returning a new
list.
/**
     * Append given list buffer at length, forming and returning a new
     * list.
     */
    public List<A> appendList(ListBuffer<A> x) {
        return appendList(x.toList());
    }

    
Copy successive elements of this list into given vector until
 list is exhausted or end of vector is reached.
/** Copy successive elements of this list into given vector until
     *  list is exhausted or end of vector is reached.
     */
    @Override @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] vec) {
        int i = 0;
        List<A> l = this;
        Object[] dest = vec;
        while (l.nonEmpty() && i < vec.length) {
            dest[i] = l.head;
            l = l.tail;
            i++;
        }
        if (l.isEmpty()) {
            if (i < vec.length)
                vec[i] = null;
            return vec;
        }

        vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
        return toArray(vec);
    }

    public Object[] toArray() {
        return toArray(new Object[size()]);
    }

    
Form a string listing all elements with given separator character.
/** Form a string listing all elements with given separator character.
     */
    public String toString(String sep) {
        if (isEmpty()) {
            return "";
        } else {
            StringBuilder buf = new StringBuilder();
            buf.append(head);
            for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
                buf.append(sep);
                buf.append(l.head);
            }
            return buf.toString();
        }
    }

    
Form a string listing all elements with comma as the separator character.
/** Form a string listing all elements with comma as the separator character.
     */
    @Override
    public String toString() {
        return toString(",");
    }

    
Compute a hash code, overrides Object
 @see java.util.List#hashCode
/** Compute a hash code, overrides Object
     *  @see java.util.List#hashCode
     */
    @Override
    public int hashCode() {
        List<A> l = this;
        int h = 1;
        while (l.tail != null) {
            h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
            l = l.tail;
        }
        return h;
    }

    
Is this list the same as other list?
 @see java.util.List#equals
/** Is this list the same as other list?
     *  @see java.util.List#equals
     */
    @Override
    public boolean equals(Object other) {
        if (other instanceof List<?>)
            return equals(this, (List<?>)other);
        if (other instanceof java.util.List<?>) {
            List<A> t = this;
            Iterator<?> oIter = ((java.util.List<?>) other).iterator();
            while (t.tail != null && oIter.hasNext()) {
                Object o = oIter.next();
                if ( !(t.head == null ? o == null : t.head.equals(o)))
                    return false;
                t = t.tail;
            }
            return (t.isEmpty() && !oIter.hasNext());
        }
        return false;
    }

    
Are the two lists the same?
/** Are the two lists the same?
     */
    public static boolean equals(List<?> xs, List<?> ys) {
        while (xs.tail != null && ys.tail != null) {
            if (xs.head == null) {
                if (ys.head != null) return false;
            } else {
                if (!xs.head.equals(ys.head)) return false;
            }
            xs = xs.tail;
            ys = ys.tail;
        }
        return xs.tail == null && ys.tail == null;
    }

    
Does the list contain the specified element?
/** Does the list contain the specified element?
     */
    @Override
    public boolean contains(Object x) {
        List<A> l = this;
        while (l.tail != null) {
            if (x == null) {
                if (l.head == null) return true;
            } else {
                if (l.head.equals(x)) return true;
            }
            l = l.tail;
        }
        return false;
    }

    
The last element in the list, if any, or null.
/** The last element in the list, if any, or null.
     */
    public A last() {
        A last = null;
        List<A> t = this;
        while (t.tail != null) {
            last = t.head;
            t = t.tail;
        }
        return last;
    }

    @SuppressWarnings("unchecked")
    public <Z> List<Z> map(Function<A, Z> mapper) {
        boolean changed = false;
        ListBuffer<Z> buf = new ListBuffer<>();
        for (A a : this) {
            Z z = mapper.apply(a);
            buf.append(z);
            changed |= (z != a);
        }
        return changed ? buf.toList() : (List<Z>)this;
    }

    @SuppressWarnings("unchecked")
    public static <T> List<T> convert(Class<T> klass, List<?> list) {
        if (list == null)
            return null;
        for (Object o : list)
            klass.cast(o);
        return (List<T>)list;
    }

    private static final Iterator<?> EMPTYITERATOR = new Iterator<Object>() {
            public boolean hasNext() {
                return false;
            }
            public Object next() {
                throw new java.util.NoSuchElementException();
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };

    @SuppressWarnings("unchecked")
    private static <A> Iterator<A> emptyIterator() {
        return (Iterator<A>)EMPTYITERATOR;
    }

    @Override
    public Iterator<A> iterator() {
        if (tail == null)
            return emptyIterator();
        return new Iterator<A>() {
            List<A> elems = List.this;
            public boolean hasNext() {
                return elems.tail != null;
            }
            public A next() {
                if (elems.tail == null)
                    throw new NoSuchElementException();
                A result = elems.head;
                elems = elems.tail;
                return result;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    public A get(int index) {
        if (index < 0)
            throw new IndexOutOfBoundsException(String.valueOf(index));

        List<A> l = this;
        for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
            ;

        if (l.isEmpty())
            throw new IndexOutOfBoundsException("Index: " + index + ", " +
                                                "Size: " + size());
        return l.head;
    }

    public boolean addAll(int index, Collection<? extends A> c) {
        if (c.isEmpty())
            return false;
        throw new UnsupportedOperationException();
    }

    public A set(int index, A element) {
        throw new UnsupportedOperationException();
    }

    public void add(int index, A element) {
        throw new UnsupportedOperationException();
    }

    public A remove(int index) {
        throw new UnsupportedOperationException();
    }

    public int indexOf(Object o) {
        int i = 0;
        for (List<A> l = this; l.tail != null; l = l.tail, i++) {
            if (l.head == null ? o == null : l.head.equals(o))
                return i;
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        int last = -1;
        int i = 0;
        for (List<A> l = this; l.tail != null; l = l.tail, i++) {
            if (l.head == null ? o == null : l.head.equals(o))
                last = i;
        }
        return last;
    }

    public ListIterator<A> listIterator() {
        return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
    }

    public ListIterator<A> listIterator(int index) {
        return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
    }

    public java.util.List<A> subList(int fromIndex, int toIndex) {
        if  (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
            throw new IllegalArgumentException();

        ArrayList<A> a = new ArrayList<>(toIndex - fromIndex);
        int i = 0;
        for (List<A> l = this; l.tail != null; l = l.tail, i++) {
            if (i == toIndex)
                break;
            if (i >= fromIndex)
                a.add(l.head);
        }

        return Collections.unmodifiableList(a);
    }

    
Collect elements into a new list (using a @code{ListBuffer})
/**
     * Collect elements into a new list (using a @code{ListBuffer})
     */
    public static <Z> Collector<Z, ListBuffer<Z>, List<Z>> collector() {
        return Collector.of(ListBuffer::new,
                ListBuffer::add,
                (buf1, buf2)-> { buf1.addAll(buf2); return buf1; },
                ListBuffer::toList);
    }
}