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.44 by jsr166, Mon May 21 20:23:38 2007 UTC vs.
Revision 1.46 by jsr166, Sun May 18 23:59:57 2008 UTC

# Line 93 | Line 93 | package java.util;
93   * @param <V> the type of mapped values
94   *
95   * @author  Josh Bloch and Doug Lea
96 – * @version %I%, %G%
96   * @see Map
97   * @see HashMap
98   * @see Hashtable
# Line 237 | Line 236 | public class TreeMap<K,V>
236       *
237       * @param value value whose presence in this map is to be tested
238       * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
239 <     *         <tt>false</tt> otherwise
239 >     *         <tt>false</tt> otherwise
240       * @since 1.2
241       */
242      public boolean containsValue(Object value) {
# Line 309 | Line 308 | public class TreeMap<K,V>
308          if (size==0 && mapSize!=0 && map instanceof SortedMap) {
309              Comparator c = ((SortedMap)map).comparator();
310              if (c == comparator || (c != null && c.equals(comparator))) {
311 <                ++modCount;
312 <                try {
313 <                    buildFromSorted(mapSize, map.entrySet().iterator(),
314 <                                    null, null);
315 <                } catch (java.io.IOException cannotHappen) {
316 <                } catch (ClassNotFoundException cannotHappen) {
317 <                }
318 <                return;
311 >                ++modCount;
312 >                try {
313 >                    buildFromSorted(mapSize, map.entrySet().iterator(),
314 >                                    null, null);
315 >                } catch (java.io.IOException cannotHappen) {
316 >                } catch (ClassNotFoundException cannotHappen) {
317 >                }
318 >                return;
319              }
320          }
321          super.putAll(map);
# Line 340 | Line 339 | public class TreeMap<K,V>
339              return getEntryUsingComparator(key);
340          if (key == null)
341              throw new NullPointerException();
342 <        Comparable<? super K> k = (Comparable<? super K>) key;
342 >        Comparable<? super K> k = (Comparable<? super K>) key;
343          Entry<K,V> p = root;
344          while (p != null) {
345              int cmp = k.compareTo(p.key);
# Line 361 | Line 360 | public class TreeMap<K,V>
360       * worthwhile here.)
361       */
362      final Entry<K,V> getEntryUsingComparator(Object key) {
363 <        K k = (K) key;
363 >        K k = (K) key;
364          Comparator<? super K> cpr = comparator;
365          if (cpr != null) {
366              Entry<K,V> p = root;
# Line 528 | Line 527 | public class TreeMap<K,V>
527      public V put(K key, V value) {
528          Entry<K,V> t = root;
529          if (t == null) {
530 <            // TBD:
531 <            // 5045147: (coll) Adding null to an empty TreeSet should
532 <            // throw NullPointerException
533 <            //
534 <            // compare(key, key); // type check
530 >            // TBD:
531 >            // 5045147: (coll) Adding null to an empty TreeSet should
532 >            // throw NullPointerException
533 >            //
534 >            // compare(key, key); // type check
535              root = new Entry<K,V>(key, value, null);
536              size = 1;
537              modCount++;
# Line 1110 | Line 1109 | public class TreeMap<K,V>
1109              return next != null;
1110          }
1111  
1112 <        final Entry<K,V> nextEntry() {
1112 >        final Entry<K,V> nextEntry() {
1113              Entry<K,V> e = next;
1114              if (e == null)
1115                  throw new NoSuchElementException();
# Line 1318 | Line 1317 | public class TreeMap<K,V>
1317           */
1318  
1319          final TreeMap.Entry<K,V> absLowest() {
1320 <            TreeMap.Entry<K,V> e =
1320 >            TreeMap.Entry<K,V> e =
1321                  (fromStart ?  m.getFirstEntry() :
1322                   (loInclusive ? m.getCeilingEntry(lo) :
1323                                  m.getHigherEntry(lo)));
# Line 1326 | Line 1325 | public class TreeMap<K,V>
1325          }
1326  
1327          final TreeMap.Entry<K,V> absHighest() {
1328 <            TreeMap.Entry<K,V> e =
1328 >            TreeMap.Entry<K,V> e =
1329                  (toEnd ?  m.getLastEntry() :
1330                   (hiInclusive ?  m.getFloorEntry(hi) :
1331                                   m.getLowerEntry(hi)));
# Line 1336 | Line 1335 | public class TreeMap<K,V>
1335          final TreeMap.Entry<K,V> absCeiling(K key) {
1336              if (tooLow(key))
1337                  return absLowest();
1338 <            TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1338 >            TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1339              return (e == null || tooHigh(e.key)) ? null : e;
1340          }
1341  
1342          final TreeMap.Entry<K,V> absHigher(K key) {
1343              if (tooLow(key))
1344                  return absLowest();
1345 <            TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1345 >            TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1346              return (e == null || tooHigh(e.key)) ? null : e;
1347          }
1348  
1349          final TreeMap.Entry<K,V> absFloor(K key) {
1350              if (tooHigh(key))
1351                  return absHighest();
1352 <            TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1352 >            TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1353              return (e == null || tooLow(e.key)) ? null : e;
1354          }
1355  
1356          final TreeMap.Entry<K,V> absLower(K key) {
1357              if (tooHigh(key))
1358                  return absHighest();
1359 <            TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1359 >            TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1360              return (e == null || tooLow(e.key)) ? null : e;
1361          }
1362  
# Line 1468 | Line 1467 | public class TreeMap<K,V>
1467          }
1468  
1469          public final Map.Entry<K,V> pollFirstEntry() {
1470 <            TreeMap.Entry<K,V> e = subLowest();
1470 >            TreeMap.Entry<K,V> e = subLowest();
1471              Map.Entry<K,V> result = exportEntry(e);
1472              if (e != null)
1473                  m.deleteEntry(e);
# Line 1476 | Line 1475 | public class TreeMap<K,V>
1475          }
1476  
1477          public final Map.Entry<K,V> pollLastEntry() {
1478 <            TreeMap.Entry<K,V> e = subHighest();
1478 >            TreeMap.Entry<K,V> e = subHighest();
1479              Map.Entry<K,V> result = exportEntry(e);
1480              if (e != null)
1481                  m.deleteEntry(e);
# Line 1595 | Line 1594 | public class TreeMap<K,V>
1594                  if (m.modCount != expectedModCount)
1595                      throw new ConcurrentModificationException();
1596                  next = successor(e);
1597 <                lastReturned = e;
1597 >                lastReturned = e;
1598                  return e;
1599              }
1600  
# Line 1606 | Line 1605 | public class TreeMap<K,V>
1605                  if (m.modCount != expectedModCount)
1606                      throw new ConcurrentModificationException();
1607                  next = predecessor(e);
1608 <                lastReturned = e;
1608 >                lastReturned = e;
1609                  return e;
1610              }
1611  
# Line 1859 | Line 1858 | public class TreeMap<K,V>
1858       * @serial include
1859       */
1860      private class SubMap extends AbstractMap<K,V>
1861 <        implements SortedMap<K,V>, java.io.Serializable {
1861 >        implements SortedMap<K,V>, java.io.Serializable {
1862          private static final long serialVersionUID = -6520786458950516097L;
1863          private boolean fromStart = false, toEnd = false;
1864          private K fromKey, toKey;
# Line 1889 | Line 1888 | public class TreeMap<K,V>
1888       */
1889  
1890      static final class Entry<K,V> implements Map.Entry<K,V> {
1891 <        K key;
1891 >        K key;
1892          V value;
1893          Entry<K,V> left = null;
1894          Entry<K,V> right = null;
# Line 2044 | Line 2043 | public class TreeMap<K,V>
2043  
2044      private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2045          if (p != null)
2046 <            p.color = c;
2046 >            p.color = c;
2047      }
2048  
2049      private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
# Line 2300 | Line 2299 | public class TreeMap<K,V>
2299  
2300      /** Intended to be called only from TreeSet.addAll */
2301      void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2302 <        try {
2303 <            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304 <        } catch (java.io.IOException cannotHappen) {
2305 <        } catch (ClassNotFoundException cannotHappen) {
2306 <        }
2302 >        try {
2303 >            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304 >        } catch (java.io.IOException cannotHappen) {
2305 >        } catch (ClassNotFoundException cannotHappen) {
2306 >        }
2307      }
2308  
2309  
# Line 2339 | Line 2338 | public class TreeMap<K,V>
2338       *         This cannot occur if str is null.
2339       */
2340      private void buildFromSorted(int size, Iterator it,
2341 <                                 java.io.ObjectInputStream str,
2342 <                                 V defaultVal)
2341 >                                 java.io.ObjectInputStream str,
2342 >                                 V defaultVal)
2343          throws  java.io.IOException, ClassNotFoundException {
2344          this.size = size;
2345          root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2346 <                               it, str, defaultVal);
2346 >                               it, str, defaultVal);
2347      }
2348  
2349      /**
# Line 2362 | Line 2361 | public class TreeMap<K,V>
2361       *        Must be equal to computeRedLevel for tree of this size.
2362       */
2363      private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2364 <                                             int redLevel,
2365 <                                             Iterator it,
2366 <                                             java.io.ObjectInputStream str,
2367 <                                             V defaultVal)
2364 >                                             int redLevel,
2365 >                                             Iterator it,
2366 >                                             java.io.ObjectInputStream str,
2367 >                                             V defaultVal)
2368          throws  java.io.IOException, ClassNotFoundException {
2369          /*
2370           * Strategy: The root is the middlemost element. To get to it, we
# Line 2386 | Line 2385 | public class TreeMap<K,V>
2385          Entry<K,V> left  = null;
2386          if (lo < mid)
2387              left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2388 <                                   it, str, defaultVal);
2388 >                                   it, str, defaultVal);
2389  
2390          // extract key and/or value from iterator or stream
2391          K key;
# Line 2418 | Line 2417 | public class TreeMap<K,V>
2417  
2418          if (mid < hi) {
2419              Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2420 <                                               it, str, defaultVal);
2420 >                                               it, str, defaultVal);
2421              middle.right = right;
2422              right.parent = middle;
2423          }

Diff Legend

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