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

Jason Hunter jhunter at servlets.com
Fri Nov 9 02:57:19 PST 2007


Ah, here's Rolf's original post.  The intent for inclusion is clear.

-jh-

Rolf Lear wrote:
> 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.
> _______________________________________________
> To control your jdom-interest membership:
> http://www.jdom.org/mailman/options/jdom-interest/youraddr@yourhost.com
> 


More information about the jdom-interest mailing list