Package io.permazen.kv.util

Class AbstractKVNavigableSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
io.permazen.util.AbstractIterationSet<E>
io.permazen.util.AbstractNavigableSet<E>
io.permazen.kv.util.AbstractKVNavigableSet<E>
Type Parameters:
E - element type
All Implemented Interfaces:
Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>
Direct Known Subclasses:
KVNavigableSet
public abstract class AbstractKVNavigableSet<E> extends AbstractNavigableSet<E>
NavigableSet support superclass for sets backed by elements encoded as byte[] array keys in a KVStore.

The key sort order must be consistent with the corresponding key ByteData key encodings, i.e., unsigned lexicographical.

There must be an equivalence between elements and byte[] key encodings (i.e., there must be only one valid encoding per set element). The values in the KVStore are ignored.

Subclass Methods

Subclasses must implement the encode() and decode() methods to convert elements to/from byte[] keys (associated values are ignored), and createSubSet() to allow creating reversed and restricted range sub-sets.

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 add() (if appropriate), remove(), and AbstractCollection.clear(); note, these methods must verify the key isVisible() before making any changes.

Additional subclass notes:

Prefix Mode

Instances support a "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 encode() or consumed by decode(). When not in prefix mode, decode() must consume the entire key to preserve correct semantics.

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 values using a KeyFilter; see filterKeys(). To be isVisible(io.permazen.util.ByteData) in the set, 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:

  • 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 key range should be visible.

  • Constructor Details

    • AbstractKVNavigableSet

      protected AbstractKVNavigableSet(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

    • AbstractKVNavigableSet

      protected AbstractKVNavigableSet(KVStore kv, boolean prefixMode, ByteData prefix)
      Convenience constructor for when the range of visible KVStore keys is all keys sharing a given 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

    • AbstractKVNavigableSet

      protected AbstractKVNavigableSet(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

    • AbstractKVNavigableSet

      protected AbstractKVNavigableSet(KVStore kv, boolean prefixMode, boolean reversed, KeyRange keyRange, KeyFilter keyFilter, Bounds<E> bounds)
      Internal constructor. Used for creating sub-sets 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

    • isEmpty

      public boolean isEmpty()
      Description copied from class: AbstractIterationSet
      Overridden in AbstractIterationSet to minimize the use of AbstractIterationSet.size().
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface Set<E>
      Overrides:
      isEmpty in class AbstractIterationSet<E>

    • first

      public E first()
      Specified by:
      first in interface SortedSet<E>
      Overrides:
      first in class AbstractNavigableSet<E>

    • last

      public E last()
      Specified by:
      last in interface SortedSet<E>
      Overrides:
      last in class AbstractNavigableSet<E>

    • pollFirst

      public E pollFirst()
      Specified by:
      pollFirst in interface NavigableSet<E>
      Overrides:
      pollFirst in class AbstractNavigableSet<E>

    • pollLast

      public E pollLast()
      Specified by:
      pollLast in interface NavigableSet<E>
      Overrides:
      pollLast in class AbstractNavigableSet<E>

    • contains

      public boolean contains(Object obj)
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface Set<E>
      Overrides:
      contains in class AbstractCollection<E>

    • iterator

      public CloseableIterator<E> iterator()
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface NavigableSet<E>
      Specified by:
      iterator in interface Set<E>
      Specified by:
      iterator in class AbstractIterationSet<E>

    • filterKeys

      public NavigableSet<E> filterKeys(KeyFilter keyFilter)
      Create a view of this instance with additional filtering applied to the underlying byte[] encoded keys. Any set element 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 AbstractNavigableSet.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(E elem)
      Description copied from class: AbstractNavigableSet
      Determine if the given element is within this instance's lower bound (if any).

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

      Overrides:
      isWithinLowerBound in class AbstractNavigableSet<E>
      Parameters:
      elem - set element
      Returns:
      true if elem is within this instance's lower bound, or this instance has no lower bound

    • isWithinUpperBound

      protected boolean isWithinUpperBound(E elem)
      Description copied from class: AbstractNavigableSet
      Determine if the given element is within this instance's upper bound (if any).

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

      Overrides:
      isWithinUpperBound in class AbstractNavigableSet<E>
      Parameters:
      elem - set element
      Returns:
      true if elem is within this instance's upper bound, or this instance has no upper bound

    • createSubSet

      protected final NavigableSet<E> createSubSet(boolean reverse, Bounds<E> newBounds)
      Description copied from class: AbstractNavigableSet
      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:
      createSubSet in class AbstractNavigableSet<E>
      Parameters:
      reverse - whether the new set's ordering should be reversed relative to this instance's ordering
      newBounds - new bounds
      Returns:
      restricted and/or reversed view of this instance

    • createSubSet

      protected abstract NavigableSet<E> createSubSet(boolean newReversed, KeyRange newKeyRange, KeyFilter newKeyFilter, Bounds<E> 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 set'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

    • encode

      protected abstract void encode(ByteData.Writer writer, Object obj)
      Encode the given 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 - set element
      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

    • decode

      protected abstract E decode(ByteData.Reader reader)
      Decode an element from a 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 set element

    • isVisible

      protected boolean isVisible(ByteData key)
      Determine if the given byte[] key is visible in this set 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:

    • encodeVisible

      protected ByteData encodeVisible(Object obj, boolean fail)
      Encode the given object, if possible, and verify corresponding byte[] key is visible, otherwise return null or throw an exception. Delegates to encode(ByteData.Writer, Object) to attempt the actual encoding.
      Parameters:
      obj - 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