Package io.permazen.util

Class AbstractNavigableSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
io.permazen.util.AbstractIterationSet<E>
io.permazen.util.AbstractNavigableSet<E>
Type Parameters:
E - element type
All Implemented Interfaces:
Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>
Direct Known Subclasses:
AbstractKVNavigableSet, ConvertedNavigableSet, ImmutableNavigableSet
public abstract class AbstractNavigableSet<E> extends AbstractIterationSet<E> implements NavigableSet<E>
Support superclass for NavigableSet implementations based on database entries.

For a read-only implementation, subclasses should implement comparator(), contains(), iterator(), and createSubSet() to handle reversed and restricted range sub-sets.

For a mutable implementation, subclasses should also implement add(), remove(), clear(), and make the iterator() mutable.

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

  • Field Details

    • bounds

      protected final Bounds<E> bounds
      Element range bounds associated with this instance.

  • Constructor Details

    • AbstractNavigableSet

      protected AbstractNavigableSet()
      Convenience constructor for the case where there are no lower or upper bounds.

    • AbstractNavigableSet

      protected AbstractNavigableSet(Bounds<E> bounds)
      Primary constructor.
      Parameters:
      bounds - range restriction
      Throws:
      IllegalArgumentException - if bounds is null

  • Method Details

    • getBounds

      public Bounds<E> getBounds()
      Get the Bounds associated with this instance.
      Returns:
      range restriction

    • remove

      public boolean remove(Object elem)
      Removes the given element from this set if it is present.

      The implementation in AbstractNavigableSet always throws UnsupportedOperationException.

      Specified by:
      remove in interface Collection<E>
      Specified by:
      remove in interface Set<E>
      Overrides:
      remove in class AbstractCollection<E>

    • first

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

    • last

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

    • pollFirst

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

    • pollLast

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

    • descendingIterator

      public CloseableIterator<E> descendingIterator()
      Specified by:
      descendingIterator in interface NavigableSet<E>

    • lower

      public E lower(E elem)
      Specified by:
      lower in interface NavigableSet<E>

    • floor

      public E floor(E elem)
      Specified by:
      floor in interface NavigableSet<E>

    • ceiling

      public E ceiling(E elem)
      Specified by:
      ceiling in interface NavigableSet<E>

    • higher

      public E higher(E elem)
      Specified by:
      higher in interface NavigableSet<E>

    • headSet

      public NavigableSet<E> headSet(E newMaxElement)
      Specified by:
      headSet in interface NavigableSet<E>
      Specified by:
      headSet in interface SortedSet<E>

    • tailSet

      public NavigableSet<E> tailSet(E newMinElement)
      Specified by:
      tailSet in interface NavigableSet<E>
      Specified by:
      tailSet in interface SortedSet<E>

    • subSet

      public NavigableSet<E> subSet(E newMinElement, E newMaxElement)
      Specified by:
      subSet in interface NavigableSet<E>
      Specified by:
      subSet in interface SortedSet<E>

    • descendingSet

      public NavigableSet<E> descendingSet()
      Specified by:
      descendingSet in interface NavigableSet<E>

    • headSet

      public NavigableSet<E> headSet(E newMaxElement, boolean inclusive)
      Specified by:
      headSet in interface NavigableSet<E>

    • tailSet

      public NavigableSet<E> tailSet(E newMinElement, boolean inclusive)
      Specified by:
      tailSet in interface NavigableSet<E>

    • subSet

      public NavigableSet<E> subSet(E newMinElement, boolean minInclusive, E newMaxElement, boolean maxInclusive)
      Specified by:
      subSet in interface NavigableSet<E>

    • buildSpliterator

      protected Spliterator<E> buildSpliterator(Iterator<E> iterator)
      Description copied from class: AbstractIterationSet
      Build a Spliterator appropriate for this set from the given instance iterator.

      Implementations should probably use Spliterators.spliteratorUnknownSize() unless the size is known.

      Overrides:
      buildSpliterator in class AbstractIterationSet<E>
      Parameters:
      iterator - a new iterator returned from {#link #iterator}

    • searchBelow

      protected E searchBelow(E elem, boolean inclusive)
      Search for a lower element. Used to implement floor() and lower().

      The implementation in AbstractNavigableSet checks the bounds then returns the first element from a head set.

      Parameters:
      elem - upper limit for search
      inclusive - true if elem itself is a candidate
      Returns:
      highest element below elem, or null if not found

    • searchAbove

      protected E searchAbove(E elem, boolean inclusive)
      Search for a higher element. Used to implement ceiling() and higher().

      The implementation in AbstractNavigableSet checks the bounds then returns the first element from a tail set.

      Parameters:
      elem - lower limit for search
      inclusive - true if elem itself is a candidate
      Returns:
      lowest element above elem, or null if not found

    • getComparator

      protected Comparator<? super E> 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

    • createSubSet

      protected abstract NavigableSet<E> createSubSet(boolean reverse, Bounds<E> 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 set'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(E elem)
      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).

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

      Parameters:
      elem - set element
      Returns:
      true if elem is within this instance's upper bound, or this instance has no upper bound