| Frames | No Frames |
1: /* AbstractSequentialList.java -- List implementation for sequential access 2: Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.util; 40: 41: /** 42: * Abstract superclass to make it easier to implement the List interface when 43: * backed by a sequential-access store, such as a linked list. For random 44: * access data, use AbstractList. This class implements the random access 45: * methods (<code>get</code>, <code>set</code>, <code>add</code>, and 46: * <code>remove</code>) atop the list iterator, opposite of AbstractList's 47: * approach of implementing the iterator atop random access. 48: * <p> 49: * 50: * To implement a list, you need an implementation for <code>size()</code> 51: * and <code>listIterator</code>. With just <code>hasNext</code>, 52: * <code>next</code>, <code>hasPrevious</code>, <code>previous</code>, 53: * <code>nextIndex</code>, and <code>previousIndex</code>, you have an 54: * unmodifiable list. For a modifiable one, add <code>set</code>, and for 55: * a variable-size list, add <code>add</code> and <code>remove</code>. 56: * <p> 57: * 58: * The programmer should provide a no-argument constructor, and one that 59: * accepts another Collection, as recommended by the Collection interface. 60: * Unfortunately, there is no way to enforce this in Java. 61: * 62: * @author Original author unknown 63: * @author Bryce McKinlay 64: * @author Eric Blake (ebb9@email.byu.edu) 65: * @see Collection 66: * @see List 67: * @see AbstractList 68: * @see AbstractCollection 69: * @see ListIterator 70: * @see LinkedList 71: * @since 1.2 72: * @status updated to 1.4 73: */ 74: public abstract class AbstractSequentialList<E> extends AbstractList<E> 75: { 76: /** 77: * The main constructor, for use by subclasses. 78: */ 79: protected AbstractSequentialList() 80: { 81: } 82: 83: /** 84: * Returns a ListIterator over the list, starting from position index. 85: * Subclasses must provide an implementation of this method. 86: * 87: * @param index the starting position of the list 88: * @return the list iterator 89: * @throws IndexOutOfBoundsException if index < 0 || index > size() 90: */ 91: public abstract ListIterator<E> listIterator(int index); 92: 93: /** 94: * Insert an element into the list at a given position (optional operation). 95: * This shifts all existing elements from that position to the end one 96: * index to the right. This version of add has no return, since it is 97: * assumed to always succeed if there is no exception. This iteration 98: * uses listIterator(index).add(o). 99: * 100: * @param index the location to insert the item 101: * @param o the object to insert 102: * @throws UnsupportedOperationException if this list does not support the 103: * add operation 104: * @throws IndexOutOfBoundsException if index < 0 || index > size() 105: * @throws ClassCastException if o cannot be added to this list due to its 106: * type 107: * @throws IllegalArgumentException if o cannot be added to this list for 108: * some other reason. 109: * @throws NullPointerException if o is null and the list does not permit 110: * the addition of null values. 111: */ 112: public void add(int index, E o) 113: { 114: listIterator(index).add(o); 115: } 116: 117: /** 118: * Insert the contents of a collection into the list at a given position 119: * (optional operation). Shift all elements at that position to the right 120: * by the number of elements inserted. This operation is undefined if 121: * this list is modified during the operation (for example, if you try 122: * to insert a list into itself). 123: * <p> 124: * 125: * This implementation grabs listIterator(index), then proceeds to use add 126: * for each element returned by c's iterator. Sun's online specs are wrong, 127: * claiming that this also calls next(): listIterator.add() correctly 128: * skips the added element. 129: * 130: * @param index the location to insert the collection 131: * @param c the collection to insert 132: * @return true if the list was modified by this action, that is, if c is 133: * non-empty 134: * @throws UnsupportedOperationException if this list does not support the 135: * addAll operation 136: * @throws IndexOutOfBoundsException if index < 0 || index > size() 137: * @throws ClassCastException if some element of c cannot be added to this 138: * list due to its type 139: * @throws IllegalArgumentException if some element of c cannot be added 140: * to this list for some other reason 141: * @throws NullPointerException if the specified collection is null 142: * @throws NullPointerException if an object, o, in c is null and the list 143: * does not permit the addition of null values. 144: * @see #add(int, Object) 145: */ 146: public boolean addAll(int index, Collection<? extends E> c) 147: { 148: Iterator<? extends E> ci = c.iterator(); 149: int size = c.size(); 150: ListIterator<E> i = listIterator(index); 151: for (int pos = size; pos > 0; pos--) 152: i.add(ci.next()); 153: return size > 0; 154: } 155: 156: /** 157: * Get the element at a given index in this list. This implementation 158: * returns listIterator(index).next(). 159: * 160: * @param index the index of the element to be returned 161: * @return the element at index index in this list 162: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 163: */ 164: public E get(int index) 165: { 166: // This is a legal listIterator position, but an illegal get. 167: if (index == size()) 168: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 169: + size()); 170: return listIterator(index).next(); 171: } 172: 173: /** 174: * Obtain an Iterator over this list, whose sequence is the list order. This 175: * implementation returns listIterator(). 176: * 177: * @return an Iterator over the elements of this list, in order 178: */ 179: public Iterator<E> iterator() 180: { 181: return listIterator(); 182: } 183: 184: /** 185: * Remove the element at a given position in this list (optional operation). 186: * Shifts all remaining elements to the left to fill the gap. This 187: * implementation uses listIterator(index) and ListIterator.remove(). 188: * 189: * @param index the position within the list of the object to remove 190: * @return the object that was removed 191: * @throws UnsupportedOperationException if this list does not support the 192: * remove operation 193: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 194: */ 195: public E remove(int index) 196: { 197: // This is a legal listIterator position, but an illegal remove. 198: if (index == size()) 199: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 200: + size()); 201: ListIterator<E> i = listIterator(index); 202: E removed = i.next(); 203: i.remove(); 204: return removed; 205: } 206: 207: /** 208: * Replace an element of this list with another object (optional operation). 209: * This implementation uses listIterator(index) and ListIterator.set(o). 210: * 211: * @param index the position within this list of the element to be replaced 212: * @param o the object to replace it with 213: * @return the object that was replaced 214: * @throws UnsupportedOperationException if this list does not support the 215: * set operation 216: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 217: * @throws ClassCastException if o cannot be added to this list due to its 218: * type 219: * @throws IllegalArgumentException if o cannot be added to this list for 220: * some other reason 221: * @throws NullPointerException if o is null and the list does not allow 222: * a value to be set to null. 223: */ 224: public E set(int index, E o) 225: { 226: // This is a legal listIterator position, but an illegal set. 227: if (index == size()) 228: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 229: + size()); 230: ListIterator<E> i = listIterator(index); 231: E old = i.next(); 232: i.set(o); 233: return old; 234: } 235: }