1 /* Vector.java -- Class that provides growable arrays.
2 Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
40 import java
.lang
.reflect
.Array
;
41 import java
.io
.Serializable
;
44 * The <code>Vector</code> classes implements growable arrays of Objects.
45 * You can access elements in a Vector with an index, just as you
46 * can in a built in array, but Vectors can grow and shrink to accommodate
47 * more or fewer objects.<p>
49 * Vectors try to mantain efficiency in growing by having a
50 * <code>capacityIncrement</code> that can be specified at instantiation.
51 * When a Vector can no longer hold a new Object, it grows by the amount
52 * in <code>capacityIncrement</code>. If this value is 0, the vector doubles in
55 * Vector implements the JDK 1.2 List interface, and is therefore a fully
56 * compliant Collection object. The iterators are fail-fast - if external
57 * code structurally modifies the vector, any operation on the iterator will
58 * then throw a {@link ConcurrentModificationException}. The Vector class is
59 * fully synchronized, but the iterators are not. So, when iterating over a
60 * vector, be sure to synchronize on the vector itself. If you don't want the
61 * expense of synchronization, use ArrayList instead. On the other hand, the
62 * Enumeration of elements() is not thread-safe, nor is it fail-fast; so it
63 * can lead to undefined behavior even in a single thread if you modify the
64 * vector during iteration.<p>
66 * Note: Some methods, especially those specified by List, specify throwing
67 * {@link IndexOutOfBoundsException}, but it is easier to implement by
68 * throwing the subclass {@link ArrayIndexOutOfBoundsException}. Others
69 * directly specify this subclass.
71 * @author Scott G. Miller
72 * @author Bryce McKinlay
73 * @author Eric Blake <ebb9@email.byu.edu>
79 * @status updated to 1.4
81 public class Vector
extends AbstractList
82 implements List
, RandomAccess
, Cloneable
, Serializable
85 * Compatible with JDK 1.0+.
87 private static final long serialVersionUID
= -2767605614048989439L;
90 * The internal array used to hold members of a Vector. The elements are
91 * in positions 0 through elementCount - 1, and all remaining slots are null.
92 * @serial the elements
94 protected Object
[] elementData
;
97 * The number of elements currently in the vector, also returned by
101 protected int elementCount
;
104 * The amount the Vector's internal array should be increased in size when
105 * a new element is added that exceeds the current size of the array,
106 * or when {@link #ensureCapacity} is called. If <= 0, the vector just
108 * @serial the amount to grow the vector by
110 protected int capacityIncrement
;
113 * Constructs an empty vector with an initial size of 10, and
114 * a capacity increment of 0
122 * Constructs a vector containing the contents of Collection, in the
123 * order given by the collection.
125 * @param c collection of elements to add to the new vector
126 * @throws NullPointerException if c is null
129 public Vector(Collection c
)
131 elementCount
= c
.size();
132 elementData
= c
.toArray(new Object
[elementCount
]);
136 * Constructs a Vector with the initial capacity and capacity
137 * increment specified.
139 * @param initialCapacity the initial size of the Vector's internal array
140 * @param capacityIncrement the amount the internal array should be
141 * increased by when necessary, 0 to double the size
142 * @throws IllegalArgumentException if initialCapacity < 0
144 public Vector(int initialCapacity
, int capacityIncrement
)
146 if (initialCapacity
< 0)
147 throw new IllegalArgumentException();
148 elementData
= new Object
[initialCapacity
];
149 this.capacityIncrement
= capacityIncrement
;
153 * Constructs a Vector with the initial capacity specified, and a capacity
154 * increment of 0 (double in size).
156 * @param initialCapacity the initial size of the Vector's internal array
157 * @throws IllegalArgumentException if initialCapacity < 0
159 public Vector(int initialCapacity
)
161 this(initialCapacity
, 0);
165 * Copies the contents of a provided array into the Vector. If the
166 * array is too large to fit in the Vector, an IndexOutOfBoundsException
167 * is thrown without modifying the array. Old elements in the Vector are
168 * overwritten by the new elements.
170 * @param a target array for the copy
171 * @throws IndexOutOfBoundsException the array is not large enough
172 * @throws NullPointerException the array is null
173 * @see #toArray(Object[])
175 public synchronized void copyInto(Object
[] a
)
177 System
.arraycopy(elementData
, 0, a
, 0, elementCount
);
181 * Trims the Vector down to size. If the internal data array is larger
182 * than the number of Objects its holding, a new array is constructed
183 * that precisely holds the elements. Otherwise this does nothing.
185 public synchronized void trimToSize()
187 // Don't bother checking for the case where size() == the capacity of the
188 // vector since that is a much less likely case; it's more efficient to
189 // not do the check and lose a bit of performance in that infrequent case
191 Object
[] newArray
= new Object
[elementCount
];
192 System
.arraycopy(elementData
, 0, newArray
, 0, elementCount
);
193 elementData
= newArray
;
197 * Ensures that <code>minCapacity</code> elements can fit within this Vector.
198 * If <code>elementData</code> is too small, it is expanded as follows:
199 * If the <code>elementCount + capacityIncrement</code> is adequate, that
200 * is the new size. If <code>capacityIncrement</code> is non-zero, the
201 * candidate size is double the current. If that is not enough, the new
202 * size is <code>minCapacity</code>.
204 * @param minCapacity the desired minimum capacity, negative values ignored
206 public synchronized void ensureCapacity(int minCapacity
)
208 if (elementData
.length
>= minCapacity
)
212 if (capacityIncrement
<= 0)
213 newCapacity
= elementData
.length
* 2;
215 newCapacity
= elementData
.length
+ capacityIncrement
;
217 Object
[] newArray
= new Object
[Math
.max(newCapacity
, minCapacity
)];
219 System
.arraycopy(elementData
, 0, newArray
, 0, elementCount
);
220 elementData
= newArray
;
224 * Explicitly sets the size of the vector (but not necessarily the size of
225 * the internal data array). If the new size is smaller than the old one,
226 * old values that don't fit are lost. If the new size is larger than the
227 * old one, the vector is padded with null entries.
229 * @param newSize The new size of the internal array
230 * @throws ArrayIndexOutOfBoundsException if the new size is negative
232 public synchronized void setSize(int newSize
)
234 // Don't bother checking for the case where size() == the capacity of the
235 // vector since that is a much less likely case; it's more efficient to
236 // not do the check and lose a bit of performance in that infrequent case
238 ensureCapacity(newSize
);
239 if (newSize
< elementCount
)
240 Arrays
.fill(elementData
, newSize
, elementCount
, null);
241 elementCount
= newSize
;
245 * Returns the size of the internal data array (not the amount of elements
246 * contained in the Vector).
248 * @return capacity of the internal data array
250 public synchronized int capacity()
252 return elementData
.length
;
256 * Returns the number of elements stored in this Vector.
258 * @return the number of elements in this Vector
260 public synchronized int size()
266 * Returns true if this Vector is empty, false otherwise
268 * @return true if the Vector is empty, false otherwise
270 public synchronized boolean isEmpty()
272 return elementCount
== 0;
276 * Returns an Enumeration of the elements of this Vector. The enumeration
277 * visits the elements in increasing index order, but is NOT thread-safe.
279 * @return an Enumeration
282 // No need to synchronize as the Enumeration is not thread-safe!
283 public Enumeration
elements()
285 return new Enumeration()
289 public boolean hasMoreElements()
291 return i
< elementCount
;
294 public Object
nextElement()
296 if (i
>= elementCount
)
297 throw new NoSuchElementException();
298 return elementData
[i
++];
304 * Returns true when <code>elem</code> is contained in this Vector.
306 * @param elem the element to check
307 * @return true if the object is contained in this Vector, false otherwise
309 public boolean contains(Object elem
)
311 return indexOf(elem
, 0) >= 0;
315 * Returns the first occurrence of <code>elem</code> in the Vector, or -1 if
316 * <code>elem</code> is not found.
318 * @param elem the object to search for
319 * @return the index of the first occurrence, or -1 if not found
321 public int indexOf(Object elem
)
323 return indexOf(elem
, 0);
327 * Searches the vector starting at <code>index</code> for object
328 * <code>elem</code> and returns the index of the first occurrence of this
329 * Object. If the object is not found, or index is larger than the size
330 * of the vector, -1 is returned.
332 * @param e the Object to search for
333 * @param index start searching at this index
334 * @return the index of the next occurrence, or -1 if it is not found
335 * @throws IndexOutOfBoundsException if index < 0
337 public synchronized int indexOf(Object e
, int index
)
339 for (int i
= index
; i
< elementCount
; i
++)
340 if (equals(e
, elementData
[i
]))
346 * Returns the last index of <code>elem</code> within this Vector, or -1
347 * if the object is not within the Vector.
349 * @param elem the object to search for
350 * @return the last index of the object, or -1 if not found
352 public int lastIndexOf(Object elem
)
354 return lastIndexOf(elem
, elementCount
- 1);
358 * Returns the index of the first occurrence of <code>elem</code>, when
359 * searching backwards from <code>index</code>. If the object does not
360 * occur in this Vector, or index is less than 0, -1 is returned.
362 * @param e the object to search for
363 * @param index the index to start searching in reverse from
364 * @return the index of the Object if found, -1 otherwise
365 * @throws IndexOutOfBoundsException if index >= size()
367 public synchronized int lastIndexOf(Object e
, int index
)
369 checkBoundExclusive(index
);
370 for (int i
= index
; i
>= 0; i
--)
371 if (equals(e
, elementData
[i
]))
377 * Returns the Object stored at <code>index</code>.
379 * @param index the index of the Object to retrieve
380 * @return the object at <code>index</code>
381 * @throws ArrayIndexOutOfBoundsException index < 0 || index >= size()
384 public synchronized Object
elementAt(int index
)
386 checkBoundExclusive(index
);
387 return elementData
[index
];
391 * Returns the first element (index 0) in the Vector.
393 * @return the first Object in the Vector
394 * @throws NoSuchElementException the Vector is empty
396 public synchronized Object
firstElement()
398 if (elementCount
== 0)
399 throw new NoSuchElementException();
401 return elementData
[0];
405 * Returns the last element in the Vector.
407 * @return the last Object in the Vector
408 * @throws NoSuchElementException the Vector is empty
410 public synchronized Object
lastElement()
412 if (elementCount
== 0)
413 throw new NoSuchElementException();
415 return elementData
[elementCount
- 1];
419 * Changes the element at <code>index</code> to be <code>obj</code>
421 * @param obj the object to store
422 * @param index the position in the Vector to store the object
423 * @throws ArrayIndexOutOfBoundsException the index is out of range
424 * @see #set(int, Object)
426 public void setElementAt(Object obj
, int index
)
432 * Removes the element at <code>index</code>, and shifts all elements at
433 * positions greater than index to their index - 1.
435 * @param index the index of the element to remove
436 * @throws ArrayIndexOutOfBoundsException index < 0 || index >= size();
439 public void removeElementAt(int index
)
445 * Inserts a new element into the Vector at <code>index</code>. Any elements
446 * at or greater than index are shifted up one position.
448 * @param obj the object to insert
449 * @param index the index at which the object is inserted
450 * @throws ArrayIndexOutOfBoundsException index < 0 || index > size()
451 * @see #add(int, Object)
453 public synchronized void insertElementAt(Object obj
, int index
)
455 checkBoundInclusive(index
);
456 if (elementCount
== elementData
.length
)
457 ensureCapacity(elementCount
+ 1);
459 System
.arraycopy(elementData
, index
, elementData
, index
+ 1,
460 elementCount
- index
);
462 elementData
[index
] = obj
;
466 * Adds an element to the Vector at the end of the Vector. The vector
467 * is increased by ensureCapacity(size() + 1) if needed.
469 * @param obj the object to add to the Vector
471 public synchronized void addElement(Object obj
)
473 if (elementCount
== elementData
.length
)
474 ensureCapacity(elementCount
+ 1);
476 elementData
[elementCount
++] = obj
;
480 * Removes the first (the lowestindex) occurance of the given object from
481 * the Vector. If such a remove was performed (the object was found), true
482 * is returned. If there was no such object, false is returned.
484 * @param obj the object to remove from the Vector
485 * @return true if the Object was in the Vector, false otherwise
486 * @see #remove(Object)
488 public synchronized boolean removeElement(Object obj
)
490 int idx
= indexOf(obj
, 0);
500 * Removes all elements from the Vector. Note that this does not
501 * resize the internal data array.
505 public synchronized void removeAllElements()
507 if (elementCount
== 0)
511 Arrays
.fill(elementData
, 0, elementCount
, null);
516 * Creates a new Vector with the same contents as this one. The clone is
517 * shallow; elements are not cloned.
519 * @return the clone of this vector
521 public synchronized Object
clone()
525 Vector clone
= (Vector
) super.clone();
526 clone
.elementData
= (Object
[]) elementData
.clone();
529 catch (CloneNotSupportedException ex
)
531 // Impossible to get here.
532 throw new InternalError(ex
.toString());
537 * Returns an Object array with the contents of this Vector, in the order
538 * they are stored within this Vector. Note that the Object array returned
539 * is not the internal data array, and that it holds only the elements
540 * within the Vector. This is similar to creating a new Object[] with the
541 * size of this Vector, then calling Vector.copyInto(yourArray).
543 * @return an Object[] containing the contents of this Vector in order
546 public synchronized Object
[] toArray()
548 Object
[] newArray
= new Object
[elementCount
];
554 * Returns an array containing the contents of this Vector.
555 * If the provided array is large enough, the contents are copied
556 * into that array, and a null is placed in the position size().
557 * In this manner, you can obtain the size of a Vector by the position
558 * of the null element, if you know the vector does not itself contain
559 * null entries. If the array is not large enough, reflection is used
560 * to create a bigger one of the same runtime type.
562 * @param a an array to copy the Vector into if large enough
563 * @return an array with the contents of this Vector in order
564 * @throws ArrayStoreException the runtime type of the provided array
565 * cannot hold the elements of the Vector
566 * @throws NullPointerException if <code>a</code> is null
569 public synchronized Object
[] toArray(Object
[] a
)
571 if (a
.length
< elementCount
)
572 a
= (Object
[]) Array
.newInstance(a
.getClass().getComponentType(),
574 else if (a
.length
> elementCount
)
575 a
[elementCount
] = null;
576 System
.arraycopy(elementData
, 0, a
, 0, elementCount
);
581 * Returns the element at position <code>index</code>.
583 * @param index the position from which an element will be retrieved
584 * @return the element at that position
585 * @throws ArrayIndexOutOfBoundsException index < 0 || index >= size()
588 public Object
get(int index
)
590 return elementAt(index
);
594 * Puts <code>element</code> into the Vector at position <code>index</code>
595 * and returns the Object that previously occupied that position.
597 * @param index the index within the Vector to place the Object
598 * @param element the Object to store in the Vector
599 * @return the previous object at the specified index
600 * @throws ArrayIndexOutOfBoundsException index < 0 || index >= size()
603 public synchronized Object
set(int index
, Object element
)
605 checkBoundExclusive(index
);
606 Object temp
= elementData
[index
];
607 elementData
[index
] = element
;
612 * Adds an object to the Vector.
614 * @param o the element to add to the Vector
615 * @return true, as specified by List
618 public boolean add(Object o
)
625 * Removes the given Object from the Vector. If it exists, true
626 * is returned, if not, false is returned.
628 * @param o the object to remove from the Vector
629 * @return true if the Object existed in the Vector, false otherwise
632 public boolean remove(Object o
)
634 return removeElement(o
);
638 * Adds an object at the specified index. Elements at or above
639 * index are shifted up one position.
641 * @param index the index at which to add the element
642 * @param element the element to add to the Vector
643 * @throws ArrayIndexOutOfBoundsException index < 0 || index > size()
646 public void add(int index
, Object element
)
648 insertElementAt(element
, index
);
652 * Removes the element at the specified index, and returns it.
654 * @param index the position from which to remove the element
655 * @return the object removed
656 * @throws ArrayIndexOutOfBoundsException index < 0 || index >= size()
659 public synchronized Object
remove(int index
)
661 checkBoundExclusive(index
);
662 Object temp
= elementData
[index
];
665 if (index
< elementCount
)
666 System
.arraycopy(elementData
, index
+ 1, elementData
, index
,
667 elementCount
- index
);
668 elementData
[elementCount
] = null;
673 * Clears all elements in the Vector and sets its size to 0.
681 * Returns true if this Vector contains all the elements in c.
683 * @param c the collection to compare to
684 * @return true if this vector contains all elements of c
685 * @throws NullPointerException if c is null
688 public synchronized boolean containsAll(Collection c
)
690 // Here just for the sychronization.
691 return super.containsAll(c
);
695 * Appends all elements of the given collection to the end of this Vector.
696 * Behavior is undefined if the collection is modified during this operation
697 * (for example, if this == c).
699 * @param c the collection to append
700 * @return true if this vector changed, in other words c was not empty
701 * @throws NullPointerException if c is null
704 public synchronized boolean addAll(Collection c
)
706 return addAll(elementCount
, c
);
710 * Remove from this vector all elements contained in the given collection.
712 * @param c the collection to filter out
713 * @return true if this vector changed
714 * @throws NullPointerException if c is null
717 public synchronized boolean removeAll(Collection c
)
720 throw new NullPointerException();
724 for (i
= 0; i
< elementCount
; i
++)
725 if (c
.contains(elementData
[i
]))
727 if (i
== elementCount
)
731 for (j
= i
++; i
< elementCount
; i
++)
732 if (! c
.contains(elementData
[i
]))
733 elementData
[j
++] = elementData
[i
];
734 elementCount
-= i
- j
;
739 * Retain in this vector only the elements contained in the given collection.
741 * @param c the collection to filter by
742 * @return true if this vector changed
743 * @throws NullPointerException if c is null
746 public synchronized boolean retainAll(Collection c
)
749 throw new NullPointerException();
753 for (i
= 0; i
< elementCount
; i
++)
754 if (! c
.contains(elementData
[i
]))
756 if (i
== elementCount
)
760 for (j
= i
++; i
< elementCount
; i
++)
761 if (c
.contains(elementData
[i
]))
762 elementData
[j
++] = elementData
[i
];
763 elementCount
-= i
- j
;
768 * Inserts all elements of the given collection at the given index of
769 * this Vector. Behavior is undefined if the collection is modified during
770 * this operation (for example, if this == c).
772 * @param c the collection to append
773 * @return true if this vector changed, in other words c was not empty
774 * @throws NullPointerException if c is null
775 * @throws ArrayIndexOutOfBoundsException index < 0 || index > size()
778 public synchronized boolean addAll(int index
, Collection c
)
780 checkBoundInclusive(index
);
781 Iterator itr
= c
.iterator();
782 int csize
= c
.size();
785 ensureCapacity(elementCount
+ csize
);
786 int end
= index
+ csize
;
787 if (elementCount
> 0 && index
!= elementCount
)
788 System
.arraycopy(elementData
, index
,
789 elementData
, end
, elementCount
- index
);
790 elementCount
+= csize
;
791 for ( ; index
< end
; index
++)
792 elementData
[index
] = itr
.next();
797 * Compares this to the given object.
799 * @param o the object to compare to
800 * @return true if the two are equal
803 public synchronized boolean equals(Object o
)
805 // Here just for the sychronization.
806 return super.equals(o
);
810 * Computes the hashcode of this object.
812 * @return the hashcode
815 public synchronized int hashCode()
817 // Here just for the sychronization.
818 return super.hashCode();
822 * Returns a string representation of this Vector in the form
823 * "[element0, element1, ... elementN]".
825 * @return the String representation of this Vector
827 public synchronized String
toString()
829 // Here just for the sychronization.
830 return super.toString();
834 * Obtain a List view of a subsection of this list, from fromIndex
835 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
836 * sublist is empty. The returned list is modifiable, and changes in one
837 * reflect in the other. If this list is structurally modified in
838 * any way other than through the returned list, the result of any subsequent
839 * operations on the returned list is undefined.
842 * @param fromIndex the index that the returned list should start from
844 * @param toIndex the index that the returned list should go to (exclusive)
845 * @return a List backed by a subsection of this vector
846 * @throws IndexOutOfBoundsException if fromIndex < 0
847 * || toIndex > size()
848 * @throws IllegalArgumentException if fromIndex > toIndex
849 * @see ConcurrentModificationException
852 public synchronized List
subList(int fromIndex
, int toIndex
)
854 List sub
= super.subList(fromIndex
, toIndex
);
855 // We must specify the correct object to synchronize upon, hence the
856 // use of a non-public API
857 return new Collections
.SynchronizedList(this, sub
);
861 * Removes a range of elements from this list.
862 * Does nothing when toIndex is equal to fromIndex.
864 * @param fromIndex the index to start deleting from (inclusive)
865 * @param toIndex the index to delete up to (exclusive)
866 * @throws IndexOutOfBoundsException if fromIndex > toIndex
868 // This does not need to be synchronized, because it is only called through
869 // clear() of a sublist, and clear() had already synchronized.
870 protected void removeRange(int fromIndex
, int toIndex
)
872 int change
= toIndex
- fromIndex
;
876 System
.arraycopy(elementData
, toIndex
, elementData
, fromIndex
,
877 elementCount
- toIndex
);
878 int save
= elementCount
;
879 elementCount
-= change
;
880 Arrays
.fill(elementData
, elementCount
, save
, null);
883 throw new IndexOutOfBoundsException();
887 * Checks that the index is in the range of possible elements (inclusive).
889 * @param index the index to check
890 * @throws ArrayIndexOutOfBoundsException if index > size
892 private void checkBoundInclusive(int index
)
894 // Implementation note: we do not check for negative ranges here, since
895 // use of a negative index will cause an ArrayIndexOutOfBoundsException
896 // with no effort on our part.
897 if (index
> elementCount
)
898 throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount
);
902 * Checks that the index is in the range of existing elements (exclusive).
904 * @param index the index to check
905 * @throws ArrayIndexOutOfBoundsException if index >= size
907 private void checkBoundExclusive(int index
)
909 // Implementation note: we do not check for negative ranges here, since
910 // use of a negative index will cause an ArrayIndexOutOfBoundsException
911 // with no effort on our part.
912 if (index
>= elementCount
)
913 throw new ArrayIndexOutOfBoundsException(index
+ " >= " + elementCount
);