gnu.lists
Class StableVector

java.lang.Object
  gnu.lists.AbstractSequence
      gnu.lists.GapVector
          gnu.lists.StableVector

All Implemented Interfaces:

Consumable, Sequence, java.lang.Iterable, java.util.Collection, java.util.List

Direct Known Subclasses:

CharBuffer

public class StableVector
extends GapVector

Implements a stable sequence with sticky positions. I.e if you have a position, it gets automatically updated after insertions and deletions.

Field Summary

protected int	free The head of the free elements in position, if they are chained.
protected static int	FREE_POSITION An invalid value for an in-use element of positions.
protected int[]	positions This array maps from the exported ipos values (indexes in the positions array) to the ipos of the underlying SimpleVector base.

Fields inherited from class gnu.lists.GapVector

base, gapEnd, gapStart

Fields inherited from interface gnu.lists.Sequence

ATTRIBUTE_VALUE, BOOLEAN_VALUE, CDATA_VALUE, CHAR_VALUE, COMMENT_VALUE, DOCUMENT_VALUE, DOUBLE_VALUE, ELEMENT_VALUE, EOF_VALUE, eofValue, FLOAT_VALUE, INT_S16_VALUE, INT_S32_VALUE, INT_S64_VALUE, INT_S8_VALUE, INT_U16_VALUE, INT_U32_VALUE, INT_U64_VALUE, INT_U8_VALUE, OBJECT_VALUE, PRIM_VALUE, PROCESSING_INSTRUCTION_VALUE, TEXT_BYTE_VALUE

Constructor Summary

protected	StableVector()
	StableVector(SimpleVector base)

Method Summary

protected int	addPos(int ipos, java.lang.Object value) Add a value at a specified Pos.
protected void	adjustPositions(int low, int high, int delta) Add a delta to all positions elements that point into a given range.
protected int	allocPositionIndex()
protected void	chainFreelist() Put all free elements in positions in a chain starting with free.
void	consumePosRange(int iposStart, int iposEnd, Consumer out)
int	copyPos(int ipos) Make a copy of a position int.
int	createPos(int index, boolean isAfter) Generate a position at a given index.
int	endPos()
void	fillPosRange(int fromPos, int toPos, java.lang.Object value)
protected void	gapReserve(int size) Make sure gap is at least 'size' elements long.
boolean	hasNext(int ipos)
protected boolean	isAfterPos(int ipos) Tests whether the position has the "isAfter" property.
int	nextIndex(int ipos) Get the offset from the beginning corresponding to a position cookie.
int	nextPos(int ipos) Return the next position following the argument.
void	releasePos(int ipos) Reclaim any resources used by the given position int.
protected void	removePosRange(int ipos0, int ipos1) Remove a range where each end-point is a position in a container.
protected void	shiftGap(int newGapStart)
int	startPos()
protected void	unchainFreelist() Set all free elements in positions to FREE_POSITION.

Methods inherited from class gnu.lists.GapVector

add, fill, gapReserve, get, getNextKind, getSegment, set, size

Methods inherited from class gnu.lists.AbstractSequence

add, addAll, addAll, clear, compare, compare, compare, consume, consumeNext, contains, containsAll, createRelativePos, elements, equals, equals, fill, firstAttributePos, firstChildPos, firstChildPos, fromEndIndex, get, getAttribute, getAttributeLength, getContainingSequenceSize, getEffectiveIndex, getIndexDifference, getIterator, getIterator, getIteratorAtPos, getLowBound, getNextTypeName, getNextTypeObject, getPosNext, getPosPrevious, getSize, gotoAttributesStart, gotoChildrenStart, gotoParent, hashCode, hasPrevious, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, nextIndex, nextMatching, parentPos, previousPos, rank, remove, remove, removeAll, removePos, retainAll, set, setPosNext, setPosPrevious, stableCompare, subList, subSequence, subSequencePos, toArray, toArray, toString, toString, unsupported, unsupportedException

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface gnu.lists.Sequence

elements, isEmpty

Methods inherited from interface java.util.List

add, addAll, addAll, clear, contains, containsAll, equals, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, retainAll, subList, toArray, toArray

Methods inherited from interface gnu.lists.Consumable

consume

Field Detail

positions

protected int[] positions

This array maps from the exported ipos values (indexes in the positions array) to the ipos of the underlying SimpleVector base. The first two elements are reserved for START_POSITION and END_POSITION. Unused elements in positions are chained together in a free list headed by the 'free' variable.

free

protected int free

