harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From le...@apache.org
Subject svn commit: r549743 [3/3] - in /harmony/enhanced/classlib/branches/java6/modules/luni/src: main/java/java/util/ test/api/common/tests/api/java/util/
Date Fri, 22 Jun 2007 07:32:13 GMT
Modified: harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeSet.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeSet.java?view=diff&rev=549743&r1=549742&r2=549743
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeSet.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeSet.java Fri Jun 22 00:32:12 2007
@@ -17,146 +17,152 @@
 
 package java.util;
 
-
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 
 /**
- * TreeSet is an implementation of SortedSet. All optional operations are
+ * TreeSet is an implementation of NavigableSet. All optional operations are
  * supported, adding and removing. The elements can be any objects which are
  * comparable to each other either using their natural order or a specified
  * Comparator.
+ * 
+ * @param <E>
+ *            type of element
+ * 
  * @since 1.2
  */
-public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>, Cloneable,
-		Serializable {
-	
+public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>,
+        Cloneable, Serializable {
+
     private static final long serialVersionUID = -2479143000061671589L;
 
-    private transient SortedMap<E, E> backingMap;
+    transient NavigableMap<E, E> backingMap;
+
+    transient NavigableSet<E> descendingSet;
+
+    TreeSet(NavigableMap<E, E> map) {
+        backingMap = map;
+    }
+
+    /**
+     * Constructs a new empty instance of TreeSet which uses natural ordering.
+     * 
+     */
+    public TreeSet() {
+        backingMap = new TreeMap<E, E>();
+    }
 
-    private TreeSet(SortedMap<E,E> map) {
-        this.backingMap = map;
+    /**
+     * Constructs a new instance of TreeSet which uses natural ordering and
+     * containing the unique elements in the specified collection.
+     * 
+     * @param collection
+     *            the collection of elements to add
+     * 
+     * @exception ClassCastException
+     *                when an element in the Collection does not implement the
+     *                Comparable interface, or the elements in the Collection
+     *                cannot be compared
+     */
+    public TreeSet(Collection<? extends E> collection) {
+        this();
+        addAll(collection);
+    }
+
+    /**
+     * Constructs a new empty instance of TreeSet which uses the specified
+     * Comparator.
+     * 
+     * @param comparator
+     *            the Comparator
+     */
+    public TreeSet(Comparator<? super E> comparator) {
+        backingMap = new TreeMap<E, E>(comparator);
+    }
+
+    /**
+     * Constructs a new instance of TreeSet containing the elements in the
+     * specified SortedSet and using the same Comparator.
+     * 
+     * @param set
+     *            the SortedSet of elements to add
+     */
+    public TreeSet(SortedSet<E> set) {
+        this(set.comparator());
+        Iterator<E> it = set.iterator();
+        while (it.hasNext()) {
+            add(it.next());
+        }
     }
 
-	/**
-	 * Constructs a new empty instance of TreeSet which uses natural ordering.
-	 * 
-	 */
-	public TreeSet() {
-		backingMap = new TreeMap<E, E>();
-	}
-
-	/**
-	 * Constructs a new instance of TreeSet which uses natural ordering and
-	 * containing the unique elements in the specified collection.
-	 * 
-	 * @param collection
-	 *            the collection of elements to add
-	 * 
-	 * @exception ClassCastException
-	 *                when an element in the Collection does not implement the
-	 *                Comparable interface, or the elements in the Collection
-	 *                cannot be compared
-	 */
-	public TreeSet(Collection<? extends E> collection) {
-		this();
-		addAll(collection);
-	}
-
-	/**
-	 * Constructs a new empty instance of TreeSet which uses the specified
-	 * Comparator.
-	 * 
-	 * @param comparator
-	 *            the Comparator
-	 */
-	public TreeSet(Comparator<? super E> comparator) {
-		backingMap = new TreeMap<E, E>(comparator);
-	}
-
-	/**
-	 * Constructs a new instance of TreeSet containing the elements in the
-	 * specified SortedSet and using the same Comparator.
-	 * 
-	 * @param set
-	 *            the SortedSet of elements to add
-	 */
-	public TreeSet(SortedSet<E> set) {
-	    this(set.comparator());
-	    Iterator<E> it = set.iterator();
-	    while (it.hasNext()) {
-	        add(it.next());
-	    }
-	}
-
-	/**
-	 * Adds the specified object to this TreeSet.
-	 * 
-	 * @param object
-	 *            the object to add
-	 * @return true when this TreeSet did not already contain the object, false
-	 *         otherwise
-	 * 
-	 * @exception ClassCastException
-	 *                when the object cannot be compared with the elements in
-	 *                this TreeSet
-	 * @exception NullPointerException
-	 *                when the object is null and the comparator cannot handle
-	 *                null
-	 */
-	@Override
+    /**
+     * Adds the specified object to this TreeSet.
+     * 
+     * @param object
+     *            the object to add
+     * @return true when this TreeSet did not already contain the object, false
+     *         otherwise
+     * 
+     * @exception ClassCastException
+     *                when the object cannot be compared with the elements in
+     *                this TreeSet
+     * @exception NullPointerException
+     *                when the object is null and the comparator cannot handle
+     *                null
+     */
+    @Override
     public boolean add(E object) {
-		return backingMap.put(object, object) == null;
-	}
+        return backingMap.put(object, object) == null;
+    }
 
-	/**
-	 * Adds the objects in the specified Collection to this TreeSet.
-	 * 
-	 * @param collection
-	 *            the Collection of objects
-	 * @return true if this TreeSet is modified, false otherwise
-	 * 
-	 * @exception ClassCastException
-	 *                when an object in the Collection cannot be compared with
-	 *                the elements in this TreeSet
-	 * @exception NullPointerException
-	 *                when an object in the Collection is null and the
-	 *                comparator cannot handle null
-	 */
-	@Override
+    /**
+     * Adds the objects in the specified Collection to this TreeSet.
+     * 
+     * @param collection
+     *            the Collection of objects
+     * @return true if this TreeSet is modified, false otherwise
+     * 
+     * @exception ClassCastException
+     *                when an object in the Collection cannot be compared with
+     *                the elements in this TreeSet
+     * @exception NullPointerException
+     *                when an object in the Collection is null and the
+     *                comparator cannot handle null
+     */
+    @Override
     public boolean addAll(Collection<? extends E> collection) {
-		return super.addAll(collection);
-	}
+        return super.addAll(collection);
+    }
 
-	/**
-	 * Removes all elements from this TreeSet, leaving it empty.
-	 * 
-	 * @see #isEmpty
-	 * @see #size
-	 */
-	@Override
+    /**
+     * Removes all elements from this TreeSet, leaving it empty.
+     * 
+     * @see #isEmpty
+     * @see #size
+     */
+    @Override
     public void clear() {
-		backingMap.clear();
-	}
+        backingMap.clear();
+    }
 
-	/**
-	 * Answers a new TreeSet with the same elements, size and comparator as this
-	 * TreeSet.
-	 * 
-	 * @return a shallow copy of this TreeSet
-	 * 
-	 * @see java.lang.Cloneable
-	 */
-	@SuppressWarnings("unchecked")
+    /**
+     * Answers a new TreeSet with the same elements, size and comparator as this
+     * TreeSet.
+     * 
+     * @return a shallow copy of this TreeSet
+     * 
+     * @see java.lang.Cloneable
+     */
+    @SuppressWarnings("unchecked")
     @Override
     public Object clone() {
         try {
             TreeSet<E> clone = (TreeSet<E>) super.clone();
             if (backingMap instanceof TreeMap) {
-                clone.backingMap = (SortedMap<E, E>) ((TreeMap<E, E>) backingMap).clone();
+                clone.backingMap = (NavigableMap<E, E>) ((TreeMap<E, E>) backingMap)
+                        .clone();
             } else {
                 clone.backingMap = new TreeMap<E, E>(backingMap);
             }
@@ -166,239 +172,354 @@
         }
     }
 
