/**
 * Copyright (C) 2019 Adrien Hopkins
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
package org.unitConverter.expressionParser;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.UnaryOperator;

/**
 * An object that can parse expressions with unary or binary operators.
 * 
 * @author Adrien Hopkins
 * @param <T>
 *            type of object that exists in parsed expressions
 * @since 2019-03-14
 */
// TODO: possibly make this class non-final?
public final class ExpressionParser<T> {
	/**
	 * A builder that can create {@code ExpressionParser<T>} instances.
	 * 
	 * @author Adrien Hopkins
	 * @param <T>
	 *            type of object that exists in parsed expressions
	 * @since 2019-03-17
	 */
	public static final class Builder<T> {
		/**
		 * A function that obtains a parseable object from a string. For example, an integer {@code ExpressionParser}
		 * would use {@code Integer::parseInt}.
		 * 
		 * @since 2019-03-14
		 */
		private final Function<String, T> objectObtainer;

		/**
		 * A map mapping operator strings to operator functions, for unary operators.
		 * 
		 * @since 2019-03-14
		 */
		private final Map<String, PriorityUnaryOperator<T>> unaryOperators;

		/**
		 * A map mapping operator strings to operator functions, for binary operators.
		 * 
		 * @since 2019-03-14
		 */
		private final Map<String, PriorityBinaryOperator<T>> binaryOperators;

		/**
		 * Creates the {@code Builder}.
		 * 
		 * @param objectObtainer
		 *            a function that can turn strings into objects of the type handled by the parser.
		 * @throws NullPointerException
		 *             if {@code objectObtainer} is null
		 * @since 2019-03-17
		 */
		public Builder(final Function<String, T> objectObtainer) {
			this.objectObtainer = Objects.requireNonNull(objectObtainer, "objectObtainer must not be null.");
			this.unaryOperators = new HashMap<>();
			this.binaryOperators = new HashMap<>();
		}

		/**
		 * Adds a binary operator to the builder.
		 * 
		 * @param text
		 *            text used to reference the operator, like '+'
		 * @param operator
		 *            operator to add
		 * @param priority
		 *            operator's priority, which determines which operators are applied first
		 * @return this builder
		 * @throws NullPointerException
		 *             if {@code text} or {@code operator} is null
		 * @since 2019-03-17
		 */
		public Builder<T> addBinaryOperator(final String text, final BinaryOperator<T> operator, final int priority) {
			Objects.requireNonNull(text, "text must not be null.");
			Objects.requireNonNull(operator, "operator must not be null.");

			// Unfortunately, I cannot use a lambda because the PriorityBinaryOperator requires arguments.
			final PriorityBinaryOperator<T> priorityOperator = new PriorityBinaryOperator<T>(priority) {
				@Override
				public T apply(final T t, final T u) {
					return operator.apply(t, u);
				}

			};
			this.binaryOperators.put(text, priorityOperator);
			return this;
		}

		/**
		 * Adds a unary operator to the builder.
		 * 
		 * @param text
		 *            text used to reference the operator, like '-'
		 * @param operator
		 *            operator to add
		 * @param priority
		 *            operator's priority, which determines which operators are applied first
		 * @return this builder
		 * @throws NullPointerException
		 *             if {@code text} or {@code operator} is null
		 * @since 2019-03-17
		 */
		public Builder<T> addUnaryOperator(final String text, final UnaryOperator<T> operator, final int priority) {
			Objects.requireNonNull(text, "text must not be null.");
			Objects.requireNonNull(operator, "operator must not be null.");

			// Unfortunately, I cannot use a lambda because the PriorityUnaryOperator requires arguments.
			final PriorityUnaryOperator<T> priorityOperator = new PriorityUnaryOperator<T>(priority) {
				@Override
				public T apply(final T t) {
					return operator.apply(t);
				}
			};
			this.unaryOperators.put(text, priorityOperator);
			return this;
		}

		/**
		 * @return an {@code ExpressionParser<T>} instance with the properties given to this builder
		 * @since 2019-03-17
		 */
		public ExpressionParser<T> build() {
			return new ExpressionParser<>(this.objectObtainer, this.unaryOperators, this.binaryOperators);
		}
	}

	/**
	 * A binary operator with a priority field that determines which operators apply first.
	 * 
	 * @author Adrien Hopkins
	 * @param <T>
	 *            type of operand and result
	 * @since 2019-03-17
	 */
	private static abstract class PriorityBinaryOperator<T>
			implements BinaryOperator<T>, Comparable<PriorityBinaryOperator<T>> {
		/**
		 * The operator's priority. Higher-priority operators are applied before lower-priority operators
		 */
		private final int priority;

		/**
		 * Creates the {@code PriorityBinaryOperator}.
		 * 
		 * @param priority
		 *            operator's priority
		 * @since 2019-03-17
		 */
		public PriorityBinaryOperator(final int priority) {
			this.priority = priority;
		}

		/**
		 * Compares this object to another by priority.
		 */
		@Override
		public int compareTo(final PriorityBinaryOperator<T> o) {
			if (this.priority < o.priority)
				return -1;
			else if (this.priority > o.priority)
				return 1;
			else
				return 0;
		}
	}

