duke@1: /*
jjg@1362:  * Copyright (c) 1999, 2012, Oracle and/or its affiliates. All rights reserved.
duke@1:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1:  *
duke@1:  * This code is free software; you can redistribute it and/or modify it
duke@1:  * under the terms of the GNU General Public License version 2 only, as
ohair@554:  * published by the Free Software Foundation.  Oracle designates this
duke@1:  * particular file as subject to the "Classpath" exception as provided
ohair@554:  * by Oracle in the LICENSE file that accompanied this code.
duke@1:  *
duke@1:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@1:  * version 2 for more details (a copy is included in the LICENSE file that
duke@1:  * accompanied this code).
duke@1:  *
duke@1:  * You should have received a copy of the GNU General Public License version
duke@1:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@1:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1:  *
ohair@554:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554:  * or visit www.oracle.com if you need additional information or have any
ohair@554:  * questions.
duke@1:  */
duke@1: 
duke@1: package com.sun.tools.javac.util;
duke@1: 
duke@1: import java.lang.reflect.Array;
duke@1: import java.util.ArrayList;
duke@1: import java.util.Collection;
duke@1: import java.util.Collections;
duke@1: import java.util.Iterator;
duke@1: import java.util.AbstractCollection;
duke@1: import java.util.ListIterator;
duke@1: import java.util.NoSuchElementException;
duke@1: 
duke@1: /** A class for generic linked lists. Links are supposed to be
duke@1:  *  immutable, the only exception being the incremental construction of
duke@1:  *  lists via ListBuffers.  List is the main container class in
duke@1:  *  GJC. Most data structures and algorthms in GJC use lists rather
duke@1:  *  than arrays.
duke@1:  *
duke@1:  *  <p>Lists are always trailed by a sentinel element, whose head and tail
duke@1:  *  are both null.
duke@1:  *
jjg@581:  *  <p><b>This is NOT part of any supported API.
jjg@581:  *  If you write code that depends on this, you do so at your own risk.
duke@1:  *  This code and its internal interfaces are subject to change or
duke@1:  *  deletion without notice.</b>
duke@1:  */
duke@1: public class List<A> extends AbstractCollection<A> implements java.util.List<A> {
duke@1: 
duke@1:     /** The first element of the list, supposed to be immutable.
duke@1:      */
duke@1:     public A head;
duke@1: 
duke@1:     /** The remainder of the list except for its first element, supposed
duke@1:      *  to be immutable.
duke@1:      */
duke@1:     //@Deprecated
duke@1:     public List<A> tail;
duke@1: 
duke@1:     /** Construct a list given its head and tail.
duke@1:      */
duke@1:     List(A head, List<A> tail) {
duke@1:         this.tail = tail;
duke@1:         this.head = head;
duke@1:     }
duke@1: 
duke@1:     /** Construct an empty list.
duke@1:      */
duke@1:     @SuppressWarnings("unchecked")
duke@1:     public static <A> List<A> nil() {
mcimadamore@184:         return (List<A>)EMPTY_LIST;
duke@1:     }
mcimadamore@184: 
vromero@1442:     private static final List<?> EMPTY_LIST = new List<Object>(null,null) {
duke@1:         public List<Object> setTail(List<Object> tail) {
duke@1:             throw new UnsupportedOperationException();
duke@1:         }
duke@1:         public boolean isEmpty() {
duke@1:             return true;
duke@1:         }
duke@1:     };
duke@1: 
mcimadamore@1347:     /** Returns the list obtained from 'l' after removing all elements 'elem'
mcimadamore@1347:      */
mcimadamore@1347:     public static <A> List<A> filter(List<A> l, A elem) {
mcimadamore@1347:         Assert.checkNonNull(elem);
mcimadamore@1347:         List<A> res = List.nil();
mcimadamore@1347:         for (A a : l) {
mcimadamore@1347:             if (a != null && !a.equals(elem)) {
mcimadamore@1347:                 res = res.prepend(a);
mcimadamore@1347:             }
mcimadamore@1347:         }
mcimadamore@1347:         return res.reverse();
mcimadamore@1347:     }
mcimadamore@1347: 
duke@1:     /** Construct a list consisting of given element.
duke@1:      */
duke@1:     public static <A> List<A> of(A x1) {
duke@1:         return new List<A>(x1, List.<A>nil());
duke@1:     }
duke@1: 
duke@1:     /** Construct a list consisting of given elements.
duke@1:      */
duke@1:     public static <A> List<A> of(A x1, A x2) {
duke@1:         return new List<A>(x1, of(x2));
duke@1:     }
duke@1: 
duke@1:     /** Construct a list consisting of given elements.
duke@1:      */
duke@1:     public static <A> List<A> of(A x1, A x2, A x3) {
duke@1:         return new List<A>(x1, of(x2, x3));
duke@1:     }
duke@1: 
duke@1:     /** Construct a list consisting of given elements.
duke@1:      */
mcimadamore@795:     @SuppressWarnings({"varargs", "unchecked"})
duke@1:     public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
duke@1:         return new List<A>(x1, new List<A>(x2, new List<A>(x3, from(rest))));
duke@1:     }
duke@1: 
duke@1:     /**
duke@1:      * Construct a list consisting all elements of given array.
duke@1:      * @param array an array; if {@code null} return an empty list
duke@1:      */
duke@1:     public static <A> List<A> from(A[] array) {
duke@1:         List<A> xs = nil();
duke@1:         if (array != null)
duke@1:             for (int i = array.length - 1; i >= 0; i--)
duke@1:                 xs = new List<A>(array[i], xs);
duke@1:         return xs;
duke@1:     }
duke@1: 
mcimadamore@1347:     public static <A> List<A> from(Iterable<? extends A> coll) {
mcimadamore@1347:         List<A> xs = nil();
mcimadamore@1347:         for (A a : coll) {
mcimadamore@1347:             xs = new List<A>(a, xs);
mcimadamore@1347:         }
mcimadamore@1347:         return xs;
mcimadamore@1347:     }
mcimadamore@1347: 
duke@1:     /** Construct a list consisting of a given number of identical elements.
duke@1:      *  @param len    The number of elements in the list.
duke@1:      *  @param init   The value of each element.
duke@1:      */
duke@1:     @Deprecated
duke@1:     public static <A> List<A> fill(int len, A init) {
duke@1:         List<A> l = nil();
duke@1:         for (int i = 0; i < len; i++) l = new List<A>(init, l);
duke@1:         return l;
duke@1:     }
duke@1: 
duke@1:     /** Does list have no elements?
duke@1:      */
duke@1:     @Override
duke@1:     public boolean isEmpty() {
duke@1:         return tail == null;
duke@1:     }
duke@1: 
duke@1:     /** Does list have elements?
duke@1:      */
duke@1:     //@Deprecated
duke@1:     public boolean nonEmpty() {
duke@1:         return tail != null;
duke@1:     }
duke@1: 
duke@1:     /** Return the number of elements in this list.
duke@1:      */
duke@1:     //@Deprecated
duke@1:     public int length() {
duke@1:         List<A> l = this;
duke@1:         int len = 0;
duke@1:         while (l.tail != null) {
duke@1:             l = l.tail;
duke@1:             len++;
duke@1:         }
duke@1:         return len;
duke@1:     }
duke@1:     @Override
duke@1:     public int size() {
duke@1:         return length();
duke@1:     }
duke@1: 
duke@1:     public List<A> setTail(List<A> tail) {
duke@1:         this.tail = tail;
duke@1:         return tail;
duke@1:     }
duke@1: 
duke@1:     /** Prepend given element to front of list, forming and returning
duke@1:      *  a new list.
duke@1:      */
duke@1:     public List<A> prepend(A x) {
duke@1:         return new List<A>(x, this);
duke@1:     }
duke@1: 
duke@1:     /** Prepend given list of elements to front of list, forming and returning
duke@1:      *  a new list.
duke@1:      */
duke@1:     public List<A> prependList(List<A> xs) {
duke@1:         if (this.isEmpty()) return xs;
duke@1:         if (xs.isEmpty()) return this;
duke@1:         if (xs.tail.isEmpty()) return prepend(xs.head);
duke@1:         // return this.prependList(xs.tail).prepend(xs.head);
duke@1:         List<A> result = this;
duke@1:         List<A> rev = xs.reverse();
jjg@816:         Assert.check(rev != xs);
duke@1:         // since xs.reverse() returned a new list, we can reuse the
duke@1:         // individual List objects, instead of allocating new ones.
duke@1:         while (rev.nonEmpty()) {
duke@1:             List<A> h = rev;
duke@1:             rev = rev.tail;
duke@1:             h.setTail(result);
duke@1:             result = h;
duke@1:         }
duke@1:         return result;
duke@1:     }
duke@1: 
duke@1:     /** Reverse list.
duke@1:      * If the list is empty or a singleton, then the same list is returned.
duke@1:      * Otherwise a new list is formed.
duke@1:      */
duke@1:     public List<A> reverse() {
duke@1:         // if it is empty or a singleton, return itself
duke@1:         if (isEmpty() || tail.isEmpty())
duke@1:             return this;
duke@1: 
duke@1:         List<A> rev = nil();
duke@1:         for (List<A> l = this; l.nonEmpty(); l = l.tail)
duke@1:             rev = new List<A>(l.head, rev);
duke@1:         return rev;
duke@1:     }
duke@1: 
duke@1:     /** Append given element at length, forming and returning
duke@1:      *  a new list.
duke@1:      */
duke@1:     public List<A> append(A x) {
duke@1:         return of(x).prependList(this);
duke@1:     }
duke@1: 
duke@1:     /** Append given list at length, forming and returning
duke@1:      *  a new list.
duke@1:      */
duke@1:     public List<A> appendList(List<A> x) {
duke@1:         return x.prependList(this);
duke@1:     }
duke@1: 
duke@1:     /**
duke@1:      * Append given list buffer at length, forming and returning a new
duke@1:      * list.
duke@1:      */
duke@1:     public List<A> appendList(ListBuffer<A> x) {
duke@1:         return appendList(x.toList());
duke@1:     }
duke@1: 
duke@1:     /** Copy successive elements of this list into given vector until
duke@1:      *  list is exhausted or end of vector is reached.
duke@1:      */
duke@1:     @Override @SuppressWarnings("unchecked")
duke@1:     public <T> T[] toArray(T[] vec) {
duke@1:         int i = 0;
duke@1:         List<A> l = this;
duke@1:         Object[] dest = vec;
duke@1:         while (l.nonEmpty() && i < vec.length) {
duke@1:             dest[i] = l.head;
duke@1:             l = l.tail;
duke@1:             i++;
duke@1:         }
duke@1:         if (l.isEmpty()) {
duke@1:             if (i < vec.length)
duke@1:                 vec[i] = null;
duke@1:             return vec;
duke@1:         }
duke@1: 
duke@1:         vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
duke@1:         return toArray(vec);
duke@1:     }
duke@1: 
duke@1:     public Object[] toArray() {
duke@1:         return toArray(new Object[size()]);
duke@1:     }
duke@1: 
duke@1:     /** Form a string listing all elements with given separator character.
duke@1:      */
duke@1:     public String toString(String sep) {
duke@1:         if (isEmpty()) {
duke@1:             return "";
duke@1:         } else {
jjg@1362:             StringBuilder buf = new StringBuilder();
duke@1:             buf.append(head);
duke@1:             for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
duke@1:                 buf.append(sep);
duke@1:                 buf.append(l.head);
duke@1:             }
duke@1:             return buf.toString();
duke@1:         }
duke@1:     }
duke@1: 
duke@1:     /** Form a string listing all elements with comma as the separator character.
duke@1:      */
duke@1:     @Override
duke@1:     public String toString() {
duke@1:         return toString(",");
duke@1:     }
duke@1: 
duke@1:     /** Compute a hash code, overrides Object
duke@1:      *  @see java.util.List#hashCode
duke@1:      */
duke@1:     @Override
duke@1:     public int hashCode() {
duke@1:         List<A> l = this;
duke@1:         int h = 1;
duke@1:         while (l.tail != null) {
duke@1:             h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
duke@1:             l = l.tail;
duke@1:         }
duke@1:         return h;
duke@1:     }
duke@1: 
duke@1:     /** Is this list the same as other list?
duke@1:      *  @see java.util.List#equals
duke@1:      */
duke@1:     @Override
duke@1:     public boolean equals(Object other) {
duke@1:         if (other instanceof List<?>)
duke@1:             return equals(this, (List<?>)other);
duke@1:         if (other instanceof java.util.List<?>) {
duke@1:             List<A> t = this;
duke@1:             Iterator<?> oIter = ((java.util.List<?>) other).iterator();
duke@1:             while (t.tail != null && oIter.hasNext()) {
duke@1:                 Object o = oIter.next();
duke@1:                 if ( !(t.head == null ? o == null : t.head.equals(o)))
duke@1:                     return false;
duke@1:                 t = t.tail;
duke@1:             }
duke@1:             return (t.isEmpty() && !oIter.hasNext());
duke@1:         }
duke@1:         return false;
duke@1:     }
duke@1: 
duke@1:     /** Are the two lists the same?
duke@1:      */
mcimadamore@184:     public static boolean equals(List<?> xs, List<?> ys) {
duke@1:         while (xs.tail != null && ys.tail != null) {
duke@1:             if (xs.head == null) {
duke@1:                 if (ys.head != null) return false;
duke@1:             } else {
duke@1:                 if (!xs.head.equals(ys.head)) return false;
duke@1:             }
duke@1:             xs = xs.tail;
duke@1:             ys = ys.tail;
duke@1:         }
duke@1:         return xs.tail == null && ys.tail == null;
duke@1:     }
duke@1: 
duke@1:     /** Does the list contain the specified element?
duke@1:      */
duke@1:     @Override
duke@1:     public boolean contains(Object x) {
duke@1:         List<A> l = this;
duke@1:         while (l.tail != null) {
duke@1:             if (x == null) {
duke@1:                 if (l.head == null) return true;
duke@1:             } else {
duke@1:                 if (l.head.equals(x)) return true;
duke@1:             }
duke@1:             l = l.tail;
duke@1:         }
duke@1:         return false;
duke@1:     }
duke@1: 
duke@1:     /** The last element in the list, if any, or null.
duke@1:      */
duke@1:     public A last() {
duke@1:         A last = null;
duke@1:         List<A> t = this;
duke@1:         while (t.tail != null) {
duke@1:             last = t.head;
duke@1:             t = t.tail;
duke@1:         }
duke@1:         return last;
duke@1:     }
duke@1: 
duke@1:     @SuppressWarnings("unchecked")
duke@1:     public static <T> List<T> convert(Class<T> klass, List<?> list) {
duke@1:         if (list == null)
duke@1:             return null;
duke@1:         for (Object o : list)
duke@1:             klass.cast(o);
duke@1:         return (List<T>)list;
duke@1:     }
duke@1: 
vromero@1442:     private static final Iterator<?> EMPTYITERATOR = new Iterator<Object>() {
duke@1:             public boolean hasNext() {
duke@1:                 return false;
duke@1:             }
duke@1:             public Object next() {
duke@1:                 throw new java.util.NoSuchElementException();
duke@1:             }
duke@1:             public void remove() {
duke@1:                 throw new UnsupportedOperationException();
duke@1:             }
duke@1:         };
duke@1: 
duke@1:     @SuppressWarnings("unchecked")
duke@1:     private static <A> Iterator<A> emptyIterator() {
mcimadamore@184:         return (Iterator<A>)EMPTYITERATOR;
duke@1:     }
duke@1: 
duke@1:     @Override
duke@1:     public Iterator<A> iterator() {
duke@1:         if (tail == null)
duke@1:             return emptyIterator();
duke@1:         return new Iterator<A>() {
duke@1:             List<A> elems = List.this;
duke@1:             public boolean hasNext() {
duke@1:                 return elems.tail != null;
duke@1:             }
duke@1:             public A next() {
duke@1:                 if (elems.tail == null)
duke@1:                     throw new NoSuchElementException();
duke@1:                 A result = elems.head;
duke@1:                 elems = elems.tail;
duke@1:                 return result;
duke@1:             }
duke@1:             public void remove() {
duke@1:                 throw new UnsupportedOperationException();
duke@1:             }
duke@1:         };
duke@1:     }
duke@1: 
duke@1:     public A get(int index) {
duke@1:         if (index < 0)
duke@1:             throw new IndexOutOfBoundsException(String.valueOf(index));
duke@1: 
duke@1:         List<A> l = this;
duke@1:         for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
duke@1:             ;
duke@1: 
duke@1:         if (l.isEmpty())
duke@1:             throw new IndexOutOfBoundsException("Index: " + index + ", " +
duke@1:                                                 "Size: " + size());
duke@1:         return l.head;
duke@1:     }
duke@1: 
duke@1:     public boolean addAll(int index, Collection<? extends A> c) {
duke@1:         if (c.isEmpty())
duke@1:             return false;
duke@1:         throw new UnsupportedOperationException();
duke@1:     }
duke@1: 
duke@1:     public A set(int index, A element) {
duke@1:         throw new UnsupportedOperationException();
duke@1:     }
duke@1: 
duke@1:     public void add(int index, A element) {
duke@1:         throw new UnsupportedOperationException();
duke@1:     }
duke@1: 
duke@1:     public A remove(int index) {
duke@1:         throw new UnsupportedOperationException();
duke@1:     }
duke@1: 
duke@1:     public int indexOf(Object o) {
duke@1:         int i = 0;
duke@1:         for (List<A> l = this; l.tail != null; l = l.tail, i++) {
duke@1:             if (l.head == null ? o == null : l.head.equals(o))
duke@1:                 return i;
duke@1:         }
duke@1:         return -1;
duke@1:     }
duke@1: 
duke@1:     public int lastIndexOf(Object o) {
duke@1:         int last = -1;
duke@1:         int i = 0;
duke@1:         for (List<A> l = this; l.tail != null; l = l.tail, i++) {
duke@1:             if (l.head == null ? o == null : l.head.equals(o))
duke@1:                 last = i;
duke@1:         }
duke@1:         return last;
duke@1:     }
duke@1: 
duke@1:     public ListIterator<A> listIterator() {
duke@1:         return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
duke@1:     }
duke@1: 
duke@1:     public ListIterator<A> listIterator(int index) {
duke@1:         return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
duke@1:     }
duke@1: 
duke@1:     public java.util.List<A> subList(int fromIndex, int toIndex) {
duke@1:         if  (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
duke@1:             throw new IllegalArgumentException();
duke@1: 
duke@1:         ArrayList<A> a = new ArrayList<A>(toIndex - fromIndex);
duke@1:         int i = 0;
duke@1:         for (List<A> l = this; l.tail != null; l = l.tail, i++) {
duke@1:             if (i == toIndex)
duke@1:                 break;
duke@1:             if (i >= fromIndex)
duke@1:                 a.add(l.head);
duke@1:         }
duke@1: 
duke@1:         return Collections.unmodifiableList(a);
duke@1:     }
duke@1: }