You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by gh...@apache.org on 2006/06/28 12:56:44 UTC
svn commit: r417719 - in
/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util:
TreeMap.java TreeSet.java
Author: gharley
Date: Wed Jun 28 03:56:43 2006
New Revision: 417719
URL: http://svn.apache.org/viewvc?rev=417719&view=rev
Log:
HARMONY 684 : performance improvement for TreeMap and TreeSet classes
Modified:
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java
Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java?rev=417719&r1=417718&r2=417719&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java Wed Jun 28 03:56:43 2006
@@ -41,6 +41,8 @@
transient int modCount = 0;
+ Set<Map.Entry<K,V>> entrySet = null;
+
/**
* Entry is an internal class which is used to hold the entries of a
* TreeMap.
@@ -77,406 +79,541 @@
return (Comparable<T>)obj;
}
- private static final class TreeMapIterator<E, K, V> implements Iterator<E> {
- private final TreeMap<K, V> backingMap;
+ private static class AbstractMapIterator <K,V> {
+ TreeMap<K, V> backingMap;
+ int expectedModCount;
+ TreeMap.Entry<K, V> node;
+ TreeMap.Entry<K, V> lastNode;
- private int expectedModCount;
+ AbstractMapIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
+ backingMap = map;
+ expectedModCount = map.modCount;
+ node = startNode;
+ }
- private final MapEntry.Type<E, K, V> type;
+ public boolean hasNext() {
+ return node != null;
+ }
- private boolean hasEnd = false;
+ final public void remove() {
+ if (expectedModCount == backingMap.modCount) {
+ if (lastNode != null) {
+ backingMap.rbDelete(lastNode);
+ lastNode = null;
+ expectedModCount++;
+ } else {
+ throw new IllegalStateException();
+ }
+ } else {
+ throw new ConcurrentModificationException();
+ }
+ }
- private Entry<K, V> node, lastNode;
+ final void makeNext() {
+ if (expectedModCount != backingMap.modCount) {
+ throw new ConcurrentModificationException();
+ } else if (node == null) {
+ throw new NoSuchElementException();
+ }
+ lastNode = node;
+ node = TreeMap.successor(node);
+ }
+ }
- private K endKey;
+ private static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
- TreeMapIterator(TreeMap<K, V> map, MapEntry.Type<E, K, V> value) {
- backingMap = map;
- type = value;
- expectedModCount = map.modCount;
- if (map.root != null) {
- node = TreeMap.minimum(map.root);
+ UnboundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
+ super(map, startNode);
}
- }
- TreeMapIterator(TreeMap<K, V> map, MapEntry.Type<E, K, V> value, Entry<K, V> startNode,
- boolean checkEnd, K end) {
- backingMap = map;
- type = value;
- expectedModCount = map.modCount;
- node = startNode;
- hasEnd = checkEnd;
- endKey = end;
- }
+ UnboundedEntryIterator(TreeMap<K, V> map) {
+ super(map, map.root == null ? null : TreeMap.minimum(map.root));
+ }
- public boolean hasNext() {
- return node != null;
- }
+ public Map.Entry<K, V> next() {
+ makeNext();
+ return lastNode;
+ }
+ }
- public E next() {
- if (expectedModCount == backingMap.modCount) {
- if (node != null) {
- lastNode = node;
- node = TreeMap.successor(node);
- if (hasEnd && node != null) {
- Comparator<? super K> c = backingMap.comparator();
- if (c == null) {
- Comparable<K> cEndKey = toComparable(endKey);
- if (cEndKey.compareTo(node.key) <= 0) {
- node = null;
- }
- } else {
- if (c.compare(endKey, node.key) <= 0) {
- node = null;
- }
- }
- }
- return type.get(lastNode);
- } else {
- throw new NoSuchElementException();
+ static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<K> {
+ public UnboundedKeyIterator(TreeMap<K, V> treeMap, Entry<K, V> entry) {
+ super(treeMap, entry);
+ }
+
+ public UnboundedKeyIterator(TreeMap<K, V> map) {
+ super(map, map.root == null ? null : TreeMap.minimum(map.root));
+ }
+
+ public K next() {
+ makeNext();
+ return lastNode.key;
+ }
+ }
+
+ static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<V> {
+
+ public UnboundedValueIterator(TreeMap<K, V> treeMap, Entry<K, V> startNode) {
+ super(treeMap, startNode);
+ }
+
+ public UnboundedValueIterator(TreeMap<K, V> map) {
+ super(map, map.root == null ? null : TreeMap.minimum(map.root));
+ }
+
+ public V next() {
+ makeNext();
+ return lastNode.value;
+ }
+ }
+
+ private static class ComparatorBoundedIterator <K, V> extends AbstractMapIterator<K, V> {
+ private K endKey;
+ private Comparator<? super K> cmp;
+
+ ComparatorBoundedIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, K end) {
+ super(map, startNode);
+ endKey = end;
+ cmp = map.comparator();
+ }
+
+ final void cleanNext() {
+ if (node != null && cmp.compare(endKey, node.key) <= 0) {
+ node = null;
}
- } else {
- throw new ConcurrentModificationException();
}
- }
+ }
- public void remove() {
- if (expectedModCount == backingMap.modCount) {
- if (lastNode != null) {
- backingMap.rbDelete(lastNode);
- lastNode = null;
- expectedModCount++;
- } else {
- throw new IllegalStateException();
+ private static class ComparatorBoundedEntryIterator <K, V> extends ComparatorBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
+
+ ComparatorBoundedEntryIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, K end) {
+ super(map, startNode,end);
+ }
+
+ public Map.Entry<K, V> next() {
+ makeNext();
+ cleanNext();
+ return lastNode;
+ }
+ }
+
+ private static class ComparatorBoundedKeyIterator <K, V> extends ComparatorBoundedIterator<K, V> implements Iterator<K> {
+
+ ComparatorBoundedKeyIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, K end) {
+ super(map, startNode,end);
+ }
+
+ public K next() {
+ makeNext();
+ cleanNext();
+ return lastNode.key;
+ }
+ }
+
+
+ private static class ComparatorBoundedValueIterator <K, V> extends ComparatorBoundedIterator<K, V> implements Iterator<V> {
+
+ ComparatorBoundedValueIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, K end) {
+ super(map, startNode,end);
+ }
+
+ public V next() {
+ makeNext();
+ cleanNext();
+ return lastNode.value;
+ }
+ }
+
+ private static class ComparableBoundedIterator <K, V> extends AbstractMapIterator<K, V> {
+ final private Comparable endKey;
+
+ public ComparableBoundedIterator(TreeMap<K, V> treeMap, Entry<K, V> entry, Comparable endKey) {
+ super(treeMap, entry);
+ this.endKey = endKey;
+ }
+
+ final void cleanNext() {
+ if ((node != null) && (endKey.compareTo(node.key) <= 0)) {
+ node = null;
}
- } else {
- throw new ConcurrentModificationException();
}
- }
- }
+ }
- static final class SubMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V> {
- private final TreeMap<K, V> backingMap;
+ private static class ComparableBoundedEntryIterator <K, V> extends ComparableBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
- private boolean hasStart, hasEnd;
- private K startKey, endKey;
+ ComparableBoundedEntryIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, Comparable end) {
+ super(map, startNode, end);
+ }
- static class SubMapSet<E, K, V> extends AbstractSet<E> implements Set<E> {
- final TreeMap<K, V> backingMap;
+ public Map.Entry<K, V> next() {
+ makeNext();
+ cleanNext();
+ return lastNode;
+ }
- boolean hasStart, hasEnd;
+ }
- K startKey, endKey;
+ private static class ComparableBoundedKeyIterator <K, V> extends ComparableBoundedIterator<K, V> implements Iterator<K> {
- final MapEntry.Type<E, K, V> type;
+ ComparableBoundedKeyIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, Comparable end) {
+ super(map, startNode,end);
+ }
- SubMapSet(TreeMap<K, V> map, MapEntry.Type<E, K, V> theType) {
- backingMap = map;
- type = theType;
- }
+ public K next() {
+ makeNext();
+ cleanNext();
+ return lastNode.key;
+ }
+ }
- SubMapSet(boolean starting, K start, TreeMap<K, V> map,
- boolean ending, K end, MapEntry.Type<E, K, V> theType) {
- this(map, theType);
- hasStart = starting;
- startKey = start;
- hasEnd = ending;
- endKey = end;
- }
+ private static class ComparableBoundedValueIterator <K, V> extends ComparableBoundedIterator<K, V> implements Iterator<V> {
+
+ ComparableBoundedValueIterator(TreeMap<K, V> map,
+ Entry<K, V> startNode, Comparable end) {
+ super(map, startNode,end);
+ }
+
+ public V next() {
+ makeNext();
+ cleanNext();
+ return lastNode.value;
+ }
+ }
+
+ static final class SubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V> {
+ private TreeMap<K,V> backingMap;
+
+ boolean hasStart, hasEnd;
+
+ K startKey, endKey;
+
+ Set<Map.Entry<K,V>> entrySet = null;
+
+ SubMap(K start, TreeMap<K,V> map) {
+ backingMap = map;
+ hasStart = true;
+ startKey = start;
+ }
+
+ SubMap(K start, TreeMap<K,V> map, K end) {
+ backingMap = map;
+ hasStart = hasEnd = true;
+ startKey = start;
+ endKey = end;
+ }
+
+ SubMap(TreeMap<K,V> map, K end) {
+ backingMap = map;
+ hasEnd = true;
+ endKey = end;
+ }
- void checkRange(K key) {
- if (backingMap.comparator() == null) {
- Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
+ private void checkRange(K key) {
+ Comparator cmp = backingMap.comparator;
+ if (cmp == null) {
+ Comparable<K> object = (Comparable<K>) key;
+ if (hasStart && object.compareTo(startKey) < 0)
throw new IllegalArgumentException();
- }
- if (hasEnd && object.compareTo(endKey) >= 0) {
+ if (hasEnd && object.compareTo(endKey) >= 0)
throw new IllegalArgumentException();
- }
- } else {
- if (hasStart
- && backingMap.comparator().compare(key, startKey) < 0) {
+ } else {
+ if (hasStart
+ && backingMap.comparator().compare(key, startKey) < 0)
throw new IllegalArgumentException();
- }
- if (hasEnd
- && backingMap.comparator().compare(key, endKey) >= 0) {
+ if (hasEnd && backingMap.comparator().compare(key, endKey) >= 0)
throw new IllegalArgumentException();
- }
- }
- }
+ }
+ }
- boolean checkRange(K key, boolean hasStart, boolean hasEnd) {
- if (backingMap.comparator() == null) {
+ private boolean isInRange(K key) {
+ Comparator<? super K> cmp = backingMap.comparator;
+ if (cmp == null) {
Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
+ if (hasStart && object.compareTo(startKey) < 0)
return false;
- }
- if (hasEnd && object.compareTo(endKey) >= 0) {
+ if (hasEnd && object.compareTo(endKey) >= 0)
return false;
- }
- } else {
- if (hasStart
- && backingMap.comparator().compare(key, startKey) < 0) {
+ } else {
+ if (hasStart && cmp.compare(key, startKey) < 0)
return false;
- }
- if (hasEnd
- && backingMap.comparator().compare(key, endKey) >= 0) {
- return false;
- }
- }
- return true;
- }
-
- @Override
- public boolean isEmpty() {
- if (hasStart) {
- TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
- return node == null || !checkRange(node.key, false, hasEnd);
- }
- return backingMap.findBefore(endKey) == null;
- }
+ if (hasEnd && cmp.compare(key, endKey) >= 0)
+ return false;
+ }
+ return true;
+ }
- @Override
- public Iterator<E> iterator() {
- TreeMap.Entry<K, V> startNode;
- if (hasStart) {
- startNode = backingMap.findAfter(startKey);
- if (startNode != null
- && !checkRange(startNode.key, false, hasEnd)) {
- startNode = null;
- }
- } else {
- startNode = backingMap.findBefore(endKey);
- if (startNode != null) {
- startNode = minimum(backingMap.root);
+ private boolean checkUpperBound(K key) {
+ if (hasEnd) {
+ Comparator<? super K> cmp = backingMap.comparator;
+ if (cmp == null) {
+ return (((Comparable<K>) key).compareTo(endKey) < 0);
+ } else {
+ return (cmp.compare(key, endKey) < 0);
}
- }
- return new TreeMapIterator<E, K, V>(backingMap, type, startNode, hasEnd,
- endKey);
- }
+ } else {
+ return true;
+ }
+ }
- @Override
- public int size() {
- int size = 0;
- Iterator<E> it = iterator();
- while (it.hasNext()) {
- size++;
- it.next();
- }
- return size;
- }
- }
+ private boolean checkLowerBound(K key) {
+ if (hasStart) {
+ Comparator<? super K> cmp = backingMap.comparator;
+ if (cmp == null) {
+ return (((Comparable<K>) key).compareTo(endKey) >= 0);
+ } else {
+ return (cmp.compare(key, endKey) >= 0);
+ }
+ } else {
+ return true;
+ }
+ }
- SubMap(K start, TreeMap<K, V> map, K end) {
- backingMap = map;
- hasStart = hasEnd = true;
- startKey = start;
- endKey = end;
- }
-
- SubMap(K start, TreeMap<K, V> map) {
- backingMap = map;
- hasStart = true;
- startKey = start;
- }
+ public Comparator<? super K> comparator() {
+ return backingMap.comparator();
+ }
- SubMap(TreeMap<K, V> map, K end) {
- backingMap = map;
- hasEnd = true;
- endKey = end;
- }
+ public boolean containsKey(Object key) {
+ if (isInRange((K)key))
+ return backingMap.containsKey(key);
+ return false;
+ }
- private void checkRange(K key) {
- if (backingMap.comparator() == null) {
- Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
- throw new IllegalArgumentException();
+ public Set<Map.Entry<K,V>> entrySet() {
+ if(entrySet==null) {
+ entrySet = new SubMapEntrySet<K,V>(this);
}
- if (hasEnd && object.compareTo(endKey) >= 0) {
- throw new IllegalArgumentException();
+ return entrySet;
+ }
+
+ public K firstKey() {
+ TreeMap.Entry<K,V> node = firstEntry();
+ if (node != null ) {
+ return node.key;
}
- } else {
- if (hasStart
- && backingMap.comparator().compare(key, startKey) < 0) {
- throw new IllegalArgumentException();
+ throw new NoSuchElementException();
+ }
+
+ TreeMap.Entry<K,V> firstEntry() {
+ if (!hasStart) {
+ TreeMap.Entry<K,V> root = backingMap.root;
+ return (root == null) ? null : minimum(backingMap.root);
}
- if (hasEnd && backingMap.comparator().compare(key, endKey) >= 0) {
- throw new IllegalArgumentException();
+ TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
+ if (node != null && checkUpperBound(node.key)) {
+ return node;
+ } else {
+ return null;
}
- }
- }
+ }
- @SuppressWarnings("unchecked")
- private boolean checkRange(Object keyObj, boolean hasStart, boolean hasEnd) {
- K key = (K)keyObj;
- if (backingMap.comparator() == null) {
- Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
- return false;
+ public V get(Object key) {
+ if (isInRange((K)key))
+ return backingMap.get(key);
+ return null;
+ }
+
+ public SortedMap<K,V> headMap(K endKey) {
+ checkRange(endKey);
+ if (hasStart)
+ return new SubMap<K,V>(startKey, backingMap, endKey);
+ return new SubMap<K,V>(backingMap, endKey);
+ }
+
+ public boolean isEmpty() {
+ if (hasStart) {
+ TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
+ return node == null || !checkUpperBound(node.key);
}
- if (hasEnd && object.compareTo(endKey) >= 0) {
- return false;
+ return backingMap.findBefore(endKey) == null;
+ }
+
+ public Set<K> keySet() {
+ if (keySet == null) {
+ keySet = new SubMapKeySet<K,V>(this);
}
- } else {
- if (hasStart
- && backingMap.comparator().compare(key, startKey) < 0) {
- return false;
+ return keySet;
+ }
+
+ public K lastKey() {
+ if (!hasEnd)
+ return backingMap.lastKey();
+ TreeMap.Entry<K,V> node = backingMap.findBefore(endKey);
+ if (node != null && checkLowerBound(node.key))
+ return node.key;
+ throw new NoSuchElementException();
+ }
+
+ public V put(K key, V value) {
+ if (isInRange(key))
+ return backingMap.put(key, value);
+ throw new IllegalArgumentException();
+ }
+
+ public V remove(Object key) {
+ if (isInRange((K)key))
+ return backingMap.remove(key);
+ return null;
+ }
+
+ public SortedMap<K,V> subMap(K startKey, K endKey) {
+ checkRange(startKey);
+ checkRange(endKey);
+ Comparator c = backingMap.comparator();
+ if (c == null) {
+ if (((Comparable) startKey).compareTo(endKey) <= 0)
+ return new SubMap<K,V>(startKey, backingMap, endKey);
+ } else {
+ if (c.compare(startKey, endKey) <= 0)
+ return new SubMap<K,V>(startKey, backingMap, endKey);
}
- if (hasEnd && backingMap.comparator().compare(key, endKey) >= 0) {
- return false;
+ throw new IllegalArgumentException();
+ }
+
+ public SortedMap<K,V> tailMap(K startKey) {
+ checkRange(startKey);
+ if (hasEnd)
+ return new SubMap<K,V>(startKey, backingMap, endKey);
+ return new SubMap<K,V>(startKey, backingMap);
+ }
+
+ public Collection<V> values() {
+ if(valuesCollection==null) {
+ valuesCollection = new SubMapValuesCollection<K,V>(this);
}
- }
- return true;
- }
+ return valuesCollection;
+ }
+ }
- public Comparator<? super K> comparator() {
- return backingMap.comparator();
- }
+ static class SubMapEntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> implements Set<Map.Entry<K,V>> {
+ SubMap<K,V> subMap;
- @Override
- public boolean containsKey(Object key) {
- if (checkRange(key, hasStart, hasEnd)) {
- return backingMap.containsKey(key);
+ SubMapEntrySet(SubMap<K,V> map) {
+ subMap = map;
}
- return false;
- }
- @Override
- public Set<Map.Entry<K, V>> entrySet() {
- return new SubMapSet<Map.Entry<K, V>, K, V>(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type<Map.Entry<K, V>, K, V>() {
- public Map.Entry<K, V> get(MapEntry<K, V> entry) {
- return entry;
- }
- }) {
- @Override
- public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
- Object v1 = get(entry.getKey()), v2 = entry.getValue();
- return v1 == null ? v2 == null : v1.equals(v2);
- }
- return false;
- }
- };
- }
+ public boolean isEmpty() {
+ return subMap.isEmpty();
+ }
- public K firstKey() {
- if (!hasStart) {
- return backingMap.firstKey();
- }
- TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
- if (node != null && checkRange(node.key, false, hasEnd)) {
- return node.key;
+ public Iterator<Map.Entry<K,V>> iterator() {
+ TreeMap.Entry<K,V> startNode = subMap.firstEntry();
+ if (subMap.hasEnd) {
+ Comparator<? super K> cmp = subMap.comparator();
+ if (cmp == null) {
+ return new ComparableBoundedEntryIterator<K,V>(subMap.backingMap, startNode, (Comparable<K>) subMap.endKey);
+ } else {
+ return new ComparatorBoundedEntryIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
+ }
+ } else {
+ return new UnboundedEntryIterator<K,V>(subMap.backingMap, startNode);
+ }
}
- throw new NoSuchElementException();
- }
- @Override
- public V get(Object key) {
- if (checkRange(key, hasStart, hasEnd)) {
- return backingMap.get(key);
+ public int size() {
+ int size = 0;
+ Iterator<Map.Entry<K,V>> it = iterator();
+ while (it.hasNext()) {
+ size++;
+ it.next();
+ }
+ return size;
}
- return null;
- }
- public SortedMap<K, V> headMap(K endKey) {
- checkRange(endKey);
- if (hasStart) {
- return new SubMap<K, V>(startKey, backingMap, endKey);
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Map.Entry<K,V> entry = (Map.Entry<K,V>) object;
+ K key = entry.getKey();
+ if (subMap.isInRange(key)) {
+ V v1 = subMap.get(key), v2 = entry.getValue();
+ return v1 == null ? v2 == null : v1.equals(v2);
+ }
+ }
+ return false;
}
- return new SubMap<K, V>(backingMap, endKey);
- }
- @Override
- public boolean isEmpty() {
- if (hasStart) {
- TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
- return node == null || !checkRange(node.key, false, hasEnd);
- }
- return backingMap.findBefore(endKey) == null;
- }
+ }
- @Override
- public Set<K> keySet() {
- if (keySet == null) {
- keySet = new SubMapSet<K, K, V>(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type<K, K, V>() {
- public K get(MapEntry<K, V> entry) {
- return entry.key;
- }
- }) {
- @Override
- public boolean contains(Object object) {
- return containsKey(object);
- }
- };
- }
- return keySet;
- }
+ static class SubMapKeySet<K,V> extends AbstractSet<K> implements Set<K> {
+ SubMap<K,V> subMap;
- public K lastKey() {
- if (!hasEnd) {
- return backingMap.lastKey();
- }
- TreeMap.Entry<K, V> node = backingMap.findBefore(endKey);
- if (node != null && checkRange(node.key, hasStart, false)) {
- return node.key;
+ SubMapKeySet(SubMap<K,V> map) {
+ subMap = map;
}
- throw new NoSuchElementException();
- }
- @Override
- public V put(K key, V value) {
- if (checkRange(key, hasStart, hasEnd)) {
- return backingMap.put(key, value);
+ public boolean contains(Object object) {
+ return subMap.containsKey(object);
}
- throw new IllegalArgumentException();
- }
- @Override
- public V remove(Object key) {
- if (checkRange(key, hasStart, hasEnd)) {
- return backingMap.remove(key);
+ public boolean isEmpty() {
+ return subMap.isEmpty();
}
- return null;
- }
- public SortedMap<K, V> subMap(K startKey, K endKey) {
- checkRange(startKey);
- checkRange(endKey);
- Comparator<? super K> c = backingMap.comparator();
- if (c == null) {
- if (toComparable(startKey).compareTo(endKey) <= 0) {
- return new SubMap<K, V>(startKey, backingMap, endKey);
+ public int size() {
+ int size = 0;
+ Iterator<K> it = iterator();
+ while (it.hasNext()) {
+ size++;
+ it.next();
}
- } else {
- if (c.compare(startKey, endKey) <= 0) {
- return new SubMap<K, V>(startKey, backingMap, endKey);
+ return size;
+ }
+
+ public Iterator<K> iterator() {
+ TreeMap.Entry<K,V> startNode = subMap.firstEntry();
+ if (subMap.hasEnd) {
+ Comparator<? super K> cmp = subMap.comparator();
+ if (cmp == null) {
+ return new ComparableBoundedKeyIterator<K,V>(subMap.backingMap, startNode, (Comparable<K>) subMap.endKey);
+ } else {
+ return new ComparatorBoundedKeyIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
+ }
+ } else {
+ return new UnboundedKeyIterator<K,V>(subMap.backingMap, startNode);
}
- }
- throw new IllegalArgumentException();
- }
+ }
+ }
- public SortedMap<K, V> tailMap(K startKey) {
- checkRange(startKey);
- if (hasEnd) {
- return new SubMap<K, V>(startKey, backingMap, endKey);
+ static class SubMapValuesCollection<K,V> extends AbstractCollection<V> {
+ SubMap<K,V> subMap;
+
+ public SubMapValuesCollection(SubMap<K,V> subMap) {
+ this.subMap = subMap;
}
- return new SubMap<K, V>(startKey, backingMap);
- }
- @Override
- public Collection<V> values() {
- return new SubMapSet<V, K, V>(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type<V, K, V>() {
- public V get(MapEntry<K, V> entry) {
- return entry.value;
- }
- });
- }
- }
+ public boolean isEmpty() {
+ return subMap.isEmpty();
+ }
+
+ public Iterator<V> iterator() {
+ TreeMap.Entry<K,V> startNode = subMap.firstEntry();
+ if (subMap.hasEnd) {
+ Comparator<? super K> cmp = subMap.comparator();
+ if (cmp == null) {
+ return new ComparableBoundedValueIterator<K,V>(subMap.backingMap, startNode, (Comparable<K>) subMap.endKey);
+ } else {
+ return new ComparatorBoundedValueIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
+ }
+ } else {
+ return new UnboundedValueIterator<K,V>(subMap.backingMap, startNode);
+ }
+ }
+
+ public int size() {
+ int cnt = 0;
+ for (Iterator<V> it = iterator(); it.hasNext();) {
+ it.next();
+ cnt++;
+ }
+ return cnt;
+ }
+ }
/**
* Constructs a new empty instance of TreeMap.
@@ -607,6 +744,7 @@
public Object clone() {
try {
TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
+ clone.entrySet = null;
if (root != null) {
clone.root = root.clone(null);
}
@@ -686,37 +824,36 @@
*/
@Override
public Set<Map.Entry<K, V>> entrySet() {
- return new AbstractSet<Map.Entry<K, V>>() {
- @Override
- public int size() {
- return size;
- }
+ if (entrySet == null) {
+ entrySet = new AbstractSet<Map.Entry<K, V>>() {
+ @Override
+ public int size() {
+ return size;
+ }
- @Override
- public void clear() {
- TreeMap.this.clear();
- }
+ @Override
+ public void clear() {
+ TreeMap.this.clear();
+ }
- @Override
- public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
- Object v1 = get(entry.getKey()), v2 = entry.getValue();
- return v1 == null ? v2 == null : v1.equals(v2);
- }
- return false;
- }
+ @Override
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
+ Object v1 = get(entry.getKey()), v2 = entry.getValue();
+ return v1 == null ? v2 == null : v1.equals(v2);
+ }
+ return false;
+ }
- @Override
- public Iterator<Map.Entry<K, V>> iterator() {
- return new TreeMapIterator<Map.Entry<K, V>, K, V>(TreeMap.this, new MapEntry.Type<Map.Entry<K, V>, K, V>() {
- public Map.Entry<K, V> get(MapEntry<K, V> entry) {
- return entry;
- }
- });
- }
- };
- }
+ @Override
+ public Iterator<Map.Entry<K, V>> iterator() {
+ return new UnboundedEntryIterator<K, V>(TreeMap.this);
+ }
+ };
+ }
+ return entrySet;
+ }
@SuppressWarnings("unchecked")
private Entry<K, V> find(Object keyObj) {
@@ -948,12 +1085,7 @@
@Override
public Iterator<K> iterator() {
- return new TreeMapIterator<K, K, V>(TreeMap.this,
- new MapEntry.Type<K, K, V>() {
- public K get(MapEntry<K, V> entry) {
- return entry.key;
- }
- });
+ return new UnboundedKeyIterator<K,V> (TreeMap.this);
}
};
}
@@ -1279,12 +1411,7 @@
@Override
public Iterator<V> iterator() {
- return new TreeMapIterator<V, K, V>(TreeMap.this,
- new MapEntry.Type<V, K, V>() {
- public V get(MapEntry<K, V> entry) {
- return entry.value;
- }
- });
+ return new UnboundedValueIterator<K,V> (TreeMap.this);
}
};
}
Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java?rev=417719&r1=417718&r2=417719&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java Wed Jun 28 03:56:43 2006
@@ -33,104 +33,11 @@
private static final long serialVersionUID = -2479143000061671589L;
- private transient TreeMap<E, E> backingMap;
+ private transient SortedMap<E, E> backingMap;
- private static final class SubSet<E> extends TreeMap.SubMap.SubMapSet<E, E, E>
- implements SortedSet<E> {
- private SubSet(TreeMap<E, E> map) {
- super(map, new MapEntry.Type<E, E, E>() {
- public E get(MapEntry<E, E> entry) {
- return entry.key;
- }
- });
- }
-
- private SubSet(E start, TreeMap<E, E> map) {
- this(map);
- hasStart = true;
- startKey = start;
- }
-
- private SubSet(E start, TreeMap<E, E> map, E end) {
- this(map);
- hasStart = hasEnd = true;
- startKey = start;
- endKey = end;
- }
-
- private SubSet(TreeMap<E, E> map, E end) {
- this(map);
- hasEnd = true;
- endKey = end;
- }
-
- public boolean add(E object) {
- checkRange(object);
- return this.backingMap.put(object, object) != null;
- }
-
- public Comparator<? super E> comparator() {
- return this.backingMap.comparator();
- }
-
- public boolean contains(Object object) {
- if (checkRange((E)object, hasStart, hasEnd))
- return this.backingMap.containsKey(object);
- return false;
- }
-
- public E first() {
- if (!hasStart)
- return this.backingMap.firstKey();
- TreeMap.Entry<E, E> node = this.backingMap.findAfter(startKey);
- if (node != null && checkRange(node.key, false, hasEnd))
- return node.key;
- throw new NoSuchElementException();
- }
-
- public SortedSet<E> headSet(E end) {
- checkRange(end);
- if (hasStart)
- return new SubSet<E>(startKey, this.backingMap, end);
- return new SubSet<E>(this.backingMap, end);
- }
-
- public E last() {
- if (!hasEnd)
- return this.backingMap.lastKey();
- TreeMap.Entry<E, E> node = this.backingMap.findBefore(endKey);
- if (node != null && checkRange(node.key, hasStart, false))
- return node.key;
- throw new NoSuchElementException();
- }
-
- public boolean remove(Object object) {
- if (checkRange((E)object, hasStart, hasEnd))
- return this.backingMap.remove(object) != null;
- return false;
- }
-
- public SortedSet<E> subSet(E start, E end) {
- checkRange(start);
- checkRange(end);
- Comparator<? super E> c = this.backingMap.comparator();
- if (c == null) {
- if (((Comparable<E>) startKey).compareTo(endKey) <= 0)
- return new SubSet<E>(start, this.backingMap, end);
- } else {
- if (c.compare(startKey, endKey) <= 0)
- return new SubSet<E>(start, this.backingMap, end);
- }
- throw new IllegalArgumentException();
- }
-
- public SortedSet<E> tailSet(E start) {
- checkRange(start);
- if (hasEnd)
- return new SubSet<E>(start, this.backingMap, endKey);
- return new SubSet<E>(start, this.backingMap);
- }
- }
+ private TreeSet(SortedMap<E,E> map) {
+ this.backingMap = map;
+ }
/**
* Constructs a new empty instance of TreeSet which uses natural ordering.
@@ -178,21 +85,9 @@
public TreeSet(SortedSet<E> set) {
this(set.comparator());
Iterator<E> it = set.iterator();
- if (it.hasNext()) {
- E object = it.next();
- TreeMap.Entry<E, E> last = new TreeMap.Entry<E, E>(object, object);
- backingMap.root = last;
- backingMap.size = 1;
- while (it.hasNext()) {
- object = it.next();
- TreeMap.Entry<E, E> x = new TreeMap.Entry<E, E>(object, object);
- x.parent = last;
- last.right = x;
- backingMap.size++;
- backingMap.balance(x);
- last = x;
- }
- }
+ while (it.hasNext()) {
+ add(it.next());
+ }
}
/**
@@ -253,7 +148,11 @@
public Object clone() {
try {
TreeSet<E> clone = (TreeSet<E>) super.clone();
- clone.backingMap = (TreeMap<E, E>) backingMap.clone();
+ if (backingMap instanceof TreeMap) {
+ clone.backingMap = (SortedMap<E,E>) ((TreeMap<E,E>) backingMap).clone();
+ } else {
+ clone.backingMap = new TreeMap<E,E>(backingMap);
+ }
return clone;
} catch (CloneNotSupportedException e) {
return null;
@@ -323,7 +222,7 @@
((Comparable<E>) end).compareTo(end);
else
c.compare(end, end);
- return new SubSet<E>(backingMap, end);
+ return new TreeSet<E>(backingMap.headMap(end));
}
/**
@@ -411,10 +310,10 @@
Comparator<? super E> c = backingMap.comparator();
if (c == null) {
if (((Comparable<E>) start).compareTo(end) <= 0)
- return new SubSet<E>(start, backingMap, end);
+ return new TreeSet<E>(backingMap.subMap(start, end));
} else {
if (c.compare(start, end) <= 0)
- return new SubSet<E>(start, backingMap, end);
+ return new TreeSet<E>(backingMap.subMap(start, end));
}
throw new IllegalArgumentException();
}
@@ -444,39 +343,42 @@
((Comparable<E>) start).compareTo(start);
else
c.compare(start, start);
- return new SubSet<E>(start, backingMap);
+ return new TreeSet<E>(backingMap.tailMap(start));
}
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeObject(backingMap.comparator());
- stream.writeInt(backingMap.size);
- if (backingMap.size > 0) {
- TreeMap.Entry<E, E> node = TreeMap.minimum(backingMap.root);
- while (node != null) {
- stream.writeObject(node.key);
- node = TreeMap.successor(node);
- }
+ int size = backingMap.size();
+ stream.writeInt(size);
+ if (size > 0) {
+ Iterator<E> it = backingMap.keySet().iterator();
+ while (it.hasNext()) {
+ stream.writeObject(it.next());
+ }
}
}
private void readObject(ObjectInputStream stream) throws IOException,
ClassNotFoundException {
stream.defaultReadObject();
- backingMap = new TreeMap<E, E>((Comparator<? super E>) stream.readObject());
- backingMap.size = stream.readInt();
- TreeMap.Entry<E, E> last = null;
- for (int i = backingMap.size; --i >= 0;) {
- TreeMap.Entry<E, E> node = new TreeMap.Entry<E, E>((E)stream.readObject());
- node.value = node.key;
- if (last == null)
- backingMap.root = node;
- else {
- node.parent = last;
- last.right = node;
- backingMap.balance(node);
- }
- last = node;
- }
+ TreeMap<E, E> map = new TreeMap<E, E>((Comparator<? super E>) stream.readObject());
+ int size = stream.readInt();
+ if (size > 0) {
+ E key = (E)stream.readObject();
+ TreeMap.Entry<E,E> last = new TreeMap.Entry<E,E>(key,key);
+ map.root = last;
+ map.size = 1;
+ for (int i=1; i<size; i++) {
+ key = (E)stream.readObject();
+ TreeMap.Entry<E,E> x = new TreeMap.Entry<E,E>(key,key);
+ x.parent = last;
+ last.right = x;
+ map.size++;
+ map.balance(x);
+ last = x;
+ }
+ }
+ backingMap = map;
}
}