//! Crate for tokenizing, lexing, and parsing for the `calc` project. This crate uses a simple stack algorithm to do order of operations.
//! Unlike many algorithms, this parser does not create a parse tree and instead does the evaluation on the fly.
//!
//! Lexing can be done with the [`Lexer`](lexer::Lexer) type. Parsing can then be done with the [`parse_and_evaluate`] function.

#![warn(clippy::complexity)]
#![warn(clippy::pedantic)]
#![allow(clippy::match_like_matches_macro)]
#![allow(clippy::must_use_candidate)]
#![allow(clippy::module_name_repetitions)]
#![allow(clippy::missing_errors_doc)]
#![no_std]
extern crate alloc;

use core::iter::Peekable;

use alloc::vec::Vec;
use error::{ParseError, ParseOrEvalError};
use lexer::Token;

mod error;
pub mod lexer;

#[derive(Clone, Copy, Debug)]
pub enum Operator {
    Add,
    Subtract,
    Multiply,
    Divide,
    Exponentiate,
}

impl Operator {
    pub fn from_char(c: u8) -> Option<Self> {
        match c {
            b'+' => Some(Self::Add),
            b'-' => Some(Self::Subtract),
            b'*' => Some(Self::Multiply),
            b'/' => Some(Self::Divide),
            b'^' => Some(Self::Exponentiate),
            _ => None,
        }
    }
    pub fn priority(self) -> u8 {
        match self {
            Operator::Add | Operator::Subtract => 0,
            Operator::Multiply | Operator::Divide => 1,
            Operator::Exponentiate => 2,
        }
    }
    pub fn is_priority_left_to_right(priority: u8) -> bool {
        match priority {
            2 => false,
            _ => true,
        }
    }
    pub fn should_be_evaluated_before(self, next_operator: Option<Self>) -> bool {
        let Some(next_operator) = next_operator else {
            return true;
        };

        match self.priority().cmp(&next_operator.priority()) {
            core::cmp::Ordering::Less => false,
            core::cmp::Ordering::Equal => Self::is_priority_left_to_right(self.priority()),
            core::cmp::Ordering::Greater => true,
        }
    }

    /// Compares `priority1` and `priority2` while correctly handling when `priority1` and `priority2` are equal.
    /// `priority2=None` signifies that there is no second operator
    fn is_first_priority_greater(priority1: u8, priority2: Option<u8>) -> bool {
        let Some(priority2) = priority2 else {
            return true;
        };

        match priority1.cmp(&priority2) {
            core::cmp::Ordering::Less => false,
            core::cmp::Ordering::Equal => Self::is_priority_left_to_right(priority1),
            core::cmp::Ordering::Greater => true,
        }
    }
}

/// Represents a simple expression eg. `9+10` or `-5`
#[derive(Debug)]
pub struct Expression<I> {
    pub first_argument: Option<I>,
    pub operator: Operator,
    pub second_argument: I,
}

fn get_last_binary_operator_from_iter<'a, I, T>(iter: I) -> Option<Operator>
where
    I: Iterator<Item = &'a ParseStackObject<T>> + DoubleEndedIterator,
    T: 'a,
{
    for stack_object in iter.rev() {
        match stack_object {
            ParseStackObject::BinaryOperator(_, operator) => return Some(*operator),
            ParseStackObject::UnaryOperator(_) => continue,
            _ => break,
        }
    }
    None
}

// Remove `(` `object` from the stack and return `object`
fn remove_opening_parenthesis<I>(stack: &mut Vec<ParseStackObject<I>>) -> Result<I, ParseError> {
    match stack.pop() {
        Some(ParseStackObject::Object(object)) => {
            stack.pop();

            return Ok(object);
        }
        Some(so) => {
            stack.push(so);
        }
        _ => (),
    }

    Err(ParseError::UnexpectedClosingParenthesis())
}

fn get_object_in_binary_context<I, T>(
    argument: T,
    token_stream: &mut Peekable<I>,
) -> Result<ParseStackObject<T>, ParseError>
where
    I: Iterator<Item = Token<T>>,
{
    let next_token = token_stream.peek();

    match next_token {
        Some(Token::Operator(operator)) => {
            let operator = *operator;

            token_stream.next();

            Ok(ParseStackObject::BinaryOperator(argument, operator))
        }

        None | Some(Token::ClosingParenthesis()) => Ok(ParseStackObject::Object(argument)),

        _ => Err(ParseError::ExpectedOperatorOrClosingParenthesis()),
    }
}

