io.permazen.util

Class AbstractNavigableMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

io.permazen.util.AbstractNavigableMap<K,V>

Type Parameters:

K - key type

V - value type

All Implemented Interfaces:

Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

Direct Known Subclasses:

AbstractKVNavigableMap, ConvertedNavigableMap, ImmutableNavigableMap

public abstract class AbstractNavigableMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>

Support superclass for NavigableMap implementations.

For a read-only implementation, subclasses should implement comparator(), get(), entrySet(), navigableKeySet(), and createSubMap() to handle reversed and restricted range sub-maps.

For a mutable implementation, subclasses should also implement put(), remove(), clear(), and make the navigableKeySet() and entrySet() iterators mutable.

All overridden methods must be aware of the range restriction bounds, if any.

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
protected Bounds<K>	bounds Key range bounds associated with this instance.

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractNavigableMap() Convenience constructor for the case where there are no lower or upper key bounds.
protected	AbstractNavigableMap(Bounds<K> bounds) Primary constructor.

Method Summary

Modifier and Type	Method and Description
Map.Entry<K,V>	ceilingEntry(K minKey)
K	ceilingKey(K minKey)
boolean	containsKey(Object obj)
protected abstract NavigableMap<K,V>	createSubMap(boolean reverse, Bounds<K> newBounds) Create a (possibly reversed) view of this instance with (possibly) tighter lower and/or upper bounds.
NavigableSet<K>	descendingKeySet()
NavigableMap<K,V>	descendingMap()
Map.Entry<K,V>	firstEntry()
K	firstKey()
Map.Entry<K,V>	floorEntry(K maxKey)
K	floorKey(K maxKey)
protected Comparator<? super K>	getComparator(boolean reversed) Get a non-null Comparator that sorts consistently with, and optionally reversed from, this instance.
NavigableMap<K,V>	headMap(K maxKey)
NavigableMap<K,V>	headMap(K newMaxKey, boolean inclusive)
Map.Entry<K,V>	higherEntry(K minKey)
K	higherKey(K minKey)
boolean	isEmpty()
protected boolean	isWithinLowerBound(K key) Determine if the given element is within this instance's lower bound (if any).
protected boolean	isWithinUpperBound(K key) Determine if the given element is within this instance's upper bound (if any).
NavigableSet<K>	keySet()
Map.Entry<K,V>	lastEntry()
K	lastKey()
Map.Entry<K,V>	lowerEntry(K maxKey)
K	lowerKey(K maxKey)
Map.Entry<K,V>	pollFirstEntry()
Map.Entry<K,V>	pollLastEntry()
V	remove(Object key) Removes the mapping for a key from this map if it is present.
protected Map.Entry<K,V>	searchAbove(K minKey, boolean inclusive) Search for a higher element.
protected Map.Entry<K,V>	searchBelow(K maxKey, boolean inclusive) Search for a lower element.
NavigableMap<K,V>	subMap(K newMinKey, boolean minInclusive, K newMaxKey, boolean maxInclusive)
NavigableMap<K,V>	subMap(K minKey, K maxKey)
NavigableMap<K,V>	tailMap(K minKey)
NavigableMap<K,V>	tailMap(K newMinKey, boolean inclusive)

Methods inherited from class java.util.AbstractMap

clear, clone, containsValue, entrySet, equals, get, hashCode, put, putAll, size, toString, values

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.NavigableMap

navigableKeySet

Methods inherited from interface java.util.SortedMap

comparator, entrySet, values

Methods inherited from interface java.util.Map

clear, compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, get, getOrDefault, hashCode, merge, put, putAll, putIfAbsent, remove, replace, replace, replaceAll, size

Field Detail

bounds

protected final Bounds<K> bounds

Key range bounds associated with this instance.

Constructor Detail

AbstractNavigableMap

protected AbstractNavigableMap()

Convenience constructor for the case where there are no lower or upper key bounds.

AbstractNavigableMap

protected AbstractNavigableMap(Bounds<K> bounds)

Primary constructor.

Parameters:

bounds - key range restriction

Throws:

IllegalArgumentException - if bounds is null

Method Detail

remove

public V remove(Object key)

Removes the mapping for a key from this map if it is present.

The implementation in AbstractNavigableMap always throws UnsupportedOperationException.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Map<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

containsKey

public boolean containsKey(Object obj)

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

keySet

public NavigableSet<K> keySet()

Specified by:

keySet in interface Map<K,V>

Specified by:

keySet in interface SortedMap<K,V>

Overrides:

keySet in class AbstractMap<K,V>

lowerEntry

public Map.Entry<K,V> lowerEntry(K maxKey)

Specified by:

lowerEntry in interface NavigableMap<K,V>

floorEntry

public Map.Entry<K,V> floorEntry(K maxKey)

Specified by:

floorEntry in interface NavigableMap<K,V>

ceilingEntry

public Map.Entry<K,V> ceilingEntry(K minKey)

Specified by:

ceilingEntry in interface NavigableMap<K,V>

