src/share/classes/java/util/TreeMap.java

Print this page




1039         public Iterator<E> descendingIterator() {
1040             if (m instanceof TreeMap)
1041                 return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042             else
1043                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044         }
1045 
1046         public int size() { return m.size(); }
1047         public boolean isEmpty() { return m.isEmpty(); }
1048         public boolean contains(Object o) { return m.containsKey(o); }
1049         public void clear() { m.clear(); }
1050         public E lower(E e) { return m.lowerKey(e); }
1051         public E floor(E e) { return m.floorKey(e); }
1052         public E ceiling(E e) { return m.ceilingKey(e); }
1053         public E higher(E e) { return m.higherKey(e); }
1054         public E first() { return m.firstKey(); }
1055         public E last() { return m.lastKey(); }
1056         public Comparator<? super E> comparator() { return m.comparator(); }
1057         public E pollFirst() {
1058             Map.Entry<E,Object> e = m.pollFirstEntry();
1059             return e == null? null : e.getKey();
1060         }
1061         public E pollLast() {
1062             Map.Entry<E,Object> e = m.pollLastEntry();
1063             return e == null? null : e.getKey();
1064         }
1065         public boolean remove(Object o) {
1066             int oldSize = size();
1067             m.remove(o);
1068             return size() != oldSize;
1069         }
1070         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071                                       E toElement,   boolean toInclusive) {
1072             return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1073                                           toElement,   toInclusive));
1074         }
1075         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076             return new KeySet<E>(m.headMap(toElement, inclusive));
1077         }
1078         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079             return new KeySet<E>(m.tailMap(fromElement, inclusive));
1080         }
1081         public SortedSet<E> subSet(E fromElement, E toElement) {
1082             return subSet(fromElement, true, toElement, false);
1083         }


