Improved the pre-/postorder iterators: They visit the root node and are now

[ginac.git] / ginac / ex.h

diff --git a/ginac/ex.h b/ginac/ex.h
index d3c801e2a1839fd9e8995deccdff45614ae76a1a..9bfa9e990fbdcee80f115f68c335f797019a4c5e 100644 (file)
--- a/ginac/ex.h
+++ b/ginac/ex.h
@@ -170,8 +170,10 @@ public:
 
        // rational functions
        ex normal(int level = 0) const;
-       ex to_rational(lst &repl_lst) const;
-       ex to_polynomial(lst &repl_lst) const;
+       ex to_rational(exmap & repl) const;
+       ex to_rational(lst & repl_lst) const;
+       ex to_polynomial(exmap & repl) const;
+       ex to_polynomial(lst & repl_lst) const;
        ex numer() const;
        ex denom() const;
        ex numer_denom() const;
@@ -396,14 +398,12 @@ public:
                return e.op(i);
        }
 
-#if 0
-       // How do we make this work in the context of the "reference to
-       // temporary" problem? Return an auto_ptr?
-       pointer operator->() const
+       // This should return an ex*, but that would be a pointer to a
+       // temporary value
+       std::auto_ptr<ex> operator->() const
        {
-               return &(operator*());
+               return std::auto_ptr<ex>(new ex(operator*()));
        }
