BooleanOperator.java

package edu.caltech.nanodb.expressions;


import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

import edu.caltech.nanodb.relations.ColumnInfo;
import edu.caltech.nanodb.relations.ColumnType;
import edu.caltech.nanodb.relations.Schema;
import edu.caltech.nanodb.relations.SchemaNameException;


/**
 * This class provides the standard Boolean logical operators AND, OR, and NOT,
 * for two or more terms (or exactly one term, in the case of NOT).  In
 * addition, there are several methods provided for manipulating Boolean
 * expressions, since many plan equivalence-rules involve manipulations of the
 * Boolean logical expressions associated with Select and Theta-Join plan nodes.
 */
public class BooleanOperator extends Expression {

    /**
     * This enumeration specifies the different kinds of Boolean operators that
     * this class can implement.
     */
    public enum Type {
        AND_EXPR("AND"),
        OR_EXPR("OR"),
        NOT_EXPR("NOT");

        /** The string representation for each operator.  Used for printing. **/
        private final String stringRep;

        /**
         * Construct a Type enum with the specified string representation.
         *
         * @param rep the string representation of the type
         */
        Type(String rep) {
            stringRep = rep;
        }

        /**
         * Accessor for the operator type's string representation.
         *
         * @return the string representation of the operator type
         */
        public String stringRep() {
            return stringRep;
        }
    }


    /** Specifies the type of this Boolean operator. */
    private Type type;


    /**
     * The list of one or more terms in this expression.  If the expression type
     * is {@link BooleanOperator.Type#NOT_EXPR} then this will contain exactly
     * one term.
     */
    private ArrayList<Expression> terms;


    public BooleanOperator(Type type, Collection<Expression> terms) {

        if (type == null)
            throw new NullPointerException("type cannot be null");

        this.type = type;
        this.terms = new ArrayList<Expression>();

        if (terms != null) {
            for (Expression term : terms)
                addTerm(term);
        }
    }


    public BooleanOperator(Type type) {
        this(type, null);
    }


    /**
     * Returns the type of this Boolean expression.
     *
     * @return the type of this Boolean expression.
     */
    public Type getType() {
        return type;
    }


    public void addTerm(Expression term) {
        if (term == null)
            throw new NullPointerException("term cannot be null");

        terms.add(term);
    }


    public Expression getTerm(int i) {
        return terms.get(i);
    }


    public ColumnInfo getColumnInfo(Schema schema) throws SchemaNameException {
        // Boolean operators always return Boolean values, so just pass a
        // Boolean value in to the TypeConverter to get out the corresponding
        // SQL datatype.
        ColumnType colType =
            new ColumnType(TypeConverter.getSQLType(Boolean.FALSE));

        return new ColumnInfo(colType);
    }


    public Object evaluate(Environment env) throws ExpressionException {

        if (terms.size() == 0) {
            throw new ExpressionException("Boolean " + type +
                " expression contains no terms!");
        }

        Object objResult;
        boolean boolResult;

        if (type == Type.NOT_EXPR) {
            if (terms.size() != 1) {
                throw new ExpressionException(
                    "NOT-expressions may have only one term.");
            }

            // Evaluate the term...
            objResult = terms.get(0).evaluate(env);
            if (objResult == null)
                boolResult = false;  // TODO:  this is UNKNOWN, not FALSE.
            else
                boolResult = TypeConverter.getBooleanValue(objResult);

            // ...then negate it.
            boolResult = !boolResult;
        }
        else {
            // AND/OR expression.

            if (terms.size() < 1) {
                throw new ExpressionException(type.stringRep() +
                    "-expressions must have at least one term.");
            }

            if (type == Type.AND_EXPR) {
                boolResult = true;
            }
            else {
                assert type == Type.OR_EXPR : "Unexpected type value " + type + "!";
                boolResult = false;
            }

            for (Expression term : terms) {
                // Evaluate the i-th term, and combine it with the current answer.
                objResult = term.evaluate(env);

                boolean termValue;
                if (objResult == null)
                    termValue = false;  // TODO:  this is UNKNOWN, not FALSE.
                else
                    termValue = TypeConverter.getBooleanValue(objResult);

                if (type == Type.AND_EXPR && !termValue) {
                    // AND term is false, so we are done.  Answer is false.
                    boolResult = false;
                    break;
                }
                else if (type == Type.OR_EXPR && termValue) {
                    // OR term is true, so we are done.  Answer is true.
                    boolResult = true;
                    break;
                }
            }
        }

        return Boolean.valueOf(boolResult);
    }


    @Override
    public Expression traverse(ExpressionProcessor p) {
        p.enter(this);

        for (int i = 0; i < terms.size(); i++) {
            Expression e = terms.get(i).traverse(p);
            terms.set(i, e);
        }

        return p.leave(this);
    }


