Home » openjdk-7 » com.sun.tools » javac » util » [javadoc | source]

    1   /*
    2    * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package com.sun.tools.javac.util;
   27   
   28   import java.lang.reflect.Array;
   29   import java.util.ArrayList;
   30   import java.util.Collection;
   31   import java.util.Collections;
   32   import java.util.Iterator;
   33   import java.util.AbstractCollection;
   34   import java.util.ListIterator;
   35   import java.util.NoSuchElementException;
   36   
   37   /** A class for generic linked lists. Links are supposed to be
   38    *  immutable, the only exception being the incremental construction of
   39    *  lists via ListBuffers.  List is the main container class in
   40    *  GJC. Most data structures and algorthms in GJC use lists rather
   41    *  than arrays.
   42    *
   43    *  <p>Lists are always trailed by a sentinel element, whose head and tail
   44    *  are both null.
   45    *
   46    *  <p><b>This is NOT part of any supported API.
   47    *  If you write code that depends on this, you do so at your own risk.
   48    *  This code and its internal interfaces are subject to change or
   49    *  deletion without notice.</b>
   50    */
   51   public class List<A> extends AbstractCollection<A> implements java.util.List<A> {
   52   
   53       /** The first element of the list, supposed to be immutable.
   54        */
   55       public A head;
   56   
   57       /** The remainder of the list except for its first element, supposed
   58        *  to be immutable.
   59        */
   60       //@Deprecated
   61       public List<A> tail;
   62   
   63       /** Construct a list given its head and tail.
   64        */
   65       List(A head, List<A> tail) {
   66           this.tail = tail;
   67           this.head = head;
   68       }
   69   
   70       /** Construct an empty list.
   71        */
   72       @SuppressWarnings("unchecked")
   73       public static <A> List<A> nil() {
   74           return (List<A>)EMPTY_LIST;
   75       }
   76   
   77       private static List<?> EMPTY_LIST = new List<Object>(null,null) {
   78           public List<Object> setTail(List<Object> tail) {
   79               throw new UnsupportedOperationException();
   80           }
   81           public boolean isEmpty() {
   82               return true;
   83           }
   84       };
   85   
   86       /** Construct a list consisting of given element.
   87        */
   88       public static <A> List<A> of(A x1) {
   89           return new List<A>(x1, List.<A>nil());
   90       }
   91   
   92       /** Construct a list consisting of given elements.
   93        */
   94       public static <A> List<A> of(A x1, A x2) {
   95           return new List<A>(x1, of(x2));
   96       }
   97   
   98       /** Construct a list consisting of given elements.
   99        */
  100       public static <A> List<A> of(A x1, A x2, A x3) {
  101           return new List<A>(x1, of(x2, x3));
  102       }
  103   
  104       /** Construct a list consisting of given elements.
  105        */
  106       @SuppressWarnings({"varargs", "unchecked"})
  107       public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
  108           return new List<A>(x1, new List<A>(x2, new List<A>(x3, from(rest))));
  109       }
  110   
  111       /**
  112        * Construct a list consisting all elements of given array.
  113        * @param array an array; if {@code null} return an empty list
  114        */
  115       public static <A> List<A> from(A[] array) {
  116           List<A> xs = nil();
  117           if (array != null)
  118               for (int i = array.length - 1; i >= 0; i--)
  119                   xs = new List<A>(array[i], xs);
  120           return xs;
  121       }
  122   
  123       /** Construct a list consisting of a given number of identical elements.
  124        *  @param len    The number of elements in the list.
  125        *  @param init   The value of each element.
  126        */
  127       @Deprecated
  128       public static <A> List<A> fill(int len, A init) {
  129           List<A> l = nil();
  130           for (int i = 0; i < len; i++) l = new List<A>(init, l);
  131           return l;
  132       }
  133   
  134       /** Does list have no elements?
  135        */
  136       @Override
  137       public boolean isEmpty() {
  138           return tail == null;
  139       }
  140   
  141       /** Does list have elements?
  142        */
  143       //@Deprecated
  144       public boolean nonEmpty() {
  145           return tail != null;
  146       }
  147   
  148       /** Return the number of elements in this list.
  149        */
  150       //@Deprecated
  151       public int length() {
  152           List<A> l = this;
  153           int len = 0;
  154           while (l.tail != null) {
  155               l = l.tail;
  156               len++;
  157           }
  158           return len;
  159       }
  160       @Override
  161       public int size() {
  162           return length();
  163       }
  164   
  165       public List<A> setTail(List<A> tail) {
  166           this.tail = tail;
  167           return tail;
  168       }
  169   
  170       /** Prepend given element to front of list, forming and returning
  171        *  a new list.
  172        */
  173       public List<A> prepend(A x) {
  174           return new List<A>(x, this);
  175       }
  176   
  177       /** Prepend given list of elements to front of list, forming and returning
  178        *  a new list.
  179        */
  180       public List<A> prependList(List<A> xs) {
  181           if (this.isEmpty()) return xs;
  182           if (xs.isEmpty()) return this;
  183           if (xs.tail.isEmpty()) return prepend(xs.head);
  184           // return this.prependList(xs.tail).prepend(xs.head);
  185           List<A> result = this;
  186           List<A> rev = xs.reverse();
  187           Assert.check(rev != xs);
  188           // since xs.reverse() returned a new list, we can reuse the
  189           // individual List objects, instead of allocating new ones.
  190           while (rev.nonEmpty()) {
  191               List<A> h = rev;
  192               rev = rev.tail;
  193               h.setTail(result);
  194               result = h;
  195           }
  196           return result;
  197       }
  198   
  199       /** Reverse list.
  200        * If the list is empty or a singleton, then the same list is returned.
  201        * Otherwise a new list is formed.
  202        */
  203       public List<A> reverse() {
  204           // if it is empty or a singleton, return itself
  205           if (isEmpty() || tail.isEmpty())
  206               return this;
  207   
  208           List<A> rev = nil();
  209           for (List<A> l = this; l.nonEmpty(); l = l.tail)
  210               rev = new List<A>(l.head, rev);
  211           return rev;
  212       }
  213   
  214       /** Append given element at length, forming and returning
  215        *  a new list.
  216        */
  217       public List<A> append(A x) {
  218           return of(x).prependList(this);
  219       }
  220   
  221       /** Append given list at length, forming and returning
  222        *  a new list.
  223        */
  224       public List<A> appendList(List<A> x) {
  225           return x.prependList(this);
  226       }
  227   
  228       /**
  229        * Append given list buffer at length, forming and returning a new
  230        * list.
  231        */
  232       public List<A> appendList(ListBuffer<A> x) {
  233           return appendList(x.toList());
  234       }
  235   
  236       /** Copy successive elements of this list into given vector until
  237        *  list is exhausted or end of vector is reached.
  238        */
  239       @Override @SuppressWarnings("unchecked")
  240       public <T> T[] toArray(T[] vec) {
  241           int i = 0;
  242           List<A> l = this;
  243           Object[] dest = vec;
  244           while (l.nonEmpty() && i < vec.length) {
  245               dest[i] = l.head;
  246               l = l.tail;
  247               i++;
  248           }
  249           if (l.isEmpty()) {
  250               if (i < vec.length)
  251                   vec[i] = null;
  252               return vec;
  253           }
  254   
  255           vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
  256           return toArray(vec);
  257       }
  258   
  259       public Object[] toArray() {
  260           return toArray(new Object[size()]);
  261       }
  262   
  263       /** Form a string listing all elements with given separator character.
  264        */
  265       public String toString(String sep) {
  266           if (isEmpty()) {
  267               return "";
  268           } else {
  269               StringBuffer buf = new StringBuffer();
  270               buf.append(head);
  271               for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
  272                   buf.append(sep);
  273                   buf.append(l.head);
  274               }
  275               return buf.toString();
  276           }
  277       }
  278   
  279       /** Form a string listing all elements with comma as the separator character.
  280        */
  281       @Override
  282       public String toString() {
  283           return toString(",");
  284       }
  285   
  286       /** Compute a hash code, overrides Object
  287        *  @see java.util.List#hashCode
  288        */
  289       @Override
  290       public int hashCode() {
  291           List<A> l = this;
  292           int h = 1;
  293           while (l.tail != null) {
  294               h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
  295               l = l.tail;
  296           }
  297           return h;
  298       }
  299   
  300       /** Is this list the same as other list?
  301        *  @see java.util.List#equals
  302        */
  303       @Override
  304       public boolean equals(Object other) {
  305           if (other instanceof List<?>)
  306               return equals(this, (List<?>)other);
  307           if (other instanceof java.util.List<?>) {
  308               List<A> t = this;
  309               Iterator<?> oIter = ((java.util.List<?>) other).iterator();
  310               while (t.tail != null && oIter.hasNext()) {
  311                   Object o = oIter.next();
  312                   if ( !(t.head == null ? o == null : t.head.equals(o)))
  313                       return false;
  314                   t = t.tail;
  315               }
  316               return (t.isEmpty() && !oIter.hasNext());
  317           }
  318           return false;
  319       }
  320   
  321       /** Are the two lists the same?
  322        */
  323       public static boolean equals(List<?> xs, List<?> ys) {
  324           while (xs.tail != null && ys.tail != null) {
  325               if (xs.head == null) {
  326                   if (ys.head != null) return false;
  327               } else {
  328                   if (!xs.head.equals(ys.head)) return false;
  329               }
  330               xs = xs.tail;
  331               ys = ys.tail;
  332           }
  333           return xs.tail == null && ys.tail == null;
  334       }
  335   
  336       /** Does the list contain the specified element?
  337        */
  338       @Override
  339       public boolean contains(Object x) {
  340           List<A> l = this;
  341           while (l.tail != null) {
  342               if (x == null) {
  343                   if (l.head == null) return true;
  344               } else {
  345                   if (l.head.equals(x)) return true;
  346               }
  347               l = l.tail;
  348           }
  349           return false;
  350       }
  351   
  352       /** The last element in the list, if any, or null.
  353        */
  354       public A last() {
  355           A last = null;
  356           List<A> t = this;
  357           while (t.tail != null) {
  358               last = t.head;
  359               t = t.tail;
  360           }
  361           return last;
  362       }
  363   
  364       @SuppressWarnings("unchecked")
  365       public static <T> List<T> convert(Class<T> klass, List<?> list) {
  366           if (list == null)
  367               return null;
  368           for (Object o : list)
  369               klass.cast(o);
  370           return (List<T>)list;
  371       }
  372   
  373       private static Iterator<?> EMPTYITERATOR = new Iterator<Object>() {
  374               public boolean hasNext() {
  375                   return false;
  376               }
  377               public Object next() {
  378                   throw new java.util.NoSuchElementException();
  379               }
  380               public void remove() {
  381                   throw new UnsupportedOperationException();
  382               }
  383           };
  384   
  385       @SuppressWarnings("unchecked")
  386       private static <A> Iterator<A> emptyIterator() {
  387           return (Iterator<A>)EMPTYITERATOR;
  388       }
  389   
  390       @Override
  391       public Iterator<A> iterator() {
  392           if (tail == null)
  393               return emptyIterator();
  394           return new Iterator<A>() {
  395               List<A> elems = List.this;
  396               public boolean hasNext() {
  397                   return elems.tail != null;
  398               }
  399               public A next() {
  400                   if (elems.tail == null)
  401                       throw new NoSuchElementException();
  402                   A result = elems.head;
  403                   elems = elems.tail;
  404                   return result;
  405               }
  406               public void remove() {
  407                   throw new UnsupportedOperationException();
  408               }
  409           };
  410       }
  411   
  412       public A get(int index) {
  413           if (index < 0)
  414               throw new IndexOutOfBoundsException(String.valueOf(index));
  415   
  416           List<A> l = this;
  417           for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
  418               ;
  419   
  420           if (l.isEmpty())
  421               throw new IndexOutOfBoundsException("Index: " + index + ", " +
  422                                                   "Size: " + size());
  423           return l.head;
  424       }
  425   
  426       public boolean addAll(int index, Collection<? extends A> c) {
  427           if (c.isEmpty())
  428               return false;
  429           throw new UnsupportedOperationException();
  430       }
  431   
  432       public A set(int index, A element) {
  433           throw new UnsupportedOperationException();
  434       }
  435   
  436       public void add(int index, A element) {
  437           throw new UnsupportedOperationException();
  438       }
  439   
  440       public A remove(int index) {
  441           throw new UnsupportedOperationException();
  442       }
  443   
  444       public int indexOf(Object o) {
  445           int i = 0;
  446           for (List<A> l = this; l.tail != null; l = l.tail, i++) {
  447               if (l.head == null ? o == null : l.head.equals(o))
  448                   return i;
  449           }
  450           return -1;
  451       }
  452   
  453       public int lastIndexOf(Object o) {
  454           int last = -1;
  455           int i = 0;
  456           for (List<A> l = this; l.tail != null; l = l.tail, i++) {
  457               if (l.head == null ? o == null : l.head.equals(o))
  458                   last = i;
  459           }
  460           return last;
  461       }
  462   
  463       public ListIterator<A> listIterator() {
  464           return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
  465       }
  466   
  467       public ListIterator<A> listIterator(int index) {
  468           return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
  469       }
  470   
  471       public java.util.List<A> subList(int fromIndex, int toIndex) {
  472           if  (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
  473               throw new IllegalArgumentException();
  474   
  475           ArrayList<A> a = new ArrayList<A>(toIndex - fromIndex);
  476           int i = 0;
  477           for (List<A> l = this; l.tail != null; l = l.tail, i++) {
  478               if (i == toIndex)
  479                   break;
  480               if (i >= fromIndex)
  481                   a.add(l.head);
  482           }
  483   
  484           return Collections.unmodifiableList(a);
  485       }
  486   }

Home » openjdk-7 » com.sun.tools » javac » util » [javadoc | source]