trim.hxx

00001 // trim.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_TRIM_HXX
00018 # define VCSN_ALGORITHMS_TRIM_HXX
00019 
00020 # include <vaucanson/algorithms/trim.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 
00024 # include <vaucanson/algorithms/sub_automaton.hh>
00025 # include <vaucanson/algorithms/accessible.hh>
00026 
00027 # include <algorithm>
00028 
00029 namespace vcsn {
00030 
00031   /*---------------------.
00032   | do_start_trim_states |
00033   `---------------------*/
00034   // preconditions :
00035   //
00036   //
00037   template <class A_, typename Auto_>
00038   std::set<hstate_t>
00039   do_useful_states(const AutomataBase<A_>&,
00040                    const Auto_&            a)
00041   {
00042     TIMER_SCOPED("useful_states");
00043     std::set<hstate_t> start = accessible_states(a);
00044     std::set<hstate_t> final = coaccessible_states(a);
00045     std::set<hstate_t> result;
00046     std::insert_iterator<std::set<hstate_t> > i(result, result.begin());
00047 
00048     set_intersection(start.begin(), start.end(), final.begin(), final.end(), i);
00049     return result;
00050   }
00051 
00052   template<typename A, typename T>
00053   std::set<hstate_t>
00054   useful_states(const Element<A, T>& a)
00055   {
00056     return do_useful_states(a.structure(), a);
00057   }
00058 
00059   template<typename A, typename T>
00060   Element<A, T>
00061   trim(const Element<A, T>& a)
00062   {
00063     return sub_automaton(a, useful_states(a));
00064   }
00065 
00066   template<typename A, typename T>
00067   void
00068   trim_here(Element<A, T>& a)
00069   {
00070     sub_automaton_here(a, useful_states(a));
00071   }
00072 
00073 } // vcsn
00074 
00075 #endif // ! VCSN_ALGORITHMS_TRIM_HXX

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