org.eclipse.platform/org.eclipse.text/3.10.0 : org/eclipse/jface/text/GapTextStore.java

GapTextStore
http://www.eclipse.org/platform: Text (Eclipse Foundation)
Eclipse Public License - v 2.0
Copyright (c) 2000, 2008 IBM Corporation and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
    IBM Corporation - initial API and implementation
/*******************************************************************************
 * Copyright (c) 2000, 2008 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.jface.text;

import org.eclipse.core.runtime.Assert;


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./**
 * 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.
 * <p>
 * <strong>Performance:</strong> 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
 * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} operation of a length of
 * about <var>d</var>, where <var>d</var> is the distance from the previous change. Let <var>a(x)</var>
 * be the algorithmic performance of an <code>arraycopy</code> operation of the length <var>x</var>,
 * then such a change then performs in <i>O(a(x))</i>,
 * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in <i>O(a(length))</i>,
 * {@link #get(int)} in <i>O(1)</i>.
 * <p>
 * How frequently the array needs re-allocation is controlled by the constructor parameters.
 * </p>
 * <p>
 * This class is not intended to be subclassed.
 * </p>
 *
 * @see CopyOnWriteTextStore for a copy-on-write text store wrapper
 * @noextend This class is not intended to be subclassed by clients.
 */
public class GapTextStore implements ITextStore {
	The minimum gap size allocated when re-allocation occurs.
Since: 3.3/**
	 * The minimum gap size allocated when re-allocation occurs.
	 * @since 3.3
	 */
	private final int fMinGapSize;
	The maximum gap size allocated when re-allocation occurs.
Since: 3.3/**
	 * The maximum gap size allocated when re-allocation occurs.
	 * @since 3.3
	 */
	private final int fMaxGapSize;
	The multiplier to compute the array size from the content length
(1 <= fSizeMultiplier <= 2).
Since: 3.3/**
	 * The multiplier to compute the array size from the content length
	 * (1&nbsp;&lt;=&nbsp;fSizeMultiplier&nbsp;&lt;=&nbsp;2).
	 *
	 * @since 3.3
	 */
	private final float fSizeMultiplier;

	The store's content /** The store's content */
	private char[] fContent= new char[0];
	Starting index of the gap /** Starting index of the gap */
	private int fGapStart= 0;
	End index of the gap /** End index of the gap */
	private int fGapEnd= 0;
	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/**
	 * 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
	 */
	private int fThreshold= 0;

	Creates a new empty text store using the specified low and high watermarks.
Params: 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/**
	 * Creates a new empty text store using the specified low and high watermarks.
	 *
	 * @param lowWatermark unused - at the lower bound, the array is only resized when the content
	 *        does not fit
	 * @param highWatermark if the gap is ever larger than this, it will automatically be shrunken
	 *        (&gt;=&nbsp;0)
	 * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} instead
	 */
	@Deprecated
	public GapTextStore(int lowWatermark, int highWatermark) {
		/*
		 * Legacy constructor. The API contract states that highWatermark is the upper bound for the
		 * gap size. Albeit this contract was not previously adhered to, it is now: The allocated
		 * gap size is fixed at half the highWatermark. Since the threshold is always twice the
		 * allocated gap size, the gap will never grow larger than highWatermark. Previously, the
		 * gap size was initialized to highWatermark, causing re-allocation if the content length
		 * shrunk right after allocation. The fixed gap size is now only half of the previous value,
		 * circumventing that problem (there was no API contract specifying the initial gap size).
		 *
		 * The previous implementation did not allow the gap size to become smaller than
		 * lowWatermark, which doesn't make any sense: that area of the gap was simply never ever
		 * used.
		 */
		this(highWatermark / 2, highWatermark / 2, 0f);
	}

