001: // Copyright (c) 2001, 2002, 2003 Per M.A. Bothner and Brainfood Inc.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.lists;
005:
006: /** Implements a stable sequence with sticky positions.
007: * I.e if you have a position, it gets automatically updated after
008: * insertions and deletions. */
009:
010: public class StableVector extends GapVector {
011: /** This array maps from the exported ipos values (indexes in the positions
012: * array) to the ipos of the underlying SimpleVector base.
013: * The first two elements are reserved for START_POSITION and END_POSITION.
014: * Unused elements in positions are chained together in a free list
015: * headed by the 'free' variable. */
016: protected int[] positions;
017:
018: /** The head of the free elements in position, if they are chained.
019: * We need track of available elements in the positions array in two ways:
020: * In unchained mode, there is no free list per se. Instead an index i
021: * is available if positions[i]==FREE_POSITION. This modemakes it
022: * easy to loop over all positions, ignores the unused ones.
023: * In chained mode, there is a free list and if index i is available,
024: * then positions[i] is the next available index, with -1 if there is none.
025: * Unchained mode is indicated by free==-2.
026: * In chained mode, free is the first element in the free list,
027: * or -1 if the free list is empty.
028: * The main virtue of this convention is that we don't need a separate
029: * list or array for the free list. But we should get rid of the
030: * unchained mode, at least. FIXME.
031: */
032: protected int free;
033:
034: /** An invalid value for an in-use element of positions. */
035: protected static final int FREE_POSITION = -1 << 1;
036:
037: /** Put all free elements in positions in a chain starting with free. */
038: protected void chainFreelist() {
039: free = -1;
040: for (int i = positions.length; --i > END_POSITION;) {
041: int pos = positions[i];
042: if (pos == FREE_POSITION) {
043: positions[i] = free;
044: free = i;
045: }
046: }
047: }
048:
049: /** Set all free elements in positions to FREE_POSITION. */
050: protected void unchainFreelist() {
051: for (int i = free; i >= 0;) {
052: int next = positions[i];
053: positions[i] = FREE_POSITION;
054: i = next;
055: }
056: free = -2;
057: }
058:
059: /** Index in positions for the start position.
060: * positions[START_POSITION] is always 0. */
061: static final int START_POSITION = 0;
062:
063: /** Index in positions for the end position.
064: * positions[END] is always (size()<<1)+1. */
065: static final int END_POSITION = 1;
066:
067: public int startPos() {
068: return START_POSITION;
069: }
070:
071: public int endPos() {
072: return END_POSITION;
073: }
074:
075: public StableVector(SimpleVector base) {
076: super (base);
077: positions = new int[16];
078: positions[START_POSITION] = 0;
079: positions[END_POSITION] = (base.getBufferLength() << 1) | 1;
080: free = -1;
081: for (int i = positions.length; --i >= 2;) {
082: positions[i] = free;
083: free = i;
084: }
085: }
086:
087: protected StableVector() {
088: }
089:
090: protected int allocPositionIndex() {
091: if (free == -2)
092: chainFreelist();
093: if (free < 0) {
094: int oldLength = positions.length;
095: int[] tmp = new int[2 * oldLength];
096: System.arraycopy(positions, 0, tmp, 0, oldLength);
097: for (int i = 2 * oldLength; --i >= oldLength;) {
098: tmp[i] = free;
099: free = i;
100: }
101: positions = tmp;
102: }
103: int pos = free;
104: free = positions[free];
105: return pos;
106: }
107:
108: public int createPos(int index, boolean isAfter) {
109: if (index == 0 && !isAfter)
110: return START_POSITION;
111: else if (isAfter && index == size())
112: return END_POSITION;
113: if (index > gapStart || (index == gapStart && isAfter))
114: index += gapEnd - gapStart;
115: int ipos = allocPositionIndex();
116: positions[ipos] = (index << 1) | (isAfter ? 1 : 0);
117: return ipos;
118: }
119:
120: protected boolean isAfterPos(int ipos) {
121: return (positions[ipos] & 1) != 0;
122: }
123:
124: public boolean hasNext(int ipos) {
125: int ppos = positions[ipos];
126: int index = ppos >>> 1;
127: if (index >= gapStart)
128: index += gapEnd - gapStart;
129: return index < base.getBufferLength();
130: }
131:
132: public int nextPos(int ipos) {
133: int ppos = positions[ipos];
134: int index = ppos >>> 1;
135: if (index >= gapStart)
136: index += gapEnd - gapStart;
137: if (index >= base.getBufferLength()) {
138: releasePos(ipos);
139: return 0;
140: }
141: if (ipos == 0)
142: ipos = createPos(0, true);
143: positions[ipos] = ppos | 1;
144: return ipos;
145: }
146:
147: public int nextIndex(int ipos) {
148: int index = positions[ipos] >>> 1;
149: if (index > gapStart)
150: index -= gapEnd - gapStart;
151: return index;
152: }
153:
154: public void releasePos(int ipos) {
155: if (ipos >= 2) {
156: if (free == -2)
157: chainFreelist();
158: positions[ipos] = free;
159: free = ipos;
160: }
161: }
162:
163: public int copyPos(int ipos) {
164: if (ipos > END_POSITION) {
165: int i = allocPositionIndex();
166: positions[i] = positions[ipos];
167: ipos = i;
168: }
169: return ipos;
170: }
171:
172: public void fillPosRange(int fromPos, int toPos, Object value) {
173: fillPosRange(positions[fromPos], positions[toPos], value);
174: }
175:
176: protected void shiftGap(int newGapStart) {
177: int oldGapStart = gapStart;
178: int delta = newGapStart - oldGapStart;
179: int low, high, adjust;
180: if (delta > 0) {
181: low = gapEnd;
182: high = low + delta;
183: adjust = (oldGapStart - low) << 1;
184: // The position corresponding to the new endGap should be adjusted
185: // only if it has the isAfter (low-order) bit is clear. Hence the -1.
186: low = low << 1;
187: high = (high << 1) - 1;
188: } else if (newGapStart == oldGapStart)
189: return;
190: else // newGapStart < gapStart:
191: {
192: // Positions at the newgapStart should be adjust only if isAfter.
193: low = (newGapStart << 1) + 1;
194: high = oldGapStart << 1;
195: adjust = (gapEnd - oldGapStart) << 1;
196: }
197: super .shiftGap(newGapStart);
198:
199: adjustPositions(low, high, adjust);
200: }
201:
202: /** Add a delta to all positions elements that point into a given range.
203: * Assume x==positions[i], then if (unsigned)x>=(unsigned)low
204: * && (unsigned)x <= (unsigned)high, then add delta to positions[i].
205: * Using unsigned comparisons allows us to compare ipos values,
206: * which include both the index and the isAfter low-order bit. */
207: protected void adjustPositions(int low, int high, int delta) {
208: if (free >= 0)
209: unchainFreelist();
210:
211: // Invert the high-order bit, because:
212: // (unsigned) X > (unsigned) Y
213: // iff (int) (X^0x80000000) > (int) (Y^0x80000000)
214: low = low ^ 0x80000000;
215: high = high ^ 0x80000000;
216:
217: for (int i = positions.length; --i > START_POSITION;) {
218: int pos = positions[i];
219: if (pos != FREE_POSITION) {
220: int index = pos ^ 0x80000000;
221: if (index >= low && index <= high)
222: positions[i] = pos + delta;
223: }
224: }
225: }
226:
227: protected void gapReserve(int size) {
228: int oldGapEnd = gapEnd;
229: int oldLength = base.getBufferLength();
230: super .gapReserve(size);
231: int newLength = base.getBufferLength();
232: adjustPositions(oldGapEnd << 1, (newLength << 1) | 1,
233: (newLength - oldLength) << 1);
234: }
235:
236: protected int addPos(int ipos, Object value) {
237: int ppos = positions[ipos];
238: int index = ppos >>> 1;
239: if (index >= gapStart)
240: index += gapEnd - gapStart;
241: // Force positions[ipos] to have the isAfter property.
242: if ((ppos & 1) == 0) {
243: if (ipos == 0)
244: ipos = createPos(0, true);
245: else
246: positions[ipos] = ppos | 1;
247: }
248: add(index, value);
249: return ipos;
250: }
251:
252: protected void removePosRange(int ipos0, int ipos1) {
253: super .removePosRange(positions[ipos0], positions[ipos1]);
254:
255: // adjust positions in gap
256: int low = gapStart;
257: int high = gapEnd;
258: if (free >= 0)
259: unchainFreelist();
260: for (int i = positions.length; --i > START_POSITION;) {
261: int pos = positions[i];
262: if (pos != FREE_POSITION) {
263: int index = pos >> 1;
264: boolean isAfter = (pos & 1) != 0;
265: if (isAfter) {
266: if (index >= low && index < high)
267: positions[i] = (gapEnd << 1) | 1;
268: } else {
269: if (index > low && index <= high)
270: positions[i] = (gapStart << 1);
271: }
272: }
273: }
274: }
275:
276: /*
277: public Object remove(int index)
278: {
279: // FIXME
280: }
281: */
282:
283: public void consumePosRange(int iposStart, int iposEnd, Consumer out) {
284: super.consumePosRange(positions[iposStart], positions[iposEnd],
285: out);
286: }
287: }
|