00001 #ifndef ASTL_DFA_MIN_H
00002 #define ASTL_DFA_MIN_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <astl.h>
00013 #include <match.h>
00014 #include <iostream>
00015 #include <set>
00016 #include <vector>
00017 #include <functional>
00018 #include <string>
00019 #include <cstring>
00020 #include <bitset>
00021 #include <iterator>
00022 #include <utility>
00023
00024 using namespace std;
00025
00026 namespace astl {
00027
00028 typedef bitset<32> bitset_type;
00029
00030
00031 template <typename CharType>
00032 class transition
00033 {
00034 protected:
00035 pair<CharType, unsigned int> letter_aim;
00036
00037 public:
00038 typedef CharType char_type;
00039
00040 transition(CharType a = 0, unsigned int aim = 0)
00041 : letter_aim(a, aim)
00042 { }
00043
00044 char_type letter() const { return letter_aim.first; }
00045
00046 unsigned int aim() const { return letter_aim.second; }
00047
00048 void aim(unsigned int new_aim) { letter_aim.second = new_aim; }
00049
00050 bool operator<(const transition<char_type> &x) const {
00051 return letter_aim < x.letter_aim;
00052 }
00053
00054 const pair<char_type, unsigned int>& make_pair() const {
00055 return letter_aim;
00056 }
00057 };
00058
00059
00060
00061
00062
00063
00064 const bitset_type letter_mask(0xFF000000);
00065 const bitset_type aim_mask(0x00FFFFFF);
00066 const unsigned long LETTER_SHIFT = 24;
00067
00068 template <>
00069 class transition<char>
00070 {
00071 protected:
00072 bitset_type data;
00073
00074 public:
00075 typedef char char_type;
00076
00077 transition()
00078 : data(0UL)
00079 { }
00080
00081 transition(char a, unsigned int aim = 0)
00082 : data((bitset_type(a) << LETTER_SHIFT) | bitset_type(aim))
00083 { }
00084
00085 char letter() const {
00086 return (char) (((data & letter_mask) >> LETTER_SHIFT).to_ulong());
00087 }
00088
00089 unsigned int aim() const { return (data & aim_mask).to_ulong(); }
00090
00091 void aim(unsigned int new_aim) {
00092 data &= letter_mask;
00093 data |= bitset_type(new_aim);
00094 }
00095
00096 bool operator<(const transition<char> &x) const {
00097 return data.to_ulong() < x.data.to_ulong();
00098 }
00099
00100 pair<char, unsigned int> make_pair() const { return std::make_pair(letter(), aim()); }
00101 };
00102
00103 template <>
00104 class transition<unsigned char>
00105 {
00106 protected:
00107 bitset_type data;
00108
00109 public:
00110 typedef unsigned char char_type;
00111
00112 transition()
00113 : data(0UL)
00114 { }
00115
00116 transition(unsigned char a, unsigned int aim = 0)
00117 : data((bitset_type(a) << LETTER_SHIFT) | bitset_type(aim))
00118 { }
00119
00120 unsigned char letter() const {
00121 return (unsigned char) (((data & letter_mask) >> LETTER_SHIFT).to_ulong());
00122 }
00123
00124 unsigned int aim() const { return (data & aim_mask).to_ulong(); }
00125
00126 void aim(unsigned int new_aim) {
00127 data &= letter_mask;
00128 data |= bitset_type(new_aim);
00129 }
00130
00131 bool operator<(const transition<unsigned char> &x) const {
00132 return data.to_ulong() < x.data.to_ulong();
00133 }
00134
00135 pair<unsigned char, unsigned int> make_pair() const {
00136 return std::make_pair(letter(), aim());
00137 }
00138 };
00139
00140
00141
00142 template <typename Transition>
00143 struct lower_transition : public binary_function<Transition, Transition, bool>
00144 {
00145 bool operator()(const Transition &x, const Transition &y) const {
00146 return x.letter() < y.letter();
00147 }
00148 };
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 static const bitset_type final_mask(1);
00167 static const bitset_type degree_in_mask(0xFFFFFFFF << 1);
00168 static const bitset_type card_mask(0x000FFFFF);
00169 static const bitset_type height_mask(0xFFF00000);
00170 static const unsigned long DEGREE_IN_SHIFT = 1;
00171 static const unsigned long HEIGHT_SHIFT = 20;
00172
00173 template <typename Transition, typename Tag>
00174 class state_base
00175 {
00176 public:
00177 typedef Tag tag_type;
00178 tag_type& tag() { return data; }
00179 const tag_type& tag() const { return data; }
00180
00181 protected:
00182 tag_type data;
00183 };
00184
00185 template <typename Transition>
00186 class state_base<Transition, empty_tag>
00187 {
00188 public:
00189 typedef empty_tag tag_type;
00190 empty_tag& tag() { return data; }
00191 const empty_tag& tag() const { return data; }
00192
00193 protected:
00194 static empty_tag data;
00195 };
00196
00197 template <typename Transition>
00198 empty_tag state_base<Transition, empty_tag>::data;
00199
00200 template <typename Transition, typename Tag = empty_tag>
00201 class state : public state_base<Transition, Tag>
00202 {
00203 public:
00204 class bool_reference;
00205 friend class bool_reference;
00206
00207 protected:
00208 bitset_type degree_in_final;
00209 bitset_type height_card;
00210 union dummy_name {
00211 private:
00212
00213
00214 Transition *_t;
00215 char _tr[sizeof(Transition)];
00216 public:
00217 Transition*& t() { return _t; }
00218 Transition& tr() { return *((Transition*) _tr); }
00219 Transition* const & t() const { return _t; }
00220 const Transition& tr() const { return *((Transition*) _tr); }
00221 } tunion;
00222
00223 public:
00224 typedef Transition* iterator;
00225 typedef const Transition* const_iterator;
00226
00227 state()
00228 : degree_in_final(0UL), height_card(0UL) {
00229 tunion.t() = NULL;
00230 }
00231
00232 state(const state &x)
00233 : degree_in_final(x.degree_in_final), height_card(x.height_card)
00234 {
00235 state_base<Transition, Tag>::tag() = x.tag();
00236 degree_in_final &= final_mask;
00237 unsigned int n = x.card();
00238 switch (n) {
00239 case 0 : tunion.t() = NULL; break;
00240 case 1 : tunion.tr() = x.tunion.tr(); break;
00241 default :
00242 tunion.t() = new Transition[n];
00243 memcpy(tunion.t(), x.tunion.t(), sizeof(Transition) * n);
00244
00245 }
00246 }
00247
00248 ~state() {
00249 if (card() > 1) delete [] tunion.t();
00250 }
00251
00252 unsigned int delta1(typename Transition::char_type a) const {
00253 const_iterator where = lower_bound(begin(), end(), Transition(a),
00254 lower_transition<Transition>());
00255 return (where == end() || (*where).letter() != a) ? 0 : (*where).aim();
00256 }
00257
00258 const_iterator begin() const {
00259 return card() == 1 ? &(tunion.tr()) : tunion.t();
00260 }
00261
00262 const_iterator end() const {
00263 return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
00264 }
00265
00266 iterator begin() {
00267 return card() == 1 ? &(tunion.tr()) : tunion.t();
00268 }
00269
00270 iterator end() {
00271 return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
00272 }
00273
00274 unsigned int size() const {
00275 return card();
00276 }
00277
00278 const_iterator find(typename Transition::char_type a) const {
00279 const_iterator where = lower_bound(begin(), end(), Transition(a),
00280 lower_transition<Transition>());
00281 return (where == end() || (*where).letter() != a) ? end() : where;
00282 }
00283
00284 iterator find(typename Transition::char_type a) {
00285 iterator where = lower_bound(begin(), end(), Transition(a),
00286 lower_transition<Transition>());
00287 return (where == end() || (*where).letter() != a) ? end() : where;
00288 }
00289
00290 void insert(const Transition &x) {
00291 unsigned int n = card();
00292 if (n == 0)
00293 tunion.tr() = x;
00294 else {
00295 iterator where = lower_bound(begin(), end(), x, lower_transition<Transition>());
00296 unsigned int i = where - begin();
00297 Transition *tmp = new Transition[n + 1];
00298 memcpy(tmp, begin(), i * sizeof(Transition));
00299 tmp[i] = x;
00300 memcpy(tmp + i + 1, where, (end() - where) * sizeof(Transition));
00301 if (n > 1) delete [] tunion.t();
00302 tunion.t() = tmp;
00303 }
00304 inc_card();
00305 }
00306
00307 void change_trans(const Transition &x) {
00308 (*(lower_bound(begin(), end(), x, lower_transition<Transition>()))) = x;
00309 }
00310
00311 void erase(const Transition &x) {
00312 unsigned int n = card();
00313 switch (n) {
00314 case 1 : tunion.t() = NULL; break;
00315 case 2 :
00316 {
00317 Transition *tmp = tunion.t();
00318 tunion.tr() = x.letter() < tmp[1].letter() ? tmp[1] : tmp[0];
00319 delete [] tmp;
00320 break;
00321 }
00322 default :
00323 {
00324 iterator where = lower_bound(begin(), end(), x,
00325 lower_transition<Transition>());
00326 Transition *tmp = new Transition[n - 1];
00327 memcpy(tmp, begin(), (where - begin()) * sizeof(Transition));
00328 memcpy(tmp + (where - begin()), where + 1,
00329 (end() - (where + 1)) * sizeof(Transition));
00330 delete [] tunion.t();
00331 tunion.t() = tmp;
00332 }
00333 }
00334 dec_card();
00335 }
00336
00337 unsigned int degree_in() const {
00338 return ((degree_in_final & degree_in_mask) >> DEGREE_IN_SHIFT).to_ulong();
00339 }
00340
00341 void inc_degree_in() {
00342 unsigned int d = degree_in() + 1;
00343 degree_in_final &= final_mask;
00344 degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
00345 }
00346
00347 void dec_degree_in() {
00348 unsigned int d = degree_in() - 1;
00349 degree_in_final &= final_mask;
00350 degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
00351 }
00352
00353 unsigned int card() const {
00354 return (height_card & card_mask).to_ulong();
00355 }
00356
00357 void inc_card() {
00358 unsigned int c = card() + 1;
00359 height_card &= height_mask;
00360 height_card |= bitset_type(c);
00361 }
00362
00363 void dec_card() {
00364 unsigned int c = card() - 1;
00365 height_card &= height_mask;
00366 height_card |= bitset_type(c);
00367 }
00368
00369 unsigned int height() const {
00370 return ((height_card & height_mask) >> HEIGHT_SHIFT).to_ulong();
00371 }
00372
00373 void height(unsigned int h) {
00374 height_card &= card_mask;
00375 height_card |= bitset_type(h) << HEIGHT_SHIFT;
00376 }
00377
00378 bool final() const {
00379 return (degree_in_final & final_mask).to_ulong() == 1;
00380 }
00381
00382 class bool_reference
00383 {
00384 bitset_type &r;
00385 public:
00386 bool_reference(bitset_type &ref)
00387 : r(ref)
00388 { }
00389
00390 operator bool() const {
00391 return (r & final_mask).to_ulong() == 1;
00392 }
00393
00394 bool_reference& operator=(const bool_reference &x) {
00395 if (x == true) r |= final_mask;
00396 else r &= degree_in_mask;
00397 return *this;
00398 }
00399
00400 bool_reference& operator=(bool b) {
00401 if (b == true) r |= final_mask;
00402 else r &= degree_in_mask;
00403 return *this;
00404 }
00405
00406 bool operator==(const bool_reference &x) const {
00407 return (r & final_mask) == (x.r & final_mask);
00408 }
00409
00410 bool operator==(bool b) const {
00411 return ((r & final_mask).to_ulong() != 0) == b;
00412 }
00413 };
00414
00415 bool_reference final() {
00416 return bool_reference(degree_in_final);
00417 }
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438 };
00439
00440
00441
00442
00443 template <typename Transition, typename Tag>
00444 inline
00445 bool operator<(const state<Transition, Tag> &x, const state<Transition, Tag> &y) {
00446 if (x.final() < y.final()) return true;
00447 if (x.final() == y.final()) {
00448 if (x.size() < y.size()) return true;
00449 else
00450 if (x.size() == y.size()) {
00451 typename state<Transition, Tag>::const_iterator i = x.begin(), j = x.end(), k = y.begin();
00452 while (i != j)
00453 if (*i < *k) return true;
00454 else if (*k < *i) return false;
00455 else { ++i; ++k; }
00456 return false;
00457 }
00458 }
00459 return false;
00460 }
00461
00462
00463
00464 template <typename Transition, typename Tag>
00465 struct compare_state
00466 : public binary_function<typename vector<state<Transition, Tag>*>::size_type,
00467 typename vector<state<Transition, Tag>*>::size_type, bool>
00468 {
00469 const vector<state<Transition, Tag>*> &Q;
00470 compare_state(const vector<state<Transition, Tag>*> &r)
00471 : Q(r)
00472 { }
00473 bool operator() (typename vector<state<Transition, Tag>*>::size_type x,
00474 typename vector<state<Transition, Tag>*>::size_type y) const {
00475 return *Q[x] < *Q[y];
00476 }
00477 };
00478
00479
00480
00496 template <typename CharTraits = plain, typename Tag = empty_tag>
00497 class DFA_min : public DFA_concept
00498 {
00499 public:
00500 typedef transition<typename CharTraits::char_type> transition_type;
00501 typedef CharTraits char_traits;
00502 typedef Tag tag_type;
00503 typedef unsigned int state_type;
00504 typedef typename CharTraits::char_type char_type;
00505 typedef DFA_min self;
00506
00507
00508 #ifndef _MSC_VER
00509 static const state_type null_state = 0;
00510 #else
00511 static const state_type null_state;
00512 #endif
00513
00514 protected:
00515 state_type i;
00516 bool ready;
00517 unsigned int _state_count, _trans_count;
00518
00519 typedef set<state_type, compare_state<transition_type, tag_type> > container;
00520 vector<container*> _pool;
00521 vector<state<transition_type, tag_type>*> Q;
00522 compare_state<transition_type, tag_type> cmp_state;
00523 state_type hole;
00524 unsigned int wc_;
00525
00526
00527 unsigned long state_creation, state_copy, state_merge;
00528
00529 container& pool(unsigned int h) {
00530 for(; _pool.size() < h + 1; _pool.push_back(new container(cmp_state)));
00531 return *(_pool[h]);
00532 }
00533
00534 void prepare();
00535
00536 typename state<transition_type, tag_type>::bool_reference final(state_type q) {
00537 return Q[q]->final();
00538 }
00539
00540 void initial(state_type q) {
00541 i = q;
00542 }
00543
00544 state_type new_state() { return new_state_(); }
00545
00546
00547 state_type new_state(const state<transition_type, tag_type> &q) { return new_state_(&q); }
00548
00549 state_type new_state_(const state<transition_type, tag_type> *s = NULL) {
00550 if (s == NULL) ++state_creation;
00551 else ++state_copy;
00552
00553 ++_state_count;
00554 while (hole < Q.size())
00555 if (Q[hole] == NULL) {
00556 Q[hole] = s == NULL ? new state<transition_type, tag_type> : new state<transition_type, tag_type>(*s);
00557 return hole++;
00558 }
00559 else ++hole;
00560 Q.push_back(s == NULL ? new state<transition_type, tag_type> : new state<transition_type, tag_type>(*s));
00561 ++hole;
00562 return Q.size() - 1;
00563 }
00564
00565 public:
00566 tag_type& tag(state_type q) { return Q[q]->tag(); }
00567
00568 const tag_type& tag(state_type q) const { return Q[q]->tag(); }
00569
00570 protected:
00571 void reset() {
00572 freeze();
00573 typename vector<state<transition_type, tag_type>*>::iterator ii =
00574 Q.begin(), j = Q.end();
00575 for(; ii != j; ++ii)
00576 delete *ii;
00577
00578 i = 0;
00579 _state_count = 0;
00580 _trans_count = 0;
00581 Q.resize(1);
00582 hole = 2;
00583 wc_ = 0;
00584 }
00585
00586 void del_state(state_type q) {
00587 ++state_merge;
00588
00589 --_state_count;
00590 _trans_count -= Q[q]->size();
00591 typename state<transition_type, tag_type>::iterator i = Q[q]->begin(),
00592 j = Q[q]->end();
00593 for(; i != j; ++i)
00594 Q[(*i).aim()]->dec_degree_in();
00595 delete Q[q];
00596 Q[q] = NULL;
00597 hole = min__(hole, q);
00598 }
00599
00600 void set_trans(state_type q, char_type a, state_type p) {
00601 ++_trans_count;
00602 Q[q]->insert(transition_type(a, p));
00603 Q[p]->inc_degree_in();
00604 }
00605
00606 state_type duplicate_state(state_type q) {
00607 _trans_count += Q[q]->size();
00608 state_type p = new_state(*Q[q]);
00609 typename state<transition_type, tag_type>::iterator i = Q[p]->begin(), j = Q[p]->end();
00610 for(; i != j; ++i)
00611 Q[(*i).aim()]->inc_degree_in();
00612 return p;
00613 }
00614
00615 void del_trans(state_type q, char_type a) {
00616 --_trans_count;
00617 Q[Q[q]->delta1(a)]->dec_degree_in();
00618 Q[q]->erase(transition_type(a));
00619 }
00620
00621 void change_trans(state_type q, char_type a, state_type p) {
00622 Q[Q[q]->delta1(a)]->dec_degree_in();
00623 Q[q]->change_trans(transition_type(a,p));
00624 Q[p]->inc_degree_in();
00625 }
00626
00627 public:
00628 void height(state_type q, unsigned int h) {
00629 Q[q]->height(h);
00630 }
00631
00632 unsigned int height(state_type q) const {
00633 return Q[q]->height();
00634 }
00635
00636 unsigned int degree_in(state_type q) const {
00637 return Q[q]->degree_in();
00638 }
00639
00640 void degree_in(state_type q, unsigned int d) {
00641 Q[q]->degree_in(d);
00642 }
00643
00647 unsigned int wc() const { return wc_; }
00648
00649 public:
00650 typedef skip_blanks_iterator<state<transition_type, tag_type> > const_iterator;
00651
00652 DFA_min()
00653 : i(0), ready(false),
00654 _state_count(0), _trans_count(0), Q(1, (state<transition_type, tag_type>*) 0),
00655 cmp_state(Q), hole(2), wc_(0),
00656 state_creation(0), state_copy(0), state_merge(0)
00657 {
00658 i = new_state();
00659 }
00660
00661 ostream& stats(ostream &out) const {
00662 out << "word count " << wc() << endl << "states " << state_count();
00663 out << endl << "transitions " << trans_count() << endl;
00664 out << "state creations " << state_creation << endl;
00665 out << "state copies " << state_copy << endl;
00666 return out << "state merges " << state_merge << endl;
00667 }
00668
00669 const_iterator begin() const {
00670 return const_iterator(&Q, initial());
00671 }
00672
00673 const_iterator end() const {
00674 return const_iterator(&Q, Q.size());
00675 }
00676
00677 ~DFA_min() { reset(); }
00678
00682 void clear() {
00683 reset();
00684 i = new_state();
00685 }
00686
00687 bool final(state_type q) const {
00688 return Q[q]->final();
00689 }
00690
00696 void freeze() {
00697 for(typename vector<container*>::iterator i = _pool.begin();
00698 i != _pool.end(); ++i)
00699 delete *i;
00700 _pool.clear();
00701 ready = false;
00702 }
00703
00711 template <class ForwardI>
00712 bool insert(ForwardI, ForwardI);
00713
00720 bool insert(const basic_string<char_type> &s) {
00721 return insert(s.begin(), s.end());
00722 }
00723
00724 state_type initial() const { return i; }
00725
00726 state_type delta1(state_type q, char_type a) const {
00727 return Q[q]->delta1(a);
00728 }
00729
00730 class edges_type
00731 {
00732 protected:
00733 state<transition_type, tag_type> *q;
00734
00735 public:
00736 typedef int difference_type;
00737 typedef char_type key_type;
00738 typedef state_type data_type;
00739 typedef pair<const char_type, state_type> value_type;
00740
00741 edges_type(state<transition_type, tag_type> *p)
00742 : q(p)
00743 { }
00744
00745 edges_type()
00746 {}
00747
00748 bool empty() const {
00749 return q->size() == 0;
00750 }
00751
00752 unsigned int size() const {
00753 return q->size();
00754 }
00755
00756 class const_iterator
00757 : public iterator<bidirectional_iterator_tag,
00758 pair<char_type, state_type> >
00759 {
00760 protected:
00761 typename state<transition_type, tag_type>::const_iterator i;
00762
00763 public:
00764 typedef const_iterator self;
00765
00766 const_iterator()
00767 { }
00768 const_iterator(typename state<transition_type, tag_type>::const_iterator j)
00769 : i(j)
00770 { }
00771 pair<char_type, unsigned int> operator* () const {
00772 return i->make_pair();
00773 }
00774 self& operator++ () {
00775 ++i;
00776 return *this;
00777 }
00778 self operator++ (int) {
00779 self tmp = *this;
00780 ++*this;
00781 return tmp;
00782 }
00783 bool operator== (const self &x) const {
00784 return i == x.i;
00785 }
00786 self& operator--() {
00787 --i;
00788 return *this;
00789 }
00790 self operator-- (int) {
00791 self tmp = *this;
00792 --*this;
00793 return tmp;
00794 }
00795 };
00796
00797 const_iterator begin() const {
00798 return const_iterator(q->begin());
00799 }
00800
00801 const_iterator end() const {
00802 return const_iterator(q->end());
00803 }
00804
00805 const_iterator find(char_type a) const {
00806 return const_iterator(q->find(a));
00807 }
00808 };
00809
00810 edges_type delta2(state_type q) const { return edges_type(Q[q]); }
00811
00812 unsigned int state_count() const { return _state_count; }
00813 unsigned int trans_count() const { return _trans_count; }
00814
00817 unsigned int size() const { return wc_; }
00818 };
00819
00820 #ifndef _MSC_VER
00821 template <typename C, typename T>
00822 const typename DFA_min<C, T>::state_type DFA_min<C, T>::null_state;
00823 #else
00824 template <typename C, typename T>
00825 const typename DFA_min<C, T>::state_type DFA_min<C, T>::null_state = 0;
00826 #endif
00827
00828 template <typename CharTraits, typename Tag>
00829 void DFA_min<CharTraits, Tag>::prepare() {
00830 const_iterator first = begin(), last = end();
00831 for(; first != last; ++first)
00832 pool(height(*first)).insert(*first);
00833 ready = true;
00834 }
00835
00836 template <class CharTraits, typename Tag>
00837 template <class InputIterator>
00838 bool DFA_min<CharTraits, Tag>::insert(InputIterator first,
00839 InputIterator last)
00840 {
00841 {
00842 cursor<DFA_min<CharTraits, Tag> > c(*this);
00843 if (match(c, first, last)) return false;
00844 }
00845 if (!ready) prepare();
00846 stack_cursor<forward_cursor<self> > c(forwardc(*this));
00847 bool duplicating;
00848
00849 for(duplicating = false; first != last; ++first) {
00850 if (!duplicating)
00851 pool(height(c.src())).erase(c.src());
00852
00853 if (!c.find(*first)) {
00854 set_trans(c.src(), *first, new_state());
00855 duplicating = true;
00856 c.find(*first);
00857 }
00858 else
00859 if (Q[c.aim()]->degree_in() > 1) {
00860 change_trans(c.src(), *first, duplicate_state(c.aim()));
00861 duplicating = true;
00862 c.find(*first);
00863 }
00864 c.forward();
00865 }
00866
00867 if (!duplicating)
00868 pool(height(c.src())).erase(c.src());
00869
00870 final(c.src()) = true;
00871 unsigned int h = height(c.src());
00872
00873 for(; c.backward(); ) {
00874
00875
00876
00877 pair<typename container::iterator, bool> i =
00878 pool(height(c.aim())).insert(c.aim());
00879 if (i.second == false) {
00880 state_type tmp = c.aim();
00881
00882 change_trans(c.src(), c.letter(), *i.first);
00883 del_state(tmp);
00884 }
00885 h = max__(height(c.src()), h+1);
00886 height(c.src(), h);
00887 }
00888 pool(height(initial())).insert(initial());
00889 ++wc_;
00890 return true;
00891 }
00892
00893 }
00894
00895 #endif // ASTL_CLASS_DFA_MIN
00896
00897