From 8043168f6c493ecc9a79ea0863cba7a4fac02895 Mon Sep 17 00:00:00 2001 From: Jesse Wilson Date: Tue, 27 Apr 2010 15:56:39 -0700 Subject: [PATCH] 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. --- .../luni/src/main/java/java/util/Collections.java | 219 ++++++++++++++- .../luni/src/main/java/java/util/LinkedList.java | 247 ++++++++++++++--- libcore/luni/src/main/java/java/util/TreeSet.java | 308 ++++++++++++++------- 3 files changed, 649 insertions(+), 125 deletions(-) diff --git a/libcore/luni/src/main/java/java/util/Collections.java b/libcore/luni/src/main/java/java/util/Collections.java index af49cc097..1b7336691 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 @@ public class Collections { Iterator> 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 @@ public class Collections { } /** + * Returns a set backed by {@code map}. + * + * @throws IllegalArgumentException if the map is not empty + * @since 1.6 + */ + public static Set newSetFromMap(Map map) { + if (map.isEmpty()) { + return new SetFromMap(map); + } + throw new IllegalArgumentException(); + } + + /** + * Returns a last-in, first-out queue as a view of {@code deque}. + * + * @since 1.6 + */ + public static Queue asLifoQueue(Deque deque) { + return new AsLIFOQueue(deque); + } + + private static class SetFromMap extends AbstractSet implements + Serializable { + private static final long serialVersionUID = 2454657854757543876L; + + // must named as it, to pass serialization compatibility test. + private Map m; + + private transient Set backingSet; + + SetFromMap(final Map 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[] toArray(T[] contents) { + return backingSet.toArray(contents); + } + + @Override + public Iterator 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 extends AbstractQueue implements + Serializable { + private static final long serialVersionUID = 1802017725587941708L; + + // must named as it, to pass serialization compatibility test. + private final Deque q; + + AsLIFOQueue(final Deque deque) { + super(); + this.q = deque; + } + + @Override + public Iterator 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[] 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 implements Collection, diff --git a/libcore/luni/src/main/java/java/util/LinkedList.java b/libcore/luni/src/main/java/java/util/LinkedList.java index 9db9c9c06..4056b8e69 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 @@ public class LinkedList extends AbstractSequentialList implements } } + /* + * NOTES:descendingIterator is not fail-fast, according to the documentation + * and test case. + */ + private class ReverseLinkIterator implements Iterator { + private int expectedModCount; + + private final LinkedList list; + + private Link link; + + private boolean canRemove; + + ReverseLinkIterator(LinkedList 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 next = link.previous; + Link 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 @@ public class LinkedList extends AbstractSequentialList implements */ @Override public boolean add(E object) { - // Cannot call addLast() as subclasses can override + return addLastImpl(object); + } + + private boolean addLastImpl(E object) { Link oldLast = voidLink.previous; Link newLink = new Link(object, oldLast, voidLink); voidLink.previous = newLink; @@ -350,12 +411,17 @@ public class LinkedList extends AbstractSequentialList implements * the object to add. */ public void addFirst(E object) { + addFirstImpl(object); + } + + private boolean addFirstImpl(E object) { Link oldFirst = voidLink.next; Link newLink = new Link(object, voidLink, oldFirst); voidLink.next = newLink; oldFirst.previous = newLink; size++; modCount++; + return true; } /** @@ -365,12 +431,7 @@ public class LinkedList extends AbstractSequentialList implements * the object to add. */ public void addLast(E object) { - Link oldLast = voidLink.previous; - Link newLink = new Link(object, oldLast, voidLink); - voidLink.previous = newLink; - oldLast.next = newLink; - size++; - modCount++; + addLastImpl(object); } /** @@ -467,6 +528,10 @@ public class LinkedList extends AbstractSequentialList implements * if this {@code LinkedList} is empty. */ public E getFirst() { + return getFirstImpl(); + } + + private E getFirstImpl() { Link first = voidLink.next; if (first != voidLink) { return first.data; @@ -598,26 +663,7 @@ public class LinkedList extends AbstractSequentialList implements @Override public boolean remove(Object object) { - Link 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 next = link.next; - Link previous = link.previous; - previous.next = next; - next.previous = previous; - size--; - modCount++; - return true; + return removeFirstOccurrenceImpl(object); } /** @@ -628,6 +674,10 @@ public class LinkedList extends AbstractSequentialList implements * if this {@code LinkedList} is empty. */ public E removeFirst() { + return removeFirstImpl(); + } + + private E removeFirstImpl() { Link first = voidLink.next; if (first != voidLink) { Link next = first.next; @@ -648,6 +698,10 @@ public class LinkedList extends AbstractSequentialList implements * if this {@code LinkedList} is empty. */ public E removeLast() { + return removeLastImpl(); + } + + private E removeLastImpl() { Link last = voidLink.previous; if (last != voidLink) { Link previous = last.previous; @@ -661,6 +715,134 @@ public class LinkedList extends AbstractSequentialList implements } /** + * {@inheritDoc} + * + * @see java.util.Deque#descendingIterator() + * @since 1.6 + */ + public Iterator descendingIterator() { + return new ReverseLinkIterator(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 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 iter = new ReverseLinkIterator(this); + return removeOneOccurrence(o, iter); + } + + private boolean removeFirstOccurrenceImpl(Object o) { + Iterator iter = new LinkIterator(this, 0); + return removeOneOccurrence(o, iter); + } + + private boolean removeOneOccurrence(Object o, Iterator 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 class LinkedList extends AbstractSequentialList implements } public boolean offer(E o) { - add(o); - return true; + return addLastImpl(o); } public E poll() { @@ -716,16 +897,20 @@ public class LinkedList extends AbstractSequentialList implements } public E remove() { - return removeFirst(); + return removeFirstImpl(); } public E peek() { + return peekFirstImpl(); + } + + private E peekFirstImpl() { Link 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 98f63034d..d636dc7ef 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 @@ import java.io.Serializable; * * @since 1.2 */ -public class TreeSet extends AbstractSet implements SortedSet, +public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, Serializable { private static final long serialVersionUID = -2479143000061671589L; /** Keys are this set's elements. Values are always Boolean.TRUE */ - private transient SortedMap backingMap; + private transient NavigableMap backingMap; - private TreeSet(SortedMap map) { - this.backingMap = map; + private transient NavigableSet descendingSet; + + TreeSet(NavigableMap map) { + backingMap = map; } /** @@ -154,7 +156,7 @@ public class TreeSet extends AbstractSet implements SortedSet, try { TreeSet clone = (TreeSet) super.clone(); if (backingMap instanceof TreeMap) { - clone.backingMap = (SortedMap) ((TreeMap) backingMap) + clone.backingMap = (NavigableMap) ((TreeMap) backingMap) .clone(); } else { clone.backingMap = new TreeMap(backingMap); @@ -194,45 +196,6 @@ public class TreeSet extends AbstractSet implements SortedSet, } /** - * 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 headSet(E end) { - // Check for errors - Comparator c = backingMap.comparator(); - if (c == null) { - ((Comparable) end).compareTo(end); - } else { - c.compare(end, end); - } - return new TreeSet(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 @@ public class TreeSet extends AbstractSet implements SortedSet, } /** - * 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 descendingIterator() { + return descendingSet().iterator(); } /** @@ -296,57 +257,147 @@ public class TreeSet extends AbstractSet implements SortedSet, } /** - * 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 entry = backingMap.pollFirstEntry(); + return (null == entry) ? null : entry.getKey(); + } + + /** + * {@inheritDoc} + * + * @see java.util.NavigableSet#pollLast() + * @since 1.6 + */ + public E pollLast() { + Map.Entry 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 descendingSet() { + return (null != descendingSet) ? descendingSet + : (descendingSet = new TreeSet(backingMap.descendingMap())); + } + + /** + * {@inheritDoc} + * + * @see java.util.NavigableSet#subSet(Object, boolean, Object, boolean) + * @since 1.6 */ @SuppressWarnings("unchecked") - public SortedSet subSet(E start, E end) { + public NavigableSet subSet(E start, boolean startInclusive, E end, + boolean endInclusive) { + Comparator c = backingMap.comparator(); + int compare = (c == null) ? ((Comparable) start).compareTo(end) : c + .compare(start, end); + if (compare <= 0) { + return new TreeSet(backingMap.subMap(start, startInclusive, end, + endInclusive)); + } + throw new IllegalArgumentException(); + } + + /** + * {@inheritDoc} + * + * @see java.util.NavigableSet#headSet(Object, boolean) + * @since 1.6 + */ + @SuppressWarnings("unchecked") + public NavigableSet headSet(E end, boolean endInclusive) { + // Check for errors Comparator c = backingMap.comparator(); if (c == null) { - if (((Comparable) start).compareTo(end) <= 0) { - return new TreeSet(backingMap.subMap(start, end)); - } + ((Comparable) end).compareTo(end); } else { - if (c.compare(start, end) <= 0) { - return new TreeSet(backingMap.subMap(start, end)); - } + c.compare(end, end); } - throw new IllegalArgumentException(); + return new TreeSet(backingMap.headMap(end, endInclusive)); } /** - * 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#tailSet(Object, boolean) + * @since 1.6 */ @SuppressWarnings("unchecked") - public SortedSet tailSet(E start) { + public NavigableSet tailSet(E start, boolean startInclusive) { // Check for errors Comparator c = backingMap.comparator(); if (c == null) { @@ -354,7 +405,76 @@ public class TreeSet extends AbstractSet implements SortedSet, } else { c.compare(start, start); } - return new TreeSet(backingMap.tailMap(start)); + return new TreeSet(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 + * start and less than end + * + * @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 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 end + * + * @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 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 + * start + * + * @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 tailSet(E start) { + return tailSet(start, true); } private void writeObject(ObjectOutputStream stream) throws IOException { @@ -377,9 +497,11 @@ public class TreeSet extends AbstractSet implements SortedSet, TreeMap map = new TreeMap( (Comparator) 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