    /**
     * Returns a string representation of this Boolean logical expression and
     * its subexpressions, including parentheses where necessary to specify
     * precedence.
     */
    @Override
    public String toString() {
        // Convert all of the components into string representations.

        StringBuilder buf = new StringBuilder();

        if (type == Type.NOT_EXPR) {
            assert terms.size() == 1 : "NOT expressions must have exactly one term";

            buf.append(type.stringRep());
            buf.append(' ');

            Expression term = terms.get(0);
            String termStr = term.toString();
            if (term instanceof BooleanOperator) {
                BooleanOperator termOp = (BooleanOperator) term;
                if (termOp.type != Type.NOT_EXPR)
                    termStr = '(' + termStr + ')';
            }

            buf.append(termStr);
        }
        else if (type == Type.AND_EXPR) {
            assert terms.size() >= 1 : "AND expressions must have at least one term";

            boolean first = true;
                for (Expression term : terms) {
                if (first)
                    first = false;
                else
                    buf.append(' ').append(type.stringRep()).append(' ');

                String termStr = term.toString();

                if (term instanceof BooleanOperator) {
                    BooleanOperator termOp = (BooleanOperator) term;
                    if (termOp.type == Type.OR_EXPR)
                        termStr = '(' + termStr + ')';
                }

                buf.append(termStr);
            }
        }
        else {  // OR_EXPR
            assert type == Type.OR_EXPR;
            assert terms.size() >= 1 : "OR expressions must have at least one term";

            boolean first = true;
            for (Expression term : terms) {
                if (first)
                    first = false;
                else
                    buf.append(' ').append(type.stringRep()).append(' ');

                buf.append(term.toString());
            }
        }

        return buf.toString();
    }


    /**
     * This method returns true if this Boolean expression contains any terms
     * that reference the exact set of tables specified in the arguments.  See
     * the documentation for {@link #getTermsReferencingAllTables} for more
     * details on what is considered to be a "matching" term by this method.
     *
     * @design This method is <em>slightly</em> more efficient than the
     *         get/remove methods, since it stops after it has found the first
     *         term that satisfies the specified conditions.  However, if there
     *         will be a subsequent call to the get or remove method, it's
     *         probably most efficient to just call it directly.
     *
     * @param tableNames a collection of table-names to look for in the terms.
     *
     * @return A list of terms that reference all of the tables specified in the
     *         input list, and no others.
     */
    public boolean hasTermsReferencingAllTables(String... tableNames) {

        // Put table names into a set so we can easily do membership tests.
        HashSet<String> inputTables = new HashSet<String>();
        for (String tableName : tableNames)
            inputTables.add(tableName);

        // Iterate through each term in this Boolean operator.  For each term,
        // find out what symbols the term contains.  Then, see if the term only
        // references the tables in the input set.
        HashSet<ColumnName> symbols = new HashSet<ColumnName>();
        HashSet<String> exprTables = new HashSet<String>();
        for (Expression term : terms) {
            symbols.clear();
            exprTables.clear();

            term.getAllSymbols(symbols);
            for (ColumnName colName : symbols) {
                if (colName.isTableSpecified())
                    exprTables.add(colName.getTableName());
            }

            if (inputTables.equals(exprTables))
                return true;
        }

        return false;
    }


    /**
     * This method finds and returns a list of all terms in this Boolean
     * expression that reference the exact set of tables specified in the
     * arguments.  If a term references other tables outside of this set then it
     * will not be returned.  If a term doesn't reference some table in this set
     * then it will not be returned.
     *
     * @param tableNames a collection of table-names to look for in the terms.
     *
     * @return A list of terms that reference all of the tables specified in the
     *         input list, and no others.
     */
    public List<Expression> getTermsReferencingAllTables(String... tableNames) {
        // Call the helper, with "remove" flag set to false.
        return _getTermsReferencingAllTables(tableNames, false);
    }


    /**
     * This method finds, removes, and returns a list of all terms in this
     * Boolean expression that reference the exact set of tables specified in
     * the arguments.  If a term references other tables outside of this set
     * then it will not be returned.  If a term doesn't reference some table in
     * this set then it will not be returned.
     * <p>
     * The sole difference between this and {@link #getTermsReferencingAllTables}
     * is that this method also removes the found terms from this Boolean
     * expression object.
     *
     * @param tableNames a collection of table-names to look for in the terms.
     *
     * @return A list of terms that reference all of the tables specified in the
     *         input list, and no others.  These terms are also removed from the
     *         Boolean expression object.
     */
    public List<Expression> removeTermsReferencingAllTables(String... tableNames) {
        // Call the helper, with "remove" flag set to true.
        return _getTermsReferencingAllTables(tableNames, true);
    }


