From 817fd3a010426d3315569be53fae47c3c406739f Mon Sep 17 00:00:00 2001 From: bryce Date: Sat, 15 Dec 2001 07:47:03 +0000 Subject: Collections drop from Classpath: 2001-12-15 Bryce McKinlay * java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of the bitset. (andNot): Likewise. (xor): Likewise. 2001-12-15 Bryce McKinlay * java/util/LinkedList.java (LinkedListItr.add): Don't skip the next entry. 2001-12-15 Eric Blake * java/util/TreeMap.java (removeNode): Fix bug in node removal. 2001-12-15 Bryce McKinlay * java/util/AbstractCollection.java (containsAll): Use size of the correct collection for loop bound. * java/util/AbstractList.java (iterator.next): Increment pos after calling get on backing list. (listIterator.next): Likewise. * java/util/LinkedList.java (addLastEntry): Don't increment size before checking for size == 0. (addFirstEntry): Rearrange to match addLastEntry. (add): Do not increment size before inserting the new entry. * java/util/AbstractCollection.java (addAll): Use size of the correct collection for loop bound. 2001-12-15 Bryce McKinlay * java/util/AbstractSet.java (removeAll): Fix scoping thinko. * java/util/HashMap.java (putAllInternal): Set size here. * java/util/Hashtable.java (putAllInternal): New method. Copy contents of a map efficiently without calling put() or putAll(). (Hashtable (map)): Use putAllInternal. (clone): Likewise. 2001-12-15 Eric Blake * java/util/Collections.java: * java/util/Vector.java: * java/util/WeakHashMap.java: Fix spelling errors. 2001-12-15 Eric Blake * java/util/AbstractCollection.java (removeAllInternal), (retainAllInternal): Add hooks for use by ArrayList. * java/util/AbstractList.java: Minor code updates. Fix some scoping. * java/util/AbstractMap.java: ditto * java/util/ArrayList.java (readObject, writeObject): ditto (removeAllInternal, retainAllInternal): Optimize. * java/util/Arrays.java: ditto * java/util/Collections.java: ditto. Change order of parameters to equals(Object, Object) to match specs. * java/util/Dictionary.java: Improve javadoc. (Dictionary): Add explicit constructor. * java/util/HashMap.java: Improve javadoc. Rearrange methods to follow order in JDK. Cleanups related to recent code migration to AbstractMap. Fix some scoping. (entrySet): Cache the result. (modCount): Ensure that this is updated correctly. * java/util/HashSet.java: Improve javadoc. Fix some scoping. (init): Add hooks for LinkedHashSet. (map): Use "" instead of Boolean.TRUE in backing map. Use package-private API where possible for less overhead. (readObject, writeObject): Fix serialization. * java/util/Hashtable.java: Improve javadoc. Fix some scoping. (entrySet, keySet, values): Cache the result. (modCount): Ensure that this is updated correctly. (contains, remove): Fix NullPointer checking to match specs. (class Enumeration): Make more like HashIterator. * java/util/IdentityHashMap.java: Minor code updates. (modCount): Ensure that this is updated correctly. (readObject, writeObject): Fix serialization. * java/util/LinkedHashMap.java: Minor code updates. Cleanups related to recent code migration to AbstractMap. * java/util/LinkedHashSet.java: New file. * java/util/LinkedList.java: (readObject, writeObject): Fix serialization. * java/util/Makefile.am: List recently added files. * java/util/Stack.java: Minor code updates. * java/util/TreeMap.java: Improve javadoc. Overhaul the class to be more efficient. Fix some scoping. Rearrange the methods. (nil): Ensure that this can be thread-safe, and make it a static final. Initialize it to be more useful as a sentinal node. (Node): Specify color in constructor. (deleteFixup, insertFixup): Improve comments and algorithm. (fabricateTree): Redesign with less overhead. (lowestGreaterThan): Add parameter first to make SubMap easier. (removeNode): Patch hole where nil was being modified. Choose predecessor instead of successor so in-place swap works. (class VerifyResult, verifyTree, verifySub, verifyError): Remove this dead code after verifying the class works. (class SubMap): Rewrite several algorithms to avoid problems with comparing nil. * java/util/TreeSet.java: Improve javadoc. Fix some scoping. (clone): Fix ClassCastException when cloning subSet(). (readObject, writeObject): Fix serialization. * java/util/WeakHashMap.java: Improve javadoc. Fix some scoping. (NULL_KEY): Make it compare as null, for ease elsewhere. (Class WeakEntry): Rename from Entry, to avoid shadowing Map.Entry. Add missing toString. (modCount): Ensure that this is updated correctly. (clear, containsValue, keySet, putAll, values, WeakHashMap(Map)): Add missing methods and constructor. 2001-12-15 Eric Blake * java/util/ArrayList.java (checkBoundExclusive), (checkBoundInclusive): Rename from range??clusive, to match AbstractList. * java/util/LinkedList.java (checkBoundsExclusive), (checkBoundsInclusive): ditto * java/util/Vector.java (checkBoundExclusive), (checkBoundInclusive): Move bounds checking into common methods. 2001-12-15 Eric Blake * java/util/AbstractList.java: (modCount): Make sure it is updated in all needed places. * java/util/ArrayList.java: Improve javadoc. Implements RandomAccess. Add serialVersionUID. Reorder methods. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. (isEmpty): Add missing method. * java/util/Collections.java: (class SynchronizedList): Make package visible. * java/util/ConcurrentModificationException.java: Improve javadoc. * java/util/EmptyStackException.java: Improve javadoc. * java/util/LinkedList.java: Improve javadoc. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. * java/util/NoSuchElementException.java: Improve javadoc. * java/util/Stack.java: Improve javadoc. Fix synchronization issues. (modCount): Make sure it is updated in all needed places. * java/util/Vector.java: Improve javadoc. Fix synchronization issues. Implements RandomAccess. Reorder methods. (modCount): Make sure it is updated in all needed places. (setSize): Fix according to specifications: this does not dictate the backing array size. (removeAll, retainAll): Faster implementations. 2001-12-15 Eric Blake * java/util/BitSet.java: Improve javadoc. (cardinality(), clear(), clear(int, int), flip(int)), (flip(int, int), get(int, int), intersects(BitSet), isEmpty()), (nextClearBit(int), nextSetBit(int), set(int, boolean)), (set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods. (clone): Fix so subclasses clone correctly. 2001-12-15 Eric Blake * java/util/AbstractCollection.java: Improve javadoc. (AbstractCollection()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. * java/util/AbstractList.java: Improve javadoc. (AbstractList()): Make constructor protected. (indexOf(Object)): Call listIterator(), not listIterator(int). (iterator()): Follow Sun's requirement to not use listIterator(0). (listIterator(int)): Make AbstractListItr anonymous. (subList(int, int)): Add support for RandomAccess. (SubList.add(int, Object), SubList.remove(Object)): Fix bug with modCount tracking. (SubList.addAll(Collection)): Add missing method. (SubList.listIterator(int)): Fix bugs in indexing, modCount tracking. (class RandomAccessSubList): Add new class. * java/util/AbstractMap.java: Improve javadoc. (keys, values, KEYS, VALUES, ENTRIES): Consolidate common map fields. (AbstractMap()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. (equals(Object)): Change algorithm to entrySet().equals(m.entrySet()), as documented by Sun. (keySet(), values()): Cache the collections. * java/util/AbstractSequentialList.java: Improve javadoc. (AbstractSequentialList()): Make constructor protected. * java/util/AbstractSet.java: Improve javadoc. (AbstractSet()): Make constructor protected. (removeAll(Collection)): Add missing method. * java/util/Arrays.java: Improve javadoc, rearrange method orders. (defaultComparator): Remove, in favor of Collections.compare(Object, Object, Comparator). (binarySearch, equals, sort): Fix natural order comparison of floats and doubles. Also improve Object comparison - when comparator is null, use natural order. (fill, sort): Add missing checks for IllegalArgumentException. (sort, qsort): Fix sorting bugs, rework the code for more legibility. (mergeSort): Inline into sort(Object[], int, int, Comparator). (class ArrayList): Rename from ListImpl, and make compatible with JDK serialization. Add methods which more efficiently override those of AbstractList. * java/util/Collections: Improve javadoc. (isSequential(List)): Add and use a method for deciding between RandomAccess and sequential algorithms on lists. (class Empty*, class Synchronized*, class Unmodifiable*): Make compliant with JDK serializability. (class Singleton*, class CopiesList, class RevereseComparator), (class UnmodifiableMap.UnmodifiableEntrySet), (class *RandomAccessList): New classes for serial compatibility. (class Empty*, class Singleton*, class CopiesList): Add methods which more efficiently override those of Abstract*. (search): Inline into binarySearch(List, Object, Comparator). (binarySearch): Make sequential search only do log(n) comparisons, instead of n. (copy(List, List)): Do bounds checking before starting. (indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate), (swap): Add new JDK 1.4 methods. (binarySearch, max, min, sort): Allow null comparator to represent natural ordering. (reverse(List)): Avoid unnecessary swap. (shuffle(List, Random)): Do shuffle in-place for RandomAccess lists. (SingletonList.get): Fix logic bug. (SingletonMap.entrySet): Make the entry immutable, and cache the returned set. (SynchronizedCollection, SynchronizedMap, UnmodifiableCollection), (UnmodifiableMap): Detect null pointer in construction. (SynchronizedMap, UnmodifiableMap): Cache collection views. * java/util/BasicMapEntry: Improve javadoc. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@48035 138bc75d-0d04-0410-961f-82ee72b054a4 --- libjava/java/util/AbstractSequentialList.java | 176 ++++++++++++++++++++------ 1 file changed, 134 insertions(+), 42 deletions(-) (limited to 'libjava/java/util/AbstractSequentialList.java') diff --git a/libjava/java/util/AbstractSequentialList.java b/libjava/java/util/AbstractSequentialList.java index 81481be0466..2267b02e523 100644 --- a/libjava/java/util/AbstractSequentialList.java +++ b/libjava/java/util/AbstractSequentialList.java @@ -1,5 +1,5 @@ /* AbstractSequentialList.java -- List implementation for sequential access - Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,100 +25,192 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Lots of doc comments still missing. -// ~ The class comment should include a description of what should be overridden -// to provide what features, as should the listIterator comment. - package java.util; /** * Abstract superclass to make it easier to implement the List interface when - * backed by a sequential-access store, such as a linked list. + * backed by a sequential-access store, such as a linked list. For random + * access data, use AbstractList. This class implements the random access + * methods (get, set, add, and + * remove) atop the list iterator, opposite of AbstractList's + * approach of implementing the iterator atop random access. + *

+ * + * To implement a list, you need an implementation for size() + * and listIterator. With just hasNext, + * next, hasPrevious, previous, + * nextIndex, and previousIndex, you have an + * unmodifiable list. For a modifiable one, add set, and for + * a variable-size list, add add and remove. + *

+ * + * The programmer should provide a no-argument constructor, and one that + * accepts another Collection, as recommended by the Collection interface. + * Unfortunately, there is no way to enforce this in Java. + * + * @author Original author unknown + * @author Bryce McKinlay + * @author Eric Blake + * @see Collection + * @see List + * @see AbstractList + * @see AbstractCollection + * @see ListIterator + * @see LinkedList + * @since 1.2 + * @status updated to 1.4 */ public abstract class AbstractSequentialList extends AbstractList { + /** + * The main constructor, for use by subclasses. + */ + protected AbstractSequentialList() + { + } + /** * Returns a ListIterator over the list, starting from position index. * Subclasses must provide an implementation of this method. * - * @exception IndexOutOfBoundsException if index < 0 || index > size() + * @param index the starting position of the list + * @return the list iterator + * @throws IndexOutOfBoundsException if index < 0 || index > size() */ public abstract ListIterator listIterator(int index); /** - * Add an element to the list at a given index. This implementation obtains a - * ListIterator positioned at the specified index, and then adds the element - * using the ListIterator's add method. + * Insert an element into the list at a given position (optional operation). + * This shifts all existing elements from that position to the end one + * index to the right. This version of add has no return, since it is + * assumed to always succeed if there is no exception. This iteration + * uses listIterator(index).add(o). * - * @param index the position to add the element - * @param o the element to insert - * @exception IndexOutOfBoundsException if index < 0 || index > size() - * @exception UnsupportedOperationException if the iterator returned by - * listIterator(index) does not support the add method. + * @param index the location to insert the item + * @param o the object to insert + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason */ public void add(int index, Object o) { - ListIterator i = listIterator(index); - i.add(o); + listIterator(index).add(o); } /** - * @specnote The spec in the JDK1.3 online docs is wrong. The implementation - * should not call next() to skip over new elements as they are - * added, because iterator.add() should add new elements BEFORE - * the cursor. + * Insert the contents of a collection into the list at a given position + * (optional operation). Shift all elements at that position to the right + * by the number of elements inserted. This operation is undefined if + * this list is modified during the operation (for example, if you try + * to insert a list into itself). + *

+ * + * This implementation grabs listIterator(index), then proceeds to use add + * for each element returned by c's iterator. Sun's online specs are wrong, + * claiming that this also calls next(): listIterator.add() correctly + * skips the added element. + * + * @param index the location to insert the collection + * @param c the collection to insert + * @return true if the list was modified by this action, that is, if c is + * non-empty + * @throws UnsupportedOperationException if this list does not support the + * addAll operation + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @throws ClassCastException if some element of c cannot be added to this + * list due to its type + * @throws IllegalArgumentException if some element of c cannot be added + * to this list for some other reason + * @throws NullPointerException if the specified collection is null + * @see #add(int, Object) */ public boolean addAll(int index, Collection c) { - boolean modified = false; Iterator ci = c.iterator(); int size = c.size(); ListIterator i = listIterator(index); - for (int pos = 0; pos < size; pos++) - { - i.add(ci.next()); - } - return (size > 0); + for (int pos = size; pos > 0; pos--) + i.add(ci.next()); + return size > 0; } + /** + * Get the element at a given index in this list. This implementation + * returns listIterator(index).next(). + * + * @param index the index of the element to be returned + * @return the element at index index in this list + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ public Object get(int index) { - ListIterator i = listIterator(index); - if (index < 0 || index > size()) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size()); - return i.next(); + // This is a legal listIterator position, but an illegal get. + if (index == size()) + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size()); + return listIterator(index).next(); } /** - * Return an Iterator over this List. This implementation returns - * listIterator(). + * Obtain an Iterator over this list, whose sequence is the list order. This + * implementation returns listIterator(). * - * @return an Iterator over this List + * @return an Iterator over the elements of this list, in order */ public Iterator iterator() { return listIterator(); } + /** + * Remove the element at a given position in this list (optional operation). + * Shifts all remaining elements to the left to fill the gap. This + * implementation uses listIterator(index) and ListIterator.remove(). + * + * @param index the position within the list of the object to remove + * @return the object that was removed + * @throws UnsupportedOperationException if this list does not support the + * remove operation + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ public Object remove(int index) { + // This is a legal listIterator position, but an illegal remove. + if (index == size()) + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size()); ListIterator i = listIterator(index); - if (index < 0 || index > size()) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size()); Object removed = i.next(); i.remove(); return removed; } + /** + * Replace an element of this list with another object (optional operation). + * This implementation uses listIterator(index) and ListIterator.set(o). + * + * @param index the position within this list of the element to be replaced + * @param o the object to replace it with + * @return the object that was replaced + * @throws UnsupportedOperationException if this list does not support the + * set operation + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + */ public Object set(int index, Object o) { + // This is a legal listIterator position, but an illegal set. + if (index == size()) + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size()); ListIterator i = listIterator(index); - if (index < 0 || index > size()) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size()); Object old = i.next(); i.set(o); return old; -- cgit v1.2.3