Vaucanson: listg_graph_impl.hxx Source File

00001 // listg_graph_impl.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005, 2006, 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 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX
00018 # define VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX
00019 
00020 # include <fstream>
00021 # include <sstream>
00022 
00023 # include <algorithm>
00024 # include <utility>
00025 
00026 # include <vaucanson/automata/implementation/listg_graph_impl.hh>
00027 # include <vaucanson/misc/contract.hh>
00028 # include <vaucanson/misc/static.hh>
00029 
00030 namespace vcsn
00031 {
00032   namespace listg
00033   {
00034 
00035     /*--------------------.
00036     | Convenient macros.  |
00037     `--------------------*/
00038 
00039     # define TParam                                                             \
00040     template <class Kind, class WordValue, class WeightValue,           \
00041             class SeriesValue, class Letter, class Tag, class GeometryCoords>
00042 
00043     # define GClass                                                             \
00044     Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, GeometryCoords>
00045 
00046     /*-------------------------.
00047     | Graph's implementation.  |
00048     `-------------------------*/
00049 
00050     /*---------------.
00051     | Constructors.  |
00052     `---------------*/
00053 
00054     TParam
00055     GClass::Graph()
00056     { }
00057 
00058     TParam
00059     GClass::Graph (unsigned initial_number_of_state,
00060                    unsigned reserve_number_of_edge)
00061     {
00062       states_.resize(initial_number_of_state);
00063       edges_.reserve(reserve_number_of_edge);
00064     }
00065 
00066     /*------------------.
00067     | Basic accessors.  |
00068     `------------------*/
00069 
00070     TParam
00071     typename GClass::states_t
00072     GClass::states() const
00073     {
00074       return states_t(hstate_t(0),
00075                       hstate_t(states_.size() - 1),
00076                       removed_states_);
00077     }
00078 
00079     TParam
00080     typename GClass::edges_t
00081     GClass::edges() const
00082     {
00083       return edges_t(hedge_t(0),
00084                      hedge_t(edges_.size() - 1),
00085                      removed_edges_);
00086     }
00087 
00088     TParam
00089     typename GClass::initial_support_t
00090     GClass::initial() const
00091     {
00092       return initial_support_t(initial_);
00093     }
00094 
00095     TParam
00096     typename GClass::final_support_t
00097     GClass::final() const
00098     {
00099       return final_support_t(final_);
00100     }
00101 
00102 
00103     /*----------------------.
00104     | States manipulation.  |
00105     `----------------------*/
00106 
00107     TParam
00108     bool
00109     GClass::has_state(const hstate_t& n) const
00110     {
00111       bool res = (n.is_valid() &&
00112                   n < unsigned(states_.size()) &&
00113                   (removed_states_.find(n) == removed_states_.end()));
00114      # ifndef VCSN_NDEBUG
00115       if (res == false)
00116       for (unsigned i = 0; i < edges_.size(); ++i)
00117               if (removed_edges_.find(hedge_t(i)) == removed_edges_.end())
00118               postcondition(edges_[i].from != n
00119                               && edges_[i].to != n);
00120       # endif // !VCSN_NDEBUG
00121       return res;
00122     }
00123 
00124     TParam
00125     typename GClass::hstate_t
00126     GClass::get_state(int n) const
00127     {
00128       precondition(has_state(hstate_t(n)));
00129       return hstate_t(n);
00130     }
00131 
00132     TParam
00133     typename GClass::hstate_t
00134     GClass::add_state()
00135     {
00136       if (removed_states_.size() == 0)
00137       {
00138         states_.push_back(state_value_t());
00139         return hstate_t(states_.size() - 1);
00140       }
00141 
00142       hstate_t n = *removed_states_.begin();
00143       removed_states_.erase(n);
00144       assertion(n < states_.size());
00145 
00146       states_[n].output_edges.clear();
00147       states_[n].input_edges.clear();
00148 
00149       postcondition(has_state(n));
00150       return n;
00151     }
00152 
00153     TParam
00154     void
00155     GClass::del_state(const hstate_t& n)
00156     {
00157       precondition (has_state(n));
00158 
00159       const state_value_t& v = states_[n];
00160       typename state_value::edges_t::const_iterator e = v.output_edges.begin();
00161       typename state_value::edges_t::const_iterator end = v.output_edges.end();
00162       typename state_value::edges_t::const_iterator next = e;
00163 
00164       for (; e != end; e = next)
00165       {
00166         ++next;
00167         this->del_edge(*e);
00168       }
00169 
00170       e = v.input_edges.begin();
00171       end = v.input_edges.end();
00172       for (next = e; e != end; e = next)
00173       {
00174         ++next;
00175         this->del_edge(*e);
00176       }
00177 
00178       removed_states_.insert(n);
00179       initial_.erase(n);
00180       final_.erase(n);
00181       postcondition(!has_state(n));
00182     }
00183 
00184     TParam
00185     void
00186     GClass::set_initial(const hstate_t& n, const series_set_elt_value_t& v,
00187                         const series_set_elt_value_t& z)
00188     {
00189       precondition (has_state(n));
00190       if (z == v)
00191         initial_.erase(n);
00192       else
00193         initial_[n] = v;
00194     }
00195 
00196     TParam
00197     const typename GClass::series_set_elt_value_t&
00198     GClass::get_initial(const hstate_t& n, const series_set_elt_value_t& z) const
00199     {
00200       precondition(has_state(n));
00201       typename initial_t::const_iterator i = initial_.find(n);
00202       if (i == initial_.end())
00203         return z;
00204       return i->second;
00205     }
00206 
00207     TParam
00208     bool
00209     GClass::is_initial(const hstate_t& s, const series_set_elt_value_t& z) const
00210     {
00211       return get_initial(s, z) != z;
00212     }
00213 
00214     TParam
00215     void
00216     GClass::clear_initial()
00217     {
00218       return initial_.clear();
00219     }
00220 
00221     TParam
00222     void
00223     GClass::set_final(const hstate_t& n, const series_set_elt_value_t& v,
00224                       const series_set_elt_value_t& z)
00225     {
00226       precondition (has_state(n));
00227       if (v == z)
00228         final_.erase(n);
00229       else
00230         final_[n] = v;
00231     }
00232 
00233     TParam
00234     const typename GClass::series_set_elt_value_t&
00235     GClass::get_final(const hstate_t& n, const series_set_elt_value_t& z) const
00236     {
00237       precondition (has_state(n));
00238       typename final_t::const_iterator i = final_.find(n);
00239       if (i == final_.end())
00240         return z;
00241       return i->second;
00242     }
00243 
00244     TParam
00245     bool
00246     GClass::is_final(const hstate_t& s, const series_set_elt_value_t& z) const
00247     {
00248       return get_final(s, z) != z;
00249     }
00250 
00251     TParam
00252     void
00253     GClass::clear_final()
00254     {
00255       return final_.clear();
00256     }
00257 
00258 
00259     /*---------------------.
00260     | Edges manipulation.  |
00261     `---------------------*/
00262 
00263     TParam
00264     bool
00265     GClass::has_edge(const hedge_t& e) const
00266     {
00267       bool res = (removed_edges_.find(e) == removed_edges_.end()
00268                   && (e < edges_.size()));
00269       # ifndef VCSN_NDEBUG
00270       if (res == false)
00271         for (unsigned i = 0; i < states_.size(); ++i)
00272           if (removed_states_.find(hstate_t(i)) == removed_states_.end())
00273             postcondition(states_[i].output_edges.find(e) ==
00274                           states_[i].output_edges.end());
00275       # endif // !VCSN_NDEBUG
00276       return res;
00277     }
00278 
00279     TParam
00280     typename GClass::hedge_t
00281     GClass::add_edge(const hstate_t& n1, const hstate_t& n2,
00282                      const label_t& v)
00283     {
00284       precondition(has_state(n1));
00285       precondition(has_state(n2));
00286       hedge_t e;
00287       if (removed_edges_.size() == 0)
00288       {
00289         edges_.push_back(edge_value_t(n1, n2, v));
00290         e = hedge_t(edges_.size() - 1);
00291       }
00292       else
00293       {
00294         e = *removed_edges_.begin();
00295         removed_edges_.erase(e);
00296         assertion(e < edges_.size());
00297         edges_[e].from = n1;
00298         edges_[e].to = n2;
00299         edges_[e].label = v;
00300       }
00301       states_[n1].output_edges.insert(e);
00302       states_[n2].input_edges.insert(e);
00303 
00304       postcondition(has_edge(e));
00305       return e;
00306     }
00307 
00308     TParam
00309     void
00310     GClass::del_edge(const hedge_t& e)
00311     {
00312       precondition (has_edge(e));
00313 
00314       const edge_value_t& ev = edges_[e];
00315       states_[ev.from].output_edges.erase(e);
00316       states_[ev.to].input_edges.erase(e);
00317       removed_edges_.insert(e);
00318 
00319       postcondition(!has_edge(e));
00320     }
00321 
00322 
00323     TParam
00324     typename GClass::hstate_t
00325     GClass::src_of(const hedge_t& e1) const
00326     {
00327       precondition(has_edge(e1));
00328       return edges_[e1].from;
00329     }
00330 
00331     TParam
00332     typename GClass::hstate_t
00333     GClass::dst_of(const hedge_t& e2) const
00334     {
00335       precondition(has_edge(e2));
00336       return edges_[e2].to;
00337     }
00338 
00339     TParam
00340     const typename GClass::label_t&
00341     GClass::label_of(const hedge_t& n) const
00342     {
00343       precondition(has_edge(n));
00344       return edges_[n];
00345     }
00346 
00347     TParam
00348     void
00349     GClass::update(const hedge_t& e, label_t l)
00350     {
00351       precondition(has_edge(e));
00352       edges_[e].label = l;
00353     }
00354 
00355 
00357     TParam
00358     template <class S>
00359     bool
00360     GClass::exists(const AutomataBase<S>& s) const
00361     {
00362       typename WordValue::iterator      it;
00363       typename label_t::const_iterator  r;
00364       label_t                           l;
00365       WordValue                         w;
00366 
00367       for (unsigned i = 0; i < edges_.size(); ++i)
00368       {
00369         if (removed_edges_.find(hedge_t(i)) != removed_edges_.end())
00370           continue;
00371         // Make sure that source and destination of edge are part of the
00372         // automaton.
00373         if (!has_state(dst_of(hedge_t(i)))
00374             || !has_state(src_of(hedge_t(i))))
00375           return false;
00376 
00377         // Make sure that every letter of the edge is in the alphabet.
00378         l = label_of(hedge_t(i));
00379         for (r = l.begin(); r != l.end(); ++r)
00380         {
00381           w = r->first;
00382           for (it = w.begin(); it != w.end(); ++it)
00383             if (!s.series().monoid().alphabet().contains(*it))
00384               return false;
00385         }
00386       }
00387       return true;
00388     }
00389 
00390     /*------.
00391     | Tag.  |
00392     `------*/
00393 
00394     TParam
00395     inline
00396     Tag& GClass::tag()
00397     {
00398       return tag_;
00399     }
00400 
00401     TParam
00402     const Tag& GClass::tag() const
00403     {
00404       return tag_;
00405     }
00406 
00407     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00408               class Letter, class Tag, class GeometryCoords, class I>
00409     Tag& op_tag(const AutomataBase<I>&,
00410                 Graph<Kind, WordValue, WeightValue,
00411                 SerieValue ,Letter, Tag, GeometryCoords>& v)
00412     {
00413       return v.tag();
00414     }
00415 
00416     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00417               class Letter, class Tag, class GeometryCoords, class I>
00418     const Tag& op_tag(const AutomataBase<I>&,
00419                       const Graph<Kind, WordValue, WeightValue,
00420                       SerieValue ,Letter, Tag, GeometryCoords>& v)
00421     {
00422       return v.tag();
00423     }
00424 
00425 
00426     /*-----------.
00427     | Geometry.  |
00428     `-----------*/
00429 
00430     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00431               class Letter, class Tag, class GeometryCoords, class I>
00432     typename GClass::geometry_t&
00433     op_geometry(const AutomataBase<I>&,
00434                 Graph<Kind, WordValue, WeightValue,
00435                 SeriesValue, Letter, Tag, GeometryCoords>& v)
00436     {
00437       return v.geometry();
00438     }
00439 
00440     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00441               class Letter, class Tag, class GeometryCoords, class I>
00442     const typename GClass::geometry_t&
00443     op_geometry(const AutomataBase<I>&,
00444                 const Graph<Kind, WordValue, WeightValue,
00445                 SeriesValue, Letter, Tag, GeometryCoords>& v)
00446     {
00447       return v.geometry();
00448     }
00449 
00450 
00451     TParam
00452     const typename GClass::geometry_t&
00453     GClass::geometry() const
00454     {
00455       return geometry_;
00456     }
00457 
00458     TParam
00459     typename GClass::geometry_t&
00460     GClass::geometry()
00461     {
00462       return geometry_;
00463     }
00464 
00465 
00466     // Remove macros to avoid name clashes.
00467 # undef TParam
00468 # undef GClass
00469   }
00470 }
00471 
00472 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX