00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef ASTL_SET_OPERATION_H
00023 #define ASTL_SET_OPERATION_H
00024
00025 #include <astl.h>
00026
00027
00028
00029
00030 #include <list>
00031 #include <vector>
00032 #include <utility>
00033 #include <string>
00034 #include <functional>
00035 #include <iostream>
00036 #include <algorithm>
00037 #include <map>
00038
00039 using namespace std;
00040
00041 namespace astl {
00042
00043 template <class Alphabet1, class Alphabet2>
00044 struct default_lower_than : public binary_function<Alphabet1, Alphabet2, bool>
00045 {
00046 bool operator() (const Alphabet1 &x, const Alphabet2 &y) const {
00047 return x < y;
00048 }
00049 };
00050
00051 template <class ForwardCursor1, class ForwardCursor2,
00052 class LowerThan = default_lower_than<typename ForwardCursor1::char_type,
00053 typename ForwardCursor2::char_type> >
00054 class union_cursor : public forward_cursor_concept
00055 {
00056 protected:
00057 ForwardCursor1 x1;
00058 ForwardCursor2 x2;
00059 bool x1_at_end, x2_at_end;
00060
00061 public:
00062 typedef union_cursor self;
00063
00064 typedef pair<typename ForwardCursor1::state_type,
00065 typename ForwardCursor2::state_type> state_type;
00066 typedef pair<typename ForwardCursor1::tag_type,
00067 typename ForwardCursor2::tag_type> tag_type;
00068 typedef typename ForwardCursor1::char_type char_type;
00069 typedef typename ForwardCursor1::char_traits char_traits;
00070
00071 union_cursor(const ForwardCursor1 &x1, const ForwardCursor2 &x2)
00072 : x1(x1), x2(x2)
00073 { }
00074
00075 bool operator==(const self &x) const { return x1 == x.x1 && x2 == x.x2; }
00076
00077 void forward() {
00078 if (x1_at_end) {
00079 x1 = x1.sink_state();
00080 x2.forward();
00081 return;
00082 }
00083 if (x2_at_end) {
00084 x2 = x2.sink_state();
00085 x1.forward();
00086 return;
00087 }
00088
00089 if (LowerThan()(x1.letter(), x2.letter())) {
00090 x2 = x2.sink_state();
00091 x1.forward();
00092 return;
00093 }
00094 if (LowerThan()(x2.letter(),x1.letter())) {
00095 x1 = x1.sink_state();
00096 x2.forward();
00097 return;
00098 }
00099
00100 x1.forward();
00101 x2.forward();
00102 }
00103
00104 bool first() {
00105 x1_at_end = x1.sink() || !x1.first();
00106 x2_at_end = x2.sink() || !x2.first();
00107 return !(x1_at_end && x2_at_end);
00108 }
00109
00110 bool next() {
00111 if (x1_at_end) {
00112 x2_at_end = !x2.next();
00113 return !x2_at_end;
00114 }
00115 if (x2_at_end) {
00116 x1_at_end = !x1.next();
00117 return !x1_at_end;
00118 }
00119
00120 if (LowerThan()(x1.letter(), x2.letter())) {
00121 x1_at_end = !x1.next();
00122 return true;
00123 }
00124 if (LowerThan()(x2.letter(), x1.letter())) {
00125 x2_at_end = !x2.next();
00126 return true;
00127 }
00128
00129 x1_at_end = !x1.next();
00130 x2_at_end = !x2.next();
00131 return !(x1_at_end && x2_at_end);
00132 }
00133
00134 char_type letter() const {
00135 return x1_at_end ? x2.letter() : x2_at_end ? x1.letter()
00136 : min__(x1.letter(), x2.letter(), LowerThan());
00137 }
00138
00139 bool find(const char_type &a) {
00140 x1_at_end = x1.sink() || !x1.find(a);
00141 x2_at_end = x2.sink() || !x2.find(a);
00142 return !(x1_at_end && x2_at_end);
00143 }
00144
00145 bool forward(const char_type &a) {
00146 if (!x1.sink()) x1.forward(a);
00147 if (!x2.sink()) x2.forward(a);
00148 return !sink();
00149 }
00150
00151 state_type src() const { return state_type(x1.src(), x2.src()); }
00152
00153 state_type aim() const {
00154 if (x1_at_end)
00155 return state_type(x1.sink_state(), x2.aim());
00156 if (x2_at_end)
00157 return state_type(x1.aim(), x2.sink_state());
00158 if (LowerThan()(x2.letter(), x1.letter()))
00159 return state_type(x1.sink_state(), x2.aim());
00160 if (LowerThan()(x1.letter(), x2.letter()))
00161 return state_type(x1.aim(), x2.sink_state());
00162 return state_type(x1.aim(), x2.aim());
00163 }
00164
00165 bool src_final() const {
00166 return (!x1.sink() && x1.src_final()) || (!x2.sink() && x2.src_final());
00167 }
00168
00169 bool aim_final() const {
00170 if (x1_at_end) return x2.aim_final();
00171 if (x2_at_end) return x1.aim_final();
00172 if (LowerThan()(x1.letter(), x2.letter()))
00173 return x1.aim_final();
00174 if (LowerThan()(x2.letter(), x1.letter()))
00175 return x2.aim_final();
00176 return x1.aim_final() || x2.aim_final();
00177 }
00178
00179 bool sink() const { return x1.sink() && x2.sink(); }
00180
00181 void to_sink() {
00182 x1.to_sink();
00183 x2.to_sink();
00184 }
00185
00186 bool exists(const char_type &a) const {
00187 if (x1.sink()) return x2.exists(a);
00188 return x1.exists(a) || (!x2.sink() && x2.exists(a));
00189 }
00190
00191 tag_type aim_tag() const {
00192 if (x1_at_end) return tag_type(x2.aim_tag(), x2.aim_tag());
00193 if (x2_at_end) return tag_type(x1.aim_tag(), x1.aim_tag());
00194 return tag_type(x1.sink() ? x2.aim_tag() : x1.aim_tag(),
00195 x2.sink() ? x1.aim_tag() : x2.aim_tag());
00196 }
00197
00198 tag_type src_tag() const {
00199 return tag_type(x1.sink() ? x2.src_tag() : x1.src_tag(),
00200 x2.sink() ? x1.src_tag() : x2.src_tag());
00201 }
00202
00203 self& operator= (const state_type &x) {
00204 x1 = x.first;
00205 x2 = x.second;
00206 x1_at_end = x2_at_end = true;
00207 return *this;
00208 }
00209
00210
00211 ForwardCursor1& first_() { return x1; }
00212 ForwardCursor2& second_() { return x2; }
00213 const ForwardCursor1& first_() const { return x1; }
00214 const ForwardCursor2& second_() const { return x2; }
00215 void reset() {
00216 x1_at_end = x1.sink();
00217 x2_at_end = x2.sink();
00218 }
00219
00220 };
00221
00222 template <class ForwardC1, class ForwardC2,
00223 class LowerThan = default_lower_than<typename ForwardC1::char_type,
00224 typename ForwardC2::char_type> >
00225 class intersection_cursor : public forward_cursor_concept
00226 {
00227 public:
00228 typedef intersection_cursor self;
00229 typedef pair<typename ForwardC1::state_type,
00230 typename ForwardC2::state_type> state_type;
00231 typedef pair<typename ForwardC1::tag_type,
00232 typename ForwardC2::tag_type> tag_type;
00233 typedef typename ForwardC1::char_type char_type;
00234 typedef typename ForwardC1::char_traits char_traits;
00235
00236 intersection_cursor(const ForwardC1 &x, const ForwardC2 &y)
00237 : x1(x), x2(y)
00238 { }
00239
00240 bool sink() const { return x1.sink() || x2.sink(); }
00241
00242 state_type sink_state() const {
00243 return state_type(x1.sink_state(), x2.sink_state());
00244 }
00245
00246 state_type src() const { return state_type(x1.src(), x2.src()); }
00247
00248 state_type aim() const { return state_type(x1.aim(), x2.aim()); }
00249
00250 self& operator=(const state_type &p) {
00251 x1 = p.first;
00252 x2 = p.second;
00253 return *this;
00254 }
00255
00256 void forward() {
00257 x1.forward();
00258 x2.forward();
00259 }
00260
00261 bool first() {
00262 if (x1.first() && x2.first())
00263 while(1)
00264 if (LowerThan()(x1.letter(), x2.letter())) {
00265 if (!x1.next()) return false;
00266 }
00267 else
00268 if (LowerThan()(x2.letter(), x1.letter())) {
00269 if (!x2.next()) return false;
00270 }
00271 else
00272 return true;
00273 return false;
00274 }
00275
00276 bool next() {
00277 if (x1.next() && x2.next())
00278 while(1)
00279 if (LowerThan()(x1.letter(), x2.letter())) {
00280 if (!x1.next()) return false;
00281 }
00282 else
00283 if (LowerThan()(x2.letter(), x1.letter())) {
00284 if (!x2.next()) return false;
00285 }
00286 else
00287 return true;
00288 return false;
00289 }
00290
00291 char_type letter() const { return x1.letter(); }
00292
00293 bool find(const char_type &a) {
00294 bool r = x1.find(a);
00295 return x2.find(a) && r;
00296 }
00297
00298 bool forward(const char_type &a) {
00299 if (x1.forward(a) && x2.forward(a)) return true;
00300 *this = sink_state();
00301 return false;
00302 }
00303
00304 bool src_final() const { return x1.src_final() && x2.src_final(); }
00305
00306 bool aim_final() const { return x1.aim_final() && x2.aim_final(); }
00307
00308 bool exists(const char_type &a) const { return x1.exists(a) && x2.exists(a); }
00309
00310 tag_type src_tag() const { return tag_type(x1.src_tag(), x2.src_tag()); }
00311
00312 tag_type aim_tag() const { return tag_type(x1.aim_tag(), x2.aim_tag()); }
00313
00314 bool operator==(const self &x) const { return x1 == x.x1 && x2 == x.x2; }
00315
00316
00317 ForwardC1& first_() { return x1; }
00318 ForwardC2& second_() { return x2; }
00319 const ForwardC1& first_() const { return x1; }
00320 const ForwardC2& second_() const { return x2; }
00321
00322 protected:
00323 ForwardC1 x1;
00324 ForwardC2 x2;
00325 };
00326
00327 template <class ForwardCursor1, class ForwardCursor2>
00328 class diff_cursor : public forward_cursor_concept
00329 {
00330 protected:
00331 ForwardCursor1 x1;
00332 mutable ForwardCursor2 x2;
00333
00334 public:
00335 typedef pair<typename ForwardCursor1::state_type,
00336 typename ForwardCursor2::state_type> state_type;
00337 typedef typename ForwardCursor1::char_type char_type;
00338 typedef typename ForwardCursor1::tag_type tag_type;
00339 typedef typename ForwardCursor1::char_traits char_traits;
00340
00341 diff_cursor(const ForwardCursor1 &x1, const ForwardCursor2 &x2)
00342 : x1(x1), x2(x2)
00343 { }
00344
00345 bool operator== (const diff_cursor &y) const {
00346 return x1 == y.x1 && x2 == y.x2;
00347 }
00348
00349 char_type letter() const { return x1.letter(); }
00350
00351 void forward() {
00352 if (!x2.sink()) x2.forward(x1.letter());
00353 x1.forward();
00354 }
00355
00356 bool first() { return x1.first(); }
00357
00358 bool next() { return x1.next(); }
00359
00360 bool find(const char_type &a) { return x1.find(a); }
00361
00362 bool forward(const char_type &a) {
00363 if (!x1.forward(a)) {
00364 x2 = x2.sink_state();
00365 return false;
00366 }
00367 if (!x2.sink()) x2.forward(a);
00368 return true;
00369 }
00370
00371 state_type src() const { return state_type(x1.src(), x2.src()); }
00372
00373 state_type aim() const {
00374 if (!x2.sink() && x2.find(x1.letter()))
00375 return state_type(x1.aim(), x2.aim());
00376 return state_type(x1.aim(), x2.sink_state());
00377 }
00378
00379 bool src_final() const {
00380 return x1.src_final() && (x2.sink() || !x2.src_final());
00381 }
00382
00383 bool aim_final() const {
00384 return x1.aim_final() && (x2.sink() || !x2.find(x1.letter()) || !x2.aim_final());
00385 }
00386
00387 bool sink() const { return x1.sink(); }
00388
00389 state_type sink_state() const {
00390 return state_type(x1.sink_state(), x2.sink_state());
00391 }
00392
00393 bool exists(const char_type &a) const { return x1.exists(a); }
00394
00395 tag_type src_tag() const { return x1.src_tag(); }
00396
00397 tag_type aim_tag() const { return x1.aim_tag(); }
00398 };
00399
00400
00401
00402 template <class C1, class C2>
00403 class sym_diff_cursor
00404 : public diff_cursor<union_cursor<C1, C2>, intersection_cursor<C1, C2> >
00405 {
00406 public:
00407 typedef diff_cursor<union_cursor<C1, C2>, intersection_cursor<C1, C2> > super;
00408 typedef sym_diff_cursor self;
00409 typedef typename super::state_type state_type;
00410 typedef typename super::tag_type tag_type;
00411
00412 sym_diff_cursor(const C1 &x1, const C2 &x2)
00413 : super(unionc(x1, x2), intersectionc(x1, x2))
00414 { }
00415
00416 self& operator=(const state_type &q) {
00417 super::operator=(q);
00418 return *this;
00419 }
00420 };
00421
00422
00423 template <class ForwardCursor1, class ForwardCursor2>
00424 class concatenation_cursor : public forward_cursor_concept
00425 {
00426 protected:
00427 typedef list<pair<bool, ForwardCursor2> > container;
00428
00429 ForwardCursor1 x1;
00430 ForwardCursor2 i;
00431 container x2;
00432 bool ok1;
00433
00434
00435
00436
00437 typename ForwardCursor2::char_type current_letter;
00438
00439 public:
00440 typedef typename ForwardCursor1::tag_type tag_type;
00441 typedef pair<typename ForwardCursor1::state_type,
00442 vector<typename ForwardCursor2::state_type> > state_type;
00443 typedef typename ForwardCursor1::char_type char_type;
00444 typedef typename ForwardCursor1::char_traits char_traits;
00445
00446 concatenation_cursor(const ForwardCursor1 &c1, const ForwardCursor2 &c2)
00447 : x1(c1), i(c2), ok1(false) {
00448 if (!x1.sink() && x1.src_final() && !i.sink())
00449 x2.push_back(make_pair(false, i));
00450 }
00451
00452 bool sink() const { return x1.sink() && x2.empty(); }
00453
00454 state_type sink_state() const {
00455 return state_type(x1.sink_state(), container());
00456 }
00457
00458 state_type src() const {
00459 state_type result(x1.src(), vector<typename ForwardCursor2::state_type>());
00460 result.second.reserve(4);
00461 for(typename container::const_iterator j = x2.begin(); j != x2.end(); ++j)
00462 result.second.push_back((*j).second.src());
00463 return result;
00464 }
00465
00466 state_type aim() const {
00467 state_type result;
00468
00469 result.second.reserve(4);
00470 for(typename container::const_iterator j = x2.begin(); j != x2.end(); ++j)
00471 if ((*j).first && (*j).second.letter() == current_letter)
00472 result.second.push_back((*j).second.aim());
00473
00474 if (ok1 && x1.letter() == current_letter) {
00475 result.first = x1.aim();
00476 if (x1.aim_final()) result.second.push_back(i.src());
00477 }
00478 else result.first = x1.sink_state();
00479 return result;
00480 }
00481
00482 void forward() {
00483 for(typename container::iterator j = x2.begin(); j != x2.end(); )
00484 if ((*j).first && (*j).second.letter() == current_letter) (*j++).second.forward();
00485 else x2.erase(j++);
00486
00487 if (ok1 && x1.letter() == current_letter) {
00488 x1.forward();
00489 if (x1.src_final()) x2.push_back(make_pair(false, i));
00490 }
00491 else {
00492 x1 = x1.sink_state();
00493 ok1 = false;
00494 }
00495 }
00496
00497 bool first() {
00498 if (!x2.empty()) {
00499 typename container::iterator j;
00500 for(j = x2.begin(); j != x2.end() && !(*j).second.first(); ++j)
00501 (*j).first = false;
00502
00503 if (j != x2.end()) {
00504 (*j).first = true;
00505 current_letter = (*j).second.letter();
00506 for(++j; j != x2.end(); ++j) {
00507 (*j).first = (*j).second.first();
00508 if ((*j).first) current_letter = min__(current_letter, (*j).second.letter());
00509 }
00510 ok1 = !x1.sink() && x1.first();
00511 if (ok1) current_letter = min__(current_letter, x1.letter());
00512
00513 return true;
00514 }
00515 }
00516 ok1 = !x1.sink() && x1.first();
00517 if (ok1) current_letter = x1.letter();
00518 return ok1;
00519 }
00520
00521 bool next() {
00522 char_type next_letter;
00523 if (!x2.empty()) {
00524 typename container::iterator j;
00525 for(j = x2.begin(); j != x2.end(); ++j)
00526 if ((*j).first) {
00527 if ((*j).second.letter() == current_letter)
00528 (*j).first = (*j).second.next();
00529 if ((*j).first) {
00530 next_letter = (*j).second.letter();
00531 break;
00532 }
00533 }
00534
00535 if (j != x2.end()) {
00536 for(++j; j != x2.end(); ++j) {
00537 if ((*j).first) {
00538 if ((*j).second.letter() == current_letter)
00539 (*j).first = (*j).second.next();
00540 if ((*j).first) next_letter = min__(next_letter, (*j).second.letter());
00541 }
00542 }
00543
00544 if (ok1 && x1.letter() == current_letter) {
00545 ok1 = x1.next();
00546 if (ok1) next_letter = min__(next_letter, x1.letter());
00547 }
00548
00549 current_letter = next_letter;
00550 return true;
00551 }
00552 }
00553 if (ok1 && x1.letter() == current_letter) {
00554 ok1 = x1.next();
00555 if (ok1) current_letter = x1.letter();
00556 return ok1;
00557 }
00558 return false;
00559 }
00560
00561 char_type letter() const { return current_letter; }
00562
00563 bool find(const char_type &a) {
00564 bool result = ok1 = !x1.sink() && x1.find(a);
00565 for(typename container::iterator j = x2.begin(); j != x2.end(); ++j) {
00566 (*j).first = (*j).second.find(a);
00567 result = result || (*j).first;
00568 }
00569 return result;
00570 }
00571
00572 bool forward(const char_type &a) {
00573 bool result = false;
00574 for(typename container::iterator j = x2.begin(); j != x2.end();)
00575 if ((*j).second.forward(a)) {
00576 result = true;
00577 ++j;
00578 }
00579 else x2.erase(j++);
00580
00581 if (!x1.sink())
00582 if (x1.forward(a)) {
00583 if (x1.src_final())
00584 x2.push_back(i);
00585 return true;
00586 }
00587
00588 return result;
00589 }
00590
00591 bool src_final() const {
00592 for(typename container::const_iterator j = x2.begin(); j != x2.end(); ++j)
00593 if ((*j).second.src_final()) return true;
00594 return false;
00595 }
00596
00597 bool aim_final() const {
00598 for(typename container::const_iterator j = x2.begin(); j != x2.end(); ++j)
00599 if ((*j).first && (*j).second.letter() == current_letter && (*j).second.aim_final())
00600 return true;
00601
00602 return false;
00603 }
00604
00605 bool operator== (const concatenation_cursor &x) const {
00606 return x1 == x.x1 && ok1 == x.ok1 && x2 == x.x2;
00607 }
00608
00609 tag_type src_tag() const {
00610 if (!x1.sink()) return x1.src_tag();
00611 else return tag_type();
00612 }
00613
00614 tag_type aim_tag() const {
00615 if (ok1) return x1.aim_tag();
00616 else return tag_type();
00617 }
00618 };
00619
00620 template <typename EnumerableCharTraits>
00621 class sigma_star_cursor : public forward_cursor_concept
00622 {
00623 protected:
00624 typename EnumerableCharTraits::iterator i;
00625
00626 public:
00627 typedef sigma_star_cursor self;
00628 typedef typename EnumerableCharTraits::char_type char_type;
00629 typedef empty_tag tag_type;
00630 typedef int state_type;
00631 typedef EnumerableCharTraits char_traits;
00632
00633 bool operator==(const self &x) const { return i == x.i; }
00634
00635 self& operator=(state_type&) { return *this; }
00636
00637 state_type src() const { return 1; }
00638
00639 state_type aim() const { return 1; }
00640
00641 state_type sink_state() const { return 0; }
00642
00643 tag_type src_tag() const { return empty_tag(); }
00644
00645 tag_type aim_tag() const { return empty_tag(); }
00646
00647 bool src_final() const { return true; }
00648
00649 bool aim_final() const { return true; }
00650
00651 bool sink() const { return false; }
00652
00653 void forward() { }
00654
00655 bool forward(const char_type&) { return true; }
00656
00657 char_type letter() const { return *i; }
00658
00659 bool first() {
00660 i = char_traits::begin();
00661 return true;
00662 }
00663
00664 bool next() { return ++i != char_traits::end(); }
00665
00666 bool find(const char_type& a) {
00667 i = find(char_traits::begin(), char_traits::end(), a);
00668 return true;
00669 }
00670
00671 bool exists(const char_type&) const { return true; }
00672 };
00673
00674
00675 #ifdef NEW_NOT
00676 template <typename ForwardCursor>
00677 class not_cursor : public ForwardCursor
00678 {
00679 public:
00680 typedef not_cursor self;
00681 typedef ForwardCursor super;
00682 typedef typename super::tag_type tag_type;
00683 typedef typename super::char_type char_type;
00684 typedef pair<typename super::state_type, bool> state_type;
00685 typedef typename super::char_traits char_traits;
00686
00687 protected:
00688 bool vstate;
00689 typename char_traits::const_iterator i;
00690
00691 public:
00692 not_cursor(const ForwardCursor &x)
00693 : super(x), vstate(false)
00694 { }
00695
00696 state_type src() const {
00697 return state_type(super::src(), vstate);
00698 }
00699
00700 self& operator=(const self &x) {
00701 super::operator=(x);
00702 vstate = x.vstate;
00703 return *this;
00704 }
00705
00706 bool sink() const { return super::sink() && !vstate; }
00707
00708 bool forward(const char_type &c) {
00709 vstate = vstate || !super::forward(c);
00710 return true;
00711 }
00712
00713 bool src_final() const { return vstate || !super::src_final(); }
00714
00715 const tag_type& src_tag() const {
00716 if (vstate) return tag_type();
00717 return super::src_tag();
00718 }
00719
00720 bool exists(const char_type &) const { return true; }
00721
00722 self& operator=(const state_type &q) {
00723 super::operator=(q.first);
00724 vstate = q.second;
00725 return *this;
00726 }
00727
00728 state_type sink_state() const {
00729 return state_type(super::sink_state(), false);
00730 }
00731
00732 bool operator==(const self &x) const {
00733 return super::operator==(x) && vstate == x.vstate;
00734 }
00735
00736 char_type letter() const { return *i; }
00737
00738 bool first() {
00739 return (i = char_traits::begin()) != char_traits::end();
00740 }
00741
00742 bool next() { return ++i != char_traits::end(); }
00743
00744 void forward() { if (!vstate) super::forward(); }
00745
00746
00747 bool find(const char_type &c) {
00748 i = find(char_traits::begin(), char_traits::end(), a);
00749 if (!vstate) super::find(c);
00750 return true;
00751 }
00752
00753 state_type aim() const {
00754 if (vstate || !super::exists(letter()))
00755 return state_type(super::sink_state(), true);
00756 return state_type(super::aim(), false);
00757 }
00758
00759 bool aim_final() const {
00760 if (vstate || !super::exists(letter())) return true;
00761 return !super::aim_final();
00762 }
00763
00764 const tag_type& aim_tag() const {
00765 if (vstate || !super::exists(letter())) return tag_type();
00766 return super::aim_tag();
00767 }
00768 };
00769
00770 #else
00771 template <typename ForwardCursor>
00772 class not_cursor
00773 : public diff_cursor<sigma_star_cursor<typename ForwardCursor::char_traits>, ForwardCursor>
00774 {
00775 public:
00776 typedef diff_cursor<sigma_star_cursor<typename ForwardCursor::char_traits>,
00777 ForwardCursor> super;
00778 typedef not_cursor self;
00779 typedef typename super::tag_type tag_type;
00780 typedef typename super::char_type char_type;
00781 typedef typename super::state_type state_type;
00782 typedef typename super::char_traits char_traits;
00783
00784 not_cursor(const ForwardCursor &x)
00785 : super(sigma_star_cursor<typename ForwardCursor::char_traits>(), x)
00786 { }
00787
00788 self& operator=(const state_type& q) {
00789 super::operator=(q);
00790 return *this;
00791 }
00792 };
00793 #endif
00794
00795 template <typename DFirstCursor1, typename DFirstCursor2>
00796 bool isomorph(DFirstCursor1 left, DFirstCursor2 first,
00797 DFirstCursor2 last = DFirstCursor2())
00798 {
00799 typedef map<typename DFirstCursor2::state_type,
00800 typename DFirstCursor1::state_type> mapping;
00801 mapping M;
00802 bool synchrone = true;
00803 while (first != last) {
00804 do {
00805 if (!synchrone) return false;
00806 if (left.letter() != first.letter())
00807 return false;
00808 if (M.find(first.src()) == M.end())
00809 M[first.src()] = left.src();
00810 else
00811 if (M[first.src()] != left.src())
00812 return false;
00813 synchrone = left.forward();
00814 } while (first.forward());
00815 if (synchrone) return false;
00816 if (M.find(first.aim()) == M.end())
00817 M[first.aim()] = left.aim();
00818 else
00819 if (M[first.aim()] != left.aim())
00820 return false;
00821 synchrone = true;
00822 do {
00823 if (!synchrone) return false;
00824 synchrone = !left.forward();
00825 } while (!first.forward());
00826 if (synchrone) return false;
00827 synchrone = true;
00828 }
00829 return true;
00830 }
00831
00832
00833
00834
00835 template <typename ForwardC1, typename ForwardC2>
00836 inline
00837 intersection_cursor<ForwardC1, ForwardC2>
00838 intersectionc(const ForwardC1 &x1, const ForwardC2 &x2) {
00839 return intersection_cursor<ForwardC1, ForwardC2>(x1, x2);
00840 }
00841
00842
00843 template <typename ForwardC1, typename ForwardC2, typename LowerThan>
00844 inline
00845 intersection_cursor<ForwardC1, ForwardC2, LowerThan>
00846 intersectionc(const ForwardC1 &x1, const ForwardC2 &x2, const LowerThan&) {
00847 return intersection_cursor<ForwardC1, ForwardC2, LowerThan>(x1, x2);
00848 }
00849
00850 template <typename ForwardC1, typename ForwardC2>
00851 inline
00852 union_cursor<ForwardC1, ForwardC2>
00853 unionc(const ForwardC1 &x1, const ForwardC2 &x2) {
00854 return union_cursor<ForwardC1, ForwardC2>(x1, x2);
00855 }
00856
00857 template <typename ForwardC1, typename ForwardC2>
00858 inline
00859 diff_cursor<ForwardC1, ForwardC2>
00860 diffc(const ForwardC1 &x1, const ForwardC2 &x2) {
00861 return diff_cursor<ForwardC1, ForwardC2>(x1, x2);
00862 }
00863
00864 template <typename ForwardC1, typename ForwardC2>
00865 inline
00866 sym_diff_cursor<ForwardC1, ForwardC2>
00867 sym_diffc(const ForwardC1 &x1, const ForwardC2 &x2) {
00868 return sym_diff_cursor<ForwardC1, ForwardC2>(x1, x2);
00869 }
00870
00871 template <typename ForwardC1, typename ForwardC2>
00872 inline
00873 concatenation_cursor<ForwardC1, ForwardC2>
00874 concatenationc(const ForwardC1 &x1, const ForwardC2 &x2) {
00875 return concatenation_cursor<ForwardC1, ForwardC2>(x1, x2);
00876 }
00877
00878 template <typename ForwardC>
00879 inline
00880 not_cursor<ForwardC> notc(const ForwardC &x) {
00881 return not_cursor<ForwardC>(x);
00882 }
00883
00884 template <typename EnumerableCharTraits>
00885 inline
00886 sigma_star_cursor<EnumerableCharTraits> sigma_starc() {
00887 return sigma_star_cursor<EnumerableCharTraits>();
00888 }
00889
00890 }
00891
00892 #endif
00893
00894
00895
00896