On Jan 12, 2007, at 13:00, [EMAIL PROTECTED] wrote:
<snip />
Just a quick comment on this, given the above stats you might
consider having a single Object field and switch the type of object
from the actual child (when there is a single child) to a List of
children when there are multiple children:
Also an interesting suggestion, thanks!
I'm still wondering whether the use of separate lists could not be
avoided altogether.
Based on Jörgs statistics, I'd say that the number of children will
most likely never reach the level where using direct index-based
access (ArrayList) has its benefits over traversing a tree of
references (LinkedList).
On top of that, all we really seem to need further in the code, is an
iterator over that list, not the list itself...
I'm thinking, roughly all we need is something like:
...
class Node {
Object parent;
Object firstChild;
Object[] siblings; //if there are siblings, always length=2
...
class ChildIterator
Node currentNode;
ChildIterator(Node n) {
currentNode = n.firstChild;
}
hasNext() {
return (currentNode.siblings != null)
&& (currentNode.siblings[1] != null);
}
next() {
if (hasNext()) {
return currentNode.siblings[1];
} else {
throw new NoSuchElementException();
}
}
etc.
The backing list would be defined by the pointers between the
objects, and not exist as a separate object (list) itself.
I'm still not completely sure about my estimation, but in the picture
painted earlier (instance count of ArrayList and Object[]), those
extra reference(s) for the siblings could turn out to be well worth
it, since they'd only slightly increase the instance size of already
existing objects, but they do avoid the creation of so many new
ArrayList instances.
Cheers,
Andreas
