You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ml...@apache.org on 2006/06/05 08:39:37 UTC
svn commit: r411690 - in
/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util:
TreeMap.java TreeSet.java
Author: mloenko
Date: Sun Jun 4 23:39:37 2006
New Revision: 411690
URL: http://svn.apache.org/viewvc?rev=411690&view=rev
Log:
improvement from HARMONY-556
[classlib][luni] TreeMap and TreeSet generification
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=411690&r1=411689&r2=411690&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 Sun Jun 4 23:39:37 2006
@@ -26,18 +26,18 @@
* supported, adding and removing. The values can be any objects. The keys can
* be any objects which are comparable to each other either using their natural
* order or a specified Comparator.
- *
+ * @since 1.2
*/
-public class TreeMap extends AbstractMap implements SortedMap, Cloneable,
+public class TreeMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, Cloneable,
Serializable {
private static final long serialVersionUID = 919286545866124006L;
transient int size = 0;
- transient Entry root;
+ transient Entry<K, V> root;
- private Comparator comparator;
+ private Comparator<? super K> comparator;
transient int modCount = 0;
@@ -45,21 +45,21 @@
* Entry is an internal class which is used to hold the entries of a
* TreeMap.
*/
- static class Entry extends MapEntry {
- Entry parent, left, right;
+ static class Entry<K, V> extends MapEntry<K, V> {
+ Entry<K, V> parent, left, right;
boolean color;
- Entry(Object key) {
+ Entry(K key) {
super(key);
}
- Entry(Object key, Object value) {
+ Entry(K key, V value) {
super(key, value);
}
- Entry clone(Entry parent) {
- Entry clone = (Entry) super.clone();
+ Entry<K, V> clone(Entry<K, V> parent) {
+ Entry<K, V> clone = (Entry<K, V>) super.clone();
clone.parent = parent;
if (left != null)
clone.left = left.clone(clone);
@@ -69,20 +69,20 @@
}
}
- private static final class TreeMapIterator implements Iterator {
- private final TreeMap backingMap;
+ private static final class TreeMapIterator<E, K, V> implements Iterator<E> {
+ private final TreeMap<K, V> backingMap;
private int expectedModCount;
- private final MapEntry.Type type;
+ private final MapEntry.Type<E, K, V> type;
private boolean hasEnd = false;
- private Entry node, lastNode;
+ private Entry<K, V> node, lastNode;
- private Object endKey;
+ private K endKey;
- TreeMapIterator(TreeMap map, MapEntry.Type value) {
+ TreeMapIterator(TreeMap<K, V> map, MapEntry.Type<E, K, V> value) {
backingMap = map;
type = value;
expectedModCount = map.modCount;
@@ -90,8 +90,8 @@
node = TreeMap.minimum(map.root);
}
- TreeMapIterator(TreeMap map, MapEntry.Type value, Entry startNode,
- boolean checkEnd, Object end) {
+ 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;
@@ -104,15 +104,15 @@
return node != null;
}
- public Object next() {
+ public E next() {
if (expectedModCount == backingMap.modCount) {
if (node != null) {
lastNode = node;
node = TreeMap.successor(node);
if (hasEnd && node != null) {
- Comparator c = backingMap.comparator();
+ Comparator<? super K> c = backingMap.comparator();
if (c == null) {
- if (((Comparable) endKey).compareTo(node.key) <= 0)
+ if (((Comparable<K>)endKey).compareTo(node.key) <= 0)
node = null;
} else {
if (c.compare(endKey, node.key) <= 0)
@@ -139,29 +139,29 @@
}
}
- static final class SubMap extends AbstractMap implements SortedMap {
- private final TreeMap backingMap;
+ static final class SubMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V> {
+ private final TreeMap<K, V> backingMap;
private boolean hasStart, hasEnd;
- private Object startKey, endKey;
+ private K startKey, endKey;
- static class SubMapSet extends AbstractSet implements Set {
- final TreeMap backingMap;
+ static class SubMapSet<E, K, V> extends AbstractSet<E> implements Set<E> {
+ final TreeMap<K, V> backingMap;
boolean hasStart, hasEnd;
- Object startKey, endKey;
+ K startKey, endKey;
- final MapEntry.Type type;
+ final MapEntry.Type<E, K, V> type;
- SubMapSet(TreeMap map, MapEntry.Type theType) {
+ SubMapSet(TreeMap<K, V> map, MapEntry.Type<E, K, V> theType) {
backingMap = map;
type = theType;
}
- SubMapSet(boolean starting, Object start, TreeMap map,
- boolean ending, Object end, MapEntry.Type theType) {
+ 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;
@@ -169,9 +169,9 @@
endKey = end;
}
- void checkRange(Object key) {
+ void checkRange(K key) {
if (backingMap.comparator() == null) {
- Comparable object = (Comparable) key;
+ Comparable<K> object = (Comparable<K>) key;
if (hasStart && object.compareTo(startKey) < 0)
throw new IllegalArgumentException();
if (hasEnd && object.compareTo(endKey) >= 0)
@@ -186,9 +186,9 @@
}
}
- boolean checkRange(Object key, boolean hasStart, boolean hasEnd) {
+ boolean checkRange(K key, boolean hasStart, boolean hasEnd) {
if (backingMap.comparator() == null) {
- Comparable object = (Comparable) key;
+ Comparable<K> object = (Comparable<K>) key;
if (hasStart && object.compareTo(startKey) < 0)
return false;
if (hasEnd && object.compareTo(endKey) >= 0)
@@ -206,14 +206,14 @@
public boolean isEmpty() {
if (hasStart) {
- TreeMap.Entry node = backingMap.findAfter(startKey);
+ TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
return node == null || !checkRange(node.key, false, hasEnd);
}
return backingMap.findBefore(endKey) == null;
}
- public Iterator iterator() {
- TreeMap.Entry startNode;
+ public Iterator<E> iterator() {
+ TreeMap.Entry<K, V> startNode;
if (hasStart) {
startNode = backingMap.findAfter(startKey);
if (startNode != null
@@ -224,13 +224,13 @@
if (startNode != null)
startNode = minimum(backingMap.root);
}
- return new TreeMapIterator(backingMap, type, startNode, hasEnd,
+ return new TreeMapIterator<E, K, V>(backingMap, type, startNode, hasEnd,
endKey);
}
public int size() {
int size = 0;
- Iterator it = iterator();
+ Iterator<E> it = iterator();
while (it.hasNext()) {
size++;
it.next();
@@ -239,28 +239,28 @@
}
}
- SubMap(Object start, TreeMap map) {
+ 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;
}
- SubMap(Object start, TreeMap map, Object end) {
- backingMap = map;
- hasStart = hasEnd = true;
- startKey = start;
- endKey = end;
- }
-
- SubMap(TreeMap map, Object end) {
+ SubMap(TreeMap<K, V> map, K end) {
backingMap = map;
hasEnd = true;
endKey = end;
}
- private void checkRange(Object key) {
+ private void checkRange(K key) {
if (backingMap.comparator() == null) {
- Comparable object = (Comparable) key;
+ Comparable<K> object = (Comparable<K>) key;
if (hasStart && object.compareTo(startKey) < 0)
throw new IllegalArgumentException();
if (hasEnd && object.compareTo(endKey) >= 0)
@@ -274,9 +274,9 @@
}
}
- private boolean checkRange(Object key, boolean hasStart, boolean hasEnd) {
+ private boolean checkRange(K key, boolean hasStart, boolean hasEnd) {
if (backingMap.comparator() == null) {
- Comparable object = (Comparable) key;
+ Comparable<K> object = (Comparable<K>) key;
if (hasStart && object.compareTo(startKey) < 0)
return false;
if (hasEnd && object.compareTo(endKey) >= 0)
@@ -291,26 +291,26 @@
return true;
}
- public Comparator comparator() {
+ public Comparator<? super K> comparator() {
return backingMap.comparator();
}
public boolean containsKey(Object key) {
- if (checkRange(key, hasStart, hasEnd))
+ if (checkRange((K)key, hasStart, hasEnd))
return backingMap.containsKey(key);
return false;
}
- public Set entrySet() {
- return new SubMapSet(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
}) {
public boolean contains(Object object) {
if (object instanceof Map.Entry) {
- Map.Entry entry = (Map.Entry) object;
+ 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);
}
@@ -319,41 +319,41 @@
};
}
- public Object firstKey() {
+ public K firstKey() {
if (!hasStart)
return backingMap.firstKey();
- TreeMap.Entry node = backingMap.findAfter(startKey);
+ TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
if (node != null && checkRange(node.key, false, hasEnd))
return node.key;
throw new NoSuchElementException();
}
- public Object get(Object key) {
- if (checkRange(key, hasStart, hasEnd))
+ public V get(Object key) {
+ if (checkRange((K)key, hasStart, hasEnd))
return backingMap.get(key);
return null;
}
- public SortedMap headMap(Object endKey) {
+ public SortedMap<K, V> headMap(K endKey) {
checkRange(endKey);
if (hasStart)
- return new SubMap(startKey, backingMap, endKey);
- return new SubMap(backingMap, endKey);
+ return new SubMap<K, V>(startKey, backingMap, endKey);
+ return new SubMap<K, V>(backingMap, endKey);
}
public boolean isEmpty() {
if (hasStart) {
- TreeMap.Entry node = backingMap.findAfter(startKey);
+ TreeMap.Entry<K, V> node = backingMap.findAfter(startKey);
return node == null || !checkRange(node.key, false, hasEnd);
}
return backingMap.findBefore(endKey) == null;
}
- public Set keySet() {
+ public Set<K> keySet() {
if (keySet == null) {
- keySet = new SubMapSet(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
}) {
@@ -365,52 +365,52 @@
return keySet;
}
- public Object lastKey() {
+ public K lastKey() {
if (!hasEnd)
return backingMap.lastKey();
- TreeMap.Entry node = backingMap.findBefore(endKey);
+ TreeMap.Entry<K, V> node = backingMap.findBefore(endKey);
if (node != null && checkRange(node.key, hasStart, false))
return node.key;
throw new NoSuchElementException();
}
- public Object put(Object key, Object value) {
+ public V put(K key, V value) {
if (checkRange(key, hasStart, hasEnd))
return backingMap.put(key, value);
throw new IllegalArgumentException();
}
- public Object remove(Object key) {
- if (checkRange(key, hasStart, hasEnd))
+ public V remove(Object key) {
+ if (checkRange((K)key, hasStart, hasEnd))
return backingMap.remove(key);
return null;
}
- public SortedMap subMap(Object startKey, Object endKey) {
+ public SortedMap<K, V> subMap(K startKey, K endKey) {
checkRange(startKey);
checkRange(endKey);
- Comparator c = backingMap.comparator();
+ Comparator<? super K> c = backingMap.comparator();
if (c == null) {
- if (((Comparable) startKey).compareTo(endKey) <= 0)
- return new SubMap(startKey, backingMap, endKey);
+ if (((Comparable<K>) startKey).compareTo(endKey) <= 0)
+ return new SubMap<K, V>(startKey, backingMap, endKey);
} else {
if (c.compare(startKey, endKey) <= 0)
- return new SubMap(startKey, backingMap, endKey);
+ return new SubMap<K, V>(startKey, backingMap, endKey);
}
throw new IllegalArgumentException();
}
- public SortedMap tailMap(Object startKey) {
+ public SortedMap<K, V> tailMap(K startKey) {
checkRange(startKey);
if (hasEnd)
- return new SubMap(startKey, backingMap, endKey);
- return new SubMap(startKey, backingMap);
+ return new SubMap<K, V>(startKey, backingMap, endKey);
+ return new SubMap<K, V>(startKey, backingMap);
}
- public Collection values() {
- return new SubMapSet(hasStart, startKey, backingMap, hasEnd,
- endKey, new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
});
@@ -418,21 +418,21 @@
}
/**
- * Contructs a new empty instance of TreeMap.
+ * Constructs a new empty instance of TreeMap.
*
*/
public TreeMap() {
- /*empty*/
+ super();
}
/**
- * Contructs a new empty instance of TreeMap which uses the specified
+ * Constructs a new empty instance of TreeMap which uses the specified
* Comparator.
*
* @param comparator
* the Comparator
*/
- public TreeMap(Comparator comparator) {
+ public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
@@ -447,7 +447,7 @@
* when a key in the Map does not implement the Comparable
* interface, or they keys in the Map cannot be compared
*/
- public TreeMap(Map map) {
+ public TreeMap(Map<? extends K,? extends V> map) {
this();
putAll(map);
}
@@ -459,17 +459,17 @@
* @param map
* the mappings to add
*/
- public TreeMap(SortedMap map) {
+ public TreeMap(SortedMap<K,? extends V> map) {
this(map.comparator());
- Iterator it = map.entrySet().iterator();
+ Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator();
if (it.hasNext()) {
- Map.Entry entry = (Map.Entry) it.next();
- Entry last = new Entry(entry.getKey(), entry.getValue());
+ Map.Entry<K, ? extends V> entry = it.next();
+ Entry<K, V> last = new Entry<K, V>(entry.getKey(), entry.getValue());
root = last;
size = 1;
while (it.hasNext()) {
- entry = (Map.Entry) it.next();
- Entry x = new Entry(entry.getKey(), entry.getValue());
+ entry = it.next();
+ Entry<K, V> x = new Entry<K, V>(entry.getKey(), entry.getValue());
x.parent = last;
last.right = x;
size++;
@@ -479,8 +479,8 @@
}
}
- void balance(Entry x) {
- Entry y;
+ void balance(Entry<K, V> x) {
+ Entry<K, V> y;
x.color = true;
while (x != root && x.parent.color) {
if (x.parent == x.parent.parent.left) {
@@ -542,7 +542,7 @@
*/
public Object clone() {
try {
- TreeMap clone = (TreeMap) super.clone();
+ TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
if (root != null)
clone.root = root.clone(null);
return clone;
@@ -556,7 +556,7 @@
*
* @return a Comparator or null if the natural ordering is used
*/
- public Comparator comparator() {
+ public Comparator<? super K> comparator() {
return comparator;
}
@@ -575,7 +575,7 @@
* when the key is null and the comparator cannot handle null
*/
public boolean containsKey(Object key) {
- return find(key) != null;
+ return find((K)key) != null;
}
/**
@@ -592,7 +592,7 @@
return false;
}
- private boolean containsValue(Entry node, Object value) {
+ private boolean containsValue(Entry<K, V> node, Object value) {
if (value == null ? node.value == null : value.equals(node.value))
return true;
if (node.left != null)
@@ -607,12 +607,12 @@
/**
* Answers a Set of the mappings contained in this TreeMap. Each element in
* the set is a Map.Entry. The set is backed by this TreeMap so changes to
- * one are relected by the other. The set does not support adding.
+ * one are reflected by the other. The set does not support adding.
*
* @return a Set of the mappings
*/
- public Set entrySet() {
- return new AbstractSet() {
+ public Set<Map.Entry<K, V>> entrySet() {
+ return new AbstractSet<Map.Entry<K, V>>() {
public int size() {
return size;
}
@@ -623,16 +623,16 @@
public boolean contains(Object object) {
if (object instanceof Map.Entry) {
- Map.Entry entry = (Map.Entry) object;
+ 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;
}
- public Iterator iterator() {
- return new TreeMapIterator(TreeMap.this, new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
});
@@ -640,12 +640,12 @@
};
}
- private Entry find(Object key) {
+ private Entry<K, V> find(K key) {
int result;
- Comparable object = null;
+ Comparable<K> object = null;
if (comparator == null)
- object = (Comparable) key;
- Entry x = root;
+ object = (Comparable<K>) key;
+ Entry<K, V> x = root;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
@@ -656,12 +656,12 @@
return null;
}
- Entry findAfter(Object key) {
+ Entry<K, V> findAfter(K key) {
int result;
- Comparable object = null;
+ Comparable<K> object = null;
if (comparator == null)
- object = (Comparable) key;
- Entry x = root, last = null;
+ object = (Comparable<K>) key;
+ Entry<K, V> x = root, last = null;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
@@ -676,12 +676,12 @@
return last;
}
- Entry findBefore(Object key) {
+ Entry<K, V> findBefore(K key) {
int result;
- Comparable object = null;
+ Comparable<K> object = null;
if (comparator == null)
- object = (Comparable) key;
- Entry x = root, last = null;
+ object = (Comparable<K>) key;
+ Entry<K, V> x = root, last = null;
while (x != null) {
result = object != null ? object.compareTo(x.key) : comparator
.compare(key, x.key);
@@ -703,14 +703,14 @@
* @exception NoSuchElementException
* when this TreeMap is empty
*/
- public Object firstKey() {
+ public K firstKey() {
if (root != null)
return minimum(root).key;
throw new NoSuchElementException();
}
- private void fixup(Entry x) {
- Entry w;
+ private void fixup(Entry<K, V> x) {
+ Entry<K, V> w;
while (x != root && !x.color) {
if (x == x.parent.left) {
w = x.parent.right;
@@ -796,8 +796,8 @@
* @exception NullPointerException
* when the key is null and the comparator cannot handle null
*/
- public Object get(Object key) {
- Entry node = find(key);
+ public V get(Object key) {
+ Entry<K, V> node = find((K)key);
if (node != null)
return node.value;
return null;
@@ -819,25 +819,25 @@
* when the end key is null and the comparator cannot handle
* null
*/
- public SortedMap headMap(Object endKey) {
+ public SortedMap<K, V> headMap(K endKey) {
// Check for errors
if (comparator == null)
- ((Comparable) endKey).compareTo(endKey);
+ ((Comparable<K>) endKey).compareTo(endKey);
else
comparator.compare(endKey, endKey);
- return new SubMap(this, endKey);
+ return new SubMap<K, V>(this, endKey);
}
/**
* Answers a Set of the keys contained in this TreeMap. The set is backed by
- * this TreeMap so changes to one are relected by the other. The set does
+ * this TreeMap so changes to one are reflected by the other. The set does
* not support adding.
*
* @return a Set of the keys
*/
- public Set keySet() {
+ public Set<K> keySet() {
if (keySet == null) {
- keySet = new AbstractSet() {
+ keySet = new AbstractSet<K>() {
public boolean contains(Object object) {
return containsKey(object);
}
@@ -850,10 +850,10 @@
TreeMap.this.clear();
}
- public Iterator iterator() {
- return new TreeMapIterator(TreeMap.this,
- new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
});
@@ -871,14 +871,14 @@
* @exception NoSuchElementException
* when this TreeMap is empty
*/
- public Object lastKey() {
+ public K lastKey() {
if (root != null)
return maximum(root).key;
throw new NoSuchElementException();
}
- private void leftRotate(Entry x) {
- Entry y = x.right;
+ private void leftRotate(Entry<K, V> x) {
+ Entry<K, V> y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
@@ -895,22 +895,22 @@
x.parent = y;
}
- static Entry maximum(Entry x) {
+ static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
while (x.right != null)
x = x.right;
return x;
}
- static Entry minimum(Entry x) {
+ static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
while (x.left != null)
x = x.left;
return x;
}
- static Entry predecessor(Entry x) {
+ static <K, V> Entry<K, V> predecessor(Entry<K, V> x) {
if (x.left != null)
return maximum(x.left);
- Entry y = x.parent;
+ Entry<K, V> y = x.parent;
while (y != null && x == y.left) {
x = y;
y = y.parent;
@@ -934,9 +934,9 @@
* @exception NullPointerException
* when the key is null and the comparator cannot handle null
*/
- public Object put(Object key, Object value) {
- MapEntry entry = rbInsert(key);
- Object result = entry.value;
+ public V put(K key, V value) {
+ MapEntry<K, V> entry = rbInsert(key);
+ V result = entry.value;
entry.value = value;
return result;
}
@@ -954,13 +954,13 @@
* when a key in the Map is null and the comparator cannot
* handle null
*/
- public void putAll(Map map) {
+ public void putAll(Map<? extends K, ? extends V> map) {
super.putAll(map);
}
- void rbDelete(Entry z) {
- Entry y = z.left == null || z.right == null ? z : successor(z);
- Entry x = y.left != null ? y.left : y.right;
+ void rbDelete(Entry<K, V> z) {
+ Entry<K, V> y = z.left == null || z.right == null ? z : successor(z);
+ Entry<K, V> x = y.left != null ? y.left : y.right;
if (x != null)
x.parent = y.parent;
if (y.parent == null)
@@ -983,12 +983,12 @@
size--;
}
- private Entry rbInsert(Object object) {
+ private Entry<K, V> rbInsert(K object) {
int result = 0;
- Comparable key = null;
+ Comparable<K> key = null;
if (comparator == null)
- key = (Comparable) object;
- Entry y = null, x = root;
+ key = (Comparable<K>) object;
+ Entry<K, V> y = null, x = root;
while (x != null) {
y = x;
result = key != null ? key.compareTo(x.key) : comparator.compare(
@@ -1000,7 +1000,7 @@
size++;
modCount++;
- Entry z = new Entry(object);
+ Entry<K, V> z = new Entry<K, V>(object);
if (y == null)
return root = z;
z.parent = y;
@@ -1026,17 +1026,17 @@
* @exception NullPointerException
* when the key is null and the comparator cannot handle null
*/
- public Object remove(Object key) {
- Entry node = find(key);
+ public V remove(Object key) {
+ Entry<K, V> node = find((K)key);
if (node == null)
return null;
- Object result = node.value;
+ V result = node.value;
rbDelete(node);
return result;
}
- private void rightRotate(Entry x) {
- Entry y = x.left;
+ private void rightRotate(Entry<K, V> x) {
+ Entry<K, V> y = x.left;
x.left = y.right;
if (y.right != null)
y.right.parent = x;
@@ -1082,21 +1082,21 @@
* when the start or end key is null and the comparator
* cannot handle null
*/
- public SortedMap subMap(Object startKey, Object endKey) {
+ public SortedMap<K, V> subMap(K startKey, K endKey) {
if (comparator == null) {
- if (((Comparable) startKey).compareTo(endKey) <= 0)
- return new SubMap(startKey, this, endKey);
+ if (((Comparable<K>) startKey).compareTo(endKey) <= 0)
+ return new SubMap<K, V>(startKey, this, endKey);
} else {
if (comparator.compare(startKey, endKey) <= 0)
- return new SubMap(startKey, this, endKey);
+ return new SubMap<K, V>(startKey, this, endKey);
}
throw new IllegalArgumentException();
}
- static Entry successor(Entry x) {
+ static <K, V> Entry<K, V> successor(Entry<K, V> x) {
if (x.right != null)
return minimum(x.right);
- Entry y = x.parent;
+ Entry<K, V> y = x.parent;
while (y != null && x == y.right) {
x = y;
y = y.parent;
@@ -1121,13 +1121,13 @@
* when the start key is null and the comparator cannot
* handle null
*/
- public SortedMap tailMap(Object startKey) {
+ public SortedMap<K, V> tailMap(K startKey) {
// Check for errors
if (comparator == null)
- ((Comparable) startKey).compareTo(startKey);
+ ((Comparable<K>) startKey).compareTo(startKey);
else
comparator.compare(startKey, startKey);
- return new SubMap(startKey, this);
+ return new SubMap<K, V>(startKey, this);
}
/**
@@ -1137,9 +1137,9 @@
*
* @return a Collection of the values
*/
- public Collection values() {
+ public Collection<V> values() {
if (valuesCollection == null) {
- valuesCollection = new AbstractCollection() {
+ valuesCollection = new AbstractCollection<V>() {
public boolean contains(Object object) {
return containsValue(object);
}
@@ -1152,10 +1152,10 @@
TreeMap.this.clear();
}
- public Iterator iterator() {
- return new TreeMapIterator(TreeMap.this,
- new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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;
}
});
@@ -1169,7 +1169,7 @@
stream.defaultWriteObject();
stream.writeInt(size);
if (size > 0) {
- Entry node = minimum(root);
+ Entry<K, V> node = minimum(root);
while (node != null) {
stream.writeObject(node.key);
stream.writeObject(node.value);
@@ -1182,10 +1182,10 @@
ClassNotFoundException {
stream.defaultReadObject();
size = stream.readInt();
- Entry last = null;
+ Entry<K, V> last = null;
for (int i = size; --i >= 0;) {
- Entry node = new Entry(stream.readObject());
- node.value = stream.readObject();
+ Entry<K, V> node = new Entry<K, V>((K)stream.readObject());
+ node.value = (V)stream.readObject();
if (last == null)
root = node;
else {
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=411690&r1=411689&r2=411690&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 Sun Jun 4 23:39:37 2006
@@ -26,117 +26,118 @@
* supported, adding and removing. The elements can be any objects which are
* comparable to each other either using their natural order or a specified
* Comparator.
+ * @since 1.2
*/
-public class TreeSet extends AbstractSet implements SortedSet, Cloneable,
+public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>, Cloneable,
Serializable {
private static final long serialVersionUID = -2479143000061671589L;
- private transient TreeMap backingMap;
+ private transient TreeMap<E, E> backingMap;
- private static final class SubSet extends TreeMap.SubMap.SubMapSet
- implements SortedSet {
- private SubSet(TreeMap map) {
- super(map, new MapEntry.Type() {
- public Object get(MapEntry entry) {
+ 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(Object start, TreeMap map) {
+ private SubSet(E start, TreeMap<E, E> map) {
this(map);
hasStart = true;
startKey = start;
}
- private SubSet(Object start, TreeMap map, Object end) {
+ private SubSet(E start, TreeMap<E, E> map, E end) {
this(map);
hasStart = hasEnd = true;
startKey = start;
endKey = end;
}
- private SubSet(TreeMap map, Object end) {
+ private SubSet(TreeMap<E, E> map, E end) {
this(map);
hasEnd = true;
endKey = end;
}
- public boolean add(Object object) {
+ public boolean add(E object) {
checkRange(object);
return this.backingMap.put(object, object) != null;
}
- public Comparator comparator() {
+ public Comparator<? super E> comparator() {
return this.backingMap.comparator();
}
public boolean contains(Object object) {
- if (checkRange(object, hasStart, hasEnd))
+ if (checkRange((E)object, hasStart, hasEnd))
return this.backingMap.containsKey(object);
return false;
}
- public Object first() {
+ public E first() {
if (!hasStart)
return this.backingMap.firstKey();
- TreeMap.Entry node = this.backingMap.findAfter(startKey);
+ 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 headSet(Object end) {
+ public SortedSet<E> headSet(E end) {
checkRange(end);
if (hasStart)
- return new SubSet(startKey, this.backingMap, end);
- return new SubSet(this.backingMap, end);
+ return new SubSet<E>(startKey, this.backingMap, end);
+ return new SubSet<E>(this.backingMap, end);
}
- public Object last() {
+ public E last() {
if (!hasEnd)
return this.backingMap.lastKey();
- TreeMap.Entry node = this.backingMap.findBefore(endKey);
+ 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(object, hasStart, hasEnd))
+ if (checkRange((E)object, hasStart, hasEnd))
return this.backingMap.remove(object) != null;
return false;
}
- public SortedSet subSet(Object start, Object end) {
+ public SortedSet<E> subSet(E start, E end) {
checkRange(start);
checkRange(end);
- Comparator c = this.backingMap.comparator();
+ Comparator<? super E> c = this.backingMap.comparator();
if (c == null) {
- if (((Comparable) startKey).compareTo(endKey) <= 0)
- return new SubSet(start, this.backingMap, end);
+ 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(start, this.backingMap, end);
+ return new SubSet<E>(start, this.backingMap, end);
}
throw new IllegalArgumentException();
}
- public SortedSet tailSet(Object start) {
+ public SortedSet<E> tailSet(E start) {
checkRange(start);
if (hasEnd)
- return new SubSet(start, this.backingMap, endKey);
- return new SubSet(start, this.backingMap);
+ return new SubSet<E>(start, this.backingMap, endKey);
+ return new SubSet<E>(start, this.backingMap);
}
}
/**
- * Contructs a new empty instance of TreeSet which uses natural ordering.
+ * Constructs a new empty instance of TreeSet which uses natural ordering.
*
*/
public TreeSet() {
- backingMap = new TreeMap();
+ backingMap = new TreeMap<E, E>();
}
/**
@@ -151,20 +152,20 @@
* Comparable interface, or the elements in the Collection
* cannot be compared
*/
- public TreeSet(Collection collection) {
+ public TreeSet(Collection<? extends E> collection) {
this();
addAll(collection);
}
/**
- * Contructs a new empty instance of TreeSet which uses the specified
+ * Constructs a new empty instance of TreeSet which uses the specified
* Comparator.
*
* @param comparator
* the Comparator
*/
- public TreeSet(Comparator comparator) {
- backingMap = new TreeMap(comparator);
+ public TreeSet(Comparator<? super E> comparator) {
+ backingMap = new TreeMap<E, E>(comparator);
}
/**
@@ -174,17 +175,17 @@
* @param set
* the SortedSet of elements to add
*/
- public TreeSet(SortedSet set) {
+ public TreeSet(SortedSet<E> set) {
this(set.comparator());
- Iterator it = set.iterator();
+ Iterator<E> it = set.iterator();
if (it.hasNext()) {
- Object object = it.next();
- TreeMap.Entry last = new TreeMap.Entry(object, object);
+ 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 x = new TreeMap.Entry(object, object);
+ TreeMap.Entry<E, E> x = new TreeMap.Entry<E, E>(object, object);
x.parent = last;
last.right = x;
backingMap.size++;
@@ -209,7 +210,7 @@
* when the object is null and the comparator cannot handle
* null
*/
- public boolean add(Object object) {
+ public boolean add(E object) {
return backingMap.put(object, object) == null;
}
@@ -227,7 +228,7 @@
* when an object in the Collection is null and the
* comparator cannot handle null
*/
- public boolean addAll(Collection collection) {
+ public boolean addAll(Collection<? extends E> collection) {
return super.addAll(collection);
}
@@ -251,8 +252,8 @@
*/
public Object clone() {
try {
- TreeSet clone = (TreeSet) super.clone();
- clone.backingMap = (TreeMap) backingMap.clone();
+ TreeSet<E> clone = (TreeSet<E>) super.clone();
+ clone.backingMap = (TreeMap<E, E>) backingMap.clone();
return clone;
} catch (CloneNotSupportedException e) {
return null;
@@ -264,7 +265,7 @@
*
* @return a Comparator or null if the natural ordering is used
*/
- public Comparator comparator() {
+ public Comparator<? super E> comparator() {
return backingMap.comparator();
}
@@ -295,7 +296,7 @@
* @exception NoSuchElementException
* when this TreeSet is empty
*/
- public Object first() {
+ public E first() {
return backingMap.firstKey();
}
@@ -315,14 +316,14 @@
* when the end object is null and the comparator cannot
* handle null
*/
- public SortedSet headSet(Object end) {
+ public SortedSet<E> headSet(E end) {
// Check for errors
- Comparator c = backingMap.comparator();
+ Comparator<? super E> c = backingMap.comparator();
if (c == null)
- ((Comparable) end).compareTo(end);
+ ((Comparable<E>) end).compareTo(end);
else
c.compare(end, end);
- return new SubSet(backingMap, end);
+ return new SubSet<E>(backingMap, end);
}
/**
@@ -343,7 +344,7 @@
*
* @see Iterator
*/
- public Iterator iterator() {
+ public Iterator<E> iterator() {
return backingMap.keySet().iterator();
}
@@ -355,7 +356,7 @@
* @exception NoSuchElementException
* when this TreeSet is empty
*/
- public Object last() {
+ public E last() {
return backingMap.lastKey();
}
@@ -406,14 +407,14 @@
* when the start or end object is null and the comparator
* cannot handle null
*/
- public SortedSet subSet(Object start, Object end) {
- Comparator c = backingMap.comparator();
+ public SortedSet<E> subSet(E start, E end) {
+ Comparator<? super E> c = backingMap.comparator();
if (c == null) {
- if (((Comparable) start).compareTo(end) <= 0)
- return new SubSet(start, backingMap, end);
+ if (((Comparable<E>) start).compareTo(end) <= 0)
+ return new SubSet<E>(start, backingMap, end);
} else {
if (c.compare(start, end) <= 0)
- return new SubSet(start, backingMap, end);
+ return new SubSet<E>(start, backingMap, end);
}
throw new IllegalArgumentException();
}
@@ -436,14 +437,14 @@
* when the start object is null and the comparator cannot
* handle null
*/
- public SortedSet tailSet(Object start) {
+ public SortedSet<E> tailSet(E start) {
// Check for errors
- Comparator c = backingMap.comparator();
+ Comparator<? super E> c = backingMap.comparator();
if (c == null)
- ((Comparable) start).compareTo(start);
+ ((Comparable<E>) start).compareTo(start);
else
c.compare(start, start);
- return new SubSet(start, backingMap);
+ return new SubSet<E>(start, backingMap);
}
private void writeObject(ObjectOutputStream stream) throws IOException {
@@ -451,7 +452,7 @@
stream.writeObject(backingMap.comparator());
stream.writeInt(backingMap.size);
if (backingMap.size > 0) {
- TreeMap.Entry node = TreeMap.minimum(backingMap.root);
+ TreeMap.Entry<E, E> node = TreeMap.minimum(backingMap.root);
while (node != null) {
stream.writeObject(node.key);
node = TreeMap.successor(node);
@@ -462,12 +463,12 @@
private void readObject(ObjectInputStream stream) throws IOException,
ClassNotFoundException {
stream.defaultReadObject();
- backingMap = new TreeMap((Comparator) stream.readObject());
+ backingMap = new TreeMap<E, E>((Comparator<? super E>) stream.readObject());
backingMap.size = stream.readInt();
- TreeMap.Entry last = null;
+ TreeMap.Entry<E, E> last = null;
for (int i = backingMap.size; --i >= 0;) {
- TreeMap.Entry node = new TreeMap.Entry(stream.readObject());
- node.value = this;
+ TreeMap.Entry<E, E> node = new TreeMap.Entry<E, E>((E)stream.readObject());
+ node.value = node.key;
if (last == null)
backingMap.root = node;
else {