The head of the free elements in position, if they are chained. We need track of available elements in the positions array in two ways: In unchained mode, there is no free list per se. Instead an index i is available if positions[i]==FREE_POSITION. This modemakes it easy to loop over all positions, ignores the unused ones. In chained mode, there is a free list and if index i is available, then positions[i] is the next available index, with -1 if there is none. Unchained mode is indicated by free==-2. In chained mode, free is the first element in the free list, or -1 if the free list is empty. The main virtue of this convention is that we don't need a separate list or array for the free list. But we should get rid of the unchained mode, at least. FIXME.

FREE_POSITION

protected static final int FREE_POSITION

An invalid value for an in-use element of positions.

See Also:

Constant Field Values

Constructor Detail

StableVector

public StableVector(SimpleVector base)

StableVector

protected StableVector()

Method Detail

chainFreelist

protected void chainFreelist()

Put all free elements in positions in a chain starting with free.

unchainFreelist

protected void unchainFreelist()

Set all free elements in positions to FREE_POSITION.

startPos

public int startPos()

Overrides:

startPos in class AbstractSequence

endPos

public int endPos()

Overrides:

endPos in class AbstractSequence

allocPositionIndex

protected int allocPositionIndex()

createPos

public int createPos(int index,
                     boolean isAfter)

Description copied from class: AbstractSequence

Generate a position at a given index. The result is a position cookie that must be free'd with releasePos.

Overrides:

createPos in class GapVector

Parameters:

index - offset from beginning of desired position

isAfter - should the position have the isAfter property

isAfterPos

protected boolean isAfterPos(int ipos)

Description copied from class: AbstractSequence

Tests whether the position has the "isAfter" property. I.e. if something is inserted at the position, will the iterator end up being after the new data?

Overrides:

isAfterPos in class GapVector

hasNext

public boolean hasNext(int ipos)

Overrides:

hasNext in class GapVector

nextPos

public int nextPos(int ipos)

Description copied from class: AbstractSequence

Return the next position following the argument. The new position has the isAfter property. The argument is implicitly released (as in releasePos). Returns 0 if we are already at end of file.

Overrides:

nextPos in class AbstractSequence

nextIndex

public int nextIndex(int ipos)

Description copied from class: AbstractSequence

Get the offset from the beginning corresponding to a position cookie.

Overrides:

nextIndex in class GapVector

releasePos

public void releasePos(int ipos)

Description copied from class: AbstractSequence

Reclaim any resources used by the given position int.

Overrides:

releasePos in class AbstractSequence

Parameters:

ipos - the Pos being free'd.

copyPos

public int copyPos(int ipos)

Description copied from class: AbstractSequence

Make a copy of a position int. For simple positions returns the argument. However, if the positions are magic cookies that are actively managed by the sequence (as opposed to for example a simple index), then making a copy may need to increment a reference count, or maybe allocate a new position cookie. In any case, the new position is initialized to the same offset (and isAfter property) as the original.

Overrides:

copyPos in class AbstractSequence

Parameters:

ipos - the position being copied.

Returns:

the new position

fillPosRange

public void fillPosRange(int fromPos,
                         int toPos,
                         java.lang.Object value)

Overrides:

fillPosRange in class GapVector

shiftGap

protected void shiftGap(int newGapStart)

Overrides:

shiftGap in class GapVector

adjustPositions

protected void adjustPositions(int low,
                               int high,
                               int delta)

Add a delta to all positions elements that point into a given range. Assume x==positions[i], then if (unsigned)x>=(unsigned)low && (unsigned)x <= (unsigned)high, then add delta to positions[i]. Using unsigned comparisons allows us to compare ipos values, which include both the index and the isAfter low-order bit.

gapReserve

protected void gapReserve(int size)

Description copied from class: GapVector

Make sure gap is at least 'size' elements long.

Overrides:

gapReserve in class GapVector

addPos

protected int addPos(int ipos,
                     java.lang.Object value)

Description copied from class: AbstractSequence

Add a value at a specified Pos.

Overrides:

addPos in class GapVector

Returns:

the updated Pos, which is after the inserted value..

removePosRange

protected void removePosRange(int ipos0,
                              int ipos1)

Description copied from class: AbstractSequence

Remove a range where each end-point is a position in a container.

Overrides:

removePosRange in class GapVector

Parameters:

ipos0 - start of range, as a poistion

ipos1 - end of range

consumePosRange

public void consumePosRange(int iposStart,
                            int iposEnd,
                            Consumer out)

Overrides:

consumePosRange in class GapVector