fix ast memory leak in tests
[scilab.git] / scilab / modules / ast / includes / analysis / gvn / MultivariateMonomial.hxx
1 /*
2  *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
4  *
5  *  This file must be used under the terms of the CeCILL.
6  *  This source file is licensed as described in the file COPYING, which
7  *  you should have received as part of this distribution.  The terms
8  *  are also available at
9  *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
10  *
11  */
12
13 #ifndef __MULTIVARIATE_MONOMIAL_HXX__
14 #define __MULTIVARIATE_MONOMIAL_HXX__
15
16 #include <cmath>
17 #include <functional>
18 #include <iostream>
19 #include <map>
20 #include <set>
21 #include <sstream>
22 #include <string>
23
24 #include "tools.hxx"
25 #include "VarExp.hxx"
26
27 namespace analysis
28 {
29
30 /**
31  * \struct MultivariateMonomial
32  * \brief Represents a multivariate monomial
33  */
34 struct MultivariateMonomial
35 {
36     typedef std::set<VarExp, VarExp::Compare> Monomial;
37
38     // Since the coeff is not used to compute the hash we must set is as mutable to be able to modify it when extract
39     // from an unordered_set or unordered_map.
40     mutable double coeff;
41     Monomial monomial;
42
43     /**
44      * \brief constructor
45      * \param var the default var to put in the monomial
46      */
47     MultivariateMonomial(const unsigned long long var) : coeff(1)
48     {
49         monomial.emplace(var);
50     }
51
52     /**
53      * \brief constructor
54      * \param coeff the default coefficient for this empty monomial
55      */
56     MultivariateMonomial(const double _coeff = 1) : coeff(_coeff) { }
57
58     /**
59      * \brief copy-constructor
60      * \param mm the monomial to copy
61      */
62     MultivariateMonomial(const MultivariateMonomial & mm) : coeff(mm.coeff), monomial(mm.monomial) { }
63
64     /**
65      * Check if the variables of the monomial have an id lower or equal to max
66      * \param max an id
67      * \return true if all the variables have an id leq to max
68      */
69     inline bool checkVariable(const unsigned long long max) const
70     {
71         for (const auto & ve : monomial)
72         {
73             if (ve.var > max)
74             {
75                 return false;
76             }
77         }
78         return true;
79     }
80
81     /**
82      * \brief Get the sum of the exponents in the monomial
83      * \return the total exponent
84      */
85     inline unsigned int exponent() const
86     {
87         unsigned int exp = 0;
88         for (const auto & ve : monomial)
89         {
90             exp += ve.exp;
91         }
92         return exp;
93     }
94
95     /**
96      * \brief Add a varexp in the monomial
97      * \param ve the varexp to add
98      * \return *this
99      */
100     inline MultivariateMonomial & add(const VarExp & ve)
101     {
102         Monomial::iterator i = monomial.find(ve);
103         if (i == monomial.end())
104         {
105             monomial.insert(ve);
106         }
107         else
108         {
109             i->exp += ve.exp;
110         }
111         return *this;
112     }
113
114     /**
115      * \brief Add a varexp in the monomial
116      * \param ve the varexp to add
117      * \return *this
118      */
119     inline MultivariateMonomial & add(VarExp && ve)
120     {
121         Monomial::iterator i = monomial.find(ve);
122         if (i == monomial.end())
123         {
124             monomial.emplace(std::move(ve));
125         }
126         else
127         {
128             i->exp += ve.exp;
129         }
130         return *this;
131     }
132
133     /**
134      * \brief Product of two monomials
135      * \param R the RHS monomial
136      * \return the product of *this and R
137      */
138     inline MultivariateMonomial operator*(const MultivariateMonomial & R) const
139     {
140         MultivariateMonomial res(*this);
141         res.coeff *= R.coeff;
142         for (const auto & ve : R.monomial)
143         {
144             res.add(ve);
145         }
146         return res;
147     }
148
149     /**
150      * \brief Product-assignment
151      */
152     inline MultivariateMonomial & operator*=(const MultivariateMonomial & R)
153     {
154         coeff *= R.coeff;
155         for (const auto & ve : R.monomial)
156         {
157             add(ve);
158         }
159         return *this;
160     }
161
162     /**
163      * \brief Product by a double
164      */
165     friend inline MultivariateMonomial operator*(const double L, const MultivariateMonomial & R)
166     {
167         return R * L;
168     }
169
170     /**
171      * \brief Product by a double
172      */
173     inline MultivariateMonomial operator*(const double R) const
174     {
175         MultivariateMonomial res(*this);
176         res.coeff *= R;
177         return res;
178     }
179
180     /**
181      * \brief Product-assignment by a double
182      */
183     inline MultivariateMonomial & operator*=(const double R)
184     {
185         coeff *= R;
186         return *this;
187     }
188
189     /**
190      * \brief Division by a double
191      */
192     inline MultivariateMonomial operator/(const double R) const
193     {
194         MultivariateMonomial res(*this);
195         res.coeff /= R;
196         return res;
197     }
198
199     /**
200      * \brief Division-assignment by a double
201      */
202     inline MultivariateMonomial & operator/=(const double R)
203     {
204         coeff /= R;
205         return *this;
206     }
207
208     /**
209      * \brief Exponentation by an uint
210      */
211     inline MultivariateMonomial operator^(unsigned int R) const
212     {
213         MultivariateMonomial res(*this);
214         if (R > 1)
215         {
216             coeff = std::pow(coeff, R);
217             for (auto & ve : res.monomial)
218             {
219                 ve.exp *= R;
220             }
221         }
222         return res;
223     }
224
225     /**
226      * \brief Equality
227      */
228     inline bool operator==(const MultivariateMonomial & R) const
229     {
230         return coeff == R.coeff && monomial == R.monomial;
231     }
232
233     /**
234      * \brief Print a monomial
235      * \param vars a map containing var id -> string representation
236      * \return the printed monomial
237      */
238     inline const std::wstring print(const std::map<unsigned long long, std::wstring> & vars) const
239     {
240         std::wostringstream wos;
241         wos << coeff;
242         for (const auto & ve : monomial)
243         {
244             wos << L"*" << ve.print(vars);
245         }
246         return wos.str();
247     }
248
249     /**
250      * \brief Overload of the << operator
251      */
252     friend inline std::wostream & operator<<(std::wostream & out, const MultivariateMonomial & m)
253     {
254         out << m.coeff;
255         for (const auto & ve : m.monomial)
256         {
257             out << L"*" << ve;
258         }
259         return out;
260     }
261
262     /**
263      * \struct Hash
264      * \brief To be used in an unordered container
265      */
266     struct Hash
267     {
268         inline std::size_t operator()(const MultivariateMonomial & m) const
269         {
270             // We don't consider the coefficient of the monomial : take care it is not a bug !!
271             // when we add a monomial 1.23*a*b in a polynomial we search in the unordered_set ?*a*b and
272             // we add 1.23 to its coefficient
273             std::size_t h = 0;
274             for (const auto & ve : m.monomial)
275             {
276                 h = tools::hash_combine(h, std::hash<unsigned long long>()(ve.var), std::hash<unsigned int>()(ve.exp));
277             }
278             return h;
279         }
280     };
281
282     /**
283      * \struct Eq
284      * \brief To be used in an unordered container
285      */
286     struct Eq
287     {
288         inline bool operator()(const MultivariateMonomial & L, const MultivariateMonomial & R) const
289         {
290             // See the comment above (to see why we ignore the coefficient)
291             return L.monomial == R.monomial;
292         }
293     };
294
295     /**
296      * \struct Compare
297      * \brief To be used in an ordered container
298      */
299     struct Compare
300     {
301         inline bool operator()(const MultivariateMonomial & L, const MultivariateMonomial & R) const
302         {
303             const unsigned int le = L.exponent();
304             const unsigned int re = R.exponent();
305             if (le < re)
306             {
307                 return true;
308             }
309             else if (le == re)
310             {
311                 const unsigned int ls = static_cast<unsigned int>(L.monomial.size());
312                 const unsigned int rs = static_cast<unsigned int>(R.monomial.size());
313                 if (ls > rs)
314                 {
315                     return true;
316                 }
317                 else if (ls == rs)
318                 {
319                     for (Monomial::const_iterator i = L.monomial.begin(), j = R.monomial.begin(), e = L.monomial.end(); i != e; ++i, ++j)
320                     {
321                         if (VarExp::Compare()(*i, *j))
322                         {
323                             return true;
324                         }
325                         else if (!VarExp::Eq()(*i, *j))
326                         {
327                             return false;
328                         }
329                     }
330
331                     for (Monomial::const_iterator i = L.monomial.begin(), j = R.monomial.begin(), e = L.monomial.end(); i != e; ++i, ++j)
332                     {
333                         if (i->exp < j->exp)
334                         {
335                             return true;
336                         }
337                         else if (i->exp > j->exp)
338                         {
339                             return false;
340                         }
341                     }
342
343                 }
344             }
345             return false;
346         }
347     };
348 };
349
350 } // namespace analysis
351
352 #endif // __MULTIVARIATE_MONOMIAL_HXX__