#include <stdio.h>
#include <malloc.h>
#include <string.h>

const char* copy(const char* s)
{
    if (s == 0)
        return 0;
    char* r = new char[strlen(s)+1];
    strcpy(r, s);
    return r;
}
const char* copy(const char* s, const char* e)
{
    int len = e - s;
    char* r = new char[len + 1];
    strncpy(r, s, len);
    r[len] = '\0';
    return r;
}

int compare(const char* a, const char* b)
{
    int len_a = strlen(a);
    int len_b = strlen(b);
    if (len_a < len_b) return -1;
    if (len_a > len_b) return 1;
    return strcmp(a, b);
}

const char* name(const char* s) { return *s == '\0' ? "I" : s; }

class Reduction
{
public:
    Reduction(char l, const char* f, const char* t, Reduction* n) : letter(l), from(copy(f)), to(copy(t)), partialOfI(false), next_sibling(n), children(0) {}
    Reduction(char l, const char* f, const char* fe, const char* t, Reduction* n) : letter(l), from(copy(f, fe)), to(copy(t)), partialOfI(false), next_sibling(n), children(0) {}
    ~Reduction() { delete from; delete to; delete next_sibling; delete children; }
    char letter;
    const char* from;
    const char* to;
    bool partialOfI; // partial sequence of a sequence that reduces to I
    Reduction* next_sibling;
    Reduction* children;
    void print(int depth)
    {
        printf("%d '%s'", depth, from);
        if (to != 0)
            printf(" -> %s", to);
        printf("\n");
        if (children != 0)
            children->print(depth+1);
        if (next_sibling != 0)
            next_sibling->print(depth);
    }
};

Reduction *reductions = 0;

bool addReduction(Reduction** ref_red, const char* at, const char* from, const char* to, bool &error)
{
    bool result = true;
    while (*ref_red != 0 && (*ref_red)->letter < *at)
        ref_red = &(*ref_red)->next_sibling;
    if (at[1] == '\0')
    {
        if (*ref_red != 0 && (*ref_red)->letter == *at)
        {
            if (to != 0)
            {
                if ((*ref_red)->partialOfI && *to == '\0')
                    error = true; // found a partial sequence of a sequence that reduces to I
                if ((*ref_red)->to != 0)
                {
                    int comp = compare(to, (*ref_red)->to);
                    if (comp >= 0)
                        return false; // found a longer or equal reduction for 'from'; nothing added
                    else
                        error = true; // found a shorter reduction: should maybe not occur
                }
                (*ref_red)->to = copy(to);
            }
        }
        else
            (*ref_red) = new Reduction(at[0], from, to, *ref_red);
    }
    else
    {
        if (*ref_red == 0 || (*ref_red)->letter != *at)
            (*ref_red) = new Reduction(at[0], from, at+1, 0, *ref_red);
        else
            result = false;
        if (to != 0 && *to == '\0')
            (*ref_red)->partialOfI = true;
        if (addReduction(&(*ref_red)->children, at+1, from, to, error))
            result = true;
    }
    return result;
}

void normalize(char *seq)
{
    for (char *s = seq; *s != '\0';)
    {
        char *r = s;
        Reduction* red = 0;
        Reduction* child = reductions;
        for (;*r != '\0';r++)
        {
            for (; child != 0; child = child->next_sibling)
            {
                if (child->letter == *r)
                    break;
            }
            if (child == 0)
            {
                red = 0;
                break;
            }
            red = child;
            if (red->to != 0)
                break;
            child = red->children;
        }
        if (red != 0 && red->to != 0)
        {
            char *t = s;
            for (const char *k = red->to; *k != '\0'; k++)
                *t++ = *k;
            strcpy(t, r+1);
            s = seq;
        }
        else
            s++;
    }
}

bool addReduction(const char* from, const char* to, bool &error)
{
    if (to != 0 && *to != '\0')
        addReduction(&reductions, to, to, 0, error);
    return addReduction(&reductions, from, from, to, error);
}

Reduction* find(const char* seq)
{
    for (Reduction *reduction = reductions; ; reduction = reduction->children)
    {
        while (reduction != 0 && reduction->letter < *seq)
            reduction = reduction->next_sibling;
        if (reduction == 0 || reduction->letter != *seq)
            break;
        if (*(++seq) == '\0')
            return reduction;
    }
    return 0;
}

