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.io.Serializable;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Consumer;
32
33 /**
34 * A Red-Black tree based {@link NavigableMap} implementation.
35 * The map is sorted according to the {@linkplain Comparable natural
36 * ordering} of its keys, or by a {@link Comparator} provided at map
37 * creation time, depending on which constructor is used.
38 *
39 * <p>This implementation provides guaranteed log(n) time cost for the
40 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
41 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
42 * Rivest's <em>Introduction to Algorithms</em>.
43 *
44 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
45 * whether or not an explicit comparator is provided, must be <em>consistent
46 * with {@code equals}</em> if this sorted map is to correctly implement the
47 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
48 * precise definition of <em>consistent with equals</em>.) This is so because
49 * the {@code Map} interface is defined in terms of the {@code equals}
50 * operation, but a sorted map performs all key comparisons using its {@code
51 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
514
515 /**
516 * Associates the specified value with the specified key in this map.
517 * If the map previously contained a mapping for the key, the old
518 * value is replaced.
519 *
520 * @param key key with which the specified value is to be associated
521 * @param value value to be associated with the specified key
522 *
523 * @return the previous value associated with {@code key}, or
524 * {@code null} if there was no mapping for {@code key}.
525 * (A {@code null} return can also indicate that the map
526 * previously associated {@code null} with {@code key}.)
527 * @throws ClassCastException if the specified key cannot be compared
528 * with the keys currently in the map
529 * @throws NullPointerException if the specified key is null
530 * and this map uses natural ordering, or its comparator
531 * does not permit null keys
532 */
533 public V put(K key, V value) {
534 Entry<K,V> t = root;
535 if (t == null) {
536 compare(key, key); // type (and possibly null) check
537
538 root = new Entry<>(key, value, null);
539 size = 1;
540 modCount++;
541 return null;
542 }
543 int cmp;
544 Entry<K,V> parent;
545 // split comparator and comparable paths
546 Comparator<? super K> cpr = comparator;
547 if (cpr != null) {
548 do {
549 parent = t;
550 cmp = cpr.compare(key, t.key);
551 if (cmp < 0)
552 t = t.left;
553 else if (cmp > 0)
554 t = t.right;
555 else
556 return t.setValue(value);
557 } while (t != null);
558 }
559 else {
560 if (key == null)
561 throw new NullPointerException();
562 @SuppressWarnings("unchecked")
563 Comparable<? super K> k = (Comparable<? super K>) key;
564 do {
565 parent = t;
566 cmp = k.compareTo(t.key);
567 if (cmp < 0)
568 t = t.left;
569 else if (cmp > 0)
570 t = t.right;
571 else
572 return t.setValue(value);
573 } while (t != null);
574 }
575 Entry<K,V> e = new Entry<>(key, value, parent);
576 if (cmp < 0)
577 parent.left = e;
578 else
579 parent.right = e;
580 fixAfterInsertion(e);
581 size++;
582 modCount++;
583 return null;
584 }
585
586 /**
587 * Removes the mapping for this key from this TreeMap if present.
588 *
589 * @param key key for which mapping should be removed
590 * @return the previous value associated with {@code key}, or
591 * {@code null} if there was no mapping for {@code key}.
592 * (A {@code null} return can also indicate that the map
593 * previously associated {@code null} with {@code key}.)
594 * @throws ClassCastException if the specified key cannot be compared
595 * with the keys currently in the map
596 * @throws NullPointerException if the specified key is null
597 * and this map uses natural ordering, or its comparator
598 * does not permit null keys
599 */
600 public V remove(Object key) {
601 Entry<K,V> p = getEntry(key);
602 if (p == null)
|
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.io.Serializable;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Consumer;
32 import java.util.function.Function;
33
34 /**
35 * A Red-Black tree based {@link NavigableMap} implementation.
36 * The map is sorted according to the {@linkplain Comparable natural
37 * ordering} of its keys, or by a {@link Comparator} provided at map
38 * creation time, depending on which constructor is used.
39 *
40 * <p>This implementation provides guaranteed log(n) time cost for the
41 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
42 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
43 * Rivest's <em>Introduction to Algorithms</em>.
44 *
45 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
46 * whether or not an explicit comparator is provided, must be <em>consistent
47 * with {@code equals}</em> if this sorted map is to correctly implement the
48 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
49 * precise definition of <em>consistent with equals</em>.) This is so because
50 * the {@code Map} interface is defined in terms of the {@code equals}
51 * operation, but a sorted map performs all key comparisons using its {@code
52 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
515
516 /**
517 * Associates the specified value with the specified key in this map.
518 * If the map previously contained a mapping for the key, the old
519 * value is replaced.
520 *
521 * @param key key with which the specified value is to be associated
522 * @param value value to be associated with the specified key
523 *
524 * @return the previous value associated with {@code key}, or
525 * {@code null} if there was no mapping for {@code key}.
526 * (A {@code null} return can also indicate that the map
527 * previously associated {@code null} with {@code key}.)
528 * @throws ClassCastException if the specified key cannot be compared
529 * with the keys currently in the map
530 * @throws NullPointerException if the specified key is null
531 * and this map uses natural ordering, or its comparator
532 * does not permit null keys
533 */
534 public V put(K key, V value) {
535 return put(key, value, true);
536 }
537
538 private void addEntry(K key, V value, int cmp, Entry<K, V> parent) {
539 Entry<K,V> e = new Entry<>(key, value, parent);
540 if (cmp < 0)
541 parent.left = e;
542 else
543 parent.right = e;
544 fixAfterInsertion(e);
545 size++;
546 modCount++;
547 }
548
549 private void addEntryToEmptyMap(K key, V value) {
550 compare(key, key); // type (and possibly null) check
551 root = new Entry<>(key, value, null);
552 size = 1;
553 modCount++;
554 }
555
556 private V put(K key, V value, boolean replaceOld) {
557 Entry<K,V> t = root;
558 if (t == null) {
559 addEntryToEmptyMap(key, value);
560 return null;
561 }
562 int cmp;
563 Entry<K,V> parent;
564 // split comparator and comparable paths
565 Comparator<? super K> cpr = comparator;
566 if (cpr != null) {
567 do {
568 parent = t;
569 cmp = cpr.compare(key, t.key);
570 if (cmp < 0)
571 t = t.left;
572 else if (cmp > 0)
573 t = t.right;
574 else {
575 V oldValue = t.value;
576 if(replaceOld) {
577 t.value = value;
578 }
579 return oldValue;
580 }
581 } while (t != null);
582 }
583 else {
584 if (key == null)
585 throw new NullPointerException();
586 @SuppressWarnings("unchecked")
587 Comparable<? super K> k = (Comparable<? super K>) key;
588 do {
589 parent = t;
590 cmp = k.compareTo(t.key);
591 if (cmp < 0)
592 t = t.left;
593 else if (cmp > 0)
594 t = t.right;
595 else {
596 V oldValue = t.value;
597 if(replaceOld) {
598 t.value = value;
599 }
600 return oldValue;
601 }
602 } while (t != null);
603 }
604 addEntry(key, value, cmp, parent);
605 return null;
606 }
607
608 @Override
609 public V putIfAbsent(K key, V value) {
610 return put(key, value, false);
611 }
612
613 @Override
614 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
615 Objects.requireNonNull(mappingFunction);
616 V newValue;
617 Entry<K,V> t = root;
618 if (t == null) {
619 if ((newValue = mappingFunction.apply(key)) != null) {
620 addEntryToEmptyMap(key, newValue);
621 return newValue;
622 } else {
623 return null;
624 }
625 }
626 int cmp;
627 Entry<K,V> parent;
628 // split comparator and comparable paths
629 Comparator<? super K> cpr = comparator;
630 if (cpr != null) {
631 do {
632 parent = t;
633 cmp = cpr.compare(key, t.key);
634 if (cmp < 0)
635 t = t.left;
636 else if (cmp > 0)
637 t = t.right;
638 else
639 return t.value;
640 } while (t != null);
641 }
642 else {
643 if (key == null)
644 throw new NullPointerException();
645 @SuppressWarnings("unchecked")
646 Comparable<? super K> k = (Comparable<? super K>) key;
647 do {
648 parent = t;
649 cmp = k.compareTo(t.key);
650 if (cmp < 0)
651 t = t.left;
652 else if (cmp > 0)
653 t = t.right;
654 else
655 return t.value;
656 } while (t != null);
657 }
658 if ((newValue = mappingFunction.apply(key)) != null) {
659 addEntry(key, newValue, cmp, parent);
660 return newValue;
661 }
662 return null;
663 }
664
665 @Override
666 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
667 Objects.requireNonNull(remappingFunction);
668 Entry<K,V> oldEntry = getEntry(key);
669 if (oldEntry != null && oldEntry.value != null) {
670 return remapValue(oldEntry, key, remappingFunction);
671 } else {
672 return null;
673 }
674 }
675
676 private V remapValue(Entry<K, V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
677 V newValue = remappingFunction.apply(key, t.value);
678 if (newValue == null) {
679 deleteEntry(t);
680 return null;
681 } else {
682 // replace old mapping
683 t.value = newValue;
684 return newValue;
685 }
686 }
687
688 @Override
689 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
690 Objects.requireNonNull(remappingFunction);
691 V newValue;
692 Entry<K,V> t = root;
693 if (t == null) {
694 newValue = remappingFunction.apply(key, null);
695 if (newValue != null) {
696 addEntryToEmptyMap(key, newValue);
697 return newValue;
698 } else {
699 return null;
700 }
701 }
702 int cmp;
703 Entry<K,V> parent;
704 // split comparator and comparable paths
705 Comparator<? super K> cpr = comparator;
706 if (cpr != null) {
707 do {
708 parent = t;
709 cmp = cpr.compare(key, t.key);
710 if (cmp < 0)
711 t = t.left;
712 else if (cmp > 0)
713 t = t.right;
714 else
715 return remapValue(t, key, remappingFunction);
716 } while (t != null);
717 }
718 else {
719 if (key == null)
720 throw new NullPointerException();
721 @SuppressWarnings("unchecked")
722 Comparable<? super K> k = (Comparable<? super K>) key;
723 do {
724 parent = t;
725 cmp = k.compareTo(t.key);
726 if (cmp < 0)
727 t = t.left;
728 else if (cmp > 0)
729 t = t.right;
730 else
731 return remapValue(t, key, remappingFunction);
732 } while (t != null);
733 }
734 if ((newValue = remappingFunction.apply(key, null)) != null) {
735 addEntry(key, newValue, cmp, parent);
736 return newValue;
737 }
738 return null;
739 }
740
741 /**
742 * Removes the mapping for this key from this TreeMap if present.
743 *
744 * @param key key for which mapping should be removed
745 * @return the previous value associated with {@code key}, or
746 * {@code null} if there was no mapping for {@code key}.
747 * (A {@code null} return can also indicate that the map
748 * previously associated {@code null} with {@code key}.)
749 * @throws ClassCastException if the specified key cannot be compared
750 * with the keys currently in the map
751 * @throws NullPointerException if the specified key is null
752 * and this map uses natural ordering, or its comparator
753 * does not permit null keys
754 */
755 public V remove(Object key) {
756 Entry<K,V> p = getEntry(key);
757 if (p == null)
|