    /**
     * This is a private helper function used by both the
     * {@link #getTermsReferencingAllTables} and
     * {@link #removeTermsReferencingAllTables} methods.
     *
     * @param tableNames an array of table-names to look for in the terms.
     * @param remove if <tt>true</tt> then matching terms will be removed from
     *        this Boolean operator's list of terms.
     *
     * @return A list of terms that reference all of the tables specified in the
     *         input list, and no others.
     */
    private List<Expression> _getTermsReferencingAllTables(String[] tableNames,
        boolean remove) {

        ArrayList<Expression> found = new ArrayList<>();

        // Put table names into a set so we can easily do membership tests.
        HashSet<String> inputTables = new HashSet<>();
        for (String tableName : tableNames)
            inputTables.add(tableName);

        // Iterate through each term in this Boolean operator.  For each term,
        // find out what symbols the term contains.  Then, see if the term only
        // references the tables in the input set.
        HashSet<ColumnName> symbols = new HashSet<>();
        HashSet<String> exprTables = new HashSet<>();
        Iterator<Expression> termIter = terms.iterator();
        while (termIter.hasNext()) {
            Expression term = termIter.next();

            symbols.clear();
            exprTables.clear();

            term.getAllSymbols(symbols);
            for (ColumnName colName : symbols) {
                if (colName.isTableSpecified())
                    exprTables.add(colName.getTableName());
            }

            if (inputTables.equals(exprTables)) {
                found.add(term);
                if (remove)
                    termIter.remove();
            }
        }

        return found;
    }


    /**
     * Returns the number of terms in the boolean expression.
     *
     * @return the number of terms in the boolean expression.
     */
    public int getNumTerms() {
        return terms.size();
    }


    /**
     * Removes the i<sup>th</sup> term, starting from 0.
     *
     * @param i the index of the term to remove.
     *
     * @throws IllegalArgumentException if the specified index is invalid.
     */
    public void removeTerm(int i) {
        if (i < 0 || i >= getNumTerms()) {
            throw new IllegalArgumentException("Term-index " + i +
                " is out of range [0, " + getNumTerms() + ")");
        }

        terms.remove(i);
    }


    /**
     * Simplifies a Boolean expression by eliminating and de-nesting as much of
     * the expression as possible.
     */
    @Override
    public Expression simplify() {
        // Go through and try to simplify anything we can inside the operator
        for (int i = 0; i < terms.size(); i++) {
            Expression e = terms.get(i);
            terms.set(i, e.simplify());
        }

        // There is only one simplification for the NOT expression:
        // NOT (NOT P) = P
        if (type == Type.NOT_EXPR) {
            assert terms.size() == 1;
            if (terms.get(0) instanceof BooleanOperator) {
                BooleanOperator nested = (BooleanOperator) terms.get(0);
                if (nested.type == Type.NOT_EXPR) {
                    assert nested.terms.size() == 1;
                    return nested.terms.get(0);
                }
            }

            // If we fall through to here, we can't do any simplification of
            // the NOT expression.
            return this;
        }

        // Handle AND and OR expression simplifications.
        assert type == Type.AND_EXPR || type == Type.OR_EXPR;

        // If there is only one term, just return the term.
        if (terms.size() == 1)
            return terms.get(0);

        int i = 0;
        while (i < terms.size()) {
            Expression e = terms.get(i);
            if (e instanceof BooleanOperator) {
                BooleanOperator b = (BooleanOperator) e;
                // If the nested Boolean operator is the same type as this
                // one, we can lift up the terms and put them in this
                // operator.
                if (b.type == type) {
                    terms.remove(i);
                    terms.addAll(i, b.terms);
                }
                else {
                    i++;
                }

                // The way this loop is constructed, we will repeat this
                // check/lift process for any child nodes we just lifted up,
                // that are also BooleanOperators of the same type, since
                // the new nodes will now be at index i.
            }
        }


        return this;
    }


    /**
     * Performs a value-eqality test for whether the specified object is an
     * expression with the same structure and contents.
     *
     * @param obj the object to which we are comparing
     */
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof BooleanOperator) {
            BooleanOperator other = (BooleanOperator) obj;

            return (type == other.type && terms.equals(other.terms));
        }
        return false;
    }


    /**
     * Computes the hash-code of an Expression.
     */
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + type.hashCode();
        hash = 31 * hash + terms.hashCode();
        return hash;
    }


    /**
     * Creates a copy of expression.
     */
    @Override
    @SuppressWarnings("unchecked")
    protected Object clone() throws CloneNotSupportedException {
        BooleanOperator expr = (BooleanOperator) super.clone();

        // Type is immutable, copy it.
        expr.type = this.type;

        expr.terms = (ArrayList<Expression>) terms.clone();

        return expr;
    }
}