changeset 137:c292c67b3100 pairPro

add generateTransitionList function
author masa
date Fri, 04 Dec 2015 20:32:09 +0900
parents 15815fcb6c2f
children ea2810db8d87
files c/regexParser/bitVector.cc c/regexParser/bitVector.h c/regexParser/subsetConstraction.cc
diffstat 3 files changed, 43 insertions(+), 127 deletions(-) [+]
line wrap: on
line diff
--- a/c/regexParser/bitVector.cc	Fri Dec 04 19:10:00 2015 +0900
+++ b/c/regexParser/bitVector.cc	Fri Dec 04 20:32:09 2015 +0900
@@ -2,58 +2,31 @@
 #include <stdlib.h>
 #include <string.h>
 #include "bitVector.h"
-extern BitVectorListPtr allocateBitVectorList();
 const BitVectorPtr allocateBitVector();
 
-BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) {
+BitVectorListPtr createBitVector(NodePtr n) {
     BitVectorListPtr nextBvl = allocateBitVectorList();
-    nextBvl->bi = bitSet(n->nodeNumber);
+    nextBvl->bi = bitSet(nextBvl,n->nodeNumber);
     return nextBvl;
 }
 
 const BitVectorPtr allocateBitVector() {
-
     BitVectorPtr bi = (BitVectorPtr)malloc(sizeof(BitVector));
-    if (bi == NULL) {
-        fprintf(stderr, "Failed to allocate memory.\n");
-        exit(-1);
-    }
-
-    bi->bitContainer = (unsigned long*)malloc(sizeof(unsigned long)*bi->arrayNum);
-    if (bi->bitContainer == NULL) {
-        fprintf(stderr, "Failed to allocate memory.\n");
-        exit(-1);
-    }
-
-    for (int i = 0; i < bi->arrayNum; i++) {
-        bi->bitContainer[i] = 0;
-    }
-
+    bi->bitContainer = 0;
     return bi;
 }
 
-BitVectorPtr bitSet(int bitSetPosition) {
-
-    BitVectorPtr bi = allocateBitVector();
-
-    bi->arrayNum = (bitSetPosition + BITBLOCK) / BITBLOCK;
-
-    int arrayPosition = bitSetPosition / BITBLOCK;
-
+void bitSet(BitVectorPtr bi, int bitSetPosition) {
     unsigned long tmp = 1 << (bitSetPosition % BITBLOCK);
-    bi->bitContainer[arrayPosition] = bi->bitContainer[arrayPosition] | tmp;
-
-    return bi;
+    bi->bitContainer = bi->bitContainer | tmp;
+    return;
 }
 
 void bitPrint(BitVectorPtr bi) {
-    for (int i = 0; i < bi->arrayNum ; i++) {
-        unsigned long vec = bi->bitContainer[i];
-        for (int j = 0; j < BITBLOCK; j++) {
-            printf( "%lu", vec & 1 );
-            vec >>= 1;
-        }
-        printf(" ");
+    unsigned long vec = bi->bitContainer;
+    for (int j = 0; j < BITBLOCK; j++) {
+        putchar((vec & 1)?'1:'0');
+        vec >>= 1;
     }
-    puts("");
+    printf("\n");
 }
--- a/c/regexParser/bitVector.h	Fri Dec 04 19:10:00 2015 +0900
+++ b/c/regexParser/bitVector.h	Fri Dec 04 20:32:09 2015 +0900
@@ -1,20 +1,14 @@
 #include "regexParser.h"
 
-#define BITBLOCK (sizeof(unsigned long) * 8)
 typedef struct bitVector {
-    int arrayNum;
-    unsigned long *bitContainer;
+    unsigned long bitContainer;
 }BitVector,*BitVectorPtr;
 
 typedef struct bitVectorList {
     bitVectorList *self;
-    BitVectorPtr bi;
-    bitVectorList* initBvl;
-    bitVectorList* next[256];
-    bool isLoopAnker;
-    bool isLoop;
+    bitVectorList *next;
 }BitVectorList, *BitVectorListPtr;
 
-BitVectorListPtr createBitVector(NodePtr,BitVectorListPtr);
-BitVectorPtr bitSet(int);
-void bitPrint(BitVectorPtr);
+extern BitVectorListPtr createBitVector(NodePtr node);
+extern BitVectorPtr bitSet(BitVector bitVetor,int bitPosition);
+extern void bitPrint(BitVectorPtr bitVector);
--- a/c/regexParser/subsetConstraction.cc	Fri Dec 04 19:10:00 2015 +0900
+++ b/c/regexParser/subsetConstraction.cc	Fri Dec 04 20:32:09 2015 +0900
@@ -3,86 +3,35 @@
 #include <ctype.h>
 #include "subsetConstraction.h"
 
-void printBitVectorList (BitVectorListPtr bvl) {
-    bool isFirstPrint = true;
-    for (int i = 0; i < 256; i++) {
-        if (bvl->next[i] != NULL) {
-            if (isFirstPrint){
-                puts("----");
-                printf("     state : "); bitPrint(bvl->bi);
-                isFirstPrint = false;
-            }
-            printf("input char : %c\n",i);
-            printf("next state : ");bitPrint(bvl->next[i]->bi);
-            bvl->isLoop = bvl->isLoopAnker;
+typedef struct transitionGenerator {
+    TransitionListPtr tl;
+    StatePtr state;
+    long stateMax;
+} TransitionGenerator, *TransitionGeneratorPtr;
+
+typedef struct tgValue {
+    TransitionListPtr tl;
+    bool asterisk;
+} TGValue, *TGValuePtr;
+
+TGValue generateTransitionList(NodePtr n,TransitionGeneretorPtr tg) {
+
+    if (n->left != NULL) {
+        TGValue tl = generateTransitionList(n->left, tg);
+    }
+    if (n->tokenType == 'a') {
+        printf("%*c",d*4, ' ');
+        for (int i = 0; i < n->cc->cond->w->length; i++) {
+            putchar(n->cc->cond->w->word[i]);
         }
+        printf("(%lu)\n",n->nodeNumber);
+    } else if (n->tokenType == 'c') {
+        TGValue tl = generateTransitionList(n->cc,tg);
+    } else {
+        printf("%*c%c(%lu)\n",d*4, ' ',n->tokenType,n->nodeNumber);
     }
 
-    for (int i = 0; i < 256; i++) {
-        if ((bvl->next[i] != NULL) && !(bvl->isLoop && bvl->isLoopAnker)) {
-        // if ((bvl->next[i] != NULL) ) {
-            printBitVectorList(bvl->next[i]);
-        }
+    if (n->right != NULL) {
+        TGValue tl = generateTransitionList(n->right, tg);
     }
 }
-
-const
-BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr, bool &fromAsterisk) {
-    bool leftIsOr, rightIsOr;
-    if (n->cc->cond->character == '*') {
-        bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
-        unsigned char repertChar = 0;
-        for (int i = 0; i < 256; i++) {
-            if (prev->next[i] != NULL) repertChar = i;
-        }
-        setNextBitVectorList(repertChar, bvl, prev->next[repertChar]); // here
-        bvl->isLoopAnker = true;
-        fromAsterisk = true;
-
-        return prev;
-    } else if (n->cc->cond->character == '|') {
-        bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
-        setNextBitVectorList(n->left->cc->cond->character, prev, bvl);
-        bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
-        setNextBitVectorList(n->right->cc->cond->character, prev, bvl);
-        fromOr = true;
-        return prev;
-    } else if (n->cc->cond->character == '+') {
-        bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
-        setNextBitVectorList(n->left->cc->cond->character, prev, bvl);
-        prev = bvl;
-        bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
-
-        if (leftIsOr){
-            for (int i = 0; i < 256; i++)
-                if (prev->next[i] != NULL)
-                    setNextBitVectorList(n->right->cc->cond->character, prev->next[i], bvl);
-        }
-        else {
-            setNextBitVectorList(n->right->cc->cond->character, prev, bvl);
-        }
-
-        fromOr = false;
-    } else if (n->tokenType == 'a') {
-        bvl = createBitVector(n,bvl);
-        fromOr = false;
-    }
-    return bvl;
-}
-
-const
-BitVectorListPtr setNextBitVectorList(unsigned char inputChar, BitVectorListPtr bvl, BitVectorListPtr next){
-    if (isalnum((int)inputChar)){
-        bvl->next[(int)inputChar] = next;
-    }
-    return next;
-}
-
-BitVectorListPtr createBitVectorList(NodePtr n) {
-    BitVectorListPtr bvl = initBitVector();
-    bool fromOr = false;
-    bool fromAsterisk = false;
-    descendTreeNode(n, bvl, bvl, fromOr, fromAsterisk);
-    printBitVectorList(bvl);
-    return bvl;
-}