harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ghar...@apache.org
Subject svn commit: r417719 - in /incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util: TreeMap.java TreeSet.java
Date Wed, 28 Jun 2006 10:56:44 GMT
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;
 	}
 }



Mime
View raw message