001 /* AbstractSequentialList.java -- List implementation for sequential access 002 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 003 004 This file is part of GNU Classpath. 005 006 GNU Classpath is free software; you can redistribute it and/or modify 007 it under the terms of the GNU General Public License as published by 008 the Free Software Foundation; either version 2, or (at your option) 009 any later version. 010 011 GNU Classpath is distributed in the hope that it will be useful, but 012 WITHOUT ANY WARRANTY; without even the implied warranty of 013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 General Public License for more details. 015 016 You should have received a copy of the GNU General Public License 017 along with GNU Classpath; see the file COPYING. If not, write to the 018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 019 02110-1301 USA. 020 021 Linking this library statically or dynamically with other modules is 022 making a combined work based on this library. Thus, the terms and 023 conditions of the GNU General Public License cover the whole 024 combination. 025 026 As a special exception, the copyright holders of this library give you 027 permission to link this library with independent modules to produce an 028 executable, regardless of the license terms of these independent 029 modules, and to copy and distribute the resulting executable under 030 terms of your choice, provided that you also meet, for each linked 031 independent module, the terms and conditions of the license of that 032 module. An independent module is a module which is not derived from 033 or based on this library. If you modify this library, you may extend 034 this exception to your version of the library, but you are not 035 obligated to do so. If you do not wish to do so, delete this 036 exception statement from your version. */ 037 038 039 package java.util; 040 041 /** 042 * Abstract superclass to make it easier to implement the List interface when 043 * backed by a sequential-access store, such as a linked list. For random 044 * access data, use AbstractList. This class implements the random access 045 * methods (<code>get</code>, <code>set</code>, <code>add</code>, and 046 * <code>remove</code>) atop the list iterator, opposite of AbstractList's 047 * approach of implementing the iterator atop random access. 048 * <p> 049 * 050 * To implement a list, you need an implementation for <code>size()</code> 051 * and <code>listIterator</code>. With just <code>hasNext</code>, 052 * <code>next</code>, <code>hasPrevious</code>, <code>previous</code>, 053 * <code>nextIndex</code>, and <code>previousIndex</code>, you have an 054 * unmodifiable list. For a modifiable one, add <code>set</code>, and for 055 * a variable-size list, add <code>add</code> and <code>remove</code>. 056 * <p> 057 * 058 * The programmer should provide a no-argument constructor, and one that 059 * accepts another Collection, as recommended by the Collection interface. 060 * Unfortunately, there is no way to enforce this in Java. 061 * 062 * @author Original author unknown 063 * @author Bryce McKinlay 064 * @author Eric Blake (ebb9@email.byu.edu) 065 * @see Collection 066 * @see List 067 * @see AbstractList 068 * @see AbstractCollection 069 * @see ListIterator 070 * @see LinkedList 071 * @since 1.2 072 * @status updated to 1.4 073 */ 074 public abstract class AbstractSequentialList<E> extends AbstractList<E> 075 { 076 /** 077 * The main constructor, for use by subclasses. 078 */ 079 protected AbstractSequentialList() 080 { 081 } 082 083 /** 084 * Returns a ListIterator over the list, starting from position index. 085 * Subclasses must provide an implementation of this method. 086 * 087 * @param index the starting position of the list 088 * @return the list iterator 089 * @throws IndexOutOfBoundsException if index < 0 || index > size() 090 */ 091 public abstract ListIterator<E> listIterator(int index); 092 093 /** 094 * Insert an element into the list at a given position (optional operation). 095 * This shifts all existing elements from that position to the end one 096 * index to the right. This version of add has no return, since it is 097 * assumed to always succeed if there is no exception. This iteration 098 * uses listIterator(index).add(o). 099 * 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 }