org.netbeans.lib.editor.util

Class OffsetGapList<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

org.netbeans.lib.editor.util.GapList<E>

org.netbeans.lib.editor.util.OffsetGapList<E>

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess, SequencedCollection<E>

public abstract class OffsetGapList<E>
extends GapList<E>

Extension of the gap list which is expected to store elements that have an integer offset stored in them.
The elements must be stored in the list in an ascending order.
To efficiently manage offsets that need to change upon inserts and removes into an underlying storage (e.g. a swing document) the list maintains an offset gap that gets moved and shrinked/extended according to inserts/removals.

The physical raw offset stored in the element needs to be preprocessed to get the real offset value.
In short the raw offset is either the actual offset in case the offset gap is above it (greater or equal to offsetGapStart value) or, it's the actual offset plus the offset gap length otherwise.

Offsets up to +1GB (Integer.MAX_VALUE / 2) can be handled by this class which should be sufficient for most uses.
It's not +2GB as then the offsets shifted above the offset gap would overflow and be below zero which would break the comparisons whether the offset is below offset gap start.
Negative offsets are supported as well with a limit of -2GB.

See Also:

Serialized Form

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor and Description
OffsetGapList()
OffsetGapList(int initialCapacity)

Method Summary

Modifier and Type	Method and Description
protected void	consistencyCheck() Internal consistency check.
void	defaultInsertUpdate(int offset, int length) Inform the list that there was an insert done into an underlying storage (e.g.
void	defaultRemoveUpdate(int offset, int length) Inform the list that there was a removal done into an underlying storage (e.g.
protected String	dumpInternals()
protected int	elementOffset(E elem) Get the offset of the element stored in the list.
protected int	elementOffset(int index) Get the offset of the element stored in the list at the given index.
protected abstract int	elementRawOffset(E elem) Get the raw offset of the given element currently stored in the list.
protected int	findElementIndex(int offset) Find an index of the first element at the given offset in the list by using binary search.
protected void	moveOffsetGap(int offset, int index) Move the offset gap so that it's on the requested offset.
protected int	offset2raw(int offset) Translate regular offset to raw offset.
protected int	offsetGapLength() Obtain the length of the offset gap.
protected int	offsetGapStart() Obtain the start of the offset gap.
protected int	raw2Offset(int rawOffset) Translate raw offset into real offset.
protected abstract void	setElementRawOffset(E elem, int rawOffset) Set the raw offset of the given element currently stored in the list.
protected void	updateElementOffsetAdd(E elem) This method updates element's offset (shifts it above offset gap if necessary) before adding the element to the list.
protected void	updateElementOffsetRemove(E elem) This method updates element's offset (shifts it below offset gap if necessary) before (or after) the element gets removed from the list.
protected void	updateOffsetGapLength(int offsetGapLengthDelta) Update the offset gap length by the given delta.
protected void	updateOffsetGapStart(int offsetDelta) Update the offset gap start by the given delta.

Methods inherited from class org.netbeans.lib.editor.util.GapList

add, add, addAll, addAll, addAll, addAll, addArray, addArray, addArray, clear, clone, consistencyError, contains, copy, copyElements, copyElements, copyItems, dumpDetails, dumpElements, ensureCapacity, get, indexOf, isEmpty, lastIndexOf, remove, remove, removeRange, set, size, swap, toArray, toArray, toString, trimToSize

Methods inherited from class java.util.AbstractList

equals, hashCode, iterator, listIterator, listIterator, subList

Methods inherited from class java.util.AbstractCollection

containsAll, remove, removeAll, retainAll

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addFirst, addLast, containsAll, copyOf, equals, getFirst, getLast, hashCode, iterator, listIterator, listIterator, of, of, of, of, of, of, of, of, of, of, of, of, remove, removeAll, removeFirst, removeLast, replaceAll, retainAll, reversed, sort, spliterator, subList

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

OffsetGapList

public OffsetGapList()

OffsetGapList

public OffsetGapList(int initialCapacity)

Method Detail

elementRawOffset

protected abstract int elementRawOffset(E elem)

Get the raw offset of the given element currently stored in the list.

Parameters:

elem - element currently stored in the list.

Returns:

raw offset of the element. It needs to be preprocessed by OffsetGapList.raw2Offset(int) to become the real offset.

setElementRawOffset

protected abstract void setElementRawOffset(E elem,
                                            int rawOffset)

Set the raw offset of the given element currently stored in the list.

Parameters:

elem - element currently stored in the list.

rawOffset - raw offset to be stored in the given element.

elementOffset

protected int elementOffset(E elem)

Get the offset of the element stored in the list.
The raw offset stored in the element is preprocessed to become a real offset.

Parameters:

elem - element stored in the list.

Returns:

offset of the element.

elementOffset

protected int elementOffset(int index)

Get the offset of the element stored in the list at the given index.
The raw offset stored in the element is preprocessed to become a real offset.

Parameters:

index - of the element in the list.

Returns:

offset of the element.

Throws:

IndexOutOfBoundsException - if index >= size() or lower than zero

defaultInsertUpdate

public void defaultInsertUpdate(int offset,
                                int length)

Inform the list that there was an insert done into an underlying storage (e.g. a swing document) which should move up offsets of the elements that have their offset greater or equal to the insertion offset.

Subclasses can build their own way of updating and they are not required to use this method.

Parameters:

offset - offset at which the insertion occurred.

length - length of the inserted area.

defaultRemoveUpdate

public void defaultRemoveUpdate(int offset,
                                int length)

Inform the list that there was a removal done into an underlying storage (e.g. a swing document) which should move down offsets of the elements that have their offsets greater than the removal offset.
The offsets inside the removal area will be moved to its begining.

Subclasses can build their own way of updating and they are not required to use this method.

Parameters:

offset - offset at which the removal occurred.

length - length of the removed area.

moveOffsetGap

protected final void moveOffsetGap(int offset,
                                   int index)

Move the offset gap so that it's on the requested offset.
This method can be used when the index of the first element at the given offset was precomputed already.

Note: Improper use of this may logically damage offsets of the elements contained in the list.

Parameters:

offset - offset to which the offsetGapStart should be assigned.

index - index of the first element in the list that has an offset that is greater or equal that the given offset parameter.
It may be computed by OffsetGapList.findElementIndex(int).

offsetGapStart

protected final int offsetGapStart()

Obtain the start of the offset gap.

Returns:

start of the offset gap.

updateOffsetGapStart

protected final void updateOffsetGapStart(int offsetDelta)

Update the offset gap start by the given delta.
This may be needed e.g. after insertion/removal was done in the document.

Note: Improper use of this may logically damage offsets of the elements contained in the list.

offsetGapLength

protected final int offsetGapLength()

Obtain the length of the offset gap.

Returns:

length of the offset gap.

updateOffsetGapLength

protected final void updateOffsetGapLength(int offsetGapLengthDelta)

Update the offset gap length by the given delta.
This may be needed e.g. after insertion/removal was done in the document.

Note: Improper use of this may logically damage offsets of the elements contained in the list.

findElementIndex

protected final int findElementIndex(int offset)

Find an index of the first element at the given offset in the list by using binary search.

Parameters:

offset - offset of the element

Returns:

index of the element. If there is no element with that index then the index of the next element (with the greater offset) (or size of the list) will be returned.
If there are multiple items with the same offset then the first one of them will be returned.

updateElementOffsetAdd

protected void updateElementOffsetAdd(E elem)

This method updates element's offset (shifts it above offset gap if necessary) before adding the element to the list.
This method should be called before (or after) the element is physically added to the list. If the element is added below the offset gap then calling of this method is not necessary.

updateElementOffsetRemove

protected void updateElementOffsetRemove(E elem)

This method updates element's offset (shifts it below offset gap if necessary) before (or after) the element gets removed from the list.
This method should be called after the element is physically removed from the list and it's desired that it retains its natural offset (not possibly shifted by the offset gap length).
If the element was located below the offset gap prior removal then calling of this method is not necessary.

raw2Offset

protected final int raw2Offset(int rawOffset)

Translate raw offset into real offset.

Parameters:

rawOffset - raw offset stored in an element.

Returns:

real offset that the element is supposed to have.

offset2raw

protected final int offset2raw(int offset)

Translate regular offset to raw offset.

Parameters:

offset - regular offset.

Returns:

raw offset that can be used in elements.

consistencyCheck

protected void consistencyCheck()

Description copied from class: GapList

Internal consistency check.

Overrides:

consistencyCheck in class GapList<E>

dumpInternals

protected String dumpInternals()

Overrides:

dumpInternals in class GapList<E>