- added lst::remove_first() and lst::remove_last()

- added symmetrize_cyclic()
- antisymmetrize() is slightly faster
- ensure_if_modifiable() clears the hash_calculated flag

diff --git a/NEWS b/NEWS
index 3788916df20a5f497c3833eb12439d9513916762..b69ad3f6c125ff7911ec7aa783d760cfd4b8d434 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -1,5 +1,9 @@
 This file records noteworthy changes.
 
 This file records noteworthy changes.
 

+0.9.1 (<date>)
+* Added remove_first() and remove_last() methods for lists.
+* Added symmetrize_cyclic().
+

 0.9.0 (7 June 2001)
 * In the output and in ginsh, lists are now delimited by { } braces, and
   matrices are delimited by single [ ] brackets.
 0.9.0 (7 June 2001)
 * In the output and in ginsh, lists are now delimited by { } braces, and
   matrices are delimited by single [ ] brackets.

diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi
index 5511a2d1ea22e2e495afdc5b3acd893f4efdc09a..9411950f659ae17ab5eaa4bad5e39163da9b5843 100644 (file)
--- a/doc/tutorial/ginac.texi
+++ b/doc/tutorial/ginac.texi
@@ -1135,6 +1135,8 @@ canonical form.
 @cindex @code{op()}
 @cindex @code{append()}
 @cindex @code{prepend()}
 @cindex @code{op()}
 @cindex @code{append()}
 @cindex @code{prepend()}

+@cindex @code{remove_first()}
+@cindex @code{remove_last()}

 
 The GiNaC class @code{lst} serves for holding a @dfn{list} of arbitrary
 expressions. These are sometimes used to supply a variable number of
 
 The GiNaC class @code{lst} serves for holding a @dfn{list} of arbitrary
 expressions. These are sometimes used to supply a variable number of


@@ -1162,13 +1164,23 @@ a list and the @code{op()} method to access individual elements:
     // ...
 @end example
 
     // ...
 @end example
 

-Finally you can append or prepend an expression to a list with the
-@code{append()} and @code{prepend()} methods:
+You can append or prepend an expression to a list with the @code{append()}
+and @code{prepend()} methods:

 
 @example
     // ...
     l.append(4*x);   // l is now @{x, 2, y, x+y, 4*x@}
     l.prepend(0);    // l is now @{0, x, 2, y, x+y, 4*x@}
 
 @example
     // ...
     l.append(4*x);   // l is now @{x, 2, y, x+y, 4*x@}
     l.prepend(0);    // l is now @{0, x, 2, y, x+y, 4*x@}

+    // ...
+@end example
+
+Finally you can remove the first or last element of a list with
+@code{remove_first()} and @code{remove_last()}:
+
+@example
+    // ...
+    l.remove_first();   // l is now @{x, 2, y, x+y, 4*x@}
+    l.remove_last();    // l is now @{x, 2, y, x+y@}

 @}
 @end example
 
 @}
 @end example
 


@@ -3541,23 +3553,26 @@ program, it will type out:
 @section Symmetrization
 @cindex @code{symmetrize()}
 @cindex @code{antisymmetrize()}
 @section Symmetrization
 @cindex @code{symmetrize()}
 @cindex @code{antisymmetrize()}

+@cindex @code{symmetrize_cyclic()}

 
 

-The two methods
+The three methods

 
 @example
 ex ex::symmetrize(const lst & l);
 ex ex::antisymmetrize(const lst & l);
 
 @example
 ex ex::symmetrize(const lst & l);
 ex ex::antisymmetrize(const lst & l);

+ex ex::symmetrize_cyclic(const lst & l);

 @end example
 
 @end example
 

-symmetrize an expression by returning the symmetric or antisymmetric sum
-over all permutations of the specified list of objects, weighted by the
-number of permutations.
+symmetrize an expression by returning the sum over all symmetric,
+antisymmetric or cyclic permutations of the specified list of objects,
+weighted by the number of permutations.

 
 

-The two additional methods
+The three additional methods

 
 @example
 ex ex::symmetrize();
 ex ex::antisymmetrize();
 
 @example
 ex ex::symmetrize();
 ex ex::antisymmetrize();

