fmp_transducer_maker.thxx 7.16 KB
Newer Older
Michaël Cadilhac's avatar
Michaël Cadilhac committed
1
//							-*- C++ -*-
2
// fmp_transducer_maker.thxx: this file is part of the Vaucanson project.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
3
//
4
// Vaucanson, a generic library for finite state machines.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
5
//
6
// Copyright (C) 2005, 2006, 2008 The Vaucanson Group.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
7
//
8
9
10
11
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
12
//
13
// The complete GNU General Public Licence Notice can be found as the
14
// `COPYING' file in the root directory.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
15
//
16
// The Vaucanson Group consists of people listed in the `AUTHORS' file.
17
//
Michaël Cadilhac's avatar
Michaël Cadilhac committed
18

19
/*
Akim Demaille's avatar
Akim Demaille committed
20
 * CPP guard should not be inserted here as
Michaël Cadilhac's avatar
Michaël Cadilhac committed
21
22
23
24
 * VCSN_CONTEXT_NAMESPACE could be changed.
 */

#include <vaucanson/algorithms/minimization_hopcroft.hh>
25
#include <vaucanson/algorithms/evaluation_fmp.hh>
Michaël Cadilhac's avatar
Michaël Cadilhac committed
26
27
28
#include <vaucanson/algorithms/aut_to_exp.hh>
#include <vaucanson/algorithms/trim.hh>
#include <vaucanson/algorithms/realtime.hh>
29

