ttmathobjects.h

00001 /*
00002  * This file is a part of TTMath Mathematical Library
00003  * and is distributed under the (new) BSD licence.
00004  * Author: Tomasz Sowa <t.sowa@ttmath.org>
00005  */
00006 
00007 /* 
00008  * Copyright (c) 2006-2010, Tomasz Sowa
00009  * All rights reserved.
00010  * 
00011  * Redistribution and use in source and binary forms, with or without
00012  * modification, are permitted provided that the following conditions are met:
00013  * 
00014  *  * Redistributions of source code must retain the above copyright notice,
00015  *    this list of conditions and the following disclaimer.
00016  *    
00017  *  * Redistributions in binary form must reproduce the above copyright
00018  *    notice, this list of conditions and the following disclaimer in the
00019  *    documentation and/or other materials provided with the distribution.
00020  *    
00021  *  * Neither the name Tomasz Sowa nor the names of contributors to this
00022  *    project may be used to endorse or promote products derived
00023  *    from this software without specific prior written permission.
00024  *
00025  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00026  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00028  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
00029  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00030  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00031  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00032  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00033  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00034  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
00035  * THE POSSIBILITY OF SUCH DAMAGE.
00036  */
00037 
00038 
00039 #ifndef headerfilettmathobject
00040 #define headerfilettmathobject
00041 
00042 /*!
00043     \file ttmathobjects.h
00044     \brief Mathematic functions.
00045 */
00046 
00047 #include <string>
00048 #include <vector>
00049 #include <list>
00050 #include <map>
00051 
00052 #include "ttmathtypes.h"
00053 #include "ttmathmisc.h"
00054 
00055 
00056 namespace ttmath
00057 {
00058 
00059 /*!
00060     objects of this class are used with the mathematical parser
00061     they hold variables or functions defined by a user
00062 
00063     each object has its own table in which we're keeping variables or functions
00064 */
00065 class Objects 
00066 {
00067 public:
00068 
00069 
00070     /*!
00071         one item (variable or function)
00072         'items' will be on the table
00073     */
00074     struct Item 
00075     {
00076         // name of a variable of a function
00077         // internally we store variables and funcions as std::string (not std::wstring even when wide characters are used)
00078         std::string value;
00079 
00080         // number of parameters required by the function
00081         // (if there's a variable this 'param' is ignored)
00082         int param;
00083 
00084         Item () {}
00085         Item (const std::string & v, int p) : value(v), param(p) {}
00086     };
00087 
00088     // 'Table' is the type of our table
00089     typedef std::map<std::string, Item> Table;
00090     typedef    Table::iterator Iterator;
00091     typedef    Table::const_iterator CIterator;
00092 
00093 
00094 
00095     /*!
00096         this method returns true if a character 'c' is a character
00097         which can be in a name
00098         
00099         if 'can_be_digit' is true that means when the 'c' is a digit this 
00100         method returns true otherwise it returns false
00101     */
00102     static bool CorrectCharacter (int c, bool can_be_digit)
00103     {
00104         if( (c>='a' && c<='z') || (c>='A' && c<='Z') )
00105             return true;
00106 
00107         if( can_be_digit && ((c>='0' && c<='9') || c=='_') )
00108             return true;
00109 
00110     return false;
00111     }
00112 
00113 
00114     /*!
00115         this method returns true if the name can be as a name of an object
00116     */
00117     template<class string_type>
00118     static bool IsNameCorrect (const string_type & name)
00119     {
00120         if( name.empty() )
00121             return false;
00122 
00123         if( !CorrectCharacter (name[0], false) )
00124             return false;
00125 
00126         typename string_type::const_iterator i = name.begin();
00127 
00128         for(++i ; i!=name.end() ; ++i)
00129             if( !CorrectCharacter (*i, true) )
00130                 return false;
00131         
00132     return true;
00133     }
00134 
00135 
00136     /*!
00137         this method returns true if such an object is defined (name exists)
00138     */
00139     bool IsDefined (const std::string & name)
00140     {
00141         Iterator i = table.find(name);
00142 
00143         if( i != table.end() )
00144             // we have this object in our table
00145             return true;
00146 
00147     return false;
00148     }
00149 
00150 
00151 
00152 #ifndef TTMATH_DONT_USE_WCHAR
00153 
00154     /*!
00155         this method returns true if such an object is defined (name exists)
00156     */
00157     bool IsDefined (const std::wstring & name)
00158     {
00159         // we should check whether the name (in wide characters) are correct
00160         // before calling AssignString() function
00161         if( !IsNameCorrect (name) )
00162             return false;
00163 
00164         Misc::AssignString (str_tmp1, name);
00165 
00166     return IsDefined (str_tmp1);
00167     }
00168 
00169 #endif
00170 
00171 
00172     /*!
00173         this method adds one object (variable of function) into the table
00174     */
00175     ErrorCode  Add (const std::string & name, const std::string & value, int param = 0)
00176     {
00177         if( !IsNameCorrect (name) )
00178             return err_incorrect_name;
00179 
00180         Iterator i = table.find(name);
00181 
00182         if( i != table.end() )
00183             // we have this object in our table
00184             return err_object_exists;
00185 
00186         table.insert( std::make_pair(name, Item (value, param)) );
00187 
00188     return err_ok;
00189     }
00190 
00191 
00192 #ifndef TTMATH_DONT_USE_WCHAR
00193 
00194     /*!
00195         this method adds one object (variable of function) into the table
00196     */
00197     ErrorCode  Add (const std::wstring & name, const std::wstring & value, int param = 0)
00198     {
00199         // we should check whether the name (in wide characters) are correct
00200         // before calling AssignString() function
00201         if( !IsNameCorrect (name) )
00202             return err_incorrect_name;
00203 
00204         Misc::AssignString (str_tmp1, name);
00205         Misc::AssignString (str_tmp2, value);
00206         
00207     return Add (str_tmp1, str_tmp2, param);
00208     }
00209 
00210 #endif
00211 
00212 
00213     /*!
00214         this method returns 'true' if the table is empty
00215     */
00216     bool Empty () const
00217     {
00218         return table.empty();
00219     }
00220 
00221 
00222     /*!
00223         this method clears the table
00224     */
00225     void Clear ()
00226     {
00227         return table.clear();
00228     }
00229 
00230 
00231     /*!
00232         this method returns 'const_iterator' on the first item on the table
00233     */
00234     CIterator Begin () const
00235     {
00236         return table.begin();
00237     }
00238 
00239 
00240     /*!
00241         this method returns 'const_iterator' pointing at the space after last item
00242         (returns table.end())
00243     */
00244     CIterator End () const
00245     {
00246         return table.end();
00247     }
00248 
00249 
00250     /*!
00251         this method changes the value and the number of parameters for a specific object
00252     */
00253     ErrorCode  EditValue (const std::string & name, const std::string & value, int param = 0)
00254     {
00255         if( !IsNameCorrect (name) )
00256             return err_incorrect_name;
00257 
00258         Iterator i = table.find(name);
00259 
00260         if( i == table.end() )
00261             return err_unknown_object;
00262     
00263         i->second.value = value;
00264         i->second.param = param;
00265 
00266     return err_ok;
00267     }
00268 
00269 
00270 #ifndef TTMATH_DONT_USE_WCHAR
00271 
00272 
00273     /*!
00274         this method changes the value and the number of parameters for a specific object
00275     */
00276     ErrorCode  EditValue (const std::wstring & name, const std::wstring & value, int param = 0)
00277     {
00278         // we should check whether the name (in wide characters) are correct
00279         // before calling AssignString() function
00280         if( !IsNameCorrect (name) )
00281             return err_incorrect_name;
00282 
00283         Misc::AssignString (str_tmp1, name);
00284         Misc::AssignString (str_tmp2, value);
00285         
00286     return EditValue (str_tmp1, str_tmp2, param);
00287     }
00288 
00289 #endif
00290 
00291 
00292     /*!
00293         this method changes the name of a specific object
00294     */
00295     ErrorCode  EditName (const std::string & old_name, const std::string & new_name)
00296     {
00297         if( !IsNameCorrect (old_name) || !IsNameCorrect (new_name) )
00298             return err_incorrect_name;
00299 
00300         Iterator old_i = table.find(old_name);
00301         if( old_i == table.end() )
00302             return err_unknown_object;
00303         
00304         if( old_name == new_name )
00305             // the new name is the same as the old one
00306             // we treat it as a normal situation
00307             return err_ok;
00308 
00309         ErrorCode  err = Add (new_name, old_i->second.value, old_i->second.param);
00310         
00311         if( err == err_ok ) 
00312         {
00313             old_i = table.find(old_name);
00314             TTMATH_ASSERT( old_i != table.end() )
00315 
00316             table.erase(old_i);
00317         }
00318 
00319     return err;
00320     }
00321 
00322 
00323 
00324 #ifndef TTMATH_DONT_USE_WCHAR
00325 
00326 
00327     /*!
00328         this method changes the name of a specific object
00329     */
00330     ErrorCode  EditName (const std::wstring & old_name, const std::wstring & new_name)
00331     {
00332         // we should check whether the name (in wide characters) are correct
00333         // before calling AssignString() function
00334         if( !IsNameCorrect (old_name) || !IsNameCorrect (new_name) )
00335             return err_incorrect_name;
00336 
00337         Misc::AssignString (str_tmp1, old_name);
00338         Misc::AssignString (str_tmp2, new_name);
00339 
00340     return EditName (str_tmp1, str_tmp2);
00341     }
00342 
00343 #endif
00344 
00345 
00346     /*!
00347         this method deletes an object
00348     */
00349     ErrorCode  Delete (const std::string & name)
00350     {
00351         if( !IsNameCorrect (name) )
00352             return err_incorrect_name;
00353 
00354         Iterator i = table.find(name);
00355 
00356         if( i == table.end() )
00357             return err_unknown_object;
00358 
00359         table.erase( i );
00360 
00361     return err_ok;
00362     }
00363 
00364 
00365 #ifndef TTMATH_DONT_USE_WCHAR
00366 
00367 
00368     /*!
00369         this method deletes an object
00370     */
00371     ErrorCode  Delete (const std::wstring & name)
00372     {
00373         // we should check whether the name (in wide characters) are correct
00374         // before calling AssignString() function
00375         if( !IsNameCorrect (name) )
00376             return err_incorrect_name;
00377 
00378         Misc::AssignString (str_tmp1, name);
00379 
00380     return Delete (str_tmp1);
00381     }    
00382         
00383 #endif
00384 
00385 
00386     /*!
00387         this method gets the value of a specific object
00388     */
00389     ErrorCode  GetValue (const std::string & name, std::string & value) const
00390     {
00391         if( !IsNameCorrect (name) )
00392             return err_incorrect_name;
00393 
00394         CIterator i = table.find(name);
00395 
00396         if( i == table.end() )
00397         {
00398             value.clear();
00399             return err_unknown_object;
00400         }
00401 
00402         value = i->second.value;
00403 
00404     return err_ok;
00405     }
00406 
00407 
00408 #ifndef TTMATH_DONT_USE_WCHAR
00409 
00410     /*!
00411         this method gets the value of a specific object
00412     */
00413     ErrorCode  GetValue (const std::wstring & name, std::wstring & value)
00414     {
00415         // we should check whether the name (in wide characters) are correct
00416         // before calling AssignString() function
00417         if( !IsNameCorrect (name) )
00418             return err_incorrect_name;
00419 
00420         Misc::AssignString (str_tmp1, name);
00421         ErrorCode  err = GetValue (str_tmp1, str_tmp2);
00422         Misc::AssignString (value, str_tmp2);
00423 
00424     return err;
00425     }
00426 
00427 #endif
00428 
00429 
00430     /*!
00431         this method gets the value of a specific object
00432         (this version is used for not copying the whole string)
00433     */
00434     ErrorCode  GetValue (const std::string & name, const char ** value) const
00435     {
00436         if( !IsNameCorrect (name) )
00437             return err_incorrect_name;
00438 
00439         CIterator i = table.find(name);
00440 
00441         if( i == table.end() )
00442         {
00443             *value = 0;
00444             return err_unknown_object;
00445         }
00446 
00447         *value = i->second.value.c_str();
00448 
00449     return err_ok;
00450     }
00451 
00452 
00453 #ifndef TTMATH_DONT_USE_WCHAR
00454 
00455     /*!
00456         this method gets the value of a specific object
00457         (this version is used for not copying the whole string)
00458     */
00459     ErrorCode  GetValue (const std::wstring & name, const char ** value)
00460     {
00461         // we should check whether the name (in wide characters) are correct
00462         // before calling AssignString() function
00463         if( !IsNameCorrect (name) )
00464             return err_incorrect_name;
00465 
00466         Misc::AssignString (str_tmp1, name);
00467 
00468     return GetValue (str_tmp1, value);
00469     }
00470 
00471 #endif
00472 
00473 
00474     /*!
00475         this method gets the value and the number of parameters
00476         of a specific object
00477     */
00478     ErrorCode  GetValueAndParam (const std::string & name, std::string & value, int * param) const
00479     {
00480         if( !IsNameCorrect (name) )
00481             return err_incorrect_name;
00482 
00483         CIterator i = table.find(name);
00484 
00485         if( i == table.end() )
00486         {
00487             value.empty();
00488             *param = 0;
00489             return err_unknown_object;
00490         }
00491 
00492         value = i->second.value;
00493         *param = i->second.param;
00494 
00495     return err_ok;
00496     }
00497 
00498 
00499 #ifndef TTMATH_DONT_USE_WCHAR
00500 
00501     /*!
00502         this method gets the value and the number of parameters
00503         of a specific object
00504     */
00505     ErrorCode  GetValueAndParam (const std::wstring & name, std::wstring & value, int * param)
00506     {
00507         // we should check whether the name (in wide characters) are correct
00508         // before calling AssignString() function
00509         if( !IsNameCorrect (name) )
00510             return err_incorrect_name;
00511 
00512         Misc::AssignString (str_tmp1, name);
00513         ErrorCode  err = GetValueAndParam (str_tmp1, str_tmp2, param);
00514         Misc::AssignString (value, str_tmp2);
00515 
00516     return err;
00517     }
00518 
00519 #endif
00520 
00521 
00522     /*!
00523         this method sets the value and the number of parameters
00524         of a specific object
00525         (this version is used for not copying the whole string)
00526     */
00527     ErrorCode  GetValueAndParam (const std::string & name, const char ** value, int * param) const
00528     {
00529         if( !IsNameCorrect (name) )
00530             return err_incorrect_name;
00531 
00532         CIterator i = table.find(name);
00533 
00534         if( i == table.end() )
00535         {
00536             *value = 0;
00537             *param = 0;
00538             return err_unknown_object;
00539         }
00540 
00541         *value = i->second.value.c_str();
00542         *param = i->second.param;
00543 
00544     return err_ok;
00545     }
00546 
00547 
00548 #ifndef TTMATH_DONT_USE_WCHAR
00549 
00550 
00551     /*!
00552         this method sets the value and the number of parameters
00553         of a specific object
00554         (this version is used for not copying the whole string
00555         but in fact we make one copying during AssignString())
00556     */
00557     ErrorCode  GetValueAndParam (const std::wstring & name, const char ** value, int * param)
00558     {
00559         // we should check whether the name (in wide characters) are correct
00560         // before calling AssignString() function
00561         if( !IsNameCorrect (name) )
00562             return err_incorrect_name;
00563 
00564         Misc::AssignString (str_tmp1, name);
00565 
00566     return GetValueAndParam (str_tmp1, value, param);
00567     }
00568 
00569 
00570 #endif
00571 
00572 
00573     /*!
00574         this method returns a pointer into the table
00575     */
00576     Table * GetTable ()
00577     {
00578         return &table;
00579     }
00580 
00581 
00582 private:
00583 
00584     Table table;
00585     std::string str_tmp1, str_tmp2;
00586 
00587 }; // end of class Objects
00588 
00589 
00590 
00591 
00592 
00593 
00594 
00595 /*!
00596     objects of the class History are used to keep values in functions
00597     which take a lot of time during calculating, for instance in the 
00598     function Factorial(x)
00599 
00600     it means that when we're calculating e.g. Factorial(1000) and the 
00601     Factorial finds that we have calculated it before, the value (result)
00602     is taken from the history
00603 */
00604 template<class ValueType>
00605 class History 
00606 {
00607     /*!
00608         one item in the History's object holds a key, a value for the key
00609         and a corresponding error code
00610     */
00611     struct Item
00612     {
00613         ValueType key, value;
00614         ErrorCode  err;
00615     };
00616 
00617 
00618     /*!
00619         we use std::list for simply deleting the first item
00620         but because we're searching through the whole container
00621         (in the method Get) the container should not be too big
00622         (linear time of searching)
00623     */
00624     typedef std::list<Item> buffer_type;
00625     buffer_type buffer;
00626     typename buffer_type::size_type buffer_max_size;
00627 
00628 public:
00629     
00630     /*!
00631         default constructor
00632         default max size of the History's container is 15 items
00633     */
00634     History ()
00635     {
00636         buffer_max_size = 15;
00637     }
00638 
00639 
00640     /*!
00641         a constructor which takes another value of the max size
00642         of the History's container
00643     */
00644     History (typename buffer_type::size_type new_size)
00645     {
00646         buffer_max_size = new_size;
00647     }
00648 
00649 
00650     /*!
00651         this method adds one item into the History
00652         if the size of the container is greater than buffer_max_size
00653         the first item will be removed
00654     */
00655     void Add (const ValueType & key, const ValueType & value, ErrorCode  err)
00656     {
00657         Item item;
00658         item.key   = key;
00659         item.value = value;
00660         item.err   = err;
00661 
00662         buffer.insert( buffer.end(), item );
00663 
00664         if( buffer.size() > buffer_max_size )
00665             buffer.erase(buffer.begin());
00666     }
00667 
00668 
00669     /*!
00670         this method checks whether we have an item which has the key equal 'key'
00671 
00672         if there's such item the method sets the 'value' and the 'err'
00673         and returns true otherwise it returns false and 'value' and 'err'
00674         remain unchanged
00675     */
00676     bool Get (const ValueType & key, ValueType & value, ErrorCode  & err)
00677     {
00678         typename buffer_type::iterator i = buffer.begin();
00679 
00680         for( ; i != buffer.end() ; ++i )
00681         {
00682             if( i->key == key )
00683             {
00684                 value = i->value;
00685                 err   = i->err;
00686                 return true;
00687             }
00688         }
00689 
00690     return false;
00691     }
00692 
00693 
00694     /*!
00695         this methods deletes an item
00696 
00697         we assume that there is only one item with the 'key'
00698         (this methods removes the first one)
00699     */
00700     bool Remove (const ValueType & key)
00701     {
00702         typename buffer_type::iterator i = buffer.begin();
00703 
00704         for( ; i != buffer.end() ; ++i )
00705         {
00706             if( i->key == key )
00707             {
00708                 buffer.erase(i);
00709                 return true;
00710             }
00711         }
00712 
00713     return false;
00714     }
00715 
00716 
00717 }; // end of class History
00718 
00719 
00720 
00721 /*!
00722     this is an auxiliary class used when calculating Gamma() or Factorial()
00723 
00724     in multithreaded environment you can provide an object of this class to
00725     the Gamma() or Factorial() function, e.g;
00726         typedef Big<1, 3> MyBig;
00727         MyBig x = 123456;
00728         CGamma<MyBig> cgamma;
00729         std::cout << Gamma(x, cgamma);
00730     each thread should have its own CGamma<> object
00731 
00732     in a single-thread environment a CGamma<> object is a static variable
00733     in a second version of Gamma() and you don't have to explicitly use it, e.g.
00734         typedef Big<1, 3> MyBig;
00735         MyBig x = 123456;
00736         std::cout << Gamma(x);
00737 */
00738 template<class ValueType>
00739 struct CGamma 
00740 {
00741     /*!
00742         this table holds factorials
00743             1
00744             1
00745             2
00746             6
00747             24
00748             120
00749             720
00750             .......
00751     */
00752     std::vector<ValueType> fact ;
00753 
00754 
00755     /*!
00756         this table holds Bernoulli numbers
00757             1
00758             -0.5
00759             0.166666666666666666666666667
00760             0
00761             -0.0333333333333333333333333333
00762             0
00763             0.0238095238095238095238095238
00764             0
00765             -0.0333333333333333333333333333
00766             0
00767             0.075757575757575757575757576
00768             .....
00769     */
00770     std::vector<ValueType> bern ;
00771 
00772 
00773     /*!
00774         here we store some calculated values
00775         (this is for speeding up, if the next argument of Gamma() or Factorial()
00776         is in the 'history' then the result we are not calculating but simply
00777         return from the 'history' object)
00778     */
00779     History<ValueType>  history ;
00780 
00781 
00782     /*!
00783         this method prepares some coefficients: factorials and Bernoulli numbers
00784         stored in 'fact' and 'bern' objects
00785         
00786         how many values should be depends on the size of the mantissa - if
00787         the mantissa is larger then we must calculate more values
00788             for a mantissa which consists of 256 bits (8 words on a 32bit platform)
00789             we have to calculate about 30 values (the size of fact and bern will be 30),
00790             and for a 2048 bits mantissa we have to calculate 306 coefficients
00791 
00792         you don't have to call this method, these coefficients will be automatically calculated
00793         when they are needed
00794 
00795         you must note that calculating these coefficients is a little time-consuming operation,
00796         (especially when the mantissa is large) and first call to Gamma() or Factorial()
00797         can take more time than next calls, and in the end this is the point when InitAll()
00798         comes in handy: you can call this method somewhere at the beginning of your program
00799     */
00800     void InitAll ();
00801     // definition is in ttmath.h
00802 };
00803 
00804 
00805 
00806 
00807 } // namespace
00808 
00809 #endif
00810