skeleton.hxx

00001 // skeleton.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 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_INTERNAL_SKELETON_HXX
00018 # define VCSN_ALGORITHMS_INTERNAL_SKELETON_HXX
00019 
00020 # include <vaucanson/algorithms/internal/skeleton.hh>
00021 
00022 namespace vcsn
00023 {
00024 
00025   /*------------------------.
00026   | Skeleton Implementation |
00027   `------------------------*/
00028 
00029   template<typename A, typename T>
00030   Skeleton<A, T>::Skeleton(const Element<A, T>& x) : a(x)
00031   {
00032 
00033     typedef Element<A, T> automaton_t;
00034 
00035     AUTOMATON_TYPES(automaton_t);
00036 
00037     int i, j;
00038     std::set<htransition_t> out;
00039     std::map<series_set_elt_t, int> Lmap;
00040     std::map<hstate_t, int> Smap;
00041 
00042     states.reserve(a.states().size());
00043     transitions.reserve(a.transitions().size());
00044     origins_transitions.reserve(a.transitions().size());
00045     aims_transitions.reserve(a.transitions().size());
00046     transitions_labels.reserve(a.transitions().size());
00047 
00048     // *** FIXME ***
00049     // HOW TO INITIALIZE A VECTOR OF LISTS?
00050     std::list<int> dummy;
00051     delta_in.assign(a.states().size(), dummy);
00052     delta_out.assign(a.states().size(), dummy);
00053 
00054 
00055     // Gives each state a number. Constructs lists I and T of initial
00056     // and final states
00057     // Time complexity: O(n log n)
00058     i = 0;
00059     for_all_states(q, a)
00060     {
00061       states.push_back(*q);
00062       Smap[*q] = i++;
00063 
00064       if (a.is_initial(*q))
00065         I.push_front(i - 1);
00066       else
00067         if (a.is_final(*q))
00068           F.push_front(i - 1);
00069     }
00070 
00071     // Gives each transition an index (transition[i] = transition whose index is i)
00072     // Gives each label an index in map Lmap
00073     // Gives each transition the index of its label (transitions_labels[i] = index
00074     // of label of transition i)
00075     // (time complexity: O(m log s + m log n))
00076     // Constructs vectors src_of and dst_of
00077 
00078     // Index of the labels
00079     i = 0;
00080     // Index of the transitions
00081     j = 0;
00082     for_all_transitions(e, a)
00083     {
00084       transitions.push_back(*e);
00085       origins_transitions.push_back(Smap[a.src_of(*e)]);
00086       aims_transitions.push_back(Smap[a.dst_of(*e)]);
00087 
00088       if (Lmap.find(a.series_of(*e)) == Lmap.end())
00089         transitions_labels.push_back(Lmap[a.series_of(*e)] = i++);
00090       else
00091         transitions_labels.push_back(Lmap[a.series_of(*e)]);
00092     }
00093 
00094     // Here, i = number of different labels
00095 
00096     /*** FIXME ***/
00097     // The following piece of code is intended to visit each entry of
00098     // map Lmap and put each label in its place in vector
00099     // labels, but it doesn't compile. The problem is then solved by
00100     // visiting all the transitions of the automaton, what can produce
00101     // several visits to the same label.
00102     //
00103     //    for (std::map<label_t, int>::iterator itr = Lmap.begin();
00104     //         itr != Lmap.end(); itr++)
00105     //      labels[itr->second] = itr->first;
00106     // *** REMARK: vector labels is obsolete
00107 
00108 
00109     // Construct the list of transitions for each label (transitions_lex indexed
00110     // by labels, transitions_lex[i] = list of transitions with label i)
00111 
00112     std::vector< std::list<int> > transitions_lex(i);
00113 
00114     for (i = 0; i < static_cast<int>(a.transitions().size()); i++)
00115       transitions_lex[transitions_labels[i]].push_front(i);
00116 
00117     // By using vector transitions_lex, defines ingoing and outgoing transitions
00118     // of each state in lexicographic order
00119     for (i = 0; i < static_cast<int>(transitions_lex.capacity()); i++)
00120       for (std::list<int>::iterator it = transitions_lex[i].begin();
00121            it != transitions_lex[i].end(); it++)
00122       {
00123         delta_in[aims_transitions[*it]].push_back(*it);
00124         delta_out[origins_transitions[*it]].push_back(*it);
00125       }
00126 
00127   }
00128 
00129   template<typename A, typename T>
00130   void Skeleton<A, T>::reserve_aux_states_int()
00131   {
00132     aux_states_int.reserve(a.states().size());
00133   }
00134 
00135   template<typename A, typename T>
00136   void Skeleton<A, T>::reserve_aux_states_bool()
00137   {
00138     aux_states_bool.reserve(a.states().size());
00139   }
00140 
00141   template<typename A, typename T>
00142   void Skeleton<A, T>::reserve_aux_states_generic()
00143   {
00144     aux_states_generic.reserve(a.states().size());
00145   }
00146 
00147   template<typename A, typename T>
00148   void Skeleton<A, T>::reserve_aux_transitions_int()
00149   {
00150     aux_transitions_int.reserve(a.transitions().size());
00151   }
00152 
00153   template<typename A, typename T>
00154   void Skeleton<A, T>::reserve_aux_transitions_bool()
00155   {
00156     aux_transitions_bool.reserve(a.transitions().size());
00157   }
00158 
00159   template<typename A, typename T>
00160   void Skeleton<A, T>::reserve_aux_transitions_generic()
00161   {
00162     aux_transitions_generic.reserve(a.transitions().size());
00163   }
00164 
00165 } // vcsn
00166 
00167 #endif // ! VCSN_ALGORITHMS_INTERNAL_SKELETON_HXX

Generated on Sat Jul 29 17:13:11 2006 for Vaucanson by  doxygen 1.4.6