30
31
namespace vcsn
{
32
  namespace VCSN_GRAPH_IMPL
33
  {
34
    VCSN_CONTEXT_NAMESPACE
35
    {
36

37
38
      template <class FirstInputIterator, class SecondInputIterator>
      automata_set_t make_automata_set(const FirstInputIterator first_begin,
39
40
41
				       const FirstInputIterator first_end,
				       const SecondInputIterator second_begin,
				       const SecondInputIterator second_end)
42
      {
43
44
	first_alphabet_t first_alpha;

45
46
47
	for (FirstInputIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

48
49
	second_alphabet_t second_alpha;

50
51
52
	for (SecondInputIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
	semiring_t	semiring;
	first_monoid_t	mA(first_alpha);
	second_monoid_t	mB(second_alpha);
	monoid_t	freemonoidproduct(mA, mB);
	series_set_t	series(semiring, freemonoidproduct);

	return automata_set_t(series);
      }

      template <class FirstInputIterator, class SecondInputIterator>
      automata_set_t make_automata_set(const FirstInputIterator first_begin,
				       const FirstInputIterator first_end,
				       const SecondInputIterator second_begin,
				       const SecondInputIterator second_end,
				       const monoid_rep_t& mrep,
				       const first_monoid_rep_t& mrep1,
				       const second_monoid_rep_t& mrep2,
				       const series_rep_t& srep,
				       const first_series_rep_t& srep1,
				       const second_series_rep_t& srep2)
      {
	first_alphabet_t first_alpha;

	for (FirstInputIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t second_alpha;

	for (SecondInputIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	semiring_t	semiring;
	first_monoid_t	mA(first_alpha, mrep1);
	second_monoid_t	mB(second_alpha, mrep2);
	monoid_t	freemonoidproduct(mA, mB, mrep);
88
	// FIXME: srep1 and srep2 cannot be used.
89
	series_set_t	series(semiring, freemonoidproduct, srep);
90
91

	return automata_set_t(series);
92
93
      }

94
95
96
97
98
99
100
101
102
      template <class FirstInputIterator, class SecondInputIterator>
      automaton_t make_automaton(const FirstInputIterator first_begin,
				 const FirstInputIterator first_end,
				 const SecondInputIterator second_begin,
				 const SecondInputIterator second_end)
      {
	return automaton_t(make_automata_set(first_begin, first_end,
					     second_begin, second_end));
      }
103
104
105

      template <class FirstInputIterator, class SecondInputIterator>
      automaton_t make_automaton(const FirstInputIterator first_begin,
106
107
108
109
110
111
112
113
114
				 const FirstInputIterator first_end,
				 const SecondInputIterator second_begin,
				 const SecondInputIterator second_end,
				 const monoid_rep_t& mrep,
				 const first_monoid_rep_t& mrep1,
				 const second_monoid_rep_t& mrep2,
				 const series_rep_t& srep,
				 const first_series_rep_t& srep1,
				 const second_series_rep_t& srep2)
115
      {
116
117
118
119
120
121
122
123
124
125
126
127
	return automaton_t(make_automata_set(first_begin, first_end,
					     second_begin, second_end,
					     mrep, mrep1, mrep2,
					     srep, srep1, srep2));
      }

      template <class T1, class T2>
      automaton_t make_automaton(const T1& first_alphabet,
				 const T2& second_alphabet)
      {
	return make_automaton(first_alphabet.begin(), first_alphabet.end(),
			      second_alphabet.begin(), second_alphabet.end());
128
129
130
131
      }

      template <class T1, class T2>
      automaton_t make_automaton(const T1& first_alphabet,
132
133
134
135
136
137
138
				 const T2& second_alphabet,
				 const monoid_rep_t& mrep,
				 const first_monoid_rep_t& mrep1,
				 const second_monoid_rep_t& mrep2,
				 const series_rep_t& srep,
				 const first_series_rep_t& srep1,
				 const second_series_rep_t& srep2)
139
140
      {
	return make_automaton(first_alphabet.begin(), first_alphabet.end(),
141
142
			      second_alphabet.begin(), second_alphabet.end(),
			      mrep, mrep1, mrep2, srep, srep1, srep2);
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
      }

      template <class FirstIterator, class SecondIterator>
      monoid_elt_t make_couple(const FirstIterator first_begin,
			       const FirstIterator first_end,
			       const SecondIterator second_begin,
			       const SecondIterator second_end,
			       const std::string& first_exp,
			       const std::string& second_exp)
      {
	first_alphabet_t	first_alpha;
	for (FirstIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t	second_alpha;
	for (SecondIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	monoid_t		fmp (first_alpha, second_alpha);
	monoid_elt_value_t	fmp_elt_value (first_exp, second_exp);

	return Element<monoid_t, monoid_elt_value_t> (fmp, fmp_elt_value);
      }

      template <class T1, class T2>
      monoid_elt_t make_couple(const T1& first_alphabet,
			       const T2& second_alphabet,
			       const std::string& first_exp,
			       const std::string& second_exp)
      {
	return make_couple(first_alphabet.begin(), first_alphabet.end(),
			   second_alphabet.begin(), second_alphabet.end(),
			   first_exp, second_exp);
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename SeriesStruct,
	        typename SeriesImpl,
	        typename S,
	        typename T>
      AUTOMATON_CONTEXT::rat_exp_t
      do_evaluation(const vcsn::AutomataBase<TransStruct>&,
		    const TransImpl&,
		    const SeriesStruct&,
		    const vcsn::rat::exp<S, T>& input,
		    const Element<TransStruct, TransImpl>& t,
		    const Element<SeriesStruct, SeriesImpl>&)
      {
	AUTOMATON_CONTEXT::automaton_t w = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().first_monoid().alphabet());
	AUTOMATON_CONTEXT::automaton_t result = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().second_monoid().alphabet());
	standard_of(w, input);
	evaluation_fmp(t, quotient(w), result);

	return aut_to_exp(generalized(quotient(realtime(trim(result)))),
	    DMChooser());
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename ArgStruct,
	        typename ArgImpl>
      AUTOMATON_CONTEXT::rat_exp_t
      evaluation(const Element<TransStruct, TransImpl>& t,
		 const Element<ArgStruct, ArgImpl>& input)
      {
	return do_evaluation(t.structure(), t.value(),
			     input.structure(), input.value(),
			     t, input);
      }


    } // End of VCSN_CONTEXT_NAMESPACE.
  } // End of VCSN_GRAPH_IMPL.
221
} // End of namespace vcsn.
222