Thomas Broyer has uploaded a new change for review.
https://gwt-review.googlesource.com/3650
Change subject: Add NavigableSet, NavigableMap to GWT and retrofit TreeMap
and TreeSet to implement it.
......................................................................
Add NavigableSet, NavigableMap to GWT and retrofit TreeMap and TreeSet to
implement it.
Author: [email protected]
Bug: issue 4236
Change-Id: I2800b2b54b06a7ef255e01ad44b11909d878362a
---
A user/super/com/google/gwt/emul/java/util/AbstractNavigableMap.java
A user/super/com/google/gwt/emul/java/util/NavigableMap.java
A user/super/com/google/gwt/emul/java/util/NavigableSet.java
M user/super/com/google/gwt/emul/java/util/TreeMap.java
M user/super/com/google/gwt/emul/java/util/TreeSet.java
5 files changed, 880 insertions(+), 120 deletions(-)
diff --git
a/user/super/com/google/gwt/emul/java/util/AbstractNavigableMap.java
b/user/super/com/google/gwt/emul/java/util/AbstractNavigableMap.java
new file mode 100644
index 0000000..6327e8b
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/AbstractNavigableMap.java
@@ -0,0 +1,403 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Licensed 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;
+
+/**
+ * Skeletal implementation of a NavigableMap.
+ */
+abstract class AbstractNavigableMap<K, V> extends AbstractMap<K, V>
+ implements NavigableMap<K, V> {
+ class DescendingMap extends AbstractNavigableMap<K, V> {
+ @Override
+ public Entry<K, V> ceilingEntry(K key) {
+ return ascendingMap().floorEntry(key);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return Collections.reverseOrder(ascendingMap().comparator());
+ }
+
+ @Override
+ public NavigableMap<K, V> descendingMap() {
+ return ascendingMap();
+ }
+
+ @Override
+ public Entry<K, V> firstEntry() {
+ return ascendingMap().lastEntry();
+ }
+
+ @Override
+ public Entry<K, V> floorEntry(K key) {
+ return ascendingMap().ceilingEntry(key);
+ }
+
+ @Override
+ public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
+ return ascendingMap().tailMap(toKey, inclusive).descendingMap();
+ }
+
+ @Override
+ public Entry<K, V> higherEntry(K key) {
+ return ascendingMap().lowerEntry(key);
+ }
+
+ @Override
+ public Entry<K, V> lastEntry() {
+ return ascendingMap().firstEntry();
+ }
+
+ @Override
+ public Entry<K, V> lowerEntry(K key) {
+ return ascendingMap().higherEntry(key);
+ }
+
+ @Override
+ public int size() {
+ return ascendingMap().size();
+ }
+
+ @Override
+ public NavigableMap<K, V> subMap(
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+ return ascendingMap().subMap(toKey, toInclusive, fromKey,
fromInclusive)
+ .descendingMap();
+ }
+
+ @Override
+ public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
+ return ascendingMap().headMap(fromKey, inclusive).descendingMap();
+ }
+
+ AbstractNavigableMap<K, V> ascendingMap() {
+ return AbstractNavigableMap.this;
+ }
+
+ @Override
+ Iterator<Entry<K, V>> descendingEntryIterator() {
+ return ascendingMap().entryIterator();
+ }
+
+ @Override
+ Iterator<Entry<K, V>> entryIterator() {
+ return ascendingMap().descendingEntryIterator();
+ }
+ }
+
+ class EntrySet extends AbstractSet<Entry<K, V>> {
+
+ @Override
+ public void clear() {
+ AbstractNavigableMap.this.clear();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ if (o instanceof Entry) {
+ Entry<?, ?> entry = (Entry<?, ?>) o;
+ Object value = get(entry.getKey());
+ if (value == null) {
+ return containsKey(entry.getKey()) && entry.getValue() == null;
+ } else {
+ return value.equals(entry.getValue());
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return entryIterator();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ if (contains(o)) {
+ Entry<?, ?> entry = (Entry<?, ?>) o;
+ AbstractNavigableMap.this.remove(entry.getKey());
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int size() {
+ return AbstractNavigableMap.this.size();
+ }
+ }
+
+ private static final class ImmutableEntry<K, V> extends
AbstractMapEntry<K, V> {
+ private final K key;
+
+ private final V value;
+
+ ImmutableEntry(K key, V value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ @Override
+ public K getKey() {
+ return key;
+ }
+
+ @Override
+ public V getValue() {
+ return value;
+ }
+
+ @Override
+ public V setValue(V value) {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ private static final class NavigableKeySet<K, V> extends AbstractSet<K>
+ implements NavigableSet<K> {
+
+ private final NavigableMap<K, V> map;
+
+ NavigableKeySet(NavigableMap<K, V> map) {
+ this.map = map;
+ }
+
+ @Override
+ public K ceiling(K k) {
+ return map.ceilingKey(k);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return map.comparator();
+ }
+
+ @Override
+ public Iterator<K> descendingIterator() {
+ return descendingSet().iterator();
+ }
+
+ @Override
+ public NavigableSet<K> descendingSet() {
+ return new NavigableKeySet<K, V>(map.descendingMap());
+ }
+
+ @Override
+ public K first() {
+ return map.firstKey();
+ }
+
+ @Override
+ public K floor(K k) {
+ return map.floorKey(k);
+ }
+
+ @Override
+ public SortedSet<K> headSet(K toElement) {
+ return headSet(toElement, false);
+ }
+
+ @Override
+ public NavigableSet<K> headSet(K toElement, boolean inclusive) {
+ return map.headMap(toElement, inclusive).navigableKeySet();
+ }
+
+ @Override
+ public K higher(K k) {
+ return map.higherKey(k);
+ }
+
+ @Override
+ public Iterator<K> iterator() {
+ return new Iterator<K>() {
+ final Iterator<Entry<K, V>> entryIterator =
map.entrySet().iterator();
+
+ @Override
+ public boolean hasNext() {
+ return entryIterator.hasNext();
+ }
+
+ @Override
+ public K next() {
+ return entryIterator.next().getKey();
+ }
+
+ @Override
+ public void remove() {
+ entryIterator.remove();
+ }
+ };
+ }
+
+ @Override
+ public K last() {
+ return map.lastKey();
+ }
+
+ @Override
+ public K lower(K k) {
+ return map.lowerKey(k);
+ }
+
+ @Override
+ public K pollFirst() {
+ return getKeyOrNull(map.pollFirstEntry());
+ }
+
+ @Override
+ public K pollLast() {
+ return getKeyOrNull(map.pollLastEntry());
+ }
+
+ @Override
+ public int size() {
+ return map.size();
+ }
+
+ @Override
+ public NavigableSet<K> subSet(
+ K fromElement, boolean fromInclusive, K toElement, boolean
toInclusive) {
+ return map.subMap(fromElement, fromInclusive, toElement, toInclusive)
+ .navigableKeySet();
+ }
+
+ @Override
+ public SortedSet<K> subSet(K fromElement, K toElement) {
+ return subSet(fromElement, true, toElement, false);
+ }
+
+ @Override
+ public SortedSet<K> tailSet(K fromElement) {
+ return tailSet(fromElement, true);
+ }
+
+ @Override
+ public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
+ return map.tailMap(fromElement, inclusive).navigableKeySet();
+ }
+ }
+
+ private static <K, V> K getKeyOrNull(Entry<K, V> entry) {
+ return (entry == null) ? null : entry.getKey();
+ }
+
+ @Override
+ public K ceilingKey(K key) {
+ return getKeyOrNull(ceilingEntry(key));
+ }
+
+ @Override
+ public NavigableSet<K> descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ public NavigableMap<K, V> descendingMap() {
+ return new DescendingMap();
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ return new EntrySet();
+ }
+
+ @Override
+ public K firstKey() {
+ Entry<K, V> entry = lastEntry();
+ if (entry == null) {
+ throw new NoSuchElementException();
+ } else {
+ return entry.getKey();
+ }
+ }
+
+ @Override
+ public K floorKey(K key) {
+ return getKeyOrNull(floorEntry(key));
+ }
+
+ @Override
+ public SortedMap<K, V> headMap(K toKey) {
+ return headMap(toKey, false);
+ }
+
+ @Override
+ public K higherKey(K key) {
+ return getKeyOrNull(higherEntry(key));
+ }
+
+ @Override
+ public K lastKey() {
+ Entry<K, V> entry = lastEntry();
+ if (entry == null) {
+ throw new NoSuchElementException();
+ } else {
+ return entry.getKey();
+ }
+ }
+
+ @Override
+ public K lowerKey(K key) {
+ return getKeyOrNull(lowerEntry(key));
+ }
+
+ @Override
+ public NavigableSet<K> navigableKeySet() {
+ return new NavigableKeySet<K, V>(this);
+ }
+
+ @Override
+ public Entry<K, V> pollFirstEntry() {
+ Entry<K, V> result = firstEntry();
+ if (result == null) {
+ return null;
+ } else {
+ final K key = result.getKey();
+ final V value = result.getValue();
+ remove(result.getKey());
+ return new ImmutableEntry<K, V>(key, value);
+ }
+ }
+
+ @Override
+ public Entry<K, V> pollLastEntry() {
+ Entry<K, V> result = lastEntry();
+ if (result == null) {
+ return null;
+ } else {
+ final K key = result.getKey();
+ final V value = result.getValue();
+ remove(result.getKey());
+ return new ImmutableEntry<K, V>(key, value);
+ }
+ }
+
+ @Override
+ public abstract int size();
+
+ @Override
+ public SortedMap<K, V> subMap(K fromKey, K toKey) {
+ return subMap(fromKey, true, toKey, false);
+ }
+
+ @Override
+ public SortedMap<K, V> tailMap(K fromKey) {
+ return tailMap(fromKey, true);
+ }
+
+ abstract Iterator<Entry<K, V>> descendingEntryIterator();
+
+ abstract Iterator<Entry<K, V>> entryIterator();
+}
diff --git a/user/super/com/google/gwt/emul/java/util/NavigableMap.java
b/user/super/com/google/gwt/emul/java/util/NavigableMap.java
new file mode 100644
index 0000000..428e5a2
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/NavigableMap.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Licensed 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;
+
+/**
+ * Sorted map providing additional query operations and views.
+ *
+ * @param <K> key type.
+ * @param <V> value type.
+ */
+public interface NavigableMap<K, V> extends SortedMap<K, V> {
+ Map.Entry<K, V> ceilingEntry(K key);
+ K ceilingKey(K key);
+ NavigableSet<K> descendingKeySet();
+ NavigableMap<K, V> descendingMap();
+ Map.Entry<K, V> firstEntry();
+ Map.Entry<K, V> floorEntry(K key);
+ K floorKey(K key);
+ NavigableMap<K, V> headMap(K toKey, boolean inclusive);
+ Map.Entry<K, V> higherEntry(K key);
+ K higherKey(K key);
+ Map.Entry<K, V> lastEntry();
+ Map.Entry<K, V> lowerEntry(K key);
+ K lowerKey(K key);
+ NavigableSet<K> navigableKeySet();
+ Map.Entry<K, V> pollFirstEntry();
+ Map.Entry<K, V> pollLastEntry();
+ NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey,
boolean toInclusive);
+ NavigableMap<K, V> tailMap(K fromKey, boolean inclusive);
+}
diff --git a/user/super/com/google/gwt/emul/java/util/NavigableSet.java
b/user/super/com/google/gwt/emul/java/util/NavigableSet.java
new file mode 100644
index 0000000..d0a969e
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/NavigableSet.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Licensed 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 {@code SortedSet} with more flexible queries.
+ *
+ * @param <E> element type.
+ */
+public interface NavigableSet<E> extends SortedSet<E> {
+ E ceiling(E e);
+ Iterator<E> descendingIterator();
+ NavigableSet<E> descendingSet();
+ E floor(E e);
+ NavigableSet<E> headSet(E toElement, boolean inclusive);
+ E higher(E e);
+ E lower(E e);
+ E pollFirst();
+ E pollLast();
+ NavigableSet<E> subSet(
+ E fromElement, boolean fromInclusive, E toElement, boolean
toInclusive);
+ NavigableSet<E> tailSet(E fromElement, boolean inclusive);
+}
\ No newline at end of file
diff --git a/user/super/com/google/gwt/emul/java/util/TreeMap.java
b/user/super/com/google/gwt/emul/java/util/TreeMap.java
index 71195cd..c4c9653 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeMap.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeMap.java
@@ -26,8 +26,8 @@
* @param <K> key type
* @param <V> value type
*/
-public class TreeMap<K, V> extends AbstractMap<K, V> implements
- SortedMap<K, V>, Serializable {
+public class TreeMap<K, V> extends AbstractNavigableMap<K, V> implements
+ Serializable {
/*
* Implementation derived from public domain C implementation as of 5
* September 2007 at:
@@ -36,6 +36,90 @@
*
* This version does not require a parent pointer kept in each node.
*/
+
+ /**
+ * Iterator for <code>descendingMap().entrySet()</code>
+ */
+ private final class DescendingEntryIterator implements Iterator<Entry<K,
V>> {
+ private final Iterator<Map.Entry<K, V>> iter;
+ private Map.Entry<K, V> last = null;
+
+ /**
+ * Constructor for <code>EntrySetIterator</code>.
+ */
+ public DescendingEntryIterator() {
+ this(SubMapType.All, null, false, null, false);
+ }
+
+ /**
+ * Create an iterator which may return only a restricted range.
+ *
+ * @param fromKey the first key to return in the iterator.
+ * @param toKey the upper bound of keys to return.
+ */
+ public DescendingEntryIterator(SubMapType type,
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+ List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
+ reverseOrderAdd(list, type, TreeMap.this.root,
+ fromKey, fromInclusive, toKey, toInclusive);
+ this.iter = list.iterator();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return iter.hasNext();
+ }
+
+ @Override
+ public Map.Entry<K, V> next() {
+ return last = iter.next();
+ }
+
+ @Override
+ public void remove() {
+ iter.remove();
+ TreeMap.this.remove(last.getKey());
+ }
+
+ private boolean inRange(SubMapType type, K key,
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+ if (type.toKeyValid()) {
+ int compare = cmp.compare(key, toKey);
+ if (toInclusive ? (compare > 0) : (compare >= 0)) {
+ return false;
+ }
+ }
+ if (type.fromKeyValid()) {
+ int compare = cmp.compare(key, fromKey);
+ if (fromInclusive ? (compare < 0) : (compare <= 0)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private void reverseOrderAdd(List<Map.Entry<K, V>> list, SubMapType
type,
+ Node<K, V> current, K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
+ if (current == null) {
+ return;
+ }
+ // TODO: truncate this recursion if the whole subtree is known to be
+ // outside of bounds?
+ if (current.child[RIGHT] != null) {
+ reverseOrderAdd(list, type, current.child[RIGHT],
+ fromKey, fromInclusive, toKey, toInclusive);
+ }
+ if (inRange(type, current.getKey(), fromKey, fromInclusive,
+ toKey, toInclusive)) {
+ list.add(current);
+ }
+ if (current.child[LEFT] != null) {
+ reverseOrderAdd(list, type, current.child[LEFT],
+ fromKey, fromInclusive, toKey, toInclusive);
+ }
+ }
+ }
/**
* Iterator for <code>EntrySet</code>.
@@ -48,7 +132,7 @@
* Constructor for <code>EntrySetIterator</code>.
*/
public EntryIterator() {
- this(SubMapType.All, null, null);
+ this(SubMapType.All, null, false, null, false);
}
/**
@@ -57,49 +141,63 @@
* @param fromKey the first key to return in the iterator.
* @param toKey the upper bound of keys to return.
*/
- public EntryIterator(SubMapType type, K fromKey, K toKey) {
+ public EntryIterator(SubMapType type,
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
- inOrderAdd(list, type, TreeMap.this.root, fromKey, toKey);
+ inOrderAdd(list, type, TreeMap.this.root,
+ fromKey, fromInclusive, toKey, toInclusive);
this.iter = list.iterator();
}
+ @Override
public boolean hasNext() {
return iter.hasNext();
}
+ @Override
public Map.Entry<K, V> next() {
return last = iter.next();
}
+ @Override
public void remove() {
iter.remove();
TreeMap.this.remove(last.getKey());
}
private void inOrderAdd(List<Map.Entry<K, V>> list, SubMapType type,
- Node<K, V> current, K fromKey, K toKey) {
+ Node<K, V> current, K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
if (current == null) {
return;
}
+ // TODO: truncate this recursion if the whole subtree is known to be
+ // outside of bounds?
if (current.child[LEFT] != null) {
- inOrderAdd(list, type, current.child[LEFT], fromKey, toKey);
+ inOrderAdd(list, type, current.child[LEFT],
+ fromKey, fromInclusive, toKey, toInclusive);
}
- if (inRange(type, current.getKey(), fromKey, toKey)) {
+ if (inRange(type, current.getKey(), fromKey, fromInclusive,
+ toKey, toInclusive)) {
list.add(current);
}
if (current.child[RIGHT] != null) {
- inOrderAdd(list, type, current.child[RIGHT], fromKey, toKey);
+ inOrderAdd(list, type, current.child[RIGHT],
+ fromKey, fromInclusive, toKey, toInclusive);
}
}
- private boolean inRange(SubMapType type, K key, K fromKey, K toKey) {
+ private boolean inRange(SubMapType type, K key,
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
if (type.toKeyValid()) {
- if (cmp.compare(key, toKey) >= 0) {
+ int compare = cmp.compare(key, toKey);
+ if (toInclusive ? (compare > 0) : (compare >= 0)) {
return false;
}
}
if (type.fromKeyValid()) {
- if (cmp.compare(key, fromKey) < 0) {
+ int compare = cmp.compare(key, fromKey);
+ if (fromInclusive ? (compare < 0) : (compare <= 0)) {
return false;
}
}
@@ -107,11 +205,7 @@
}
}
- private final class EntrySet extends AbstractSet<Entry<K, V>> {
- @Override
- public void clear() {
- TreeMap.this.clear();
- }
+ private final class EntrySet extends AbstractNavigableMap<K, V>.EntrySet
{
@SuppressWarnings("unchecked")
@Override
@@ -124,11 +218,6 @@
return lookupEntry != null
&& Utility.equalsWithNullCheck(lookupEntry.getValue(),
entry.getValue());
- }
-
- @Override
- public Iterator<Entry<K, V>> iterator() {
- return new EntryIterator();
}
@SuppressWarnings("unchecked")
@@ -150,10 +239,28 @@
state.value = entry.getValue();
return removeWithState(entry.getKey(), state);
}
+ }
+
+ private static final class KeyIterator<K, V> implements Iterator<K> {
+ private final Iterator<Entry<K, V>> entryIterator;
+
+ KeyIterator(Iterator<Entry<K, V>> entryIterator) {
+ this.entryIterator = entryIterator;
+ }
@Override
- public int size() {
- return TreeMap.this.size();
+ public boolean hasNext() {
+ return entryIterator.hasNext();
+ }
+
+ @Override
+ public K next() {
+ return entryIterator.next().getKey();
+ }
+
+ @Override
+ public void remove() {
+ entryIterator.remove();
}
}
@@ -209,10 +316,12 @@
&& Utility.equalsWithNullCheck(value, other.getValue());
}
+ @Override
public K getKey() {
return key;
}
+ @Override
public V getValue() {
return value;
}
@@ -224,6 +333,7 @@
return keyHash ^ valueHash;
}
+ @Override
public V setValue(V value) {
V old = this.value;
this.value = value;
@@ -261,17 +371,23 @@
}
}
- private class SubMap extends AbstractMap<K, V> implements SortedMap<K,
V> {
+ private class SubMap extends AbstractNavigableMap<K, V> {
+
+ public final boolean fromInclusive;
// valid only if type is Range or Tail
public final K fromKey;
+
+ public final boolean toInclusive;
// valid only if type is Range or Head
public final K toKey;
public final SubMapType type;
- SubMap(SubMapType type, K fromKey, K toKey) {
+ SubMap(SubMapType type,
+ K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
switch (type) {
case Range:
if (cmp.compare(toKey, fromKey) < 0) {
@@ -293,9 +409,17 @@
}
this.type = type;
this.fromKey = fromKey;
+ this.fromInclusive = fromInclusive;
this.toKey = toKey;
+ this.toInclusive = toInclusive;
}
+ @Override
+ public java.util.Map.Entry<K, V> ceilingEntry(K key) {
+ return guardInRange(TreeMap.this.getNodeAfter(key, true));
+ }
+
+ @Override
public Comparator<? super K> comparator() {
return TreeMap.this.comparator();
}
@@ -312,7 +436,7 @@
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
- return new AbstractSet<Entry<K, V>>() {
+ return new EntrySet() {
@SuppressWarnings("unchecked")
@Override
@@ -336,11 +460,6 @@
return SubMap.this.isEmpty();
}
- @Override
- public Iterator<Entry<K, V>> iterator() {
- return new EntryIterator(type, fromKey, toKey);
- }
-
@SuppressWarnings("unchecked")
@Override
public boolean remove(Object o) {
@@ -356,27 +475,29 @@
state.value = entry.getValue();
return removeWithState(entry.getKey(), state);
}
-
- @Override
- public int size() {
- // TODO(jat): more efficient way to do this?
- int n = 0;
- Iterator<Entry<K, V>> it = iterator();
- while (it.hasNext()) {
- it.next();
- n++;
- }
- return n;
- }
};
}
- public K firstKey() {
- Node<K, V> node = throwNSE(getFirstSubmapNode());
- if (type.toKeyValid() && cmp.compare(node.key, toKey) > 0) {
- throw new NoSuchElementException();
+ @Override
+ public Node<K, V> firstEntry() {
+ Node<K, V> node = getFirstSubmapNode();
+ if (type.toKeyValid()) {
+ int compare = cmp.compare(node.key, toKey);
+ if (toInclusive ? (compare > 0) : (compare >= 0)) {
+ return null;
+ }
}
- return node.key;
+ return node;
+ }
+
+ @Override
+ public K firstKey() {
+ return throwNSE(firstEntry()).key;
+ }
+
+ @Override
+ public java.util.Map.Entry<K, V> floorEntry(K key) {
+ return guardInRange(TreeMap.this.getNodeBefore(key, true));
}
@SuppressWarnings("unchecked")
@@ -389,16 +510,25 @@
return TreeMap.this.get(key);
}
- public SortedMap<K, V> headMap(K toKey) {
- if (type.toKeyValid() && cmp.compare(toKey, this.toKey) > 0) {
- throw new IllegalArgumentException("subMap: " + toKey
- + " greater than " + this.toKey);
+ @Override
+ public NavigableMap<K, V> headMap(K toKey, boolean toInclusive) {
+ if (type.toKeyValid()) {
+ int compare = cmp.compare(toKey, this.toKey);
+ if (toInclusive ? (compare > 0) : (compare >= 0)) {
+ throw new IllegalArgumentException("subMap: " + toKey
+ + " greater than " + this.toKey);
+ }
}
if (type.fromKeyValid()) {
- return TreeMap.this.subMap(fromKey, toKey);
+ return TreeMap.this.subMap(fromKey, fromInclusive, toKey,
toInclusive);
} else {
- return TreeMap.this.headMap(toKey);
+ return TreeMap.this.headMap(toKey, toInclusive);
}
+ }
+
+ @Override
+ public java.util.Map.Entry<K, V> higherEntry(K key) {
+ return guardInRange(TreeMap.this.getNodeAfter(key, false));
}
@Override
@@ -406,12 +536,21 @@
return getFirstSubmapNode() == null;
}
- public K lastKey() {
- Node<K, V> node = throwNSE(getLastSubmapNode());
- if (type.fromKeyValid() && cmp.compare(node.key, fromKey) < 0) {
- throw new NoSuchElementException();
+ @Override
+ public Node<K, V> lastEntry() {
+ Node<K, V> node = getLastSubmapNode();
+ if (type.fromKeyValid()) {
+ int compare = cmp.compare(node.key, fromKey);
+ if (fromInclusive ? (compare < 0) : (compare <= 0)) {
+ return null;
+ }
}
- return node.key;
+ return node;
+ }
+
+ @Override
+ public Entry<K, V> lowerEntry(K key) {
+ return guardInRange(TreeMap.this.getNodeBefore(key, false));
}
@Override
@@ -433,34 +572,78 @@
return TreeMap.this.remove(key);
}
- public SortedMap<K, V> subMap(K newFromKey, K newToKey) {
- if (type.fromKeyValid() && cmp.compare(newFromKey, fromKey) < 0) {
- throw new IllegalArgumentException("subMap: " + newFromKey
- + " less than " + fromKey);
+ @Override
+ public int size() {
+ // TODO(jat): more efficient way to do this?
+ int n = 0;
+ Iterator<Entry<K, V>> it = entryIterator();
+ while (it.hasNext()) {
+ it.next();
+ n++;
}
- if (type.toKeyValid() && cmp.compare(newToKey, toKey) > 0) {
- throw new IllegalArgumentException("subMap: " + newToKey
- + " greater than " + toKey);
- }
- return TreeMap.this.subMap(newFromKey, newToKey);
+ return n;
}
- public SortedMap<K, V> tailMap(K fromKey) {
+ @Override
+ public NavigableMap<K, V> subMap(K newFromKey, boolean
newFromInclusive,
+ K newToKey, boolean newToInclusive) {
+ if (type.fromKeyValid() && cmp.compare(newFromKey, fromKey) < 0) {
+ throw new IllegalArgumentException("subMap: " + newFromKey +
+ " less than " + fromKey);
+ }
+ if (type.toKeyValid() && cmp.compare(newToKey, toKey) > 0) {
+ throw new IllegalArgumentException("subMap: " + newToKey +
+ " greater than " + toKey);
+ }
+ return TreeMap.this.subMap(newFromKey, newFromInclusive,
+ newToKey, newToInclusive);
+ }
+
+ @Override
+ public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
if (type.fromKeyValid() && cmp.compare(fromKey, this.fromKey) < 0) {
throw new IllegalArgumentException("subMap: " + fromKey + " less
than "
+ this.fromKey);
}
if (type.toKeyValid()) {
- return TreeMap.this.subMap(fromKey, toKey);
+ return TreeMap.this.subMap(fromKey, fromInclusive, toKey,
inclusive);
} else {
- return TreeMap.this.tailMap(fromKey);
+ return TreeMap.this.tailMap(fromKey, inclusive);
}
+ }
+
+ @Override
+ Iterator<Entry<K, V>> descendingEntryIterator() {
+ return new DescendingEntryIterator(type, fromKey, fromInclusive,
toKey,
+ toInclusive);
+ }
+
+ @Override
+ Iterator<Entry<K, V>> entryIterator() {
+ return new EntryIterator(type, fromKey, fromInclusive, toKey,
+ toInclusive);
+ }
+
+ boolean inRange(K key) {
+ if (type.toKeyValid()) {
+ int compare = cmp.compare(key, toKey);
+ if (toInclusive ? (compare > 0) : (compare >= 0)) {
+ return false;
+ }
+ }
+ if (type.fromKeyValid()) {
+ int compare = cmp.compare(key, fromKey);
+ if (fromInclusive ? (compare < 0) : (compare <= 0)) {
+ return false;
+ }
+ }
+ return true;
}
private Node<K, V> getFirstSubmapNode() {
Node<K, V> node;
if (type.fromKeyValid()) {
- node = getNodeAtOrAfter(fromKey);
+ node = getNodeAfter(fromKey, fromInclusive);
} else {
node = getFirstNode();
}
@@ -471,7 +654,7 @@
private Node<K, V> getLastSubmapNode() {
Node<K, V> node;
if (type.toKeyValid()) {
- node = getNodeBefore(toKey);
+ node = getNodeBefore(toKey, toInclusive);
} else {
node = getLastNode();
}
@@ -479,18 +662,8 @@
return node != null && inRange(node.getKey()) ? node : null;
}
- private boolean inRange(K key) {
- if (type.toKeyValid()) {
- if (cmp.compare(key, toKey) >= 0) {
- return false;
- }
- }
- if (type.fromKeyValid()) {
- if (cmp.compare(key, fromKey) < 0) {
- return false;
- }
- }
- return true;
+ private Entry<K, V> guardInRange(Entry<K, V> entry) {
+ return inRange(entry.getKey()) ? entry : null;
}
}
@@ -544,6 +717,7 @@
*/
@SuppressWarnings("unchecked")
private static Comparator<?> DEFAULT_COMPARATOR = new
Comparator<Comparable>() {
+ @Override
public int compare(Comparable a, Comparable b) {
// Explicit null check to match JRE specs
if (a == null || b == null) {
@@ -554,13 +728,13 @@
};
private static final int LEFT = 0;
+
private static final int RIGHT = 1;
private static int otherChild(int child) {
assert (child == 0 || child == 1);
return 1 - child;
}
-
/**
* Throw a NoSuchElementException if the specified node is null.
*
@@ -588,12 +762,12 @@
*/
@SuppressWarnings("unused")
private K exposeKeyType;
+
@SuppressWarnings("unused")
private V exposeValueType;
// The root of the tree.
private transient Node<K, V> root;
-
// The number of nodes in the tree.
private int size = 0;
@@ -622,11 +796,17 @@
}
@Override
+ public Entry<K, V> ceilingEntry(K key) {
+ return getNodeAfter(key, true);
+ }
+
+ @Override
public void clear() {
root = null;
size = 0;
}
+ @Override
public Comparator<? super K> comparator() {
if (cmp == DEFAULT_COMPARATOR) {
return null;
@@ -645,8 +825,19 @@
return new EntrySet();
}
+ @Override
+ public Entry<K, V> firstEntry() {
+ return getFirstNode();
+ }
+
+ @Override
public K firstKey() {
return throwNSE(getFirstNode()).key;
+ }
+
+ @Override
+ public Entry<K, V> floorEntry(K key) {
+ return getNodeBefore(key, true);
}
@SuppressWarnings("unchecked")
@@ -663,12 +854,29 @@
return entry != null ? entry.getValue() : null;
}
- public SortedMap<K, V> headMap(K toKey) {
- return new SubMap(SubMapType.Head, null, toKey);
+ @Override
+ public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
+ return new SubMap(SubMapType.Head, null, false, toKey, inclusive);
}
+ @Override
+ public Entry<K, V> higherEntry(K key) {
+ return getNodeAfter(key, false);
+ }
+
+ @Override
+ public Entry<K, V> lastEntry() {
+ return getLastNode();
+ }
+
+ @Override
public K lastKey() {
return throwNSE(getLastNode()).key;
+ }
+
+ @Override
+ public Entry<K, V> lowerEntry(K key) {
+ return getNodeBefore(key, false);
}
@Override
@@ -697,29 +905,32 @@
return size;
}
- public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
- return new SubMap(SubMapType.Range, fromKey, toKey);
+ @Override
+ public NavigableMap<K, V> subMap(
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+ return new SubMap(SubMapType.Range, fromKey, fromInclusive,
+ toKey, toInclusive);
}
- public SortedMap<K, V> tailMap(K fromKey) {
- return new SubMap(SubMapType.Tail, fromKey, null);
+ @Override
+ public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
+ return new SubMap(SubMapType.Tail, fromKey, inclusive, null, false);
}
/**
- * Returns the first node which compares equal to or greater than the
given
- * key.
+ * Returns the first node which compares greater than the given key.
*
* @param key the key to search for
* @return the next node, or null if there is none
*/
- protected Node<K, V> getNodeAtOrAfter(K key) {
+ protected Node<K, V> getNodeAfter(K key, boolean inclusive) {
Node<K, V> foundNode = null;
Node<K, V> node = root;
while (node != null) {
int c = cmp.compare(key, node.key);
- if (c == 0) {
+ if (inclusive && c == 0) {
return node;
- } else if (c > 0) {
+ } else if (c >= 0) {
node = node.child[RIGHT];
} else {
foundNode = node;
@@ -735,12 +946,14 @@
* @param key the key to search for
* @return the previous node, or null if there is none
*/
- protected Node<K, V> getNodeBefore(K key) {
+ protected Node<K, V> getNodeBefore(K key, boolean inclusive) {
Node<K, V> foundNode = null;
Node<K, V> node = root;
while (node != null) {
int c = cmp.compare(key, node.key);
- if (c <= 0) {
+ if (inclusive && c == 0) {
+ return node;
+ } else if (c <= 0) {
node = node.child[LEFT];
} else {
foundNode = node;
@@ -764,6 +977,16 @@
*/
void assertCorrectness() {
assertCorrectness(root, true);
+ }
+
+ @Override
+ Iterator<Entry<K, V>> descendingEntryIterator() {
+ return new DescendingEntryIterator();
+ }
+
+ @Override
+ Iterator<Entry<K, V>> entryIterator() {
+ return new EntryIterator();
}
/**
@@ -1061,5 +1284,4 @@
save.isRed = false;
return save;
}
-
}
diff --git a/user/super/com/google/gwt/emul/java/util/TreeSet.java
b/user/super/com/google/gwt/emul/java/util/TreeSet.java
index 1d1fedc..fe95b0a 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeSet.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeSet.java
@@ -1,12 +1,12 @@
/*
* Copyright 2008 Google Inc.
- *
+ *
* Licensed 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
@@ -21,15 +21,24 @@
* Implements a set using a TreeMap. <a
*
href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html";>[Sun
* docs]</a>
- *
+ *
* @param <E> element type.
*/
-public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>,
Serializable {
+public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>,
Serializable {
/**
* TreeSet is stored as a TreeMap of the requested type to a constant
Boolean.
*/
- private SortedMap<E, Boolean> map;
+ private NavigableMap<E, Boolean> map;
+
+ /**
+ * Used to wrap subset maps in a new TreeSet.
+ *
+ * @param map map to use for backing store
+ */
+ private TreeSet(NavigableMap<E, Boolean> map) {
+ this.map = map;
+ }
public TreeSet() {
map = new TreeMap<E, Boolean>();
@@ -54,19 +63,15 @@
addAll(s);
}
- /**
- * Used to wrap subset maps in a new TreeSet.
- *
- * @param map map to use for backing store
- */
- private TreeSet(SortedMap<E, Boolean> map) {
- this.map = map;
- }
-
@Override
public boolean add(E o) {
// Use Boolean.FALSE as a convenient non-null value to store in the map
return map.put(o, Boolean.FALSE) == null;
+ }
+
+ @Override
+ public E ceiling(E e) {
+ return map.ceilingKey(e);
}
@Override
@@ -83,12 +88,36 @@
return map.containsKey(o);
}
+ @Override
+ public Iterator<E> descendingIterator() {
+ return map.descendingKeySet().iterator();
+ }
+
+ @Override
+ public NavigableSet<E> descendingSet() {
+ return new TreeSet<E>(map.descendingMap());
+ }
+
public E first() {
return map.firstKey();
}
+ @Override
+ public E floor(E e) {
+ return map.floorKey(e);
+ }
+
public SortedSet<E> headSet(E toElement) {
- return new TreeSet<E>(map.headMap(toElement));
+ return headSet(toElement, false);
+ }
+
+ public NavigableSet<E> headSet(E toElement, boolean inclusive) {
+ return new TreeSet<E>(map.headMap(toElement, inclusive));
+ }
+
+ @Override
+ public E higher(E e) {
+ return map.higherKey(e);
}
@Override
@@ -101,6 +130,23 @@
}
@Override
+ public E lower(E e) {
+ return map.lowerKey(e);
+ }
+
+ @Override
+ public E pollFirst() {
+ Map.Entry<E, Boolean> entry = map.pollFirstEntry();
+ return (entry == null) ? null : entry.getKey();
+ }
+
+ @Override
+ public E pollLast() {
+ Map.Entry<E, Boolean> entry = map.pollLastEntry();
+ return (entry == null) ? null : entry.getKey();
+ }
+
+ @Override
public boolean remove(Object o) {
return map.remove(o) != null;
}
@@ -110,11 +156,21 @@
return map.size();
}
+ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
+ E toElement, boolean toInclusive) {
+ return new TreeSet<E>(map.subMap(
+ fromElement, fromInclusive, toElement, toInclusive));
+ }
+
public SortedSet<E> subSet(E fromElement, E toElement) {
- return new TreeSet<E>(map.subMap(fromElement, toElement));
+ return subSet(fromElement, true, toElement, false);
}
public SortedSet<E> tailSet(E fromElement) {
- return new TreeSet<E>(map.tailMap(fromElement));
+ return tailSet(fromElement, true);
+ }
+
+ public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
+ return new TreeSet<E>(map.tailMap(fromElement, inclusive));
}
}
--
To view, visit https://gwt-review.googlesource.com/3650
To unsubscribe, visit https://gwt-review.googlesource.com/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I2800b2b54b06a7ef255e01ad44b11909d878362a
Gerrit-PatchSet: 1
Gerrit-Project: gwt
Gerrit-Branch: master
Gerrit-Owner: Thomas Broyer <[email protected]>
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
---
You received this message because you are subscribed to the Google Groups "GWT Contributors" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
