Thu, 10 Jun 2010 16:08:01 -0700
6944312: Potential rebranding issues in openjdk/langtools repository sources
Reviewed-by: darcy
1 /*
2 * Copyright (c) 1999, 2006, 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 */
26 package com.sun.tools.javac.util;
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;
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> {
53 /** The first element of the list, supposed to be immutable.
54 */
55 public A head;
57 /** The remainder of the list except for its first element, supposed
58 * to be immutable.
59 */
60 //@Deprecated
61 public List<A> tail;
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 }
70 /** Construct an empty list.
71 */
72 @SuppressWarnings("unchecked")
73 public static <A> List<A> nil() {
74 return (List<A>)EMPTY_LIST;
75 }
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 };
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 }
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 }
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 }
104 /** Construct a list consisting of given elements.
105 */
106 @SuppressWarnings("varargs")
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 }
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 }
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 }
134 /** Does list have no elements?
135 */
136 @Override
137 public boolean isEmpty() {
138 return tail == null;
139 }
141 /** Does list have elements?
142 */
143 //@Deprecated
144 public boolean nonEmpty() {
145 return tail != null;
146 }
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 }
165 public List<A> setTail(List<A> tail) {
166 this.tail = tail;
167 return tail;
168 }
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 }
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 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 }
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;
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 }
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 }
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 }
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 }
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 }
255 vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
256 return toArray(vec);
257 }
259 public Object[] toArray() {
260 return toArray(new Object[size()]);
261 }
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 }
279 /** Form a string listing all elements with comma as the separator character.
280 */
281 @Override
282 public String toString() {
283 return toString(",");
284 }
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 }
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 }
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 }
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 }
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 }
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 }
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 };
385 @SuppressWarnings("unchecked")
386 private static <A> Iterator<A> emptyIterator() {
387 return (Iterator<A>)EMPTYITERATOR;
388 }
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 }
412 public A get(int index) {
413 if (index < 0)
414 throw new IndexOutOfBoundsException(String.valueOf(index));
416 List<A> l = this;
417 for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
418 ;
420 if (l.isEmpty())
421 throw new IndexOutOfBoundsException("Index: " + index + ", " +
422 "Size: " + size());
423 return l.head;
424 }
426 public boolean addAll(int index, Collection<? extends A> c) {
427 if (c.isEmpty())
428 return false;
429 throw new UnsupportedOperationException();
430 }
432 public A set(int index, A element) {
433 throw new UnsupportedOperationException();
434 }
436 public void add(int index, A element) {
437 throw new UnsupportedOperationException();
438 }
440 public A remove(int index) {
441 throw new UnsupportedOperationException();
442 }
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 }
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 }
463 public ListIterator<A> listIterator() {
464 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
465 }
467 public ListIterator<A> listIterator(int index) {
468 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
469 }
471 public java.util.List<A> subList(int fromIndex, int toIndex) {
472 if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
473 throw new IllegalArgumentException();
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 }
484 return Collections.unmodifiableList(a);
485 }
486 }