+ex ex::symmetrize_cyclic();

 @end example
 
 symmetrize or antisymmetrize an expression over its free indices.
 @end example
 
 symmetrize or antisymmetrize an expression over its free indices.


@@ -3574,8 +3589,8 @@ almost any kind of object (anything that is @code{subs()}able):
      // -> 1/2*A.j.i+1/2*A.i.j
     cout << indexed(A, i, j, k).antisymmetrize(lst(i, j)) << endl;
      // -> -1/2*A.j.i.k+1/2*A.i.j.k
      // -> 1/2*A.j.i+1/2*A.i.j
     cout << indexed(A, i, j, k).antisymmetrize(lst(i, j)) << endl;
      // -> -1/2*A.j.i.k+1/2*A.i.j.k

-    cout << lst(a, b, c).symmetrize(lst(a, b, c)) << endl;
-     // -> 1/6*@{a,b,c@}+1/6*@{c,a,b@}+1/6*@{b,a,c@}+1/6*@{c,b,a@}+1/6*@{b,c,a@}+1/6*@{a,c,b@}
+    cout << lst(a, b, c).symmetrize_cyclic(lst(a, b, c)) << endl;
+     // -> 1/3*@{a,b,c@}+1/3*@{b,c,a@}+1/3*@{c,a,b@}

 @}
 @end example
 
 @}
 @end example
 


@@ -4588,7 +4603,7 @@ cout << e << endl;
  // -> "GiNaC rulez"+"Hello, world!"
 @end example
 
  // -> "GiNaC rulez"+"Hello, world!"
 @end example
 

