| 1 |
|
/* |
| 2 |
< |
* %W% %E% |
| 2 |
> |
* Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. |
| 3 |
> |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 |
|
* |
| 5 |
< |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved. |
| 6 |
< |
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
| 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. Sun designates this |
| 8 |
> |
* particular file as subject to the "Classpath" exception as provided |
| 9 |
> |
* by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 |
> |
* CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 |
> |
* have any questions. |
| 24 |
|
*/ |
| 25 |
|
|
| 26 |
|
package java.util; |
| 1135 |
|
throw new IllegalStateException(); |
| 1136 |
|
if (modCount != expectedModCount) |
| 1137 |
|
throw new ConcurrentModificationException(); |
| 1138 |
+ |
// deleted entries are replaced by their successors |
| 1139 |
|
if (lastReturned.left != null && lastReturned.right != null) |
| 1140 |
|
next = lastReturned; |
| 1141 |
|
deleteEntry(lastReturned); |
| 1142 |
< |
expectedModCount++; |
| 1142 |
> |
expectedModCount = modCount; |
| 1143 |
|
lastReturned = null; |
| 1144 |
|
} |
| 1145 |
|
} |
| 1227 |
|
// SubMaps |
| 1228 |
|
|
| 1229 |
|
/** |
| 1230 |
+ |
* Dummy value serving as unmatchable fence key for unbounded |
| 1231 |
+ |
* SubMapIterators |
| 1232 |
+ |
*/ |
| 1233 |
+ |
private static final Object UNBOUNDED = new Object(); |
| 1234 |
+ |
|
| 1235 |
+ |
/** |
| 1236 |
|
* @serial include |
| 1237 |
|
*/ |
| 1238 |
|
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> |
| 1571 |
|
abstract class SubMapIterator<T> implements Iterator<T> { |
| 1572 |
|
TreeMap.Entry<K,V> lastReturned; |
| 1573 |
|
TreeMap.Entry<K,V> next; |
| 1574 |
< |
final K fenceKey; |
| 1574 |
> |
final Object fenceKey; |
| 1575 |
|
int expectedModCount; |
| 1576 |
|
|
| 1577 |
|
SubMapIterator(TreeMap.Entry<K,V> first, |
| 1579 |
|
expectedModCount = m.modCount; |
| 1580 |
|
lastReturned = null; |
| 1581 |
|
next = first; |
| 1582 |
< |
fenceKey = fence == null ? null : fence.key; |
| 1582 |
> |
fenceKey = fence == null ? UNBOUNDED : fence.key; |
| 1583 |
|
} |
| 1584 |
|
|
| 1585 |
|
public final boolean hasNext() { |
| 1606 |
|
return e; |
| 1607 |
|
} |
| 1608 |
|
|
| 1609 |
< |
public void remove() { |
| 1609 |
> |
final void removeAscending() { |
| 1610 |
|
if (lastReturned == null) |
| 1611 |
|
throw new IllegalStateException(); |
| 1612 |
|
if (m.modCount != expectedModCount) |
| 1613 |
|
throw new ConcurrentModificationException(); |
| 1614 |
+ |
// deleted entries are replaced by their successors |
| 1615 |
|
if (lastReturned.left != null && lastReturned.right != null) |
| 1616 |
|
next = lastReturned; |
| 1617 |
|
m.deleteEntry(lastReturned); |
| 1592 |
– |
expectedModCount++; |
| 1618 |
|
lastReturned = null; |
| 1619 |
+ |
expectedModCount = m.modCount; |
| 1620 |
+ |
} |
| 1621 |
+ |
|
| 1622 |
+ |
final void removeDescending() { |
| 1623 |
+ |
if (lastReturned == null) |
| 1624 |
+ |
throw new IllegalStateException(); |
| 1625 |
+ |
if (m.modCount != expectedModCount) |
| 1626 |
+ |
throw new ConcurrentModificationException(); |
| 1627 |
+ |
m.deleteEntry(lastReturned); |
| 1628 |
+ |
lastReturned = null; |
| 1629 |
+ |
expectedModCount = m.modCount; |
| 1630 |
|
} |
| 1631 |
+ |
|
| 1632 |
|
} |
| 1633 |
|
|
| 1634 |
|
final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { |
| 1639 |
|
public Map.Entry<K,V> next() { |
| 1640 |
|
return nextEntry(); |
| 1641 |
|
} |
| 1642 |
+ |
public void remove() { |
| 1643 |
+ |
removeAscending(); |
| 1644 |
+ |
} |
| 1645 |
|
} |
| 1646 |
|
|
| 1647 |
|
final class SubMapKeyIterator extends SubMapIterator<K> { |
| 1652 |
|
public K next() { |
| 1653 |
|
return nextEntry().key; |
| 1654 |
|
} |
| 1655 |
+ |
public void remove() { |
| 1656 |
+ |
removeAscending(); |
| 1657 |
+ |
} |
| 1658 |
|
} |
| 1659 |
|
|
| 1660 |
|
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { |
| 1666 |
|
public Map.Entry<K,V> next() { |
| 1667 |
|
return prevEntry(); |
| 1668 |
|
} |
| 1669 |
+ |
public void remove() { |
| 1670 |
+ |
removeDescending(); |
| 1671 |
+ |
} |
| 1672 |
|
} |
| 1673 |
|
|
| 1674 |
|
final class DescendingSubMapKeyIterator extends SubMapIterator<K> { |
| 1679 |
|
public K next() { |
| 1680 |
|
return prevEntry().key; |
| 1681 |
|
} |
| 1682 |
+ |
public void remove() { |
| 1683 |
+ |
removeDescending(); |
| 1684 |
+ |
} |
| 1685 |
|
} |
| 1686 |
|
} |
| 1687 |
|
|
| 1713 |
|
} |
| 1714 |
|
|
| 1715 |
|
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| 1716 |
< |
if (!inClosedRange(toKey)) |
| 1716 |
> |
if (!inRange(toKey, inclusive)) |
| 1717 |
|
throw new IllegalArgumentException("toKey out of range"); |
| 1718 |
|
return new AscendingSubMap(m, |
| 1719 |
|
fromStart, lo, loInclusive, |
| 2377 |
|
|
| 2378 |
|
if (hi < lo) return null; |
| 2379 |
|
|
| 2380 |
< |
int mid = (lo + hi) / 2; |
| 2380 |
> |
int mid = (lo + hi) >>> 1; |
| 2381 |
|
|
| 2382 |
|
Entry<K,V> left = null; |
| 2383 |
|
if (lo < mid) |
