[jdom-interest] breadth first traversal, nextElement()

[Dennis Sosnoski]

I think the key issue here is that Bradley's code assumes you're 
starting at some element of the tree (the root element, if you want to 
walk the whole tree) and will enumerate all the children of that element 
in a width-first traversal. After processing the root element you fill 
the array with all the children of the root element and process those, 
then next with all *their* children (the grandchildren of the root 
element), etc. If you start from the 1 element of your diagram I believe 
everything works out correctly in this manner.

If you want to start at an arbitrary element and find the next element 
in the tree for a width-first traversal the code I sent last night 
should get you there.

  - Dennis

Azrael wrote:

> It probably might seem quite rude of me to critique someone elses code 
> that has been offered as a suggestion to me.. but I hope it isn't 
> taken that way.. as I do appreciate it..
> I think general interest requires that if someone offers a suggestion. 
> and it needs changes.. that I bring them to everyone who might be 
> interested.
> I attach a small picture giving the tree I'm assuming this is working 
> on. (very small attachment 14kb .. so I hope no-one minds)
>
> Bradley S. Huffman wrote:
> public class BreadthFirst {
>
>>
>>     private List mylist = new ArrayList();
>>     private int cursor = 0;
>>
>>     public BreadthFirst(Element start) {
>>         mylist.add(start);
>>     }
>>
>>     public Object next() {
>>         int size = mylist.size();
>
>
> Let's say I pass element 11 as my 'start'.
> If I understand correctly, mylist will now contain the element I wish 
> to start from, and only that element. So 'size = 1' 'cursor = 0'
>
>>         // First check if we have run out of items. If so reload list
>>         // with children of all the Elements.
>>         if ((size != 0) && (cursor >= size)) {
>
>
> size is indeed not 0, but cursor 0 >= 1 is false
>
>>             List temp = new ArrayList();
>>             for (int i = 0; i < size; i++) {
>>                 if (mylist.get(i) instanceof Element) {
>>                     Element element = (Element) mylist.get(i);
>>                     temp.addAll(element.getContent());
>>                 }
>>             }
>>             mylist = temp;
>>             cursor = 0;
>>         }
>>
>>         // Anything in the list? No, return null
>>         if (size == 0) {
>>             return null;
>>         }
>
>
> size =1 so the above is skipped
>
>>         // Yes, return item pointed to by cursor.
>>         if (cursor < size) {
>>             cursor++;
>>             return mylist.get(cursor - 1);
>>         }
>
>
> cursor 0 is less than size 1, so cursor++, means cursor = 1
> and we return back the very element we initially put into the List.
>
>>     }
>> }
>>
>
> Additionally from looking at the for loop we're only ever dealing with 
> children.. if we can get into it.. and that doesn't quite work 
> properly as far as I can see.
> Referring to the diagram attached. The numbers indicate the way in 
> which I want the breadth-first traversal to 'walk' (hopefully this is 
> what others understand breadth-first to be .. I hope I'm not wrong 
> with my terminology).
> So if pass Element '11' in.. and want the next element, I should get 
> Element '12' this means I not only have to check what children I 
> have.. but I need to initially check the children of my previous 
> siblings first.
> If I passed Element '9' as my initial starting point, I would need to 
> pass my next sibling.
>
> Roughly: if start == last child of my parent (youngest of my siblings)
>             && start.getParent() == last child of its parent
>       return my first 'nephew/niece'
>
>     if start == last child of its parent
>      && start.getParent() != last child of it's parent
>         return the 'nephew/niece' of my parent that was 'born' after me
>
>     if start != last child of my parent
>           return my next sibling
>
> descriptions based on family tree monemclature .. hope it isn't 
> confusing.
>
>
>
> ------------------------------------------------------------------------
>