I was toying with adding breadth first search, so you could skip trees of uninteresting children, but the more I looked at the algorithm... and it's breadth first, not depth first.
Okay, first in the constructor, it sets curr_ if the condition is true. But curr_ is the top node, so that's as breadth first as you get! Secondly, in popFront, it checks for curr_ to have a child, and sets curr_ to that child, then checks the condition. If that child itself has children, they don't get visited before this child is checked.
If it were depth first, it would need to loop until there were no children at all, then visit that node, then go up parent nodes, visiting each one. Once a parent node has a next node, go to that node, do not visit it, and start going down to the lowest child again.
I believe it is a breadth first traversal, even though it goes down the children, before going to the next siblings. The condition is checked at the topmost node, and no more depth is traversed, until the next iteration. Parent nodes will always be produced by the iterator before their children, since it checks the condition as soon as it goes down to firstChild, rather than continuing down firstChild to the bottom, then checking the condition only while returning back up.
So, good news for me I can just say "void skipChildren() { curr_ = curr_.next_; }" and it'll skip those children. But if you needed depth first searching, say to prune children without messing up the iterator, you'd mess up the iterator. Whatever you mutated the tree into, the iterator would descend into that, after visiting the parent node.
If it is a breadth first iterator, maybe it should go to .next_ first, rather than .firstChild_. You can use next_ to go across, just like firstChild_ goes down, until you hit the end, and then .prev_ instead of .parent_ to return, until a node is found that has a .firstChild. That'd be a more intutive way of breadth first searching... I think?
Considering this document:
<A>
<AB>
<BE/><BF/><BG/>
<AC>
<CH/><CI/><CJ/>
</AC>
<AD>
<DK/><DL/>
</AD>
</A>A
AB AC AD
BE BF BG CH CI CJ DK DL
currently the order returned is:
A, AB, BE, BF, BG, AC, CH, CI, CJ, AD, DK, DL (I checked)
A breadth first search that prioritized next_ above firstChild_ would have this order:
A, AB, AC, AD, DK, DL, CH, CI CJ, BE, BF, BG
A depth first traversal would be thus:
BE, BF, BG, AB, CH, CI, CJ, AC, DK, DL, AD, A
That traversal prioritizes firstChild_ and goes from prev_ to next_. A depth first prioritizing firstChild_ and going from next_ to prev_ would be this:
DL, DK, AD, CJ, CI, CH, AC, BG, BF, BE, AB, A
which is the exact reverse order of the breadth first search prioritizing firstChild_ and going from prev_ to next_.
I was toying with adding breadth first search, so you could skip trees of uninteresting children, but the more I looked at the algorithm... and it's breadth first, not depth first.
Okay, first in the constructor, it sets curr_ if the condition is true. But curr_ is the top node, so that's as breadth first as you get! Secondly, in popFront, it checks for curr_ to have a child, and sets curr_ to that child, then checks the condition. If that child itself has children, they don't get visited before this child is checked.
If it were depth first, it would need to loop until there were no children at all, then visit that node, then go up parent nodes, visiting each one. Once a parent node has a next node, go to that node, do not visit it, and start going down to the lowest child again.
I believe it is a breadth first traversal, even though it goes down the children, before going to the next siblings. The condition is checked at the topmost node, and no more depth is traversed, until the next iteration. Parent nodes will always be produced by the iterator before their children, since it checks the condition as soon as it goes down to firstChild, rather than continuing down firstChild to the bottom, then checking the condition only while returning back up.
So, good news for me I can just say "void skipChildren() { curr_ = curr_.next_; }" and it'll skip those children. But if you needed depth first searching, say to prune children without messing up the iterator, you'd mess up the iterator. Whatever you mutated the tree into, the iterator would descend into that, after visiting the parent node.
If it is a breadth first iterator, maybe it should go to .next_ first, rather than .firstChild_. You can use next_ to go across, just like firstChild_ goes down, until you hit the end, and then .prev_ instead of .parent_ to return, until a node is found that has a .firstChild. That'd be a more intutive way of breadth first searching... I think?
Considering this document:
currently the order returned is:
A, AB, BE, BF, BG, AC, CH, CI, CJ, AD, DK, DL(I checked)A breadth first search that prioritized next_ above firstChild_ would have this order:
A, AB, AC, AD, DK, DL, CH, CI CJ, BE, BF, BGA depth first traversal would be thus:
BE, BF, BG, AB, CH, CI, CJ, AC, DK, DL, AD, AThat traversal prioritizes firstChild_ and goes from prev_ to next_. A depth first prioritizing firstChild_ and going from next_ to prev_ would be this:
DL, DK, AD, CJ, CI, CH, AC, BG, BF, BE, AB, Awhich is the exact reverse order of the breadth first search prioritizing firstChild_ and going from prev_ to next_.