higherEntry

public Map.Entry<K,V> higherEntry(K minKey)

Specified by:

higherEntry in interface NavigableMap<K,V>

lowerKey

public K lowerKey(K maxKey)

Specified by:

lowerKey in interface NavigableMap<K,V>

floorKey

public K floorKey(K maxKey)

Specified by:

floorKey in interface NavigableMap<K,V>

ceilingKey

public K ceilingKey(K minKey)

Specified by:

ceilingKey in interface NavigableMap<K,V>

higherKey

public K higherKey(K minKey)

Specified by:

higherKey in interface NavigableMap<K,V>

firstEntry

public Map.Entry<K,V> firstEntry()

Specified by:

firstEntry in interface NavigableMap<K,V>

lastEntry

public Map.Entry<K,V> lastEntry()

Specified by:

lastEntry in interface NavigableMap<K,V>

pollFirstEntry

public Map.Entry<K,V> pollFirstEntry()

Specified by:

pollFirstEntry in interface NavigableMap<K,V>

pollLastEntry

public Map.Entry<K,V> pollLastEntry()

Specified by:

pollLastEntry in interface NavigableMap<K,V>

descendingMap

public NavigableMap<K,V> descendingMap()

Specified by:

descendingMap in interface NavigableMap<K,V>

descendingKeySet

public NavigableSet<K> descendingKeySet()

Specified by:

descendingKeySet in interface NavigableMap<K,V>

subMap

public NavigableMap<K,V> subMap(K minKey,
                                K maxKey)

Specified by:

subMap in interface NavigableMap<K,V>

Specified by:

subMap in interface SortedMap<K,V>

headMap

public NavigableMap<K,V> headMap(K maxKey)

Specified by:

headMap in interface NavigableMap<K,V>

Specified by:

headMap in interface SortedMap<K,V>

tailMap

public NavigableMap<K,V> tailMap(K minKey)

Specified by:

tailMap in interface NavigableMap<K,V>

Specified by:

tailMap in interface SortedMap<K,V>

headMap

public NavigableMap<K,V> headMap(K newMaxKey,
                                 boolean inclusive)

Specified by:

headMap in interface NavigableMap<K,V>

tailMap

public NavigableMap<K,V> tailMap(K newMinKey,
                                 boolean inclusive)

Specified by:

tailMap in interface NavigableMap<K,V>

subMap

public NavigableMap<K,V> subMap(K newMinKey,
                                boolean minInclusive,
                                K newMaxKey,
                                boolean maxInclusive)

Specified by:

subMap in interface NavigableMap<K,V>

searchBelow

protected Map.Entry<K,V> searchBelow(K maxKey,
                                     boolean inclusive)

Search for a lower element. Used to implement floorEntry() and lowerEntry().

The implementation in AbstractNavigableMap checks the bounds then returns the first entry from a head map.

Parameters:

maxKey - upper limit for search

inclusive - true if maxKey itself is a candidate

Returns:

highest element below maxKey, or null if not found

searchAbove

protected Map.Entry<K,V> searchAbove(K minKey,
                                     boolean inclusive)

Search for a higher element. Used to implement ceilingEntry() and higherEntry().

The implementation in AbstractNavigableMap checks the bounds then returns the first entry from a tail map.

Parameters:

minKey - lower limit for search

inclusive - true if minKey itself is a candidate

Returns:

lowest element above minKey, or null if not found

getComparator

protected Comparator<? super K> getComparator(boolean reversed)

Get a non-null Comparator that sorts consistently with, and optionally reversed from, this instance.

Parameters:

reversed - whether to return a reversed Comparator

Returns:

a non-null Comparator

createSubMap

protected abstract NavigableMap<K,V> createSubMap(boolean reverse,
                                                  Bounds<K> newBounds)

Create a (possibly reversed) view of this instance with (possibly) tighter lower and/or upper bounds. The newBounds are consistent with the new ordering (i.e., reversed relative to this instance's ordering if reverse is true) and have already been range-checked against this instance's current bounds.

Parameters:

reverse - whether the new map's ordering should be reversed relative to this instance's ordering

newBounds - new bounds

Returns:

restricted and/or reversed view of this instance

Throws:

IllegalArgumentException - if newBounds is null

IllegalArgumentException - if a bound in newBounds is null and this set does not permit null elements

isWithinLowerBound

protected boolean isWithinLowerBound(K key)

Determine if the given element is within this instance's lower bound (if any).

The implementation in AbstractNavigableMap returns this.bounds.isWithinLowerBound(this.comparator(), elem).

Parameters:

key - map key

Returns:

true if elem is within this instance's lower bound, or this instance has no lower bound

isWithinUpperBound

protected boolean isWithinUpperBound(K key)

Determine if the given element is within this instance's upper bound (if any).

The implementation in AbstractNavigableMap returns this.bounds.isWithinUpperBound(this.comparator(), elem).

Parameters:

key - map key

Returns:

true if elem is within this instance's upper bound, or this instance has no upper bound