1179         }
1180         public K next() {
1181             return prevEntry().key;
1182         }
1183     }
1184 
1185     // Little utilities
1186 
1187     /**
1188      * Compares two keys using the correct comparison method for this TreeMap.
1189      */
1190     final int compare(Object k1, Object k2) {
1191         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192             : comparator.compare((K)k1, (K)k2);
1193     }
1194 
1195     /**
1196      * Test two values for equality.  Differs from o1.equals(o2) only in
1197      * that it copes with {@code null} o1 properly.
1198      */
1199     final static boolean valEquals(Object o1, Object o2) {
1200         return (o1==null ? o2==null : o1.equals(o2));
1201     }
1202 
1203     /**
1204      * Return SimpleImmutableEntry for entry, or null if null
1205      */
1206     static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207         return e == null? null :
1208             new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209     }
1210 
1211     /**
1212      * Return key for entry, or null if null
1213      */
1214     static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215         return e == null? null : e.key;
1216     }
1217 
1218     /**
1219      * Returns the key corresponding to the specified Entry.
1220      * @throws NoSuchElementException if the Entry is null
1221      */
1222     static <K> K key(Entry<K,?> e) {
1223         if (e==null)
1224             throw new NoSuchElementException();
1225         return e.key;
1226     }
1227 
1228 
1229     // SubMaps
1230 
1231     /**
1232      * Dummy value serving as unmatchable fence key for unbounded
1233      * SubMapIterators
1234      */
1235     private static final Object UNBOUNDED = new Object();
1236 
1237     /**
1238      * @serial include
1239      */
1240     static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241         implements NavigableMap<K,V>, java.io.Serializable {
1242         /**
1243          * The backing map.
1244          */
1245         final TreeMap<K,V> m;
1246 
1247         /**
1248          * Endpoints are represented as triples (fromStart, lo,
1249          * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250          * true, then the low (absolute) bound is the start of the
1251          * backing map, and the other values are ignored. Otherwise,
1252          * if loInclusive is true, lo is the inclusive bound, else lo
1253          * is the exclusive bound. Similarly for the upper bound.
1254          */
1255         final K lo, hi;
1256         final boolean fromStart, toEnd;
1257         final boolean loInclusive, hiInclusive;
1258 
1259         NavigableSubMap(TreeMap<K,V> m,
1260                         boolean fromStart, K lo, boolean loInclusive,


1395 
1396         public boolean isEmpty() {
1397             return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398         }
1399 
1400         public int size() {
1401             return (fromStart && toEnd) ? m.size() : entrySet().size();
1402         }
1403 
1404         public final boolean containsKey(Object key) {
1405             return inRange(key) && m.containsKey(key);
1406         }
1407 
1408         public final V put(K key, V value) {
1409             if (!inRange(key))
1410                 throw new IllegalArgumentException("key out of range");
1411             return m.put(key, value);
1412         }
1413 
1414         public final V get(Object key) {
1415             return !inRange(key)? null :  m.get(key);
1416         }
1417 
1418         public final V remove(Object key) {
1419             return !inRange(key)? null  : m.remove(key);
1420         }
1421 
1422         public final Map.Entry<K,V> ceilingEntry(K key) {
1423             return exportEntry(subCeiling(key));
1424         }
1425 
1426         public final K ceilingKey(K key) {
1427             return keyOrNull(subCeiling(key));
1428         }
1429 
1430         public final Map.Entry<K,V> higherEntry(K key) {
1431             return exportEntry(subHigher(key));
1432         }
1433 
1434         public final K higherKey(K key) {
1435             return keyOrNull(subHigher(key));
1436         }
1437 
1438         public final Map.Entry<K,V> floorEntry(K key) {
1439             return exportEntry(subFloor(key));


1542             public boolean contains(Object o) {
1543                 if (!(o instanceof Map.Entry))
1544                     return false;
1545                 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1546                 K key = entry.getKey();
1547                 if (!inRange(key))
1548                     return false;
1549                 TreeMap.Entry node = m.getEntry(key);
1550                 return node != null &&
1551                     valEquals(node.getValue(), entry.getValue());
1552             }
1553 
1554             public boolean remove(Object o) {
1555                 if (!(o instanceof Map.Entry))
1556                     return false;
1557                 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1558                 K key = entry.getKey();
1559                 if (!inRange(key))
1560                     return false;
1561                 TreeMap.Entry<K,V> node = m.getEntry(key);
1562                 if (node!=null && valEquals(node.getValue(),entry.getValue())){

1563                     m.deleteEntry(node);
1564                     return true;
1565                 }
1566                 return false;
1567             }
1568         }
1569 
1570         /**
1571          * Iterators for SubMaps
1572          */
1573         abstract class SubMapIterator<T> implements Iterator<T> {
1574             TreeMap.Entry<K,V> lastReturned;
1575             TreeMap.Entry<K,V> next;
1576             final Object fenceKey;
1577             int expectedModCount;
1578 
1579             SubMapIterator(TreeMap.Entry<K,V> first,
1580                            TreeMap.Entry<K,V> fence) {
1581                 expectedModCount = m.modCount;
1582                 lastReturned = null;


1707 
1708         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1709                                         K toKey,   boolean toInclusive) {
1710             if (!inRange(fromKey, fromInclusive))
1711                 throw new IllegalArgumentException("fromKey out of range");
1712             if (!inRange(toKey, toInclusive))
1713                 throw new IllegalArgumentException("toKey out of range");
1714             return new AscendingSubMap(m,
1715                                        false, fromKey, fromInclusive,
1716                                        false, toKey,   toInclusive);
1717         }
1718 
1719         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1720             if (!inRange(toKey, inclusive))
1721                 throw new IllegalArgumentException("toKey out of range");
1722             return new AscendingSubMap(m,
1723                                        fromStart, lo,    loInclusive,
1724                                        false,     toKey, inclusive);
1725         }
1726 
1727         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1728             if (!inRange(fromKey, inclusive))
1729                 throw new IllegalArgumentException("fromKey out of range");
1730             return new AscendingSubMap(m,
1731                                        false, fromKey, inclusive,
1732                                        toEnd, hi,      hiInclusive);
1733         }
1734 
1735         public NavigableMap<K,V> descendingMap() {
1736             NavigableMap<K,V> mv = descendingMapView;
1737             return (mv != null) ? mv :
1738                 (descendingMapView =
1739                  new DescendingSubMap(m,
1740                                       fromStart, lo, loInclusive,
1741                                       toEnd,     hi, hiInclusive));
1742         }
1743 
1744         Iterator<K> keyIterator() {
1745             return new SubMapKeyIterator(absLowest(), absHighFence());
1746         }
1747 


1788 
1789         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1790                                         K toKey,   boolean toInclusive) {
1791             if (!inRange(fromKey, fromInclusive))
1792                 throw new IllegalArgumentException("fromKey out of range");
1793             if (!inRange(toKey, toInclusive))
1794                 throw new IllegalArgumentException("toKey out of range");
1795             return new DescendingSubMap(m,
1796                                         false, toKey,   toInclusive,
1797                                         false, fromKey, fromInclusive);
1798         }
1799 
1800         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1801             if (!inRange(toKey, inclusive))
1802                 throw new IllegalArgumentException("toKey out of range");
1803             return new DescendingSubMap(m,
1804                                         false, toKey, inclusive,
1805                                         toEnd, hi,    hiInclusive);
1806         }
1807 
1808         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1809             if (!inRange(fromKey, inclusive))
1810                 throw new IllegalArgumentException("fromKey out of range");
1811             return new DescendingSubMap(m,
1812                                         fromStart, lo, loInclusive,
1813                                         false, fromKey, inclusive);
1814         }
1815 
1816         public NavigableMap<K,V> descendingMap() {
1817             NavigableMap<K,V> mv = descendingMapView;
1818             return (mv != null) ? mv :
1819                 (descendingMapView =
1820                  new AscendingSubMap(m,
1821                                      fromStart, lo, loInclusive,
1822                                      toEnd,     hi, hiInclusive));
1823         }
1824 
1825         Iterator<K> keyIterator() {
1826             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1827         }
1828 


