Class UnicodeSetStringSpan.OffsetList

  • Enclosing class:
    UnicodeSetStringSpan

    private static final class UnicodeSetStringSpan.OffsetList
    extends java.lang.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 Summary

      Fields 
      Modifier and Type Field Description
      private int length  
      private int[] list  
      private int start  
    • Constructor Summary

      Constructors 
      Constructor Description
      OffsetList()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addOffset​(int offset)
      Adds an offset.
      void addOffsetAndCount​(int offset, int count)
      Adds an offset and updates its count.
      void clear()  
      boolean containsOffset​(int offset)  
      boolean hasCountAtOffset​(int offset, int count)  
      boolean isEmpty()  
      int popMinimum​(OutputInt outCount)
      Finds the lowest stored offset from a non-empty list, removes it, and reduces all other offsets by this minimum.
      void setMaxLength​(int maxLength)  
      void shift​(int delta)
      Reduces all stored offsets by delta, used when the current position moves by delta.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • list

        private int[] list
      • length

        private int length
      • start

        private int start
    • Constructor Detail

      • OffsetList

        public OffsetList()
    • Method Detail

      • 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]