001: // Copyright (c) 2001 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: /**
007: * An array with a gap in the middle, allowing efficient insert and delete.
008: * The actual storage is delegated to a SimpleVector, so the element
009: * type depends on the sub-class of SimpleVector used.
010: */
011:
012: public class GapVector extends AbstractSequence implements Sequence {
013: public SimpleVector base;
014: public int gapStart;
015: public int gapEnd;
016:
017: public GapVector(SimpleVector base) {
018: this .base = base;
019: this .gapStart = 0;
020: this .gapEnd = base.size;
021: }
022:
023: protected GapVector() {
024: }
025:
026: public int size() {
027: return base.size - (gapEnd - gapStart);
028: }
029:
030: public boolean hasNext(int ipos) {
031: int index = ipos >>> 1;
032: if (index >= gapStart)
033: index += gapEnd - gapStart;
034: return index < base.size;
035: }
036:
037: public int getNextKind(int ipos) {
038: return hasNext(ipos) ? base.getElementKind() : EOF_VALUE;
039: }
040:
041: public Object get(int index) {
042: // If index is out of bounds, the base.get will catch that.
043: if (index >= gapStart)
044: index += gapEnd - gapStart;
045: return base.get(index);
046: }
047:
048: public Object set(int index, Object value) {
049: // If index is out of bounds, the base.set will catch that.
050: if (index >= gapStart)
051: index += gapEnd - gapStart;
052: return base.set(index, value);
053: }
054:
055: public void fill(Object value) {
056: base.fill(gapEnd, base.size, value);
057: base.fill(0, gapStart, value);
058: }
059:
060: public void fillPosRange(int fromPos, int toPos, Object value) {
061: int from = fromPos == -1 ? base.size : fromPos >>> 1;
062: int to = toPos == -1 ? base.size : toPos >>> 1;
063: int limit = gapStart < to ? gapStart : to;
064: for (int i = from; i < limit; i++)
065: base.setBuffer(i, value);
066: for (int i = gapEnd; i < to; i++)
067: base.setBuffer(i, value);
068: }
069:
070: protected void shiftGap(int newGapStart) {
071: int delta = newGapStart - gapStart;
072: if (delta > 0)
073: base.shift(gapEnd, gapStart, delta);
074: else if (delta < 0)
075: base.shift(newGapStart, gapEnd + delta, -delta);
076: gapEnd += delta;
077: gapStart = newGapStart;
078: }
079:
080: /** Make sure gap is at least 'size' elements long. */
081: protected void gapReserve(int size) {
082: if (size > gapEnd - gapStart) {
083: int oldLength = base.size;
084: int newLength = oldLength < 16 ? 16 : 2 * oldLength;
085: int minLength = oldLength - (gapEnd - gapStart) + size;
086: if (newLength < minLength)
087: newLength = minLength;
088: // FIXME this does unneeded copying.
089: // It may also leave unwanted junk in the gap (gap for gc).
090: base.setSize(newLength);
091: int newGapEnd = newLength - oldLength + gapEnd;
092: base.shift(gapEnd, newGapEnd, oldLength - gapEnd);
093: gapEnd = newGapEnd;
094: }
095: }
096:
097: /** Adjust gap to 'where', and make sure it is least `size' elements long. */
098: protected void gapReserve(int where, int size) {
099: gapReserve(size);
100: if (where != gapStart)
101: shiftGap(where);
102: }
103:
104: /** If needed, move the gap so the given segment is contiguous.
105: * @return the offset in the base array containing the segment,
106: * or -1 if the parameters are bad.
107: */
108:
109: public int getSegment(int where, int len) {
110: int length = size();
111: if (where < 0 || where > length)
112: return -1;
113: if (len < 0)
114: len = 0;
115: else if (where + len > length)
116: len = length - where;
117: // if (len < 0 || where + len > length)
118: // return -1;
119: if (where + len <= gapStart)
120: return where;
121: if (where >= gapStart)
122: return where + (gapEnd - gapStart);
123: // Shift the gap depending in which direction needs least copying.
124: if (gapStart - where > (len >> 1)) {
125: shiftGap(where + len);
126: return where;
127: } else {
128: shiftGap(where);
129: return where + (gapEnd - gapStart);
130: }
131: }
132:
133: protected int addPos(int ipos, Object value) {
134: int index = ipos >>> 1;
135: if (index >= gapStart)
136: index += gapEnd - gapStart;
137: add(index, value);
138: return ((index + 1) << 1) | 1;
139: }
140:
141: public void add(int index, Object o) {
142: gapReserve(index, 1);
143: base.set(index, o);
144: gapStart++;
145: }
146:
147: protected void removePosRange(int ipos0, int ipos1) {
148: ipos0 >>>= 1;
149: ipos1 >>>= 1;
150: if (ipos0 > gapEnd)
151: shiftGap(ipos0 - gapEnd + gapStart);
152: else if (ipos1 < gapStart)
153: shiftGap(ipos1);
154: if (ipos0 < gapStart) {
155: base.clearBuffer(ipos0, gapStart - ipos0);
156: gapStart = ipos0;
157: }
158: if (ipos1 > gapEnd) {
159: base.clearBuffer(gapEnd, ipos1 - gapEnd);
160: gapEnd = ipos1;
161: }
162: }
163:
164: /* FIXME - ths is quite wrong!
165: public Object remove(int index)
166: {
167: if (index >= gapStart)
168: index += gapEnd - gapStart;
169: return base.remove(index);
170: }
171: */
172:
173: public int createPos(int index, boolean isAfter) {
174: if (index > gapStart)
175: index += gapEnd - gapStart;
176: // if (index == gapStart && isAfter) index = gapEnd; ??
177: return (index << 1) | (isAfter ? 1 : 0);
178: }
179:
180: protected boolean isAfterPos(int ipos) {
181: return (ipos & 1) != 0;
182: }
183:
184: protected int nextIndex(int ipos) {
185: int index = ipos == -1 ? base.size : ipos >>> 1;
186: if (index > gapStart)
187: index -= gapEnd - gapStart;
188: return index;
189: }
190:
191: public void consumePosRange(int iposStart, int iposEnd, Consumer out) {
192: if (out.ignoring())
193: return;
194: int i = iposStart >>> 1;
195: int end = iposEnd >>> 1;
196: if (i < gapStart) {
197: int lim = end > gapStart ? end : gapStart;
198: consumePosRange(iposStart, lim << 1, out);
199: }
200: if (end > gapEnd) {
201: i = i < gapEnd ? gapEnd : i;
202: consumePosRange(i << 1, iposEnd, out);
203: }
204: }
205:
206: }
|