package brs.visitor;

import brs.*;
import ordering.*;

/**
 * Finds a data object in a binary host tree that satisfies the
 * Binary Search Tree Property.
 * @author Dung X. Nguyen
 */
public class BSTFinder implements IVisitor {
    private AOrder _order;

    public BSTFinder(AOrder order) {
        _order = order;
    }

    /**
    * Returns null.
    * @param host an empty binary (which obviously satisfies the
    * Binary Search Tree Property).
    * @param input not used
    */
    public Object emptyCase(BiTree host, Object input) {
        return null;
    }

    /**
    * Returns the tree whose root is equal to input via the ordering order,
    * otherwise returns null.
    * @param host non empty and satisfies BSTP.
    * @param input object to be looked up.
    * @return null or a BiTree object whose root is equal input (via order).
    */
    public Object nonEmptyCase(BiTree host, Object input) {
        Object root = host.getRootDat();
        if (_order.lt(input, root)) {
            return host.getLeftSubTree().execute(this, input);
        }
        if (_order.eq(input, root)) {
            return host;
        }
        return host.getRightSubTree().execute(this, input);
    }
}