101 * @author Josh Bloch and Doug Lea
102 * @see Map
103 * @see HashMap
104 * @see Hashtable
105 * @see Comparable
106 * @see Comparator
107 * @see Collection
108 * @since 1.2
109 */
110
111 public class TreeMap<K,V>
112 extends AbstractMap<K,V>
113 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
114 {
115 /**
116 * The comparator used to maintain order in this tree map, or
117 * null if it uses the natural ordering of its keys.
118 *
119 * @serial
120 */
121 private final Comparator<? super K> comparator;
122
123 private transient Entry<K,V> root;
124
125 /**
126 * The number of entries in the tree
127 */
128 private transient int size = 0;
129
130 /**
131 * The number of structural modifications to the tree.
132 */
133 private transient int modCount = 0;
134
135 /**
136 * Constructs a new, empty tree map, using the natural ordering of its
137 * keys. All keys inserted into the map must implement the {@link
138 * Comparable} interface. Furthermore, all such keys must be
139 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
140 * a {@code ClassCastException} for any keys {@code k1} and
1336 /**
1337 * @serial include
1338 */
1339 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1340 implements NavigableMap<K,V>, java.io.Serializable {
1341 @java.io.Serial
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,
1362 boolean toEnd, K hi, boolean hiInclusive) {
1363 if (!fromStart && !toEnd) {
1364 if (m.compare(lo, hi) > 0)
1365 throw new IllegalArgumentException("fromKey > toKey");
1366 } else {
1367 if (!fromStart) // type check
1368 m.compare(lo, lo);
1369 if (!toEnd)
1370 m.compare(hi, hi);
1371 }
1372
1373 this.m = m;
1374 this.fromStart = fromStart;
1375 this.lo = lo;
1376 this.loInclusive = loInclusive;
1919 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1920 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1921 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1922 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1923 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1924 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1925 }
1926
1927 /**
1928 * @serial include
1929 */
1930 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1931 @java.io.Serial
1932 private static final long serialVersionUID = 912986545866120460L;
1933 DescendingSubMap(TreeMap<K,V> m,
1934 boolean fromStart, K lo, boolean loInclusive,
1935 boolean toEnd, K hi, boolean hiInclusive) {
1936 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1937 }
1938
1939 private final Comparator<? super K> reverseComparator =
1940 Collections.reverseOrder(m.comparator);
1941
1942 public Comparator<? super K> comparator() {
1943 return reverseComparator;
1944 }
1945
1946 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1947 K toKey, boolean toInclusive) {
1948 if (!inRange(fromKey, fromInclusive))
1949 throw new IllegalArgumentException("fromKey out of range");
1950 if (!inRange(toKey, toInclusive))
1951 throw new IllegalArgumentException("toKey out of range");
1952 return new DescendingSubMap<>(m,
1953 false, toKey, toInclusive,
1954 false, fromKey, fromInclusive);
1955 }
1956
1957 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1958 if (!inRange(toKey, inclusive))
2007 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2008 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
2009 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
2010 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
2011 }
2012
2013 /**
2014 * This class exists solely for the sake of serialization
2015 * compatibility with previous releases of TreeMap that did not
2016 * support NavigableMap. It translates an old-version SubMap into
2017 * a new-version AscendingSubMap. This class is never otherwise
2018 * used.
2019 *
2020 * @serial include
2021 */
2022 private class SubMap extends AbstractMap<K,V>
2023 implements SortedMap<K,V>, java.io.Serializable {
2024 @java.io.Serial
2025 private static final long serialVersionUID = -6520786458950516097L;
2026 private boolean fromStart = false, toEnd = false;
2027 private K fromKey, toKey;
2028 @java.io.Serial
2029 private Object readResolve() {
2030 return new AscendingSubMap<>(TreeMap.this,
2031 fromStart, fromKey, true,
2032 toEnd, toKey, false);
2033 }
2034 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2035 public K lastKey() { throw new InternalError(); }
2036 public K firstKey() { throw new InternalError(); }
2037 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2038 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2039 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2040 public Comparator<? super K> comparator() { throw new InternalError(); }
2041 }
2042
2043
2044 // Red-black mechanics
2045
2046 private static final boolean RED = false;
2047 private static final boolean BLACK = true;
|
101 * @author Josh Bloch and Doug Lea
102 * @see Map
103 * @see HashMap
104 * @see Hashtable
105 * @see Comparable
106 * @see Comparator
107 * @see Collection
108 * @since 1.2
109 */
110
111 public class TreeMap<K,V>
112 extends AbstractMap<K,V>
113 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
114 {
115 /**
116 * The comparator used to maintain order in this tree map, or
117 * null if it uses the natural ordering of its keys.
118 *
119 * @serial
120 */
121 @SuppressWarnings("serial") // Not statically typed as Serializable
122 private final Comparator<? super K> comparator;
123
124 private transient Entry<K,V> root;
125
126 /**
127 * The number of entries in the tree
128 */
129 private transient int size = 0;
130
131 /**
132 * The number of structural modifications to the tree.
133 */
134 private transient int modCount = 0;
135
136 /**
137 * Constructs a new, empty tree map, using the natural ordering of its
138 * keys. All keys inserted into the map must implement the {@link
139 * Comparable} interface. Furthermore, all such keys must be
140 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
141 * a {@code ClassCastException} for any keys {@code k1} and
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 @SuppressWarnings("serial") // Not statically typed as Serializable
1358 final K lo;
1359 @SuppressWarnings("serial") // Not statically typed as Serializable
1360 final K hi;
1361 final boolean fromStart, toEnd;
1362 final boolean loInclusive, hiInclusive;
1363
1364 NavigableSubMap(TreeMap<K,V> m,
1365 boolean fromStart, K lo, boolean loInclusive,
1366 boolean toEnd, K hi, boolean hiInclusive) {
1367 if (!fromStart && !toEnd) {
1368 if (m.compare(lo, hi) > 0)
1369 throw new IllegalArgumentException("fromKey > toKey");
1370 } else {
1371 if (!fromStart) // type check
1372 m.compare(lo, lo);
1373 if (!toEnd)
1374 m.compare(hi, hi);
1375 }
1376
1377 this.m = m;
1378 this.fromStart = fromStart;
1379 this.lo = lo;
1380 this.loInclusive = loInclusive;
1923 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1924 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1925 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1926 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1927 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1928 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1929 }
1930
1931 /**
1932 * @serial include
1933 */
1934 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1935 @java.io.Serial
1936 private static final long serialVersionUID = 912986545866120460L;
1937 DescendingSubMap(TreeMap<K,V> m,
1938 boolean fromStart, K lo, boolean loInclusive,
1939 boolean toEnd, K hi, boolean hiInclusive) {
1940 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1941 }
1942
1943 @SuppressWarnings("serial") // Not statically typed as Serializable
1944 private final Comparator<? super K> reverseComparator =
1945 Collections.reverseOrder(m.comparator);
1946
1947 public Comparator<? super K> comparator() {
1948 return reverseComparator;
1949 }
1950
1951 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1952 K toKey, boolean toInclusive) {
1953 if (!inRange(fromKey, fromInclusive))
1954 throw new IllegalArgumentException("fromKey out of range");
1955 if (!inRange(toKey, toInclusive))
1956 throw new IllegalArgumentException("toKey out of range");
1957 return new DescendingSubMap<>(m,
1958 false, toKey, toInclusive,
1959 false, fromKey, fromInclusive);
1960 }
1961
1962 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1963 if (!inRange(toKey, inclusive))
2012 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2013 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
2014 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
2015 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
2016 }
2017
2018 /**
2019 * This class exists solely for the sake of serialization
2020 * compatibility with previous releases of TreeMap that did not
2021 * support NavigableMap. It translates an old-version SubMap into
2022 * a new-version AscendingSubMap. This class is never otherwise
2023 * used.
2024 *
2025 * @serial include
2026 */
2027 private class SubMap extends AbstractMap<K,V>
2028 implements SortedMap<K,V>, java.io.Serializable {
2029 @java.io.Serial
2030 private static final long serialVersionUID = -6520786458950516097L;
2031 private boolean fromStart = false, toEnd = false;
2032 @SuppressWarnings("serial") // Not statically typed as Serializable
2033 private K fromKey;
2034 @SuppressWarnings("serial") // Not statically typed as Serializable
2035 private K toKey;
2036 @java.io.Serial
2037 private Object readResolve() {
2038 return new AscendingSubMap<>(TreeMap.this,
2039 fromStart, fromKey, true,
2040 toEnd, toKey, false);
2041 }
2042 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2043 public K lastKey() { throw new InternalError(); }
2044 public K firstKey() { throw new InternalError(); }
2045 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2046 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2047 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2048 public Comparator<? super K> comparator() { throw new InternalError(); }
2049 }
2050
2051
2052 // Red-black mechanics
2053
2054 private static final boolean RED = false;
2055 private static final boolean BLACK = true;
|