| 902 |
|
NavigableMap<K, V> km = descendingMap; |
| 903 |
|
return (km != null) ? km : |
| 904 |
|
(descendingMap = new DescendingSubMap(this, |
| 905 |
< |
true, null, 0, |
| 906 |
< |
true, null, 0)); |
| 905 |
> |
true, null, true, |
| 906 |
> |
true, null, true)); |
| 907 |
|
} |
| 908 |
|
|
| 909 |
|
/** |
| 917 |
|
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| 918 |
|
K toKey, boolean toInclusive) { |
| 919 |
|
return new AscendingSubMap(this, |
| 920 |
< |
false, fromKey, excluded(fromInclusive), |
| 921 |
< |
false, toKey, excluded(toInclusive)); |
| 920 |
> |
false, fromKey, fromInclusive, |
| 921 |
> |
false, toKey, toInclusive); |
| 922 |
|
} |
| 923 |
|
|
| 924 |
|
/** |
| 931 |
|
*/ |
| 932 |
|
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| 933 |
|
return new AscendingSubMap(this, |
| 934 |
< |
true, null, 0, |
| 935 |
< |
false, toKey, excluded(inclusive)); |
| 934 |
> |
true, null, true, |
| 935 |
> |
false, toKey, inclusive); |
| 936 |
|
} |
| 937 |
|
|
| 938 |
|
/** |
| 945 |
|
*/ |
| 946 |
|
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
| 947 |
|
return new AscendingSubMap(this, |
| 948 |
< |
false, fromKey, excluded(inclusive), |
| 949 |
< |
true, null, 0); |
| 950 |
< |
} |
| 951 |
< |
|
| 952 |
< |
/** |
| 953 |
< |
* Translates a boolean "inclusive" value to the correct int value |
| 954 |
< |
* for the loExcluded or hiExcluded field. |
| 955 |
< |
*/ |
| 956 |
< |
static int excluded(boolean inclusive) { |
| 957 |
< |
return inclusive ? 0 : 1; |
| 948 |
> |
false, fromKey, inclusive, |
| 949 |
> |
true, null, true); |
| 950 |
|
} |
| 951 |
|
|
| 952 |
|
/** |
| 1225 |
|
|
| 1226 |
|
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> |
| 1227 |
|
implements NavigableMap<K,V>, java.io.Serializable { |
| 1236 |
– |
|
| 1228 |
|
/* |
| 1229 |
|
* The backing map. |
| 1230 |
|
*/ |
| 1231 |
|
final TreeMap<K,V> m; |
| 1232 |
|
|
| 1233 |
|
/* |
| 1234 |
< |
* Endpoints are represented as triples (fromStart, lo, loExcluded) |
| 1235 |
< |
* and (toEnd, hi, hiExcluded). If fromStart is true, then |
| 1236 |
< |
* the low (absolute) bound is the start of the backing map, and the |
| 1237 |
< |
* other values are ignored. Otherwise, if loExcluded is |
| 1238 |
< |
* zero, lo is the inclusive bound, else loExcluded is one, |
| 1239 |
< |
* and lo is the exclusive bound. Similarly for the upper bound. |
| 1234 |
> |
* Endpoints are represented as triples (fromStart, lo, |
| 1235 |
> |
* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is |
| 1236 |
> |
* true, then the low (absolute) bound is the start of the |
| 1237 |
> |
* backing map, and the other values are ignored. Otherwise, |
| 1238 |
> |
* if loInclusive is true, lo is the inclusive bound, else lo |
| 1239 |
> |
* is the exclusive bound. Similarly for the upper bound. |
| 1240 |
|
*/ |
| 1241 |
|
|
| 1242 |
|
final K lo, hi; |
| 1243 |
|
final boolean fromStart, toEnd; |
| 1244 |
< |
final int loExcluded, hiExcluded; |
| 1244 |
> |
final boolean loInclusive, hiInclusive; |
| 1245 |
|
|
| 1246 |
|
NavigableSubMap(TreeMap<K,V> m, |
| 1247 |
< |
boolean fromStart, K lo, int loExcluded, |
| 1248 |
< |
boolean toEnd, K hi, int hiExcluded) { |
| 1247 |
> |
boolean fromStart, K lo, boolean loInclusive, |
| 1248 |
> |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1249 |
|
if (!fromStart && !toEnd) { |
| 1250 |
|
if (m.compare(lo, hi) > 0) |
| 1251 |
|
throw new IllegalArgumentException("fromKey > toKey"); |
| 1252 |
+ |
} else { |
| 1253 |
+ |
if (!fromStart) // type check |
| 1254 |
+ |
m.compare(lo, lo); |
| 1255 |
+ |
if (!toEnd) |
| 1256 |
+ |
m.compare(hi, hi); |
| 1257 |
|
} |
| 1262 |
– |
else if (!fromStart) // type check |
| 1263 |
– |
m.compare(lo, lo); |
| 1264 |
– |
else if (!toEnd) |
| 1265 |
– |
m.compare(hi, hi); |
| 1258 |
|
|
| 1259 |
|
this.m = m; |
| 1260 |
|
this.fromStart = fromStart; |
| 1261 |
|
this.lo = lo; |
| 1262 |
< |
this.loExcluded = loExcluded; |
| 1262 |
> |
this.loInclusive = loInclusive; |
| 1263 |
|
this.toEnd = toEnd; |
| 1264 |
|
this.hi = hi; |
| 1265 |
< |
this.hiExcluded = hiExcluded; |
| 1265 |
> |
this.hiInclusive = hiInclusive; |
| 1266 |
|
} |
| 1267 |
|
|
| 1268 |
|
// internal utilities |
| 1269 |
|
|
| 1270 |
+ |
final boolean tooLow(Object key) { |
| 1271 |
+ |
if (!fromStart) { |
| 1272 |
+ |
int c = m.compare(key, lo); |
| 1273 |
+ |
if (c < 0 || (c == 0 && !loInclusive)) |
| 1274 |
+ |
return true; |
| 1275 |
+ |
} |
| 1276 |
+ |
return false; |
| 1277 |
+ |
} |
| 1278 |
+ |
|
| 1279 |
+ |
final boolean tooHigh(Object key) { |
| 1280 |
+ |
if (!toEnd) { |
| 1281 |
+ |
int c = m.compare(key, hi); |
| 1282 |
+ |
if (c > 0 || (c == 0 && !hiInclusive)) |
| 1283 |
+ |
return true; |
| 1284 |
+ |
} |
| 1285 |
+ |
return false; |
| 1286 |
+ |
} |
| 1287 |
+ |
|
| 1288 |
|
final boolean inRange(Object key) { |
| 1289 |
< |
return (fromStart || m.compare(key, lo) >= loExcluded) |
| 1280 |
< |
&& (toEnd || m.compare(hi, key) >= hiExcluded); |
| 1289 |
> |
return !tooLow(key) && !tooHigh(key); |
| 1290 |
|
} |
| 1291 |
|
|
| 1292 |
|
final boolean inClosedRange(Object key) { |
| 1298 |
|
return inclusive ? inRange(key) : inClosedRange(key); |
| 1299 |
|
} |
| 1300 |
|
|
| 1301 |
< |
final boolean tooLow(K key) { |
| 1302 |
< |
return !fromStart && m.compare(key, lo) < loExcluded; |
| 1301 |
> |
/** |
| 1302 |
> |
* Return SimpleImmutableEntry for entry, or null if null |
| 1303 |
> |
*/ |
| 1304 |
> |
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { |
| 1305 |
> |
return e == null? null : |
| 1306 |
> |
new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1307 |
|
} |
| 1308 |
|
|
| 1309 |
< |
final boolean tooHigh(K key) { |
| 1310 |
< |
return !toEnd && m.compare(hi, key) < hiExcluded; |
| 1309 |
> |
/** |
| 1310 |
> |
* Return key for entry, or null if null |
| 1311 |
> |
*/ |
| 1312 |
> |
static <K,V> K exportKey(TreeMap.Entry<K,V> e) { |
| 1313 |
> |
return e == null? null : e.key; |
| 1314 |
|
} |
| 1315 |
|
|
| 1316 |
< |
/** Returns the lowest entry in this submap (absolute ordering) */ |
| 1317 |
< |
final TreeMap.Entry<K,V> loEntry() { |
| 1318 |
< |
TreeMap.Entry<K,V> result = |
| 1316 |
> |
/* |
| 1317 |
> |
* Absolute versions of relation operations. |
| 1318 |
> |
* Subclasses map to these using like-named "sub" |
| 1319 |
> |
* versions that invert senses for descending maps |
| 1320 |
> |
*/ |
| 1321 |
> |
|
| 1322 |
> |
final TreeMap.Entry<K,V> absLowest() { |
| 1323 |
> |
TreeMap.Entry<K,V> e = |
| 1324 |
|
(fromStart ? m.getFirstEntry() : |
| 1325 |
< |
(loExcluded == 0 ? m.getCeilingEntry(lo) : |
| 1326 |
< |
m.getHigherEntry(lo))); |
| 1327 |
< |
return (result == null || tooHigh(result.key)) ? null : result; |
| 1325 |
> |
(loInclusive ? m.getCeilingEntry(lo) : |
| 1326 |
> |
m.getHigherEntry(lo))); |
| 1327 |
> |
return (e == null || tooHigh(e.key)) ? null : e; |
| 1328 |
|
} |
| 1329 |
|
|
| 1330 |
< |
/** Returns the highest key in this submap (absolute ordering) */ |
| 1331 |
< |
final TreeMap.Entry<K,V> hiEntry() { |
| 1311 |
< |
TreeMap.Entry<K,V> result = |
| 1330 |
> |
final TreeMap.Entry<K,V> absHighest() { |
| 1331 |
> |
TreeMap.Entry<K,V> e = |
| 1332 |
|
(toEnd ? m.getLastEntry() : |
| 1333 |
< |
(hiExcluded == 0 ? m.getFloorEntry(hi) : |
| 1334 |
< |
m.getLowerEntry(hi))); |
| 1335 |
< |
return (result == null || tooLow(result.key)) ? null : result; |
| 1333 |
> |
(hiInclusive ? m.getFloorEntry(hi) : |
| 1334 |
> |
m.getLowerEntry(hi))); |
| 1335 |
> |
return (e == null || tooLow(e.key)) ? null : e; |
| 1336 |
|
} |
| 1337 |
< |
|
| 1338 |
< |
/** Polls the lowest entry in this submap (absolute ordering) */ |
| 1339 |
< |
final Map.Entry<K,V> pollLoEntry() { |
| 1340 |
< |
TreeMap.Entry<K,V> e = loEntry(); |
| 1341 |
< |
if (e == null) |
| 1342 |
< |
return null; |
| 1323 |
< |
Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1324 |
< |
m.deleteEntry(e); |
| 1325 |
< |
return result; |
| 1337 |
> |
|
| 1338 |
> |
final TreeMap.Entry<K,V> absCeiling(K key) { |
| 1339 |
> |
if (tooLow(key)) |
| 1340 |
> |
return absLowest(); |
| 1341 |
> |
TreeMap.Entry<K,V> e = m.getCeilingEntry(key); |
| 1342 |
> |
return (e == null || tooHigh(e.key)) ? null : e; |
| 1343 |
|
} |
| 1344 |
|
|
| 1345 |
< |
/** Polls the highest key in this submap (absolute ordering) */ |
| 1346 |
< |
final Map.Entry<K,V> pollHiEntry() { |
| 1347 |
< |
TreeMap.Entry<K,V> e = hiEntry(); |
| 1348 |
< |
if (e == null) |
| 1349 |
< |
return null; |
| 1333 |
< |
Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1334 |
< |
m.deleteEntry(e); |
| 1335 |
< |
return result; |
| 1345 |
> |
final TreeMap.Entry<K,V> absHigher(K key) { |
| 1346 |
> |
if (tooLow(key)) |
| 1347 |
> |
return absLowest(); |
| 1348 |
> |
TreeMap.Entry<K,V> e = m.getHigherEntry(key); |
| 1349 |
> |
return (e == null || tooHigh(e.key)) ? null : e; |
| 1350 |
|
} |
| 1351 |
|
|
| 1352 |
< |
/** |
| 1353 |
< |
* Return the absolute high fence for ascending traversal |
| 1354 |
< |
*/ |
| 1355 |
< |
final TreeMap.Entry<K,V> hiFence() { |
| 1356 |
< |
if (toEnd) |
| 1343 |
< |
return null; |
| 1344 |
< |
else if (hiExcluded == 0) |
| 1345 |
< |
return m.getHigherEntry(hi); |
| 1346 |
< |
else |
| 1347 |
< |
return m.getCeilingEntry(hi); |
| 1352 |
> |
final TreeMap.Entry<K,V> absFloor(K key) { |
| 1353 |
> |
if (tooHigh(key)) |
| 1354 |
> |
return absHighest(); |
| 1355 |
> |
TreeMap.Entry<K,V> e = m.getFloorEntry(key); |
| 1356 |
> |
return (e == null || tooLow(e.key)) ? null : e; |
| 1357 |
|
} |
| 1358 |
|
|
| 1359 |
< |
/** |
| 1360 |
< |
* Return the absolute low fence for descending traversal |
| 1361 |
< |
*/ |
| 1362 |
< |
final TreeMap.Entry<K,V> loFence() { |
| 1363 |
< |
if (fromStart) |
| 1355 |
< |
return null; |
| 1356 |
< |
else if (loExcluded == 0) |
| 1357 |
< |
return m.getLowerEntry(lo); |
| 1358 |
< |
else |
| 1359 |
< |
return m.getFloorEntry(lo); |
| 1359 |
> |
final TreeMap.Entry<K,V> absLower(K key) { |
| 1360 |
> |
if (tooHigh(key)) |
| 1361 |
> |
return absHighest(); |
| 1362 |
> |
TreeMap.Entry<K,V> e = m.getLowerEntry(key); |
| 1363 |
> |
return (e == null || tooLow(e.key)) ? null : e; |
| 1364 |
|
} |
| 1365 |
|
|
| 1366 |
+ |
/** Returns the absolute high fence for ascending traversal */ |
| 1367 |
+ |
final TreeMap.Entry<K,V> absHighFence() { |
| 1368 |
+ |
return (toEnd ? null : (hiInclusive ? |
| 1369 |
+ |
m.getHigherEntry(hi) : |
| 1370 |
+ |
m.getCeilingEntry(hi))); |
| 1371 |
+ |
} |
| 1372 |
+ |
|
| 1373 |
+ |
/** Return the absolute low fence for descending traversal */ |
| 1374 |
+ |
final TreeMap.Entry<K,V> absLowFence() { |
| 1375 |
+ |
return (fromStart ? null : (loInclusive ? |
| 1376 |
+ |
m.getLowerEntry(lo) : |
| 1377 |
+ |
m.getFloorEntry(lo))); |
| 1378 |
+ |
} |
| 1379 |
+ |
|
| 1380 |
+ |
// Abstract methods defined in ascending vs descending classes |
| 1381 |
+ |
// These relay to the appropriate absolute versions |
| 1382 |
+ |
|
| 1383 |
+ |
abstract TreeMap.Entry<K,V> subLowest(); |
| 1384 |
+ |
abstract TreeMap.Entry<K,V> subHighest(); |
| 1385 |
+ |
abstract TreeMap.Entry<K,V> subCeiling(K key); |
| 1386 |
+ |
abstract TreeMap.Entry<K,V> subHigher(K key); |
| 1387 |
+ |
abstract TreeMap.Entry<K,V> subFloor(K key); |
| 1388 |
+ |
abstract TreeMap.Entry<K,V> subLower(K key); |
| 1389 |
+ |
|
| 1390 |
+ |
/** Returns ascending iterator from the perspective of this submap */ |
| 1391 |
+ |
abstract Iterator<K> keyIterator(); |
| 1392 |
+ |
|
| 1393 |
+ |
/** Returns descending iterator from the perspective of this submap */ |
| 1394 |
+ |
abstract Iterator<K> descendingKeyIterator(); |
| 1395 |
+ |
|
| 1396 |
+ |
// public methods |
| 1397 |
|
|
| 1398 |
|
public boolean isEmpty() { |
| 1399 |
< |
return entrySet().isEmpty(); |
| 1399 |
> |
return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty(); |
| 1400 |
|
} |
| 1401 |
|
|
| 1402 |
< |
public boolean containsKey(Object key) { |
| 1403 |
< |
return inRange(key) && m.containsKey(key); |
| 1402 |
> |
public int size() { |
| 1403 |
> |
return (fromStart && toEnd) ? m.size() : entrySet().size(); |
| 1404 |
|
} |
| 1405 |
|
|
| 1406 |
< |
public V get(Object key) { |
| 1407 |
< |
if (!inRange(key)) |
| 1373 |
< |
return null; |
| 1374 |
< |
return m.get(key); |
| 1406 |
> |
public final boolean containsKey(Object key) { |
| 1407 |
> |
return inRange(key) && m.containsKey(key); |
| 1408 |
|
} |
| 1409 |
|
|
| 1410 |
< |
public V put(K key, V value) { |
| 1410 |
> |
public final V put(K key, V value) { |
| 1411 |
|
if (!inRange(key)) |
| 1412 |
|
throw new IllegalArgumentException("key out of range"); |
| 1413 |
|
return m.put(key, value); |
| 1414 |
|
} |
| 1415 |
|
|
| 1416 |
< |
public V remove(Object key) { |
| 1417 |
< |
if (!inRange(key)) |
| 1385 |
< |
return null; |
| 1386 |
< |
return m.remove(key); |
| 1416 |
> |
public final V get(Object key) { |
| 1417 |
> |
return !inRange(key)? null : m.get(key); |
| 1418 |
|
} |
| 1419 |
|
|
| 1420 |
< |
public Map.Entry<K,V> ceilingEntry(K key) { |
| 1421 |
< |
TreeMap.Entry<K,V> e = subCeiling(key); |
| 1391 |
< |
return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1420 |
> |
public final V remove(Object key) { |
| 1421 |
> |
return !inRange(key)? null : m.remove(key); |
| 1422 |
|
} |
| 1423 |
|
|
| 1424 |
< |
public K ceilingKey(K key) { |
| 1425 |
< |
TreeMap.Entry<K,V> e = subCeiling(key); |
| 1396 |
< |
return e == null? null : e.key; |
| 1424 |
> |
public final Map.Entry<K,V> ceilingEntry(K key) { |
| 1425 |
> |
return exportEntry(subCeiling(key)); |
| 1426 |
|
} |
| 1427 |
|
|
| 1428 |
< |
public Map.Entry<K,V> higherEntry(K key) { |
| 1429 |
< |
TreeMap.Entry<K,V> e = subHigher(key); |
| 1401 |
< |
return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1428 |
> |
public final K ceilingKey(K key) { |
| 1429 |
> |
return exportKey(subCeiling(key)); |
| 1430 |
|
} |
| 1431 |
|
|
| 1432 |
< |
public K higherKey(K key) { |
| 1433 |
< |
TreeMap.Entry<K,V> e = subHigher(key); |
| 1406 |
< |
return e == null? null : e.key; |
| 1432 |
> |
public final Map.Entry<K,V> higherEntry(K key) { |
| 1433 |
> |
return exportEntry(subHigher(key)); |
| 1434 |
|
} |
| 1435 |
|
|
| 1436 |
< |
public Map.Entry<K,V> floorEntry(K key) { |
| 1437 |
< |
TreeMap.Entry<K,V> e = subFloor(key); |
| 1411 |
< |
return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1436 |
> |
public final K higherKey(K key) { |
| 1437 |
> |
return exportKey(subHigher(key)); |
| 1438 |
|
} |
| 1439 |
|
|
| 1440 |
< |
public K floorKey(K key) { |
| 1441 |
< |
TreeMap.Entry<K,V> e = subFloor(key); |
| 1416 |
< |
return e == null? null : e.key; |
| 1440 |
> |
public final Map.Entry<K,V> floorEntry(K key) { |
| 1441 |
> |
return exportEntry(subFloor(key)); |
| 1442 |
|
} |
| 1443 |
|
|
| 1444 |
< |
public Map.Entry<K,V> lowerEntry(K key) { |
| 1445 |
< |
TreeMap.Entry<K,V> e = subLower(key); |
| 1421 |
< |
return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
| 1444 |
> |
public final K floorKey(K key) { |
| 1445 |
> |
return exportKey(subFloor(key)); |
| 1446 |
|
} |
| 1447 |
|
|
| 1448 |
< |
public K lowerKey(K key) { |
| 1449 |
< |
TreeMap.Entry<K,V> e = subLower(key); |
| 1426 |
< |
return e == null? null : e.key; |
| 1448 |
> |
public final Map.Entry<K,V> lowerEntry(K key) { |
| 1449 |
> |
return exportEntry(subLower(key)); |
| 1450 |
|
} |
| 1451 |
|
|
| 1452 |
< |
abstract Iterator<K> keyIterator(); |
| 1453 |
< |
abstract Iterator<K> descendingKeyIterator(); |
| 1452 |
> |
public final K lowerKey(K key) { |
| 1453 |
> |
return exportKey(subLower(key)); |
| 1454 |
> |
} |
| 1455 |
|
|
| 1456 |
< |
public NavigableSet<K> descendingKeySet() { |
| 1457 |
< |
return descendingMap().navigableKeySet(); |
| 1456 |
> |
public final K firstKey() { |
| 1457 |
> |
return key(subLowest()); |
| 1458 |
> |
} |
| 1459 |
> |
|
| 1460 |
> |
public final K lastKey() { |
| 1461 |
> |
return key(subHighest()); |
| 1462 |
> |
} |
| 1463 |
> |
|
| 1464 |
> |
public final Map.Entry<K,V> firstEntry() { |
| 1465 |
> |
return exportEntry(subLowest()); |
| 1466 |
> |
} |
| 1467 |
> |
|
| 1468 |
> |
public final Map.Entry<K,V> lastEntry() { |
| 1469 |
> |
return exportEntry(subHighest()); |
| 1470 |
> |
} |
| 1471 |
> |
|
| 1472 |
> |
public final Map.Entry<K,V> pollFirstEntry() { |
| 1473 |
> |
TreeMap.Entry<K,V> e = subLowest(); |
| 1474 |
> |
Map.Entry<K,V> result = exportEntry(e); |
| 1475 |
> |
if (e != null) |
| 1476 |
> |
m.deleteEntry(e); |
| 1477 |
> |
return result; |
| 1478 |
> |
} |
| 1479 |
> |
|
| 1480 |
> |
public final Map.Entry<K,V> pollLastEntry() { |
| 1481 |
> |
TreeMap.Entry<K,V> e = subHighest(); |
| 1482 |
> |
Map.Entry<K,V> result = exportEntry(e); |
| 1483 |
> |
if (e != null) |
| 1484 |
> |
m.deleteEntry(e); |
| 1485 |
> |
return result; |
| 1486 |
|
} |
| 1487 |
|
|
| 1488 |
|
// Views |
| 1490 |
|
transient EntrySetView entrySetView = null; |
| 1491 |
|
transient KeySet<K> navigableKeySetView = null; |
| 1492 |
|
|
| 1493 |
+ |
public final NavigableSet<K> navigableKeySet() { |
| 1494 |
+ |
KeySet<K> nksv = navigableKeySetView; |
| 1495 |
+ |
return (nksv != null) ? nksv : |
| 1496 |
+ |
(navigableKeySetView = new TreeMap.KeySet(this)); |
| 1497 |
+ |
} |
| 1498 |
+ |
|
| 1499 |
+ |
public final Set<K> keySet() { |
| 1500 |
+ |
return navigableKeySet(); |
| 1501 |
+ |
} |
| 1502 |
+ |
|
| 1503 |
+ |
public NavigableSet<K> descendingKeySet() { |
| 1504 |
+ |
return descendingMap().navigableKeySet(); |
| 1505 |
+ |
} |
| 1506 |
+ |
|
| 1507 |
+ |
public final SortedMap<K,V> subMap(K fromKey, K toKey) { |
| 1508 |
+ |
return subMap(fromKey, true, toKey, false); |
| 1509 |
+ |
} |
| 1510 |
+ |
|
| 1511 |
+ |
public final SortedMap<K,V> headMap(K toKey) { |
| 1512 |
+ |
return headMap(toKey, false); |
| 1513 |
+ |
} |
| 1514 |
+ |
|
| 1515 |
+ |
public final SortedMap<K,V> tailMap(K fromKey) { |
| 1516 |
+ |
return tailMap(fromKey, true); |
| 1517 |
+ |
} |
| 1518 |
+ |
|
| 1519 |
+ |
// View classes |
| 1520 |
+ |
|
| 1521 |
|
abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> { |
| 1522 |
|
private transient int size = -1, sizeModCount; |
| 1523 |
|
|
| 1537 |
|
} |
| 1538 |
|
|
| 1539 |
|
public boolean isEmpty() { |
| 1540 |
< |
TreeMap.Entry<K,V> n = loEntry(); |
| 1540 |
> |
TreeMap.Entry<K,V> n = absLowest(); |
| 1541 |
|
return n == null || tooHigh(n.key); |
| 1542 |
|
} |
| 1543 |
|
|
| 1569 |
|
} |
| 1570 |
|
} |
| 1571 |
|
|
| 1492 |
– |
public NavigableSet<K> navigableKeySet() { |
| 1493 |
– |
KeySet<K> nksv = navigableKeySetView; |
| 1494 |
– |
return (nksv != null) ? nksv : |
| 1495 |
– |
(navigableKeySetView = new TreeMap.KeySet(this)); |
| 1496 |
– |
} |
| 1497 |
– |
|
| 1498 |
– |
public Set<K> keySet() { |
| 1499 |
– |
return navigableKeySet(); |
| 1500 |
– |
} |
| 1501 |
– |
|
| 1502 |
– |
public SortedMap<K,V> subMap(K fromKey, K toKey) { |
| 1503 |
– |
return subMap(fromKey, true, toKey, false); |
| 1504 |
– |
} |
| 1505 |
– |
|
| 1506 |
– |
public SortedMap<K,V> headMap(K toKey) { |
| 1507 |
– |
return headMap(toKey, false); |
| 1508 |
– |
} |
| 1509 |
– |
|
| 1510 |
– |
public SortedMap<K,V> tailMap(K fromKey) { |
| 1511 |
– |
return tailMap(fromKey, true); |
| 1512 |
– |
} |
| 1513 |
– |
|
| 1514 |
– |
// The following four definitions are correct only for |
| 1515 |
– |
// ascending submaps. They are overridden in DescendingSubMap. |
| 1516 |
– |
// They are defined in the base class because the definitions |
| 1517 |
– |
// in DescendingSubMap rely on those for AscendingSubMap. |
| 1518 |
– |
|
| 1519 |
– |
/** |
| 1520 |
– |
* Returns the entry corresponding to the ceiling of the specified |
| 1521 |
– |
* key from the perspective of this submap, or null if the submap |
| 1522 |
– |
* contains no such entry. |
| 1523 |
– |
*/ |
| 1524 |
– |
TreeMap.Entry<K,V> subCeiling(K key) { |
| 1525 |
– |
if (tooLow(key)) |
| 1526 |
– |
return loEntry(); |
| 1527 |
– |
TreeMap.Entry<K,V> e = m.getCeilingEntry(key); |
| 1528 |
– |
return (e == null || tooHigh(e.key)) ? null : e; |
| 1529 |
– |
} |
| 1530 |
– |
|
| 1531 |
– |
/** |
| 1532 |
– |
* Returns the entry corresponding to the higher of the specified |
| 1533 |
– |
* key from the perspective of this submap, or null if the submap |
| 1534 |
– |
* contains no such entry. |
| 1535 |
– |
*/ |
| 1536 |
– |
TreeMap.Entry<K,V> subHigher(K key) { |
| 1537 |
– |
if (tooLow(key)) |
| 1538 |
– |
return loEntry(); |
| 1539 |
– |
TreeMap.Entry<K,V> e = m.getHigherEntry(key); |
| 1540 |
– |
return (e == null || tooHigh(e.key)) ? null : e; |
| 1541 |
– |
} |
| 1542 |
– |
|
| 1543 |
– |
/** |
| 1544 |
– |
* Returns the entry corresponding to the floor of the specified |
| 1545 |
– |
* key from the perspective of this submap, or null if the submap |
| 1546 |
– |
* contains no such entry. |
| 1547 |
– |
*/ |
| 1548 |
– |
TreeMap.Entry<K,V> subFloor(K key) { |
| 1549 |
– |
if (tooHigh(key)) |
| 1550 |
– |
return hiEntry(); |
| 1551 |
– |
TreeMap.Entry<K,V> e = m.getFloorEntry(key); |
| 1552 |
– |
return (e == null || tooLow(e.key)) ? null : e; |
| 1553 |
– |
} |
| 1554 |
– |
|
| 1555 |
– |
/** |
| 1556 |
– |
* Returns the entry corresponding to the lower of the specified |
| 1557 |
– |
* key from the perspective of this submap, or null if the submap |
| 1558 |
– |
* contains no such entry. |
| 1559 |
– |
*/ |
| 1560 |
– |
TreeMap.Entry<K,V> subLower(K key) { |
| 1561 |
– |
if (tooHigh(key)) |
| 1562 |
– |
return hiEntry(); |
| 1563 |
– |
TreeMap.Entry<K,V> e = m.getLowerEntry(key); |
| 1564 |
– |
return (e == null || tooLow(e.key)) ? null : e; |
| 1565 |
– |
} |
| 1566 |
– |
|
| 1572 |
|
/** |
| 1573 |
|
* Iterators for SubMaps |
| 1574 |
|
*/ |
| 1645 |
|
|
| 1646 |
|
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { |
| 1647 |
|
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last, |
| 1648 |
< |
TreeMap.Entry<K,V> lastExcluded) { |
| 1649 |
< |
super(last, lastExcluded); |
| 1648 |
> |
TreeMap.Entry<K,V> fence) { |
| 1649 |
> |
super(last, fence); |
| 1650 |
|
} |
| 1651 |
|
|
| 1652 |
|
public Map.Entry<K,V> next() { |
| 1656 |
|
|
| 1657 |
|
final class DescendingSubMapKeyIterator extends SubMapIterator<K> { |
| 1658 |
|
DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last, |
| 1659 |
< |
TreeMap.Entry<K,V> lastExcluded) { |
| 1660 |
< |
super(last, lastExcluded); |
| 1659 |
> |
TreeMap.Entry<K,V> fence) { |
| 1660 |
> |
super(last, fence); |
| 1661 |
|
} |
| 1662 |
|
public K next() { |
| 1663 |
|
return prevEntry().key; |
| 1665 |
|
} |
| 1666 |
|
} |
| 1667 |
|
|
| 1668 |
< |
static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1668 |
> |
static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1669 |
|
private static final long serialVersionUID = 912986545866124060L; |
| 1670 |
|
|
| 1671 |
|
AscendingSubMap(TreeMap<K,V> m, |
| 1672 |
< |
boolean fromStart, K lo, int loExcluded, |
| 1673 |
< |
boolean toEnd, K hi, int hiExcluded) { |
| 1674 |
< |
super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded); |
| 1672 |
> |
boolean fromStart, K lo, boolean loInclusive, |
| 1673 |
> |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1674 |
> |
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| 1675 |
|
} |
| 1676 |
|
|
| 1677 |
|
public Comparator<? super K> comparator() { |
| 1685 |
|
if (!inRange(toKey, toInclusive)) |
| 1686 |
|
throw new IllegalArgumentException("toKey out of range"); |
| 1687 |
|
return new AscendingSubMap(m, |
| 1688 |
< |
false, fromKey, excluded(fromInclusive), |
| 1689 |
< |
false, toKey, excluded(toInclusive)); |
| 1688 |
> |
false, fromKey, fromInclusive, |
| 1689 |
> |
false, toKey, toInclusive); |
| 1690 |
|
} |
| 1691 |
|
|
| 1692 |
|
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| 1693 |
|
if (!inClosedRange(toKey)) |
| 1694 |
|
throw new IllegalArgumentException("toKey out of range"); |
| 1695 |
|
return new AscendingSubMap(m, |
| 1696 |
< |
fromStart, lo, loExcluded, |
| 1697 |
< |
false, toKey, excluded(inclusive)); |
| 1696 |
> |
fromStart, lo, loInclusive, |
| 1697 |
> |
false, toKey, inclusive); |
| 1698 |
|
} |
| 1699 |
|
|
| 1700 |
|
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){ |
| 1701 |
|
if (!inRange(fromKey, inclusive)) |
| 1702 |
|
throw new IllegalArgumentException("fromKey out of range"); |
| 1703 |
|
return new AscendingSubMap(m, |
| 1704 |
< |
false, fromKey, excluded(inclusive), |
| 1705 |
< |
toEnd, hi, hiExcluded); |
| 1704 |
> |
false, fromKey, inclusive, |
| 1705 |
> |
toEnd, hi, hiInclusive); |
| 1706 |
> |
} |
| 1707 |
> |
|
| 1708 |
> |
public NavigableMap<K,V> descendingMap() { |
| 1709 |
> |
NavigableMap<K,V> mv = descendingMapView; |
| 1710 |
> |
return (mv != null) ? mv : |
| 1711 |
> |
(descendingMapView = |
| 1712 |
> |
new DescendingSubMap(m, |
| 1713 |
> |
fromStart, lo, loInclusive, |
| 1714 |
> |
toEnd, hi, hiInclusive)); |
| 1715 |
|
} |
| 1716 |
|
|
| 1717 |
|
Iterator<K> keyIterator() { |
| 1718 |
< |
return new SubMapKeyIterator(loEntry(), hiFence()); |
| 1718 |
> |
return new SubMapKeyIterator(absLowest(), absHighFence()); |
| 1719 |
|
} |
| 1720 |
|
|
| 1721 |
|
Iterator<K> descendingKeyIterator() { |
| 1722 |
< |
return new DescendingSubMapKeyIterator(hiEntry(), loFence()); |
| 1722 |
> |
return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); |
| 1723 |
|
} |
| 1724 |
|
|
| 1725 |
< |
class AscendingEntrySetView extends NavigableSubMap.EntrySetView { |
| 1725 |
> |
final class AscendingEntrySetView extends EntrySetView { |
| 1726 |
|
public Iterator<Map.Entry<K,V>> iterator() { |
| 1727 |
< |
return new SubMapEntryIterator(loEntry(), hiFence()); |
| 1727 |
> |
return new SubMapEntryIterator(absLowest(), absHighFence()); |
| 1728 |
|
} |
| 1729 |
|
} |
| 1730 |
|
|
| 1733 |
|
return (es != null) ? es : new AscendingEntrySetView(); |
| 1734 |
|
} |
| 1735 |
|
|
| 1736 |
< |
public K firstKey() { |
| 1737 |
< |
return key(loEntry()); |
| 1738 |
< |
} |
| 1739 |
< |
|
| 1740 |
< |
public K lastKey() { |
| 1741 |
< |
return key(hiEntry()); |
| 1728 |
< |
} |
| 1729 |
< |
|
| 1730 |
< |
public Map.Entry<K,V> firstEntry() { |
| 1731 |
< |
return loEntry(); |
| 1732 |
< |
} |
| 1733 |
< |
|
| 1734 |
< |
public Map.Entry<K,V> lastEntry() { |
| 1735 |
< |
return hiEntry(); |
| 1736 |
< |
} |
| 1737 |
< |
|
| 1738 |
< |
public Map.Entry<K,V> pollFirstEntry() { |
| 1739 |
< |
return pollLoEntry(); |
| 1740 |
< |
} |
| 1741 |
< |
|
| 1742 |
< |
public Map.Entry<K,V> pollLastEntry() { |
| 1743 |
< |
return pollHiEntry(); |
| 1744 |
< |
} |
| 1745 |
< |
|
| 1746 |
< |
public NavigableMap<K,V> descendingMap() { |
| 1747 |
< |
NavigableMap<K,V> mv = descendingMapView; |
| 1748 |
< |
return (mv != null) ? mv : |
| 1749 |
< |
(descendingMapView = |
| 1750 |
< |
new DescendingSubMap(m, |
| 1751 |
< |
fromStart, lo, loExcluded, |
| 1752 |
< |
toEnd, hi, hiExcluded)); |
| 1753 |
< |
} |
| 1736 |
> |
TreeMap.Entry<K,V> subLowest() { return absLowest(); } |
| 1737 |
> |
TreeMap.Entry<K,V> subHighest() { return absHighest(); } |
| 1738 |
> |
TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); } |
| 1739 |
> |
TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); } |
| 1740 |
> |
TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); } |
| 1741 |
> |
TreeMap.Entry<K,V> subLower(K key) { return absLower(key); } |
| 1742 |
|
} |
| 1743 |
|
|
| 1744 |
< |
static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1744 |
> |
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| 1745 |
|
private static final long serialVersionUID = 912986545866120460L; |
| 1746 |
|
DescendingSubMap(TreeMap<K,V> m, |
| 1747 |
< |
boolean fromStart, K lo, int loExcluded, |
| 1748 |
< |
boolean toEnd, K hi, int hiExcluded) { |
| 1749 |
< |
super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded); |
| 1747 |
> |
boolean fromStart, K lo, boolean loInclusive, |
| 1748 |
> |
boolean toEnd, K hi, boolean hiInclusive) { |
| 1749 |
> |
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| 1750 |
|
} |
| 1751 |
|
|
| 1752 |
|
private final Comparator<? super K> reverseComparator = |
| 1763 |
|
if (!inRange(toKey, toInclusive)) |
| 1764 |
|
throw new IllegalArgumentException("toKey out of range"); |
| 1765 |
|
return new DescendingSubMap(m, |
| 1766 |
< |
false, toKey, excluded(toInclusive), |
| 1767 |
< |
false, fromKey, excluded(fromInclusive)); |
| 1766 |
> |
false, toKey, toInclusive, |
| 1767 |
> |
false, fromKey, fromInclusive); |
| 1768 |
|
} |
| 1769 |
|
|
| 1770 |
|
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| 1771 |
|
if (!inRange(toKey, inclusive)) |
| 1772 |
|
throw new IllegalArgumentException("toKey out of range"); |
| 1773 |
|
return new DescendingSubMap(m, |
| 1774 |
< |
false, toKey, excluded(inclusive), |
| 1775 |
< |
toEnd, hi, hiExcluded); |
| 1774 |
> |
false, toKey, inclusive, |
| 1775 |
> |
toEnd, hi, hiInclusive); |
| 1776 |
|
} |
| 1777 |
|
|
| 1778 |
|
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){ |
| 1779 |
|
if (!inRange(fromKey, inclusive)) |
| 1780 |
|
throw new IllegalArgumentException("fromKey out of range"); |
| 1781 |
|
return new DescendingSubMap(m, |
| 1782 |
< |
fromStart, lo, loExcluded, |
| 1783 |
< |
false, fromKey, excluded(inclusive)); |
| 1782 |
> |
fromStart, lo, loInclusive, |
| 1783 |
> |
false, fromKey, inclusive); |
| 1784 |
> |
} |
| 1785 |
> |
|
| 1786 |
> |
public NavigableMap<K,V> descendingMap() { |
| 1787 |
> |
NavigableMap<K,V> mv = descendingMapView; |
| 1788 |
> |
return (mv != null) ? mv : |
| 1789 |
> |
(descendingMapView = |
| 1790 |
> |
new AscendingSubMap(m, |
| 1791 |
> |
fromStart, lo, loInclusive, |
| 1792 |
> |
toEnd, hi, hiInclusive)); |
| 1793 |
|
} |
| 1794 |
|
|
| 1795 |
|
Iterator<K> keyIterator() { |
| 1796 |
< |
return new DescendingSubMapKeyIterator(hiEntry(), loFence()); |
| 1796 |
> |
return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); |
| 1797 |
|
} |
| 1798 |
|
|
| 1799 |
|
Iterator<K> descendingKeyIterator() { |
| 1800 |
< |
return new SubMapKeyIterator(loEntry(), hiFence()); |
| 1800 |
> |
return new SubMapKeyIterator(absLowest(), absHighFence()); |
| 1801 |
|
} |
| 1802 |
|
|
| 1803 |
< |
class DescendingEntrySetView extends NavigableSubMap.EntrySetView { |
| 1803 |
> |
final class DescendingEntrySetView extends EntrySetView { |
| 1804 |
|
public Iterator<Map.Entry<K,V>> iterator() { |
| 1805 |
< |
return new DescendingSubMapEntryIterator(hiEntry(), loFence()); |
| 1805 |
> |
return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); |
| 1806 |
|
} |
| 1807 |
|
} |
| 1808 |
|
|
| 1811 |
|
return (es != null) ? es : new DescendingEntrySetView(); |
| 1812 |
|
} |
| 1813 |
|
|
| 1814 |
< |
public K firstKey() { |
| 1815 |
< |
return key(hiEntry()); |
| 1816 |
< |
} |
| 1817 |
< |
|
| 1818 |
< |
public K lastKey() { |
| 1819 |
< |
return key(loEntry()); |
| 1823 |
< |
} |
| 1824 |
< |
|
| 1825 |
< |
public Map.Entry<K,V> firstEntry() { |
| 1826 |
< |
return hiEntry(); |
| 1827 |
< |
} |
| 1828 |
< |
|
| 1829 |
< |
public Map.Entry<K,V> lastEntry() { |
| 1830 |
< |
return loEntry(); |
| 1831 |
< |
} |
| 1832 |
< |
|
| 1833 |
< |
public Map.Entry<K,V> pollFirstEntry() { |
| 1834 |
< |
return pollHiEntry(); |
| 1835 |
< |
} |
| 1836 |
< |
|
| 1837 |
< |
public Map.Entry<K,V> pollLastEntry() { |
| 1838 |
< |
return pollLoEntry(); |
| 1839 |
< |
} |
| 1840 |
< |
|
| 1841 |
< |
public NavigableMap<K,V> descendingMap() { |
| 1842 |
< |
NavigableMap<K,V> mv = descendingMapView; |
| 1843 |
< |
return (mv != null) ? mv : |
| 1844 |
< |
(descendingMapView = |
| 1845 |
< |
new AscendingSubMap(m, |
| 1846 |
< |
fromStart, lo, loExcluded, |
| 1847 |
< |
toEnd, hi, hiExcluded)); |
| 1848 |
< |
} |
| 1849 |
< |
|
| 1850 |
< |
@Override TreeMap.Entry<K,V> subCeiling(K key) { |
| 1851 |
< |
return super.subFloor(key); |
| 1852 |
< |
} |
| 1853 |
< |
|
| 1854 |
< |
@Override TreeMap.Entry<K,V> subHigher(K key) { |
| 1855 |
< |
return super.subLower(key); |
| 1856 |
< |
} |
| 1857 |
< |
|
| 1858 |
< |
@Override TreeMap.Entry<K,V> subFloor(K key) { |
| 1859 |
< |
return super.subCeiling(key); |
| 1860 |
< |
} |
| 1861 |
< |
|
| 1862 |
< |
@Override TreeMap.Entry<K,V> subLower(K key) { |
| 1863 |
< |
return super.subHigher(key); |
| 1864 |
< |
} |
| 1814 |
> |
TreeMap.Entry<K,V> subLowest() { return absHighest(); } |
| 1815 |
> |
TreeMap.Entry<K,V> subHighest() { return absLowest(); } |
| 1816 |
> |
TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); } |
| 1817 |
> |
TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); } |
| 1818 |
> |
TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); } |
| 1819 |
> |
TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); } |
| 1820 |
|
} |
| 1821 |
|
|
| 1822 |
|
/** |
| 1849 |
|
private K fromKey, toKey; |
| 1850 |
|
private Object readResolve() { |
| 1851 |
|
return new AscendingSubMap(TreeMap.this, |
| 1852 |
< |
fromStart, fromKey, 0, |
| 1853 |
< |
toEnd, toKey, 1); |
| 1852 |
> |
fromStart, fromKey, true, |
| 1853 |
> |
toEnd, toKey, false); |
| 1854 |
|
} |
| 1855 |
|
public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); } |
| 1856 |
|
public K lastKey() { throw new InternalError(); } |
