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

Azrael azrael at azrael-uk.f2s.com
Wed Aug 28 07:55:31 PDT 2002


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.


-- 
                 Azrael

            ("\''/").___..--'''"-._
            `0_ O  )   `-.  (     ).`-.__.`)
            (_Y_.)'  ._   )  `._ `. ``-..-'
          _..`--'_..-_/  /--'_.' .'
         ((i).-''  ((i).'  (((.-'

Of all God's creatures there is only one that cannot be made the slave 
of the lash. That one is the cat. If man could be crossed with a cat it 
would improve man, but it would deteriorate the cat.

ICQ#52944566
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.jpg
Type: image/jpeg
Size: 14693 bytes
Desc: not available
Url : http://jdom.org/pipermail/jdom-interest/attachments/20020828/6cdb2da7/example.jpg


More information about the jdom-interest mailing list