ginac/expairseq.h

   1 /** @file expairseq.h */
   2
   3 #ifndef _EXPAIRSEQ_H_
   4 #define _EXPAIRSEQ_H_
   5
   6 #include <vector>
   7 #include <list>
   8
   9 class expairseq;
  10
  11 #include "basic.h"
  12 #include "ex.h"
  13 #include "numeric.h"
  14 #include "debugmsg.h"
  15 #include "expair.h"
  16
  17 //#define EXPAIRSEQ_USE_HASHTAB
  18
  19 typedef vector<expair> epvector;
  20 typedef epvector::iterator epviter;
  21
  22 inline void iter_swap(epvector::iterator it1, epvector::iterator it2)
  23 {
  24     debugmsg("iter_swap epvector",LOGLEVEL_NONMEMBER_FUNCTION);
  25     (*it1).rest.swap((*it2).rest);
  26     (*it1).coeff.swap((*it2).coeff);
  27 }
  28
  29 typedef epvector::iterator epp;
  30 typedef list<epp> epplist;
  31 typedef vector<epplist> epplistvector;
  32
  33 /** A sequence of class expair.
  34  *  This is used for time-critical classes like sums and products of terms
  35  *  since handling a list of coeff and rest is much faster than handling a
  36  *  list of products or powers, respectively. (Incidentally, Maple does it
  37  *  the same way.) */
  38 class expairseq : public basic
  39 {
  40 // member functions
  41
  42     // default constructor, destructor, copy constructor assignment operator and helpers
  43 public:
  44     expairseq() : basic(TINFO_EXPAIRSEQ)
  45 #ifdef EXPAIRSEQ_USE_HASHTAB
  46         , hashtabsize(0)
  47 #endif // def EXPAIRSEQ_USE_HASHTAB
  48         {
  49             debugmsg("expairseq default constructor",LOGLEVEL_CONSTRUCT);
  50         }
  51     ~expairseq()
  52         {
  53             debugmsg("expairseq destructor",LOGLEVEL_DESTRUCT);
  54             destroy(0);
  55         }
  56     expairseq(expairseq const & other);
  57     expairseq const & operator=(expairseq const & other);
  58 protected:
  59     void copy(expairseq const & other);
  60     void destroy(bool call_parent)
  61         {
  62             if (call_parent) basic::destroy(call_parent);
  63         };
  64
  65     // other constructors
  66 public:
  67     expairseq(ex const & lh, ex const & rh);
  68     expairseq(exvector const & v);
  69     expairseq(epvector const & v, ex const & oc);
  70     expairseq(epvector * vp, ex const & oc); // vp will be deleted
  71
  72     // functions overriding virtual functions from bases classes
  73 public:
  74     basic * duplicate() const;
  75     void printraw(ostream & os) const;
  76     void printtree(ostream & os, unsigned indent) const;
  77     void print(ostream & os, unsigned upper_precedence=0) const;
  78     bool info(unsigned inf) const;
  79     int nops() const;
  80     ex op(int const i) const;
  81     ex & let_op(int const i);
  82     ex eval(int level=0) const;
  83     ex evalf(int level=0) const;
  84     ex normal(lst &sym_lst, lst &repl_lst, int level=0) const;
  85     ex diff(symbol const & s) const;
  86     ex subs(lst const & ls, lst const & lr) const;
  87 protected:
  88     int compare_same_type(basic const & other) const;
  89     bool is_equal_same_type(basic const & other) const;
  90     unsigned return_type(void) const;
  91     unsigned calchash(void) const;
  92     ex expand(unsigned options=0) const;
  93
  94     // new virtual functions which can be overridden by derived classes
  95 protected:
  96     virtual ex thisexpairseq(epvector const & v, ex const & oc) const;
  97     virtual ex thisexpairseq(epvector * vp, ex const & oc) const;
  98     virtual void printseq(ostream & os, char delim, unsigned this_precedence,
  99                           unsigned upper_precedence) const;
 100     virtual void printpair(ostream & os, expair const & p,
 101                            unsigned upper_precedence) const;
 102     virtual expair split_ex_to_pair(ex const & e) const;
 103     virtual expair combine_ex_with_coeff_to_pair(ex const & e,
 104                                                  ex const & c) const;
 105     virtual expair combine_pair_with_coeff_to_pair(expair const & p,
 106                                                    ex const & c) const;
 107     virtual ex recombine_pair_to_ex(expair const & p) const;
 108     virtual bool expair_needs_further_processing(epp it);
 109     virtual ex default_overall_coeff(void) const;
 110     virtual void combine_overall_coeff(ex const & c);
 111     virtual void combine_overall_coeff(ex const & c1, ex const & c2);
 112     virtual bool can_make_flat(expair const & p) const;
 113
 114     // non-virtual functions in this class
 115 protected:
 116     void construct_from_2_ex_via_exvector(ex const & lh, ex const & rh);
 117     void construct_from_2_ex(ex const & lh, ex const & rh);
 118     void construct_from_2_expairseq(expairseq const & s1,
 119                                     expairseq const & s2);
 120     void construct_from_expairseq_ex(expairseq const & s,
 121                                      ex const & e);
 122     void construct_from_exvector(exvector const & v);
 123     void construct_from_epvector(epvector const & v);
 124     void make_flat(exvector const & v);
 125     void make_flat(epvector const & v);
 126     epvector * bubblesort(epvector::iterator itbegin, epvector::iterator itend);
 127     epvector * mergesort(epvector::iterator itbegin, epvector::iterator itend);
 128     void canonicalize(void);
 129     void combine_same_terms_sorted_seq(void);
 130 #ifdef EXPAIRSEQ_USE_HASHTAB
 131     void combine_same_terms(void);
 132     unsigned calc_hashtabsize(unsigned sz) const;
 133     unsigned calc_hashindex(ex const & e) const;
 134     void shrink_hashtab(void);
 135     void remove_hashtab_entry(epvector::const_iterator element);
 136     void move_hashtab_entry(epvector::const_iterator oldpos,
 137                             epvector::iterator newpos);
 138     void sorted_insert(epplist & eppl, epp elem);
 139     void build_hashtab_and_combine(epvector::iterator & first_numeric,
 140                                    epvector::iterator & last_non_zero,
 141                                    vector<bool> & touched,
 142                                    unsigned & number_of_zeroes);
 143     void drop_coeff_0_terms(epvector::iterator & first_numeric,
 144                             epvector::iterator & last_non_zero,
 145                             vector<bool> & touched,
 146                             unsigned & number_of_zeroes);
 147     bool has_coeff_0(void) const;
 148     void add_numerics_to_hashtab(epvector::iterator first_numeric,                                              epvector::const_iterator last_non_zero);
 149 #endif // def EXPAIRSEQ_USE_HASHTAB
 150     bool is_canonical() const;
 151     epvector * expandchildren(unsigned options) const;
 152     epvector * evalchildren(int level) const;
 153     epvector evalfchildren(int level) const;
 154     epvector normalchildren(int level) const;
 155     epvector diffchildren(symbol const & s) const;
 156     epvector * subschildren(lst const & ls, lst const & lr) const;
 157
 158 // member variables
 159
 160 protected:
 161     epvector seq;
 162     ex overall_coeff;
 163     static unsigned precedence;
 164 #ifdef EXPAIRSEQ_USE_HASHTAB
 165     epplistvector hashtab;
 166     unsigned hashtabsize;
 167     unsigned hashmask;
 168     static unsigned maxhashtabsize;
 169     static unsigned minhashtabsize;
 170     static unsigned hashtabfactor;
 171 #endif // def EXPAIRSEQ_USE_HASHTAB
 172 };
 173
 174 // global constants
 175
 176 extern const expairseq some_expairseq;
 177 extern type_info const & typeid_expairseq;
 178
 179 #define ex_to_expairseq(X) static_cast<expairseq const &>(*(X).bp)
 180
 181 #endif // ndef _EXPAIRSEQ_H_
 182
 183