static ExpressionTree pushDownNot(ExpressionTree root) {
      if (root.getOperator() == ExpressionTree.Operator.NOT) {
        ExpressionTree child = root.getChildren().get(0);
        switch (child.getOperator()) {
          case NOT:
            return pushDownNot(child.getChildren().get(0));
          case CONSTANT:
            return  new ExpressionTree(child.getConstant().not());
          case AND:
            root = new ExpressionTree(ExpressionTree.Operator.OR);
            for(ExpressionTree kid: child.getChildren()) {
              root.getChildren().add(pushDownNot(new
                  ExpressionTree(ExpressionTree.Operator.NOT, kid)));
            }
            break;
          case OR:
            root = new ExpressionTree(ExpressionTree.Operator.AND);
            for(ExpressionTree kid: child.getChildren()) {
              root.getChildren().add(pushDownNot(new ExpressionTree
                  (ExpressionTree.Operator.NOT, kid)));
            }
            break;
          // for leaf, we don't do anything
          default:
            break;
        }
      } else if (root.getChildren() != null) {
        // iterate through children and push down not for each one
        for(int i=0; i < root.getChildren().size(); ++i) {
          root.getChildren().set(i, pushDownNot(root.getChildren().get(i)));
        }
      }
      return root;
    }
Push the negations all the way to just before the leaves. Also remove
double negatives.
@param root the expression to normalize
@return the normalized expression, which may share some or all of the
nodes of the original expression.
storage-api/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java