Filling out implementations of java.util.

The new code comes straight from Harmony. None of the below classes
were divergent from Harmony so the change was quite straightforward.

The changes have been tested against Harmony's test suite and jtreg.
I haven't added any new tests to our suite, but I don't need to.
diff --git a/libcore/luni/src/main/java/java/util/Collections.java b/libcore/luni/src/main/java/java/util/Collections.java
index af49cc0..1b73366 100644
--- a/libcore/luni/src/main/java/java/util/Collections.java
+++ b/libcore/luni/src/main/java/java/util/Collections.java
@@ -18,6 +18,7 @@
 package java.util;
 
 import java.io.IOException;
+import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.ObjectStreamException;
 import java.io.Serializable;
@@ -1283,7 +1284,7 @@
                 Iterator<Map.Entry<K, V>> it = iterator();
                 if (size > contents.length) {
                     Class<?> ct = contents.getClass().getComponentType();
-                    contents = (T[]) java.lang.reflect.Array.newInstance(ct, size);
+                    contents = (T[]) Array.newInstance(ct, size);
                 }
                 while (index < size) {
                     contents[index++] = (T) it.next();
@@ -2687,6 +2688,222 @@
     }
 
     /**
+     * Returns a set backed by {@code map}.
+     *
+     * @throws IllegalArgumentException if the map is not empty
+     * @since 1.6
+     */
+    public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
+        if (map.isEmpty()) {
+            return new SetFromMap<E>(map);
+        }
+        throw new IllegalArgumentException();
+    }
+
+    /**
+     * Returns a last-in, first-out queue as a view of {@code deque}.
+     *
+     * @since 1.6
+     */
+    public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
+        return new AsLIFOQueue<T>(deque);
+    }
+
+    private static class SetFromMap<E> extends AbstractSet<E> implements
+            Serializable {
+        private static final long serialVersionUID = 2454657854757543876L;
+
+        // must named as it, to pass serialization compatibility test.
+        private Map<E, Boolean> m;
+
+        private transient Set<E> backingSet;
+
+        SetFromMap(final Map<E, Boolean> map) {
+            super();
+            m = map;
+            backingSet = map.keySet();
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            return backingSet.equals(object);
+        }
+
+        @Override
+        public int hashCode() {
+            return backingSet.hashCode();
+        }
+
+        @Override
+        public boolean add(E object) {
+            return m.put(object, Boolean.TRUE) == null;
+        }
+
+        @Override
+        public void clear() {
+            m.clear();
+        }
+
+        @Override
+        public String toString() {
+            return backingSet.toString();
+        }
+
+        @Override
+        public boolean contains(Object object) {
+            return backingSet.contains(object);
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> collection) {
+            return backingSet.containsAll(collection);
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return m.isEmpty();
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            return m.remove(object) != null;
+        }
+
+        @Override
+        public boolean retainAll(Collection<?> collection) {
+            return backingSet.retainAll(collection);
+        }
+
+        @Override
+        public Object[] toArray() {
+            return backingSet.toArray();
+        }
+
+        @Override
+        public <T> T[] toArray(T[] contents) {
+            return backingSet.toArray(contents);
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return backingSet.iterator();
+        }
+
+        @Override
+        public int size() {
+            return m.size();
+        }
+
+        @SuppressWarnings("unchecked")
+        private void readObject(ObjectInputStream stream)
+                throws IOException, ClassNotFoundException {
+            stream.defaultReadObject();
+            backingSet = m.keySet();
+        }
+    }
+
+    private static class AsLIFOQueue<E> extends AbstractQueue<E> implements
+            Serializable {
+        private static final long serialVersionUID = 1802017725587941708L;
+
+        // must named as it, to pass serialization compatibility test.
+        private final Deque<E> q;
+
+        AsLIFOQueue(final Deque<E> deque) {
+            super();
+            this.q = deque;
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return q.iterator();
+        }
+
+        @Override
+        public int size() {
+            return q.size();
+        }
+
+        public boolean offer(E o) {
+            return q.offerFirst(o);
+        }
+
+        public E peek() {
+            return q.peekFirst();
+        }
+
+        public E poll() {
+            return q.pollFirst();
+        }
+
+        @Override
+        public boolean add(E o) {
+            q.push(o);
+            return true;
+        }
+
+        @Override
+        public void clear() {
+            q.clear();
+        }
+
+        @Override
+        public E element() {
+            return q.getFirst();
+        }
+
+        @Override
+        public E remove() {
+            return q.pop();
+        }
+
+        @Override
+        public boolean contains(Object object) {
+            return q.contains(object);
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> collection) {
+            return q.containsAll(collection);
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return q.isEmpty();
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            return q.remove(object);
+        }
+
+        @Override
+        public boolean removeAll(Collection<?> collection) {
+            return q.removeAll(collection);
+        }
+
+        @Override
+        public boolean retainAll(Collection<?> collection) {
+            return q.retainAll(collection);
+        }
+
+        @Override
+        public Object[] toArray() {
+            return q.toArray();
+        }
+
+        @Override
+        public <T> T[] toArray(T[] contents) {
+            return q.toArray(contents);
+        }
+
+        @Override
+        public String toString() {
+            return q.toString();
+        }
+    }
+
+    /**
      * Class represents a dynamically typesafe view of the specified collection.
      */
     private static class CheckedCollection<E> implements Collection<E>,