2126                     }
2127                     setColor(parentOf(x), BLACK);
2128                     setColor(parentOf(parentOf(x)), RED);
2129                     rotateLeft(parentOf(parentOf(x)));
2130                 }
2131             }
2132         }
2133         root.color = BLACK;
2134     }
2135 
2136     /**
2137      * Delete node p, and then rebalance the tree.
2138      */
2139     private void deleteEntry(Entry<K,V> p) {
2140         modCount++;
2141         size--;
2142 
2143         // If strictly internal, copy successor's element to p and then make p
2144         // point to successor.
2145         if (p.left != null && p.right != null) {
2146             Entry<K,V> s = successor (p);
2147             p.key = s.key;
2148             p.value = s.value;
2149             p = s;
2150         } // p has 2 children
2151 
2152         // Start fixup at replacement node, if it exists.
2153         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2154 
2155         if (replacement != null) {
2156             // Link replacement to parent
2157             replacement.parent = p.parent;
2158             if (p.parent == null)
2159                 root = replacement;
2160             else if (p == p.parent.left)
2161                 p.parent.left  = replacement;
2162             else
2163                 p.parent.right = replacement;
2164 
2165             // Null out links so they are OK to use by fixAfterDeletion.
2166             p.left = p.right = p.parent = null;




1039         public Iterator<E> descendingIterator() {
1040             if (m instanceof TreeMap)
1041                 return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042             else
1043                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044         }
1045 
1046         public int size() { return m.size(); }
1047         public boolean isEmpty() { return m.isEmpty(); }
1048         public boolean contains(Object o) { return m.containsKey(o); }
1049         public void clear() { m.clear(); }
1050         public E lower(E e) { return m.lowerKey(e); }
1051         public E floor(E e) { return m.floorKey(e); }
1052         public E ceiling(E e) { return m.ceilingKey(e); }
1053         public E higher(E e) { return m.higherKey(e); }
1054         public E first() { return m.firstKey(); }
1055         public E last() { return m.lastKey(); }
1056         public Comparator<? super E> comparator() { return m.comparator(); }
1057         public E pollFirst() {
1058             Map.Entry<E,Object> e = m.pollFirstEntry();
1059             return (e == null) ? null : e.getKey();
1060         }
1061         public E pollLast() {
1062             Map.Entry<E,Object> e = m.pollLastEntry();
1063             return (e == null) ? null : e.getKey();
1064         }
1065         public boolean remove(Object o) {
1066             int oldSize = size();
1067             m.remove(o);
1068             return size() != oldSize;
1069         }
1070         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071                                       E toElement,   boolean toInclusive) {
1072             return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1073                                           toElement,   toInclusive));
1074         }
1075         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076             return new KeySet<E>(m.headMap(toElement, inclusive));
1077         }
1078         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079             return new KeySet<E>(m.tailMap(fromElement, inclusive));
1080         }
1081         public SortedSet<E> subSet(E fromElement, E toElement) {
1082             return subSet(fromElement, true, toElement, false);
1083         }