-#endif
 
        ex operator[](difference_type n) const
        {
@@ -530,8 +530,8 @@ class const_preorder_iterator : public std::iterator<std::forward_iterator_tag,
 public:
        const_preorder_iterator() throw() {}
 
-       // Provide implicit conversion from const_iterator, so begin() and
-       // end() can be used to create const_preorder_iterators
+       // Provide implicit conversion from const_iterator, so ex::begin() and
+       // ex::end() can be used to create const_preorder_iterators
        const_preorder_iterator(const const_iterator & cit)
        {
                s.push(internal::_iter_rep(cit.e, cit.i, cit.e.nops()));
@@ -540,11 +540,13 @@ public:
 public:
        ex operator*() const
        {
-               const internal::_iter_rep & r = s.top();
-               return r.e.op(r.i);
+               return s.top().e;
        }
 
-       // operator->() not implemented (see above)
+       std::auto_ptr<ex> operator->() const
+       {
+               return std::auto_ptr<ex>(new ex(operator*()));
+       }
 
        const_preorder_iterator &operator++()
        {
@@ -561,7 +563,7 @@ public:
 
        bool operator==(const const_preorder_iterator &other) const throw()
        {
-               return s == other.s;
+               return s.top() == other.s.top();
        }
 
        bool operator!=(const const_preorder_iterator &other) const throw()
@@ -570,22 +572,21 @@ public:
        }
 
 private:
-       std::stack<internal::_iter_rep> s;
+       std::stack<internal::_iter_rep, std::vector<internal::_iter_rep> > s;
 
        void increment()
        {
-               internal::_iter_rep & current = s.top();
-               const ex & child = current.e.op(current.i);
-               size_t n = child.nops();
-               if (n)
-                       s.push(internal::_iter_rep(child, 0, n));
-               else
-                       ++current.i;
-
                while (s.top().i == s.top().i_end && s.size() > 1) {
                        s.pop();
                        ++s.top().i;
                }
+
+               internal::_iter_rep & current = s.top();
+
+               if (current.i != current.i_end) {
+                       const ex & child = current.e.op(current.i);
+                       s.push(internal::_iter_rep(child, 0, child.nops()));
+               }
        }
 };
 
@@ -594,22 +595,27 @@ class const_postorder_iterator : public std::iterator<std::forward_iterator_tag,
 public:
        const_postorder_iterator() throw() {}
 
-       // Provide implicit conversion from const_iterator, so begin() and
-       // end() can be used to create const_postorder_iterators
+       // Provide implicit conversion from const_iterator, so ex::begin() and
+       // ex::end() can be used to create const_postorder_iterators
        const_postorder_iterator(const const_iterator & cit)
        {
-               s.push(internal::_iter_rep(cit.e, cit.i, cit.e.nops()));
-               descend();
+               size_t n = cit.e.nops();
+               if (cit.i != n) {
+                       s.push(internal::_iter_rep(cit.e, cit.i, n));
+                       descend();
+               }
        }
 
 public:
        ex operator*() const
        {
-               const internal::_iter_rep & r = s.top();
-               return r.e.op(r.i);
+               return s.top().e;
        }
 
-       // operator->() not implemented
+       std::auto_ptr<ex> operator->() const
+       {
+               return std::auto_ptr<ex>(new ex(operator*()));
+       }
 
        const_postorder_iterator &operator++()
        {
@@ -635,12 +641,12 @@ public:
        }
 
 private:
-       std::stack<internal::_iter_rep> s;
+       std::stack<internal::_iter_rep, std::vector<internal::_iter_rep> > s;
 
        void descend()
        {
-               while (s.top().i != s.top().i_end && s.top().e.op(s.top().i).nops() > 0) {
-                       const internal::_iter_rep & current = s.top();
+               while (s.top().i != s.top().i_end) {
+                       internal::_iter_rep & current = s.top();
                        const ex & child = current.e.op(current.i);
                        s.push(internal::_iter_rep(child, 0, child.nops()));
                }
@@ -648,10 +654,12 @@ private:
 
        void increment()
        {
-               ++s.top().i;
-               descend();
-               if (s.top().i == s.top().i_end && s.size() > 1)
+               if (s.top().i == s.top().i_end)
                        s.pop();
+               if (s.size() > 0) {
+                       ++s.top().i;
+                       descend();
+               }
        }
 };
 
@@ -677,6 +685,23 @@ inline bool are_ex_trivially_equal(const ex &e1, const ex &e2)
        return e1.bp == e2.bp;
 }
 
+/* Function objects for STL sort() etc. */
+struct ex_is_less : public std::binary_function<ex, ex, bool> {
+       bool operator() (const ex &lh, const ex &rh) const { return lh.compare(rh) < 0; }
+};
+
+struct ex_is_equal : public std::binary_function<ex, ex, bool> {
+       bool operator() (const ex &lh, const ex &rh) const { return lh.is_equal(rh); }
+};
+
+struct op0_is_equal : public std::binary_function<ex, ex, bool> {
+       bool operator() (const ex &lh, const ex &rh) const { return lh.op(0).is_equal(rh.op(0)); }
+};
+
+struct ex_swap : public std::binary_function<ex, ex, void> {
+       void operator() (ex &lh, ex &rh) const { lh.swap(rh); }
+};
+
 // wrapper functions around member functions
 inline size_t nops(const ex & thisex)
 { return thisex.nops(); }
@@ -714,6 +739,12 @@ inline ex normal(const ex & thisex, int level=0)
 inline ex to_rational(const ex & thisex, lst & repl_lst)
 { return thisex.to_rational(repl_lst); }
 
+inline ex to_rational(const ex & thisex, exmap & repl)
+{ return thisex.to_rational(repl); }
+
+inline ex to_polynomial(const ex & thisex, exmap & repl)
+{ return thisex.to_polynomial(repl); }
+
 inline ex to_polynomial(const ex & thisex, lst & repl_lst)
 { return thisex.to_polynomial(repl_lst); }
 
@@ -777,23 +808,6 @@ inline bool is_zero(const ex & thisex)
 inline void swap(ex & e1, ex & e2)
 { e1.swap(e2); }
 
-/* Function objects for STL sort() etc. */
-struct ex_is_less : public std::binary_function<ex, ex, bool> {
-       bool operator() (const ex &lh, const ex &rh) const { return lh.compare(rh) < 0; }
-};
-
-struct ex_is_equal : public std::binary_function<ex, ex, bool> {
-       bool operator() (const ex &lh, const ex &rh) const { return lh.is_equal(rh); }
-};
-
-struct op0_is_equal : public std::binary_function<ex, ex, bool> {
-       bool operator() (const ex &lh, const ex &rh) const { return lh.op(0).is_equal(rh.op(0)); }
-};
-
-struct ex_swap : public std::binary_function<ex, ex, void> {
-       void operator() (ex &lh, ex &rh) const { lh.swap(rh); }
-};
-
 inline ex ex::subs(const exmap & m, unsigned options) const
 {
        return bp->subs(m, options);