complete.hxx

00001 // complete.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 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_ALGORITHMS_COMPLETE_HXX
00018 # define VCSN_ALGORITHMS_COMPLETE_HXX
00019 
00020 # include <vaucanson/algorithms/complete.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/misc/usual_macros.hh>
00024 
00025 # include <list>
00026 # include <set>
00027 
00028 namespace vcsn {
00029 
00030   /*--------------.
00031   | complete_here |
00032   `--------------*/
00033 
00034   template <typename A, typename T>
00035   void
00036   complete_here(Element<A, T>& work)
00037   {
00038     TIMER_SCOPED("complete");
00039     typedef Element<A, T> automaton_t;
00040     AUTOMATON_TYPES(automaton_t);
00041     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00042     hstate_t sink_state;
00043     bool sink_added = false;
00044     std::list<hstate_t> dst;
00045 
00046     for_all_states(s, work)
00047       for_all_letters(l, work.structure().series().monoid().alphabet())
00048       {
00049         dst.clear();
00050         work.letter_deltac(dst, *s, *l, delta_kind::states());
00051         if (dst.size() == 0)
00052         {
00053           if (not sink_added)
00054           {
00055             sink_state = work.add_state();
00056             sink_added = true;
00057           }
00058           work.add_letter_transition(*s, sink_state, *l);
00059         }
00060       }
00061 
00062     if (sink_added)
00063       for_all_letters(l, work.structure().series().monoid().alphabet())
00064         work.add_letter_transition(sink_state, sink_state, *l);
00065   }
00066 
00067   /*---------.
00068   | complete |
00069   `---------*/
00070 
00071   template <typename A, typename T>
00072   Element<A, T>
00073   complete(const Element<A, T>& e)
00074   {
00075     Element<A, T> res(e);
00076     complete_here(res);
00077     return res;
00078   }
00079 
00080   /*------------.
00081   | is_complete |
00082   `------------*/
00083 
00084   template <class A, class T>
00085   bool
00086   is_complete(const Element<A, T>& e)
00087   {
00088     TIMER_SCOPED("is_complete");
00089     typedef Element<A, T> automaton_t;
00090     AUTOMATON_TYPES(automaton_t);
00091     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00092     const alphabet_t& alpha = e.structure().series().monoid().alphabet();
00093     for_all_states(i, e)
00094     {
00095       std::set<hstate_t> dst;
00096       for_all_letters(j, alpha)
00097       {
00098         dst.clear();
00099         e.letter_deltac(dst, *i, *j, delta_kind::states());
00100 
00101         if (dst.size() == 0)
00102           return false;
00103       }
00104     }
00105     return true;
00106   }
00107 
00108 } // vcsn
00109 
00110 #endif // ! VCSN_ALGORITHMS_COMPLETE_HXX

Generated on Sun Jul 29 19:35:18 2007 for Vaucanson by  doxygen 1.5.2