Robust/src/ClassLibrary/SSJava/ArrayList.java

   1 /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
   2    implementation of the List interface
   3    Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39
  40 //package java.util;
  41
  42 /*import java.io.IOException;
  43 import java.io.ObjectInputStream;
  44 import java.io.ObjectOutputStream;
  45 import java.io.Serializable;
  46 import java.lang.reflect.Array;
  47 */
  48 /**
  49  * An array-backed implementation of the List interface.  This implements
  50  * all optional list operations, and permits null elements, so that it is
  51  * better than Vector, which it replaces. Random access is roughly constant
  52  * time, and iteration is roughly linear time, so it is nice and fast, with
  53  * less overhead than a LinkedList.
  54  * <p>
  55  *
  56  * Each list has a capacity, and as the array reaches that capacity it
  57  * is automatically transferred to a larger array. You also have access to
  58  * ensureCapacity and trimToSize to control the backing array's size, avoiding
  59  * reallocation or wasted memory.
  60  * <p>
  61  *
  62  * ArrayList is not synchronized, so if you need multi-threaded access,
  63  * consider using:<br>
  64  * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
  65  * <p>
  66  *
  67  * The iterators are <i>fail-fast</i>, meaning that any structural
  68  * modification, except for <code>remove()</code> called on the iterator
  69  * itself, cause the iterator to throw a
  70  * {@link ConcurrentModificationException} rather than exhibit
  71  * non-deterministic behavior.
  72  *
  73  * @author Jon A. Zeppieri
  74  * @author Bryce McKinlay
  75  * @author Eric Blake (ebb9@email.byu.edu)
  76  * @see Collection
  77  * @see List
  78  * @see LinkedList
  79  * @see Vector
  80  * @see Collections#synchronizedList(List)
  81  * @see AbstractList
  82  * @status updated to 1.4
  83  */
  84 //public class ArrayList<E> extends AbstractList<E>
  85 //  implements List<E>, RandomAccess, Cloneable, Serializable
  86 public class ArrayList
  87 {
  88   protected transient int modCount;
  89   /**
  90    * Compatible with JDK 1.2
  91    */
  92   private static final long serialVersionUID = 8683452581122892189L;
  93
  94   /**
  95    * The default capacity for new ArrayLists.
  96    */
  97   private static final int DEFAULT_CAPACITY = 10;
  98
  99   /**
 100    * The number of elements in this list.
 101    * @serial the list size
 102    */
 103   private int size;
 104
 105   /**
 106    * Where the data is stored.
 107    */
 108   //private transient E[] data;
 109   private transient Object[] data;
 110
 111   /**
 112    * Construct a new ArrayList with the supplied initial capacity.
 113    *
 114    * @param capacity initial capacity of this ArrayList
 115    * @throws IllegalArgumentException if capacity is negative
 116    */
 117   public ArrayList(int capacity)
 118   {
 119     // Must explicitly check, to get correct exception.
 120     if (capacity < 0)
 121       throw new Error("Illegal Argument Exception")/*IllegalArgumentException()*/;
 122     data = (Object/*E*/[]) new Object[capacity];
 123   }
 124
 125   /**
 126    * Construct a new ArrayList with the default capacity (16).
 127    */
 128   public ArrayList()
 129   {
 130     this(DEFAULT_CAPACITY);
 131   }
 132
 133   /**
 134    * Construct a new ArrayList, and initialize it with the elements
 135    * in the supplied Collection. The initial capacity is 110% of the
 136    * Collection's size.
 137    *
 138    * @param c the collection whose elements will initialize this list
 139    * @throws NullPointerException if c is null
 140    */
 141   /*public ArrayList(Collection<? extends E> c)
 142   {
 143     this((int) (c.size() * 1.1f));
 144     addAll(c);
 145   }*/
 146
 147   /**
 148    * Trims the capacity of this List to be equal to its size;
 149    * a memory saver.
 150    */
 151   public void trimToSize()
 152   {
 153     // Not a structural change from the perspective of iterators on this list,
 154     // so don't update modCount.
 155     if (size != data.length)
 156       {
 157         Object/*E*/[] newData = /*(ObjectE[])*/ new Object[size];
 158         System.arraycopy(data, 0, newData, 0, size);
 159         data = newData;
 160       }
 161   }
 162
 163   /**
 164    * Guarantees that this list will have at least enough capacity to
 165    * hold minCapacity elements. This implementation will grow the list to
 166    * max(current * 2, minCapacity) if (minCapacity &gt; current). The JCL says
 167    * explictly that "this method increases its capacity to minCap", while
 168    * the JDK 1.3 online docs specify that the list will grow to at least the
 169    * size specified.
 170    *
 171    * @param minCapacity the minimum guaranteed capacity
 172    */
 173   public void ensureCapacity(int minCapacity)
 174   {
 175     int current = data.length;
 176
 177     if (minCapacity > current)
 178       {
 179         Object/*E*/[] newData = /*(E[])*/ new Object[Math.max(current * 2, minCapacity)];
 180         System.arraycopy(data, 0, newData, 0, size);
 181         data = newData;
 182       }
 183   }
 184
 185   /**
 186    * Returns the number of elements in this list.
 187    *
 188    * @return the list size
 189    */
 190   public int size()
 191   {
 192     return size;
 193   }
 194
 195   /**
 196    * Checks if the list is empty.
 197    *
 198    * @return true if there are no elements
 199    */
 200   public boolean isEmpty()
 201   {
 202     return size == 0;
 203   }
 204
 205   /**
 206    * Returns true iff element is in this ArrayList.
 207    *
 208    * @param e the element whose inclusion in the List is being tested
 209    * @return true if the list contains e
 210    */
 211   public boolean contains(Object e)
 212   {
 213     return indexOf(e) != -1;
 214   }
 215
 216   /**
 217    * Returns the lowest index at which element appears in this List, or
 218    * -1 if it does not appear.
 219    *
 220    * @param e the element whose inclusion in the List is being tested
 221    * @return the index where e was found
 222    */
 223   public int indexOf(Object e)
 224   {
 225     for (int i = 0; i < size; i++)
 226       if (equals(e, data[i]))
 227         return i;
 228     return -1;
 229   }
 230
 231   /**
 232    * Returns the highest index at which element appears in this List, or
 233    * -1 if it does not appear.
 234    *
 235    * @param e the element whose inclusion in the List is being tested
 236    * @return the index where e was found
 237    */
 238   public int lastIndexOf(Object e)
 239   {
 240     for (int i = size - 1; i >= 0; i--)
 241       if (equals(e, data[i]))
 242         return i;
 243     return -1;
 244   }
 245
 246   boolean equals(Object o1, Object o2)
 247   {
 248     return o1 == null ? o2 == null : o1.equals(o2);
 249   }
 250
 251   /**
 252    * Creates a shallow copy of this ArrayList (elements are not cloned).
 253    *
 254    * @return the cloned object
 255    */
 256   /*public Object clone()
 257   {
 258     ArrayList<E> clone = null;
 259     try
 260       {
 261         clone = (ArrayList<E>) super.clone();
 262         //clone = new ArrayList();
 263         clone.data = (E[]) data.clone();
 264       }
 265     catch (CloneNotSupportedException e)
 266       {
 267         // Impossible to get here.
 268       }
 269     return clone;
 270   }*/
 271
 272   /**
 273    * Returns an Object array containing all of the elements in this ArrayList.
 274    * The array is independent of this list.
 275    *
 276    * @return an array representation of this list
 277    */
 278   public Object[] toArray()
 279   {
 280     Object/*E*/[] array = /*(E[])*/ new Object[size];
 281     System.arraycopy(data, 0, array, 0, size);
 282     return array;
 283   }
 284
 285   /**
 286    * Returns an Array whose component type is the runtime component type of
 287    * the passed-in Array.  The returned Array is populated with all of the
 288    * elements in this ArrayList.  If the passed-in Array is not large enough
 289    * to store all of the elements in this List, a new Array will be created
 290    * and returned; if the passed-in Array is <i>larger</i> than the size
 291    * of this List, then size() index will be set to null.
 292    *
 293    * @param a the passed-in Array
 294    * @return an array representation of this list
 295    * @throws ArrayStoreException if the runtime type of a does not allow
 296    *         an element in this list
 297    * @throws NullPointerException if a is null
 298    */
 299   /*public <T> T[] toArray(T[] a)
 300   {
 301     if (a.length < size)
 302       a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
 303     else if (a.length > size)
 304       a[size] = null;
 305     System.arraycopy(data, 0, a, 0, size);
 306     return a;
 307   }*/
 308
 309   /**
 310    * Retrieves the element at the user-supplied index.
 311    *
 312    * @param index the index of the element we are fetching
 313    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 314    */
 315   public Object/*E*/ get(int index)
 316   {
 317     checkBoundExclusive(index);
 318     return data[index];
 319   }
 320
 321   /**
 322    * Sets the element at the specified index.  The new element, e,
 323    * can be an object of any type or null.
 324    *
 325    * @param index the index at which the element is being set
 326    * @param e the element to be set
 327    * @return the element previously at the specified index
 328    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= 0
 329    */
 330   public Object/*E*/ set(int index, Object/*E*/ e)
 331   {
 332     checkBoundExclusive(index);
 333     Object/*E*/ result = data[index];
 334     data[index] = e;
 335     return result;
 336   }
 337
 338   /**
 339    * Appends the supplied element to the end of this list.
 340    * The element, e, can be an object of any type or null.
 341    *
 342    * @param e the element to be appended to this list
 343    * @return true, the add will always succeed
 344    */
 345   public boolean add(Object/*E*/ e)
 346   {
 347     modCount++;
 348     if (size == data.length)
 349       ensureCapacity(size + 1);
 350     data[size++] = e;
 351     return true;
 352   }
 353
 354   /**
 355    * Adds the supplied element at the specified index, shifting all
 356    * elements currently at that index or higher one to the right.
 357    * The element, e, can be an object of any type or null.
 358    *
 359    * @param index the index at which the element is being added
 360    * @param e the item being added
 361    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 362    */
 363   public void add(int index, Object/*E*/ e)
 364   {
 365     checkBoundInclusive(index);
 366     modCount++;
 367     if (size == data.length)
 368       ensureCapacity(size + 1);
 369     if (index != size)
 370       System.arraycopy(data, index, data, index + 1, size - index);
 371     data[index] = e;
 372     size++;
 373   }
 374
 375   /**
 376    * Removes the element at the user-supplied index.
 377    *
 378    * @param index the index of the element to be removed
 379    * @return the removed Object
 380    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 381    */
 382   public Object/*E*/ remove(int index)
 383   {
 384     checkBoundExclusive(index);
 385     Object/*E*/ r = data[index];
 386     modCount++;
 387     if (index != --size)
 388       System.arraycopy(data, index + 1, data, index, size - index);
 389     // Aid for garbage collection by releasing this pointer.
 390     data[size] = null;
 391     return r;
 392   }
 393
 394   /**
 395    * Removes all elements from this List
 396    */
 397   public void clear()
 398   {
 399     if (size > 0)
 400       {
 401         modCount++;
 402         // Allow for garbage collection.
 403         //Arrays.fill(data, 0, size, null);
 404         for(int i = 0; i < size; i++) {
 405           this.data[i] = null;
 406         }
 407         size = 0;
 408       }
 409   }
 410
 411   /**
 412    * Add each element in the supplied Collection to this List. It is undefined
 413    * what happens if you modify the list while this is taking place; for
 414    * example, if the collection contains this list.  c can contain objects
 415    * of any type, as well as null values.
 416    *
 417    * @param c a Collection containing elements to be added to this List
 418    * @return true if the list was modified, in other words c is not empty
 419    * @throws NullPointerException if c is null
 420    */
 421   /*public boolean addAll(Collection<? extends E> c)
 422   {
 423     return addAll(size, c);
 424   }*/
 425
 426   /**
 427    * Add all elements in the supplied collection, inserting them beginning
 428    * at the specified index.  c can contain objects of any type, as well
 429    * as null values.
 430    *
 431    * @param index the index at which the elements will be inserted
 432    * @param c the Collection containing the elements to be inserted
 433    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; 0
 434    * @throws NullPointerException if c is null
 435    */
 436   /*public boolean addAll(int index, Collection<? extends E> c)
 437   {
 438     checkBoundInclusive(index);
 439     Iterator<? extends E> itr = c.iterator();
 440     int csize = c.size();
 441
 442     modCount++;
 443     if (csize + size > data.length)
 444       ensureCapacity(size + csize);
 445     int end = index + csize;
 446     if (size > 0 && index != size)
 447       System.arraycopy(data, index, data, end, size - index);
 448     size += csize;
 449     for ( ; index < end; index++)
 450       data[index] = itr.next();
 451     return csize > 0;
 452   }*/
 453
 454   /**
 455    * Removes all elements in the half-open interval [fromIndex, toIndex).
 456    * Does nothing when toIndex is equal to fromIndex.
 457    *
 458    * @param fromIndex the first index which will be removed
 459    * @param toIndex one greater than the last index which will be removed
 460    * @throws IndexOutOfBoundsException if fromIndex &gt; toIndex
 461    */
 462   protected void removeRange(int fromIndex, int toIndex)
 463   {
 464     int change = toIndex - fromIndex;
 465     if (change > 0)
 466       {
 467         modCount++;
 468         System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
 469         size -= change;
 470       }
 471     else if (change < 0)
 472       throw new Error("Index Out Of Bounds Exception")/*IndexOutOfBoundsException()*/;
 473   }
 474
 475   /**
 476    * Checks that the index is in the range of possible elements (inclusive).
 477    *
 478    * @param index the index to check
 479    * @throws IndexOutOfBoundsException if index &gt; size
 480    */
 481   private void checkBoundInclusive(int index)
 482   {
 483     // Implementation note: we do not check for negative ranges here, since
 484     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 485     // a subclass of the required exception, with no effort on our part.
 486     if (index > size)
 487       raiseBoundsError(index);
 488   }
 489
 490   /**
 491    * Checks that the index is in the range of existing elements (exclusive).
 492    *
 493    * @param index the index to check
 494    * @throws IndexOutOfBoundsException if index &gt;= size
 495    */
 496   private void checkBoundExclusive(int index)
 497   {
 498     // Implementation note: we do not check for negative ranges here, since
 499     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 500     // a subclass of the required exception, with no effort on our part.
 501     if (index >= size)
 502       raiseBoundsError(index);
 503   }
 504
 505   /**
 506    * Raise the ArrayIndexOfOutBoundsException.
 507    *
 508    * @param index the index of the access
 509    * @throws IndexOutOfBoundsException unconditionally
 510    */
 511   private void raiseBoundsError(int index)
 512   {
 513     // Implementaion note: put in a separate method to make the JITs job easier
 514     // (separate common from uncommon code at method boundaries when trivial to
 515     // do so).
 516     throw new Error/*IndexOutOfBoundsException*/("IndexOutOfBoundsException Index: " + index + ", Size: " + size);
 517   }
 518
 519
 520   /**
 521    * Remove from this list all elements contained in the given collection.
 522    * This is not public, due to Sun's API, but this performs in linear
 523    * time while the default behavior of AbstractList would be quadratic.
 524    *
 525    * @param c the collection to filter out
 526    * @return true if this list changed
 527    * @throws NullPointerException if c is null
 528    */
 529   /*boolean removeAllInternal(Collection<?> c)
 530   {
 531     int i;
 532     int j;
 533     for (i = 0; i < size; i++)
 534       if (c.contains(data[i]))
 535         break;
 536     if (i == size)
 537       return false;
 538
 539     modCount++;
 540     for (j = i++; i < size; i++)
 541       if (! c.contains(data[i]))
 542         data[j++] = data[i];
 543     size -= i - j;
 544     return true;
 545   }*/
 546
 547   /**
 548    * Retain in this vector only the elements contained in the given collection.
 549    * This is not public, due to Sun's API, but this performs in linear
 550    * time while the default behavior of AbstractList would be quadratic.
 551    *
 552    * @param c the collection to filter by
 553    * @return true if this vector changed
 554    * @throws NullPointerException if c is null
 555    * @since 1.2
 556    */
 557   /*boolean retainAllInternal(Collection<?> c)
 558   {
 559     int i;
 560     int j;
 561     for (i = 0; i < size; i++)
 562       if (! c.contains(data[i]))
 563         break;
 564     if (i == size)
 565       return false;
 566
 567     modCount++;
 568     for (j = i++; i < size; i++)
 569       if (c.contains(data[i]))
 570         data[j++] = data[i];
 571     size -= i - j;
 572     return true;
 573   }*/
 574
 575   /**
 576    * Serializes this object to the given stream.
 577    *
 578    * @param s the stream to write to
 579    * @throws IOException if the underlying stream fails
 580    * @serialData the size field (int), the length of the backing array
 581    *             (int), followed by its elements (Objects) in proper order.
 582    */
 583   /*private void writeObject(ObjectOutputStream s) throws IOException
 584   {
 585     // The 'size' field.
 586     s.defaultWriteObject();
 587     // We serialize unused list entries to preserve capacity.
 588     int len = data.length;
 589     s.writeInt(len);
 590     // it would be more efficient to just write "size" items,
 591     // this need readObject read "size" items too.
 592     for (int i = 0; i < size; i++)
 593       s.writeObject(data[i]);
 594   }*/
 595
 596   /**
 597    * Deserializes this object from the given stream.
 598    *
 599    * @param s the stream to read from
 600    * @throws ClassNotFoundException if the underlying stream fails
 601    * @throws IOException if the underlying stream fails
 602    * @serialData the size field (int), the length of the backing array
 603    *             (int), followed by its elements (Objects) in proper order.
 604    */
 605   /*private void readObject(ObjectInputStream s)
 606     throws IOException, ClassNotFoundException
 607   {
 608     // the `size' field.
 609     s.defaultReadObject();
 610     int capacity = s.readInt();
 611     data = (E[]) new Object[capacity];
 612     for (int i = 0; i < size; i++)
 613       data[i] = (E) s.readObject();
 614   }*/
 615
 616   public ArrayListIterator iterator()
 617   {
 618     // Bah, Sun's implementation forbids using listIterator(0).
 619     return new ArrayListIterator(this);
 620   }
 621 }