1179         }
1180         public K next() {
1181             return prevEntry().key;
1182         }
1183     }
1184 
1185     // Little utilities
1186 
1187     /**
1188      * Compares two keys using the correct comparison method for this TreeMap.
1189      */
1190     final int compare(Object k1, Object k2) {
1191         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192             : comparator.compare((K)k1, (K)k2);
1193     }
1194 
1195     /**
1196      * Test two values for equality.  Differs from o1.equals(o2) only in
1197      * that it copes with {@code null} o1 properly.
1198      */
1199     static final boolean valEquals(Object o1, Object o2) {
1200         return (o1==null ? o2==null : o1.equals(o2));
1201     }
1202 
1203     /**
1204      * Return SimpleImmutableEntry for entry, or null if null
1205      */
1206     static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207         return (e == null) ? null :
1208             new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209     }
1210 
1211     /**
1212      * Return key for entry, or null if null
1213      */
1214     static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215         return (e == null) ? null : e.key;
1216     }
1217 
1218     /**
1219      * Returns the key corresponding to the specified Entry.
1220      * @throws NoSuchElementException if the Entry is null
1221      */
1222     static <K> K key(Entry<K,?> e) {
1223         if (e==null)
1224             throw new NoSuchElementException();
1225         return e.key;
1226     }
1227 
1228 
1229     // SubMaps
1230 
1231     /**
1232      * Dummy value serving as unmatchable fence key for unbounded
1233      * SubMapIterators
1234      */
1235     private static final Object UNBOUNDED = new Object();
1236 
1237     /**
1238      * @serial include
1239      */
1240     abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241         implements NavigableMap<K,V>, java.io.Serializable {
1242         /**
1243          * The backing map.
1244          */
1245         final TreeMap<K,V> m;
1246 
1247         /**
1248          * Endpoints are represented as triples (fromStart, lo,
1249          * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250          * true, then the low (absolute) bound is the start of the
1251          * backing map, and the other values are ignored. Otherwise,
1252          * if loInclusive is true, lo is the inclusive bound, else lo
1253          * is the exclusive bound. Similarly for the upper bound.
1254          */
1255         final K lo, hi;
1256         final boolean fromStart, toEnd;
1257         final boolean loInclusive, hiInclusive;
1258 
1259         NavigableSubMap(TreeMap<K,V> m,
1260                         boolean fromStart, K lo, boolean loInclusive,


1395 
1396         public boolean isEmpty() {
1397             return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398         }
1399 
1400         public int size() {
1401             return (fromStart && toEnd) ? m.size() : entrySet().size();
1402         }
1403 
1404         public final boolean containsKey(Object key) {
1405             return inRange(key) && m.containsKey(key);
1406         }
1407 
1408         public final V put(K key, V value) {
1409             if (!inRange(key))
1410                 throw new IllegalArgumentException("key out of range");
1411             return m.put(key, value);
1412         }
1413 
1414         public final V get(Object key) {
1415             return !inRange(key) ? null :  m.get(key);
1416         }
1417 
1418         public final V remove(Object key) {
1419             return !inRange(key) ? null : m.remove(key);
1420         }
1421 
1422         public final Map.Entry<K,V> ceilingEntry(K key) {
1423             return exportEntry(subCeiling(key));
1424         }
1425 
1426         public final K ceilingKey(K key) {
1427             return keyOrNull(subCeiling(key));
1428         }
1429 
1430         public final Map.Entry<K,V> higherEntry(K key) {
1431             return exportEntry(subHigher(key));
1432         }
1433 
1434         public final K higherKey(K key) {
1435             return keyOrNull(subHigher(key));
1436         }
1437 
1438         public final Map.Entry<K,V> floorEntry(K key) {
1439             return exportEntry(subFloor(key));


1542             public boolean contains(Object o) {
1543                 if (!(o instanceof Map.Entry))
1544                     return false;
1545                 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1546                 K key = entry.getKey();
1547                 if (!inRange(key))
1548                     return false;
1549                 TreeMap.Entry node = m.getEntry(key);
1550                 return node != null &&
1551                     valEquals(node.getValue(), entry.getValue());
1552             }
1553 
1554             public boolean remove(Object o) {
1555                 if (!(o instanceof Map.Entry))
1556                     return false;
1557                 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1558                 K key = entry.getKey();
1559                 if (!inRange(key))
1560                     return false;
1561                 TreeMap.Entry<K,V> node = m.getEntry(key);
1562                 if (node!=null && valEquals(node.getValue(),
1563                                             entry.getValue())) {
1564                     m.deleteEntry(node);
1565                     return true;
1566                 }
1567                 return false;
1568             }
1569         }
1570 
1571         /**
1572          * Iterators for SubMaps
1573          */
1574         abstract class SubMapIterator<T> implements Iterator<T> {
1575             TreeMap.Entry<K,V> lastReturned;
1576             TreeMap.Entry<K,V> next;
1577             final Object fenceKey;
1578             int expectedModCount;
1579 
1580             SubMapIterator(TreeMap.Entry<K,V> first,
1581                            TreeMap.Entry<K,V> fence) {
1582                 expectedModCount = m.modCount;
1583                 lastReturned = null;


1708 
1709         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1710                                         K toKey,   boolean toInclusive) {
1711             if (!inRange(fromKey, fromInclusive))
1712                 throw new IllegalArgumentException("fromKey out of range");
1713             if (!inRange(toKey, toInclusive))
1714                 throw new IllegalArgumentException("toKey out of range");
1715             return new AscendingSubMap(m,
1716                                        false, fromKey, fromInclusive,
1717                                        false, toKey,   toInclusive);
1718         }
1719 
1720         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1721             if (!inRange(toKey, inclusive))
1722                 throw new IllegalArgumentException("toKey out of range");
1723             return new AscendingSubMap(m,
1724                                        fromStart, lo,    loInclusive,
1725                                        false,     toKey, inclusive);
1726         }
1727 
1728         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1729             if (!inRange(fromKey, inclusive))
1730                 throw new IllegalArgumentException("fromKey out of range");
1731             return new AscendingSubMap(m,
1732                                        false, fromKey, inclusive,
1733                                        toEnd, hi,      hiInclusive);
1734         }
1735 
1736         public NavigableMap<K,V> descendingMap() {
1737             NavigableMap<K,V> mv = descendingMapView;
1738             return (mv != null) ? mv :
1739                 (descendingMapView =
1740                  new DescendingSubMap(m,
1741                                       fromStart, lo, loInclusive,
1742                                       toEnd,     hi, hiInclusive));
1743         }
1744 
1745         Iterator<K> keyIterator() {
1746             return new SubMapKeyIterator(absLowest(), absHighFence());
1747         }
1748 


1789 
1790         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1791                                         K toKey,   boolean toInclusive) {
1792             if (!inRange(fromKey, fromInclusive))
1793                 throw new IllegalArgumentException("fromKey out of range");
1794             if (!inRange(toKey, toInclusive))
1795                 throw new IllegalArgumentException("toKey out of range");
1796             return new DescendingSubMap(m,
1797                                         false, toKey,   toInclusive,
1798                                         false, fromKey, fromInclusive);
1799         }
1800 
1801         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1802             if (!inRange(toKey, inclusive))
1803                 throw new IllegalArgumentException("toKey out of range");
1804             return new DescendingSubMap(m,
1805                                         false, toKey, inclusive,
1806                                         toEnd, hi,    hiInclusive);
1807         }
1808 
1809         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1810             if (!inRange(fromKey, inclusive))
1811                 throw new IllegalArgumentException("fromKey out of range");
1812             return new DescendingSubMap(m,
1813                                         fromStart, lo, loInclusive,
1814                                         false, fromKey, inclusive);
1815         }
1816 
1817         public NavigableMap<K,V> descendingMap() {
1818             NavigableMap<K,V> mv = descendingMapView;
1819             return (mv != null) ? mv :
1820                 (descendingMapView =
1821                  new AscendingSubMap(m,
1822                                      fromStart, lo, loInclusive,
1823                                      toEnd,     hi, hiInclusive));
1824         }
1825 
1826         Iterator<K> keyIterator() {
1827             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1828         }
1829 


2127                     }
2128                     setColor(parentOf(x), BLACK);
2129                     setColor(parentOf(parentOf(x)), RED);
2130                     rotateLeft(parentOf(parentOf(x)));
2131                 }
2132             }
2133         }
2134         root.color = BLACK;
2135     }
2136 
2137     /**
2138      * Delete node p, and then rebalance the tree.
2139      */
2140     private void deleteEntry(Entry<K,V> p) {
2141         modCount++;
2142         size--;
2143 
2144         // If strictly internal, copy successor's element to p and then make p
2145         // point to successor.
2146         if (p.left != null && p.right != null) {
2147             Entry<K,V> s = successor(p);
2148             p.key = s.key;
2149             p.value = s.value;
2150             p = s;
2151         } // p has 2 children
2152 
2153         // Start fixup at replacement node, if it exists.
2154         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2155 
2156         if (replacement != null) {
2157             // Link replacement to parent
2158             replacement.parent = p.parent;
2159             if (p.parent == null)
2160                 root = replacement;
2161             else if (p == p.parent.left)
2162                 p.parent.left  = replacement;
2163             else
2164                 p.parent.right = replacement;
2165 
2166             // Null out links so they are OK to use by fixAfterDeletion.
2167             p.left = p.right = p.parent = null;