Added const_iterator, const_preorder_iterator, const_postorder_iterator. The
authorChristian Bauer <Christian.Bauer@uni-mainz.de>
Fri, 29 Aug 2003 21:29:14 +0000 (21:29 +0000)
committerChristian Bauer <Christian.Bauer@uni-mainz.de>
Fri, 29 Aug 2003 21:29:14 +0000 (21:29 +0000)
pre-/postorder iterators don't visit the root node; this should probably be
fixed. The ex::traverse*() functions can then be removed.

ginac/ex.h

index 70ce112dd799690cbfe73e04fa54b68d2924a4fb..6132960802d714e8dbb739dee66236ea3197b239 100644 (file)
@@ -26,6 +26,7 @@
 #include <iosfwd>
 #include <iterator>
 #include <functional>
 #include <iosfwd>
 #include <iterator>
 #include <functional>
+#include <stack>
 
 #include "basic.h"
 #include "ptr.h"
 
 #include "basic.h"
 #include "ptr.h"
@@ -53,6 +54,7 @@ static library_init library_initializer;
 
 
 class scalar_products;
 
 
 class scalar_products;
+class const_iterator;
 
 
 /** Lightweight wrapper for GiNaC's symbolic objects.  Basically all it does is
 
 
 /** Lightweight wrapper for GiNaC's symbolic objects.  Basically all it does is
@@ -91,140 +93,6 @@ public:
        ex(const std::string &s, const ex &l);
        
 public:
        ex(const std::string &s, const ex &l);
        
 public:
-       // Iterators
-       class const_iterator : public std::iterator<std::random_access_iterator_tag, ex, ptrdiff_t, const ex *, const ex &>
-       {
-               friend class ex;
-
-       public:
-               const_iterator() throw() {}
-               const_iterator(const basic *bp_, size_t i_) throw() : bp(bp_), i(i_) {}
-
-               bool operator==(const const_iterator &other) const throw()
-               {
-                       return bp == other.bp && i == other.i;
-               }
-
-               bool operator!=(const const_iterator &other) const throw()
-               {
-                       return !(*this == other);
-               }
-
-               bool operator<(const const_iterator &other) const throw()
-               {
-                       return i < other.i;
-               }
-
-               bool operator>(const const_iterator &other) const throw()
-               {
-                       return other < *this;
-               }
-
-               bool operator<=(const const_iterator &other) const throw()
-               {
-                       return !(other < *this);
-               }
-
-               bool operator>=(const const_iterator &other) const throw()
-               {
-                       return !(*this < other);
-               }
-
-               // This should return an ex&, but that would be a reference to a
-               // temporary value
-               ex operator*() const
-               {
-                       return bp->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
-               {
-                       return &(operator*());
-               }
-#endif
-
-               const_iterator &operator++() throw()
-               {
-                       ++i;
-                       return *this;
-               }
-
-               const_iterator operator++(int) throw()
-               {
-                       const_iterator tmp = *this;
-                       ++i;
-                       return tmp;
-               }
-
-               const_iterator &operator+=(difference_type n) throw()
-               {
-                       i += n;
-                       return *this;
-               }
-
-               const_iterator operator+(difference_type n) const throw()
-               {
-                       return const_iterator(bp, i + n);
-               }
-
-               inline friend const_iterator operator+(difference_type n, const const_iterator &it) throw()
-               {
-                       return const_iterator(it.bp, it.i + n);
-               }
-
-               const_iterator &operator--() throw()
-               {
-                       --i;
-                       return *this;
-               }
-
-               const_iterator operator--(int) throw()
-               {
-                       const_iterator tmp = *this;
-                       --i;
-                       return tmp;
-               }
-
-               const_iterator &operator-=(difference_type n) throw()
-               {
-                       i -= n;
-                       return *this;
-               }
-
-               const_iterator operator-(difference_type n) const throw()
-               {
-                       return const_iterator(bp, i - n);
-               }
-
-               inline friend difference_type operator-(const const_iterator &lhs, const const_iterator &rhs) throw()
-               {
-                       return lhs.i - rhs.i;
-               }
-
-               ex operator[](difference_type n) const
-               {
-                       return bp->op(i + n);
-               }
-
-       protected:
-               const basic *bp;
-               size_t i;
-       };
-
-       const_iterator begin() const throw() { return const_iterator(get_pointer(bp), 0); }
-       const_iterator end() const throw() { return const_iterator(get_pointer(bp), bp->nops()); }
-
-#if 0
-       // This doesn't work because of the "reference to temporary" problem
-       // in operator*()
-       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-       const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
-       const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
-#endif
-
        // non-virtual functions in this class
 public:
        /** Efficiently swap the contents of two expressions. */
        // non-virtual functions in this class
 public:
        /** Efficiently swap the contents of two expressions. */
