- added lst::remove_first() and lst::remove_last()
authorChristian Bauer <Christian.Bauer@uni-mainz.de>
Sat, 9 Jun 2001 19:17:32 +0000 (19:17 +0000)
committerChristian Bauer <Christian.Bauer@uni-mainz.de>
Sat, 9 Jun 2001 19:17:32 +0000 (19:17 +0000)
- added symmetrize_cyclic()
- antisymmetrize() is slightly faster
- ensure_if_modifiable() clears the hash_calculated flag

NEWS
doc/tutorial/ginac.texi
ginac/basic.cpp
ginac/container.pl
ginac/ex.h
ginac/indexed.cpp
ginac/inifcns.cpp
ginac/inifcns.h
ginac/matrix.cpp
ginac/utils.h

diff --git a/NEWS b/NEWS
index 3788916..b69ad3f 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -1,5 +1,9 @@
 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.
index 5511a2d..9411950 100644 (file)
@@ -1135,6 +1135,8 @@ canonical form.
 @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
@@ -1162,13 +1164,23 @@ a list and the @code{op()} method to access individual elements:
     // ...
 @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@}
+    // ...
+@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
 
@@ -3541,23 +3553,26 @@ program, it will type out:
 @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);
+ex ex::symmetrize_cyclic(const lst & l);
 @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();
+ex ex::symmetrize_cyclic();
 @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
-    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
 
@@ -4588,7 +4603,7 @@ cout << e << endl;
  // -> "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")));
index 2b1b68b..a2e10f7 100644 (file)
@@ -732,6 +732,7 @@ void basic::ensure_if_modifiable(void) const
 {
        if (this->refcount>1)
                throw(std::runtime_error("cannot modify multiply referenced object"));
+       clearflag(status_flags::hash_calculated);
 }
 
 //////////
index 480d5a5..2754615 100755 (executable)
@@ -54,6 +54,7 @@ if ($reserve) {
 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;
@@ -63,6 +64,12 @@ ${CONTAINER} & ${CONTAINER}::prepend(const ex & b)
        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}";
@@ -217,6 +224,7 @@ protected:
        // 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,
@@ -540,6 +548,13 @@ ${CONTAINER} & ${CONTAINER}::append(const ex & b)
        return *this;
 }
 
+${CONTAINER} & ${CONTAINER}::remove_last(void)
+{
+       ensure_if_modifiable();
+       seq.pop_back();
+       return *this;
+}
+
 ${PREPEND_IMPLEMENTATION}
 
 // protected
index 84b05d8..26183ef 100644 (file)
@@ -119,6 +119,8 @@ public:
        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;
@@ -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 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); }
 
index 90e3d4c..3f2cb71 100644 (file)
@@ -852,6 +852,12 @@ ex ex::antisymmetrize(void) const
        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
 //////////
index 4d1c978..0ee9b27 100644 (file)
@@ -517,24 +517,35 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite
        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);
-       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;
-       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) {
-                       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;
        }
+
+       delete[] iv;
+       delete[] iv2;
+
        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);
 }
 
+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
 {
@@ -568,6 +603,17 @@ ex ex::antisymmetrize(const lst & l) const
        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;
index 3d170ff..314228f 100644 (file)
@@ -151,6 +151,17 @@ inline ex antisymmetrize(const ex & e, const exvector & v)
        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)
 {
index 872b8e0..1f2e0ea 100644 (file)
@@ -682,7 +682,6 @@ ex & matrix::operator() (unsigned ro, unsigned co)
                throw (std::range_error("matrix::operator(): index out of range"));
 
        ensure_if_modifiable();
-       clearflag(status_flags::hash_calculated);
        return m[ro*col+co];
 }
 
index ae97225..29eef7c 100644 (file)
@@ -283,6 +283,39 @@ void shaker_sort(It first, It last, Cmp comp)
        } 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; }