# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1450519595 -32400
# Node ID 313f1c17632889f2a630becb2ba3247e50527cbe
# Parent  6b31d6ef9ba4ce6d37820500d495226cf886aefa
implement mergeTransition

diff -r 6b31d6ef9ba4 -r 313f1c176328 regexParser/subsetConstraction.cc
--- a/regexParser/subsetConstraction.cc	Sat Dec 19 16:09:19 2015 +0900
+++ b/regexParser/subsetConstraction.cc	Sat Dec 19 19:06:35 2015 +0900
@@ -112,28 +112,89 @@
     return cc;
 }
 
+CharClassWalkerPtr findLeftMost(CharClassPtr next,CharClassWalker walk) {
+    while (next->left) {
+        CharClassStackPtr ts = NEW(CharClassStack);
+        ts->next = walk->stack;
+        ts->left = false;
+        ts->cc = next;
+        walk->stack = ts;
+        next = next->left;
+    }
+    walk->next = next;
+    return walk;
+}
+
+CharClassWalkerPtr createCharClassWalker (CharClassPtr next) {
+    CharClassWalkerPtr walk = NEW(CharClassWalker);
+    walk->next = NULL;
+    if (!next) return walk;
+    if (!next->left) {
+        walk->next = next;
+        return walk;
+    }
+    walk->next = findLeftMost(next,walk);
+    return walk;
+}
+
+bool hasNext(CharClassWalkerPtr walk) {
+    return walk->next != NULL;
+}
+
+CharClassPtr getNext(CharClassWalkerPtr walk) {
+    CharClassPtr current = walk->next;
+    if (ts->left && current->right) {
+        ts->left = true;
+        CharClassPtr next = findLeftMost(current->right,walk);
+        walk->next = next;
+    } else {
+        TransitionPtr tsOld = ts;
+        ts = ts->next;
+        free(tsOld);
+        CharClassPtr ret;
+        if (ts) ret = ts->cc;
+        else ret = NULL;
+        walk->next = ret;
+    }
+    return current;
+}
+
+TransitionPtr mergeTransition(TransitionPtr x,TransitionPtr y) {
+    CharClassWalkerPtr walk = createCharClassWalker(x);
+    CharClassPtr ccy = y->condition;
+    for (CharClassPtr cc = getNext(walk); hasNext(walk); cc=getNext(walk)) {
+        unsigned long begin = cc->range.cond.begin;
+        unsigned long end = cc->range.cond.end;
+        BitVectorPtr bi = cc->nextState;
+        ccy = charClassMerge(ccy,begin,end,*bi);
+    }
+    TransitionPtr z = createTransition(ccy);
+    free(walk);
+    return z;
+}
+
 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;
+            tgv1.ts = mergeTransition(tgv.ts,tgv1.ts);
+            return tgv1;
         }
-        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);
+        tgv.ts = mergeTransition(tgv.ts,tgv1.ts);
+        tgv.asterisk |= tgv1.asterisk;
         return tgv;
     } else if (n->tokenType == '*') {
         TGValue tgv = generateTransition(n->left,tg);
         tgv.asterisk = true;
         return tgv;
     } else if (n->tokenType == 'c'){
+        tgv2.ts = createTransition(n->cc);
         return tgv2;
     } else if (n->tokenType == 'a'){
         TGValue tgv;
diff -r 6b31d6ef9ba4 -r 313f1c176328 regexParser/subsetConstraction.h
--- a/regexParser/subsetConstraction.h	Sat Dec 19 16:09:19 2015 +0900
+++ b/regexParser/subsetConstraction.h	Sat Dec 19 19:06:35 2015 +0900
@@ -11,4 +11,15 @@
     bool asterisk;
 } TGValue, *TGValuePtr;
 
+typedef struct charClassStack {
+    bool left;
+    CharClassPtr cc;
+    CharClassStackPtr next;
+} CharClassStack, *CharClassStackPtr;
+
+typedef struct charClassWalker {
+    CharClassStack stack;
+    CharClassPtr next;
+} CharClassWalker, *CharClassWalkerPtr;
+
 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState);
diff -r 6b31d6ef9ba4 -r 313f1c176328 regexParser/transition.h
--- a/regexParser/transition.h	Sat Dec 19 16:09:19 2015 +0900
+++ b/regexParser/transition.h	Sat Dec 19 19:06:35 2015 +0900
@@ -2,19 +2,17 @@
 
 typedef struct transition {
     CharClassPtr condition;
-    BitVectorPtr nextState;
     struct transition *next;
 } Transition, *TransitionPtr;
 
 typedef struct state {
-    BitVectorPtr bitState;
     TransitionPtr transition;
     struct state *next;
 } State, *StatePtr;
 
 StatePtr createState(BitVectorPtr bi, TransitionPtr ts, StatePtr next);
 StatePtr appendState(StatePtr x, StatePtr y);
-TransitionPtr createTransition(CharClassPtr cc ,BitVectorPtr state);
+TransitionPtr createTransition(CharClassPtr cc);
 TransitionPtr appendTransition0(TransitionPtr curr,TransitionPtr next);
 TransitionPtr appendTransition(TransitionPtr curr,TransitionPtr next);