Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 199:98ff9d94566a pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix CharClassWalker
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 26 Dec 2015 18:09:27 +0900
parents 4fefd80c05f2
children
comparison
equal deleted inserted replaced
197:63a98405aafa 199:98ff9d94566a
115 115
116 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) { 116 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) {
117 while (next->left) { 117 while (next->left) {
118 CharClassStackPtr ccs = NEW(CharClassStack); 118 CharClassStackPtr ccs = NEW(CharClassStack);
119 ccs->next = walk->stack; 119 ccs->next = walk->stack;
120 ccs->turn = LEFT; 120 ccs->turn = walk->turn;
121 walk->turn = LEFT;
121 ccs->cc = next; 122 ccs->cc = next;
122 walk->stack = ccs; 123 walk->stack = ccs;
123 next = next->left; 124 next = next->left;
124 } 125 }
126 walk->turn = SELF;
125 walk->next = next; 127 walk->next = next;
126 } 128 }
127 129
128 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) { 130 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) {
129 CharClassWalkerPtr walk = NEW(CharClassWalker); 131 CharClassWalkerPtr walk = NEW(CharClassWalker);
130 walk->next = NULL; 132 walk->next = NULL;
131 walk->stack = NULL; 133 walk->stack = NULL;
132 if (!next) return walk; 134 if (!next) return walk;
133 if (!next->left) {
134 walk->next = next;
135 return walk;
136 }
137 findLeftMost(next,walk); 135 findLeftMost(next,walk);
138 return walk; 136 return walk;
139 } 137 }
140 138
141 bool hasNext(CharClassWalkerPtr walk) { 139 bool hasNext(CharClassWalkerPtr walk) {
142 return walk->next != NULL; 140 return walk->next != NULL;
143 } 141 }
144 142
145 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) { 143 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) {
146 if (!walk->stack) {
147 return NULL;
148 }
149 CharClassStackPtr prev = walk->stack->next; 144 CharClassStackPtr prev = walk->stack->next;
150 free(walk->stack); 145 free(walk->stack);
151 walk->stack = prev; 146 walk->stack = prev;
147 walk->turn = prev->turn;
152 return prev; 148 return prev;
153 } 149 }
154 150
155 CharClassPtr getNext(CharClassWalkerPtr walk) { 151 CharClassPtr getNext(CharClassWalkerPtr walk) {
156 CharClassPtr current = walk->next; 152 CharClassPtr current = walk->next;
157 walk->next = NULL; 153 walk->next = NULL;
158 while (walk->stack) { 154 if (walk->turn == SELF) {
159 while (walk->stack->turn == RIGHT) {
160 if (charClassStackPop(walk) == NULL) {
161 return current;
162 }
163 }
164 if (walk->stack->turn == LEFT) {
165 walk->next = walk->stack->cc;
166 walk->stack->turn = SELF;
167 return current;
168 }
169 if (current->right) { 155 if (current->right) {
170 walk->stack->turn = RIGHT; 156 walk->turn = RIGHT;
171 findLeftMost(current->right,walk); 157 findLeftMost(current->right,walk);
172 return current; 158 return current;
173 } 159 }
160 }
161 while (walk->stack) {
162 walk->next = walk->stack->cc;
174 charClassStackPop(walk); 163 charClassStackPop(walk);
175 } 164 if (walk->turn == LEFT) {
165 walk->turn = SELF;
166 return current;
167 }
168 }
169 walk->next = NULL;
176 return current; 170 return current;
177 } 171 }
178 172
179 void setState(CharClassPtr cc, BitVector bi) { 173 void setState(CharClassPtr cc, BitVector bi) {
180 cc->nextState = bi; 174 cc->nextState = bi;