00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_COMPLETE_HXX
00018 # define VCSN_ALGORITHMS_COMPLETE_HXX
00019
00020 # include <vaucanson/algorithms/complete.hh>
00021 # include <vaucanson/algorithms/realtime.hh>
00022
00023 # include <vaucanson/automata/concept/automata_base.hh>
00024 # include <vaucanson/misc/usual_macros.hh>
00025
00026 # include <list>
00027 # include <set>
00028
00029 namespace vcsn {
00030
00031
00032
00033
00034
00035 template <typename A, typename T>
00036 void
00037 complete_here(Element<A, T>& work)
00038 {
00039 precondition(is_realtime(work));
00040 TIMER_SCOPED("complete");
00041 typedef Element<A, T> automaton_t;
00042 AUTOMATON_TYPES(automaton_t);
00043 AUTOMATON_FREEMONOID_TYPES(automaton_t);
00044 hstate_t sink_state;
00045 bool sink_added = false;
00046 std::list<hstate_t> dst;
00047
00048 for_all_states(s, work)
00049 for_all_letters(l, work.structure().series().monoid().alphabet())
00050 {
00051 dst.clear();
00052 work.letter_deltac(dst, *s, *l, delta_kind::states());
00053 if (dst.size() == 0)
00054 {
00055 if (not sink_added)
00056 {
00057 sink_state = work.add_state();
00058 sink_added = true;
00059 }
00060 work.add_letter_transition(*s, sink_state, *l);
00061 }
00062 }
00063
00064 if (sink_added)
00065 for_all_letters(l, work.structure().series().monoid().alphabet())
00066 work.add_letter_transition(sink_state, sink_state, *l);
00067 }
00068
00069
00070
00071
00072
00073 template <typename A, typename T>
00074 Element<A, T>
00075 complete(const Element<A, T>& e)
00076 {
00077 Element<A, T> res(e);
00078 complete_here(res);
00079 return res;
00080 }
00081
00082
00083
00084
00085
00086 template <class A, class T>
00087 bool
00088 is_complete(const Element<A, T>& e)
00089 {
00090 precondition(is_realtime(e));
00091 TIMER_SCOPED("is_complete");
00092 typedef Element<A, T> automaton_t;
00093 AUTOMATON_TYPES(automaton_t);
00094 AUTOMATON_FREEMONOID_TYPES(automaton_t);
00095 const alphabet_t& alpha = e.structure().series().monoid().alphabet();
00096 for_all_states(i, e)
00097 {
00098 std::set<hstate_t> dst;
00099 for_all_letters(j, alpha)
00100 {
00101 dst.clear();
00102 e.letter_deltac(dst, *i, *j, delta_kind::states());
00103
00104 if (dst.size() == 0)
00105 return false;
00106 }
00107 }
00108 return true;
00109 }
00110
00111 }
00112
00113 #endif // ! VCSN_ALGORITHMS_COMPLETE_HXX