-	/**
+    /**
      * Answers the Comparator used to compare elements in this TreeSet.
      * 
      * @return a Comparator or null if the natural ordering is used
      */
-	public Comparator<? super E> comparator() {
-		return backingMap.comparator();
-	}
-
-	/**
-	 * Searches this TreeSet for the specified object.
-	 * 
-	 * @param object
-	 *            the object to search for
-	 * @return true if <code>object</code> is an element of this TreeSet,
-	 *         false otherwise
-	 * 
-	 * @exception ClassCastException
-	 *                when the object cannot be compared with the elements in
-	 *                this TreeSet
-	 * @exception NullPointerException
-	 *                when the object is null and the comparator cannot handle
-	 *                null
-	 */
-	@Override
+    public Comparator<? super E> comparator() {
+        return backingMap.comparator();
+    }
+
+    /**
+     * Searches this TreeSet for the specified object.
+     * 
+     * @param object
+     *            the object to search for
+     * @return true if <code>object</code> is an element of this TreeSet,
+     *         false otherwise
+     * 
+     * @exception ClassCastException
+     *                when the object cannot be compared with the elements in
+     *                this TreeSet
+     * @exception NullPointerException
+     *                when the object is null and the comparator cannot handle
+     *                null
+     */
+    @Override
     public boolean contains(Object object) {
-		return backingMap.containsKey(object);
-	}
+        return backingMap.containsKey(object);
+    }
 
-	/**
-	 * Answers the first element in this TreeSet.
-	 * 
-	 * @return the first element
-	 * 
-	 * @exception NoSuchElementException
-	 *                when this TreeSet is empty
-	 */
-	public E first() {
-		return backingMap.firstKey();
-	}
-
-	/**
-	 * Answers a SortedSet of the specified portion of this TreeSet which
-	 * contains elements less than the end element. The returned SortedSet is
-	 * backed by this TreeSet so changes to one are reflected by the other.
-	 * 
-	 * @param end
-	 *            the end element
-	 * @return a subset where the elements are less than <code>end</code>
-	 * 
-	 * @exception ClassCastException
-	 *                when the end object cannot be compared with the elements
-	 *                in this TreeSet
-	 * @exception NullPointerException
-	 *                when the end object is null and the comparator cannot
-	 *                handle null
-	 */
-	@SuppressWarnings("unchecked")
-    public SortedSet<E> headSet(E end) {
-	    // Check for errors
-	    Comparator<? super E> c = backingMap.comparator();
-	    if (c == null) {
-	        ((Comparable<E>) end).compareTo(end);
-	    } else {
-	        c.compare(end, end);
-	    }
-	    return new TreeSet<E>(backingMap.headMap(end));
-	}
-
-	/**
-	 * Answers if this TreeSet has no elements, a size of zero.
-	 * 
-	 * @return true if this TreeSet has no elements, false otherwise
-	 * 
-	 * @see #size
-	 */
-	@Override
+    /**
+     * Answers if this TreeSet has no elements, a size of zero.
+     * 
+     * @return true if this TreeSet has no elements, false otherwise
+     * 
+     * @see #size
+     */
+    @Override
     public boolean isEmpty() {
-		return backingMap.isEmpty();
-	}
+        return backingMap.isEmpty();
+    }
 
-	/**
-	 * Answers an Iterator on the elements of this TreeSet.
-	 * 
-	 * @return an Iterator on the elements of this TreeSet
-	 * 
-	 * @see Iterator
-	 */
-	@Override
+    /**
+     * Answers an Iterator on the elements of this TreeSet.
+     * 
+     * @return an Iterator on the elements of this TreeSet
+     * 
+     * @see Iterator
+     */
+    @Override
     public Iterator<E> iterator() {
-		return backingMap.keySet().iterator();
-	}
+        return backingMap.keySet().iterator();
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#descendingIterator()
+     * @since 1.6
+     */
+    public Iterator<E> descendingIterator() {
+        return descendingSet().iterator();
+    }
 
-	/**
-	 * Answers the last element in this TreeSet.
-	 * 
-	 * @return the last element
-	 * 
-	 * @exception NoSuchElementException
-	 *                when this TreeSet is empty
-	 */
-	public E last() {
-		return backingMap.lastKey();
-	}
-
-	/**
-	 * Removes an occurrence of the specified object from this TreeSet.
-	 * 
-	 * @param object
-	 *            the object to remove
-	 * @return true if this TreeSet is modified, false otherwise
-	 * 
-	 * @exception ClassCastException
-	 *                when the object cannot be compared with the elements in
-	 *                this TreeSet
-	 * @exception NullPointerException
-	 *                when the object is null and the comparator cannot handle
-	 *                null
-	 */
-	@Override
+    /**
+     * Removes an occurrence of the specified object from this TreeSet.
+     * 
+     * @param object
+     *            the object to remove
+     * @return true if this TreeSet is modified, false otherwise
+     * 
+     * @exception ClassCastException
+     *                when the object cannot be compared with the elements in
+     *                this TreeSet
+     * @exception NullPointerException
+     *                when the object is null and the comparator cannot handle
+     *                null
+     */
+    @Override
     public boolean remove(Object object) {
-		return backingMap.remove(object) != null;
-	}
+        return backingMap.remove(object) != null;
+    }
 
-	/**
-	 * Answers the number of elements in this TreeSet.
-	 * 
-	 * @return the number of elements in this TreeSet
-	 */
-	@Override
+    /**
+     * Answers the number of elements in this TreeSet.
+     * 
+     * @return the number of elements in this TreeSet
+     */
+    @Override
     public int size() {
-		return backingMap.size();
-	}
+        return backingMap.size();
+    }
 
