1322 static <K> K key(Entry<K,?> e) {
1323 if (e==null)
1324 throw new NoSuchElementException();
1325 return e.key;
1326 }
1327
1328
1329 // SubMaps
1330
1331 /**
1332 * Dummy value serving as unmatchable fence key for unbounded
1333 * SubMapIterators
1334 */
1335 private static final Object UNBOUNDED = new Object();
1336
1337 /**
1338 * @serial include
1339 */
1340 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1341 implements NavigableMap<K,V>, java.io.Serializable {
1342 private static final long serialVersionUID = -2102997345730753016L;
1343 /**
1344 * The backing map.
1345 */
1346 final TreeMap<K,V> m;
1347
1348 /**
1349 * Endpoints are represented as triples (fromStart, lo,
1350 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1351 * true, then the low (absolute) bound is the start of the
1352 * backing map, and the other values are ignored. Otherwise,
1353 * if loInclusive is true, lo is the inclusive bound, else lo
1354 * is the exclusive bound. Similarly for the upper bound.
1355 */
1356 final K lo, hi;
1357 final boolean fromStart, toEnd;
1358 final boolean loInclusive, hiInclusive;
1359
1360 NavigableSubMap(TreeMap<K,V> m,
1361 boolean fromStart, K lo, boolean loInclusive,
1827 public boolean tryAdvance(Consumer<? super K> action) {
1828 if (hasNext()) {
1829 action.accept(next());
1830 return true;
1831 }
1832 return false;
1833 }
1834 public long estimateSize() {
1835 return Long.MAX_VALUE;
1836 }
1837 public int characteristics() {
1838 return Spliterator.DISTINCT | Spliterator.ORDERED;
1839 }
1840 }
1841 }
1842
1843 /**
1844 * @serial include
1845 */
1846 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1847 private static final long serialVersionUID = 912986545866124060L;
1848
1849 AscendingSubMap(TreeMap<K,V> m,
1850 boolean fromStart, K lo, boolean loInclusive,
1851 boolean toEnd, K hi, boolean hiInclusive) {
1852 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1853 }
1854
1855 public Comparator<? super K> comparator() {
1856 return m.comparator();
1857 }
1858
1859 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1860 K toKey, boolean toInclusive) {
1861 if (!inRange(fromKey, fromInclusive))
1862 throw new IllegalArgumentException("fromKey out of range");
1863 if (!inRange(toKey, toInclusive))
1864 throw new IllegalArgumentException("toKey out of range");
1865 return new AscendingSubMap<>(m,
1866 false, fromKey, fromInclusive,
1910 }
1911 }
1912
1913 public Set<Map.Entry<K,V>> entrySet() {
1914 EntrySetView es = entrySetView;
1915 return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
1916 }
1917
1918 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1919 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1920 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1921 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1922 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1923 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1924 }
1925
1926 /**
1927 * @serial include
1928 */
1929 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1930 private static final long serialVersionUID = 912986545866120460L;
1931 DescendingSubMap(TreeMap<K,V> m,
1932 boolean fromStart, K lo, boolean loInclusive,
1933 boolean toEnd, K hi, boolean hiInclusive) {
1934 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1935 }
1936
1937 private final Comparator<? super K> reverseComparator =
1938 Collections.reverseOrder(m.comparator);
1939
1940 public Comparator<? super K> comparator() {
1941 return reverseComparator;
1942 }
1943
1944 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1945 K toKey, boolean toInclusive) {
1946 if (!inRange(fromKey, fromInclusive))
1947 throw new IllegalArgumentException("fromKey out of range");
1948 if (!inRange(toKey, toInclusive))
1949 throw new IllegalArgumentException("toKey out of range");
2002
2003 TreeMap.Entry<K,V> subLowest() { return absHighest(); }
2004 TreeMap.Entry<K,V> subHighest() { return absLowest(); }
2005 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2006 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
2007 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
2008 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
2009 }
2010
2011 /**
2012 * This class exists solely for the sake of serialization
2013 * compatibility with previous releases of TreeMap that did not
2014 * support NavigableMap. It translates an old-version SubMap into
2015 * a new-version AscendingSubMap. This class is never otherwise
2016 * used.
2017 *
2018 * @serial include
2019 */
2020 private class SubMap extends AbstractMap<K,V>
2021 implements SortedMap<K,V>, java.io.Serializable {
2022 private static final long serialVersionUID = -6520786458950516097L;
2023 private boolean fromStart = false, toEnd = false;
2024 private K fromKey, toKey;
2025 private Object readResolve() {
2026 return new AscendingSubMap<>(TreeMap.this,
2027 fromStart, fromKey, true,
2028 toEnd, toKey, false);
2029 }
2030 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2031 public K lastKey() { throw new InternalError(); }
2032 public K firstKey() { throw new InternalError(); }
2033 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2034 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2035 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2036 public Comparator<? super K> comparator() { throw new InternalError(); }
2037 }
2038
2039
2040 // Red-black mechanics
2041
2042 private static final boolean RED = false;
2043 private static final boolean BLACK = true;
2044
2389 x = parentOf(x);
2390 } else {
2391 if (colorOf(leftOf(sib)) == BLACK) {
2392 setColor(rightOf(sib), BLACK);
2393 setColor(sib, RED);
2394 rotateLeft(sib);
2395 sib = leftOf(parentOf(x));
2396 }
2397 setColor(sib, colorOf(parentOf(x)));
2398 setColor(parentOf(x), BLACK);
2399 setColor(leftOf(sib), BLACK);
2400 rotateRight(parentOf(x));
2401 x = root;
2402 }
2403 }
2404 }
2405
2406 setColor(x, BLACK);
2407 }
2408
2409 private static final long serialVersionUID = 919286545866124006L;
2410
2411 /**
2412 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2413 * serialize it).
2414 *
2415 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2416 * mappings) is emitted (int), followed by the key (Object)
2417 * and value (Object) for each key-value mapping represented
2418 * by the TreeMap. The key-value mappings are emitted in
2419 * key-order (as determined by the TreeMap's Comparator,
2420 * or by the keys' natural ordering if the TreeMap has no
2421 * Comparator).
2422 */
2423 private void writeObject(java.io.ObjectOutputStream s)
2424 throws java.io.IOException {
2425 // Write out the Comparator and any hidden stuff
2426 s.defaultWriteObject();
2427
2428 // Write out size (number of Mappings)
2429 s.writeInt(size);
2430
2431 // Write out keys and values (alternating)
2432 for (Map.Entry<K, V> e : entrySet()) {
2433 s.writeObject(e.getKey());
2434 s.writeObject(e.getValue());
2435 }
2436 }
2437
2438 /**
2439 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2440 * deserialize it).
2441 */
2442 private void readObject(final java.io.ObjectInputStream s)
2443 throws java.io.IOException, ClassNotFoundException {
2444 // Read in the Comparator and any hidden stuff
2445 s.defaultReadObject();
2446
2447 // Read in size
2448 int size = s.readInt();
2449
2450 buildFromSorted(size, null, s, null);
2451 }
2452
2453 /** Intended to be called only from TreeSet.readObject */
2454 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2455 throws java.io.IOException, ClassNotFoundException {
2456 buildFromSorted(size, null, s, defaultVal);
2457 }
2458
2459 /** Intended to be called only from TreeSet.addAll */
2460 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2461 try {
|
1322 static <K> K key(Entry<K,?> e) {
1323 if (e==null)
1324 throw new NoSuchElementException();
1325 return e.key;
1326 }
1327
1328
1329 // SubMaps
1330
1331 /**
1332 * Dummy value serving as unmatchable fence key for unbounded
1333 * SubMapIterators
1334 */
1335 private static final Object UNBOUNDED = new Object();
1336
1337 /**
1338 * @serial include
1339 */
1340 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1341 implements NavigableMap<K,V>, java.io.Serializable {
1342 @java.io.Serial
1343 private static final long serialVersionUID = -2102997345730753016L;
1344 /**
1345 * The backing map.
1346 */
1347 final TreeMap<K,V> m;
1348
1349 /**
1350 * Endpoints are represented as triples (fromStart, lo,
1351 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1352 * true, then the low (absolute) bound is the start of the
1353 * backing map, and the other values are ignored. Otherwise,
1354 * if loInclusive is true, lo is the inclusive bound, else lo
1355 * is the exclusive bound. Similarly for the upper bound.
1356 */
1357 final K lo, hi;
1358 final boolean fromStart, toEnd;
1359 final boolean loInclusive, hiInclusive;
1360
1361 NavigableSubMap(TreeMap<K,V> m,
1362 boolean fromStart, K lo, boolean loInclusive,
1828 public boolean tryAdvance(Consumer<? super K> action) {
1829 if (hasNext()) {
1830 action.accept(next());
1831 return true;
1832 }
1833 return false;
1834 }
1835 public long estimateSize() {
1836 return Long.MAX_VALUE;
1837 }
1838 public int characteristics() {
1839 return Spliterator.DISTINCT | Spliterator.ORDERED;
1840 }
1841 }
1842 }
1843
1844 /**
1845 * @serial include
1846 */
1847 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1848 @java.io.Serial
1849 private static final long serialVersionUID = 912986545866124060L;
1850
1851 AscendingSubMap(TreeMap<K,V> m,
1852 boolean fromStart, K lo, boolean loInclusive,
1853 boolean toEnd, K hi, boolean hiInclusive) {
1854 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1855 }
1856
1857 public Comparator<? super K> comparator() {
1858 return m.comparator();
1859 }
1860
1861 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1862 K toKey, boolean toInclusive) {
1863 if (!inRange(fromKey, fromInclusive))
1864 throw new IllegalArgumentException("fromKey out of range");
1865 if (!inRange(toKey, toInclusive))
1866 throw new IllegalArgumentException("toKey out of range");
1867 return new AscendingSubMap<>(m,
1868 false, fromKey, fromInclusive,
1912 }
1913 }
1914
1915 public Set<Map.Entry<K,V>> entrySet() {
1916 EntrySetView es = entrySetView;
1917 return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
1918 }
1919
1920 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1921 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1922 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1923 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1924 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1925 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1926 }
1927
1928 /**
1929 * @serial include
1930 */
1931 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1932 @java.io.Serial
1933 private static final long serialVersionUID = 912986545866120460L;
1934 DescendingSubMap(TreeMap<K,V> m,
1935 boolean fromStart, K lo, boolean loInclusive,
1936 boolean toEnd, K hi, boolean hiInclusive) {
1937 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1938 }
1939
1940 private final Comparator<? super K> reverseComparator =
1941 Collections.reverseOrder(m.comparator);
1942
1943 public Comparator<? super K> comparator() {
1944 return reverseComparator;
1945 }
1946
1947 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1948 K toKey, boolean toInclusive) {
1949 if (!inRange(fromKey, fromInclusive))
1950 throw new IllegalArgumentException("fromKey out of range");
1951 if (!inRange(toKey, toInclusive))
1952 throw new IllegalArgumentException("toKey out of range");
2005
2006 TreeMap.Entry<K,V> subLowest() { return absHighest(); }
2007 TreeMap.Entry<K,V> subHighest() { return absLowest(); }
2008 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2009 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
2010 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
2011 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
2012 }
2013
2014 /**
2015 * This class exists solely for the sake of serialization
2016 * compatibility with previous releases of TreeMap that did not
2017 * support NavigableMap. It translates an old-version SubMap into
2018 * a new-version AscendingSubMap. This class is never otherwise
2019 * used.
2020 *
2021 * @serial include
2022 */
2023 private class SubMap extends AbstractMap<K,V>
2024 implements SortedMap<K,V>, java.io.Serializable {
2025 @java.io.Serial
2026 private static final long serialVersionUID = -6520786458950516097L;
2027 private boolean fromStart = false, toEnd = false;
2028 private K fromKey, toKey;
2029 @java.io.Serial
2030 private Object readResolve() {
2031 return new AscendingSubMap<>(TreeMap.this,
2032 fromStart, fromKey, true,
2033 toEnd, toKey, false);
2034 }
2035 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2036 public K lastKey() { throw new InternalError(); }
2037 public K firstKey() { throw new InternalError(); }
2038 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2039 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2040 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2041 public Comparator<? super K> comparator() { throw new InternalError(); }
2042 }
2043
2044
2045 // Red-black mechanics
2046
2047 private static final boolean RED = false;
2048 private static final boolean BLACK = true;
2049
2394 x = parentOf(x);
2395 } else {
2396 if (colorOf(leftOf(sib)) == BLACK) {
2397 setColor(rightOf(sib), BLACK);
2398 setColor(sib, RED);
2399 rotateLeft(sib);
2400 sib = leftOf(parentOf(x));
2401 }
2402 setColor(sib, colorOf(parentOf(x)));
2403 setColor(parentOf(x), BLACK);
2404 setColor(leftOf(sib), BLACK);
2405 rotateRight(parentOf(x));
2406 x = root;
2407 }
2408 }
2409 }
2410
2411 setColor(x, BLACK);
2412 }
2413
2414 @java.io.Serial
2415 private static final long serialVersionUID = 919286545866124006L;
2416
2417 /**
2418 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2419 * serialize it).
2420 *
2421 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2422 * mappings) is emitted (int), followed by the key (Object)
2423 * and value (Object) for each key-value mapping represented
2424 * by the TreeMap. The key-value mappings are emitted in
2425 * key-order (as determined by the TreeMap's Comparator,
2426 * or by the keys' natural ordering if the TreeMap has no
2427 * Comparator).
2428 */
2429 @java.io.Serial
2430 private void writeObject(java.io.ObjectOutputStream s)
2431 throws java.io.IOException {
2432 // Write out the Comparator and any hidden stuff
2433 s.defaultWriteObject();
2434
2435 // Write out size (number of Mappings)
2436 s.writeInt(size);
2437
2438 // Write out keys and values (alternating)
2439 for (Map.Entry<K, V> e : entrySet()) {
2440 s.writeObject(e.getKey());
2441 s.writeObject(e.getValue());
2442 }
2443 }
2444
2445 /**
2446 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2447 * deserialize it).
2448 */
2449 @java.io.Serial
2450 private void readObject(final java.io.ObjectInputStream s)
2451 throws java.io.IOException, ClassNotFoundException {
2452 // Read in the Comparator and any hidden stuff
2453 s.defaultReadObject();
2454
2455 // Read in size
2456 int size = s.readInt();
2457
2458 buildFromSorted(size, null, s, null);
2459 }
2460
2461 /** Intended to be called only from TreeSet.readObject */
2462 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2463 throws java.io.IOException, ClassNotFoundException {
2464 buildFromSorted(size, null, s, defaultVal);
2465 }
2466
2467 /** Intended to be called only from TreeSet.addAll */
2468 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2469 try {
|