Class GapTextStore

  • All Implemented Interfaces:
    ITextStore

    public class GapTextStore
    extends java.lang.Object
    implements ITextStore
    Implements a gap managing text store. The gap text store relies on the assumption that consecutive changes to a document are co-located. The start of the gap is always moved to the location of the last change.

    Performance: Typing-style changes perform in constant time unless re-allocation becomes necessary. Generally, a change that does not cause re-allocation will cause at most one arraycopy operation of a length of about d, where d is the distance from the previous change. Let a(x) be the algorithmic performance of an arraycopy operation of the length x , then such a change then performs in O(a(x)), get(int, length) performs in O(a(length)), get(int) in O(1).

    How frequently the array needs re-allocation is controlled by the constructor parameters.

    This class is not intended to be subclassed.

    See Also:
    for a copy-on-write text store wrapper @noextend This class is not intended to be subclassed by clients.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private char[] fContent
      The store's content
      private int fGapEnd
      End index of the gap
      private int fGapStart
      Starting index of the gap
      private int fMaxGapSize
      The maximum gap size allocated when re-allocation occurs.
      private int fMinGapSize
      The minimum gap size allocated when re-allocation occurs.
      private float fSizeMultiplier
      The multiplier to compute the array size from the content length (1 <= fSizeMultiplier <= 2).
      private int fThreshold
      The current high water mark.
    • Constructor Summary

      Constructors 
      Constructor Description
      GapTextStore()
      GapTextStore​(int lowWatermark, int highWatermark)
      Creates a new empty text store using the specified low and high watermarks.
      GapTextStore​(int minSize, int maxSize, float maxGapFactor)
      Creates an empty text store that uses re-allocation thresholds relative to the content length.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void adjustGap​(int offset, int remove, int add)
      Moves the gap to offset + add, moving any content after offset + remove behind the gap.
      private char[] allocate​(int size)
      Allocates a new char[size].
      private void arrayCopy​(int srcPos, char[] dest, int destPos, int length)  
      private int gapSize()
      Returns the gap size.
      char get​(int offset)
      Returns the character at the specified offset.
      java.lang.String get​(int offset, int length)
      Returns the text of the specified character range.
      protected java.lang.String getContentAsString()
      Returns a copy of the content of this text store.
      protected int getGapEndIndex()
      Returns the end index of the gap managed by this text store.
      protected int getGapStartIndex()
      Returns the start index of the gap managed by this text store.
      int getLength()
      Returns number of characters stored in this text store.
      private int moveGap​(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart)
      Moves the gap to newGapStart.
      private int reallocate​(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart)
      Reallocates a new array and copies the data from the previous one.
      void replace​(int offset, int length, java.lang.String text)
      Replaces the specified character range with the given text.
      void set​(java.lang.String text)
      Replace the content of the text store with the given text.
      • Methods inherited from class java.lang.Object

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

      • fMinGapSize

        private final int fMinGapSize
        The minimum gap size allocated when re-allocation occurs. @since 3.3
      • fMaxGapSize

        private final int fMaxGapSize
        The maximum gap size allocated when re-allocation occurs. @since 3.3
      • fSizeMultiplier

        private final float fSizeMultiplier
        The multiplier to compute the array size from the content length (1 <= fSizeMultiplier <= 2). @since 3.3
      • fContent

        private char[] fContent
        The store's content
      • fGapStart

        private int fGapStart
        Starting index of the gap
      • fGapEnd

        private int fGapEnd
        End index of the gap
      • fThreshold

        private int fThreshold
        The current high water mark. If a change would cause the gap to grow larger than this, the array is re-allocated. @since 3.3
    • Constructor Detail

      • GapTextStore

        public GapTextStore​(int lowWatermark,
                            int highWatermark)
        Creates a new empty text store using the specified low and high watermarks.
        Parameters:
        lowWatermark - unused - at the lower bound, the array is only resized when the content does not fit
        highWatermark - if the gap is ever larger than this, it will automatically be shrunken (>= 0) @deprecated use GapTextStore(int, int, float) instead
      • GapTextStore

        public GapTextStore​(int minSize,
                            int maxSize,
                            float maxGapFactor)
        Creates an empty text store that uses re-allocation thresholds relative to the content length. Re-allocation is controlled by the gap factor, which is the quotient of the gap size and the array size. Re-allocation occurs if a change causes the gap factor to go outside [0, maxGapFactor]. When re-allocation occurs, the array is sized such that the gap factor is 0.5 * maxGapFactor. The gap size computed in this manner is bounded by the minSize and maxSize parameters.

        A maxGapFactor of 0 creates a text store that never has a gap at all (if minSize is 0); a maxGapFactor of 1 creates a text store that doubles its size with every re-allocation and that never shrinks.

        The minSize and maxSize parameters are absolute bounds to the allocated gap size. Use minSize to avoid frequent re-allocation for small documents. Use maxSize to avoid a huge gap being allocated for large documents.

        Parameters:
        minSize - the minimum gap size to allocate (>= 0; use 0 for no minimum)
        maxSize - the maximum gap size to allocate (>= minSize; use Integer.MAX_VALUE for no maximum)
        maxGapFactor - is the maximum fraction of the array that is occupied by the gap ( 0 <= maxGapFactor <= 1 ) @since 3.3
    • Method Detail

      • get

        public final char get​(int offset)
        Description copied from interface: ITextStore
        Returns the character at the specified offset.
        Specified by:
        get in interface ITextStore
        Parameters:
        offset - the offset in this text store
        Returns:
        the character at this offset
      • get

        public final java.lang.String get​(int offset,
                                          int length)
        Description copied from interface: ITextStore
        Returns the text of the specified character range.
        Specified by:
        get in interface ITextStore
        Parameters:
        offset - the offset of the range
        length - the length of the range
        Returns:
        the text of the range
      • getLength

        public final int getLength()
        Description copied from interface: ITextStore
        Returns number of characters stored in this text store.
        Specified by:
        getLength in interface ITextStore
        Returns:
        the number of characters stored in this text store
      • set

        public final void set​(java.lang.String text)
        Description copied from interface: ITextStore
        Replace the content of the text store with the given text. Convenience method for replace(0, getLength(), text.
        Specified by:
        set in interface ITextStore
        Parameters:
        text - the new content of the text store
      • replace

        public final void replace​(int offset,
                                  int length,
                                  java.lang.String text)
        Description copied from interface: ITextStore
        Replaces the specified character range with the given text. replace(getLength(), 0, "some text") is a valid call and appends text to the end of the text store.
        Specified by:
        replace in interface ITextStore
        Parameters:
        offset - the offset of the range to be replaced
        length - the number of characters to be replaced
        text - the substitution text
      • adjustGap

        private void adjustGap​(int offset,
                               int remove,
                               int add)
        Moves the gap to offset + add, moving any content after offset + remove behind the gap. The gap size is kept between 0 and fThreshold, leading to re-allocation if needed. The content between offset and offset + add is undefined after this operation.
        Parameters:
        offset - the offset at which a change happens
        remove - the number of character which are removed or overwritten at offset
        add - the number of character which are inserted or overwriting at offset
      • moveGap

        private int moveGap​(int offset,
                            int remove,
                            int oldGapSize,
                            int newGapSize,
                            int newGapStart)
        Moves the gap to newGapStart.
        Parameters:
        offset - the change offset
        remove - the number of removed / overwritten characters
        oldGapSize - the old gap size
        newGapSize - the gap size after the change
        newGapStart - the offset in the array to move the gap to
        Returns:
        the new gap end @since 3.3
      • reallocate

        private int reallocate​(int offset,
                               int remove,
                               int oldGapSize,
                               int newGapSize,
                               int newGapStart)
        Reallocates a new array and copies the data from the previous one.
        Parameters:
        offset - the change offset
        remove - the number of removed / overwritten characters
        oldGapSize - the old gap size
        newGapSize - the gap size after the change if no re-allocation would occur (can be negative)
        newGapStart - the offset in the array to move the gap to
        Returns:
        the new gap end @since 3.3
      • allocate

        private char[] allocate​(int size)
        Allocates a new char[size].
        Parameters:
        size - the length of the new array.
        Returns:
        a newly allocated char array @since 3.3
      • arrayCopy

        private void arrayCopy​(int srcPos,
                               char[] dest,
                               int destPos,
                               int length)
      • gapSize

        private int gapSize()
        Returns the gap size.
        Returns:
        the gap size @since 3.3
      • getContentAsString

        protected java.lang.String getContentAsString()
        Returns a copy of the content of this text store. For internal use only.
        Returns:
        a copy of the content of this text store
      • getGapStartIndex

        protected int getGapStartIndex()
        Returns the start index of the gap managed by this text store. For internal use only.
        Returns:
        the start index of the gap managed by this text store
      • getGapEndIndex

        protected int getGapEndIndex()
        Returns the end index of the gap managed by this text store. For internal use only.
        Returns:
        the end index of the gap managed by this text store