#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "subsetConstraction.h"

CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) {
    CharClassPtr cc = NEW(CharClass);
    return cc;
}

CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
    // 重なっているccの領域を分割する
    // 必要ならばnextStateを重ねあわせる
    // 変更があった場合は新しくリストを作って返す
    if (end < cc->cond.range.begin ) { // 1
        if (cc->left) {
            return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,charClassMerge(cc->left,begin,end,nextState),cc->right);
        } else {
            CharClassPtr cc1 =  createCharClassRange(begin,end,NULL,cc);
            cc1->nextState = nextState;
            return cc1;
        }
    } else if (end == cc->cond.range.begin && begin != end ) { // 2
        CharClassPtr cc1;
        if (cc->left) {
            cc1 = charClassMerge(cc->left,begin,end-1,nextState);
        } else {
            cc1 = createCharClassRange(begin,end-1,NULL,NULL);
            cc1->nextState = nextState;
        }
        if (cc->cond.range.begin == cc->cond.range.end) {
            CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right);
            cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc2;
        }
        CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->left,cc->right);
        cc3->nextState = cc->nextState;
        CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.begin,cc1,cc3);
        cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
        return cc2;
    } else if (end < cc->cond.range.end) { // range.begin < end
        if (begin < cc->cond.range.begin) {  // 3
            CharClassPtr cc1;
            if (cc->left) {
                cc1 = charClassMerge(cc->left,begin,cc->cond.range.begin-1,nextState);
            } else {
                cc1 = createCharClassRange(begin,cc->cond.range.begin-1,NULL,NULL);
                cc1->nextState = nextState;
            }
            CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->left,cc->right);
            cc3->nextState = cc->nextState;
            CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,end,cc1,cc3);
            cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc2;
        }
        if (begin == cc->cond.range.begin) {  // 6
            CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right);
            cc2->nextState = cc->nextState;
            CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2);
            cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc1;
        }
        // 9
        CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL);
        cc2->nextState = cc->nextState;
        CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right);
        cc3->nextState = cc->nextState;
        CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3);
        cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
        return cc1;
    } else if (end == cc->cond.range.end) {
        if (begin == cc->cond.range.begin) { // 7
            CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right);
            cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc1;
        } else if (begin < cc->cond.range.begin) { // 4
            CharClassPtr cc1;
            if (cc->left) {
                cc1 = charClassMerge(cc->left,begin,cc->cond.range.begin-1,nextState);
            } else {
                cc1 = createCharClassRange(begin,cc->cond.range.begin-1,NULL,NULL);
                cc1->nextState = nextState;
            }
            CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,end,cc1,cc->right);
            cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc3;
        }
        // 10 cond.range.begin < begin
        CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right);
        cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
        CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,cc2);
        cc1->nextState = cc->nextState;
        return cc1;
    }
    if (begin > cc->cond.range.end ) { // 13
        if (cc->right) {
            return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,charClassMerge(cc->right,begin,end,nextState));
        } else {
            CharClassPtr cc1 =  createCharClassRange(begin,end,cc,NULL);
            cc1->nextState = nextState;
            return cc1;
        }
    }
    if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
        if (end > cc->cond.range.end) { // cond.range.end < end
            if (begin == cc->cond.range.begin) {    // 8
                CharClassPtr cc1;
                if (cc->right) {
                    cc1 = charClassMerge(cc->right,cc->cond.range.end+1,end,nextState);
                } else {
                    cc1 = createCharClassRange(cc->cond.range.end+1,end,NULL,NULL);
                    cc1->nextState = nextState;
                }
                CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,cc1);
                cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
                return cc3;
            }
            if (begin > cc->cond.range.begin) {  // 11
                CharClassPtr cc1;
                if (cc->right) {
                    cc1 = charClassMerge(cc->right,cc->cond.range.end+1,end,nextState);
                } else {
                    cc1 = createCharClassRange(cc->cond.range.end+1,end,NULL,NULL);
                    cc1->nextState = nextState;
                }
                CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL);
                cc3->nextState = cc->nextState;
                CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc3,cc1);
                cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
                return cc2;
            }
        }
        // begin != end && end != cc->cond.range.end
        if (begin == cc->cond.range.end) { // 12
            CharClassPtr cc1;
            if (cc->right) {
                cc1 = charClassMerge(cc->right,begin+1,end,nextState);
            } else {
                cc1 = createCharClassRange(begin+1,end,NULL,NULL);
                cc1->nextState = nextState;
            }
            if (cc->cond.range.begin == cc->cond.range.end) {
                CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right);
                cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
                return cc2;
            }
            CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end-1,cc->left,NULL);
            cc3->nextState = cc->nextState;
            CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3);
            cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
            return cc2;
        }
    } else if (begin < cc->cond.range.begin) { // 5
        CharClassPtr cc1;
        if (cc->left) {
            cc1 = charClassMerge(cc->left,begin,cc->cond.range.begin-1,nextState);
        } else {
            cc1 =  createCharClassRange(begin,cc->cond.range.begin-1,NULL,NULL);
            cc1->nextState = nextState;
        }
        CharClassPtr cc3;
        if (cc->right) {
            cc3 = charClassMerge(cc->right,cc->cond.range.end+1,end,nextState);
        } else {
            cc3 =  createCharClassRange(cc->cond.range.end+1,end,NULL,NULL);
            cc3->nextState = nextState;
        }
        CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc3);
        cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
        return cc2;
    } else {
        printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
    }
    return cc;
}

TGValue generateTransition(NodePtr n,TransitionGenerator tg) {
    TGValue tgv2;
    if (n->tokenType == '+') {
        TGValue tgv = generateTransition(n->left,tg);
        if (tgv.asterisk) {
            TGValue tgv1 = generateTransition(n->right,tg);
            tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer;
            return tgv;
        }
        TGValue tgv1 = generateTransition(n->right,tg);
        tgv.ts->nextState = tgv1.ts->nextState;
        return tgv;
    } else if (n->tokenType == '|') {
        TGValue tgv  = generateTransition(n->left,tg);
        TGValue tgv1 = generateTransition(n->right,tg);
        tgv.ts = appendTransition(tgv.ts,tgv1.ts);
        return tgv;
    } else if (n->tokenType == '*') {
        TGValue tgv = generateTransition(n->left,tg);
        tgv.asterisk = true;
        return tgv;
    } else if (n->tokenType == 'c'){
        return tgv2;
    } else if (n->tokenType == 'a'){
        TGValue tgv;
        tgv.ts = (TransitionPtr)malloc(sizeof(Transition));
        tgv.ts->condition = n->cc;
        tgv.ts->nextState = (BitVectorPtr)malloc(sizeof(BitVector));
        bitSet(tgv.ts->nextState,n->nodeNumber);
        tg.ts = appendTransition(tg.ts,tgv.ts);
        return tgv;
    } else {
        // error
    }
    return tgv2;
}

void printTransitionList(TransitionPtr ts) {
    for (;ts;ts = ts->next) {
        printf("\n");
    }
}

TransitionGenerator generateTransitionList(NodePtr n) {
    TransitionGenerator tg;
    tg.ts = (TransitionPtr)malloc(sizeof(Transition));
    generateTransition(n,tg);
    printTransitionList(tg.ts);
    return tg;
}