[jdom-interest] Bug in ListIterator.add() method

Rolf Lear rlear at algorithmics.com
Fri Apr 22 10:58:43 PDT 2005


Since I dug up some of my JDOM stuff from years ago, here is my patch.

I have run this through the JDom test harness (JDom-test), and all tests
pass. (The harness did point out a couple of bugs .... which are now
corrected.)

Feel free to apply as you wish, I pass any ownership/copyright to Jason,
etc.

In essense, the patch completely re-writes the ListIterator in ContentList.

Rolf

Index: ContentList.java
===================================================================
RCS file: /home/cvspublic/jdom/src/java/org/jdom/ContentList.java,v
retrieving revision 1.39
diff -u -r1.39 ContentList.java
--- ContentList.java	28 Feb 2004 03:30:27 -0000	1.39
+++ ContentList.java	22 Apr 2005 17:56:44 -0000
@@ -84,19 +84,6 @@
 
     private static final int INITIAL_ARRAY_SIZE = 5;
 
-    /**
-     * Used inner class FilterListIterator to help hasNext and
-     * hasPrevious the next index of our cursor (must be here
-     * for JDK1.1).
-     */
-    private static final int CREATE  = 0;
-    private static final int HASPREV = 1;
-    private static final int HASNEXT = 2;
-    private static final int PREV    = 3;
-    private static final int NEXT    = 4;
-    private static final int ADD     = 5;
-    private static final int REMOVE  = 6;
-
     /** Our backing list */
 //    protected ArrayList list;
     private Content elementData[];
@@ -719,77 +706,91 @@
         /** The Filter that applies */
         Filter filter;
 
-        /** The last operation performed */
-        int lastOperation;
-
-        /** Initial start index in backing list */
-        int initialCursor;
-
+        /** Whether this iterator is in forward or reverse. */
+        private boolean forward = false;
+        /** Whether a call to remove() is valid */
+        private boolean canremove = false;
+        /** Whether a call to set() is valid */
+        private boolean canset = false;
+        
         /** Index in backing list of next object */
-        int cursor;
-
-        /** Index in backing list of last object returned */
-        int last;
+        private int cursor = -1;
+        /** the backing index to use if we actually DO move */
+        private int tmpcursor = -1;
+        /** Index in ListIterator */
+        private int index = -1;
 
         /** Expected modCount in our backing list */