diff --git a/libcore/luni/src/main/java/java/util/LinkedList.java b/libcore/luni/src/main/java/java/util/LinkedList.java
index 9db9c9c..4056b8e 100644
--- a/libcore/luni/src/main/java/java/util/LinkedList.java
+++ b/libcore/luni/src/main/java/java/util/LinkedList.java
@@ -181,6 +181,64 @@
         }
     }
 
+	/*
+	 * NOTES:descendingIterator is not fail-fast, according to the documentation
+	 * and test case.
+	 */
+	private class ReverseLinkIterator<ET> implements Iterator<ET> {
+		private int expectedModCount;
+
+		private final LinkedList<ET> list;
+
+        private Link<ET> link;
+
+        private boolean canRemove;
+
+        ReverseLinkIterator(LinkedList<ET> linkedList) {
+            super();
+            list = linkedList;
+            expectedModCount = list.modCount;
+            link = list.voidLink;
+            canRemove = false;
+        }
+
+        public boolean hasNext() {
+            return link.previous != list.voidLink;
+        }
+
+        public ET next() {
+            if (expectedModCount == list.modCount) {
+                if (hasNext()) {
+                    link = link.previous;
+                    canRemove = true;
+                    return link.data;
+                }
+                throw new NoSuchElementException();
+            }
+            throw new ConcurrentModificationException();
+
+        }
+
+        public void remove() {
+            if (expectedModCount == list.modCount) {
+                if (canRemove) {
+                    Link<ET> next = link.previous;
+                    Link<ET> previous = link.next;
+                    next.next = previous;
+                    previous.previous = next;
+                    link = previous;
+                    list.size--;
+                    list.modCount++;
+                    expectedModCount++;
+                    canRemove = false;
+                    return;
+                }
+                throw new IllegalStateException();
+            }
+            throw new ConcurrentModificationException();
+        }
+    }
+
     /**
      * Constructs a new empty instance of {@code LinkedList}.
      */
