gnu.lists

Class StableVector

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 intfree
The head of the free elements in position, if they are chained.
protected static intFREE_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.
Constructor Summary
StableVector(SimpleVector base)
protected StableVector()
Method Summary
protected intaddPos(int ipos, Object value)
protected voidadjustPositions(int low, int high, int delta)
Add a delta to all positions elements that point into a given range.
protected intallocPositionIndex()
protected voidchainFreelist()
Put all free elements in positions in a chain starting with free.
voidconsumePosRange(int iposStart, int iposEnd, Consumer out)
intcopyPos(int ipos)
intcreatePos(int index, boolean isAfter)
intendPos()
voidfillPosRange(int fromPos, int toPos, Object value)
protected voidgapReserve(int size)
booleanhasNext(int ipos)
protected booleanisAfterPos(int ipos)
intnextIndex(int ipos)
intnextPos(int ipos)
voidreleasePos(int ipos)
protected voidremovePosRange(int ipos0, int ipos1)
protected voidshiftGap(int newGapStart)
intstartPos()
protected voidunchainFreelist()
Set all free elements in positions to FREE_POSITION.

Field Detail

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.

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 Detail

StableVector

public StableVector(SimpleVector base)

StableVector

protected StableVector()

Method Detail

addPos

protected int addPos(int ipos, Object 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)

copyPos

public int copyPos(int ipos)

createPos

public int createPos(int index, boolean isAfter)

endPos

public int endPos()

fillPosRange

public void fillPosRange(int fromPos, int toPos, Object value)

gapReserve

protected void gapReserve(int size)

hasNext

public boolean hasNext(int ipos)

isAfterPos

protected boolean isAfterPos(int ipos)

nextIndex

public int nextIndex(int ipos)

nextPos

public int nextPos(int ipos)

releasePos

public void releasePos(int ipos)

removePosRange

protected void removePosRange(int ipos0, int ipos1)

shiftGap

protected void shiftGap(int newGapStart)

startPos

public int startPos()

unchainFreelist

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