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