gnu.lists

Class StableVector

Implemented Interfaces:
java.util.List, Consumable, Sequence
Known Direct 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 static int
FREE_POSITION
An invalid value for an in-use element of positions.
protected int
free
The head of the free elements in position, if they are chained.
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, 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, eofValue

Constructor Summary

StableVector()
StableVector(SimpleVector base)

Method Summary

protected int
addPos(int ipos, 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, 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, addPos, consumePosRange, createPos, fill, fillPosRange, gapReserve, gapReserve, get, getNextKind, getSegment, hasNext, isAfterPos, nextIndex, removePosRange, set, shiftGap, size

Methods inherited from class gnu.lists.AbstractSequence

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

Field Details

FREE_POSITION

protected static final int FREE_POSITION
An invalid value for an in-use element of positions.
Field Value:
-2

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.

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.

Constructor Details

StableVector

protected StableVector()

StableVector

public StableVector(SimpleVector base)

Method Details

addPos

protected int addPos(int ipos,
                     Object value)
Add a value at a specified Pos.
Overrides:
addPos in interface GapVector
Returns:
the updated Pos, which is after the inserted value..

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.

allocPositionIndex

protected int allocPositionIndex()

chainFreelist

protected void chainFreelist()
Put all free elements in positions in a chain starting with free.

consumePosRange

public void consumePosRange(int iposStart,
                            int iposEnd,
                            Consumer out)
Overrides:
consumePosRange in interface GapVector

copyPos

public int copyPos(int ipos)
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 interface AbstractSequence
Parameters:
ipos - the position being copied.
Returns:
the new position

createPos

public int createPos(int index,
                     boolean isAfter)
Generate a position at a given index. The result is a position cookie that must be free'd with releasePos.
Overrides:
createPos in interface GapVector
Parameters:
index - offset from beginning of desired position
isAfter - should the position have the isAfter property

endPos

public int endPos()
Overrides:
endPos in interface AbstractSequence

fillPosRange

public void fillPosRange(int fromPos,
                         int toPos,
                         Object value)
Overrides:
fillPosRange in interface GapVector

gapReserve

protected void gapReserve(int size)
Make sure gap is at least 'size' elements long.
Overrides:
gapReserve in interface GapVector

hasNext

public boolean hasNext(int ipos)
Overrides:
hasNext in interface GapVector

isAfterPos

protected boolean isAfterPos(int ipos)
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 interface GapVector

nextIndex

public int nextIndex(int ipos)
Get the offset from the beginning corresponding to a position cookie.
Overrides:
nextIndex in interface GapVector

nextPos

public int nextPos(int ipos)
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 interface AbstractSequence

releasePos

public void releasePos(int ipos)
Reclaim any resources used by the given position int.
Overrides:
releasePos in interface AbstractSequence
Parameters:
ipos - the Pos being free'd.

removePosRange

protected void removePosRange(int ipos0,
                              int ipos1)
Remove a range where each end-point is a position in a container.
Overrides:
removePosRange in interface GapVector
Parameters:
ipos0 - start of range, as a poistion
ipos1 - end of range

shiftGap

protected void shiftGap(int newGapStart)
Overrides:
shiftGap in interface GapVector

startPos

public int startPos()
Overrides:
startPos in interface AbstractSequence

unchainFreelist

protected void unchainFreelist()
Set all free elements in positions to FREE_POSITION.