- if (seq.size()<=1) return 1;
-
-#ifdef EXPAIRSEQ_USE_HASHTAB
- if (hashtabsize>0) return 1; // not canoncalized
-#endif // def EXPAIRSEQ_USE_HASHTAB
-
- epvector::const_iterator it=seq.begin();
- epvector::const_iterator it_last=it;
- for (++it; it!=seq.end(); it_last=it, ++it) {
- if (!((*it_last).is_less(*it)||(*it_last).is_equal(*it))) {
- if (!is_ex_exactly_of_type((*it_last).rest,numeric)||
- !is_ex_exactly_of_type((*it).rest,numeric)) {
- // double test makes it easier to set a breakpoint...
- if (!is_ex_exactly_of_type((*it_last).rest,numeric)||
- !is_ex_exactly_of_type((*it).rest,numeric)) {
- printpair(cout,*it_last,0);
- cout << ">";
- printpair(cout,*it,0);
- cout << "\n";
- cout << "pair1:" << endl;
- (*it_last).rest.printtree(cout);
- (*it_last).coeff.printtree(cout);
- cout << "pair2:" << endl;
- (*it).rest.printtree(cout);
- (*it).coeff.printtree(cout);
- return 0;
- }
- }
- }
- }
- return 1;
-}
-
-epvector * expairseq::expandchildren(unsigned options) const
-{
- epvector::const_iterator last=seq.end();
- epvector::const_iterator cit=seq.begin();
- while (cit!=last) {
- ex const & expanded_ex=(*cit).rest.expand(options);
- if (!are_ex_trivially_equal((*cit).rest,expanded_ex)) {
-
- // something changed, copy seq, eval and return it
- epvector *s=new epvector;
- s->reserve(seq.size());
-
- // copy parts of seq which are known not to have changed
- epvector::const_iterator cit2=seq.begin();
- while (cit2!=cit) {
- s->push_back(*cit2);
- ++cit2;
- }
- // copy first changed element
- s->push_back(combine_ex_with_coeff_to_pair(expanded_ex,
- (*cit2).coeff));
- ++cit2;
- // copy rest
- while (cit2!=last) {
- s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.expand(options),
- (*cit2).coeff));
- ++cit2;
- }
- return s;
- }
- ++cit;
- }
-
- return 0; // nothing has changed
-}
-
-epvector * expairseq::evalchildren(int level) const
-{
- // returns a NULL pointer if nothing had to be evaluated
- // returns a pointer to a newly created epvector otherwise
- // (which has to be deleted somewhere else)
-
- if (level==1) {
- return 0;
- }
- if (level == -max_recursion_level) {
- throw(std::runtime_error("max recursion level reached"));
- }
-
- --level;
- epvector::const_iterator last=seq.end();
- epvector::const_iterator cit=seq.begin();
- while (cit!=last) {
- ex const & evaled_ex=(*cit).rest.eval(level);
- if (!are_ex_trivially_equal((*cit).rest,evaled_ex)) {
-
- // something changed, copy seq, eval and return it
- epvector *s=new epvector;
- s->reserve(seq.size());
-
- // copy parts of seq which are known not to have changed
- epvector::const_iterator cit2=seq.begin();
- while (cit2!=cit) {
- s->push_back(*cit2);
- ++cit2;
- }
- // copy first changed element
- s->push_back(combine_ex_with_coeff_to_pair(evaled_ex,
- (*cit2).coeff));
- ++cit2;
- // copy rest
- while (cit2!=last) {
- s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.eval(level),
- (*cit2).coeff));
- ++cit2;
- }
- return s;
- }
- ++cit;
- }
-
- return 0; // nothing has changed
-}
-
-epvector expairseq::evalfchildren(int level) const
-{
- epvector s;
- s.reserve(seq.size());
-
- if (level==1) {
- return seq;
- }
- if (level == -max_recursion_level) {
- throw(std::runtime_error("max recursion level reached"));
- }
- --level;
- for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
- s.push_back(combine_ex_with_coeff_to_pair((*it).rest.evalf(level),
- (*it).coeff));
- }
- return s;
-}
-
-epvector expairseq::normalchildren(int level) const
-{
- epvector s;
- s.reserve(seq.size());
-
- if (level==1) {
- return seq;
- }
- if (level == -max_recursion_level) {
- throw(std::runtime_error("max recursion level reached"));
- }
- --level;
- for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
- s.push_back(combine_ex_with_coeff_to_pair((*it).rest.normal(level),
- (*it).coeff));
- }
- return s;
-}
-
-epvector expairseq::diffchildren(symbol const & y) const
-{
- epvector s;
- s.reserve(seq.size());
-
- for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
- s.push_back(combine_ex_with_coeff_to_pair((*it).rest.diff(y),
- (*it).coeff));
- }
- return s;
-}
-
-epvector * expairseq::subschildren(lst const & ls, lst const & lr) const
-{
- // returns a NULL pointer if nothing had to be substituted
- // returns a pointer to a newly created epvector otherwise
- // (which has to be deleted somewhere else)
-
- epvector::const_iterator last=seq.end();
- epvector::const_iterator cit=seq.begin();
- while (cit!=last) {
- ex const & subsed_ex=(*cit).rest.subs(ls,lr);
- if (!are_ex_trivially_equal((*cit).rest,subsed_ex)) {
-
- // something changed, copy seq, subs and return it
- epvector *s=new epvector;
- s->reserve(seq.size());
-
- // copy parts of seq which are known not to have changed
- epvector::const_iterator cit2=seq.begin();
- while (cit2!=cit) {
- s->push_back(*cit2);
- ++cit2;
- }
- // copy first changed element
- s->push_back(combine_ex_with_coeff_to_pair(subsed_ex,
- (*cit2).coeff));
- ++cit2;
- // copy rest
- while (cit2!=last) {
- s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.subs(ls,lr),
- (*cit2).coeff));
- ++cit2;
- }
- return s;
- }
- ++cit;
- }
-
- return 0; // nothing has changed
-}
-
-/*
-epvector expairseq::subschildren(lst const & ls, lst const & lr) const
-{
- epvector s;
- s.reserve(seq.size());
-
- for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
- s.push_back(split_ex_to_pair((*it).rest.subs(ls,lr),(*it).coeff));
- }
- return s;
-}
-*/
-
-/*
-void expairseq::sort(epviter first, epviter last, expair_is_less comp)
-{
- if (first != last) {
- introsort_loop(first, last, lg(last - first) * 2, comp);
- __final_insertion_sort(first, last, comp);
- }
-}
-
-ptrdiff_t expairseq::lg(ptrdiff_t n)
-{
- ptrdiff_t k;
- for (k = 0; n > 1; n >>= 1) ++k;
- return k;
-}
-
-void expairseq::introsort_loop(epviter first, epviter last,
- ptrdiff_t depth_limit, expair_is_less comp)
-{
- while (last - first > stl_threshold) {
- if (depth_limit == 0) {
- partial_sort(first, last, last, comp);
- return;
- }
- --depth_limit;
- epviter cut = unguarded_partition(first, last,
- expair(__median(*first, *(first + (last - first)/2),
- *(last - 1), comp)), comp);
- introsort_loop(cut, last, depth_limit, comp);
- last = cut;
- }
-}
-
-epviter expairseq::unguarded_partition(epviter first, epviter last,
- expair pivot, expair_is_less comp)
-{
- while (1) {
- while (comp(*first, pivot)) ++first;
- --last;
- while (comp(pivot, *last)) --last;
- if (!(first < last)) return first;
- iter_swap(first, last);
- ++first;
- }
-}
-
-void expairseq::partial_sort(epviter first, epviter middle, epviter last,
- expair_is_less comp) {
- make_heap(first, middle, comp);
- for (RandomAccessIterator i = middle; i < last; ++i)
- if (comp(*i, *first))
- __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
- sort_heap(first, middle, comp);
+ if (seq.size() <= 1)
+ return 1;
+
+#if EXPAIRSEQ_USE_HASHTAB
+ if (hashtabsize > 0) return 1; // not canoncalized
+#endif // EXPAIRSEQ_USE_HASHTAB
+
+ epvector::const_iterator it = seq.begin(), itend = seq.end();
+ epvector::const_iterator it_last = it;
+ for (++it; it!=itend; it_last=it, ++it) {
+ if (!(it_last->is_less(*it) || it_last->is_equal(*it))) {
+ if (!is_exactly_a<numeric>(it_last->rest) ||
+ !is_exactly_a<numeric>(it->rest)) {
+ // double test makes it easier to set a breakpoint...
+ if (!is_exactly_a<numeric>(it_last->rest) ||
+ !is_exactly_a<numeric>(it->rest)) {
+ printpair(std::clog, *it_last, 0);
+ std::clog << ">";
+ printpair(std::clog, *it, 0);
+ std::clog << "\n";
+ std::clog << "pair1:" << std::endl;
+ it_last->rest.print(print_tree(std::clog));
+ it_last->coeff.print(print_tree(std::clog));
+ std::clog << "pair2:" << std::endl;
+ it->rest.print(print_tree(std::clog));
+ it->coeff.print(print_tree(std::clog));
+ return 0;
+ }
+ }
+ }
+ }
+ return 1;
+}
+
+
+/** Member-wise expand the expairs in this sequence.
+ *
+ * @see expairseq::expand()
+ * @return pointer to epvector containing expanded pairs or zero pointer,
+ * if no members were changed. */
+std::auto_ptr<epvector> expairseq::expandchildren(unsigned options) const
+{
+ const epvector::const_iterator last = seq.end();
+ epvector::const_iterator cit = seq.begin();
+ while (cit!=last) {
+ const ex &expanded_ex = cit->rest.expand(options);
+ if (!are_ex_trivially_equal(cit->rest,expanded_ex)) {
+
+ // something changed, copy seq, eval and return it
+ std::auto_ptr<epvector> s(new epvector);
+ s->reserve(seq.size());
+
+ // copy parts of seq which are known not to have changed
+ epvector::const_iterator cit2 = seq.begin();
+ while (cit2!=cit) {
+ s->push_back(*cit2);
+ ++cit2;
+ }
+
+ // copy first changed element
+ s->push_back(combine_ex_with_coeff_to_pair(expanded_ex,
+ cit2->coeff));
+ ++cit2;
+
+ // copy rest
+ while (cit2!=last) {
+ s->push_back(combine_ex_with_coeff_to_pair(cit2->rest.expand(options),
+ cit2->coeff));
+ ++cit2;
+ }
+ return s;
+ }
+ ++cit;
+ }
+
+ return std::auto_ptr<epvector>(0); // signalling nothing has changed
+}
+
+
+/** Member-wise evaluate the expairs in this sequence.
+ *
+ * @see expairseq::eval()
+ * @return pointer to epvector containing evaluated pairs or zero pointer,
+ * if no members were changed. */
+std::auto_ptr<epvector> expairseq::evalchildren(int level) const
+{
+ // returns a NULL pointer if nothing had to be evaluated
+ // returns a pointer to a newly created epvector otherwise
+ // (which has to be deleted somewhere else)
+
+ if (level==1)
+ return std::auto_ptr<epvector>(0);
+
+ if (level == -max_recursion_level)
+ throw(std::runtime_error("max recursion level reached"));
+
+ --level;
+ epvector::const_iterator last = seq.end();
+ epvector::const_iterator cit = seq.begin();
+ while (cit!=last) {
+ const ex &evaled_ex = cit->rest.eval(level);
+ if (!are_ex_trivially_equal(cit->rest,evaled_ex)) {
+
+ // something changed, copy seq, eval and return it
+ std::auto_ptr<epvector> s(new epvector);
+ s->reserve(seq.size());
+
+ // copy parts of seq which are known not to have changed
+ epvector::const_iterator cit2=seq.begin();
+ while (cit2!=cit) {
+ s->push_back(*cit2);
+ ++cit2;
+ }
+
+ // copy first changed element
+ s->push_back(combine_ex_with_coeff_to_pair(evaled_ex,
+ cit2->coeff));
+ ++cit2;
+
+ // copy rest
+ while (cit2!=last) {
+ s->push_back(combine_ex_with_coeff_to_pair(cit2->rest.eval(level),
+ cit2->coeff));
+ ++cit2;
+ }
+ return s;
+ }
+ ++cit;
+ }
+
+ return std::auto_ptr<epvector>(0); // signalling nothing has changed
+}
+
+
+/** Member-wise substitute in this sequence.
+ *
+ * @see expairseq::subs()
+ * @return pointer to epvector containing pairs after application of subs,
+ * or NULL pointer if no members were changed. */
+std::auto_ptr<epvector> expairseq::subschildren(const exmap & m, unsigned options) const
+{
+ // When any of the objects to be substituted is a product or power
+ // we have to recombine the pairs because the numeric coefficients may
+ // be part of the search pattern.
+ if (!(options & (subs_options::pattern_is_product | subs_options::pattern_is_not_product))) {
+
+ // Search the list of substitutions and cache our findings
+ for (exmap::const_iterator it = m.begin(); it != m.end(); ++it) {
+ if (is_exactly_a<mul>(it->first) || is_exactly_a<power>(it->first)) {
+ options |= subs_options::pattern_is_product;
+ break;
+ }
+ }
+ if (!(options & subs_options::pattern_is_product))
+ options |= subs_options::pattern_is_not_product;
+ }
+
+ if (options & subs_options::pattern_is_product) {
+
+ // Substitute in the recombined pairs
+ epvector::const_iterator cit = seq.begin(), last = seq.end();
+ while (cit != last) {
+
+ const ex &orig_ex = recombine_pair_to_ex(*cit);
+ const ex &subsed_ex = orig_ex.subs(m, options);
+ if (!are_ex_trivially_equal(orig_ex, subsed_ex)) {
+
+ // Something changed, copy seq, subs and return it
+ std::auto_ptr<epvector> s(new epvector);
+ s->reserve(seq.size());
+
+ // Copy parts of seq which are known not to have changed
+ s->insert(s->begin(), seq.begin(), cit);
+
+ // Copy first changed element
+ s->push_back(split_ex_to_pair(subsed_ex));
+ ++cit;
+
+ // Copy rest
+ while (cit != last) {
+ s->push_back(split_ex_to_pair(recombine_pair_to_ex(*cit).subs(m, options)));
+ ++cit;
+ }
+ return s;
+ }
+
+ ++cit;
+ }
+
+ } else {
+
+ // Substitute only in the "rest" part of the pairs
+ epvector::const_iterator cit = seq.begin(), last = seq.end();
+ while (cit != last) {
+
+ const ex &subsed_ex = cit->rest.subs(m, options);
+ if (!are_ex_trivially_equal(cit->rest, subsed_ex)) {
+
+ // Something changed, copy seq, subs and return it
+ std::auto_ptr<epvector> s(new epvector);
+ s->reserve(seq.size());
+
+ // Copy parts of seq which are known not to have changed
+ s->insert(s->begin(), seq.begin(), cit);
+
+ // Copy first changed element
+ s->push_back(combine_ex_with_coeff_to_pair(subsed_ex, cit->coeff));
+ ++cit;
+
+ // Copy rest
+ while (cit != last) {
+ s->push_back(combine_ex_with_coeff_to_pair(cit->rest.subs(m, options),
+ cit->coeff));
+ ++cit;
+ }
+ return s;
+ }
+
+ ++cit;
+ }
+ }
+
+ // Nothing has changed
+ return std::auto_ptr<epvector>(0);