	/**
	 * A unary operator with a priority field that determines which operators apply first.
	 * 
	 * @author Adrien Hopkins
	 * @param <T>
	 *            type of operand and result
	 * @since 2019-03-17
	 */
	private static abstract class PriorityUnaryOperator<T>
			implements UnaryOperator<T>, Comparable<PriorityUnaryOperator<T>> {
		/**
		 * The operator's priority. Higher-priority operators are applied before lower-priority operators
		 */
		private final int priority;

		/**
		 * Creates the {@code PriorityUnaryOperator}.
		 * 
		 * @param priority
		 *            operator's priority
		 * @since 2019-03-17
		 */
		public PriorityUnaryOperator(final int priority) {
			this.priority = priority;
		}

		/**
		 * Compares this object to another by priority.
		 */
		@Override
		public int compareTo(final PriorityUnaryOperator<T> o) {
			if (this.priority < o.priority)
				return -1;
			else if (this.priority > o.priority)
				return 1;
			else
				return 0;
		}
	}

	/**
	 * The types of tokens that are available.
	 * 
	 * @author Adrien Hopkins
	 * @since 2019-03-14
	 */
	private static enum TokenType {
		OBJECT, UNARY_OPERATOR, BINARY_OPERATOR;
	}

	/**
	 * A function that obtains a parseable object from a string. For example, an integer {@code ExpressionParser} would
	 * use {@code Integer::parseInt}.
	 * 
	 * @since 2019-03-14
	 */
	private final Function<String, T> objectObtainer;

	/**
	 * A map mapping operator strings to operator functions, for unary operators.
	 * 
	 * @since 2019-03-14
	 */
	private final Map<String, PriorityUnaryOperator<T>> unaryOperators;

	/**
	 * A map mapping operator strings to operator functions, for binary operators.
	 * 
	 * @since 2019-03-14
	 */
	private final Map<String, PriorityBinaryOperator<T>> binaryOperators;

	/**
	 * Creates the {@code ExpressionParser}.
	 * 
	 * @param objectObtainer
	 *            function to get objects from strings
	 * @param unaryOperators
	 *            operators available to the parser
	 * @since 2019-03-14
	 */
	private ExpressionParser(final Function<String, T> objectObtainer,
			final Map<String, PriorityUnaryOperator<T>> unaryOperators,
			final Map<String, PriorityBinaryOperator<T>> binaryOperators) {
		this.objectObtainer = objectObtainer;
		this.unaryOperators = unaryOperators;
		this.binaryOperators = binaryOperators;
	}

	/**
	 * Converts a given mathematical expression to reverse Polish notation (operators after operands).
	 * <p>
	 * For example,<br>
	 * {@code 2 * (3 + 4)}<br>
	 * becomes<br>
	 * {@code 2 3 4 + *}.
	 * 
	 * @param expression
	 * @return
	 * @since 2019-03-17
	 */
	private String convertExpressionToReversePolish(final String expression) {
		Objects.requireNonNull(expression, "expression must not be null.");

		// TODO method stub org.unitConverter.expressionParser.ExpressionParser.convertExpressionToPolish(expression)
		throw new UnsupportedOperationException();
	}

	/**
	 * Determines whether an inputted string is an object or an operator
	 * 
	 * @param token
	 *            string to input
	 * @return type of token it is
	 * @throws NullPointerException
	 *             if {@code expression} is null
	 * @since 2019-03-14
	 */
	private TokenType getTokenType(final String token) {
		Objects.requireNonNull(token, "token must not be null.");

		if (this.unaryOperators.containsKey(token))
			return TokenType.UNARY_OPERATOR;
		else if (this.binaryOperators.containsKey(token))
			return TokenType.BINARY_OPERATOR;
		else
			return TokenType.OBJECT;
	}

	/**
	 * Parses an expression.
	 * 
	 * @param expression
	 *            expression to parse
	 * @return result
	 * @throws NullPointerException
	 *             if {@code expression} is null
	 * @since 2019-03-14
	 */
	public T parseExpression(final String expression) {
		return this.parseReversePolishExpression(this.convertExpressionToReversePolish(expression));
	}

	/**
	 * Parses an expression expressed in reverse Polish notation.
	 * 
	 * @param expression
	 *            expression to parse
	 * @return result
	 * @throws NullPointerException
	 *             if {@code expression} is null
	 * @since 2019-03-14
	 */
	private T parseReversePolishExpression(final String expression) {
		Objects.requireNonNull(expression, "expression must not be null.");

		final Deque<T> stack = new ArrayDeque<>();

		// iterate over every item in the expression, then
		for (final String item : expression.split(" ")) {
			// choose a path based on what kind of thing was just read
			switch (this.getTokenType(item)) {

				case BINARY_OPERATOR:
					if (stack.size() < 2)
						throw new IllegalStateException(String.format(
								"Attempted to call binary operator %s with only %d arguments.", item, stack.size()));

					// get two arguments and operator, then apply!
					final T o1 = stack.pop();
					final T o2 = stack.pop();
					final BinaryOperator<T> binaryOperator = this.binaryOperators.get(item);

					stack.push(binaryOperator.apply(o1, o2));
					break;

				case OBJECT:
					// just add it to the stack
					stack.push(this.objectObtainer.apply(item));
					break;

				case UNARY_OPERATOR:
					if (stack.size() < 1)
						throw new IllegalStateException(String.format(
								"Attempted to call unary operator %s with only %d arguments.", item, stack.size()));

					// get one argument and operator, then apply!
					final T o = stack.pop();
					final UnaryOperator<T> unaryOperator = this.unaryOperators.get(item);

					stack.push(unaryOperator.apply(o));
					break;
				default:
					throw new AssertionError(
							String.format("Internal error: Invalid token type %s.", this.getTokenType(item)));

			}
		}

		// return answer, or throw an exception if I can't
		if (stack.size() > 1)
			throw new IllegalStateException("Computation ended up with more than one answer.");
		else if (stack.size() == 0)
			throw new IllegalStateException("Computation ended up without an answer.");
		return stack.pop();
	}
}