-	/**
-	 * Answers a SortedSet of the specified portion of this TreeSet which
-	 * contains elements greater or equal to the start element but less than the
-	 * end element. The returned SortedSet is backed by this TreeSet so changes
-	 * to one are reflected by the other.
-	 * 
-	 * @param start
-	 *            the start element
-	 * @param end
-	 *            the end element
-	 * @return a subset where the elements are greater or equal to
-	 *         <code>start</code> and less than <code>end</code>
-	 * 
-	 * @exception ClassCastException
-	 *                when the start or end object cannot be compared with the
-	 *                elements in this TreeSet
-	 * @exception NullPointerException
-	 *                when the start or end object is null and the comparator
-	 *                cannot handle null
-	 */
-	@SuppressWarnings("unchecked")
-    public SortedSet<E> subSet(E start, E end) {
+    /**
+     * Answers the first element in this TreeSet.
+     * 
+     * @return the first element
+     * 
+     * @exception NoSuchElementException
+     *                when this TreeSet is empty
+     */
+    public E first() {
+        return backingMap.firstKey();
+    }
+
+    /**
+     * Answers the last element in this TreeSet.
+     * 
+     * @return the last element
+     * 
+     * @exception NoSuchElementException
+     *                when this TreeSet is empty
+     */
+    public E last() {
+        return backingMap.lastKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#pollFirst()
+     * @since 1.6
+     */
+    public E pollFirst() {
+        Map.Entry<E, E> entry = backingMap.pollFirstEntry();
+        return (null == entry) ? null : entry.getKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#pollLast()
+     * @since 1.6
+     */
+    public E pollLast() {
+        Map.Entry<E, E> entry = backingMap.pollLastEntry();
+        return (null == entry) ? null : entry.getKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#higher(java.lang.Object)
+     * @since 1.6
+     */
+    public E higher(E e) {
+        return backingMap.higherKey(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#lower(java.lang.Object)
+     * @since 1.6
+     */
+    public E lower(E e) {
+        return backingMap.lowerKey(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#ceiling(java.lang.Object)
+     * @since 1.6
+     */
+    public E ceiling(E e) {
+        return backingMap.ceilingKey(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#floor(java.lang.Object)
+     * @since 1.6
+     */
+    public E floor(E e) {
+        return backingMap.floorKey(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#descendingSet()
+     * @since 1.6
+     */
+    public NavigableSet<E> descendingSet() {
+        return (null != descendingSet) ? descendingSet
+                : (descendingSet = new TreeSet<E>(backingMap.descendingMap()));
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#subSet(Object, boolean, Object, boolean)
+     * @since 1.6
+     */
+    @SuppressWarnings("unchecked")
+    public NavigableSet<E> subSet(E start, boolean startInclusive, E end,
+            boolean endInclusive) {
+        Comparator<? super E> c = backingMap.comparator();
+        int compare = (c == null) ? ((Comparable<E>) start).compareTo(end) : c
+                .compare(start, end);
+        if (compare <= 0) {
+            return new TreeSet<E>(backingMap.subMap(start, startInclusive, end,
+                    endInclusive));
+        }
+        throw new IllegalArgumentException();
+    }
+
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#headSet(Object, boolean)
+     * @since 1.6
+     */
+    @SuppressWarnings("unchecked")
+    public NavigableSet<E> headSet(E end, boolean endInclusive) {
+        // Check for errors
         Comparator<? super E> c = backingMap.comparator();
         if (c == null) {
-            if (((Comparable<E>) start).compareTo(end) <= 0) {
-                return new TreeSet<E>(backingMap.subMap(start, end));
-            }
+            ((Comparable<E>) end).compareTo(end);
         } else {
-            if (c.compare(start, end) <= 0) {
-                return new TreeSet<E>(backingMap.subMap(start, end));
-            }
+            c.compare(end, end);
         }
-        throw new IllegalArgumentException();
+        return new TreeSet<E>(backingMap.headMap(end, endInclusive));
     }
 
-	/**
-	 * Answers a SortedSet of the specified portion of this TreeSet which
-	 * contains elements greater or equal to the start element. The returned
-	 * SortedSet is backed by this TreeSet so changes to one are reflected by
-	 * the other.
-	 * 
-	 * @param start
-	 *            the start element
-	 * @return a subset where the elements are greater or equal to
-	 *         <code>start</code>
-	 * 
-	 * @exception ClassCastException
-	 *                when the start object cannot be compared with the elements
-	 *                in this TreeSet
-	 * @exception NullPointerException
-	 *                when the start object is null and the comparator cannot
-	 *                handle null
-	 */
-	@SuppressWarnings("unchecked")
-    public SortedSet<E> tailSet(E start) {
-		// Check for errors
-		Comparator<? super E> c = backingMap.comparator();
-		if (c == null) {
+    /**
+     * {@inheritDoc}
+     * 
+     * @see java.util.NavigableSet#tailSet(Object, boolean)
+     * @since 1.6
+     */
+    @SuppressWarnings("unchecked")
+    public NavigableSet<E> tailSet(E start, boolean startInclusive) {
+        // Check for errors
+        Comparator<? super E> c = backingMap.comparator();
+        if (c == null) {
             ((Comparable<E>) start).compareTo(start);
         } else {
             c.compare(start, start);
         }
-		return new TreeSet<E>(backingMap.tailMap(start));
-	}
+        return new TreeSet<E>(backingMap.tailMap(start, startInclusive));
+    }
 
-	private void writeObject(ObjectOutputStream stream) throws IOException {
-	    stream.defaultWriteObject();
-	    stream.writeObject(backingMap.comparator());
-	    int size = backingMap.size();
-	    stream.writeInt(size);
-	    if (size > 0) {
-	        Iterator<E> it = backingMap.keySet().iterator();
-	        while (it.hasNext()) {
-	            stream.writeObject(it.next());
-	        }
-	    }
-	}
-
-	@SuppressWarnings("unchecked")
-	private void readObject(ObjectInputStream stream) throws IOException,
-	ClassNotFoundException {
-	    stream.defaultReadObject();
-	    TreeMap<E, E> map = new TreeMap<E, E>((Comparator<? super E>) stream.readObject());
-	    int size = stream.readInt();
-	    if (size > 0) {
-	        E key = (E)stream.readObject();
-	        TreeMap.Entry<E,E> last = new TreeMap.Entry<E,E>(key,key);
-	        map.root = last;
-	        map.size = 1;
-	        for (int i=1; i<size; i++) {
-	            key = (E)stream.readObject();
-	            TreeMap.Entry<E,E> x = new TreeMap.Entry<E,E>(key,key);
-	            x.parent = last;
-	            last.right = x;
-	            map.size++;
-	            map.balance(x);
-	            last = x;
-	        }
-	    }
-	    backingMap = map;
-	}
+    /**
+     * Answers a SortedSet of the specified portion of this TreeSet which
+     * contains elements greater or equal to the start element but less than the
+     * end element. The returned SortedSet is backed by this TreeSet so changes
+     * to one are reflected by the other.
+     * 
+     * @param start
+     *            the start element
+     * @param end
+     *            the end element
+     * @return a subset where the elements are greater or equal to
+     *         <code>start</code> and less than <code>end</code>
+     * 
+     * @exception ClassCastException
+     *                when the start or end object cannot be compared with the
+     *                elements in this TreeSet
+     * @exception NullPointerException
+     *                when the start or end object is null and the comparator
+     *                cannot handle null
+     */
+    @SuppressWarnings("unchecked")
+    public SortedSet<E> subSet(E start, E end) {
+        return subSet(start, true, end, false);
+    }
+
+    /**
+     * Answers a SortedSet of the specified portion of this TreeSet which
+     * contains elements less than the end element. The returned SortedSet is
+     * backed by this TreeSet so changes to one are reflected by the other.
+     * 
+     * @param end
+     *            the end element
+     * @return a subset where the elements are less than <code>end</code>
+     * 
+     * @exception ClassCastException
+     *                when the end object cannot be compared with the elements
+     *                in this TreeSet
+     * @exception NullPointerException
+     *                when the end object is null and the comparator cannot
+     *                handle null
+     */
+    @SuppressWarnings("unchecked")
+    public SortedSet<E> headSet(E end) {
+        return headSet(end, false);
+    }
+
+    /**
+     * Answers a SortedSet of the specified portion of this TreeSet which
+     * contains elements greater or equal to the start element. The returned
+     * SortedSet is backed by this TreeSet so changes to one are reflected by
+     * the other.
+     * 
+     * @param start
+     *            the start element
+     * @return a subset where the elements are greater or equal to
+     *         <code>start</code>
+     * 
+     * @exception ClassCastException
+     *                when the start object cannot be compared with the elements
+     *                in this TreeSet
+     * @exception NullPointerException
+     *                when the start object is null and the comparator cannot
+     *                handle null
+     */
+    @SuppressWarnings("unchecked")
+    public SortedSet<E> tailSet(E start) {
+        return tailSet(start, true);
+    }
+
+    private void writeObject(ObjectOutputStream stream) throws IOException {
+        stream.defaultWriteObject();
+        stream.writeObject(backingMap.comparator());
+        int size = backingMap.size();
+        stream.writeInt(size);
+        if (size > 0) {
+            Iterator<E> it = backingMap.keySet().iterator();
+            while (it.hasNext()) {
+                stream.writeObject(it.next());
+            }
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private void readObject(ObjectInputStream stream) throws IOException,
+            ClassNotFoundException {
+        stream.defaultReadObject();
+        TreeMap<E, E> map = new TreeMap<E, E>((Comparator<? super E>) stream
+                .readObject());
+        int size = stream.readInt();
+        if (size > 0) {
+            E key = (E) stream.readObject();
+            TreeMap.Entry<E, E> last = new TreeMap.Entry<E, E>(key, key);
+            map.root = last;
+            map.size = 1;
+            for (int i = 1; i < size; i++) {
+                key = (E) stream.readObject();
+                TreeMap.Entry<E, E> x = new TreeMap.Entry<E, E>(key, key);
+                x.parent = last;
+                last.right = x;
+                map.size++;
+                map.balance(x);
+                last = x;
+            }
+        }
+        backingMap = map;
+    }
 }

Modified: harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeMapTest.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeMapTest.java?view=diff&rev=549743&r1=549742&r2=549743
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeMapTest.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeMapTest.java Fri Jun 22 00:32:12 2007
@@ -17,18 +17,32 @@
 
 package tests.api.java.util;
 
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.text.CollationKey;
 import java.text.Collator;
 import java.util.AbstractMap;
+import java.util.Arrays;
+import java.util.BitSet;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Iterator;
+import java.util.LinkedList;
 import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Random;
 import java.util.Set;
 import java.util.SortedMap;
 import java.util.TreeMap;
+import java.util.Map.Entry;
 
 import org.apache.harmony.testframework.serialization.SerializationTest;
 
@@ -74,6 +88,9 @@
             if (null == o1) {
                 return -1;
             }
+            if (null == o2) {
+                return 1;
+            }
             return o1.compareTo(o2);
         }
     }
@@ -261,12 +278,24 @@
         Object o = new Object();
         tm.put("Hello", o);
         assertTrue("Failed to get mapping", tm.get("Hello") == o);
-
+        
+		// Test for the same key & same value
+		tm = new TreeMap();
+		Object o2 = new Object();
+		Integer key1 = 1;
+		Integer key2 = 2;
+		assertNull(tm.put(key1, o));
+		assertNull(tm.put(key2, o));
+		assertEquals(2, tm.values().size());
+		assertEquals(2, tm.keySet().size());
+		assertSame(tm.get(key1), tm.get(key2));
+		assertSame(o, tm.put(key1, o2));
+		assertSame(o2, tm.get(key1));
     }
 
     /**
-     * @tests java.util.TreeMap#headMap(java.lang.Object)
-     */
+	 * @tests java.util.TreeMap#headMap(java.lang.Object)
+	 */
     public void test_headMapLjava_lang_Object() {
         // Test for method java.util.SortedMap
         // java.util.TreeMap.headMap(java.lang.Object)
@@ -327,6 +356,14 @@
         treemap = new TreeMap();
 		SortedMap<String, String> headMap =  treemap.headMap("100");
 		headMap.headMap("100");
+		
+		TreeMap t = new TreeMap();
+		try {
+            SortedMap th = t.headMap(null);
+            fail("Should throw a NullPointerException");
+        } catch( NullPointerException npe) {
+            // expected
+        }
     }
 
     /**
@@ -350,6 +387,13 @@
         // Test for method java.lang.Object java.util.TreeMap.lastKey()
         assertTrue("Returned incorrect last key", tm.lastKey().equals(
                 objArray[objArray.length - 1].toString()));
+        assertNotSame(objArray[objArray.length - 1].toString(), tm.lastKey());
+		assertEquals(objArray[objArray.length - 2].toString(), tm
+				.headMap("999").lastKey());
+		assertEquals(objArray[objArray.length - 1].toString(), tm
+				.tailMap("123").lastKey());
+		assertEquals(objArray[objArray.length - 2].toString(), tm.subMap("99",
+				"999").lastKey());
     }
 
     /**
@@ -374,10 +418,24 @@
 
         tm = new TreeMap();
         assertNull(tm.put(new Integer(1), new Object()));
+        
+        try {
+			tm.put(new Object(), new Object());
+			fail("Should throw a ClassCastException");
+		} catch (ClassCastException e) {
+			// expected
+		}
 
         // regression for Harmony-2474
+        // but RI6 changes its behavior
+        // so the test changes too
         tm = new TreeMap();
-        tm.remove(o);
+        try {
+            tm.remove(o);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            //expected
+        }
     }
 
     /**
@@ -411,11 +469,29 @@
     public void test_size() {
         // Test for method int java.util.TreeMap.size()
         assertEquals("Returned incorrect size", 1000, tm.size());
+		assertEquals("Returned incorrect size", 447, tm.headMap("500").size());
+		assertEquals("Returned incorrect size", 1000, tm.headMap("null").size());
+		assertEquals("Returned incorrect size", 0, tm.headMap("").size());
+		assertEquals("Returned incorrect size", 448, tm.headMap("500a").size());
+		assertEquals("Returned incorrect size", 553, tm.tailMap("500").size());
+		assertEquals("Returned incorrect size", 0, tm.tailMap("null").size());
+		assertEquals("Returned incorrect size", 1000, tm.tailMap("").size());
+		assertEquals("Returned incorrect size", 552, tm.tailMap("500a").size());
+		assertEquals("Returned incorrect size", 111, tm.subMap("500", "600")
+				.size());
+		try {
+			tm.subMap("null", "600");
+			fail("Should throw an IllegalArgumentException");
+		} catch (IllegalArgumentException e) {
+			// expected
+		}
+		assertEquals("Returned incorrect size", 1000, tm.subMap("", "null")
+				.size()); 
     }
 
     /**
-     * @tests java.util.TreeMap#subMap(java.lang.Object, java.lang.Object)
-     */
+	 * @tests java.util.TreeMap#subMap(java.lang.Object, java.lang.Object)
+	 */
     public void test_subMapLjava_lang_ObjectLjava_lang_Object() {
         // Test for method java.util.SortedMap
         // java.util.TreeMap.subMap(java.lang.Object, java.lang.Object)
@@ -451,6 +527,14 @@
         assertEquals("3", map.lastKey());
         SortedMap<String, String> sub = map.subMap("1", "3"); //$NON-NLS-1$ //$NON-NLS-2$
         assertEquals("2", sub.lastKey()); //$NON-NLS-1$
+        
+        TreeMap t = new TreeMap();
+        try {
+			SortedMap th = t.subMap(null,new Object());
+			fail("Should throw a NullPointerException");
+        } catch( NullPointerException npe) {
+        	// expected
+        }
     }
 
     /**
@@ -469,6 +553,14 @@
 
         // Regression for Harmony-1066
         assertTrue(tail instanceof Serializable);
+        
+        TreeMap t = new TreeMap();
+        try {
+            SortedMap th = t.tailMap(null);
+            fail("Should throw a NullPointerException");
+        } catch( NullPointerException npe) {
+            // expected
+        }
     }
 
     /**
@@ -521,6 +613,988 @@
         // This assertion will fail on RI. This is a bug of RI.
         SerializationTest.verifySelf(headMap);
     }
+    
+    /**
+     * @tests {@link java.util.TreeMap#firstEntry()}
+     */
+    public void test_firstEntry() throws Exception {
+        Integer testint = new Integer(-1);
+        Integer testint10000 = new Integer(-10000);
+        Integer testint9999 = new Integer(-9999);
+        assertEquals(objArray[0].toString(), tm.firstEntry().getKey());
+        assertEquals(objArray[0], tm.firstEntry().getValue());
+        tm.put(testint.toString(), testint);
+        assertEquals(testint.toString(), tm.firstEntry().getKey());
+        assertEquals(testint, tm.firstEntry().getValue());
+        tm.put(testint10000.toString(), testint10000);
+        assertEquals(testint.toString(), tm.firstEntry().getKey());
+        assertEquals(testint, tm.firstEntry().getValue());
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint.toString(), tm.firstEntry().getKey());
+        Entry entry = tm.firstEntry();
+        assertEquals(testint, entry.getValue());
+        assertEntry(entry);
+        tm.clear();
+        assertNull(tm.firstEntry());
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#lastEntry()
+     */
+    public void test_lastEntry() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999].toString(), tm.lastEntry().getKey());
+        assertEquals(objArray[999], tm.lastEntry().getValue());
+        tm.put(testint10000.toString(), testint10000);
+        assertEquals(objArray[999].toString(), tm.lastEntry().getKey());
+        assertEquals(objArray[999], tm.lastEntry().getValue());
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint9999.toString(), tm.lastEntry().getKey());
+        Entry entry = tm.lastEntry();
+        assertEquals(testint9999, entry.getValue());
+        assertEntry(entry);
+        tm.clear();
+        assertNull(tm.lastEntry());
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#pollFirstEntry()
+     */
+    public void test_pollFirstEntry() throws Exception {
+        Integer testint = new Integer(-1);
+        Integer testint10000 = new Integer(-10000);
+        Integer testint9999 = new Integer(-9999);
+        assertEquals(objArray[0].toString(), tm.pollFirstEntry().getKey());
+        assertEquals(objArray[1], tm.pollFirstEntry().getValue());
+        assertEquals(objArray[10], tm.pollFirstEntry().getValue());
+        tm.put(testint.toString(), testint);
+        tm.put(testint10000.toString(), testint10000);
+        assertEquals(testint.toString(), tm.pollFirstEntry().getKey());
+        assertEquals(testint10000, tm.pollFirstEntry().getValue());
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint9999.toString(), tm.pollFirstEntry().getKey());
+        Entry entry = tm.pollFirstEntry();
+        assertEntry(entry);
+        assertEquals(objArray[100], entry.getValue());
+        tm.clear();
+        assertNull(tm.pollFirstEntry());
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#pollLastEntry()
+     */
+    public void test_pollLastEntry() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999].toString(), tm.pollLastEntry().getKey());
+        assertEquals(objArray[998], tm.pollLastEntry().getValue());
+        assertEquals(objArray[997], tm.pollLastEntry().getValue());
+        tm.put(testint10000.toString(), testint10000);
+        assertEquals(objArray[996], tm.pollLastEntry().getValue());
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint9999.toString(), tm.pollLastEntry().getKey());
+        Entry entry = tm.pollLastEntry();
+        assertEquals(objArray[995], entry.getValue());
+        assertEntry(entry);
+        tm.clear();
+        assertNull(tm.pollLastEntry());
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#lowerEntry(Object)
+     */
+    public void test_lowerEntry() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999], tm.lowerEntry(testint9999.toString())
+                .getValue());
+        assertEquals(objArray[100], tm.lowerEntry(testint10000.toString())
+                .getValue());
+        tm.put(testint10000.toString(), testint10000);
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(objArray[999], tm.lowerEntry(testint9999.toString())
+                .getValue());
+        Entry entry = tm.lowerEntry(testint10000.toString());
+        assertEquals(objArray[100], entry.getValue());
+        assertEntry(entry);
+        try {
+            tm.lowerEntry(testint10000);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.lowerEntry(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.lowerEntry(testint9999.toString()));
+        assertNull(tm.lowerEntry(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#lowerKey(Object)
+     */
+    public void test_lowerKey() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999].toString(), tm.lowerKey(testint9999
+                .toString()));
+        assertEquals(objArray[100].toString(), tm.lowerKey(testint10000
+                .toString()));
+        tm.put(testint10000.toString(), testint10000);
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(objArray[999].toString(), tm.lowerKey(testint9999
+                .toString()));
+        assertEquals(objArray[100].toString(), tm.lowerKey(testint10000
+                .toString()));
+        try {
+            tm.lowerKey(testint10000);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.lowerKey(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.lowerKey(testint9999.toString()));
+        assertNull(tm.lowerKey(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#floorEntry(Object)
+     */
+    public void test_floorEntry() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999], tm.floorEntry(testint9999.toString())
+                .getValue());
+        assertEquals(objArray[100], tm.floorEntry(testint10000.toString())
+                .getValue());
+        tm.put(testint10000.toString(), testint10000);
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint9999, tm.floorEntry(testint9999.toString())
+                .getValue());
+        Entry entry = tm.floorEntry(testint10000.toString());
+        assertEquals(testint10000, entry.getValue());
+        assertEntry(entry);
+        try {
+            tm.floorEntry(testint10000);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.floorEntry(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.floorEntry(testint9999.toString()));
+        assertNull(tm.floorEntry(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#floorKey(Object)
+     */
+    public void test_floorKey() throws Exception {
+        Integer testint10000 = new Integer(10000);
+        Integer testint9999 = new Integer(9999);
+        assertEquals(objArray[999].toString(), tm.floorKey(testint9999
+                .toString()));
+        assertEquals(objArray[100].toString(), tm.floorKey(testint10000
+                .toString()));
+        tm.put(testint10000.toString(), testint10000);
+        tm.put(testint9999.toString(), testint9999);
+        assertEquals(testint9999.toString(), tm
+                .floorKey(testint9999.toString()));
+        assertEquals(testint10000.toString(), tm.floorKey(testint10000
+                .toString()));
+        try {
+            tm.floorKey(testint10000);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.floorKey(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.floorKey(testint9999.toString()));
+        assertNull(tm.floorKey(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#ceilingEntry(Object)
+     */
+    public void test_ceilingEntry() throws Exception {
+        Integer testint100 = new Integer(100);
+        Integer testint = new Integer(-1);
+        assertEquals(objArray[0], tm.ceilingEntry(testint.toString())
+                .getValue());
+        assertEquals(objArray[100], tm.ceilingEntry(testint100.toString())
+                .getValue());
+        tm.put(testint.toString(), testint);
+        tm.put(testint100.toString(), testint);
+        assertEquals(testint, tm.ceilingEntry(testint.toString()).getValue());
+        Entry entry = tm.ceilingEntry(testint100.toString());
+        assertEquals(testint, entry.getValue());
+        assertEntry(entry);
+        try {
+            tm.ceilingEntry(testint100);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.ceilingEntry(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.ceilingEntry(testint.toString()));
+        assertNull(tm.ceilingEntry(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#ceilingKey(Object)
+     */
+    public void test_ceilingKey() throws Exception {
+        Integer testint100 = new Integer(100);
+        Integer testint = new Integer(-1);
+        assertEquals(objArray[0].toString(), tm.ceilingKey(testint.toString()));
+        assertEquals(objArray[100].toString(), tm.ceilingKey(testint100
+                .toString()));
+        tm.put(testint.toString(), testint);
+        tm.put(testint100.toString(), testint);
+        assertEquals(testint.toString(), tm.ceilingKey(testint.toString()));
+        assertEquals(testint100.toString(), tm
+                .ceilingKey(testint100.toString()));
+        try {
+            tm.ceilingKey(testint100);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.ceilingKey(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.ceilingKey(testint.toString()));
+        assertNull(tm.ceilingKey(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#higherEntry(Object)
+     */
+    public void test_higherEntry() throws Exception {
+        Integer testint9999 = new Integer(9999);
+        Integer testint10000 = new Integer(10000);
+        Integer testint100 = new Integer(100);
+        Integer testint = new Integer(-1);
+        assertEquals(objArray[0], tm.higherEntry(testint.toString()).getValue());
+        assertEquals(objArray[101], tm.higherEntry(testint100.toString())
+                .getValue());
+        assertEquals(objArray[101], tm.higherEntry(testint10000.toString())
+                .getValue());
+        tm.put(testint9999.toString(), testint);
+        tm.put(testint100.toString(), testint);
+        tm.put(testint10000.toString(), testint);
+        assertEquals(objArray[0], tm.higherEntry(testint.toString()).getValue());
+        assertEquals(testint, tm.higherEntry(testint100.toString()).getValue());
+        Entry entry = tm.higherEntry(testint10000.toString());
+        assertEquals(objArray[101], entry.getValue());
+        assertEntry(entry);
+        assertNull(tm.higherEntry(testint9999.toString()));
+        try {
+            tm.higherEntry(testint100);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.higherEntry(null);
+            fail("should throw ClassCastException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.higherEntry(testint.toString()));
+        assertNull(tm.higherEntry(null));
+    }
+
+    /**
+     * @tests {@link java.util.TreeMap#higherKey(Object)
+     */
+    public void test_higherKey() throws Exception {
+        Integer testint9999 = new Integer(9999);
+        Integer testint10000 = new Integer(10000);
+        Integer testint100 = new Integer(100);
+        Integer testint = new Integer(-1);
+        assertEquals(objArray[0].toString(), tm.higherKey(testint.toString()));
+        assertEquals(objArray[101].toString(), tm.higherKey(testint100
+                .toString()));
+        assertEquals(objArray[101].toString(), tm.higherKey(testint10000
+                .toString()));
+        tm.put(testint9999.toString(), testint);
+        tm.put(testint100.toString(), testint);
+        tm.put(testint10000.toString(), testint);
+        assertEquals(objArray[0].toString(), tm.higherKey(testint.toString()));
+        assertEquals(testint10000.toString(), tm.higherKey(testint100
+                .toString()));
+        assertEquals(objArray[101].toString(), tm.higherKey(testint10000
+                .toString()));
+        assertNull(tm.higherKey(testint9999.toString()));
+        try {
+            tm.higherKey(testint100);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.higherKey(null);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        tm.clear();
+        assertNull(tm.higherKey(testint.toString()));
+        assertNull(tm.higherKey(null));
+    }
+
+    public void test_navigableKeySet() throws Exception {
+        Integer testint9999 = new Integer(9999);
+        Integer testint10000 = new Integer(10000);
+        Integer testint100 = new Integer(100);
+        Integer testint0 = new Integer(0);
+        NavigableSet set = tm.navigableKeySet();
+        assertFalse(set.contains(testint9999.toString()));
+        tm.put(testint9999.toString(), testint9999);
+        assertTrue(set.contains(testint9999.toString()));
+        tm.remove(testint9999.toString());
+        assertFalse(set.contains(testint9999.toString()));
+        try {
+            set.add(new Object());
+            fail("should throw UnsupportedOperationException");
+        } catch (UnsupportedOperationException e) {
+            // expected
+        }
+        try {
+            set.add(null);
+            fail("should throw UnsupportedOperationException");
+        } catch (UnsupportedOperationException e) {
+            // expected
+        }
+        try {
+            set.addAll(null);
+            fail("should throw UnsupportedOperationException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        Collection collection = new LinkedList();
+        set.addAll(collection);
+        try {
+            collection.add(new Object());
+            set.addAll(collection);
+            fail("should throw UnsupportedOperationException");
+        } catch (UnsupportedOperationException e) {
+            // expected
+        }
+        set.remove(testint100.toString());
+        assertFalse(tm.containsKey(testint100.toString()));
+        assertTrue(tm.containsKey(testint0.toString()));
+        Iterator iter = set.iterator();
+        iter.next();
+        iter.remove();
+        assertFalse(tm.containsKey(testint0.toString()));
+        collection.add(new Integer(200).toString());
+        set.retainAll(collection);
+        assertEquals(1, tm.size());
+        set.removeAll(collection);
+        assertEquals(0, tm.size());
+        tm.put(testint10000.toString(), testint10000);
+        assertEquals(1, tm.size());
+        set.clear();
+        assertEquals(0, tm.size());
+    }
+
+    private void assertEntry(Entry entry) {
+        try {
+            entry.setValue(new Object());
+            fail("should throw UnsupportedOperationException");
+        } catch (UnsupportedOperationException e) {
+            // expected
+        }
+        assertEquals((entry.getKey() == null ? 0 : entry.getKey().hashCode())
+                ^ (entry.getValue() == null ? 0 : entry.getValue().hashCode()),
+                entry.hashCode());
+        assertEquals(entry.toString(), entry.getKey() + "=" + entry.getValue());
+    }
+
+    /**
+     * @tests java.util.TreeMap#subMap(java.lang.Object,boolean,
+     *        java.lang.Object,boolean)
+     */
+    public void test_subMapLjava_lang_ObjectZLjava_lang_ObjectZ() {
+        // normal case
+        SortedMap subMap = tm.subMap(objArray[100].toString(), true,
+                objArray[109].toString(), true);
+        assertEquals("subMap is of incorrect size", 10, subMap.size());
+        subMap = tm.subMap(objArray[100].toString(), true, objArray[109]
+                .toString(), false);
+        assertEquals("subMap is of incorrect size", 9, subMap.size());
+        for (int counter = 100; counter < 109; counter++) {
+            assertTrue("SubMap contains incorrect elements", subMap.get(
+                    objArray[counter].toString()).equals(objArray[counter]));
+        }
+        subMap = tm.subMap(objArray[100].toString(), false, objArray[109]
+                .toString(), true);
+        assertEquals("subMap is of incorrect size", 9, subMap.size());
+        assertNull(subMap.get(objArray[100].toString()));
+
+        // Exceptions
+        try {
+            tm.subMap(objArray[9].toString(), true, objArray[1].toString(),
+                    true);
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        try {
+            tm.subMap(objArray[9].toString(), false, objArray[1].toString(),
+                    false);
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        try {
+            tm.subMap(null, true, null, true);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.subMap(null, false, objArray[100], true);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.subMap(new LinkedList(), false, objArray[100], true);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+
+        // use integer elements to test
+        TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
+        assertEquals(0, treeMapInt.subMap(new Integer(-1), true,
+                new Integer(100), true).size());
+        for (int i = 0; i < 100; i++) {
+            treeMapInt.put(new Integer(i), new Integer(i).toString());
+        }
+        SortedMap<Integer, String> result = treeMapInt.subMap(new Integer(-1),
+                true, new Integer(100), true);
+        assertEquals(100, result.size());
+        result.put(new Integer(-1), new Integer(-1).toString());
+        assertEquals(101, result.size());
+        assertEquals(101, treeMapInt.size());
+        result = treeMapInt
+                .subMap(new Integer(50), true, new Integer(60), true);
+        assertEquals(11, result.size());
+        try {
+            result.put(new Integer(-2), new Integer(-2).toString());
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        assertEquals(11, result.size());
+        treeMapInt.remove(new Integer(50));
+        assertEquals(100, treeMapInt.size());
+        assertEquals(10, result.size());
+        result.remove(new Integer(60));
+        assertEquals(99, treeMapInt.size());
+        assertEquals(9, result.size());
+        SortedMap<Integer, String> result2 = null;
+        try {
+            result2 = result.subMap(new Integer(-2), new Integer(100));
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        result2 = result.subMap(new Integer(50), new Integer(60));
+        assertEquals(9, result2.size());
+
+        // sub map of sub map
+        NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
+        for (int i = 0; i < 10; ++i) {
+            mapIntObj.put(i, new Object());
+        }
+        mapIntObj = mapIntObj.subMap(5, false, 9, true);
+        assertEquals(4, mapIntObj.size());
+        mapIntObj = mapIntObj.subMap(5, false, 9, true);
+        assertEquals(4, mapIntObj.size());
+        mapIntObj = mapIntObj.subMap(5, false, 6, false);
+        assertEquals(0, mapIntObj.size());
+        
+        // a special comparator dealing with null key
+        tm = new TreeMap(new Comparator() {
+            public int compare(Object o1, Object o2) {
+                if (o1 == null) {
+                    return -1;
+                }
+                return ((String) o1).compareTo((String) o2);
+            }
+        });
+        tm.put(new String("1st"), 1);
+        tm.put(new String("2nd"), 2);
+        tm.put(new String("3rd"), 3);
+        String nullKey = null;
+        tm.put(nullKey, -1);
+        SortedMap s = tm.subMap(null, "3rd");
+        assertEquals(3, s.size());
+        assertTrue(s.containsValue(-1));
+        assertTrue(s.containsValue(1));
+        assertTrue(s.containsValue(2));
+        assertFalse(s.containsKey(null));
+        // RI fails here
+        assertTrue(s.containsKey("1st"));
+        assertTrue(s.containsKey("2nd"));
+        s = tm.descendingMap();
+        s = s.subMap("3rd", null);
+        assertEquals(4, s.size());
+        assertTrue(s.containsValue(-1));
+        assertTrue(s.containsValue(1));
+        assertTrue(s.containsValue(2));
+        assertTrue(s.containsValue(3));
+        assertFalse(s.containsKey(null));
+        assertTrue(s.containsKey("1st"));
+        assertTrue(s.containsKey("2nd"));
+        assertTrue(s.containsKey("3rd"));
+    }
+
+    public void test_subMap_NullTolerableComparator() {
+        // Null Tolerable Comparator
+        TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
+                new MockComparatorNullTolerable());
+        treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
+        treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
+        SortedMap<String, String> subMapWithNull = treeMapWithNull.subMap(null,
+                true, "key1", true); //$NON-NLS-1$ 
+        
+        // RI fails here
+        assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
+        assertEquals("value1", subMapWithNull.get("key1"));
+        assertEquals("value2", subMapWithNull.get(null));
+        treeMapWithNull.put("key0", "value2");
+        treeMapWithNull.put("key3", "value3");
+        treeMapWithNull.put("key4", "value4");
+        treeMapWithNull.put("key5", "value5");
+        treeMapWithNull.put("key6", "value6");
+        assertEquals("Size of subMap should be 3:", 3, subMapWithNull.size()); //$NON-NLS-1$
+        subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
+        assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
+    }
+    
+
+    /**
+     * @tests java.util.TreeMap#headMap(java.lang.Object,boolea)
+     */
+    public void test_headMapLjava_lang_ObjectZL() {
+        // normal case
+        SortedMap subMap = tm.headMap(objArray[100].toString(), true);
+        assertEquals("subMap is of incorrect size", 4, subMap.size());
+        subMap = tm.headMap(objArray[109].toString(), true);
+        assertEquals("subMap is of incorrect size", 13, subMap.size());
+        for (int counter = 100; counter < 109; counter++) {
+            assertTrue("SubMap contains incorrect elements", subMap.get(
+                    objArray[counter].toString()).equals(objArray[counter]));
+        }
+        subMap = tm.headMap(objArray[100].toString(), false);
+        assertEquals("subMap is of incorrect size", 3, subMap.size());
+        assertNull(subMap.get(objArray[100].toString()));
+
+        // Exceptions
+        assertEquals(0, tm.headMap("", true).size());
+        assertEquals(0, tm.headMap("", false).size());
+
+        try {
+            tm.headMap(null, true);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.headMap(null, false);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.headMap(new Object(), true);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.headMap(new Object(), false);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+
+        // use integer elements to test
+        TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
+        assertEquals(0, treeMapInt.headMap(new Integer(-1), true).size());
+        for (int i = 0; i < 100; i++) {
+            treeMapInt.put(new Integer(i), new Integer(i).toString());
+        }
+        SortedMap<Integer, String> result = treeMapInt
+                .headMap(new Integer(101));
+        assertEquals(100, result.size());
+        try {
+            result.put(new Integer(101), new Integer(101).toString());
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        assertEquals(100, result.size());
+        assertEquals(100, treeMapInt.size());
+        result = treeMapInt.headMap(new Integer(50), true);
+        assertEquals(51, result.size());
+        result.put(new Integer(-1), new Integer(-1).toString());
+        assertEquals(52, result.size());
+
+        treeMapInt.remove(new Integer(40));
+        assertEquals(100, treeMapInt.size());
+        assertEquals(51, result.size());
+        result.remove(new Integer(30));
+        assertEquals(99, treeMapInt.size());
+        assertEquals(50, result.size());
+        SortedMap<Integer, String> result2 = null;
+        try {
+            result.subMap(new Integer(-2), new Integer(100));
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        try {
+            result.subMap(new Integer(1), new Integer(100));
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        result2 = result.subMap(new Integer(-2), new Integer(48));
+        assertEquals(47,result2.size());
+        
+        result2 = result.subMap(new Integer(40), new Integer(50));
+        assertEquals(9, result2.size());
+
+        // Null Tolerable Comparator
+        TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
+                new MockComparatorNullTolerable());
+        treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
+        treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
+        SortedMap<String, String> subMapWithNull = treeMapWithNull.headMap(
+                null, true); //$NON-NLS-1$ 
+        assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
+        assertEquals(null, subMapWithNull.get("key1"));
+        assertEquals("value2", subMapWithNull.get(null));
+        treeMapWithNull.put("key0", "value2");
+        treeMapWithNull.put("key3", "value3");
+        treeMapWithNull.put("key4", "value4");
+        treeMapWithNull.put("key5", "value5");
+        treeMapWithNull.put("key6", "value6");
+        assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
+        subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
+        assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
+
+        // head map of head map
+        NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
+        for (int i = 0; i < 10; ++i) {
+            mapIntObj.put(i, new Object());
+        }
+        mapIntObj = mapIntObj.headMap(5, false);
+        assertEquals(5, mapIntObj.size());
+        mapIntObj = mapIntObj.headMap(5, false);
+        assertEquals(5, mapIntObj.size());
+        mapIntObj = mapIntObj.tailMap(5, false);
+        assertEquals(0, mapIntObj.size());
+    }
+
+    /**
+     * @tests java.util.TreeMap#tailMap(java.lang.Object,boolea)
+     */
+    public void test_tailMapLjava_lang_ObjectZL() {
+        // normal case
+        SortedMap subMap = tm.tailMap(objArray[100].toString(), true);
+        assertEquals("subMap is of incorrect size", 997, subMap.size());
+        subMap = tm.tailMap(objArray[109].toString(), true);
+        assertEquals("subMap is of incorrect size", 988, subMap.size());
+        for (int counter = 119; counter > 110; counter--) {
+            assertTrue("SubMap contains incorrect elements", subMap.get(
+                    objArray[counter].toString()).equals(objArray[counter]));
+        }
+        subMap = tm.tailMap(objArray[100].toString(), false);
+        assertEquals("subMap is of incorrect size", 996, subMap.size());
+        assertNull(subMap.get(objArray[100].toString()));
+
+        // Exceptions
+        assertEquals(1000, tm.tailMap("", true).size());
+        assertEquals(1000, tm.tailMap("", false).size());
+
+        try {
+            tm.tailMap(null, true);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.tailMap(null, false);
+            fail("should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            tm.tailMap(new Object(), true);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+        try {
+            tm.tailMap(new Object(), false);
+            fail("should throw ClassCastException");
+        } catch (ClassCastException e) {
+            // expected
+        }
+
+        // use integer elements to test
+        TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
+        assertEquals(0, treeMapInt.tailMap(new Integer(-1), true).size());
+        for (int i = 0; i < 100; i++) {
+            treeMapInt.put(new Integer(i), new Integer(i).toString());
+        }
+        SortedMap<Integer, String> result = treeMapInt.tailMap(new Integer(1));
+        assertEquals(99, result.size());
+        try {
+            result.put(new Integer(-1), new Integer(-1).toString());
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        assertEquals(99, result.size());
+        assertEquals(100, treeMapInt.size());
+        result = treeMapInt.tailMap(new Integer(50), true);
+        assertEquals(50, result.size());
+        result.put(new Integer(101), new Integer(101).toString());
+        assertEquals(51, result.size());
+
+        treeMapInt.remove(new Integer(60));
+        assertEquals(100, treeMapInt.size());
+        assertEquals(50, result.size());
+        result.remove(new Integer(70));
+        assertEquals(99, treeMapInt.size());
+        assertEquals(49, result.size());
+        SortedMap<Integer, String> result2 = null;
+        try {
+            result2 = result.subMap(new Integer(-2), new Integer(100));
+            fail("should throw IllegalArgumentException");
+        } catch (IllegalArgumentException e) {
+            // expected
+        }
+        result2 = result.subMap(new Integer(60), new Integer(70));
+        assertEquals(9, result2.size());
+
+        // Null Tolerable Comparator
+        TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
+                new MockComparatorNullTolerable());
+        treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
+        treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
+        SortedMap<String, String> subMapWithNull = treeMapWithNull.tailMap(
+                "key1", true); //$NON-NLS-1$ 
+        assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
+        assertEquals("value1", subMapWithNull.get("key1"));
+        assertEquals(null, subMapWithNull.get(null));
+        treeMapWithNull.put("key0", "value2");
+        treeMapWithNull.put("key3", "value3");
+        treeMapWithNull.put("key4", "value4");
+        treeMapWithNull.put("key5", "value5");
+        treeMapWithNull.put("key6", "value6");
+        assertEquals("Size of subMap should be 5:", 5, subMapWithNull.size()); //$NON-NLS-1$
+        subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
+        assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
+
+        // tail map of tail map
+        NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
+        for (int i = 0; i < 10; ++i) {
+            mapIntObj.put(i, new Object());
+        }
+        mapIntObj = mapIntObj.tailMap(5, false);
+        assertEquals(4, mapIntObj.size());
+        mapIntObj = mapIntObj.tailMap(5, false);
+        assertEquals(4, mapIntObj.size());
+        mapIntObj = mapIntObj.headMap(5, false);
+        assertEquals(0, mapIntObj.size());
+    }
+
+    public void test_descendingMap_subMap() throws Exception {
+        TreeMap<Integer, Object> tm = new TreeMap<Integer, Object>();
+        for (int i = 0; i < 10; ++i) {
+            tm.put(i, new Object());
+        }
+        NavigableMap<Integer, Object> descMap = tm.descendingMap();
+        assertEquals(7, descMap.subMap(8, true, 1, false).size());
+        assertEquals(4, descMap.headMap(6, true).size());
+        assertEquals(2, descMap.tailMap(2, false).size());
+
+        // sub map of sub map of descendingMap
+        NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
+        for (int i = 0; i < 10; ++i) {
+            mapIntObj.put(i, new Object());
+        }
+        mapIntObj = mapIntObj.descendingMap();
+        NavigableMap<Integer, Object> subMapIntObj = mapIntObj.subMap(9, true,
+                5, false);
+        assertEquals(4, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.subMap(9, true, 5, false);
+        assertEquals(4, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.subMap(6, false, 5, false);
+        assertEquals(0, subMapIntObj.size());
+
+        subMapIntObj = mapIntObj.headMap(5, false);
+        assertEquals(4, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.headMap(5, false);
+        assertEquals(4, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.tailMap(5, false);
+        assertEquals(0, subMapIntObj.size());
+
+        subMapIntObj = mapIntObj.tailMap(5, false);
+        assertEquals(5, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.tailMap(5, false);
+        assertEquals(5, subMapIntObj.size());
+        subMapIntObj = subMapIntObj.headMap(5, false);
+        assertEquals(0, subMapIntObj.size());
+    }
+
+    /**
+     * This test is about an old bug of RI.The bug is that: if the TreeMap has
+     * no comparator or its comparator is not null-tolerable, it can not put a
+     * null-key entry into this TreeMap.But RI can do it when the TreeMap is
+     * empty, and can not do it when the TreeMap is not empty.It is best for
+     * Harmony to follow RI's behavior for legacy reason. This test is to test
+     * the "illegal" TreeMap with the first null key. It can be easily removed
+     * when the bug is fixed in the future.
+     */
+    public void test_illegalFirstNullKey() {
+        // if the comparator is null
+        TreeMap<String, String> map = new TreeMap<String, String>();
+        map.put((String) null, "NullValue");
+        illegalFirstNullKeyMapTester(map);
+        illegalFirstNullKeyMapTester(map.descendingMap());
+
+        // if the comparator is not null, but do not permit null key
+        map = new TreeMap<String, String>(new Comparator<String>() {
+            public int compare(String object1, String object2) {
+                return object1.compareTo(object2);
+            }
+        });
+        map.put((String) null, "NullValue");
+        illegalFirstNullKeyMapTester(map);
+        illegalFirstNullKeyMapTester(map.descendingMap());
+    }
+
+    private void illegalFirstNullKeyMapTester(NavigableMap<String, String> map) {
+        try {
+            map.get(null);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        try {
+            map.put("NormalKey", "value");
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // expected
+        }
+        Set<String> keySet = map.keySet();
+        assertTrue(!keySet.isEmpty());
+        assertEquals(1, keySet.size());
+        for (String key : keySet) {
+            assertEquals(key, null);
+            try {
+                map.get(key);
+                fail("Should throw NullPointerException");
+            } catch (NullPointerException e) {
+                // ignore
+            }
+        }
+        Set<Entry<String, String>> entrySet = map.entrySet();
+        assertTrue(!entrySet.isEmpty());
+        assertEquals(1, entrySet.size());
+        for (Entry<String, String> entry : entrySet) {
+            assertEquals(null, entry.getKey());
+            assertEquals("NullValue", entry.getValue());
+        }
+        Collection<String> values = map.values();
+        assertTrue(!values.isEmpty());
+        assertEquals(1, values.size());
+        for (String value : values) {
+            assertEquals("NullValue", value);
+        }
+
+        try {
+            map.headMap(null, true);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+        try {
+            map.headMap(null, false);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+
+        try {
+            map.subMap(null, false, null, false);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+        try {
+            map.subMap(null, true, null, true);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+        try {
+            map.tailMap(null, true);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+        try {
+            map.tailMap(null, false);
+            fail("Should throw NullPointerException");
+        } catch (NullPointerException e) {
+            // ignore
+        }
+    }
 
     /**
      * Tests equals() method.
@@ -567,5 +1641,4 @@
             tm.put(x.toString(), x);
         }
     }
-
 }

Modified: harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeSetTest.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeSetTest.java?view=diff&rev=549743&r1=549742&r2=549743
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeSetTest.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/luni/src/test/api/common/tests/api/java/util/TreeSetTest.java Fri Jun 22 00:32:12 2007
@@ -17,10 +17,12 @@
 
 package tests.api.java.util;
 
+import java.net.Inet4Address;
 import java.util.Arrays;
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.NavigableSet;
 import java.util.Set;
 import java.util.SortedSet;
 import java.util.TreeSet;



Mime
View raw message