@@ -250,7 +308,10 @@
      */
     @Override
     public boolean add(E object) {
-        // Cannot call addLast() as subclasses can override
+        return addLastImpl(object);
+    }
+
+    private boolean addLastImpl(E object) {
         Link<E> oldLast = voidLink.previous;
         Link<E> newLink = new Link<E>(object, oldLast, voidLink);
         voidLink.previous = newLink;
@@ -350,12 +411,17 @@
      *            the object to add.
      */
     public void addFirst(E object) {
+        addFirstImpl(object);
+    }
+
+    private boolean addFirstImpl(E object) {
         Link<E> oldFirst = voidLink.next;
         Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
         voidLink.next = newLink;
         oldFirst.previous = newLink;
         size++;
         modCount++;
+        return true;
     }
 
     /**
@@ -365,12 +431,7 @@
      *            the object to add.
      */
     public void addLast(E object) {
-        Link<E> oldLast = voidLink.previous;
-        Link<E> newLink = new Link<E>(object, oldLast, voidLink);
-        voidLink.previous = newLink;
-        oldLast.next = newLink;
-        size++;
-        modCount++;
+        addLastImpl(object);
     }
 
     /**
@@ -467,6 +528,10 @@
      *             if this {@code LinkedList} is empty.
      */
     public E getFirst() {
+        return getFirstImpl();
+    }
+
+    private E getFirstImpl() {
         Link<E> first = voidLink.next;
         if (first != voidLink) {
             return first.data;
@@ -598,26 +663,7 @@
 
     @Override
     public boolean remove(Object object) {
-        Link<E> link = voidLink.next;
-        if (object != null) {
-            while (link != voidLink && !object.equals(link.data)) {
-                link = link.next;
-            }
-        } else {
-            while (link != voidLink && link.data != null) {
-                link = link.next;
-            }
-        }
-        if (link == voidLink) {
-            return false;
-        }
-        Link<E> next = link.next;
-        Link<E> previous = link.previous;
-        previous.next = next;
-        next.previous = previous;
-        size--;
-        modCount++;
-        return true;
+        return removeFirstOccurrenceImpl(object);
     }
 
     /**
@@ -628,6 +674,10 @@
      *             if this {@code LinkedList} is empty.
      */
     public E removeFirst() {
+        return removeFirstImpl();
+    }
+
+    private E removeFirstImpl() {
         Link<E> first = voidLink.next;
         if (first != voidLink) {
             Link<E> next = first.next;
@@ -648,6 +698,10 @@
      *             if this {@code LinkedList} is empty.
      */
     public E removeLast() {
+        return removeLastImpl();
+    }
+
+    private E removeLastImpl() {
         Link<E> last = voidLink.previous;
         if (last != voidLink) {
             Link<E> previous = last.previous;
@@ -661,6 +715,134 @@
     }
 
     /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#descendingIterator()
+     * @since 1.6
+     */
+    public Iterator<E> descendingIterator() {
+        return new ReverseLinkIterator<E>(this);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#offerFirst(java.lang.Object)
+     * @since 1.6
+     */
+    public boolean offerFirst(E e) {
+        return addFirstImpl(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#offerLast(java.lang.Object)
+     * @since 1.6
+     */
+    public boolean offerLast(E e) {
+        return addLastImpl(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#peekFirst()
+     * @since 1.6
+     */
+    public E peekFirst() {
+        return peekFirstImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#peekLast()
+     * @since 1.6
+     */
+    public E peekLast() {
+        Link<E> last = voidLink.previous;
+        return (last == voidLink) ? null : last.data;
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#pollFirst()
+     * @since 1.6
+     */
+    public E pollFirst() {
+        return (size == 0) ? null : removeFirstImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#pollLast()
+     * @since 1.6
+     */
+    public E pollLast() {
+        return (size == 0) ? null : removeLastImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#pop()
+     * @since 1.6
+     */
+    public E pop() {
+        return removeFirstImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#push(java.lang.Object)
+     * @since 1.6
+     */
+    public void push(E e) {
+        addFirstImpl(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#removeFirstOccurrence(java.lang.Object)
+     * @since 1.6
+     */
+    public boolean removeFirstOccurrence(Object o) {
+        return removeFirstOccurrenceImpl(o);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.Deque#removeLastOccurrence(java.lang.Object)
+     * @since 1.6
+     */
+    public boolean removeLastOccurrence(Object o) {
+        Iterator<E> iter = new ReverseLinkIterator<E>(this);
+        return removeOneOccurrence(o, iter);
+    }
+
+    private boolean removeFirstOccurrenceImpl(Object o) {
+        Iterator<E> iter = new LinkIterator<E>(this, 0);
+        return removeOneOccurrence(o, iter);
+    }
+
+    private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
+        while (iter.hasNext()) {
+            E element = iter.next();
+            if (o == null ? element == null : o.equals(element)) {
+                iter.remove();
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
      * Replaces the element at the specified location in this {@code LinkedList}
      * with the specified object.
      *
@@ -707,8 +889,7 @@
     }
 
     public boolean offer(E o) {
-        add(o);
-        return true;
+        return addLastImpl(o);
     }
 
     public E poll() {
@@ -716,16 +897,20 @@
     }
 
     public E remove() {
-        return removeFirst();
+        return removeFirstImpl();
     }
 
     public E peek() {
+        return peekFirstImpl();
+    }
+
+    private E peekFirstImpl() {
         Link<E> first = voidLink.next;
         return first == voidLink ? null : first.data;
     }
 
     public E element() {
-        return getFirst();
+        return getFirstImpl();
     }
 
     /**
diff --git a/libcore/luni/src/main/java/java/util/TreeSet.java b/libcore/luni/src/main/java/java/util/TreeSet.java
index 98f6303..d636dc7 100644
--- a/libcore/luni/src/main/java/java/util/TreeSet.java
+++ b/libcore/luni/src/main/java/java/util/TreeSet.java
@@ -30,16 +30,18 @@
  *
  * @since 1.2
  */
-public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>,
+public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>,
         Cloneable, Serializable {
 
     private static final long serialVersionUID = -2479143000061671589L;
 
     /** Keys are this set's elements. Values are always Boolean.TRUE */
-    private transient SortedMap<E, Object> backingMap;
+    private transient NavigableMap<E, Object> backingMap;
 
-    private TreeSet(SortedMap<E, Object> map) {
-        this.backingMap = map;
+    private transient NavigableSet<E> descendingSet;
+
+    TreeSet(NavigableMap<E, Object> map) {
+        backingMap = map;
     }
 
     /**
@@ -154,7 +156,7 @@
         try {
             TreeSet<E> clone = (TreeSet<E>) super.clone();
             if (backingMap instanceof TreeMap) {
-                clone.backingMap = (SortedMap<E, Object>) ((TreeMap<E, Object>) backingMap)
+                clone.backingMap = (NavigableMap<E, Object>) ((TreeMap<E, Object>) backingMap)
                         .clone();
             } else {
                 clone.backingMap = new TreeMap<E, Object>(backingMap);
@@ -194,45 +196,6 @@
     }
 
     /**
-     * Returns the first element in this {@code TreeSet}.
-     *
-     * @return the first element.
-     * @throws NoSuchElementException
-     *             when this {@code TreeSet} is empty.
-     */
-    public E first() {
-        return backingMap.firstKey();
-    }
-
-    /**
-     * Returns a SortedSet of the specified portion of this {@code TreeSet}
-     * which contains elements which are all less than the end element. The
-     * returned SortedSet is backed by this {@code 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}
-     * @throws ClassCastException
-     *             when the end object cannot be compared with the elements in
-     *             this {@code TreeSet}.
-     * @throws 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));
-    }
-
-    /**
      * Returns true if this {@code TreeSet} has no element, otherwise false.
      *
      * @return true if this {@code TreeSet} has no element.
@@ -255,15 +218,13 @@
     }
 
     /**
-     * Returns the last element in this {@code TreeSet}. The last element is
-     * the highest element.
+     * {@inheritDoc}
      *
-     * @return the last element.
-     * @throws NoSuchElementException
-     *             when this {@code TreeSet} is empty.
+     * @see java.util.NavigableSet#descendingIterator()
+     * @since 1.6
      */
-    public E last() {
-        return backingMap.lastKey();
+    public Iterator<E> descendingIterator() {
+        return descendingSet().iterator();
     }
 
     /**
@@ -296,57 +257,147 @@
     }
 
     /**
-     * Returns a SortedSet of the specified portion of this {@code TreeSet}
-     * which contains elements greater or equal to the start element but less
-     * than the end element. The returned SortedSet is backed by this
-     * {@code TreeSet} so changes to one are reflected by the other.
+     * Answers the first element in this TreeSet.
      *
-     * @param start
-     *            the start element.
-     * @param end
-     *            the end element (exclusive).
-     * @return a subset where the elements are greater or equal to {@code start}
-     *         and less than {@code end}
-     * @throws ClassCastException
-     *             when the start or end object cannot be compared with the
-     *             elements in this {@code TreeSet}.
-     * @throws NullPointerException
-     *             when the start or end object is null and the comparator
-     *             cannot handle null.
+     * @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, Object> entry = backingMap.pollFirstEntry();
+        return (null == entry) ? null : entry.getKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @see java.util.NavigableSet#pollLast()
+     * @since 1.6
+     */
+    public E pollLast() {
+        Map.Entry<E, Object> 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 SortedSet<E> subSet(E start, E end) {
+    public NavigableSet<E> subSet(E start, boolean startInclusive, E end,
+            boolean endInclusive) {
         Comparator<? super E> c = backingMap.comparator();
-        if (c == null) {
-            if (((Comparable<E>) start).compareTo(end) <= 0) {
-                return new TreeSet<E>(backingMap.subMap(start, end));
-            }
-        } else {
-            if (c.compare(start, end) <= 0) {
-                return new TreeSet<E>(backingMap.subMap(start, end));
-            }
+        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();
     }
 
     /**
-     * Returns a SortedSet of the specified portion of this {@code TreeSet}
-     * which contains elements greater or equal to the start element. The
-     * returned SortedSet is backed by this {@code TreeSet} so changes to one
-     * are reflected by the other.
+     * {@inheritDoc}
      *
-     * @param start
-     *            the start element.
-     * @return a subset where the elements are greater or equal to {@code start}
-     * @throws ClassCastException
-     *             when the start object cannot be compared with the elements in
-     *             this {@code TreeSet}.
-     * @throws NullPointerException
-     *             when the start object is null and the comparator cannot
-     *             handle null.
+     * @see java.util.NavigableSet#headSet(Object, boolean)
+     * @since 1.6
      */
     @SuppressWarnings("unchecked")
-    public SortedSet<E> tailSet(E start) {
+    public NavigableSet<E> headSet(E end, boolean endInclusive) {
+        // 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, endInclusive));
+    }
+
+    /**
+     * {@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) {
@@ -354,7 +405,76 @@
         } else {
             c.compare(start, start);
         }
-        return new TreeSet<E>(backingMap.tailMap(start));
+        return new TreeSet<E>(backingMap.tailMap(start, startInclusive));
+    }
+
+    /**
+     * 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 {
@@ -377,9 +497,11 @@
         TreeMap<E, Object> map = new TreeMap<E, Object>(
                 (Comparator<? super E>) stream.readObject());
         int size = stream.readInt();
-        for (int i = 0; i < size; i++) {
-            E elem = (E)stream.readObject();
-            map.put(elem, Boolean.TRUE);
+        if (size > 0) {
+            for(int i=0; i<size; i++) {
+                E elem = (E)stream.readObject();
+                map.put(elem, Boolean.TRUE);
+            }
         }
         backingMap = map;
     }