Package io.permazen.kv.util

Class AbstractKVNavigableMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

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

io.permazen.kv.util.AbstractKVNavigableMap<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:

KVNavigableMap

public abstract class AbstractKVNavigableMap<K,V>
extends AbstractNavigableMap<K,V>

NavigableMap support superclass for maps backed by keys and values encoded as byte[] arrays in a KVStore, and whose key sort order is consistent with the byte[] key encoding. There must be an equivalence between map keys and byte[] key encodings (i.e., there must be only one valid encoding per map key).

Subclass Methods

Subclasses must implement the encodeKey(), decodeKey(), and decodeValue() methods to convert keys and value to/from KVStore keys and values, and createSubMap() to allow creating reversed and restricted range sub-maps.

Subclasses must also implement comparator(), and the resulting sort order must be consistent with the sort order of the encoded byte[] keys (possibly reversed).

This class provides a read-only implementation; for a mutable implementation, subclasses should also implement put(), remove(), and AbstractMap.clear(); note, these methods must verify the key isVisible() before making any changes.

Additional subclass notes:

• navigableKeySet() returns a Set for which:
  • The add() method is not supported.
  • The remove() method and the remove() method of the associated Iterator delegate to this instance's remove() method.
  • The clear() method delegates to this instance's AbstractMap.clear() method.
• entrySet() returns a Set for which:
  • The add() method is not supported.
  • The remove() method and the remove() method of the associated Iterator delegate to this instance's remove() method (but only when the Map.Entry is still contained in the map).
  • The Map.Entry elements' setValue() method delegates to this instance's put() method (but only when the Map.Entry is still contained in the map).
  • The clear() method delegates to this instance's AbstractMap.clear() method.

Prefix Mode

Instances support "prefix mode" where the byte[] keys may have arbitrary trailing garbage, which is ignored, and so by definition no key can be a prefix of any other key. The length of the prefix is determined implicitly by the number of bytes produced by encodeKey() or consumed by decodeKey(). When not in prefix mode, decodeKey() must consume the entire key to preserve correct semantics.

Prefix mode can also be used when the map values (or some portion thereof) are contained in the key's "garbage" suffix. The decodeValue() takes a KVPair so it can read from both the key and the value. In particular, instances can be built from key/value data where all the values are empty.

Key Restrictions

Instances are configured with an (optional) KeyRange; when range restriction is in effect, this key range corresponds to the bounds.

Instances also support filtering visible keys using a KeyFilter; see filterKeys(). To be isVisible(byte[]) in the map, keys must both be in the KeyRange and pass the KeyFilter.

Concurrent Modifications

This implementation never throws ConcurrentModificationException; instead, iterators always see the most up-to-date state of the associated KVStore.

See Also:

• AbstractKVNavigableSet

Nested Class Summary

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

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

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

Map.Entry<K extends Object,V extends Object>

Field Summary

Fields

Modifier and Type	Field	Description
protected final KeyFilter	keyFilter	Key filter, or null if all keys in the range should be visible.
protected final KeyRange	keyRange	Key range, or null for the entire range.
protected final KVStore	kv	The underlying KVStore.
protected final boolean	prefixMode	Whether we are in "prefix" mode.
protected final boolean	reversed	Whether the ordering of this instance is reversed.

Fields inherited from class io.permazen.util.AbstractNavigableMap

bounds

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractKVNavigableMap(KVStore kv, boolean prefixMode)	Convenience constructor for when there are no range restrictions.
protected	AbstractKVNavigableMap(KVStore kv, boolean prefixMode, boolean reversed, KeyRange keyRange, KeyFilter keyFilter, Bounds<K> bounds)	Internal constructor.
protected	AbstractKVNavigableMap(KVStore kv, boolean prefixMode, byte[] prefix)	Convenience constructor for when the range of visible KVStore keys is all keys sharing a given byte[] prefix.
protected	AbstractKVNavigableMap(KVStore kv, boolean prefixMode, KeyRange keyRange)	Primary constructor.

Method Summary