/// Returns Some(Ok(())) if the stack can be simplified. Returns Ok(Err(e)) if there is an error evaluating the popped expression. Returns None if the expression cannot be simplified
fn simplify_stack_once<E>(
    stack: &mut Vec<ParseStackObject<E::Item>>,
) -> Option<Result<(), E::Error>>
where
    E: Evaluator,
{
    let mut stack_iter = stack.iter();

    let stack_object2 = stack_iter.next_back()?;
    let stack_object1 = stack_iter.next_back()?;

    let operator2 = stack_object2.operation();
    stack_object2.first_operand()?; // We cannot simplify if our second operation is unary because we're missing an operand

    let operator1 = stack_object1.operation()?;

    let operator2_priority = operator2.map(Operator::priority);
    let operator1_priority = if stack_object1.first_operand().is_some() {
        // Operator is binary
        operator1.priority()
    } else {
        // Operator is unary, so we should promote it to the last binary operator's priority.
        // This is for operations like 3^-2*5 which should be equivalent to (3^-2)*5 and not 3^-(2*5) even though * is normally evaluated before -
        get_last_binary_operator_from_iter(stack_iter)
            .map_or(0, Operator::priority)
            .max(operator1.priority())
    };

    if Operator::is_first_priority_greater(operator1_priority, operator2_priority) {
        let argument2 = stack.pop()?.try_into_first_operand()?;
        let argument1 = stack.pop()?.try_into_first_operand();

        let expr = Expression {
            first_argument: argument1,
            operator: operator1,
            second_argument: argument2,
        };

        let result = match E::evaluate(expr) {
            Ok(val) => val,
            Err(err) => return Some(Err(err)),
        };

        let new_stack_object = if let Some(operator) = operator2 {
            ParseStackObject::BinaryOperator(result, operator)
        } else {
            ParseStackObject::Object(result)
        };

        stack.push(new_stack_object);

        return Some(Ok(()));
    }

    None
}

#[derive(Debug)]
enum ParseStackObject<I> {
    BinaryOperator(I, Operator),
    UnaryOperator(Operator),
    Object(I),
    OpenParenthesis(),
}

impl<I> ParseStackObject<I> {
    fn try_into_first_operand(self) -> Option<I> {
        match self {
            ParseStackObject::BinaryOperator(arg, _) => Some(arg),
            ParseStackObject::Object(obj) => Some(obj),
            ParseStackObject::UnaryOperator(_) | ParseStackObject::OpenParenthesis() => None,
        }
    }

    fn first_operand(&self) -> Option<&I> {
        match &self {
            ParseStackObject::BinaryOperator(arg, _) => Some(arg),
            ParseStackObject::Object(obj) => Some(obj),
            ParseStackObject::UnaryOperator(_) | ParseStackObject::OpenParenthesis() => None,
        }
    }
    fn operation(&self) -> Option<Operator> {
        match &self {
            ParseStackObject::BinaryOperator(_, op) | ParseStackObject::UnaryOperator(op) => {
                Some(*op)
            }
            ParseStackObject::Object(_) | ParseStackObject::OpenParenthesis() => None,
        }
    }
}

/// An error for when a number is too large to fit into a number type
pub struct NumberTooLarge;

/// A trait for Zero-Sized-Types that can evaluate expressions
pub trait Evaluator {
    /// The number type to be evaluated
    type Item;
    type Error;

    fn evaluate(expression: Expression<Self::Item>) -> Result<Self::Item, Self::Error>;
    fn add_digit(number_so_far: Self::Item, next_digit: u8) -> Self::Item;
    fn zero() -> Self::Item;
}

/// Parses and evaluates the expression defined by `token_stream` using the [evaluator](crate::Evaluator) `E`.
pub fn parse_and_evaluate<E, I>(token_stream: &mut I) -> Result<E::Item, ParseOrEvalError<E::Error>>
where
    I: Iterator<Item = Token<E::Item>>,
    E: Evaluator,
{
    let mut stack = Vec::<ParseStackObject<E::Item>>::new();
    let mut token_stream = token_stream.peekable();

    loop {
        if let Some(v) = simplify_stack_once::<E>(&mut stack) {
            if let Err(e) = v {
                return Err(ParseOrEvalError::EvalError(e));
            }
            continue;
        }

        // TODO: fix early exiting with invalid parenthesis

        if let Some(next_token) = token_stream.next() {
            match next_token {
                Token::Number(num) => {
                    let stack_object = get_object_in_binary_context(num, &mut token_stream)?;

                    stack.push(stack_object);
                }
                Token::Operator(op) => {
                    stack.push(ParseStackObject::UnaryOperator(op));
                }
                Token::OpenParenthesis() => {
                    stack.push(ParseStackObject::OpenParenthesis());
                }
                Token::ClosingParenthesis() => {
                    let object = match remove_opening_parenthesis(&mut stack) {
                        Ok(object) => object,
                        Err(err) => return Err(err.into()),
                    };

                    let stack_object = match get_object_in_binary_context(object, &mut token_stream)
                    {
                        Ok(obj) => obj,
                        Err(err) => return Err(err.into()),
                    };

                    stack.push(stack_object);
                }
            }
        } else {
            break;
        }
    }

    if stack.len() == 1 {
        if let Some(ParseStackObject::Object(obj)) = stack.pop() {
            return Ok(obj);
        }
    }

    Err(ParseOrEvalError::ParseError(
        ParseError::UnexpectedClosingParenthesis(),
    ))
}