1054 public E first() { return m.firstKey(); } |
1054 public E first() { return m.firstKey(); } |
1055 public E last() { return m.lastKey(); } |
1055 public E last() { return m.lastKey(); } |
1056 public Comparator<? super E> comparator() { return m.comparator(); } |
1056 public Comparator<? super E> comparator() { return m.comparator(); } |
1057 public E pollFirst() { |
1057 public E pollFirst() { |
1058 Map.Entry<E,Object> e = m.pollFirstEntry(); |
1058 Map.Entry<E,Object> e = m.pollFirstEntry(); |
1059 return e == null? null : e.getKey(); |
1059 return (e == null) ? null : e.getKey(); |
1060 } |
1060 } |
1061 public E pollLast() { |
1061 public E pollLast() { |
1062 Map.Entry<E,Object> e = m.pollLastEntry(); |
1062 Map.Entry<E,Object> e = m.pollLastEntry(); |
1063 return e == null? null : e.getKey(); |
1063 return (e == null) ? null : e.getKey(); |
1064 } |
1064 } |
1065 public boolean remove(Object o) { |
1065 public boolean remove(Object o) { |
1066 int oldSize = size(); |
1066 int oldSize = size(); |
1067 m.remove(o); |
1067 m.remove(o); |
1068 return size() != oldSize; |
1068 return size() != oldSize; |
1194 |
1194 |
1195 /** |
1195 /** |
1196 * Test two values for equality. Differs from o1.equals(o2) only in |
1196 * Test two values for equality. Differs from o1.equals(o2) only in |
1197 * that it copes with {@code null} o1 properly. |
1197 * that it copes with {@code null} o1 properly. |
1198 */ |
1198 */ |
1199 final static boolean valEquals(Object o1, Object o2) { |
1199 static final boolean valEquals(Object o1, Object o2) { |
1200 return (o1==null ? o2==null : o1.equals(o2)); |
1200 return (o1==null ? o2==null : o1.equals(o2)); |
1201 } |
1201 } |
1202 |
1202 |
1203 /** |
1203 /** |
1204 * Return SimpleImmutableEntry for entry, or null if null |
1204 * Return SimpleImmutableEntry for entry, or null if null |
1205 */ |
1205 */ |
1206 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { |
1206 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { |
1207 return e == null? null : |
1207 return (e == null) ? null : |
1208 new AbstractMap.SimpleImmutableEntry<K,V>(e); |
1208 new AbstractMap.SimpleImmutableEntry<K,V>(e); |
1209 } |
1209 } |
1210 |
1210 |
1211 /** |
1211 /** |
1212 * Return key for entry, or null if null |
1212 * Return key for entry, or null if null |
1213 */ |
1213 */ |
1214 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) { |
1214 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) { |
1215 return e == null? null : e.key; |
1215 return (e == null) ? null : e.key; |
1216 } |
1216 } |
1217 |
1217 |
1218 /** |
1218 /** |
1219 * Returns the key corresponding to the specified Entry. |
1219 * Returns the key corresponding to the specified Entry. |
1220 * @throws NoSuchElementException if the Entry is null |
1220 * @throws NoSuchElementException if the Entry is null |
1235 private static final Object UNBOUNDED = new Object(); |
1235 private static final Object UNBOUNDED = new Object(); |
1236 |
1236 |
1237 /** |
1237 /** |
1238 * @serial include |
1238 * @serial include |
1239 */ |
1239 */ |
1240 static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> |
1240 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V> |
1241 implements NavigableMap<K,V>, java.io.Serializable { |
1241 implements NavigableMap<K,V>, java.io.Serializable { |
1242 /** |
1242 /** |
1243 * The backing map. |
1243 * The backing map. |
1244 */ |
1244 */ |
1245 final TreeMap<K,V> m; |
1245 final TreeMap<K,V> m; |
1410 throw new IllegalArgumentException("key out of range"); |
1410 throw new IllegalArgumentException("key out of range"); |
1411 return m.put(key, value); |
1411 return m.put(key, value); |
1412 } |
1412 } |
1413 |
1413 |
1414 public final V get(Object key) { |
1414 public final V get(Object key) { |
1415 return !inRange(key)? null : m.get(key); |
1415 return !inRange(key) ? null : m.get(key); |
1416 } |
1416 } |
1417 |
1417 |
1418 public final V remove(Object key) { |
1418 public final V remove(Object key) { |
1419 return !inRange(key)? null : m.remove(key); |
1419 return !inRange(key) ? null : m.remove(key); |
1420 } |
1420 } |
1421 |
1421 |
1422 public final Map.Entry<K,V> ceilingEntry(K key) { |
1422 public final Map.Entry<K,V> ceilingEntry(K key) { |
1423 return exportEntry(subCeiling(key)); |
1423 return exportEntry(subCeiling(key)); |
1424 } |
1424 } |
1557 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
1557 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
1558 K key = entry.getKey(); |
1558 K key = entry.getKey(); |
1559 if (!inRange(key)) |
1559 if (!inRange(key)) |
1560 return false; |
1560 return false; |
1561 TreeMap.Entry<K,V> node = m.getEntry(key); |
1561 TreeMap.Entry<K,V> node = m.getEntry(key); |
1562 if (node!=null && valEquals(node.getValue(),entry.getValue())){ |
1562 if (node!=null && valEquals(node.getValue(), |
|
1563 entry.getValue())) { |
1563 m.deleteEntry(node); |
1564 m.deleteEntry(node); |
1564 return true; |
1565 return true; |
1565 } |
1566 } |
1566 return false; |
1567 return false; |
1567 } |
1568 } |
1722 return new AscendingSubMap(m, |
1723 return new AscendingSubMap(m, |
1723 fromStart, lo, loInclusive, |
1724 fromStart, lo, loInclusive, |
1724 false, toKey, inclusive); |
1725 false, toKey, inclusive); |
1725 } |
1726 } |
1726 |
1727 |
1727 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){ |
1728 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
1728 if (!inRange(fromKey, inclusive)) |
1729 if (!inRange(fromKey, inclusive)) |
1729 throw new IllegalArgumentException("fromKey out of range"); |
1730 throw new IllegalArgumentException("fromKey out of range"); |
1730 return new AscendingSubMap(m, |
1731 return new AscendingSubMap(m, |
1731 false, fromKey, inclusive, |
1732 false, fromKey, inclusive, |
1732 toEnd, hi, hiInclusive); |
1733 toEnd, hi, hiInclusive); |
1803 return new DescendingSubMap(m, |
1804 return new DescendingSubMap(m, |
1804 false, toKey, inclusive, |
1805 false, toKey, inclusive, |
1805 toEnd, hi, hiInclusive); |
1806 toEnd, hi, hiInclusive); |
1806 } |
1807 } |
1807 |
1808 |
1808 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){ |
1809 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
1809 if (!inRange(fromKey, inclusive)) |
1810 if (!inRange(fromKey, inclusive)) |
1810 throw new IllegalArgumentException("fromKey out of range"); |
1811 throw new IllegalArgumentException("fromKey out of range"); |
1811 return new DescendingSubMap(m, |
1812 return new DescendingSubMap(m, |
1812 fromStart, lo, loInclusive, |
1813 fromStart, lo, loInclusive, |
1813 false, fromKey, inclusive); |
1814 false, fromKey, inclusive); |
2141 size--; |
2142 size--; |
2142 |
2143 |
2143 // If strictly internal, copy successor's element to p and then make p |
2144 // If strictly internal, copy successor's element to p and then make p |
2144 // point to successor. |
2145 // point to successor. |
2145 if (p.left != null && p.right != null) { |
2146 if (p.left != null && p.right != null) { |
2146 Entry<K,V> s = successor (p); |
2147 Entry<K,V> s = successor(p); |
2147 p.key = s.key; |
2148 p.key = s.key; |
2148 p.value = s.value; |
2149 p.value = s.value; |
2149 p = s; |
2150 p = s; |
2150 } // p has 2 children |
2151 } // p has 2 children |
2151 |
2152 |