Index: /luni/src/main/java/java/util/TreeSet.java =================================================================== --- /luni/src/main/java/java/util/TreeSet.java (revision 411466) +++ /luni/src/main/java/java/util/TreeSet.java (working copy) @@ -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 extends AbstractSet implements SortedSet, Cloneable, Serializable { private static final long serialVersionUID = -2479143000061671589L; - private transient TreeMap backingMap; + private transient TreeMap 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 extends TreeMap.SubMap.SubMapSet + implements SortedSet { + private SubSet(TreeMap map) { + super(map, new MapEntry.Type() { + public E get(MapEntry entry) { return entry.key; } }); } - private SubSet(Object start, TreeMap map) { + private SubSet(E start, TreeMap map) { this(map); hasStart = true; startKey = start; } - private SubSet(Object start, TreeMap map, Object end) { + private SubSet(E start, TreeMap map, E end) { this(map); hasStart = hasEnd = true; startKey = start; endKey = end; } - private SubSet(TreeMap map, Object end) { + private SubSet(TreeMap 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 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 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 headSet(E end) { checkRange(end); if (hasStart) - return new SubSet(startKey, this.backingMap, end); - return new SubSet(this.backingMap, end); + return new SubSet(startKey, this.backingMap, end); + return new SubSet(this.backingMap, end); } - public Object last() { + public E last() { if (!hasEnd) return this.backingMap.lastKey(); - TreeMap.Entry node = this.backingMap.findBefore(endKey); + TreeMap.Entry 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 subSet(E start, E end) { checkRange(start); checkRange(end); - Comparator c = this.backingMap.comparator(); + Comparator c = this.backingMap.comparator(); if (c == null) { - if (((Comparable) startKey).compareTo(endKey) <= 0) - return new SubSet(start, this.backingMap, end); + if (((Comparable) startKey).compareTo(endKey) <= 0) + return new SubSet(start, this.backingMap, end); } else { if (c.compare(startKey, endKey) <= 0) - return new SubSet(start, this.backingMap, end); + return new SubSet(start, this.backingMap, end); } throw new IllegalArgumentException(); } - public SortedSet tailSet(Object start) { + public SortedSet tailSet(E start) { checkRange(start); if (hasEnd) - return new SubSet(start, this.backingMap, endKey); - return new SubSet(start, this.backingMap); + return new SubSet(start, this.backingMap, endKey); + return new SubSet(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(); } /** @@ -151,20 +152,20 @@ * Comparable interface, or the elements in the Collection * cannot be compared */ - public TreeSet(Collection collection) { + public TreeSet(Collection 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 comparator) { + backingMap = new TreeMap(comparator); } /** @@ -174,17 +175,17 @@ * @param set * the SortedSet of elements to add */ - public TreeSet(SortedSet set) { + public TreeSet(SortedSet set) { this(set.comparator()); - Iterator it = set.iterator(); + Iterator it = set.iterator(); if (it.hasNext()) { - Object object = it.next(); - TreeMap.Entry last = new TreeMap.Entry(object, object); + E object = it.next(); + TreeMap.Entry last = new TreeMap.Entry(object, object); backingMap.root = last; backingMap.size = 1; while (it.hasNext()) { object = it.next(); - TreeMap.Entry x = new TreeMap.Entry(object, object); + TreeMap.Entry x = new TreeMap.Entry(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 collection) { return super.addAll(collection); } @@ -251,8 +252,8 @@ */ public Object clone() { try { - TreeSet clone = (TreeSet) super.clone(); - clone.backingMap = (TreeMap) backingMap.clone(); + TreeSet clone = (TreeSet) super.clone(); + clone.backingMap = (TreeMap) 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 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 headSet(E end) { // Check for errors - Comparator c = backingMap.comparator(); + Comparator c = backingMap.comparator(); if (c == null) - ((Comparable) end).compareTo(end); + ((Comparable) end).compareTo(end); else c.compare(end, end); - return new SubSet(backingMap, end); + return new SubSet(backingMap, end); } /** @@ -343,7 +344,7 @@ * * @see Iterator */ - public Iterator iterator() { + public Iterator 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 subSet(E start, E end) { + Comparator c = backingMap.comparator(); if (c == null) { - if (((Comparable) start).compareTo(end) <= 0) - return new SubSet(start, backingMap, end); + if (((Comparable) start).compareTo(end) <= 0) + return new SubSet(start, backingMap, end); } else { if (c.compare(start, end) <= 0) - return new SubSet(start, backingMap, end); + return new SubSet(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 tailSet(E start) { // Check for errors - Comparator c = backingMap.comparator(); + Comparator c = backingMap.comparator(); if (c == null) - ((Comparable) start).compareTo(start); + ((Comparable) start).compareTo(start); else c.compare(start, start); - return new SubSet(start, backingMap); + return new SubSet(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 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((Comparator) stream.readObject()); backingMap.size = stream.readInt(); - TreeMap.Entry last = null; + TreeMap.Entry last = null; for (int i = backingMap.size; --i >= 0;) { - TreeMap.Entry node = new TreeMap.Entry(stream.readObject()); - node.value = this; + TreeMap.Entry node = new TreeMap.Entry((E)stream.readObject()); + node.value = node.key; if (last == null) backingMap.root = node; else { Index: /luni/src/main/java/java/util/TreeMap.java =================================================================== --- /luni/src/main/java/java/util/TreeMap.java (revision 411466) +++ /luni/src/main/java/java/util/TreeMap.java (working copy) @@ -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 extends AbstractMap implements SortedMap, Cloneable, Serializable { private static final long serialVersionUID = 919286545866124006L; transient int size = 0; - transient Entry root; + transient Entry root; - private Comparator comparator; + private Comparator 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 extends MapEntry { + Entry 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 clone(Entry parent) { + Entry clone = (Entry) 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 implements Iterator { + private final TreeMap backingMap; private int expectedModCount; - private final MapEntry.Type type; + private final MapEntry.Type type; private boolean hasEnd = false; - private Entry node, lastNode; + private Entry node, lastNode; - private Object endKey; + private K endKey; - TreeMapIterator(TreeMap map, MapEntry.Type value) { + TreeMapIterator(TreeMap map, MapEntry.Type 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 map, MapEntry.Type value, Entry 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 c = backingMap.comparator(); if (c == null) { - if (((Comparable) endKey).compareTo(node.key) <= 0) + if (((Comparable)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 extends AbstractMap implements SortedMap { + private final TreeMap 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 extends AbstractSet implements Set { + final TreeMap backingMap; boolean hasStart, hasEnd; - Object startKey, endKey; + K startKey, endKey; - final MapEntry.Type type; + final MapEntry.Type type; - SubMapSet(TreeMap map, MapEntry.Type theType) { + SubMapSet(TreeMap map, MapEntry.Type 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 map, + boolean ending, K end, MapEntry.Type 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 object = (Comparable) 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 object = (Comparable) 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 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 iterator() { + TreeMap.Entry 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(backingMap, type, startNode, hasEnd, endKey); } public int size() { int size = 0; - Iterator it = iterator(); + Iterator it = iterator(); while (it.hasNext()) { size++; it.next(); @@ -239,28 +239,28 @@ } } - SubMap(Object start, TreeMap map) { + SubMap(K start, TreeMap map, K end) { + backingMap = map; + hasStart = hasEnd = true; + startKey = start; + endKey = end; + } + + SubMap(K start, TreeMap map) { backingMap = map; hasStart = true; startKey = start; } - SubMap(Object start, TreeMap map, Object end) { + SubMap(TreeMap map, K end) { backingMap = map; - hasStart = hasEnd = true; - startKey = start; - endKey = end; - } - - SubMap(TreeMap map, Object 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 object = (Comparable) 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 object = (Comparable) 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 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> entrySet() { + return new SubMapSet, K, V>(hasStart, startKey, backingMap, hasEnd, + endKey, new MapEntry.Type, K, V>() { + public Map.Entry get(MapEntry entry) { return entry; } }) { public boolean contains(Object object) { if (object instanceof Map.Entry) { - Map.Entry entry = (Map.Entry) object; + Map.Entry entry = (Map.Entry) 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 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 headMap(K endKey) { checkRange(endKey); if (hasStart) - return new SubMap(startKey, backingMap, endKey); - return new SubMap(backingMap, endKey); + return new SubMap(startKey, backingMap, endKey); + return new SubMap(backingMap, endKey); } public boolean isEmpty() { if (hasStart) { - TreeMap.Entry node = backingMap.findAfter(startKey); + TreeMap.Entry node = backingMap.findAfter(startKey); return node == null || !checkRange(node.key, false, hasEnd); } return backingMap.findBefore(endKey) == null; } - public Set keySet() { + public Set keySet() { if (keySet == null) { - keySet = new SubMapSet(hasStart, startKey, backingMap, hasEnd, - endKey, new MapEntry.Type() { - public Object get(MapEntry entry) { + keySet = new SubMapSet(hasStart, startKey, backingMap, hasEnd, + endKey, new MapEntry.Type() { + public K get(MapEntry 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 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 subMap(K startKey, K endKey) { checkRange(startKey); checkRange(endKey); - Comparator c = backingMap.comparator(); + Comparator c = backingMap.comparator(); if (c == null) { - if (((Comparable) startKey).compareTo(endKey) <= 0) - return new SubMap(startKey, backingMap, endKey); + if (((Comparable) startKey).compareTo(endKey) <= 0) + return new SubMap(startKey, backingMap, endKey); } else { if (c.compare(startKey, endKey) <= 0) - return new SubMap(startKey, backingMap, endKey); + return new SubMap(startKey, backingMap, endKey); } throw new IllegalArgumentException(); } - public SortedMap tailMap(Object startKey) { + public SortedMap tailMap(K startKey) { checkRange(startKey); if (hasEnd) - return new SubMap(startKey, backingMap, endKey); - return new SubMap(startKey, backingMap); + return new SubMap(startKey, backingMap, endKey); + return new SubMap(startKey, backingMap); } - public Collection values() { - return new SubMapSet(hasStart, startKey, backingMap, hasEnd, - endKey, new MapEntry.Type() { - public Object get(MapEntry entry) { + public Collection values() { + return new SubMapSet(hasStart, startKey, backingMap, hasEnd, + endKey, new MapEntry.Type() { + public V get(MapEntry 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 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 map) { this(); putAll(map); } @@ -459,17 +459,17 @@ * @param map * the mappings to add */ - public TreeMap(SortedMap map) { + public TreeMap(SortedMap map) { this(map.comparator()); - Iterator it = map.entrySet().iterator(); + Iterator> it = map.entrySet().iterator(); if (it.hasNext()) { - Map.Entry entry = (Map.Entry) it.next(); - Entry last = new Entry(entry.getKey(), entry.getValue()); + Map.Entry entry = it.next(); + Entry last = new Entry(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 x = new Entry(entry.getKey(), entry.getValue()); x.parent = last; last.right = x; size++; @@ -479,8 +479,8 @@ } } - void balance(Entry x) { - Entry y; + void balance(Entry x) { + Entry 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 clone = (TreeMap) 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 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 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> entrySet() { + return new AbstractSet>() { 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 entry = (Map.Entry) 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> iterator() { + return new TreeMapIterator, K, V>(TreeMap.this, new MapEntry.Type, K, V>() { + public Map.Entry get(MapEntry entry) { return entry; } }); @@ -640,12 +640,12 @@ }; } - private Entry find(Object key) { + private Entry find(K key) { int result; - Comparable object = null; + Comparable object = null; if (comparator == null) - object = (Comparable) key; - Entry x = root; + object = (Comparable) key; + Entry 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 findAfter(K key) { int result; - Comparable object = null; + Comparable object = null; if (comparator == null) - object = (Comparable) key; - Entry x = root, last = null; + object = (Comparable) key; + Entry 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 findBefore(K key) { int result; - Comparable object = null; + Comparable object = null; if (comparator == null) - object = (Comparable) key; - Entry x = root, last = null; + object = (Comparable) key; + Entry 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 x) { + Entry 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 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 headMap(K endKey) { // Check for errors if (comparator == null) - ((Comparable) endKey).compareTo(endKey); + ((Comparable) endKey).compareTo(endKey); else comparator.compare(endKey, endKey); - return new SubMap(this, endKey); + return new SubMap(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 keySet() { if (keySet == null) { - keySet = new AbstractSet() { + keySet = new AbstractSet() { 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 iterator() { + return new TreeMapIterator(TreeMap.this, + new MapEntry.Type() { + public K get(MapEntry 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 x) { + Entry 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 Entry maximum(Entry x) { while (x.right != null) x = x.right; return x; } - static Entry minimum(Entry x) { + static Entry minimum(Entry x) { while (x.left != null) x = x.left; return x; } - static Entry predecessor(Entry x) { + static Entry predecessor(Entry x) { if (x.left != null) return maximum(x.left); - Entry y = x.parent; + Entry 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 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 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 z) { + Entry y = z.left == null || z.right == null ? z : successor(z); + Entry 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 rbInsert(K object) { int result = 0; - Comparable key = null; + Comparable key = null; if (comparator == null) - key = (Comparable) object; - Entry y = null, x = root; + key = (Comparable) object; + Entry 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 z = new Entry(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 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 x) { + Entry 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 subMap(K startKey, K endKey) { if (comparator == null) { - if (((Comparable) startKey).compareTo(endKey) <= 0) - return new SubMap(startKey, this, endKey); + if (((Comparable) startKey).compareTo(endKey) <= 0) + return new SubMap(startKey, this, endKey); } else { if (comparator.compare(startKey, endKey) <= 0) - return new SubMap(startKey, this, endKey); + return new SubMap(startKey, this, endKey); } throw new IllegalArgumentException(); } - static Entry successor(Entry x) { + static Entry successor(Entry x) { if (x.right != null) return minimum(x.right); - Entry y = x.parent; + Entry 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 tailMap(K startKey) { // Check for errors if (comparator == null) - ((Comparable) startKey).compareTo(startKey); + ((Comparable) startKey).compareTo(startKey); else comparator.compare(startKey, startKey); - return new SubMap(startKey, this); + return new SubMap(startKey, this); } /** @@ -1137,9 +1137,9 @@ * * @return a Collection of the values */ - public Collection values() { + public Collection values() { if (valuesCollection == null) { - valuesCollection = new AbstractCollection() { + valuesCollection = new AbstractCollection() { 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 iterator() { + return new TreeMapIterator(TreeMap.this, + new MapEntry.Type() { + public V get(MapEntry entry) { return entry.value; } }); @@ -1169,7 +1169,7 @@ stream.defaultWriteObject(); stream.writeInt(size); if (size > 0) { - Entry node = minimum(root); + Entry 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 last = null; for (int i = size; --i >= 0;) { - Entry node = new Entry(stream.readObject()); - node.value = stream.readObject(); + Entry node = new Entry((K)stream.readObject()); + node.value = (V)stream.readObject(); if (last == null) root = node; else {