Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 168:6b31d6ef9ba4 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
impl createCharClassRange()
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Dec 2015 16:09:19 +0900
parents 3bf2c6d6d53e
children 313f1c176328
comparison
equal deleted inserted replaced
167:3bf2c6d6d53e 168:6b31d6ef9ba4
4 #include "subsetConstraction.h" 4 #include "subsetConstraction.h"
5 5
6 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) { 6 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) {
7 CharClassPtr cc = NEW(CharClass); 7 CharClassPtr cc = NEW(CharClass);
8 return cc; 8 return cc;
9 }
10
11 CharClassPtr createCharClassRange(unsigned long begin, unsigned long end,unsigned long state, CharClassPtr left, CharClassPtr right) {
12 CharClassPtr cc = NEW(CharClass);
13 cc->type = 'r';
14 cc->cond.range.begin = begin;
15 cc->cond.range.end = end;
16 cc->left = left;
17 cc->right = right;
18 cc->nextState.bitContainer = state;
19 return cc;
9 } 20 }
10 21
11 CharClassPtr mergeCCTree(CharClassPtr cc,unsigned char mBegin,unsigned char mEnd,BitVector nextState) { 22 CharClassPtr mergeCCTree(CharClassPtr cc,unsigned char mBegin,unsigned char mEnd,BitVector nextState) {
12 CharClassPtr cc1; 23 CharClassPtr cc1;
13 if (cc) { 24 if (cc) {
14 cc1 = charClassMerge(cc,mBegin,mEnd,nextState); 25 cc1 = charClassMerge(cc,mBegin,mEnd,nextState);
15 } else { 26 } else {
16 cc1 = createCharClassRange(mBegin,mEnd,NULL,NULL); 27 cc1 = createCharClassRange(mBegin,mEnd,nextState.bitContainer,NULL,NULL);
17 cc1->nextState = nextState;
18 } 28 }
19 return cc1; 29 return cc1;
20 } 30 }
21 31
22 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { 32 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
25 // 変更があった場合は新しくリストを作って返す 35 // 変更があった場合は新しくリストを作って返す
26 if (end < cc->cond.range.begin ) { // 1 36 if (end < cc->cond.range.begin ) { // 1
27 if (cc->left) { 37 if (cc->left) {
28 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,charClassMerge(cc->left,begin,end,nextState),cc->right); 38 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,charClassMerge(cc->left,begin,end,nextState),cc->right);
29 } else { 39 } else {
30 CharClassPtr cc1 = createCharClassRange(begin,end,NULL,cc); 40 return createCharClassRange(begin,end,nextState.bitContainer,NULL,cc);
31 cc1->nextState = nextState;
32 return cc1;
33 } 41 }
34 } else if (end == cc->cond.range.begin && begin != end ) { // 2 42 } else if (end == cc->cond.range.begin && begin != end ) { // 2
35 CharClassPtr cc1 = mergeCCTree(cc->left,begin,end-1,nextState); 43 CharClassPtr cc1 = mergeCCTree(cc->left,begin,end-1,nextState);
36 if (cc->cond.range.begin == cc->cond.range.end) { 44 if (cc->cond.range.begin == cc->cond.range.end) {
37 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right); 45 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,
38 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer; 46 cc->nextState.bitContainer | nextState.bitContainer, cc1,cc->right);
39 return cc2;
40 } 47 }
41 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->left,cc->right); 48 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right);
42 cc3->nextState = cc->nextState; 49 return createCharClassRange(cc->cond.range.begin,cc->cond.range.begin,
43 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.begin,cc1,cc3); 50 cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
44 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
45 return cc2;
46 } else if (end < cc->cond.range.end) { // range.begin < end 51 } else if (end < cc->cond.range.end) { // range.begin < end
47 if (begin < cc->cond.range.begin) { // 3 52 if (begin < cc->cond.range.begin) { // 3
48 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); 53 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
49 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->left,cc->right); 54 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right);
50 cc3->nextState = cc->nextState; 55 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
51 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,end,cc1,cc3);
52 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
53 return cc2;
54 } 56 }
55 if (begin == cc->cond.range.begin) { // 6 57 if (begin == cc->cond.range.begin) { // 6
56 CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right); 58 CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right);
57 cc2->nextState = cc->nextState; 59 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc2);
58 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2);
59 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
60 return cc1;
61 } 60 }
62 // 9 61 // 9
63 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL); 62 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL);
64 cc2->nextState = cc->nextState; 63 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right);
65 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right); 64 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc2,cc3);
66 cc3->nextState = cc->nextState;
67 CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3);
68 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
69 return cc1;
70 } else if (end == cc->cond.range.end) { 65 } else if (end == cc->cond.range.end) {
71 if (begin == cc->cond.range.begin) { // 7 66 if (begin == cc->cond.range.begin) { // 7
72 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right); 67 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc->right);
73 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
74 return cc1;
75 } else if (begin < cc->cond.range.begin) { // 4 68 } else if (begin < cc->cond.range.begin) { // 4
76 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); 69 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
77 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,end,cc1,cc->right); 70 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right);
78 cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
79 return cc3;
80 } 71 }
81 // 10 cond.range.begin < begin 72 // 10 cond.range.begin < begin
82 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right); 73 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,NULL,cc->right);
83 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer; 74 return createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,cc2);
84 CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,cc2);
85 cc1->nextState = cc->nextState;
86 return cc1;
87 } 75 }
88 if (begin > cc->cond.range.end ) { // 13 76 if (begin > cc->cond.range.end ) { // 13
89 if (cc->right) { 77 if (cc->right) {
90 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,charClassMerge(cc->right,begin,end,nextState)); 78 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,charClassMerge(cc->right,begin,end,nextState));
91 } else { 79 } else {
92 CharClassPtr cc1 = createCharClassRange(begin,end,cc,NULL); 80 return createCharClassRange(begin,end,nextState.bitContainer,cc,NULL);
93 cc1->nextState = nextState;
94 return cc1;
95 } 81 }
96 } 82 }
97 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { 83 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
98 if (end > cc->cond.range.end) { // cond.range.end < end 84 if (end > cc->cond.range.end) { // cond.range.end < end
99 if (begin == cc->cond.range.begin) { // 8 85 if (begin == cc->cond.range.begin) { // 8
100 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); 86 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
101 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,cc1); 87 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,
102 cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer; 88 cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc1);
103 return cc3;
104 } 89 }
105 if (begin > cc->cond.range.begin) { // 11 90 if (begin > cc->cond.range.begin) { // 11
106 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); 91 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
107 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL); 92 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL);
108 cc3->nextState = cc->nextState; 93 return createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc3,cc1);
109 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc3,cc1);
110 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
111 return cc2;
112 } 94 }
113 } 95 }
114 // begin != end && end != cc->cond.range.end 96 // begin != end && end != cc->cond.range.end
115 if (begin == cc->cond.range.end) { // 12 97 if (begin == cc->cond.range.end) { // 12
116 CharClassPtr cc1 = mergeCCTree(cc->right,begin+1,end,nextState); 98 CharClassPtr cc1 = mergeCCTree(cc->right,begin+1,end,nextState);
117 if (cc->cond.range.begin == cc->cond.range.end) { 99 if (cc->cond.range.begin == cc->cond.range.end) {
118 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right); 100 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right);
119 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
120 return cc2;
121 } 101 }
122 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end-1,cc->left,NULL); 102 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end-1,cc->nextState.bitContainer,cc->left,NULL);
123 cc3->nextState = cc->nextState; 103 return createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
124 CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3);
125 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
126 return cc2;
127 } 104 }
128 } else if (begin < cc->cond.range.begin) { // 5 105 } else if (begin < cc->cond.range.begin) { // 5
129 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); 106 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
130 CharClassPtr cc3 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); 107 CharClassPtr cc3 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
131 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc3); 108 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
132 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
133 return cc2;
134 } else { 109 } else {
135 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); 110 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
136 } 111 }
137 return cc; 112 return cc;
138 } 113 }