From d25d03d03b37b5f5000fd5d0a53f93f01f506b87 Mon Sep 17 00:00:00 2001 From: bryce Date: Wed, 22 Nov 2000 11:59:59 +0000 Subject: [PATCH] 2000-11-22 Bryce McKinlay * Makefile.in: Rebuilt. * Makefile.am (core_java_source_files): Added Collections.java. * java/util/List.java: Merged from classpath. * java/util/Vector.java: Ditto. * java/util/Collections.java: From classpath. * java/util/ArrayList.java (addAll(Collection)): Call addAll(int,Collection) instead of duplicating code. (indexOf): Clean up int initialization. (clear): Set cleared array entries to null, to allow garbage collection. * java/util/List.java: Minor formatting fixes. * java/util/SimpleTimeZone.java: ditto. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@37652 138bc75d-0d04-0410-961f-82ee72b054a4 --- libjava/ChangeLog | 15 + libjava/Makefile.am | 1 + libjava/Makefile.in | 60 +- libjava/java/util/ArrayList.java | 24 +- libjava/java/util/Collections.java | 1829 +++++++++++++++++++++++++++++++++ libjava/java/util/List.java | 360 ++++++- libjava/java/util/SimpleTimeZone.java | 2 +- libjava/java/util/Vector.java | 954 +++++++++++------ 8 files changed, 2824 insertions(+), 421 deletions(-) create mode 100644 libjava/java/util/Collections.java diff --git a/libjava/ChangeLog b/libjava/ChangeLog index 97d8c32..d8481b2 100644 --- a/libjava/ChangeLog +++ b/libjava/ChangeLog @@ -1,3 +1,18 @@ +2000-11-22 Bryce McKinlay + + * Makefile.in: Rebuilt. + * Makefile.am (core_java_source_files): Added Collections.java. + * java/util/List.java: Merged from classpath. + * java/util/Vector.java: Ditto. + * java/util/Collections.java: From classpath. + * java/util/ArrayList.java (addAll(Collection)): Call + addAll(int,Collection) instead of duplicating code. + (indexOf): Clean up int initialization. + (clear): Set cleared array entries to null, to allow garbage + collection. + * java/util/List.java: Minor formatting fixes. + * java/util/SimpleTimeZone.java: ditto. + 2000-11-18 Tom Tromey * Makefile.in: Rebuilt. diff --git a/libjava/Makefile.am b/libjava/Makefile.am index 5f2f446..c8e6f07 100644 --- a/libjava/Makefile.am +++ b/libjava/Makefile.am @@ -929,6 +929,7 @@ java/util/BitSet.java \ java/util/Bucket.java \ java/util/Calendar.java \ java/util/Collection.java \ +java/util/Collections.java \ java/util/Comparator.java \ java/util/ConcurrentModificationException.java \ java/util/Date.java \ diff --git a/libjava/Makefile.in b/libjava/Makefile.in index 2cfb0a5..fe3d641 100644 --- a/libjava/Makefile.in +++ b/libjava/Makefile.in @@ -119,43 +119,29 @@ here = @here@ libgcj_basedir = @libgcj_basedir@ AUTOMAKE_OPTIONS = foreign no-installinfo -@TESTSUBDIR_TRUE@SUBDIRS = \ -@TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include -@TESTSUBDIR_FALSE@SUBDIRS = \ -@TESTSUBDIR_FALSE@$(DIRLTDL) gcj include -@USE_LIBDIR_TRUE@toolexeclibdir = \ -@USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR) -@USE_LIBDIR_FALSE@toolexeclibdir = \ -@USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR) -@USE_LIBDIR_FALSE@toolexecdir = \ -@USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias) -@NO_X_TRUE@cond_x_ltlibrary = \ -@NO_X_FALSE@cond_x_ltlibrary = \ -@NO_X_FALSE@libgcjx.la +@TESTSUBDIR_TRUE@SUBDIRS = @TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include +@TESTSUBDIR_FALSE@SUBDIRS = @TESTSUBDIR_FALSE@$(DIRLTDL) gcj include +@USE_LIBDIR_TRUE@toolexeclibdir = @USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR) +@USE_LIBDIR_FALSE@toolexeclibdir = @USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR) +@USE_LIBDIR_FALSE@toolexecdir = @USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias) +@NO_X_TRUE@cond_x_ltlibrary = +@NO_X_FALSE@cond_x_ltlibrary = @NO_X_FALSE@libgcjx.la toolexeclib_LTLIBRARIES = libgcj.la $(cond_x_ltlibrary) toolexeclib_DATA = libgcj.spec data_DATA = libgcj.zip -@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = \ -@NEEDS_DATA_START_TRUE@libgcjdata.a -@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = \ -@NEEDS_DATA_START_TRUE@libgcjdata.c +@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = @NEEDS_DATA_START_TRUE@libgcjdata.a +@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = @NEEDS_DATA_START_TRUE@libgcjdata.c -@NATIVE_TRUE@bin_PROGRAMS = \ -@NATIVE_TRUE@jv-convert gij +@NATIVE_TRUE@bin_PROGRAMS = @NATIVE_TRUE@jv-convert gij bin_SCRIPTS = addr2name.awk -@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = \ -@CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/zip/zip$(EXEEXT) -@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = \ -@CANADIAN_TRUE@@NULL_TARGET_FALSE@zip -@CANADIAN_FALSE@ZIP = \ -@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/zip/zip$(EXEEXT) -@CANADIAN_TRUE@GCJH = \ -@CANADIAN_TRUE@gcjh -@CANADIAN_FALSE@GCJH = \ -@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT) +@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/zip/zip$(EXEEXT) +@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_FALSE@zip +@CANADIAN_FALSE@ZIP = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/zip/zip$(EXEEXT) +@CANADIAN_TRUE@GCJH = @CANADIAN_TRUE@gcjh +@CANADIAN_FALSE@GCJH = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT) GCJCOMPILE = $(LIBTOOL) --tag=GCJ --mode=compile $(GCJ) -fassume-compiled -fclasspath=$(here) -L$(here) $(JC1FLAGS) -MD -MT $@ -MF $(@:.lo=.d) -c GCJLINK = $(LIBTOOL) --mode=link $(GCJ) -L$(here) $(JC1FLAGS) $(LDFLAGS) -o $@ @@ -170,10 +156,8 @@ AM_CXXFLAGS = -fno-rtti -fvtable-thunks -fasynchronous-exceptions \ -fdollars-in-identifiers \ @LIBGCJ_CXXFLAGS@ @EXCEPTIONSPEC@ @X_CFLAGS@ $(WARNINGS) -D_GNU_SOURCE -@USING_GCC_TRUE@AM_CFLAGS = \ -@USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS) -@USING_GCC_FALSE@AM_CFLAGS = \ -@USING_GCC_FALSE@@LIBGCJ_CFLAGS@ +@USING_GCC_TRUE@AM_CFLAGS = @USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS) +@USING_GCC_FALSE@AM_CFLAGS = @USING_GCC_FALSE@@LIBGCJ_CFLAGS@ JCFLAGS = -g JC1FLAGS = -g @LIBGCJ_JAVAFLAGS@ @@ -240,8 +224,7 @@ extra_headers = java/lang/Object.h java/lang/Class.h NM = nm -@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = \ -@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS +@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = @NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS CONVERT_DIR = gnu/gcj/convert @@ -695,6 +678,7 @@ java/util/BitSet.java \ java/util/Bucket.java \ java/util/Calendar.java \ java/util/Collection.java \ +java/util/Collections.java \ java/util/Comparator.java \ java/util/ConcurrentModificationException.java \ java/util/Date.java \ @@ -1180,7 +1164,7 @@ libgcj-test.spec.in libgcj.spec.in DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST) -TAR = tar +TAR = gtar GZIP_ENV = --best DIST_SUBDIRS = @DIRLTDL@ testsuite gcj include @DIRLTDL@ gcj include DEP_FILES = .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \ @@ -1653,7 +1637,7 @@ DEP_FILES = .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \ .deps/java/util/Arrays.P .deps/java/util/BasicMapEntry.P \ .deps/java/util/BitSet.P .deps/java/util/Bucket.P \ .deps/java/util/Calendar.P .deps/java/util/Collection.P \ -.deps/java/util/Comparator.P \ +.deps/java/util/Collections.P .deps/java/util/Comparator.P \ .deps/java/util/ConcurrentModificationException.P \ .deps/java/util/Date.P .deps/java/util/Dictionary.P \ .deps/java/util/EmptyStackException.P .deps/java/util/Enumeration.P \ @@ -2070,7 +2054,7 @@ distdir: $(DISTFILES) @for file in $(DISTFILES); do \ d=$(srcdir); \ if test -d $$d/$$file; then \ - cp -pr $$/$$file $(distdir)/$$file; \ + cp -pr $$d/$$file $(distdir)/$$file; \ else \ test -f $(distdir)/$$file \ || ln $$d/$$file $(distdir)/$$file 2> /dev/null \ diff --git a/libjava/java/util/ArrayList.java b/libjava/java/util/ArrayList.java index 084084c..ef7d6e5 100644 --- a/libjava/java/util/ArrayList.java +++ b/libjava/java/util/ArrayList.java @@ -43,7 +43,7 @@ import java.io.ObjectStreamField; * to or removing from the end of a list, checking the size, &c. * * @author Jon A. Zeppieri - * @version $Id: ArrayList.java,v 1.2 2000/10/29 05:06:10 bryce Exp $ + * @version $Id: ArrayList.java,v 1.3 2000/11/02 10:08:03 bryce Exp $ * @see java.util.AbstractList * @see java.util.List */ @@ -219,15 +219,7 @@ public class ArrayList extends AbstractList */ public boolean addAll(Collection c) { - modCount++; - Iterator itr = c.iterator(); - int csize = c.size(); - ensureCapacity(size + csize); - for (int pos = 0; pos < csize; pos++) - { - data[size++] = itr.next(); - } - return (csize > 0); + return addAll(size, c); } /** @@ -295,9 +287,7 @@ public class ArrayList extends AbstractList */ public int indexOf(Object e) { - int i; - - for (i = 0; i < size; i++) + for (int i = 0; i < size; i++) { if (e == null ? data[i] == null : e.equals(data[i])) return i; @@ -330,6 +320,10 @@ public class ArrayList extends AbstractList public void clear() { modCount++; + for (int i = 0; i < size; i++) + { + data[i] = null; + } size = 0; } @@ -364,8 +358,8 @@ public class ArrayList extends AbstractList } /** - * Returns an Array whse component type is the runtime component type of - * the passes-in Array. The returned Array is populated with all of the + * Returns an Array whose component type is the runtime component type of + * the passed-in Array. The returned Array is populated with all of the * elements in this ArrayList. If the passed-in Array is not large enough * to store all of the elements in this List, a new Array will be created * and returned; if the passed-in Array is larger than the size diff --git a/libjava/java/util/Collections.java b/libjava/java/util/Collections.java new file mode 100644 index 0000000..a827071 --- /dev/null +++ b/libjava/java/util/Collections.java @@ -0,0 +1,1829 @@ +/* Collections.java -- Utility class with methods to operate on collections + Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +// TO DO: +// ~ Serialization is very much broken. Blame Sun for not specifying it. +// ~ The synchronized* and unmodifiable* methods don't have doc-comments. + +package java.util; + +import java.io.Serializable; + +/** + * Utility class consisting of static methods that operate on, or return + * Collections. Contains methods to sort, search, reverse, fill and shuffle + * Collections, methods to facilitate interoperability with legacy APIs that + * are unaware of collections, a method to return a list which consists of + * multiple copies of one element, and methods which "wrap" collections to give + * them extra properties, such as thread-safety and unmodifiability. + */ +public class Collections +{ + + /** + * This class is non-instantiable. + */ + private Collections() + { + } + + /** + * An immutable, empty Set. + * Note: This implementation isn't Serializable, although it should be by the + * spec. + */ + public static final Set EMPTY_SET = new AbstractSet() + { + + public int size() + { + return 0; + } + + // This is really cheating! I think it's perfectly valid, though - the + // more conventional code is here, commented out, in case anyone disagrees. + public Iterator iterator() + { + return EMPTY_LIST.iterator(); + } + + // public Iterator iterator() { + // return new Iterator() { + // + // public boolean hasNext() { + // return false; + // } + // + // public Object next() { + // throw new NoSuchElementException(); + // } + // + // public void remove() { + // throw new UnsupportedOperationException(); + // } + // }; + // } + + }; + + /** + * An immutable, empty List. + * Note: This implementation isn't serializable, although it should be by the + * spec. + */ + public static final List EMPTY_LIST = new AbstractList() + { + + public int size() + { + return 0; + } + + public Object get(int index) + { + throw new IndexOutOfBoundsException(); + } + }; + + /** + * An immutable, empty Map. + * Note: This implementation isn't serializable, although it should be by the + * spec. + */ + public static final Map EMPTY_MAP = new AbstractMap() + { + + public Set entrySet() + { + return EMPTY_SET; + } + }; + + /** + * Compare two objects with or without a Comparator. If c is null, uses the + * natural ordering. Slightly slower than doing it inline if the JVM isn't + * clever, but worth it for removing a duplicate of the search code. + * Note: This same code is used in Arrays (for sort as well as search) + */ + private static int compare(Object o1, Object o2, Comparator c) + { + if (c == null) + { + return ((Comparable) o1).compareTo(o2); + } + else + { + return c.compare(o1, o2); + } + } + + /** + * The hard work for the search routines. If the Comparator given is null, + * uses the natural ordering of the elements. + */ + private static int search(List l, Object key, final Comparator c) + { + + int pos = 0; + + // We use a linear search using an iterator if we can guess that the list + // is sequential-access. + if (l instanceof AbstractSequentialList) + { + ListIterator i = l.listIterator(); + while (i.hasNext()) + { + final int d = compare(key, i.next(), c); + if (d == 0) + { + return pos; + } + else if (d < 0) + { + return -pos - 1; + } + pos++; + } + + // We assume the list is random-access, and use a binary search + } + else + { + int low = 0; + int hi = l.size() - 1; + while (low <= hi) + { + pos = (low + hi) >> 1; + final int d = compare(key, l.get(pos), c); + if (d == 0) + { + return pos; + } + else if (d < 0) + { + hi = pos - 1; + } + else + { + low = ++pos; // This gets the insertion point right on the last loop + } + } + } + + // If we failed to find it, we do the same whichever search we did. + return -pos - 1; + } + + /** + * Perform a binary search of a List for a key, using the natural ordering of + * the elements. The list must be sorted (as by the sort() method) - if it is + * not, the behaviour of this method is undefined, and may be an infinite + * loop. Further, the key must be comparable with every item in the list. If + * the list contains the key more than once, any one of them may be found. To + * avoid pathological behaviour on sequential-access lists, a linear search + * is used if (l instanceof AbstractSequentialList). Note: although the + * specification allows for an infinite loop if the list is unsorted, it will + * not happen in this (Classpath) implementation. + * + * @param l the list to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + * @exception ClassCastException if key could not be compared with one of the + * elements of l + * @exception NullPointerException if a null element has compareTo called + */ + public static int binarySearch(List l, Object key) + { + return search(l, key, null); + } + + /** + * Perform a binary search of a List for a key, using a supplied Comparator. + * The list must be sorted (as by the sort() method with the same Comparator) + * - if it is not, the behaviour of this method is undefined, and may be an + * infinite loop. Further, the key must be comparable with every item in the + * list. If the list contains the key more than once, any one of them may be + * found. To avoid pathological behaviour on sequential-access lists, a + * linear search is used if (l instanceof AbstractSequentialList). Note: + * although the specification allows for an infinite loop if the list is + * unsorted, it will not happen in this (Classpath) implementation. + * + * @param l the list to search (must be sorted) + * @param key the value to search for + * @param c the comparator by which the list is sorted + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + * @exception ClassCastException if key could not be compared with one of the + * elements of l + */ + public static int binarySearch(List l, Object key, Comparator c) + { + if (c == null) + { + throw new NullPointerException(); + } + return search(l, key, c); + } + + /** + * Copy one list to another. If the destination list is longer than the + * source list, the remaining elements are unaffected. This method runs in + * linear time. + * + * @param dest the destination list. + * @param source the source list. + * @exception IndexOutOfBoundsException if the destination list is shorter + * than the source list (the elements that can be copied will be, prior to + * the exception being thrown). + * @exception UnsupportedOperationException if dest.listIterator() does not + * support the set operation. + */ + public static void copy(List dest, List source) + { + Iterator i1 = source.iterator(); + ListIterator i2 = dest.listIterator(); + while (i1.hasNext()) + { + i2.next(); + i2.set(i1.next()); + } + } + + /** + * Returns an Enumeration over a collection. This allows interoperability + * with legacy APIs that require an Enumeration as input. + * + * @param c the Collection to iterate over + * @returns an Enumeration backed by an Iterator over c + */ + public static Enumeration enumeration(Collection c) + { + final Iterator i = c.iterator(); + return new Enumeration() + { + public final boolean hasMoreElements() + { + return i.hasNext(); + } + public final Object nextElement() + { + return i.next(); + } + }; + } + + /** + * Replace every element of a list with a given value. This method runs in + * linear time. + * + * @param l the list to fill. + * @param val the object to vill the list with. + * @exception UnsupportedOperationException if l.listIterator() does not + * support the set operation. + */ + public static void fill(List l, Object val) + { + ListIterator i = l.listIterator(); + while (i.hasNext()) + { + i.next(); + i.set(val); + } + } + + /** + * Find the maximum element in a Collection, according to the natural + * ordering of the elements. This implementation iterates over the + * Collection, so it works in linear time. + * + * @param c the Collection to find the maximum element of + * @returns the maximum element of c + * @exception NoSuchElementException if c is empty + * @exception ClassCastException if elements in c are not mutually comparable + * @exception NullPointerException if null.compareTo is called + */ + public static Object max(Collection c) + { + Iterator i = c.iterator(); + Comparable max = (Comparable) i.next(); // throws NoSuchElementException + while (i.hasNext()) + { + Object o = i.next(); + if (max.compareTo(o) < 0) + { + max = (Comparable) o; + } + } + return max; + } + + /** + * Find the maximum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the maximum element of + * @param order the Comparator to order the elements by + * @returns the maximum element of c + * @exception NoSuchElementException if c is empty + * @exception ClassCastException if elements in c are not mutually comparable + */ + public static Object max(Collection c, Comparator order) + { + Iterator i = c.iterator(); + Object max = i.next(); // throws NoSuchElementException + while (i.hasNext()) + { + Object o = i.next(); + if (order.compare(max, o) < 0) + { + max = o; + } + } + return max; + } + + /** + * Find the minimum element in a Collection, according to the natural + * ordering of the elements. This implementation iterates over the + * Collection, so it works in linear time. + * + * @param c the Collection to find the minimum element of + * @returns the minimum element of c + * @exception NoSuchElementException if c is empty + * @exception ClassCastException if elements in c are not mutually comparable + * @exception NullPointerException if null.compareTo is called + */ + public static Object min(Collection c) + { + Iterator i = c.iterator(); + Comparable min = (Comparable) i.next(); // throws NoSuchElementException + while (i.hasNext()) + { + Object o = i.next(); + if (min.compareTo(o) > 0) + { + min = (Comparable) o; + } + } + return min; + } + + /** + * Find the minimum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the minimum element of + * @param order the Comparator to order the elements by + * @returns the minimum element of c + * @exception NoSuchElementException if c is empty + * @exception ClassCastException if elements in c are not mutually comparable + */ + public static Object min(Collection c, Comparator order) + { + Iterator i = c.iterator(); + Object min = i.next(); // throws NoSuchElementExcception + while (i.hasNext()) + { + Object o = i.next(); + if (order.compare(min, o) > 0) + { + min = o; + } + } + return min; + } + + /** + * Creates an immutable list consisting of the same object repeated n times. + * The returned object is tiny, consisting of only a single reference to the + * object and a count of the number of elements. It is Serializable. + * + * @param n the number of times to repeat the object + * @param o the object to repeat + * @returns a List consisting of n copies of o + * @throws IllegalArgumentException if n < 0 + */ + // It's not Serializable, because the serialized form is unspecced. + // Also I'm only assuming that it should be because I don't think it's + // stated - I just would be amazed if it isn't... + public static List nCopies(final int n, final Object o) + { + + // Check for insane arguments + if (n < 0) + { + throw new IllegalArgumentException(); + } + + // Create a minimal implementation of List + return new AbstractList() + { + + public int size() + { + return n; + } + + public Object get(int index) + { + if (index < 0 || index >= n) + { + throw new IndexOutOfBoundsException(); + } + return o; + } + }; + } + + /** + * Reverse a given list. This method works in linear time. + * + * @param l the list to reverse. + * @exception UnsupportedOperationException if l.listIterator() does not + * support the set operation. + */ + public static void reverse(List l) + { + ListIterator i1 = l.listIterator(); + ListIterator i2 = l.listIterator(l.size()); + while (i1.nextIndex() < i2.previousIndex()) + { + Object o = i1.next(); + i1.set(i2.previous()); + i2.set(o); + } + } + + /** + * Get a comparator that implements the reverse of natural ordering. This is + * intended to make it easy to sort into reverse order, by simply passing + * Collections.reverseOrder() to the sort method. The return value of this + * method is Serializable. + */ + // The return value isn't Serializable, because the spec is broken. + public static Comparator reverseOrder() + { + return new Comparator() + { + public int compare(Object a, Object b) + { + return -((Comparable) a).compareTo(b); + } + }; + } + + /** + * Shuffle a list according to a default source of randomness. The algorithm + * used would result in a perfectly fair shuffle (that is, each element would + * have an equal chance of ending up in any position) with a perfect source + * of randomness; in practice the results are merely very close to perfect. + *

+ * This method operates in linear time on a random-access list, but may take + * quadratic time on a sequential-access list. + * Note: this (classpath) implementation will never take quadratic time, but + * it does make a copy of the list. This is in line with the behaviour of the + * sort methods and seems preferable. + * + * @param l the list to shuffle. + * @exception UnsupportedOperationException if l.listIterator() does not + * support the set operation. + */ + public static void shuffle(List l) + { + shuffle(l, new Random()); + } + + /** + * Shuffle a list according to a given source of randomness. The algorithm + * used iterates backwards over the list, swapping each element with an + * element randomly selected from the elements in positions less than or + * equal to it (using r.nextInt(int)). + *

+ * This algorithm would result in a perfectly fair shuffle (that is, each + * element would have an equal chance of ending up in any position) if r were + * a perfect source of randomness. In practise (eg if r = new Random()) the + * results are merely very close to perfect. + *

+ * This method operates in linear time on a random-access list, but may take + * quadratic time on a sequential-access list. + * Note: this (classpath) implementation will never take quadratic time, but + * it does make a copy of the list. This is in line with the behaviour of the + * sort methods and seems preferable. + * + * @param l the list to shuffle. + * @param r the source of randomness to use for the shuffle. + * @exception UnsupportedOperationException if l.listIterator() does not + * support the set operation. + */ + public static void shuffle(List l, Random r) + { + Object[] a = l.toArray(); // Dump l into an array + ListIterator i = l.listIterator(l.size()); + + // Iterate backwards over l + while (i.hasPrevious()) + { + + // Obtain a random position to swap with. nextIndex is used so that the + // range of the random number includes the current position. + int swap = r.nextInt(i.nextIndex()); + + // Swap the swapth element of the array with the next element of the + // list. + Object o = a[swap]; + a[swap] = a[i.previousIndex()]; + a[i.previousIndex()] = o; + + // Set the element in the original list accordingly. + i.previous(); + i.set(o); + } + } + + /** + * Obtain an immutable Set consisting of a single element. The return value + * of this method is Serializable. + * + * @param o the single element. + * @returns an immutable Set containing only o. + */ + // It's not serializable because the spec is broken. + public static Set singleton(final Object o) + { + + return new AbstractSet() + { + + public int size() + { + return 1; + } + + public Iterator iterator() + { + return new Iterator() + { + + private boolean hasNext = true; + + public boolean hasNext() + { + return hasNext; + } + + public Object next() + { + if (hasNext) + { + hasNext = false; + return o; + } + else + { + throw new NoSuchElementException(); + } + } + + public void remove() + { + throw new UnsupportedOperationException(); + } + }; + } + }; + } + + /** + * Obtain an immutable List consisting of a single element. The return value + * of this method is Serializable. + * + * @param o the single element. + * @returns an immutable List containing only o. + */ + // It's not serializable because the spec is broken. + public static List singletonList(final Object o) + { + + return new AbstractList() + { + + public int size() + { + return 1; + } + + public Object get(int index) + { + if (index == 0) + { + throw new IndexOutOfBoundsException(); + } + else + { + return o; + } + } + }; + } + + /** + * Obtain an immutable Map consisting of a single key value pair. + * The return value of this method is Serializable. + * + * @param key the single key. + * @param value the single value. + * @returns an immutable Map containing only the single key value pair. + */ + // It's not serializable because the spec is broken. + public static Map singletonMap(final Object key, final Object value) + { + + return new AbstractMap() + { + public Set entrySet() + { + return singleton(new BasicMapEntry(key, value)); + } + }; + } + + /** + * Sort a list according to the natural ordering of its elements. The list + * must be modifiable, but can be of fixed size. The sort algorithm is + * precisely that used by Arrays.sort(Object[]), which offers guaranteed + * nlog(n) performance. This implementation dumps the list into an array, + * sorts the array, and then iterates over the list setting each element from + * the array. + * + * @param l the List to sort + * @exception ClassCastException if some items are not mutually comparable + * @exception UnsupportedOperationException if the List is not modifiable + */ + public static void sort(List l) + { + Object[] a = l.toArray(); + Arrays.sort(a); + ListIterator i = l.listIterator(); + for (int pos = 0; pos < a.length; pos++) + { + i.next(); + i.set(a[pos]); + } + } + + /** + * Sort a list according to a specified Comparator. The list must be + * modifiable, but can be of fixed size. The sort algorithm is precisely that + * used by Arrays.sort(Object[], Comparator), which offers guaranteed + * nlog(n) performance. This implementation dumps the list into an array, + * sorts the array, and then iterates over the list setting each element from + * the array. + * + * @param l the List to sort + * @param c the Comparator specifying the ordering for the elements + * @exception ClassCastException if c will not compare some pair of items + * @exception UnsupportedOperationException if the List is not modifiable + */ + public static void sort(List l, Comparator c) + { + Object[] a = l.toArray(); + Arrays.sort(a, c); + ListIterator i = l.listIterator(); + for (int pos = 0; pos < a.length; pos++) + { + i.next(); + i.set(a[pos]); + } + } + + // All the methods from here on in require doc-comments. + + public static Collection synchronizedCollection(Collection c) + { + return new SynchronizedCollection(c); + } + public static List synchronizedList(List l) + { + return new SynchronizedList(l); + } + public static Map synchronizedMap(Map m) + { + return new SynchronizedMap(m); + } + public static Set synchronizedSet(Set s) + { + return new SynchronizedSet(s); + } + public static SortedMap synchronizedSortedMap(SortedMap m) + { + return new SynchronizedSortedMap(m); + } + public static SortedSet synchronizedSortedSet(SortedSet s) + { + return new SynchronizedSortedSet(s); + } + public static Collection unmodifiableCollection(Collection c) + { + return new UnmodifiableCollection(c); + } + public static List unmodifiableList(List l) + { + return new UnmodifiableList(l); + } + public static Map unmodifiableMap(Map m) + { + return new UnmodifiableMap(m); + } + public static Set unmodifiableSet(Set s) + { + return new UnmodifiableSet(s); + } + public static SortedMap unmodifiableSortedMap(SortedMap m) + { + return new UnmodifiableSortedMap(m); + } + public static SortedSet unmodifiableSortedSet(SortedSet s) + { + return new UnmodifiableSortedSet(s); + } + + // Sun's spec will need to be checked for the precise names of these + // classes, for serializability's sake. However, from what I understand, + // serialization is broken for these classes anyway. + + // Note: although this code is largely uncommented, it is all very + // mechanical and there's nothing really worth commenting. + // When serialization of these classes works, we'll need doc-comments on + // them to document the serialized form. + + private static class UnmodifiableIterator implements Iterator + { + private Iterator i; + + public UnmodifiableIterator(Iterator i) + { + this.i = i; + } + + public Object next() + { + return i.next(); + } + public boolean hasNext() + { + return i.hasNext(); + } + public void remove() + { + throw new UnsupportedOperationException(); + } + } + + private static class UnmodifiableListIterator extends UnmodifiableIterator + implements ListIterator + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private ListIterator li; + + public UnmodifiableListIterator(ListIterator li) + { + super(li); + this.li = li; + } + + public boolean hasPrevious() + { + return li.hasPrevious(); + } + public Object previous() + { + return li.previous(); + } + public int nextIndex() + { + return li.nextIndex(); + } + public int previousIndex() + { + return li.previousIndex(); + } + public void add(Object o) + { + throw new UnsupportedOperationException(); + } + public void set(Object o) + { + throw new UnsupportedOperationException(); + } + } + + private static class UnmodifiableCollection implements Collection, + Serializable + { + Collection c; + + public UnmodifiableCollection(Collection c) + { + this.c = c; + } + + public boolean add(Object o) + { + throw new UnsupportedOperationException(); + } + public boolean addAll(Collection c) + { + throw new UnsupportedOperationException(); + } + public void clear() + { + throw new UnsupportedOperationException(); + } + public boolean contains(Object o) + { + return c.contains(o); + } + public boolean containsAll(Collection c1) + { + return c.containsAll(c1); + } + public boolean isEmpty() + { + return c.isEmpty(); + } + public Iterator iterator() + { + return new UnmodifiableIterator(c.iterator()); + } + public boolean remove(Object o) + { + throw new UnsupportedOperationException(); + } + public boolean removeAll(Collection c) + { + throw new UnsupportedOperationException(); + } + public boolean retainAll(Collection c) + { + throw new UnsupportedOperationException(); + } + public int size() + { + return c.size(); + } + public Object[] toArray() + { + return c.toArray(); + } + public Object[] toArray(Object[]a) + { + return c.toArray(a); + } + } + + private static class UnmodifiableList extends UnmodifiableCollection + implements List + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + List l; + + public UnmodifiableList(List l) + { + super(l); + this.l = l; + } + + public void add(int index, Object o) + { + l.add(index, o); + } + public boolean addAll(int index, Collection c) + { + return l.addAll(index, c); + } + public boolean equals(Object o) + { + return l.equals(o); + } + public Object get(int index) + { + return l.get(index); + } + public int hashCode() + { + return l.hashCode(); + } + public int indexOf(Object o) + { + return l.indexOf(o); + } + public int lastIndexOf(Object o) + { + return l.lastIndexOf(o); + } + public ListIterator listIterator() + { + return new UnmodifiableListIterator(l.listIterator()); + } + public ListIterator listIterator(int index) + { + return new UnmodifiableListIterator(l.listIterator(index)); + } + public Object remove(int index) + { + return l.remove(index); + } + public boolean remove(Object o) + { + return l.remove(o); + } + public Object set(int index, Object o) + { + return l.set(index, o); + } + public List subList(int fromIndex, int toIndex) + { + return new UnmodifiableList(l.subList(fromIndex, toIndex)); + } + } + + private static class UnmodifiableSet extends UnmodifiableCollection + implements Set + { + public UnmodifiableSet(Set s) + { + super(s); + } + public boolean equals(Object o) + { + return c.equals(o); + } + public int hashCode() + { + return c.hashCode(); + } + } + + private static class UnmodifiableSortedSet extends UnmodifiableSet + implements SortedSet + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private SortedSet ss; + + public UnmodifiableSortedSet(SortedSet ss) + { + super(ss); + this.ss = ss; + } + + public Comparator comparator() + { + return ss.comparator(); + } + public Object first() + { + return ss.first(); + } + public Object last() + { + return ss.last(); + } + public SortedSet headSet(Object toElement) + { + return new UnmodifiableSortedSet(ss.headSet(toElement)); + } + public SortedSet tailSet(Object fromElement) + { + return new UnmodifiableSortedSet(ss.tailSet(fromElement)); + } + public SortedSet subSet(Object fromElement, Object toElement) + { + return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement)); + } + } + + private static class UnmodifiableMap implements Map, Serializable + { + + Map m; + + public UnmodifiableMap(Map m) + { + this.m = m; + } + + public void clear() + { + throw new UnsupportedOperationException(); + } + public boolean containsKey(Object key) + { + return m.containsKey(key); + } + public boolean containsValue(Object value) + { + return m.containsValue(value); + } + + // This is one of the ickiest cases of nesting I've ever seen. It just + // means "return an UnmodifiableSet, except that the iterator() method + // returns an UnmodifiableIterator whos next() method returns an + // unmodifiable wrapper around its normal return value". + public Set entrySet() + { + return new UnmodifiableSet(m.entrySet()) + { + public Iterator iterator() + { + return new UnmodifiableIterator(c.iterator()) + { + public Object next() + { + final Map.Entry e = (Map.Entry) super.next(); + return new Map.Entry() + { + public Object getKey() + { + return e.getKey(); + } + public Object getValue() + { + return e.getValue(); + } + public Object setValue(Object value) + { + throw new UnsupportedOperationException(); + } + public int hashCode() + { + return e.hashCode(); + } + public boolean equals(Object o) + { + return e.equals(o); + } + }; + } + }; + } + }; + } + public boolean equals(Object o) + { + return m.equals(o); + } + public Object get(Object key) + { + return m.get(key); + } + public Object put(Object key, Object value) + { + throw new UnsupportedOperationException(); + } + public int hashCode() + { + return m.hashCode(); + } + public boolean isEmpty() + { + return m.isEmpty(); + } + public Set keySet() + { + return new UnmodifiableSet(m.keySet()); + } + public void putAll(Map m) + { + throw new UnsupportedOperationException(); + } + public Object remove(Object o) + { + throw new UnsupportedOperationException(); + } + public int size() + { + return m.size(); + } + public Collection values() + { + return new UnmodifiableCollection(m.values()); + } + } + + private static class UnmodifiableSortedMap extends UnmodifiableMap + implements SortedMap + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private SortedMap sm; + + public UnmodifiableSortedMap(SortedMap sm) + { + super(sm); + this.sm = sm; + } + + public Comparator comparator() + { + return sm.comparator(); + } + public Object firstKey() + { + return sm.firstKey(); + } + public Object lastKey() + { + return sm.lastKey(); + } + public SortedMap headMap(Object toKey) + { + return new UnmodifiableSortedMap(sm.headMap(toKey)); + } + public SortedMap tailMap(Object fromKey) + { + return new UnmodifiableSortedMap(sm.tailMap(fromKey)); + } + public SortedMap subMap(Object fromKey, Object toKey) + { + return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); + } + } + + // All the "Synchronized" wrapper objects include a "sync" field which + // specifies what object to synchronize on. That way, nested wrappers such as + // UnmodifiableMap.keySet synchronize on the right things. + + private static class SynchronizedIterator implements Iterator + { + Object sync; + private Iterator i; + + public SynchronizedIterator(Object sync, Iterator i) + { + this.sync = sync; + this.i = i; + } + + public Object next() + { + synchronized(sync) + { + return i.next(); + } + } + public boolean hasNext() + { + synchronized(sync) + { + return i.hasNext(); + } + } + public void remove() + { + synchronized(sync) + { + i.remove(); + } + } + } + + private static class SynchronizedListIterator extends SynchronizedIterator + implements ListIterator + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private ListIterator li; + + public SynchronizedListIterator(Object sync, ListIterator li) + { + super(sync, li); + this.li = li; + } + + public boolean hasPrevious() + { + synchronized(sync) + { + return li.hasPrevious(); + } + } + public Object previous() + { + synchronized(sync) + { + return li.previous(); + } + } + public int nextIndex() + { + synchronized(sync) + { + return li.nextIndex(); + } + } + public int previousIndex() + { + synchronized(sync) + { + return li.previousIndex(); + } + } + public void add(Object o) + { + synchronized(sync) + { + li.add(o); + } + } + public void set(Object o) + { + synchronized(sync) + { + li.set(o); + } + } + } + + private static class SynchronizedCollection implements Collection, + Serializable + { + Object sync; + Collection c; + + public SynchronizedCollection(Collection c) + { + this.sync = this; + this.c = c; + } + public SynchronizedCollection(Object sync, Collection c) + { + this.c = c; + this.sync = sync; + } + + public boolean add(Object o) + { + synchronized(sync) + { + return c.add(o); + } + } + public boolean addAll(Collection col) + { + synchronized(sync) + { + return c.addAll(col); + } + } + public void clear() + { + synchronized(sync) + { + c.clear(); + } + } + public boolean contains(Object o) + { + synchronized(sync) + { + return c.contains(o); + } + } + public boolean containsAll(Collection c1) + { + synchronized(sync) + { + return c.containsAll(c1); + } + } + public boolean isEmpty() + { + synchronized(sync) + { + return c.isEmpty(); + } + } + public Iterator iterator() + { + synchronized(sync) + { + return new SynchronizedIterator(sync, c.iterator()); + } + } + public boolean remove(Object o) + { + synchronized(sync) + { + return c.remove(o); + } + } + public boolean removeAll(Collection col) + { + synchronized(sync) + { + return c.removeAll(col); + } + } + public boolean retainAll(Collection col) + { + synchronized(sync) + { + return c.retainAll(col); + } + } + public int size() + { + synchronized(sync) + { + return c.size(); + } + } + public Object[] toArray() + { + synchronized(sync) + { + return c.toArray(); + } + } + public Object[] toArray(Object[]a) + { + synchronized(sync) + { + return c.toArray(a); + } + } + } + + private static class SynchronizedList extends SynchronizedCollection + implements List + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + List l; + + public SynchronizedList(Object sync, List l) + { + super(sync, l); + this.l = l; + } + public SynchronizedList(List l) + { + super(l); + } + + public void add(int index, Object o) + { + synchronized(sync) + { + l.add(index, o); + } + } + public boolean addAll(int index, Collection c) + { + synchronized(sync) + { + return l.addAll(index, c); + } + } + public boolean equals(Object o) + { + synchronized(sync) + { + return l.equals(o); + } + } + public Object get(int index) + { + synchronized(sync) + { + return l.get(index); + } + } + public int hashCode() + { + synchronized(sync) + { + return l.hashCode(); + } + } + public int indexOf(Object o) + { + synchronized(sync) + { + return l.indexOf(o); + } + } + public int lastIndexOf(Object o) + { + synchronized(sync) + { + return l.lastIndexOf(o); + } + } + public ListIterator listIterator() + { + synchronized(sync) + { + return new SynchronizedListIterator(sync, l.listIterator()); + } + } + public ListIterator listIterator(int index) + { + synchronized(sync) + { + return new SynchronizedListIterator(sync, l.listIterator(index)); + } + } + public Object remove(int index) + { + synchronized(sync) + { + return l.remove(index); + } + } + public boolean remove(Object o) + { + synchronized(sync) + { + return l.remove(o); + } + } + public Object set(int index, Object o) + { + synchronized(sync) + { + return l.set(index, o); + } + } + public List subList(int fromIndex, int toIndex) + { + synchronized(sync) + { + return new SynchronizedList(l.subList(fromIndex, toIndex)); + } + } + } + + private static class SynchronizedSet extends SynchronizedCollection + implements Set + { + + public SynchronizedSet(Object sync, Set s) + { + super(sync, s); + } + public SynchronizedSet(Set s) + { + super(s); + } + + public boolean equals(Object o) + { + synchronized(sync) + { + return c.equals(o); + } + } + public int hashCode() + { + synchronized(sync) + { + return c.hashCode(); + } + } + } + + private static class SynchronizedSortedSet extends SynchronizedSet + implements SortedSet + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private SortedSet ss; + + public SynchronizedSortedSet(Object sync, SortedSet ss) + { + super(sync, ss); + this.ss = ss; + } + public SynchronizedSortedSet(SortedSet ss) + { + super(ss); + } + + public Comparator comparator() + { + synchronized(sync) + { + return ss.comparator(); + } + } + public Object first() + { + synchronized(sync) + { + return ss.first(); + } + } + public Object last() + { + synchronized(sync) + { + return ss.last(); + } + } + public SortedSet headSet(Object toElement) + { + synchronized(sync) + { + return new SynchronizedSortedSet(sync, ss.headSet(toElement)); + } + } + public SortedSet tailSet(Object fromElement) + { + synchronized(sync) + { + return new SynchronizedSortedSet(sync, ss.tailSet(fromElement)); + } + } + public SortedSet subSet(Object fromElement, Object toElement) + { + synchronized(sync) + { + return new SynchronizedSortedSet(sync, + ss.subSet(fromElement, toElement)); + } + } + } + + private static class SynchronizedMap implements Map, Serializable + { + + Object sync; + Map m; + + public SynchronizedMap(Object sync, Map m) + { + this.sync = sync; + this.m = m; + } + public SynchronizedMap(Map m) + { + this.m = m; + this.sync = this; + } + + public void clear() + { + synchronized(sync) + { + m.clear(); + } + } + public boolean containsKey(Object key) + { + synchronized(sync) + { + return m.containsKey(key); + } + } + public boolean containsValue(Object value) + { + synchronized(sync) + { + return m.containsValue(value); + } + } + + // This is one of the ickiest cases of nesting I've ever seen. It just + // means "return an SynchronizedSet, except that the iterator() method + // returns an SynchronizedIterator whos next() method returns a + // synchronized wrapper around its normal return value". + public Set entrySet() + { + synchronized(sync) + { + return new SynchronizedSet(sync, m.entrySet()) + { + public Iterator iterator() + { + synchronized(SynchronizedMap.this.sync) + { + return new SynchronizedIterator(SynchronizedMap.this.sync, + c.iterator()) + { + public Object next() + { + synchronized(SynchronizedMap.this.sync) + { + final Map.Entry e = (Map.Entry) super.next(); + return new Map.Entry() + { + public Object getKey() + { + synchronized(SynchronizedMap.this.sync) + { + return e.getKey(); + } + } + public Object getValue() + { + synchronized(SynchronizedMap.this.sync) + { + return e.getValue(); + } + } + public Object setValue(Object value) + { + synchronized(SynchronizedMap.this.sync) + { + return e.setValue(value); + } + } + public int hashCode() + { + synchronized(SynchronizedMap.this.sync) + { + return e.hashCode(); + } + } + public boolean equals(Object o) + { + synchronized(SynchronizedMap.this.sync) + { + return e.equals(o); + } + } + }; + } + } + }; + } + } + }; + } + } + public boolean equals(Object o) + { + synchronized(sync) + { + return m.equals(o); + } + } + public Object get(Object key) + { + synchronized(sync) + { + return m.get(key); + } + } + public Object put(Object key, Object value) + { + synchronized(sync) + { + return m.put(key, value); + } + } + public int hashCode() + { + synchronized(sync) + { + return m.hashCode(); + } + } + public boolean isEmpty() + { + synchronized(sync) + { + return m.isEmpty(); + } + } + public Set keySet() + { + synchronized(sync) + { + return new SynchronizedSet(sync, m.keySet()); + } + } + public void putAll(Map map) + { + synchronized(sync) + { + m.putAll(map); + } + } + public Object remove(Object o) + { + synchronized(sync) + { + return m.remove(o); + } + } + + public int size() + { + synchronized(sync) + { + return m.size(); + } + } + public Collection values() + { + synchronized(sync) + { + return new SynchronizedCollection(sync, m.values()); + } + } + } + + private static class SynchronizedSortedMap extends SynchronizedMap + implements SortedMap + { + + // This is stored both here and in the superclass, to avoid excessive + // casting. + private SortedMap sm; + + public SynchronizedSortedMap(Object sync, SortedMap sm) + { + super(sync, sm); + this.sm = sm; + } + public SynchronizedSortedMap(SortedMap sm) + { + super(sm); + } + + public Comparator comparator() + { + synchronized(sync) + { + return sm.comparator(); + } + } + public Object firstKey() + { + synchronized(sync) + { + return sm.firstKey(); + } + } + public Object lastKey() + { + synchronized(sync) + { + return sm.lastKey(); + } + } + public SortedMap headMap(Object toKey) + { + return new SynchronizedSortedMap(sync, sm.headMap(toKey)); + } + public SortedMap tailMap(Object fromKey) + { + return new SynchronizedSortedMap(sync, sm.tailMap(fromKey)); + } + public SortedMap subMap(Object fromKey, Object toKey) + { + return new SynchronizedSortedMap(sync, sm.subMap(fromKey, toKey)); + } + } +} diff --git a/libjava/java/util/List.java b/libjava/java/util/List.java index ea69217..e3e2617 100644 --- a/libjava/java/util/List.java +++ b/libjava/java/util/List.java @@ -1,47 +1,333 @@ -/* Copyright (C) 2000 Free Software Foundation +/* List.java -- An ordered collection which allows indexed access + Copyright (C) 1998 Free Software Foundation, Inc. - This file is part of libgcj. +This file is part of GNU Classpath. -This software is copyrighted work licensed under the terms of the -Libgcj License. Please consult the file "LIBGCJ_LICENSE" for -details. */ +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +// TO DO: +// ~ Doc comment for the interface itself needs to be put into english. +// ~ Some more @see clauses might be nice. package java.util; /** - * @author Warren Levy - * @date March 16, 2000. - */ -/* Written using on-line Java Platform 1.2 API Specification. - * Status: Believed complete and correct. + * [This is what this doc comment will mention: + * ~ Additional restrictions on some methods. Others included for completeness. + * ~ ListIterator and what it can do + * ~ Positional and iterated access + * ~ search (but linear time) + * ~ be careful when containing self as an element, because equals and hashCode + * loop.] */ - -// JDK1.2 public interface List extends Collection { - public int size(); - public boolean isEmpty(); - public boolean contains(Object o); - public Iterator iterator(); - public Object[] toArray(); - public Object[] toArray(Object[] a); - public boolean add(Object o); - public boolean remove(Object o); - public boolean containsAll(Collection c); - public boolean addAll(Collection c); - public boolean addAll(int index, Collection c); - public boolean removeAll(Collection c); - public boolean retainAll(Collection c); - public void clear(); - public boolean equals(Object o); - public int hashCode(); - public Object get(int index); - public Object set(int index, Object element); - public void add(int index, Object element); - public Object remove(int index); - public int indexOf(Object o); - public int lastIndexOf(Object o); - public ListIterator listIterator(); - public ListIterator listIterator(int index); - public List subList(int fromIndex, int toIndex); + /** + * Insert an element into the list at a given position. + * + * @param index the location to insert the item. + * @param o the object to insert. + * @exception UnsupportedOperationException if this list does not support the + * add operation. + * @exception IndexOutOfBoundsException if index < 0 || index > size() + * @exception ClassCastException if o cannot be added to this list due to its + * type. + * @exception IllegalArgumentException if o cannot be added to this list for + * some other reason. + */ + void add(int index, Object o); + + /** + * Add an element to the end of the list. + * + * @param o the object to add. + * @returns true, as Collection defines this method as returning true if the + * list was modified as a result of this action, and it always is for a + * list. + * @exception UnsupportedOperationException if this list does not support the + * add operation. + * @exception ClassCastException if o cannot be added to this list due to its + * type. + * @exception IllegalArgumentException if o cannot be added to this list for + * some other reason. + */ + boolean add(Object o); + + /** + * Insert the contents of a collection into the list at a given position. + * + * @param index the location to insert the collection. + * @param c the collection to insert. + * @returns true if the list was modified by this action, that is, if c is + * non-empty. + * @exception UnsupportedOperationException if this list does not support the + * addAll operation. + * @exception IndexOutOfBoundsException if index < 0 || index > size() + * @exception ClassCastException if some element of c cannot be added to this + * list due to its type. + * @exception IllegalArgumentException if some element of c cannot be added + * to this list for some other reason. + */ + boolean addAll(int index, Collection c); + + /** + * Add the contents of a collection to the end of the list. + * + * @param c the collection to add. + * @returns true if the list was modified by this action, that is, if c is + * non-empty. + * @exception UnsupportedOperationException if this list does not support the + * addAll operation. + * @exception ClassCastException if some element of c cannot be added to this + * list due to its type. + * @exception IllegalArgumentException if some element of c cannot be added + * to this list for some other reason. + */ + boolean addAll(Collection c); + + /** + * Clear the list, such that a subsequent call to isEmpty() would return + * true. + * + * @exception UnsupportedOperationException if this list does not support the + * clear operation. + */ + void clear(); + + /** + * Test whether this list contains a given object as one of its elements. + * + * @param o the element to look for. + * @returns true if this list contains an element e such that o == + * null ? e == null : o.equals(e). + */ + boolean contains(Object o); + + /** + * Test whether this list contains every element in a given collection. + * + * @param c the collection to test for. + * @returns true if for every element o in c, contains(o) would return true. + */ + boolean containsAll(Collection c); + + /** + * Test whether this list is equal to another object. A List is defined to be + * equal to an object if and only if that object is also a List, and the two + * lists are equal. Two lists l1 and l2 are defined to be equal if and only + * if l1.size() == l2.size(), and for every integer n between 0 + * and l1.size() - 1 inclusive, l1.get(n) == null ? + * l2.get(n) == null : l1.get(n).equals(l2.get(n)). + * + * @param o the object to test for equality with this list. + * @returns true if o is equal to this list. + */ + boolean equals(Object o); + + /** + * Get the element at a given index in this list. + * + * @param index the index of the element to be returned. + * @returns the element at index index in this list. + * @exception IndexOutOfBoundsException if index < 0 || index >= size() + */ + Object get(int index); + + /** + * Obtain a hash code for this list. In order to obey the general contract of + * the hashCode method of class Object, this value is calculated as follows: + * 

+   *   hashCode = 1;
+   *   Iterator i = list.iterator();
+   *   while (i.hasNext()) {
+   *     Object obj = i.next();
+   *     hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
+   *   }
+   *
+ * This ensures that the general contract of Object.hashCode() is adhered to. + * + * @returns the hash code of this list. + */ + int hashCode(); + + /** + * Obtain the first index at which a given object is to be found in this + * list. + * + * @returns the least integer n such that o == null ? get(n) == null : + * o.equals(get(n)), or -1 if there is no such index. + */ + int indexOf(Object o); + + /** + * Test whether this list is empty, that is, if size() == 0. + * + * @returns true if this list contains no elements. + */ + boolean isEmpty(); + + /** + * Obtain an Iterator over this list. + * + * @returns an Iterator over the elements of this list, in order. + */ + Iterator iterator(); + + /** + * Obtain the last index at which a given object is to be found in this + * list. + * + * @returns the greatest integer n such that o == null ? get(n) == null + * : o.equals(get(n)). + */ + int lastIndexOf(Object o); + + /** + * Obtain a ListIterator over this list, starting at the beginning. + * + * @returns a ListIterator over the elements of this list, in order, starting + * at the beginning. + */ + ListIterator listIterator(); + + /** + * Obtain a ListIterator over this list, starting at a given position. + * + * @param index the position, between 0 and size() inclusive, to begin the + * iteration from. + * @returns a ListIterator over the elements of this list, in order, starting + * at index. + * @exception IndexOutOfBoundsException if index < 0 || index > size() + */ + ListIterator listIterator(int index); + + /** + * Remove the element at a given position in this list. + * + * @param index the position within the list of the object to remove. + * @returns the object that was removed. + * @exception UnsupportedOperationException if this list does not support the + * remove operation. + * @exception IndexOutOfBoundsException if index < 0 || index > size() + */ + Object remove(int index); + + /** + * Remove the first occurence of an object from this list. That is, remove + * the first element e such that o == null ? e == null : + * o.equals(e). + * + * @param o the object to remove. + * @returns true if the list changed as a result of this call, that is, if + * the list contained at least one occurrence of o. + * @exception UnsupportedOperationException if this list does not support the + * remove operation. + */ + boolean remove(Object o); + + /** + * Remove all elements of a given collection from this list. That is, remove + * every element e such that c.contains(e). + * + * @returns true if this list was modified as a result of this call. + * @exception UnsupportedOperationException if this list does not support the + * removeAll operation. + */ + boolean removeAll(Collection c); + + /** + * Remove all elements of this list that are not contained in a given + * collection. That is, remove every element e such that !c.contains(e). + * + * @returns true if this list was modified as a result of this call. + * @exception UnsupportedOperationException if this list does not support the + * retainAll operation. + */ + boolean retainAll(Collection c); + + /** + * Replace an element of this list with another object. + * + * @param index the position within this list of the element to be replaced. + * @param o the object to replace it with. + * @returns the object that was replaced. + * @exception UnsupportedOperationException if this list does not support the + * set operation. + * @exception IndexOutOfBoundsException if index < 0 || index >= size() + * @exception ClassCastException if o cannot be added to this list due to its + * type. + * @exception IllegalArgumentException if o cannot be added to this list for + * some other reason. + */ + Object set(int index, Object o); + + /** + * Get the number of elements in this list. + * + * @returns the number of elements in the list. + */ + int size(); + + /** + * Obtain a List view of a subsection of this list, from fromIndex + * (inclusive) to toIndex (exclusive). The returned list should be modifiable + * if and only if this list is modifiable. Changes to the returned list + * should be reflected in this list. If this list is structurally modified in + * any way other than through the returned list, the result of any subsequent + * operations on the returned list is undefined. + * + * @param fromIndex the index that the returned list should start from + * (inclusive). + * @param toIndex the index that the returned list should go to (exclusive). + * @returns a List backed by a subsection of this list. + * @exception IndexOutOfBoundsException if fromIndex < 0 || toIndex > size() + * || fromIndex > toIndex. + */ + List subList(int fromIndex, int toIndex); + + /** + * Copy the current contents of this list into an array. + * + * @returns an array of type Object[] and length equal to the length of this + * list, containing the elements currently in this list, in order. + */ + Object[] toArray(); + + /** + * Copy the current contents of this list into an array. If the array passed + * as an argument has length less than that of this list, an array of the + * same run-time type as a, and length equal to the length of this list, is + * allocated using Reflection. Otherwise, a itself is used. The elements of + * this list are copied into it, and if there is space in the array, the + * following element is set to null. The resultant array is returned. + * Note: The fact that the following element is set to null is only useful + * if it is known that this list does not contain any null elements. + * + * @param a the array to copy this list into. + * @returns an array containing the elements currently in this list, in + * order. + * @exception ArrayStoreException if the type of any element of the + * collection is not a subtype of the element type of a. + */ + Object[] toArray(Object[] a); } diff --git a/libjava/java/util/SimpleTimeZone.java b/libjava/java/util/SimpleTimeZone.java index 4fc05e4..685949c 100644 --- a/libjava/java/util/SimpleTimeZone.java +++ b/libjava/java/util/SimpleTimeZone.java @@ -763,7 +763,7 @@ public class SimpleTimeZone extends TimeZone else { int length = input.readInt(); - byte[]byteArray = new byte[length]; + byte[] byteArray = new byte[length]; input.read(byteArray, 0, length); if (length >= 4) { diff --git a/libjava/java/util/Vector.java b/libjava/java/util/Vector.java index 81178bf..2fcc029 100644 --- a/libjava/java/util/Vector.java +++ b/libjava/java/util/Vector.java @@ -1,463 +1,757 @@ -/* Copyright (C) 1998, 1999, 2000 Free Software Foundation +/* Vector.java -- Class that provides growable arrays. + Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. - This file is part of libgcj. +This file is part of GNU Classpath. -This software is copyrighted work licensed under the terms of the -Libgcj License. Please consult the file "LIBGCJ_LICENSE" for -details. */ +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. -package java.util; +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + +package java.util; +import java.lang.reflect.Array; import java.io.Serializable; /** - * @author Warren Levy - * @date August 17, 1998. + * the Vector classes implements growable arrays of Objects. + * You can access elements in a Vector with an index, just as you + * can in a built in array, but Vectors can grow and shrink to accomodate + * more or fewer objects. + * + * Vectors try to mantain efficiency in growing by having a + * capacityIncrement that can be specified at instantiation. + * When a Vector can no longer hold a new Object, it grows by the amount + * in capacityIncrement. + * + * Vector implements the JDK 1.2 List interface, and is therefor a fully + * compliant Collection object. + * + * @specnote The JCL claims that various methods in this class throw + * IndexOutOfBoundsException, which would be consistent with other collections + * classes. ArrayIndexOutOfBoundsException is actually thrown, per the online + * docs, even for List method implementations. + * + * @author Scott G. Miller */ -/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 - * "The Java Language Specification", ISBN 0-201-63451-1 - * plus online API docs for JDK 1.2 beta from http://www.javasoft.com. - * Status: Believed complete and correct - */ - -final class VectorEnumeration implements Enumeration +public class Vector extends AbstractList + implements List, Cloneable, Serializable { - private int enumIndex; - private Vector enumVec; + /** + * The amount the Vector's internal array should be increased in size when + * a new element is added that exceeds the current size of the array, + * or when {@link #ensureCapacity} is called. + * @serial + */ + protected int capacityIncrement = 0; + + /** + * The number of elements currently in the vector, also returned by + * {@link #size}. + * @serial + */ + protected int elementCount = 0; + + /** + * The internal array used to hold members of a Vector + * @serial + */ + protected Object[] elementData; - public VectorEnumeration(Vector vec) - { - enumVec = vec; - enumIndex = 0; - } + private static final long serialVersionUID = -2767605614048989439L; - public boolean hasMoreElements() + /** + * Constructs an empty vector with an initial size of 10, and + * a capacity increment of 0 + */ + public Vector() { - return enumIndex < enumVec.size(); + this(10); } - public Object nextElement() + /** + * Constructs a vector containing the contents of Collection, in the + * order given by the collection + * + * @param c A collection of elements to be added to the newly constructed + * vector + */ + public Vector(Collection c) { - if (! (enumIndex < enumVec.size())) - throw new NoSuchElementException(); - - return enumVec.elementData[enumIndex++]; + int csize = c.size(); + elementData = new Object[csize]; + elementCount = csize; + Iterator itr = c.iterator(); + for (int i = 0; i < csize; i++) + { + elementData[i] = itr.next(); + } } -} -// TODO12: -// public class Vector extends AbstractList -// implements List, Cloneable, Serializable - -public class Vector implements Cloneable, Serializable -{ - /* The size of the increment to use when growing this vector. - The default of 0 means to double the capacity when growing. */ - protected int capacityIncrement; - - /* The number of elements currently in elementData */ - protected int elementCount; - - /* The buffer in which elements of this vector are stored */ - protected Object[] elementData; - - private static final long serialVersionUID = -2767605614048989439L; - - public Vector() + /** + * Constructs a Vector with the initial capacity and capacity + * increment specified + * + * @param initialCapacity The initial size of the Vector's internal + * array + * @param capacityIncrement The amount the internal array should be + * increased if necessary + */ + public Vector(int initialCapacity, int capacityIncrement) { - this(10, 0); + elementData = new Object[initialCapacity]; + this.capacityIncrement = capacityIncrement; } - public Vector(int initCap) + /** + * Constructs a Vector with the initial capacity specified + * + * @param initialCapacity The initial size of the Vector's internal array + */ + public Vector(int initialCapacity) { - this(initCap, 0); + elementData = new Object[initialCapacity]; } - public Vector(int initCap, int capIncrement) + /** + * Copies the contents of a provided array into the Vector. If the + * array is too large to fit in the Vector, an ArrayIndexOutOfBoundsException + * is thrown. Old elements in the Vector are overwritten by the new + * elements + * + * @param anArray An array from which elements will be copied into the Vector + * + * @throws ArrayIndexOutOfBoundsException the array being copied + * is larger than the Vectors internal data array + */ + public synchronized void copyInto(Object[] anArray) { - if (initCap < 0) - throw new IllegalArgumentException (); - elementData = new Object[initCap]; - capacityIncrement = capIncrement; - elementCount = 0; + System.arraycopy(elementData, 0, anArray, 0, elementCount); } - public final synchronized void addElement(Object obj) + /** + * Trims the Vector down to size. If the internal data array is larger + * than the number of Objects its holding, a new array is constructed + * that precisely holds the elements. + */ + public synchronized void trimToSize() { - // Make sure there's room for a new element + // Check if the Vector is already trimmed, to save execution time if (elementCount == elementData.length) - ensureCapacity(elementCount+1); + return; + // Guess not - elementData[elementCount++] = obj; + Object[]newArray = new Object[elementCount]; + System.arraycopy(elementData, 0, newArray, 0, elementCount); + elementData = newArray; } - public final int capacity() + /** + * Ensures that minCapacity elements can fit within this Vector. + * If it cannot hold this many elements, the internal data array is expanded + * in the following manner. If the current size plus the capacityIncrement + * is sufficient, the internal array is expanded by capacityIncrement. + * If capacityIncrement is non-positive, the size is doubled. If + * neither is sufficient, the internal array is expanded to size minCapacity + * + * @param minCapacity The minimum capacity the internal array should be + * able to handle after executing this method + */ + public synchronized void ensureCapacity(int minCapacity) { - return elementData.length; - } + modCount++; + if (elementData.length >= minCapacity) + return; - public synchronized Object clone() - { - // New vector needs to have same size, capacity and capacityIncrement - Vector newVec = new Vector(elementData.length, capacityIncrement); + int newCapacity; + if (capacityIncrement <= 0) + newCapacity = elementData.length * 2; + else + newCapacity = elementData.length + capacityIncrement; + + Object[] newArray = new Object[Math.max(newCapacity, minCapacity)]; - System.arraycopy(elementData, 0, newVec.elementData, 0, elementCount); - newVec.elementCount = elementCount; - return newVec; + System.arraycopy(elementData, 0, newArray, 0, elementData.length); + elementData = newArray; } - public final boolean contains(Object obj) + /** + * Explicitly sets the size of the internal data array, copying the + * old values to the new internal array. If the new array is smaller + * than the old one, old values that don't fit are lost. If the new size + * is larger than the old one, the vector is padded with null entries. + * + * @param newSize The new size of the internal array + */ + public synchronized void setSize(int newSize) { - for (int i = 0; i < elementCount; i++) - { - if (obj == null - ? elementData[i] == null - : obj.equals(elementData[i])) - return true; - } - - return false; + modCount++; + Object[] newArray = new Object[newSize]; + System.arraycopy(elementData, 0, newArray, 0, + Math.min(newSize, elementCount)); + elementCount = newSize; + elementData = newArray; } - public final synchronized void copyInto(Object[] objArray) + /** + * Returns the size of the internal data array (not the amount of elements + * contained in the Vector) + * + * @returns capacity of the internal data array + */ + public int capacity() { - System.arraycopy(elementData, 0, objArray, 0, elementCount); + return elementData.length; } - public final synchronized Object elementAt(int idx) + /** + * Returns the number of elements stored in this Vector + * + * @returns the number of elements in this Vector + */ + public int size() { - if (idx < 0 || idx >= size()) - throw new ArrayIndexOutOfBoundsException(); - - return elementData[idx]; + return elementCount; } - public final synchronized Enumeration elements() + /** + * Returns true if this Vector is empty, false otherwise + * + * @returns true if the Vector is empty, false otherwise + */ + public boolean isEmpty() { - return new VectorEnumeration(this); + return elementCount == 0; } - public final synchronized void ensureCapacity(int minCap) + /** + * Searches the vector starting at index for object elem + * and returns the index of the first occurence of this Object. If + * the object is not found, -1 is returned + * + * @param e The Object to search for + * @param index Start searching at this index + * @returns The index of the first occurence of elem, or -1 + * if it is not found + */ + public synchronized int indexOf(Object e, int index) { - // Increasing the vector could make it much larger than minCap; - // e.g. if minCap is just larger than the vector, size may double. - // If someone cares about this possibility they should set capacityIncrement - if (minCap > elementData.length) + for (int i = index; i < elementCount; i++) { - // Increase the vector; double it if capacityIncrement is zero - int newSize = elementData.length; - newSize += - (capacityIncrement > 0) ? capacityIncrement : elementData.length; - - // Make sure newSize is at least minCap - if (newSize < minCap) - newSize = minCap; - - Object[] newArray = new Object[newSize]; - System.arraycopy(elementData, 0, newArray, 0, elementCount); - elementData = newArray; + if (e == null ? elementData[i] == null : e.equals(elementData[i])) + return i; } + return -1; } - public final synchronized Object firstElement() + /** + * Returns the first occurence of elem in the Vector, or -1 if + * elem is not found. + * + * @param elem The object to search for + * @returns The index of the first occurence of elem or -1 if + * not found + */ + public int indexOf(Object elem) { - if (elementCount == 0) - throw new NoSuchElementException(); - - return elementData[0]; + return indexOf(elem, 0); } - public final int indexOf(Object obj) + /** + * Returns true if elem is contained in this Vector, false otherwise. + * + * @param elem The element to check + * @returns true if the object is contained in this Vector, false otherwise + */ + public boolean contains(Object elem) { - return indexOf(obj, 0); + return indexOf(elem, 0) != -1; } - public final synchronized int indexOf(Object obj, int idx) + /** + * Returns the index of the first occurence of elem, when searching + * backwards from index. If the object does not occur in this Vector, + * -1 is returned. + * + * @param eThe object to search for + * @param index The index to start searching in reverse from + * @returns The index of the Object if found, -1 otherwise + */ + public synchronized int lastIndexOf(Object e, int index) { - if (idx < 0) - throw new IllegalArgumentException (); - for (int i = idx; i < elementCount; i++) + if (index >= elementCount) + throw new ArrayIndexOutOfBoundsException(index); + + for (int i = index; i >= 0; i--) { - if (obj == null - ? elementData[i] == null - : obj.equals(elementData[i])) + if (e == null ? elementData[i] == null : e.equals(elementData[i])) return i; } - return -1; } - public final synchronized void insertElementAt(Object obj, int idx) + /** + * Returns the last index of elem within this Vector, or -1 + * if the object is not within the Vector + * + * @param elem The object to search for + * @returns the last index of the object, or -1 if not found + */ + public int lastIndexOf(Object elem) { - if (idx < 0 || idx > size()) - throw new ArrayIndexOutOfBoundsException(); - else if (idx == size()) // Spec says just use addElement() - addElement(obj); - else - { - // Make sure there's room for a new element - if (elementCount == elementData.length) - ensureCapacity(elementCount+1); + return lastIndexOf(elem, elementCount - 1); + } - // Shift the existing elements up and increment elementCount - for (int i = elementCount++; i > idx; --i) - elementData[i] = elementData[i-1]; + /** + * Returns the Object stored at index. If index is out of range + * an ArrayIndexOutOfBoundsException is thrown. + * + * @param index the index of the Object to retrieve + * @returns The object at index + * @throws ArrayIndexOutOfBoundsException index is + * larger than the Vector + */ + public synchronized Object elementAt(int index) + { + //Within the bounds of this Vector does not necessarily mean within + //the bounds of the internal array + if (index >= elementCount) + throw new ArrayIndexOutOfBoundsException(index); - elementData[idx] = obj; - } + return elementData[index]; } - public final boolean isEmpty() + /** + * Returns the first element in the Vector. If there is no first Object + * (The vector is empty), a NoSuchElementException is thrown. + * + * @returns The first Object in the Vector + * @throws NoSuchElementException the Vector is empty + */ + public synchronized Object firstElement() { - return elementCount == 0; + if (elementCount == 0) + throw new NoSuchElementException(); + + return elementAt(0); } - public final synchronized Object lastElement() + /** + * Returns the last element in the Vector. If the Vector has no last element + * (The vector is empty), a NoSuchElementException is thrown. + * + * @returns The last Object in the Vector + * @throws NoSuchElementException the Vector is empty + */ + public synchronized Object lastElement() { if (elementCount == 0) throw new NoSuchElementException(); - return elementData[elementCount - 1]; + return elementAt(elementCount - 1); } - public final int lastIndexOf(Object obj) + /** + * Places obj at index within the Vector. If index + * refers to an index outside the Vector, an ArrayIndexOutOfBoundsException + * is thrown. + * + * @param obj The object to store + * @param index The position in the Vector to store the object + * @throws ArrayIndexOutOfBoundsException the index is out of range + */ + public synchronized void setElementAt(Object obj, int index) { - return lastIndexOf(obj, size()-1); + if ((index < 0) || (index >= elementCount)) + throw new ArrayIndexOutOfBoundsException(index); + + elementData[index] = obj; } - public final synchronized int lastIndexOf(Object obj, int idx) + /** + * Puts element into the Vector at position index and returns + * the Object that previously occupied that position. + * + * @param index The index within the Vector to place the Object + * @param element The Object to store in the Vector + * @returns The previous object at the specified index + * @throws ArrayIndexOutOfBoundsException the index is out of range + * + */ + public synchronized Object set(int index, Object element) { - if (idx < 0) - throw new IllegalArgumentException (); - for (int i = idx; i >= 0; --i) - { - if (obj == null - ? elementData[i] == null - : obj.equals(elementData[i])) - return i; - } + if (index >= elementCount) + throw new ArrayIndexOutOfBoundsException(index); - return -1; + Object temp = elementData[index]; + elementData[index] = element; + return temp; } - public final synchronized void removeAllElements() + /** + * Removes the element at index, and shifts all elements at + * positions greater than index to their index - 1. + * + * @param index The index of the element to remove + */ + public synchronized void removeElementAt(int index) { - // Remove elements now to assist the gc in early cleanup - for (int i = elementCount-1; i >= 0; --i) - elementData[i] = null; - elementCount = 0; + if (index >= elementCount) + throw new ArrayIndexOutOfBoundsException(index); + + modCount++; + elementCount--; + if (index < elementCount) + System.arraycopy(elementData, index + 1, elementData, index, + elementCount - index); + //Delete the last element (which has been copied back one index) + //so it can be garbage collected; + elementData[elementCount] = null; } - public final synchronized boolean removeElement(Object obj) + /** + * Inserts a new element into the Vector at index. Any elements + * at or greater than index are shifted up one position. + * + * @param obj The object to insert + * @param index The index at which the object is inserted + */ + public void insertElementAt(Object obj, int index) { - for (int i = 0; i < elementCount; i++) - { - if (obj == null - ? elementData[i] == null - : obj.equals(elementData[i])) - { - int j; - - // Decrement count first to ensure we don't walk off end of array - --elementCount; - - for (j = i; j < elementCount; j++) - elementData[j] = elementData[j+1]; - - // At this point, j was incrememented and points to old last element - // Remove element now to assist the gc in early cleanup - elementData[j] = null; - return true; - } - } - - return false; + if ((index < 0) || (index > elementCount)) + throw new ArrayIndexOutOfBoundsException(index); + + ensureCapacity(++elementCount); + modCount++; + System.arraycopy(elementData, index, elementData, index + 1, + elementCount - 1 - index); + elementData[index] = obj; } - public final synchronized void removeElementAt(int idx) + /** + * Adds an element to the Vector at the end of the Vector. If the vector + * cannot hold the element with its present capacity, its size is increased + * based on the same rules followed if ensureCapacity was called with the + * argument currentSize+1. + * + * @param obj The object to add to the Vector + */ + public synchronized void addElement(Object obj) { - int i; - - if (idx < 0 || idx >= size()) - throw new ArrayIndexOutOfBoundsException(); - - // Decrement count first to ensure we don't walk off the end of the array - --elementCount; - - for (i = idx; i < elementCount; i++) - elementData[i] = elementData[i+1]; + ensureCapacity(elementCount + 1); + modCount++; + elementData[elementCount++] = obj; + } - // At this point, i was incrememented and now points to the old last element - // Remove element now to assist the gc in early cleanup - elementData[i] = null; + /** + * Removes the first occurence of the given object from the Vector. + * If such a remove was performed (the object was found), true is returned. + * If there was no such object, false is returned. + * + * @param obj The object to remove from the Vector + * @returns true if the Object was in the Vector, false otherwise + */ + public synchronized boolean removeElement(Object obj) + { + int idx = indexOf(obj); + if (idx != -1) + { + removeElementAt(idx); + return true; + } + return false; } - public final synchronized void setElementAt(Object obj, int idx) + /** + * Removes all elements from the Vector. Note that this does not + * resize the internal data array. + */ + public synchronized void removeAllElements() { - if (idx < 0 || idx >= size()) - throw new ArrayIndexOutOfBoundsException(); + modCount++; + if (elementCount == 0) + return; - elementData[idx] = obj; + for (int i = 0; i < elementCount; i++) + { + elementData[i] = null; + } + elementCount = 0; } - public final synchronized void setSize(int newSize) + /** + * Creates a new Vector with the same contents as this one. + */ + public synchronized Object clone() { - if (newSize < 0) - throw new ArrayIndexOutOfBoundsException(); - - // Java Lang Spec p. 658 says to remove the excess elements and discard - // when new size is smaller than old size. - // When truncating, we could alternatively just reset elementCount instead - // of freeing up the memory if the spec hadn't specified. The spec makes - // sense though; if someone cares enough to call a setSize() function - // they probably are doing so to free memory. - if (newSize < elementCount) + try { - elementCount = newSize; - trimToSize(); + Vector clone = (Vector) super.clone(); + clone.elementData = (Object[]) elementData.clone(); + return clone; } - else if (newSize > elementCount) // Skip == case + catch (CloneNotSupportedException ex) { - // TBD: ensureCapacity() may create a vector much larger than newSize; - // do we want to make the vector exactly newSize? Spec is unclear. - ensureCapacity(newSize); - - // Make sure to null out new elements of grown vector - for (int i = elementCount; i < newSize; i++) - elementData[i] = null; - elementCount = newSize; + throw new InternalError(ex.toString()); } } - public final int size() + /** + * Returns an Object array with the contents of this Vector, in the order + * they are stored within this Vector. Note that the Object array returned + * is not the internal data array, and that it holds only the elements + * within the Vector. This is similar to creating a new Object[] with the + * size of this Vector, then calling Vector.copyInto(yourArray). + * + * @returns An Object[] containing the contents of this Vector in order + * + */ + public synchronized Object[] toArray() { - return elementCount; + Object[] newArray = new Object[elementCount]; + copyInto(newArray); + return newArray; } - public final synchronized String toString() + /** + * Returns an array containing the contents of this Vector. + * If the provided array is large enough, the contents are copied + * into that array, and a null is placed in the position size(). + * In this manner, you can obtain the size of a Vector by the position + * of the null element. If the type of the provided array cannot + * hold the elements, an ArrayStoreException is thrown. + * + * If the provided array is not large enough, + * a new one is created with the contents of the Vector, and no null + * element. The new array is of the same runtime type as the provided + * array. + * + * + * @param array An array to copy the Vector into if large enough + * @returns An array with the contents of this Vector in order + * @throws ArrayStoreException the runtime type of the provided array + * cannot hold the elements of the Vector + */ + public synchronized Object[] toArray(Object[] array) { - // Following the Java Lang Spec p. 656 - - // Prepend first element with open bracket - StringBuffer result = new StringBuffer("["); - - if (elementCount > 0) // add first element if one exists - result.append(elementData[0].toString()); - - // Prepend subsequent elements with ", " - for (int i = 1; i < elementCount; i++) - result.append(", ").append(elementData[i].toString()); - - // Append last element with closing bracket - result.append("]"); - return result.toString(); + if (array.length < elementCount) + array = (Object[]) Array.newInstance(array.getClass().getComponentType(), + elementCount); + else + array[elementCount] = null; + System.arraycopy(elementData, 0, array, 0, elementCount); + return array; } - public final synchronized void trimToSize() + /** + * Returns the element at position index + * + * @param index the position from which an element will be retrieved + * @throws ArrayIndexOutOfBoundsException the index is not within the + * range of the Vector + */ + public synchronized Object get(int index) { - // Give up excess storage capacity to save memory - // - // Don't bother checking for the case where size() == the capacity of the - // vector since that is a much less likely case; it's more efficient to - // not do the check and lose a bit of performance in that infrequent case - Object[] newArray = new Object[elementCount]; - System.arraycopy(elementData, 0, newArray, 0, elementCount); - elementData = newArray; + return elementAt(index); } - // TODO12: - // public Vector(Collection c) - // { - // } - - // TODO12: - // public public boolean add(Object o) - // { - // } - - // TODO12: - // public void add(int index, Object element) - // { - // } - - // TODO12: - // public boolean addAll(Collection c) - // { - // } - - // TODO12: - // public boolean addAll(int index, Collection c) - // { - // } - - // TODO12: - // public void clear() - // { - // } + /** + * Removes the given Object from the Vector. If it exists, true + * is returned, if not, false is returned. + * + * @param o The object to remove from the Vector + * @returns true if the Object existed in the Vector, false otherwise + */ + public boolean remove(Object o) + { + return removeElement(o); + } - // TODO12: - // public boolean containsAll(Collection c) - // { - // } + /** + * Adds an object to the Vector. + * + * @param o The element to add to the Vector + */ + public synchronized boolean add(Object o) + { + addElement(o); + return true; + } - // TODO12: - // public boolean equals(Object o) - // { - // } + /** + * Adds an object at the specified index. Elements at or above + * index are shifted up one position. + * + * @param index The index at which to add the element + * @param element The element to add to the Vector + */ + public void add(int index, Object element) + { + insertElementAt(element, index); + } - // TODO12: - // public int hashCode() - // { - // } + /** + * Removes the element at the specified index, and returns it. + * + * @param index The position from which to remove the element + * @returns The object removed + * @throws ArrayIndexOutOfBoundsException the index was out of the range + * of the Vector + */ + public synchronized Object remove(int index) + { + if (index >= elementCount) + throw new ArrayIndexOutOfBoundsException(index); + + Object temp = elementData[index]; + removeElementAt(index); + return temp; + } - // TODO12: - // public Object get(int index) - // { - // } + /** + * Clears all elements in the Vector and sets its size to 0 + */ + public void clear() + { + removeAllElements(); + } - public synchronized boolean remove(Object o) + public synchronized boolean containsAll(Collection c) { - for (int i = 0; i < elementCount; ++i) + Iterator itr = c.iterator(); + int size = c.size(); + for (int pos = 0; pos < size; pos++) { - if (o == null - ? elementData[i] == null - : o.equals (elementData[i])) - { - System.arraycopy (elementData, i, elementData, i + 1, - elementCount - i - 1); - return true; - } + if (!contains(itr.next())) + return false; } - return false; + return true; } - // TODO12: - // public Object remove(int index) - // { - // } + public synchronized boolean addAll(Collection c) + { + return addAll(elementCount, c); + } + + public synchronized boolean removeAll(Collection c) + { + return super.removeAll(c); + } + + public synchronized boolean retainAll(Collection c) + { + return super.retainAll(c); + } - // TODO12: - // public boolean removeAll(Collection c) - // { - // } + public synchronized boolean addAll(int index, Collection c) + { + if (index < 0 || index > elementCount) + throw new ArrayIndexOutOfBoundsException(index); + modCount++; + Iterator itr = c.iterator(); + int csize = c.size(); + + ensureCapacity(elementCount + csize); + int end = index + csize; + if (elementCount > 0 && index != elementCount) + System.arraycopy(elementData, index, elementData, end, csize); + elementCount += csize; + for (; index < end; index++) + { + elementData[index] = itr.next(); + } + return (csize > 0); + } - // TODO12: - // public boolean retainAll(Collection c) - // { - // } + public synchronized boolean equals(Object c) + { + return super.equals(c); + } - // TODO12: - // public Object set(int index, Object element) - // { - // } + public synchronized int hashCode() + { + return super.hashCode(); + } - // TODO12: - // public Object[] toArray() - // { - // } + /** + * Returns a string representation of this Vector in the form + * [element0, element1, ... elementN] + * + * @returns the String representation of this Vector + */ + public synchronized String toString() + { + String r = "["; + for (int i = 0; i < elementCount; i++) + { + r += elementData[i]; + if (i < elementCount - 1) + r += ", "; + } + r += "]"; + return r; + } - // TODO12: - // public Object[] toArray(Object[] a) - // { - // } + /** + * Returns an Enumeration of the elements of this List. + * The Enumeration returned is compatible behavior-wise with + * the 1.1 elements() method, in that it does not check for + * concurrent modification. + * + * @returns an Enumeration + */ + public synchronized Enumeration elements() + { + return new Enumeration() + { + int i = 0; + public boolean hasMoreElements() + { + return (i < elementCount); + } + public Object nextElement() + { + if (i >= elementCount) + throw new NoSuchElementException(); + return (elementAt(i++)); + } + }; + } + + public List subList(int fromIndex, int toIndex) + { + List sub = super.subList(fromIndex, toIndex); + return Collections.synchronizedList(sub); + } + + /** @specnote This is not specified as synchronized in the JCL, but it seems + * to me that is should be. If it isn't, a clear() operation on a sublist + * will not be synchronized w.r.t. the Vector object. + */ + protected synchronized void removeRange(int fromIndex, int toIndex) + { + modCount++; + if (fromIndex != toIndex) + { + System.arraycopy(elementData, toIndex, elementData, fromIndex, + elementCount - toIndex); + elementCount -= (toIndex - fromIndex); + } + } } -- 2.7.4