Modifier and Type	Method	Description
protected abstract NavigableMap<K,V>	createSubMap(boolean newReversed, KeyRange newKeyRange, KeyFilter newKeyFilter, Bounds<K> newBounds)	Create a (possibly reversed) view of this instance with (possibly) tighter lower and/or upper bounds and the given KeyFilter, if any.
protected final 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.
protected abstract K	decodeKey(ByteReader reader)	Decode a key object from an encoded byte[] key.
protected abstract V	decodeValue(KVPair pair)	Decode a value object from an encoded byte[] key/value pair.
protected abstract void	encodeKey(ByteWriter writer, Object obj)	Encode the given key object into a byte[] key.
protected byte[]	encodeVisibleKey(Object obj, boolean fail)	Encode the given key object, if possible, and verify the corresponding byte[] key is visible, otherwise return null or throw an exception.
Set<Map.Entry<K,V>>	entrySet()
NavigableMap<K,V>	filterKeys(KeyFilter keyFilter)	Create a view of this instance with additional filtering applied to the underlying byte[] keys.
V	get(Object obj)
protected boolean	isVisible(byte[] key)	Determine if the given byte[] key is visible in this map according to the configured KeyRange and/or KeyFilter, if any.
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>	navigableKeySet()

Methods inherited from class io.permazen.util.AbstractNavigableMap

ceilingEntry, ceilingKey, containsKey, descendingKeySet, descendingMap, firstEntry, firstKey, floorEntry, floorKey, getBounds, getComparator, headMap, headMap, higherEntry, higherKey, isEmpty, keySet, lastEntry, lastKey, lowerEntry, lowerKey, pollFirstEntry, pollLastEntry, remove, searchAbove, searchBelow, subMap, subMap, tailMap, tailMap

Methods inherited from class java.util.AbstractMap

clear, clone, containsValue, equals, 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.Map

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

Methods inherited from interface java.util.SortedMap

comparator, values

Field Details

kv

protected final KVStore kv

The underlying KVStore.

prefixMode

protected final boolean prefixMode

Whether we are in "prefix" mode.

reversed

protected final boolean reversed

Whether the ordering of this instance is reversed.

keyRange

protected final KeyRange keyRange

Key range, or null for the entire range.

keyFilter

protected final KeyFilter keyFilter

Key filter, or null if all keys in the range should be visible.

Constructor Details

AbstractKVNavigableMap

protected AbstractKVNavigableMap(KVStore kv,
 boolean prefixMode)

Convenience constructor for when there are no range restrictions.

Parameters:

kv - underlying KVStore

prefixMode - whether to allow keys to have trailing garbage

Throws:

IllegalArgumentException - if kv is null

AbstractKVNavigableMap

protected AbstractKVNavigableMap(KVStore kv,
 boolean prefixMode,
 byte[] prefix)

Convenience constructor for when the range of visible KVStore keys is all keys sharing a given byte[] prefix.

Parameters:

kv - underlying KVStore

prefixMode - whether to allow keys to have trailing garbage

prefix - prefix defining minimum and maximum keys

Throws:

IllegalArgumentException - if kv is null

IllegalArgumentException - if prefix is null or empty

AbstractKVNavigableMap

protected AbstractKVNavigableMap(KVStore kv,
 boolean prefixMode,
 KeyRange keyRange)

Primary constructor.

Parameters:

kv - underlying KVStore

prefixMode - whether to allow keys to have trailing garbage

keyRange - key range restriction, or null for none

Throws:

IllegalArgumentException - if kv is null

AbstractKVNavigableMap

protected AbstractKVNavigableMap(KVStore kv,
 boolean prefixMode,
 boolean reversed,
 KeyRange keyRange,
 KeyFilter keyFilter,
 Bounds<K> bounds)

Internal constructor. Used for creating sub-maps and reversed views.

Note: if bounds are set, then keyRange must exclude all keys outside of those bounds.

Parameters:

kv - underlying KVStore

prefixMode - whether to allow keys to have trailing garbage

reversed - whether ordering is reversed (implies bounds are also inverted, but not keyRange)

