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

[Andres March]

How is the numbering of your diagram determined?  Would order = branch#  x level# ?  It seems strange to process the elements sequentially in this manner.  From your previous posts I inferred that 11 would be last because it is the deepest child of the last branch.  But my comprehension of your problem was incorrect.  Usually, if I was to parse an entire tree manually I would complete each branch iteratively before beginning on the next.  For example, I would hit 1,2,5,12 before starting on 3,6,7,13,14,8.

I thought about doing it the way you have written about but it never made sense to me.  You have to go back to the same element multiple times - once to process and the other times to check for children....  I've included the code I commonly use for my method.  Sorry, if it doesn't help.

public void processAll(rootElem) {
 
	ArrayList childrenList = rootElem.getChildren();
	Iterator it = childrenList.iterator();
	while( it.hasNext() )  {
		Element childElem = it.next();
		// do whatever you want with it 
		processAll(childElem);

        	}	

ANDRES MARCH
LEAD APPLICATION DEVELOPER
eHEALTHCONTRACTS, INC.
WWW.eHEALTHCONTRACTS.COM <http://www.eHEALTHCONTRACTS.COM> 
OFFICE: 510.581.5646 x205
MOBILE: 415.999.6735
FAX: 510.582.8013

Note:

The information contained in this message may be privileged and confidential and protected from disclosure. If the reader of this message is not the intended recipient, or an employee or agent responsible for delivering this message to the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please notify us immediately by replying to the message and deleting it from your computer.

Thank you. eHealthContracts, Inc.



-----Original Message-----
From: Azrael [mailto:azrael at azrael-uk.f2s.com]
Sent: Wednesday, August 28, 2002 7:56 AM
To: jdom-interest at jdom.org
Subject: Re: [jdom-interest] breadth first traversal, nextElement()


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