[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
PATCH: More collections List updates
|
From: |
Bryce McKinlay |
|
Subject: |
PATCH: More collections List updates |
|
Date: |
Thu, 02 Nov 2000 23:03:59 +1300 |
Hi,
I have rewritten most of LinkedList. The new implementation is simpler,
faster and conforms to the spec more closely. While working on this I
realised the flaw in my previous change (removal of) the SubList
iterator in AbstractList: Although correct, it resulted in poor
performance for iterators on sublists of linked lists, as the iterator
would ultimately traverse the linked list via its get() method,
requiring quadratic-ish time. The fix was to restore the existing
iterator wrapper approach. A few other minor bugs are also fixed by this
patch.
Unfortunately, gcj can not build AbstractList any more due to a static
inner class bug (specifically, it cant handle the references to modCount
from the Sublist iterator anonymous class). So, what I'm going to do is
commit this patch to both classpath and libgcj, and then comment out the
offending lines in libgcj as a workaround until the compiler is fixed.
regards
[ bryce ]
2000-11-02 Bryce McKinlay <address@hidden>
* java/util/AbstractList.java: Throw messages with
IndexOutOfBoundsExceptions.
(listIterator()): Call listIterator(0).
(size): New field. Initialize to size().
(hasNext): Test position against size, not size().
(remove): Increment knownMod by one instead of resetting it from
modCount.
(add): Ditto.
(SubList.upMod): Removed.
(SubList.set): Don't call upMod() or update knownMod.
(SubList.add(int,Object)): Increment modCount instead of caling upMod().
(SubList.remove): Ditto.
(SubList.addAll): Don't call backingList.size(). Increment size from
c.size().
(SubList.iterator): New method. Call listIterator(0).
(SubList.listIterator): New method. Restore code to return an anonymous
listIterator implementation (with some changes).
* java/util/AbstractSequentialList.java: Throw messages with
IndexOutOfBoundsExceptions.
(addAll): Add a specnote.
* java/util/ArrayList.java (removeRange): Get the math right.
(addAll): Increment modCount _before_ creating iterator.
* java/util/LinkedList.java: Rewritten, mostly.
Index: AbstractList.java
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/util/AbstractList.java,v
retrieving revision 1.2
diff -u -r1.2 AbstractList.java
--- AbstractList.java 2000/10/29 05:06:10 1.2
+++ AbstractList.java 2000/11/02 09:48:01
@@ -145,15 +145,22 @@
return -1;
}
+ /**
+ * Return an Iterator over this List. This implementation calls
+ * listIterator(0).
+ *
+ * @return an Iterator over this List
+ */
public ListIterator listIterator()
{
- return new AbstractListItr(0);
+ return listIterator(0);
}
public ListIterator listIterator(int index)
{
if (index < 0 || index > size())
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size());
return new AbstractListItr(index);
}
@@ -193,10 +200,10 @@
throw new UnsupportedOperationException();
}
- public List subList(final int fromIndex, final int toIndex)
+ public List subList(int fromIndex, int toIndex)
{
if (fromIndex > toIndex)
- throw new IllegalArgumentException();
+ throw new IllegalArgumentException(fromIndex + " > " + toIndex);
if (fromIndex < 0 || toIndex > size())
throw new IndexOutOfBoundsException();
@@ -208,6 +215,7 @@
private int knownMod = modCount;
private int position;
private int lastReturned = -1;
+ private int size = size();
AbstractListItr(int start_pos)
{
@@ -223,7 +231,7 @@
public boolean hasNext()
{
checkMod();
- return position < size();
+ return position < size;
}
public boolean hasPrevious()
@@ -235,7 +243,7 @@
public Object next()
{
checkMod();
- if (position < size())
+ if (position < size)
{
lastReturned = position++;
return get(lastReturned);
@@ -280,7 +288,7 @@
throw new IllegalStateException();
}
AbstractList.this.remove(lastReturned);
- knownMod = modCount;
+ knownMod++;
position = lastReturned;
lastReturned = -1;
}
@@ -298,7 +306,7 @@
checkMod();
AbstractList.this.add(position++, o);
lastReturned = -1;
- knownMod = modCount;
+ knownMod++;
}
} // AbstractList.Iterator
@@ -311,7 +319,9 @@
public SubList(AbstractList backing, int fromIndex, int toIndex)
{
backingList = backing;
- upMod();
+ // FIXME: The `this' prefixes in this class are a workaround for a
+ // gcj bug. They should be removed later.
+ this.modCount = backingList.modCount;
offset = fromIndex;
size = toIndex - fromIndex;
}
@@ -332,17 +342,6 @@
}
/**
- * This method is called after every method that causes a structural
- * modification to the backing list. It updates the local modCount field
- * to match that of the backing list.
- * Note that since this method is private, it will be inlined.
- */
- private void upMod()
- {
- this.modCount = backingList.modCount;
- }
-
- /**
* This method checks that a value is between 0 and size (inclusive). If
* it is not, an exception is thrown.
* Note that since this method is private, it will be inlined.
@@ -352,7 +351,8 @@
private void checkBoundsInclusive(int index)
{
if (index < 0 || index > size)
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
}
/**
@@ -365,7 +365,8 @@
private void checkBoundsExclusive(int index)
{
if (index < 0 || index >= size)
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
}
public int size()
@@ -379,7 +380,6 @@
checkMod();
checkBoundsExclusive(index);
o = backingList.set(index + offset, o);
- upMod();
return o;
}
@@ -395,7 +395,7 @@
checkMod();
checkBoundsInclusive(index);
backingList.add(index + offset, o);
- upMod();
+ this.modCount++;
size++;
}
@@ -404,7 +404,7 @@
checkMod();
checkBoundsExclusive(index);
Object o = backingList.remove(index + offset);
- upMod();
+ this.modCount++;
size--;
return o;
}
@@ -417,19 +417,122 @@
// this call will catch the toIndex < fromIndex condition
backingList.removeRange(offset + fromIndex, offset + toIndex);
- upMod();
+ this.modCount = backingList.modCount;
size -= toIndex - fromIndex;
}
-
+
public boolean addAll(int index, Collection c)
{
checkMod();
checkBoundsInclusive(index);
- int s = backingList.size();
+ int csize = c.size();
boolean result = backingList.addAll(offset + index, c);
- upMod();
- size += backingList.size() - s;
+ this.modCount = backingList.modCount;
+ size += csize;
return result;
+ }
+
+ public Iterator iterator()
+ {
+ return listIterator(0);
+ }
+
+ 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();
+ SubList.this.modCount++;
+ size--;
+ position = nextIndex();
+ }
+
+ public void set(Object o)
+ {
+ i.set(o);
+ }
+
+ public void add(Object o)
+ {
+ i.add(o);
+ SubList.this.modCount++;
+ 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 modCount++ must be executed 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.
+ };
}
- } // AbstractList.SubList
+ } // AbstractList.SubList
}
Index: AbstractSequentialList.java
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/util/AbstractSequentialList.java,v
retrieving revision 1.2
diff -u -r1.2 AbstractSequentialList.java
--- AbstractSequentialList.java 2000/10/29 05:06:10 1.2
+++ AbstractSequentialList.java 2000/11/02 09:48:01
@@ -64,6 +64,12 @@
i.add(o);
}
+ /**
+ * @specnote The spec in the JDK1.3 online docs is wrong. The implementation
+ * should not call next() to skip over new elements as they are
+ * added, because iterator.add() should add new elements BEFORE
+ * the cursor.
+ */
public boolean addAll(int index, Collection c)
{
boolean modified = false;
@@ -81,7 +87,8 @@
{
ListIterator i = listIterator(index);
if (index < 0 || index > size())
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size());
return i.next();
}
@@ -100,7 +107,8 @@
{
ListIterator i = listIterator(index);
if (index < 0 || index > size())
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size());
Object removed = i.next();
i.remove();
return removed;
@@ -110,7 +118,8 @@
{
ListIterator i = listIterator(index);
if (index < 0 || index > size())
- throw new IndexOutOfBoundsException();
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size());
Object old = i.next();
i.set(o);
return old;
Index: ArrayList.java
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/util/ArrayList.java,v
retrieving revision 1.2
diff -u -r1.2 ArrayList.java
--- ArrayList.java 2000/10/29 05:06:10 1.2
+++ ArrayList.java 2000/11/02 09:48:01
@@ -187,7 +187,7 @@
if (fromIndex != toIndex)
{
System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
- size -= (fromIndex - toIndex);
+ size -= (toIndex - fromIndex);
}
}
@@ -219,9 +219,9 @@
*/
public boolean addAll(Collection c)
{
+ modCount++;
Iterator itr = c.iterator();
int csize = c.size();
- modCount++;
ensureCapacity(size + csize);
for (int pos = 0; pos < csize; pos++)
{
@@ -240,13 +240,13 @@
*/
public boolean addAll(int index, Collection c)
{
- Iterator itr = c.iterator();
- int csize = c.size();
-
- modCount++;
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
size);
+ modCount++;
+ Iterator itr = c.iterator();
+ int csize = c.size();
+
ensureCapacity(size + csize);
int end = index + csize;
if (size > 0 && index != size)
Index: LinkedList.java
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/util/LinkedList.java,v
retrieving revision 1.1
diff -u -r1.1 LinkedList.java
--- LinkedList.java 2000/08/27 22:06:44 1.1
+++ LinkedList.java 2000/11/02 09:48:01
@@ -7,7 +7,7 @@
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
-
+
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
@@ -30,16 +30,17 @@
import java.io.ObjectOutputStream;
import java.io.ObjectInputStream;
import java.io.IOException;
+import java.lang.reflect.Array;
// TO DO:
// ~ Doc comment for the class.
// ~ Doc comments for the non-list methods.
-// ~ Some commenting on the Backing API and other general implementation notes.
+// ~ other general implementation notes.
/**
* Linked list implementation of the List interface.
*/
-public class LinkedList extends AbstractSequentialList
+public class LinkedList extends AbstractSequentialList
implements Serializable, Cloneable
{
static final long serialVersionUID = 876323262645176354L;
@@ -49,7 +50,8 @@
* previous field) of the list. The data field is null. If the list is empty,
* both the head and the tail point to ends itself.
*/
- transient Entry ends = new Entry();
+ transient Entry first;
+ transient Entry last;
/**
* The current length of the list.
@@ -59,260 +61,86 @@
/**
* Class to represent an entry in the list. Holds a single element.
*/
- private static class Entry {
-
- /**
- * The list element.
- */
- Object data = null;
-
- /**
- * The next entry in the list. If this is the last entry in the list, the
- * ends field of the list is held here.
- */
+ private static class Entry
+ {
+ Object data;
Entry next;
-
- /**
- * The previous entry in the list. If this is the first entry in the list,
- * the ends field of the list is held here.
- */
Entry previous;
-
- /**
- * Create an entry with given data and linkage.
- */
- Entry(Object d, Entry n, Entry p) {
- data = d;
- next = n;
- previous = p;
+
+ Entry(Object data)
+ {
+ this.data = data;
}
-
- /**
- * Create an entry with no data and linking to itself, for use as the ends
- * field of the list.
- */
- Entry() {
- next = previous = this;
- }
-
- /**
- * Remove this entry.
- */
- Object remove() {
- previous.next = next;
- next.previous = previous;
- return data;
- }
- }
-
- private static interface Backing {
- void checkMod(int known);
- void upMod();
- void incSize(int by);
- void decSize(int by);
}
-
- private final Backing back = new Backing() {
- public void checkMod(int known) {
- if (known != modCount) {
- throw new ConcurrentModificationException();
- }
- }
- public void upMod() {
- modCount++;
- }
- public void incSize(int by) {
- size += by;
- }
- public void decSize(int by) {
- size -= by;
- }
- };
-
- /** A ListIterator over the list. This class keeps track of its
- * position in the list, the size of the list, and the two list
- * entries it is between. This enables it to be used identically
- * for both the list itself and a sublist of the list.
- */
- private static class Iter implements ListIterator {
-
- /**
- * The index of the element that will be returned by next().
- */
- int pos;
-
- /**
- * The size of the backing list.
- */
- int size;
-
- /**
- * The entry containing the element that will be returned by next().
- */
- Entry next;
-
- /**
- * The entry containing the element that will be returned by previous().
- */
- Entry previous;
-
- /**
- * The entry that will be affected by remove() or set().
- */
- Entry recent;
-
- /**
- * The known value of the modCount of the backing list.
- */
- int knownMod;
-
- private final Backing b;
-
- /**
- * Create a new Iter starting at a given Entry within the list, at a given
- * position, in a list of given size.
- *
- * @param index the index to begin iteration.
- * @exception IndexOutOfBoundsException if index < 0 || index > size.
- */
- Iter(Backing backing, Entry n, int index, int s, int modCount) {
- b = backing;
- pos = index;
- size = s;
- next = n;
- previous = n.previous;
- knownMod = modCount;
- }
-
- public int nextIndex() {
- b.checkMod(knownMod);
- return pos;
- }
-
- public int previousIndex() {
- b.checkMod(knownMod);
- return pos - 1;
- }
-
- public boolean hasNext() {
- b.checkMod(knownMod);
- return pos < size;
- }
-
- public boolean hasPrevious() {
- b.checkMod(knownMod);
- return pos > 0;
- }
-
- public Object next() {
- b.checkMod(knownMod);
- if (pos >= size) {
- throw new NoSuchElementException();
- } else {
- pos++;
- recent = previous = next;
- next = recent.next;
- return recent.data;
- }
- }
-
- public Object previous() {
- b.checkMod(knownMod);
- if (pos <= 0) {
- throw new NoSuchElementException();
- } else {
- pos--;
- recent = next = previous;
- previous = recent.previous;
- return recent.data;
- }
- }
-
- public void remove() {
- b.checkMod(knownMod);
- if (recent == null) {
- throw new IllegalStateException();
- }
-
- // Adjust the position to before the removed element
- if (recent == previous) pos--;
-
- // Could use recent.remove() but this way is quicker, and also correctly
- // fixes next and previous.
- next = recent.previous.next = recent.next;
- previous = recent.next.previous = recent.previous;
- size--;
- b.decSize(1);
- knownMod++;
- b.upMod();
- recent = null;
- }
-
- public void add(Object o) {
- b.checkMod(knownMod);
- previous.next = next.previous = new Entry(o, next, previous);
-
- // New for 1.2RC1 - the semantics changed so that the iterator is
- // positioned *after* the new element.
- previous = previous.next;
- pos++;
-
- size++;
- b.incSize(1);
- knownMod++;
- b.upMod();
- recent = null;
- }
-
- public void set(Object o) {
- b.checkMod(knownMod);
- if (recent == null) {
- throw new IllegalStateException();
- }
- recent.data = o;
- }
- }
-
+
/**
* Obtain the Entry at a given position in a list. This method of course
* takes linear time, but it is intelligent enough to take the shorter of the
* paths to get to the Entry required. This implies that the first or last
* entry in the list is obtained in constant time, which is a very desirable
* property.
- * For speed and flexibility in which ranges are valid, range checking is not
- * done in this method, and if n is outside the range -1 <= n <= size, the
- * result will be wrong (but no exception will be thrown).
- * Note that you *can* obtain entries at position -1 and size, which are
- * equal to prehead and posttail respectively.
- * This method is static so that it can also be used in subList.
+ * For speed and flexibility, range checking is not done in this method:
+ * Incorrect values will be returned if (n < 0) or (n >= size).
*
* @param n the number of the entry to get.
- * @param size the size of the list to get the entry in.
- * @param head the entry before the first element of the list (usually ends).
- * @param tail the entry after the last element of the list (usually ends).
*/
- static Entry getEntry(int n, int size, Entry head, Entry tail) {
-
- // n less than size/2, iterate from start
- if (n < size >> 1) {
- while (n-- >= 0) {
- head = head.next;
+ private Entry getEntry(int n)
+ {
+ Entry e;
+ if (n < size / 2)
+ {
+ e = first;
+ // n less than size/2, iterate from start
+ while (n-- > 0)
+ {
+ e = e.next;
+ }
}
- return head;
-
- // n greater than size/2, iterate from end
- } else {
- while (++n <= size) {
- tail = tail.previous;
+ else
+ {
+ e = last;
+ // n greater than size/2, iterate from end
+ while (++n < size)
+ {
+ e = e.previous;
+ }
+ }
+ return e;
+ }
+
+ /** Remove an entry from the list. This will adjust size and deal with
+ * `first' and `last' appropriatly. It does not effect modCount, that is
+ * the responsibility of the caller. */
+ private void removeEntry(Entry e)
+ {
+ if (size == 1)
+ first = last = null;
+ else
+ {
+ if (e == first)
+ {
+ first = e.next;
+ e.next.previous = null;
+ }
+ else if (e == last)
+ {
+ last = e.previous;
+ e.previous.next = null;
+ }
+ else
+ {
+ e.next.previous = e.previous;
+ e.previous.next = e.next;
+ }
}
- return tail;
- }
+ size--;
}
/**
* Create an empty linked list.
*/
- public LinkedList() {
+ public LinkedList()
+ {
super();
}
@@ -322,7 +150,8 @@
*
* @param c the collection to populate this list from.
*/
- public LinkedList(Collection c) {
+ public LinkedList(Collection c)
+ {
super();
// Note: addAll could be made slightly faster, but not enough so to justify
// re-implementing it from scratch. It is just a matter of a relatively
@@ -330,84 +159,279 @@
addAll(c);
}
- public Object getFirst() {
- if (size == 0) {
+ public Object getFirst()
+ {
+ if (size == 0)
throw new NoSuchElementException();
- }
- return ends.next.data;
+ return first.data;
}
- public Object getLast() {
- if (size == 0) {
+ public Object getLast()
+ {
+ if (size == 0)
throw new NoSuchElementException();
- }
- return ends.previous.data;
+ return last.data;
}
- public Object removeFirst() {
- if (size == 0) {
+ public Object removeFirst()
+ {
+ if (size == 0)
throw new NoSuchElementException();
- }
size--;
modCount++;
- return ends.next.remove();
+ Object r = first.data;
+
+ if (first.next != null)
+ first.next.previous = null;
+ return r;
}
- public Object removeLast() {
- if (size == 0) {
+ public Object removeLast()
+ {
+ if (size == 0)
throw new NoSuchElementException();
- }
size--;
modCount++;
- return ends.previous.remove();
+ Object r = last.data;
+
+ if (last.previous != null)
+ last.previous.next = null;
+ return r;
}
- public void addFirst(Object o) {
- ends.next.previous = ends.next = new Entry(o, ends.next, ends);
- size++;
+ public void addFirst(Object o)
+ {
modCount++;
+ Entry e = new Entry(o);
+
+ if (size == 0)
+ first = last = e;
+ else
+ {
+ e.next = first;
+ first.previous = e;
+ first = e;
+ }
+ size++;
}
- public void addLast(Object o) {
- ends.previous.next = ends.previous = new Entry(o, ends, ends.previous);
- size++;
+ public void addLast(Object o)
+ {
modCount++;
+ addLastEntry(new Entry(o));
+ }
+
+ private void addLastEntry(Entry e)
+ {
+ if (size == 0)
+ first = last = e;
+ else
+ {
+ e.previous = last;
+ last.next = e;
+ last = e;
+ }
+ size++;
}
- /**
- * Obtain the number of elements currently in this list.
- *
- * @returns the number of elements currently in this list.
- */
- public int size() {
+ public boolean contains(Object o)
+ {
+ Entry e = first;
+ while (e != null)
+ {
+ if (e.data == null ? o == null : o.equals(e.data))
+ return true;
+ e = e.next;
+ }
+ return false;
+ }
+
+ public int size()
+ {
return size;
}
+
+ public boolean add(Object o)
+ {
+ modCount++;
+ addLastEntry(new Entry(o));
+ return true;
+ }
+
+ public boolean remove(Object o)
+ {
+ modCount++;
+ Entry e = first;
+ while (e != null)
+ {
+ if (e.data == null ? o == null : o.equals(e.data))
+ {
+ removeEntry(e);
+ return true;
+ }
+ e = e.next;
+ }
+ return false;
+ }
- /**
- * Remove a range of elements from this list.
- *
- * @param fromIndex the index, inclusive, to remove from.
- * @param toIndex the index, exclusive, to remove to.
- * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex <
- * 0 || toIndex > size().
- */
- // Note: normally removeRange is provided to allow efficient ways to
- // implement clear() on subLists. However, in this case clear on subLists
- // works anyway, so this implementation is included just for completeness
- // and because subclasses might try to use it.
- protected void removeRange(int fromIndex, int toIndex) {
- subList(fromIndex, toIndex).clear();
+ public boolean addAll(Collection c)
+ {
+ return addAll(size, c);
}
+
+ public boolean addAll(int index, Collection c)
+ {
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ modCount++;
+ int csize = c.size();
- /**
- * Clear the list.
- */
- public void clear() {
- ends.next = ends.previous = ends;
+ if (csize == 0)
+ return false;
+
+ Iterator itr = c.iterator();
+
+ // Get the entries just before and after index. If index is at the start
+ // of the list, BEFORE is null. If index is at the end of thelist, AFTER is
+ // null. If the list is empty, both are null.
+ Entry after = null;
+ Entry before = null;
+ if (index != size)
+ {
+ after = getEntry(index);
+ before = after.previous;
+ }
+ else
+ before = last;
+
+ // Create the first new entry. We do not yet set the link from `before'
+ // to the first entry, in order to deal with the case where (c == this).
+ // [Actually, we don't have to handle this case to fufill the
+ // contract for addAll(), but Sun's implementation appears to.]
+ Entry e = new Entry(itr.next());
+ e.previous = before;
+ Entry prev = e;
+ Entry firstNew = e;
+
+ // Create and link all the remaining entries.
+ for (int pos = 1; pos < csize; pos++)
+ {
+ e = new Entry(itr.next());
+ e.previous = prev;
+ prev.next = e;
+ prev = e;
+ }
+ // Fix up the links between the last new entry and the following entry.
+ prev.next = after;
+ if (after != null)
+ after.previous = e;
+ else
+ last = e;
+
+ if (before != null)
+ before.next = firstNew;
+ else
+ first = firstNew;
+
+ size += csize;
+ return true;
+ }
+
+ public void clear()
+ {
modCount++;
+ first = null;
+ last = null;
size = 0;
}
+ public Object get(int index)
+ {
+ if (index < 0 || index >= size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ Entry e = getEntry(index);
+ return e.data;
+ }
+
+ public Object set(int index, Object o)
+ {
+ if (index < 0 || index >= size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ Entry e = getEntry(index);
+ Object old = e.data;
+ e.data = o;
+ return old;
+ }
+
+ public void add(int index, Object o)
+ {
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ modCount++;
+ addEntry(index, new Entry(o));
+ }
+
+ private void addEntry(int index, Entry e)
+ {
+ if (index < size)
+ {
+ Entry after = getEntry(index);
+ e.next = after;
+ e.previous = after.previous;
+ if (after.previous == null)
+ first = e;
+ else
+ after.previous.next = e;
+ after.previous = e;
+ size++;
+ }
+ else
+ addLastEntry(e);
+ }
+
+ public Object remove(int index)
+ {
+ if (index < 0 || index >= size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ modCount++;
+ Entry e = getEntry(index);
+ removeEntry(e);
+ return e.data;
+ }
+
+ public int indexOf(Object o)
+ {
+ int index = 0;
+ Entry e = first;
+ while (e != null)
+ {
+ if (e.data == null ? o == null : o.equals(e.data))
+ return index;
+ ++index;
+ e = e.next;
+ }
+ return -1;
+ }
+
+ public int lastIndexOf(Object o)
+ {
+ int index = size - 1;
+ Entry e = last;
+ while (e != null)
+ {
+ if (e.data == null ? o == null : o.equals(e.data))
+ return index;
+ --index;
+ e = e.previous;
+ }
+ return -1;
+ }
+
/**
* Obtain a ListIterator over this list, starting at a given index. The
* ListIterator returned by this method supports the add, remove and set
@@ -416,121 +440,13 @@
* @param index the index of the element to be returned by the first call to
* next(), or size() to be initially positioned at the end of the list.
* @exception IndexOutOfBoundsException if index < 0 || index > size().
- */
- public ListIterator listIterator(int index) {
-
- // Check bounds
- if (index < 0 || index > size) {
- throw new IndexOutOfBoundsException();
- }
-
- return new Iter(back, getEntry(index, size, ends, ends),
- index, size, modCount);
- }
-
- /**
- * Obtain a List view of a subsection of this list, from fromIndex
- * (inclusive) to toIndex (exclusive). The returned list is modifiable in
- * every respect. Changes to the returned list are reflected in this list. If
- * this list is structurally modified is any way other than through the
- * returned list, any subsequent operations on the returned list will result
- * in a ConcurrentModificationException (that is, the returned list is
- * fail-fast).
- *
- * @param fromIndex the index that the returned list should start from
- * (inclusive).
- * @param toIndex the index that the returned list should go to (exclusive).
- * @returns a List backed by a subsection of this list.
- * @exception IndexOutOfBoundsException if fromIndex < 0 || toIndex > size()
- * || fromIndex > toIndex.
*/
- public List subList(int fromIndex, int toIndex) {
-
- // Check bounds
- if (fromIndex > toIndex || fromIndex < 0 || toIndex > size) {
- throw new IndexOutOfBoundsException();
- }
-
- return new SubLinkedList(back, modCount,
- getEntry(fromIndex - 1, size, ends, ends),
- getEntry(toIndex, size, ends, ends),
- toIndex - fromIndex);
- }
-
- private static class SubLinkedList extends AbstractSequentialList {
-
- Entry head; // entry before the beginning
- Entry tail; // entry after the end
- int size;
- private final Backing b;
-
- private final Backing back = new Backing() {
- public void checkMod(int known) {
- if (known != modCount) {
- throw new ConcurrentModificationException();
- }
- }
- public void upMod() {
- modCount++;
- }
- public void incSize(int by) {
- size += by;
- }
- public void decSize(int by) {
- size -= by;
- }
- };
-
- SubLinkedList(Backing backing, int knownMod, Entry h, Entry t, int s) {
- this.modCount = knownMod;
- b = backing;
- head = h;
- tail = t;
- size = s;
- }
-
- public int size() {
- b.checkMod(this.modCount);
- return size;
- }
-
- public ListIterator listIterator(int index) {
- b.checkMod(this.modCount);
-
- // Check bounds
- if (index < 0 || index > size) {
- throw new IndexOutOfBoundsException();
- }
-
- return new Iter(back, getEntry(index, size, head, tail),
- index, size, modCount);
- }
-
- public void clear() {
- b.checkMod(this.modCount);
- head.next = tail;
- tail.previous = head;
- size = 0;
- b.decSize(size);
- modCount++;
- b.upMod();
- }
-
- // No removeRange because this class cannot be publically subclassed.
-
- public List subList(int fromIndex, int toIndex) {
- b.checkMod(this.modCount);
-
- // Check bounds
- if (fromIndex > toIndex || fromIndex < 0 || toIndex > size) {
- throw new IndexOutOfBoundsException();
- }
-
- return new SubLinkedList(back, this.modCount,
- getEntry(fromIndex - 1, size, head, tail),
- getEntry(toIndex, size, head, tail),
- toIndex - fromIndex);
- }
+ public ListIterator listIterator(int index)
+ {
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:" +
+ size);
+ return new LinkedListItr(index);
}
/**
@@ -538,34 +454,60 @@
* @return an object of the same class as this object, containing the
* same elements in the same order.
*/
- public Object clone()
+ public Object clone()
{
- LinkedList copy;
+ LinkedList copy = null;
try
{
copy = (LinkedList) super.clone();
}
catch (CloneNotSupportedException ex)
{
- throw new InternalError(ex.getMessage());
}
copy.size = 0;
- copy.ends = new Entry();
copy.addAll(this);
return copy;
}
+
+ public Object[] toArray()
+ {
+ Object[] array = new Object[size];
+ Entry e = first;
+ for (int i = 0; i < size; i++)
+ {
+ array[i] = e.data;
+ e = e.next;
+ }
+ return array;
+ }
+
+ public Object[] toArray(Object[] array)
+ {
+ if (array.length < size)
+ array = (Object[])
Array.newInstance(array.getClass().getComponentType(),
+ size);
+ else if (array.length > size)
+ array[size] = null;
+ Entry e = first;
+ for (int i = 0; i < size; i++)
+ {
+ array[i] = e.data;
+ e = e.next;
+ }
+ return array;
+ }
/**
* Serialize an object to a stream.
* @serialdata the size of the list (int), followed by all the elements
* (Object) in proper order.
*/
- private void writeObject(ObjectOutputStream s)
- throws IOException
+ private void writeObject(ObjectOutputStream s) throws IOException
{
s.writeInt(size);
- for (Iterator i = iterator(); i.hasNext(); )
- s.writeObject(i.next());
+ Iterator itr = iterator();
+ for (int i = 0; i < size; i++)
+ s.writeObject(itr.next());
}
/**
@@ -577,8 +519,133 @@
throws IOException, ClassNotFoundException
{
int serialSize = s.readInt();
- ends = new Entry();
- for (int i=0; i< serialSize; i++)
- addLast(s.readObject());
+ for (int i = 0; i < serialSize; i++)
+ addLastEntry(new Entry(s.readObject()));
}
+
+ /** A ListIterator over the list. This class keeps track of its
+ * position in the list, the size of the list, and the two list
+ * entries it is between. This enables it to be used identically
+ * for both the list itself and a sublist of the list.
+ */
+ class LinkedListItr implements ListIterator
+ {
+ int knownMod;
+ Entry next; // entry that will be returned by next().
+ Entry previous; // entry that will be returned by previous().
+ Entry lastReturned; // entry that will be affected by remove() or set().
+ int position; // index of `next'.
+
+ /**
+ * Create a new Iter starting at a given Entry within the list, at a given
+ * position, in a list of given size.
+ */
+ LinkedListItr(int index)
+ {
+ if (index == size)
+ {
+ next = null;
+ previous = last;
+ }
+ else
+ {
+ next = getEntry(index);
+ previous = next.previous;
+ }
+ position = index;
+ knownMod = modCount;
+ }
+
+ private void checkMod()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ public int nextIndex()
+ {
+ checkMod();
+ return position;
+ }
+
+ public int previousIndex()
+ {
+ checkMod();
+ return position - 1;
+ }
+
+ public boolean hasNext()
+ {
+ checkMod();
+ return (next != null);
+ }
+
+ public boolean hasPrevious()
+ {
+ checkMod();
+ return (previous != null);
+ }
+
+ public Object next()
+ {
+ checkMod();
+ if (next == null)
+ throw new NoSuchElementException();
+ position++;
+ lastReturned = previous = next;
+ next = lastReturned.next;
+ return lastReturned.data;
+ }
+
+ public Object previous()
+ {
+ checkMod();
+ if (previous == null)
+ throw new NoSuchElementException();
+ position--;
+ lastReturned = next = previous;
+ previous = lastReturned.previous;
+ return lastReturned.data;
+ }
+
+ public void remove()
+ {
+ checkMod();
+ if (lastReturned == null)
+ throw new IllegalStateException();
+
+ // Adjust the position to before the removed element, if the element
+ // being removed is behind the cursor.
+ if (lastReturned == previous)
+ position--;
+
+ next = lastReturned.next;
+ previous = lastReturned.previous;
+ // Because the list is being manipulated directly, there's no need to
+ // touch either modCount or knownMod here.
+ removeEntry(lastReturned);
+
+ lastReturned = null;
+ }
+
+ public void add(Object o)
+ {
+ checkMod();
+ // Because the list is being manipulated directly, there's no need to
+ // touch either modCount or knownMod here.
+ Entry e = new Entry(o);
+ addEntry(position, e);
+ previous = e;
+ position++;
+ lastReturned = null;
+ }
+
+ public void set(Object o)
+ {
+ checkMod();
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ lastReturned.data = o;
+ }
+ } // class LinkedListItr
}
- PATCH: More collections List updates,
Bryce McKinlay <=