1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
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.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)
603 return null;
|
1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
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.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 || oldValue == null) {
577 t.value = value;
578 }
579 return oldValue;
580 }
581 } while (t != null);
582 } else {
583 if (key == null)
584 throw new NullPointerException();
585 @SuppressWarnings("unchecked")
586 Comparable<? super K> k = (Comparable<? super K>) key;
587 do {
588 parent = t;
589 cmp = k.compareTo(t.key);
590 if (cmp < 0)
591 t = t.left;
592 else if (cmp > 0)
593 t = t.right;
594 else {
595 V oldValue = t.value;
596 if (replaceOld || oldValue == null) {
597 t.value = value;
598 }
599 return oldValue;
600 }
601 } while (t != null);
602 }
603 addEntry(key, value, cmp, parent);
604 return null;
605 }
606
607 @Override
608 public V putIfAbsent(K key, V value) {
609 return put(key, value, false);
610 }
611
612 /**
613 * {@inheritDoc}
614 *
615 * <p>This method will, on a best-effort basis, throw a
616 * {@link ConcurrentModificationException} if it is detected that the
617 * remapping function modifies this map during computation.
618 *
619 * @throws ConcurrentModificationException if it is detected that the
620 * remapping function modified this map
621 */
622 @Override
623 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
624 Objects.requireNonNull(mappingFunction);
625 V newValue;
626 Entry<K, V> t = root;
627 if (t == null) {
628 newValue = getNewValueAndCheckModification(key, mappingFunction);
629 if (newValue != null) {
630 addEntryToEmptyMap(key, newValue);
631 return newValue;
632 } else {
633 return null;
634 }
635 }
636 int cmp;
637 Entry<K, V> parent;
638 // split comparator and comparable paths
639 Comparator<? super K> cpr = comparator;
640 if (cpr != null) {
641 do {
642 parent = t;
643 cmp = cpr.compare(key, t.key);
644 if (cmp < 0)
645 t = t.left;
646 else if (cmp > 0)
647 t = t.right;
648 else
649 return t.value;
650 } while (t != null);
651 } else {
652 if (key == null)
653 throw new NullPointerException();
654 @SuppressWarnings("unchecked")
655 Comparable<? super K> k = (Comparable<? super K>) key;
656 do {
657 parent = t;
658 cmp = k.compareTo(t.key);
659 if (cmp < 0)
660 t = t.left;
661 else if (cmp > 0)
662 t = t.right;
663 else
664 return t.value;
665 } while (t != null);
666 }
667 newValue = getNewValueAndCheckModification(key, mappingFunction);
668 if (newValue != null) {
669 addEntry(key, newValue, cmp, parent);
670 return newValue;
671 }
672 return null;
673 }
674
675 private V getNewValueAndCheckModification(K key, Function<? super K, ? extends V> mappingFunction) {
676 V newValue;
677 int mc = modCount;
678 newValue = mappingFunction.apply(key);
679 if (mc != modCount) {
680 throw new ConcurrentModificationException();
681 }
682 return newValue;
683 }
684
685 /**
686 * {@inheritDoc}
687 *
688 * <p>This method will, on a best-effort basis, throw a
689 * {@link ConcurrentModificationException} if it is detected that the
690 * remapping function modifies this map during computation.
691 *
692 * @throws ConcurrentModificationException if it is detected that the
693 * remapping function modified this map
694 */
695 @Override
696 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
697 Objects.requireNonNull(remappingFunction);
698 Entry<K, V> oldEntry = getEntry(key);
699 if (oldEntry != null && oldEntry.value != null) {
700 return remapValue(oldEntry, key, remappingFunction);
701 } else {
702 return null;
703 }
704 }
705
706 private V remapValue(Entry<K, V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
707 V newValue = getNewValueAndCheckModification(key, t.value, remappingFunction);
708 if (newValue == null) {
709 deleteEntry(t);
710 return null;
711 } else {
712 // replace old mapping
713 t.value = newValue;
714 return newValue;
715 }
716 }
717
718 private V getNewValueAndCheckModification(K key, V oldValue, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
719 int mc = modCount;
720 V newValue = remappingFunction.apply(key, oldValue);
721 if (mc != modCount) {
722 throw new ConcurrentModificationException();
723 }
724 return newValue;
725 }
726
727 /**
728 * {@inheritDoc}
729 *
730 * <p>This method will, on a best-effort basis, throw a
731 * {@link ConcurrentModificationException} if it is detected that the
732 * remapping function modifies this map during computation.
733 *
734 * @throws ConcurrentModificationException if it is detected that the
735 * remapping function modified this map
736 */
737 @Override
738 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
739 Objects.requireNonNull(remappingFunction);
740 V newValue;
741 Entry<K, V> t = root;
742 if (t == null) {
743 newValue = getNewValueAndCheckModification(key, null, remappingFunction);
744 if (newValue != null) {
745 addEntryToEmptyMap(key, newValue);
746 return newValue;
747 } else {
748 return null;
749 }
750 }
751 int cmp;
752 Entry<K, V> parent;
753 // split comparator and comparable paths
754 Comparator<? super K> cpr = comparator;
755 if (cpr != null) {
756 do {
757 parent = t;
758 cmp = cpr.compare(key, t.key);
759 if (cmp < 0)
760 t = t.left;
761 else if (cmp > 0)
762 t = t.right;
763 else
764 return remapValue(t, key, remappingFunction);
765 } while (t != null);
766 } else {
767 if (key == null)
768 throw new NullPointerException();
769 @SuppressWarnings("unchecked")
770 Comparable<? super K> k = (Comparable<? super K>) key;
771 do {
772 parent = t;
773 cmp = k.compareTo(t.key);
774 if (cmp < 0)
775 t = t.left;
776 else if (cmp > 0)
777 t = t.right;
778 else
779 return remapValue(t, key, remappingFunction);
780 } while (t != null);
781 }
782 newValue = getNewValueAndCheckModification(key, null, remappingFunction);
783 if (newValue != null) {
784 addEntry(key, newValue, cmp, parent);
785 return newValue;
786 }
787 return null;
788 }
789
790 /**
791 * {@inheritDoc}
792 *
793 * <p>This method will, on a best-effort basis, throw a
794 * {@link ConcurrentModificationException} if it is detected that the
795 * remapping function modifies this map during computation.
796 *
797 * @throws ConcurrentModificationException if it is detected that the
798 * remapping function modified this map
799 */
800 @Override
801 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
802 Objects.requireNonNull(remappingFunction);
803 Objects.requireNonNull(value);
804 Entry<K, V> t = root;
805 if (t == null) {
806 addEntryToEmptyMap(key, value);
807 return value;
808 }
809 int cmp;
810 Entry<K, V> parent;
811 // split comparator and comparable paths
812 Comparator<? super K> cpr = comparator;
813 if (cpr != null) {
814 do {
815 parent = t;
816 cmp = cpr.compare(key, t.key);
817 if (cmp < 0)
818 t = t.left;
819 else if (cmp > 0)
820 t = t.right;
821 else return mergeValue(t, value, remappingFunction);
822 } while (t != null);
823 } else {
824 if (key == null)
825 throw new NullPointerException();
826 @SuppressWarnings("unchecked")
827 Comparable<? super K> k = (Comparable<? super K>) key;
828 do {
829 parent = t;
830 cmp = k.compareTo(t.key);
831 if (cmp < 0)
832 t = t.left;
833 else if (cmp > 0)
834 t = t.right;
835 else return mergeValue(t, value, remappingFunction);
836 } while (t != null);
837 }
838 addEntry(key, value, cmp, parent);
839 return value;
840 }
841
842 private V mergeValue(Entry<K, V> t, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
843 V oldValue = t.value;
844 V newValue;
845 if (t.value == null) {
846 newValue = value;
847 } else {
848 int mc = modCount;
849 newValue = remappingFunction.apply(oldValue, value);
850 if (mc != modCount) {
851 throw new ConcurrentModificationException();
852 }
853 }
854 if (newValue == null) {
855 deleteEntry(t);
856 return null;
857 } else {
858 // replace old mapping
859 t.value = newValue;
860 return newValue;
861 }
862 }
863
864 /**
865 * Removes the mapping for this key from this TreeMap if present.
866 *
867 * @param key key for which mapping should be removed
868 * @return the previous value associated with {@code key}, or
869 * {@code null} if there was no mapping for {@code key}.
870 * (A {@code null} return can also indicate that the map
871 * previously associated {@code null} with {@code key}.)
872 * @throws ClassCastException if the specified key cannot be compared
873 * with the keys currently in the map
874 * @throws NullPointerException if the specified key is null
875 * and this map uses natural ordering, or its comparator
876 * does not permit null keys
877 */
878 public V remove(Object key) {
879 Entry<K,V> p = getEntry(key);
880 if (p == null)
881 return null;
|