AbstractArray


1   package org.python.core;
2   
3   import java.io.Serializable  ;
4   import java.lang.reflect.Array  ;
5   import java.util.Arrays  ;
6   
7   /**
8    * Abstract class that manages bulk structural and data operations
9    * on arrays, defering type-specific element-wise operations to the
10   * subclass.  Subclasses supply the underlying array and the
11   * type-specific operations--greatly reducing the need for casting
12   * (thus achieving array-like performances with collection-like
13   * flexibility).  Also includes
14   * functionality to support integration with the the jdk's
15   * collections (via methods that return a modification increment).<P>
16   * Subclasses will want to provide the following methods (which are
17   * not declared in this class since subclasses should specify the
18   * explicit return type):
19   * <UL>
20   * <LI><CODE>&lt;type&gt; get(int)</CODE></LI>
21   * <LI><CODE>void set(int, &lt;type&gt;)</CODE></LI>
22   * <LI><CODE>void add(&lt;type&gt;)</CODE></LI>
23   * <LI><CODE>void add(int, &lt;type&gt;)</CODE></LI>
24   * <LI><CODE>&lt;type&gt;[] toArray()</CODE></LI>
25   * </UL><P>
26   * Clone cannot be supported since the array is not held locally.
27   * But the @link #AbstractArray(AbstractArray) constructor can be used
28   * for suclasses that need to support clone.
29   * <P>
30   * This "type-specific collections" approach was originally developed
31   * by Dennis Sosnoski, who provides a more complete library at the
32   * referenced URL.  Sosnoski's library does not integrate with the
33   * jdk collection classes but provides collection-like classes.
34   *
35   * @author Clark Updike
36   * @see <A HREF="http://www.sosnoski.com/opensrc/tclib/index.html">
37   *      Sosnoski's Type-Specific Collection Library</A>
38   */
39  public abstract class AbstractArray implements Serializable  {
40  
41      /**
42       * Size of the current array, which can be larger than the
43       * <CODE>size</CODE> field.
44       */
45      protected int capacity;
46  
47      /**
48       * The number of values currently present in the array.
49       */
50      protected int size;
51  
52      /**
53       * The modification count increment indicates if a structural change
54       * occured as a result of an operation that would make concurrent iteration
55       * over the array invalid.  It is typically used by subclasses that
56       * extend <CODE>AbstractList</CODE>, by adding the value to
57       * <CODE>AbstractList.modCount</CODE> after performing a potentially
58       * structure-altering operation.  A value of 0 indicates that
59       * it is still valid to iterate over the array.  A value of 1
60       * indicates it is no longer valid to iterate over the range.<P>
61       * This class uses a somewhat stricter semantic for <CODE>modCount</CODE>.
62       * Namely, <CODE>modCountIncr</CODE> is only set to 1 if a structural
63       * change occurred.  The jdk collections generally increment
64       * <CODE>modCount</CODE> if a potentially structure-altering method
65       * is called, regardless of whether or not a change actually occurred.
66       *
67       * <b>See also:</b> <code>java.util.AbstractList#modCount</code>
68       */
69      protected int modCountIncr;
70  
71      /**
72       * Since AbstractArray can support a clone method, this facilitates
73       * sublcasses that want to implement clone (poor man's cloning).
74       * Sublclasses can then do this:
75       * <PRE>
76       * public MyManagedArray(MyManagedArray toCopy) {
77       * super(this);
78       * this.baseArray = (<my array type>)toCopy.copyArray();
79       * this.someProp = toCopy.someProp;
80       * <etc>
81       * }
82       * <p/>
83       * public Object clone() {
84       * return new MyManagedArray(this);
85       * }
86       * </PRE>
87       *
88       * @param toCopy
89       */
90      public AbstractArray(AbstractArray toCopy) {
91          capacity = toCopy.capacity;
92          // let modCountIncr default to 0
93          size = toCopy.size;
94      }
95  
96      /**
97       * Use when the subclass has a preexisting array.
98       *
99       * @param size the initial size of the array
100      */
101     public AbstractArray(int size) {
102         this.size = size;
103         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         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         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, 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         modCountIncr = 0;
170         if (size != 0) {
171             modCountIncr = 1;
172             clearRange(0, size);  
173             setSize(0);
174         }
175 
176     }
177 
178 
179     /**
180      * Clears out the values in the specified range.  For object arrays,
181      * the cleared range is nullified.  For primitve arrays, it is
182      * "zero-ed" out.
183      * <P>Note: This method does not set <CODE>modCountIncr</CODE> to
184      * <CODE>1</CODE> even though <CODE>java.util.ArrayList</CODE>
185      * would.
186      *
187      * @param start the start index, inclusive
188      * @param stop  the stop index, exclusive
189      */
190     protected void clearRange(int start, int stop) {
191 
192         if (start < stop && start >= 0 && stop <= size) {
193             clearRangeInternal(start, stop);
194         } else {
195             if (start == stop && start >= 0 && stop <= size) return;
196 
197             throw new ArrayIndexOutOfBoundsException  ("start and stop must follow: 0 <= start <= stop <= " +
198                     (size) + ", but found start= " + start + " and stop=" + stop);
199         }
200     }
201 
202     /**
203      * Used internally, no bounds checking.
204      *
205      * @param start the start index, inclusive
206      * @param stop  the stop index, exclusive
207      */
208     private void clearRangeInternal(int start, int stop) {
209 
210         Object   base = getArray();
211         Class   arrayType = base.getClass().getComponentType();
212         if (arrayType.isPrimitive()) {
213             if (arrayType == Boolean.TYPE) {
214                 Arrays.fill((boolean[]) base, start, stop, false);
215             } else if (arrayType == Character.TYPE) {
216                 Arrays.fill((char[]) base, start, stop, '\u0000');
217             } else if (arrayType == Byte.TYPE) {
218                 Arrays.fill((byte[]) base, start, stop, (byte) 0);
219             } else if (arrayType == Short.TYPE) {
220                 Arrays.fill((short[]) base, start, stop, (short) 0);
221             } else if (arrayType == Integer.TYPE) {
222                 Arrays.fill((int[]) base, start, stop, 0);
223             } else if (arrayType == Long.TYPE) {
224                 Arrays.fill((long[]) base, start, stop, 0);
225             } else if (arrayType == Float.TYPE) {
226                 Arrays.fill((float[]) base, start, stop, 0.f);
227             } else if (arrayType == Double.TYPE) {
228                 Arrays.fill((double[]) base, start, stop, 0.);
229             }
230         } else {
231             Arrays.fill((Object  []) base, start, stop, null);
232         }
233 
234     }
235 
236     /**
237      * Constructs and returns a simple array containing the same data as held
238      * in this growable array.
239      *
240      * @return array containing a shallow copy of the data.
241      */
242     public Object   copyArray() {
243         Object   copy = Array.newInstance(getArray().getClass().getComponentType(), size);
244         System.arraycopy(getArray(), 0, copy, 0, size);
245         return copy;
246     }
247 
248     /**
249      * Ensures that the base array has at least the specified
250      * minimum capacity.
251      * <P><CODE>AbstractList</CODE> subclasses should update their
252      * <CODE>modCount</CODE> after calling this method.
253      *
254      * @param minCapacity new minimum size required
255      */
256     protected void ensureCapacity(int minCapacity) {
257         // ArrayList always increments the mod count, even if no
258         // structural change is made (not sure why).
259         // This only indicates a mod count change if a change is made.
260         modCountIncr = 0;
261         if (minCapacity > capacity) {
262             modCountIncr = 1;
263             int newCapacity = (capacity * 2) + 1;
264             newCapacity = (newCapacity < minCapacity)
265                     ? minCapacity
266                     : newCapacity;
267             setNewBase(newCapacity);
268             capacity = newCapacity;
269         }
270     }
271 
272     /**
273      * Gets the next add position for appending a value to those in the array.
274      * If the underlying array is full, it is grown by the appropriate size
275      * increment so that the index value returned is always valid for the
276      * array in use by the time of the return.
277      * <P><CODE>AbstractList</CODE> subclasses should update their
278      * <CODE>modCount</CODE> after calling this method.
279      *
280      * @return index position for next added element
281      */
282     protected int getAddIndex() {
283         int index = size++;
284         if (size > capacity) {
285             ensureCapacity(size);
286         }
287         return index;
288     }
289 
290     /**
291      * Get the backing array. This method is used by the type-agnostic base
292      * class code to access the array used for type-specific storage by the
293      * child class.
294      *
295      * @return backing array object
296      */
297     protected abstract Object   getArray();
298 
299     protected boolean isEmpty() {
300         return size == 0;
301     }
302 
303     /**
304      * Makes room to insert a value at a specified index in the array.
305      * <P><CODE>AbstractList</CODE> subclasses should update their
306      * <CODE>modCount</CODE> after calling this method.  Does not change
307      * the <CODE>size</CODE> property of the array.
308      *
309      * @param index index position at which to insert element
310      */
311     protected void makeInsertSpace(int index) {
312         makeInsertSpace(index, 1);
313     }
314 
315     protected void makeInsertSpace(int index, int length) {
316 
317         modCountIncr = 0;
318         if (index >= 0 && index <= size) {
319             int toCopy = size - index;
320             size = size + length;
321             // First increase array size if needed
322             if (size > capacity) {
323                 ensureCapacity(size);
324             }
325             if (index < size - 1) {
326                 modCountIncr = 1;
327                 Object   array = getArray();
328                 System.arraycopy(array, index, array, index + length, toCopy);
329             }
330         } else {
331             throw new ArrayIndexOutOfBoundsException  ("Index must be between 0 and " +
332                     size + ", but was " + index);
333         }
334     }
335 
336     /**
337      * Remove a value from the array. All values above the index removed
338      * are moved down one index position.
339      * <P><CODE>AbstractList</CODE> subclasses should always increment
340      * their <CODE>modCount</CODE> method after calling this, as
341      * <CODE>remove</CODE> always causes a structural modification.
342      *
343      * @param index index number of value to be removed
344      */
345     public void remove(int index) {
346         if (index >= 0 && index < size) {
347             size = size - 1;
348             if (index < size) {
349                 Object   base = getArray();
350                 System.arraycopy(base, index + 1, base, index, size - index);
351                 clearRangeInternal(size, size);
352             }
353 
354         } else {
355             if (size == 0) {
356                 throw new IllegalStateException  ("Cannot remove data from an empty array");
357             }
358             throw new IndexOutOfBoundsException  ("Index must be between 0 and " +
359                     (size - 1) + ", but was " + index);
360 
361         }
362     }
363 
364     /**
365      * Removes a range from the array at the specified indices.
366      * @param start inclusive
367      * @param stop exclusive
368      */
369     public void remove(int start, int stop) {
370         if (start >= 0 && stop <= size && start <= stop) {
371             Object   base = getArray();
372             int nRemove = stop - start;
373             if (nRemove == 0) return;
374             System.arraycopy(base, stop, base, start, size - stop);
375             size = size - nRemove;
376             clearRangeInternal(size, size + nRemove - 1);
377             setArray(base);
378             return;
379         }
380 
381         throw new IndexOutOfBoundsException  ("start and stop must follow: 0 <= start <= stop <= " +
382                 (size - 1) + ", but found start= " + start + " and stop=" + stop);
383     }
384 
385     /**
386      * Allows an array type to overwrite a segment of the array.
387      * Will expand the array if <code>(atIndex + 1) + ofArrayType</code>'s length
388      * is greater than the current length.
389      * <P><CODE>AbstractList</CODE> subclasses should update their
390      * <CODE>modCount</CODE> after calling this method.
391      *
392      * @param array
393      * @param atIndex
394      */
395     public void replaceSubArray(Object   array, int atIndex) {
396         int arrayLen = Array.getLength(array);
397         replaceSubArray(atIndex, Math.min(size, atIndex + arrayLen), array, 0, arrayLen);
398     }
399     
400     /**
401      * Replace a range of this array with another subarray.
402      * @param thisStart the start index (inclusive) of the subarray in this 
403      * array to be replaced
404      * @param thisStop the stop index (exclusive) of the subarray in this 
405      * array to be replaced
406      * @param srcArray the source array from which to copy
407      * @param srcStart the start index (inclusive) of the replacement subarray
408      * @param srcStop the stop index (exclusive)  of the replacement subarray
409      */
410     public void replaceSubArray(int thisStart, int thisStop, Object   srcArray, 
411             int srcStart, int srcStop) {
412     
413         modCountIncr = 0;
414         if (!srcArray.getClass().isArray()) {
415             throw new IllegalArgumentException  ("'array' must be an array type");
416         }
417     
418         int replacedLen = thisStop - thisStart;
419          if (thisStart < 0 || replacedLen < 0 || thisStop > size) {
420             String   message = null;
421             if (thisStart < 0) {
422                 message = "thisStart < 0 (thisStart = " + thisStart + ")";
423             } else if (replacedLen < 0) {
424                 message = "thisStart > thistStop (thisStart = " + thisStart + 
425                                 ", thisStop = " + thisStop + ")";
426             } else if (thisStop > size) {
427                 message = "thisStop > size (thisStop = " + thisStop + 
428                                 ", size = " + size + ")";
429             } else {
430                 throw new InternalError  ("Incorrect validation logic");
431             }
432     
433             throw new ArrayIndexOutOfBoundsException  (message);
434         }
435     
436         int srcLen = Array.getLength(srcArray);
437         int replacementLen = srcStop - srcStart;
438         if (srcStart < 0 || replacementLen < 0 || srcStop > srcLen) {
439             String   message = null;
440             if (srcStart < 0) {
441                 message = "srcStart < 0 (srcStart = " + srcStart +")";
442             } else if (replacementLen < 0) {
443                 message = "srcStart > srcStop (srcStart = " + srcStart + 
444                                 ", srcStop = " + srcStop + ")";
445             } else if (srcStop > srcLen) {
446                 message = "srcStop > srcArray length (srcStop = " + srcStop + 
447                                 ", srcArray length = " +srcLen + ")";
448             } else {
449                 throw new InternalError  ("Incorrect validation logic");
450             }
451             
452             throw new IllegalArgumentException  ("start, stop and array must follow:\n\t"
453                     + "0 <= start <= stop <= array length\nBut found\n\t" +
454                     message);
455         }
456     
457         int lengthChange = replacementLen - replacedLen;
458         
459         // Adjust array size if needed.
460         if (lengthChange < 0) {
461             remove(thisStop + lengthChange, thisStop);
462         } else if (lengthChange > 0) {
463             makeInsertSpace(thisStop, lengthChange);
464         }
465     
466         try {
467             modCountIncr = 1;
468             System.arraycopy(srcArray, srcStart, getArray(), thisStart, replacementLen);
469         } catch (ArrayStoreException   e) {
470             throw new IllegalArgumentException  ("'ofArrayType' must be compatible with existing array type of " +
471                     getArray().getClass().getName() + "\tsee java.lang.Class.getName().");
472         }
473     }
474     
475     /**
476      * Set the backing array. This method is used by the type-agnostic base
477      * class code to set the array used for type-specific storage by the
478      * child class.
479      *
480      * @param array the backing array object
481      */
482     protected abstract void setArray(Object   array);
483 
484     /**
485      * Replaces the existing base array in the subclass with a new
486      * base array resized to the specified capacity.
487      *
488      * @param newCapacity
489      */
490     private void setNewBase(int newCapacity) {
491         modCountIncr = 1;
492         Object   base = getArray();
493         Class   baseType = base.getClass().getComponentType();
494         Object   newBase = Array.newInstance(baseType, newCapacity);
495         System.arraycopy(base, 0, newBase, 0, capacity);
496         setArray(newBase);
497     }
498 
499     /**
500      * Sets the number of values currently present in the array. If the new
501      * size is greater than the current size, the added values are initialized
502      * to the default values. If the new size is less than the current size,
503      * all values dropped from the array are discarded.
504      * <P><CODE>AbstractList</CODE> subclasses should update their
505      * <CODE>modCount</CODE> after calling this method.
506      *
507      * @param count number of values to be set
508      */
509     public void setSize(int count) {
510         if (count > capacity) {
511             ensureCapacity(count);
512         } else if (count < size) {
513             clearRange(count, size);  
514         }
515         size = count;
516     }
517 
518     /**
519      * Get the number of values currently present in the array.
520      *
521      * @return count of values present
522      */
523     public int getSize() {
524         return size;
525     }
526 
527     /**
528      * Provides a default comma-delimited representation of array.
529      *
530      * @see java.lang.Object#toString()
531      */
532     public String   toString() {
533         StringBuffer   buf = new StringBuffer  ();
534         buf.append("[");
535 
536         Object   base = getArray();
537         Class   arrayType = base.getClass().getComponentType();
538         int n = size - 1;
539         if (arrayType.isPrimitive()) {
540             for (int i = 0; i < n; i++) {
541                 buf.append(Array.get(base, i)).append(", ");
542             }
543             if (n >= 0) buf.append(Array.get(base, n));
544         } else {
545             Object  [] objects = (Object  []) base;
546             for (int i = 0; i < n; i++) {
547                 buf.append(objects[i]).append(", ");
548             }
549             if (n >= 0) buf.append(objects[n]);
550         }
551         buf.append("]");
552         return buf.toString();
553     }
554 
555 
556     /**
557      * Removes any excess capacity in the backing array so it is
558      * just big enough to hold the amount of data actually in the array.
559      */
560     protected void trimToSize() {
561         // Don't need to adjust modCountIncr since AbstractList subclasses
562         // should only ever see up to the size (and not the capacity--which
563         // is encapsulated).
564         if (size < capacity) {
565             setNewBase(size);
566         }
567     }
568 
569 
570     /**
571      * Returns the modification count increment, which is used by
572      * <CODE>AbstractList</CODE> subclasses to adjust <CODE>modCount</CODE>
573      * <CODE>AbstractList</CODE> uses it's <CODE>modCount</CODE> field
574      * to invalidate concurrent operations (like iteration) that should
575      * fail if the underlying array changes structurally during the
576      * operation.
577      *
578      * @return the modification count increment (0 if no change, 1 if changed)
579      */
580     public int getModCountIncr() {
581         return modCountIncr;
582     }
583 }
584
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags