Merge "Latest java.util.concurrent from the JSR 166 project." into dalvik-dev

5 files changed, 1831 insertions, 1 deletions

diff --git a/luni/src/main/java/java/util/AbstractMap.java b/luni/src/main/java/java/util/AbstractMap.java
index c98a25f..86b4740 100644
--- a/luni/src/main/java/java/util/AbstractMap.java
+++ b/luni/src/main/java/java/util/AbstractMap.java
@@ -17,6 +17,8 @@
 
 package java.util;
 
+import java.io.Serializable;
+
 /**
  * This class is an abstract implementation of the {@code Map} interface. This
  * implementation does not support adding. A subclass must implement the
@@ -32,6 +34,240 @@ public abstract class AbstractMap<K, V> implements Map<K, V> {
     Collection<V> valuesCollection;
 
     /**
+     * An immutable key-value mapping.
+     *
+     * @param <K>
+     *            the type of key
+     * @param <V>
+     *            the type of value
+     *
+     * @since 1.6
+     */
+    public static class SimpleImmutableEntry<K, V> implements Map.Entry<K, V>,
+            Serializable {
+
+        private static final long serialVersionUID = 7138329143949025153L;
+
+        private K key;
+
+        private V value;
+
+        /**
+         * Constructs a new instance by key and value.
+         *
+         * @param theKey
+         *            the key
+         * @param theValue
+         *            the value
+         */
+        public SimpleImmutableEntry(K theKey, V theValue) {
+            key = theKey;
+            value = theValue;
+        }
+
+        /**
+         * Constructs a new instance by an entry
+         *
+         * @param entry
+         *            the entry
+         */
+        public SimpleImmutableEntry(Map.Entry<? extends K, ? extends V> entry) {
+            key = entry.getKey();
+            value = entry.getValue();
+        }
+
+        /**
+         * {@inheritDoc}
+         *
+         * @see java.util.Map.Entry#getKey()
+         */
+        public K getKey() {
+            return key;
+        }
+
+        /**
+         * {@inheritDoc}
+         *
+         * @see java.util.Map.Entry#getValue()
+         */
+        public V getValue() {
+            return value;
+        }
+
+        /**
+         * Throws an UnsupportedOperationException.
+         *
+         * @param object
+         *            new value
+         * @return (Does not)
+         * @throws UnsupportedOperationException
+         *             always
+         *
+         * @see java.util.Map.Entry#setValue(java.lang.Object)
+         */
+        public V setValue(V object) {
+            throw new UnsupportedOperationException();
+        }
+
+        /**
+         * Returns whether the object is equal to this entry. This works across
+         * all kinds of the Map.Entry interface.
+         *
+         * @see java.lang.Object#equals(java.lang.Object)
+         */
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (object instanceof Map.Entry) {
+                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
+                return (key == null ? entry.getKey() == null : key.equals(entry
+                        .getKey()))
+                        && (value == null ? entry.getValue() == null : value
+                                .equals(entry.getValue()));
+            }
+            return false;
+        }
+
+        /**
+         * Returns the hash code of this entry.
+         *
+         * @see java.lang.Object#hashCode()
+         */
+        @Override
+        public int hashCode() {
+            return (key == null ? 0 : key.hashCode())
+                    ^ (value == null ? 0 : value.hashCode());
+        }
+
+        /**
+         * Returns a String representation of this entry.
+         *
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return key + "=" + value; //$NON-NLS-1$
+        }
+    }
+
+    /**
+     * A key-value mapping.
+     *
+     * @param <K>
+     *            the type of key
+     * @param <V>
+     *            the type of value
+     *
+     * @since 1.6
+     */
+    public static class SimpleEntry<K, V> implements Map.Entry<K, V>,
+            Serializable {
+
+        private static final long serialVersionUID = -8499721149061103585L;
+
+        private K key;
+
+        private V value;
+
+        /**
+         * Constructs a new instance by key and value.
+         *
+         * @param theKey
+         *            the key
+         * @param theValue
+         *            the value
+         */
+        public SimpleEntry(K theKey, V theValue) {
+            key = theKey;
+            value = theValue;
+        }
+
+        /**
+         * Constructs a new instance by an entry
+         *
+         * @param entry
+         *            the entry
+         */
+        public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
+            key = entry.getKey();
+            value = entry.getValue();
+        }
+
+        /**
+         * {@inheritDoc}
+         *
+         * @see java.util.Map.Entry#getKey()
+         */
+        public K getKey() {
+            return key;
+        }
+
+        /**
+         * {@inheritDoc}
+         *
+         * @see java.util.Map.Entry#getValue()
+         */
+        public V getValue() {
+            return value;
+        }
+
+        /**
+         * {@inheritDoc}
+         *
+         * @see java.util.Map.Entry#setValue(java.lang.Object)
+         */
+        public V setValue(V object) {
+            V result = value;
+            value = object;
+            return result;
+        }
+
+        /**
+         * Returns whether the object is equal to this entry. This works across
+         * all kinds of the Map.Entry interface.
+         *
+         * @see java.lang.Object#equals(java.lang.Object)
+         */
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (object instanceof Map.Entry) {
+                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
+                return (key == null ? entry.getKey() == null : key.equals(entry
+                        .getKey()))
+                        && (value == null ? entry.getValue() == null : value
+                                .equals(entry.getValue()));
+            }
+            return false;
+        }
+
+        /**
+         * Returns the hash code of this entry.
+         *
+         * @see java.lang.Object#hashCode()
+         */
+        @Override
+        public int hashCode() {
+            return (key == null ? 0 : key.hashCode())
+                    ^ (value == null ? 0 : value.hashCode());
+        }
+
+        /**
+         * Returns a String representation of this entry.
+         *
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return key + "=" + value; //$NON-NLS-1$
+        }
+    }
+
+    /**
      * Constructs a new instance of this {@code AbstractMap}.
      */
     protected AbstractMap() {
@@ -453,4 +689,4 @@ public abstract class AbstractMap<K, V> implements Map<K, V> {
         result.valuesCollection = null;
         return result;
     }
-}
+}
\ No newline at end of file
diff --git a/luni/src/main/java/java/util/ArrayDeque.java b/luni/src/main/java/java/util/ArrayDeque.java
new file mode 100644
index 0000000..2e2fe3a
--- /dev/null
+++ b/luni/src/main/java/java/util/ArrayDeque.java
@@ -0,0 +1,885 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package java.util;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.reflect.Array;
+
+/**
+ * An implementation of Deque, backed by an array.
+ *
+ * ArrayDeques have no size limit, can not contain null element, and they are
+ * not thread-safe.
+ *
+ * All optional operations are supported, and the elements can be any objects.
+ *
+ * @param <E>
+ *            the type of elements in this collection
+ *
+ * @since 1.6
+ */
+public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>,
+        Cloneable, Serializable {
+
+    private static final long serialVersionUID = 2340985798034038923L;
+
+    private static final int DEFAULT_SIZE = 16;
+
+    private enum DequeStatus {
+        Empty, Normal, Full;
+    }
+
+    private transient DequeStatus status;
+
+    private transient int modCount;
+
+    // the pointer of the head element
+    private transient int front;
+
+    // the pointer of the "next" position of the tail element
+    private transient int rear;
+
+    private transient E[] elements;
+
+    @SuppressWarnings("hiding")
+    private class ArrayDequeIterator<E> implements Iterator<E> {
+        private int pos;
+
+        private final int expectedModCount;
+
+        private boolean canRemove;
+
+        @SuppressWarnings("synthetic-access")
+        ArrayDequeIterator() {
+            super();
+            pos = front;
+            expectedModCount = modCount;
+            canRemove = false;
+        }
+
+        @SuppressWarnings("synthetic-access")
+        public boolean hasNext() {
+            if (expectedModCount != modCount) {
+                return false;
+            }
+            return hasNextInternal();
+        }
+
+        private boolean hasNextInternal() {
+            // canRemove means "next" method is called, and the Full
+            // status can ensure that this method is not called just
+            // after "remove" method is call.(so, canRemove can keep
+            // true after "next" method called)
+            return (pos != rear)
+                    || ((status == DequeStatus.Full) && !canRemove);
+        }
+
+        @SuppressWarnings( { "synthetic-access", "unchecked" })
+        public E next() {
+            if (hasNextInternal()) {
+                E result = (E) elements[pos];
+                if (expectedModCount == modCount && null != result) {
+                    canRemove = true;
+                    pos = circularBiggerPos(pos);
+                    return result;
+                }
+                throw new ConcurrentModificationException();
+            }
+            throw new NoSuchElementException();
+        }
+
+        @SuppressWarnings("synthetic-access")
+        public void remove() {
+            if (canRemove) {
+                int removedPos = circularSmallerPos(pos);
+                if (expectedModCount == modCount
+                        && null != elements[removedPos]) {
+                    removeInternal(removedPos, true);
+                    canRemove = false;
+                    return;
+                }
+                throw new ConcurrentModificationException();
+            }
+            throw new IllegalStateException();
+        }
+    }
+
+    /*
+     * NOTES:descendingIterator is not fail-fast, according to the documentation
+     * and test case.
+     */
+    @SuppressWarnings("hiding")
+    private class ReverseArrayDequeIterator<E> implements Iterator<E> {
+        private int pos;
+
+        private final int expectedModCount;
+
+        private boolean canRemove;
+
+        @SuppressWarnings("synthetic-access")
+        ReverseArrayDequeIterator() {
+            super();
+            expectedModCount = modCount;
+            pos = circularSmallerPos(rear);
+            canRemove = false;
+        }
+
+        @SuppressWarnings("synthetic-access")
+        public boolean hasNext() {
+            if (expectedModCount != modCount) {
+                return false;
+            }
+            return hasNextInternal();
+        }
+
+        private boolean hasNextInternal() {
+            // canRemove means "next" method is called, and the Full
+            // status can ensure that this method is not called just
+            // after "remove" method is call.(so, canRemove can keep
+            // true after "next" method called)
+            return (circularBiggerPos(pos) != front)
+                    || ((status == DequeStatus.Full) && !canRemove);
+        }
+
+        @SuppressWarnings( { "synthetic-access", "unchecked" })
+        public E next() {
+            if (hasNextInternal()) {
+                E result = (E) elements[pos];
+                canRemove = true;
+                pos = circularSmallerPos(pos);
+                return result;
+            }
+            throw new NoSuchElementException();
+        }
+
+        @SuppressWarnings("synthetic-access")
+        public void remove() {
+            if (canRemove) {
+                removeInternal(circularBiggerPos(pos), false);
+                canRemove = false;
+                return;
+            }
+            throw new IllegalStateException();
+        }
+    }
+
+    /**
+     * Constructs a new empty instance of ArrayDeque big enough for 16 elements.
+     */
+    public ArrayDeque() {
+        this(DEFAULT_SIZE);
+    }
+
+    /**
+     * Constructs a new empty instance of ArrayDeque big enough for specified
+     * number of elements.
+     *
+     * @param minSize
+     *            the smallest size of the ArrayDeque
+     */
+    @SuppressWarnings("unchecked")
+    public ArrayDeque(final int minSize) {
+        int size = countInitSize(minSize);
+        elements = (E[]) new Object[size];
+        front = rear = 0;
+        status = DequeStatus.Empty;
+        modCount = 0;
+    }
+
+    /*
+     * count out the size for a new deque, and ensure that size >= minSize
+     */
+    private int countInitSize(final int minSize) {
+        int size = Math.max(minSize, DEFAULT_SIZE);
+        // get the smallest number that not smaller than size,
+        // and is a power of 2.
+        size = Integer.highestOneBit(size - 1) << 1;
+        if (0 >= size) {
+            size = minSize;
+        }
+        return size;
+    }
+
+    /**
+     * Constructs a new instance of ArrayDeque containing the elements of the
+     * specified collection, with the order returned by the collection's
+     * iterator.
+     *
+     * @param c
+     *            the source of the elements
+     * @throws NullPointerException
+     *             if the collection is null
+     */
+    @SuppressWarnings("unchecked")
+    public ArrayDeque(Collection<? extends E> c) {
+        elements = (E[]) new Object[countInitSize(c.size())];
+        front = rear = 0;
+        status = DequeStatus.Empty;
+        modCount = 0;
+        Iterator<? extends E> it = c.iterator();
+        while (it.hasNext()) {
+            addLastImpl(it.next());
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param e
+     *            the element
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Deque#addFirst(java.lang.Object)
+     */
+    public void addFirst(E e) {
+        offerFirst(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param e
+     *            the element
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Deque#addLast(java.lang.Object)
+     */
+    public void addLast(E e) {
+        addLastImpl(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param e
+     *            the element
+     * @return true
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Deque#offerFirst(java.lang.Object)
+     */
+    public  boolean offerFirst(E e) {
+        checkNull(e);
+        checkAndExpand();
+        front = circularSmallerPos(front);
+        elements[front] = e;
+        resetStatus(true);
+        modCount++;
+        return true;
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param e
+     *            the element
+     * @return true if the operation succeeds or false if it fails
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Deque#offerLast(java.lang.Object)
+     */
+    public boolean offerLast(E e) {
+        return addLastImpl(e);
+    }
+
+    /**
+     * Inserts the element at the tail of the deque.
+     *
+     * @param e
+     *            the element
+     * @return true if the operation succeeds or false if it fails.
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Queue#offer(java.lang.Object)
+     */
+    public boolean offer(E e) {
+        return addLastImpl(e);
+    }
+
+    /**
+     * Inserts the element to the tail of the deque.
+     *
+     * @param e
+     *            the element
+     * @return true
+     * @see java.util.AbstractCollection#add(java.lang.Object)
+     */
+    @Override
+    public boolean add(E e) {
+        return addLastImpl(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param e
+     *            the element to push
+     * @throws NullPointerException
+     *             if the element is null
+     * @see java.util.Deque#push(java.lang.Object)
+     */
+    public void push(E e) {
+        offerFirst(e);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Deque#removeFirst()
+     */
+    public  E removeFirst() {
+        checkEmpty();
+        return removePollFirstImpl();
+    }
+
+    /**
+     * Gets and removes the head element of this deque. This method throws an
+     * exception if the deque is empty.
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Queue#remove()
+     */
+    public E remove() {
+        return removeFirst();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Deque#pop()
+     */
+    public E pop() {
+        return removeFirst();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the tail element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Deque#removeLast()
+     */
+    public  E removeLast() {
+        checkEmpty();
+        return removeLastImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the head element or null if the deque is empty
+     * @see java.util.Deque#pollFirst()
+     */
+    public  E pollFirst() {
+        return (status == DequeStatus.Empty) ? null : removePollFirstImpl();
+    }
+
+    /**
+     * Gets and removes the head element of this deque. This method returns null
+     * if the deque is empty.
+     *
+     * @return the head element or null if the deque is empty
+     * @see java.util.Queue#poll()
+     */
+    public E poll() {
+        return pollFirst();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the tail element or null if the deque is empty
+     * @see java.util.Deque#pollLast()
+     */
+    public  E pollLast() {
+        return (status == DequeStatus.Empty) ? null : removeLastImpl();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Deque#getFirst()
+     */
+    public  E getFirst() {
+        checkEmpty();
+        return elements[front];
+    }
+
+    /**
+     * Gets but does not remove the head element of this deque. It throws an
+     * exception if the deque is empty.
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Queue#element()
+     */
+    public E element() {
+        return getFirst();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the tail element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     * @see java.util.Deque#getLast()
+     */
+    public  E getLast() {
+        checkEmpty();
+        return elements[circularSmallerPos(rear)];
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the head element or null if the deque is empty
+     * @see java.util.Deque#peekFirst()
+     */
+    public  E peekFirst() {
+        return (status == DequeStatus.Empty) ? null : elements[front];
+    }
+
+    /**
+     * Gets but not removes the head element of this deque. This method returns
+     * null if the deque is empty.
+     *
+     * @return the head element or null if the deque is empty
+     * @see java.util.Queue#peek()
+     */
+    public  E peek() {
+        return (status == DequeStatus.Empty) ? null : elements[front];
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the tail element or null if the deque is empty
+     * @see java.util.Deque#peekLast()
+     */
+    public  E peekLast() {
+        return (status == DequeStatus.Empty) ? null
+                : elements[circularSmallerPos(rear)];
+    }
+
+    private void checkNull(E e) {
+        if (null == e) {
+            throw new NullPointerException();
+        }
+    }
+
+    private void checkEmpty() {
+        if (status == DequeStatus.Empty) {
+            throw new NoSuchElementException();
+        }
+    }
+
+    private int circularSmallerPos(int current) {
+        return (current - 1 < 0) ? (elements.length - 1) : current - 1;
+    }
+
+    private int circularBiggerPos(int current) {
+        return (current + 1 >= elements.length) ? 0 : current + 1;
+    }
+
+    @SuppressWarnings("unchecked")
+    /*
+     * If array of elements is full, there will be a new bigger array to store
+     * the elements.
+     */
+    private void checkAndExpand() {
+        if (status != DequeStatus.Full) {
+            return;
+        }
+        if (Integer.MAX_VALUE == elements.length) {
+            throw new IllegalStateException();
+        }
+        int length = elements.length;
+        int newLength = length << 1;
+        // bigger than Integer.MAX_VALUE
+        if (newLength < 0) {
+            newLength = Integer.MAX_VALUE;
+        }
+        E[] newElements = (E[]) new Object[newLength];
+        System.arraycopy(elements, front, newElements, 0, length - front);
+        System.arraycopy(elements, 0, newElements, length - front, front);
+        front = 0;
+        rear = length;
+        status = DequeStatus.Normal;
+        elements = newElements;
+    }
+
+    /**
+     * Resets the status after adding or removing operation.
+     *
+     * @param adding
+     *            if the method is called after an "adding" operation
+     */
+    private void resetStatus(boolean adding) {
+        if (front == rear) {
+            status = adding ? DequeStatus.Full : DequeStatus.Empty;
+        } else {
+            status = DequeStatus.Normal;
+        }
+    }
+
+    private  boolean addLastImpl(E e) {
+        checkNull(e);
+        checkAndExpand();
+        elements[rear] = e;
+        rear = circularBiggerPos(rear);
+        resetStatus(true);
+        modCount++;
+        return true;
+    }
+
+    private E removePollFirstImpl() {
+        E element = elements[front];
+        elements[front] = null;
+        front = circularBiggerPos(front);
+        resetStatus(false);
+        modCount++;
+        return element;
+    }
+
+    private E removeLastImpl() {
+        int last = circularSmallerPos(rear);
+        E element = elements[last];
+        elements[last] = null;
+        rear = last;
+        resetStatus(false);
+        modCount++;
+        return element;
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param obj
+     *            the element to be removed
+     * @return true if the operation succeeds or false if the deque does not
+     *         contain the element
+     * @see java.util.Deque#removeFirstOccurrence(java.lang.Object)
+     */
+    public boolean removeFirstOccurrence(Object obj) {
+        return removeFirstOccurrenceImpl(obj);
+    }
+
+    /**
+     * Removes the first equivalent element of the specified object. If the
+     * deque does not contain the element, it is unchanged and returns false.
+     *
+     * @param obj
+     *            the element to be removed
+     * @return true if the operation succeeds or false if the deque does not
+     *         contain the element
+     * @see java.util.AbstractCollection#remove(java.lang.Object)
+     */
+    @Override
+    public boolean remove(Object obj) {
+        return removeFirstOccurrenceImpl(obj);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param obj
+     *            the element to be removed
+     * @return true if the operation succeeds or false if the deque does not
+     *         contain the element.
+     * @see java.util.Deque#removeLastOccurrence(java.lang.Object)
+     */
+    public  boolean removeLastOccurrence(final Object obj) {
+        if (null != obj) {
+            Iterator<E> iter = descendingIterator();
+            while (iter.hasNext()) {
+                if (iter.next().equals(obj)) {
+                    iter.remove();
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    private  boolean removeFirstOccurrenceImpl(final Object obj) {
+        if (null != obj) {
+            Iterator<E> iter = iterator();
+            while (iter.hasNext()) {
+                if (iter.next().equals(obj)) {
+                    iter.remove();
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    /*
+     * Removes the element in the cursor position and shifts front elements to
+     * fill the gap if frontShift is true, shifts rear elements otherwise.
+     *
+     */
+    private void removeInternal(final int current, final boolean frontShift) {
+        int cursor = current;
+        if (frontShift) {
+            while (cursor != front) {
+                int next = circularSmallerPos(cursor);
+                elements[cursor] = elements[next];
+                cursor = next;
+            }
+            front = circularBiggerPos(front);
+        } else {
+            while (cursor != rear) {
+                int next = circularBiggerPos(cursor);
+                elements[cursor] = elements[next];
+                cursor = next;
+            }
+            rear = circularSmallerPos(rear);
+        }
+        elements[cursor] = null;
+        resetStatus(false);
+    }
+
+    /**
+     * Returns the size of the deque.
+     *
+     * @return the size of the deque
+     * @see java.util.AbstractCollection#size()
+     */
+    @Override
+    public  int size() {
+        if (status == DequeStatus.Full) {
+            return elements.length;
+        }
+        return (front <= rear) ? (rear - front)
+                : (rear + elements.length - front);
+    }
+
+    /**
+     * Returns true if the deque has no elements.
+     *
+     * @return true if the deque has no elements, false otherwise
+     * @see java.util.AbstractCollection#isEmpty()
+     */
+    @Override
+    public  boolean isEmpty() {
+        return 0 == size();
+    }
+
+    /**
+     * Returns true if the specified element is in the deque.
+     *
+     * @param obj
+     *            the element
+     * @return true if the element is in the deque, false otherwise
+     * @see java.util.AbstractCollection#contains(java.lang.Object)
+     */
+    @SuppressWarnings("cast")
+    @Override
+    public  boolean contains(final Object obj) {
+        if (null != obj) {
+            Iterator<E> it = new ArrayDequeIterator<E>();
+            while (it.hasNext()) {
+                if (obj.equals((E) it.next())) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Empty the deque.
+     *
+     * @see java.util.AbstractCollection#clear()
+     */
+    @SuppressWarnings("cast")
+    @Override
+    public  void clear() {
+        if (status != DequeStatus.Empty) {
+            int cursor = front;
+            do {
+                elements[cursor] = null;
+                cursor = circularBiggerPos(cursor);
+            } while (cursor != rear);
+            status = DequeStatus.Empty;
+        }
+        front = rear = 0;
+        modCount = 0;
+    }
+
+    /**
+     * Returns a clone of the deque.
+     *
+     * @return the clone of the deque
+     * @see java.lang.Object#clone()
+     * @see java.lang.Cloneable
+     */
+    @SuppressWarnings("unchecked")
+    @Override
+    public  ArrayDeque<E> clone() {
+        try {
+            ArrayDeque<E> newDeque = (ArrayDeque<E>) super.clone();
+            newDeque.elements = elements.clone();
+            return newDeque;
+        } catch (CloneNotSupportedException e) {
+            return null;
+        }
+    }
+
+    /**
+     * Returns all the elements in an array from head to tail. The result is a
+     * copy of all the elements.
+     *
+     * @return the Array of all the elements
+     * @see java.util.AbstractCollection#toArray()
+     */
+    @Override
+    public Object[] toArray() {
+        return newArray(new Object[size()]);
+    }
+
+    /**
+     * Returns all the elements in an array from head to tail, and the type of
+     * the result array is the type of the argument array. If the argument array
+     * is big enough, the elements from the deque will be stored in it(elements
+     * following the tail of the deque is set to null, if any); otherwise, it
+     * will return a new array with the size of the argument array and size of
+     * the deque.
+     *
+     * @param <T>
+     *            the type of elements in the array
+     * @param array
+     *            the array stores all the elements from the deque, if it has
+     *            enough space; otherwise, a new array of the same type and the
+     *            size of the deque will be used
+     * @return the Array of all the elements
+     * @throws ArrayStoreException
+     *             if the type of the argument array is not compatible with
+     *             every element in the deque
+     * @throws NullPointerException
+     *             if the argument array is null
+     * @see java.util.AbstractCollection#toArray
+     */
+    @Override
+    public <T> T[] toArray(T[] array) {
+        return newArray(array);
+    }
+
+    @SuppressWarnings("unchecked")
+    private  <T> T[] newArray(T[] array) {
+        int size = size();
+        if (size > array.length) {
+            Class<?> clazz = array.getClass().getComponentType();
+            array = (T[]) Array.newInstance(clazz, size);
+        }
+        if (front < rear) {
+            System.arraycopy(elements, front, array, 0, size);
+        } else if (size != 0) {
+            int length = elements.length;
+            System.arraycopy(elements, front, array, 0, length - front);
+            System.arraycopy(elements, 0, array, length - front, rear);
+        }
+        if (size < array.length) {
+            array[size] = null;
+        }
+        return array;
+    }
+
+    /**
+     * Returns the iterator of the deque. The elements will be ordered from head
+     * to tail.
+     *
+     * @return the iterator
+     * @see java.util.AbstractCollection#iterator()
+     */
+    @SuppressWarnings("synthetic-access")
+    @Override
+    public Iterator<E> iterator() {
+        return new ArrayDequeIterator<E>();
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @return the reverse order Iterator
+     * @see java.util.Deque#descendingIterator()
+     */
+    public Iterator<E> descendingIterator() {
+        return new ReverseArrayDequeIterator<E>();
+    }
+
+    /**
+     * Deserialization method.
+     *
+     * @param stream
+     *            the ObjectInputStream
+     * @throws IOException
+     * @throws ClassNotFoundException
+     */
+    @SuppressWarnings("unchecked")
+    private void readObject(ObjectInputStream stream) throws IOException,
+            ClassNotFoundException {
+        stream.defaultReadObject();
+        int size = stream.readInt();
+        elements = (E[]) new Object[countInitSize(size)];
+        front = rear = 0;
+        status = DequeStatus.Empty;
+        modCount = 0;
+        for (int i = 0; i < size; i++) {
+            addLastImpl((E) stream.readObject());
+        }
+    }
+
+    /**
+     * Serialization method.
+     *
+     * @param stream
+     *            the ObjectOutputStream
+     * @serialData The current size of the deque, followed by all the elements
+     *             from head to tail.
+     * @throws IOException
+     *
+     */
+    private void writeObject(ObjectOutputStream stream) throws IOException {
+        stream.defaultWriteObject();
+        stream.writeInt(size());
+        Iterator<?> it = new ArrayDequeIterator<E>();
+        while (it.hasNext()) {
+            stream.writeObject(it.next());
+        }
+    }
+
+}
\ No newline at end of file
diff --git a/luni/src/main/java/java/util/Deque.java b/luni/src/main/java/java/util/Deque.java
new file mode 100644
index 0000000..b13cdb0
--- /dev/null
+++ b/luni/src/main/java/java/util/Deque.java
@@ -0,0 +1,255 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package java.util;
+
+/**
+ * A kind of collection that can insert or remove element at both ends("double
+ * ended queue"). Mostly a deque has no limit of its size.
+ *
+ * Extending from Queue, a deque can be used as a Queue which behavior is
+ * first-in-first-out. Furthermore, a deque can also be used as a Stack(legacy
+ * class) which behavior is last-in-first-out.
+ *
+ * A typical deque does not allow null to be inserted as its element, while some
+ * implementations allow it. But null should not be inserted even in these
+ * implementations, since method poll return null to indicate that there is no
+ * element left in the deque.
+ *
+ * A deque can also remove interior elements by removeFirstOccurrence and
+ * removeLastOccurrence methods. A deque can not access elements by index.
+ *
+ * @param <E>
+ *            the type of elements in this collection
+ * @since 1.6
+ */
+public interface Deque<E> extends Queue<E> {
+
+    /**
+     * Inserts an element at the head of this deque if it dose not violate size
+     * limit immediately. It is better to use offerFirst(E) if a deque is
+     * size-limited.
+     *
+     * @param e
+     *            the element
+     * @throws IllegalStateException
+     *             if it can not add now due to size limit
+     * @throws ClassCastException
+     *             if the class of element can not be added into this deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     * @throws IllegalArgumentException
+     *             if the element can not be added due to some property.
+     */
+    void addFirst(E e);
+
+    /**
+     * Inserts an element at the tail of this deque if it dose not violate size
+     * limit immediately. It is better to use offerLast(E) if a deque is
+     * size-limited.
+     *
+     * @param e
+     *            the element
+     * @throws IllegalStateException
+     *             if it can not add now due to size limit
+     * @throws ClassCastException
+     *             if the class of element can not be added into this deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     * @throws IllegalArgumentException
+     *             if the element can not be added due to some property.
+     */
+    void addLast(E e);
+
+    /**
+     * Inserts an element at the head of this deque unless it would violate size
+     * limit. It is better than the addFirst(E) method in a size-limited deque,
+     * because the latter one may fail to add the element only by throwing an
+     * exception.
+     *
+     * @param e
+     *            the element
+     * @return true if the operation succeeds or false if it fails.
+     * @throws ClassCastException
+     *             if the class of element can not be added into this deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     * @throws IllegalArgumentException
+     *             if the element can not be added due to some property.
+     */
+    boolean offerFirst(E e);
+
+    /**
+     * Inserts an element at the tail of this deque unless it would violate size
+     * limit. It is better than the addLast(E) method in a size-limited deque,
+     * because the latter one may fail to add the element only by throwing an
+     * exception.
+     *
+     * @param e
+     *            the element
+     * @return true if the operation succeeds or false if it fails
+     * @throws ClassCastException
+     *             if the class of element can not be added into this deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     * @throws IllegalArgumentException
+     *             if the element can not be added due to some property
+     */
+    boolean offerLast(E e);
+
+    /**
+     * Gets and removes the head element of this deque. This method throws an
+     * exception if the deque is empty.
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     */
+    E removeFirst();
+
+    /**
+     * Gets and removes the tail element of this deque. This method throws an
+     * exception if the deque is empty.
+     *
+     * @return the tail element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     */
+    E removeLast();
+
+    /**
+     * Gets and removes the head element of this deque. This method returns null
+     * if the deque is empty.
+     *
+     * @return the head element or null if the deque is empty
+     */
+    E pollFirst();
+
+    /**
+     * Gets and removes the tail element of this deque. This method returns null
+     * if the deque is empty.
+     *
+     * @return the tail element or null if the deque is empty
+     */
+    E pollLast();
+
+    /**
+     * Gets but not removes the head element of this deque. This method throws
+     * an exception if the deque is empty.
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     */
+    E getFirst();
+
+    /**
+     * Gets but not removes the tail element of this deque. This method throws
+     * an exception if the deque is empty.
+     *
+     * @return the tail element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     */
+    E getLast();
+
+    /**
+     * Gets but not removes the head element of this deque. This method returns
+     * null if the deque is empty.
+     *
+     * @return the head element or null if the deque is empty
+     */
+    E peekFirst();
+
+    /**
+     * Gets but not removes the tail element of this deque. This method returns
+     * null if the deque is empty.
+     *
+     * @return the tail element or null if the deque is empty
+     */
+    E peekLast();
+
+    /**
+     * Removes the first equivalent element of the specified object. If the
+     * deque does not contain the element, it is unchanged and returns false.
+     *
+     * @param o
+     *            the element to be removed
+     * @return true if the operation succeeds or false if the deque does not
+     *         contain the element.
+     * @throws ClassCastException
+     *             if the class of the element is incompatible with the deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     */
+    boolean removeFirstOccurrence(Object o);
+
+    /**
+     * Removes the last equivalent element of the specified object. If the deque
+     * does not contain the element, it is unchanged and returns false.
+     *
+     * @param o
+     *            the element to be removed
+     * @return true if the operation succeeds or false if the deque does not
+     *         contain the element.
+     * @throws ClassCastException
+     *             if the class of the element is incompatible with the deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     */
+    boolean removeLastOccurrence(Object o);
+
+    /**
+     * Pushes the element to the deque(at the head of the deque), just same as
+     * addFirst(E).
+     *
+     * @param e
+     *            the element
+     * @throws IllegalStateException
+     *             if it can not add now due to size limit
+     * @throws ClassCastException
+     *             if the class of element can not be added into this deque
+     * @throws NullPointerException
+     *             if the element is null and the deque can not contain null
+     *             element
+     * @throws IllegalArgumentException
+     *             if the element can not be added due to some property.
+     */
+    void push(E e);
+
+    /**
+     * Pops the head element of the deque, just same as removeFirst().
+     *
+     * @return the head element
+     * @throws NoSuchElementException
+     *             if the deque is empty
+     */
+    E pop();
+
+    /**
+     * Returns the iterator in reverse order, from tail to head.
+     *
+     * @return the iterator in reverse order
+     */
+    Iterator<E> descendingIterator();
+}
\ No newline at end of file
diff --git a/luni/src/main/java/java/util/NavigableMap.java b/luni/src/main/java/java/util/NavigableMap.java
new file mode 100644
index 0000000..a87a8c0
--- /dev/null
+++ b/luni/src/main/java/java/util/NavigableMap.java
@@ -0,0 +1,262 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+/**
+ * NavigableMap is a SortedMap with navigation methods answering the closest
+ * matches for specified item.
+ *
+ * @param <K>
+ *            the type of key
+ * @param <V>
+ *            the type of value
+ * @since 1.6
+ */
+public interface NavigableMap<K, V> extends SortedMap<K, V> {
+    /**
+     * Returns the entry with the smallest key, or null if the map is empty.
+     *
+     * @return the entry with the smallest key, or null if the map is empty
+     */
+    Map.Entry<K, V> firstEntry();
+
+    /**
+     * Returns the entry with the biggest key, or null if the map is empty.
+     *
+     * @return the entry with the biggest key, or null if the map is empty
+     */
+    Map.Entry<K, V> lastEntry();
+
+    /**
+     * Deletes and returns the entry with the smallest key, or null if the map
+     * is empty.
+     *
+     * @return the entry with the smallest key, or null if the map is empty
+     */
+    Map.Entry<K, V> pollFirstEntry();
+
+    /**
+     * Deletes and returns the entry with the biggest key, or null if the map is
+     * empty.
+     *
+     * @return the entry with the biggest key, or null if the map is empty
+     */
+    Map.Entry<K, V> pollLastEntry();
+
+    /**
+     * Returns an entry related with the smallest key greater than or equal to
+     * the specified key, or null if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the entry, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    Map.Entry<K, V> ceilingEntry(K key);
+
+    /**
+     * Returns the smallest key greater than or equal to the specified key, or
+     * null if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the smallest key greater than or equal to key, or null if no such
+     *         key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    K ceilingKey(K key);
+
+    /**
+     * Returns an entry related with the smallest key greater than the specified
+     * key, or null if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the entry, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    Map.Entry<K, V> higherEntry(K key);
+
+    /**
+     * Returns the smallest key greater than the specified key, or null if no
+     * such key.
+     *
+     * @param key
+     *            the key
+     * @return the smallest key greater than key, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    K higherKey(K key);
+
+    /**
+     * Returns an entry related with the biggest key less than or equal to the
+     * specified key, or null if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the entry, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    Map.Entry<K, V> floorEntry(K key);
+
+    /**
+     * Returns the biggest key less than or equal to the specified key, or null
+     * if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the biggest key less than or equal to key, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    K floorKey(K key);
+
+    /**
+     * Returns an entry related with the biggest key less than the specified
+     * key, or null if no such key.
+     *
+     * @param key
+     *            the key
+     * @return the entry, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    Map.Entry<K, V> lowerEntry(K key);
+
+    /**
+     * Returns the biggest key less than the specified key, or null if no such
+     * key.
+     *
+     * @param key
+     *            the key
+     * @return the biggest key less than key, or null if no such key
+     * @throws ClassCastException
+     *             if the key cannot be compared with the keys in the map
+     * @throws NullPointerException
+     *             if the key is null and the map can not contain null key
+     */
+    K lowerKey(K key);
+
+    /**
+     * Returns a NavigableSet view of the keys in ascending order.
+     *
+     * @return the navigable set view
+     */
+    NavigableSet<K> navigableKeySet();
+
+    /**
+     * Returns a reverse order view of the map.
+     *
+     * @return the reverse order view of the map
+     */
+    NavigableMap<K, V> descendingMap();
+
+    /**
+     * Returns a NavigableSet view of the keys in descending order.
+     *
+     * @return the navigable set view
+     */
+    NavigableSet<K> descendingKeySet();
+
+    /**
+     * Returns a view of part of the map whose keys is from startKey to endKey.
+     *
+     * @param startKey
+     *            the start key
+     * @param startInclusive
+     *            true if the start key is in the returned map
+     * @param endKey
+     *            the end key
+     * @param endInclusive
+     *            true if the end key is in the returned map
+     * @return the sub-map view
+     *
+     * @exception ClassCastException
+     *                when the class of the start or end key is inappropriate
+     *                for this SubMap
+     * @exception NullPointerException
+     *                when the start or end key is null and this SortedMap does
+     *                not support null keys
+     * @exception IllegalArgumentException
+     *                when the start key is greater than the end key
+     */
+    NavigableMap<K, V> subMap(K startKey, boolean startInclusive, K endKey,
+            boolean endInclusive);
+
+    /**
+     * Returns a view of the head of the map whose keys are smaller than (or
+     * equal to, depends on inclusive argument) endKey.
+     *
+     * @param endKey
+     *            the end key
+     * @param inclusive
+     *            true if the end key is in the returned map
+     * @return the head-map view
+     *
+     * @exception ClassCastException
+     *                when the class of the end key is inappropriate for this
+     *                SubMap
+     * @exception NullPointerException
+     *                when the end key is null and this SortedMap does not
+     *                support null keys
+     * @exception IllegalArgumentException
+     *                when the map is range-limited and end key is out of the
+     *                range of the map
+     */
+    NavigableMap<K, V> headMap(K endKey, boolean inclusive);
+
+    /**
+     * Returns a view of the tail of the map whose keys are bigger than (or
+     * equal to, depends on inclusive argument) startKey.
+     *
+     * @param startKey
+     *            the start key
+     * @param inclusive
+     *            true if the start key is in the returned map
+     * @return the tail-map view
+     *
+     * @exception ClassCastException
+     *                when the class of the start key is inappropriate for this
+     *                SubMap
+     * @exception NullPointerException
+     *                when the start key is null and this SortedMap does not
+     *                support null keys
+     * @exception IllegalArgumentException
+     *                when the map is range-limited and start key is out of the
+     *                range of the map
+     */
+    NavigableMap<K, V> tailMap(K startKey, boolean inclusive);
+}
\ No newline at end of file
diff --git a/luni/src/main/java/java/util/NavigableSet.java b/luni/src/main/java/java/util/NavigableSet.java
new file mode 100644
index 0000000..ae94b77
--- /dev/null
+++ b/luni/src/main/java/java/util/NavigableSet.java
@@ -0,0 +1,192 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package java.util;
+
+/**
+ * NavigableSet is a SortedSet with navigation methods answering the closest
+ * matches for specified item.
+ *
+ * @param <E>
+ *            the type of element
+ * @since 1.6
+ */
+public interface NavigableSet<E> extends SortedSet<E> {
+
+    /**
+     * Deletes and returns the smallest element, or null if the set is empty.
+     *
+     * @return the smallest element, or null if the set is empty
+     */
+    E pollFirst();
+
+    /**
+     * Deletes and returns the biggest element, or null if the set is empty.
+     *
+     * @return the biggest element, or null if the set is empty
+     */
+    E pollLast();
+
+    /**
+     * Returns the smallest element bigger than the specified one, or null if no
+     * such element.
+     *
+     * @param e
+     *            the specified element
+     * @return the smallest element bigger than the specified one, or null if no
+     *         such element
+     * @throws ClassCastException
+     *             if the element cannot be compared with the ones in the set
+     * @throws NullPointerException
+     *             if the element is null and the set can not contain null
+     */
+    E higher(E e);
+
+    /**
+     * Returns the smallest element bigger than or equal to the specified one,
+     * or null if no such element.
+     *
+     * @param e
+     *            the specified element
+     * @return the smallest element bigger than or equal to the specified one,
+     *         or null if no such element
+     * @throws ClassCastException
+     *             if the element cannot be compared with the ones in the set
+     * @throws NullPointerException
+     *             if the element is null and the set can not contain null
+     */
+    E ceiling(E e);
+
+    /**
+     * Returns the biggest element less than the specified one, or null if no
+     * such element.
+     *
+     * @param e
+     *            the specified element
+     * @return the biggest element less than the specified one, or null if no
+     *         such element
+     * @throws ClassCastException
+     *             if the element cannot be compared with the ones in the set
+     * @throws NullPointerException
+     *             if the element is null and the set can not contain null
+     */
+    E lower(E e);
+
+    /**
+     * Returns the biggest element less than or equal to the specified one, or
+     * null if no such element.
+     *
+     * @param e
+     *            the specified element
+     * @return the biggest element less than or equal to the specified one, or
+     *         null if no such element
+     * @throws ClassCastException
+     *             if the element cannot be compared with the ones in the set
+     * @throws NullPointerException
+     *             if the element is null and the set can not contain null
+     */
+    E floor(E e);
+
+    /**
+     * Returns a descending iterator of this set.
+     *
+     * @return the descending iterator
+     */
+    Iterator<E> descendingIterator();
+
+    /**
+     * Returns a reverse order view of this set.
+     *
+     * @return the reverse order view
+     */
+    NavigableSet<E> descendingSet();
+
+    /**
+     * Returns a NavigableSet of the specified portion of this set which
+     * contains elements greater (or equal to, depends on startInclusive) the
+     * start element but less than (or equal to, depends on endInclusive) the
+     * end element. The returned NavigableSet is backed by this set so changes
+     * to one are reflected by the other.
+     *
+     * @param start
+     *            the start element
+     * @param startInclusive
+     *            true if the start element is in the returned set
+     * @param end
+     *            the end element
+     * @param endInclusive
+     *            true if the end element is in the returned set
+     * @return the subset
+     *
+     * @throws ClassCastException
+     *             when the start or end object cannot be compared with the
+     *             elements in this set
+     * @throws NullPointerException
+     *             when the start or end object is null and the set cannot
+     *             contain null
+     * @throws IllegalArgumentException
+     *             when the start is bigger than end; or start or end is out of
+     *             range and the set has a range
+     */
+    NavigableSet<E> subSet(E start, boolean startInclusive, E end,
+            boolean endInclusive);
+
+    /**
+     * Returns a NavigableSet of the specified portion of this set which
+     * contains elements less than (or equal to, depends on endInclusive) the
+     * end element. The returned NavigableSet is backed by this set so changes
+     * to one are reflected by the other.
+     *
+     * @param end
+     *            the end element
+     * @param endInclusive
+     *            true if the end element is in the returned set
+     * @return the subset
+     *
+     * @throws ClassCastException
+     *             when the end object cannot be compared with the elements in
+     *             this set
+     * @throws NullPointerException
+     *             when the end object is null and the set cannot contain handle
+     *             null
+     * @throws IllegalArgumentException
+     *             when end is out of range and the set has a range
+     */
+    NavigableSet<E> headSet(E end, boolean endInclusive);
+
+    /**
+     * Returns a NavigableSet of the specified portion of this set which
+     * contains elements greater (or equal to, depends on startInclusive) the
+     * start element. The returned NavigableSet is backed by this set so changes
+     * to one are reflected by the other.
+     *
+     * @param start
+     *            the start element
+     * @param startInclusive
+     *            true if the start element is in the returned set
+     * @return the subset
+     *
+     * @throws ClassCastException
+     *             when the start object cannot be compared with the elements in
+     *             this set
+     * @throws NullPointerException
+     *             when the start object is null and the set cannot contain null
+     * @throws IllegalArgumentException
+     *             when start is out of range and the set has a range
+     */
+    NavigableSet<E> tailSet(E start, boolean startInclusive);
+}
\ No newline at end of file