001 /*
002 * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package com.sun.tools.javac.util;
027
028 import java.lang.reflect.Array;
029 import java.util.ArrayList;
030 import java.util.Collection;
031 import java.util.Collections;
032 import java.util.Iterator;
033 import java.util.AbstractCollection;
034 import java.util.ListIterator;
035 import java.util.NoSuchElementException;
036
037 /** A class for generic linked lists. Links are supposed to be
038 * immutable, the only exception being the incremental construction of
039 * lists via ListBuffers. List is the main container class in
040 * GJC. Most data structures and algorthms in GJC use lists rather
041 * than arrays.
042 *
043 * <p>Lists are always trailed by a sentinel element, whose head and tail
044 * are both null.
045 *
046 * <p><b>This is NOT part of any API supported by Sun Microsystems. If
047 * you write code that depends on this, you do so at your own risk.
048 * This code and its internal interfaces are subject to change or
049 * deletion without notice.</b>
050 */
051 public class List<A> extends AbstractCollection<A> implements java.util.List<A> {
052
053 /** The first element of the list, supposed to be immutable.
054 */
055 public A head;
056
057 /** The remainder of the list except for its first element, supposed
058 * to be immutable.
059 */
060 //@Deprecated
061 public List<A> tail;
062
063 /** Construct a list given its head and tail.
064 */
065 List(A head, List<A> tail) {
066 this.tail = tail;
067 this.head = head;
068 }
069
070 /** Construct an empty list.
071 */
072 @SuppressWarnings("unchecked")
073 public static <A> List<A> nil() {
074 return (List<A>)EMPTY_LIST;
075 }
076
077 private static List<?> EMPTY_LIST = new List<Object>(null,null) {
078 public List<Object> setTail(List<Object> tail) {
079 throw new UnsupportedOperationException();
080 }
081 public boolean isEmpty() {
082 return true;
083 }
084 };
085
086 /** Construct a list consisting of given element.
087 */
088 public static <A> List<A> of(A x1) {
089 return new List<A>(x1, List.<A>nil());
090 }
091
092 /** Construct a list consisting of given elements.
093 */
094 public static <A> List<A> of(A x1, A x2) {
095 return new List<A>(x1, of(x2));
096 }
097
098 /** Construct a list consisting of given elements.
099 */
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 public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
107 return new List<A>(x1, new List<A>(x2, new List<A>(x3, from(rest))));
108 }
109
110 /**
111 * Construct a list consisting all elements of given array.
112 * @param array an array; if {@code null} return an empty list
113 */
114 public static <A> List<A> from(A[] array) {
115 List<A> xs = nil();
116 if (array != null)
117 for (int i = array.length - 1; i >= 0; i--)
118 xs = new List<A>(array[i], xs);
119 return xs;
120 }
121
122 /** Construct a list consisting of a given number of identical elements.
123 * @param len The number of elements in the list.
124 * @param init The value of each element.
125 */
126 @Deprecated
127 public static <A> List<A> fill(int len, A init) {
128 List<A> l = nil();
129 for (int i = 0; i < len; i++) l = new List<A>(init, l);
130 return l;
131 }
132
133 /** Does list have no elements?
134 */
135 @Override
136 public boolean isEmpty() {
137 return tail == null;
138 }
139
140 /** Does list have elements?
141 */
142 //@Deprecated
143 public boolean nonEmpty() {
144 return tail != null;
145 }
146
147 /** Return the number of elements in this list.
148 */
149 //@Deprecated
150 public int length() {
151 List<A> l = this;
152 int len = 0;
153 while (l.tail != null) {
154 l = l.tail;
155 len++;
156 }
157 return len;
158 }
159 @Override
160 public int size() {
161 return length();
162 }
163
164 public List<A> setTail(List<A> tail) {
165 this.tail = tail;
166 return tail;
167 }
168
169 /** Prepend given element to front of list, forming and returning
170 * a new list.
171 */
172 public List<A> prepend(A x) {
173 return new List<A>(x, this);
174 }
175
176 /** Prepend given list of elements to front of list, forming and returning
177 * a new list.
178 */
179 public List<A> prependList(List<A> xs) {
180 if (this.isEmpty()) return xs;
181 if (xs.isEmpty()) return this;
182 if (xs.tail.isEmpty()) return prepend(xs.head);
183 // return this.prependList(xs.tail).prepend(xs.head);
184 List<A> result = this;
185 List<A> rev = xs.reverse();
186 assert rev != xs;
187 // since xs.reverse() returned a new list, we can reuse the
188 // individual List objects, instead of allocating new ones.
189 while (rev.nonEmpty()) {
190 List<A> h = rev;
191 rev = rev.tail;
192 h.setTail(result);
193 result = h;
194 }
195 return result;
196 }
197
198 /** Reverse list.
199 * If the list is empty or a singleton, then the same list is returned.
200 * Otherwise a new list is formed.
201 */
202 public List<A> reverse() {
203 // if it is empty or a singleton, return itself
204 if (isEmpty() || tail.isEmpty())
205 return this;
206
207 List<A> rev = nil();
208 for (List<A> l = this; l.nonEmpty(); l = l.tail)
209 rev = new List<A>(l.head, rev);
210 return rev;
211 }
212
213 /** Append given element at length, forming and returning
214 * a new list.
215 */
216 public List<A> append(A x) {
217 return of(x).prependList(this);
218 }
219
220 /** Append given list at length, forming and returning
221 * a new list.
222 */
223 public List<A> appendList(List<A> x) {
224 return x.prependList(this);
225 }
226
227 /**
228 * Append given list buffer at length, forming and returning a new
229 * list.
230 */
231 public List<A> appendList(ListBuffer<A> x) {
232 return appendList(x.toList());
233 }
234
235 /** Copy successive elements of this list into given vector until
236 * list is exhausted or end of vector is reached.
237 */
238 @Override @SuppressWarnings("unchecked")
239 public <T> T[] toArray(T[] vec) {
240 int i = 0;
241 List<A> l = this;
242 Object[] dest = vec;
243 while (l.nonEmpty() && i < vec.length) {
244 dest[i] = l.head;
245 l = l.tail;
246 i++;
247 }
248 if (l.isEmpty()) {
249 if (i < vec.length)
250 vec[i] = null;
251 return vec;
252 }
253
254 vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
255 return toArray(vec);
256 }
257
258 public Object[] toArray() {
259 return toArray(new Object[size()]);
260 }
261
262 /** Form a string listing all elements with given separator character.
263 */
264 public String toString(String sep) {
265 if (isEmpty()) {
266 return "";
267 } else {
268 StringBuffer buf = new StringBuffer();
269 buf.append(head);
270 for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
271 buf.append(sep);
272 buf.append(l.head);
273 }
274 return buf.toString();
275 }
276 }
277
278 /** Form a string listing all elements with comma as the separator character.
279 */
280 @Override
281 public String toString() {
282 return toString(",");
283 }
284
285 /** Compute a hash code, overrides Object
286 * @see java.util.List#hashCode
287 */
288 @Override
289 public int hashCode() {
290 List<A> l = this;
291 int h = 1;
292 while (l.tail != null) {
293 h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
294 l = l.tail;
295 }
296 return h;
297 }
298
299 /** Is this list the same as other list?
300 * @see java.util.List#equals
301 */
302 @Override
303 public boolean equals(Object other) {
304 if (other instanceof List<?>)
305 return equals(this, (List<?>)other);
306 if (other instanceof java.util.List<?>) {
307 List<A> t = this;
308 Iterator<?> oIter = ((java.util.List<?>) other).iterator();
309 while (t.tail != null && oIter.hasNext()) {
310 Object o = oIter.next();
311 if ( !(t.head == null ? o == null : t.head.equals(o)))
312 return false;
313 t = t.tail;
314 }
315 return (t.isEmpty() && !oIter.hasNext());
316 }
317 return false;
318 }
319
320 /** Are the two lists the same?
321 */
322 public static boolean equals(List<?> xs, List<?> ys) {
323 while (xs.tail != null && ys.tail != null) {
324 if (xs.head == null) {
325 if (ys.head != null) return false;
326 } else {
327 if (!xs.head.equals(ys.head)) return false;
328 }
329 xs = xs.tail;
330 ys = ys.tail;
331 }
332 return xs.tail == null && ys.tail == null;
333 }
334
335 /** Does the list contain the specified element?
336 */
337 @Override
338 public boolean contains(Object x) {
339 List<A> l = this;
340 while (l.tail != null) {
341 if (x == null) {
342 if (l.head == null) return true;
343 } else {
344 if (l.head.equals(x)) return true;
345 }
346 l = l.tail;
347 }
348 return false;
349 }
350
351 /** The last element in the list, if any, or null.
352 */
353 public A last() {
354 A last = null;
355 List<A> t = this;
356 while (t.tail != null) {
357 last = t.head;
358 t = t.tail;
359 }
360 return last;
361 }
362
363 @SuppressWarnings("unchecked")
364 public static <T> List<T> convert(Class<T> klass, List<?> list) {
365 if (list == null)
366 return null;
367 for (Object o : list)
368 klass.cast(o);
369 return (List<T>)list;
370 }
371
372 private static Iterator<?> EMPTYITERATOR = new Iterator<Object>() {
373 public boolean hasNext() {
374 return false;
375 }
376 public Object next() {
377 throw new java.util.NoSuchElementException();
378 }
379 public void remove() {
380 throw new UnsupportedOperationException();
381 }
382 };
383
384 @SuppressWarnings("unchecked")
385 private static <A> Iterator<A> emptyIterator() {
386 return (Iterator<A>)EMPTYITERATOR;
387 }
388
389 @Override
390 public Iterator<A> iterator() {
391 if (tail == null)
392 return emptyIterator();
393 return new Iterator<A>() {
394 List<A> elems = List.this;
395 public boolean hasNext() {
396 return elems.tail != null;
397 }
398 public A next() {
399 if (elems.tail == null)
400 throw new NoSuchElementException();
401 A result = elems.head;
402 elems = elems.tail;
403 return result;
404 }
405 public void remove() {
406 throw new UnsupportedOperationException();
407 }
408 };
409 }
410
411 public A get(int index) {
412 if (index < 0)
413 throw new IndexOutOfBoundsException(String.valueOf(index));
414
415 List<A> l = this;
416 for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
417 ;
418
419 if (l.isEmpty())
420 throw new IndexOutOfBoundsException("Index: " + index + ", " +
421 "Size: " + size());
422 return l.head;
423 }
424
425 public boolean addAll(int index, Collection<? extends A> c) {
426 if (c.isEmpty())
427 return false;
428 throw new UnsupportedOperationException();
429 }
430
431 public A set(int index, A element) {
432 throw new UnsupportedOperationException();
433 }
434
435 public void add(int index, A element) {
436 throw new UnsupportedOperationException();
437 }
438
439 public A remove(int index) {
440 throw new UnsupportedOperationException();
441 }
442
443 public int indexOf(Object o) {
444 int i = 0;
445 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
446 if (l.head == null ? o == null : l.head.equals(o))
447 return i;
448 }
449 return -1;
450 }
451
452 public int lastIndexOf(Object o) {
453 int last = -1;
454 int i = 0;
455 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
456 if (l.head == null ? o == null : l.head.equals(o))
457 last = i;
458 }
459 return last;
460 }
461
462 public ListIterator<A> listIterator() {
463 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
464 }
465
466 public ListIterator<A> listIterator(int index) {
467 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
468 }
469
470 public java.util.List<A> subList(int fromIndex, int toIndex) {
471 if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
472 throw new IllegalArgumentException();
473
474 ArrayList<A> a = new ArrayList<A>(toIndex - fromIndex);
475 int i = 0;
476 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
477 if (i == toIndex)
478 break;
479 if (i >= fromIndex)
480 a.add(l.head);
481 }
482
483 return Collections.unmodifiableList(a);
484 }
485 }