--- jsr166/src/main/java/util/TreeMap.java 2007/01/30 03:54:29 1.42 +++ jsr166/src/main/java/util/TreeMap.java 2010/10/22 05:18:30 1.53 @@ -1,8 +1,26 @@ /* - * %W% %E% + * Copyright (c) 1997, 2008, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright 2007 Sun Microsystems, Inc. All rights reserved. - * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. */ package java.util; @@ -75,7 +93,6 @@ package java.util; * @param the type of mapped values * * @author Josh Bloch and Doug Lea - * @version %I%, %G% * @see Map * @see HashMap * @see Hashtable @@ -219,7 +236,7 @@ public class TreeMap * * @param value value whose presence in this map is to be tested * @return true if a mapping to value exists; - * false otherwise + * false otherwise * @since 1.2 */ public boolean containsValue(Object value) { @@ -291,14 +308,14 @@ public class TreeMap if (size==0 && mapSize!=0 && map instanceof SortedMap) { Comparator c = ((SortedMap)map).comparator(); if (c == comparator || (c != null && c.equals(comparator))) { - ++modCount; - try { - buildFromSorted(mapSize, map.entrySet().iterator(), - null, null); - } catch (java.io.IOException cannotHappen) { - } catch (ClassNotFoundException cannotHappen) { - } - return; + ++modCount; + try { + buildFromSorted(mapSize, map.entrySet().iterator(), + null, null); + } catch (java.io.IOException cannotHappen) { + } catch (ClassNotFoundException cannotHappen) { + } + return; } } super.putAll(map); @@ -322,7 +339,7 @@ public class TreeMap return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); - Comparable k = (Comparable) key; + Comparable k = (Comparable) key; Entry p = root; while (p != null) { int cmp = k.compareTo(p.key); @@ -343,7 +360,7 @@ public class TreeMap * worthwhile here.) */ final Entry getEntryUsingComparator(Object key) { - K k = (K) key; + K k = (K) key; Comparator cpr = comparator; if (cpr != null) { Entry p = root; @@ -510,11 +527,11 @@ public class TreeMap public V put(K key, V value) { Entry t = root; if (t == null) { - // TBD: - // 5045147: (coll) Adding null to an empty TreeSet should - // throw NullPointerException - // - // compare(key, key); // type check + // TBD: + // 5045147: (coll) Adding null to an empty TreeSet should + // throw NullPointerException + // + // compare(key, key); // type check root = new Entry(key, value, null); size = 1; modCount++; @@ -1004,7 +1021,7 @@ public class TreeMap } Iterator descendingKeyIterator() { - return new DescendingKeyIterator(getFirstEntry()); + return new DescendingKeyIterator(getLastEntry()); } static final class KeySet extends AbstractSet implements NavigableSet { @@ -1038,11 +1055,11 @@ public class TreeMap public Comparator comparator() { return m.comparator(); } public E pollFirst() { Map.Entry e = m.pollFirstEntry(); - return e == null? null : e.getKey(); + return (e == null) ? null : e.getKey(); } public E pollLast() { Map.Entry e = m.pollLastEntry(); - return e == null? null : e.getKey(); + return (e == null) ? null : e.getKey(); } public boolean remove(Object o) { int oldSize = size(); @@ -1051,14 +1068,14 @@ public class TreeMap } public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { - return new TreeSet(m.subMap(fromElement, fromInclusive, - toElement, toInclusive)); + return new KeySet(m.subMap(fromElement, fromInclusive, + toElement, toInclusive)); } public NavigableSet headSet(E toElement, boolean inclusive) { - return new TreeSet(m.headMap(toElement, inclusive)); + return new KeySet(m.headMap(toElement, inclusive)); } public NavigableSet tailSet(E fromElement, boolean inclusive) { - return new TreeSet(m.tailMap(fromElement, inclusive)); + return new KeySet(m.tailMap(fromElement, inclusive)); } public SortedSet subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); @@ -1070,7 +1087,7 @@ public class TreeMap return tailSet(fromElement, true); } public NavigableSet descendingSet() { - return new TreeSet(m.descendingMap()); + return new KeySet(m.descendingMap()); } } @@ -1092,23 +1109,25 @@ public class TreeMap return next != null; } - final Entry nextEntry() { - Entry e = lastReturned = next; + final Entry nextEntry() { + Entry e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); + lastReturned = e; return e; } final Entry prevEntry() { - Entry e = lastReturned= next; + Entry e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); + lastReturned = e; return e; } @@ -1176,7 +1195,7 @@ public class TreeMap * Test two values for equality. Differs from o1.equals(o2) only in * that it copes with null o1 properly. */ - final static boolean valEquals(Object o1, Object o2) { + static final boolean valEquals(Object o1, Object o2) { return (o1==null ? o2==null : o1.equals(o2)); } @@ -1184,7 +1203,7 @@ public class TreeMap * Return SimpleImmutableEntry for entry, or null if null */ static Map.Entry exportEntry(TreeMap.Entry e) { - return e == null? null : + return (e == null) ? null : new AbstractMap.SimpleImmutableEntry(e); } @@ -1192,7 +1211,7 @@ public class TreeMap * Return key for entry, or null if null */ static K keyOrNull(TreeMap.Entry e) { - return e == null? null : e.key; + return (e == null) ? null : e.key; } /** @@ -1217,7 +1236,7 @@ public class TreeMap /** * @serial include */ - static abstract class NavigableSubMap extends AbstractMap + abstract static class NavigableSubMap extends AbstractMap implements NavigableMap, java.io.Serializable { /** * The backing map. @@ -1298,7 +1317,7 @@ public class TreeMap */ final TreeMap.Entry absLowest() { - TreeMap.Entry e = + TreeMap.Entry e = (fromStart ? m.getFirstEntry() : (loInclusive ? m.getCeilingEntry(lo) : m.getHigherEntry(lo))); @@ -1306,7 +1325,7 @@ public class TreeMap } final TreeMap.Entry absHighest() { - TreeMap.Entry e = + TreeMap.Entry e = (toEnd ? m.getLastEntry() : (hiInclusive ? m.getFloorEntry(hi) : m.getLowerEntry(hi))); @@ -1316,28 +1335,28 @@ public class TreeMap final TreeMap.Entry absCeiling(K key) { if (tooLow(key)) return absLowest(); - TreeMap.Entry e = m.getCeilingEntry(key); + TreeMap.Entry e = m.getCeilingEntry(key); return (e == null || tooHigh(e.key)) ? null : e; } final TreeMap.Entry absHigher(K key) { if (tooLow(key)) return absLowest(); - TreeMap.Entry e = m.getHigherEntry(key); + TreeMap.Entry e = m.getHigherEntry(key); return (e == null || tooHigh(e.key)) ? null : e; } final TreeMap.Entry absFloor(K key) { if (tooHigh(key)) return absHighest(); - TreeMap.Entry e = m.getFloorEntry(key); + TreeMap.Entry e = m.getFloorEntry(key); return (e == null || tooLow(e.key)) ? null : e; } final TreeMap.Entry absLower(K key) { if (tooHigh(key)) return absHighest(); - TreeMap.Entry e = m.getLowerEntry(key); + TreeMap.Entry e = m.getLowerEntry(key); return (e == null || tooLow(e.key)) ? null : e; } @@ -1392,11 +1411,11 @@ public class TreeMap } public final V get(Object key) { - return !inRange(key)? null : m.get(key); + return !inRange(key) ? null : m.get(key); } public final V remove(Object key) { - return !inRange(key)? null : m.remove(key); + return !inRange(key) ? null : m.remove(key); } public final Map.Entry ceilingEntry(K key) { @@ -1448,7 +1467,7 @@ public class TreeMap } public final Map.Entry pollFirstEntry() { - TreeMap.Entry e = subLowest(); + TreeMap.Entry e = subLowest(); Map.Entry result = exportEntry(e); if (e != null) m.deleteEntry(e); @@ -1456,7 +1475,7 @@ public class TreeMap } public final Map.Entry pollLastEntry() { - TreeMap.Entry e = subHighest(); + TreeMap.Entry e = subHighest(); Map.Entry result = exportEntry(e); if (e != null) m.deleteEntry(e); @@ -1539,7 +1558,8 @@ public class TreeMap if (!inRange(key)) return false; TreeMap.Entry node = m.getEntry(key); - if (node!=null && valEquals(node.getValue(),entry.getValue())){ + if (node!=null && valEquals(node.getValue(), + entry.getValue())) { m.deleteEntry(node); return true; } @@ -1569,22 +1589,24 @@ public class TreeMap } final TreeMap.Entry nextEntry() { - TreeMap.Entry e = lastReturned = next; + TreeMap.Entry e = next; if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); + lastReturned = e; return e; } final TreeMap.Entry prevEntry() { - TreeMap.Entry e = lastReturned = next; + TreeMap.Entry e = next; if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); + lastReturned = e; return e; } @@ -1702,7 +1724,7 @@ public class TreeMap false, toKey, inclusive); } - public NavigableMap tailMap(K fromKey, boolean inclusive){ + public NavigableMap tailMap(K fromKey, boolean inclusive) { if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); return new AscendingSubMap(m, @@ -1783,7 +1805,7 @@ public class TreeMap toEnd, hi, hiInclusive); } - public NavigableMap tailMap(K fromKey, boolean inclusive){ + public NavigableMap tailMap(K fromKey, boolean inclusive) { if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); return new DescendingSubMap(m, @@ -1837,7 +1859,7 @@ public class TreeMap * @serial include */ private class SubMap extends AbstractMap - implements SortedMap, java.io.Serializable { + implements SortedMap, java.io.Serializable { private static final long serialVersionUID = -6520786458950516097L; private boolean fromStart = false, toEnd = false; private K fromKey, toKey; @@ -1867,7 +1889,7 @@ public class TreeMap */ static final class Entry implements Map.Entry { - K key; + K key; V value; Entry left = null; Entry right = null; @@ -2022,7 +2044,7 @@ public class TreeMap private static void setColor(Entry p, boolean c) { if (p != null) - p.color = c; + p.color = c; } private static Entry leftOf(Entry p) { @@ -2121,7 +2143,7 @@ public class TreeMap // If strictly internal, copy successor's element to p and then make p // point to successor. if (p.left != null && p.right != null) { - Entry s = successor (p); + Entry s = successor(p); p.key = s.key; p.value = s.value; p = s; @@ -2278,11 +2300,11 @@ public class TreeMap /** Intended to be called only from TreeSet.addAll */ void addAllForTreeSet(SortedSet set, V defaultVal) { - try { - buildFromSorted(set.size(), set.iterator(), null, defaultVal); - } catch (java.io.IOException cannotHappen) { - } catch (ClassNotFoundException cannotHappen) { - } + try { + buildFromSorted(set.size(), set.iterator(), null, defaultVal); + } catch (java.io.IOException cannotHappen) { + } catch (ClassNotFoundException cannotHappen) { + } } @@ -2317,12 +2339,12 @@ public class TreeMap * This cannot occur if str is null. */ private void buildFromSorted(int size, Iterator it, - java.io.ObjectInputStream str, - V defaultVal) + java.io.ObjectInputStream str, + V defaultVal) throws java.io.IOException, ClassNotFoundException { this.size = size; root = buildFromSorted(0, 0, size-1, computeRedLevel(size), - it, str, defaultVal); + it, str, defaultVal); } /** @@ -2340,10 +2362,10 @@ public class TreeMap * Must be equal to computeRedLevel for tree of this size. */ private final Entry buildFromSorted(int level, int lo, int hi, - int redLevel, - Iterator it, - java.io.ObjectInputStream str, - V defaultVal) + int redLevel, + Iterator it, + java.io.ObjectInputStream str, + V defaultVal) throws java.io.IOException, ClassNotFoundException { /* * Strategy: The root is the middlemost element. To get to it, we @@ -2364,7 +2386,7 @@ public class TreeMap Entry left = null; if (lo < mid) left = buildFromSorted(level+1, lo, mid - 1, redLevel, - it, str, defaultVal); + it, str, defaultVal); // extract key and/or value from iterator or stream K key; @@ -2396,7 +2418,7 @@ public class TreeMap if (mid < hi) { Entry right = buildFromSorted(level+1, mid+1, hi, redLevel, - it, str, defaultVal); + it, str, defaultVal); middle.right = right; right.parent = middle; }