// Set implementation
// Matt Perry (mjperry2@uiuc.edu)

#include <fstream>
#include <iostream>
#include "parser.h"
#include "set.h"

using namespace std;

Element vars[26];

Parser::Token Parser::eval()
{
    Token tok = testop();

    if (curtok.type != END && curtok.type != ERROR)
	return error("trailing garbage");

    return tok;
}

// test operations, lowest precedence:
// element [ set-operation
// element ![ set-operation
// set-operation < set-operation
// set-operation <= set-operation
// set-operation = set-operation
// set-operation != set-operation
Parser::Token Parser::testop()
{
    Token left = setop();
    Token right;

    for (;;) {
	switch (curtok.type) {
	case INSET:
	    right = setop();
	    if (left.type != NUMBER && left.type != STRING && left.type != SET)
		return error("expected element for left operand in [ operation");
	    if (right.type != SET)
		return error("expected set for right operand in [ operation");
	    left = Token(NUMBER, Element((double)test_in_set(left.e, *right.e.set)));
	    break;
	case NOTINSET:
	    right = setop();
	    if (left.type != NUMBER && left.type != STRING && left.type != SET)
		return error("expected element for left operand in ![ operation");
	    if (right.type != SET)
		return error("expected set for right operand in ![ operation");
	    left = Token(NUMBER, Element((double)!test_in_set(left.e, *right.e.set)));
	    break;
	case SUBSET:
	    right = setop();
	    if (left.type != SET)
		return error("expected set for left operand in <= operation");
	    if (right.type != SET)
		return error("expected set for right operand in <= operation");
	    left = Token(NUMBER, Element((double)test_subset(*left.e.set, *right.e.set)));
	    break;
	case PROPER_SUBSET:
	    right = setop();
	    if (left.type != SET)
		return error("expected set for left operand in < operation");
	    if (right.type != SET)
		return error("expected set for right operand in < operation");
	    left = Token(NUMBER, Element((double)test_proper_subset(*left.e.set, *right.e.set)));
	    break;
	case EQUAL:
	    right = setop();
	    if (left.type != SET)
		return error("expected set for left operand in = operation");
	    if (right.type != SET)
		return error("expected set for right operand in = operation");
	    left = Token(NUMBER, Element((double)test_equal(*left.e.set, *right.e.set)));
	    break;
	case NOTEQUAL:
	    right = setop();
	    if (left.type != SET)
		return error("expected set for left operand in != operation");
	    if (right.type != SET)
		return error("expected set for right operand in != operation");
	    left = Token(NUMBER, Element((double)!test_equal(*left.e.set, *right.e.set)));
	    break;
	default:
	    return left;
	}
    }

}

// set operations:
// assignment + assignment
// assignment ^ assignment
// assignment - assignment
// assignment / assignment
Parser::Token Parser::setop()
{
    Token left = assign();
    Token right;

    for (;;) {
	switch (curtok.type) {
	case UNION:
	    right = assign();
	    if (left.type != SET)
		return error("expected set for left operand in + operation");
	    if (right.type != SET)
		return error("expected set for right operand in + operation");
	    left = Token(set_union(*left.e.set, *right.e.set));
	    break;
	case INTERSECTION:
	    right = assign();
	    if (left.type != SET)
		return error("expected set for left operand in ^ operation");
	    if (right.type != SET)
		return error("expected set for right operand in ^ operation");
	    left = Token(set_intersection(*left.e.set, *right.e.set));
	    break;
	case DIFF:
	    right = assign();
	    if (left.type != SET)
		return error("expected set for left operand in - operation");
	    if (right.type != SET)
		return error("expected set for right operand in - operation");
	    left = Token(set_difference(*left.e.set, *right.e.set));
	    break;
	case SYMDIFF:
	    right = assign();
	    if (left.type != SET)
		return error("expected set for left operand in / operation");
	    if (right.type != SET)
		return error("expected set for right operand in / operation");
	    left = Token(set_symmetric_difference(*left.e.set, *right.e.set));
	    break;
	default:
	    return left;
	}
    }
}

// assignment:
// element : element
Parser::Token Parser::assign()
{
    Token left = getelem();
    Token right;

    for (;;) {
	switch (curtok.type) {
	case ASSIGN:
	    right = getelem();
	    if (left.type != VAR)
		return error("expected variable for left operand in : operation");
	    if (right.type != NUMBER && right.type != STRING && right.type != SET)
		return error("expected element for right operand in : operation");
	    vars[toupper(left.var)-'A'] = right.e;
	    left = right;
	    break;
	default:
	    return expand(left);
	}
    }
}