	Equivalent to new GapTextStore(256, 4096, 0.1f). 
Since: 3.3/**
	 * Equivalent to
	 * {@linkplain GapTextStore#GapTextStore(int, int, float) new GapTextStore(256, 4096, 0.1f)}.
	 *
	 * @since 3.3
	 */
	public GapTextStore() {
		this(256, 4096, 0.1f);
	}

	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.

Params: 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/**
	 * Creates an empty text store that uses re-allocation thresholds relative to the content
	 * length. Re-allocation is controlled by the <em>gap factor</em>, 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 <code>[0,&nbsp;maxGapFactor]</code>. When re-allocation occurs, the array is sized
	 * such that the gap factor is <code>0.5 * maxGapFactor</code>. The gap size computed in this
	 * manner is bounded by the <code>minSize</code> and <code>maxSize</code> parameters.
	 * <p>
	 * A <code>maxGapFactor</code> of <code>0</code> creates a text store that never has a gap
	 * at all (if <code>minSize</code> is 0); a <code>maxGapFactor</code> of <code>1</code>
	 * creates a text store that doubles its size with every re-allocation and that never shrinks.
	 * </p>
	 * <p>
	 * The <code>minSize</code> and <code>maxSize</code> parameters are absolute bounds to the
	 * allocated gap size. Use <code>minSize</code> to avoid frequent re-allocation for small
	 * documents. Use <code>maxSize</code> to avoid a huge gap being allocated for large
	 * documents.
	 * </p>
	 *
	 * @param minSize the minimum gap size to allocate (&gt;=&nbsp;0; use 0 for no minimum)
	 * @param maxSize the maximum gap size to allocate (&gt;=&nbsp;minSize; use
	 *        {@link Integer#MAX_VALUE} for no maximum)
	 * @param maxGapFactor is the maximum fraction of the array that is occupied by the gap (<code>0&nbsp;&lt;=&nbsp;maxGapFactor&nbsp;&lt;=&nbsp;1</code>)
	 * @since 3.3
	 */
	public GapTextStore(int minSize, int maxSize, float maxGapFactor) {
		Assert.isLegal(0f <= maxGapFactor && maxGapFactor <= 1f);
		Assert.isLegal(0 <= minSize && minSize <= maxSize);
		fMinGapSize= minSize;
		fMaxGapSize= maxSize;
		fSizeMultiplier= 1 / (1 - maxGapFactor / 2);
	}

	@Override
	public final char get(int offset) {
		if (offset < fGapStart)
			return fContent[offset];

		return fContent[offset + gapSize()];
	}

	@Override
	public final String get(int offset, int length) {
		if (fGapStart <= offset)
			return new String(fContent, offset + gapSize() , length);

		final int end= offset + length;

		if (end <= fGapStart)
			return new String(fContent, offset, length);

		StringBuilder buf= new StringBuilder(length); // see Bug 113871
		buf.append(fContent, offset, fGapStart - offset);
		buf.append(fContent, fGapEnd, end - fGapStart);
		return buf.toString();
	}

	@Override
	public final int getLength() {
		return fContent.length - gapSize();
	}

	@Override
	public final void set(String text) {
		/*
		 * Moves the gap to the end of the content. There is no sensible prediction of where the
		 * next change will occur, but at least the next change will not trigger re-allocation. This
		 * is especially important when using the GapTextStore within a CopyOnWriteTextStore, where
		 * the GTS is only initialized right before a modification.
		 */
		replace(0, getLength(), text);
	}

	@Override
	public final void replace(int offset, int length, String text) {
		if (text == null) {
			adjustGap(offset, length, 0);
		} else {
			int textLength= text.length();
			adjustGap(offset, length, textLength);
			if (textLength != 0)
				text.getChars(0, textLength, fContent, offset);
		}
	}

	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.
Params: 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/**
	 * Moves the gap to <code>offset + add</code>, moving any content after
	 * <code>offset + remove</code> behind the gap. The gap size is kept between 0 and
	 * {@link #fThreshold}, leading to re-allocation if needed. The content between
	 * <code>offset</code> and <code>offset + add</code> is undefined after this operation.
	 *
	 * @param offset the offset at which a change happens
	 * @param remove the number of character which are removed or overwritten at <code>offset</code>
	 * @param add the number of character which are inserted or overwriting at <code>offset</code>
	 */
	private void adjustGap(int offset, int remove, int add) {
		final int oldGapSize= gapSize();
		final int newGapSize= oldGapSize - add + remove;
		final boolean reuseArray= 0 <= newGapSize && newGapSize <= fThreshold;

		final int newGapStart= offset + add;
		final int newGapEnd;

		if (reuseArray)
			newGapEnd= moveGap(offset, remove, oldGapSize, newGapSize, newGapStart);
		else
			newGapEnd= reallocate(offset, remove, oldGapSize, newGapSize, newGapStart);

		fGapStart= newGapStart;
		fGapEnd= newGapEnd;
	}

	Moves the gap to newGapStart.
Params: 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/**
	 * Moves the gap to <code>newGapStart</code>.
	 *
	 * @param offset the change offset
	 * @param remove the number of removed / overwritten characters
	 * @param oldGapSize the old gap size
	 * @param newGapSize the gap size after the change
	 * @param newGapStart the offset in the array to move the gap to
	 * @return the new gap end
	 * @since 3.3
	 */
	private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) {
		/*
		 * No re-allocation necessary. The area between the change offset and gap can be copied
		 * in at most one operation. Don't copy parts that will be overwritten anyway.
		 */
		final int newGapEnd= newGapStart + newGapSize;
		if (offset < fGapStart) {
			int afterRemove= offset + remove;
			if (afterRemove < fGapStart) {
				final int betweenSize= fGapStart - afterRemove;
				arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
			}
			// otherwise, only the gap gets enlarged
		} else {
			final int offsetShifted= offset + oldGapSize;
			final int betweenSize= offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
			arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
		}
		return newGapEnd;
	}

	Reallocates a new array and copies the data from the previous one.
