X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Findexed.cpp;h=d63711044b03fbff787a47aeba51a14908c79d72;hp=c3fe1d9a26e6d49ca311b0e793913d6050ef402f;hb=0c718e0dda0d2de1224f39ec5e3c39720e0abfc2;hpb=539de73dc25de63f2888f8696d73ac3fc83db45f diff --git a/ginac/indexed.cpp b/ginac/indexed.cpp index c3fe1d9a..d6371104 100644 --- a/ginac/indexed.cpp +++ b/ginac/indexed.cpp @@ -3,7 +3,7 @@ * Implementation of GiNaC's indexed expressions. */ /* - * GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany + * GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -20,6 +20,8 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ +#include +#include #include #include "indexed.h" @@ -28,199 +30,182 @@ #include "mul.h" #include "ncmul.h" #include "power.h" +#include "relational.h" +#include "symmetry.h" +#include "lst.h" +#include "print.h" #include "archive.h" #include "utils.h" -#include "debugmsg.h" namespace GiNaC { GINAC_IMPLEMENT_REGISTERED_CLASS(indexed, exprseq) ////////// -// default constructor, destructor, copy constructor assignment operator and helpers +// default ctor, dtor, copy ctor, assignment operator and helpers ////////// -indexed::indexed() : symmetry(unknown) +indexed::indexed() : symtree(sy_none()) { - debugmsg("indexed default constructor", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; } void indexed::copy(const indexed & other) { inherited::copy(other); - symmetry = other.symmetry; + symtree = other.symtree; } -void indexed::destroy(bool call_parent) -{ - if (call_parent) - inherited::destroy(call_parent); -} +DEFAULT_DESTROY(indexed) ////////// // other constructors ////////// -indexed::indexed(const ex & b) : inherited(b), symmetry(unknown) +indexed::indexed(const ex & b) : inherited(b), symtree(sy_none()) { - debugmsg("indexed constructor from ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, const ex & i1) : inherited(b, i1), symmetry(unknown) +indexed::indexed(const ex & b, const ex & i1) : inherited(b, i1), symtree(sy_none()) { - debugmsg("indexed constructor from ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, const ex & i1, const ex & i2) : inherited(b, i1, i2), symmetry(unknown) +indexed::indexed(const ex & b, const ex & i1, const ex & i2) : inherited(b, i1, i2), symtree(sy_none()) { - debugmsg("indexed constructor from ex,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symmetry(unknown) +indexed::indexed(const ex & b, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symtree(sy_none()) { - debugmsg("indexed constructor from ex,ex,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, const ex & i1, const ex & i2, const ex & i3, const ex & i4) : inherited(b, i1, i2, i3, i4), symmetry(unknown) +indexed::indexed(const ex & b, const ex & i1, const ex & i2, const ex & i3, const ex & i4) : inherited(b, i1, i2, i3, i4), symtree(sy_none()) { - debugmsg("indexed constructor from ex,ex,ex,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, symmetry_type symm, const ex & i1, const ex & i2) : inherited(b, i1, i2), symmetry(symm) +indexed::indexed(const ex & b, const symmetry & symm, const ex & i1, const ex & i2) : inherited(b, i1, i2), symtree(symm) { - debugmsg("indexed constructor from ex,symmetry,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, symmetry_type symm, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symmetry(symm) +indexed::indexed(const ex & b, const symmetry & symm, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symtree(symm) { - debugmsg("indexed constructor from ex,symmetry,ex,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, symmetry_type symm, const ex & i1, const ex & i2, const ex & i3, const ex & i4) : inherited(b, i1, i2, i3, i4), symmetry(symm) +indexed::indexed(const ex & b, const symmetry & symm, const ex & i1, const ex & i2, const ex & i3, const ex & i4) : inherited(b, i1, i2, i3, i4), symtree(symm) { - debugmsg("indexed constructor from ex,symmetry,ex,ex,ex,ex", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, const exvector & v) : inherited(b), symmetry(unknown) +indexed::indexed(const ex & b, const exvector & v) : inherited(b), symtree(sy_none()) { - debugmsg("indexed constructor from ex,exvector", LOGLEVEL_CONSTRUCT); seq.insert(seq.end(), v.begin(), v.end()); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(const ex & b, symmetry_type symm, const exvector & v) : inherited(b), symmetry(symm) +indexed::indexed(const ex & b, const symmetry & symm, const exvector & v) : inherited(b), symtree(symm) { - debugmsg("indexed constructor from ex,symmetry,exvector", LOGLEVEL_CONSTRUCT); seq.insert(seq.end(), v.begin(), v.end()); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); + validate(); } -indexed::indexed(symmetry_type symm, const exprseq & es) : inherited(es), symmetry(symm) +indexed::indexed(const symmetry & symm, const exprseq & es) : inherited(es), symtree(symm) { - debugmsg("indexed constructor from symmetry,exprseq", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); } -indexed::indexed(symmetry_type symm, const exvector & v, bool discardable) : inherited(v, discardable), symmetry(symm) +indexed::indexed(const symmetry & symm, const exvector & v, bool discardable) : inherited(v, discardable), symtree(symm) { - debugmsg("indexed constructor from symmetry,exvector", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); } -indexed::indexed(symmetry_type symm, exvector * vp) : inherited(vp), symmetry(symm) +indexed::indexed(const symmetry & symm, exvector * vp) : inherited(vp), symtree(symm) { - debugmsg("indexed constructor from symmetry,exvector *", LOGLEVEL_CONSTRUCT); tinfo_key = TINFO_indexed; - GINAC_ASSERT(all_indices_of_type_idx()); } ////////// // archiving ////////// -/** Construct object from archive_node. */ indexed::indexed(const archive_node &n, const lst &sym_lst) : inherited(n, sym_lst) { - debugmsg("indexed constructor from archive_node", LOGLEVEL_CONSTRUCT); - unsigned int symm; - if (!(n.find_unsigned("symmetry", symm))) - throw (std::runtime_error("unknown indexed symmetry type in archive")); -} - -/** Unarchive the object. */ -ex indexed::unarchive(const archive_node &n, const lst &sym_lst) -{ - return (new indexed(n, sym_lst))->setflag(status_flags::dynallocated); + if (!n.find_ex("symmetry", symtree, sym_lst)) { + // GiNaC versions <= 0.9.0 had an unsigned "symmetry" property + unsigned symm = 0; + n.find_unsigned("symmetry", symm); + switch (symm) { + case 1: + symtree = sy_symm(); + break; + case 2: + symtree = sy_anti(); + break; + default: + symtree = sy_none(); + break; + } + const_cast(ex_to(symtree)).validate(seq.size() - 1); + } } -/** Archive the object. */ void indexed::archive(archive_node &n) const { inherited::archive(n); - n.add_unsigned("symmetry", symmetry); + n.add_ex("symmetry", symtree); } +DEFAULT_UNARCHIVE(indexed) + ////////// -// functions overriding virtual functions from bases classes +// functions overriding virtual functions from base classes ////////// -void indexed::printraw(std::ostream & os) const +void indexed::print(const print_context & c, unsigned level) const { - debugmsg("indexed printraw", LOGLEVEL_PRINT); GINAC_ASSERT(seq.size() > 0); - os << class_name() << "("; - seq[0].printraw(os); - os << ",indices="; - printrawindices(os); - os << ",hash=" << hashvalue << ",flags=" << flags << ")"; -} + if (is_a(c)) { -void indexed::printtree(std::ostream & os, unsigned indent) const -{ - debugmsg("indexed printtree", LOGLEVEL_PRINT); - GINAC_ASSERT(seq.size() > 0); + c.s << std::string(level, ' ') << class_name() + << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec + << ", " << seq.size()-1 << " indices" + << ", symmetry=" << symtree << std::endl; + unsigned delta_indent = static_cast(c).delta_indent; + seq[0].print(c, level + delta_indent); + printindices(c, level + delta_indent); - os << std::string(indent, ' ') << class_name() << ", " << seq.size()-1 << " indices"; - os << ",hash=" << hashvalue << ",flags=" << flags << std::endl; - printtreeindices(os, indent); -} + } else { -void indexed::print(std::ostream & os, unsigned upper_precedence) const -{ - debugmsg("indexed print", LOGLEVEL_PRINT); - GINAC_ASSERT(seq.size() > 0); + bool is_tex = is_a(c); + const ex & base = seq[0]; - const ex & base = seq[0]; - bool need_parens = is_ex_exactly_of_type(base, add) || is_ex_exactly_of_type(base, mul) - || is_ex_exactly_of_type(base, ncmul) || is_ex_exactly_of_type(base, power); - if (need_parens) - os << "("; - os << base; - if (need_parens) - os << ")"; - printindices(os); + if (precedence() <= level) + c.s << (is_tex ? "{(" : "("); + if (is_tex) + c.s << "{"; + base.print(c, precedence()); + if (is_tex) + c.s << "}"; + printindices(c, level); + if (precedence() <= level) + c.s << (is_tex ? ")}" : ")"); + } } bool indexed::info(unsigned inf) const @@ -230,6 +215,12 @@ bool indexed::info(unsigned inf) const return inherited::info(inf); } +struct idx_is_not : public std::binary_function { + bool operator() (const ex & e, unsigned inf) const { + return !(ex_to(e).get_value().info(inf)); + } +}; + bool indexed::all_index_values_are(unsigned inf) const { // No indices? Then no property can be fulfilled @@ -237,123 +228,60 @@ bool indexed::all_index_values_are(unsigned inf) const return false; // Check all indices - exvector::const_iterator it = seq.begin() + 1, itend = seq.end(); - while (it != itend) { - GINAC_ASSERT(is_ex_of_type(*it, idx)); - if (!ex_to_idx(*it).get_value().info(inf)) - return false; - it++; - } - return true; + return find_if(seq.begin() + 1, seq.end(), bind2nd(idx_is_not(), inf)) == seq.end(); } int indexed::compare_same_type(const basic & other) const { - GINAC_ASSERT(is_of_type(other, indexed)); + GINAC_ASSERT(is_a(other)); return inherited::compare_same_type(other); } -// The main difference between sort_index_vector() and canonicalize_indices() -// is that the latter takes the symmetry of the object into account. Once we -// implement mixed symmetries, canonicalize_indices() will only be able to -// reorder index pairs with known symmetry properties, while sort_index_vector() -// always sorts the whole vector. - -/** Bring a vector of indices into a canonic order (don't care about the - * symmetry of the objects carrying the indices). Dummy indices will lie - * next to each other after the sorting. - * - * @param v Index vector to be sorted */ -static void sort_index_vector(exvector &v) -{ - // Nothing to sort if less than 2 elements - if (v.size() < 2) - return; - - // Simple bubble sort algorithm should be sufficient for the small - // number of indices expected - exvector::iterator it1 = v.begin(), itend = v.end(), next_to_last_idx = itend - 1; - while (it1 != next_to_last_idx) { - exvector::iterator it2 = it1 + 1; - while (it2 != itend) { - if (it1->compare(*it2) > 0) - it1->swap(*it2); - it2++; - } - it1++; - } -} - -/** Bring a vector of indices into a canonic order. This operation only makes - * sense if the object carrying these indices is either symmetric or totally - * antisymmetric with respect to the indices. - * - * @param itbegin Start of index vector - * @param itend End of index vector - * @param antisymm Whether the object is antisymmetric - * @return the sign introduced by the reordering of the indices if the object - * is antisymmetric (or 0 if two equal indices are encountered). For - * symmetric objects, this is always +1. If the index vector was - * already in a canonic order this function returns INT_MAX. */ -static int canonicalize_indices(exvector::iterator itbegin, exvector::iterator itend, bool antisymm) -{ - bool something_changed = false; - int sig = 1; - - // Simple bubble sort algorithm should be sufficient for the small - // number of indices expected - exvector::iterator it1 = itbegin, next_to_last_idx = itend - 1; - while (it1 != next_to_last_idx) { - exvector::iterator it2 = it1 + 1; - while (it2 != itend) { - int cmpval = it1->compare(*it2); - if (cmpval == 1) { - it1->swap(*it2); - something_changed = true; - if (antisymm) - sig = -sig; - } else if (cmpval == 0 && antisymm) { - something_changed = true; - sig = 0; - } - it2++; - } - it1++; - } - - return something_changed ? sig : INT_MAX; -} - ex indexed::eval(int level) const { // First evaluate children, then we will end up here again if (level > 1) - return indexed(symmetry, evalchildren(level)); + return indexed(ex_to(symtree), evalchildren(level)); + + const ex &base = seq[0]; + + // If the base object is 0, the whole object is 0 + if (base.is_zero()) + return _ex0; + + // If the base object is a product, pull out the numeric factor + if (is_ex_exactly_of_type(base, mul) && is_ex_exactly_of_type(base.op(base.nops() - 1), numeric)) { + exvector v(seq); + ex f = ex_to(base.op(base.nops() - 1)); + v[0] = seq[0] / f; + return f * thisexprseq(v); + } // Canonicalize indices according to the symmetry properties - if (seq.size() > 2 && (symmetry != unknown && symmetry != mixed)) { + if (seq.size() > 2) { exvector v = seq; - int sig = canonicalize_indices(v.begin() + 1, v.end(), symmetry == antisymmetric); + GINAC_ASSERT(is_exactly_a(symtree)); + int sig = canonicalize(v.begin() + 1, ex_to(symtree)); if (sig != INT_MAX) { // Something has changed while sorting indices, more evaluations later if (sig == 0) - return _ex0(); + return _ex0; return ex(sig) * thisexprseq(v); } } // Let the class of the base object perform additional evaluations - return op(0).bp->eval_indexed(*this); + return ex_to(base).eval_indexed(*this); } ex indexed::thisexprseq(const exvector & v) const { - return indexed(symmetry, v); + return indexed(ex_to(symtree), v); } ex indexed::thisexprseq(exvector * vp) const { - return indexed(symmetry, vp); + return indexed(ex_to(symtree), vp); } ex indexed::expand(unsigned options) const @@ -364,7 +292,7 @@ ex indexed::expand(unsigned options) const // expand_indexed expands (a+b).i -> a.i + b.i const ex & base = seq[0]; - ex sum = _ex0(); + ex sum = _ex0; for (unsigned i=0; i 1) { - exvector::const_iterator it=seq.begin() + 1, itend = seq.end(); - while (it != itend) { - it->printraw(os); - it++; - if (it != itend) - os << ","; - } - } -} -void indexed::printtreeindices(std::ostream & os, unsigned indent) const -{ - if (seq.size() > 1) { exvector::const_iterator it=seq.begin() + 1, itend = seq.end(); - while (it != itend) { - os << std::string(indent + delta_indent, ' '); - it->printraw(os); - os << std::endl; - it++; - } - } -} -void indexed::printindices(std::ostream & os) const -{ - if (seq.size() > 1) { - exvector::const_iterator it=seq.begin() + 1, itend = seq.end(); - while (it != itend) { - it->print(os); - it++; + if (is_a(c)) { + + // TeX output: group by variance + bool first = true; + bool covariant = true; + + while (it != itend) { + bool cur_covariant = (is_ex_of_type(*it, varidx) ? ex_to(*it).is_covariant() : true); + if (first || cur_covariant != covariant) { // Variance changed + // The empty {} prevents indices from ending up on top of each other + if (!first) + c.s << "}{}"; + covariant = cur_covariant; + if (covariant) + c.s << "_{"; + else + c.s << "^{"; + } + it->print(c, level); + c.s << " "; + first = false; + it++; + } + c.s << "}"; + + } else { + + // Ordinary output + while (it != itend) { + it->print(c, level); + it++; + } } } } -/** Check whether all indices are of class idx. This function is used - * internally to make sure that all constructed indexed objects really - * carry indices and not some other classes. */ -bool indexed::all_indices_of_type_idx(void) const +/** Check whether all indices are of class idx and validate the symmetry + * tree. This function is used internally to make sure that all constructed + * indexed objects really carry indices and not some other classes. */ +void indexed::validate(void) const { GINAC_ASSERT(seq.size() > 0); exvector::const_iterator it = seq.begin() + 1, itend = seq.end(); while (it != itend) { if (!is_ex_of_type(*it, idx)) - return false; + throw(std::invalid_argument("indices of indexed object must be of type idx")); it++; } - return true; + + if (!symtree.is_zero()) { + if (!is_ex_exactly_of_type(symtree, symmetry)) + throw(std::invalid_argument("symmetry of indexed object must be of type symmetry")); + const_cast(ex_to(symtree)).validate(seq.size() - 1); + } +} + +/** Implementation of ex::diff() for an indexed object always returns 0. + * + * @see ex::diff */ +ex indexed::derivative(const symbol & s) const +{ + return _ex0; } ////////// // global functions ////////// -/** Given a vector of indices, split them into two vectors, one containing - * the free indices, the other containing the dummy indices. */ -static void find_free_and_dummy(exvector::const_iterator it, exvector::const_iterator itend, exvector & out_free, exvector & out_dummy) -{ - out_free.clear(); - out_dummy.clear(); - - // No indices? Then do nothing - if (it == itend) - return; - - // Only one index? Then it is a free one if it's not numeric - if (itend - it == 1) { - if (ex_to_idx(*it).is_symbolic()) - out_free.push_back(*it); - return; - } - - // Sort index vector. This will cause dummy indices come to lie next - // to each other (because the sort order is defined to guarantee this). - exvector v(it, itend); - sort_index_vector(v); - - // Find dummy pairs and free indices - it = v.begin(); itend = v.end(); - exvector::const_iterator last = it++; - while (it != itend) { - if (is_dummy_pair(*it, *last)) { - out_dummy.push_back(*last); - it++; - if (it == itend) - return; - } else { - if (!it->is_equal(*last) && ex_to_idx(*last).is_symbolic()) - out_free.push_back(*last); - } - last = it++; +struct idx_is_equal_ignore_dim : public std::binary_function { + bool operator() (const ex &lh, const ex &rh) const + { + if (lh.is_equal(rh)) + return true; + else + try { + // Replacing the dimension might cause an error (e.g. with + // index classes that only work in a fixed number of dimensions) + return lh.is_equal(ex_to(rh).replace_dim(ex_to(lh).get_dim())); + } catch (...) { + return false; + } } - if (ex_to_idx(*last).is_symbolic()) - out_free.push_back(*last); -} +}; /** Check whether two sorted index vectors are consistent (i.e. equal). */ static bool indices_consistent(const exvector & v1, const exvector & v2) @@ -491,15 +411,41 @@ static bool indices_consistent(const exvector & v1, const exvector & v2) if (v1.size() != v2.size()) return false; - // And also the indices themselves - exvector::const_iterator ait = v1.begin(), aitend = v1.end(), - bit = v2.begin(), bitend = v2.end(); - while (ait != aitend) { - if (!ait->is_equal(*bit)) - return false; - ait++; bit++; + return equal(v1.begin(), v1.end(), v2.begin(), idx_is_equal_ignore_dim()); +} + +exvector indexed::get_indices(void) const +{ + GINAC_ASSERT(seq.size() >= 1); + return exvector(seq.begin() + 1, seq.end()); +} + +exvector indexed::get_dummy_indices(void) const +{ + exvector free_indices, dummy_indices; + find_free_and_dummy(seq.begin() + 1, seq.end(), free_indices, dummy_indices); + return dummy_indices; +} + +exvector indexed::get_dummy_indices(const indexed & other) const +{ + exvector indices = get_free_indices(); + exvector other_indices = other.get_free_indices(); + indices.insert(indices.end(), other_indices.begin(), other_indices.end()); + exvector dummy_indices; + find_dummy_indices(indices, dummy_indices); + return dummy_indices; +} + +bool indexed::has_dummy_index_for(const ex & i) const +{ + exvector::const_iterator it = seq.begin() + 1, itend = seq.end(); + while (it != itend) { + if (is_dummy_pair(*it, i)) + return true; + it++; } - return true; + return false; } exvector indexed::get_free_indices(void) const @@ -535,7 +481,7 @@ exvector mul::get_free_indices(void) const // And remove the dummy indices exvector free_indices, dummy_indices; - find_free_and_dummy(un.begin(), un.end(), free_indices, dummy_indices); + find_free_and_dummy(un, free_indices, dummy_indices); return free_indices; } @@ -550,7 +496,7 @@ exvector ncmul::get_free_indices(void) const // And remove the dummy indices exvector free_indices, dummy_indices; - find_free_and_dummy(un.begin(), un.end(), free_indices, dummy_indices); + find_free_and_dummy(un, free_indices, dummy_indices); return free_indices; } @@ -560,9 +506,146 @@ exvector power::get_free_indices(void) const return basis.get_free_indices(); } +/** Rename dummy indices in an expression. + * + * @param e Expression to work on + * @param local_dummy_indices The set of dummy indices that appear in the + * expression "e" + * @param global_dummy_indices The set of dummy indices that have appeared + * before and which we would like to use in "e", too. This gets updated + * by the function */ +static ex rename_dummy_indices(const ex & e, exvector & global_dummy_indices, exvector & local_dummy_indices) +{ + unsigned global_size = global_dummy_indices.size(), + local_size = local_dummy_indices.size(); + + // Any local dummy indices at all? + if (local_size == 0) + return e; + + if (global_size < local_size) { + + // More local indices than we encountered before, add the new ones + // to the global set + int old_global_size = global_size; + int remaining = local_size - global_size; + exvector::const_iterator it = local_dummy_indices.begin(), itend = local_dummy_indices.end(); + while (it != itend && remaining > 0) { + if (find_if(global_dummy_indices.begin(), global_dummy_indices.end(), bind2nd(op0_is_equal(), *it)) == global_dummy_indices.end()) { + global_dummy_indices.push_back(*it); + global_size++; + remaining--; + } + it++; + } + + // If this is the first set of local indices, do nothing + if (old_global_size == 0) + return e; + } + GINAC_ASSERT(local_size <= global_size); + + // Construct lists of index symbols + exlist local_syms, global_syms; + for (unsigned i=0; i(local_uniq), ex_is_less()); + set_difference(global_syms.begin(), global_syms.end(), local_syms.begin(), local_syms.end(), std::back_insert_iterator(global_uniq), ex_is_less()); + + // Replace remaining non-common local index symbols by global ones + if (local_uniq.empty()) + return e; + else { + while (global_uniq.size() > local_uniq.size()) + global_uniq.pop_back(); + return e.subs(lst(local_uniq), lst(global_uniq)); + } +} + +/** Given a set of indices, extract those of class varidx. */ +static void find_variant_indices(const exvector & v, exvector & variant_indices) +{ + exvector::const_iterator it1, itend; + for (it1 = v.begin(), itend = v.end(); it1 != itend; ++it1) { + if (is_exactly_a(*it1)) + variant_indices.push_back(*it1); + } +} + +/** Raise/lower dummy indices in a single indexed objects to canonicalize their + * variance. + * + * @param e Object to work on + * @param variant_dummy_indices The set of indices that might need repositioning (will be changed by this function) + * @param moved_indices The set of indices that have been repositioned (will be changed by this function) + * @return true if 'e' was changed */ +bool reposition_dummy_indices(ex & e, exvector & variant_dummy_indices, exvector & moved_indices) +{ + bool something_changed = false; + + // If a dummy index is encountered for the first time in the + // product, pull it up, otherwise, pull it down + exvector::const_iterator it2, it2start, it2end; + for (it2start = ex_to(e).seq.begin(), it2end = ex_to(e).seq.end(), it2 = it2start + 1; it2 != it2end; ++it2) { + if (!is_exactly_a(*it2)) + continue; + + exvector::iterator vit, vitend; + for (vit = variant_dummy_indices.begin(), vitend = variant_dummy_indices.end(); vit != vitend; ++vit) { + if (it2->op(0).is_equal(vit->op(0))) { + if (ex_to(*it2).is_covariant()) { + e = e.subs(lst( + *it2 == ex_to(*it2).toggle_variance(), + ex_to(*it2).toggle_variance() == *it2 + )); + something_changed = true; + it2 = ex_to(e).seq.begin() + (it2 - it2start); + it2start = ex_to(e).seq.begin(); + it2end = ex_to(e).seq.end(); + } + moved_indices.push_back(*vit); + variant_dummy_indices.erase(vit); + goto next_index; + } + } + + for (vit = moved_indices.begin(), vitend = moved_indices.end(); vit != vitend; ++vit) { + if (it2->op(0).is_equal(vit->op(0))) { + if (ex_to(*it2).is_contravariant()) { + e = e.subs(*it2 == ex_to(*it2).toggle_variance()); + something_changed = true; + it2 = ex_to(e).seq.begin() + (it2 - it2start); + it2start = ex_to(e).seq.begin(); + it2end = ex_to(e).seq.end(); + } + goto next_index; + } + } + +next_index: ; + } + + return something_changed; +} + +/* Ordering that only compares the base expressions of indexed objects. */ +struct ex_base_is_less : public std::binary_function { + bool operator() (const ex &lh, const ex &rh) const + { + return (is_a(lh) ? lh.op(0) : lh).compare(is_a(rh) ? rh.op(0) : rh) < 0; + } +}; + /** Simplify product of indexed expressions (commutative, noncommutative and * simple squares), return list of free indices. */ -ex simplify_indexed_product(const ex & e, exvector & free_indices, const scalar_products & sp) +ex simplify_indexed_product(const ex & e, exvector & free_indices, exvector & dummy_indices, const scalar_products & sp) { // Remember whether the product was commutative or noncommutative // (because we chop it into factors and need to reassemble later) @@ -574,19 +657,19 @@ ex simplify_indexed_product(const ex & e, exvector & free_indices, const scalar_ if (is_ex_exactly_of_type(e, power)) { // We only get called for simple squares, split a^2 -> a*a - GINAC_ASSERT(e.op(1).is_equal(_ex2())); + GINAC_ASSERT(e.op(1).is_equal(_ex2)); v.push_back(e.op(0)); v.push_back(e.op(0)); } else { - for (int i=0; ireturn_type() != return_types::commutative); + + // Indexed factor found, get free indices and look for contraction + // candidates + exvector free1, dummy1; + find_free_and_dummy(ex_to(*it1).seq.begin() + 1, ex_to(*it1).seq.end(), free1, dummy1); + exvector::iterator it2; for (it2 = it1 + 1; it2 != itend; it2++) { if (!is_ex_of_type(*it2, indexed)) continue; + bool second_noncommutative = (it2->return_type() != return_types::commutative); + + // Find free indices of second factor and merge them with free + // indices of first factor + exvector un; + find_free_and_dummy(ex_to(*it2).seq.begin() + 1, ex_to(*it2).seq.end(), un, dummy1); + un.insert(un.end(), free1.begin(), free1.end()); + // Check whether the two factors share dummy indices - exvector un(ex_to_indexed(*it1).seq.begin() + 1, ex_to_indexed(*it1).seq.end()); - un.insert(un.end(), ex_to_indexed(*it2).seq.begin() + 1, ex_to_indexed(*it2).seq.end()); exvector free, dummy; - find_free_and_dummy(un.begin(), un.end(), free, dummy); - if (dummy.size() == 0) + find_free_and_dummy(un, free, dummy); + unsigned num_dummies = dummy.size(); + if (num_dummies == 0) continue; // At least one dummy index, is it a defined scalar product? - if (free.size() == 0) { + bool contracted = false; + if (free.empty()) { if (sp.is_defined(*it1, *it2)) { *it1 = sp.evaluate(*it1, *it2); - *it2 = _ex1(); - something_changed = true; - goto try_again; + *it2 = _ex1; + goto contraction_done; } } // Try to contract the first one with the second one - bool contracted = it1->op(0).bp->contract_with(it1, it2, v); + contracted = ex_to(it1->op(0)).contract_with(it1, it2, v); if (!contracted) { // That didn't work; maybe the second object knows how to // contract itself with the first one - contracted = it2->op(0).bp->contract_with(it2, it1, v); + contracted = ex_to(it2->op(0)).contract_with(it2, it1, v); } if (contracted) { - something_changed = true; +contraction_done: + if (first_noncommutative || second_noncommutative + || is_ex_exactly_of_type(*it1, add) || is_ex_exactly_of_type(*it2, add) + || is_ex_exactly_of_type(*it1, mul) || is_ex_exactly_of_type(*it2, mul) + || is_ex_exactly_of_type(*it1, ncmul) || is_ex_exactly_of_type(*it2, ncmul)) { + + // One of the factors became a sum or product: + // re-expand expression and run again + // Non-commutative products are always re-expanded to give + // simplify_ncmul() the chance to re-order and canonicalize + // the product + ex r = (non_commutative ? ex(ncmul(v, true)) : ex(mul(v))); + return simplify_indexed(r, free_indices, dummy_indices, sp); + } // Both objects may have new indices now or they might // even not be indexed objects any more, so we have to // start over + something_changed = true; goto try_again; } } } // Find free indices (concatenate them all and call find_free_and_dummy()) - exvector un, dummy_indices; - it1 = v.begin(); itend = v.end(); - while (it1 != itend) { + // and all dummy indices that appear + exvector un, individual_dummy_indices; + for (it1 = v.begin(), itend = v.end(); it1 != itend; ++it1) { + exvector free_indices_of_factor; if (is_ex_of_type(*it1, indexed)) { - const indexed & o = ex_to_indexed(*it1); - un.insert(un.end(), o.seq.begin() + 1, o.seq.end()); + exvector dummy_indices_of_factor; + find_free_and_dummy(ex_to(*it1).seq.begin() + 1, ex_to(*it1).seq.end(), free_indices_of_factor, dummy_indices_of_factor); + individual_dummy_indices.insert(individual_dummy_indices.end(), dummy_indices_of_factor.begin(), dummy_indices_of_factor.end()); + } else + free_indices_of_factor = it1->get_free_indices(); + un.insert(un.end(), free_indices_of_factor.begin(), free_indices_of_factor.end()); + } + exvector local_dummy_indices; + find_free_and_dummy(un, free_indices, local_dummy_indices); + local_dummy_indices.insert(local_dummy_indices.end(), individual_dummy_indices.begin(), individual_dummy_indices.end()); + + // Filter out the dummy indices with variance + exvector variant_dummy_indices; + find_variant_indices(local_dummy_indices, variant_dummy_indices); + + // Any indices with variance present at all? + if (!variant_dummy_indices.empty()) { + + // Yes, bring the product into a canonical order that only depends on + // the base expressions of indexed objects + if (!non_commutative) + std::sort(v.begin(), v.end(), ex_base_is_less()); + + exvector moved_indices; + + // Iterate over all indexed objects in the product + for (it1 = v.begin(), itend = v.end(); it1 != itend; ++it1) { + if (!is_ex_of_type(*it1, indexed)) + continue; + + if (reposition_dummy_indices(*it1, variant_dummy_indices, moved_indices)) + something_changed = true; } - it1++; } - find_free_and_dummy(un.begin(), un.end(), free_indices, dummy_indices); - if (something_changed) { - if (non_commutative) - return ncmul(v); - else - return mul(v); - } else - return e; + ex r; + if (something_changed) + r = non_commutative ? ex(ncmul(v, true)) : ex(mul(v)); + else + r = e; + + // The result should be symmetric with respect to exchange of dummy + // indices, so if the symmetrization vanishes, the whole expression is + // zero. This detects things like eps.i.j.k * p.j * p.k = 0. + if (local_dummy_indices.size() >= 2) { + lst dummy_syms; + for (int i=0; i(r.op(0).op(0)).scalar_mul_indexed(r.op(0), ex_to(r.op(1))); + else + return r; } +/** This structure stores the original and symmetrized versions of terms + * obtained during the simplification of sums. */ +class terminfo { +public: + terminfo(const ex & orig_, const ex & symm_) : orig(orig_), symm(symm_) {} + + ex orig; /**< original term */ + ex symm; /**< symmtrized term */ +}; + +class terminfo_is_less { +public: + bool operator() (const terminfo & ti1, const terminfo & ti2) const + { + return (ti1.symm.compare(ti2.symm) < 0); + } +}; + +/** This structure stores the individual symmetrized terms obtained during + * the simplification of sums. */ +class symminfo { +public: + symminfo() : num(0) {} + + symminfo(const ex & symmterm_, const ex & orig_, unsigned num_) : orig(orig_), num(num_) + { + if (is_exactly_a(symmterm_) && is_exactly_a(symmterm_.op(symmterm_.nops()-1))) { + coeff = symmterm_.op(symmterm_.nops()-1); + symmterm = symmterm_ / coeff; + } else { + coeff = 1; + symmterm = symmterm_; + } + } + + ex symmterm; /**< symmetrized term */ + ex coeff; /**< coefficient of symmetrized term */ + ex orig; /**< original term */ + unsigned num; /**< how many symmetrized terms resulted from the original term */ +}; + +class symminfo_is_less_by_symmterm { +public: + bool operator() (const symminfo & si1, const symminfo & si2) const + { + return (si1.symmterm.compare(si2.symmterm) < 0); + } +}; + +class symminfo_is_less_by_orig { +public: + bool operator() (const symminfo & si1, const symminfo & si2) const + { + return (si1.orig.compare(si2.orig) < 0); + } +}; + /** Simplify indexed expression, return list of free indices. */ -ex simplify_indexed(const ex & e, exvector & free_indices, const scalar_products & sp) +ex simplify_indexed(const ex & e, exvector & free_indices, exvector & dummy_indices, const scalar_products & sp) { // Expand the expression ex e_expanded = e.expand(); // Simplification of single indexed object: just find the free indices + // and perform dummy index renaming/repositioning if (is_ex_of_type(e_expanded, indexed)) { - const indexed &i = ex_to_indexed(e_expanded); - exvector dummy_indices; - find_free_and_dummy(i.seq.begin() + 1, i.seq.end(), free_indices, dummy_indices); - return e_expanded; + + // Find the dummy indices + const indexed &i = ex_to(e_expanded); + exvector local_dummy_indices; + find_free_and_dummy(i.seq.begin() + 1, i.seq.end(), free_indices, local_dummy_indices); + + // Filter out the dummy indices with variance + exvector variant_dummy_indices; + find_variant_indices(local_dummy_indices, variant_dummy_indices); + + // Any indices with variance present at all? + if (!variant_dummy_indices.empty()) { + + // Yes, reposition them + exvector moved_indices; + reposition_dummy_indices(e_expanded, variant_dummy_indices, moved_indices); + } + + // Rename the dummy indices + return rename_dummy_indices(e_expanded, dummy_indices, local_dummy_indices); } // Simplification of sum = sum of simplifications, check consistency of // free indices in each term if (is_ex_exactly_of_type(e_expanded, add)) { - ex sum = _ex0(); + bool first = true; + ex sum; + free_indices.clear(); for (unsigned i=0; i(sum.op(0)).add_indexed(sum, term); + else + sum += term; + } + } } - return sum; + // If the sum turns out to be zero, we are finished + if (sum.is_zero()) { + free_indices.clear(); + return sum; + } + + // More than one term and more than one dummy index? + int num_terms_orig = (is_exactly_a(sum) ? sum.nops() : 1); + if (num_terms_orig < 2 || dummy_indices.size() < 2) + return sum; + + // Yes, construct list of all dummy index symbols + lst dummy_syms; + for (int i=0; i terms; + for (unsigned i=0; i terms_pass2; + for (std::vector::const_iterator i=terms.begin(); i!=terms.end(); ) { + unsigned num = 1; + std::vector::const_iterator j = i + 1; + while (j != terms.end() && j->symm == i->symm) { + num++; + j++; + } + terms_pass2.push_back(terminfo(i->orig * num, i->symm * num)); + i = j; + } + + // If there is only one term left, we are finished + if (terms_pass2.size() == 1) + return terms_pass2[0].orig; + + // Chop the symmetrized terms into subterms + std::vector sy; + for (std::vector::const_iterator i=terms_pass2.begin(); i!=terms_pass2.end(); ++i) { + if (is_exactly_a(i->symm)) { + unsigned num = i->symm.nops(); + for (unsigned j=0; jsymm.op(j), i->orig, num)); + } else + sy.push_back(symminfo(i->symm, i->orig, 1)); + } + + // Sort by symmetrized subterms + std::sort(sy.begin(), sy.end(), symminfo_is_less_by_symmterm()); + + // Combine equal symmetrized subterms + std::vector sy_pass2; + exvector result; + for (std::vector::const_iterator i=sy.begin(); i!=sy.end(); ) { + + // Combine equal terms + std::vector::const_iterator j = i + 1; + if (j != sy.end() && j->symmterm == i->symmterm) { + + // More than one term, collect the coefficients + ex coeff = i->coeff; + while (j != sy.end() && j->symmterm == i->symmterm) { + coeff += j->coeff; + j++; + } + + // Add combined term to result + if (!coeff.is_zero()) + result.push_back(coeff * i->symmterm); + + } else { + + // Single term, store for second pass + sy_pass2.push_back(*i); + } + + i = j; + } + + // Were there any remaining terms that didn't get combined? + if (sy_pass2.size() > 0) { + + // Yes, sort by their original terms + std::sort(sy_pass2.begin(), sy_pass2.end(), symminfo_is_less_by_orig()); + + for (std::vector::const_iterator i=sy_pass2.begin(); i!=sy_pass2.end(); ) { + + // How many symmetrized terms of this original term are left? + unsigned num = 1; + std::vector::const_iterator j = i + 1; + while (j != sy_pass2.end() && j->orig == i->orig) { + num++; + j++; + } + + if (num == i->num) { + + // All terms left, then add the original term to the result + result.push_back(i->orig); + + } else { + + // Some terms were combined with others, add up the remaining symmetrized terms + std::vector::const_iterator k; + for (k=i; k!=j; k++) + result.push_back(k->coeff * k->symmterm); + } + + i = j; + } + } + + // Add all resulting terms + ex sum_symm = (new add(result))->setflag(status_flags::dynallocated); + if (sum_symm.is_zero()) + free_indices.clear(); + return sum_symm; } // Simplification of products if (is_ex_exactly_of_type(e_expanded, mul) || is_ex_exactly_of_type(e_expanded, ncmul) - || (is_ex_exactly_of_type(e_expanded, power) && is_ex_of_type(e_expanded.op(0), indexed) && e_expanded.op(1).is_equal(_ex2()))) - return simplify_indexed_product(e_expanded, free_indices, sp); + || (is_ex_exactly_of_type(e_expanded, power) && is_ex_of_type(e_expanded.op(0), indexed) && e_expanded.op(1).is_equal(_ex2))) + return simplify_indexed_product(e_expanded, free_indices, dummy_indices, sp); // Cannot do anything free_indices.clear(); return e_expanded; } -ex simplify_indexed(const ex & e) +/** Simplify/canonicalize expression containing indexed objects. This + * performs contraction of dummy indices where possible and checks whether + * the free indices in sums are consistent. + * + * @return simplified expression */ +ex ex::simplify_indexed(void) const { - exvector free_indices; + exvector free_indices, dummy_indices; scalar_products sp; - return simplify_indexed(e, free_indices, sp); + return GiNaC::simplify_indexed(*this, free_indices, dummy_indices, sp); } -ex simplify_indexed(const ex & e, const scalar_products & sp) +/** Simplify/canonicalize expression containing indexed objects. This + * performs contraction of dummy indices where possible, checks whether + * the free indices in sums are consistent, and automatically replaces + * scalar products by known values if desired. + * + * @param sp Scalar products to be replaced automatically + * @return simplified expression */ +ex ex::simplify_indexed(const scalar_products & sp) const { - exvector free_indices; - return simplify_indexed(e, free_indices, sp); + exvector free_indices, dummy_indices; + return GiNaC::simplify_indexed(*this, free_indices, dummy_indices, sp); +} + +/** Symmetrize expression over its free indices. */ +ex ex::symmetrize(void) const +{ + return GiNaC::symmetrize(*this, get_free_indices()); +} + +/** Antisymmetrize expression over its free indices. */ +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()); } ////////// @@ -732,6 +1139,19 @@ void scalar_products::add(const ex & v1, const ex & v2, const ex & sp) spm[make_key(v1, v2)] = sp; } +void scalar_products::add_vectors(const lst & l) +{ + // Add all possible pairs of products + unsigned num = l.nops(); + for (unsigned i=0; i