Mercurial > hg > Applications > Grep

annotate regexParser/CharClass.cc @ 308:1188debbef10

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
separate CharClass
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 08 Feb 2016 12:45:45 +0900
parents regexParser/subsetConstruction.cc@3e78631a6222
children 058c87665213
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
96
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <stdlib.h>
101
2cc097419169 fix print
masasann
parents: 100
diff changeset
3 #include <ctype.h>
191
02031fb73af8 remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 190
diff changeset
4
02031fb73af8 remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 190
diff changeset
5 #include "regexParser.h"
216
4852bfa85db4 spell fix
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 215
diff changeset
6 #include "subsetConstruction.h"
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
7 #include "node.h"
191
02031fb73af8 remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 190
diff changeset
8 #include "BitVector.h"
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
9 #include "error.h"
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
10
308
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
11 #include "CharClass.h"
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
12
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
13
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
14 CharClassPtr createCharClassWord(RegexInfoPtr ri) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
15 CharClassPtr cc = NEW(CharClass);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
16 cc->type = 'a';
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
17 cc->left = NULL;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
18 cc->right = NULL;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
19 cc->cond.w.word = ri->tokenValue;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
20 cc->cond.w.length = ri->ptr - ri->tokenValue;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
21 cc->cond.range.begin = cc->cond.range.end = *ri->tokenValue;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
22 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
23 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
24
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
25 /*
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
26 cond.range.begin cond.range.end
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
27 |----------------|
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
28 1.b---e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
29 2.b------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
30 3.b------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
31 4.b-----------------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
32 5.b----------------------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
33
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
34 |----------------|
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
35 6. b---------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
36 7. b----------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
37 8. b---------------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
38
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
39 |----------------|
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
40 9. b-----e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
41 10. b--------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
42 11. b-------------e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
43
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
44 |----------------|
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
45 12. b-----e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
46
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
47 |----------------|
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
48 13. b--e
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
49
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
50 */
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
51 CharClassPtr insertCharClass(CharClassPtr cc, unsigned long begin, unsigned long end) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
52 if (begin>end) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
53 unsigned long tmp = begin; begin = end; end = tmp;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
54 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
55 if (cc == NULL) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
56 return createCharClassRange(begin,end,0,0,0);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
57 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
58 if (end < cc->cond.range.begin ) { // 1
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
59 if (cc->left) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
60 cc->left = insertCharClass(cc->left,begin,end);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
61 } else {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
62 cc->left = createCharClassRange(begin,end,0,0,0);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
63 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
64 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
65 } else if (end == cc->cond.range.begin ) { // 2
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
66 cc->cond.range.begin = begin;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
67 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
68 } else if (end <= cc->cond.range.end) { // 3,4,6,7,9,10
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
69 if (begin < cc->cond.range.begin) { // 3,4
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
70 cc->cond.range.begin = begin;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
71 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
72 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
73 } else if (begin > cc->cond.range.end ) { // 13
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
74 if (cc->right) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
75 cc->right = insertCharClass(cc->right,begin,end);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
76 } else {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
77 cc->right = createCharClassRange(begin,end,0,0,0);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
78 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
79 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
80 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
81 if (cc->right) {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
82 CharClassPtr right = cc->right;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
83 begin = cc->cond.range.begin;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
84 free(cc);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
85 return insertCharClass(right,begin,end);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
86 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
87 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
88 if (end > cc->cond.range.end) cc->cond.range.end = end; // 11,8
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
89 } else if (begin < cc->cond.range.begin) { // 5
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
90 cc->cond.range.begin = begin;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
91 cc->cond.range.end = end;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
92 } else {
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
93 printf("insertCharClass Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
94 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
95 return cc;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
96 }
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
97
222
c38a7b2dd996 implement exportState function (not correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 220
diff changeset
98
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
99 CharClassPtr createCharClassRange(unsigned long begin, unsigned long end,unsigned long state, CharClassPtr left, CharClassPtr right) {
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
100 CharClassPtr cc = NEW(CharClass);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
101 cc->type = 'r';
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
102 cc->cond.range.begin = begin;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
103 cc->cond.range.end = end;
262
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 261
diff changeset
104 cc->cond.w.word = NULL;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 261
diff changeset
105 cc->cond.w.length = 0;
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
106 cc->left = left;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
107 cc->right = right;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
108 cc->nextState.bitContainer = state;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
109 return cc;
144
d8a4922eceae remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 143
diff changeset
110 }
d8a4922eceae remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 143
diff changeset
111
308
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
112 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) ;
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
113
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
114 CharClassPtr mergeCCTree(CharClassPtr cc,unsigned char mBegin,unsigned char mEnd,BitVector nextState) {
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
115 CharClassPtr cc1;
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
116 if (cc) {
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
117 cc1 = charClassMerge(cc,mBegin,mEnd,nextState);
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
118 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
119 cc1 = createCharClassRange(mBegin,mEnd,nextState.bitContainer,NULL,NULL);
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
120 }
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
121 return cc1;
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
122 }
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
123
261
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
124 /*
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
125 cond.range.begin cond.range.end
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
126 |----------------|
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
127 1.b---e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
128 2.b------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
129 3.b------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
130 4.b-----------------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
131 5.b----------------------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
132
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
133 |----------------|
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
134 6. b---------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
135 7. b----------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
136 8. b---------------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
137
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
138 |----------------|
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
139 9. b-----e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
140 10. b--------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
141 11. b-------------e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
142
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
143 |----------------|
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
144 12. b-----e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
145
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
146 |----------------|
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
147 13. b--e
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
148
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
149 */
2b36dde3ffb7 add cond.range image above charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
150
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
151 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
152 // 重なっているccの領域を分割する
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
153 // 必要ならばnextStateを重ねあわせる
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
154 // 変更があった場合は新しくリストを作って返す
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
155 if (end < cc->cond.range.begin ) { // 1
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
156 if (cc->left) {
188
109d22faf7b5 remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 187
diff changeset
157 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,nextState.bitContainer,charClassMerge(cc->left,begin,end,nextState),cc->right);
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
158 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
159 return createCharClassRange(begin,end,nextState.bitContainer,NULL,cc);
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
160 }
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
161 } else if (end == cc->cond.range.begin && begin != end ) { // 2
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
162 CharClassPtr cc1 = mergeCCTree(cc->left,begin,end-1,nextState);
156
b5ecfc008bcf impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 155
diff changeset
163 if (cc->cond.range.begin == cc->cond.range.end) {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
164 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
165 cc->nextState.bitContainer | nextState.bitContainer, cc1,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
166 }
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
167 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
168 return createCharClassRange(cc->cond.range.begin,cc->cond.range.begin,
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
169 cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
170 } else if (end < cc->cond.range.end) { // range.begin < end
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
171 if (begin < cc->cond.range.begin) { // 3
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
172 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
173 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
174 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
175 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
176 if (begin == cc->cond.range.begin) { // 6
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
177 CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
178 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc2);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
179 }
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
180 // 9
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
181 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
182 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
183 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc2,cc3);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
184 } else if (end == cc->cond.range.end) {
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
185 if (begin == cc->cond.range.begin) { // 7
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
186 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
187 } else if (begin < cc->cond.range.begin) { // 4
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
188 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
189 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
190 }
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
191 // 10 cond.range.begin < begin
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
192 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,NULL,cc->right);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
193 return createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,cc2);
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
194 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
195 if (begin > cc->cond.range.end ) { // 13
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
196 if (cc->right) {
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 289
diff changeset
197 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer,cc->left,charClassMerge(cc->right,begin,end,nextState));
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
198 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
199 return createCharClassRange(begin,end,nextState.bitContainer,cc,NULL);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
200 }
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
201 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
202 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
203 if (end > cc->cond.range.end) { // cond.range.end < end
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
204 if (begin == cc->cond.range.begin) { // 8
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
205 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
206 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
207 cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc1);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
208 }
211
bc596e357a52 delete conditional branch in charClassMerge() (pattern 12)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 209
diff changeset
209 if (begin > cc->cond.range.begin) { // 11,12
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
210 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
211 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
212 return createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc3,cc1);
156
b5ecfc008bcf impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 155
diff changeset
213 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
214 }
156
b5ecfc008bcf impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 155
diff changeset
215 } else if (begin < cc->cond.range.begin) { // 5
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
216 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
217 CharClassPtr cc3 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
218 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
219 } else {
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
220 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
221 }
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
222 return cc;
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
223 }
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
224
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
225 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) {
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
226 while (next->left) {
171
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
227 CharClassStackPtr ccs = NEW(CharClassStack);
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
228 ccs->next = walk->stack;
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
229 ccs->turn = walk->turn;
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
230 walk->turn = LEFT;
171
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
231 ccs->cc = next;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
232 walk->stack = ccs;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
233 next = next->left;
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
234 }
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
235 walk->turn = SELF;
172
540fc12871d9 remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 171
diff changeset
236 walk->next = next;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
237 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
238
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
239 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) {
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
240 CharClassWalkerPtr walk = NEW(CharClassWalker);
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
241 walk->next = NULL;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
242 walk->stack = NULL;
241
87ad91af8a15 turn initialization in charclasswalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 239
diff changeset
243 walk->turn = LEFT;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
244 if (!next) return walk;
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
245 findLeftMost(next,walk);
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
246 return walk;
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
247 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
248
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
249 bool hasNext(CharClassWalkerPtr walk) {
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
250 return walk->next != NULL;
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
251 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
252
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
253 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) {
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
254 CharClassStackPtr prev = walk->stack->next;
209
959f8c00da17 fix charClassStackPop()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 208
diff changeset
255 walk->turn = walk->stack->turn;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
256 free(walk->stack);
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
257 walk->stack = prev;
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
258 return prev;
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
259 }
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
260
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
261 CharClassPtr getNext(CharClassWalkerPtr walk) {
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
262 CharClassPtr current = walk->next;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
263 walk->next = NULL;
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
264 if (walk->turn == SELF) {
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
265 if (current->right) {
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
266 walk->turn = RIGHT;
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
267 findLeftMost(current->right,walk);
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
268 return current;
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
269 }
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
270 }
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
271 while (walk->stack) {
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
272 walk->next = walk->stack->cc;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
273 charClassStackPop(walk);
201
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
274 if (walk->turn == LEFT) {
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
275 walk->turn = SELF;
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
276 return current;
b8bc24abaf8a add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 198
diff changeset
277 }
254
21b9ba76f91b remove warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 250
diff changeset
278 }
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
279 return current;
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
280 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
281
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
282 void setState(CharClassPtr cc, BitVector bi) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
283 // if (word case) setNext(bitVector to the word list)
189
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 188
diff changeset
284 cc->nextState = bi;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
285 if (cc->left) {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
286 setState(cc->left,bi);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
287 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
288 if (cc->right) {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
289 setState(cc->right,bi);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
290 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
291 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
292
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
293 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) {
178
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
294 if (x->cc == NULL) {
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
295 return y;
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
296 }
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
297 CharClassWalkerPtr walk = createCharClassWalker(x->cc);
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
298 CharClassPtr ccy = y;
172
540fc12871d9 remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 171
diff changeset
299 BitVector bi;
208
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
300 while (hasNext(walk)) {
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
301 CharClassPtr cc = getNext(walk);
171
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
302 unsigned long begin = cc->cond.range.begin;
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
303 unsigned long end = cc->cond.range.end;
172
540fc12871d9 remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 171
diff changeset
304 bi = cc->nextState;
171
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
305 ccy = charClassMerge(ccy,begin,end,bi);
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
306 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
307 free(walk);
178
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
308 return ccy;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
309 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
310
308
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
311 /* end */