< prev index next >
src/java.base/share/classes/java/util/TreeMap.java
Print this page
rev 16828 : implements default methods in TreeMap v0
rev 16829 : TreeMap
rev 16830 : TreeMap
rev 16831 : add modCount check for compute* methods
*** 27,36 ****
--- 27,37 ----
import java.io.Serializable;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
+ import java.util.function.Function;
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} provided at map
*** 529,564 ****
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
! Entry<K,V> t = root;
! if (t == null) {
! compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
! Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
! else
! return t.setValue(value);
! } while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
--- 530,656 ----
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
! return put(key, value, true);
! }
+ private void addEntry(K key, V value, int cmp, Entry<K, V> parent) {
+ Entry<K, V> e = new Entry<>(key, value, parent);
+ if (cmp < 0)
+ parent.left = e;
+ else
+ parent.right = e;
+ fixAfterInsertion(e);
+ size++;
+ modCount++;
+ }
+
+ private void addEntryToEmptyMap(K key, V value) {
+ compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
+ }
+
+ private V put(K key, V value, boolean replaceOld) {
+ Entry<K, V> t = root;
+ if (t == null) {
+ addEntryToEmptyMap(key, value);
return null;
}
int cmp;
! Entry<K, V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
! else {
! V oldValue = t.value;
! if (replaceOld) {
! t.value = value;
}
+ return oldValue;
+ }
+ } while (t != null);
+ } else {
+ if (key == null)
+ throw new NullPointerException();
+ @SuppressWarnings("unchecked")
+ Comparable<? super K> k = (Comparable<? super K>) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
else {
+ V oldValue = t.value;
+ if (replaceOld) {
+ t.value = value;
+ }
+ return oldValue;
+ }
+ } while (t != null);
+ }
+ addEntry(key, value, cmp, parent);
+ return null;
+ }
+
+ @Override
+ public V putIfAbsent(K key, V value) {
+ return put(key, value, false);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>This method will, on a best-effort basis, throw a
+ * {@link ConcurrentModificationException} if it is detected that the
+ * remapping function modifies this map during computation.
+ *
+ * @throws ConcurrentModificationException if it is detected that the
+ * remapping function modified this map
+ */
+ @Override
+ public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+ Objects.requireNonNull(mappingFunction);
+ V newValue;
+ Entry<K, V> t = root;
+ if (t == null) {
+ newValue = getNewValueAndCheckModification(key, mappingFunction);
+ if (newValue != null) {
+ addEntryToEmptyMap(key, newValue);
+ return newValue;
+ } else {
+ return null;
+ }
+ }
+ int cmp;
+ Entry<K, V> parent;
+ // split comparator and comparable paths
+ Comparator<? super K> cpr = comparator;
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else
+ return t.value;
+ } while (t != null);
+ } else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
*** 567,587 ****
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
! return t.setValue(value);
} while (t != null);
}
! Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
! parent.left = e;
else
! parent.right = e;
! fixAfterInsertion(e);
! size++;
! modCount++;
return null;
}
/**
* Removes the mapping for this key from this TreeMap if present.
--- 659,791 ----
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
! return t.value;
} while (t != null);
}
! newValue = getNewValueAndCheckModification(key, mappingFunction);
! if (newValue != null) {
! addEntry(key, newValue, cmp, parent);
! return newValue;
! }
! return null;
! }
!
! private V getNewValueAndCheckModification(K key, Function<? super K, ? extends V> mappingFunction) {
! V newValue;
! int mc = modCount;
! newValue = mappingFunction.apply(key);
! if (mc != modCount) {
! throw new ConcurrentModificationException();
! }
! return newValue;
! }
!
! /**
! * {@inheritDoc}
! *
! * <p>This method will, on a best-effort basis, throw a
! * {@link ConcurrentModificationException} if it is detected that the
! * remapping function modifies this map during computation.
! *
! * @throws ConcurrentModificationException if it is detected that the
! * remapping function modified this map
! */
! @Override
! public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
! Objects.requireNonNull(remappingFunction);
! Entry<K, V> oldEntry = getEntry(key);
! if (oldEntry != null && oldEntry.value != null) {
! return remapValue(oldEntry, key, remappingFunction);
! } else {
! return null;
! }
! }
!
! private V remapValue(Entry<K, V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
! V newValue = getNewValueAndCheckModification(key, t.value, remappingFunction);
! if (newValue == null) {
! deleteEntry(t);
! return null;
! } else {
! // replace old mapping
! t.value = newValue;
! return newValue;
! }
! }
!
! private V getNewValueAndCheckModification(K key, V oldValue, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
! int mc = modCount;
! V newValue = remappingFunction.apply(key, oldValue);
! if (mc != modCount) {
! throw new ConcurrentModificationException();
! }
! return newValue;
! }
!
! /**
! * {@inheritDoc}
! *
! * <p>This method will, on a best-effort basis, throw a
! * {@link ConcurrentModificationException} if it is detected that the
! * remapping function modifies this map during computation.
! *
! * @throws ConcurrentModificationException if it is detected that the
! * remapping function modified this map
! */
! @Override
! public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
! Objects.requireNonNull(remappingFunction);
! V newValue;
! Entry<K, V> t = root;
! if (t == null) {
! newValue = getNewValueAndCheckModification(key, null, remappingFunction);
! if (newValue != null) {
! addEntryToEmptyMap(key, newValue);
! return newValue;
! } else {
! return null;
! }
! }
! int cmp;
! Entry<K, V> parent;
! // split comparator and comparable paths
! Comparator<? super K> cpr = comparator;
! if (cpr != null) {
! do {
! parent = t;
! cmp = cpr.compare(key, t.key);
if (cmp < 0)
! t = t.left;
! else if (cmp > 0)
! t = t.right;
else
! return remapValue(t, key, remappingFunction);
! } while (t != null);
! } else {
! if (key == null)
! throw new NullPointerException();
! @SuppressWarnings("unchecked")
! Comparable<? super K> k = (Comparable<? super K>) key;
! do {
! parent = t;
! cmp = k.compareTo(t.key);
! if (cmp < 0)
! t = t.left;
! else if (cmp > 0)
! t = t.right;
! else
! return remapValue(t, key, remappingFunction);
! } while (t != null);
! }
! newValue = getNewValueAndCheckModification(key, null, remappingFunction);
! if (newValue != null) {
! addEntry(key, newValue, cmp, parent);
! return newValue;
! }
return null;
}
/**
* Removes the mapping for this key from this TreeMap if present.
< prev index next >