-        int expected;
+        private int expected = -1;
+        
+        /** Number of elements matching the filter. */
+        private int fsize = 0;
 
         /**
          * Default constructor
          */
         FilterListIterator(Filter filter, int start) {
             this.filter = filter;
-            initialCursor = initializeCursor(start);
-            last = -1;
             expected = ContentList.this.getModCount();
-            lastOperation = CREATE;
+            // always start list iterators in backward mode ....
+            // it makes sense... really.
+            forward = false;
+            
+            if (start < 0) {
+                throw new IndexOutOfBoundsException("Index: " + start);
+            }
+
+            // the number of matching elements....
+            fsize = 0;
+            
+            // go through the list, count the matching elements...
+            for (int i = 0; i < ContentList.this.size(); i++) {
+                if (filter.matches(ContentList.this.get(i))) {
+                    if (start == fsize) {
+                        // set the back-end cursor to the matching
element....
+                        cursor = i;
+                        // set the front-end cursor too.
+                        index = fsize;
+                    }
+                    fsize++;
+                }
+            }
+
+            if (start > fsize) {
+                throw new IndexOutOfBoundsException("Index: " + start +
+                                                    " Size: " + fsize);
+            }
+            
+            if (cursor == -1) {
+                // implies that start == fsize (i.e. after the last element
- valid for a ListIterator cursor.
+                // put the insertion point at the end of the Underlying
content list ....
+                // i.e. an add() at this point may potentially end up with
filtered content between previous() and next()
+                // the alternative is to put the cursor on the Content
after the last Content that the filter passed
+                // The implications are ambiguous.
+                cursor = ContentList.this.size();
+                index = fsize;
+            }
+            
         }
 
         /**
          * Returns <code>true</code> if this list iterator has a next
element.
          */
         public boolean hasNext() {
-            checkConcurrentModification();
-
-            switch(lastOperation) {
-            case CREATE:  cursor = initialCursor;
-                          break;
-            case PREV:    cursor = last;
-                          break;
-            case ADD:
-            case NEXT:    cursor = moveForward(last + 1);
-                          break;
-            case REMOVE:  cursor = moveForward(last);
-                          break;
-            case HASPREV: cursor = moveForward(cursor + 1);
-                          break;
-            case HASNEXT: break;
-            default:      throw new IllegalStateException("Unknown
operation");
-            }
-
-            if (lastOperation != CREATE) {
-                lastOperation = HASNEXT;
-            }
-
-            return (cursor < ContentList.this.size()) ? true : false;
+            return nextIndex() < fsize;
         }
 
         /**
          * Returns the next element in the list.
          */
         public Object next() {
-            checkConcurrentModification();
-
-            if (hasNext()) {
-                last = cursor;
-            }
-            else {
-                last = ContentList.this.size();
-                throw new NoSuchElementException();
-            }
-
-            lastOperation = NEXT;
-            return ContentList.this.get(last);
+            if (! hasNext()) throw new NoSuchElementException("next() is
beyond the end of the Iterator.");
+            index = nextIndex();
+            cursor = tmpcursor;
+            forward = true;
+            canremove = true;
+            canset = true;
+            return ContentList.this.get(cursor);
         }
 
         /**
@@ -797,50 +798,20 @@
          * elements when traversing the list in the reverse direction.
          */
         public boolean hasPrevious() {
-            checkConcurrentModification();
-
-            switch(lastOperation) {
-            case CREATE:  cursor = initialCursor;
-                          int size = ContentList.this.size();
-                          if (cursor >= size) {
-                              cursor = moveBackward(size - 1);
-                          }
-                          break;
-            case PREV:
-            case REMOVE:  cursor = moveBackward(last - 1);
-                          break;
-            case HASNEXT: cursor = moveBackward(cursor - 1);
-                          break;
-            case ADD:
-            case NEXT:    cursor = last;
-                          break;
-            case HASPREV: break;
-            default:      throw new IllegalStateException("Unknown
operation");
-            }
-
-            if (lastOperation != CREATE) {
-                lastOperation = HASPREV;
-            }
-
-            return (cursor < 0) ? false : true;
+            return previousIndex() >= 0;
         }
 
         /**
          * Returns the previous element in the list.
          */
         public Object previous() {
-            checkConcurrentModification();
-
-            if (hasPrevious()) {
-                last = cursor;
-            }
-            else {
-                last = -1;
-                throw new NoSuchElementException();
-            }
-
-            lastOperation = PREV;
-            return ContentList.this.get(last);
+            if (! hasPrevious()) throw new
NoSuchElementException("previous() is before the start of the Iterator.");
+            index = previousIndex();
+            cursor = tmpcursor;
+            forward = false;
+            canremove = true;
+            canset = true;
+            return ContentList.this.get(cursor);
         }
 
         /**
@@ -849,19 +820,23 @@
          */
         public int nextIndex() {
             checkConcurrentModification();
-            hasNext();
-
-            int count = 0;
-            for (int i = 0; i < ContentList.this.size(); i++) {
-                if (filter.matches(ContentList.this.get(i))) {
-                    if (i == cursor) {
-                        return count;
+            
+            if (forward) {
+                // starting with next possibility ....
+                for (int i = cursor + 1; i < ContentList.this.size(); i++)
{
+                    if (filter.matches(ContentList.this.get(i))) {
+                        tmpcursor = i;
+                        return index + 1;
                     }
-                    count++;
                 }
-            }
-            expected = ContentList.this.getModCount();
-            return count;
+                // never found another match.... put the insertion point at
the end of the list....
+                tmpcursor = ContentList.this.size();
+                return index + 1;
+            }
+            
+            // we've been going backwards ... so nextIndex() returns the
same element.
+            tmpcursor = cursor;
+            return index;
         }
 
         /**
@@ -871,37 +846,40 @@
          */
         public int previousIndex() {
             checkConcurrentModification();
-
-            if (hasPrevious()) {
-                int count = 0;
-                for (int i = 0; i < ContentList.this.size(); i++) {
+            if (!forward) {
+                // starting with next possibility ....
+                for (int i = cursor - 1; i >= 0; i--) {
                     if (filter.matches(ContentList.this.get(i))) {
-                        if (i == cursor) {
-                            return count;
-                        }
-                        count++;
+                        tmpcursor = i;
+                        return index - 1;
                     }
                 }
-            }
-            return -1;
+                // never found another match.... put the insertion point at
the start of the list....
+                tmpcursor = -1;
+                return index -1;
+            }
+            
+            // we've been going forwards ... so previousIndex() returns the
same element.
+            tmpcursor = cursor;
+            return index;
+
         }
 
         /**
          * Inserts the specified element into the list.
          */
         public void add(Object obj) {
-            checkConcurrentModification();
-
-            if (filter.matches(obj)) {
-                last = cursor + 1;
-                ContentList.this.add(last, obj);
-            }
-            else {
-                throw new IllegalAddException("Filter won't allow add of "
+
-                                              (obj.getClass()).getName());
-            }
-            expected = ContentList.this.getModCount();
-            lastOperation = ADD;
+            // call to nextIndex() will check concurrent.
+            nextIndex();
+            // tmpcursor is the backing cursor of the next element
+            // remember that List.add(index,obj) is really an insert....
+            ContentList.this.add(tmpcursor, obj);
+            forward = true;
+            expected = getModCount();
+            canremove = canset = false;
+            index = nextIndex();
+            cursor = tmpcursor;
+            fsize++;
         }
 
         /**
@@ -910,28 +888,15 @@
          * the last call to <code>next</code> or <code>previous</code>.
          */
         public void remove() {
-            checkConcurrentModification();
-
-            if ((last < 0) || (lastOperation == REMOVE)) {
-                throw new IllegalStateException("no preceeding call to " +
-                                                "prev() or next()");
-            }
-
-            if (lastOperation == ADD) {
-                throw new IllegalStateException("cannot call remove() " +
-                                                "after add()");
-            }
-
-            Object old = ContentList.this.get(last);
-            if (filter.matches(old)) {
-                ContentList.this.remove(last);
-            }
-            else throw new IllegalAddException("Filter won't allow " +
-                                                (old.getClass()).getName()
+
-                                                " (index " + last +
-                                                ") to be removed");
-            expected = ContentList.this.getModCount();
-            lastOperation = REMOVE;
+            if (!canremove) throw new IllegalStateException("Can not remove
an element unless either next() or previous() has been called since the last
remove()");
+            nextIndex(); // to get out cursor ...
+            ContentList.this.remove(cursor);
+            cursor = tmpcursor - 1;
+            expected = getModCount();
+            forward = false;
+            canremove = false;
+            canset = false;
+            fsize--;
         }
 
         /**
@@ -939,98 +904,17 @@
          * <code>previous</code> with the specified element.
          */
         public void set(Object obj) {
+            if (!canset) throw new IllegalStateException("Can not set an
element unless either next() or previous() has been called since the last
remove() or set()");
             checkConcurrentModification();
-
-            if ((lastOperation == ADD) || (lastOperation == REMOVE)) {
-                throw new IllegalStateException("cannot call set() after "
+
-                                                "add() or remove()");
-            }
-
-            if (last < 0) {
-                throw new IllegalStateException("no preceeding call to " +
-                                                "prev() or next()");
-            }
-
-            if (filter.matches(obj)) {
-                Object old = ContentList.this.get(last);
-                if (!filter.matches(old)) {
-                    throw new IllegalAddException("Filter won't allow " +
-                                  (old.getClass()).getName() + " (index " +
-                                  last + ") to be removed");
-                }
-                ContentList.this.set(last, obj);
-            }
-            else {
+            
+            if (!filter.matches(obj)) {
                 throw new IllegalAddException("Filter won't allow index " +
-                                              last + " to be set to " +
+                                              index + " to be set to " +
                                               (obj.getClass()).getName());
             }
 
+            ContentList.this.set(cursor, obj);
             expected = ContentList.this.getModCount();
-            // Don't set lastOperation
-        }
-
-        /**
-         * Returns index in the backing list by moving forward start
-         * objects that match our filter.
-         */
-        private int initializeCursor(int start) {
-            if (start < 0) {
-                throw new IndexOutOfBoundsException("Index: " + start);
-            }
-
-            int count = 0;
-            for (int i = 0; i < ContentList.this.size(); i++) {
-                Object obj = ContentList.this.get(i);
-                if (filter.matches(obj)) {
-                    if (start == count) {
-                        return i;
-                    }
-                    count++;
-                }
-            }
-
-            if (start > count) {
-                throw new IndexOutOfBoundsException("Index: " + start +
-                                                    " Size: " + count);
-            }
-
-            return ContentList.this.size();
-        }
-
-        /**
-         * Returns index in the backing list of the next object matching
-         * our filter, starting at the given index and moving forwards.
-         */
-        private int moveForward(int start) {
-            if (start < 0) {
-                start = 0;
-            }
-            for (int i = start; i < ContentList.this.size(); i++) {
-                Object obj = ContentList.this.get(i);
-                if (filter.matches(obj)) {
-                    return i;
-                }
-            }
-            return ContentList.this.size();
-        }
-
-        /**
-         * Returns index in the backing list of the next object matching
-         * our filter, starting at the given index and moving backwards.
-         */
-        private int moveBackward(int start) {
-            if (start >= ContentList.this.size()) {
-                start = ContentList.this.size() - 1;
-            }
-
-            for (int i = start; i >= 0; --i) {
-                Object obj = ContentList.this.get(i);
-                if (filter.matches(obj)) {
-                    return i;
-                }
-            }
-            return -1;
         }
 
         /**



-----Original Message-----
From: jdom-interest-bounces at jdom.org
[mailto:jdom-interest-bounces at jdom.org]On Behalf Of Rolf Lear
Sent: Friday, April 22, 2005 11:34 AM
To: 'Bradley S. Huffman'; Christian Gruber
Cc: jdom-interest at jdom.org
Subject: RE: [jdom-interest] Bug in ListIterator.add() method


The complete iterator stuff in JDom is based on pre-collections stuff. There
is a lot of scope to re-hash the iterator problem.

I'll volunteer a patch in the next couple of days if people want to see the
iterator stuff re-written. When I was looking at the Parent/Child stuff a
year or so ago I odentified the iterator processes as being a weak point in
JDom in the sense that it was just plain complex. The wayu I though I would
re-do it implied Java1.2 logic IIRC.

Anyways, I'll use the weekend to produce a patch if people want.

Rolf



-----Original Message-----
From: jdom-interest-bounces at jdom.org
[mailto:jdom-interest-bounces at jdom.org]On Behalf Of Bradley S. Huffman
Sent: Friday, April 22, 2005 10:57 AM
To: Christian Gruber
Cc: jdom-interest at jdom.org
Subject: Re: [jdom-interest] Bug in ListIterator.add() method


Christian Gruber writes:

> As I suppose, Jdoms ListIterator.add() implementation has a problem
> when it is called more than once and when it is called at the end of
> the list.

Looking at the code it looks like the sequence

    listIterator.add(new Element("a"));
    listIterator.add(new Element("b"));
    listIterator.add(new Element("c"));

will produce <c><b><a> instead of <a><b><c> and continue iterating on
element 2 (<b>) instead of after the last new element. That is a bug.

Brad
_______________________________________________
To control your jdom-interest membership:
http://www.jdom.org/mailman/options/jdom-interest/youraddr@yourhost.com

This email and any files transmitted with it are confidential and
proprietary to Algorithmics Incorporated and its affiliates
("Algorithmics").  If received in error, use is prohibited.  Please destroy,
and notify sender.  Sender does not waive confidentiality or privilege.
Internet communications cannot be guaranteed to be timely, secure, error or
virus-free.  Algorithmics does not accept liability for any errors or
omissions.  Any commitment intended to bind Algorithmics must be reduced to
writing and signed by an authorized signatory.
_______________________________________________
To control your jdom-interest membership:
http://www.jdom.org/mailman/options/jdom-interest/youraddr@yourhost.com

This email and any files transmitted with it are confidential and
proprietary to Algorithmics Incorporated and its affiliates
("Algorithmics").  If received in error, use is prohibited.  Please destroy,
and notify sender.  Sender does not waive confidentiality or privilege.
Internet communications cannot be guaranteed to be timely, secure, error or
virus-free.  Algorithmics does not accept liability for any errors or
omissions.  Any commitment intended to bind Algorithmics must be reduced to
writing and signed by an authorized signatory.


More information about the jdom-interest mailing list