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