[jdom-interest] Re: List's in JDOM - a small essay

[Joseph Bowbeer]

By the way, I've wondered about the use of LinkedList throughout JDOM.  For
many uses, I believe ArrayList would perform better.  You need to expect to
be doing a lot of insertion and/or deletion at the head or middle of the
list before you've made up for the extra memory and time consumed by
creating each of the LinkedList's individual nodes.

Can you design your FilterList so that it *can* be implemented on top of an
ArrayList?

It looks like you can make a generic filtered List by first implementing a
FilteredListIterator (with a built-in Filter), and then instantiating an
AbstractSequentialList with a listIterator method that returns your
FilteredListIterator.

The FilteredListIterator in turn can be built from a Filter and a List.
(I'm suggesting that you should consider implementing the underlying List as
an ArrayList.)

The Filter can be something like the following:

    interface Filter {
        boolean filter(Object entry);
    }

Filter.filter(entry) returns true if the given entry makes the "cut".

Concerning traversing the filtered list in reverse, there are probably ways
to ease the pain using List.reverse().

for (Iterator iter = element.getChildren("foo").reverse(); iter.hasNext(); )
{
    bar( iter.next() );
}

Reversing a FilterList should create a new AbstractSequentialList using a
filtered ListIterator that runs in reverse.


----- original message -----

From: Jools jools at jools.org
Date: Thu, 08 Mar 2001 21:36:03 +0000

Well seeing as we've had a fair bit of traffic on the subject of
lists in JDOM, I have decided to write this email, with which I hope
to shed a little light on the way we are going with lists in JDOM.

Thanks to Philip Nelson for giving me a prod, I'm a bit behind on my
email right now (only 900 to go !)

I'm currently rewriting specific portions of JDOM to use a FilterList
which internally uses a singly linked list and allows filtering of the
items contained therein.

Iterating
~~~~~~~~~

Why use a singly linked list ? Because most operations on a JDOM object
are via an iterator, and this is normally in one direction. Thus
the FilterList is optimized for this operation, in JDOM terms it means
that the following is very efficient;

Iterator iter = element.getChildren("foo").iterator();
while (iter.hasNext()) {
 iter.next();
}

Because we examine each item to see if it matches the criteria specified
in the iterator, and we only move over the list once any one single
iteration is vey efficient.

With PartialListwe would have have to iterate over every item first in
order to copy the required items into the PartialList, then we iterator
over it again using the iterator. So we save one iteration. So far so
good!

But there's no such thing as a free lunch! Here's the down side, random
access causes us an interesting problem.

Take the original code and do it the hard way (and backwards!);

List foos = element.getChildren("foo");
for (int i=foos.size(); i > 0; i--) {
 foos.get(i-1);
}

This is our worst case ! for the size() call we have to iterate over the
entire list in order to see how many foos we have. Then for each item
we have to iterate through the entire list until we get to the correct
index checking each one along the way.

I can here you say "What about a sparse index?" or "Why not just keep a
reference to the last element?". Because this list needs to be totally
lightweight. Just go through your code add see how many times you call
getChildren().iterator() then you'll see what I mean.

Plus, if we get hammered on this performance side of things, then we
could
always optimize after we get it all working (Knuth).


Liveness
~~~~~~~~

FilterList always uses a 'live' reference to the data in child lists.
no copying is required in order to create a 'view' of the data in a
list.

This means that any modifications made to a child list will
automatically
be seen in the parent list.

Typically, when using iterators if a change is made to the parent list
during iteration, you might find that a ConcurrentModificationException
get thrown because the parent has been modified whilst you are
iterating.

This was one area of PartialList which bothered me (amongst others) as
we never used the backing list to get our iterators, it was from the
PartialList. So if a modification was made to the parent list, and
we had an iterator on the PartialList ConcurrentModificationException
would not be thrown and we would possibly risk our document getting
out of order.

Conclusion
~~~~~~~~~~

The preservation of order is very important to us and so is getting an
API which is not too heavy, or too CPU bound.
But all if this is in vain if we loose the correct ordering of the
document.

--Jools