1039 public Iterator<E> descendingIterator() {
1040 if (m instanceof TreeMap)
1041 return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042 else
1043 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044 }
1045
1046 public int size() { return m.size(); }
1047 public boolean isEmpty() { return m.isEmpty(); }
1048 public boolean contains(Object o) { return m.containsKey(o); }
1049 public void clear() { m.clear(); }
1050 public E lower(E e) { return m.lowerKey(e); }
1051 public E floor(E e) { return m.floorKey(e); }
1052 public E ceiling(E e) { return m.ceilingKey(e); }
1053 public E higher(E e) { return m.higherKey(e); }
1054 public E first() { return m.firstKey(); }
1055 public E last() { return m.lastKey(); }
1056 public Comparator<? super E> comparator() { return m.comparator(); }
1057 public E pollFirst() {
1058 Map.Entry<E,Object> e = m.pollFirstEntry();
1059 return e == null? null : e.getKey();
1060 }
1061 public E pollLast() {
1062 Map.Entry<E,Object> e = m.pollLastEntry();
1063 return e == null? null : e.getKey();
1064 }
1065 public boolean remove(Object o) {
1066 int oldSize = size();
1067 m.remove(o);
1068 return size() != oldSize;
1069 }
1070 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071 E toElement, boolean toInclusive) {
1072 return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1073 toElement, toInclusive));
1074 }
1075 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076 return new KeySet<E>(m.headMap(toElement, inclusive));
1077 }
1078 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079 return new KeySet<E>(m.tailMap(fromElement, inclusive));
1080 }
1081 public SortedSet<E> subSet(E fromElement, E toElement) {
1082 return subSet(fromElement, true, toElement, false);
1083 }
1179 }
1180 public K next() {
1181 return prevEntry().key;
1182 }
1183 }
1184
1185 // Little utilities
1186
1187 /**
1188 * Compares two keys using the correct comparison method for this TreeMap.
1189 */
1190 final int compare(Object k1, Object k2) {
1191 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192 : comparator.compare((K)k1, (K)k2);
1193 }
1194
1195 /**
1196 * Test two values for equality. Differs from o1.equals(o2) only in
1197 * that it copes with {@code null} o1 properly.
1198 */
1199 final static boolean valEquals(Object o1, Object o2) {
1200 return (o1==null ? o2==null : o1.equals(o2));
1201 }
1202
1203 /**
1204 * Return SimpleImmutableEntry for entry, or null if null
1205 */
1206 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207 return e == null? null :
1208 new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209 }
1210
1211 /**
1212 * Return key for entry, or null if null
1213 */
1214 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215 return e == null? null : e.key;
1216 }
1217
1218 /**
1219 * Returns the key corresponding to the specified Entry.
1220 * @throws NoSuchElementException if the Entry is null
1221 */
1222 static <K> K key(Entry<K,?> e) {
1223 if (e==null)
1224 throw new NoSuchElementException();
1225 return e.key;
1226 }
1227
1228
1229 // SubMaps
1230
1231 /**
1232 * Dummy value serving as unmatchable fence key for unbounded
1233 * SubMapIterators
1234 */
1235 private static final Object UNBOUNDED = new Object();
1236
1237 /**
1238 * @serial include
1239 */
1240 static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241 implements NavigableMap<K,V>, java.io.Serializable {
1242 /**
1243 * The backing map.
1244 */
1245 final TreeMap<K,V> m;
1246
1247 /**
1248 * Endpoints are represented as triples (fromStart, lo,
1249 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250 * true, then the low (absolute) bound is the start of the
1251 * backing map, and the other values are ignored. Otherwise,
1252 * if loInclusive is true, lo is the inclusive bound, else lo
1253 * is the exclusive bound. Similarly for the upper bound.
1254 */
1255 final K lo, hi;
1256 final boolean fromStart, toEnd;
1257 final boolean loInclusive, hiInclusive;
1258
1259 NavigableSubMap(TreeMap<K,V> m,
1260 boolean fromStart, K lo, boolean loInclusive,
1395
1396 public boolean isEmpty() {
1397 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398 }
1399
1400 public int size() {
1401 return (fromStart && toEnd) ? m.size() : entrySet().size();
1402 }
1403
1404 public final boolean containsKey(Object key) {
1405 return inRange(key) && m.containsKey(key);
1406 }
1407
1408 public final V put(K key, V value) {
1409 if (!inRange(key))
1410 throw new IllegalArgumentException("key out of range");
1411 return m.put(key, value);
1412 }
1413
1414 public final V get(Object key) {
1415 return !inRange(key)? null : m.get(key);
1416 }
1417
1418 public final V remove(Object key) {
1419 return !inRange(key)? null : m.remove(key);
1420 }
1421
1422 public final Map.Entry<K,V> ceilingEntry(K key) {
1423 return exportEntry(subCeiling(key));
1424 }
1425
1426 public final K ceilingKey(K key) {
1427 return keyOrNull(subCeiling(key));
1428 }
1429
1430 public final Map.Entry<K,V> higherEntry(K key) {
1431 return exportEntry(subHigher(key));
1432 }
1433
1434 public final K higherKey(K key) {
1435 return keyOrNull(subHigher(key));
1436 }
1437
1438 public final Map.Entry<K,V> floorEntry(K key) {
1439 return exportEntry(subFloor(key));
1542 public boolean contains(Object o) {
1543 if (!(o instanceof Map.Entry))
1544 return false;
1545 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1546 K key = entry.getKey();
1547 if (!inRange(key))
1548 return false;
1549 TreeMap.Entry node = m.getEntry(key);
1550 return node != null &&
1551 valEquals(node.getValue(), entry.getValue());
1552 }
1553
1554 public boolean remove(Object o) {
1555 if (!(o instanceof Map.Entry))
1556 return false;
1557 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1558 K key = entry.getKey();
1559 if (!inRange(key))
1560 return false;
1561 TreeMap.Entry<K,V> node = m.getEntry(key);
1562 if (node!=null && valEquals(node.getValue(),entry.getValue())){
1563 m.deleteEntry(node);
1564 return true;
1565 }
1566 return false;
1567 }
1568 }
1569
1570 /**
1571 * Iterators for SubMaps
1572 */
1573 abstract class SubMapIterator<T> implements Iterator<T> {
1574 TreeMap.Entry<K,V> lastReturned;
1575 TreeMap.Entry<K,V> next;
1576 final Object fenceKey;
1577 int expectedModCount;
1578
1579 SubMapIterator(TreeMap.Entry<K,V> first,
1580 TreeMap.Entry<K,V> fence) {
1581 expectedModCount = m.modCount;
1582 lastReturned = null;
1707
1708 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1709 K toKey, boolean toInclusive) {
1710 if (!inRange(fromKey, fromInclusive))
1711 throw new IllegalArgumentException("fromKey out of range");
1712 if (!inRange(toKey, toInclusive))
1713 throw new IllegalArgumentException("toKey out of range");
1714 return new AscendingSubMap(m,
1715 false, fromKey, fromInclusive,
1716 false, toKey, toInclusive);
1717 }
1718
1719 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1720 if (!inRange(toKey, inclusive))
1721 throw new IllegalArgumentException("toKey out of range");
1722 return new AscendingSubMap(m,
1723 fromStart, lo, loInclusive,
1724 false, toKey, inclusive);
1725 }
1726
1727 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1728 if (!inRange(fromKey, inclusive))
1729 throw new IllegalArgumentException("fromKey out of range");
1730 return new AscendingSubMap(m,
1731 false, fromKey, inclusive,
1732 toEnd, hi, hiInclusive);
1733 }
1734
1735 public NavigableMap<K,V> descendingMap() {
1736 NavigableMap<K,V> mv = descendingMapView;
1737 return (mv != null) ? mv :
1738 (descendingMapView =
1739 new DescendingSubMap(m,
1740 fromStart, lo, loInclusive,
1741 toEnd, hi, hiInclusive));
1742 }
1743
1744 Iterator<K> keyIterator() {
1745 return new SubMapKeyIterator(absLowest(), absHighFence());
1746 }
1747
1788
1789 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1790 K toKey, boolean toInclusive) {
1791 if (!inRange(fromKey, fromInclusive))
1792 throw new IllegalArgumentException("fromKey out of range");
1793 if (!inRange(toKey, toInclusive))
1794 throw new IllegalArgumentException("toKey out of range");
1795 return new DescendingSubMap(m,
1796 false, toKey, toInclusive,
1797 false, fromKey, fromInclusive);
1798 }
1799
1800 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1801 if (!inRange(toKey, inclusive))
1802 throw new IllegalArgumentException("toKey out of range");
1803 return new DescendingSubMap(m,
1804 false, toKey, inclusive,
1805 toEnd, hi, hiInclusive);
1806 }
1807
1808 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1809 if (!inRange(fromKey, inclusive))
1810 throw new IllegalArgumentException("fromKey out of range");
1811 return new DescendingSubMap(m,
1812 fromStart, lo, loInclusive,
1813 false, fromKey, inclusive);
1814 }
1815
1816 public NavigableMap<K,V> descendingMap() {
1817 NavigableMap<K,V> mv = descendingMapView;
1818 return (mv != null) ? mv :
1819 (descendingMapView =
1820 new AscendingSubMap(m,
1821 fromStart, lo, loInclusive,
1822 toEnd, hi, hiInclusive));
1823 }
1824
1825 Iterator<K> keyIterator() {
1826 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1827 }
1828
2126 }
2127 setColor(parentOf(x), BLACK);
2128 setColor(parentOf(parentOf(x)), RED);
2129 rotateLeft(parentOf(parentOf(x)));
2130 }
2131 }
2132 }
2133 root.color = BLACK;
2134 }
2135
2136 /**
2137 * Delete node p, and then rebalance the tree.
2138 */
2139 private void deleteEntry(Entry<K,V> p) {
2140 modCount++;
2141 size--;
2142
2143 // If strictly internal, copy successor's element to p and then make p
2144 // point to successor.
2145 if (p.left != null && p.right != null) {
2146 Entry<K,V> s = successor (p);
2147 p.key = s.key;
2148 p.value = s.value;
2149 p = s;
2150 } // p has 2 children
2151
2152 // Start fixup at replacement node, if it exists.
2153 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2154
2155 if (replacement != null) {
2156 // Link replacement to parent
2157 replacement.parent = p.parent;
2158 if (p.parent == null)
2159 root = replacement;
2160 else if (p == p.parent.left)
2161 p.parent.left = replacement;
2162 else
2163 p.parent.right = replacement;
2164
2165 // Null out links so they are OK to use by fixAfterDeletion.
2166 p.left = p.right = p.parent = null;
|
1039 public Iterator<E> descendingIterator() {
1040 if (m instanceof TreeMap)
1041 return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042 else
1043 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044 }
1045
1046 public int size() { return m.size(); }
1047 public boolean isEmpty() { return m.isEmpty(); }
1048 public boolean contains(Object o) { return m.containsKey(o); }
1049 public void clear() { m.clear(); }
1050 public E lower(E e) { return m.lowerKey(e); }
1051 public E floor(E e) { return m.floorKey(e); }
1052 public E ceiling(E e) { return m.ceilingKey(e); }
1053 public E higher(E e) { return m.higherKey(e); }
1054 public E first() { return m.firstKey(); }
1055 public E last() { return m.lastKey(); }
1056 public Comparator<? super E> comparator() { return m.comparator(); }
1057 public E pollFirst() {
1058 Map.Entry<E,Object> e = m.pollFirstEntry();
1059 return (e == null) ? null : e.getKey();
1060 }
1061 public E pollLast() {
1062 Map.Entry<E,Object> e = m.pollLastEntry();
1063 return (e == null) ? null : e.getKey();
1064 }
1065 public boolean remove(Object o) {
1066 int oldSize = size();
1067 m.remove(o);
1068 return size() != oldSize;
1069 }
1070 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071 E toElement, boolean toInclusive) {
1072 return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1073 toElement, toInclusive));
1074 }
1075 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076 return new KeySet<E>(m.headMap(toElement, inclusive));
1077 }
1078 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079 return new KeySet<E>(m.tailMap(fromElement, inclusive));
1080 }
1081 public SortedSet<E> subSet(E fromElement, E toElement) {
1082 return subSet(fromElement, true, toElement, false);
1083 }
1179 }
1180 public K next() {
1181 return prevEntry().key;
1182 }
1183 }
1184
1185 // Little utilities
1186
1187 /**
1188 * Compares two keys using the correct comparison method for this TreeMap.
1189 */
1190 final int compare(Object k1, Object k2) {
1191 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192 : comparator.compare((K)k1, (K)k2);
1193 }
1194
1195 /**
1196 * Test two values for equality. Differs from o1.equals(o2) only in
1197 * that it copes with {@code null} o1 properly.
1198 */
1199 static final boolean valEquals(Object o1, Object o2) {
1200 return (o1==null ? o2==null : o1.equals(o2));
1201 }
1202
1203 /**
1204 * Return SimpleImmutableEntry for entry, or null if null
1205 */
1206 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207 return (e == null) ? null :
1208 new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209 }
1210
1211 /**
1212 * Return key for entry, or null if null
1213 */
1214 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215 return (e == null) ? null : e.key;
1216 }
1217
1218 /**
1219 * Returns the key corresponding to the specified Entry.
1220 * @throws NoSuchElementException if the Entry is null
1221 */
1222 static <K> K key(Entry<K,?> e) {
1223 if (e==null)
1224 throw new NoSuchElementException();
1225 return e.key;
1226 }
1227
1228
1229 // SubMaps
1230
1231 /**
1232 * Dummy value serving as unmatchable fence key for unbounded
1233 * SubMapIterators
1234 */
1235 private static final Object UNBOUNDED = new Object();
1236
1237 /**
1238 * @serial include
1239 */
1240 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241 implements NavigableMap<K,V>, java.io.Serializable {
1242 /**
1243 * The backing map.
1244 */
1245 final TreeMap<K,V> m;
1246
1247 /**
1248 * Endpoints are represented as triples (fromStart, lo,
1249 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250 * true, then the low (absolute) bound is the start of the
1251 * backing map, and the other values are ignored. Otherwise,
1252 * if loInclusive is true, lo is the inclusive bound, else lo
1253 * is the exclusive bound. Similarly for the upper bound.
1254 */
1255 final K lo, hi;
1256 final boolean fromStart, toEnd;
1257 final boolean loInclusive, hiInclusive;
1258
1259 NavigableSubMap(TreeMap<K,V> m,
1260 boolean fromStart, K lo, boolean loInclusive,
1395
1396 public boolean isEmpty() {
1397 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398 }
1399
1400 public int size() {
1401 return (fromStart && toEnd) ? m.size() : entrySet().size();
1402 }
1403
1404 public final boolean containsKey(Object key) {
1405 return inRange(key) && m.containsKey(key);
1406 }
1407
1408 public final V put(K key, V value) {
1409 if (!inRange(key))
1410 throw new IllegalArgumentException("key out of range");
1411 return m.put(key, value);
1412 }
1413
1414 public final V get(Object key) {
1415 return !inRange(key) ? null : m.get(key);
1416 }
1417
1418 public final V remove(Object key) {
1419 return !inRange(key) ? null : m.remove(key);
1420 }
1421
1422 public final Map.Entry<K,V> ceilingEntry(K key) {
1423 return exportEntry(subCeiling(key));
1424 }
1425
1426 public final K ceilingKey(K key) {
1427 return keyOrNull(subCeiling(key));
1428 }
1429
1430 public final Map.Entry<K,V> higherEntry(K key) {
1431 return exportEntry(subHigher(key));
1432 }
1433
1434 public final K higherKey(K key) {
1435 return keyOrNull(subHigher(key));
1436 }
1437
1438 public final Map.Entry<K,V> floorEntry(K key) {
1439 return exportEntry(subFloor(key));
1542 public boolean contains(Object o) {
1543 if (!(o instanceof Map.Entry))
1544 return false;
1545 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1546 K key = entry.getKey();
1547 if (!inRange(key))
1548 return false;
1549 TreeMap.Entry node = m.getEntry(key);
1550 return node != null &&
1551 valEquals(node.getValue(), entry.getValue());
1552 }
1553
1554 public boolean remove(Object o) {
1555 if (!(o instanceof Map.Entry))
1556 return false;
1557 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1558 K key = entry.getKey();
1559 if (!inRange(key))
1560 return false;
1561 TreeMap.Entry<K,V> node = m.getEntry(key);
1562 if (node!=null && valEquals(node.getValue(),
1563 entry.getValue())) {
1564 m.deleteEntry(node);
1565 return true;
1566 }
1567 return false;
1568 }
1569 }
1570
1571 /**
1572 * Iterators for SubMaps
1573 */
1574 abstract class SubMapIterator<T> implements Iterator<T> {
1575 TreeMap.Entry<K,V> lastReturned;
1576 TreeMap.Entry<K,V> next;
1577 final Object fenceKey;
1578 int expectedModCount;
1579
1580 SubMapIterator(TreeMap.Entry<K,V> first,
1581 TreeMap.Entry<K,V> fence) {
1582 expectedModCount = m.modCount;
1583 lastReturned = null;
1708
1709 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1710 K toKey, boolean toInclusive) {
1711 if (!inRange(fromKey, fromInclusive))
1712 throw new IllegalArgumentException("fromKey out of range");
1713 if (!inRange(toKey, toInclusive))
1714 throw new IllegalArgumentException("toKey out of range");
1715 return new AscendingSubMap(m,
1716 false, fromKey, fromInclusive,
1717 false, toKey, toInclusive);
1718 }
1719
1720 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1721 if (!inRange(toKey, inclusive))
1722 throw new IllegalArgumentException("toKey out of range");
1723 return new AscendingSubMap(m,
1724 fromStart, lo, loInclusive,
1725 false, toKey, inclusive);
1726 }
1727
1728 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1729 if (!inRange(fromKey, inclusive))
1730 throw new IllegalArgumentException("fromKey out of range");
1731 return new AscendingSubMap(m,
1732 false, fromKey, inclusive,
1733 toEnd, hi, hiInclusive);
1734 }
1735
1736 public NavigableMap<K,V> descendingMap() {
1737 NavigableMap<K,V> mv = descendingMapView;
1738 return (mv != null) ? mv :
1739 (descendingMapView =
1740 new DescendingSubMap(m,
1741 fromStart, lo, loInclusive,
1742 toEnd, hi, hiInclusive));
1743 }
1744
1745 Iterator<K> keyIterator() {
1746 return new SubMapKeyIterator(absLowest(), absHighFence());
1747 }
1748
1789
1790 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1791 K toKey, boolean toInclusive) {
1792 if (!inRange(fromKey, fromInclusive))
1793 throw new IllegalArgumentException("fromKey out of range");
1794 if (!inRange(toKey, toInclusive))
1795 throw new IllegalArgumentException("toKey out of range");
1796 return new DescendingSubMap(m,
1797 false, toKey, toInclusive,
1798 false, fromKey, fromInclusive);
1799 }
1800
1801 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1802 if (!inRange(toKey, inclusive))
1803 throw new IllegalArgumentException("toKey out of range");
1804 return new DescendingSubMap(m,
1805 false, toKey, inclusive,
1806 toEnd, hi, hiInclusive);
1807 }
1808
1809 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1810 if (!inRange(fromKey, inclusive))
1811 throw new IllegalArgumentException("fromKey out of range");
1812 return new DescendingSubMap(m,
1813 fromStart, lo, loInclusive,
1814 false, fromKey, inclusive);
1815 }
1816
1817 public NavigableMap<K,V> descendingMap() {
1818 NavigableMap<K,V> mv = descendingMapView;
1819 return (mv != null) ? mv :
1820 (descendingMapView =
1821 new AscendingSubMap(m,
1822 fromStart, lo, loInclusive,
1823 toEnd, hi, hiInclusive));
1824 }
1825
1826 Iterator<K> keyIterator() {
1827 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1828 }
1829
2127 }
2128 setColor(parentOf(x), BLACK);
2129 setColor(parentOf(parentOf(x)), RED);
2130 rotateLeft(parentOf(parentOf(x)));
2131 }
2132 }
2133 }
2134 root.color = BLACK;
2135 }
2136
2137 /**
2138 * Delete node p, and then rebalance the tree.
2139 */
2140 private void deleteEntry(Entry<K,V> p) {
2141 modCount++;
2142 size--;
2143
2144 // If strictly internal, copy successor's element to p and then make p
2145 // point to successor.
2146 if (p.left != null && p.right != null) {
2147 Entry<K,V> s = successor(p);
2148 p.key = s.key;
2149 p.value = s.value;
2150 p = s;
2151 } // p has 2 children
2152
2153 // Start fixup at replacement node, if it exists.
2154 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2155
2156 if (replacement != null) {
2157 // Link replacement to parent
2158 replacement.parent = p.parent;
2159 if (p.parent == null)
2160 root = replacement;
2161 else if (p == p.parent.left)
2162 p.parent.left = replacement;
2163 else
2164 p.parent.right = replacement;
2165
2166 // Null out links so they are OK to use by fixAfterDeletion.
2167 p.left = p.right = p.parent = null;
|