From d9fd7154ec7908eff8bbbce75651eccf51064ac1 Mon Sep 17 00:00:00 2001 From: Bryce McKinlay 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. From-SVN: r48035 --- libjava/java/util/LinkedHashSet.java | 149 +++++++++++++++++++++++++++++++++++ 1 file changed, 149 insertions(+) create mode 100644 libjava/java/util/LinkedHashSet.java (limited to 'libjava/java/util/LinkedHashSet.java') diff --git a/libjava/java/util/LinkedHashSet.java b/libjava/java/util/LinkedHashSet.java new file mode 100644 index 0000000..f98c32e --- /dev/null +++ b/libjava/java/util/LinkedHashSet.java @@ -0,0 +1,149 @@ +/* LinkedHashSet.java -- a set backed by a LinkedHashMap, for linked + list traversal. + Copyright (C) 2001 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +package java.util; + +import java.io.Serializable; + +/** + * This class provides a hashtable-backed implementation of the + * Set interface, with predictable traversal order. + *

+ * + * It uses a hash-bucket approach; that is, hash collisions are handled + * by linking the new node off of the pre-existing node (or list of + * nodes). In this manner, techniques such as linear probing (which + * can cause primary clustering) and rehashing (which does not fit very + * well with Java's method of precomputing hash codes) are avoided. In + * addition, this maintains a doubly-linked list which tracks insertion + * order. Note that the insertion order is not modified if an + * add simply reinserts an element in the set. + *

+ * + * One of the nice features of tracking insertion order is that you can + * copy a set, and regardless of the implementation of the original, + * produce the same results when iterating over the copy. This is possible + * without needing the overhead of TreeSet. + *

+ * + * Under ideal circumstances (no collisions), LinkedHashSet offers O(1) + * performance on most operations. In the worst case (all elements map + * to the same hash code -- very unlikely), most operations are O(n). + *

+ * + * LinkedHashSet accepts the null entry. It is not synchronized, so if + * you need multi-threaded access, consider using:
+ * Set s = Collections.synchronizedSet(new LinkedHashSet(...)); + *

+ * + * The iterators are fail-fast, meaning that any structural + * modification, except for remove() called on the iterator + * itself, cause the iterator to throw a + * {@link ConcurrentModificationException} rather than exhibit + * non-deterministic behavior. + * + * @author Eric Blake + * @see Object#hashCode() + * @see Collection + * @see Set + * @see HashSet + * @see TreeSet + * @see Collections#synchronizedSet(Set) + * @since 1.4 + * @status updated to 1.4 + */ +public class LinkedHashSet extends HashSet + implements Set, Cloneable, Serializable +{ + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -2851667679971038690L; + + /** + * Construct a new, empty HashSet whose backing HashMap has the default + * capacity (11) and loadFacor (0.75). + */ + public LinkedHashSet() + { + super(); + } + + /** + * Construct a new, empty HashSet whose backing HashMap has the supplied + * capacity and the default load factor (0.75). + * + * @param initialCapacity the initial capacity of the backing HashMap + * @throws IllegalArgumentException if the capacity is negative + */ + public LinkedHashSet(int initialCapacity) + { + super(initialCapacity); + } + + /** + * Construct a new, empty HashSet whose backing HashMap has the supplied + * capacity and load factor. + * + * @param initialCapacity the initial capacity of the backing HashMap + * @param loadFactor the load factor of the backing HashMap + * @throws IllegalArgumentException if either argument is negative, or + * if loadFactor is POSITIVE_INFINITY or NaN + */ + public LinkedHashSet(int initialCapacity, float loadFactor) + { + super(initialCapacity, loadFactor); + } + + /** + * Construct a new HashSet with the same elements as are in the supplied + * collection (eliminating any duplicates, of course). The backing storage + * has twice the size of the collection, or the default size of 11, + * whichever is greater; and the default load factor (0.75). + * + * @param c a collection of initial set elements + * @throws NullPointerException if c is null + */ + public LinkedHashSet(Collection c) + { + super(c); + } + + /** + * Helper method which initializes the backing Map. + * + * @param capacity the initial capacity + * @param load the initial load factor + * @return the backing HashMap + */ + HashMap init(int capacity, float load) + { + return new LinkedHashMap(capacity, load); + } + +} -- cgit v1.1