Package io.github.mahmoudimus.quic.connection

Class RangeSet

java.lang.Object
io.github.mahmoudimus.quic.connection.RangeSet
All Implemented Interfaces:
Iterable<RangeSet.Range>
public final class RangeSet extends Object implements Iterable<RangeSet.Range>
A set of non-negative long values stored as disjoint, non-adjacent half-open ranges, for long runs with random insertion and removal: received packet numbers, ACK ranges, received and acknowledged stream offsets.

Adjacent and overlapping ranges are always merged, so iteration yields the smallest possible set of ranges, in ascending order.

Threads. Not thread-safe; a set belongs to one connection, which serializes access.

  • Constructor Details

    • RangeSet

      public RangeSet()
      An empty set.

    • RangeSet

      public RangeSet(RangeSet other)
      A copy of another set.
      Parameters:
      other - the set to copy

  • Method Details

    • contains

      public boolean contains(long x)
      Whether a value is in the set.
      Parameters:
      x - the value
      Returns:
      true if a range contains it

    • insertOne

      public boolean insertOne(long x)
      Adds one value.
      Parameters:
      x - the value
      Returns:
      true if the set changed

    • insert

      public boolean insert(long start, long end)
      Adds the values [start, end), merging with overlapping and adjacent ranges.
      Parameters:
      start - the first value
      end - one past the last value
      Returns:
      true if the set changed; false for an empty range or one already contained

    • remove

      public boolean remove(long start, long end)
      Removes the values [start, end).
      Parameters:
      start - the first value
      end - one past the last value
      Returns:
      true if the set changed

    • replace

      public List<RangeSet.Range> replace(long start, long end)
      Adds [start, end) and returns the parts of it that were already present, in ascending order. Used to deduplicate stream data received out of order.
      Parameters:
      start - the first value
      end - one past the last value
      Returns:
      the intersection of the previous set with the range

    • add

      public void add(RangeSet other)
      Adds every value of another set.
      Parameters:
      other - the values to add

    • subtract

      public void subtract(RangeSet other)
      Removes every value of another set.
      Parameters:
      other - the values to remove

    • isEmpty

      public boolean isEmpty()
      Whether the set is empty.
      Returns:
      true if it holds no values

    • size

      public int size()
      The number of disjoint ranges.
      Returns:
      the range count

    • min

      public long min()
      The smallest value.
      Returns:
      the start of the first range
      Throws:
      NoSuchElementException - if the set is empty

    • max

      public long max()
      The largest value.
      Returns:
      one less than the end of the last range
      Throws:
      NoSuchElementException - if the set is empty

    • peekMin

      public RangeSet.Range peekMin()
      The first range.
      Returns:
      the lowest range, or null if the set is empty

    • popMin

      public RangeSet.Range popMin()
      Removes and returns the first range.
      Returns:
      the lowest range, or null if the set is empty

    • clear

      public void clear()
      Removes every value.

    • iterator

      public Iterator<RangeSet.Range> iterator()
      The ranges in ascending order.
      Specified by:
      iterator in interface Iterable<RangeSet.Range>
      Returns:
      an iterator that does not support removal

    • descending

      public Iterable<RangeSet.Range> descending()
      The ranges in descending order, as ACK frames list them.
      Returns:
      the ranges, highest first

    • elements

      public LongStream elements()
      Every value, in ascending order.
      Returns:
      the values

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      The ranges, as [a..b, c..d].
      Overrides:
      toString in class Object