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: @Version("@(#)List.java 1.43 07/05/05")
052: public class List<A> extends AbstractCollection<A> implements
053: java.util.List<A> {
054:
055: /** The first element of the list, supposed to be immutable.
056: */
057: public A head;
058:
059: /** The remainder of the list except for its first element, supposed
060: * to be immutable.
061: */
062: //@Deprecated
063: public List<A> tail;
064:
065: /** Construct a list given its head and tail.
066: */
067: List(A head, List<A> tail) {
068: this .tail = tail;
069: this .head = head;
070: }
071:
072: /** Construct an empty list.
073: */
074: @SuppressWarnings("unchecked")
075: public static <A> List<A> nil() {
076: return EMPTY_LIST;
077: }
078:
079: private static List EMPTY_LIST = new List<Object>(null, null) {
080: public List<Object> setTail(List<Object> tail) {
081: throw new UnsupportedOperationException();
082: }
083:
084: public boolean isEmpty() {
085: return true;
086: }
087: };
088:
089: /** Construct a list consisting of given element.
090: */
091: public static <A> List<A> of(A x1) {
092: return new List<A>(x1, List.<A> nil());
093: }
094:
095: /** Construct a list consisting of given elements.
096: */
097: public static <A> List<A> of(A x1, A x2) {
098: return new List<A>(x1, of(x2));
099: }
100:
101: /** Construct a list consisting of given elements.
102: */
103: public static <A> List<A> of(A x1, A x2, A x3) {
104: return new List<A>(x1, of(x2, x3));
105: }
106:
107: /** Construct a list consisting of given elements.
108: */
109: public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
110: return new List<A>(x1, new List<A>(x2, new List<A>(x3,
111: from(rest))));
112: }
113:
114: /**
115: * Construct a list consisting all elements of given array.
116: * @param array an array; if {@code null} return an empty list
117: */
118: public static <A> List<A> from(A[] array) {
119: List<A> xs = nil();
120: if (array != null)
121: for (int i = array.length - 1; i >= 0; i--)
122: xs = new List<A>(array[i], xs);
123: return xs;
124: }
125:
126: /** Construct a list consisting of a given number of identical elements.
127: * @param len The number of elements in the list.
128: * @param init The value of each element.
129: */
130: @Deprecated
131: public static <A> List<A> fill(int len, A init) {
132: List<A> l = nil();
133: for (int i = 0; i < len; i++)
134: l = new List<A>(init, l);
135: return l;
136: }
137:
138: /** Does list have no elements?
139: */
140: @Override
141: public boolean isEmpty() {
142: return tail == null;
143: }
144:
145: /** Does list have elements?
146: */
147: //@Deprecated
148: public boolean nonEmpty() {
149: return tail != null;
150: }
151:
152: /** Return the number of elements in this list.
153: */
154: //@Deprecated
155: public int length() {
156: List<A> l = this ;
157: int len = 0;
158: while (l.tail != null) {
159: l = l.tail;
160: len++;
161: }
162: return len;
163: }
164:
165: @Override
166: public int size() {
167: return length();
168: }
169:
170: public List<A> setTail(List<A> tail) {
171: this .tail = tail;
172: return tail;
173: }
174:
175: /** Prepend given element to front of list, forming and returning
176: * a new list.
177: */
178: public List<A> prepend(A x) {
179: return new List<A>(x, this );
180: }
181:
182: /** Prepend given list of elements to front of list, forming and returning
183: * a new list.
184: */
185: public List<A> prependList(List<A> xs) {
186: if (this .isEmpty())
187: return xs;
188: if (xs.isEmpty())
189: return this ;
190: if (xs.tail.isEmpty())
191: return prepend(xs.head);
192: // return this.prependList(xs.tail).prepend(xs.head);
193: List<A> result = this ;
194: List<A> rev = xs.reverse();
195: assert rev != xs;
196: // since xs.reverse() returned a new list, we can reuse the
197: // individual List objects, instead of allocating new ones.
198: while (rev.nonEmpty()) {
199: List<A> h = rev;
200: rev = rev.tail;
201: h.setTail(result);
202: result = h;
203: }
204: return result;
205: }
206:
207: /** Reverse list.
208: * If the list is empty or a singleton, then the same list is returned.
209: * Otherwise a new list is formed.
210: */
211: public List<A> reverse() {
212: // if it is empty or a singleton, return itself
213: if (isEmpty() || tail.isEmpty())
214: return this ;
215:
216: List<A> rev = nil();
217: for (List<A> l = this ; l.nonEmpty(); l = l.tail)
218: rev = new List<A>(l.head, rev);
219: return rev;
220: }
221:
222: /** Append given element at length, forming and returning
223: * a new list.
224: */
225: public List<A> append(A x) {
226: return of(x).prependList(this );
227: }
228:
229: /** Append given list at length, forming and returning
230: * a new list.
231: */
232: public List<A> appendList(List<A> x) {
233: return x.prependList(this );
234: }
235:
236: /**
237: * Append given list buffer at length, forming and returning a new
238: * list.
239: */
240: public List<A> appendList(ListBuffer<A> x) {
241: return appendList(x.toList());
242: }
243:
244: /** Copy successive elements of this list into given vector until
245: * list is exhausted or end of vector is reached.
246: */
247: @Override
248: @SuppressWarnings("unchecked")
249: public <T> T[] toArray(T[] vec) {
250: int i = 0;
251: List<A> l = this ;
252: Object[] dest = vec;
253: while (l.nonEmpty() && i < vec.length) {
254: dest[i] = l.head;
255: l = l.tail;
256: i++;
257: }
258: if (l.isEmpty()) {
259: if (i < vec.length)
260: vec[i] = null;
261: return vec;
262: }
263:
264: vec = (T[]) Array.newInstance(
265: vec.getClass().getComponentType(), size());
266: return toArray(vec);
267: }
268:
269: public Object[] toArray() {
270: return toArray(new Object[size()]);
271: }
272:
273: /** Form a string listing all elements with given separator character.
274: */
275: public String toString(String sep) {
276: if (isEmpty()) {
277: return "";
278: } else {
279: StringBuffer buf = new StringBuffer();
280: buf.append(head);
281: for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
282: buf.append(sep);
283: buf.append(l.head);
284: }
285: return buf.toString();
286: }
287: }
288:
289: /** Form a string listing all elements with comma as the separator character.
290: */
291: @Override
292: public String toString() {
293: return toString(",");
294: }
295:
296: /** Compute a hash code, overrides Object
297: * @see java.util.List#hashCode
298: */
299: @Override
300: public int hashCode() {
301: List<A> l = this ;
302: int h = 1;
303: while (l.tail != null) {
304: h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
305: l = l.tail;
306: }
307: return h;
308: }
309:
310: /** Is this list the same as other list?
311: * @see java.util.List#equals
312: */
313: @Override
314: public boolean equals(Object other) {
315: if (other instanceof List<?>)
316: return equals(this , (List<?>) other);
317: if (other instanceof java.util.List<?>) {
318: List<A> t = this ;
319: Iterator<?> oIter = ((java.util.List<?>) other).iterator();
320: while (t.tail != null && oIter.hasNext()) {
321: Object o = oIter.next();
322: if (!(t.head == null ? o == null : t.head.equals(o)))
323: return false;
324: t = t.tail;
325: }
326: return (t.isEmpty() && !oIter.hasNext());
327: }
328: return false;
329: }
330:
331: /** Are the two lists the same?
332: */
333: public static boolean equals(List xs, List ys) {
334: while (xs.tail != null && ys.tail != null) {
335: if (xs.head == null) {
336: if (ys.head != null)
337: return false;
338: } else {
339: if (!xs.head.equals(ys.head))
340: return false;
341: }
342: xs = xs.tail;
343: ys = ys.tail;
344: }
345: return xs.tail == null && ys.tail == null;
346: }
347:
348: /** Does the list contain the specified element?
349: */
350: @Override
351: public boolean contains(Object x) {
352: List<A> l = this ;
353: while (l.tail != null) {
354: if (x == null) {
355: if (l.head == null)
356: return true;
357: } else {
358: if (l.head.equals(x))
359: return true;
360: }
361: l = l.tail;
362: }
363: return false;
364: }
365:
366: /** The last element in the list, if any, or null.
367: */
368: public A last() {
369: A last = null;
370: List<A> t = this ;
371: while (t.tail != null) {
372: last = t.head;
373: t = t.tail;
374: }
375: return last;
376: }
377:
378: @SuppressWarnings("unchecked")
379: public static <T> List<T> convert(Class<T> klass, List<?> list) {
380: if (list == null)
381: return null;
382: for (Object o : list)
383: klass.cast(o);
384: return (List<T>) list;
385: }
386:
387: private static Iterator EMPTYITERATOR = new Iterator() {
388: public boolean hasNext() {
389: return false;
390: }
391:
392: public Object next() {
393: throw new java.util.NoSuchElementException();
394: }
395:
396: public void remove() {
397: throw new UnsupportedOperationException();
398: }
399: };
400:
401: @SuppressWarnings("unchecked")
402: private static <A> Iterator<A> emptyIterator() {
403: return EMPTYITERATOR;
404: }
405:
406: @Override
407: public Iterator<A> iterator() {
408: if (tail == null)
409: return emptyIterator();
410: return new Iterator<A>() {
411: List<A> elems = List.this ;
412:
413: public boolean hasNext() {
414: return elems.tail != null;
415: }
416:
417: public A next() {
418: if (elems.tail == null)
419: throw new NoSuchElementException();
420: A result = elems.head;
421: elems = elems.tail;
422: return result;
423: }
424:
425: public void remove() {
426: throw new UnsupportedOperationException();
427: }
428: };
429: }
430:
431: public A get(int index) {
432: if (index < 0)
433: throw new IndexOutOfBoundsException(String.valueOf(index));
434:
435: List<A> l = this ;
436: for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
437: ;
438:
439: if (l.isEmpty())
440: throw new IndexOutOfBoundsException("Index: " + index
441: + ", " + "Size: " + size());
442: return l.head;
443: }
444:
445: public boolean addAll(int index, Collection<? extends A> c) {
446: if (c.isEmpty())
447: return false;
448: throw new UnsupportedOperationException();
449: }
450:
451: public A set(int index, A element) {
452: throw new UnsupportedOperationException();
453: }
454:
455: public void add(int index, A element) {
456: throw new UnsupportedOperationException();
457: }
458:
459: public A remove(int index) {
460: throw new UnsupportedOperationException();
461: }
462:
463: public int indexOf(Object o) {
464: int i = 0;
465: for (List<A> l = this ; l.tail != null; l = l.tail, i++) {
466: if (l.head == null ? o == null : l.head.equals(o))
467: return i;
468: }
469: return -1;
470: }
471:
472: public int lastIndexOf(Object o) {
473: int last = -1;
474: int i = 0;
475: for (List<A> l = this ; l.tail != null; l = l.tail, i++) {
476: if (l.head == null ? o == null : l.head.equals(o))
477: last = i;
478: }
479: return last;
480: }
481:
482: public ListIterator<A> listIterator() {
483: return Collections.unmodifiableList(new ArrayList<A>(this ))
484: .listIterator();
485: }
486:
487: public ListIterator<A> listIterator(int index) {
488: return Collections.unmodifiableList(new ArrayList<A>(this ))
489: .listIterator(index);
490: }
491:
492: public java.util.List<A> subList(int fromIndex, int toIndex) {
493: if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
494: throw new IllegalArgumentException();
495:
496: ArrayList<A> a = new ArrayList<A>(toIndex - fromIndex);
497: int i = 0;
498: for (List<A> l = this; l.tail != null; l = l.tail, i++) {
499: if (i == toIndex)
500: break;
501: if (i >= fromIndex)
502: a.add(l.head);
503: }
504:
505: return Collections.unmodifiableList(a);
506: }
507: }
|