Class UnicodeSetStringSpan.OffsetList

java.lang.Object
com.ibm.icu.impl.UnicodeSetStringSpan.OffsetList
Enclosing class:
UnicodeSetStringSpan

private static final class UnicodeSetStringSpan.OffsetList extends Object
Helper class for UnicodeSetStringSpan.

List of offsets from the current position from where to try matching a code point or a string. Stores offsets rather than indexes to simplify the code and use the same list for both increments (in span()) and decrements (in spanBack()).

Assumption: The maximum offset is limited, and the offsets that are stored at any one time are relatively dense, that is, there are normally no gaps of hundreds or thousands of offset values.

This class optionally also tracks the minimum non-negative count for each position, intended to count the smallest number of elements of any path leading to that position.

The implementation uses a circular buffer of count integers, each indicating whether the corresponding offset is in the list, and its path element count. This avoids inserting into a sorted list of offsets (or absolute indexes) and physically moving part of the list.

Note: In principle, the caller should setMaxLength() to the maximum of the max string length and U16_LENGTH/U8_LENGTH to account for "long" single code points.

Note: An earlier version did not track counts and stored only byte flags. With boolean flags, if maxLength were guaranteed to be no more than 32 or 64, the list could be stored as bit flags in a single integer. Rather than handling a circular buffer with a start list index, the integer would simply be shifted when lower offsets are removed. UnicodeSet does not have a limit on the lengths of strings.

  • Field Details

    • list

      private int[] list
    • length

      private int length
    • start

      private int start
  • Constructor Details

    • OffsetList

      public OffsetList()
  • Method Details

    • setMaxLength

      public void setMaxLength(int maxLength)
    • clear

      public void clear()
    • isEmpty

      public boolean isEmpty()
    • shift

      public void shift(int delta)
      Reduces all stored offsets by delta, used when the current position moves by delta. There must not be any offsets lower than delta. If there is an offset equal to delta, it is removed.
      Parameters:
      delta - [1..maxLength]
    • addOffset

      public void addOffset(int offset)
      Adds an offset. The list must not contain it yet.
      Parameters:
      offset - [1..maxLength]
    • addOffsetAndCount

      public void addOffsetAndCount(int offset, int count)
      Adds an offset and updates its count. The list may already contain the offset.
      Parameters:
      offset - [1..maxLength]
    • containsOffset

      public boolean containsOffset(int offset)
      Parameters:
      offset - [1..maxLength]
    • hasCountAtOffset

      public boolean hasCountAtOffset(int offset, int count)
      Parameters:
      offset - [1..maxLength]
    • popMinimum

      public int popMinimum(OutputInt outCount)
      Finds the lowest stored offset from a non-empty list, removes it, and reduces all other offsets by this minimum.
      Returns:
      min=[1..maxLength]