This is the mail archive of the
java-patches@sources.redhat.com
mailing list for the Java project.
PATCH: java/util/BitSet, java/util/Abstract*, java/util/ArrayList
- To: java-patches at sources dot redhat dot com
- Subject: PATCH: java/util/BitSet, java/util/Abstract*, java/util/ArrayList
- From: Bryce McKinlay <bryce at albatross dot co dot nz>
- Date: Sun, 29 Oct 2000 18:05:38 +1300
I'm checking in my patches for ArrayList and
Abstract{Map,List,Collection,Set,SequentialList} - see the classpath
list for details. I've also merged the libgcj and classpath
implementations of java/util/BitSet. Basically I kept the libgcj
implementation but added the missing JDK 1.2 methods, and merged in the
javadoc from classpath, and fixed a couple of bugs.
regards
[ bryce ]
2000-10-29 Bryce McKinlay <bryce@albatross.co.nz>
* java/util/BitSet.java: Merged with classpath, new JDK 1.2 methods
implemented.
(toString): Declare `bit' as long, not int.
(data): Made package-private, not private.
Index: BitSet.java
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/util/BitSet.java,v
retrieving revision 1.8
diff -u -r1.8 BitSet.java
--- BitSet.java 2000/10/29 04:46:45 1.8
+++ BitSet.java 2000/10/29 04:49:01
@@ -2,7 +2,7 @@
/* Copyright (C) 1998, 1999, 2000 Free Software Foundation
-This file is part of libgcj.
+ This file is part of libgcj.
This software is copyrighted work licensed under the terms of the
Libgcj License. Please consult the file "LIBGCJ_LICENSE" for
@@ -11,32 +11,64 @@
package java.util;
import java.io.Serializable;
-/**
- * @author Tom Tromey <tromey@cygnus.com>
- * @date October 23, 1998.
- */
-
/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
* hashCode algorithm taken from JDK 1.2 docs.
*/
+/**
+ * This class can be thought of in two ways. You can see it as a
+ * vector of bits or as a set of non-negative integers. The name
+ * <code>BitSet</code> is a bit misleading.
+ *
+ * It is implemented by a bit vector, but its equally possible to see
+ * it as set of non-negative integer; each integer in the set is
+ * represented by a set bit at the corresponding index. The size of
+ * this structure is determined by the highest integer in the set.
+ *
+ * You can union, intersect and build (symmetric) remainders, by
+ * invoking the logical operations and, or, andNot, resp. xor.
+ *
+ * This implementation is NOT synchronized against concurrent access from
+ * multiple threads. Specifically, if one thread is reading from a bitset
+ * while another thread is simultaneously modifying it, the results are
+ * undefined.
+ *
+ * @specnote There is some confusion as to whether or not this class should
+ * be synchronized. JDK 1.1 javadocs explicitly state that the
+ * class is NOT synchronized, however the code listed in the JDK 1.3
+ * javadoc for the hashCode() method implies that it is. It is not
+ * stated elsewhere in the 1.2 javadoc that the class is
+ * synchronized, unlike Hashtable and Vector. From an efficiency
+ * perspective, it is very undesirable to synchronize this class
+ * because multiple locks and explicit lock ordering are required
+ * to safely synchronize some methods. For this reason we're going
+ * with the unsynchronized implementation unless the specs are
+ * changed to explicitly say otherwise.
+ *
+ * @author Jochen Hoenicke
+ * @author Tom Tromey <tromey@cygnus.com>
+ * @date October 23, 1998.
+ * @status API complete to JDK 1.3.
+ */
public final class BitSet implements Cloneable, Serializable
{
- public void and(BitSet bs)
- {
- int max = Math.min(bits.length, bs.bits.length);
- int i;
- for (i = 0; i < max; ++i)
- bits[i] &= bs.bits[i];
- for (; i < bits.length; ++i)
- bits[i] = 0;
- }
-
+ /**
+ * Create a new empty bit set.
+ */
public BitSet()
{
this(64);
}
+ /**
+ * Create a new empty bit set, with a given size. This
+ * constructor reserves enough space to represent the integers
+ * from <code>0</code> to <code>nbits-1</code>.
+ * @param nbits the initial size of the bit set.
+ * @throws NegativeArraySizeException if the specified initial
+ * size is negative.
+ * @require nbits >= 0
+ */
public BitSet(int nbits)
{
if (nbits < 0)
@@ -47,6 +79,49 @@
bits = new long[length];
}
+ /**
+ * Performs the logical AND operation on this bit set and the
+ * given <code>set</code>. This means it builds the intersection
+ * of the two sets. The result is stored into this bit set.
+ * @param set the second bit set.
+ * @require set != null
+ */
+ public void and(BitSet bs)
+ {
+ int max = Math.min(bits.length, bs.bits.length);
+ int i;
+ for (i = 0; i < max; ++i)
+ bits[i] &= bs.bits[i];
+ for (; i < bits.length; ++i)
+ bits[i] = 0;
+ }
+
+ /**
+ * Performs the logical AND operation on this bit set and the
+ * complement of the given <code>set</code>. This means it
+ * selects every element in the first set, that isn't in the
+ * second set. The result is stored into this bit set.
+ * @param set the second bit set.
+ * @require set != null
+ * @since JDK1.2
+ */
+ public void andNot(BitSet bs)
+ {
+ int max = Math.min(bits.length, bs.bits.length);
+ int i;
+ for (i = 0; i < max; ++i)
+ bits[i] &= ~bs.bits[i];
+ }
+
+ /**
+ * Removes the integer <code>bitIndex</code> from this set. That is
+ * the corresponding bit is cleared. If the index is not in the set,
+ * this method does nothing.
+ * @param bitIndex a non-negative integer.
+ * @exception ArrayIndexOutOfBoundsException if the specified bit index
+ * is negative.
+ * @require bitIndex >= 0
+ */
public void clear(int pos)
{
if (pos < 0)
@@ -57,6 +132,12 @@
bits[offset] &= ~(1L << bit);
}
+ /**
+ * Create a clone of this bit set, that is an instance of the same
+ * class and contains the same elements. But it doesn't change when
+ * this bit set changes.
+ * @return the clone of this object.
+ */
public Object clone()
{
BitSet bs = new BitSet(bits.length * 64);
@@ -64,6 +145,11 @@
return bs;
}
+ /**
+ * Returns true if the <code>obj</code> is a bit set that contains
+ * exactly the same elements as this bit set, otherwise false.
+ * @return true if obj equals this bit set.
+ */
public boolean equals(Object obj)
{
if (!(obj instanceof BitSet))
@@ -84,6 +170,15 @@
return true;
}
+ /**
+ * Returns true if the integer <code>bitIndex</code> is in this bit
+ * set, otherwise false.
+ * @param bitIndex a non-negative integer
+ * @return the value of the bit at the specified index.
+ * @exception ArrayIndexOutOfBoundsException if the specified bit index
+ * is negative.
+ * @require bitIndex >= 0
+ */
public boolean get(int pos)
{
if (pos < 0)
@@ -98,6 +193,36 @@
return (bits[offset] & (1L << bit)) == 0 ? false : true;
}
+ /**
+ * Returns a hash code value for this bit set. The hash code of
+ * two bit sets containing the same integers is identical. The algorithm
+ * used to compute it is as follows:
+ *
+ * Suppose the bits in the BitSet were to be stored in an array of
+ * long integers called <code>bits</code>, in such a manner that
+ * bit <code>k</code> is set in the BitSet (for non-negative values
+ * of <code>k</code>) if and only if
+ *
+ * <pre>
+ * ((k/64) < bits.length) && ((bits[k/64] & (1L << (bit % 64))) != 0)
+ * </pre>
+ *
+ * Then the following definition of the hashCode method
+ * would be a correct implementation of the actual algorithm:
+ *
+ * <pre>
+ * public int hashCode() {
+ * long h = 1234;
+ * for (int i = bits.length-1; i>=0; i--) {
+ * h ^= bits[i] * (i + 1);
+ * }
+ * return (int)((h >> 32) ^ h);
+ * }
+ * </pre>
+ *
+ * Note that the hash code values changes, if the set is changed.
+ * @return the hash code value for this bit set.
+ */
public int hashCode()
{
long h = 1234;
@@ -106,6 +231,45 @@
return (int) ((h >> 32) ^ h);
}
+ /**
+ * Returns the logical number of bits actually used by this bit
+ * set. It returns the index of the highest set bit plus one.
+ * Note that this method doesn't return the number of set bits.
+ * @return the index of the highest set bit plus one.
+ */
+ public int length()
+ {
+ // Set i to highest index that contains a non-zero value.
+ int i;
+ for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
+ ;
+
+ // if i < 0 all bits are cleared.
+ if (i < 0)
+ return 0;
+
+ // Now determine the exact length.
+ long b = bits[i];
+ int len = (i + 1) * 64;
+ // b >= 0 checks if the highest bit is zero.
+ while (b >= 0)
+ {
+ --len;
+ b <<= 1;
+ }
+
+ return len;
+ }
+
+ /**
+ * Performs the logical OR operation on this bit set and the
+ * given <code>set</code>. This means it builds the union
+ * of the two sets. The result is stored into this bit set, which
+ * grows as necessary.
+ * @param set the second bit set.
+ * @exception OutOfMemoryError if the current set can't grow.
+ * @require set != null
+ */
public void or(BitSet bs)
{
ensure(bs.bits.length - 1);
@@ -114,6 +278,16 @@
bits[i] |= bs.bits[i];
}
+ /**
+ * Add the integer <code>bitIndex</code> to this set. That is
+ * the corresponding bit is set to true. If the index was already in
+ * the set, this method does nothing. The size of this structure
+ * is automatically increased as necessary.
+ * @param bitIndex a non-negative integer.
+ * @exception ArrayIndexOutOfBoundsException if the specified bit index
+ * is negative.
+ * @require bitIndex >= 0
+ */
public void set(int pos)
{
if (pos < 0)
@@ -124,35 +298,58 @@
bits[offset] |= 1L << bit;
}
+ /**
+ * Returns the number of bits actually used by this bit set. Note
+ * that this method doesn't return the number of set bits.
+ * @returns the number of bits currently used.
+ */
public int size()
{
return bits.length * 64;
}
+ /**
+ * Returns the string representation of this bit set. This
+ * consists of a comma separated list of the integers in this set
+ * surrounded by curly braces. There is a space after each comma.
+ * @return the string representation.
+ */
public String toString()
{
- StringBuffer result = new StringBuffer("{");
+ String r = "{";
boolean first = true;
for (int i = 0; i < bits.length; ++i)
{
- int bit = 1;
+ long bit = 1;
long word = bits[i];
+ if (word == 0)
+ continue;
for (int j = 0; j < 64; ++j)
{
if ((word & bit) != 0)
{
if (!first)
- result.append(", ");
- result.append(64 * i + j);
+ r += ", ";
+ r += Integer.toString(64 * i + j);
first = false;
}
bit <<= 1;
}
}
- return result.append("}").toString();
+ return r += "}";
}
+ /**
+ * Performs the logical XOR operation on this bit set and the
+ * given <code>set</code>. This means it builds the symmetric
+ * remainder of the two sets (the elements that are in one set,
+ * but not in the other). The result is stored into this bit set,
+ * which grows as necessary.
+ * @param set the second bit set.
+ * @exception OutOfMemoryError if the current set can't grow.
+ * @require set != null
+ */
public void xor(BitSet bs)
{
ensure(bs.bits.length - 1);
@@ -173,6 +370,7 @@
}
// The actual bits.
- private long[] bits;
+ long[] bits;
+
private static final long serialVersionUID = 7997698588986878753L;
}
2000-10-27 Bryce McKinlay <bryce@albatross.co.nz>
* java/util/AbstractCollection.java (addAll): Use size() instead of
hasNext() in iterator loop.
(clear): Ditto.
(contains): Ditto. Simplify loop.
(containsAll): Ditto.
(remove): Ditto.
(removeAll): Ditto.
(retainAll): Ditto.
(toArray): Ditto.
(toString): Ditto. Use string concatenation operators, not
StringBuffer.
* java/util/AbstractList.java (addAll): Use size() instead of
hasNext() in iterator loop.
(equals): Ditto.
(hashCode): Ditto.
(indexOf): Ditto. Don't take null check outside of the loop.
(iterator): Return an AbstractListItr instead of anonymous class.
(lastIndexOf): Use a for loop bounded by size() instead of
hasPrevious() in iterator loop.
(listIterator): Return an AbstractListItr.
(removeRange): Remove bounds checking code and docs.
(AbstractListItr): New inner class. Code moved here from
listIterator().
(SubList.iterator): Removed. Use default implementation from
AbstractList instead.
(SubList.listIterator): As above.
* java/util/AbstractMap.java (clear): Use a for loop bounded by size()
instead of hasNext() in iterator loop.
(containsValue): Ditto.
(equals): Ditto.
(get): Ditto.
(put): Ditto.
(putAll): Ditto.
(remove): Ditto.
(toString): Ditto. Use string concatenation operators, not
StringBuffer.
* java/util/AbstractSequentialList.java (addAll): Use a for loop
bounded by size() instead of hasNext() in iterator loop.
* java/util/AbstractSet.java (hashCode): Don't catch exception as
part of normal execution flow. Do an explicit null check instead.
* java/util/ArrayList.java (_iSize): Rename to `size'.
(_arData): Rename to `data'.
(get): Check lower bounds also. Simplify IndexOutOfBoundsException
message.
(remove): Ditto.
(removeRange): Make protected. Don't check bounds.
(add): Check lower bounds also. Simplify IndexOutOfBoundsException
message.
(addAll (Collection)): Use a size-bounded for loop instead of hasNext()
check.
(addAll (int, Collection)): Check lower bounds. Simplify exception
string.
(clone): Clone the data array too.
(indexOf): Inline doesEqual().
(lastIndexOf): Ditto.
(clear): Don't set array data to null.
(set): Check lower bounds. Simplify exception string.
(toArray): Correct comment.
(trimToSize): Don't update modCount, this is not a structural change.
Add comment.
Index: AbstractCollection.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractCollection.java,v
retrieving revision 1.6
diff -u -r1.6 AbstractCollection.java
--- AbstractCollection.java 2000/10/26 10:19:00 1.6
+++ AbstractCollection.java 2000/10/27 09:35:22
@@ -1,5 +1,5 @@
/* AbstractCollection.java -- Abstract implementation of most of Collection
- Copyright (C) 1998 Free Software Foundation, Inc.
+ Copyright (C) 1998, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
@@ -85,11 +85,12 @@
*/
public boolean addAll(Collection c)
{
- Iterator i = c.iterator();
+ Iterator itr = c.iterator();
+ int size = c.size();
boolean modified = false;
- while (i.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
- modified |= add(i.next());
+ modified |= add(itr.next());
}
return modified;
}
@@ -106,11 +107,12 @@
*/
public void clear()
{
- Iterator i = iterator();
- while (i.hasNext())
+ Iterator itr = iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
- i.next();
- i.remove();
+ itr.next();
+ itr.remove();
}
}
@@ -127,31 +129,13 @@
*/
public boolean contains(Object o)
{
- Iterator i = iterator();
-
- // This looks crazily inefficient, but it takes the test o==null outside
- // the loop, saving time, and also saves needing to store the result of
- // i.next() each time.
- if (o == null)
+ Iterator itr = iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
- while (i.hasNext())
- {
- if (i.next() == null)
- {
- return true;
- }
- }
+ if (o == null ? itr.next() == null : o.equals(itr.next()))
+ return true;
}
- else
- {
- while (i.hasNext())
- {
- if (o.equals(i.next()))
- {
- return true;
- }
- }
- }
return false;
}
@@ -167,13 +151,12 @@
*/
public boolean containsAll(Collection c)
{
- Iterator i = c.iterator();
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ int size = c.size();
+ for (int pos = 0; pos < size; pos++)
{
- if (!contains(i.next()))
- {
- return false;
- }
+ if (!contains(itr.next()))
+ return false;
}
return true;
}
@@ -208,33 +191,16 @@
*/
public boolean remove(Object o)
{
- Iterator i = iterator();
-
- // This looks crazily inefficient, but it takes the test o==null outside
- // the loop, saving time, and also saves needing to store the result of
- // i.next() each time.
- if (o == null)
+ Iterator itr = iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
- while (i.hasNext())
+ if (o == null ? itr.next() == null : o.equals(itr.next()))
{
- if (i.next() == null)
- {
- i.remove();
- return true;
- }
+ itr.remove();
+ return true;
}
}
- else
- {
- while (i.hasNext())
- {
- if (o.equals(i.next()))
- {
- i.remove();
- return true;
- }
- }
- }
return false;
}
@@ -253,17 +219,18 @@
*/
public boolean removeAll(Collection c)
{
- Iterator i = iterator();
- boolean changed = false;
- while (i.hasNext())
+ Iterator itr = iterator();
+ int size = size();
+ boolean modified = false;
+ for (int pos = 0; pos < size; pos++)
{
- if (c.contains(i.next()))
+ if (c.contains(itr.next()))
{
- i.remove();
- changed = true;
+ itr.remove();
+ modified = true;
}
}
- return changed;
+ return modified;
}
/**
@@ -281,17 +248,18 @@
*/
public boolean retainAll(Collection c)
{
- Iterator i = iterator();
- boolean changed = false;
- while (i.hasNext())
+ Iterator itr = iterator();
+ int size = size();
+ boolean modified = false;
+ for (int pos = 0; pos < size; pos++)
{
- if (!c.contains(i.next()))
+ if (!c.contains(itr.next()))
{
- i.remove();
- changed = true;
+ itr.remove();
+ modified = true;
}
}
- return changed;
+ return modified;
}
/**
@@ -304,11 +272,11 @@
*/
public Object[] toArray()
{
- Object[] a = new Object[size()];
- Iterator i = iterator();
+ Iterator itr = iterator();
+ Object[]a = new Object[size()];
for (int pos = 0; pos < a.length; pos++)
{
- a[pos] = i.next();
+ a[pos] = itr.next();
}
return a;
}
@@ -333,19 +301,20 @@
*/
public Object[] toArray(Object[]a)
{
- final int n = size();
- if (a.length < n)
+ int size = size();
+ if (a.length < size)
{
- a = (Object[])Array.newInstance(a.getClass().getComponentType(), n);
+ a = (Object[])Array.newInstance(a.getClass().getComponentType(),
+ size);
}
- Iterator i = iterator();
- for (int pos = 0; pos < n; pos++)
+ Iterator itr = iterator();
+ for (int pos = 0; pos < size; pos++)
{
- a[pos] = i.next();
+ a[pos] = itr.next();
}
- if (a.length > n)
+ if (a.length > size)
{
- a[n] = null;
+ a[size] = null;
}
return a;
}
@@ -361,19 +330,16 @@
*/
public String toString()
{
- StringBuffer s = new StringBuffer();
- s.append('[');
- Iterator i = iterator();
- boolean more = i.hasNext();
- while (more)
- {
- s.append(i.next());
- if (more = i.hasNext())
- {
- s.append(", ");
- }
+ Iterator itr = iterator();
+ int size = size();
+ String r = "[";
+ for (int pos = 0; pos < size; pos++)
+ {
+ r += itr.next();
+ if (pos < size - 1)
+ r += ", ";
}
- s.append(']');
- return s.toString();
+ r += "]";
+ return r;
}
}
Index: AbstractList.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractList.java,v
retrieving revision 1.10
diff -u -r1.10 AbstractList.java
--- AbstractList.java 2000/10/26 10:19:00 1.10
+++ AbstractList.java 2000/10/27 09:35:22
@@ -67,20 +67,13 @@
public boolean addAll(int index, Collection c)
{
- Iterator i = c.iterator();
- if (i.hasNext())
+ Iterator itr = c.iterator();
+ int size = c.size();
+ for (int pos = 0; pos < size; pos++)
{
- do
- {
- add(index++, i.next());
- }
- while (i.hasNext());
- return true;
+ add(index++, itr.next());
}
- else
- {
- return false;
- }
+ return (size > 0);
}
public void clear()
@@ -91,50 +84,33 @@
public boolean equals(Object o)
{
if (o == this)
- {
- return true;
+ return true;
+ if (!(o instanceof List))
+ return false;
+ int size = size();
+ if (size != ((List) o).size())
+ return false;
+
+ Iterator itr1 = iterator();
+ Iterator itr2 = ((List) o).iterator();
+
+ for (int pos = 0; pos < size; pos++)
+ {
+ Object e = itr1.next();
+ if (e == null ? itr2.next() != null : !e.equals(itr2.next()))
+ return false;
}
- else if (!(o instanceof List))
- {
- return false;
- }
- else
- {
- Iterator i1 = iterator();
- Iterator i2 = ((List) o).iterator();
- while (i1.hasNext())
- {
- if (!i2.hasNext())
- {
- return false;
- }
- else
- {
- Object e = i1.next();
- if (e == null ? i2.next() != null : !e.equals(i2.next()))
- {
- return false;
- }
- }
- }
- if (i2.hasNext())
- {
- return false;
- }
- else
- {
- return true;
- }
- }
+ return true;
}
public int hashCode()
{
int hashCode = 1;
- Iterator i = iterator();
- while (i.hasNext())
+ Iterator itr = iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
- Object obj = i.next();
+ Object obj = itr.next();
hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
}
return hashCode;
@@ -142,221 +118,44 @@
public int indexOf(Object o)
{
- int index = 0;
- ListIterator i = listIterator();
- if (o == null)
- {
- while (i.hasNext())
- {
- if (i.next() == null)
- {
- return index;
- }
- index++;
- }
- }
- else
+ ListIterator itr = listIterator(0);
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
- while (i.hasNext())
- {
- if (o.equals(i.next()))
- {
- return index;
- }
- index++;
- }
+ if (o == null ? itr.next() == null : o.equals(itr.next()))
+ return pos;
}
return -1;
}
public Iterator iterator()
{
- return new Iterator()
- {
- private int knownMod = modCount;
- private int position = 0;
- boolean removed = true;
-
- private void checkMod()
- {
- if (knownMod != modCount)
- {
- throw new ConcurrentModificationException();
- }
- }
-
- public boolean hasNext()
- {
- checkMod();
- return position < size();
- }
-
- public Object next()
- {
- checkMod();
- removed = false;
- try
- {
- return get(position++);
- }
- catch (IndexOutOfBoundsException e)
- {
- throw new NoSuchElementException();
- }
- }
-
- public void remove()
- {
- checkMod();
- if (removed)
- {
- throw new IllegalStateException();
- }
- AbstractList.this.remove(--position);
- knownMod = modCount;
- removed = true;
- }
- };
+ return new AbstractListItr(0);
}
public int lastIndexOf(Object o)
{
- int index = size();
- ListIterator i = listIterator(index);
- if (o == null)
+ int size = size();
+ ListIterator itr = listIterator(size);
+ for (int pos = size; pos > 0; pos--)
{
- while (i.hasPrevious())
- {
- index--;
- if (i.previous() == null)
- {
- return index;
- }
- }
+ if (o == null ? itr.previous() == null : o.equals(itr.previous()))
+ return pos - 1;
}
- else
- {
- while (i.hasPrevious())
- {
- index--;
- if (o.equals(i.previous()))
- {
- return index;
- }
- }
- }
return -1;
}
public ListIterator listIterator()
{
- return listIterator(0);
+ return new AbstractListItr(0);
}
- public ListIterator listIterator(final int index)
+ public ListIterator listIterator(int index)
{
if (index < 0 || index > size())
- {
- throw new IndexOutOfBoundsException();
- }
-
- return new ListIterator()
- {
- private int knownMod = modCount;
- private int position = index;
- private int lastReturned = -1;
-
- private void checkMod()
- {
- if (knownMod != modCount)
- {
- throw new ConcurrentModificationException();
- }
- }
-
- public boolean hasNext()
- {
- checkMod();
- return position < size();
- }
-
- public boolean hasPrevious()
- {
- checkMod();
- return position > 0;
- }
-
- public Object next()
- {
- checkMod();
- if (hasNext())
- {
- lastReturned = position++;
- return get(lastReturned);
- }
- else
- {
- throw new NoSuchElementException();
- }
- }
-
- public Object previous()
- {
- checkMod();
- if (hasPrevious())
- {
- lastReturned = --position;
- return get(lastReturned);
- }
- else
- {
- throw new NoSuchElementException();
- }
- }
-
- public int nextIndex()
- {
- checkMod();
- return position;
- }
-
- public int previousIndex()
- {
- checkMod();
- return position - 1;
- }
-
- public void remove()
- {
- checkMod();
- if (lastReturned < 0)
- {
- throw new IllegalStateException();
- }
- AbstractList.this.remove(lastReturned);
- knownMod = modCount;
- position = lastReturned;
- lastReturned = -1;
- }
-
- public void set(Object o)
- {
- checkMod();
- if (lastReturned < 0)
- {
- throw new IllegalStateException();
- }
- AbstractList.this.set(lastReturned, o);
- }
+ throw new IndexOutOfBoundsException();
- public void add(Object o)
- {
- checkMod();
- AbstractList.this.add(position++, o);
- lastReturned = -1;
- knownMod = modCount;
- }
- };
+ return new AbstractListItr(index);
}
public Object remove(int index)
@@ -378,29 +177,14 @@
*
* @param fromIndex the index, inclusive, to remove from.
* @param toIndex the index, exclusive, to remove to.
- * @exception UnsupportedOperationException if this list does not support
- * the removeRange operation.
- * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex <
- * 0 || toIndex > size().
*/
protected void removeRange(int fromIndex, int toIndex)
{
- if (fromIndex > toIndex)
- {
- throw new IllegalArgumentException();
- }
- else if (fromIndex < 0 || toIndex > size())
- {
- throw new IndexOutOfBoundsException();
- }
- else
+ ListIterator itr = listIterator(fromIndex);
+ for (int index = fromIndex; index < toIndex; index++)
{
- ListIterator i = listIterator(fromIndex);
- for (int index = fromIndex; index < toIndex; index++)
- {
- i.next();
- i.remove();
- }
+ itr.next();
+ itr.remove();
}
}
@@ -415,9 +199,109 @@
throw new IllegalArgumentException();
if (fromIndex < 0 || toIndex > size())
throw new IndexOutOfBoundsException();
+
return new SubList(this, fromIndex, toIndex);
}
+ class AbstractListItr implements ListIterator
+ {
+ private int knownMod = modCount;
+ private int position;
+ private int lastReturned = -1;
+
+ AbstractListItr(int start_pos)
+ {
+ this.position = start_pos;
+ }
+
+ private void checkMod()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean hasNext()
+ {
+ checkMod();
+ return position < size();
+ }
+
+ public boolean hasPrevious()
+ {
+ checkMod();
+ return position > 0;
+ }
+
+ public Object next()
+ {
+ checkMod();
+ if (position < size())
+ {
+ lastReturned = position++;
+ return get(lastReturned);
+ }
+ else
+ {
+ throw new NoSuchElementException();
+ }
+ }
+
+ public Object previous()
+ {
+ checkMod();
+ if (position > 0)
+ {
+ lastReturned = --position;
+ return get(lastReturned);
+ }
+ else
+ {
+ throw new NoSuchElementException();
+ }
+ }
+
+ public int nextIndex()
+ {
+ checkMod();
+ return position;
+ }
+
+ public int previousIndex()
+ {
+ checkMod();
+ return position - 1;
+ }
+
+ public void remove()
+ {
+ checkMod();
+ if (lastReturned < 0)
+ {
+ throw new IllegalStateException();
+ }
+ AbstractList.this.remove(lastReturned);
+ knownMod = modCount;
+ position = lastReturned;
+ lastReturned = -1;
+ }
+
+ public void set(Object o)
+ {
+ checkMod();
+ if (lastReturned < 0)
+ throw new IllegalStateException();
+ AbstractList.this.set(lastReturned, o);
+ }
+
+ public void add(Object o)
+ {
+ checkMod();
+ AbstractList.this.add(position++, o);
+ lastReturned = -1;
+ knownMod = modCount;
+ }
+ } // AbstractList.Iterator
+
static class SubList extends AbstractList
{
private AbstractList backingList;
@@ -432,15 +316,6 @@
size = toIndex - fromIndex;
}
- // Note that within this class two fields called modCount are inherited -
- // one from the superclass, and one from the outer class.
- // The code uses both these two fields and *no other* to provide fail-fast
- // behaviour. For correct operation, the two fields should contain equal
- // values. Therefore, if this.modCount != backingList.modCount, there
- // has been a concurrent modification. This is all achieved purely by using
- // the modCount field, precisely according to the docs of AbstractList.
- // See the methods upMod and checkMod.
-
/**
* This method checks the two modCount fields to ensure that there has
* not been a concurrent modification. It throws an exception if there
@@ -453,9 +328,7 @@
private void checkMod()
{
if (this.modCount != backingList.modCount)
- {
- throw new ConcurrentModificationException();
- }
+ throw new ConcurrentModificationException();
}
/**
@@ -479,9 +352,7 @@
private void checkBoundsInclusive(int index)
{
if (index < 0 || index > size)
- {
- throw new IndexOutOfBoundsException();
- }
+ throw new IndexOutOfBoundsException();
}
/**
@@ -494,9 +365,7 @@
private void checkBoundsExclusive(int index)
{
if (index < 0 || index >= size)
- {
- throw new IndexOutOfBoundsException();
- }
+ throw new IndexOutOfBoundsException();
}
public int size()
@@ -505,114 +374,6 @@
return size;
}
- public Iterator iterator()
- {
- return listIterator();
- }
-
- public ListIterator listIterator(final int index)
- {
- checkMod();
- checkBoundsInclusive(index);
-
- return new ListIterator()
- {
- ListIterator i = backingList.listIterator(index + offset);
- int position = index;
-
- public boolean hasNext()
- {
- checkMod();
- return position < size;
- }
-
- public boolean hasPrevious()
- {
- checkMod();
- return position > 0;
- }
-
- public Object next()
- {
- if (position < size)
- {
- Object o = i.next();
- position++;
- return o;
- }
- else
- {
- throw new NoSuchElementException();
- }
- }
-
- public Object previous()
- {
- if (position > 0)
- {
- Object o = i.previous();
- position--;
- return o;
- }
- else
- {
- throw new NoSuchElementException();
- }
- }
-
- public int nextIndex()
- {
- return offset + i.nextIndex();
- }
-
- public int previousIndex()
- {
- return offset + i.previousIndex();
- }
-
- public void remove()
- {
- i.remove();
- upMod();
- size--;
- position = nextIndex();
- }
-
- public void set(Object o)
- {
- i.set(o);
- }
-
- public void add(Object o)
- {
- i.add(o);
- upMod();
- size++;
- position++;
- }
-
- // Here is the reason why the various modCount fields are mostly
- // ignored in this wrapper listIterator.
- // IF the backing listIterator is failfast, then the following holds:
- // Using any other method on this list will call a corresponding
- // method on the backing list *after* the backing listIterator
- // is created, which will in turn cause a ConcurrentModException
- // when this listIterator comes to use the backing one. So it is
- // implicitly failfast.
- // If the backing listIterator is NOT failfast, then the whole of
- // this list isn't failfast, because the modCount field of the
- // backing list is not valid. It would still be *possible* to
- // make the iterator failfast wrt modifications of the sublist
- // only, but somewhat pointless when the list can be changed under
- // us.
- // Either way, no explicit handling of modCount is needed.
- // However upMod() must be called in add and remove, and size
- // must also be updated in these two methods, since they do not go
- // through the corresponding methods of the subList.
-
- };
- }
-
public Object set(int index, Object o)
{
checkMod();
@@ -670,5 +431,5 @@
size += backingList.size() - s;
return result;
}
- }
+ } // AbstractList.SubList
}
Index: AbstractMap.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractMap.java,v
retrieving revision 1.11
diff -u -r1.11 AbstractMap.java
--- AbstractMap.java 2000/10/26 10:19:00 1.11
+++ AbstractMap.java 2000/10/27 09:35:22
@@ -33,6 +33,15 @@
public abstract class AbstractMap implements Map
{
+ /**
+ * Remove all entries from this Map. This default implementation calls
+ * entrySet().clear().
+ *
+ * @throws UnsupportedOperationException
+ * @specnote The JCL book claims that this implementation always throws
+ * UnsupportedOperationException, while the online docs claim it
+ * calls entrySet().clear(). We take the later to be correct.
+ */
public void clear()
{
entrySet().clear();
@@ -41,30 +50,30 @@
public boolean containsKey(Object key)
{
Object k;
- Iterator entries = entrySet().iterator();
-
- while (entries.hasNext())
+ Set es = entrySet();
+ Iterator entries = es.iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
k = ((Map.Entry) entries.next()).getKey();
if (key == null ? k == null : key.equals(k))
return true;
}
-
return false;
}
public boolean containsValue(Object value)
{
Object v;
- Iterator entries = entrySet().iterator();
-
- while (entries.hasNext())
+ Set es = entrySet();
+ Iterator entries = es.iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
{
v = ((Map.Entry) entries.next()).getValue();
if (value == null ? v == null : value.equals(v))
return true;
}
-
return false;
}
@@ -72,43 +81,37 @@
public boolean equals(Object o)
{
- if (this == o)
+ if (o == this)
return true;
-
- if (o == null || !(o instanceof Map))
+ if (!(o instanceof Map))
return false;
Map m = (Map) o;
- if (m.size() != size())
+ Set s = m.entrySet();
+ Iterator itr = entrySet().iterator();
+ int size = size();
+
+ if (m.size() != size)
return false;
- Object key, value1, value2;
- Map.Entry entry;
- Iterator entries = entrySet().iterator();
- while (entries.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
- entry = (Map.Entry) entries.next();
- key = entry.getKey();
- value1 = entry.getValue();
- value2 = m.get(key);
-
- if (!((value1 == null && value2 == null) || value1.equals(value2)))
+ if (!s.contains(itr.next()))
return false;
}
-
return true;
}
public Object get(Object key)
{
- Object k;
- Map.Entry entry;
- Iterator entries = entrySet().iterator();
+ Set s = entrySet();
+ Iterator entries = s.iterator();
+ int size = size();
- while (entries.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
- entry = (Map.Entry) entries.next();
- k = entry.getKey();
+ Map.Entry entry = (Map.Entry) entries.next();
+ Object k = entry.getKey();
if (key == null ? k == null : key.equals(k))
return entry.getValue();
}
@@ -119,11 +122,12 @@
public int hashCode()
{
int hashcode = 0;
- Iterator entries = entrySet().iterator();
-
- while (entries.hasNext())
- hashcode += entries.next().hashCode();
-
+ Iterator itr = entrySet().iterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
+ {
+ hashcode += itr.next().hashCode();
+ }
return hashcode;
}
@@ -185,7 +189,9 @@
{
Map.Entry entry;
Iterator entries = m.entrySet().iterator();
- while (entries.hasNext())
+ int size = m.size();
+
+ for (int pos = 0; pos < size; pos++)
{
entry = (Map.Entry) entries.next();
put(entry.getKey(), entry.getValue());
@@ -194,17 +200,16 @@
public Object remove(Object key)
{
- Object k, value;
- Map.Entry entry;
Iterator entries = entrySet().iterator();
+ int size = size();
- while (entries.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
- entry = (Map.Entry) entries.next();
- k = entry.getKey();
+ Map.Entry entry = (Map.Entry) entries.next();
+ Object k = entry.getKey();
if (key == null ? k == null : key.equals(k))
{
- value = entry.getValue();
+ Object value = entry.getValue();
entries.remove();
return value;
}
@@ -220,20 +225,17 @@
public String toString()
{
- StringBuffer sb = new StringBuffer("{");
- String comma = "";
Iterator entries = entrySet().iterator();
-
- while (entries.hasNext())
- {
- Map.Entry entry = (Map.Entry) entries.next();
- sb.append(comma).append(entry.getKey()).append('=').append(entry.
- getValue
- ());
- comma = ", ";
+ int size = size();
+ String r = "{";
+ for (int pos = 0; pos < size; pos++)
+ {
+ r += entries.next();
+ if (pos < size - 1)
+ r += ", ";
}
-
- return sb.append('}').toString();
+ r += "}";
+ return r;
}
public Collection values()
Index: AbstractSequentialList.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractSequentialList.java,v
retrieving revision 1.8
diff -u -r1.8 AbstractSequentialList.java
--- AbstractSequentialList.java 2000/10/26 10:19:00 1.8
+++ AbstractSequentialList.java 2000/10/27 09:35:22
@@ -1,5 +1,5 @@
/* AbstractSequentialList.java -- List implementation for sequential access
- Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
@@ -38,6 +38,7 @@
*/
public abstract class AbstractSequentialList extends AbstractList
{
+
/**
* Returns a ListIterator over the list, starting from position index.
* Subclasses must provide an implementation of this method.
@@ -65,24 +66,22 @@
public boolean addAll(int index, Collection c)
{
- boolean changed = false;
+ boolean modified = false;
Iterator ci = c.iterator();
+ int size = c.size();
ListIterator i = listIterator(index);
- while (ci.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
i.add(ci.next());
- changed = true;
}
- return changed;
+ return (size > 0);
}
public Object get(int index)
{
ListIterator i = listIterator(index);
- if (!i.hasNext())
- {
- throw new IndexOutOfBoundsException();
- }
+ if (index < 0 || index > size())
+ throw new IndexOutOfBoundsException();
return i.next();
}
@@ -100,10 +99,8 @@
public Object remove(int index)
{
ListIterator i = listIterator(index);
- if (!i.hasNext())
- {
- throw new IndexOutOfBoundsException();
- }
+ if (index < 0 || index > size())
+ throw new IndexOutOfBoundsException();
Object removed = i.next();
i.remove();
return removed;
@@ -112,10 +109,8 @@
public Object set(int index, Object o)
{
ListIterator i = listIterator(index);
- if (!i.hasNext())
- {
- throw new IndexOutOfBoundsException();
- }
+ if (index < 0 || index > size())
+ throw new IndexOutOfBoundsException();
Object old = i.next();
i.set(o);
return old;
Index: AbstractSet.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractSet.java,v
retrieving revision 1.7
diff -u -r1.7 AbstractSet.java
--- AbstractSet.java 2000/10/26 10:19:00 1.7
+++ AbstractSet.java 2000/10/27 09:35:22
@@ -1,5 +1,5 @@
/* AbstractSet.java -- Abstract implementation of most of Set
- Copyright (C) 1998 Free Software Foundation, Inc.
+ Copyright (C) 1998, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
@@ -38,6 +38,7 @@
*/
public abstract class AbstractSet extends AbstractCollection implements Set
{
+
/**
* Tests whether the given object is equal to this Set. This implementation
* first checks whether this set <em>is</em> the given object, and returns
@@ -51,17 +52,11 @@
public boolean equals(Object o)
{
if (o == this)
- {
- return true;
- }
+ return true;
else if (o instanceof Set && ((Set) o).size() == size())
- {
- return containsAll((Collection) o);
- }
+ return containsAll((Collection) o);
else
- {
- return false;
- }
+ return false;
}
/**
@@ -74,17 +69,14 @@
*/
public int hashCode()
{
+ Iterator itr = iterator();
+ int size = size();
int hash = 0;
- Iterator i = iterator();
- while (i.hasNext())
+ for (int pos = 0; pos < size; pos++)
{
- try
- {
- hash += i.next().hashCode();
- }
- catch (NullPointerException e)
- {
- }
+ Object obj = itr.next();
+ if (obj != null)
+ hash += obj.hashCode();
}
return hash;
}
Index: ArrayList.java
===================================================================
RCS file: /cvs/classpath/java/util/ArrayList.java,v
retrieving revision 1.6
diff -u -r1.6 ArrayList.java
--- ArrayList.java 2000/10/26 10:19:00 1.6
+++ ArrayList.java 2000/10/27 09:35:22
@@ -54,10 +54,10 @@
private static final int DEFAULT_CAPACITY = 16;
/** the number of elements in this list */
- int _iSize;
+ int size;
/** where the data is stored */
- Object[]_arData;
+ Object[] data;
/** used for serialization -- denotes which fields are serialized */
private static final ObjectStreamField[] serialPersistentFields =
@@ -66,11 +66,11 @@
/**
* Construct a new ArrayList with the supplied initial capacity.
*
- * @param iCapacity
+ * @param capacity Initial capacity of this ArrayList
*/
- public ArrayList(int iCapacity)
+ public ArrayList(int capacity)
{
- _arData = new Object[iCapacity];
+ data = new Object[capacity];
}
@@ -87,60 +87,63 @@
* in the supplied Collection; Sun specs say that the initial
* capacity is 110% of the Collection's size.
*
- * @param oCollection the collection whose elements will
- * initialize this list
+ * @param c the collection whose elements will initialize this list
*/
- public ArrayList(Collection oCollection)
+ public ArrayList(Collection c)
{
- this((int) (oCollection.size() * 1.1));
- addAll(oCollection);
+ this((int) (c.size() * 1.1));
+ addAll(c);
}
/**
* Guarantees that this list will have at least enough capacity to
- * hold iMinCapacity elements.
+ * hold minCapacity elements.
*
- * @param iMinCapacity the minimum guaranteed capacity
+ * @specnote This implementation will grow the list to
+ * max(current * 2, minCapacity) if (minCapacity > current). The JCL says
+ * explictly that "this method increases its capacity to minCap", while
+ * the JDK 1.3 online docs specify that the list will grow to at least the
+ * size specified.
+ * @param minCapacity the minimum guaranteed capacity
*/
- public void ensureCapacity(int iMinCapacity)
+ public void ensureCapacity(int minCapacity)
{
- Object[] arNewData;
- int iCapacity = _arData.length;
+ Object[] newData;
+ int current = data.length;
- if (iMinCapacity > iCapacity)
+ if (minCapacity > current)
{
- arNewData = new Object[Math.max((iCapacity * 2), iMinCapacity)];
- System.arraycopy(_arData, 0, arNewData, 0, iCapacity);
- _arData = arNewData;
+ newData = new Object[Math.max((current * 2), minCapacity)];
+ System.arraycopy(data, 0, newData, 0, size);
+ data = newData;
}
}
/**
* Appends the supplied element to the end of this list.
*
- * @param oElement the element to be appended to this list
+ * @param e the element to be appended to this list
*/
- public boolean add(Object oElement)
+ public boolean add(Object e)
{
- ensureCapacity(_iSize + 1);
- _arData[_iSize++] = oElement;
modCount++;
+ ensureCapacity(size + 1);
+ data[size++] = e;
return true;
}
/**
* Retrieves the element at the user-supplied index.
*
- * @param iIndex the index of the element we are fetching
+ * @param index the index of the element we are fetching
* @throws IndexOutOfBoundsException (iIndex < 0) || (iIndex >= size())
*/
- public Object get(int iIndex)
+ public Object get(int index)
{
- if (iIndex >= _iSize)
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "index=" + String.valueOf(iIndex));
- return _arData[iIndex];
+ if (index < 0 || index >= size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ return data[index];
}
/**
@@ -148,7 +151,7 @@
*/
public int size()
{
- return _iSize;
+ return size;
}
/**
@@ -158,65 +161,33 @@
* @return the removed Object
* @throws IndexOutOfBoundsException (iIndex < 0) || (iIndex >= size())
*/
- public Object remove(int iIndex)
+ public Object remove(int index)
{
- Object oResult;
-
- if (iIndex >= _iSize)
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "index=" + String.valueOf(iIndex));
-
- oResult = _arData[iIndex];
-
- if (iIndex != --_iSize)
- System.arraycopy(_arData, (iIndex + 1), _arData, iIndex,
- (_iSize - iIndex));
-
modCount++;
- _arData[_iSize] = null;
-
- return oResult;
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ Object r = data[index];
+ if (index != --size)
+ System.arraycopy(data, (index + 1), data, index, (size - index));
+ data[size] = null;
+ return r;
}
/**
* Removes all elements in the half-open interval [iFromIndex, iToIndex).
*
- * @param iFromIndex the first index which will be removed
- * @param iToIndex one greater than the last index which will be
+ * @param fromIndex the first index which will be removed
+ * @param toIndex one greater than the last index which will be
* removed
*/
- public void removeRange(int iFromIndex, int iToIndex)
+ protected void removeRange(int fromIndex, int toIndex)
{
- int iReduction;
- int i;
-
- if ((iFromIndex >= _iSize) || (iToIndex >= _iSize))
- {
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "indices=" +
- String.valueOf(iFromIndex) + "," +
- String.valueOf(iToIndex));
- }
- else if (iFromIndex > iToIndex)
- {
- throw new IllegalArgumentException("fromIndex(" +
- String.valueOf(iFromIndex) +
- ") > toIndex(" +
- String.valueOf(iToIndex) + ")");
- }
- else if (iFromIndex != iToIndex)
+ modCount++;
+ if (fromIndex != toIndex)
{
- iReduction = iToIndex - iFromIndex;
- System.arraycopy(_arData, (iFromIndex + iReduction), _arData,
- iFromIndex, (_iSize - iFromIndex - iReduction));
- modCount++;
-
- for (i = (iFromIndex + iReduction); i < _iSize; i++)
- _arData[i] = null;
-
- _iSize -= iReduction;
+ System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
+ size -= (fromIndex - toIndex);
}
}
@@ -224,86 +195,68 @@
* Adds the supplied element at the specified index, shifting all
* elements currently at that index or higher one to the right.
*
- * @param iIndex the index at which the element is being added
- * @param oElement the element being added
+ * @param index the index at which the element is being added
+ * @param e the item being added
*/
- public void add(int iIndex, Object oElement)
+ public void add(int index, Object e)
{
- if (iIndex > _iSize)
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "index=" + String.valueOf(iIndex));
-
- ensureCapacity(_iSize + 1);
- System.arraycopy(_arData, iIndex, _arData,
- (iIndex + 1), (_iSize - iIndex));
- _arData[iIndex] = oElement;
- _iSize++;
modCount++;
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ ensureCapacity(size + 1);
+ if (index != size)
+ System.arraycopy(data, index, data, index + 1, size - index);
+ data[index] = e;
+ size++;
}
/**
* Add each element in the supplied Collection to this List.
*
- * @param oCollection a Collection containing elements to be
- * added to this List
+ * @param c a Collection containing elements to be
+ * added to this List
*/
- public boolean addAll(Collection oCollection)
+ public boolean addAll(Collection c)
{
- Iterator itElements;
- int iLen = oCollection.size();
-
- if (iLen > 0)
+ Iterator itr = c.iterator();
+ int csize = c.size();
+ modCount++;
+ ensureCapacity(size + csize);
+ for (int pos = 0; pos < csize; pos++)
{
- ensureCapacity(_iSize + iLen);
- modCount++;
-
- itElements = oCollection.iterator();
-
- while (itElements.hasNext())
- _arData[_iSize++] = itElements.next();
-
- return true;
+ data[size++] = itr.next();
}
- return false;
+ return (csize > 0);
}
/**
* Add all elements in the supplied collection, inserting them beginning
* at the specified index.
*
- * @param iIndex the index at which the elements will be inserted
- * @param oCollection the Collection containing the elements to be
- * inserted
+ * @param index the index at which the elements will be inserted
+ * @param c the Collection containing the elements to be
+ * inserted
*/
- public boolean addAll(int iIndex, Collection oCollection)
+ public boolean addAll(int index, Collection c)
{
- Iterator itElements;
- int iLen;
-
- if (iIndex > _iSize)
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "index=" + String.valueOf(iIndex));
-
- iLen = oCollection.size();
+ Iterator itr = c.iterator();
+ int csize = c.size();
- if (iLen > 0)
+ modCount++;
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ ensureCapacity(size + csize);
+ int end = index + csize;
+ if (size > 0 && index != size)
+ System.arraycopy(data, index, data, end, csize);
+ size += csize;
+ for (; index < end; index++)
{
- ensureCapacity(_iSize + iLen);
-
- System.arraycopy(_arData, iIndex, _arData,
- (iIndex + iLen), (_iSize - iIndex));
- modCount++;
- _iSize += iLen;
-
- itElements = oCollection.iterator();
- while (itElements.hasNext())
- _arData[iIndex++] = itElements.next();
-
- return true;
+ data[index] = itr.next();
}
- return false;
+ return (csize > 0);
}
/**
@@ -311,46 +264,42 @@
*/
public Object clone()
{
- ArrayList oClone;
-
+ ArrayList clone = null;
try
- {
- oClone = (ArrayList) super.clone();
- oClone._arData = _arData;
- oClone._iSize = _iSize;
- }
- catch (CloneNotSupportedException e)
{
- oClone = null;
+ clone = (ArrayList) super.clone();
+ clone.data = new Object[data.length];
+ System.arraycopy(data, 0, clone.data, 0, size);
}
- return oClone;
+ catch (CloneNotSupportedException e) {}
+ return clone;
}
/**
* Returns true iff oElement is in this ArrayList.
*
- * @param oElement the element whose inclusion in the List is being
- * tested
+ * @param e the element whose inclusion in the List is being
+ * tested
*/
- public boolean contains(Object oElement)
+ public boolean contains(Object e)
{
- return (indexOf(oElement) != -1);
+ return (indexOf(e) != -1);
}
/**
* Returns the lowest index at which oElement appears in this List, or
* -1 if it does not appear.
*
- * @param oElement the element whose inclusion in the List is being
- * tested
+ * @param e the element whose inclusion in the List is being
+ * tested
*/
- public int indexOf(Object oElement)
+ public int indexOf(Object e)
{
int i;
- for (i = 0; i < _iSize; i++)
+ for (i = 0; i < size; i++)
{
- if (doesEqual(oElement, _arData[i]))
+ if (e == null ? data[i] == null : e.equals(data[i]))
return i;
}
return -1;
@@ -360,16 +309,16 @@
* Returns the highest index at which oElement appears in this List, or
* -1 if it does not appear.
*
- * @param oElement the element whose inclusion in the List is being
- * tested
+ * @param e the element whose inclusion in the List is being
+ * tested
*/
- public int lastIndexOf(Object oElement)
+ public int lastIndexOf(Object e)
{
int i;
- for (i = _iSize - 1; i >= 0; i--)
+ for (i = size - 1; i >= 0; i--)
{
- if (doesEqual(oElement, _arData[i]))
+ if (e == null ? data[i] == null : e.equals(data[i]))
return i;
}
return -1;
@@ -380,39 +329,28 @@
*/
public void clear()
{
- int i;
-
- if (_iSize > 0)
- {
- modCount++;
- _iSize = 0;
-
- for (i = 0; i < _iSize; i++)
- _arData[i] = null;
- }
+ modCount++;
+ size = 0;
}
/**
* Sets the element at the specified index.
*
- * @param iIndex the index at which the element is being set
- * @param oElement the element to be set
+ * @param index the index at which the element is being set
+ * @param e the element to be set
* @return the element previously at the specified index, or null if
* none was there
*/
- public Object set(int iIndex, Object oElement)
+ public Object set(int index, Object e)
{
- Object oResult;
-
- if (iIndex >= _iSize)
- throw new IndexOutOfBoundsException("ArrayList size=" +
- String.valueOf(_iSize) + "; " +
- "index=" + String.valueOf(iIndex));
- oResult = _arData[iIndex];
+ Object result;
+ if (index < 0 || index >= size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ result = data[index];
// SEH: no structural change, so don't update modCount
- _arData[iIndex] = oElement;
-
- return oResult;
+ data[index] = e;
+ return result;
}
/**
@@ -420,9 +358,9 @@
*/
public Object[] toArray()
{
- Object[] arObjects = new Object[_iSize];
- System.arraycopy(_arData, 0, arObjects, 0, _iSize);
- return arObjects;
+ Object[] array = new Object[size];
+ System.arraycopy(data, 0, array, 0, size);
+ return array;
}
/**
@@ -431,68 +369,61 @@
* 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 <i>larger</i> than the size
- * of this List, then size() + 1 index will be set to null.
+ * of this List, then size() index will be set to null.
*
- * @param arObjects the passed-in Array
+ * @param array the passed-in Array
*/
- public Object[] toArray(Object[]arObjects)
+ public Object[] toArray(Object[] array)
{
- Object[] arReturn = (arObjects.length >= _iSize)
- ? arObjects
- : (Object[])
- Array.newInstance(arObjects.getClass().getComponentType(), _iSize);
-
- System.arraycopy(_arData, 0, arReturn, 0, _iSize);
-
- if (arReturn.length > _iSize)
- arReturn[_iSize] = null;
-
- return arReturn;
+ if (array.length < size)
+ array = (Object[]) Array.newInstance(array.getClass().getComponentType(),
+ size);
+ else if (array.length > size)
+ array[size] = null;
+ System.arraycopy(data, 0, array, 0, size);
+ return array;
}
/**
- * Trims the capacity of tjis List to be equal to its size;
- * a memory saver.
+ * Trims the capacity of this List to be equal to its size;
+ * a memory saver.
*/
public void trimToSize()
{
- Object[] arNewData = new Object[_iSize];
- System.arraycopy(_arData, 0, arNewData, 0, _iSize);
- modCount++;
- _arData = arNewData;
+ // not a structural change from the perspective of iterators on this list,
+ // so don't update modCount
+ Object[] newData = new Object[size];
+ System.arraycopy(data, 0, newData, 0, size);
+ data = newData;
}
- private void writeObject(ObjectOutputStream oOut) throws IOException
+ private void writeObject(ObjectOutputStream out) throws IOException
{
int i;
- ObjectOutputStream.PutField oFields = oOut.putFields();
- oFields.put("size", _iSize);
- oOut.writeFields();
+ ObjectOutputStream.PutField fields = out.putFields();
+ fields.put("size", size);
+ out.writeFields();
- oOut.writeInt(_arData.length);
- for (i = 0; i < _arData.length; i++)
- oOut.writeObject(_arData[i]);
+ // FIXME: Do we really want to serialize unused list entries??
+ out.writeInt(data.length);
+ for (i = 0; i < data.length; i++)
+ out.writeObject(data[i]);
}
- private void readObject(ObjectInputStream oIn)
+ private void readObject(ObjectInputStream in)
throws IOException, ClassNotFoundException
{
int i;
- int iCapacity;
+ int capacity;
- ObjectInputStream.GetField oFields = oIn.readFields();
- _iSize = oFields.get("size", 0);
+ ObjectInputStream.GetField fields = in.readFields();
+ size = fields.get("size", 0);
- iCapacity = oIn.readInt();
- _arData = new Object[iCapacity];
+ capacity = in.readInt();
+ data = new Object[capacity];
- for (i = 0; i < iCapacity; i++)
- _arData[i] = oIn.readObject();
- }
-
- private static final boolean doesEqual(Object oOne, Object oTwo)
- {
- return ((oOne == null) ? (oTwo == null) : oOne.equals(oTwo));
+ for (i = 0; i < capacity; i++)
+ data[i] = in.readObject();
}
}