001: // -*-Java-*-
002: // Copyright (c) 2001 Per M.A. Bothner and Brainfood Inc.
003: // This is free software; for terms and warranty disclaimer see ./COPYING.
004:
005: package gnu.lists;
006:
007: import java.util.*;
008:
009: /** A SimpleVector implement as a simple array plus a current size.
010: *
011: * Methods with the word "Buffer" are methods which use the underlying
012: * array, ignoring the 'size' field.
013: *
014: * Can be used to implement CommonLisp simple vectors, but all simple
015: * vectors are also adjustable (by re-allocating the buffer)
016: * and have a fill pointer (the size field). */
017:
018: public abstract class SimpleVector extends AbstractSequence implements
019: Sequence {
020: /** The (current) number of elements.
021: * Must always have size() >= 0 && size() <= getBufferLength(). */
022: public int size;
023:
024: public final int size() {
025: return size;
026: }
027:
028: /**
029: * Set the size to a specified value.
030: * The data buffer is grown if needed, with new elements set to zero/null. If
031: * size is less than the current value, removed values are set to zero/null..
032: * (This is because if you decrease and then increase the vector the
033: * should be zero/null, and it is cleaner and better for gc to do the
034: * zeroing/nulling on remove rather than add.)
035: * If you need to change the size without setting removed elements to
036: * zero/null (e.g. to change Common Lisp's fill pointer) set size directly.
037: */
038: public void setSize(int size) {
039: int oldSize = this .size;
040: this .size = size;
041: if (size < oldSize)
042: clearBuffer(size, oldSize - size);
043: else {
044: int oldLength = getBufferLength();
045: if (size > oldLength) {
046: int newLength = oldLength < 16 ? 16 : 2 * oldLength;
047: setBufferLength(size > newLength ? size : newLength);
048: }
049: }
050: }
051:
052: /** Get the allocated length of the data buffer. */
053: public abstract int getBufferLength();
054:
055: public abstract void setBufferLength(int length);
056:
057: protected boolean isAfter(int ipos, Object xpos) {
058: return (ipos & 1) != 0;
059: }
060:
061: protected int nextIndex(int ipos, Object xpos) {
062: return ipos >>> 1;
063: }
064:
065: public void makePosition(int index, boolean isAfter,
066: PositionContainer posSet, int posNumber) {
067: posSet.setPosition(posNumber, (index << 1) | (isAfter ? 1 : 0),
068: null);
069: posSet.setSequence(posNumber, this );
070: }
071:
072: /*
073: protected void ensureSize(int space)
074: {
075: int oldLength = data.length;
076: int newLength = size +
077: if (size > space)
078: setBufferLength(space < 16 ? 16 : 2 * space);
079: this.size = size;
080: }
081: */
082:
083: protected abstract Object getBuffer();
084:
085: public Object get(int index) {
086: if (index >= size)
087: throw new IndexOutOfBoundsException();
088: return getBuffer(index);
089: }
090:
091: protected Object getNext(int ipos, Object xpos) {
092: int index = ipos >>> 1;
093: return index >= size ? eofValue : getBuffer(index);
094: }
095:
096: public int intAtBuffer(int index) {
097: return Convert.toInt(getBuffer(index));
098: }
099:
100: public int intAt(int index) {
101: if (index >= size)
102: throw new IndexOutOfBoundsException();
103: return intAtBuffer(index);
104: }
105:
106: public long longAt(int index) {
107: if (index >= size)
108: throw new IndexOutOfBoundsException();
109: return longAtBuffer(index);
110: }
111:
112: public long longAtBuffer(int index) {
113: return Convert.toLong(getBuffer(index));
114: }
115:
116: protected abstract Object getBuffer(int index);
117:
118: public Object set(int index, Object value) {
119: if (index >= size)
120: throw new IndexOutOfBoundsException();
121: Object old = getBuffer(index);
122: setBuffer(index, value);
123: return old;
124: }
125:
126: protected abstract Object setBuffer(int index, Object value);
127:
128: public void fill(Object value) {
129: for (int i = size; --i >= 0;)
130: setBuffer(i, value);
131: }
132:
133: public void fill(int fromIndex, int toIndex, Object value) {
134: if (fromIndex < 0 || toIndex > size)
135: throw new IndexOutOfBoundsException();
136: for (int i = fromIndex; i < toIndex; i++)
137: setBuffer(i, value);
138: }
139:
140: public void shift(int srcStart, int dstStart, int count) {
141: Object data = getBuffer();
142: System.arraycopy(data, srcStart, data, dstStart, count);
143: }
144:
145: public boolean add(Object o) {
146: add(size, o);
147: return true;
148: }
149:
150: protected void add(PositionContainer posSet, int posNumber,
151: Object value) {
152: int ipos = posSet.getPositionInt(posNumber);
153: add(ipos >>> 1, value);
154: posSet.setPosition(posNumber, ipos + 2, null);
155: }
156:
157: public void add(int index, Object o) {
158: int newSize = size + 1;
159: size = newSize;
160: int length = getBufferLength();
161: if (newSize > length)
162: setBufferLength(length < 16 ? 16 : 2 * length);
163: this .size = newSize;
164: if (size != index)
165: shift(index, index + 1, size - index);
166: set(index, o);
167: }
168:
169: public boolean addAll(int index, Collection c) {
170: boolean changed = false;
171: int count = c.size();
172: setSize(size + count);
173: shift(index, index + count, size - count - index);
174: for (Iterator it = c.iterator(); it.hasNext();) {
175: set(index++, it.next());
176: changed = true;
177: }
178: return changed;
179: }
180:
181: protected abstract void clearBuffer(int start, int count);
182:
183: protected void remove(int ipos0, Object xpos0, int ipos1,
184: Object xpos1) {
185: ipos0 = ipos0 >>> 1;
186: ipos1 = ipos1 >>> 1;
187: if (ipos0 < 0 || ipos0 > ipos1 || ipos1 >= size)
188: throw new IndexOutOfBoundsException();
189: shift(ipos1, ipos0, size - ipos1);
190: int count = ipos1 - ipos0;
191: size = size - count;
192: clearBuffer(size, count);
193: }
194:
195: protected void remove(int ipos, Object xpos, int count) {
196: int index = ipos >>> 1;
197: int ipos0, ipos1;
198: if (count >= 0) {
199: ipos0 = index;
200: ipos1 = index + count;
201: } else {
202: ipos0 = index + count;
203: ipos1 = index;
204: count = -count;
205: }
206: if (ipos0 < 0 || ipos1 >= size)
207: throw new IndexOutOfBoundsException();
208: shift(ipos1, ipos0, size - ipos1);
209: size = size - count;
210: clearBuffer(size, count);
211: }
212:
213: public Object remove(int index) {
214: if (index < 0 || index >= size)
215: throw new IndexOutOfBoundsException();
216: Object result = get(index);
217: shift(index + 1, index, 1);
218: size = size - 1;
219: clearBuffer(size, 1);
220: return result;
221: }
222:
223: public boolean remove(Object o) {
224: int index = indexOf(o);
225: if (index < 0)
226: return false;
227: Object result = get(index);
228: shift(index + 1, index, 1);
229: size = size - 1;
230: clearBuffer(size, 1);
231: return true;
232: }
233:
234: public boolean removeAll(Collection c) {
235: boolean changed = false;
236: int j = 0;
237: for (int i = 0; i < size; i++) {
238: Object value = get(i);
239: if (c.contains(value)) {
240: changed = true;
241: } else {
242: if (changed)
243: set(j, value);
244: j++;
245: }
246: }
247: setSize(j);
248: return changed;
249: }
250:
251: public boolean retainAll(Collection c) {
252: boolean changed = false;
253: int j = 0;
254: for (int i = 0; i < size; i++) {
255: Object value = get(i);
256: if (!c.contains(value)) {
257: changed = true;
258: } else {
259: if (changed)
260: set(j, value);
261: j++;
262: }
263: }
264: setSize(j);
265: return changed;
266: }
267:
268: public void clear() {
269: setSize(0);
270: }
271:
272: /** This is convenience hack for printing "uniform vectors" (srfi 4).
273: * It may go away without notice! */
274: public String getTag() {
275: return null;
276: }
277:
278: public void consume(int start, int length, Consumer out) {
279: consume(start << 1, null, (start + length) << 1, null, out);
280: }
281:
282: public boolean consumeNext(int ipos, Object xpos, Consumer out) {
283: int index = ipos >>> 1;
284: if (index >= size)
285: return false;
286: out.writeObject(getBuffer(index));
287: return true;
288: }
289:
290: protected void consume(int iposStart, Object xposStart,
291: int iposEnd, Object xposEnd, Consumer out) {
292: if (out.ignoring())
293: return;
294: int i = iposStart >>> 1;
295: int end = iposEnd >>> 1;
296: for (; i < end; i++)
297: out.writeObject(getBuffer(i));
298: }
299:
300: public int getNextKind(int ipos, Object xpos) {
301: return hasNext(ipos, xpos) ? getElementKind() : EOF_VALUE;
302: }
303:
304: public int getElementKind() {
305: return OBJECT_VALUE;
306: }
307: }
|