class DepthFirstAllIterator
{
public:
    DepthFirstAllIterator(Reduction *root) : _root(root), _depth(0)
    {
        _path[0] = _root;
    }
    void reset() { _depth = 0; _path[0] = _root; }
    bool more() { return _path[0] != 0; }
    void next()
    {
        if (_path[_depth]->children != 0 && _depth < 100)
        {
            _path[_depth+1] = _path[_depth]->children;
            _depth++;
            return;
        }
        while(_depth >= 0) 
        {
            if (_path[_depth]->next_sibling != 0)
            {
                _path[_depth] = _path[_depth]->next_sibling;
                return;
            }
            _path[_depth] = 0;
            _depth--;
        }
    }
    int from_len() { return _depth+1; }
    const char* from() { return _path[_depth]->from; }
    const char* to() { return _path[_depth]->to; }
private:
    Reduction* _root;
    Reduction* _path[100];
    int _depth;
};

class DepthFirstIterator : public DepthFirstAllIterator
{
public:
    DepthFirstIterator(Reduction *root) : DepthFirstAllIterator(root)
    {
        while (more() && to() == 0)
            DepthFirstAllIterator::next();
    }
    void next()
    {
        do
            DepthFirstAllIterator::next();
        while (more() && to() == 0);
    }
};

class Iterator
{
public:
    Iterator(Reduction* root, int depth = 0) : _it(root), _more(true), _depth(depth)
    {
        for (int i = 1; i < 101; i++)
            _available_length[i] = false;
        _max_length = 0;
        for (; _it.more(); _it.next())
        {
            _available_length[_it.from_len()] = true;
            if (_it.from_len() > _max_length)
                _max_length = _it.from_len();
        }
        if (_max_length == 0)
        {
            _more = false;
            return;
        }
        _cur_length = 1 + depth;
        if (_cur_length > _max_length)
        {
            _more = false;
            return;
        }
        while (!_available_length[_cur_length])
            _cur_length++;
        _it.reset();
        while (_it.from_len() != _cur_length)
            _it.next();
    }
    bool more() { return _more; }
    void next()
    {
        for (;;)
        {
            _it.next();
            if (!_it.more())
                break;
            if (_it.from_len() == _cur_length)
                return;
        }
        if (++_cur_length > _max_length)
        {
            _more = false;
            return;
        }
        while (!_available_length[_cur_length])
            _cur_length++;
        _it.reset();
        while (_it.from_len() != _cur_length)
            _it.next();
    }
    const char *from() { return _it.from(); }
    const char *to() { return _it.to(); }
private:
    DepthFirstIterator _it;
    int _depth;
    bool _available_length[101];
    int _max_length;
    int _cur_length;
    bool _more;
};

void findElements(char *seq, char *at, int &c, FILE* fout)
{
    for (Reduction* r = reductions; r != 0; r = r->next_sibling)
    {
        *at = r->letter;
        at[1] = '\0';
        Reduction *red = find(seq);
        if (red == 0 || red->to == 0)
        {
            char buffer[200];
            strcpy(buffer, seq);
            normalize(buffer);
            if (strcmp(buffer, seq) == 0)
            {
                if (fout != 0) fprintf(fout, "= %s\n", seq);
                c++;
                findElements(seq, at + 1, c, fout);
            }
            else
                if (fout != 0) fprintf(fout, "  %s -> %s\n", seq, buffer);
        }
        else
            if (fout != 0) fprintf(fout, "  %s = %s\n", seq, red->to);
    }
}

