package shuntingyard

import "core:container/queue"

import "../lex"
import syn "../syntax-tree/"

shunting_yard :: proc(tokens: []syn.TOKEN) -> []syn.TOKEN {
	ast := make([dynamic]syn.TOKEN)
	operator_stack := &queue.Queue(syn.TOKEN){}
	queue.init(operator_stack)

	for token in tokens {
		#partial switch token.type {
		case syn.TOKEN_TYPE.NUMBER:
			append(&ast, token)
		case syn.TOKEN_TYPE.OPERATOR:
			if queue.len(operator_stack^) == 0 {
				queue.push_back(operator_stack, token)
				continue
			}
			current_token_importance := get_operator_importance(token)
			for queue.len(operator_stack^) != 0 {
				last_token := queue.peek_back(operator_stack)
				last_token_importance := get_operator_importance(last_token^)

				// If operators importance is lower than the last ones on the stack (or equal)
				// and operator is not ^, pop last operator from stack to ast
				if current_token_importance <= last_token_importance {
					append(&ast, queue.pop_back(operator_stack))
				} else {
					//append(&ast, token)
					queue.push_back(operator_stack, token)
					break
				}
			}

			if queue.len(operator_stack^) == 0 {
				queue.push_back(operator_stack, token)
			}
		case syn.TOKEN_TYPE.OPEN_PARENTHESIS:
			queue.push_back(operator_stack, token)
		case syn.TOKEN_TYPE.CLOSE_PARENTHESIS:
			for queue.peek_back(operator_stack).type != syn.TOKEN_TYPE.OPEN_PARENTHESIS {
				append(&ast, queue.pop_back(operator_stack))
			}
			queue.pop_back(operator_stack)
		}
	}

	for queue.len(operator_stack^) != 0 {
		append(&ast, queue.pop_back(operator_stack))
	}

	return ast[:]
}

get_operator_importance :: proc(operator: syn.TOKEN) -> int {
	switch operator.value {
	case syn.OPERATOR_TYPE.DIVIDE, syn.OPERATOR_TYPE.MULTIPLY:
		// Numbers taken from Wikipedia
		return 3
	case syn.OPERATOR_TYPE.MINUS, syn.OPERATOR_TYPE.PLUS:
		return 2
	}

	return 0

}