diff options
Diffstat (limited to 'libjava/java/util')
| -rw-r--r-- | libjava/java/util/Collection.java | 75 | ||||
| -rw-r--r-- | libjava/java/util/Comparator.java | 71 | ||||
| -rw-r--r-- | libjava/java/util/Enumeration.java | 15 | ||||
| -rw-r--r-- | libjava/java/util/HashMap.java | 812 | ||||
| -rw-r--r-- | libjava/java/util/Iterator.java | 46 | ||||
| -rw-r--r-- | libjava/java/util/LinkedHashMap.java | 474 | ||||
| -rw-r--r-- | libjava/java/util/List.java | 345 | ||||
| -rw-r--r-- | libjava/java/util/ListIterator.java | 118 | ||||
| -rw-r--r-- | libjava/java/util/Map.java | 270 | ||||
| -rw-r--r-- | libjava/java/util/RandomAccess.java | 53 | ||||
| -rw-r--r-- | libjava/java/util/Set.java | 191 | ||||
| -rw-r--r-- | libjava/java/util/SortedMap.java | 126 | ||||
| -rw-r--r-- | libjava/java/util/SortedSet.java | 130 |
13 files changed, 2114 insertions, 612 deletions
diff --git a/libjava/java/util/Collection.java b/libjava/java/util/Collection.java index b7dbb69..11baa30 100644 --- a/libjava/java/util/Collection.java +++ b/libjava/java/util/Collection.java @@ -1,5 +1,5 @@ /* Collection.java -- Interface that represents a collection of objects - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,9 +25,6 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Maybe some more @see clauses would be helpful. - package java.util; /** @@ -57,9 +54,23 @@ package java.util; * and returns a collection containing the same elements (that is, creates a * copy of the argument using its own implementation). * - * @see java.util.List - * @see java.util.Set - * @see java.util.AbstractCollection + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see List + * @see Set + * @see Map + * @see SortedSet + * @see SortedMap + * @see HashSet + * @see TreeSet + * @see ArrayList + * @see LinkedList + * @see Vector + * @see Collections + * @see Arrays + * @see AbstractCollection + * @since 1.2 + * @status updated to 1.4 */ public interface Collection { @@ -67,12 +78,12 @@ public interface Collection * Add an element to this collection. * * @param o the object to add. - * @returns true if the collection was modified as a result of this action. - * @exception UnsupportedOperationException if this collection does not + * @return true if the collection was modified as a result of this action. + * @throws UnsupportedOperationException if this collection does not * support the add operation. - * @exception ClassCastException if o cannot be added to this collection due + * @throws ClassCastException if o cannot be added to this collection due * to its type. - * @exception IllegalArgumentException if o cannot be added to this + * @throws IllegalArgumentException if o cannot be added to this * collection for some other reason. */ boolean add(Object o); @@ -81,12 +92,12 @@ public interface Collection * Add the contents of a given collection to this collection. * * @param c the collection to add. - * @returns true if the collection was modified as a result of this action. - * @exception UnsupportedOperationException if this collection does not + * @return true if the collection was modified as a result of this action. + * @throws UnsupportedOperationException if this collection does not * support the addAll operation. - * @exception ClassCastException if some element of c cannot be added to this + * @throws ClassCastException if some element of c cannot be added to this * collection due to its type. - * @exception IllegalArgumentException if some element of c cannot be added + * @throws IllegalArgumentException if some element of c cannot be added * to this collection for some other reason. */ boolean addAll(Collection c); @@ -95,7 +106,7 @@ public interface Collection * Clear the collection, such that a subsequent call to isEmpty() would * return true. * - * @exception UnsupportedOperationException if this collection does not + * @throws UnsupportedOperationException if this collection does not * support the clear operation. */ void clear(); @@ -105,7 +116,7 @@ public interface Collection * elements. * * @param o the element to look for. - * @returns true if this collection contains at least one element e such that + * @return true if this collection contains at least one element e such that * <code>o == null ? e == null : o.equals(e)</code>. */ boolean contains(Object o); @@ -114,7 +125,7 @@ public interface Collection * Test whether this collection contains every element in a given collection. * * @param c the collection to test for. - * @returns true if for every element o in c, contains(o) would return true. + * @return true if for every element o in c, contains(o) would return true. */ boolean containsAll(Collection c); @@ -132,7 +143,7 @@ public interface Collection * preserve the symmetry of the relation. * * @param o the object to compare to this collection. - * @returns true if the o is equal to this collection. + * @return true if the o is equal to this collection. */ boolean equals(Object o); @@ -148,21 +159,21 @@ public interface Collection * method renders it impossible to correctly implement both Set and List, as * the required implementations are mutually exclusive. * - * @returns a hash code for this collection. + * @return a hash code for this collection. */ int hashCode(); /** * Test whether this collection is empty, that is, if size() == 0. * - * @returns true if this collection contains no elements. + * @return true if this collection contains no elements. */ boolean isEmpty(); /** * Obtain an Iterator over this collection. * - * @returns an Iterator over the elements of this collection, in any order. + * @return an Iterator over the elements of this collection, in any order. */ Iterator iterator(); @@ -172,9 +183,9 @@ public interface Collection * : o.equals(e)</code>. * * @param o the object to remove. - * @returns true if the collection changed as a result of this call, that is, + * @return true if the collection changed as a result of this call, that is, * if the collection contained at least one occurrence of o. - * @exception UnsupportedOperationException if this collection does not + * @throws UnsupportedOperationException if this collection does not * support the remove operation. */ boolean remove(Object o); @@ -183,8 +194,8 @@ public interface Collection * Remove all elements of a given collection from this collection. That is, * remove every element e such that c.contains(e). * - * @returns true if this collection was modified as a result of this call. - * @exception UnsupportedOperationException if this collection does not + * @return true if this collection was modified as a result of this call. + * @throws UnsupportedOperationException if this collection does not * support the removeAll operation. */ boolean removeAll(Collection c); @@ -193,8 +204,8 @@ public interface Collection * Remove all elements of this collection that are not contained in a given * collection. That is, remove every element e such that !c.contains(e). * - * @returns true if this collection was modified as a result of this call. - * @exception UnsupportedOperationException if this collection does not + * @return true if this collection was modified as a result of this call. + * @throws UnsupportedOperationException if this collection does not * support the retainAll operation. */ boolean retainAll(Collection c); @@ -202,14 +213,14 @@ public interface Collection /** * Get the number of elements in this collection. * - * @returns the number of elements in the collection. + * @return the number of elements in the collection. */ int size(); /** * Copy the current contents of this collection into an array. * - * @returns an array of type Object[] and length equal to the size of this + * @return an array of type Object[] and length equal to the size of this * collection, containing the elements currently in this collection, in * any order. */ @@ -227,9 +238,9 @@ public interface Collection * if it is known that this collection does not contain any null elements. * * @param a the array to copy this collection into. - * @returns an array containing the elements currently in this collection, in + * @return an array containing the elements currently in this collection, in * any order. - * @exception ArrayStoreException if the type of any element of the + * @throws ArrayStoreException if the type of any element of the * collection is not a subtype of the element type of a. */ Object[] toArray(Object[] a); diff --git a/libjava/java/util/Comparator.java b/libjava/java/util/Comparator.java index fc61fc3..8522301 100644 --- a/libjava/java/util/Comparator.java +++ b/libjava/java/util/Comparator.java @@ -29,36 +29,67 @@ package java.util; /** * Interface for objects that specify an ordering between objects. The ordering - * can be <EM>total</EM>, such that two objects only compare equal if they are - * equal by the equals method, or <EM>partial</EM> such that this is not - * necessarily true. For example, a case-sensitive dictionary order comparison - * of Strings is total, but if it is case-insensitive it is partial, because - * "abc" and "ABC" compare as equal even though "abc".equals("ABC") returns - * false. + * should be <em>total</em>, such that any two objects of the correct type + * can be compared, and the comparison is reflexive, anti-symmetric, and + * transitive. It is also recommended that the comparator be <em>consistent + * with equals</em>, although this is not a strict requirement. A relation + * is consistent with equals if these two statements always have the same + * results (if no exceptions occur):<br> + * <code>compare((Object) e1, (Object) e2) == 0</code> and + * <code>e1.equals((Object) e2)</code><br> + * Comparators that violate consistency with equals may cause strange behavior + * in sorted lists and sets. For example, a case-sensitive dictionary order + * comparison of Strings is consistent with equals, but if it is + * case-insensitive it is not, because "abc" and "ABC" compare as equal even + * though "abc".equals("ABC") returns false. * <P> * In general, Comparators should be Serializable, because when they are passed * to Serializable data structures such as SortedMap or SortedSet, the entire * data structure will only serialize correctly if the comparator is * Serializable. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Comparable + * @see TreeMap + * @see TreeSet + * @see SortedMap + * @see SortedSet + * @see Arrays#sort(Object[], Comparator) + * @see java.io.Serializable + * @since 1.2 + * @status updated to 1.4 */ public interface Comparator { /** * Return an integer that is negative, zero or positive depending on whether * the first argument is less than, equal to or greater than the second - * according to this ordering. This method should obey the following contract: - * <UL> - * <LI>if compare(a, b) < 0 then compare(b, a) > 0</LI> - * <LI>if compare(a, b) throws an exception, so does compare(b, a)</LI> - * <LI>if compare(a, b) < 0 and compare(b, c) < 0 then compare(a, c) - * < 0</LI> - * <LI>if a.equals(b) or both a and b are null, then compare(a, b) == 0. - * The converse need not be true, but if it is, this Comparator - * specifies a <EM>total</EM> ordering.</LI> - * </UL> + * according to this ordering. This method should obey the following + * contract: + * <ul> + * <li>if compare(a, b) < 0 then compare(b, a) > 0</li> + * <li>if compare(a, b) throws an exception, so does compare(b, a)</li> + * <li>if compare(a, b) < 0 and compare(b, c) < 0 then compare(a, c) + * < 0</li> + * <li>if compare(a, b) == 0 then compare(a, c) and compare(b, c) must + * have the same sign</li + * </ul> + * To be consistent with equals, the following additional constraint is + * in place: + * <ul> + * <li>if a.equals(b) or both a and b are null, then + * compare(a, b) == 0.</li> + * </ul><p> * + * Although it is permissible for a comparator to provide an order + * inconsistent with equals, that should be documented. + * + * @param o1 the first object + * @param o2 the second object + * @return the comparison * @throws ClassCastException if the elements are not of types that can be - * compared by this ordering. + * compared by this ordering. */ int compare(Object o1, Object o2); @@ -66,8 +97,12 @@ public interface Comparator * Return true if the object is equal to this object. To be * considered equal, the argument object must satisfy the constraints * of <code>Object.equals()</code>, be a Comparator, and impose the - * same ordering as this Comparator. + * same ordering as this Comparator. The default implementation + * inherited from Object is usually adequate. + * * @param obj The object + * @return true if it is a Comparator that imposes the same order + * @see Object#equals(Object) */ boolean equals(Object obj); } diff --git a/libjava/java/util/Enumeration.java b/libjava/java/util/Enumeration.java index 66624bd..5bcfbee 100644 --- a/libjava/java/util/Enumeration.java +++ b/libjava/java/util/Enumeration.java @@ -42,7 +42,12 @@ package java.util; * be obtained by the enumeration method in class Collections. * * @author Warren Levy <warrenl@cygnus.com> - * @date August 25, 1998. + * @author Eric Blake <ebb9@email.byu.edu> + * @see Iterator + * @see Hashtable + * @see Vector + * @since 1.0 + * @status updated to 1.4 */ public interface Enumeration { @@ -50,8 +55,8 @@ public interface Enumeration * Tests whether there are elements remaining in the enumeration. * * @return true if there is at least one more element in the enumeration, - * that is, if the next call to nextElement will not throw a - * NoSuchElementException. + * that is, if the next call to nextElement will not throw a + * NoSuchElementException. */ boolean hasMoreElements(); @@ -59,7 +64,7 @@ public interface Enumeration * Obtain the next element in the enumeration. * * @return the next element in the enumeration - * @exception NoSuchElementException if there are no more elements + * @throws NoSuchElementException if there are no more elements */ - Object nextElement() throws NoSuchElementException; + Object nextElement(); } diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java index 4bc88b7..b75718f 100644 --- a/libjava/java/util/HashMap.java +++ b/libjava/java/util/HashMap.java @@ -1,6 +1,6 @@ /* HashMap.java -- a class providing a basic hashtable data structure, mapping Object --> Object - 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. @@ -37,83 +37,137 @@ import java.io.ObjectOutputStream; // a bug in here, chances are you should make a similar change to the Hashtable // code. +// NOTE: This implementation has some nasty coding style in order to +// support LinkedHashMap, which extends this. + /** * This class provides a hashtable-backed implementation of the - * Map interface. + * Map interface. + * <p> * - * 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 casue primary clustering) and - * rehashing (which does not fit very well with Java's method of - * precomputing hash codes) are avoided. + * 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. + * <p> * - * Under ideal circumstances (no collisions, HashMap offers O(1) + * Under ideal circumstances (no collisions), HashMap offers O(1) * performance on most operations (<pre>containsValue()</pre> is, - * of course, O(n)). In the worst case (all keys map to the same + * of course, O(n)). In the worst case (all keys map to the same * hash code -- very unlikely), most operations are O(n). + * <p> * - * HashMap is part of the JDK1.2 Collections API. It differs from + * HashMap is part of the JDK1.2 Collections API. It differs from * Hashtable in that it accepts the null key and null values, and it * does not support "Enumeration views." + * <p> + * + * The iterators are <i>fail-fast</i>, meaning that any structural + * modification, except for <code>remove()</code> called on the iterator + * itself, cause the iterator to throw a + * <code>ConcurrentModificationException</code> rather than exhibit + * non-deterministic behavior. * - * @author Jon Zeppieri - * @author Jochen Hoenicke - * @author Bryce McKinlay + * @author Jon Zeppieri + * @author Jochen Hoenicke + * @author Bryce McKinlay + * @author Eric Blake <ebb9@email.byu.edu> + * @see Object#hashCode() + * @see Collection + * @see Map + * @see TreeMap + * @see LinkedHashMap + * @see IdentityHashMap + * @see Hashtable + * @since 1.2 */ public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { - /** Default number of buckets. This is the value the JDK 1.3 uses. Some - * early documentation specified this value as 101. That is incorrect. */ - private static final int DEFAULT_CAPACITY = 11; - /** The defaulty load factor; this is explicitly specified by the spec. */ - private static final float DEFAULT_LOAD_FACTOR = 0.75f; + /** + * Default number of buckets. This is the value the JDK 1.3 uses. Some + * early documentation specified this value as 101. That is incorrect. + */ + static final int DEFAULT_CAPACITY = 11; + + /** + * The default load factor; this is explicitly specified by the spec. + */ + static final float DEFAULT_LOAD_FACTOR = 0.75f; + + /** "enum" of iterator types. */ + static final int KEYS = 0, + VALUES = 1, + ENTRIES = 2; + /** + * Compatible with JDK 1.2. + */ private static final long serialVersionUID = 362498820763181265L; - /** - * The rounded product of the capacity and the load factor; when the number + /** + * The rounded product of the capacity and the load factor; when the number * of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>. * @serial */ int threshold; - /** Load factor of this HashMap: used in computing the threshold. + /** + * Load factor of this HashMap: used in computing the threshold. * @serial */ - float loadFactor = DEFAULT_LOAD_FACTOR; + final float loadFactor; - /** - * Array containing the actual key-value mappings + /** + * Array containing the actual key-value mappings. */ - transient Entry[] buckets; + transient HashEntry[] buckets; - /** - * counts the number of modifications this HashMap has undergone, used + /** + * Counts the number of modifications this HashMap has undergone, used * by Iterators to know when to throw ConcurrentModificationExceptions. */ transient int modCount; - /** the size of this HashMap: denotes the number of key-value pairs */ + /** + * The size of this HashMap: denotes the number of key-value pairs. + */ transient int size; /** * Class to represent an entry in the hash table. Holds a single key-value - * pair. + * pair. This is extended again in LinkedHashMap. See {@link clone()} + * for why this must be Cloneable. */ - static class Entry extends BasicMapEntry + static class HashEntry extends BasicMapEntry implements Cloneable { - Entry next; - - Entry(Object key, Object value) + /** The next entry in the linked list. */ + HashEntry next; + + /** + * Simple constructor. + * @param key the key + * @param value the value + */ + HashEntry(Object key, Object value) { super(key, value); } + + /** + * Called when this entry is removed from the map. This version simply + * returns the value, but in LinkedHashMap, it must also do bookkeeping. + * @return the value of this key as it is removed. + */ + Object cleanup() + { + return value; + } } /** - * construct a new HashMap with the default capacity (11) and the default + * Construct a new HashMap with the default capacity (11) and the default * load factor (0.75). */ public HashMap() @@ -122,237 +176,279 @@ public class HashMap extends AbstractMap } /** - * construct a new HashMap from the given Map - * - * every element in Map t will be put into this new HashMap + * Construct a new HashMap from the given Map, with initial capacity + * the greater of the size of <code>m</code> or the default of 11. + * <p> * - * @param t a Map whose key / value pairs will be put into - * the new HashMap. <b>NOTE: key / value pairs - * are not cloned in this constructor</b> + * Every element in Map m will be put into this new HashMap. + * + * @param m a Map whose key / value pairs will be put into + * the new HashMap. <b>NOTE: key / value pairs + * are not cloned in this constructor.</b> + * @throws NullPointerException if m is null */ public HashMap(Map m) { - int size = Math.max(m.size() * 2, DEFAULT_CAPACITY); - buckets = new Entry[size]; - threshold = (int) (size * loadFactor); - putAll(m); + this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); + putAllInternal(m); } /** - * construct a new HashMap with a specific inital capacity - * - * @param initialCapacity the initial capacity of this HashMap (>=0) + * Construct a new HashMap with a specific inital capacity and + * default load factor of 0.75. * - * @throws IllegalArgumentException if (initialCapacity < 0) + * @param initialCapacity the initial capacity of this HashMap (>=0) + * @throws IllegalArgumentException if (initialCapacity < 0) */ - public HashMap(int initialCapacity) throws IllegalArgumentException + public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** - * construct a new HashMap with a specific inital capacity and load factor + * Construct a new HashMap with a specific inital capacity and load factor. * - * @param initialCapacity the initial capacity (>=0) - * @param loadFactor the load factor - * - * @throws IllegalArgumentException if (initialCapacity < 0) || - * (loadFactor <= 0) + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (>0, not NaN) + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) */ public HashMap(int initialCapacity, float loadFactor) - throws IllegalArgumentException { if (initialCapacity < 0) - throw new IllegalArgumentException("Illegal Initial Capacity: " - + initialCapacity); - if (loadFactor <= 0) - throw new IllegalArgumentException("Illegal Load Factor: " + loadFactor); + throw new IllegalArgumentException("Illegal Capacity: " + + initialCapacity); + if (! (loadFactor > 0)) // check for NaN too + throw new IllegalArgumentException("Illegal Load: " + loadFactor); if (initialCapacity == 0) initialCapacity = 1; - buckets = new Entry[initialCapacity]; + buckets = new HashEntry[initialCapacity]; this.loadFactor = loadFactor; - this.threshold = (int) (initialCapacity * loadFactor); + threshold = (int) (initialCapacity * loadFactor); } - /** returns the number of kay-value mappings currently in this Map */ + /** + * Returns the number of kay-value mappings currently in this Map + * @return the size + */ public int size() { return size; } - /** returns true if there are no key-value mappings currently in this Map */ + /** + * Returns true if there are no key-value mappings currently in this Map + * @return <code>size() == 0</code> + */ public boolean isEmpty() { return size == 0; } /** - * returns true if this HashMap contains a value <pre>o</pre>, such that + * Returns true if this HashMap contains a value <pre>o</pre>, such that * <pre>o.equals(value)</pre>. * - * @param value the value to search for in this Hashtable + * @param value the value to search for in this HashMap + * @return true if at least one key maps to the value */ public boolean containsValue(Object value) { - for (int i = 0; i < buckets.length; i++) + for (int i = buckets.length - 1; i >= 0; i--) { - Entry e = buckets[i]; - while (e != null) - { - if (value == null ? e.value == null : value.equals(e.value)) - return true; - e = e.next; - } + HashEntry e = buckets[i]; + while (e != null) + { + if (value == null ? e.value == null : value.equals(e.value)) + return true; + e = e.next; + } } return false; } - /** - * returns true if the supplied object equals (<pre>equals()</pre>) a key - * in this HashMap + /** + * Returns true if the supplied object <pre>equals()</pre> a key + * in this HashMap. * - * @param key the key to search for in this HashMap + * @param key the key to search for in this HashMap + * @return true if the key is in the table + * @see #containsValue(Object) */ public boolean containsKey(Object key) { int idx = hash(key); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - return true; - e = e.next; + return true; + e = e.next; } return false; } /** - * return the value in this Hashtable associated with the supplied key, or <pre>null</pre> - * if the key maps to nothing + * Return the value in this HashMap associated with the supplied key, + * or <pre>null</pre> if the key maps to nothing. NOTE: Since the value + * could also be null, you must use containsKey to see if this key + * actually maps to something. * - * @param key the key for which to fetch an associated value + * @param key the key for which to fetch an associated value + * @return what the key maps to, if present + * @see #put(Object, Object) + * @see #containsKey(Object) */ public Object get(Object key) { int idx = hash(key); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - return e.value; - e = e.next; + return e.value; + e = e.next; } return null; } /** - * puts the supplied value into the Map, mapped by the supplied key + * Puts the supplied value into the Map, mapped by the supplied key. + * The value may be retrieved by any object which <code>equals()</code> + * this key. NOTE: Since the prior value could also be null, you must + * first use containsKey if you want to see if you are replacing the + * key's mapping. * - * @param key the HashMap key used to locate the value - * @param value the value to be stored in the HashMap + * @param key the key used to locate the value + * @param value the value to be stored in the HashMap + * @return the prior mapping of the key, or null if there was none + * @see #get(Object) + * @see Object#equals(Object) */ public Object put(Object key, Object value) { modCount++; int idx = hash(key); - Entry e = buckets[idx]; - + HashEntry e = buckets[idx]; + while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - { - Object r = e.value; - e.value = value; - return r; - } - else - { - e = e.next; - } + // Must use this method for necessary bookkeeping in LinkedHashMap. + return e.setValue(value); + else + e = e.next; } - + // At this point, we know we need to add a new entry. if (++size > threshold) { - rehash(); - // Need a new hash value to suit the bigger table. - idx = hash(key); + rehash(); + // Need a new hash value to suit the bigger table. + idx = hash(key); } - e = new Entry(key, value); - + // LinkedHashMap cannot override put(), hence this call. + addEntry(key, value, idx, true); + return null; + } + + /** + * Helper method for put, that creates and adds a new Entry. This is + * overridden in LinkedHashMap for bookkeeping purposes. + * + * @param key the key of the new Entry + * @param value the value + * @param idx the index in buckets where the new Entry belongs + * @param callRemove Whether to call the removeEldestEntry method. + * @see #put(Object, Object) + */ + void addEntry(Object key, Object value, int idx, boolean callRemove) + { + HashEntry e = new HashEntry(key, value); + e.next = buckets[idx]; buckets[idx] = e; - - return null; } /** - * removes from the HashMap and returns the value which is mapped by the - * supplied key; if the key maps to nothing, then the HashMap remains unchanged, - * and <pre>null</pre> is returned + * Removes from the HashMap and returns the value which is mapped by the + * supplied key. If the key maps to nothing, then the HashMap remains + * unchanged, and <pre>null</pre> is returned. NOTE: Since the value + * could also be null, you must use containsKey to see if you are + * actually removing a mapping. * - * @param key the key used to locate the value to remove from the HashMap + * @param key the key used to locate the value to remove + * @return whatever the key mapped to, if present */ public Object remove(Object key) { modCount++; int idx = hash(key); - Entry e = buckets[idx]; - Entry last = null; + HashEntry e = buckets[idx]; + HashEntry last = null; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - { - if (last == null) - buckets[idx] = e.next; - else - last.next = e.next; - size--; - return e.value; - } - last = e; - e = e.next; + { + if (last == null) + buckets[idx] = e.next; + else + last.next = e.next; + size--; + // Method call necessary for LinkedHashMap to work correctly. + return e.cleanup(); + } + last = e; + e = e.next; } return null; } + /** + * Copies all elements of the given map into this hashtable. If this table + * already has a mapping for a key, the new mapping replaces the current + * one. + * + * @param m the map to be hashed into this + */ public void putAll(Map m) { - int msize = m.size(); Iterator itr = m.entrySet().iterator(); - - for (int i=0; i < msize; i++) + + for (int msize = m.size(); msize > 0; msize--) { Map.Entry e = (Map.Entry) itr.next(); - // Optimize in case the Entry is one of our own. - if (e instanceof BasicMapEntry) - { - BasicMapEntry entry = (BasicMapEntry) e; - put(entry.key, entry.value); - } - else - { + // Optimize in case the Entry is one of our own. + if (e instanceof BasicMapEntry) + { + BasicMapEntry entry = (BasicMapEntry) e; + put(entry.key, entry.value); + } + else + { put(e.getKey(), e.getValue()); - } + } } } + /** + * Clears the Map so it has no keys. This is O(1). + */ public void clear() { modCount++; - for (int i=0; i < buckets.length; i++) - { - buckets[i] = null; - } + Arrays.fill(buckets, null); size = 0; } - /** - * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but - * its contents are not) + /** + * Returns a shallow clone of this HashMap. The Map itself is cloned, + * but its contents are not. This is O(n). + * + * @return the clone */ public Object clone() { @@ -363,49 +459,39 @@ public class HashMap extends AbstractMap } catch (CloneNotSupportedException x) { + // This is impossible. } - copy.buckets = new Entry[buckets.length]; - - for (int i=0; i < buckets.length; i++) - { - Entry e = buckets[i]; - Entry last = null; - - while (e != null) - { - if (last == null) - { - copy.buckets[i] = new Entry(e.key, e.value); - last = copy.buckets[i]; - } - else - { - last.next = new Entry(e.key, e.value); - last = last.next; - } - e = e.next; - } - } + copy.buckets = new HashEntry[buckets.length]; + copy.putAllInternal(this); return copy; } - /** returns a "set view" of this HashMap's keys */ + /** + * Returns a "set view" of this HashMap's keys. The set is backed by the + * HashMap, so changes in one show up in the other. The set supports + * element removal, but not element addition. + * + * @return a set view of the keys + * @see #values() + * @see #entrySet() + */ public Set keySet() { - // Create an AbstractSet with custom implementations of those methods that - // can be overriden easily and efficiently. + // Create an AbstractSet with custom implementations of those methods that + // can be overridden easily and efficiently. return new AbstractSet() { public int size() { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.KEYS); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(KEYS); } - + public void clear() { HashMap.this.clear(); @@ -415,20 +501,29 @@ public class HashMap extends AbstractMap { return HashMap.this.containsKey(o); } - + public boolean remove(Object o) { // Test against the size of the HashMap to determine if anything - // really got removed. This is neccessary because the return value of - // HashMap.remove() is ambiguous in the null case. + // really got removed. This is neccessary because the return value of + // HashMap.remove() is ambiguous in the null case. int oldsize = size; HashMap.this.remove(o); - return (oldsize != size); + return (oldsize != size); } }; } - - /** Returns a "collection view" (or "bag view") of this HashMap's values. */ + + /** + * Returns a "collection view" (or "bag view") of this HashMap's values. + * The collection is backed by the HashMap, so changes in one show up + * in the other. The collection supports element removal, but not element + * addition. + * + * @return a bag view of the values + * @see #keySet() + * @see #entrySet() + */ public Collection values() { // We don't bother overriding many of the optional methods, as doing so @@ -439,12 +534,13 @@ public class HashMap extends AbstractMap { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.VALUES); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(VALUES); } - + public void clear() { HashMap.this.clear(); @@ -452,23 +548,37 @@ public class HashMap extends AbstractMap }; } - /** Returns a "set view" of this HashMap's entries. */ + /** + * Returns a "set view" of this HashMap's entries. The set is backed by + * the HashMap, so changes in one show up in the other. The set supports + * element removal, but not element addition. + * <p> + * + * Note that the iterators for all three views, from keySet(), entrySet(), + * and values(), traverse the HashMap in the same sequence. + * + * @return a set view of the entries + * @see #keySet() + * @see #values() + * @see Map.Entry + */ public Set entrySet() { - // Create an AbstractSet with custom implementations of those methods that - // can be overriden easily and efficiently. + // Create an AbstractSet with custom implementations of those methods that + // can be overridden easily and efficiently. return new AbstractSet() { public int size() { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.ENTRIES); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(ENTRIES); } - + public void clear() { HashMap.this.clear(); @@ -476,143 +586,184 @@ public class HashMap extends AbstractMap public boolean contains(Object o) { - if (!(o instanceof Map.Entry)) - return false; - Map.Entry me = (Map.Entry) o; - Entry e = getEntry(me); - return (e != null); + return getEntry(o) != null; } - + public boolean remove(Object o) { - if (!(o instanceof Map.Entry)) - return false; - Map.Entry me = (Map.Entry) o; - Entry e = getEntry(me); - if (e != null) - { - HashMap.this.remove(e.key); - return true; - } - return false; + HashEntry e = getEntry(o); + if (e != null) + { + HashMap.this.remove(e.key); + return true; + } + return false; } }; } - - /** Return an index in the buckets array for `key' based on its hashCode() */ - private int hash(Object key) + + /** Helper method that returns an index in the buckets array for `key; + * based on its hashCode(). + * + * @param key the key + * @return the bucket number + */ + int hash(Object key) { - if (key == null) - return 0; - else - return Math.abs(key.hashCode() % buckets.length); + return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length); } - /** Return an Entry who's key and value equal the supplied Map.Entry. - * This is used by entrySet's contains() and remove() methods. They can't - * use contains(key) and remove(key) directly because that would result - * in entries with the same key but a different value being matched. */ - private Entry getEntry(Map.Entry me) + /** + * Helper method for entrySet(), which matches both key and value + * simultaneously. + * + * @param o the entry to match + * @return the matching entry, if found, or null + * @see #entrySet() + */ + private HashEntry getEntry(Object o) { + if (!(o instanceof Map.Entry)) + return null; + Map.Entry me = (Map.Entry) o; int idx = hash(me.getKey()); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (e.equals(me)) - return e; - e = e.next; + return e; + e = e.next; } return null; } - - /** - * increases the size of the HashMap and rehashes all keys to new array - * indices; this is called when the addition of a new value would cause - * size() > threshold. Note that the existing Entry objects are reused in + + /** + * Increases the size of the HashMap and rehashes all keys to new array + * indices; this is called when the addition of a new value would cause + * size() > threshold. Note that the existing Entry objects are reused in * the new hash table. + * <p> + * + * This is not specified, but the new size is twice the current size plus + * one; this number is not always prime, unfortunately. */ private void rehash() { - Entry[] oldBuckets = buckets; - + HashEntry[] oldBuckets = buckets; + int newcapacity = (buckets.length * 2) + 1; threshold = (int) (newcapacity * loadFactor); - buckets = new Entry[newcapacity]; - - for (int i = 0; i < oldBuckets.length; i++) + buckets = new HashEntry[newcapacity]; + + for (int i = oldBuckets.length - 1; i >= 0; i--) { - Entry e = oldBuckets[i]; + HashEntry e = oldBuckets[i]; while (e != null) - { - int idx = hash(e.key); - Entry dest = buckets[idx]; - - if (dest != null) - { - while (dest.next != null) - dest = dest.next; - dest.next = e; - } - else - { - buckets[idx] = e; - } - - Entry next = e.next; - e.next = null; - e = next; - } + { + int idx = hash(e.key); + HashEntry dest = buckets[idx]; + + if (dest != null) + { + while (dest.next != null) + dest = dest.next; + dest.next = e; + } + else + { + buckets[idx] = e; + } + + HashEntry next = e.next; + e.next = null; + e = next; + } + } + } + + /** + * Generates a parameterized iterator. Must be overrideable, since + * LinkedHashMap iterates in a different order. + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + * @return the appropriate iterator + */ + Iterator iterator(int type) + { + return new HashIterator(type); + } + + /** + * A simplified, more efficient internal implementation of putAll(). The + * Map constructor and clone() should not call putAll or put, in order to + * be compatible with the JDK implementation with respect to subclasses. + */ + void putAllInternal(Map m) + { + Iterator itr = m.entrySet().iterator(); + + for (int msize = m.size(); msize > 0; msize--) + { + Map.Entry e = (Map.Entry) itr.next(); + Object key = e.getKey(); + int idx = hash(key); + addEntry(key, e.getValue(), idx, false); } } /** * Serializes this object to the given stream. - * @serialdata the <i>capacity</i>(int) that is the length of the - * bucket array, the <i>size</i>(int) of the hash map are emitted - * first. They are followed by size entries, each consisting of - * a key (Object) and a value (Object). + * + * @param s the stream to write to + * @throws IOException if the underlying stream fails + * @serialData the <i>capacity</i>(int) that is the length of the + * bucket array, the <i>size</i>(int) of the hash map + * are emitted first. They are followed by size entries, + * each consisting of a key (Object) and a value (Object). */ private void writeObject(ObjectOutputStream s) throws IOException { - // the threshold and loadFactor fields + // Write the threshold and loadFactor fields. s.defaultWriteObject(); s.writeInt(buckets.length); s.writeInt(size); - Iterator it = entrySet().iterator(); + // Avoid creating a wasted Set by creating the iterator directly. + Iterator it = iterator(ENTRIES); while (it.hasNext()) { - Map.Entry entry = (Map.Entry) it.next(); - s.writeObject(entry.getKey()); - s.writeObject(entry.getValue()); + HashEntry entry = (HashEntry) it.next(); + s.writeObject(entry.key); + s.writeObject(entry.value); } } /** * Deserializes this object from the given stream. - * @serialdata the <i>capacity</i>(int) that is the length of the - * bucket array, the <i>size</i>(int) of the hash map are emitted - * first. They are followed by size entries, each consisting of - * a key (Object) and a value (Object). + * + * @param s the stream to read from + * @throws ClassNotFoundException if the underlying stream fails + * @throws IOException if the underlying stream fails + * @serialData the <i>capacity</i>(int) that is the length of the + * bucket array, the <i>size</i>(int) of the hash map + * are emitted first. They are followed by size entries, + * each consisting of a key (Object) and a value (Object). */ private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { - // the threshold and loadFactor fields + // Read the threshold and loadFactor fields. s.defaultReadObject(); - int capacity = s.readInt(); + // Read and use capacity. + buckets = new HashEntry[s.readInt()]; int len = s.readInt(); - size = 0; - modCount = 0; - buckets = new Entry[capacity]; + // Already happens automatically. + // size = 0; + // modCount = 0; - for (int i = 0; i < len; i++) - { - Object key = s.readObject(); - Object value = s.readObject(); - put(key, value); - } + // Read and use key/value pairs. + for ( ; len > 0; len--) + put(s.readObject(), s.readObject()); } /** @@ -620,64 +771,70 @@ public class HashMap extends AbstractMap * This implementation is parameterized to give a sequential view of * keys, values, or entries. * - * @author Jon Zeppieri + * @author Jon Zeppieri */ class HashIterator implements Iterator { - static final int KEYS = 0, - VALUES = 1, - ENTRIES = 2; - - // the type of this Iterator: KEYS, VALUES, or ENTRIES. - int type; - // the number of modifications to the backing Hashtable that we know about. - int knownMod; - // The total number of elements returned by next(). Used to determine if - // there are more elements remaining. - int count; - // Current index in the physical hash table. - int idx; - // The last Entry returned by a next() call. - Entry last; - // The next entry that should be returned by next(). It is set to something - // if we're iterating through a bucket that contains multiple linked - // entries. It is null if next() needs to find a new bucket. - Entry next; - - /* construct a new HashtableIterator with the supllied type: - KEYS, VALUES, or ENTRIES */ + /** + * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, + * or {@link #ENTRIES}. + */ + final int type; + /** + * The number of modifications to the backing HashMap that we know about. + */ + int knownMod = modCount; + /** The number of elements remaining to be returned by next(). */ + int count = size; + /** Current index in the physical hash table. */ + int idx = buckets.length; + /** The last Entry returned by a next() call. */ + HashEntry last; + /** + * The next entry that should be returned by next(). It is set to something + * if we're iterating through a bucket that contains multiple linked + * entries. It is null if next() needs to find a new bucket. + */ + HashEntry next; + + /** + * Construct a new HashIterator with the supplied type. + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + */ HashIterator(int type) { this.type = type; - knownMod = HashMap.this.modCount; - count = 0; - idx = buckets.length; } - /** returns true if the Iterator has more elements */ + /** + * Returns true if the Iterator has more elements. + * @return true if there are more elements + * @throws ConcurrentModificationException if the HashMap was modified + */ public boolean hasNext() { - if (knownMod != HashMap.this.modCount) - throw new ConcurrentModificationException(); - return count < size; + if (knownMod != modCount) + throw new ConcurrentModificationException(); + return count > 0; } - /** returns the next element in the Iterator's sequential view */ + /** + * Returns the next element in the Iterator's sequential view. + * @return the next element + * @throws ConcurrentModificationException if the HashMap was modified + * @throws NoSuchElementException if there is none + */ public Object next() { - if (knownMod != HashMap.this.modCount) - throw new ConcurrentModificationException(); - if (count == size) + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (count == 0) throw new NoSuchElementException(); - count++; - Entry e = null; - if (next != null) - e = next; + count--; + HashEntry e = next; while (e == null) - { - e = buckets[--idx]; - } + e = buckets[--idx]; next = e.next; last = e; @@ -688,25 +845,22 @@ public class HashMap extends AbstractMap return e; } - /** - * removes from the backing HashMap the last element which was fetched with the - * <pre>next()</pre> method + /** + * Removes from the backing HashMap the last element which was fetched + * with the <pre>next()</pre> method. + * @throws ConcurrentModificationException if the HashMap was modified + * @throws IllegalStateException if called when there is no last element */ public void remove() { - if (knownMod != HashMap.this.modCount) - throw new ConcurrentModificationException(); + if (knownMod != modCount) + throw new ConcurrentModificationException(); if (last == null) - { - throw new IllegalStateException(); - } - else - { - HashMap.this.remove(last.key); - knownMod++; - count--; - last = null; - } + throw new IllegalStateException(); + + HashMap.this.remove(last.key); + knownMod++; + last = null; } } } diff --git a/libjava/java/util/Iterator.java b/libjava/java/util/Iterator.java index 92620f8..cc68c87 100644 --- a/libjava/java/util/Iterator.java +++ b/libjava/java/util/Iterator.java @@ -1,5 +1,5 @@ /* Iterator.java -- Interface for iterating over collections - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -28,20 +28,28 @@ executable file might be covered by the GNU General Public License. */ package java.util; /** - * An object which iterates over a collection. An Iterator is used to return the - * items once only, in sequence, by successive calls to the next method. It is - * also possible to remove elements from the underlying collection by using the - * optional remove method. Iterator is intended as a replacement for the - * Enumeration interface of previous versions of Java, which did not have the - * remove method and had less conveniently named methods. + * An object which iterates over a collection. An Iterator is used to return + * the items once only, in sequence, by successive calls to the next method. + * It is also possible to remove elements from the underlying collection by + * using the optional remove method. Iterator is intended as a replacement + * for the Enumeration interface of previous versions of Java, which did not + * have the remove method and had less conveniently named methods. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Collection + * @see ListIterator + * @see Enumeration + * @since 1.2 + * @status updated to 1.4 */ public interface Iterator { /** - * Tests whether there are elements remaining in the collection. + * Tests whether there are elements remaining in the collection. In other + * words, calling <code>next()</code> will not throw an exception. * - * @return true if there is at least one more element in the collection, - * that is, if the next call to next will not throw NoSuchElementException. + * @return true if there is at least one more element in the collection */ boolean hasNext(); @@ -49,20 +57,20 @@ public interface Iterator * Obtain the next element in the collection. * * @return the next element in the collection - * @exception NoSuchElementException if there are no more elements + * @throws NoSuchElementException if there are no more elements */ Object next(); /** - * Remove from the underlying collection the last element returned by next. - * This method can be called only once after each call to next. It does not - * affect what will be returned by subsequent calls to next. This operation is - * optional, it may throw an UnsupportedOperationException. + * Remove from the underlying collection the last element returned by next + * (optional operation). This method can be called only once after each + * call to <code>next()</code>. It does not affect what will be returned + * by subsequent calls to next. * - * @exception IllegalStateException if next has not yet been called or remove - * has already been called since the last call to next. - * @exception UnsupportedOperationException if this Iterator does not support - * the remove operation. + * @throws IllegalStateException if next has not yet been called or remove + * has already been called since the last call to next. + * @throws UnsupportedOperationException if this Iterator does not support + * the remove operation. */ void remove(); } diff --git a/libjava/java/util/LinkedHashMap.java b/libjava/java/util/LinkedHashMap.java new file mode 100644 index 0000000..8950d58 --- /dev/null +++ b/libjava/java/util/LinkedHashMap.java @@ -0,0 +1,474 @@ +/* LinkedHashMap.java -- a class providing hashtable data structure, + mapping Object --> Object, with 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.IOException; +import java.io.Serializable; +import java.io.ObjectInputStream; +import java.io.ObjectOutputStream; + +/** + * This class provides a hashtable-backed implementation of the + * Map interface, with predictable traversal order. + * <p> + * + * 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 either + * insertion or access order. Note that the insertion order is not + * modified if a <code>put</code> simply reinserts a key in the map. + * <p> + * + * One of the nice features of tracking insertion order is that you can + * copy a hashtable, 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 <code>TreeMap</code>. + * <p> + * + * When using this {@link #LinkedHashMap(int, float, boolean) constructor}, + * you build an access-order mapping. This can be used to implement LRU + * caches, for example. In this case, every invocation of <code>put</code>, + * <code>putAll</code>, or <code>get</code> moves the accessed entry to + * the end of the iteration list. By overriding + * {@link #removeEldestEntry(Map.Entry)}, you can also control the + * removal of the oldest entry, and thereby do things like keep the map + * at a fixed size. + * <p> + * + * Under ideal circumstances (no collisions), LinkedHashMap offers O(1) + * performance on most operations (<pre>containsValue()</pre> is, + * of course, O(n)). In the worst case (all keys map to the same + * hash code -- very unlikely), most operations are O(n). + * <p> + * + * LinkedHashMap accepts the null key and null values. It is not + * synchronized, so if you need multi-threaded access, consider using:<br> + * <code>Map m = Collections.synchronizedMap(new LinkedHashMap(...));</code> + * <p> + * + * The iterators are <i>fail-fast</i>, meaning that any structural + * modification, except for <code>remove()</code> called on the iterator + * itself, cause the iterator to throw a + * {@link ConcurrentModificationException} rather than exhibit + * non-deterministic behavior. + * + * @author Eric Blake <ebb9@email.byu.edu> + * @see Object#hashCode() + * @see Collection + * @see Map + * @see HashMap + * @see TreeMap + * @see Hashtable + * @since 1.4 + */ +public class LinkedHashMap extends HashMap +{ + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 3801124242820219131L; + + /** + * The first Entry to iterate over. + */ + transient LinkedHashEntry head; + + /** + * The last Entry to iterate over. + */ + transient LinkedHashEntry tail; + + /** + * The iteration order of this linked hash map: <code>true</code> for + * access-order, <code>false</code> for insertion-order. + * @serial + */ + final boolean accessOrder; + + /** + * Class to represent an entry in the hash table. Holds a single key-value + * pair and the doubly-linked insertion order list. + */ + class LinkedHashEntry extends HashEntry + { + /** The predecessor in the iteration list, null if this is the eldest. */ + LinkedHashEntry pred; + /** The successor in the iteration list, null if this is the newest. */ + LinkedHashEntry succ; + + /** + * Simple constructor. + * @param key the key + * @param value the value + */ + LinkedHashEntry(Object key, Object value) + { + super(key, value); + if (head == null) + head = this; + pred = tail; + tail = this; + if (pred != null) + pred.succ = this; + } + + /** + * Sets the value of this entry, and shuffles it to the end of + * the list if this is in access-order. + * @param value the new value + * @return the prior value + */ + public Object setValue(Object value) + { + if (accessOrder && succ != null) + { + succ.pred = pred; + if (pred == null) + head = succ; + else + pred.succ = succ; + succ = null; + pred = tail; + pred.succ = this; + tail = this; + } + return super.setValue(value); + } + + /** + * Called when this entry is removed from the map. This version does + * the necessary bookkeeping to keep the doubly-linked list in order. + * @return the value of this key as it is removed + */ + Object cleanup() + { + if (pred == null) + head = succ; + else + pred.succ = succ; + if (succ == null) + tail = pred; + else + succ.pred = pred; + + return value; + } + } + + /** + * Construct a new insertion-ordered LinkedHashMap with the default + * capacity (11) and the default load factor (0.75). + */ + public LinkedHashMap() + { + super(); + accessOrder = false; + } + + /** + * Construct a new insertion-ordered LinkedHashMap from the given Map, + * with initial capacity the greater of the size of <code>m</code> or + * the default of 11. + * <p> + * + * Every element in Map m will be put into this new HashMap, in the + * order of m's iterator. + * + * @param m a Map whose key / value pairs will be put into + * the new HashMap. <b>NOTE: key / value pairs + * are not cloned in this constructor.</b> + * @throws NullPointerException if m is null + */ + public LinkedHashMap(Map m) + { + super(m); + accessOrder = false; + } + + /** + * Construct a new insertion-ordered LinkedHashMap with a specific + * inital capacity and default load factor of 0.75. + * + * @param initialCapacity the initial capacity of this HashMap (>=0) + * @throws IllegalArgumentException if (initialCapacity < 0) + */ + public LinkedHashMap(int initialCapacity) + { + super(initialCapacity); + accessOrder = false; + } + + /** + * Construct a new insertion-orderd LinkedHashMap with a specific + * inital capacity and load factor. + * + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (>0, not NaN) + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) + */ + public LinkedHashMap(int initialCapacity, float loadFactor) + { + super(initialCapacity, loadFactor); + accessOrder = false; + } + + /** + * Construct a new LinkedHashMap with a specific inital capacity, load + * factor, and ordering mode. + * + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (>0, not NaN) + * @param accessOrder true for access-order, false for insertion-order + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) + */ + public LinkedHashMap(int initialCapacity, float loadFactor, + boolean accessOrder) + { + super(initialCapacity, loadFactor); + this.accessOrder = accessOrder; + } + + /** + * Clears the Map so it has no keys. This is O(1). + */ + public void clear() + { + super.clear(); + head = null; + tail = null; + } + + /** + * Returns true if this HashMap contains a value <pre>o</pre>, such that + * <pre>o.equals(value)</pre>. + * + * @param value the value to search for in this HashMap + * @return true if at least one key maps to the value + */ + public boolean containsValue(Object value) + { + LinkedHashEntry e = head; + while (e != null) + { + if (value == null ? e.value == null : value.equals(e.value)) + return true; + e = e.succ; + } + return false; + } + + /** + * Return the value in this Map associated with the supplied key, + * or <pre>null</pre> if the key maps to nothing. If this is an + * access-ordered Map and the key is found, this performs structural + * modification, moving the key to the newest end of the list. NOTE: + * Since the value could also be null, you must use containsKey to + * see if this key actually maps to something. + * + * @param key the key for which to fetch an associated value + * @return what the key maps to, if present + * @see #put(Object, Object) + * @see #containsKey(Object) + */ + public Object get(Object key) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) + { + if (key == null ? e.key == null : key.equals(e.key)) + { + if (accessOrder) + { + modCount++; + LinkedHashEntry l = (LinkedHashEntry) e; + if (l.succ != null) + { + l.succ.pred = l.pred; + if (l.pred == null) + head = l.succ; + else + l.pred.succ = l.succ; + l.succ = null; + l.pred = tail; + tail.succ = l; + tail = l; + } + } + return e.value; + } + e = e.next; + } + return null; + } + + /** + * Returns <code>true</code> if this map should remove the eldest entry. + * This method is invoked by all calls to <code>put</code> and + * <code>putAll</code> which place a new entry in the map, providing + * the implementer an opportunity to remove the eldest entry any time + * a new one is added. This can be used to save memory usage of the + * hashtable, as well as emulating a cache, by deleting stale entries. + * <p> + * + * For example, to keep the Map limited to 100 entries, override as follows: + * <pre> + * private static final int MAX_ENTRIES = 100; + * + * protected boolean removeEldestEntry(Map.Entry eldest) + * { + * return size() > MAX_ENTRIES; + * } + * </pre><p> + * + * Typically, this method does not modify the map, but just uses the + * return value as an indication to <code>put</code> whether to proceed. + * However, if you override it to modify the map, you must return false + * (indicating that <code>put</code> should do nothing), or face + * unspecified behavior. + * <p> + * + * This method is called after the eldest entry has been inserted, so + * if <code>put</code> was called on a previously empty map, the eldest + * entry is the one you just put in! The default implementation just + * returns <code>false</code>, so that this map always behaves like + * a normal one with unbounded growth. + * + * @param eldest the eldest element which would be removed if this + * returns true. For an access-order map, this is the least + * recently accessed; for an insertion-order map, this is the + * earliest element inserted. + * @return true if <code>eldest</code> should be removed + */ + protected boolean removeEldestEntry(Map.Entry eldest) + { + return false; + } + + /** Helper method called by <code>put</code>, which creates and adds a + * new Entry, followed by performing bookkeeping (like removeEldestEntry). + * + * @param key the key of the new Entry + * @param value the value + * @param idx the index in buckets where the new Entry belongs + * @param callRemove Whether to call the removeEldestEntry method. + * @see #put(Object, Object) + * @see #removeEldestEntry(Map.Entry) + */ + void addEntry(Object key, Object value, int idx, boolean callRemove) + { + LinkedHashEntry e = new LinkedHashEntry(key, value); + + e.next = buckets[idx]; + buckets[idx] = e; + + if (callRemove && removeEldestEntry(head)) + remove(head); + } + + void putAllInternal(Map m) + { + head = null; + tail = null; + super.putAllInternal(m); + } + + /** + * Generates a parameterized iterator. This allows traversal to follow + * the doubly-linked list instead of the random bin order of HashMap. + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + * @return the appropriate iterator + */ + Iterator iterator(final int type) + { + return new Iterator() + { + /** The current Entry */ + LinkedHashEntry current = head; + + /** The previous Entry returned by next() */ + LinkedHashEntry last; + + /** The number of known modifications to the backing HashMap */ + int knownMod = modCount; + + /** + * Returns true if the Iterator has more elements. + * @return true if there are more elements + * @throws ConcurrentModificationException if the HashMap was modified + */ + public boolean hasNext() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + return current != null; + } + + /** + * Returns the next element in the Iterator's sequential view. + * @return the next element + * @throws ConcurrentModificationException if the HashMap was modified + * @throws NoSuchElementException if there is none + */ + public Object next() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (current == null) + throw new NoSuchElementException(); + last = current; + current = current.succ; + return type == VALUES ? last.value : type == KEYS ? last.key : last; + } + + /** + * Removes from the backing HashMap the last element which was fetched + * with the <pre>next()</pre> method. + * @throws ConcurrentModificationException if the HashMap was modified + * @throws IllegalStateException if called when there is no last element + */ + public void remove() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (last == null) + throw new IllegalStateException(); + + LinkedHashMap.this.remove(last.key); + knownMod++; + last = null; + } + }; + } +} diff --git a/libjava/java/util/List.java b/libjava/java/util/List.java index e3e2617..25892d7 100644 --- a/libjava/java/util/List.java +++ b/libjava/java/util/List.java @@ -1,5 +1,5 @@ /* List.java -- An ordered collection which allows indexed access - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,131 +25,179 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comment for the interface itself needs to be put into english. -// ~ Some more @see clauses might be nice. - package java.util; /** - * [This is what this doc comment will mention: - * ~ Additional restrictions on some methods. Others included for completeness. - * ~ ListIterator and what it can do - * ~ Positional and iterated access - * ~ search (but linear time) - * ~ be careful when containing self as an element, because equals and hashCode - * loop.] + * An ordered collection (also known as a list). This collection allows + * access to elements by position, as well as control on where elements + * are inserted. Unlike sets, duplicate elements are permitted by this + * general contract (if a subclass forbids duplicates, this should be + * documented). + * <p> + * + * List places additional requirements on <code>iterator</code>, + * <code>add</code>, <code>remove</code>, <code>equals</code>, and + * <code>hashCode</code>, in addition to requiring more methods. List + * indexing is 0-based (like arrays), although some implementations may + * require time proportional to the index to obtain an arbitrary element. + * The List interface is incompatible with Set; you cannot implement both + * simultaneously. + * <p> + * + * Lists also provide a <code>ListIterator</code> which allows bidirectional + * traversal and other features atop regular iterators. Lists can be + * searched for arbitrary elements, and allow easy insertion and removal + * of multiple elements in one method call. + * <p> + * + * Note: While lists may contain themselves as elements, this leads to + * undefined (usually infinite recursive) behavior for some methods like + * hashCode or equals. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Collection + * @see Set + * @see ArrayList + * @see LinkedList + * @see Vector + * @see Arrays#asList(Object[]) + * @see Collections#nCopies(int, Object) + * @see Collections#EMPTY_LIST + * @see AbstractList + * @see AbstractSequentialList + * @since 1.2 + * @status updated to 1.4 */ public interface List extends Collection { /** - * Insert an element into the list at a given position. + * 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. * - * @param index the location to insert the item. - * @param o the object to insert. - * @exception UnsupportedOperationException if this list does not support the - * add operation. - * @exception IndexOutOfBoundsException if index < 0 || index > size() - * @exception ClassCastException if o cannot be added to this list due to its - * type. - * @exception IllegalArgumentException if o cannot be added to this list for - * some other reason. + * @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 */ void add(int index, Object o); /** - * Add an element to the end of the list. + * Add an element to the end of the list (optional operation). If the list + * imposes restraints on what can be inserted, such as no null elements, + * this should be documented. * - * @param o the object to add. - * @returns true, as Collection defines this method as returning true if the - * list was modified as a result of this action, and it always is for a - * list. - * @exception UnsupportedOperationException if this list does not support the - * add operation. - * @exception ClassCastException if o cannot be added to this list due to its - * type. - * @exception IllegalArgumentException if o cannot be added to this list for - * some other reason. + * @param o the object to add + * @return true, as defined by Collection for a modified list + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @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 */ boolean add(Object o); /** - * Insert the contents of a collection into the list at a given position. + * 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). * - * @param index the location to insert the collection. - * @param c the collection to insert. - * @returns true if the list was modified by this action, that is, if c is - * non-empty. - * @exception UnsupportedOperationException if this list does not support the - * addAll operation. - * @exception IndexOutOfBoundsException if index < 0 || index > size() - * @exception ClassCastException if some element of c cannot be added to this - * list due to its type. - * @exception IllegalArgumentException if some element of c cannot be added - * to this list for some other reason. + * @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) */ boolean addAll(int index, Collection c); /** - * Add the contents of a collection to the end of the list. + * Add the contents of a collection to the end of the list (optional + * operation). This operation is undefined if this list is modified + * during the operation (for example, if you try to insert a list into + * itself). * - * @param c the collection to add. - * @returns true if the list was modified by this action, that is, if c is - * non-empty. - * @exception UnsupportedOperationException if this list does not support the - * addAll operation. - * @exception ClassCastException if some element of c cannot be added to this - * list due to its type. - * @exception IllegalArgumentException if some element of c cannot be added - * to this list for some other reason. + * @param c the collection to add + * @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 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(Object) */ boolean addAll(Collection c); /** * Clear the list, such that a subsequent call to isEmpty() would return - * true. + * true (optional operation). * - * @exception UnsupportedOperationException if this list does not support the - * clear operation. + * @throws UnsupportedOperationException if this list does not support the + * clear operation */ void clear(); /** * Test whether this list contains a given object as one of its elements. + * This is defined as the existence of an element e such that + * <code>o == null ? e == null : o.equals(e)</code>. * - * @param o the element to look for. - * @returns true if this list contains an element e such that <code>o == - * null ? e == null : o.equals(e)</code>. + * @param o the element to look for + * @return true if this list contains the element */ boolean contains(Object o); /** * Test whether this list contains every element in a given collection. * - * @param c the collection to test for. - * @returns true if for every element o in c, contains(o) would return true. + * @param c the collection to test for + * @return true if for every element o in c, contains(o) would return true + * @throws NullPointerException if the collection is null + * @see #contains(Object) */ boolean containsAll(Collection c); /** * Test whether this list is equal to another object. A List is defined to be * equal to an object if and only if that object is also a List, and the two - * lists are equal. Two lists l1 and l2 are defined to be equal if and only + * lists have the same sequence. Two lists l1 and l2 are equal if and only * if <code>l1.size() == l2.size()</code>, and for every integer n between 0 * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ? * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>. * - * @param o the object to test for equality with this list. - * @returns true if o is equal to this list. + * @param o the object to test for equality with this list + * @return true if o is equal to this list + * @see Object#equals(Object) + * @see #hashCode() */ boolean equals(Object o); /** * Get the element at a given index in this list. * - * @param index the index of the element to be returned. - * @returns the element at index index in this list. - * @exception IndexOutOfBoundsException if index < 0 || index >= size() + * @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() */ Object get(int index); @@ -159,14 +207,17 @@ public interface List extends Collection * <pre> * hashCode = 1; * Iterator i = list.iterator(); - * while (i.hasNext()) { - * Object obj = i.next(); - * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); - * } + * while (i.hasNext()) + * { + * Object obj = i.next(); + * hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); + * } * </pre> * This ensures that the general contract of Object.hashCode() is adhered to. * - * @returns the hash code of this list. + * @return the hash code of this list + * @see Object#hashCode() + * @see #equals(Object) */ int hashCode(); @@ -174,22 +225,23 @@ public interface List extends Collection * Obtain the first index at which a given object is to be found in this * list. * - * @returns the least integer n such that <code>o == null ? get(n) == null : - * o.equals(get(n))</code>, or -1 if there is no such index. + * @param o the object to search for + * @return the least integer n such that <code>o == null ? get(n) == null : + * o.equals(get(n))</code>, or -1 if there is no such index */ int indexOf(Object o); /** * Test whether this list is empty, that is, if size() == 0. * - * @returns true if this list contains no elements. + * @return true if this list contains no elements */ boolean isEmpty(); /** - * Obtain an Iterator over this list. + * Obtain an Iterator over this list, whose sequence is the list order. * - * @returns an Iterator over the elements of this list, in order. + * @return an Iterator over the elements of this list, in order */ Iterator iterator(); @@ -197,119 +249,135 @@ public interface List extends Collection * Obtain the last index at which a given object is to be found in this * list. * - * @returns the greatest integer n such that <code>o == null ? get(n) == null - * : o.equals(get(n))</code>. + * @return the greatest integer n such that <code>o == null ? get(n) == null + * : o.equals(get(n))</code>, or -1 if there is no such index */ int lastIndexOf(Object o); /** * Obtain a ListIterator over this list, starting at the beginning. * - * @returns a ListIterator over the elements of this list, in order, starting - * at the beginning. + * @return a ListIterator over the elements of this list, in order, starting + * at the beginning */ ListIterator listIterator(); /** * Obtain a ListIterator over this list, starting at a given position. + * A first call to next() would return the same as get(index), and a + * first call to previous() would return the same as get(index - 1). * * @param index the position, between 0 and size() inclusive, to begin the - * iteration from. - * @returns a ListIterator over the elements of this list, in order, starting - * at index. - * @exception IndexOutOfBoundsException if index < 0 || index > size() + * iteration from + * @return a ListIterator over the elements of this list, in order, starting + * at index + * @throws IndexOutOfBoundsException if index < 0 || index > size() */ ListIterator listIterator(int index); /** - * Remove the element at a given position in this list. + * Remove the element at a given position in this list (optional operation). + * Shifts all remaining elements to the left to fill the gap. * - * @param index the position within the list of the object to remove. - * @returns the object that was removed. - * @exception UnsupportedOperationException if this list does not support the - * remove operation. - * @exception IndexOutOfBoundsException if index < 0 || index > size() + * @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() */ Object remove(int index); /** - * Remove the first occurence of an object from this list. That is, remove - * the first element e such that <code>o == null ? e == null : - * o.equals(e)</code>. + * Remove the first occurence of an object from this list (optional + * operation). That is, remove the first element e such that + * <code>o == null ? e == null : o.equals(e)</code>. * - * @param o the object to remove. - * @returns true if the list changed as a result of this call, that is, if - * the list contained at least one occurrence of o. - * @exception UnsupportedOperationException if this list does not support the - * remove operation. + * @param o the object to remove + * @return true if the list changed as a result of this call, that is, if + * the list contained at least one occurrence of o + * @throws UnsupportedOperationException if this list does not support the + * remove operation */ boolean remove(Object o); /** - * Remove all elements of a given collection from this list. That is, remove - * every element e such that c.contains(e). + * Remove all elements of a given collection from this list (optional + * operation). That is, remove every element e such that c.contains(e). * - * @returns true if this list was modified as a result of this call. - * @exception UnsupportedOperationException if this list does not support the - * removeAll operation. + * @param c the collection to filter out + * @return true if this list was modified as a result of this call + * @throws UnsupportedOperationException if this list does not support the + * removeAll operation + * @throws NullPointerException if the collection is null + * @see #remove(Object) + * @see #contains(Object) */ boolean removeAll(Collection c); /** * Remove all elements of this list that are not contained in a given - * collection. That is, remove every element e such that !c.contains(e). + * collection (optional operation). That is, remove every element e such + * that !c.contains(e). * - * @returns true if this list was modified as a result of this call. - * @exception UnsupportedOperationException if this list does not support the - * retainAll operation. + * @param c the collection to retain + * @return true if this list was modified as a result of this call + * @throws UnsupportedOperationException if this list does not support the + * retainAll operation + * @throws NullPointerException if the collection is null + * @see #remove(Object) + * @see #contains(Object) */ boolean retainAll(Collection c); /** - * Replace an element of this list with another object. + * Replace an element of this list with another object (optional operation). * - * @param index the position within this list of the element to be replaced. - * @param o the object to replace it with. - * @returns the object that was replaced. - * @exception UnsupportedOperationException if this list does not support the - * set operation. - * @exception IndexOutOfBoundsException if index < 0 || index >= size() - * @exception ClassCastException if o cannot be added to this list due to its - * type. - * @exception IllegalArgumentException if o cannot be added to this list for - * some other reason. + * @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 */ Object set(int index, Object o); /** - * Get the number of elements in this list. + * Get the number of elements in this list. If the list contains more + * than Integer.MAX_VALUE elements, return Integer.MAX_VALUE. * - * @returns the number of elements in the list. + * @return the number of elements in the list */ int size(); /** * Obtain a List view of a subsection of this list, from fromIndex - * (inclusive) to toIndex (exclusive). The returned list should be modifiable - * if and only if this list is modifiable. Changes to the returned list - * should be reflected in this list. If this list is structurally modified in + * (inclusive) to toIndex (exclusive). If the two indices are equal, the + * sublist is empty. The returned list should be modifiable if and only + * if this list is modifiable. Changes to the returned list should be + * reflected in this list. If this list is structurally modified in * any way other than through the returned list, the result of any subsequent * operations on the returned list is undefined. * * @param fromIndex the index that the returned list should start from - * (inclusive). - * @param toIndex the index that the returned list should go to (exclusive). - * @returns a List backed by a subsection of this list. - * @exception IndexOutOfBoundsException if fromIndex < 0 || toIndex > size() - * || fromIndex > toIndex. + * (inclusive) + * @param toIndex the index that the returned list should go to (exclusive) + * @return a List backed by a subsection of this list + * @throws IndexOutOfBoundsException if fromIndex < 0 + * || toIndex > size() || fromIndex > toIndex + * @throws IllegalArgumentException if fromIndex > toIndex (according to + * AbstractList). Don't you love Sun's inconsistent specifications? */ List subList(int fromIndex, int toIndex); /** * Copy the current contents of this list into an array. * - * @returns an array of type Object[] and length equal to the length of this - * list, containing the elements currently in this list, in order. + * @return an array of type Object[] and length equal to the length of this + * list, containing the elements currently in this list, in order */ Object[] toArray(); @@ -323,11 +391,12 @@ public interface List extends Collection * Note: The fact that the following element is set to null is only useful * if it is known that this list does not contain any null elements. * - * @param a the array to copy this list into. - * @returns an array containing the elements currently in this list, in - * order. - * @exception ArrayStoreException if the type of any element of the - * collection is not a subtype of the element type of a. + * @param a the array to copy this list into + * @return an array containing the elements currently in this list, in + * order + * @throws ArrayStoreException if the type of any element of the + * collection is not a subtype of the element type of a + * @throws NullPointerException if the specified array is null */ Object[] toArray(Object[] a); } diff --git a/libjava/java/util/ListIterator.java b/libjava/java/util/ListIterator.java index 8a8d2c7..92f4937 100644 --- a/libjava/java/util/ListIterator.java +++ b/libjava/java/util/ListIterator.java @@ -1,5 +1,5 @@ /* ListIterator.java -- Extended Iterator for iterating over ordered lists - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -32,116 +32,128 @@ package java.util; * elements may be accessed in forward or reverse order, elements may be * replaced as well as removed, and new elements may be inserted, during the * traversal of the list. + * <p> + * + * A list with n elements provides n+1 iterator positions (the front, the end, + * or between two elements). Note that <code>remove</code> and <code>set</code> + * operate on the last element returned, whether it was by <code>next</code> + * or <code>previous</code>. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Collection + * @see List + * @see Iterator + * @see Enumeration + * @since 1.2 + * @status updated to 1.4 */ public interface ListIterator extends Iterator { /** * Tests whether there are elements remaining in the list in the forward - * direction. + * direction. In other words, next() will not fail with a + * NoSuchElementException. * - * @return true if there is at least one more element in the list in the - * forward direction, that is, if the next call to next will not throw - * NoSuchElementException. + * @return true if the list continues in the forward direction */ boolean hasNext(); /** * Tests whether there are elements remaining in the list in the reverse - * direction. + * direction. In other words, previous() will not fail with a + * NoSuchElementException. * - * @return true if there is at least one more element in the list in the - * reverse direction, that is, if the next call to previous will not throw - * NoSuchElementException. + * @return true if the list continues in the reverse direction */ boolean hasPrevious(); /** * Obtain the next element in the list in the forward direction. Repeated - * calls to next may be used to iterate over the entire list, or calls to next - * and previous may be used together to go forwards and backwards. Alternating - * calls to next and previous will return the same element. + * calls to next may be used to iterate over the entire list, or calls to + * next and previous may be used together to go forwards and backwards. + * Alternating calls to next and previous will return the same element. * * @return the next element in the list in the forward direction - * @exception NoSuchElementException if there are no more elements + * @throws NoSuchElementException if there are no more elements */ Object next(); /** * Obtain the next element in the list in the reverse direction. Repeated - * calls to previous may be used to iterate backwards over the entire list, or - * calls to next and previous may be used together to go forwards and + * calls to previous may be used to iterate backwards over the entire list, + * or calls to next and previous may be used together to go forwards and * backwards. Alternating calls to next and previous will return the same * element. * * @return the next element in the list in the reverse direction - * @exception NoSuchElementException if there are no more elements + * @throws NoSuchElementException if there are no more elements */ Object previous(); /** * Find the index of the element that would be returned by a call to next. + * If hasNext() returns false, this returns the list size. * - * @return the index of the element that would be returned by a call to next, - * or list.size() if the iterator is at the end of the list. + * @return the index of the element that would be returned by next() */ int nextIndex(); /** - * Find the index of the element that would be returned by a call to previous. + * Find the index of the element that would be returned by a call to + * previous. If hasPrevious() returns false, this returns -1. * - * @return the index of the element that would be returned by a call to - * previous, or -1 if the iterator is at the beginning of the list. + * @return the index of the element that would be returned by previous() */ int previousIndex(); /** - * Insert an element into the list at the current position of the iterator. - * The element is inserted in between the element that would be returned by - * previous and the element that would be returned by next. After the - * insertion, a subsequent call to next is unaffected, but a call to - * previous returns the item that was added. This operation is optional, it - * may throw an UnsupportedOperationException. + * Insert an element into the list at the current position of the iterator + * (optional operation). The element is inserted in between the element that + * would be returned by previous and the element that would be returned by + * next. After the insertion, a subsequent call to next is unaffected, but + * a call to previous returns the item that was added. The values returned + * by nextIndex() and previousIndex() are incremented. * * @param o the object to insert into the list - * @exception ClassCastException the object is of a type which cannot be added - * to this list - * @exception IllegalArgumentException some other aspect of the object stops - * it being added to this list - * @exception UnsupportedOperationException if this ListIterator does not - * support the add operation + * @throws ClassCastException the object is of a type which cannot be added + * to this list + * @throws IllegalArgumentException some other aspect of the object stops + * it being added to this list + * @throws UnsupportedOperationException if this ListIterator does not + * support the add operation */ void add(Object o); /** * Remove from the list the element last returned by a call to next or - * previous. This method may only be called if neither add nor remove have - * been called since the last call to next or previous. This operation is - * optional, it may throw an UnsupportedOperationException. + * previous (optional operation). This method may only be called if neither + * add nor remove have been called since the last call to next or previous. * - * @exception IllegalStateException if neither next or previous have been - * called, or if add or remove has been called since the last call to next - * or previous. - * @exception UnsupportedOperationException if this ListIterator does not - * support the remove operation. + * @throws IllegalStateException if neither next or previous have been + * called, or if add or remove has been called since the last call + * to next or previous + * @throws UnsupportedOperationException if this ListIterator does not + * support the remove operation */ void remove(); /** * Replace the element last returned by a call to next or previous with a - * given object. This method may only be called if neither add nor remove have - * been called since the last call to next or previous. This operation is - * optional, it may throw an UnsupportedOperationException. + * given object (optional operation). This method may only be called if + * neither add nor remove have been called since the last call to next or + * previous. * * @param o the object to replace the element with - * @exception ClassCastException the object is of a type which cannot be added - * to this list - * @exception IllegalArgumentException some other aspect of the object stops - * it being added to this list - * @exception IllegalStateException if neither next or previous have been - * called, or if add or remove has been called since the last call to next - * or previous. - * @exception UnsupportedOperationException if this ListIterator does not - * support the set operation. + * @throws ClassCastException the object is of a type which cannot be added + * to this list + * @throws IllegalArgumentException some other aspect of the object stops + * it being added to this list + * @throws IllegalStateException if neither next or previous have been + * called, or if add or remove has been called since the last call + * to next or previous + * @throws UnsupportedOperationException if this ListIterator does not + * support the set operation */ void set(Object o); } diff --git a/libjava/java/util/Map.java b/libjava/java/util/Map.java index b1d4326..2cd22b3 100644 --- a/libjava/java/util/Map.java +++ b/libjava/java/util/Map.java @@ -1,5 +1,6 @@ -/* Map.java -- An object that maps keys to values - Copyright (C) 1998 Free Software Foundation, Inc. +/* Map.java: interface Map -- An object that maps keys to values + interface Map.Entry -- an Entry in a Map + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,34 +26,293 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comments for everything. - package java.util; +/** + * An object that maps keys onto values. Keys cannot be duplicated. This + * interface replaces the obsolete {@link Dictionary} abstract class. + * <p> + * + * The map has three collection views, which are backed by the map + * (modifications on one show up on the other): a set of keys, a collection + * of values, and a set of key-value mappings. Some maps have a guaranteed + * order, but not all do. + * <p> + * + * Note: Be careful about using mutable keys. Behavior is unspecified if + * a key's comparison behavior is changed after the fact. As a corollary + * to this rule, don't use a Map as one of its own keys or values, as it makes + * hashCode and equals have undefined behavior. + * <p> + * + * All maps are recommended to provide a no argument constructor, which builds + * an empty map, and one that accepts a Map parameter and copies the mappings + * (usually by putAll), to create an equivalent map. Unfortunately, Java + * cannot enforce these suggestions. + * <p> + * + * The map may be unmodifiable, in which case unsupported operations will + * throw an UnsupportedOperationException. Note that some operations may be + * safe, such as putAll(m) where m is empty, even if the operation would + * normally fail with a non-empty argument. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see HashMap + * @see TreeMap + * @see Hashtable + * @see SortedMap + * @see Collection + * @see Set + * @since 1.2 + * @status updated to 1.4 + */ public interface Map { + /** + * Remove all entries from this Map (optional operation). + * + * @throws UnsupportedOperationException if clear is not supported + */ public void clear(); + + /** + * Returns true if this contains a mapping for the given key. + * + * @param key the key to search for + * @return true if the map contains the key + * @throws ClassCastException if the key is of an inappropriate type + * @throws NullPointerException if key is <code>null</code> but the map + * does not permit null keys + */ public boolean containsKey(Object key); + + /** + * Returns true if this contains at least one mapping with the given value. + * In other words, returns true if a value v exists where + * <code>(value == null ? v == null : value.equals(v))</code>. This usually + * requires linear time. + * + * @param value the value to search for + * @return true if the map contains the value + */ public boolean containsValue(Object value); + + /** + * Returns a set view of the mappings in this Map. Each element in the + * set is a Map.Entry. The set is backed by the map, so that changes in + * one show up in the other. Modifications made while an iterator is + * in progress cause undefined behavior. If the set supports removal, + * these methods remove the underlying mapping from the map: + * <code>Iterator.remove</code>, <code>Set.remove</code>, + * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>. + * Element addition, via <code>add</code> or <code>addAll</code>, is + * not supported via this set. + * + * @return the set view of all mapping entries + * @see Map.Entry + */ public Set entrySet(); + + /** + * Compares the specified object with this map for equality. Returns + * <code>true</code> if the other object is a Map with the same mappings, + * that is,<br> + * <code>o instanceof Map && entrySet().equals(((Map) o).entrySet();</code> + * This allows comparison of maps, regardless of implementation. + * + * @param o the object to be compared + * @return true if the object equals this map + * @see Set#equals(Object) + */ public boolean equals(Object o); + + /** + * Returns the value mapped by the given key. Returns <code>null</code> if + * there is no mapping. However, in Maps that accept null values, you + * must rely on <code>containsKey</code> to determine if a mapping exists. + * + * @param key the key to look up + * @return the value associated with the key, or null if key not in map + * @throws ClassCastException if the key is an inappropriate type + * @throws NullPointerException if this map does not accept null keys + * @see #containsKey(Object) + */ public Object get(Object key); + + /** + * Associates the given key to the given value (optional operation). If the + * map already contains the key, its value is replaced. Be aware that in + * a map that permits <code>null</code> values, a null return does not + * always imply that the mapping was created. + * + * @param key the key to map + * @param value the value to be mapped + * @return the previous value of the key, or null if there was no mapping + * @throws UnsupportedOperationException if the operation is not supported + * @throws ClassCastException if the key or value is of the wrong type + * @throws IllegalArgumentException if something about this key or value + * prevents it from existing in this map + * @throws NullPointerException if the map forbids null keys or values + * @see #containsKey(Object) + */ public Object put(Object key, Object value); + + /** + * Returns the hash code for this map. This is the sum of all hashcodes + * for each Map.Entry object in entrySet. This allows comparison of maps, + * regardless of implementation, and satisfies the contract of + * Object.hashCode. + * + * @return the hash code + * @see Map.Entry#hashCode() + */ public int hashCode(); + + /** + * Returns true if the map contains no mappings. + * + * @return true if the map is empty + */ public boolean isEmpty(); + + /** + * Returns a set view of the keys in this Map. The set is backed by the + * map, so that changes in one show up in the other. Modifications made + * while an iterator is in progress cause undefined behavior. If the set + * supports removal, these methods remove the underlying mapping from + * the map: <code>Iterator.remove</code>, <code>Set.remove</code>, + * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>. + * Element addition, via <code>add</code> or <code>addAll</code>, is + * not supported via this set. + * + * @return the set view of all keys + */ public Set keySet(); + + /** + * Copies all entries of the given map to this one (optional operation). If + * the map already contains a key, its value is replaced. + * + * @param m the mapping to load into this map + * @throws UnsupportedOperationException if the operation is not supported + * @throws ClassCastException if a key or value is of the wrong type + * @throws IllegalArgumentException if something about a key or value + * prevents it from existing in this map + * @throws NullPointerException if the map forbids null keys or values, or + * if <code>m</code> is null. + * @see #put(Object, Object) + */ public void putAll(Map m); + + /** + * Removes the mapping for this key if present (optional operation). If + * the key is not present, this returns null. Note that maps which permit + * null values may also return null if the key was removed. + * + * @param key the key to remove + * @return the value the key mapped to, or null if not present + * @throws UnsupportedOperationException if deletion is unsupported + */ public Object remove(Object o); + + /** + * Returns the number of key-value mappings in the map. If there are more + * than Integer.MAX_VALUE mappings, return Integer.MAX_VALUE. + * + * @return the number of mappings + */ public int size(); + + /** + * Returns a collection (or bag) view of the values in this Map. The + * collection is backed by the map, so that changes in one show up in + * the other. Modifications made while an iterator is in progress cause + * undefined behavior. If the collection supports removal, these methods + * remove the underlying mapping from the map: <code>Iterator.remove</code>, + * <code>Collection.remove</code>, <code>removeAll</code>, + * <code>retainAll</code>, and <code>clear</code>. Element addition, via + * <code>add</code> or <code>addAll</code>, is not supported via this + * collection. + * + * @return the collection view of all values + */ public Collection values(); + /** + * A map entry (key-value pair). The Map.entrySet() method returns a set + * view of these objects; there is no other valid way to come across them. + * These objects are only valid for the duration of an iteration; in other + * words, if you mess with one after modifying the map, you are asking + * for undefined behavior. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Map + * @see Map#entrySet() + * @since 1.2 + * @status updated to 1.4 + */ public static interface Entry { + /** + * Get the key corresponding to this entry. + * + * @return the key + */ public Object getKey(); + + /** + * Get the value corresponding to this entry. If you already called + * Iterator.remove(), this is undefined. + * + * @return the value + */ public Object getValue(); + + /** + * Replaces the value with the specified object (optional operation). + * This writes through to the map, and is undefined if you already + * called Iterator.remove(). + * + * @param value the new value to store + * @return the old value + * @throws UnsupportedOperationException if the operation is not supported + * @throws ClassCastException if the value is of the wrong type + * @throws IllegalArgumentException if something about the value + * prevents it from existing in this map + * @throws NullPointerException if the map forbids null values + */ public Object setValue(Object value); + + /** + * Returns the hash code of the entry. This is defined as the exclusive-or + * of the hashcodes of the key and value (using 0 for null). In other + * words, this must be: + * <pre> + * (getKey() == null ? 0 : getKey().hashCode()) ^ + * (getValue() == null ? 0 : getValue().hashCode()) + * </pre> + * + * @return the hash code + */ public int hashCode(); + + /** + * Compares the specified object with this entry. Returns true only if + * the object is a mapping of identical key and value. In other words, + * this must be: + * <pre> + * (o instanceof Map.Entry) + * && (getKey() == null ? ((HashMap) o).getKey() == null + * : getKey().equals(((HashMap) o).getKey())) + * && (getValue() == null ? ((HashMap) o).getValue() == null + * : getValue().equals(((HashMap) o).getValue())) + * </pre> + * + * @param o the object to compare + * @return true if it is equal + */ public boolean equals(Object o); } } diff --git a/libjava/java/util/RandomAccess.java b/libjava/java/util/RandomAccess.java new file mode 100644 index 0000000..dd2b140 --- /dev/null +++ b/libjava/java/util/RandomAccess.java @@ -0,0 +1,53 @@ +/* RandomAccess.java -- A tagging interface that lists can use to tailor + operations to the correct algorithm + 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; + +/** + * Marker interface used to inform <code>List</code> implementations that + * they support fast (usually constant time) random access. This allows + * generic list algorithms to tailor their behavior based on the list + * type. + * <p> + * + * For example, some sorts are n*log(n) on an array, but decay to quadratic + * time on a linked list. As a rule of thumb, this interface should be + * used is this loop:<br> + * <code>for (int i = 0, n = list.size(); i < n; i++) list.get(i);</code> + * <br>runs faster than this loop:<br> + * <code>for (Iterator i = list.iterator(); i.hasNext(); ) i.next();</code> + * + * @author Eric Blake <ebb9@email.byu.edu> + * @see List + * @since 1.4 + * @status updated to 1.4 + */ +public interface RandomAccess +{ + // Tagging interface only. +} diff --git a/libjava/java/util/Set.java b/libjava/java/util/Set.java index 3c8c09b..c22228c 100644 --- a/libjava/java/util/Set.java +++ b/libjava/java/util/Set.java @@ -1,5 +1,5 @@ /* Set.java -- A collection that prohibits duplicates - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,25 +25,208 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comments for everything. - package java.util; +/** + * A collection that contains no duplicates. In other words, for two set + * elements e1 and e2, <code>e1.equals(e2)</code> returns false. There + * are additional stipulations on <code>add</code>, <code>equals</code> + * and <code>hashCode</code>, as well as the requirements that constructors + * do not permit duplicate elements. The Set interface is incompatible with + * List; you cannot implement both simultaneously. + * <p> + * + * Note: Be careful about using mutable objects in sets. In particular, + * if a mutable object changes to become equal to another set element, you + * have violated the contract. As a special case of this, a Set is not + * allowed to be an element of itself, without risking undefined behavior. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Collection + * @see List + * @see SortedSet + * @see HashSet + * @see TreeSet + * @see LinkedHashSet + * @see AbstractSet + * @see Collections#singleton(Object) + * @see Collections#EMPTY_SET + * @since 1.2 + * @status updated to 1.4 + */ public interface Set extends Collection { + /** + * Adds the specified element to the set if it is not already present + * (optional operation). In particular, the comparison algorithm is + * <code>o == null ? e == null : o.equals(e)</code>. Sets need not permit + * all values, and may document what exceptions will be thrown if + * a value is not permitted. + * + * @param o the object to add + * @return true if the object was not previously in the set + * @throws UnsupportedOperationException if this operation is not allowed + * @throws ClassCastException if the class of o prevents it from being added + * @throws IllegalArgumentException if some aspect of o prevents it from + * being added + * @throws NullPointerException if null is not permitted in this set + */ boolean add(Object o); + + /** + * Adds all of the elements of the given collection to this set (optional + * operation). If the argument is also a Set, this returns the mathematical + * <i>union</i> of the two. The behavior is unspecified if the set is + * modified while this is taking place. + * + * @param c the collection to add + * @return true if the set changed as a result + * @throws UnsupportedOperationException if this operation is not allowed + * @throws ClassCastException if the class of an element prevents it from + * being added + * @throws IllegalArgumentException if something about an element prevents + * it from being added + * @throws NullPointerException if null is not permitted in this set, or + * if the argument c is null + * @see #add(Object) + */ boolean addAll(Collection c); + + /** + * Removes all elements from this set (optional operation). This set will + * be empty afterwords, unless an exception occurs. + * + * @throws UnsupportedOperationException if this operation is not allowed + */ void clear(); + + /** + * Returns true if the set contains the specified element. In other words, + * this looks for <code>o == null ? e == null : o.equals(e)</code>. + * + * @param o the object to look for + * @return true if it is found in the set + */ boolean contains(Object o); + + /** + * Returns true if this set contains all elements in the specified + * collection. If the argument is also a set, this is the <i>subset</i> + * relationship. + * + * @param c the collection to check membership in + * @return true if all elements in this set are in c + * @throws NullPointerException if c is null + * @see #contains(Object) + */ boolean containsAll(Collection c); + + /** + * Compares the specified object to this for equality. For sets, the object + * must be a set, the two must have the same size, and every element in + * one must be in the other. + * + * @param o the object to compare to + * @return true if it is an equal set + */ boolean equals(Object o); + + /** + * Returns the hash code for this set. In order to satisfy the contract of + * equals, this is the sum of the hashcode of all elements in the set. + * + * @return the sum of the hashcodes of all set elements + */ int hashCode(); + + /** + * Returns true if the set contains no elements. + * + * @return true if the set is empty + */ boolean isEmpty(); + + /** + * Returns an iterator over the set. The iterator has no specific order, + * unless further specified. + * + * @return a set iterator + */ Iterator iterator(); + + /** + * Removes the specified element from this set (optional operation). If + * an element e exists, <code>o == null ? e == null : o.equals(e)</code>, + * it is removed from the set. + * + * @param o the object to remove + * @return true if the set changed (an object was removed) + * @throws UnsupportedOperationException if this operation is not allowed + */ boolean remove(Object o); + + /** + * Removes from this set all elements contained in the specified collection + * (optional operation). If the argument is a set, this returns the + * <i>asymmetric set difference</i> of the two sets. + * + * @param c the collection to remove from this set + * @return true if this set changed as a result + * @throws UnsupportedOperationException if this operation is not allowed + * @throws NullPointerException if c is null + * @see #remove(Object) + */ boolean removeAll(Collection c); + + /** + * Retains only the elements in this set that are also in the specified + * collection (optional operation). If the argument is also a set, this + * performs the <i>intersection</i> of the two sets. + * + * @param c the collection to keep + * @return true if this set was modified + * @throws UnsupportedOperationException if this operation is not allowed + * @throws NullPointerException if c is null + * @see #remove(Object) + */ boolean retainAll(Collection c); + + /** + * Returns the number of elements in the set. If there are more + * than Integer.MAX_VALUE mappings, return Integer.MAX_VALUE. This is + * the <i>cardinality</i> of the set. + * + * @return the number of elements + */ int size(); + + /** + * Returns an array containing the elements of this set. If the set + * makes a guarantee about iteration order, the array has the same + * order. The array is distinct from the set; modifying one does not + * affect the other. + * + * @return an array of this set's elements + * @see #toArray(Object[]) + */ Object[] toArray(); + + /** + * Returns an array containing the elements of this set, of the same runtime + * type of the argument. If the given set is large enough, it is reused, + * and null is inserted in the first unused slot. Otherwise, reflection + * is used to build a new array. If the set makes a guarantee about iteration + * order, the array has the same order. The array is distinct from the set; + * modifying one does not affect the other. + * + * @param a the array to determine the return type; if it is big enough + * it is used and returned + * @return an array holding the elements of the set + * @throws ArrayStoreException if the runtime type of a is not a supertype + * of all elements in the set + * @throws NullPointerException if a is null + * @see #toArray() + */ + Object[] toArray(Object[] a); } diff --git a/libjava/java/util/SortedMap.java b/libjava/java/util/SortedMap.java index 2de57a1..5be6c19 100644 --- a/libjava/java/util/SortedMap.java +++ b/libjava/java/util/SortedMap.java @@ -1,5 +1,5 @@ /* SortedMap.java -- A map that makes guarantees about the order of its keys - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,17 +25,135 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comments for everything. - package java.util; +/** + * A map which guarantees its key's iteration order. The entries in the + * map are related by the <i>natural ordering</i> of the keys if they + * are Comparable, or by the provided Comparator. Additional operations + * take advantage of the sorted nature of the map. + * <p> + * + * All keys entered in the map must be mutually comparable; in other words, + * <code>k1.compareTo(k2)</code> or <code>comparator.compare(k1, k2)</code> + * must not throw a ClassCastException. The ordering must be <i>consistent + * with equals</i> (see {@link Comparator} for this definition), if the + * map is to obey the general contract of the Map interface. If not, + * the results are well-defined, but probably not what you wanted. + * <p> + * + * It is recommended that all implementing classes provide four constructors: + * 1) one that takes no arguments and builds an empty map sorted by natural + * order of the keys; 2) one that takes a Comparator for the sorting order; + * 3) one that takes a Map and sorts according to the natural order of its + * keys; and 4) one that takes a SortedMap and sorts by the same comparator. + * Unfortunately, the Java language does not provide a way to enforce this. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Map + * @see TreeMap + * @see SortedSet + * @see Comparable + * @see Comparator + * @see Collection + * @see ClassCastException + * @since 1.2 + * @status updated to 1.4 + */ public interface SortedMap extends Map { + /** + * Returns the comparator used in sorting this map, or null if it is + * the keys' natural ordering. + * + * @return the sorting comparator + */ Comparator comparator(); + + /** + * Returns the first (lowest sorted) key in the map. + * + * @return the first key + */ Object firstKey(); + + /** + * Returns a view of the portion of the map strictly less than toKey. The + * view is backed by this map, so changes in one show up in the other. + * The submap supports all optional operations of the original. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of toKey. Note that the endpoint is not + * included; if you want the endpoint, pass the successor object in to + * toKey. For example, for Strings, you can request + * <code>headMap(limit + "\0")</code>. + * + * @param toKey the exclusive upper range of the submap + * @return the submap + * @throws ClassCastException if toKey is not comparable to the map contents + * @throws IllegalArgumentException if this is a subMap, and toKey is out + * of range + * @throws NullPointerException if toKey is null but the map does not allow + * null keys + */ SortedMap headMap(Object toKey); + + /** + * Returns the last (highest sorted) key in the map. + * + * @return the last key + */ Object lastKey(); + + /** + * Returns a view of the portion of the map greater than or equal to + * fromKey, and strictly less than toKey. The view is backed by this map, + * so changes in one show up in the other. The submap supports all + * optional operations of the original. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of fromKey and toKey. Note that the + * lower endpoint is included, but the upper is not; if you want to + * change the inclusion or exclusion of an endpoint, pass the successor + * object in instead. For example, for Strings, you can request + * <code>subMap(lowlimit + "\0", highlimit + "\0")</code> to reverse + * the inclusiveness of both endpoints. + * + * @param fromKey the inclusive lower range of the submap + * @param toKey the exclusive upper range of the submap + * @return the submap + * @throws ClassCastException if fromKey or toKey is not comparable to + * the map contents + * @throws IllegalArgumentException if this is a subMap, and fromKey or + * toKey is out of range + * @throws NullPointerException if fromKey or toKey is null but the map + * does not allow null keys + */ SortedMap subMap(Object fromKey, Object toKey); + + /** + * Returns a view of the portion of the map greater than or equal to + * fromKey. The view is backed by this map, so changes in one show up + * in the other. The submap supports all optional operations of the original. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of fromKey. Note that the endpoint is + * included; if you do not want the endpoint, pass the successor object in + * to fromKey. For example, for Strings, you can request + * <code>tailMap(limit + "\0")</code>. + * + * @param fromKey the inclusive lower range of the submap + * @return the submap + * @throws ClassCastException if fromKey is not comparable to the map + * contents + * @throws IllegalArgumentException if this is a subMap, and fromKey is out + * of range + * @throws NullPointerException if fromKey is null but the map does not allow + * null keys + */ SortedMap tailMap(Object fromKey); } diff --git a/libjava/java/util/SortedSet.java b/libjava/java/util/SortedSet.java index f72dd66..ea39811 100644 --- a/libjava/java/util/SortedSet.java +++ b/libjava/java/util/SortedSet.java @@ -1,6 +1,6 @@ -/* SortedSet.java -- A set that makes guarantees about the order of its +/* SortedSet.java -- A set that makes guarantees about the order of its elements - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -26,17 +26,137 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comments for everything. - package java.util; +/** + * A set which guarantees its iteration order. The elements in the set + * are related by the <i>natural ordering</i> if they are Comparable, or + * by the provided Comparator. Additional operations take advantage of + * the sorted nature of the set. + * <p> + * + * All elements entered in the set must be mutually comparable; in other words, + * <code>k1.compareTo(k2)</code> or <code>comparator.compare(k1, k2)</code> + * must not throw a ClassCastException. The ordering must be <i>consistent + * with equals</i> (see {@link Comparator} for this definition), if the + * map is to obey the general contract of the Set interface. If not, + * the results are well-defined, but probably not what you wanted. + * <p> + * + * It is recommended that all implementing classes provide four constructors: + * 1) one that takes no arguments and builds an empty set sorted by natural + * order of the elements; 2) one that takes a Comparator for the sorting order; + * 3) one that takes a Set and sorts according to the natural order of its + * elements; and 4) one that takes a SortedSet and sorts by the same + * comparator. Unfortunately, the Java language does not provide a way to + * enforce this. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + * @see Set + * @see TreeSet + * @see SortedMap + * @see Collection + * @see Comparable + * @see Comparator + * @see ClassCastException + * @since 1.2 + * @status updated to 1.4 + */ public interface SortedSet extends Set { + /** + * Returns the comparator used in sorting this set, or null if it is + * the elements' natural ordering. + * + * @return the sorting comparator + */ Comparator comparator(); + + /** + * Returns the first (lowest sorted) element in the map. + * + * @return the first element + */ Object first(); + + /** + * Returns a view of the portion of the set strictly less than toElement. The + * view is backed by this set, so changes in one show up in the other. + * The subset supports all optional operations of the original. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of toElement. Note that the endpoint is not + * included; if you want the endpoint, pass the successor object in to + * toElement. For example, for Strings, you can request + * <code>headSet(limit + "\0")</code>. + * + * @param toElement the exclusive upper range of the subset + * @return the subset + * @throws ClassCastException if toElement is not comparable to the set + * contents + * @throws IllegalArgumentException if this is a subSet, and toElement is out + * of range + * @throws NullPointerException if toElement is null but the map does not + * allow null elements + */ SortedSet headSet(Object toElement); + + /** + * Returns the last (highest sorted) element in the map. + * + * @return the last element + */ Object last(); + + /** + * Returns a view of the portion of the set greater than or equal to + * fromElement, and strictly less than toElement. The view is backed by + * this set, so changes in one show up in the other. The subset supports all + * optional operations of the original. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of fromElement and toElement. Note that the + * lower endpoint is included, but the upper is not; if you want to + * change the inclusion or exclusion of an endpoint, pass the successor + * object in instead. For example, for Strings, you can request + * <code>subSet(lowlimit + "\0", highlimit + "\0")</code> to reverse + * the inclusiveness of both endpoints. + * + * @param fromElement the inclusive lower range of the subset + * @param toElement the exclusive upper range of the subset + * @return the subset + * @throws ClassCastException if fromElement or toElement is not comparable + * to the set contents + * @throws IllegalArgumentException if this is a subSet, and fromElement or + * toElement is out of range + * @throws NullPointerException if fromElement or toElement is null but the + * set does not allow null elements + */ SortedSet subSet(Object fromElement, Object toElement); + + /** + * Returns a view of the portion of the set greater than or equal to + * fromElement. The view is backed by this set, so changes in one show up + * in the other. The subset supports all optional operations of the original. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of fromElement. Note that the endpoint is + * included; if you do not want the endpoint, pass the successor object in + * to fromElement. For example, for Strings, you can request + * <code>tailSet(limit + "\0")</code>. + * + * @param fromElement the inclusive lower range of the subset + * @return the subset + * @throws ClassCastException if fromElement is not comparable to the set + * contents + * @throws IllegalArgumentException if this is a subSet, and fromElement is + * out of range + * @throws NullPointerException if fromElement is null but the set does not + * allow null elements + */ SortedSet tailSet(Object fromElement); } |