gnu.lists

Class StableManager

java.lang.Object

gnu.lists.StableManager

public class StableManager
extends java.lang.Object

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

Field Summary

Fields

Modifier and Type	Field and Description
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.

Constructor Summary

Constructors

Constructor and Description
StableManager(SimpleVector base)

Method Summary

Modifier and Type	Method and Description
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)
int	createPos(int index, boolean isAfter)
int	endPos()
protected void	gapReserve(SimpleVector base, int where, int needed) Adjust gap to 'where', and make sure it is least `needed' elements long.
boolean	hasNext(int ipos)
protected boolean	isAfterPos(int ipos)
int	nextIndex(int ipos)
int	nextPos(int ipos)
void	releasePos(int ipos)
protected void	removePosRange(int ipos0, int ipos1)
int	startPos()
protected void	unchainFreelist() Set all free elements in positions to FREE_POSITION.

Methods inherited from class java.lang.Object

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

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 keep 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 mode makes it easy to loop over all positions, ignoring 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

StableManager

public StableManager(SimpleVector base)

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()

endPos

public int endPos()

allocPositionIndex

protected int allocPositionIndex()

createPos

public int createPos(int index,
                     boolean isAfter)

isAfterPos

protected boolean isAfterPos(int ipos)

hasNext

public boolean hasNext(int ipos)

nextPos

public int nextPos(int ipos)

nextIndex

public int nextIndex(int ipos)

releasePos

public void releasePos(int ipos)

copyPos

public int copyPos(int ipos)

gapReserve

protected void gapReserve(SimpleVector base,
                          int where,
                          int needed)

Adjust gap to 'where', and make sure it is least `needed' elements long.

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.

removePosRange

protected void removePosRange(int ipos0,
                              int ipos1)

consumePosRange

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