Re: [HACKERS] WITH RECURSIVE patch V0.1

On Mon, May 19, 2008 at 11:56:17AM +0200, Zoltan Boszormenyi wrote:
> >From an implementation point of view, the only difference between
> >breadth-first and depth-first is that your tuplestore needs to be LIFO
> >instead of FIFO.
> 
> Are you sure? I think a LIFO tuplestore would simply return reversed
> breadth-first order. Depth-first means for every new record descend into
> another recursion first then continue with the next record on the right.

Say your tree looks like: 
Root->A, D 
A->B,C
D->E,F

LIFO pushes A and D. It then pops A and pushes B and C. B and C have no
children and are returned. Then D is popped and E and F pushed. So the
returned order is: A,B,C,D,E,F. You could also do B,C,A,E,F,D if you
wanted.

FIFO pushes A and D. It then pops A and puts B and C at *the end*. It
then pops D and pushes E and F at the end. So you get the order
A,D,B,C,E,F

Hope this helps,
-- 
Martijn van Oosterhout   <[email protected]>   http://svana.org/kleptog/
> Please line up in a tree and maintain the heap invariant while 
> boarding. Thank you for flying nlogn airlines.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIMVEmIB7bNG8LQkwRAinMAJ0Usp4+Fte3+S2mUx5CTfvRs/bdJQCfSNmW
sXco8KzLPkLydpaLKBAeB8w=
=wAjf
-----END PGP SIGNATURE-----