Java > Open Source Codes > org > eclipse > emf > common > util > BasicEList


1 /**
2  * <copyright>
3  *
4  * Copyright (c) 2002-2004 IBM Corporation and others.
5  * All rights reserved. This program and the accompanying materials
6  * are made available under the terms of the Eclipse Public License v1.0
7  * which accompanies this distribution, and is available at
8  * http://www.eclipse.org/legal/epl-v10.html
9  *
10  * Contributors:
11  * IBM - Initial API and implementation
12  *
13  * </copyright>
14  *
15  * $Id: BasicEList.java,v 1.10 2005/06/12 13:24:00 emerks Exp $
16  */
17 package org.eclipse.emf.common.util;
18
19
20 import java.io.IOException ;
21 import java.io.ObjectInputStream ;
22 import java.io.ObjectOutputStream ;
23 import java.io.Serializable ;
24 import java.lang.reflect.Array ;
25 import java.util.AbstractList ;
26 import java.util.Collection ;
27 import java.util.ConcurrentModificationException ;
28 import java.util.Iterator ;
29 import java.util.List ;
30 import java.util.ListIterator ;
31 import java.util.NoSuchElementException ;
32
33
34 /**
35  * A highly extensible list implementation.
36  */
37 public class BasicEList extends AbstractList implements EList, Cloneable , Serializable
38 {
39   /**
40    * The size of the list.
41    */
42   protected int size;
43
44   /**
45    * The underlying data storage of the list.
46    */
47   protected transient Object data[];
48
49   /**
50    * Creates an empty instance with no initial capacity.
51    * The data storage will be null.
52    */
53   public BasicEList()
54   {
55   }
56
57   /**
58    * Creates an empty instance with the given capacity.
59    * @param initialCapacity the initial capacity of the list before it must grow.
60    * @exception IllegalArgumentException if the <code>initialCapacity</code> is negative.
61    */
62   public BasicEList(int initialCapacity)
63   {
64     if (initialCapacity < 0)
65     {
66       throw new IllegalArgumentException ("Illegal Capacity: " + initialCapacity);
67     }
68
69     data = newData(initialCapacity);
70   }
71
72   /**
73    * Creates an instance that is a copy of the collection.
74    * @param collection the initial contents of the list.
75    */
76   public BasicEList(Collection collection)
77   {
78     size = collection.size();
79
80     // Conditionally create the data.
81 //
82 if (size > 0)
83     {
84       // Allow for a bit-shift of growth.
85 //
86 data = newData(size + size / 8 + 1);
87       collection.toArray(data);
88     }
89   }
90
91   /**
92    * Creates an initialized instance that directly uses the given arguments.
93    * @param size the size of the list.
94    * @param data the underlying storage of the list.
95    */
96   protected BasicEList(int size, Object [] data)
97   {
98     this.size = size;
99     this.data = data;
100   }
101
102   /**
103    * Returns new allocated data storage.
104    * Clients may override this to create typed storage.
105    * The cost of type checking via a typed array is negligable.
106    * @return new data storage.
107    */
108   protected Object [] newData(int capacity)
109   {
110     return new Object [capacity];
111   }
112
113   /**
114    * Returns whether <code>equals</code> rather than <code>==</code> should be used to compare members.
115    * The default is to return <code>true</code> but clients can optimize performance by returning <code>false</code>.
116    * The performance difference is highly significant.
117    * @return whether <code>equals</code> rather than <code>==</code> should be used.
118    */
119   protected boolean useEquals()
120   {
121     return true;
122   }
123
124   /**
125    * Returns whether two objects are equal using the {@link #useEquals appropriate} comparison mechanism.
126    * @return whether two objects are equal.
127    */
128   protected boolean equalObjects(Object firstObject, Object secondObject)
129   {
130     return
131       useEquals() && firstObject != null ?
132         firstObject.equals(secondObject) :
133         firstObject == secondObject;
134   }
135
136   /**
137    * Returns whether <code>null</code> is a valid object for the list.
138    * The default is to return <code>true</code>, but clients can override this to exclude <code>null</code>.
139    * @return whether <code>null</code> is a valid object for the list.
140    */
141   protected boolean canContainNull()
142   {
143     return true;
144   }
145
146   /**
147    * Returns whether objects are constrained to appear at most once in the list.
148    * The default is to return <code>false</code>, but clients can override this to ensure uniqueness of contents.
149    * The performance impact is signifcant: operations such as <code>add</code> are O(n) as a result requiring uniqueness.
150    * @return whether objects are constrained to appear at most once in the list.
151    */
152   protected boolean isUnique()
153   {
154     return false;
155   }
156
157   /**
158    * Validates a new content object and returns the validated object.
159    * This implementation checks for null, if {@link #canContainNull necessary} and returns the argument object.
160    * Clients may throw additional types of runtime exceptions
161    * in order to handle constraint violations.
162    * @param index the position of the new content.
163    * @param object the new content.
164    * @return the validated content.
165    * @exception IllegalArgumentException if a constraint prevents the object from being added.
166    */
167   protected Object validate(int index, Object object)
168   {
169     if (!canContainNull() && object == null)
170     {
171       throw new IllegalArgumentException ("The 'no null' constraint is violated");
172     }
173
174     return object;
175   }
176
177   /**
178    * Assigns the object into the data storage at the given index and returns the object that's been stored.
179    * Clients can monitor access to the storage via this method.
180    * @param index the position of the new content.
181    * @param object the new content.
182    * @return the object that's been stored.
183    *
184    */
185   protected Object assign(int index, Object object)
186   {
187     return data[index] = object;
188   }
189
190   /**
191    * Resolves the object at the index and returns the result.
192    * This implementation simply returns the <code>object</code>;
193    * clients can use this to transform objects as they are fetched.
194    * @param index the position of the content.
195    * @param object the content.
196    * @return the resolved object.
197    */
198   protected Object resolve(int index, Object object)
199   {
200     return object;
201   }
202
203   /**
204    * Called to indicate that the data storage has been set.
205    * This implementation does nothing;
206    * clients can use this to monitor settings to the data storage.
207    * @param index the position that was set.
208    * @param newObject the new object at the position.
209    * @param oldObject the old object at the position.
210    */
211   protected void didSet(int index, Object newObject, Object oldObject)
212   {
213   }
214
215   /**
216    * Called to indicate that an object has been added to the data storage.
217    * This implementation does nothing;
218    * clients can use this to monitor additions to the data storage.
219    * @param index the position object the new object.
220    * @param newObject the new object at the position.
221    */
222   protected void didAdd(int index, Object newObject)
223   {
224   }
225
226   /**
227    * Called to indicate that an object has been removed from the data storage.
228    * This implementation does nothing;
229    * clients can use this to monitor removals from the data storage.
230    * @param index the position of the old object.
231    * @param oldObject the old object at the position.
232    */
233   protected void didRemove(int index, Object oldObject)
234   {
235   }
236
237   /**
238    * Called to indicate that the data storage has been cleared.
239    * This implementation calls {@link #didRemove didRemove} for each object;
240    * clients can use this to monitor clearing of the data storage.
241    * @param size the original size of the list.
242    * @param oldObjects the old data storage being discarded.
243    * @see #didRemove
244    */
245   protected void didClear(int size, Object [] oldObjects)
246   {
247     if (oldObjects != null)
248     {
249       for (int i = 0; i < size; ++i)
250       {
251         didRemove(i, oldObjects[i]);
252       }
253     }
254   }
255
256   /**
257    * Called to indicate that an object has been moved in the data storage.
258    * This implementation does nothing;
259    * clients can use this to monitor movement in the data storage.
260    * @param index the position of the moved object.
261    * @param movedObject the moved object at the position.
262    * @param oldIndex the position the object was at before the move.
263    */
264   protected void didMove(int index, Object movedObject, int oldIndex)
265   {
266   }
267
268   /**
269    * Called to indicate that the data storage has been changed.
270    * This implementation does nothing;
271    * clients can use this to monitor change in the data storage.
272    */
273   protected void didChange()
274   {
275   }
276
277   /**
278    * Returns the number of objects in the list.
279    * @return the number of objects in the list.
280    */
281   public int size()
282   {
283     return size;
284   }
285
286   /**
287    * Returns whether the list has zero size.
288    * @return whether the list has zero size.
289    */
290   public boolean isEmpty()
291   {
292     return size == 0;
293   }
294
295   /**
296    * Returns whether the list contains the object.
297    * This implementation uses either <code>equals</code> or <code>"=="</code> depending on {@link #useEquals useEquals}.
298    * @param object the object in question.
299    * @return whether the list contains the object.
300    * @see #useEquals
301    */
302   public boolean contains(Object object)
303   {
304     if (useEquals() && object != null)
305     {
306       for (int i = 0; i < size; ++i)
307       {
308         if (object.equals(data[i]))
309         {
310           return true;
311         }
312       }
313     }
314     else
315     {
316       for (int i = 0; i < size; ++i)
317       {
318         if (data[i] == object)
319         {
320           return true;
321         }
322       }
323     }
324
325     return false;
326   }
327
328   /**
329    * Returns whether the list contains each object in the collection.
330    * This implementation delegates to {@link #contains contains},
331    * which may use either <code>equals</code> or <code>"=="</code> depending on {@link #useEquals useEquals}.
332    * @param collection the collection of objects in question.
333    * @return whether the list contains each object in the collection.
334    * @see #contains
335    * @see #useEquals
336    */
337   public boolean containsAll(Collection collection)
338   {
339     for (Iterator i = collection.iterator(); i.hasNext(); )
340     {
341       if (!contains(i.next()))
342       {
343         return false;
344       }
345     }
346
347     return true;
348   }
349
350   /**
351    * Returns the position of the first occurrence of the object in the list.
352    * This implementation uses either <code>equals</code> or <code>"=="</code> depending on {@link #useEquals useEquals}.
353    * @param object the object in question.
354    * @return the position of the first occurrence of the object in the list.
355    */
356   public int indexOf(Object object)
357   {
358     if (useEquals() && object != null)
359     {
360       for (int i = 0; i < size; ++i)
361       {
362         if (object.equals(data[i]))
363         {
364           return i;
365         }
366       }
367     }
368     else
369     {
370       for (int i = 0; i < size; ++i)
371       {
372         if (data[i] == object)
373         {
374           return i;
375         }
376       }
377     }
378     return -1;
379   }
380
381   /**
382    * Returns the position of the last occurrence of the object in the list.
383    * This implementation uses either <code>equals</code> or <code>"=="</code> depending on {@link #useEquals useEquals}.
384    * @param object the object in question.
385    * @return the position of the last occurrence of the object in the list.
386    */
387   public int lastIndexOf(Object object)
388   {
389     if (useEquals() && object != null)
390     {
391       for (int i = size - 1; i >= 0; --i)
392       {
393         if (object.equals(data[i]))
394         {
395           return i;
396         }
397       }
398     }
399     else
400     {
401       for (int i = size - 1; i >= 0; --i)
402       {
403         if (data[i] == object)
404         {
405           return i;
406         }
407       }
408     }
409     return -1;
410   }
411
412   /**
413    * Returns an array containing all the objects in sequence.
414    * Clients may override {@link #newData newData} to create typed storage in this case.
415    * @return an array containing all the objects in sequence.
416    * @see #newData
417    */
418   public Object [] toArray()
419   {
420     Object [] result = newData(size);
421
422     // Guard for no data.
423 //
424 if (size > 0)
425     {
426       System.arraycopy(data, 0, result, 0, size);
427     }
428     return result;
429   }
430
431   /**
432    * Returns an array containing all the objects in sequence.
433    * @param array the array that will be filled and returned, if it's big enough;
434    * otherwise, a suitably large array of the same type will be allocated and used instead.
435    * @return an array containing all the objects in sequence.
436    * @see #newData
437    */
438   public Object [] toArray(Object array[])
439   {
440     // Guard for no data.
441 //
442 if (size > 0)
443     {
444       if (array.length < size)
445       {
446         array = (Object [])Array.newInstance(array.getClass().getComponentType(), size);
447       }
448   
449       System.arraycopy(data, 0, array, 0, size);
450     }
451
452     if (array.length > size)
453     {
454       array[size] = null;
455     }
456
457     return array;
458   }
459
460   /**
461    * Returns direct <b>unsafe</b> access to the underlying data storage.
462    * Clients may <b>not</b> modify this
463    * and may <b>not</b> assume that the array remains valid as the list is modified.
464    * @return direct <b>unsafe</b> access to the underlying data storage.
465    */
466   public Object [] data()
467   {
468     return data;
469   }
470
471   /**
472    * Updates directly and <b>unsafely</b> the underlying data storage.
473    * Clients <b>must</b> be aware that this subverts all callbacks
474    * and hence possibly the integrity of the list.
475    */
476   public void setData(int size, Object [] data)
477   {
478     this.size = size;
479     this.data = data;
480     ++modCount;
481   }
482
483   /**
484    * An IndexOutOfBoundsException that constructs a message from the argument data.
485    * Having this avoids having the byte code that computes the message repeated/inlined at the creation site.
486    */
487   protected static class BasicIndexOutOfBoundsException extends IndexOutOfBoundsException
488   {
489     /**
490      * Constructs an instance with a message based on the arguments.
491      */
492     public BasicIndexOutOfBoundsException(int index, int size)
493     {
494       super("index=" + index + ", size=" + size);
495     }
496   }
497   
498   /**
499    * Returns the object at the index.
500    * This implementation delegates to {@link #resolve resolve}
501    * so that clients may transform the fetched object.
502    * @param index the position in question.
503    * @return the object at the index.
504    * @exception IndexOutOfBoundsException if the index isn't within the size range.
505    * @see #resolve
506    * @see #basicGet
507    */
508   public Object get(int index)
509   {
510     if (index >= size)
511       throw new BasicIndexOutOfBoundsException(index, size);
512
513     return resolve(index, data[index]);
514   }
515
516   /**
517    * Returns the object at the index without {@link #resolve resolving} it.
518    * @param index the position in question.
519    * @return the object at the index.
520    * @exception IndexOutOfBoundsException if the index isn't within the size range.
521    * @see #resolve
522    * @see #get
523    */
524   public Object basicGet(int index)
525   {
526     if (index >= size)
527       throw new BasicIndexOutOfBoundsException(index, size);
528
529     return data[index];
530   }
531
532   /**
533    * Sets the object at the index
534    * and returns the old object at the index.
535    * This implementation delegates to {@link #setUnique setUnique}
536    * after range checking and after {@link #isUnique uniqueness} checking.
537    * @param index the position in question.
538    * @param object the object to set.
539    * @return the old object at the index.
540    * @exception IndexOutOfBoundsException if the index isn't within the size range.
541    * @exception IllegalArgumentException if there is a constraint violation, e.g., non-uniqueness.
542    * @see #setUnique
543    */
544   public Object set(int index, Object object)
545   {
546     if (index >= size)
547       throw new BasicIndexOutOfBoundsException(index, size);
548
549     if (isUnique())
550     {
551       int currentIndex = indexOf(object);
552       if (currentIndex >=0 && currentIndex != index)
553       {
554         throw new IllegalArgumentException ("The 'no duplicates' constraint is violated");
555       }
556     }
557
558     return setUnique(index, object);
559   }
560
561   /**
562    * Sets the object at the index
563    * and returns the old object at the index;
564    * it does no ranging checking or uniqueness checking.
565    * This implementation delegates to {@link #assign assign}, {@link #didSet didSet}, and {@link #didChange didChange}.
566    * @param index the position in question.
567    * @param object the object to set.
568    * @return the old object at the index.
569    * @see #set
570    */
571   public Object setUnique(int index, Object object)
572   {
573     Object oldObject = data[index];
574     assign(index, validate(index, object));
575     didSet(index, object, oldObject);
576     didChange();
577     return oldObject;
578   }
579
580   /**
581    * Adds the object at the end of the list
582    * and returns whether the object was added;
583    * if {@link #isUnique uniqueness} is required,
584    * duplicates will be ignored and <code>false</code> will be returned.
585    * This implementation delegates to {@link #addUnique(Object) addUnique(Object)}
586    * after uniqueness checking.
587    * @param object the object to be added.
588    * @return whether the object was added.
589    * @see #addUnique(Object)
590    */
591   public boolean add(Object object)
592   {
593     if (isUnique() && contains(object))
594     {
595       return false;
596     }
597     else
598     {
599       addUnique(object);
600       return true;
601     }
602   }
603
604   /**
605    * Adds the object at the end of the list;
606    * it does no uniqueness checking.
607    * This implementation delegates to {@link #assign assign}, {@link #didAdd didAdd}, and {@link #didChange didChange}.
608    * after uniqueness checking.
609    * @param object the object to be added.
610    * @see #add(Object)
611    */
612   public void addUnique(Object object)
613   {
614     // ++modCount
615 //
616 grow(size + 1);
617
618     assign(size, validate(size, object));
619     didAdd(size++, object);
620     didChange();
621   }
622
623   /**
624    * Adds the object at the given index in the list.
625    * If {@link #isUnique uniqueness} is required,
626    * duplicates will be ignored.
627    * This implementation delegates to {@link #addUnique(int, Object) addUnique(int, Object)}
628    * after uniqueness checking.
629    * @param object the object to be added.
630    * @exception IllegalArgumentException if {@link #isUnique uniqueness} is required,
631    * and the object is a duplicate.
632    * @see #addUnique(int, Object)
633    */
634   public void add(int index, Object object)
635   {
636     if (index > size)
637       throw new BasicIndexOutOfBoundsException(index, size);
638
639     if (isUnique() && contains(object))
640     {
641       throw new IllegalArgumentException ("The 'no duplicates' constraint is violated");
642     }
643
644     addUnique(index, object);
645   }
646
647   /**
648    * Adds the object at the given index in the list;
649    * it does no ranging checking or uniqueness checking.
650    * This implementation delegates to {@link #assign assign}, {@link #didAdd didAdd}, and {@link #didChange didChange}.
651    * @param object the object to be added.
652    * @see #add(int, Object)
653    */
654   public void addUnique(int index, Object object)
655   {
656     // ++modCount
657 //
658 grow(size + 1);
659
660     if (index != size)
661     {
662       System.arraycopy(data, index, data, index + 1, size - index);
663     }
664     assign(index, validate(index, object));
665     ++size;
666     didAdd(index, object);
667     didChange();
668   }
669
670   /**
671    * Adds each object of the collection to the end of the list.
672    * If {@link #isUnique uniqueness} is required,
673    * duplicates will be {@link #getNonDuplicates removed} from the collection,
674    * which could even result in an empty collection.
675    * This implementation delegates to {@link #addAllUnique(Collection) addAllUnique(Collection)}
676    * after uniqueness checking.
677    * @param collection the collection of objects to be added.
678    * @see #addAllUnique(Collection)
679    */
680   public boolean addAll(Collection collection)
681   {
682     if (isUnique())
683     {
684        collection = getNonDuplicates(collection);
685     }
686     return addAllUnique(collection);
687   }
688
689   /**
690    * Adds each object of the collection to the end of the list;
691    * it does no uniqueness checking.
692    * This implementation delegates to {@link #assign assign}, {@link #didAdd didAdd}, and {@link #didChange didChange}.
693    * @param collection the collection of objects to be added.
694    * @see #addAll(Collection)
695    */
696   public boolean addAllUnique(Collection collection)
697   {
698     int growth = collection.size();
699
700     // ++modCount
701 //
702 grow(size + growth);
703
704     Iterator objects = collection.iterator();
705     int oldSize = size;
706     size += growth;
707     for (int i = oldSize; i < size; ++i)
708     {
709       Object object = objects.next();
710       assign(i, validate(i, object));
711       didAdd(i, object);
712       didChange();
713     }
714
715     return growth != 0;
716   }
717
718   /**
719    * Adds each object of the collection at each successive index in the list
720    * and returns whether any objects were added.
721    * If {@link #isUnique uniqueness} is required,
722    * duplicates will be {@link #getNonDuplicates removed} from the collection,
723    * which could even result in an empty collection.
724    * This implementation delegates to {@link #addAllUnique(int, Collection) addAllUnique(int, Collection)}
725    * after uniqueness checking.
726    * @param index the index at which to add.
727    * @param collection the collection of objects to be added.
728    * @return whether any objects were added.
729    * @see #addAllUnique(int, Collection)
730    */
731   public boolean addAll(int index, Collection collection)
732   {
733     if (index > size)
734       throw new BasicIndexOutOfBoundsException(index, size);
735
736     if (isUnique())
737     {
738       collection = getNonDuplicates(collection);
739     }
740     return addAllUnique(index, collection);
741   }
742
743   /**
744    * Adds each object of the collection at each successive index in the list
745    * and returns whether any objects were added;
746    * it does no ranging checking or uniqueness checking.
747    * This implementation delegates to {@link #assign assign}, {@link #didAdd didAdd}, and {@link #didChange didChange}.
748    * @param index the index at which to add.
749    * @param collection the collection of objects to be added.
750    * @return whether any objects were added.
751    * @see #addAll(int, Collection)
752    */
753   public boolean addAllUnique(int index, Collection collection)
754   {
755     int growth = collection.size();
756
757     // ++modCount
758 //
759 grow(size + growth);
760
761     int shifted = size - index;
762     if (shifted > 0)
763     {
764       System.arraycopy(data, index, data, index + growth, shifted);
765     }
766
767     Iterator objects = collection.iterator();
768     size += growth;
769     for (int i = 0; i < growth; ++i)
770     {
771       Object object = objects.next();
772       assign(index, validate(index, object));
773       didAdd(index, object);
774       didChange();
775       ++index;
776     }
777
778     return growth != 0;
779   }
780
781   /**
782    * Removes the object from the list and returns whether the object was actually contained by the list.
783    * This implementation uses {@link #indexOf indexOf} to find the object
784    * and delegates to {@link #remove(int) remove(int)}
785    * in the case that it finds the object.
786    * @param object the object to be removed.
787    * @return whether the object was actually contained by the list.
788    */
789   public boolean remove(Object object)
790   {
791     int index = indexOf(object);
792     if (index >= 0)
793     {
794       remove(index);
795       return true;
796     }
797     else
798     {
799       return false;
800     }
801   }
802
803   /**
804    * Removes each object of the collection from the list and returns whether any object was actually contained by the list.
805    * @param collection the collection of objects to be removed.
806    * @return whether any object was actually contained by the list.
807    */
808   public boolean removeAll(Collection collection)
809   {
810     boolean modified = false;
811     for (int i = size; --i >= 0; )
812     {
813       if (collection.contains(data[i]))
814       {
815         remove(i);
816         modified = true;
817       }
818     }
819
820     return modified;
821   }
822
823   /**
824    * Removes the object at the index from the list and returns it.
825    * This implementation delegates to {@link #didRemove didRemove} and {@link #didChange didChange}.
826    * @param index the position of the object to remove.
827    * @return the removed object.
828    * @exception IndexOutOfBoundsException if the index isn't within the size range.
829    */
830   public Object remove(int index)
831   {
832     if (index >= size)
833       throw new BasicIndexOutOfBoundsException(index, size);
834
835     ++modCount;
836     Object oldObject = data[index];
837
838     int shifted = size - index - 1;
839     if (shifted > 0)
840     {
841       System.arraycopy(data, index+1, data, index, shifted);
842     }
843
844     // Don't hold onto a duplicate reference to the last object.
845 //
846 data[--size] = null;
847     didRemove(index, oldObject);
848     didChange();
849
850     return oldObject;
851   }
852
853   /**
854    * Removes from the list each object not contained by the collection
855    * and returns whether any object was actually removed.
856    * This delegates to {@link #remove(int) remove(int)}
857    * in the case that it finds an object that isn't retained.
858    * @param collection the collection of objects to be retained.
859    * @return whether any object was actually removed.
860    */
861   public boolean retainAll(Collection collection)
862   {
863     boolean modified = false;
864     for (int i = size; --i >= 0; )
865     {
866       if (!collection.contains(data[i]))
867       {
868         remove(i);
869         modified = true;
870       }
871     }
872     return modified;
873   }
874
875   /**
876    * Clears the list of all objects.
877    * This implementation discards the data storage without modifying it
878    * and delegates to {@link #didClear didClear} and {@link #didChange didChange}.
879    */
880   public void clear()
881   {
882     ++modCount;
883
884     Object [] oldData = data;
885     int oldSize = size;
886
887     // Give it all back to the garbage collector.
888 //
889 data = null;
890     size = 0;
891
892     didClear(oldSize, oldData);
893     didChange();
894   }
895
896   /**
897    * Moves the object to the index of the list.
898    * This implementation uses {@link #indexOf} of find the object
899    * and delegates to {@link #move(int, int) move(int, int)}.
900    * @param index the new position for the object in the list.
901    * @param object the object to be moved.
902    * @exception IndexOutOfBoundsException if the index isn't within the size range or the object isn't contained by the list.
903    */
904   public void move(int index, Object object)
905   {
906     move(index, indexOf(object));
907   }
908
909   /**
910    * Moves the object at the source index of the list to the target index of the list
911    * and returns the moved object.
912    * This implementation delegates to {@link #assign assign}, {@link #didMove didMove}, and {@link #didChange didChange}.
913    * @param targetIndex the new position for the object in the list.
914    * @param sourceIndex the old position of the object in the list.
915    * @return the moved object.
916    * @exception IndexOutOfBoundsException if either index isn't within the size range.
917    */
918   public Object move(int targetIndex, int sourceIndex)
919   {
920     ++modCount;
921     if (targetIndex >= size)
922       throw new IndexOutOfBoundsException ("targetIndex=" + targetIndex + ", size=" + size);
923
924     if (sourceIndex >= size)
925       throw new IndexOutOfBoundsException ("sourceIndex=" + sourceIndex + ", size=" + size);
926
927     Object object = data[sourceIndex];
928     if (targetIndex != sourceIndex)
929     {
930       if (targetIndex < sourceIndex)
931       {
932         System.arraycopy(data, targetIndex, data, targetIndex + 1, sourceIndex - targetIndex);
933       }
934       else
935       {
936         System.arraycopy(data, sourceIndex + 1, data, sourceIndex, targetIndex - sourceIndex);
937       }
938       assign(targetIndex, object);
939       didMove(targetIndex, object, sourceIndex);
940       didChange();
941     }
942     return object;
943   }
944
945   /**
946    * Shrinks the capacity of the list to the minimal requirements.
947    * @see #grow
948    */
949   public void shrink()
950   {
951     ++modCount;
952
953     // Conditionally create the data.
954 //
955 if (size == 0)
956     {
957       // Give it all back to the garbage collector.
958 //
959 data = null;
960     }
961     else if (size < data.length)
962     {
963       Object [] oldData = data;
964       data = newData(size);
965       System.arraycopy(oldData, 0, data, 0, size);
966     }
967   }
968
969   /**
970    * Grows the capacity of the list
971    * to ensure that no additional growth is needed until the size exceeds the specified minimun capacity.
972    * @see #shrink
973    */
974   public void grow(int minimumCapacity)
975   {
976     ++modCount;
977     int oldCapacity = data == null ? 0 : data.length;
978     if (minimumCapacity > oldCapacity)
979     {
980       Object oldData[] = data;
981
982       // This seems to be a pretty sweet formula that supports good growth.
983 // Adding an object to a list will create a list of capacity 4,
984 // which is just about the average list size.
985 //
986 int newCapacity = oldCapacity + oldCapacity / 2 + 4;
987       if (newCapacity < minimumCapacity)
988       {
989         newCapacity = minimumCapacity;
990       }
991       data = newData(newCapacity);
992       if (oldData != null)
993       {
994         System.arraycopy(oldData, 0, data, 0, size);
995       }
996     }
997   }
998
999   private synchronized void writeObject(ObjectOutputStream objectOutputStream) throws IOException
1000  {
1001    objectOutputStream.defaultWriteObject();
1002    if (data == null)
1003    {
1004      objectOutputStream.writeInt(0);
1005    }
1006    else
1007    {
1008      objectOutputStream.writeInt(data.length);
1009      for (int i = 0; i < size; ++i)
1010      {
1011        objectOutputStream.writeObject(data[i]);
1012      }
1013    }
1014  }
1015
1016  private synchronized void readObject(ObjectInputStream objectInputStream) throws IOException , ClassNotFoundException
1017  {
1018    objectInputStream.defaultReadObject();
1019    int arrayLength = objectInputStream.readInt();
1020    if (arrayLength > 0)
1021    {
1022      try
1023      {
1024        data = newData(arrayLength);
1025      }
1026      catch (Throwable exception)
1027      {
1028        data = new Object [arrayLength];
1029      }
1030
1031      for (int i = 0; i < size; ++i)
1032      {
1033        didAdd(i, assign(i, objectInputStream.readObject()));
1034      }
1035    }
1036  }
1037
1038  /**
1039   * Returns a shallow copy of this list.
1040   * @return a shallow copy of this list.
1041   */
1042  public Object clone()
1043  {
1044    try
1045    {
1046      BasicEList clone = (BasicEList)super.clone();
1047      if (size > 0)
1048      {
1049        clone.size = size;
1050        clone.data = newData(size);
1051        System.arraycopy(data, 0, clone.data, 0, size);
1052      }
1053      return clone;
1054    }
1055    catch (CloneNotSupportedException exception)
1056    {
1057      throw new InternalError ();
1058    }
1059  }
1060
1061  /**
1062   * Returns whether the object is a list with corresponding equal objects.
1063   * This implementation uses either <code>equals</code> or <code>"=="</code> depending on {@link #useEquals useEquals}.
1064   * @return whether the object is a list with corresponding equal objects.
1065   * @see #useEquals
1066   */
1067  public boolean equals(Object object)
1068  {
1069    if (object == this)
1070    {
1071      return true;
1072    }
1073
1074    if (!(object instanceof List ))
1075    {
1076      return false;
1077    }
1078
1079    List list = (List )object;
1080    if (list