Vaucanson  1.4.1
implementation/semiring/cyclic_semiring.hxx
1 // tropical_semiring.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, 2011 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_CYCLIC_SEMIRING_HXX
18 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_CYCLIC_SEMIRING_HXX
19 # include <vaucanson/config/system.hh>
20 # include <vaucanson/algebra/implementation/semiring/cyclic_semiring.hh>
21 # include <vaucanson/misc/random.hh>
22 # include <vaucanson/misc/limits.hh>
23 # include <boost/swap.hpp>
24 # include <boost/tuple/tuple.hpp>
25 
26 namespace vcsn {
27 
28  namespace algebra {
29 
39  inline
40  boost::tuple<unsigned int, int, int>
41  ext_gcd (unsigned int a, unsigned int b)
42  {
43  unsigned int q, r;
44  int x1 = 0;
45  int x2 = 1;
46  int y1 = 1;
47  int y2 = 0;
48  int x, y;
49 
50  if (a < b)
51  {
52  boost::swap (a, b);
53  boost::swap (x1, x2);
54  boost::swap (y1, y2);
55  }
56 
57  if (b == 0)
58  return boost::tuple<unsigned int, int, int> (a, 1, 0);
59 
60  while (b > 0)
61  {
62  q = a / b;
63  r = a - q * b;
64  x = x2 - q * x1;
65  y = y2 - q * y1;
66  a = b;
67  b = r;
68  x2 = x1;
69  x1 = x;
70  y2 = y1;
71  y1 = y;
72  }
73 
74  return boost::tuple<unsigned int, int, int> (a, x2, y2);
75  }
76 
77  /*---------------.
78  | Identity value |
79  `---------------*/
80 
81  template<unsigned int n, typename T>
82  T identity_value(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
83  {
84  return T(1);
85  }
86 
87  template<unsigned int n, typename T>
88  bool show_identity_value(SELECTOR(algebra::CyclicSemiring<n>),
89  SELECTOR(T))
90  {
91  return false;
92  }
93 
94  template<unsigned int n, typename T>
95  bool
96  is_positive_semiring(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
97  {
98  return false;
99  }
100 
101  template<unsigned int n, typename T>
102  T zero_value(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
103  {
104  return T(0);
105  }
106 
107  /*------------.
108  | op_contains |
109  `------------*/
110  template<unsigned int n, typename T>
111  bool op_contains(const algebra::CyclicSemiring<n>&, T c)
112  {
113  return true;
114  }
115 
116  /*---------------.
117  | Multiplication |
118  `---------------*/
119  template<unsigned int n, typename T, typename U>
120  void op_in_mul(const algebra::CyclicSemiring<n>&,
121  T& dst, U arg)
122  {
123  dst = (dst * arg) % n;
124  dst = (dst < 0) ? dst + n : dst;
125  }
126 
127  template<unsigned int n, typename T, typename U>
128  T op_mul(const algebra::CyclicSemiring<n>&, T a, U b)
129  {
130  T res = (a * b) % n;
131  return ((res < 0) ? res + n : res);
132  }
133 
134  /*-----------------------.
135  | Mutiplication for Z/2Z |
136  `-----------------------*/
137 
138  inline
139  void op_in_mul(const algebra::CyclicSemiring<2>&,
140  bool& dst, bool arg)
141  {
142  dst = dst && arg;
143  }
144 
145  inline
146  bool op_mul(const algebra::CyclicSemiring<2>&, bool a, bool b)
147  {
148  return (a && b);
149  }
150 
151  /*---------.
152  | Addition |
153  `---------*/
154  template<unsigned int n, typename T, typename U>
155  void op_in_add(const algebra::CyclicSemiring<n>&,
156  T& dst, U arg)
157  {
158  dst = ((dst + arg) + (2 * n)) % n;
159  }
160 
161  template<unsigned int n, typename T, typename U>
162  T op_add(const algebra::CyclicSemiring<n>&, T a, U b)
163  {
164  return ((a + b) + (2 * n)) % n;
165  }
166 
167  /*------------------.
168  | Addition for Z/2Z |
169  `------------------*/
170 
171  inline
172  void op_in_add(const algebra::CyclicSemiring<2>&,
173  bool& dst, bool arg)
174  {
175  dst = dst ^ arg;
176  }
177 
178  inline
179  bool op_add(const algebra::CyclicSemiring<2>&, bool a, bool b)
180  {
181  return a ^ b;
182  }
183 
184  /*---------.
185  | Division |
186  `---------*/
187 
188  template<unsigned int n, typename T, typename U>
189  void op_in_div (const algebra::CyclicSemiring<n>& s1,
190  T& dst, U arg)
191  {
192  boost::tuple<unsigned int , int, int> res = ext_gcd (dst, arg);
193  if (res.get<0> () == 1)
194  {
195  op_in_mul (s1, dst, res.get<2> ());
196  return;
197  }
198 
199  assertion(! "tried to divide by a number"
200  " without multiplicative inverse.");
201  }
202 
203  template<unsigned int n, typename T, typename U>
204  T op_div (const algebra::CyclicSemiring<n>& s, T a, U b)
205  {
206  boost::tuple<unsigned int , int, int> res = ext_gcd (a, b);
207  if (res.get<0> () == 1)
208  return (op_mul (s, a, res.get<2> ()));
209 
210  assertion(! "tried to divide by a number"
211  " without multiplicative inverse.");
212  }
213 
214  /*------------------.
215  | Division for Z/2Z |
216  `------------------*/
217 
218  inline
219  void op_in_div (const algebra::CyclicSemiring<2>& s1,
220  bool& dst, bool arg)
221  {
222  if (arg == 1)
223  return;
224  assertion (! "Division by zero.");
225  }
226 
227  inline
228  bool op_div (const algebra::CyclicSemiring<2>& s, bool a, bool b)
229  {
230  if (b == 1)
231  return (a);
232  assertion(! "Division by zero.");
233  }
234 
235  /*-------------.
236  | Substraction |
237  `-------------*/
238 
239  template<unsigned int n, typename T, typename U>
240  void op_in_sub(const algebra::CyclicSemiring<n>& s1,
241  T& dst, U arg)
242  {
243  dst = (dst - arg) % n;
244  dst = (dst < 0) ? dst + n : dst;
245  }
246 
247  template<unsigned int n, typename T, typename U>
248  T op_sub(const algebra::CyclicSemiring<n>& s,
249  T a, U b)
250  {
251  T res = (a - b) % n;
252  return ((res < 0) ? res + n : res);
253  }
254 
255  /*----------------------.
256  | Substraction for Z/2Z |
257  `----------------------*/
258 
259  inline
260  void op_in_sub(const algebra::CyclicSemiring<2>& s1,
261  bool& dst, bool arg)
262  {
263  dst = dst ^ arg;
264  }
265 
266  inline
267  bool op_sub(const algebra::CyclicSemiring<2>& s,
268  bool a, bool b)
269  {
270  return (a ^ b);
271  }
272 
273  /*-----.
274  | Star |
275  `-----*/
276 
277  template <unsigned int n, typename T>
278  bool
279  op_starable(const algebra::CyclicSemiring<n>&, T b)
280  {
281  if (b == T(0))
282  return true;
283  return false;
284  }
285 
286  template <unsigned int n, class T>
287  void
288  op_in_star(const algebra::CyclicSemiring<n>&, T& b)
289  {
290  if (b == T(0))
291  {
292  b = T(1);
293  return;
294  }
295  assertion(! "star not defined.");
296  }
297 
298  template <unsigned int n, class T>
299  Element<algebra::CyclicSemiring<n>, T>
300  op_choose(const algebra::CyclicSemiring<n>& set, SELECTOR(T))
301  {
302  return Element<algebra::CyclicSemiring<n>, T>
303  (set, misc::random::generate<T>());
304  }
305 
306  template <unsigned int n, typename T>
307  bool
308  op_can_choose_non_starable(const algebra::CyclicSemiring<n>&,
309  SELECTOR(T))
310  {
311  return true;
312  }
313 
314  template <unsigned int n, class T>
315  Element<algebra::CyclicSemiring<n>, T>
316  op_choose_starable(const algebra::CyclicSemiring<n>& set,
317  SELECTOR(T))
318  {
319  T r;
320  do
321  r = op_choose(set, SELECT(T));
322  while (!op_starable(set, r));
323  return r;
324  }
325 
326  template <unsigned int n, class T>
327  Element<algebra::CyclicSemiring<n>, T>
328  op_choose_non_starable(const algebra::CyclicSemiring<n>& set,
329  SELECTOR(T))
330  {
331  T r;
332  do
333  r = op_choose(set, SELECT(T));
334  while (op_starable(set, r));
335  return r;
336  }
337 
338  /*---------------.
339  | Pretty printer |
340  `---------------*/
341  template<unsigned int n, typename St, typename T>
342  St& op_rout(const algebra::CyclicSemiring<n>&, St& st, const T& v)
343  {
344  st << v;
345  return st;
346  }
347 
348  } // algebra
349 
350 } // vcsn
351 
352 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_CYCLIC_SEMIRING_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1