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/TreeSet.java | 333 ++++++++++++++++++++++++++++------------- 1 file changed, 225 insertions(+), 108 deletions(-) (limited to 'libjava/java/util/TreeSet.java') diff --git a/libjava/java/util/TreeSet.java b/libjava/java/util/TreeSet.java index ba85213..3d2ef3d 100644 --- a/libjava/java/util/TreeSet.java +++ b/libjava/java/util/TreeSet.java @@ -1,4 +1,4 @@ -/* TreeSet.java -- a class providing a TreeMap-backet SortedSet +/* TreeSet.java -- a class providing a TreeMap-backed SortedSet Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -33,54 +33,91 @@ import java.io.ObjectInputStream; import java.io.ObjectOutputStream; /** - * This class provides a TreeMap-backed implementation of the - * SortedSet interface. + * This class provides a TreeMap-backed implementation of the SortedSet + * interface. The elements will be sorted according to their natural + * order, or according to the provided Comparator.

* - * Each element in the Set is a key in the backing TreeMap; each key - * maps to a static token, denoting that the key does, in fact, exist. + * Most operations are O(log n), but there is so much overhead that this + * makes small sets expensive. Note that the ordering must be consistent + * with equals to correctly implement the Set interface. If this + * condition is violated, the set is still well-behaved, but you may have + * suprising results when comparing it to other sets.

* - * Most operations are O(log n). + * This implementation is not synchronized. If you need to share this between + * multiple threads, do something like:
+ * SortedSet s + * = Collections.synchronizedSortedSet(new TreeSet(...));

* - * TreeSet is a part of the JDK1.2 Collections API. + * The iterators are fail-fast, meaning that any structural + * modification, except for remove() called on the iterator + * itself, cause the iterator to throw a + * ConcurrentModificationException rather than exhibit + * non-deterministic behavior. * - * @author Jon Zeppieri + * @author Jon Zeppieri + * @author Bryce McKinlay + * @author Eric Blake + * @see Collection + * @see Set + * @see HashSet + * @see LinkedHashSet + * @see Comparable + * @see Comparator + * @see Collections#synchronizedSortedSet(SortedSet) + * @see TreeMap + * @since 1.2 + * @status updated to 1.4 */ - public class TreeSet extends AbstractSet implements SortedSet, Cloneable, Serializable { - /** The TreeMap which backs this Set */ - transient SortedMap map; + /** + * Compatible with JDK 1.2. + */ + private static final long serialVersionUID = -2479143000061671589L; - static final long serialVersionUID = -2479143000061671589L; + /** + * The SortedMap which backs this Set. + */ + // Not final because of readObject. This will always be one of TreeMap or + // TreeMap.SubMap, which both extend AbstractMap. + private transient SortedMap map; /** - * Construct a new TreeSet whose backing TreeMap using the "natural" - * ordering of keys. + * Construct a new TreeSet whose backing TreeMap using the "natural" + * ordering of keys. Elements that are not mutually comparable will cause + * ClassCastExceptions down the road. + * + * @see Comparable */ public TreeSet() { map = new TreeMap(); } - /** - * Construct a new TreeSet whose backing TreeMap uses the supplied - * Comparator. + /** + * Construct a new TreeSet whose backing TreeMap uses the supplied + * Comparator. Elements that are not mutually comparable will cause + * ClassCastExceptions down the road. * - * @param oComparator the Comparator this Set will use + * @param comparator the Comparator this Set will use */ public TreeSet(Comparator comparator) { map = new TreeMap(comparator); } - /** + /** * Construct a new TreeSet whose backing TreeMap uses the "natural" * orering of the keys and which contains all of the elements in the - * supplied Collection. + * supplied Collection. This runs in n*log(n) time. * - * @param oCollection the new Set will be initialized with all - * of the elements in this Collection + * @param collection the new Set will be initialized with all + * of the elements in this Collection + * @throws ClassCastException if the elements of the collection are not + * comparable + * @throws NullPointerException if the collection is null + * @see Comparable */ public TreeSet(Collection collection) { @@ -93,54 +130,57 @@ public class TreeSet extends AbstractSet * SortedSet and containing all of the elements in the supplied SortedSet. * This constructor runs in linear time. * - * @param sortedSet the new TreeSet will use this SortedSet's - * comparator and will initialize itself - * with all of the elements in this SortedSet + * @param sortedSet the new TreeSet will use this SortedSet's comparator + * and will initialize itself with all its elements + * @throws NullPointerException if sortedSet is null */ public TreeSet(SortedSet sortedSet) { - TreeMap map = new TreeMap(sortedSet.comparator()); - int i = 0; + map = new TreeMap(sortedSet.comparator()); Iterator itr = sortedSet.iterator(); - map.putKeysLinear(itr, sortedSet.size()); - this.map = map; + ((TreeMap) map).putKeysLinear(itr, sortedSet.size()); } - - /* This private constructor is used to implement the subSet() calls around - a backing TreeMap.SubMap. */ - TreeSet(SortedMap backingMap) + + /** + * This private constructor is used to implement the subSet() calls around + * a backing TreeMap.SubMap. + * + * @param backingMap the submap + */ + private TreeSet(SortedMap backingMap) { map = backingMap; } - /** + /** * Adds the spplied Object to the Set if it is not already in the Set; - * returns true if the element is added, false otherwise + * returns true if the element is added, false otherwise. * - * @param obj the Object to be added to this Set + * @param obj the Object to be added to this Set + * @throws ClassCastException if the element cannot be compared with objects + * already in the set */ public boolean add(Object obj) { - return (map.put(obj, Boolean.TRUE) == null); + return map.put(obj, "") == null; } /** * Adds all of the elements in the supplied Collection to this TreeSet. * - * @param c All of the elements in this Collection - * will be added to the Set. - * - * @return true if the Set is altered, false otherwise + * @param c The collection to add + * @return true if the Set is altered, false otherwise + * @throws NullPointerException if c is null + * @throws ClassCastException if an element in c cannot be compared with + * objects already in the set */ public boolean addAll(Collection c) { boolean result = false; - int size = c.size(); + int pos = c.size(); Iterator itr = c.iterator(); - - for (int i = 0; i < size; i++) - result |= (map.put(itr.next(), Boolean.TRUE) == null); - + while (--pos >= 0) + result |= (map.put(itr.next(), "") == null); return result; } @@ -152,137 +192,214 @@ public class TreeSet extends AbstractSet map.clear(); } - /** Returns a shallow copy of this Set. */ + /** + * Returns a shallow copy of this Set. The elements are not cloned. + * + * @return the cloned set + */ public Object clone() { TreeSet copy = null; try { copy = (TreeSet) super.clone(); + // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts. + copy.map = (SortedMap) ((AbstractMap) map).clone(); } catch (CloneNotSupportedException x) - { + { + // Impossible result. } - copy.map = (SortedMap) ((TreeMap) map).clone(); return copy; } - /** Returns this Set's comparator */ + /** + * Returns this Set's comparator. + * + * @return the comparator, or null if the set uses natural ordering + */ public Comparator comparator() { return map.comparator(); } - /** - * Returns true if this Set contains the supplied Object, - * false otherwise + /** + * Returns true if this Set contains the supplied Object, false otherwise. * - * @param oObject the Object whose existence in the Set is - * being tested + * @param obj the Object to check for + * @return true if it is in the set + * @throws ClassCastException if obj cannot be compared with objects + * already in the set */ public boolean contains(Object obj) { return map.containsKey(obj); } - /** Returns true if this Set has size 0, false otherwise */ - public boolean isEmpty() + /** + * Returns the first (by order) element in this Set. + * + * @return the first element + * @throws NoSuchElementException if the set is empty + */ + public Object first() { - return map.isEmpty(); + return map.firstKey(); } - /** Returns the number of elements in this Set */ - public int size() + /** + * Returns a view of this Set including all elements less than + * to. The returned set is backed by the original, so changes + * in one appear in the other. The subset will throw an + * {@link IllegalArgumentException} for any attempt to access or add an + * element beyond the specified cutoff. The returned set does not include + * the endpoint; if you want inclusion, pass the successor element. + * + * @param to the (exclusive) cutoff point + * @return a view of the set less than the cutoff + * @throws ClassCastException if to is not compatible with + * the comparator (or is not Comparable, for natural ordering) + * @throws NullPointerException if to is null, but the comparator does not + * tolerate null elements + */ + public SortedSet headSet(Object to) { - return map.size(); + return new TreeSet(map.headMap(to)); } - /** - * If the supplied Object is in this Set, it is removed, and true is - * returned; otherwise, false is returned. + /** + * Returns true if this Set has size 0, false otherwise. * - * @param obj the Object we are attempting to remove - * from this Set + * @return true if the set is empty */ - public boolean remove(Object obj) + public boolean isEmpty() { - return (map.remove(obj) != null); + return map.isEmpty(); } - /** Returns the first (by order) element in this Set */ - public Object first() + /** + * Returns in Iterator over the elements in this TreeSet, which traverses + * in ascending order. + * + * @return an iterator + */ + public Iterator iterator() { - return map.firstKey(); + return map.keySet().iterator(); } - /** Returns the last (by order) element in this Set */ + /** + * Returns the last (by order) element in this Set. + * + * @return the last element + * @throws NoSuchElementException if the set is empty + */ public Object last() { return map.lastKey(); } /** - * Returns a view of this Set including all elements in the interval - * [oFromElement, oToElement). + * If the supplied Object is in this Set, it is removed, and true is + * returned; otherwise, false is returned. * - * @param from the resultant view will contain all - * elements greater than or equal to this element - * @param to the resultant view will contain all - * elements less than this element + * @param obj the Object to remove from this Set + * @return true if the set was modified + * @throws ClassCastException if obj cannot be compared to set elements */ - public SortedSet subSet(Object from, Object to) + public boolean remove(Object obj) { - return new TreeSet(map.subMap(from, to)); + return map.remove(obj) != null; } /** - * Returns a view of this Set including all elements less than oToElement + * Returns the number of elements in this Set * - * @param toElement the resultant view will contain all - * elements less than this element + * @return the set size */ - public SortedSet headSet(Object to) + public int size() { - return new TreeSet(map.headMap(to)); + return map.size(); } /** - * Returns a view of this Set including all elements greater than or - * equal to oFromElement. + * Returns a view of this Set including all elements greater or equal to + * from and less than to (a half-open interval). + * The returned set is backed by the original, so changes in one appear in + * the other. The subset will throw an {@link IllegalArgumentException} + * for any attempt to access or add an element beyond the specified cutoffs. + * The returned set includes the low endpoint but not the high; if you want + * to reverse this behavior on either end, pass in the successor element. * - * @param from the resultant view will contain all - * elements greater than or equal to this element + * @param from the (inclusive) low cutoff point + * @param to the (exclusive) high cutoff point + * @return a view of the set between the cutoffs + * @throws ClassCastException if either cutoff is not compatible with + * the comparator (or is not Comparable, for natural ordering) + * @throws NullPointerException if from or to is null, but the comparator + * does not tolerate null elements + * @throws IllegalArgumentException if from is greater than to */ - public SortedSet tailSet(Object from) + public SortedSet subSet(Object from, Object to) { - return new TreeSet(map.tailMap(from)); + return new TreeSet(map.subMap(from, to)); } - /** Returns in Iterator over the elements in this TreeSet */ - public Iterator iterator() + /** + * Returns a view of this Set including all elements greater or equal to + * from. The returned set is backed by the original, so + * changes in one appear in the other. The subset will throw an + * {@link IllegalArgumentException} for any attempt to access or add an + * element beyond the specified cutoff. The returned set includes the + * endpoint; if you want to exclude it, pass in the successor element. + * + * @param from the (inclusive) low cutoff point + * @return a view of the set above the cutoff + * @throws ClassCastException if from is not compatible with + * the comparator (or is not Comparable, for natural ordering) + * @throws NullPointerException if from is null, but the comparator + * does not tolerate null elements + */ + public SortedSet tailSet(Object from) { - return map.keySet().iterator(); + return new TreeSet(map.tailMap(from)); } - private void writeObject(ObjectOutputStream out) throws IOException + /** + * Serializes this object to the given stream. + * + * @param s the stream to write to + * @throws IOException if the underlying stream fails + * @serialData the comparator (Object), followed by the set size + * (int), the the elements in sorted order (Object) + */ + private void writeObject(ObjectOutputStream s) throws IOException { + s.defaultWriteObject(); Iterator itr = map.keySet().iterator(); - int size = map.size(); - - out.writeObject(map.comparator()); - out.writeInt(size); - - for (int i = 0; i < size; i++) - out.writeObject(itr.next()); + int pos = map.size(); + s.writeObject(map.comparator()); + s.writeInt(pos); + while (--pos >= 0) + s.writeObject(itr.next()); } - private void readObject(ObjectInputStream in) + /** + * Deserializes this object from the given stream. + * + * @param s the stream to read from + * @throws ClassNotFoundException if the underlying stream fails + * @throws IOException if the underlying stream fails + * @serialData the comparator (Object), followed by the set size + * (int), the the elements in sorted order (Object) + */ + private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { - Comparator comparator = (Comparator) in.readObject(); - int size = in.readInt(); - TreeMap map = new TreeMap(comparator); - map.putFromObjStream(in, size, false); - this.map = map; + s.defaultReadObject(); + Comparator comparator = (Comparator) s.readObject(); + int size = s.readInt(); + map = new TreeMap(comparator); + ((TreeMap) map).putFromObjStream(s, size, false); } } -- cgit v1.1