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: /* #ifdef JAVA2 */
007: import java.util.*;
008:
009: /* #endif */
010:
011: /** A SimpleVector implement as a simple array plus a current size.
012: *
013: * Methods with the word "Buffer" are methods which use the underlying
014: * array, ignoring the 'size' field.
015: *
016: * Can be used to implement CommonLisp simple vectors, but all simple
017: * vectors are also adjustable (by re-allocating the buffer)
018: * and have a fill pointer (the size field). */
019:
020: public abstract class SimpleVector extends AbstractSequence implements
021: Sequence, Array {
022: /** The (current) number of elements.
023: * Must always have size() >= 0 && size() <= getBufferLength(). */
024: public int size;
025:
026: public final int size() {
027: return size;
028: }
029:
030: /**
031: * Set the size to a specified value.
032: * The data buffer is grown if needed, with new elements set to zero/null. If
033: * size is less than the current value, removed values are set to zero/null..
034: * (This is because if you decrease and then increase the vector the
035: * should be zero/null, and it is cleaner and better for gc to do the
036: * zeroing/nulling on remove rather than add.)
037: * If you need to change the size without setting removed elements to
038: * zero/null (e.g. to change Common Lisp's fill pointer) set size directly.
039: */
040: public void setSize(int size) {
041: int oldSize = this .size;
042: this .size = size;
043: if (size < oldSize)
044: clearBuffer(size, oldSize - size);
045: else {
046: int oldLength = getBufferLength();
047: if (size > oldLength) {
048: int newLength = oldLength < 16 ? 16 : 2 * oldLength;
049: setBufferLength(size > newLength ? size : newLength);
050: }
051: }
052: }
053:
054: /** Get the allocated length of the data buffer. */
055: public abstract int getBufferLength();
056:
057: public abstract void setBufferLength(int length);
058:
059: protected boolean isAfterPos(int ipos) {
060: return (ipos & 1) != 0;
061: }
062:
063: protected int nextIndex(int ipos) {
064: return ipos == -1 ? size : ipos >>> 1;
065: }
066:
067: public int createPos(int index, boolean isAfter) {
068: return (index << 1) | (isAfter ? 1 : 0);
069: }
070:
071: public int nextPos(int ipos) {
072: if (ipos == -1)
073: return 0;
074: int index = ipos >>> 1;
075: if (index == size)
076: return 0;
077: return (index << 1) + 3;
078: }
079:
080: /*
081: protected void ensureSize(int space)
082: {
083: int oldLength = data.length;
084: int newLength = size +
085: if (size > space)
086: setBufferLength(space < 16 ? 16 : 2 * space);
087: this.size = size;
088: }
089: */
090:
091: protected abstract Object getBuffer();
092:
093: public Object get(int index) {
094: if (index >= size)
095: throw new IndexOutOfBoundsException();
096: return getBuffer(index);
097: }
098:
099: public Object getPosNext(int ipos) {
100: int index = ipos >>> 1;
101: return index >= size ? eofValue : getBuffer(index);
102: }
103:
104: public int intAtBuffer(int index) {
105: return Convert.toInt(getBuffer(index));
106: }
107:
108: public int intAt(int index) {
109: if (index >= size)
110: throw new IndexOutOfBoundsException();
111: return intAtBuffer(index);
112: }
113:
114: public long longAt(int index) {
115: if (index >= size)
116: throw new IndexOutOfBoundsException();
117: return longAtBuffer(index);
118: }
119:
120: public long longAtBuffer(int index) {
121: return Convert.toLong(getBuffer(index));
122: }
123:
124: public Object getRowMajor(int i) {
125: return get(i);
126: }
127:
128: protected abstract Object getBuffer(int index);
129:
130: public Object set(int index, Object value) {
131: if (index >= size)
132: throw new IndexOutOfBoundsException();
133: Object old = getBuffer(index);
134: setBuffer(index, value);
135: return old;
136: }
137:
138: protected abstract Object setBuffer(int index, Object value);
139:
140: public void fill(Object value) {
141: for (int i = size; --i >= 0;)
142: setBuffer(i, value);
143: }
144:
145: public void fillPosRange(int fromPos, int toPos, Object value) {
146: int i = fromPos == -1 ? size : fromPos >>> 1;
147: int j = toPos == -1 ? size : toPos >>> 1;
148: for (; i < j; i++)
149: setBuffer(i, value);
150: }
151:
152: public void fill(int fromIndex, int toIndex, Object value) {
153: if (fromIndex < 0 || toIndex > size)
154: throw new IndexOutOfBoundsException();
155: for (int i = fromIndex; i < toIndex; i++)
156: setBuffer(i, value);
157: }
158:
159: public void shift(int srcStart, int dstStart, int count) {
160: Object data = getBuffer();
161: System.arraycopy(data, srcStart, data, dstStart, count);
162: }
163:
164: public boolean add(Object o) {
165: add(size, o);
166: return true;
167: }
168:
169: protected int addPos(int ipos, Object value) {
170: int index = ipos >>> 1;
171: add(index, value);
172: // Increment index and set isAfter bit.
173: return (index << 1) + 3;
174: }
175:
176: public void add(int index, Object o) {
177: int newSize = size + 1;
178: size = newSize;
179: int length = getBufferLength();
180: if (newSize > length)
181: setBufferLength(length < 16 ? 16 : 2 * length);
182: this .size = newSize;
183: if (size != index)
184: shift(index, index + 1, size - index);
185: set(index, o);
186: }
187:
188: /* #ifdef JAVA2 */
189: public boolean addAll(int index, Collection c) {
190: boolean changed = false;
191: int count = c.size();
192: setSize(size + count);
193: shift(index, index + count, size - count - index);
194: for (Iterator it = c.iterator(); it.hasNext();) {
195: set(index++, it.next());
196: changed = true;
197: }
198: return changed;
199: }
200:
201: /* #endif */
202: /* #ifndef JAVA2 */
203: // public boolean addAll(int index, Sequence c)
204: // {
205: // boolean changed = false;
206: // int count = c.size();
207: // setSize(size + count);
208: // shift(index, index + count, size - count - index);
209: // for (java.util.Enumeration it = c.elements(); it.hasMoreElements(); )
210: // {
211: // set(index++, it.nextElement());
212: // changed = true;
213: // }
214: // return changed;
215: // }
216: /* #endif */
217:
218: protected abstract void clearBuffer(int start, int count);
219:
220: protected void removePosRange(int ipos0, int ipos1) {
221: ipos0 = ipos0 >>> 1;
222: ipos1 = ipos1 >>> 1;
223: if (ipos0 >= ipos1)
224: return;
225: if (ipos1 > size)
226: ipos1 = size;
227: shift(ipos1, ipos0, size - ipos1);
228: int count = ipos1 - ipos0;
229: size = size - count;
230: clearBuffer(size, count);
231: }
232:
233: public void removePos(int ipos, int count) {
234: int index = ipos >>> 1;
235: if (index > size)
236: index = size;
237: int ipos0, ipos1;
238: if (count >= 0) {
239: ipos0 = index;
240: ipos1 = index + count;
241: } else {
242: ipos0 = index + count;
243: ipos1 = index;
244: count = -count;
245: }
246: if (ipos0 < 0 || ipos1 >= size)
247: throw new IndexOutOfBoundsException();
248: shift(ipos1, ipos0, size - ipos1);
249: size = size - count;
250: clearBuffer(size, count);
251: }
252:
253: public Object remove(int index) {
254: if (index < 0 || index >= size)
255: throw new IndexOutOfBoundsException();
256: Object result = get(index);
257: shift(index + 1, index, 1);
258: size = size - 1;
259: clearBuffer(size, 1);
260: return result;
261: }
262:
263: public boolean remove(Object o) {
264: int index = indexOf(o);
265: if (index < 0)
266: return false;
267: shift(index + 1, index, 1);
268: size = size - 1;
269: clearBuffer(size, 1);
270: return true;
271: }
272:
273: /* #ifdef JAVA2 */
274: public boolean removeAll(Collection c) {
275: boolean changed = false;
276: int j = 0;
277: for (int i = 0; i < size; i++) {
278: Object value = get(i);
279: if (c.contains(value)) {
280: changed = true;
281: } else {
282: if (changed)
283: set(j, value);
284: j++;
285: }
286: }
287: setSize(j);
288: return changed;
289: }
290:
291: public boolean retainAll(Collection c) {
292: boolean changed = false;
293: int j = 0;
294: for (int i = 0; i < size; i++) {
295: Object value = get(i);
296: if (!c.contains(value)) {
297: changed = true;
298: } else {
299: if (changed)
300: set(j, value);
301: j++;
302: }
303: }
304: setSize(j);
305: return changed;
306: }
307:
308: /* #endif */
309:
310: public void clear() {
311: setSize(0);
312: }
313:
314: /** This is convenience hack for printing "uniform vectors" (srfi 4).
315: * It may go away without notice! */
316: public String getTag() {
317: return null;
318: }
319:
320: protected static int compareToInt(SimpleVector v1, SimpleVector v2) {
321: int n1 = v1.size;
322: int n2 = v2.size;
323: int n = n1 > n2 ? n2 : n1;
324: for (int i = 0; i < n; i++) {
325: int i1 = v1.intAtBuffer(i);
326: int i2 = v2.intAtBuffer(i);
327: if (11 != i2)
328: return i1 > i2 ? 1 : -1;
329: }
330: return n1 - n2;
331: }
332:
333: protected static int compareToLong(SimpleVector v1, SimpleVector v2) {
334: int n1 = v1.size;
335: int n2 = v2.size;
336: int n = n1 > n2 ? n2 : n1;
337: for (int i = 0; i < n; i++) {
338: long i1 = v1.longAtBuffer(i);
339: long i2 = v2.longAtBuffer(i);
340: if (i1 != i2)
341: return i1 > i2 ? 1 : -1;
342: }
343: return n1 - n2;
344: }
345:
346: public void consume(int start, int length, Consumer out) {
347: consumePosRange(start << 1, (start + length) << 1, out);
348: }
349:
350: public boolean consumeNext(int ipos, Consumer out) {
351: int index = ipos >>> 1;
352: if (index >= size)
353: return false;
354: out.writeObject(getBuffer(index));
355: return true;
356: }
357:
358: public void consumePosRange(int iposStart, int iposEnd, Consumer out) {
359: if (out.ignoring())
360: return;
361: int i = iposStart >>> 1;
362: int end = iposEnd >>> 1;
363: if (end > size)
364: end = size;
365: for (; i < end; i++)
366: out.writeObject(getBuffer(i));
367: }
368:
369: public int getNextKind(int ipos) {
370: return hasNext(ipos) ? getElementKind() : EOF_VALUE;
371: }
372:
373: public int getElementKind() {
374: return OBJECT_VALUE;
375: }
376:
377: public Array transpose(int[] lowBounds, int[] dimensions,
378: int offset0, int[] factors) {
379: GeneralArray array = new GeneralArray();
380: array.strides = factors;
381: array.dimensions = dimensions;
382: array.lowBounds = lowBounds;
383: array.offset = offset0;
384: array.base = this ;
385: array.simple = false;
386: return array;
387: }
388: }
|