-(note that GiNaC's automatic term reordering is in effect here), or even
+(GiNaC's automatic term reordering is in effect here), or even

 
 @example
 e = pow(mystring("One string"), 2*sin(Pi-mystring("Another string")));
 
 @example
 e = pow(mystring("One string"), 2*sin(Pi-mystring("Another string")));

diff --git a/ginac/basic.cpp b/ginac/basic.cpp
index 2b1b68b0cf82c193b958c0864df2f652e948a74a..a2e10f715531d286c0d3fef0a0a13a4e5cc8d18a 100644 (file)
--- a/ginac/basic.cpp
+++ b/ginac/basic.cpp
@@ -732,6 +732,7 @@ void basic::ensure_if_modifiable(void) const
 {
        if (this->refcount>1)
                throw(std::runtime_error("cannot modify multiply referenced object"));
 {
        if (this->refcount>1)
                throw(std::runtime_error("cannot modify multiply referenced object"));

+       clearflag(status_flags::hash_calculated);

 }
 
 //////////
 }
 
 //////////

diff --git a/ginac/container.pl b/ginac/container.pl
index 480d5a565cd32caad51a9b4011dc3a1d54ca811c..275461557c4f7d2aaa460ae47ef0ce69de38e13e 100755 (executable)
--- a/ginac/container.pl
+++ b/ginac/container.pl
@@ -54,6 +54,7 @@ if ($reserve) {
 if ($prepend) {
        $PREPEND_INTERFACE=<<END_OF_PREPEND_INTERFACE;
        virtual ${CONTAINER} & prepend(const ex & b);
 if ($prepend) {
        $PREPEND_INTERFACE=<<END_OF_PREPEND_INTERFACE;
        virtual ${CONTAINER} & prepend(const ex & b);

+       virtual ${CONTAINER} & remove_first(void);

 END_OF_PREPEND_INTERFACE
 
        $PREPEND_IMPLEMENTATION=<<END_OF_PREPEND_IMPLEMENTATION;
 END_OF_PREPEND_INTERFACE
 
        $PREPEND_IMPLEMENTATION=<<END_OF_PREPEND_IMPLEMENTATION;


@@ -63,6 +64,12 @@ ${CONTAINER} & ${CONTAINER}::prepend(const ex & b)
        seq.push_front(b);
        return *this;
 }
        seq.push_front(b);
        return *this;
 }

+${CONTAINER} & ${CONTAINER}::remove_first(void)
+{
+       ensure_if_modifiable();
+       seq.pop_front();
+       return *this;
+}

 END_OF_PREPEND_IMPLEMENTATION
 } else {
        $PREPEND_INTERFACE="    // no prepend possible for ${CONTAINER}";
 END_OF_PREPEND_IMPLEMENTATION
 } else {
        $PREPEND_INTERFACE="    // no prepend possible for ${CONTAINER}";


@@ -217,6 +224,7 @@ protected:
        // new virtual functions which can be overridden by derived classes
 public:
        virtual ${CONTAINER} & append(const ex & b);
        // new virtual functions which can be overridden by derived classes
 public:
        virtual ${CONTAINER} & append(const ex & b);

+       virtual ${CONTAINER} & remove_last(void);

 ${PREPEND_INTERFACE}
 protected:
        virtual void printseq(const print_context & c, char openbracket, char delim,
 ${PREPEND_INTERFACE}
 protected:
        virtual void printseq(const print_context & c, char openbracket, char delim,


@@ -540,6 +548,13 @@ ${CONTAINER} & ${CONTAINER}::append(const ex & b)
        return *this;
 }
 
        return *this;
 }
 

+${CONTAINER} & ${CONTAINER}::remove_last(void)
+{
+       ensure_if_modifiable();
+       seq.pop_back();
+       return *this;
+}
+

 ${PREPEND_IMPLEMENTATION}
 
 // protected
 ${PREPEND_IMPLEMENTATION}
 
 // protected

diff --git a/ginac/ex.h b/ginac/ex.h
index 84b05d887dab363b35f1350b4e9ded0e193ad5b4..26183ef51248edf2e66bc8246d6d2696b4b573df 100644 (file)
--- a/ginac/ex.h
+++ b/ginac/ex.h
@@ -119,6 +119,8 @@ public:
        ex symmetrize(const lst & l) const;
        ex antisymmetrize(void) const;
        ex antisymmetrize(const lst & l) const;
        ex symmetrize(const lst & l) const;
        ex antisymmetrize(void) const;
        ex antisymmetrize(const lst & l) const;

+       ex symmetrize_cyclic(void) const;
+       ex symmetrize_cyclic(const lst & l) const;

        ex simplify_ncmul(const exvector & v) const { return bp->simplify_ncmul(v); }
        ex operator[](const ex & index) const;
        ex operator[](int i) const;
        ex simplify_ncmul(const exvector & v) const { return bp->simplify_ncmul(v); }
        ex operator[](const ex & index) const;
        ex operator[](int i) const;


@@ -412,6 +414,12 @@ inline ex antisymmetrize(const ex & thisex)
 inline ex antisymmetrize(const ex & thisex, const lst & l)
 { return thisex.antisymmetrize(l); }
 
 inline ex antisymmetrize(const ex & thisex, const lst & l)
 { return thisex.antisymmetrize(l); }
 

+inline ex symmetrize_cyclic(const ex & thisex)
+{ return thisex.symmetrize_cyclic(); }
+
+inline ex symmetrize_cyclic(const ex & thisex, const lst & l)
+{ return thisex.symmetrize_cyclic(l); }
+

 inline ex op(const ex & thisex, int i)
 { return thisex.op(i); }
 
 inline ex op(const ex & thisex, int i)
 { return thisex.op(i); }
 

diff --git a/ginac/indexed.cpp b/ginac/indexed.cpp
index 90e3d4c361b049ab016483c074c48f8b13658189..3f2cb717b2b5e5577c5ef4ed01b82e39bfb94505 100644 (file)
--- a/ginac/indexed.cpp
+++ b/ginac/indexed.cpp
@@ -852,6 +852,12 @@ ex ex::antisymmetrize(void) const
        return GiNaC::antisymmetrize(*this, get_free_indices());
 }
 
        return GiNaC::antisymmetrize(*this, get_free_indices());
 }
 

+/** Symmetrize expression by cyclic permutation over its free indices. */
+ex ex::symmetrize_cyclic(void) const
+{
+       return GiNaC::symmetrize_cyclic(*this, get_free_indices());
+}
+

 //////////
 // helper classes
 //////////
 //////////
 // helper classes
 //////////

diff --git a/ginac/inifcns.cpp b/ginac/inifcns.cpp
index 4d1c978b716a6b2c2ba456acd26a2d7dfcf66b02..0ee9b2737fd30ef8b31fe39dcb965f887ee114b8 100644 (file)
--- a/ginac/inifcns.cpp
+++ b/ginac/inifcns.cpp
@@ -517,24 +517,35 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite
        if (num < 2)
                return e;
 
        if (num < 2)
                return e;
 

-       // Sort object vector, transform it into a list, and make a copy so we
-       // will know which objects get substituted for which
+       // Transform object vector to a list

        exlist iv_lst;
        iv_lst.insert(iv_lst.begin(), first, last);
        exlist iv_lst;
        iv_lst.insert(iv_lst.begin(), first, last);

-       shaker_sort(iv_lst.begin(), iv_lst.end(), ex_is_less());
-       lst orig_lst(iv_lst);
+       lst orig_lst(iv_lst, true);
+
+       // Create index vectors for permutation
+       unsigned *iv = new unsigned[num], *iv2;
+       for (unsigned i=0; i<num; i++)
+               iv[i] = i;
+       iv2 = (asymmetric ? new unsigned[num] : NULL);

 
        // Loop over all permutations (the first permutation, which is the
        // identity, is unrolled)
        ex sum = e;
 
        // Loop over all permutations (the first permutation, which is the
        // identity, is unrolled)
        ex sum = e;

-       while (next_permutation(iv_lst.begin(), iv_lst.end(), ex_is_less())) {
-               ex term = e.subs(orig_lst, lst(iv_lst));
+       while (std::next_permutation(iv, iv + num)) {
+               lst new_lst;
+               for (unsigned i=0; i<num; i++)
+                       new_lst.append(orig_lst.op(iv[i]));
+               ex term = e.subs(orig_lst, new_lst);

                if (asymmetric) {
                if (asymmetric) {

-                       exlist test_lst = iv_lst;
-                       term *= permutation_sign(test_lst.begin(), test_lst.end(), ex_is_less());
+                       memcpy(iv2, iv, num * sizeof(unsigned));
+                       term *= permutation_sign(iv2, iv2 + num);

                }
                sum += term;
        }
                }
                sum += term;
        }

+
+       delete[] iv;
+       delete[] iv2;
+

        return sum / factorial(numeric(num));
 }
 
        return sum / factorial(numeric(num));
 }
 


@@ -548,6 +559,30 @@ ex antisymmetrize(const ex & e, exvector::const_iterator first, exvector::const_
        return symm(e, first, last, true);
 }
 
        return symm(e, first, last, true);
 }
 

+ex symmetrize_cyclic(const ex & e, exvector::const_iterator first, exvector::const_iterator last)
+{
+       // Need at least 2 objects for this operation
+       int num = last - first;
+       if (num < 2)
+               return e;
+
+       // Transform object vector to a list
+       exlist iv_lst;
+       iv_lst.insert(iv_lst.begin(), first, last);
+       lst orig_lst(iv_lst, true);
+       lst new_lst = orig_lst;
+
+       // Loop over all cyclic permutations (the first permutation, which is
+       // the identity, is unrolled)
+       ex sum = e;
+       for (unsigned i=0; i<num-1; i++) {
+               ex perm = new_lst.op(0);
+               new_lst.remove_first().append(perm);
+               sum += e.subs(orig_lst, new_lst);
+       }
+       return sum / num;
+}
+

 /** Symmetrize expression over a list of objects (symbols, indices). */
 ex ex::symmetrize(const lst & l) const
 {
 /** Symmetrize expression over a list of objects (symbols, indices). */
 ex ex::symmetrize(const lst & l) const
 {


@@ -568,6 +603,17 @@ ex ex::antisymmetrize(const lst & l) const
        return symm(*this, v.begin(), v.end(), true);
 }
 
        return symm(*this, v.begin(), v.end(), true);
 }
 

+/** Symmetrize expression by cyclic permutation over a list of objects
+ *  (symbols, indices). */
+ex ex::symmetrize_cyclic(const lst & l) const
+{
+       exvector v;
+       v.reserve(l.nops());
+       for (unsigned i=0; i<l.nops(); i++)
+               v.push_back(l.op(i));
+       return GiNaC::symmetrize_cyclic(*this, v.begin(), v.end());
+}
+

 /** Force inclusion of functions from initcns_gamma and inifcns_zeta
  *  for static lib (so ginsh will see them). */
 unsigned force_include_tgamma = function_index_tgamma;
 /** Force inclusion of functions from initcns_gamma and inifcns_zeta
  *  for static lib (so ginsh will see them). */
 unsigned force_include_tgamma = function_index_tgamma;

diff --git a/ginac/inifcns.h b/ginac/inifcns.h
index 3d170ff8df5435d332971e9731e3795c3cbaefc4..314228f8033972bbeee3944f6fbc84064129361a 100644 (file)
--- a/ginac/inifcns.h
+++ b/ginac/inifcns.h
@@ -151,6 +151,17 @@ inline ex antisymmetrize(const ex & e, const exvector & v)
        return antisymmetrize(e, v.begin(), v.end());
 }
 
        return antisymmetrize(e, v.begin(), v.end());
 }
 

+/** Symmetrize expression by cyclic permuation over a set of objects
+ *  (symbols, indices). */
+ex symmetrize_cyclic(const ex & e, exvector::const_iterator first, exvector::const_iterator last);
+
+/** Symmetrize expression by cyclic permutation over a set of objects
+ *  (symbols, indices). */
+inline ex symmetrize_cyclic(const ex & e, const exvector & v)
+{
+       return symmetrize(e, v.begin(), v.end());
+}
+

 /** Check whether a function is the Order (O(n)) function. */
 inline bool is_order_function(const ex & e)
 {
 /** Check whether a function is the Order (O(n)) function. */
 inline bool is_order_function(const ex & e)
 {

diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp
index 872b8e006012c3a4ecf6279cf315ed8c34e5f793..1f2e0ea8c655f80968c9096ea392f7ec0de00e71 100644 (file)
--- a/ginac/matrix.cpp
+++ b/ginac/matrix.cpp
@@ -682,7 +682,6 @@ ex & matrix::operator() (unsigned ro, unsigned co)
                throw (std::range_error("matrix::operator(): index out of range"));
 
        ensure_if_modifiable();
                throw (std::range_error("matrix::operator(): index out of range"));
 
        ensure_if_modifiable();

-       clearflag(status_flags::hash_calculated);

        return m[ro*col+co];
 }
 
        return m[ro*col+co];
 }
 

diff --git a/ginac/utils.h b/ginac/utils.h
index ae972254c04f36b687d4b73fd2498353ce4255fa..29eef7cad8753edd12f12af3430ba13ddad58fd2 100644 (file)
--- a/ginac/utils.h
+++ b/ginac/utils.h
@@ -283,6 +283,39 @@ void shaker_sort(It first, It last, Cmp comp)
        } while (first != last);
 }
 
        } while (first != last);
 }
 

+/* In-place cyclic permutation of a container (no copying, only swapping). */
+template <class It>
+void cyclic_permutation(It first, It last, It new_first)
+{
+       unsigned num = last - first;
+again:
+       if (first == new_first || num < 2)
+               return;
+
+       unsigned num1 = new_first - first, num2 = last - new_first;
+       if (num1 >= num2) {
+               It a = first, b = new_first;
+               while (b != last) {
+                       std::iter_swap(a, b);
+                       ++a; ++b;
+               }
+               if (num1 > num2) {
+                       first += num2;
+                       num = num1;
+                       goto again;
+               }
+       } else {
+               It a = new_first, b = last;
+               do {
+                       --a; --b;
+                       std::iter_swap(a, b);
+               } while (a != first);
+               last -= num1;
+               num = num2;
+               goto again;
+       }
+}
+

 /* 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; }
 /* 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; }