void derive(bool &error)
{
    bool go = true;
    for (int pass = 0; pass < 10 && go && !error; pass++)
    {
        go = false;
        for (Iterator first_it(reductions); first_it.more(); first_it.next())
        {
            for (const char* common = first_it.from() + 1; *common != '\0'; common++)
            {
                Reduction* second = find(common);
                if (second != 0 && second->children)
                {
                    for (Iterator second_it(second->children, strlen(common)); second_it.more(); second_it.next())
                    {
                        char left[200];
                        sprintf(left, "%.*s%s", common - first_it.from(), first_it.from(), second_it.to() == 0 ? "<null>" : second_it.to());
                        char right[200];
                        sprintf(right, "%s%s", first_it.to() == 0 ? "" : first_it.to(), second_it.from() + strlen(common));
                        normalize(left);
                        normalize(right);
                        if (strcmp(left, right) != 0)
                        {
                            if (compare(left, right) < 0)
                            {
                                if (addReduction(right, left, error))
                                    go = true;
                            }
                            else
                            {
                                if (addReduction(left, right, error))
                                    go = true;
                            }
                        }
                    }
                }
            }
        }
    }
    if (go && !error)
    {
        printf("== still go after 10 passes\n");
        error = true;
    }
}

void testCaseCountElements(const char *rule, int size)
{
    delete reductions;
    reductions = 0;

    bool error = false;
    for (const char *s = rule; *s != '\0';)
    {
        char buffer[50];
        char *t = buffer;
        while (*s != '\0' && *s != ' ')
            *t++ = *s++;
        *t = '\0';
        addReduction(buffer, "", error);
        if (*s == ' ')
            s++;
    }
    derive(error);
    if (error)
    {
        printf("Error: Error during reduction of rule %s\n");
        return;
    }
    int c = 1;
    for (DepthFirstAllIterator it(reductions); it.more(); it.next())
        if (it.to() == 0)
        {
            char buffer[200];
            strcpy(buffer, it.from());
            normalize(buffer);
            if (strcmp(buffer, it.from()) == 0)
                c++;
        }
    if (c != size)
    {
        c = 1;
        char seq[200];
        findElements(seq, seq, c, 0);
    }    
    if (c != size)
    {
        printf("Error: Counted size %d, instead of expected %d for rule %s\n", c, size, rule);
        printf("I +\n");
        char seq[200];
        for (DepthFirstAllIterator it(reductions); it.more(); it.next())
        {
            printf("%s", it.from());
            if (it.to() != 0)
                printf(" -> %s", it.to());
            else
            {
                char buffer[200];
                strcpy(buffer, it.from());
                normalize(buffer);
                if (strcmp(buffer, it.from()) == 0)
                    printf(" +");
                else
                    printf(" (-> %s)", buffer);
            }
            printf("\n");
        }
        printf("\n");
        c = 1;
        findElements(seq, seq, c, stdout);
        printf("%d\n", c);
        return;
    }
    printf("Info: Passed rule %s\n", rule);
}

int main(int argc, char* argv[])
{
    testCaseCountElements("aa bb abab",                      4); // Klein group K4
    testCaseCountElements("aaa bb abaab",                    6); // group C3xC2
    testCaseCountElements("aaa bb abab",                     6); // symmetric group S3,dihedral Dih6 (triangle)
    testCaseCountElements("aaa bb ababab",                  12); // alternating group A4 (tetrahedron)
    testCaseCountElements("aaa bb abaababaab",              24); // group A4xC2
    testCaseCountElements("aaa bb ababababab",              60); // alternating group A5 (icosahedron)
    testCaseCountElements("aaa bbb abab",                   12); // alternating group A4 (tetrahedron)
    testCaseCountElements("aaaa bb abaaab",                  8); // group C4xC2
    testCaseCountElements("aaaa bb abab",                    8); // dihedral group Dih8 (square)
    testCaseCountElements("aaaa bb abababab aabaab",        16); // group K8:C2
    testCaseCountElements("aaaa bbb abaaabb",               12); // group C4xC3
    testCaseCountElements("aaaa bbbb ababbb aabb",           8); // dicyclic group Dic8, quaternion Q8
    testCaseCountElements("aaaa bbbb abaaabbb",             16); // group C4xC4
    testCaseCountElements("aaaa bbbb ababbb",               16); // group C4:C4
    testCaseCountElements("aaaaa bbbb abababab aabaaaabbb", 20); // Frobenius group F20
    testCaseCountElements("aaaaaa bb abaaaaab",             12); // group C6xC2
    testCaseCountElements("aaaaaa bb abab",                 12); // dihedral group Dih12
    testCaseCountElements("aaaaaa bbbb ababbb aaabb",       12); // dicyclic group Dic12
    testCaseCountElements("aaaaaaaa bb abaaaaaaab",         16); // group C8xC2

    return 0;
}