keyRange - key range restriction, or null for none

keyFilter - key filter, or null for none

bounds - range restriction

Throws:

IllegalArgumentException - if kv or bounds is null

Method Details

get

public V get(Object obj)

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

entrySet

public Set<Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in interface SortedMap<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

navigableKeySet

public NavigableSet<K> navigableKeySet()

filterKeys

public NavigableMap<K,V> filterKeys(KeyFilter keyFilter)

Create a view of this instance with additional filtering applied to the underlying byte[] keys. Any map entry for which the corresponding key does not pass keyFilter will be effectively hidden from view.

The restrictions of the given KeyFilter will be added to any current KeyFilter restrictions on this instance. The AbstractNavigableMap.bounds associated with this instance will not change.

Parameters:

keyFilter - additional key filtering to apply

Returns:

filtered view of this instance

Throws:

IllegalArgumentException - if keyFilter is null

isWithinLowerBound

protected boolean isWithinLowerBound(K key)

Description copied from class: AbstractNavigableMap

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).

Overrides:

isWithinLowerBound in class AbstractNavigableMap<K,V>

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)

Description copied from class: AbstractNavigableMap

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).

Overrides:

isWithinUpperBound in class AbstractNavigableMap<K,V>

Parameters:

key - map key

Returns:

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

createSubMap

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

Description copied from class: AbstractNavigableMap

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.

Specified by:

createSubMap in class AbstractNavigableMap<K,V>

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

createSubMap

protected abstract NavigableMap<K,V> createSubMap(boolean newReversed,
 KeyRange newKeyRange,
 KeyFilter newKeyFilter,
 Bounds<K> newBounds)

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

Parameters:

newReversed - whether the new map's ordering should be reversed (implies newBounds are also inverted, but not keyRange); note: means "absolutely" reversed, not relative to this instance

newKeyRange - new key range, or null for none; will be consistent with bounds, if any

newKeyFilter - new key filter, or null for none

newBounds - new bounds

Returns:

restricted and/or filtered view of this instance

Throws:

IllegalArgumentException - if newBounds is null

encodeKey

protected abstract void encodeKey(ByteWriter writer,
 Object obj)

Encode the given key object into a byte[] key. Note that this method must throw IllegalArgumentException, not ClassCastException or NullPointerException, if obj does not have the correct type or is an illegal null value.

Parameters:

writer - output for encoded byte[] key corresponding to obj

obj - map key object

Throws:

IllegalArgumentException - if obj is not of the required Java type supported by this set

IllegalArgumentException - if obj is null and this set does not support null elements

decodeKey

protected abstract K decodeKey(ByteReader reader)

Decode a key object from an encoded byte[] key.

If not in prefix mode, all of reader must be consumed; otherwise, the consumed portion is the prefix and any following keys with the same prefix are ignored.

Parameters:

reader - input for encoded bytes

Returns:

decoded map key

decodeValue

protected abstract V decodeValue(KVPair pair)

Decode a value object from an encoded byte[] key/value pair.

Parameters:

pair - key/value pair

Returns:

decoded map value

isVisible

protected boolean isVisible(byte[] key)

Determine if the given byte[] key is visible in this map according to the configured KeyRange and/or KeyFilter, if any.

Parameters:

key - key to test

Returns:

true if key is visible

Throws:

IllegalArgumentException - if key is null

See Also:

• filterKeys()

encodeVisibleKey

protected byte[] encodeVisibleKey(Object obj,
 boolean fail)

Encode the given key object, if possible, and verify the corresponding byte[] key is visible, otherwise return null or throw an exception. Delegates to encodeKey(ByteWriter, Object) to attempt the actual encoding.

Parameters:

obj - key object to encode, possibly null

fail - whether, if obj can't be encoded, to throw an exception (true) or return null (false)

Returns:

encoed key for obj, or null if fail is false and obj has the wrong type or is out of bounds

Throws:

IllegalArgumentException - if fail is true and obj has the wrong type

IllegalArgumentException - if fail is true and the resulting key is not visible