8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Consumer;
29
30 /**
31 * A Red-Black tree based {@link NavigableMap} implementation.
32 * The map is sorted according to the {@linkplain Comparable natural
33 * ordering} of its keys, or by a {@link Comparator} provided at map
34 * creation time, depending on which constructor is used.
35 *
36 * <p>This implementation provides guaranteed log(n) time cost for the
37 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
38 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
39 * Rivest's <em>Introduction to Algorithms</em>.
40 *
41 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
42 * whether or not an explicit comparator is provided, must be <em>consistent
43 * with {@code equals}</em> if this sorted map is to correctly implement the
44 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
45 * precise definition of <em>consistent with equals</em>.) This is so because
46 * the {@code Map} interface is defined in terms of the {@code equals}
47 * operation, but a sorted map performs all key comparisons using its {@code
926 /**
927 * @throws ClassCastException {@inheritDoc}
928 * @throws NullPointerException if {@code toKey} is null
929 * and this map uses natural ordering, or its comparator
930 * does not permit null keys
931 * @throws IllegalArgumentException {@inheritDoc}
932 */
933 public SortedMap<K,V> headMap(K toKey) {
934 return headMap(toKey, false);
935 }
936
937 /**
938 * @throws ClassCastException {@inheritDoc}
939 * @throws NullPointerException if {@code fromKey} is null
940 * and this map uses natural ordering, or its comparator
941 * does not permit null keys
942 * @throws IllegalArgumentException {@inheritDoc}
943 */
944 public SortedMap<K,V> tailMap(K fromKey) {
945 return tailMap(fromKey, true);
946 }
947
948 // View class support
949
950 class Values extends AbstractCollection<V> {
951 public Iterator<V> iterator() {
952 return new ValueIterator(getFirstEntry());
953 }
954
955 public int size() {
956 return TreeMap.this.size();
957 }
958
959 public boolean contains(Object o) {
960 return TreeMap.this.containsValue(o);
961 }
962
963 public boolean remove(Object o) {
964 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
965 if (valEquals(e.getValue(), o)) {
|
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.BiConsumer;
29 import java.util.function.BiFunction;
30 import java.util.function.Consumer;
31
32 /**
33 * A Red-Black tree based {@link NavigableMap} implementation.
34 * The map is sorted according to the {@linkplain Comparable natural
35 * ordering} of its keys, or by a {@link Comparator} provided at map
36 * creation time, depending on which constructor is used.
37 *
38 * <p>This implementation provides guaranteed log(n) time cost for the
39 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
40 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
41 * Rivest's <em>Introduction to Algorithms</em>.
42 *
43 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
44 * whether or not an explicit comparator is provided, must be <em>consistent
45 * with {@code equals}</em> if this sorted map is to correctly implement the
46 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
47 * precise definition of <em>consistent with equals</em>.) This is so because
48 * the {@code Map} interface is defined in terms of the {@code equals}
49 * operation, but a sorted map performs all key comparisons using its {@code
928 /**
929 * @throws ClassCastException {@inheritDoc}
930 * @throws NullPointerException if {@code toKey} is null
931 * and this map uses natural ordering, or its comparator
932 * does not permit null keys
933 * @throws IllegalArgumentException {@inheritDoc}
934 */
935 public SortedMap<K,V> headMap(K toKey) {
936 return headMap(toKey, false);
937 }
938
939 /**
940 * @throws ClassCastException {@inheritDoc}
941 * @throws NullPointerException if {@code fromKey} is null
942 * and this map uses natural ordering, or its comparator
943 * does not permit null keys
944 * @throws IllegalArgumentException {@inheritDoc}
945 */
946 public SortedMap<K,V> tailMap(K fromKey) {
947 return tailMap(fromKey, true);
948 }
949
950 @Override
951 public void forEach(BiConsumer<? super K, ? super V> action) {
952 Objects.requireNonNull(action);
953 int expectedModCount = modCount;
954 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
955 action.accept(e.key, e.value);
956
957 if (expectedModCount != modCount) {
958 throw new ConcurrentModificationException();
959 }
960 }
961 }
962
963 @Override
964 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
965 Objects.requireNonNull(function);
966 int expectedModCount = modCount;
967
968 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
969 e.value = Objects.requireNonNull(function.apply(e.key, e.value));
970
971 if (expectedModCount != modCount) {
972 throw new ConcurrentModificationException();
973 }
974 }
975 }
976
977 // View class support
978
979 class Values extends AbstractCollection<V> {
980 public Iterator<V> iterator() {
981 return new ValueIterator(getFirstEntry());
982 }
983
984 public int size() {
985 return TreeMap.this.size();
986 }
987
988 public boolean contains(Object o) {
989 return TreeMap.this.containsValue(o);
990 }
991
992 public boolean remove(Object o) {
993 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
994 if (valEquals(e.getValue(), o)) {
|