001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.io.Serializable; 023 import java.lang.reflect.Array; 024 import java.util.ArrayList; 025 import java.util.Collection; 026 import java.util.ConcurrentModificationException; 027 import java.util.Iterator; 028 import java.util.List; 029 import java.util.ListIterator; 030 import java.util.NoSuchElementException; 031 import java.lang.ref.WeakReference; 032 033 /** 034 * A doubly-linked list implementation of the {@link List} interface, 035 * supporting a {@link ListIterator} that allows concurrent modifications 036 * to the underlying list. 037 * <p> 038 * Implements all of the optional {@link List} operations, the 039 * stack/queue/dequeue operations available in {@link java.util.LinkedList} 040 * and supports a {@link ListIterator} that allows concurrent modifications 041 * to the underlying list (see {@link #cursor}). 042 * <p> 043 * <b>Note that this implementation is not synchronized.</b> 044 * 045 * @deprecated Use new version in list subpackage, which has been rewritten 046 * and now returns the cursor from the listIterator method. Will be removed in v4.0 047 * @see java.util.LinkedList 048 * @since Commons Collections 1.0 049 * @version $Revision: 647116 $ $Date: 2008-04-11 12:23:08 +0100 (Fri, 11 Apr 2008) $ 050 * 051 * @author Rodney Waldhoff 052 * @author Janek Bogucki 053 * @author Simon Kitching 054 */ 055 public class CursorableLinkedList implements List, Serializable { 056 /** Ensure serialization compatibility */ 057 private static final long serialVersionUID = 8836393098519411393L; 058 059 //--- public methods --------------------------------------------- 060 061 /** 062 * Appends the specified element to the end of this list. 063 * 064 * @param o element to be appended to this list. 065 * @return <tt>true</tt> 066 */ 067 public boolean add(Object o) { 068 insertListable(_head.prev(),null,o); 069 return true; 070 } 071 072 /** 073 * Inserts the specified element at the specified position in this list. 074 * Shifts the element currently at that position (if any) and any subsequent 075 * elements to the right (adds one to their indices). 076 * 077 * @param index index at which the specified element is to be inserted. 078 * @param element element to be inserted. 079 * 080 * @throws ClassCastException if the class of the specified element 081 * prevents it from being added to this list. 082 * @throws IllegalArgumentException if some aspect of the specified 083 * element prevents it from being added to this list. 084 * @throws IndexOutOfBoundsException if the index is out of range 085 * (index < 0 || index > size()). 086 */ 087 public void add(int index, Object element) { 088 if(index == _size) { 089 add(element); 090 } else { 091 if(index < 0 || index > _size) { 092 throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size); 093 } 094 Listable succ = (isEmpty() ? null : getListableAt(index)); 095 Listable pred = (null == succ ? null : succ.prev()); 096 insertListable(pred,succ,element); 097 } 098 } 099 100 /** 101 * Appends all of the elements in the specified collection to the end of 102 * this list, in the order that they are returned by the specified 103 * {@link Collection}'s {@link Iterator}. The behavior of this operation is 104 * unspecified if the specified collection is modified while 105 * the operation is in progress. (Note that this will occur if the 106 * specified collection is this list, and it's nonempty.) 107 * 108 * @param c collection whose elements are to be added to this list. 109 * @return <tt>true</tt> if this list changed as a result of the call. 110 * 111 * @throws ClassCastException if the class of an element in the specified 112 * collection prevents it from being added to this list. 113 * @throws IllegalArgumentException if some aspect of an element in the 114 * specified collection prevents it from being added to this 115 * list. 116 */ 117 public boolean addAll(Collection c) { 118 if(c.isEmpty()) { 119 return false; 120 } 121 Iterator it = c.iterator(); 122 while(it.hasNext()) { 123 insertListable(_head.prev(),null,it.next()); 124 } 125 return true; 126 } 127 128 /** 129 * Inserts all of the elements in the specified collection into this 130 * list at the specified position. Shifts the element currently at 131 * that position (if any) and any subsequent elements to the right 132 * (increases their indices). The new elements will appear in this 133 * list in the order that they are returned by the specified 134 * {@link Collection}'s {@link Iterator}. The behavior of this operation is 135 * unspecified if the specified collection is modified while the 136 * operation is in progress. (Note that this will occur if the specified 137 * collection is this list, and it's nonempty.) 138 * 139 * @param index index at which to insert first element from the specified 140 * collection. 141 * @param c elements to be inserted into this list. 142 * @return <tt>true</tt> if this list changed as a result of the call. 143 * 144 * @throws ClassCastException if the class of one of elements of the 145 * specified collection prevents it from being added to this 146 * list. 147 * @throws IllegalArgumentException if some aspect of one of elements of 148 * the specified collection prevents it from being added to 149 * this list. 150 * @throws IndexOutOfBoundsException if the index is out of range (index 151 * < 0 || index > size()). 152 */ 153 public boolean addAll(int index, Collection c) { 154 if(c.isEmpty()) { 155 return false; 156 } else if(_size == index || _size == 0) { 157 return addAll(c); 158 } else { 159 Listable succ = getListableAt(index); 160 Listable pred = (null == succ) ? null : succ.prev(); 161 Iterator it = c.iterator(); 162 while(it.hasNext()) { 163 pred = insertListable(pred,succ,it.next()); 164 } 165 return true; 166 } 167 } 168 169 /** 170 * Inserts the specified element at the beginning of this list. 171 * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}). 172 * 173 * @param o element to be prepended to this list. 174 * @return <tt>true</tt> 175 */ 176 public boolean addFirst(Object o) { 177 insertListable(null,_head.next(),o); 178 return true; 179 } 180 181 /** 182 * Inserts the specified element at the end of this list. 183 * (Equivalent to {@link #add(java.lang.Object)}). 184 * 185 * @param o element to be appended to this list. 186 * @return <tt>true</tt> 187 */ 188 public boolean addLast(Object o) { 189 insertListable(_head.prev(),null,o); 190 return true; 191 } 192 193 /** 194 * Removes all of the elements from this list. This 195 * list will be empty after this call returns (unless 196 * it throws an exception). 197 */ 198 public void clear() { 199 /* 200 // this is the quick way, but would force us 201 // to break all the cursors 202 _modCount++; 203 _head.setNext(null); 204 _head.setPrev(null); 205 _size = 0; 206 */ 207 Iterator it = iterator(); 208 while(it.hasNext()) { 209 it.next(); 210 it.remove(); 211 } 212 } 213 214 /** 215 * Returns <tt>true</tt> if this list contains the specified element. 216 * More formally, returns <tt>true</tt> if and only if this list contains 217 * at least one element <tt>e</tt> such that 218 * <tt>(o==null ? e==null : o.equals(e))</tt>. 219 * 220 * @param o element whose presence in this list is to be tested. 221 * @return <tt>true</tt> if this list contains the specified element. 222 */ 223 public boolean contains(Object o) { 224 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 225 if((null == o && null == elt.value()) || 226 (o != null && o.equals(elt.value()))) { 227 return true; 228 } 229 } 230 return false; 231 } 232 233 /** 234 * Returns <tt>true</tt> if this list contains all of the elements of the 235 * specified collection. 236 * 237 * @param c collection to be checked for containment in this list. 238 * @return <tt>true</tt> if this list contains all of the elements of the 239 * specified collection. 240 */ 241 public boolean containsAll(Collection c) { 242 Iterator it = c.iterator(); 243 while(it.hasNext()) { 244 if(!this.contains(it.next())) { 245 return false; 246 } 247 } 248 return true; 249 } 250 251 /** 252 * Returns a {@link ListIterator} for iterating through the 253 * elements of this list. Unlike {@link #iterator}, a cursor 254 * is not bothered by concurrent modifications to the 255 * underlying list. 256 * <p> 257 * Specifically, when elements are added to the list before or 258 * after the cursor, the cursor simply picks them up automatically. 259 * When the "current" (i.e., last returned by {@link ListIterator#next} 260 * or {@link ListIterator#previous}) element of the list is removed, 261 * the cursor automatically adjusts to the change (invalidating the 262 * last returned value--i.e., it cannot be removed). 263 * <p> 264 * Note that the returned {@link ListIterator} does not support the 265 * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex} 266 * methods (they throw {@link UnsupportedOperationException} when invoked. 267 * <p> 268 * Historical Note: In previous versions of this class, the object 269 * returned from this method was required to be explicitly closed. This 270 * is no longer necessary. 271 * 272 * @see #cursor(int) 273 * @see #listIterator 274 * @see CursorableLinkedList.Cursor 275 */ 276 public CursorableLinkedList.Cursor cursor() { 277 return new Cursor(0); 278 } 279 280 /** 281 * Returns a {@link ListIterator} for iterating through the 282 * elements of this list, initialized such that 283 * {@link ListIterator#next} will return the element at 284 * the specified index (if any) and {@link ListIterator#previous} 285 * will return the element immediately preceding it (if any). 286 * Unlike {@link #iterator}, a cursor 287 * is not bothered by concurrent modifications to the 288 * underlying list. 289 * 290 * @see #cursor 291 * @see #listIterator(int) 292 * @see CursorableLinkedList.Cursor 293 * @throws IndexOutOfBoundsException if the index is out of range (index 294 * < 0 || index > size()). 295 */ 296 public CursorableLinkedList.Cursor cursor(int i) { 297 return new Cursor(i); 298 } 299 300 /** 301 * Compares the specified object with this list for equality. Returns 302 * <tt>true</tt> if and only if the specified object is also a list, both 303 * lists have the same size, and all corresponding pairs of elements in 304 * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and 305 * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : 306 * e1.equals(e2))</tt>.) In other words, two lists are defined to be 307 * equal if they contain the same elements in the same order. This 308 * definition ensures that the equals method works properly across 309 * different implementations of the <tt>List</tt> interface. 310 * 311 * @param o the object to be compared for equality with this list. 312 * @return <tt>true</tt> if the specified object is equal to this list. 313 */ 314 public boolean equals(Object o) { 315 if(o == this) { 316 return true; 317 } else if(!(o instanceof List)) { 318 return false; 319 } 320 Iterator it = ((List)o).listIterator(); 321 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 322 if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) { 323 return false; 324 } 325 } 326 return !it.hasNext(); 327 } 328 329 /** 330 * Returns the element at the specified position in this list. 331 * 332 * @param index index of element to return. 333 * @return the element at the specified position in this list. 334 * 335 * @throws IndexOutOfBoundsException if the index is out of range (index 336 * < 0 || index >= size()). 337 */ 338 public Object get(int index) { 339 return getListableAt(index).value(); 340 } 341 342 /** 343 * Returns the element at the beginning of this list. 344 */ 345 public Object getFirst() { 346 try { 347 return _head.next().value(); 348 } catch(NullPointerException e) { 349 throw new NoSuchElementException(); 350 } 351 } 352 353 /** 354 * Returns the element at the end of this list. 355 */ 356 public Object getLast() { 357 try { 358 return _head.prev().value(); 359 } catch(NullPointerException e) { 360 throw new NoSuchElementException(); 361 } 362 } 363 364 /** 365 * Returns the hash code value for this list. The hash code of a list 366 * is defined to be the result of the following calculation: 367 * <pre> 368 * hashCode = 1; 369 * Iterator i = list.iterator(); 370 * while (i.hasNext()) { 371 * Object obj = i.next(); 372 * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); 373 * } 374 * </pre> 375 * This ensures that <tt>list1.equals(list2)</tt> implies that 376 * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists, 377 * <tt>list1</tt> and <tt>list2</tt>, as required by the general 378 * contract of <tt>Object.hashCode</tt>. 379 * 380 * @return the hash code value for this list. 381 * @see Object#hashCode() 382 * @see Object#equals(Object) 383 * @see #equals(Object) 384 */ 385 public int hashCode() { 386 int hash = 1; 387 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 388 hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode()); 389 } 390 return hash; 391 } 392 393 /** 394 * Returns the index in this list of the first occurrence of the specified 395 * element, or -1 if this list does not contain this element. 396 * More formally, returns the lowest index <tt>i</tt> such that 397 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 398 * or -1 if there is no such index. 399 * 400 * @param o element to search for. 401 * @return the index in this list of the first occurrence of the specified 402 * element, or -1 if this list does not contain this element. 403 */ 404 public int indexOf(Object o) { 405 int ndx = 0; 406 407 // perform the null check outside of the loop to save checking every 408 // single time through the loop. 409 if (null == o) { 410 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 411 if (null == elt.value()) { 412 return ndx; 413 } 414 ndx++; 415 } 416 } else { 417 418 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 419 if (o.equals(elt.value())) { 420 return ndx; 421 } 422 ndx++; 423 } 424 } 425 return -1; 426 } 427 428 /** 429 * Returns <tt>true</tt> if this list contains no elements. 430 * @return <tt>true</tt> if this list contains no elements. 431 */ 432 public boolean isEmpty() { 433 return(0 == _size); 434 } 435 436 /** 437 * Returns a fail-fast iterator. 438 * @see List#iterator 439 */ 440 public Iterator iterator() { 441 return listIterator(0); 442 } 443 444 /** 445 * Returns the index in this list of the last occurrence of the specified 446 * element, or -1 if this list does not contain this element. 447 * More formally, returns the highest index <tt>i</tt> such that 448 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 449 * or -1 if there is no such index. 450 * 451 * @param o element to search for. 452 * @return the index in this list of the last occurrence of the specified 453 * element, or -1 if this list does not contain this element. 454 */ 455 public int lastIndexOf(Object o) { 456 int ndx = _size-1; 457 458 // perform the null check outside of the loop to save checking every 459 // single time through the loop. 460 if (null == o) { 461 for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { 462 if (null == elt.value()) { 463 return ndx; 464 } 465 ndx--; 466 } 467 } else { 468 for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { 469 if (o.equals(elt.value())) { 470 return ndx; 471 } 472 ndx--; 473 } 474 } 475 return -1; 476 } 477 478 /** 479 * Returns a fail-fast ListIterator. 480 * @see List#listIterator 481 */ 482 public ListIterator listIterator() { 483 return listIterator(0); 484 } 485 486 /** 487 * Returns a fail-fast ListIterator. 488 * @see List#listIterator(int) 489 */ 490 public ListIterator listIterator(int index) { 491 if(index<0 || index > _size) { 492 throw new IndexOutOfBoundsException(index + " < 0 or > " + _size); 493 } 494 return new ListIter(index); 495 } 496 497 /** 498 * Removes the first occurrence in this list of the specified element. 499 * If this list does not contain the element, it is 500 * unchanged. More formally, removes the element with the lowest index i 501 * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if 502 * such an element exists). 503 * 504 * @param o element to be removed from this list, if present. 505 * @return <tt>true</tt> if this list contained the specified element. 506 */ 507 public boolean remove(Object o) { 508 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 509 if(null == o && null == elt.value()) { 510 removeListable(elt); 511 return true; 512 } else if(o != null && o.equals(elt.value())) { 513 removeListable(elt); 514 return true; 515 } 516 } 517 return false; 518 } 519 520 /** 521 * Removes the element at the specified position in this list (optional 522 * operation). Shifts any subsequent elements to the left (subtracts one 523 * from their indices). Returns the element that was removed from the 524 * list. 525 * 526 * @param index the index of the element to removed. 527 * @return the element previously at the specified position. 528 * 529 * @throws IndexOutOfBoundsException if the index is out of range (index 530 * < 0 || index >= size()). 531 */ 532 public Object remove(int index) { 533 Listable elt = getListableAt(index); 534 Object ret = elt.value(); 535 removeListable(elt); 536 return ret; 537 } 538 539 /** 540 * Removes from this list all the elements that are contained in the 541 * specified collection. 542 * 543 * @param c collection that defines which elements will be removed from 544 * this list. 545 * @return <tt>true</tt> if this list changed as a result of the call. 546 */ 547 public boolean removeAll(Collection c) { 548 if(0 == c.size() || 0 == _size) { 549 return false; 550 } else { 551 boolean changed = false; 552 Iterator it = iterator(); 553 while(it.hasNext()) { 554 if(c.contains(it.next())) { 555 it.remove(); 556 changed = true; 557 } 558 } 559 return changed; 560 } 561 } 562 563 /** 564 * Removes the first element of this list, if any. 565 */ 566 public Object removeFirst() { 567 if(_head.next() != null) { 568 Object val = _head.next().value(); 569 removeListable(_head.next()); 570 return val; 571 } else { 572 throw new NoSuchElementException(); 573 } 574 } 575 576 /** 577 * Removes the last element of this list, if any. 578 */ 579 public Object removeLast() { 580 if(_head.prev() != null) { 581 Object val = _head.prev().value(); 582 removeListable(_head.prev()); 583 return val; 584 } else { 585 throw new NoSuchElementException(); 586 } 587 } 588 589 /** 590 * Retains only the elements in this list that are contained in the 591 * specified collection. In other words, removes 592 * from this list all the elements that are not contained in the specified 593 * collection. 594 * 595 * @param c collection that defines which elements this set will retain. 596 * 597 * @return <tt>true</tt> if this list changed as a result of the call. 598 */ 599 public boolean retainAll(Collection c) { 600 boolean changed = false; 601 Iterator it = iterator(); 602 while(it.hasNext()) { 603 if(!c.contains(it.next())) { 604 it.remove(); 605 changed = true; 606 } 607 } 608 return changed; 609 } 610 611 /** 612 * Replaces the element at the specified position in this list with the 613 * specified element. 614 * 615 * @param index index of element to replace. 616 * @param element element to be stored at the specified position. 617 * @return the element previously at the specified position. 618 * 619 * @throws ClassCastException if the class of the specified element 620 * prevents it from being added to this list. 621 * @throws IllegalArgumentException if some aspect of the specified 622 * element prevents it from being added to this list. 623 * @throws IndexOutOfBoundsException if the index is out of range 624 * (index < 0 || index >= size()). 625 */ 626 public Object set(int index, Object element) { 627 Listable elt = getListableAt(index); 628 Object val = elt.setValue(element); 629 broadcastListableChanged(elt); 630 return val; 631 } 632 633 /** 634 * Returns the number of elements in this list. 635 * @return the number of elements in this list. 636 */ 637 public int size() { 638 return _size; 639 } 640 641 /** 642 * Returns an array containing all of the elements in this list in proper 643 * sequence. Obeys the general contract of the {@link Collection#toArray} method. 644 * 645 * @return an array containing all of the elements in this list in proper 646 * sequence. 647 */ 648 public Object[] toArray() { 649 Object[] array = new Object[_size]; 650 int i = 0; 651 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 652 array[i++] = elt.value(); 653 } 654 return array; 655 } 656 657 /** 658 * Returns an array containing all of the elements in this list in proper 659 * sequence; the runtime type of the returned array is that of the 660 * specified array. Obeys the general contract of the 661 * {@link Collection#toArray} method. 662 * 663 * @param a the array into which the elements of this list are to 664 * be stored, if it is big enough; otherwise, a new array of the 665 * same runtime type is allocated for this purpose. 666 * @return an array containing the elements of this list. 667 * @exception ArrayStoreException 668 * if the runtime type of the specified array 669 * is not a supertype of the runtime type of every element in 670 * this list. 671 */ 672 public Object[] toArray(Object a[]) { 673 if(a.length < _size) { 674 a = (Object[])Array.newInstance(a.getClass().getComponentType(), _size); 675 } 676 int i = 0; 677 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 678 a[i++] = elt.value(); 679 } 680 if(a.length > _size) { 681 a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't 682 } 683 return a; 684 } 685 686 /** 687 * Returns a {@link String} representation of this list, suitable for debugging. 688 * @return a {@link String} representation of this list, suitable for debugging. 689 */ 690 public String toString() { 691 StringBuffer buf = new StringBuffer(); 692 buf.append("["); 693 for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { 694 if(_head.next() != elt) { 695 buf.append(", "); 696 } 697 buf.append(elt.value()); 698 } 699 buf.append("]"); 700 return buf.toString(); 701 } 702 703 /** 704 * Returns a fail-fast sublist. 705 * @see List#subList(int,int) 706 */ 707 public List subList(int i, int j) { 708 if(i < 0 || j > _size || i > j) { 709 throw new IndexOutOfBoundsException(); 710 } else if(i == 0 && j == _size) { 711 return this; 712 } else { 713 return new CursorableSubList(this,i,j); 714 } 715 } 716 717 //--- protected methods ------------------------------------------ 718 719 /** 720 * Inserts a new <i>value</i> into my 721 * list, after the specified <i>before</i> element, and before the 722 * specified <i>after</i> element 723 * 724 * @return the newly created 725 * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 726 */ 727 protected Listable insertListable(Listable before, Listable after, Object value) { 728 _modCount++; 729 _size++; 730 Listable elt = new Listable(before,after,value); 731 if(null != before) { 732 before.setNext(elt); 733 } else { 734 _head.setNext(elt); 735 } 736 737 if(null != after) { 738 after.setPrev(elt); 739 } else { 740 _head.setPrev(elt); 741 } 742 broadcastListableInserted(elt); 743 return elt; 744 } 745 746 /** 747 * Removes the given 748 * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 749 * from my list. 750 */ 751 protected void removeListable(Listable elt) { 752 _modCount++; 753 _size--; 754 if(_head.next() == elt) { 755 _head.setNext(elt.next()); 756 } 757 if(null != elt.next()) { 758 elt.next().setPrev(elt.prev()); 759 } 760 if(_head.prev() == elt) { 761 _head.setPrev(elt.prev()); 762 } 763 if(null != elt.prev()) { 764 elt.prev().setNext(elt.next()); 765 } 766 broadcastListableRemoved(elt); 767 } 768 769 /** 770 * Returns the 771 * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 772 * at the specified index. 773 * 774 * @throws IndexOutOfBoundsException if index is less than zero or 775 * greater than or equal to the size of this list. 776 */ 777 protected Listable getListableAt(int index) { 778 if(index < 0 || index >= _size) { 779 throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size); 780 } 781 if(index <=_size/2) { 782 Listable elt = _head.next(); 783 for(int i = 0; i < index; i++) { 784 elt = elt.next(); 785 } 786 return elt; 787 } else { 788 Listable elt = _head.prev(); 789 for(int i = (_size-1); i > index; i--) { 790 elt = elt.prev(); 791 } 792 return elt; 793 } 794 } 795 796 /** 797 * Registers a {@link CursorableLinkedList.Cursor} to be notified 798 * of changes to this list. 799 */ 800 protected void registerCursor(Cursor cur) { 801 // We take this opportunity to clean the _cursors list 802 // of WeakReference objects to garbage-collected cursors. 803 for (Iterator it = _cursors.iterator(); it.hasNext(); ) { 804 WeakReference ref = (WeakReference) it.next(); 805 if (ref.get() == null) { 806 it.remove(); 807 } 808 } 809 810 _cursors.add( new WeakReference(cur) ); 811 } 812 813 /** 814 * Removes a {@link CursorableLinkedList.Cursor} from 815 * the set of cursors to be notified of changes to this list. 816 */ 817 protected void unregisterCursor(Cursor cur) { 818 for (Iterator it = _cursors.iterator(); it.hasNext(); ) { 819 WeakReference ref = (WeakReference) it.next(); 820 Cursor cursor = (Cursor) ref.get(); 821 if (cursor == null) { 822 // some other unrelated cursor object has been 823 // garbage-collected; let's take the opportunity to 824 // clean up the cursors list anyway.. 825 it.remove(); 826 827 } else if (cursor == cur) { 828 ref.clear(); 829 it.remove(); 830 break; 831 } 832 } 833 } 834 835 /** 836 * Informs all of my registered cursors that they are now 837 * invalid. 838 */ 839 protected void invalidateCursors() { 840 Iterator it = _cursors.iterator(); 841 while (it.hasNext()) { 842 WeakReference ref = (WeakReference) it.next(); 843 Cursor cursor = (Cursor) ref.get(); 844 if (cursor != null) { 845 // cursor is null if object has been garbage-collected 846 cursor.invalidate(); 847 ref.clear(); 848 } 849 it.remove(); 850 } 851 } 852 853 /** 854 * Informs all of my registered cursors that the specified 855 * element was changed. 856 * @see #set(int,java.lang.Object) 857 */ 858 protected void broadcastListableChanged(Listable elt) { 859 Iterator it = _cursors.iterator(); 860 while (it.hasNext()) { 861 WeakReference ref = (WeakReference) it.next(); 862 Cursor cursor = (Cursor) ref.get(); 863 if (cursor == null) { 864 it.remove(); // clean up list 865 } else { 866 cursor.listableChanged(elt); 867 } 868 } 869 } 870 871 /** 872 * Informs all of my registered cursors that the specified 873 * element was just removed from my list. 874 */ 875 protected void broadcastListableRemoved(Listable elt) { 876 Iterator it = _cursors.iterator(); 877 while (it.hasNext()) { 878 WeakReference ref = (WeakReference) it.next(); 879 Cursor cursor = (Cursor) ref.get(); 880 if (cursor == null) { 881 it.remove(); // clean up list 882 } else { 883 cursor.listableRemoved(elt); 884 } 885 } 886 } 887 888 /** 889 * Informs all of my registered cursors that the specified 890 * element was just added to my list. 891 */ 892 protected void broadcastListableInserted(Listable elt) { 893 Iterator it = _cursors.iterator(); 894 while (it.hasNext()) { 895 WeakReference ref = (WeakReference) it.next(); 896 Cursor cursor = (Cursor) ref.get(); 897 if (cursor == null) { 898 it.remove(); // clean up list 899 } else { 900 cursor.listableInserted(elt); 901 } 902 } 903 } 904 905 private void writeObject(ObjectOutputStream out) throws IOException { 906 out.defaultWriteObject(); 907 out.writeInt(_size); 908 Listable cur = _head.next(); 909 while (cur != null) { 910 out.writeObject(cur.value()); 911 cur = cur.next(); 912 } 913 } 914 915 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 916 in.defaultReadObject(); 917 _size = 0; 918 _modCount = 0; 919 _cursors = new ArrayList(); 920 _head = new Listable(null,null,null); 921 int size = in.readInt(); 922 for (int i=0;i<size;i++) { 923 this.add(in.readObject()); 924 } 925 } 926 927 //--- protected attributes --------------------------------------- 928 929 /** The number of elements in me. */ 930 protected transient int _size = 0; 931 932 /** 933 * A sentry node. 934 * <p> 935 * <tt>_head.next()</tt> points to the first element in the list, 936 * <tt>_head.prev()</tt> to the last. Note that it is possible for 937 * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be 938 * non-null, as when I am a sublist for some larger list. 939 * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine 940 * if a given 941 * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 942 * is the first or last element in the list. 943 */ 944 protected transient Listable _head = new Listable(null,null,null); 945 946 /** Tracks the number of structural modifications to me. */ 947 protected transient int _modCount = 0; 948 949 /** 950 * A list of the currently {@link CursorableLinkedList.Cursor}s currently 951 * open in this list. 952 */ 953 protected transient List _cursors = new ArrayList(); 954 955 //--- inner classes ---------------------------------------------- 956 957 static class Listable implements Serializable { 958 private Listable _prev = null; 959 private Listable _next = null; 960 private Object _val = null; 961 962 Listable(Listable prev, Listable next, Object val) { 963 _prev = prev; 964 _next = next; 965 _val = val; 966 } 967 968 Listable next() { 969 return _next; 970 } 971 972 Listable prev() { 973 return _prev; 974 } 975 976 Object value() { 977 return _val; 978 } 979 980 void setNext(Listable next) { 981 _next = next; 982 } 983 984 void setPrev(Listable prev) { 985 _prev = prev; 986 } 987 988 Object setValue(Object val) { 989 Object temp = _val; 990 _val = val; 991 return temp; 992 } 993 } 994 995 class ListIter implements ListIterator { 996 Listable _cur = null; 997 Listable _lastReturned = null; 998 int _expectedModCount = _modCount; 999 int _nextIndex = 0; 1000 1001 ListIter(int index) { 1002 if(index == 0) { 1003 _cur = new Listable(null,_head.next(),null); 1004 _nextIndex = 0; 1005 } else if(index == _size) { 1006 _cur = new Listable(_head.prev(),null,null); 1007 _nextIndex = _size; 1008 } else { 1009 Listable temp = getListableAt(index); 1010 _cur = new Listable(temp.prev(),temp,null); 1011 _nextIndex = index; 1012 } 1013 } 1014 1015 public Object previous() { 1016 checkForComod(); 1017 if(!hasPrevious()) { 1018 throw new NoSuchElementException(); 1019 } else { 1020 Object ret = _cur.prev().value(); 1021 _lastReturned = _cur.prev(); 1022 _cur.setNext(_cur.prev()); 1023 _cur.setPrev(_cur.prev().prev()); 1024 _nextIndex--; 1025 return ret; 1026 } 1027 } 1028 1029 public boolean hasNext() { 1030 checkForComod(); 1031 return(null != _cur.next() && _cur.prev() != _head.prev()); 1032 } 1033 1034 public Object next() { 1035 checkForComod(); 1036 if(!hasNext()) { 1037 throw new NoSuchElementException(); 1038 } else { 1039 Object ret = _cur.next().value(); 1040 _lastReturned = _cur.next(); 1041 _cur.setPrev(_cur.next()); 1042 _cur.setNext(_cur.next().next()); 1043 _nextIndex++; 1044 return ret; 1045 } 1046 } 1047 1048 public int previousIndex() { 1049 checkForComod(); 1050 if(!hasPrevious()) { 1051 return -1; 1052 } 1053 return _nextIndex-1; 1054 } 1055 1056 public boolean hasPrevious() { 1057 checkForComod(); 1058 return(null != _cur.prev() && _cur.next() != _head.next()); 1059 } 1060 1061 public void set(Object o) { 1062 checkForComod(); 1063 try { 1064 _lastReturned.setValue(o); 1065 } catch(NullPointerException e) { 1066 throw new IllegalStateException(); 1067 } 1068 } 1069 1070 public int nextIndex() { 1071 checkForComod(); 1072 if(!hasNext()) { 1073 return size(); 1074 } 1075 return _nextIndex; 1076 } 1077 1078 public void remove() { 1079 checkForComod(); 1080 if(null == _lastReturned) { 1081 throw new IllegalStateException(); 1082 } else { 1083 _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next()); 1084 _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev()); 1085 removeListable(_lastReturned); 1086 _lastReturned = null; 1087 _nextIndex--; 1088 _expectedModCount++; 1089 } 1090 } 1091 1092 public void add(Object o) { 1093 checkForComod(); 1094 _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o)); 1095 _lastReturned = null; 1096 _nextIndex++; 1097 _expectedModCount++; 1098 } 1099 1100 protected void checkForComod() { 1101 if(_expectedModCount != _modCount) { 1102 throw new ConcurrentModificationException(); 1103 } 1104 } 1105 } 1106 1107 public class Cursor extends ListIter implements ListIterator { 1108 boolean _valid = false; 1109 1110 Cursor(int index) { 1111 super(index); 1112 _valid = true; 1113 registerCursor(this); 1114 } 1115 1116 public int previousIndex() { 1117 throw new UnsupportedOperationException(); 1118 } 1119 1120 public int nextIndex() { 1121 throw new UnsupportedOperationException(); 1122 } 1123 1124 public void add(Object o) { 1125 checkForComod(); 1126 Listable elt = insertListable(_cur.prev(),_cur.next(),o); 1127 _cur.setPrev(elt); 1128 _cur.setNext(elt.next()); 1129 _lastReturned = null; 1130 _nextIndex++; 1131 _expectedModCount++; 1132 } 1133 1134 protected void listableRemoved(Listable elt) { 1135 if(null == _head.prev()) { 1136 _cur.setNext(null); 1137 } else if(_cur.next() == elt) { 1138 _cur.setNext(elt.next()); 1139 } 1140 if(null == _head.next()) { 1141 _cur.setPrev(null); 1142 } else if(_cur.prev() == elt) { 1143 _cur.setPrev(elt.prev()); 1144 } 1145 if(_lastReturned == elt) { 1146 _lastReturned = null; 1147 } 1148 } 1149 1150 protected void listableInserted(Listable elt) { 1151 if(null == _cur.next() && null == _cur.prev()) { 1152 _cur.setNext(elt); 1153 } else if(_cur.prev() == elt.prev()) { 1154 _cur.setNext(elt); 1155 } 1156 if(_cur.next() == elt.next()) { 1157 _cur.setPrev(elt); 1158 } 1159 if(_lastReturned == elt) { 1160 _lastReturned = null; 1161 } 1162 } 1163 1164 protected void listableChanged(Listable elt) { 1165 if(_lastReturned == elt) { 1166 _lastReturned = null; 1167 } 1168 } 1169 1170 protected void checkForComod() { 1171 if(!_valid) { 1172 throw new ConcurrentModificationException(); 1173 } 1174 } 1175 1176 protected void invalidate() { 1177 _valid = false; 1178 } 1179 1180 /** 1181 * Mark this cursor as no longer being needed. Any resources 1182 * associated with this cursor are immediately released. 1183 * In previous versions of this class, it was mandatory to close 1184 * all cursor objects to avoid memory leaks. It is <i>no longer</i> 1185 * necessary to call this close method; an instance of this class 1186 * can now be treated exactly like a normal iterator. 1187 */ 1188 public void close() { 1189 if(_valid) { 1190 _valid = false; 1191 unregisterCursor(this); 1192 } 1193 } 1194 } 1195 1196 } 1197 1198 /** 1199 * @deprecated Use new version in list subpackage, which has been rewritten 1200 * and now returns the cursor from the listIterator method. Will be removed in v4.0 1201 */ 1202 class CursorableSubList extends CursorableLinkedList implements List { 1203 1204 //--- constructors ----------------------------------------------- 1205 1206 CursorableSubList(CursorableLinkedList list, int from, int to) { 1207 if(0 > from || list.size() < to) { 1208 throw new IndexOutOfBoundsException(); 1209 } else if(from > to) { 1210 throw new IllegalArgumentException(); 1211 } 1212 _list = list; 1213 if(from < list.size()) { 1214 _head.setNext(_list.getListableAt(from)); 1215 _pre = (null == _head.next()) ? null : _head.next().prev(); 1216 } else { 1217 _pre = _list.getListableAt(from-1); 1218 } 1219 if(from == to) { 1220 _head.setNext(null); 1221 _head.setPrev(null); 1222 if(to < list.size()) { 1223 _post = _list.getListableAt(to); 1224 } else { 1225 _post = null; 1226 } 1227 } else { 1228 _head.setPrev(_list.getListableAt(to-1)); 1229 _post = _head.prev().next(); 1230 } 1231 _size = to - from; 1232 _modCount = _list._modCount; 1233 } 1234 1235 //--- public methods ------------------------------------------ 1236 1237 public void clear() { 1238 checkForComod(); 1239 Iterator it = iterator(); 1240 while(it.hasNext()) { 1241 it.next(); 1242 it.remove(); 1243 } 1244 } 1245 1246 public Iterator iterator() { 1247 checkForComod(); 1248 return super.iterator(); 1249 } 1250 1251 public int size() { 1252 checkForComod(); 1253 return super.size(); 1254 } 1255 1256 public boolean isEmpty() { 1257 checkForComod(); 1258 return super.isEmpty(); 1259 } 1260 1261 public Object[] toArray() { 1262 checkForComod(); 1263 return super.toArray(); 1264 } 1265 1266 public Object[] toArray(Object a[]) { 1267 checkForComod(); 1268 return super.toArray(a); 1269 } 1270 1271 public boolean contains(Object o) { 1272 checkForComod(); 1273 return super.contains(o); 1274 } 1275 1276 public boolean remove(Object o) { 1277 checkForComod(); 1278 return super.remove(o); 1279 } 1280 1281 public Object removeFirst() { 1282 checkForComod(); 1283 return super.removeFirst(); 1284 } 1285 1286 public Object removeLast() { 1287 checkForComod(); 1288 return super.removeLast(); 1289 } 1290 1291 public boolean addAll(Collection c) { 1292 checkForComod(); 1293 return super.addAll(c); 1294 } 1295 1296 public boolean add(Object o) { 1297 checkForComod(); 1298 return super.add(o); 1299 } 1300 1301 public boolean addFirst(Object o) { 1302 checkForComod(); 1303 return super.addFirst(o); 1304 } 1305 1306 public boolean addLast(Object o) { 1307 checkForComod(); 1308 return super.addLast(o); 1309 } 1310 1311 public boolean removeAll(Collection c) { 1312 checkForComod(); 1313 return super.removeAll(c); 1314 } 1315 1316 public boolean containsAll(Collection c) { 1317 checkForComod(); 1318 return super.containsAll(c); 1319 } 1320 1321 public boolean addAll(int index, Collection c) { 1322 checkForComod(); 1323 return super.addAll(index,c); 1324 } 1325 1326 public int hashCode() { 1327 checkForComod(); 1328 return super.hashCode(); 1329 } 1330 1331 public boolean retainAll(Collection c) { 1332 checkForComod(); 1333 return super.retainAll(c); 1334 } 1335 1336 public Object set(int index, Object element) { 1337 checkForComod(); 1338 return super.set(index,element); 1339 } 1340 1341 public boolean equals(Object o) { 1342 checkForComod(); 1343 return super.equals(o); 1344 } 1345 1346 public Object get(int index) { 1347 checkForComod(); 1348 return super.get(index); 1349 } 1350 1351 public Object getFirst() { 1352 checkForComod(); 1353 return super.getFirst(); 1354 } 1355 1356 public Object getLast() { 1357 checkForComod(); 1358 return super.getLast(); 1359 } 1360 1361 public void add(int index, Object element) { 1362 checkForComod(); 1363 super.add(index,element); 1364 } 1365 1366 public ListIterator listIterator(int index) { 1367 checkForComod(); 1368 return super.listIterator(index); 1369 } 1370 1371 public Object remove(int index) { 1372 checkForComod(); 1373 return super.remove(index); 1374 } 1375 1376 public int indexOf(Object o) { 1377 checkForComod(); 1378 return super.indexOf(o); 1379 } 1380 1381 public int lastIndexOf(Object o) { 1382 checkForComod(); 1383 return super.lastIndexOf(o); 1384 } 1385 1386 public ListIterator listIterator() { 1387 checkForComod(); 1388 return super.listIterator(); 1389 } 1390 1391 public List subList(int fromIndex, int toIndex) { 1392 checkForComod(); 1393 return super.subList(fromIndex,toIndex); 1394 } 1395 1396 //--- protected methods ------------------------------------------ 1397 1398 /** 1399 * Inserts a new <i>value</i> into my 1400 * list, after the specified <i>before</i> element, and before the 1401 * specified <i>after</i> element 1402 * 1403 * @return the newly created {@link CursorableLinkedList.Listable} 1404 */ 1405 protected Listable insertListable(Listable before, Listable after, Object value) { 1406 _modCount++; 1407 _size++; 1408 Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value); 1409 if(null == _head.next()) { 1410 _head.setNext(elt); 1411 _head.setPrev(elt); 1412 } 1413 if(before == _head.prev()) { 1414 _head.setPrev(elt); 1415 } 1416 if(after == _head.next()) { 1417 _head.setNext(elt); 1418 } 1419 broadcastListableInserted(elt); 1420 return elt; 1421 } 1422 1423 /** 1424 * Removes the given {@link CursorableLinkedList.Listable} from my list. 1425 */ 1426 protected void removeListable(Listable elt) { 1427 _modCount++; 1428 _size--; 1429 if(_head.next() == elt && _head.prev() == elt) { 1430 _head.setNext(null); 1431 _head.setPrev(null); 1432 } 1433 if(_head.next() == elt) { 1434 _head.setNext(elt.next()); 1435 } 1436 if(_head.prev() == elt) { 1437 _head.setPrev(elt.prev()); 1438 } 1439 _list.removeListable(elt); 1440 broadcastListableRemoved(elt); 1441 } 1442 1443 /** 1444 * Test to see if my underlying list has been modified 1445 * by some other process. If it has, throws a 1446 * {@link ConcurrentModificationException}, otherwise 1447 * quietly returns. 1448 * 1449 * @throws ConcurrentModificationException 1450 */ 1451 protected void checkForComod() throws ConcurrentModificationException { 1452 if(_modCount != _list._modCount) { 1453 throw new ConcurrentModificationException(); 1454 } 1455 } 1456 1457 //--- protected attributes --------------------------------------- 1458 1459 /** My underlying list */ 1460 protected CursorableLinkedList _list = null; 1461 1462 /** The element in my underlying list preceding the first element in my list. */ 1463 protected Listable _pre = null; 1464 1465 /** The element in my underlying list following the last element in my list. */ 1466 protected Listable _post = null; 1467 1468 }