harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r385545 - in /incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util: TreeMap.java TreeMapEntry.java TreeSet.java
Date Mon, 13 Mar 2006 13:30:45 GMT
Author: tellison
Date: Mon Mar 13 05:30:43 2006
New Revision: 385545

URL: http://svn.apache.org/viewcvs?rev=385545&view=rev
Log:
Fixes to TreeMap:
 - rename TreeMapEntry to inner Entry type
 - declare invariant fields as final 
 - update TreeSet to reflect modifications

Removed:
    incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMapEntry.java
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/viewcvs/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java?rev=385545&r1=385544&r2=385545&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
Mon Mar 13 05:30:43 2006
@@ -35,22 +35,50 @@
 
 	transient int size = 0;
 
-	transient TreeMapEntry root;
+	transient Entry root;
 
 	private Comparator comparator;
 
 	transient int modCount = 0;
 
+	/**
+	 * Entry is an internal class which is used to hold the entries of a
+	 * TreeMap.
+	 */
+	static class Entry extends MapEntry {
+		Entry parent, left, right;
+
+		boolean color;
+
+		Entry(Object key) {
+			super(key);
+		}
+
+		Entry(Object key, Object value) {
+			super(key, value);
+		}
+
+		Entry clone(Entry parent) {
+			Entry clone = (Entry) super.clone();
+			clone.parent = parent;
+			if (left != null)
+				clone.left = left.clone(clone);
+			if (right != null)
+				clone.right = right.clone(clone);
+			return clone;
+		}
+	}
+
 	private static final class TreeMapIterator implements Iterator {
-		private TreeMap backingMap;
+		private final TreeMap backingMap;
 
 		private int expectedModCount;
 
-		private MapEntry.Type type;
+		private final MapEntry.Type type;
 
 		private boolean hasEnd = false;
 
-		private TreeMapEntry node, lastNode;
+		private Entry node, lastNode;
 
 		private Object endKey;
 
@@ -62,8 +90,8 @@
 				node = TreeMap.minimum(map.root);
 		}
 