@@ -235,6 +103,10 @@ public:
                bp.swap(other.bp);
        }
 
                bp.swap(other.bp);
        }
 
+       // iterators
+       const_iterator begin() const throw();
+       const_iterator end() const throw();
+
        // evaluation
        ex eval(int level = 0) const { return bp->eval(level); }
        ex evalf(int level = 0) const { return bp->evalf(level); }
        // evaluation
        ex eval(int level = 0) const { return bp->eval(level); }
        ex evalf(int level = 0) const { return bp->evalf(level); }
@@ -502,6 +374,298 @@ bool ex::is_equal(const ex & other) const
 }
 
 
 }
 
 
+// Iterators
+
+class const_iterator : public std::iterator<std::random_access_iterator_tag, ex, ptrdiff_t, const ex *, const ex &>
+{
+       friend class ex;
+       friend class const_preorder_iterator;
+       friend class const_postorder_iterator;
+
+public:
+       const_iterator() throw() {}
+
+private:
+       const_iterator(const ex &e_, size_t i_) throw() : e(e_), i(i_) {}
+
+public:
+       // This should return an ex&, but that would be a reference to a
+       // temporary value
+       ex operator*() const
+       {
+               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
+       {
+               return &(operator*());
+       }
+#endif
+
+       ex operator[](difference_type n) const
+       {
+               return e.op(i + n);
+       }
+
+       const_iterator &operator++() throw()
+       {
+               ++i;
+               return *this;
+       }
+
+       const_iterator operator++(int) throw()
+       {
+               const_iterator tmp = *this;
+               ++i;
+               return tmp;
+       }
+
+       const_iterator &operator+=(difference_type n) throw()
+       {
+               i += n;
+               return *this;
+       }
+
+       const_iterator operator+(difference_type n) const throw()
+       {
+               return const_iterator(e, i + n);
+       }
+
+       inline friend const_iterator operator+(difference_type n, const const_iterator &it) throw()
+       {
+               return const_iterator(it.e, it.i + n);
+       }
+
+       const_iterator &operator--() throw()
+       {
+               --i;
+               return *this;
+       }
+
+       const_iterator operator--(int) throw()
+       {
+               const_iterator tmp = *this;
+               --i;
+               return tmp;
+       }
+
+       const_iterator &operator-=(difference_type n) throw()
+       {
+               i -= n;
+               return *this;
+       }
+
+       const_iterator operator-(difference_type n) const throw()
+       {
+               return const_iterator(e, i - n);
+       }
+
+       inline friend difference_type operator-(const const_iterator &lhs, const const_iterator &rhs) throw()
+       {
+               return lhs.i - rhs.i;
+       }
+
+       bool operator==(const const_iterator &other) const throw()
+       {
+               return are_ex_trivially_equal(e, other.e) && i == other.i;
+       }
+
+       bool operator!=(const const_iterator &other) const throw()
+       {
+               return !(*this == other);
+       }
+
+       bool operator<(const const_iterator &other) const throw()
+       {
+               return i < other.i;
+       }
+
+       bool operator>(const const_iterator &other) const throw()
+       {
+               return other < *this;
+       }
+
+       bool operator<=(const const_iterator &other) const throw()
+       {
+               return !(other < *this);
+       }
+
+       bool operator>=(const const_iterator &other) const throw()
+       {
+               return !(*this < other);
+       }
+
+protected:
+       ex e; // this used to be a "const basic *", but in view of object fusion that wouldn't be safe
+       size_t i;
+};
+
+namespace internal {
+
+struct _iter_rep {
+       _iter_rep(const ex &e_, size_t i_, size_t i_end_) : e(e_), i(i_), i_end(i_end_) {}
+
+       bool operator==(const _iter_rep &other) const throw()
+       {
+               return are_ex_trivially_equal(e, other.e) && i == other.i;
+       }
+
+       bool operator!=(const _iter_rep &other) const throw()
+       {
+               return !(*this == other);
+       }
+
+       ex e;
+       size_t i;
+       size_t i_end;
+};
+
+} // namespace internal
+
+class const_preorder_iterator : public std::iterator<std::forward_iterator_tag, ex, ptrdiff_t, const ex *, const ex &>
+{
+public:
+       const_preorder_iterator() throw() {}
+
+       // Provide implicit conversion from const_iterator, so begin() and
+       // 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()));
+       }
+
+public:
+       ex operator*() const
+       {
+               const internal::_iter_rep & r = s.top();
+               return r.e.op(r.i);
+       }
+
+       // operator->() not implemented (see above)
+
+       const_preorder_iterator &operator++()
+       {
+               increment();
+               return *this;
+       }
+
+       const_preorder_iterator operator++(int)
+       {
+               const_preorder_iterator tmp = *this;
+               increment();
+               return tmp;
+       }
+
+       bool operator==(const const_preorder_iterator &other) const throw()
+       {
+               return s == other.s;
+       }
+
+       bool operator!=(const const_preorder_iterator &other) const throw()
+       {
+               return !(*this == other);
+       }
+
+private:
+       std::stack<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;
+               }
+       }
+};
+
+class const_postorder_iterator : public std::iterator<std::forward_iterator_tag, ex, ptrdiff_t, const ex *, const ex &>
+{
+public:
+       const_postorder_iterator() throw() {}
+
+       // Provide implicit conversion from const_iterator, so begin() and
+       // 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();
+       }
+
+public:
+       ex operator*() const
+       {
+               const internal::_iter_rep & r = s.top();
+               return r.e.op(r.i);
+       }
+
+       // operator->() not implemented
+
+       const_postorder_iterator &operator++()
+       {
+               increment();
+               return *this;
+       }
+
+       const_postorder_iterator operator++(int)
+       {
+               const_postorder_iterator tmp = *this;
+               increment();
+               return tmp;
+       }
+
+       bool operator==(const const_postorder_iterator &other) const throw()
+       {
+               return s == other.s;
+       }
+
+       bool operator!=(const const_postorder_iterator &other) const throw()
+       {
+               return !(*this == other);
+       }
+
+private:
+       std::stack<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();
+                       const ex & child = current.e.op(current.i);
+                       s.push(internal::_iter_rep(child, 0, child.nops()));
+               }
+       }
+
+       void increment()
+       {
+               ++s.top().i;
+               descend();
+               if (s.top().i == s.top().i_end && s.size() > 1)
+                       s.pop();
+       }
+};
+
+inline const_iterator ex::begin() const throw()
+{
+       return const_iterator(*this, 0);
+}
+
+inline const_iterator ex::end() const throw()
+{
+       return const_iterator(*this, nops());
+}
+
+
 // utility functions
 
 /** Compare two objects of class quickly without doing a deep tree traversal.
 // utility functions
 
 /** Compare two objects of class quickly without doing a deep tree traversal.