package org.matheclipse.core.builtin.function;

import org.matheclipse.core.eval.exception.Validate;
import org.matheclipse.core.eval.interfaces.AbstractCoreFunctionEvaluator;
import org.matheclipse.core.expression.F;
import org.matheclipse.core.interfaces.IAST;
import org.matheclipse.core.interfaces.IExpr;
import org.matheclipse.core.patternmatching.IPatternMatcher;
import org.matheclipse.core.patternmatching.PatternMatcher;

public class FreeQ extends AbstractCoreFunctionEvaluator {

	public FreeQ() {
	}

	public IExpr evaluate(final IAST ast) {
		Validate.checkSize(ast, 3);
		IExpr arg1 = F.eval(ast.arg1());
		IExpr arg2 = F.eval(ast.arg2());
		final IPatternMatcher matcher = new PatternMatcher(arg2);
		if (matcher.isRuleWithoutPatterns()) {
			// special for FreeQ(), don't implemented in MemberQ()!
			if (arg1.isOrderlessAST() && arg2.isOrderlessAST() && arg1.head().equals(arg2.head())) {
				if (!isFreeOrderless((IAST) arg1, (IAST) arg1)) {
					return F.False;
				}
			}
		}
		return F.bool(arg1.isFree(matcher, true));
	}

	/**
	 * Checks if orderless1.size() is greaterequal orderless2.size() and returns false, if
	 * every argument in orderless2 equals an argument in orderless1. I.e. orderless1
	 * doesn't contain every argument of orderless2.
	 * 
	 * @param orderless1
	 * @param orderless2
	 * @return false if orderless1.size() is greaterequal orderless2.size() and if every
	 *         argument in orderless2 equals an argument in orderless1
	 */
	public boolean isFreeOrderless(IAST orderless1, IAST orderless2) {
		if (orderless1.size() >= orderless2.size()) {
			IExpr temp;
			boolean evaled = false;
			int[] array = new int[orderless1.size()];
			for (int i = 1; i < orderless2.size(); i++) {
				temp = orderless2.get(i);
				evaled = false;
				for (int j = 1; j < orderless1.size(); j++) {
					if (array[j] != (-1) && temp.equals(orderless1.get(j))) {
						array[j] = -1;
						evaled = true;
						break;
					}
				}
				if (!evaled) {
					break;
				}
			}
			if (evaled) {
				return false;
			}
		}
		return true;
	}
}