-		TreeMapIterator(TreeMap map, MapEntry.Type value,
-				TreeMapEntry startNode, boolean checkEnd, Object end) {
+		TreeMapIterator(TreeMap map, MapEntry.Type value, Entry startNode,
+				boolean checkEnd, Object end) {
 			backingMap = map;
 			type = value;
 			expectedModCount = map.modCount;
@@ -112,33 +140,33 @@
 	}
 
 	static final class SubMap extends AbstractMap implements SortedMap {
-		private TreeMap backingMap;
+		private final TreeMap backingMap;
 
 		private boolean hasStart, hasEnd;
 
 		private Object startKey, endKey;
 
 		static class SubMapSet extends AbstractSet implements Set {
-			TreeMap backingMap;
+			final TreeMap backingMap;
 
 			boolean hasStart, hasEnd;
 
 			Object startKey, endKey;
 
-			MapEntry.Type type;
+			final MapEntry.Type type;
 
-			SubMapSet() {
-				/*empty*/
+			SubMapSet(TreeMap map, MapEntry.Type theType) {
+				backingMap = map;
+				type = theType;
 			}
 
 			SubMapSet(boolean starting, Object start, TreeMap map,
 					boolean ending, Object end, MapEntry.Type theType) {
-				backingMap = map;
+				this(map, theType);
 				hasStart = starting;
 				startKey = start;
 				hasEnd = ending;
 				endKey = end;
-				type = theType;
 			}
 
 			void checkRange(Object key) {
@@ -158,18 +186,18 @@
 				}
 			}
 
-			boolean checkRange(Object key, boolean start, boolean end) {
+			boolean checkRange(Object key, boolean hasStart, boolean hasEnd) {
 				if (backingMap.comparator() == null) {
 					Comparable object = (Comparable) key;
-					if (start && object.compareTo(startKey) < 0)
+					if (hasStart && object.compareTo(startKey) < 0)
 						return false;
-					if (end && object.compareTo(endKey) >= 0)
+					if (hasEnd && object.compareTo(endKey) >= 0)
 						return false;
 				} else {
-					if (start
+					if (hasStart
 							&& backingMap.comparator().compare(key, startKey) < 0)
 						return false;
-					if (end
+					if (hasEnd
 							&& backingMap.comparator().compare(key, endKey) >= 0)
 						return false;
 				}
@@ -178,14 +206,14 @@
 
 			public boolean isEmpty() {
 				if (hasStart) {
-					TreeMapEntry 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() {
-				TreeMapEntry startNode;
+				TreeMap.Entry startNode;
 				if (hasStart) {
 					startNode = backingMap.findAfter(startKey);
 					if (startNode != null
@@ -246,17 +274,18 @@
 			}
 		}
 
-		private boolean checkRange(Object key, boolean start, boolean end) {
+		private boolean checkRange(Object key, boolean hasStart, boolean hasEnd) {
 			if (backingMap.comparator() == null) {
 				Comparable object = (Comparable) key;
-				if (start && object.compareTo(startKey) < 0)
+				if (hasStart && object.compareTo(startKey) < 0)
 					return false;
-				if (end && object.compareTo(endKey) >= 0)
+				if (hasEnd && object.compareTo(endKey) >= 0)
 					return false;
 			} else {
-				if (start && backingMap.comparator().compare(key, startKey) < 0)
+				if (hasStart
+						&& backingMap.comparator().compare(key, startKey) < 0)
 					return false;
-				if (end && backingMap.comparator().compare(key, endKey) >= 0)
+				if (hasEnd && backingMap.comparator().compare(key, endKey) >= 0)
 					return false;
 			}
 			return true;
@@ -293,7 +322,7 @@
 		public Object firstKey() {
 			if (!hasStart)
 				return backingMap.firstKey();
-			TreeMapEntry node = backingMap.findAfter(startKey);
+			TreeMap.Entry node = backingMap.findAfter(startKey);
 			if (node != null && checkRange(node.key, false, hasEnd))
 				return node.key;
 			throw new NoSuchElementException();
@@ -314,7 +343,7 @@
 
 		public boolean isEmpty() {
 			if (hasStart) {
-				TreeMapEntry node = backingMap.findAfter(startKey);
+				TreeMap.Entry node = backingMap.findAfter(startKey);
 				return node == null || !checkRange(node.key, false, hasEnd);
 			}
 			return backingMap.findBefore(endKey) == null;
@@ -339,7 +368,7 @@
 		public Object lastKey() {
 			if (!hasEnd)
 				return backingMap.lastKey();
-			TreeMapEntry node = backingMap.findBefore(endKey);
+			TreeMap.Entry node = backingMap.findBefore(endKey);
 			if (node != null && checkRange(node.key, hasStart, false))
 				return node.key;
 			throw new NoSuchElementException();
@@ -435,14 +464,12 @@
 		Iterator it = map.entrySet().iterator();
 		if (it.hasNext()) {
 			Map.Entry entry = (Map.Entry) it.next();
-			TreeMapEntry last = new TreeMapEntry(entry.getKey(), entry
-					.getValue());
+			Entry last = new Entry(entry.getKey(), entry.getValue());
 			root = last;
 			size = 1;
 			while (it.hasNext()) {
 				entry = (Map.Entry) it.next();
-				TreeMapEntry x = new TreeMapEntry(entry.getKey(), entry
-						.getValue());
+				Entry x = new Entry(entry.getKey(), entry.getValue());
 				x.parent = last;
 				last.right = x;
 				size++;
@@ -452,8 +479,8 @@
 		}
 	}
 
-	void balance(TreeMapEntry x) {
-		TreeMapEntry y;
+	void balance(Entry x) {
+		Entry y;
 		x.color = true;
 		while (x != root && x.parent.color) {
 			if (x.parent == x.parent.parent.left) {
@@ -565,7 +592,7 @@
 		return false;
 	}
 
-	private boolean containsValue(TreeMapEntry 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)
@@ -613,12 +640,12 @@
 		};
 	}
 
-	private TreeMapEntry find(Object key) {
+	private Entry find(Object key) {
 		int result;
 		Comparable object = null;
 		if (comparator == null)
 			object = (Comparable) key;
-		TreeMapEntry x = root;
+		Entry x = root;
 		while (x != null) {
 			result = object != null ? object.compareTo(x.key) : comparator
 					.compare(key, x.key);
@@ -629,12 +656,12 @@
 		return null;
 	}
 
-	TreeMapEntry findAfter(Object key) {
+	Entry findAfter(Object key) {
 		int result;
 		Comparable object = null;
 		if (comparator == null)
 			object = (Comparable) key;
-		TreeMapEntry x = root, last = null;
+		Entry x = root, last = null;
 		while (x != null) {
 			result = object != null ? object.compareTo(x.key) : comparator
 					.compare(key, x.key);
@@ -649,12 +676,12 @@
 		return last;
 	}
 
-	TreeMapEntry findBefore(Object key) {
+	Entry findBefore(Object key) {
 		int result;
 		Comparable object = null;
 		if (comparator == null)
 			object = (Comparable) key;
-		TreeMapEntry x = root, last = null;
+		Entry x = root, last = null;
 		while (x != null) {
 			result = object != null ? object.compareTo(x.key) : comparator
 					.compare(key, x.key);
@@ -682,8 +709,8 @@
 		throw new NoSuchElementException();
 	}
 
-	private void fixup(TreeMapEntry x) {
-		TreeMapEntry w;
+	private void fixup(Entry x) {
+		Entry w;
 		while (x != root && !x.color) {
 			if (x == x.parent.left) {
 				w = x.parent.right;
@@ -770,7 +797,7 @@
 	 *                when the key is null and the comparator cannot handle null
 	 */
 	public Object get(Object key) {
-		TreeMapEntry node = find(key);
+		Entry node = find(key);
 		if (node != null)
 			return node.value;
 		return null;
@@ -850,8 +877,8 @@
 		throw new NoSuchElementException();
 	}
 
-	private void leftRotate(TreeMapEntry x) {
-		TreeMapEntry y = x.right;
+	private void leftRotate(Entry x) {
+		Entry y = x.right;
 		x.right = y.left;
 		if (y.left != null)
 			y.left.parent = x;
@@ -868,22 +895,22 @@
 		x.parent = y;
 	}
 
-	static TreeMapEntry maximum(TreeMapEntry x) {
+	static Entry maximum(Entry x) {
 		while (x.right != null)
 			x = x.right;
 		return x;
 	}
 
-	static TreeMapEntry minimum(TreeMapEntry x) {
+	static Entry minimum(Entry x) {
 		while (x.left != null)
 			x = x.left;
 		return x;
 	}
 
-	static TreeMapEntry predecessor(TreeMapEntry x) {
+	static Entry predecessor(Entry x) {
 		if (x.left != null)
 			return maximum(x.left);
-		TreeMapEntry y = x.parent;
+		Entry y = x.parent;
 		while (y != null && x == y.left) {
 			x = y;
 			y = y.parent;
@@ -931,9 +958,9 @@
 		super.putAll(map);
 	}
 
-	void rbDelete(TreeMapEntry z) {
-		TreeMapEntry y = z.left == null || z.right == null ? z : successor(z);
-		TreeMapEntry 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)
@@ -956,12 +983,12 @@
 		size--;
 	}
 
-	private TreeMapEntry rbInsert(Object object) {
+	private Entry rbInsert(Object object) {
 		int result = 0;
 		Comparable key = null;
 		if (comparator == null)
 			key = (Comparable) object;
-		TreeMapEntry y = null, x = root;
+		Entry y = null, x = root;
 		while (x != null) {
 			y = x;
 			result = key != null ? key.compareTo(x.key) : comparator.compare(
@@ -973,7 +1000,7 @@
 
 		size++;
 		modCount++;
-		TreeMapEntry z = new TreeMapEntry(object);
+		Entry z = new Entry(object);
 		if (y == null)
 			return root = z;
 		z.parent = y;
@@ -1000,7 +1027,7 @@
 	 *                when the key is null and the comparator cannot handle null
 	 */
 	public Object remove(Object key) {
-		TreeMapEntry node = find(key);
+		Entry node = find(key);
 		if (node == null)
 			return null;
 		Object result = node.value;
@@ -1008,8 +1035,8 @@
 		return result;
 	}
 
-	private void rightRotate(TreeMapEntry x) {
-		TreeMapEntry y = x.left;
+	private void rightRotate(Entry x) {
+		Entry y = x.left;
 		x.left = y.right;
 		if (y.right != null)
 			y.right.parent = x;
@@ -1066,10 +1093,10 @@
 		throw new IllegalArgumentException();
 	}
 
-	static TreeMapEntry successor(TreeMapEntry x) {
+	static Entry successor(Entry x) {
 		if (x.right != null)
 			return minimum(x.right);
-		TreeMapEntry y = x.parent;
+		Entry y = x.parent;
 		while (y != null && x == y.right) {
 			x = y;
 			y = y.parent;
@@ -1142,7 +1169,7 @@
 		stream.defaultWriteObject();
 		stream.writeInt(size);
 		if (size > 0) {
-			TreeMapEntry node = minimum(root);
+			Entry node = minimum(root);
 			while (node != null) {
 				stream.writeObject(node.key);
 				stream.writeObject(node.value);
@@ -1155,9 +1182,9 @@
 			ClassNotFoundException {
 		stream.defaultReadObject();
 		size = stream.readInt();
-		TreeMapEntry last = null;
+		Entry last = null;
 		for (int i = size; --i >= 0;) {
-			TreeMapEntry node = new TreeMapEntry(stream.readObject());
+			Entry node = new Entry(stream.readObject());
 			node.value = stream.readObject();
 			if (last == null)
 				root = node;

Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeSet.java?rev=385545&r1=385544&r2=385545&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
Mon Mar 13 05:30:43 2006
@@ -36,32 +36,29 @@
 
 	private static final class SubSet extends TreeMap.SubMap.SubMapSet
 			implements SortedSet {
-		SubSet() {
-			type = new MapEntry.Type() {
+		private SubSet(TreeMap map) {
+			super(map, new MapEntry.Type() {
 				public Object get(MapEntry entry) {
 					return entry.key;
 				}
-			};
+			});
 		}
 
 		private SubSet(Object start, TreeMap map) {
-			this();
-			this.backingMap = map;
+			this(map);
 			hasStart = true;
 			startKey = start;
 		}
 
 		private SubSet(Object start, TreeMap map, Object end) {
-			this();
-			this.backingMap = map;
+			this(map);
 			hasStart = hasEnd = true;
 			startKey = start;
 			endKey = end;
 		}
 
 		private SubSet(TreeMap map, Object end) {
-			this();
-			this.backingMap = map;
+			this(map);
 			hasEnd = true;
 			endKey = end;
 		}
@@ -84,7 +81,7 @@
 		public Object first() {
 			if (!hasStart)
 				return this.backingMap.firstKey();
-			TreeMapEntry 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();
@@ -100,7 +97,7 @@
 		public Object last() {
 			if (!hasEnd)
 				return this.backingMap.lastKey();
-			TreeMapEntry 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();
@@ -182,12 +179,12 @@
 		Iterator it = set.iterator();
 		if (it.hasNext()) {
 			Object object = it.next();
-			TreeMapEntry last = new TreeMapEntry(object, object);
+			TreeMap.Entry last = new TreeMap.Entry(object, object);
 			backingMap.root = last;
 			backingMap.size = 1;
 			while (it.hasNext()) {
 				object = it.next();
-				TreeMapEntry x = new TreeMapEntry(object, object);
+				TreeMap.Entry x = new TreeMap.Entry(object, object);
 				x.parent = last;
 				last.right = x;
 				backingMap.size++;
@@ -454,7 +451,7 @@
 		stream.writeObject(backingMap.comparator());
 		stream.writeInt(backingMap.size);
 		if (backingMap.size > 0) {
-			TreeMapEntry node = TreeMap.minimum(backingMap.root);
+			TreeMap.Entry node = TreeMap.minimum(backingMap.root);
 			while (node != null) {
 				stream.writeObject(node.key);
 				node = TreeMap.successor(node);
@@ -467,9 +464,9 @@
 		stream.defaultReadObject();
 		backingMap = new TreeMap((Comparator) stream.readObject());
 		backingMap.size = stream.readInt();
-		TreeMapEntry last = null;
+		TreeMap.Entry last = null;
 		for (int i = backingMap.size; --i >= 0;) {
-			TreeMapEntry node = new TreeMapEntry(stream.readObject());
+			TreeMap.Entry node = new TreeMap.Entry(stream.readObject());
 			node.value = this;
 			if (last == null)
 				backingMap.root = node;



Mime
View raw message