ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/TreeMap.java
(Generate patch)

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.34 by dl, Sun Apr 23 20:59:49 2006 UTC vs.
Revision 1.41 by jsr166, Sun Jan 7 07:38:27 2007 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
# Line 68 | Line 68 | package java.util;
68   * associated map using <tt>put</tt>.)
69   *
70   * <p>This class is a member of the
71 < * <a href="{@docRoot}/../guide/collections/index.html">
71 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
72   * Java Collections Framework</a>.
73   *
74   * @param <K> the type of keys maintained by this map
# Line 510 | Line 510 | public class TreeMap<K,V>
510      public V put(K key, V value) {
511          Entry<K,V> t = root;
512          if (t == null) {
513 <            compare(key, key); // type check
513 >            // TBD:
514 >            // 5045147: (coll) Adding null to an empty TreeSet should
515 >            // throw NullPointerException
516 >            //
517 >            // compare(key, key); // type check
518              root = new Entry<K,V>(key, value, null);
519              size = 1;
520              modCount++;
# Line 1046 | Line 1050 | public class TreeMap<K,V>
1050              return size() != oldSize;
1051          }
1052          public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1053 <                                      E toElement, boolean toInclusive) {
1053 >                                      E toElement,   boolean toInclusive) {
1054              return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1055                                             toElement,   toInclusive));
1056          }
# Line 1113 | Line 1117 | public class TreeMap<K,V>
1117                  throw new IllegalStateException();
1118              if (modCount != expectedModCount)
1119                  throw new ConcurrentModificationException();
1120 +            // deleted entries are replaced by their successors
1121              if (lastReturned.left != null && lastReturned.right != null)
1122                  next = lastReturned;
1123              deleteEntry(lastReturned);
1124 <            expectedModCount++;
1124 >            expectedModCount = modCount;
1125              lastReturned = null;
1126          }
1127      }
# Line 1203 | Line 1208 | public class TreeMap<K,V>
1208  
1209      // SubMaps
1210  
1211 +    /**
1212 +     * @serial include
1213 +     */
1214      static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1215          implements NavigableMap<K,V>, java.io.Serializable {
1216 <        /*
1216 >        /**
1217           * The backing map.
1218           */
1219          final TreeMap<K,V> m;
1220  
1221 <        /*
1221 >        /**
1222           * Endpoints are represented as triples (fromStart, lo,
1223           * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1224           * true, then the low (absolute) bound is the start of the
# Line 1218 | Line 1226 | public class TreeMap<K,V>
1226           * if loInclusive is true, lo is the inclusive bound, else lo
1227           * is the exclusive bound. Similarly for the upper bound.
1228           */
1221 –
1229          final K lo, hi;
1230          final boolean fromStart, toEnd;
1231          final boolean loInclusive, hiInclusive;
# Line 1343 | Line 1350 | public class TreeMap<K,V>
1350          }
1351  
1352          // Abstract methods defined in ascending vs descending classes
1353 <        // These relay to the appropriate  absolute versions
1353 >        // These relay to the appropriate absolute versions
1354  
1355          abstract TreeMap.Entry<K,V> subLowest();
1356          abstract TreeMap.Entry<K,V> subHighest();
# Line 1575 | Line 1582 | public class TreeMap<K,V>
1582                  return e;
1583              }
1584  
1585 <            public void remove() {
1585 >            final void removeAscending() {
1586                  if (lastReturned == null)
1587                      throw new IllegalStateException();
1588                  if (m.modCount != expectedModCount)
1589                      throw new ConcurrentModificationException();
1590 +                // deleted entries are replaced by their successors
1591                  if (lastReturned.left != null && lastReturned.right != null)
1592                      next = lastReturned;
1593                  m.deleteEntry(lastReturned);
1586 –                expectedModCount++;
1594                  lastReturned = null;
1595 +                expectedModCount = m.modCount;
1596 +            }
1597 +
1598 +            final void removeDescending() {
1599 +                if (lastReturned == null)
1600 +                    throw new IllegalStateException();
1601 +                if (m.modCount != expectedModCount)
1602 +                    throw new ConcurrentModificationException();
1603 +                m.deleteEntry(lastReturned);
1604 +                lastReturned = null;
1605 +                expectedModCount = m.modCount;
1606              }
1607 +
1608          }
1609  
1610          final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
# Line 1596 | Line 1615 | public class TreeMap<K,V>
1615              public Map.Entry<K,V> next() {
1616                  return nextEntry();
1617              }
1618 +            public void remove() {
1619 +                removeAscending();
1620 +            }
1621          }
1622  
1623          final class SubMapKeyIterator extends SubMapIterator<K> {
# Line 1606 | Line 1628 | public class TreeMap<K,V>
1628              public K next() {
1629                  return nextEntry().key;
1630              }
1631 +            public void remove() {
1632 +                removeAscending();
1633 +            }
1634          }
1635  
1636          final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
# Line 1617 | Line 1642 | public class TreeMap<K,V>
1642              public Map.Entry<K,V> next() {
1643                  return prevEntry();
1644              }
1645 +            public void remove() {
1646 +                removeDescending();
1647 +            }
1648          }
1649  
1650          final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
# Line 1627 | Line 1655 | public class TreeMap<K,V>
1655              public K next() {
1656                  return prevEntry().key;
1657              }
1658 +            public void remove() {
1659 +                removeDescending();
1660 +            }
1661          }
1662      }
1663  
1664 +    /**
1665 +     * @serial include
1666 +     */
1667      static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1668          private static final long serialVersionUID = 912986545866124060L;
1669  
1670          AscendingSubMap(TreeMap<K,V> m,
1671                          boolean fromStart, K lo, boolean loInclusive,
1672 <                        boolean toEnd, K hi, boolean hiInclusive) {
1672 >                        boolean toEnd,     K hi, boolean hiInclusive) {
1673              super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1674          }
1675  
# Line 1644 | Line 1678 | public class TreeMap<K,V>
1678          }
1679  
1680          public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1681 <                                        K toKey, boolean toInclusive) {
1681 >                                        K toKey,   boolean toInclusive) {
1682              if (!inRange(fromKey, fromInclusive))
1683                  throw new IllegalArgumentException("fromKey out of range");
1684              if (!inRange(toKey, toInclusive))
# Line 1655 | Line 1689 | public class TreeMap<K,V>
1689          }
1690  
1691          public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1692 <            if (!inClosedRange(toKey))
1692 >            if (!inRange(toKey, inclusive))
1693                  throw new IllegalArgumentException("toKey out of range");
1694              return new AscendingSubMap(m,
1695                                         fromStart, lo,    loInclusive,
# Line 1706 | Line 1740 | public class TreeMap<K,V>
1740          TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1741      }
1742  
1743 +    /**
1744 +     * @serial include
1745 +     */
1746      static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1747          private static final long serialVersionUID = 912986545866120460L;
1748          DescendingSubMap(TreeMap<K,V> m,
1749                          boolean fromStart, K lo, boolean loInclusive,
1750 <                        boolean toEnd, K hi, boolean hiInclusive) {
1750 >                        boolean toEnd,     K hi, boolean hiInclusive) {
1751              super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1752          }
1753  
# Line 1722 | Line 1759 | public class TreeMap<K,V>
1759          }
1760  
1761          public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1762 <                                        K toKey, boolean toInclusive) {
1762 >                                        K toKey,   boolean toInclusive) {
1763              if (!inRange(fromKey, fromInclusive))
1764                  throw new IllegalArgumentException("fromKey out of range");
1765              if (!inRange(toKey, toInclusive))
# Line 1790 | Line 1827 | public class TreeMap<K,V>
1827       * support NavigableMap.  It translates an old-version SubMap into
1828       * a new-version AscendingSubMap. This class is never otherwise
1829       * used.
1830 +     *
1831 +     * @serial include
1832       */
1833      private class SubMap extends AbstractMap<K,V>
1834          implements SortedMap<K,V>, java.io.Serializable {
# Line 1873 | Line 1912 | public class TreeMap<K,V>
1912          public boolean equals(Object o) {
1913              if (!(o instanceof Map.Entry))
1914                  return false;
1915 <            Map.Entry e = (Map.Entry)o;
1915 >            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1916  
1917              return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1918          }
# Line 2314 | Line 2353 | public class TreeMap<K,V>
2353  
2354          if (hi < lo) return null;
2355  
2356 <        int mid = (lo + hi) / 2;
2356 >        int mid = (lo + hi) >>> 1;
2357  
2358          Entry<K,V> left  = null;
2359          if (lo < mid)

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines