X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fex.h;h=2447c3f268061bd77ab59f58f5f01c21777c5be0;hp=30a009eb80dde265b52a66017f65f31a09a8dc03;hb=ffad02322624ab79fdad1a23a3aa83cd67376151;hpb=3fb7166724ec9a4e5acac793f42c347da9aa9a87

diff --git a/ginac/ex.h b/ginac/ex.h
index 30a009eb..2447c3f2 100644
--- a/ginac/ex.h
+++ b/ginac/ex.h
@@ -26,6 +26,7 @@
 #include <iosfwd>
 #include <iterator>
 #include <functional>
+#include <stack>
 
 #include "basic.h"
 #include "ptr.h"
@@ -53,6 +54,7 @@ static library_init library_initializer;
 
 
 class scalar_products;
+class const_iterator;
 
 
 /** Lightweight wrapper for GiNaC's symbolic objects.  Basically all it does is
@@ -62,14 +64,14 @@ class scalar_products;
 class ex
 {
 	friend class archive_node;
-	friend bool are_ex_trivially_equal(const ex &, const ex &);
-	template<class T> friend const T &ex_to(const ex &);
-	template<class T> friend bool is_a(const ex &);
-	template<class T> friend bool is_exactly_a(const ex &);
+	friend inline bool are_ex_trivially_equal(const ex &, const ex &);
+	template<class T> friend inline const T &ex_to(const ex &);
+	template<class T> friend inline bool is_a(const ex &);
+	template<class T> friend inline bool is_exactly_a(const ex &);
 	
 	// default constructor, copy constructor and assignment operator
 public:
-	ex();
+	ex() throw();
 #ifdef OBSCURE_CINT_HACK
 	ex(const ex & other);
 	ex & operator=(const ex & other);
@@ -91,149 +93,20 @@ 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() {}
-		const_iterator(const basic *bp_, size_t i_) : bp(bp_), i(i_) {}
-
-		bool operator==(const const_iterator &other) const
-		{
-			return bp == other.bp && i == other.i;
-		}
-
-		bool operator!=(const const_iterator &other) const
-		{
-			return !(*this == other);
-		}
-
-		bool operator<(const const_iterator &other) const
-		{
-			return i < other.i;
-		}
-
-		bool operator>(const const_iterator &other) const
-		{
-			return other < *this;
-		}
-
-		bool operator<=(const const_iterator &other) const
-		{
-			return !(other < *this);
-		}
-
-		bool operator>=(const const_iterator &other) const
-		{
-			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++()
-		{
-			++i;
-			return *this;
-		}
-
-		const_iterator operator++(int)
-		{
-			const_iterator tmp = *this;
-			++i;
-			return tmp;
-		}
-
-		const_iterator &operator+=(difference_type n)
-		{
-			i += n;
-			return *this;
-		}
-
-		const_iterator operator+(difference_type n) const
-		{
-			return const_iterator(bp, i + n);
-		}
-
-		inline friend const_iterator operator+(difference_type n, const const_iterator &it)
-		{
-			return const_iterator(it.bp, it.i + n);
-		}
-
-		const_iterator &operator--()
-		{
-			--i;
-			return *this;
-		}
-
-		const_iterator operator--(int)
-		{
-			const_iterator tmp = *this;
-			--i;
-			return tmp;
-		}
-
-		const_iterator &operator-=(difference_type n)
-		{
-			i -= n;
-			return *this;
-		}
-
-		const_iterator operator-(difference_type n) const
-		{
-			return const_iterator(bp, i - n);
-		}
-
-		inline friend difference_type operator-(const const_iterator &lhs, const const_iterator &rhs)
-		{
-			return lhs.i - rhs.i;
-		}
-
-		reference operator[](difference_type n) const
-		{
-		}
-
-	protected:
-		const basic *bp;
-		size_t i;
-	};
-
-	const_iterator begin() const { return const_iterator(get_pointer(bp), 0); }
-	const_iterator end() const { 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. */
-	void swap(ex & other)
+	void swap(ex & other) throw()
 	{
 		GINAC_ASSERT(bp->flags & status_flags::dynallocated);
 		GINAC_ASSERT(other.bp->flags & status_flags::dynallocated);
 		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); }
@@ -297,25 +170,27 @@ 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;
 
 	// polynomial algorithms
-	ex unit(const symbol &x) const;
-	ex content(const symbol &x) const;
+	ex unit(const ex &x) const;
+	ex content(const ex &x) const;
 	numeric integer_content() const;
-	ex primpart(const symbol &x) const;
-	ex primpart(const symbol &x, const ex &cont) const;
+	ex primpart(const ex &x) const;
+	ex primpart(const ex &x, const ex &cont) const;
 	ex smod(const numeric &xi) const { return bp->smod(xi); }
 	numeric max_coefficient() const;
 
 	// indexed objects
 	exvector get_free_indices() const { return bp->get_free_indices(); }
-	ex simplify_indexed() const;
-	ex simplify_indexed(const scalar_products & sp) const;
+	ex simplify_indexed(unsigned options = 0) const;
+	ex simplify_indexed(const scalar_products & sp, unsigned options = 0) const;
 
 	// comparison
 	int compare(const ex & other) const;
@@ -345,6 +220,7 @@ private:
 	static basic & construct_from_double(double d);
 	static ptr<basic> construct_from_string_and_lst(const std::string &s, const ex &l);
 	void makewriteable();
+	void share(const ex & other) const;
 
 #ifdef OBSCURE_CINT_HACK
 public:
@@ -368,7 +244,7 @@ protected:
 // member variables
 
 private:
-	ptr<basic> bp;      ///< pointer to basic object managed by this
+	mutable ptr<basic> bp;  ///< pointer to basic object managed by this
 
 #ifdef OBSCURE_CINT_HACK
 public:
@@ -386,7 +262,7 @@ public:
 extern const basic *_num0_bp;
 
 inline
-ex::ex() : bp(*const_cast<basic *>(_num0_bp))
+ex::ex() throw() : bp(*const_cast<basic *>(_num0_bp))
 {
 	GINAC_ASSERT(bp->flags & status_flags::dynallocated);
 #ifdef OBSCURE_CINT_HACK
@@ -481,7 +357,14 @@ int ex::compare(const ex & other) const
 {
 	if (bp == other.bp)  // trivial case: both expressions point to same basic
 		return 0;
-	return bp->compare(*other.bp);
+	const int cmpval = bp->compare(*other.bp);
+	if (cmpval == 0) {
+		// Expressions point to different, but equal, trees: conserve
+		// memory and make subsequent compare() operations faster by
+		// making both expression point to the same tree.
+		share(other);
+	}
+	return cmpval;
 }
 
 inline
@@ -493,6 +376,304 @@ 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);
+	}
+
+	// This should return an ex*, but that would be a pointer to a
+	// temporary value
+	std::auto_ptr<ex> operator->() const
+	{
+		return std::auto_ptr<ex>(new ex(operator*()));
+	}
+
+	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 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()));
+	}
+
+public:
+	ex operator*() const
+	{
+		return s.top().e;
+	}
+
+	std::auto_ptr<ex> operator->() const
+	{
+		return std::auto_ptr<ex>(new ex(operator*()));
+	}
+
+	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.top() == other.s.top();
+	}
+
+	bool operator!=(const const_preorder_iterator &other) const throw()
+	{
+		return !(*this == other);
+	}
+
+private:
+	std::stack<internal::_iter_rep, std::vector<internal::_iter_rep> > s;
+
+	void increment()
+	{
+		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()));
+		}
+	}
+};
+
+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 ex::begin() and
+	// ex::end() can be used to create const_postorder_iterators
+	const_postorder_iterator(const const_iterator & cit)
+	{
+		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
+	{
+		return s.top().e;
+	}
+
+	std::auto_ptr<ex> operator->() const
+	{
+		return std::auto_ptr<ex>(new ex(operator*()));
+	}
+
+	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, std::vector<internal::_iter_rep> > s;
+
+	void descend()
+	{
+		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()));
+		}
+	}
+
+	void increment()
+	{
+		if (s.top().i == s.top().i_end)
+			s.pop();
+		if (s.size() > 0) {
+			++s.top().i;
+			descend();
+		}
+	}
+};
+
+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.
@@ -504,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(); }
@@ -541,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); }
 
@@ -565,11 +769,11 @@ inline ex series(const ex & thisex, const ex & r, int order, unsigned options =
 inline bool match(const ex & thisex, const ex & pattern, lst & repl_lst)
 { return thisex.match(pattern, repl_lst); }
 
-inline ex simplify_indexed(const ex & thisex)
-{ return thisex.simplify_indexed(); }
+inline ex simplify_indexed(const ex & thisex, unsigned options = 0)
+{ return thisex.simplify_indexed(options); }
 
-inline ex simplify_indexed(const ex & thisex, const scalar_products & sp)
-{ return thisex.simplify_indexed(sp); }
+inline ex simplify_indexed(const ex & thisex, const scalar_products & sp, unsigned options = 0)
+{ return thisex.simplify_indexed(sp, options); }
 
 inline ex symmetrize(const ex & thisex)
 { return thisex.symmetrize(); }
@@ -604,29 +808,6 @@ inline bool is_zero(const ex & thisex)
 inline void swap(ex & e1, ex & e2)
 { e1.swap(e2); }
 
-
-// This makes STL algorithms use the more efficient swap operation for ex objects
-inline void iter_swap(std::vector<ex>::iterator i1, std::vector<ex>::iterator i2)
-{ i1->swap(*i2); }
-
-
-/* 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);
@@ -709,7 +890,9 @@ inline bool is_exactly_a(const ex &obj)
 /** Return a reference to the basic-derived class T object embedded in an
  *  expression.  This is fast but unsafe: the result is undefined if the
  *  expression does not contain a T object at its top level.  Hence, you
- *  should generally check the type of e first.
+ *  should generally check the type of e first.  Also, you shouldn't cache
+ *  the returned reference because GiNaC's garbage collector may destroy
+ *  the referenced object any time it's used in another expression.
  *
  *  @param e expression
  *  @return reference to object of class T
@@ -723,4 +906,31 @@ inline const T &ex_to(const ex &e)
 
 } // namespace GiNaC
 
+
+// Specializations of Standard Library algorithms
+namespace std {
+
+/** Specialization of std::swap() for ex objects. */
+template <>
+inline void swap(GiNaC::ex &a, GiNaC::ex &b)
+{
+	a.swap(b);
+}
+
+/** Specialization of std::iter_swap() for vector<ex> iterators. */
+template <>
+inline void iter_swap(vector<GiNaC::ex>::iterator i1, vector<GiNaC::ex>::iterator i2)
+{
+	i1->swap(*i2);
+}
+
+/** Specialization of std::iter_swap() for list<ex> iterators. */
+template <>
+inline void iter_swap(list<GiNaC::ex>::iterator i1, list<GiNaC::ex>::iterator i2)
+{
+	i1->swap(*i2);
+}
+
+} // namespace std
+
 #endif // ndef __GINAC_EX_H__