Vaucanson  1.4.1
str_words.hxx
1 // str_words.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 The Vaucanson
6 // Group.
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12 //
13 // The complete GNU General Public Licence Notice can be found as the
14 // `COPYING' file in the root directory.
15 //
16 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
17 //
18 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_MONOID_STR_WORDS_HXX
19 # define VCSN_ALGEBRA_IMPLEMENTATION_MONOID_STR_WORDS_HXX
20 
21 # include <vaucanson/algebra/implementation/monoid/str_words.hh>
22 
23 # include <vaucanson/misc/char_traits.hh>
24 
25 namespace vcsn {
26 
27  namespace algebra {
28 
29  template <typename A>
30  std::pair<bool, int>
31  op_parse(const FreeMonoid<A>& s,
32  std::basic_string<typename A::letter_t>& v,
33  const std::string& in)
34  {
35  if (in.empty())
36  return std::make_pair(true, 0);
37 
38  std::string& empty = s.representation()->empty;
39  int empty_size = empty.size();
40  std::string& concat = s.representation()->concat;
41  int concat_size = concat.size();
42  bool last_token_is_letter = false;
43 
44  size_t i;
45  for (i = 0; i < in.size();)
46  {
47  // Is this a concatenation symbol?
48  if ((concat_size > 0) && !in.compare(i, concat_size, concat))
49  {
50  if (!last_token_is_letter)
51  return std::make_pair(false, i);
52  i += concat_size;
53  last_token_is_letter = false;
54  continue;
55  }
56 
59  // if (last_token_is_letter && concat_size > 0)
60  // return std::make_pair(false, i);
61 
62  // Is this the empty word?
63  if (!in.compare(i, empty_size, empty))
64  {
65  i += empty_size;
66  last_token_is_letter = true;
67  continue;
68  }
69 
70  // Finally try to read a real letter.
71  // Note that op_parse will update i.
72  std::pair<bool, typename A::letter_t> letter =
73  op_parse(s.alphabet().structure(), s.alphabet().value(), in, i);
74  if (!letter.first)
75  return std::make_pair(false, i);
76  v.push_back(letter.second);
77  last_token_is_letter = true;
78  }
79  return std::make_pair(last_token_is_letter, i);
80  }
81 
82  template<typename A>
83  void
84  op_in_mul(const algebra::FreeMonoid<A>&,
85  std::basic_string<typename A::letter_t>& dst,
86  const std::basic_string<typename A::letter_t>& src)
87  {
88  dst += src;
89  }
90 
91  template<typename A>
92  std::basic_string<typename A::letter_t>
93  op_mul(const algebra::FreeMonoid<A>&,
94  const std::basic_string<typename A::letter_t>& a,
95  const std::basic_string<typename A::letter_t>& b)
96  {
97  return a + b;
98  }
99 
100  template<typename A, typename St, typename U, typename V>
101  St&
102  op_rout(const FreeMonoid<A>& s,
103  St& st,
104  const std::basic_string<typename A::letter_t, U, V>& v)
105  {
106  if (v.empty())
107  st << s.representation()->empty;
108  else
109  {
110  // Type helpers.
111  typedef typename A::letter_t letter_t;
112  typedef algebra::letter_traits<letter_t> letter_traits_t;
113  typedef typename std::basic_string<letter_t, U, V>::const_iterator
114  iter_t;
115 
116  iter_t i = v.begin();
117 
118  // Print the first letter.
119  st << letter_traits_t::letter_to_literal(*i);
120  ++i;
121 
122  // Print the following letters using the concat string.
123  while (i != v.end())
124  {
125  st << s.representation()->concat
126  << letter_traits_t::letter_to_literal(*i);
127  ++i;
128  }
129  }
130 
131  return st;
132  }
133 
134  template <typename A>
135  bool
136  op_xeq(const algebra::FreeMonoid<A>& s,
137  const std::basic_string<typename A::letter_t>& a,
138  const std::basic_string<typename A::letter_t>& b)
139  {
140  typename std::basic_string<typename A::letter_t>::const_iterator
141  m = b.begin();
142  typename std::basic_string<typename A::letter_t>::const_iterator l;
143  for (l = a.begin(); m != b.end() && l != a.end(); ++l)
144  {
145  if (! s.alphabet().letter_equality(*l, *m))
146  return false;
147  ++m;
148  }
149  return (m == b.end() && l == a.end());
150  }
151 
152  template<typename A>
153  const std::basic_string<typename A::letter_t>&
154  identity_value(SELECTOR(algebra::FreeMonoid<A>),
155  SELECTOR(std::basic_string<typename A::letter_t>))
156  {
157  static const std::basic_string<typename A::letter_t> instance;
158  return instance;
159  }
160 
161  template<typename A>
162  const std::basic_string<typename A::letter_t,
163  misc::char_traits<typename A::letter_t> >&
164  identity_value(SELECTOR(algebra::FreeMonoid<A>),
165  SELECTOR2(std::basic_string<typename A::letter_t,
166  misc::char_traits<typename A::letter_t> >))
167  {
168  static const std::basic_string<typename A::letter_t,
169  misc::char_traits<typename A::letter_t> > instance;
170  return instance;
171  }
172 
173  template<typename A>
174  std::basic_string<typename A::letter_t>
175  op_convert(SELECTOR(algebra::FreeMonoid<A>),
176  SELECTOR(std::basic_string<typename A::letter_t>),
177  const typename A::letter_t& c)
178  {
179  std::basic_string<typename A::letter_t> str;
180  str = c;
181  return str;
182  }
183 
184  template<typename A, typename B, typename C, typename D>
185  bool
186  op_is_atom(const algebra::FreeMonoid<A>&,
187  const std::basic_string<B, C, D>& v)
188  {
189  return v.size() <= 1;
190  }
191 
192 
193  template <class A>
194  Element<algebra::FreeMonoid<A>, std::basic_string<typename A::letter_t> >
195  op_choose(const algebra::FreeMonoid<A>& s,
196  SELECTOR(std::basic_string<typename A::letter_t>))
197  {
198  unsigned length =
199  misc::random::generate<unsigned>(0, op_choose_max_word_length);
200  std::basic_string<typename A::letter_t> r;
201  for (unsigned i = 0; i < length; ++i)
202  r = r + s.alphabet().choose();
203  return Element<algebra::FreeMonoid<A>,
204  std::basic_string<typename A::letter_t> >(s, r);
205  }
206 
207 # define WORD_TRAITS \
208  word_traits<FreeMonoid<A>, std::basic_string<typename A::letter_t> >
209 
210  template <typename A>
211  inline typename WORD_TRAITS::first_projection_value_t
212  WORD_TRAITS::first_projection(const WORD_TRAITS::word_value_t& str)
213  {
214  // We can not project if the type does not support it.
215  static_assertion_(not (misc::static_eq<first_projection_t,
216  undefined_type>::value), need_first_projection);
217 
218  first_projection_value_t R;
219 
220  // We assume we can access the first projection with "first".
221  for_all_const_(word_value_t, i, str)
222  R += (*i).first;
223 
224  return R;
225  }
226 
227  template <typename A>
228  inline typename WORD_TRAITS::first_projection_t
229  WORD_TRAITS::first_projection(const WORD_TRAITS::first_monoid_t& mon,
230  const WORD_TRAITS::word_t& word)
231  {
232  // We can not project if the type does not support it.
233  static_assertion_(not (misc::static_eq<first_projection_t,
234  undefined_type>::value), need_first_projection);
235 
236  first_projection_t R(mon);
237 
238  R.value() = first_projection(word.value());
239 
240  return R;
241  }
242 
243  template <typename A>
244  inline typename WORD_TRAITS::second_projection_value_t
245  WORD_TRAITS::second_projection(const WORD_TRAITS::word_value_t& str)
246  {
247  // We can not project if the type does not support it.
248  static_assertion_(not (misc::static_eq<second_projection_t,
249  undefined_type>::value), need_second_projection);
250 
251  second_projection_value_t R;
252 
253  // We assume we can access the second projection with "second".
254  for_all_const_(word_value_t, i, str)
255  R += (*i).second;
256 
257  return R;
258  }
259 
260  template <typename A>
261  inline typename WORD_TRAITS::second_projection_t
262  WORD_TRAITS::second_projection(const WORD_TRAITS::second_monoid_t& mon,
263  const WORD_TRAITS::word_t& word)
264  {
265  // We can not project if the type does not support it.
266  static_assertion_(not (misc::static_eq<second_projection_t,
267  undefined_type>::value), need_second_projection);
268 
269  second_projection_t R(mon);
270 
271  R.value() = second_projection(word.value());
272 
273  return R;
274  }
275 
276 # undef WORD_TRAITS
277 
278  } // ! algebra
279 
280 } // ! vcsn
281 
282 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_MONOID_STR_WORDS_HXX
Generated on Sat Jul 14 2012 18:46:41 for Vaucanson by   doxygen 1.8.1.1