package brs.visitor;

import brs.*;
import rac.*;
import fp.*;

/**
 * Processes the tree nodes via breadth-first traversal.
 * Uses a FIFO queue.
 * @author DXN
 */
public class BreadthFirst implements IVisitor {

    private IRAContainer _queue = new LRSQueueFactory().makeRAC();
    private ILambda _f;
    private Object _acc; // accumulated result.
    
    // IRAContainer visitor to go through the queue and process each tree
    // in the queus with a given BiTree visitor.
    private IRACVisitor _processQ = new IRACVisitor() {
        public Object emptyCase(IRAContainer q, Object treeVis) {
            return _acc;
        }
        public Object nonEmptyCase(IRAContainer q, Object treeVis) {
            ((BiTree)q.get()).execute((IVisitor)treeVis, null);
            return q.execute(this, treeVis);
        }
    };
    
    public BreadthFirst(ILambda f) {
        _f = f;
    }

    /**
     */
    public Object emptyCase(BiTree host, Object b) {
        return b;
    }

    /**
     * Prints the root data, saves the left and right subtrees in _queue
     * and "process" _queue.
     */
    public Object nonEmptyCase(BiTree host, final Object b) {
        _queue.put(host.getLeftSubTree());
        _queue.put(host.getRightSubTree());
        _acc = _f.apply(host, b);
        return _queue.execute(_processQ, new IVisitor() {
            public Object emptyCase(BiTree h, Object nu) {
                return b;
            }
            public Object nonEmptyCase(final BiTree h, Object nu) {
                _queue.put(h.getLeftSubTree());
                _queue.put(h.getRightSubTree());
                _acc = _f.apply(h, _acc);
                return _acc;
            }
        });
    }
            
    /**
     * Simple test code.
     */
    public static void main(String[] args) {
        BiTree t0 = new BiTree();
        t0.insertRoot(new Integer(1));
        BiTree t1 = new BiTree();
        t1.insertRoot(new Integer(2));
        BiTree t2 = new BiTree();
        t2.insertRoot(new Integer(3));
        t0.setLeftSubTree(t1);
        t0.setRightSubTree(t2);
        t1.getLeftSubTree().insertRoot(new Integer(4));
        t1.getLeftSubTree().getRightSubTree().insertRoot(new Integer(6));
        t2.getRightSubTree().insertRoot(new Integer(5));
        t2.getRightSubTree().getLeftSubTree().insertRoot(new Integer(7));
        System.out.println("t0 is: \n" + t0 + "\n");
        System.out.println("Breadth first printing:");
        ILambda print = new ILambda() {
            public Object apply(Object... args) {
                System.out.print("" + args[1] + ((BiTree)args[0]).getRootDat());
                return " ";
            }
        };
        t0.execute(new BreadthFirst(print), "");
        
        System.out.println("\nBreadth first adding:");
        ILambda add= new ILambda() {
            public Object apply(Object... args) {
                return (Integer)args[1] + (Integer)((BiTree)args[0]).getRootDat();
            }
        };
        System.out.println(t0.execute(new BreadthFirst(add), 0));
        System.out.println("\nDone!");
    }
}