set_operation.h

00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2003 Vincent Le Maout (vincent.lemaout@chello.fr).
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  * 
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with this library; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019  *
00020  */
00021 
00022 #ifndef ASTL_SET_OPERATION_H
00023 #define ASTL_SET_OPERATION_H
00024 
00025 #include <astl.h>
00026 
00027 // Requirements: 
00028 // Outgoing transitions of adapted cursors must be sorted in increasing order
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();  // case (0, q2)
00081       return;
00082     }
00083     if (x2_at_end) {
00084       x2 = x2.sink_state();
00085       x1.forward();  // case (q1, 0)
00086       return;
00087     }
00088     // case (q1, q2)
00089     if (LowerThan()(x1.letter(), x2.letter())) {  // x1.letter() < x2.letter()
00090       x2 = x2.sink_state();
00091       x1.forward(); 
00092       return;
00093     }
00094     if (LowerThan()(x2.letter(),x1.letter())) {   // x2.letter() < x1.letter()
00095       x1 = x1.sink_state();
00096       x2.forward();
00097       return;
00098     }
00099     // x1.letter() == x2.letter()
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();   // (0, q2)
00113       return !x2_at_end;
00114     }
00115     if (x2_at_end) {
00116       x1_at_end = !x1.next();   // (q1, 0)
00117       return !x1_at_end;
00118     }
00119     // case (q1, q2)
00120     if (LowerThan()(x1.letter(), x2.letter())) { // x1.letter() < x2.letter()
00121       x1_at_end = !x1.next();
00122       return true;
00123     }
00124     if (LowerThan()(x2.letter(), x1.letter())) { // x2.letter() < x1.letter()
00125       x2_at_end = !x2.next();
00126       return true;
00127     } 
00128     // x2.letter() == x1.letter()
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   // Not a standard requirement, do not use in algorithms (needed by wgrep):
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    //  *first == *second 
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    //  *first == *second 
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);  // we don't want any lazy boolean evaluation
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   // Not a standard requirement, do not use in algorithms (needed by wgrep):
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;  // mutable because methods *_final() are const 
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 // Symmetrical Difference
00401 // (A1 || A2) \ (A1 && A2)
00402 template <class C1, class C2>   // C1,C2 forward cursor types
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; // ok1 == true signifie x1 est actif et sur une transition
00433   // déréférençable. Invariant: x1.sink() && ok1 == false (on ne peut
00434   // pas avoir x1 sur le puits ET ok1 vrai simultanément
00435   // x1.sink() == true => ok1 == false). Même chose pour les curseurs de
00436   // x2 qui possèdent leur booléen associé (cf typedef container).
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 // #define NEW_NOT 
00674 // Requirements on types: ForwardCursor::char_traits must be an EnumerableCharTraits
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;    // is the cursor pointing to the virtual default state ?
00689   typename char_traits::const_iterator i;   // current transition letter
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   // Linear time, sorry
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;  // both cursors should keep going up & down simultaneously
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 // Helper functions:
00834 // Build a forward cursor adapter intersection from two forward cursors:
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 // Use a non-default order relation on letters:
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 } // namespace astl
00891 
00892 #endif
00893 
00894 
00895 
00896 

Generated on Sun Mar 8 02:41:35 2009 for ASTL by  doxygen 1.5.7.1