Debian Codegraph @

extern/ttmath/ttmathobjects.h

raw
1 /*
2 * This file is a part of TTMath Mathematical Library
3 * and is distributed under the (new) BSD licence.
4 * Author: Tomasz Sowa <[email protected]>
5 */
6
7 /*
8 * Copyright (c) 2006-2010, Tomasz Sowa
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * * Neither the name Tomasz Sowa nor the names of contributors to this
22 * project may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35 * THE POSSIBILITY OF SUCH DAMAGE.
36 */
37
38
39 #ifndef headerfilettmathobject
40 #define headerfilettmathobject
41
42 /*!
43 \file ttmathobjects.h
44 \brief Mathematic functions.
45 */
46
47 #include <string>
48 #include <vector>
49 #include <list>
50 #include <map>
51
52 #include "ttmathtypes.h"
53 #include "ttmathmisc.h"
54
55
56 namespace ttmath
57 {
58
59 /*!
60 objects of this class are used with the mathematical parser
61 they hold variables or functions defined by a user
62
63 each object has its own table in which we're keeping variables or functions
64 */
65 class Objects
66 {
67 public:
68
69
70 /*!
71 one item (variable or function)
72 'items' will be on the table
73 */
74 struct Item
75 {
76 // name of a variable of a function
77 // internally we store variables and funcions as std::string (not std::wstring even when wide characters are used)
78 std::string value;
79
80 // number of parameters required by the function
81 // (if there's a variable this 'param' is ignored)
82 int param;
83
84 Item() {}
85 Item(const std::string & v, int p) : value(v), param(p) {}
86 };
87
88 // 'Table' is the type of our table
89 typedef std::map<std::string, Item> Table;
90 typedef Table::iterator Iterator;
91 typedef Table::const_iterator CIterator;
92
93
94
95 /*!
96 this method returns true if a character 'c' is a character
97 which can be in a name
98
99 if 'can_be_digit' is true that means when the 'c' is a digit this
100 method returns true otherwise it returns false
101 */
102 static bool CorrectCharacter(int c, bool can_be_digit)
103 {
104 if( (c>='a' && c<='z') || (c>='A' && c<='Z') )
105 return true;
106
107 if( can_be_digit && ((c>='0' && c<='9') || c=='_') )
108 return true;
109
110 return false;
111 }
112
113
114 /*!
115 this method returns true if the name can be as a name of an object
116 */
117 template<class string_type>
118 static bool IsNameCorrect(const string_type & name)
119 {
120 if( name.empty() )
121 return false;
122
123 if( !CorrectCharacter(name[0], false) )
124 return false;
125
126 typename string_type::const_iterator i = name.begin();
127
128 for(++i ; i!=name.end() ; ++i)
129 if( !CorrectCharacter(*i, true) )
130 return false;
131
132 return true;
133 }
134
135
136 /*!
137 this method returns true if such an object is defined (name exists)
138 */
139 bool IsDefined(const std::string & name)
140 {
141 Iterator i = table.find(name);
142
143 if( i != table.end() )
144 // we have this object in our table
145 return true;
146
147 return false;
148 }
149
150
151
152 #ifndef TTMATH_DONT_USE_WCHAR
153
154 /*!
155 this method returns true if such an object is defined (name exists)
156 */
157 bool IsDefined(const std::wstring & name)
158 {
159 // we should check whether the name (in wide characters) are correct
160 // before calling AssignString() function
161 if( !IsNameCorrect(name) )
162 return false;
163
164 Misc::AssignString(str_tmp1, name);
165
166 return IsDefined(str_tmp1);
167 }
168
169 #endif
170
171
172 /*!
173 this method adds one object (variable of function) into the table
174 */
175 ErrorCode Add(const std::string & name, const std::string & value, int param = 0)
176 {
177 if( !IsNameCorrect(name) )
178 return err_incorrect_name;
179
180 Iterator i = table.find(name);
181
182 if( i != table.end() )
183 // we have this object in our table
184 return err_object_exists;
185
186 table.insert( std::make_pair(name, Item(value, param)) );
187
188 return err_ok;
189 }
190
191
192 #ifndef TTMATH_DONT_USE_WCHAR
193
194 /*!
195 this method adds one object (variable of function) into the table
196 */
197 ErrorCode Add(const std::wstring & name, const std::wstring & value, int param = 0)
198 {
199 // we should check whether the name (in wide characters) are correct
200 // before calling AssignString() function
201 if( !IsNameCorrect(name) )
202 return err_incorrect_name;
203
204 Misc::AssignString(str_tmp1, name);
205 Misc::AssignString(str_tmp2, value);
206
207 return Add(str_tmp1, str_tmp2, param);
208 }
209
210 #endif
211
212
213 /*!
214 this method returns 'true' if the table is empty
215 */
216 bool Empty() const
217 {
218 return table.empty();
219 }
220
221
222 /*!
223 this method clears the table
224 */
225 void Clear()
226 {
227 return table.clear();
228 }
229
230
231 /*!
232 this method returns 'const_iterator' on the first item on the table
233 */
234 CIterator Begin() const
235 {
236 return table.begin();
237 }
238
239
240 /*!
241 this method returns 'const_iterator' pointing at the space after last item
242 (returns table.end())
243 */
244 CIterator End() const
245 {
246 return table.end();
247 }
248
249
250 /*!
251 this method changes the value and the number of parameters for a specific object
252 */
253 ErrorCode EditValue(const std::string & name, const std::string & value, int param = 0)
254 {
255 if( !IsNameCorrect(name) )
256 return err_incorrect_name;
257
258 Iterator i = table.find(name);
259
260 if( i == table.end() )
261 return err_unknown_object;
262
263 i->second.value = value;
264 i->second.param = param;
265
266 return err_ok;
267 }
268
269
270 #ifndef TTMATH_DONT_USE_WCHAR
271
272
273 /*!
274 this method changes the value and the number of parameters for a specific object
275 */
276 ErrorCode EditValue(const std::wstring & name, const std::wstring & value, int param = 0)
277 {
278 // we should check whether the name (in wide characters) are correct
279 // before calling AssignString() function
280 if( !IsNameCorrect(name) )
281 return err_incorrect_name;
282
283 Misc::AssignString(str_tmp1, name);
284 Misc::AssignString(str_tmp2, value);
285
286 return EditValue(str_tmp1, str_tmp2, param);
287 }
288
289 #endif
290
291
292 /*!
293 this method changes the name of a specific object
294 */
295 ErrorCode EditName(const std::string & old_name, const std::string & new_name)
296 {
297 if( !IsNameCorrect(old_name) || !IsNameCorrect(new_name) )
298 return err_incorrect_name;
299
300 Iterator old_i = table.find(old_name);
301 if( old_i == table.end() )
302 return err_unknown_object;
303
304 if( old_name == new_name )
305 // the new name is the same as the old one
306 // we treat it as a normal situation
307 return err_ok;
308
309 ErrorCode err = Add(new_name, old_i->second.value, old_i->second.param);
310
311 if( err == err_ok )
312 {
313 old_i = table.find(old_name);
314 TTMATH_ASSERT( old_i != table.end() )
315
316 table.erase(old_i);
317 }
318
319 return err;
320 }
321
322
323
324 #ifndef TTMATH_DONT_USE_WCHAR
325
326
327 /*!
328 this method changes the name of a specific object
329 */
330 ErrorCode EditName(const std::wstring & old_name, const std::wstring & new_name)
331 {
332 // we should check whether the name (in wide characters) are correct
333 // before calling AssignString() function
334 if( !IsNameCorrect(old_name) || !IsNameCorrect(new_name) )
335 return err_incorrect_name;
336
337 Misc::AssignString(str_tmp1, old_name);
338 Misc::AssignString(str_tmp2, new_name);
339
340 return EditName(str_tmp1, str_tmp2);
341 }
342
343 #endif
344
345
346 /*!
347 this method deletes an object
348 */
349 ErrorCode Delete(const std::string & name)
350 {
351 if( !IsNameCorrect(name) )
352 return err_incorrect_name;
353
354 Iterator i = table.find(name);
355
356 if( i == table.end() )
357 return err_unknown_object;
358
359 table.erase( i );
360
361 return err_ok;
362 }
363
364
365 #ifndef TTMATH_DONT_USE_WCHAR
366
367
368 /*!
369 this method deletes an object
370 */
371 ErrorCode Delete(const std::wstring & name)
372 {
373 // we should check whether the name (in wide characters) are correct
374 // before calling AssignString() function
375 if( !IsNameCorrect(name) )
376 return err_incorrect_name;
377
378 Misc::AssignString(str_tmp1, name);
379
380 return Delete(str_tmp1);
381 }
382
383 #endif
384
385
386 /*!
387 this method gets the value of a specific object
388 */
389 ErrorCode GetValue(const std::string & name, std::string & value) const
390 {
391 if( !IsNameCorrect(name) )
392 return err_incorrect_name;
393
394 CIterator i = table.find(name);
395
396 if( i == table.end() )
397 {
398 value.clear();
399 return err_unknown_object;
400 }
401
402 value = i->second.value;
403
404 return err_ok;
405 }
406
407
408 #ifndef TTMATH_DONT_USE_WCHAR
409
410 /*!
411 this method gets the value of a specific object
412 */
413 ErrorCode GetValue(const std::wstring & name, std::wstring & value)
414 {
415 // we should check whether the name (in wide characters) are correct
416 // before calling AssignString() function
417 if( !IsNameCorrect(name) )
418 return err_incorrect_name;
419
420 Misc::AssignString(str_tmp1, name);
421 ErrorCode err = GetValue(str_tmp1, str_tmp2);
422 Misc::AssignString(value, str_tmp2);
423
424 return err;
425 }
426
427 #endif
428
429
430 /*!
431 this method gets the value of a specific object
432 (this version is used for not copying the whole string)
433 */
434 ErrorCode GetValue(const std::string & name, const char ** value) const
435 {
436 if( !IsNameCorrect(name) )
437 return err_incorrect_name;
438
439 CIterator i = table.find(name);
440
441 if( i == table.end() )
442 {
443 *value = 0;
444 return err_unknown_object;
445 }
446
447 *value = i->second.value.c_str();
448
449 return err_ok;
450 }
451
452
453 #ifndef TTMATH_DONT_USE_WCHAR
454
455 /*!
456 this method gets the value of a specific object
457 (this version is used for not copying the whole string)
458 */
459 ErrorCode GetValue(const std::wstring & name, const char ** value)
460 {
461 // we should check whether the name (in wide characters) are correct
462 // before calling AssignString() function
463 if( !IsNameCorrect(name) )
464 return err_incorrect_name;
465
466 Misc::AssignString(str_tmp1, name);
467
468 return GetValue(str_tmp1, value);
469 }
470
471 #endif
472
473
474 /*!
475 this method gets the value and the number of parameters
476 of a specific object
477 */
478 ErrorCode GetValueAndParam(const std::string & name, std::string & value, int * param) const
479 {
480 if( !IsNameCorrect(name) )
481 return err_incorrect_name;
482
483 CIterator i = table.find(name);
484
485 if( i == table.end() )
486 {
487 value.empty();
488 *param = 0;
489 return err_unknown_object;
490 }
491
492 value = i->second.value;
493 *param = i->second.param;
494
495 return err_ok;
496 }
497
498
499 #ifndef TTMATH_DONT_USE_WCHAR
500
501 /*!
502 this method gets the value and the number of parameters
503 of a specific object
504 */
505 ErrorCode GetValueAndParam(const std::wstring & name, std::wstring & value, int * param)
506 {
507 // we should check whether the name (in wide characters) are correct
508 // before calling AssignString() function
509 if( !IsNameCorrect(name) )
510 return err_incorrect_name;
511
512 Misc::AssignString(str_tmp1, name);
513 ErrorCode err = GetValueAndParam(str_tmp1, str_tmp2, param);
514 Misc::AssignString(value, str_tmp2);
515
516 return err;
517 }
518
519 #endif
520
521
522 /*!
523 this method sets the value and the number of parameters
524 of a specific object
525 (this version is used for not copying the whole string)
526 */
527 ErrorCode GetValueAndParam(const std::string & name, const char ** value, int * param) const
528 {
529 if( !IsNameCorrect(name) )
530 return err_incorrect_name;
531
532 CIterator i = table.find(name);
533
534 if( i == table.end() )
535 {
536 *value = 0;
537 *param = 0;
538 return err_unknown_object;
539 }
540
541 *value = i->second.value.c_str();
542 *param = i->second.param;
543
544 return err_ok;
545 }
546
547
548 #ifndef TTMATH_DONT_USE_WCHAR
549
550
551 /*!
552 this method sets the value and the number of parameters
553 of a specific object
554 (this version is used for not copying the whole string
555 but in fact we make one copying during AssignString())
556 */
557 ErrorCode GetValueAndParam(const std::wstring & name, const char ** value, int * param)
558 {
559 // we should check whether the name (in wide characters) are correct
560 // before calling AssignString() function
561 if( !IsNameCorrect(name) )
562 return err_incorrect_name;
563
564 Misc::AssignString(str_tmp1, name);
565
566 return GetValueAndParam(str_tmp1, value, param);
567 }
568
569
570 #endif
571
572
573 /*!
574 this method returns a pointer into the table
575 */
576 Table * GetTable()
577 {
578 return &table;
579 }
580
581
582 private:
583
584 Table table;
585 std::string str_tmp1, str_tmp2;
586
587 }; // end of class Objects
588
589
590
591
592
593
594
595 /*!
596 objects of the class History are used to keep values in functions
597 which take a lot of time during calculating, for instance in the
598 function Factorial(x)
599
600 it means that when we're calculating e.g. Factorial(1000) and the
601 Factorial finds that we have calculated it before, the value (result)
602 is taken from the history
603 */
604 template<class ValueType>
605 class History
606 {
607 /*!
608 one item in the History's object holds a key, a value for the key
609 and a corresponding error code
610 */
611 struct Item
612 {
613 ValueType key, value;
614 ErrorCode err;
615 };
616
617
618 /*!
619 we use std::list for simply deleting the first item
620 but because we're searching through the whole container
621 (in the method Get) the container should not be too big
622 (linear time of searching)
623 */
624 typedef std::list<Item> buffer_type;
625 buffer_type buffer;
626 typename buffer_type::size_type buffer_max_size;
627
628 public:
629
630 /*!
631 default constructor
632 default max size of the History's container is 15 items
633 */
634 History()
635 {
636 buffer_max_size = 15;
637 }
638
639
640 /*!
641 a constructor which takes another value of the max size
642 of the History's container
643 */
644 History(typename buffer_type::size_type new_size)
645 {
646 buffer_max_size = new_size;
647 }
648
649
650 /*!
651 this method adds one item into the History
652 if the size of the container is greater than buffer_max_size
653 the first item will be removed
654 */
655 void Add(const ValueType & key, const ValueType & value, ErrorCode err)
656 {
657 Item item;
658 item.key = key;
659 item.value = value;
660 item.err = err;
661
662 buffer.insert( buffer.end(), item );
663
664 if( buffer.size() > buffer_max_size )
665 buffer.erase(buffer.begin());
666 }
667
668
669 /*!
670 this method checks whether we have an item which has the key equal 'key'
671
672 if there's such item the method sets the 'value' and the 'err'
673 and returns true otherwise it returns false and 'value' and 'err'
674 remain unchanged
675 */
676 bool Get(const ValueType & key, ValueType & value, ErrorCode & err)
677 {
678 typename buffer_type::iterator i = buffer.begin();
679
680 for( ; i != buffer.end() ; ++i )
681 {
682 if( i->key == key )
683 {
684 value = i->value;
685 err = i->err;
686 return true;
687 }
688 }
689
690 return false;
691 }
692
693
694 /*!
695 this methods deletes an item
696
697 we assume that there is only one item with the 'key'
698 (this methods removes the first one)
699 */
700 bool Remove(const ValueType & key)
701 {
702 typename buffer_type::iterator i = buffer.begin();
703
704 for( ; i != buffer.end() ; ++i )
705 {
706 if( i->key == key )
707 {
708 buffer.erase(i);
709 return true;
710 }
711 }
712
713 return false;
714 }
715
716
717 }; // end of class History
718
719
720
721 /*!
722 this is an auxiliary class used when calculating Gamma() or Factorial()
723
724 in multithreaded environment you can provide an object of this class to
725 the Gamma() or Factorial() function, e.g;
726 typedef Big<1, 3> MyBig;
727 MyBig x = 123456;
728 CGamma<MyBig> cgamma;
729 std::cout << Gamma(x, cgamma);
730 each thread should have its own CGamma<> object
731
732 in a single-thread environment a CGamma<> object is a static variable
733 in a second version of Gamma() and you don't have to explicitly use it, e.g.
734 typedef Big<1, 3> MyBig;
735 MyBig x = 123456;
736 std::cout << Gamma(x);
737 */
738 template<class ValueType>
739 struct CGamma
740 {
741 /*!
742 this table holds factorials
743 1
744 1
745 2
746 6
747 24
748 120
749 720
750 .......
751 */
752 std::vector<ValueType> fact;
753
754
755 /*!
756 this table holds Bernoulli numbers
757 1
758 -0.5
759 0.166666666666666666666666667
760 0
761 -0.0333333333333333333333333333
762 0
763 0.0238095238095238095238095238
764 0
765 -0.0333333333333333333333333333
766 0
767 0.075757575757575757575757576
768 .....
769 */
770 std::vector<ValueType> bern;
771
772
773 /*!
774 here we store some calculated values
775 (this is for speeding up, if the next argument of Gamma() or Factorial()
776 is in the 'history' then the result we are not calculating but simply
777 return from the 'history' object)
778 */
779 History<ValueType> history;
780
781
782 /*!
783 this method prepares some coefficients: factorials and Bernoulli numbers
784 stored in 'fact' and 'bern' objects
785
786 how many values should be depends on the size of the mantissa - if
787 the mantissa is larger then we must calculate more values
788 for a mantissa which consists of 256 bits (8 words on a 32bit platform)
789 we have to calculate about 30 values (the size of fact and bern will be 30),
790 and for a 2048 bits mantissa we have to calculate 306 coefficients
791
792 you don't have to call this method, these coefficients will be automatically calculated
793 when they are needed
794
795 you must note that calculating these coefficients is a little time-consuming operation,
796 (especially when the mantissa is large) and first call to Gamma() or Factorial()
797 can take more time than next calls, and in the end this is the point when InitAll()
798 comes in handy: you can call this method somewhere at the beginning of your program
799 */
800 void InitAll();
801 // definition is in ttmath.h
802 };
803
804
805
806
807 } // namespace
808
809 #endif