001: package org.python.core;
002:
003: import java.io.Serializable;
004: import java.lang.reflect.Array;
005: import java.util.Arrays;
006:
007: /**
008: * Abstract class that manages bulk structural and data operations
009: * on arrays, defering type-specific element-wise operations to the
010: * subclass. Subclasses supply the underlying array and the
011: * type-specific operations--greatly reducing the need for casting
012: * (thus achieving array-like performances with collection-like
013: * flexibility). Also includes
014: * functionality to support integration with the the jdk's
015: * collections (via methods that return a modification increment).<P>
016: * Subclasses will want to provide the following methods (which are
017: * not declared in this class since subclasses should specify the
018: * explicit return type):
019: * <UL>
020: * <LI><CODE><type> get(int)</CODE></LI>
021: * <LI><CODE>void set(int, <type>)</CODE></LI>
022: * <LI><CODE>void add(<type>)</CODE></LI>
023: * <LI><CODE>void add(int, <type>)</CODE></LI>
024: * <LI><CODE><type>[] toArray()</CODE></LI>
025: * </UL><P>
026: * Clone cannot be supported since the array is not held locally.
027: * But the @link #AbstractArray(AbstractArray) constructor can be used
028: * for suclasses that need to support clone.
029: * <P>
030: * This "type-specific collections" approach was originally developed
031: * by Dennis Sosnoski, who provides a more complete library at the
032: * referenced URL. Sosnoski's library does not integrate with the
033: * jdk collection classes but provides collection-like classes.
034: *
035: * @author Clark Updike
036: * @see <A href="http://www.sosnoski.com/opensrc/tclib/index.html">
037: * Sosnoski's Type-Specific Collection Library</A>
038: */
039: public abstract class AbstractArray implements Serializable {
040:
041: /**
042: * Size of the current array, which can be larger than the
043: * <CODE>size</CODE> field.
044: */
045: protected int capacity;
046:
047: /**
048: * The number of values currently present in the array.
049: */
050: protected int size;
051:
052: /**
053: * The modification count increment indicates if a structural change
054: * occured as a result of an operation that would make concurrent iteration
055: * over the array invalid. It is typically used by subclasses that
056: * extend <CODE>AbstractList</CODE>, by adding the value to
057: * <CODE>AbstractList.modCount</CODE> after performing a potentially
058: * structure-altering operation. A value of 0 indicates that
059: * it is still valid to iterate over the array. A value of 1
060: * indicates it is no longer valid to iterate over the range.<P>
061: * This class uses a somewhat stricter semantic for <CODE>modCount</CODE>.
062: * Namely, <CODE>modCountIncr</CODE> is only set to 1 if a structural
063: * change occurred. The jdk collections generally increment
064: * <CODE>modCount</CODE> if a potentially structure-altering method
065: * is called, regardless of whether or not a change actually occurred.
066: *
067: * <b>See also:</b> <code>java.util.AbstractList#modCount</code>
068: */
069: protected int modCountIncr;
070:
071: /**
072: * Since AbstractArray can support a clone method, this facilitates
073: * sublcasses that want to implement clone (poor man's cloning).
074: * Sublclasses can then do this:
075: * <PRE>
076: * public MyManagedArray(MyManagedArray toCopy) {
077: * super(this);
078: * this.baseArray = (<my array type>)toCopy.copyArray();
079: * this.someProp = toCopy.someProp;
080: * <etc>
081: * }
082: * <p/>
083: * public Object clone() {
084: * return new MyManagedArray(this);
085: * }
086: * </PRE>
087: *
088: * @param toCopy
089: */
090: public AbstractArray(AbstractArray toCopy) {
091: this .capacity = toCopy.capacity;
092: // let modCountIncr default to 0
093: this .size = toCopy.size;
094: }
095:
096: /**
097: * Use when the subclass has a preexisting array.
098: *
099: * @param size the initial size of the array
100: */
101: public AbstractArray(int size) {
102: this .size = size;
103: this .capacity = size;
104: }
105:
106: /**
107: * Creates the managed array with a default size of 10.
108: *
109: * @param type array element type (primitive type or object class)
110: */
111: public AbstractArray(Class type) {
112: this (type, 10);
113: }
114:
115: /**
116: * Construtor for multi-dimensional array types.
117: * For example, <CODE>char[][]</CODE>. This class only manages the
118: * top level dimension of the array. For single dimension
119: * arrays (the more typical usage), use the other constructors.<P>
120: *
121: * @param type Array element type (primitive type or object class).
122: * @param dimensions An int array specifying the dimensions. For
123: * a 2D array, something like <CODE>new int[] {10,0}</CODE> to
124: * create 10 elements each of which can hold an reference to an
125: * array of the same type.
126: * @see Array#newInstance(java.lang.Class, int[])
127: */
128: public AbstractArray(Class type, int[] dimensions) {
129: Object array = Array.newInstance(type, dimensions);
130: this .capacity = dimensions[0];
131: setArray(array);
132: }
133:
134: /**
135: * Creates the managed array with the specified size.
136: *
137: * @param type array element type (primitive type or object class)
138: * @param size number of elements initially allowed in array
139: */
140: public AbstractArray(Class type, int size) {
141: Object array = Array.newInstance(type, size);
142: this .capacity = Math.max(size, 10);
143: setArray(array);
144: }
145:
146: /**
147: * Appends the supplied array, which must be an array of the same
148: * type as <CODE>this</CODE>, to the end of <CODE>this</CODE>.
149: * <P><CODE>AbstractList</CODE> subclasses should update their
150: * <CODE>modCount</CODE> after calling this method.
151: *
152: * @param ofArrayType the array to append
153: */
154: public void appendArray(Object ofArrayType) {
155: replaceSubArray(ofArrayType, this .size);
156: }
157:
158: /**
159: * Set the array to the empty state, clearing all the data out and
160: * nulling objects (or "zero-ing" primitives).
161: * <P>Note: This method does not set <CODE>modCountIncr</CODE> to
162: * <CODE>1</CODE> even though <CODE>java.util.ArrayList</CODE>
163: * would.
164: * <p/>
165: * <P><CODE>AbstractList</CODE> subclasses should update their
166: * <CODE>modCount</CODE> after calling this method.
167: */
168: public void clear() {
169: this .modCountIncr = 0;
170: if (this .size != 0) {
171: this .modCountIncr = 1;
172: clearRange(0, this .size);
173: setSize(0);
174: }
175:
176: }
177:
178: /**
179: * Clears out the values in the specified range. For object arrays,
180: * the cleared range is nullified. For primitve arrays, it is
181: * "zero-ed" out.
182: * <P>Note: This method does not set <CODE>modCountIncr</CODE> to
183: * <CODE>1</CODE> even though <CODE>java.util.ArrayList</CODE>
184: * would.
185: *
186: * @param start the start index, inclusive
187: * @param stop the stop index, exclusive
188: */
189: protected void clearRange(int start, int stop) {
190:
191: if (start < stop && start >= 0 && stop <= this .size) {
192: clearRangeInternal(start, stop);
193: } else {
194: if (start == stop && start >= 0 && stop <= this .size) {
195: return;
196: }
197:
198: throw new ArrayIndexOutOfBoundsException(
199: "start and stop must follow: 0 <= start <= stop <= "
200: + (this .size) + ", but found start= "
201: + start + " and stop=" + stop);
202: }
203: }
204:
205: /**
206: * Used internally, no bounds checking.
207: *
208: * @param start the start index, inclusive
209: * @param stop the stop index, exclusive
210: */
211: private void clearRangeInternal(int start, int stop) {
212:
213: Object base = getArray();
214: Class arrayType = base.getClass().getComponentType();
215: if (arrayType.isPrimitive()) {
216: if (arrayType == Boolean.TYPE) {
217: Arrays.fill((boolean[]) base, start, stop, false);
218: } else if (arrayType == Character.TYPE) {
219: Arrays.fill((char[]) base, start, stop, '\u0000');
220: } else if (arrayType == Byte.TYPE) {
221: Arrays.fill((byte[]) base, start, stop, (byte) 0);
222: } else if (arrayType == Short.TYPE) {
223: Arrays.fill((short[]) base, start, stop, (short) 0);
224: } else if (arrayType == Integer.TYPE) {
225: Arrays.fill((int[]) base, start, stop, 0);
226: } else if (arrayType == Long.TYPE) {
227: Arrays.fill((long[]) base, start, stop, 0);
228: } else if (arrayType == Float.TYPE) {
229: Arrays.fill((float[]) base, start, stop, 0.f);
230: } else if (arrayType == Double.TYPE) {
231: Arrays.fill((double[]) base, start, stop, 0.);
232: }
233: } else {
234: Arrays.fill((Object[]) base, start, stop, null);
235: }
236:
237: }
238:
239: /**
240: * Constructs and returns a simple array containing the same data as held
241: * in this growable array.
242: *
243: * @return array containing a shallow copy of the data.
244: */
245: public Object copyArray() {
246: Object copy = Array.newInstance(getArray().getClass()
247: .getComponentType(), this .size);
248: System.arraycopy(getArray(), 0, copy, 0, this .size);
249: return copy;
250: }
251:
252: /**
253: * Ensures that the base array has at least the specified
254: * minimum capacity.
255: * <P><CODE>AbstractList</CODE> subclasses should update their
256: * <CODE>modCount</CODE> after calling this method.
257: *
258: * @param minCapacity new minimum size required
259: */
260: protected void ensureCapacity(int minCapacity) {
261: // ArrayList always increments the mod count, even if no
262: // structural change is made (not sure why).
263: // This only indicates a mod count change if a change is made.
264: this .modCountIncr = 0;
265: if (minCapacity > this .capacity) {
266: this .modCountIncr = 1;
267: int newCapacity = (this .capacity * 2) + 1;
268: newCapacity = (newCapacity < minCapacity) ? minCapacity
269: : newCapacity;
270: setNewBase(newCapacity);
271: this .capacity = newCapacity;
272: }
273: }
274:
275: /**
276: * Gets the next add position for appending a value to those in the array.
277: * If the underlying array is full, it is grown by the appropriate size
278: * increment so that the index value returned is always valid for the
279: * array in use by the time of the return.
280: * <P><CODE>AbstractList</CODE> subclasses should update their
281: * <CODE>modCount</CODE> after calling this method.
282: *
283: * @return index position for next added element
284: */
285: protected int getAddIndex() {
286: int index = this .size++;
287: if (this .size > this .capacity) {
288: ensureCapacity(this .size);
289: }
290: return index;
291: }
292:
293: /**
294: * Get the backing array. This method is used by the type-agnostic base
295: * class code to access the array used for type-specific storage by the
296: * child class.
297: *
298: * @return backing array object
299: */
300: protected abstract Object getArray();
301:
302: protected boolean isEmpty() {
303: return this .size == 0;
304: }
305:
306: /**
307: * Makes room to insert a value at a specified index in the array.
308: * <P><CODE>AbstractList</CODE> subclasses should update their
309: * <CODE>modCount</CODE> after calling this method. Does not change
310: * the <CODE>size</CODE> property of the array.
311: *
312: * @param index index position at which to insert element
313: */
314: protected void makeInsertSpace(int index) {
315: makeInsertSpace(index, 1);
316: }
317:
318: protected void makeInsertSpace(int index, int length) {
319:
320: this .modCountIncr = 0;
321: if (index >= 0 && index <= this .size) {
322: int toCopy = this .size - index;
323: this .size = this .size + length;
324: // First increase array size if needed
325: if (this .size > this .capacity) {
326: ensureCapacity(this .size);
327: }
328: if (index < this .size - 1) {
329: this .modCountIncr = 1;
330: Object array = getArray();
331: System.arraycopy(array, index, array, index + length,
332: toCopy);
333: }
334: } else {
335: throw new ArrayIndexOutOfBoundsException(
336: "Index must be between 0 and " + this .size
337: + ", but was " + index);
338: }
339: }
340:
341: /**
342: * Remove a value from the array. All values above the index removed
343: * are moved down one index position.
344: * <P><CODE>AbstractList</CODE> subclasses should always increment
345: * their <CODE>modCount</CODE> method after calling this, as
346: * <CODE>remove</CODE> always causes a structural modification.
347: *
348: * @param index index number of value to be removed
349: */
350: public void remove(int index) {
351: if (index >= 0 && index < this .size) {
352: this .size = this .size - 1;
353: if (index < this .size) {
354: Object base = getArray();
355: System.arraycopy(base, index + 1, base, index,
356: this .size - index);
357: clearRangeInternal(this .size, this .size);
358: }
359:
360: } else {
361: if (this .size == 0) {
362: throw new IllegalStateException(
363: "Cannot remove data from an empty array");
364: }
365: throw new IndexOutOfBoundsException(
366: "Index must be between 0 and " + (this .size - 1)
367: + ", but was " + index);
368:
369: }
370: }
371:
372: /**
373: * Removes a range from the array at the specified indices.
374: * @param start inclusive
375: * @param stop exclusive
376: */
377: public void remove(int start, int stop) {
378: if (start >= 0 && stop <= this .size && start <= stop) {
379: Object base = getArray();
380: int nRemove = stop - start;
381: if (nRemove == 0) {
382: return;
383: }
384: System.arraycopy(base, stop, base, start, this .size - stop);
385: this .size = this .size - nRemove;
386: clearRangeInternal(this .size, this .size + nRemove - 1);
387: setArray(base);
388: return;
389: }
390:
391: throw new IndexOutOfBoundsException(
392: "start and stop must follow: 0 <= start <= stop <= "
393: + (this .size - 1) + ", but found start= "
394: + start + " and stop=" + stop);
395: }
396:
397: /**
398: * Allows an array type to overwrite a segment of the array.
399: * Will expand the array if <code>(atIndex + 1) + ofArrayType</code>'s length
400: * is greater than the current length.
401: * <P><CODE>AbstractList</CODE> subclasses should update their
402: * <CODE>modCount</CODE> after calling this method.
403: *
404: * @param array
405: * @param atIndex
406: */
407: public void replaceSubArray(Object array, int atIndex) {
408: int arrayLen = Array.getLength(array);
409: replaceSubArray(atIndex, Math
410: .min(this .size, atIndex + arrayLen), array, 0, arrayLen);
411: }
412:
413: /**
414: * Replace a range of this array with another subarray.
415: * @param thisStart the start index (inclusive) of the subarray in this
416: * array to be replaced
417: * @param thisStop the stop index (exclusive) of the subarray in this
418: * array to be replaced
419: * @param srcArray the source array from which to copy
420: * @param srcStart the start index (inclusive) of the replacement subarray
421: * @param srcStop the stop index (exclusive) of the replacement subarray
422: */
423: public void replaceSubArray(int this Start, int this Stop,
424: Object srcArray, int srcStart, int srcStop) {
425:
426: this .modCountIncr = 0;
427: if (!srcArray.getClass().isArray()) {
428: throw new IllegalArgumentException(
429: "'array' must be an array type");
430: }
431:
432: int replacedLen = this Stop - this Start;
433: if (this Start < 0 || replacedLen < 0 || this Stop > this .size) {
434: String message = null;
435: if (this Start < 0) {
436: message = "thisStart < 0 (thisStart = " + this Start
437: + ")";
438: } else if (replacedLen < 0) {
439: message = "thisStart > thistStop (thisStart = "
440: + this Start + ", thisStop = " + this Stop + ")";
441: } else if (this Stop > this .size) {
442: message = "thisStop > size (thisStop = " + this Stop
443: + ", size = " + this .size + ")";
444: } else {
445: throw new InternalError("Incorrect validation logic");
446: }
447:
448: throw new ArrayIndexOutOfBoundsException(message);
449: }
450:
451: int srcLen = Array.getLength(srcArray);
452: int replacementLen = srcStop - srcStart;
453: if (srcStart < 0 || replacementLen < 0 || srcStop > srcLen) {
454: String message = null;
455: if (srcStart < 0) {
456: message = "srcStart < 0 (srcStart = " + srcStart + ")";
457: } else if (replacementLen < 0) {
458: message = "srcStart > srcStop (srcStart = " + srcStart
459: + ", srcStop = " + srcStop + ")";
460: } else if (srcStop > srcLen) {
461: message = "srcStop > srcArray length (srcStop = "
462: + srcStop + ", srcArray length = " + srcLen
463: + ")";
464: } else {
465: throw new InternalError("Incorrect validation logic");
466: }
467:
468: throw new IllegalArgumentException(
469: "start, stop and array must follow:\n\t"
470: + "0 <= start <= stop <= array length\nBut found\n\t"
471: + message);
472: }
473:
474: int lengthChange = replacementLen - replacedLen;
475:
476: // Adjust array size if needed.
477: if (lengthChange < 0) {
478: remove(this Stop + lengthChange, this Stop);
479: } else if (lengthChange > 0) {
480: makeInsertSpace(this Stop, lengthChange);
481: }
482:
483: try {
484: this .modCountIncr = 1;
485: System.arraycopy(srcArray, srcStart, getArray(), this Start,
486: replacementLen);
487: } catch (ArrayStoreException e) {
488: throw new IllegalArgumentException(
489: "'ofArrayType' must be compatible with existing array type of "
490: + getArray().getClass().getName()
491: + "\tsee java.lang.Class.getName().");
492: }
493: }
494:
495: /**
496: * Set the backing array. This method is used by the type-agnostic base
497: * class code to set the array used for type-specific storage by the
498: * child class.
499: *
500: * @param array the backing array object
501: */
502: protected abstract void setArray(Object array);
503:
504: /**
505: * Replaces the existing base array in the subclass with a new
506: * base array resized to the specified capacity.
507: *
508: * @param newCapacity
509: */
510: private void setNewBase(int newCapacity) {
511: this .modCountIncr = 1;
512: Object base = getArray();
513: Class baseType = base.getClass().getComponentType();
514: Object newBase = Array.newInstance(baseType, newCapacity);
515: System.arraycopy(base, 0, newBase, 0, this .capacity);
516: setArray(newBase);
517: }
518:
519: /**
520: * Sets the number of values currently present in the array. If the new
521: * size is greater than the current size, the added values are initialized
522: * to the default values. If the new size is less than the current size,
523: * all values dropped from the array are discarded.
524: * <P><CODE>AbstractList</CODE> subclasses should update their
525: * <CODE>modCount</CODE> after calling this method.
526: *
527: * @param count number of values to be set
528: */
529: public void setSize(int count) {
530: if (count > this .capacity) {
531: ensureCapacity(count);
532: } else if (count < this .size) {
533: clearRange(count, this .size);
534: }
535: this .size = count;
536: }
537:
538: /**
539: * Get the number of values currently present in the array.
540: *
541: * @return count of values present
542: */
543: public int getSize() {
544: return this .size;
545: }
546:
547: /**
548: * Provides a default comma-delimited representation of array.
549: *
550: * @see java.lang.Object#toString()
551: */
552: public String toString() {
553: StringBuffer buf = new StringBuffer();
554: buf.append("[");
555:
556: Object base = getArray();
557: Class arrayType = base.getClass().getComponentType();
558: int n = this .size - 1;
559: if (arrayType.isPrimitive()) {
560: for (int i = 0; i < n; i++) {
561: buf.append(Array.get(base, i)).append(", ");
562: }
563: if (n >= 0)
564: buf.append(Array.get(base, n));
565: } else {
566: Object[] objects = (Object[]) base;
567: for (int i = 0; i < n; i++) {
568: buf.append(objects[i]).append(", ");
569: }
570: if (n >= 0) {
571: buf.append(objects[n]);
572: }
573: }
574: buf.append("]");
575: return buf.toString();
576: }
577:
578: /**
579: * Removes any excess capacity in the backing array so it is
580: * just big enough to hold the amount of data actually in the array.
581: */
582: protected void trimToSize() {
583: // Don't need to adjust modCountIncr since AbstractList subclasses
584: // should only ever see up to the size (and not the capacity--which
585: // is encapsulated).
586: if (this .size < this .capacity) {
587: setNewBase(this .size);
588: }
589: }
590:
591: /**
592: * Returns the modification count increment, which is used by
593: * <CODE>AbstractList</CODE> subclasses to adjust <CODE>modCount</CODE>
594: * <CODE>AbstractList</CODE> uses it's <CODE>modCount</CODE> field
595: * to invalidate concurrent operations (like iteration) that should
596: * fail if the underlying array changes structurally during the
597: * operation.
598: *
599: * @return the modification count increment (0 if no change, 1 if changed)
600: */
601: public int getModCountIncr() {
602: return this.modCountIncr;
603: }
604: }
|