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.45 by jsr166, Sun May 18 23:47:56 2008 UTC

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

Diff Legend

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