DGtal  0.9.2
MPolynomialReader.h
1 
17 #pragma once
18 
31 #if defined(MPolynomialReader_RECURSES)
32 #error Recursive header files inclusion detected in MPolynomialReader.h
33 #else // defined(MPolynomialReader_RECURSES)
34 
35 #define MPolynomialReader_RECURSES
36 
37 #if !defined MPolynomialReader_h
38 
39 #define MPolynomialReader_h
40 
42 // Inclusions
43 #include <iostream>
44 #include "DGtal/base/Common.h"
45 #include "DGtal/math/MPolynomial.h"
46 #include <boost/spirit/include/qi.hpp>
47 #include <boost/spirit/include/phoenix_core.hpp>
48 #include <boost/spirit/include/phoenix_operator.hpp>
49 #include <boost/spirit/include/phoenix_fusion.hpp>
50 #include <boost/spirit/include/phoenix_stl.hpp>
51 #include <boost/fusion/include/adapt_struct.hpp>
52 #include <boost/variant/recursive_variant.hpp>
54 
55 namespace DGtal
56 {
57  namespace detail {
58 
63  struct power_node {
64  int k;
65  int e;
66  };
67 
72  struct monomial_node {
73  double coef;
74  std::vector<power_node> powers;
75  };
76 
77 
79  struct top_node;
80 
85  typedef
86  boost::variant< boost::recursive_wrapper<top_node>, monomial_node >
87  expr_node;
88 
93  struct top_node {
94  std::vector<char> ops;
95  std::vector<expr_node> expressions;
96  int exp;
97  };
98 
99  }
100 
101 }
102 
107 BOOST_FUSION_ADAPT_STRUCT(
109  (int, k)
110  (int, e)
111 )
112 
113 
117 BOOST_FUSION_ADAPT_STRUCT(
118  DGtal::detail::monomial_node,
119  (double, coef)
120  (std::vector<DGtal::detail::power_node>, powers)
121 )
122 
127 BOOST_FUSION_ADAPT_STRUCT(
128  DGtal::detail::top_node,
129  (std::vector<char>, ops)
130  (std::vector<DGtal::detail::expr_node>, expressions)
131  (int, exp)
132 )
133 
134 namespace DGtal
135 {
136  namespace qi = boost::spirit::qi;
137  namespace ascii = boost::spirit::ascii;
138  namespace phoenix = boost::phoenix;
139 
147  template <typename Iterator>
149  : qi::grammar<Iterator, detail::top_node(), ascii::space_type>
150  {
152  : MPolynomialGrammar::base_type(top)
153  {
154  using qi::eps;
155  using qi::lit;
156  using qi::int_;
157  using qi::_val;
158  using qi::_1;
159  using qi::double_;
160  using phoenix::at_c;
161  using phoenix::push_back;
162 
163  top = // An expression is an additive or subtractive expression
164  mulexpr [push_back(at_c<1>(_val), _1)]
165  >> *( ( lit('+') [ push_back(at_c<0>(_val), '+') ]
166  >> mulexpr [push_back(at_c<1>(_val), _1)] )
167  | ( ( lit('-') [ push_back(at_c<0>(_val), '-') ]
168  >> mulexpr [push_back(at_c<1>(_val), _1)] ) ) );
169 
170  mulexpr = // Each mul expression may be a product of sub-expressions
171  subexpr [push_back(at_c<1>(_val), _1)]
172  >> *( ( lit('*') [ push_back(at_c<0>(_val), '*') ]
173  >> mulexpr [push_back(at_c<1>(_val), _1)] ) );
174 
175  subexpr = // a sub-expression is a monomial or some ( ) or some ( )^k
176  monomial
177  | expexpr;
178 
179  expexpr = // ( expr ) or ( expr )^k
180  lit('(') [ push_back(at_c<0>(_val), '^') ]
181  >> top [ push_back(at_c<1>(_val), _1) ]
182  >> lit(')')
183  >> ( ( lit('^') >> int_ [ at_c<2>(_val) = _1 ] )
184  | eps [ at_c<2>(_val) = 1 ] ) ;
185 
186  monomial = // coef.power(s)*, or power(s)+
187  ( double_ [at_c<0>(_val) = _1]
188  >> *( genvariable [push_back(at_c<1>(_val), _1)] ) )
189  | +( genvariable [push_back(at_c<1>(_val), _1)]
190  >> eps [at_c<0>(_val) = 1] );
191 
192  genvariable = // may be some X_k^m or x^m, y^m ...
193  litvariable | variable;
194  variable = // X_0 X_1 ... X_0^4 X_1^2 X_3^0 ...
195  lit('X') >> lit('_')
196  >> int_ [at_c<0>(_val) = _1]
197  >> ( ( lit('^') >> int_ [at_c<1>(_val) = _1] ) // X_k^e
198  | eps [at_c<1>(_val) = 1] // X_k
199  );
200  litvariable = // x y z t x^4 y^5 z^2 ...
201  ( lit('x') [at_c<0>(_val) = 0]
202  | lit('y') [at_c<0>(_val) = 1]
203  | lit('z') [at_c<0>(_val) = 2]
204  | lit('t') [at_c<0>(_val) = 3] )
205  >> ( ( lit('^') >> int_ [at_c<1>(_val) = _1] ) // x^3 z^4
206  | eps [at_c<1>(_val) = 1] // x y z
207  );
208 
209  }
210 
211 
212  qi::rule<Iterator, detail::top_node(), ascii::space_type> top;
213  qi::rule<Iterator, detail::top_node(), ascii::space_type> mulexpr;
214  qi::rule<Iterator, detail::expr_node(), ascii::space_type> subexpr;
215  qi::rule<Iterator, detail::top_node(), ascii::space_type> expexpr;
216  qi::rule<Iterator, detail::monomial_node(), ascii::space_type> monomial;
217  qi::rule<Iterator, detail::power_node(), ascii::space_type> variable;
218  qi::rule<Iterator, detail::power_node(), ascii::space_type> genvariable;
219  qi::rule<Iterator, detail::power_node(), ascii::space_type> litvariable;
220 
221  };
222 }
223 
224 
225 namespace DGtal
226 {
228  // template class MPolynomialReader
255  template <int n, typename TRing,
256  typename TAlloc = std::allocator<TRing>,
257  typename TIterator = std::string::const_iterator>
259  {
260  public:
261  typedef TRing Ring;
262  typedef TIterator Iterator;
263  typedef TAlloc Alloc;
266 
268  Grammar gpolynomial;
269 
274 
284  Iterator read( Polynomial & p, Iterator begin, Iterator end )
285  {
286  using qi::phrase_parse;
287  using ascii::space;
289  bool r = phrase_parse( begin, end, gpolynomial, space, m );
290  if (r) p = make( m );
291  return r ? begin : end;
292  }
293 
294 
295 
296  // ----------------------- Interface --------------------------------------
297  public:
298 
303  void selfDisplay ( std::ostream & out ) const;
304 
309  bool isValid() const;
310 
311 
312 
313  // ------------------------------ internals ------------------------------
314  private:
315 
319  Polynomial make( const detail::power_node & pnode )
320  {
321  return Xe_k<n, Ring>( pnode.k, pnode.e );
322  }
323 
327  Polynomial make( const detail::monomial_node & mnode )
328  {
329  Polynomial m;
330  if ( mnode.powers.size() != 0 )
331  {
332  m = make( mnode.powers[ 0 ] );
333  for ( unsigned int i = 1; i < mnode.powers.size(); ++i )
334  m *= make( mnode.powers[ i ] );
335  }
336  else
337  m = 1;
338  return ( (Ring) mnode.coef ) * m;
339  }
340 
346  struct ExprNodeMaker : boost::static_visitor<> {
347  Polynomial myP;
350  : myPR( reader )
351  {}
352  void operator()( const detail::monomial_node & mnode)
353  {
354  myP = myPR.make( mnode );
355  }
356  void operator()( const detail::top_node & topnode)
357  {
358  myP = myPR.make( topnode );
359  }
360  };
361 
366  Polynomial make( const detail::top_node & topnode )
367  {
368  ASSERT( ! topnode.expressions.empty() );
369  Polynomial p;
370  ExprNodeMaker emaker( *this );
371  if ( topnode.ops.empty() )
372  {
373  // Node is identity. Nothing special to do.
374  boost::apply_visitor( emaker, topnode.expressions[ 0 ] );
375  p = emaker.myP;
376  }
377  else if ( topnode.ops[ 0 ] == '^' )
378  {
379  // Node is some exponent ( ... )^k. ^0 is admissible.
380  boost::apply_visitor( emaker, topnode.expressions[ 0 ] );
381  p = (Ring) 1;
382  for ( unsigned int i = 1; i <= (unsigned int)topnode.exp; ++i )
383  p *= emaker.myP;
384  }
385  else
386  {
387  // Node is expr1 (*|+|-) expr2 (*|+|-) expr3 ...
388  // NB: either ops are in {+,-} or in {*} only.
389  boost::apply_visitor( emaker, topnode.expressions[ 0 ] );
390  p = emaker.myP;
391  for ( unsigned int i = 0; i < (unsigned int)topnode.ops.size(); ++i )
392  {
393  boost::apply_visitor( emaker, topnode.expressions[ i+1 ] );
394  switch ( topnode.ops[ i ] ) {
395  case '+': p += emaker.myP; break;
396  case '-': p -= emaker.myP; break;
397  case '*': p *= emaker.myP; break;
398  default: std::cerr << "[UNKNOWN-node]" << topnode.ops[ i ] << std::endl;
399  }
400  }
401  }
402  return p;
403  }
404 
405  // ------------------------- Datas --------------------------------------
406  private:
407 
408 
409  // ------------------------- Hidden services ----------------------------
410  protected:
411 
412 
413  }; // end of class MPolynomialReader
414 
415 
422  template <int n, typename TRing, typename TAlloc, typename TIterator>
423  std::ostream&
424  operator<< ( std::ostream & out,
425  const MPolynomialReader<n, TRing, TAlloc, TIterator> & object );
426 
454  template < int n, typename TRing, class TAlloc >
455  std::istream&
456  operator>> ( std::istream & in,
457  MPolynomial<n,TRing,TAlloc> & aMPolynomial );
458 
459 } // namespace DGtal
460 
461 
463 // Includes inline functions.
464 #include "DGtal/io/readers/MPolynomialReader.ih"
465 
466 // //
468 
469 #endif // !defined MPolynomialReader_h
470 
471 #undef MPolynomialReader_RECURSES
472 #endif // else defined(MPolynomialReader_RECURSES)
Iterator read(Polynomial &p, Iterator begin, Iterator end)
qi::rule< Iterator, detail::power_node(), ascii::space_type > genvariable
ExprNodeMaker(MPolynomialReader &reader)
Aim: This class converts a string polynomial expression in a multivariate polynomial.
boost::variant< boost::recursive_wrapper< top_node >, monomial_node > expr_node
STL namespace.
Grammar gpolynomial
Polynomial grammar.
qi::rule< Iterator, detail::power_node(), ascii::space_type > variable
qi::rule< Iterator, detail::monomial_node(), ascii::space_type > monomial
std::ostream & operator<<(std::ostream &out, const ClosedIntegerHalfPlane< TSpace > &object)
MPolynomial< n, Ring, Alloc > Polynomial
void operator()(const detail::top_node &topnode)
void operator()(const detail::monomial_node &mnode)
int exp
the exponent k
void operator>>(const Display3D< Space, KSpace > &aDisplay3D, DGtal::Mesh< typename Display3D< Space, KSpace >::RealPoint > &aMesh)
qi::rule< Iterator, detail::top_node(), ascii::space_type > mulexpr
MPolynomialGrammar< Iterator > Grammar
DGtal is the top-level namespace which contains all DGtal functions and types.
void selfDisplay(std::ostream &out) const
qi::rule< Iterator, detail::top_node(), ascii::space_type > expexpr
qi::rule< Iterator, detail::top_node(), ascii::space_type > top
Polynomial make(const detail::top_node &topnode)
std::vector< power_node > powers
std::vector< expr_node > expressions
the sub-expressions (one more than ops).
qi::rule< Iterator, detail::expr_node(), ascii::space_type > subexpr
qi::rule< Iterator, detail::power_node(), ascii::space_type > litvariable
Polynomial make(const detail::monomial_node &mnode)
std::vector< char > ops
the operation(s), or '^' to designate (expr) or ( expr )^k
Polynomial make(const detail::power_node &pnode)