 | Mailing List | | Home | | Forum Home | | JBoss - Java Application Server | | Tomcat - JSP/Servlet container | | Struts - A MVC web framework | | iText - An open source PDF Java Library | | JDOM - JDOM XML Parser | | JSP - A mailing list about Java Server Pages specification and reference | | J2EE - A mailing list for Java(tm) 2 Platform, Enterprise Edition | | J2EE Pattern - An interest list for Sun Java Center J2EE Pattern Catalog | | Servlet - A mailing list for discussion about Sun Microsystem's Java Servlet API Technology | |
Struts & Hibernate
|
|
|
| | | Subject: Re: Bug in ListIterator.add() method | Subject: Re: Bug in ListIterator.add() method 2007-11-09 - By Jason Hunter
Back
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@(protected)
> [mailto:jdom-interest-bounces@(protected)]On Behalf Of Rolf Lear
> Sent: Friday, April 22, 2005 11:34 AM
> To: 'Bradley S. Huffman'; Christian Gruber
> Cc: jdom-interest@(protected)
> 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@(protected)
> [mailto:jdom-interest-bounces@(protected)]On Behalf Of Bradley S. Huffman
> Sent: Friday, April 22, 2005 10:57 AM
> To: Christian Gruber
> Cc: jdom-interest@(protected)
> 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@(protected)
>
> 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@(protected)
>
> 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@(protected)
>
__ ____ ____ ____ ____ ____ ____ ____ ____ ____
To control your jdom-interest membership:
http://www.jdom.org/mailman/options/jdom-interest/youraddr@(protected)
|
|
|
