[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
PATCH for collections classes
|
From: |
Bryce McKinlay |
|
Subject: |
PATCH for collections classes |
|
Date: |
Fri, 27 Oct 2000 23:20:22 +1300 |
As part of my current goal of merging classpath's collections into gcj,
I've started to go through the existing collections code and try to weed
out bugs and inefficiencies where I can see them. So far I've looked at
Abstract{Map,List,Collection,Set,SequentialList} and ArrayList, and this
patch is the result.
Along with various bug fixes and cosmetic changes, the major changes
here are:
1. Change all iterator loops to for-loops bounded by size, instead of
while loops based on hasNext(). This improves the efficiency of many
methods. For example:
Iterator itr = c.iterator();
while (itr.hasNext()
{
... = itr.next();
}
becomes:
Iterator itr = c.iterator();
int size = c.size();
for (int pos = 0; pos < size; pos++)
{
... = itr.next();
}
2. Changed AbstractList to use a single inner class, AbstractListItr,
for all its iterators (including sublist iterators). Firstly, I couldn't
figure out any reason why there needs to be separate Iterator and
Listiterator classes for Lists, given that ListIterator implements
Iterator, so now iterator() just returns a list iterator. Secondly, I
realized that it simplified things greatly to use this same class to
implement the sublist iterators. This is actually more efficient than
the existing implementation, because no "backing iterator" is needed,
and we get correct concurrent modification check semantics for free.
However, I later realised that there *is* one advantage to using a
separate iterator class here: the ability to check the size field of the
sublist directly, rather than going through a virtual call to size(). Is
it worth all the code duplication to get this benefit?
Although I've tested these changes with gcj against example code from
the JCL supplement book, I'd appreciate if you guys could cast an eye
over them and provide some additional sanity checking. Comments welcome.
regards
[ bryce ]
P.S. Could someone send me a copy of the collections test tools
(MapBash, ListBash, etc), from javacollections.org? I can't connect to
that site and can't find my copies.
2000-10-27 Bryce McKinlay <address@hidden>
* 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();
}
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- PATCH for collections classes,
Bryce McKinlay <=