// element:
// ( test-operation )
// { set }
// number
// "string"
// [a-zA-Z] (variable)
// | test-op | (size of test-operation, must be a set)
// @ element (powerset of element, must be a set)
Parser::Token Parser::getelem()
{
    Token tok;

    get_token();

    switch (curtok.type) {
    case LP:
	tok = testop();
	if (curtok.type != RP)
	    return error("missing ')'");
	get_token();
	return tok;
    case LB:
	tok = getset();
	if (curtok.type != RB)
	    return error("missing '}'");
	get_token();
	return tok;
    case RB:
	return curtok;
    case NUMBER:
    case STRING:
    case SET:
    case VAR:
	tok = curtok;
	get_token();
	return tok;
    case SIZE:
	tok = testop();
	if (tok.type != SET)
	    return error("expected set for |S| operation");
	if (curtok.type != SIZE)
	    return error("missing '|'");
	get_token();
	return Token(NUMBER, Element((double)tok.e.set->size()));
    case POWERSET:
	tok = expand(getelem());
	if (tok.type != SET)
	    return error("expected set for @ operation");
	return Token(SET, set_powerset(*tok.e.set));
    case END:
	return curtok;
    }

    return error("invalid token");
}

// set:
// {}
// { element1, ..., elementN }
Parser::Token Parser::getset()
{
    Set s;

    switch (curtok.type) {
    case LB:
	while (true) {
	    Token t = setop();
	    if (t.type == RB && s.size() == 0) // empty set
		break;

	    if (t.type == NUMBER || t.type == STRING || t.type == SET)
		s.insert(t.e);
	    if (curtok.type == RB)
		break;
	    if (curtok.type != COMMA)
		return error("invalid set syntax");
	}

	return Token(s);
    };

    return error("invalid token");
}

// reads the next token from the expression string, and returns what it is
Parser::Token Parser::get_token()
{
    while (isspace(*expr))
	++expr;

    if (*expr == 0) {
	curtok.type = END;
	return curtok;
    }
    if (isdigit(*expr)) {
	curtok = Token(NUMBER, Element(atof(expr)));
	while (isdigit(*expr) || (*expr == '.'))
	    expr++;
	return curtok;
    }
    if (*expr == '"') {
	char* beg = ++expr;
	while (*expr && *expr != '"')
	    expr++;
	if (*expr == 0)
	    return (curtok=error("unterminated string"));
	*expr = 0;

	curtok = Token(STRING, Element(string(beg)));

	*expr++ = '"';
	return curtok;
    }
    if (isalpha(*expr)) {
	curtok.type = VAR;
	curtok.var = *expr++;
	return curtok;
    }
    if (strncmp(expr, "<=", 2) == 0) {
	curtok.type = SUBSET;
	expr += 2;
	return curtok;
    }
    if (strncmp(expr, "!=", 2) == 0) {
	curtok.type = NOTEQUAL;
	expr += 2;
	return curtok;
    }
    if (strncmp(expr, "![", 2) == 0) {
	curtok.type = NOTINSET;
	expr += 2;
	return curtok;
    }
    if ((strchr("+^-/<=[@|(){},:", *expr)) != NULL) {
	curtok.type = TokenType(*expr);
	expr++;
	return curtok;
    }

    return (curtok=error("syntax error"));
}

// expand a token from it's variable form.
// has no effect if it's not a variable.
// if it is a variable, expands to a token of the variable's type and value
Parser::Token Parser::expand(const Token& tok)
{
    if (tok.type != VAR)
	return tok;

    int i = toupper(tok.var)-'A';
    switch (vars[i].type) {
    case Element::NONE: // undefined var, don't expand
	return tok;
    case Element::NUMBER:
	return Token(NUMBER, vars[i]);
    case Element::STRING:
	return Token(STRING, vars[i]);
    case Element::SET:
	return Token(SET, vars[i]);
    }
    return error("bad var type???");
}

Parser::Token Parser::error(char* str)
{
    Token tok(ERROR);
    tok.e = Element(str);

    if (*expr == 0)
	cerr << "error: " << str << endl;
    else
	cerr << "error: " << str << " at " << expr << endl;

    got_error = true;
    return tok;
}

void help()
{
    ifstream is("README");
    string line;
    int i = 0;

    while (getline(is, line)) {
	cout << line << endl;
	if (i++ >= 20) {
	    i = 0;
	    cout << "<hit enter>";
	    getline(cin, line);
	}
    }
}

int main()
{
    string input;

    cout << "Set calculator 1.0" << endl;
    cout << "written by Matt Perry (mjperry2@uiuc.edu)" << endl;
    cout << endl;
    cout << "Type 'help' for help, 'quit' to quit" << endl;

    while (true) {
	cout << "> ";
	getline(cin, input);
	if (input == "quit")
	    break;
	if (input == "help") {
	    help();
	    continue;
	}
	if (input == "")
	    continue;

	char* str = strdup(input.c_str());
	Parser pobj(str);
	Parser::Token tok = pobj.eval();
	if (tok.type != Parser::ERROR)
	    cout << tok.e << endl;
	free(str);
    }

    return 0;
}