Mercurial > hg > Applications > Grep

comparison c/regexParser/subsetConstraction.cc @ 155:6cd0141bed6c pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
impl charClassMerge
author masa
date Fri, 18 Dec 2015 15:40:55 +0900
parents 1fad21fd6028
children b5ecfc008bcf
comparison
equal deleted inserted replaced
154:1fad21fd6028 155:6cd0141bed6c
11 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { 11 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
12 // 重なっているccの領域を分割する 12 // 重なっているccの領域を分割する
13 // 必要ならばnextStateを重ねあわせる 13 // 必要ならばnextStateを重ねあわせる
14 // 変更があった場合は新しくリストを作って返す 14 // 変更があった場合は新しくリストを作って返す
15 if (end < cc->cond.range.begin ) { // 1 15 if (end < cc->cond.range.begin ) { // 1
16 CharClassPtr cc1 = charClassMerge(cc,cc->cond.range.begin,cc->cond.range.end,nextState);
17 if (cc->left) { 16 if (cc->left) {
18 cc1->left = charClassMerge(cc->left,begin,end,nextState); 17 return createCharClassRange(cc->begin,cc->end,charClassMerge(cc->left,begin,end,nextState),cc->right);
19 return cc1; 18 } else {
20 } else { 19 CharClassPtr cc1 = createCharClassRange(begin,end,NULL,cc);
21 CharClassPtr cc2 = charClassMerge(cc,begin,end,nextState); 20 cc1->nextState = nextState;
22 cc2->nextState = nextState;
23 cc1->left = cc2;
24 return cc1; 21 return cc1;
25 } 22 }
26 } else if (end == cc->cond.range.begin ) { // 2 23 } else if (end == cc->cond.range.begin ) { // 2
27 cc->cond.range.begin = begin; 24 CharClassPtr cc1;
28 return cc; 25 if (cc->left) {
29 } else if (end <= cc->cond.range.end) { // 3,4,6,7,9,10 26 cc1 = charClassMerge(cc->left,begin,end-1,nextState);
30 if (begin < cc->cond.range.begin) { // 3,4 27 } else {
31 cc->cond.range.begin = begin; 28 cc1 = createCharClassRange(begin,end-1,NULL,NULL);
32 } 29 cc1->nextState = nextState;
33 return cc; 30 }
34 } else if (begin > cc->cond.range.end ) { // 13 31 if (cc->begin == cc->end) {
32 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc1,cc->right);
33 cc2->nextState = cc->nextState | nextState;
34 return cc2;
35 }
36 CharClassPtr cc3;
37 createCharClassRange(cc->begin+1,cc->end,cc->left,cc->end);
38 cc3->nextState = cc->nextState;
39 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->begin,cc1,cc3);
40 cc2->nextState = cc->nextState | nextState;
41 return cc2;
42 } else if (end < cc->cond.range.end) {
43 if (begin < cc->cond.range.begin) { // 3
44 CharClassPtr cc1;
45 if (cc->left) {
46 cc1 = charClassMerge(cc->left,begin,cc->begin-1,nextState);
47 } else {
48 cc1 = createCharClassRange(begin,cc->begin-1,NULL,NULL);
49 cc1->nextState = nextState;
50 }
51 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc->left,cc->right);
52 cc3->nextState = cc->nextState;
53 CharClassPtr cc2 = createCharClassRange(cc->begin,end,cc1,cc3);
54 cc2->nextState = cc->nextState | nextState;
55 return cc2;
56 }
57 if (begin == cc->cond.range.begin) { // 6
58 CharClassPtr cc2 = createCharClassRange(end,cc->end,NULL,cc->right);
59 cc2->nextState = cc->nextState;
60 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2);
61 cc1->nextState = cc->nextState | nextState;
62 return cc1;
63 }
64 // 9
65 CharClassPtr cc2 = createCharClassRange(cc->begin,begin-1,cc->left,NULL);
66 cc2->nextState = cc1->nextState;
67 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,NULL,cc->right);
68 cc3->nextState = cc->nextState;
69 CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3);
70 cc1->nextState = cc->nextState | nextState;
71 return cc1;
72 } else if (end == cc->cond.range.end) {
73 if (begin == cc->cond.range.begin) { // 7
74 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right);
75 cc1->nextState = cc->nextState | nextState;
76 return cc1;
77 } else if (begin < cc->cond.range.begin) { // 4
78 CharClassPtr cc1;
79 if (cc->left) {
80 cc1 = charClassMerge(cc->left,begin,end-1,nextState);
81 } else {
82 cc1 = createCharClassRange(begin,end-1,NULL,NULL);
83 cc1->nextState = nextState;
84 }
85 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right);
86 cc3->nextState = cc->nextState | nextState;
87 return cc3;
88 }
89 // 10
90 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right);
91 cc2->nextState = cc->nextState | nextState;
92 CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,NULL,NULL);
93 cc1->nextState = cc->nextState;
94 return cc1;
95
96 }
97 if (begin > cc->cond.range.end ) { // 13
35 if (cc->right) { 98 if (cc->right) {
36 cc->right = charClassMerge(cc->right,begin,end,nextState); 99 return createCharClassRange(cc->begin,cc->end,cc->left,charClassMerge(cc->right,begin,end,nextState));
37 } else { 100 } else {
38 cc->right = charClassMerge(cc,begin,end,nextState); 101 CharClassPtr cc1 = createCharClassRange(begin,end,cc,NULL);
39 } 102 cc1->nextState = nextState;
40 return cc; 103 return cc1;
41 } 104 }
42 if (cc->right) { 105 }
43 CharClassPtr right = cc->right; 106 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
44 begin = cc->cond.range.begin; 107 if (end > cc->cond.range.end) {
45 free(cc); 108 if (begin == cc->cond.range.begin) { // 8
46 return charClassMerge(right,begin,end,nextState); 109 CharClassPtr cc1;
47 } 110 if (cc->left) {
48 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12 111 cc1 = charClassMerge(cc->left,begin,end-1,nextState);
49 if (end > cc->cond.range.end) cc->cond.range.end = end; // 11,8 112 } else {
113 cc1 = createCharClassRange(begin,end-1,NULL,NULL);
114 cc1->nextState = nextState;
115 }
116 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right);
117 cc3->nextState = cc->nextState | nextState;
118 return cc3;
119 }
120 // 11
121 cc->cond.range.end = end; // 11,8
122 return cc;
123 }
124 // 12
125 CharClassPtr cc1;
126 if (cc->right) {
127 cc1 = charClassMerge(cc->right,begin+1,end,nextState);
128 } else {
129 cc1 = createCharClassRange(begin+1,end,NULL,NULL);
130 cc1->nextState = nextState;
131 }
132 if (cc->begin == cc->end) {
133 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc->left,cc1);
134 cc2->nextState = cc->nextState | nextState;
135 return cc2;
136 }
137 CharClassPtr cc3 = createCharClassRange(cc->begin,cc->end-1,NULL,cc->right);
138 cc3->nextState = cc->nextState;
139 CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3);
140 cc2->nextState = cc->nextState | nextState;
141 return cc2;
50 } else if (begin < cc->cond.range.begin) { // 5 142 } else if (begin < cc->cond.range.begin) { // 5
51 cc->cond.range.begin = begin; 143 cc->cond.range.begin = begin;
52 cc->cond.range.end = end; 144 cc->cond.range.end = end;
53 } else { 145 } else {
54 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); 146 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);