Vaucanson: bmig_graph_letters_spec.hxx Source File

00001 // boost_graph.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2007, 2008 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 
00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HXX_
00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HXX_
00020 
00021 # include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh>
00022 
00023 namespace vcsn
00024 {
00025   namespace bmig
00026   {
00027 
00028     /*--------------------.
00029     | Convenient macros.  |
00030     `--------------------*/
00031 
00032   # define BMIGRAPH_TPARAM                                              \
00033     template <class WordValue,                                          \
00034               class SeriesValue, class Letter, class Tag, class GeometryCoords>
00035 
00036   # define BMIGRAPH                                                     \
00037     Graph<labels_are_letters, WordValue, bool, SeriesValue, Letter, Tag, GeometryCoords>
00038 
00039     /*-------------------------.
00040     | Graph's implementation.  |
00041     `-------------------------*/
00042 
00043     /*---------------.
00044     | Constructors.  |
00045     `---------------*/
00046 
00047     BMIGRAPH_TPARAM
00048     inline
00049     BMIGRAPH::Graph ()
00050       : initial_bitset_(0),
00051         final_bitset_(0),
00052         number_of_epsilon_(0),
00053         number_of_state_(0)
00054     {
00055     }
00056 
00066     BMIGRAPH_TPARAM
00067     BMIGRAPH::Graph (unsigned initial_number_of_states,
00068                       unsigned)
00069       : initial_bitset_(initial_number_of_states),
00070         final_bitset_(initial_number_of_states),
00071         number_of_epsilon_(0),
00072         number_of_state_(initial_number_of_states),
00073         states_(initial_number_of_states)
00074     {
00075       for (unsigned i = 0; i < initial_number_of_states; ++i)
00076       {
00077         boost::shared_ptr<unsigned> p(new unsigned(i));
00078         states_[i] = p;
00079       }
00080     }
00081 
00082     BMIGRAPH_TPARAM
00083     BMIGRAPH::Graph (const self_t& g)
00084     {
00085       tag_ = g.tag_;
00086       initial_bitset_ = g.initial_bitset_;
00087       final_bitset_ = g.final_bitset_;
00088       number_of_epsilon_ = g.number_of_epsilon_;
00089       number_of_state_ = g.number_of_state_;
00090 
00091       initial_.clear();
00092       final_.clear();
00093       graph_.clear();
00094       typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
00095       map_transitions.clear();
00096 
00097       states_.resize(g.number_of_state_);
00098       for (unsigned i = 0; i < g.number_of_state_; ++i)
00099       {
00100         boost::shared_ptr<unsigned> p(new unsigned(i));
00101         states_[i] = p;
00102       }
00103       for (typename graph_data_t::const_iterator i = g.graph_.begin();
00104           i != g.graph_.end();
00105           ++i)
00106         graph_.insert(edge_data_t(states_[*i->from_],
00107                                   states_[*i->to_],
00108                                   i->label_));
00109       for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it)
00110         initial_.insert(states_[**it]);
00111       for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it)
00112         final_.insert(states_[**it]);
00113 
00114   # define VCSN_COPY_GEOMETRY(Type)                                                                     \
00115       {                                                                                                 \
00116         typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type();                      \
00117         map_##Type.clear();                                                                             \
00118         for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
00119             i != g.geometry_.Type().end();                                                              \
00120             ++i)                                                                                                \
00121           map_##Type[i->first] = i->second;                                                             \
00122       }
00123       VCSN_COPY_GEOMETRY(states)
00124       VCSN_COPY_GEOMETRY(initials)
00125       VCSN_COPY_GEOMETRY(finals)
00126   # undef VCSN_COPY_GEOMETRY
00127       {
00128         for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
00129             i != g.geometry_.transitions().end();
00130             ++i)
00131         {
00132           typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
00133                                                                 states_[*i->first.value()->to_],
00134                                                                 i->first.value()->label_);
00135           if (tmp != graph_.end())
00136             map_transitions[htransition_t(tmp)] = i->second;
00137         }
00138       }
00139     }
00140 
00141     /*--------------.
00142     | Destructors.  |
00143     `--------------*/
00144 
00145     BMIGRAPH_TPARAM
00146     inline
00147     BMIGRAPH::~Graph ()
00148     {
00149     }
00150 
00151     BMIGRAPH_TPARAM
00152     typename BMIGRAPH::self_t&
00153     BMIGRAPH::operator= (const self_t& g)
00154     {
00155       if (this == &g)
00156         return *this;
00157       tag_ = g.tag_;
00158       initial_bitset_ = g.initial_bitset_;
00159       final_bitset_ = g.final_bitset_;
00160       number_of_epsilon_ = g.number_of_epsilon_;
00161       number_of_state_ = g.number_of_state_;
00162 
00163       initial_.clear();
00164       final_.clear();
00165       graph_.clear();
00166       typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
00167       map_transitions.clear();
00168 
00169       states_.resize(g.number_of_state_);
00170       for (unsigned i = 0; i < g.number_of_state_; ++i)
00171       {
00172         boost::shared_ptr<unsigned> p(new unsigned(i));
00173         states_[i] = p;
00174       }
00175       for (typename graph_data_t::const_iterator i = g.graph_.begin();
00176           i != g.graph_.end();
00177           ++i)
00178         graph_.insert(edge_data_t(states_[*i->from_],
00179                                   states_[*i->to_],
00180                                   i->label_));
00181       for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it)
00182         initial_.insert(states_[**it]);
00183       for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it)
00184         final_.insert(states_[**it]);
00185 
00186   # define VCSN_COPY_GEOMETRY(Type)                                                                     \
00187       {                                                                                                 \
00188         typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type();                      \
00189         map_##Type.clear();                                                                             \
00190         for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
00191             i != g.geometry_.Type().end();                                                              \
00192             ++i)                                                                                                \
00193           map_##Type[i->first] = i->second;                                                             \
00194       }
00195       VCSN_COPY_GEOMETRY(states)
00196       VCSN_COPY_GEOMETRY(initials)
00197       VCSN_COPY_GEOMETRY(finals)
00198   # undef VCSN_COPY_GEOMETRY
00199       for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
00200           i != g.geometry_.transitions().end();
00201           ++i)
00202       {
00203         typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
00204             states_[*i->first.value()->to_],
00205             i->first.value()->label_);
00206         if (tmp != graph_.end())
00207           map_transitions[htransition_t(tmp)] = i->second;
00208       }
00209       return *this;
00210     }
00211 
00212     /*------------------.
00213     | Basic accessors.  |
00214     `------------------*/
00215 
00216     BMIGRAPH_TPARAM
00217     typename BMIGRAPH::states_t
00218     BMIGRAPH::states() const
00219     {
00220       return misc::Support<states_data_t>(states_);
00221     }
00222 
00223     BMIGRAPH_TPARAM
00224     typename BMIGRAPH::edges_t
00225     BMIGRAPH::edges() const
00226     {
00227       return edges_t(graph_);
00228     }
00229 
00230     BMIGRAPH_TPARAM
00231     typename BMIGRAPH::initial_support_t
00232     BMIGRAPH::initial () const
00233     {
00234       return initial_support_t(initial_);
00235     }
00236 
00237     BMIGRAPH_TPARAM
00238     typename BMIGRAPH::final_support_t
00239     BMIGRAPH::final () const
00240     {
00241       return final_support_t(final_);
00242     }
00243 
00244 
00245     /*----------------------.
00246     | State manipulations.  |
00247     `----------------------*/
00248 
00249     BMIGRAPH_TPARAM
00250     bool
00251     BMIGRAPH::has_state (const hstate_t& s) const
00252     {
00253       return s < states_.size();
00254     }
00255 
00256     BMIGRAPH_TPARAM
00257     typename BMIGRAPH::hstate_t
00258     BMIGRAPH::add_state ()
00259     {
00260       initial_bitset_.append(false);
00261       final_bitset_.append(false);
00262       boost::shared_ptr<unsigned> p(new unsigned(number_of_state_++));
00263       state_t h(p);
00264       states_.push_back(h);
00265       return hstate_t(h);
00266     }
00267 
00268     BMIGRAPH_TPARAM
00269     typename BMIGRAPH::hstate_t
00270     BMIGRAPH::get_state (unsigned s) const
00271     {
00272       precondition(s < states_.size());
00273       return hstate_t(states_[s]);
00274     }
00275 
00276     BMIGRAPH_TPARAM
00277     void
00278     BMIGRAPH::del_state (const hstate_t& s)
00279     {
00280       precondition (has_state(s));
00281 
00282       // One removes the state h
00283       graph_.get<src>().erase(s.value());
00284       graph_.get<dst>().erase(s.value());
00285 
00286       if (number_of_state_ > 1 && s != (number_of_state_ - 1))
00287       {
00288         state_t lastone = states_.back();
00289         states_[s] = lastone;
00290   # define VCSN_UPDATE(Set)                                   \
00291         if (Set##bitset_[*lastone])                           \
00292         {                                                     \
00293           if (Set##bitset_[s])                                \
00294             Set.erase(s.value());                             \
00295           else                                                \
00296             Set##bitset_[s] = true;                           \
00297         }                                                     \
00298         else                                                  \
00299         {                                                     \
00300           if (Set##bitset_[s])                                \
00301           {                                                   \
00302             Set##bitset_[s] = false;                          \
00303             Set.erase(s.value());                             \
00304           }                                                   \
00305         }
00306 
00307         //Updating initial/final states information
00308         VCSN_UPDATE(initial_)
00309         VCSN_UPDATE(final_)
00310   # undef VCSN_UPDATE
00311         *lastone = *s.value();
00312       }
00313       else
00314       {
00315         initial_.erase(s.value());
00316         final_.erase(s.value());
00317       }
00318 
00319       --number_of_state_;
00320       states_.pop_back();
00321       postcondition(states_.size() == number_of_state_);
00322       initial_bitset_.resize(number_of_state_);
00323       final_bitset_.resize(number_of_state_);
00324 
00325       //Useless postcondition since the states are renumbered
00326       //postcondition(!has_state(h));
00327     }
00328 
00329     BMIGRAPH_TPARAM
00330     void
00331     BMIGRAPH::set_initial (const hstate_t& s,
00332                              const series_set_elt_value_t& v,
00333                              const series_set_elt_value_t& z)
00334     {
00335       precondition(has_state(s));
00336       if (z == v)
00337       {
00338         initial_.erase (s.value());
00339         initial_bitset_[s] = false;
00340       }
00341       else
00342       {
00343         initial_.insert (s.value());
00344         initial_bitset_[s] = true;
00345       }
00346     }
00347 
00348     BMIGRAPH_TPARAM
00349     const typename BMIGRAPH::series_set_elt_value_t&
00350     BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &) const
00351     {
00352       precondition(has_state(s));
00353       return initial_bitset_[s];
00354     }
00355 
00356     BMIGRAPH_TPARAM
00357     bool
00358     BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const
00359     {
00360       precondition(has_state(s));
00361       return initial_bitset_[s];
00362     }
00363 
00364     BMIGRAPH_TPARAM
00365     void
00366     BMIGRAPH::clear_initial()
00367     {
00368       initial_.clear();
00369       initial_bitset_.reset();
00370     }
00371 
00372     BMIGRAPH_TPARAM
00373     void
00374     BMIGRAPH::set_final(const hstate_t& s,
00375                           const series_set_elt_value_t& v,
00376                           const series_set_elt_value_t& z)
00377     {
00378       precondition(has_state(s));
00379       if (z == v)
00380       {
00381         final_.erase (s.value());
00382         final_bitset_[s] = false;
00383       }
00384       else
00385       {
00386         final_.insert (s.value());
00387         final_bitset_[s] = true;
00388       }
00389     }
00390 
00391     BMIGRAPH_TPARAM
00392     const typename BMIGRAPH::series_set_elt_value_t&
00393     BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &) const
00394     {
00395       precondition(has_state(s));
00396       return final_bitset_[s];
00397     }
00398 
00399     BMIGRAPH_TPARAM
00400     bool
00401     BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const
00402     {
00403       precondition(has_state(s));
00404       return final_bitset_[s];
00405     }
00406 
00407     BMIGRAPH_TPARAM
00408     void
00409     BMIGRAPH::clear_final()
00410     {
00411       final_.clear();
00412       final_bitset_.reset();
00413     }
00414 
00415     /*---------------------.
00416     | Edge manipulations.  |
00417     `---------------------*/
00418 
00419     BMIGRAPH_TPARAM
00420     bool
00421     BMIGRAPH::has_edge (const hedge_t& h) const
00422     {
00423       succ_range r = graph_.equal_range(boost::make_tuple(*h.value()->from_,
00424                                                     h.value()->label_));
00425       succ_iterator it;
00426       state_t to = h.value()->to_;
00427       for (it = r.first; it != r.second && it->to_ != to; ++it)
00428         /*Nothing*/;
00429 
00430       return it != r.second;
00431     }
00432 
00433     BMIGRAPH_TPARAM
00434     typename BMIGRAPH::hedge_t
00435     BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l)
00436     {
00437       return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first);
00438     }
00439 
00440     BMIGRAPH_TPARAM
00441     void
00442     BMIGRAPH::del_edge (const hedge_t& h)
00443     {
00444       precondition (has_edge(h));
00445       graph_.erase(h.value());
00446 
00447       // h points to an invalid edgeValue since it is already destroyed.
00448       // We can't check this postcondition anymore!
00449       //postcondition(!has_edge(h));
00450     }
00451 
00452     BMIGRAPH_TPARAM
00453     typename BMIGRAPH::hstate_t
00454     BMIGRAPH::src_of (const hedge_t& h) const
00455     {
00456       return hstate_t(h.value()->from_);
00457     }
00458 
00459     BMIGRAPH_TPARAM
00460     typename BMIGRAPH::hstate_t
00461     BMIGRAPH::dst_of (const hedge_t& h) const
00462     {
00463       return hstate_t(h.value()->to_);
00464     }
00465 
00466     BMIGRAPH_TPARAM
00467     const typename BMIGRAPH::label_t&
00468     BMIGRAPH::label_of (const hedge_t& h) const
00469     {
00470       return h.value()->label_;
00471     }
00472 
00473     BMIGRAPH_TPARAM
00474     void
00475     BMIGRAPH::update(const hedge_t& h, const label_t& l)
00476     {
00477       graph_.modify(h.value(), update_hlabel<label_t>(l));
00478     }
00479 
00480     BMIGRAPH_TPARAM
00481     template <class S>
00482     bool
00483     BMIGRAPH::exists (const AutomataBase<S>& s) const
00484     {
00485       typename WordValue::iterator      it;
00486       typename label_t::const_iterator  r;
00487       label_t                           l;
00488       WordValue                         w;
00489 
00490       for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i)
00491       {
00492         // Make sure that source and destination of edge are part of the
00493         // automaton.
00494         if (!has_state(dst_of(hedge_t(i))) ||
00495             !has_state(src_of(hedge_t(i))))
00496           return false;
00497 
00498         // Make sure that every letter of the edge is in the alphabet.
00499         l = label_of(hedge_t(i));
00500         for (r = l.begin(); r != l.end(); ++r)
00501         {
00502           w = r->first;
00503           for (it = w.begin(); it != w.end(); ++it)
00504             if (!s.series().monoid().alphabet().contains(*it))
00505               return false;
00506         }
00507       }
00508       return true;
00509     }
00510 
00511     BMIGRAPH_TPARAM
00512     inline
00513     typename BMIGRAPH::tag_t&
00514     BMIGRAPH::tag ()
00515     {
00516       return tag_;
00517     }
00518 
00519     BMIGRAPH_TPARAM
00520     inline
00521     const typename BMIGRAPH::tag_t&
00522     BMIGRAPH::tag () const
00523     {
00524       return tag_;
00525     }
00526 
00527     BMIGRAPH_TPARAM
00528     inline
00529     typename BMIGRAPH::geometry_t&
00530     BMIGRAPH::geometry ()
00531     {
00532       return geometry_;
00533     }
00534 
00535     BMIGRAPH_TPARAM
00536     inline
00537     const typename BMIGRAPH::geometry_t&
00538     BMIGRAPH::geometry () const
00539     {
00540       return geometry_;
00541     }
00542 
00543     template <class WordValue, class SeriesValue,
00544               class Letter, class Tag, class GeometryCoords, class I>
00545     Tag&
00546     op_tag(const AutomataBase<I>&, BMIGRAPH &g)
00547     {
00548       return g.tag();
00549     }
00550 
00551     template <class WordValue, class SeriesValue,
00552               class Letter, class Tag, class GeometryCoords, class I>
00553     const Tag&
00554     op_tag(const AutomataBase<I>&, BMIGRAPH &g)
00555     {
00556       return g.tag();
00557     }
00558 
00559     template <class WordValue, class SeriesValue,
00560               class Letter, class Tag, class GeometryCoords, class I>
00561     typename BMIGRAPH::geometry_t&
00562     op_geometry(const AutomataBase<I>&, BMIGRAPH &g)
00563     {
00564       return g.geometry();
00565     }
00566 
00567     template <class WordValue, class SeriesValue,
00568               class Letter, class Tag, class GeometryCoords, class I>
00569     const typename BMIGRAPH::geometry_t&
00570     op_geometry(const AutomataBase<I>&, const BMIGRAPH &g)
00571     {
00572       return g.geometry();
00573     }
00574 
00575     BMIGRAPH_TPARAM
00576     typename BMIGRAPH::graph_data_t::const_iterator
00577     BMIGRAPH::find_edge(const state_t& from, const state_t& to,
00578                           const label_t& label) const
00579     {
00580       succ_range r = graph_.equal_range(::boost::make_tuple(from, label));
00581       for (succ_iterator i = r.first; i != r.second; ++i)
00582         if (i->to_ == to)
00583           return i;
00584       return graph_.end();
00585     }
00586 
00587     /*------------------.
00588     | Delta functions.  |
00589     `------------------*/
00590   # define DEFINE_DELTA_FUNCTION(FunName, DeltaKind, Target, GetElt)            \
00591     BMIGRAPH_TPARAM                                                             \
00592     template <typename OutputIterator, typename Query>                          \
00593     void                                                                        \
00594     BMIGRAPH::FunName(OutputIterator res,                                       \
00595                         const typename BMIGRAPH::hstate_t& s,                   \
00596                         const Query& query,                                     \
00597                         ::vcsn::delta_kind::DeltaKind) const                    \
00598     {                                                                           \
00599       assertion(has_state(s));                                                  \
00600       Target##_range r = graph_.get<Target>().equal_range(s.value());           \
00601       for (Target##_iterator e = r.first; e != r.second; ++e)                   \
00602         if (query(hedge_t(graph_.project<0>(e))))                               \
00603           *res++ = GetElt;                                                      \
00604     }
00605 
00606     DEFINE_DELTA_FUNCTION (delta, transitions, src, hedge_t(graph_.project<0>(e)));
00607     DEFINE_DELTA_FUNCTION (delta, states, src, hstate_t(e->to_));
00608     DEFINE_DELTA_FUNCTION (rdelta, transitions, dst, hedge_t(graph_.project<0>(e)));
00609     DEFINE_DELTA_FUNCTION (rdelta, states, dst, hstate_t(e->from_));
00610 
00611   # undef DEFINE_DELTA_FUNCTION
00612 
00613 
00614     // End of syntactic sugar
00615 # undef BMIGRAPH_TPARAM
00616 # undef BMIGRAPH
00617   } // End of namespace boost
00618 } // End of namespace vcsn
00619 
00620 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //