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 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.
|
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.
protected static final 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.
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.
protected StableVector()
protected int addPos(int ipos, Object value)
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.
protected int allocPositionIndex()
protected void chainFreelist()
Put all free elements in positions in a chain starting with free.
public void consumePosRange(int iposStart, int iposEnd,
Consumer out)
public int copyPos(int ipos)
public int createPos(int index, boolean isAfter)
public int endPos()
public void fillPosRange(int fromPos, int toPos, Object value)
protected void gapReserve(int size)
public boolean hasNext(int ipos)
protected boolean isAfterPos(int ipos)
public int nextIndex(int ipos)
public int nextPos(int ipos)
public void releasePos(int ipos)
protected void removePosRange(int ipos0, int ipos1)
protected void shiftGap(int newGapStart)
public int startPos()
protected void unchainFreelist()
Set all free elements in positions to FREE_POSITION.