Params: 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/**
	 * Reallocates a new array and copies the data from the previous one.
	 *
	 * @param offset the change offset
	 * @param remove the number of removed / overwritten characters
	 * @param oldGapSize the old gap size
	 * @param newGapSize the gap size after the change if no re-allocation would occur (can be negative)
	 * @param newGapStart the offset in the array to move the gap to
	 * @return the new gap end
	 * @since 3.3
	 */
	private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) {
		// the new content length (without any gap)
		final int newLength= fContent.length - newGapSize;
		// the new array size based on the gap factor
		int newArraySize= (int) (newLength * fSizeMultiplier);
		newGapSize= newArraySize - newLength;

		// bound the gap size within min/max
		if (newGapSize < fMinGapSize) {
			newGapSize= fMinGapSize;
			newArraySize= newLength + newGapSize;
		} else if (newGapSize > fMaxGapSize) {
			newGapSize= fMaxGapSize;
			newArraySize= newLength + newGapSize;
		}

		// the upper threshold is always twice the gapsize
		fThreshold= newGapSize * 2;
		final char[] newContent= allocate(newArraySize);
		final int newGapEnd= newGapStart + newGapSize;

		/*
		 * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
		 * array. Either one of change offset and the gap may come first.
		 * - unchanged area before the change offset / gap
		 * - area between the change offset and the gap (either one may be first)
		 * - rest area after the change offset / after the gap
		 */
		if (offset < fGapStart) {
			// change comes before gap
			arrayCopy(0, newContent, 0, offset);
			int afterRemove= offset + remove;
			if (afterRemove < fGapStart) {
				// removal is completely before the gap
				final int betweenSize= fGapStart - afterRemove;
				arrayCopy(afterRemove, newContent, newGapEnd, betweenSize);
				final int restSize= fContent.length - fGapEnd;
				arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize);
			} else {
				// removal encompasses the gap
				afterRemove += oldGapSize;
				final int restSize= fContent.length - afterRemove;
				arrayCopy(afterRemove, newContent, newGapEnd, restSize);
			}
		} else {
			// gap comes before change
			arrayCopy(0, newContent, 0, fGapStart);
			final int offsetShifted= offset + oldGapSize;
			final int betweenSize= offsetShifted - fGapEnd;
			arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
			final int afterRemove= offsetShifted + remove;
			final int restSize= fContent.length - afterRemove;
			arrayCopy(afterRemove, newContent, newGapEnd, restSize);
		}

		fContent= newContent;
		return newGapEnd;
	}

	Allocates a new char[size].
Params: size – the length of the new array.
Returns: a newly allocated char array
Since: 3.3/**
	 * Allocates a new <code>char[size]</code>.
	 *
	 * @param size the length of the new array.
	 * @return a newly allocated char array
	 * @since 3.3
	 */
	private char[] allocate(int size) {
		return new char[size];
	}

	/*
	 * Executes System.arraycopy if length != 0. A length < 0 cannot happen -> don't hide coding
	 * errors by checking for negative lengths.
	 * @since 3.3
	 */
	private void arrayCopy(int srcPos, char[] dest, int destPos, int length) {
		if (length != 0)
			System.arraycopy(fContent, srcPos, dest, destPos, length);
	}

	Returns the gap size.
Returns: the gap size
Since: 3.3/**
	 * Returns the gap size.
	 *
	 * @return the gap size
	 * @since 3.3
	 */
	private int gapSize() {
		return fGapEnd - fGapStart;
	}

	Returns a copy of the content of this text store.
For internal use only.
Returns: a copy of the content of this text store/**
	 * Returns a copy of the content of this text store.
	 * For internal use only.
	 *
	 * @return a copy of the content of this text store
	 */
	protected String getContentAsString() {
		return new String(fContent);
	}

	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/**
	 * Returns the start index of the gap managed by this text store.
	 * For internal use only.
	 *
	 * @return the start index of the gap managed by this text store
	 */
	protected int getGapStartIndex() {
		return fGapStart;
	}

	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/**
	 * Returns the end index of the gap managed by this text store.
	 * For internal use only.
	 *
	 * @return the end index of the gap managed by this text store
	 */
	protected int getGapEndIndex() {
		return fGapEnd;
	}
}
See Also:	for a copy-on-write text store wrapper
@noextend	This class is not intended to be subclassed by clients.
Params:	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
Params:	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
Params:	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
Params:	size – the length of the new array.
Returns:	a newly allocated char array
Since:	3.3
/

org.eclipse.platform/ org.eclipse.text/ 3.10.0/ org/eclipse/jface/text/GapTextStore.java
