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