3 * GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 #ifndef __GINAC_EXPAIRSEQ_H__
21 #define __GINAC_EXPAIRSEQ_H__
25 #include <ginac/expair.h>
27 //#define EXPAIRSEQ_USE_HASHTAB
29 typedef vector<expair> epvector;
30 typedef epvector::iterator epviter;
32 inline void iter_swap(epvector::iterator it1, epvector::iterator it2)
34 debugmsg("iter_swap epvector",LOGLEVEL_NONMEMBER_FUNCTION);
35 (*it1).rest.swap((*it2).rest);
36 (*it1).coeff.swap((*it2).coeff);
39 typedef epvector::iterator epp;
40 typedef list<epp> epplist;
41 typedef vector<epplist> epplistvector;
43 /** A sequence of class expair.
44 * This is used for time-critical classes like sums and products of terms
45 * since handling a list of coeff and rest is much faster than handling a
46 * list of products or powers, respectively. (Incidentally, Maple does it
48 class expairseq : public basic
52 // default constructor, destructor, copy constructor assignment operator and helpers
54 expairseq() : basic(TINFO_expairseq)
55 #ifdef EXPAIRSEQ_USE_HASHTAB
57 #endif // def EXPAIRSEQ_USE_HASHTAB
59 debugmsg("expairseq default constructor",LOGLEVEL_CONSTRUCT);
63 debugmsg("expairseq destructor",LOGLEVEL_DESTRUCT);
66 expairseq(expairseq const & other);
67 expairseq const & operator=(expairseq const & other);
69 void copy(expairseq const & other);
70 void destroy(bool call_parent)
72 if (call_parent) basic::destroy(call_parent);
77 expairseq(ex const & lh, ex const & rh);
78 expairseq(exvector const & v);
79 expairseq(epvector const & v, ex const & oc);
80 expairseq(epvector * vp, ex const & oc); // vp will be deleted
82 // functions overriding virtual functions from bases classes
84 basic * duplicate() const;
85 void printraw(ostream & os) const;
86 void printtree(ostream & os, unsigned indent) const;
87 void print(ostream & os, unsigned upper_precedence=0) const;
88 bool info(unsigned inf) const;
90 ex op(int const i) const;
91 ex & let_op(int const i);
92 ex eval(int level=0) const;
93 ex evalf(int level=0) const;
94 ex normal(lst &sym_lst, lst &repl_lst, int level=0) const;
95 ex diff(symbol const & s) const;
96 ex subs(lst const & ls, lst const & lr) const;
98 int compare_same_type(basic const & other) const;
99 bool is_equal_same_type(basic const & other) const;
100 unsigned return_type(void) const;
101 unsigned calchash(void) const;
102 ex expand(unsigned options=0) const;
104 // new virtual functions which can be overridden by derived classes
106 virtual ex thisexpairseq(epvector const & v, ex const & oc) const;
107 virtual ex thisexpairseq(epvector * vp, ex const & oc) const;
108 virtual void printseq(ostream & os, char delim, unsigned this_precedence,
109 unsigned upper_precedence) const;
110 virtual void printpair(ostream & os, expair const & p,
111 unsigned upper_precedence) const;
112 virtual expair split_ex_to_pair(ex const & e) const;
113 virtual expair combine_ex_with_coeff_to_pair(ex const & e,
115 virtual expair combine_pair_with_coeff_to_pair(expair const & p,
117 virtual ex recombine_pair_to_ex(expair const & p) const;
118 virtual bool expair_needs_further_processing(epp it);
119 virtual ex default_overall_coeff(void) const;
120 virtual void combine_overall_coeff(ex const & c);
121 virtual void combine_overall_coeff(ex const & c1, ex const & c2);
122 virtual bool can_make_flat(expair const & p) const;
124 // non-virtual functions in this class
126 void construct_from_2_ex_via_exvector(ex const & lh, ex const & rh);
127 void construct_from_2_ex(ex const & lh, ex const & rh);
128 void construct_from_2_expairseq(expairseq const & s1,
129 expairseq const & s2);
130 void construct_from_expairseq_ex(expairseq const & s,
132 void construct_from_exvector(exvector const & v);
133 void construct_from_epvector(epvector const & v);
134 void make_flat(exvector const & v);
135 void make_flat(epvector const & v);
136 epvector * bubblesort(epvector::iterator itbegin, epvector::iterator itend);
137 epvector * mergesort(epvector::iterator itbegin, epvector::iterator itend);
138 void canonicalize(void);
139 void combine_same_terms_sorted_seq(void);
140 #ifdef EXPAIRSEQ_USE_HASHTAB
141 void combine_same_terms(void);
142 unsigned calc_hashtabsize(unsigned sz) const;
143 unsigned calc_hashindex(ex const & e) const;
144 void shrink_hashtab(void);
145 void remove_hashtab_entry(epvector::const_iterator element);
146 void move_hashtab_entry(epvector::const_iterator oldpos,
147 epvector::iterator newpos);
148 void sorted_insert(epplist & eppl, epp elem);
149 void build_hashtab_and_combine(epvector::iterator & first_numeric,
150 epvector::iterator & last_non_zero,
151 vector<bool> & touched,
152 unsigned & number_of_zeroes);
153 void drop_coeff_0_terms(epvector::iterator & first_numeric,
154 epvector::iterator & last_non_zero,
155 vector<bool> & touched,
156 unsigned & number_of_zeroes);
157 bool has_coeff_0(void) const;
158 void add_numerics_to_hashtab(epvector::iterator first_numeric, epvector::const_iterator last_non_zero);
159 #endif // def EXPAIRSEQ_USE_HASHTAB
160 bool is_canonical() const;
161 epvector * expandchildren(unsigned options) const;
162 epvector * evalchildren(int level) const;
163 epvector evalfchildren(int level) const;
164 epvector normalchildren(int level) const;
165 epvector diffchildren(symbol const & s) const;
166 epvector * subschildren(lst const & ls, lst const & lr) const;
173 static unsigned precedence;
174 #ifdef EXPAIRSEQ_USE_HASHTAB
175 epplistvector hashtab;
176 unsigned hashtabsize;
178 static unsigned maxhashtabsize;
179 static unsigned minhashtabsize;
180 static unsigned hashtabfactor;
181 #endif // def EXPAIRSEQ_USE_HASHTAB
186 extern const expairseq some_expairseq;
187 extern type_info const & typeid_expairseq;
189 #define ex_to_expairseq(X) static_cast<expairseq const &>(*(X).bp)
191 #endif // ndef __GINAC_EXPAIRSEQ_H__