Return-Path: Delivered-To: apmail-incubator-harmony-commits-archive@www.apache.org Received: (qmail 34329 invoked from network); 13 Mar 2006 13:31:23 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 13 Mar 2006 13:31:23 -0000 Received: (qmail 58111 invoked by uid 500); 13 Mar 2006 13:31:23 -0000 Delivered-To: apmail-incubator-harmony-commits-archive@incubator.apache.org Received: (qmail 58026 invoked by uid 500); 13 Mar 2006 13:31:22 -0000 Mailing-List: contact harmony-commits-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: harmony-dev@incubator.apache.org Delivered-To: mailing list harmony-commits@incubator.apache.org Received: (qmail 58014 invoked by uid 99); 13 Mar 2006 13:31:22 -0000 X-ASF-Spam-Status: No, hits=-9.4 required=10.0 tests=ALL_TRUSTED,NO_REAL_NAME X-Spam-Check-By: apache.org Received: from [209.237.227.194] (HELO minotaur.apache.org) (209.237.227.194) by apache.org (qpsmtpd/0.29) with SMTP; Mon, 13 Mar 2006 05:31:21 -0800 Received: (qmail 34059 invoked by uid 65534); 13 Mar 2006 13:30:46 -0000 Message-ID: <20060313133046.34058.qmail@minotaur.apache.org> Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: harmony-commits@incubator.apache.org From: tellison@apache.org X-Mailer: svnmailer-1.0.7 X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N 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;