Mercurial > jdk8-mips64-public > langtools / file comparison

comparison: src/share/classes/com/sun/tools/javac/util/List.java

src/share/classes/com/sun/tools/javac/util/List.java

changeset 1
9a66ca7c79fa
child 184
905e151a185a
equal deleted inserted replaced
-1:000000000000 1:9a66ca7c79fa
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 }

Mercurial Repository: jdk8-mips64-public/langtools

mercurial