- epsilon*epsilon contractions work
[ginac.git] / ginac / indexed.cpp
1 /** @file indexed.cpp
2  *
3  *  Implementation of GiNaC's indexed expressions. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21  */
22
23 #include <stdexcept>
24 #include <algorithm>
25
26 #include "indexed.h"
27 #include "idx.h"
28 #include "add.h"
29 #include "mul.h"
30 #include "ncmul.h"
31 #include "power.h"
32 #include "symmetry.h"
33 #include "lst.h"
34 #include "print.h"
35 #include "archive.h"
36 #include "utils.h"
37 #include "debugmsg.h"
38
39 namespace GiNaC {
40
41 GINAC_IMPLEMENT_REGISTERED_CLASS(indexed, exprseq)
42
43 //////////
44 // default constructor, destructor, copy constructor assignment operator and helpers
45 //////////
46
47 indexed::indexed() : symtree(sy_none())
48 {
49         debugmsg("indexed default constructor", LOGLEVEL_CONSTRUCT);
50         tinfo_key = TINFO_indexed;
51 }
52
53 void indexed::copy(const indexed & other)
54 {
55         inherited::copy(other);
56         symtree = other.symtree;
57 }
58
59 DEFAULT_DESTROY(indexed)
60
61 //////////
62 // other constructors
63 //////////
64
65 indexed::indexed(const ex & b) : inherited(b), symtree(sy_none())
66 {
67         debugmsg("indexed constructor from ex", LOGLEVEL_CONSTRUCT);
68         tinfo_key = TINFO_indexed;
69         validate();
70 }
71
72 indexed::indexed(const ex & b, const ex & i1) : inherited(b, i1), symtree(sy_none())
73 {
74         debugmsg("indexed constructor from ex,ex", LOGLEVEL_CONSTRUCT);
75         tinfo_key = TINFO_indexed;
76         validate();
77 }
78
79 indexed::indexed(const ex & b, const ex & i1, const ex & i2) : inherited(b, i1, i2), symtree(sy_none())
80 {
81         debugmsg("indexed constructor from ex,ex,ex", LOGLEVEL_CONSTRUCT);
82         tinfo_key = TINFO_indexed;
83         validate();
84 }
85
86 indexed::indexed(const ex & b, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symtree(sy_none())
87 {
88         debugmsg("indexed constructor from ex,ex,ex,ex", LOGLEVEL_CONSTRUCT);
89         tinfo_key = TINFO_indexed;
90         validate();
91 }
92
93 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())
94 {
95         debugmsg("indexed constructor from ex,ex,ex,ex,ex", LOGLEVEL_CONSTRUCT);
96         tinfo_key = TINFO_indexed;
97         validate();
98 }
99
100 indexed::indexed(const ex & b, const symmetry & symm, const ex & i1, const ex & i2) : inherited(b, i1, i2), symtree(symm)
101 {
102         debugmsg("indexed constructor from ex,symmetry,ex,ex", LOGLEVEL_CONSTRUCT);
103         tinfo_key = TINFO_indexed;
104         validate();
105 }
106
107 indexed::indexed(const ex & b, const symmetry & symm, const ex & i1, const ex & i2, const ex & i3) : inherited(b, i1, i2, i3), symtree(symm)
108 {
109         debugmsg("indexed constructor from ex,symmetry,ex,ex,ex", LOGLEVEL_CONSTRUCT);
110         tinfo_key = TINFO_indexed;
111         validate();
112 }
113
114 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)
115 {
116         debugmsg("indexed constructor from ex,symmetry,ex,ex,ex,ex", LOGLEVEL_CONSTRUCT);
117         tinfo_key = TINFO_indexed;
118         validate();
119 }
120
121 indexed::indexed(const ex & b, const exvector & v) : inherited(b), symtree(sy_none())
122 {
123         debugmsg("indexed constructor from ex,exvector", LOGLEVEL_CONSTRUCT);
124         seq.insert(seq.end(), v.begin(), v.end());
125         tinfo_key = TINFO_indexed;
126         validate();
127 }
128
129 indexed::indexed(const ex & b, const symmetry & symm, const exvector & v) : inherited(b), symtree(symm)
130 {
131         debugmsg("indexed constructor from ex,symmetry,exvector", LOGLEVEL_CONSTRUCT);
132         seq.insert(seq.end(), v.begin(), v.end());
133         tinfo_key = TINFO_indexed;
134         validate();
135 }
136
137 indexed::indexed(const symmetry & symm, const exprseq & es) : inherited(es), symtree(symm)
138 {
139         debugmsg("indexed constructor from symmetry,exprseq", LOGLEVEL_CONSTRUCT);
140         tinfo_key = TINFO_indexed;
141 }
142
143 indexed::indexed(const symmetry & symm, const exvector & v, bool discardable) : inherited(v, discardable), symtree(symm)
144 {
145         debugmsg("indexed constructor from symmetry,exvector", LOGLEVEL_CONSTRUCT);
146         tinfo_key = TINFO_indexed;
147 }
148
149 indexed::indexed(const symmetry & symm, exvector * vp) : inherited(vp), symtree(symm)
150 {
151         debugmsg("indexed constructor from symmetry,exvector *", LOGLEVEL_CONSTRUCT);
152         tinfo_key = TINFO_indexed;
153 }
154
155 //////////
156 // archiving
157 //////////
158
159 indexed::indexed(const archive_node &n, const lst &sym_lst) : inherited(n, sym_lst)
160 {
161         debugmsg("indexed constructor from archive_node", LOGLEVEL_CONSTRUCT);
162         if (!n.find_ex("symmetry", symtree, sym_lst)) {
163                 // GiNaC versions <= 0.9.0 had an unsigned "symmetry" property
164                 unsigned symm = 0;
165                 n.find_unsigned("symmetry", symm);
166                 switch (symm) {
167                         case 1:
168                                 symtree = sy_symm();
169                                 break;
170                         case 2:
171                                 symtree = sy_anti();
172                                 break;
173                         default:
174                                 symtree = sy_none();
175                                 break;
176                 }
177                 ex_to_nonconst_symmetry(symtree).validate(seq.size() - 1);
178         }
179 }
180
181 void indexed::archive(archive_node &n) const
182 {
183         inherited::archive(n);
184         n.add_ex("symmetry", symtree);
185 }
186
187 DEFAULT_UNARCHIVE(indexed)
188
189 //////////
190 // functions overriding virtual functions from base classes
191 //////////
192
193 void indexed::print(const print_context & c, unsigned level) const
194 {
195         debugmsg("indexed print", LOGLEVEL_PRINT);
196         GINAC_ASSERT(seq.size() > 0);
197
198         if (is_of_type(c, print_tree)) {
199
200                 c.s << std::string(level, ' ') << class_name()
201                     << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec
202                     << ", " << seq.size()-1 << " indices"
203                     << ", symmetry=" << symtree << std::endl;
204                 unsigned delta_indent = static_cast<const print_tree &>(c).delta_indent;
205                 seq[0].print(c, level + delta_indent);
206                 printindices(c, level + delta_indent);
207
208         } else {
209
210                 bool is_tex = is_of_type(c, print_latex);
211                 const ex & base = seq[0];
212                 bool need_parens = is_ex_exactly_of_type(base, add) || is_ex_exactly_of_type(base, mul)
213                                 || is_ex_exactly_of_type(base, ncmul) || is_ex_exactly_of_type(base, power)
214                                 || is_ex_of_type(base, indexed);
215                 if (is_tex)
216                         c.s << "{";
217                 if (need_parens)
218                         c.s << "(";
219                 base.print(c);
220                 if (need_parens)
221                         c.s << ")";
222                 if (is_tex)
223                         c.s << "}";
224                 printindices(c, level);
225         }
226 }
227
228 bool indexed::info(unsigned inf) const
229 {
230         if (inf == info_flags::indexed) return true;
231         if (inf == info_flags::has_indices) return seq.size() > 1;
232         return inherited::info(inf);
233 }
234
235 struct idx_is_not : public std::binary_function<ex, unsigned, bool> {
236         bool operator() (const ex & e, unsigned inf) const {
237                 return !(ex_to<idx>(e).get_value().info(inf));
238         }
239 };
240
241 bool indexed::all_index_values_are(unsigned inf) const
242 {
243         // No indices? Then no property can be fulfilled
244         if (seq.size() < 2)
245                 return false;
246
247         // Check all indices
248         return find_if(seq.begin() + 1, seq.end(), bind2nd(idx_is_not(), inf)) == seq.end();
249 }
250
251 int indexed::compare_same_type(const basic & other) const
252 {
253         GINAC_ASSERT(is_of_type(other, indexed));
254         return inherited::compare_same_type(other);
255 }
256
257 ex indexed::eval(int level) const
258 {
259         // First evaluate children, then we will end up here again
260         if (level > 1)
261                 return indexed(ex_to<symmetry>(symtree), evalchildren(level));
262
263         const ex &base = seq[0];
264
265         // If the base object is 0, the whole object is 0
266         if (base.is_zero())
267                 return _ex0();
268
269         // If the base object is a product, pull out the numeric factor
270         if (is_ex_exactly_of_type(base, mul) && is_ex_exactly_of_type(base.op(base.nops() - 1), numeric)) {
271                 exvector v(seq);
272                 ex f = ex_to<numeric>(base.op(base.nops() - 1));
273                 v[0] = seq[0] / f;
274                 return f * thisexprseq(v);
275         }
276
277         // Canonicalize indices according to the symmetry properties
278         if (seq.size() > 2) {
279                 exvector v = seq;
280                 GINAC_ASSERT(is_ex_exactly_of_type(symtree, symmetry));
281                 int sig = canonicalize(v.begin() + 1, ex_to<symmetry>(symtree));
282                 if (sig != INT_MAX) {
283                         // Something has changed while sorting indices, more evaluations later
284                         if (sig == 0)
285                                 return _ex0();
286                         return ex(sig) * thisexprseq(v);
287                 }
288         }
289
290         // Let the class of the base object perform additional evaluations
291         return base.bp->eval_indexed(*this);
292 }
293
294 int indexed::degree(const ex & s) const
295 {
296         return is_equal(*s.bp) ? 1 : 0;
297 }
298
299 int indexed::ldegree(const ex & s) const
300 {
301         return is_equal(*s.bp) ? 1 : 0;
302 }
303
304 ex indexed::coeff(const ex & s, int n) const
305 {
306         if (is_equal(*s.bp))
307                 return n==1 ? _ex1() : _ex0();
308         else
309                 return n==0 ? ex(*this) : _ex0();
310 }
311
312 ex indexed::thisexprseq(const exvector & v) const
313 {
314         return indexed(ex_to<symmetry>(symtree), v);
315 }
316
317 ex indexed::thisexprseq(exvector * vp) const
318 {
319         return indexed(ex_to<symmetry>(symtree), vp);
320 }
321
322 ex indexed::expand(unsigned options) const
323 {
324         GINAC_ASSERT(seq.size() > 0);
325
326         if ((options & expand_options::expand_indexed) && is_ex_exactly_of_type(seq[0], add)) {
327
328                 // expand_indexed expands (a+b).i -> a.i + b.i
329                 const ex & base = seq[0];
330                 ex sum = _ex0();
331                 for (unsigned i=0; i<base.nops(); i++) {
332                         exvector s = seq;
333                         s[0] = base.op(i);
334                         sum += thisexprseq(s).expand();
335                 }
336                 return sum;
337
338         } else
339                 return inherited::expand(options);
340 }
341
342 //////////
343 // virtual functions which can be overridden by derived classes
344 //////////
345
346 // none
347
348 //////////
349 // non-virtual functions in this class
350 //////////
351
352 void indexed::printindices(const print_context & c, unsigned level) const
353 {
354         if (seq.size() > 1) {
355
356                 exvector::const_iterator it=seq.begin() + 1, itend = seq.end();
357
358                 if (is_of_type(c, print_latex)) {
359
360                         // TeX output: group by variance
361                         bool first = true;
362                         bool covariant = true;
363
364                         while (it != itend) {
365                                 bool cur_covariant = (is_ex_of_type(*it, varidx) ? ex_to<varidx>(*it).is_covariant() : true);
366                                 if (first || cur_covariant != covariant) {
367                                         if (!first)
368                                                 c.s << "}";
369                                         covariant = cur_covariant;
370                                         if (covariant)
371                                                 c.s << "_{";
372                                         else
373                                                 c.s << "^{";
374                                 }
375                                 it->print(c, level);
376                                 c.s << " ";
377                                 first = false;
378                                 it++;
379                         }
380                         c.s << "}";
381
382                 } else {
383
384                         // Ordinary output
385                         while (it != itend) {
386                                 it->print(c, level);
387                                 it++;
388                         }
389                 }
390         }
391 }
392
393 /** Check whether all indices are of class idx and validate the symmetry
394  *  tree. This function is used internally to make sure that all constructed
395  *  indexed objects really carry indices and not some other classes. */
396 void indexed::validate(void) const
397 {
398         GINAC_ASSERT(seq.size() > 0);
399         exvector::const_iterator it = seq.begin() + 1, itend = seq.end();
400         while (it != itend) {
401                 if (!is_ex_of_type(*it, idx))
402                         throw(std::invalid_argument("indices of indexed object must be of type idx"));
403                 it++;
404         }
405
406         if (!symtree.is_zero()) {
407                 if (!is_ex_exactly_of_type(symtree, symmetry))
408                         throw(std::invalid_argument("symmetry of indexed object must be of type symmetry"));
409                 ex_to_nonconst_symmetry(symtree).validate(seq.size() - 1);
410         }
411 }
412
413 /** Implementation of ex::diff() for an indexed object always returns 0.
414  *
415  *  @see ex::diff */
416 ex indexed::derivative(const symbol & s) const
417 {
418         return _ex0();
419 }
420
421 //////////
422 // global functions
423 //////////
424
425 /** Check whether two sorted index vectors are consistent (i.e. equal). */
426 static bool indices_consistent(const exvector & v1, const exvector & v2)
427 {
428         // Number of indices must be the same
429         if (v1.size() != v2.size())
430                 return false;
431
432         return equal(v1.begin(), v1.end(), v2.begin(), ex_is_equal());
433 }
434
435 exvector indexed::get_indices(void) const
436 {
437         GINAC_ASSERT(seq.size() >= 1);
438         return exvector(seq.begin() + 1, seq.end());
439 }
440
441 exvector indexed::get_dummy_indices(void) const
442 {
443         exvector free_indices, dummy_indices;
444         find_free_and_dummy(seq.begin() + 1, seq.end(), free_indices, dummy_indices);
445         return dummy_indices;
446 }
447
448 exvector indexed::get_dummy_indices(const indexed & other) const
449 {
450         exvector indices = get_free_indices();
451         exvector other_indices = other.get_free_indices();
452         indices.insert(indices.end(), other_indices.begin(), other_indices.end());
453         exvector dummy_indices;
454         find_dummy_indices(indices, dummy_indices);
455         return dummy_indices;
456 }
457
458 bool indexed::has_dummy_index_for(const ex & i) const
459 {
460         exvector::const_iterator it = seq.begin() + 1, itend = seq.end();
461         while (it != itend) {
462                 if (is_dummy_pair(*it, i))
463                         return true;
464                 it++;
465         }
466         return false;
467 }
468
469 exvector indexed::get_free_indices(void) const
470 {
471         exvector free_indices, dummy_indices;
472         find_free_and_dummy(seq.begin() + 1, seq.end(), free_indices, dummy_indices);
473         return free_indices;
474 }
475
476 exvector add::get_free_indices(void) const
477 {
478         exvector free_indices;
479         for (unsigned i=0; i<nops(); i++) {
480                 if (i == 0)
481                         free_indices = op(i).get_free_indices();
482                 else {
483                         exvector free_indices_of_term = op(i).get_free_indices();
484                         if (!indices_consistent(free_indices, free_indices_of_term))
485                                 throw (std::runtime_error("add::get_free_indices: inconsistent indices in sum"));
486                 }
487         }
488         return free_indices;
489 }
490
491 exvector mul::get_free_indices(void) const
492 {
493         // Concatenate free indices of all factors
494         exvector un;
495         for (unsigned i=0; i<nops(); i++) {
496                 exvector free_indices_of_factor = op(i).get_free_indices();
497                 un.insert(un.end(), free_indices_of_factor.begin(), free_indices_of_factor.end());
498         }
499
500         // And remove the dummy indices
501         exvector free_indices, dummy_indices;
502         find_free_and_dummy(un, free_indices, dummy_indices);
503         return free_indices;
504 }
505
506 exvector ncmul::get_free_indices(void) const
507 {
508         // Concatenate free indices of all factors
509         exvector un;
510         for (unsigned i=0; i<nops(); i++) {
511                 exvector free_indices_of_factor = op(i).get_free_indices();
512                 un.insert(un.end(), free_indices_of_factor.begin(), free_indices_of_factor.end());
513         }
514
515         // And remove the dummy indices
516         exvector free_indices, dummy_indices;
517         find_free_and_dummy(un, free_indices, dummy_indices);
518         return free_indices;
519 }
520
521 exvector power::get_free_indices(void) const
522 {
523         // Return free indices of basis
524         return basis.get_free_indices();
525 }
526
527 /** Rename dummy indices in an expression.
528  *
529  *  @param e Expression to be worked on
530  *  @param local_dummy_indices The set of dummy indices that appear in the
531  *    expression "e"
532  *  @param global_dummy_indices The set of dummy indices that have appeared
533  *    before and which we would like to use in "e", too. This gets updated
534  *    by the function */
535 static ex rename_dummy_indices(const ex & e, exvector & global_dummy_indices, exvector & local_dummy_indices)
536 {
537         unsigned global_size = global_dummy_indices.size(),
538                  local_size = local_dummy_indices.size();
539
540         // Any local dummy indices at all?
541         if (local_size == 0)
542                 return e;
543
544         if (global_size < local_size) {
545
546                 // More local indices than we encountered before, add the new ones
547                 // to the global set
548                 int old_global_size = global_size;
549                 int remaining = local_size - global_size;
550                 exvector::const_iterator it = local_dummy_indices.begin(), itend = local_dummy_indices.end();
551                 while (it != itend && remaining > 0) {
552                         if (find_if(global_dummy_indices.begin(), global_dummy_indices.end(), bind2nd(ex_is_equal(), *it)) == global_dummy_indices.end()) {
553                                 global_dummy_indices.push_back(*it);
554                                 global_size++;
555                                 remaining--;
556                         }
557                         it++;
558                 }
559                 shaker_sort(global_dummy_indices.begin(), global_dummy_indices.end(), ex_is_less(), ex_swap());
560
561                 // If this is the first set of local indices, do nothing
562                 if (old_global_size == 0)
563                         return e;
564         }
565         GINAC_ASSERT(local_size <= global_size);
566
567         // Construct lists of index symbols
568         exlist local_syms, global_syms;
569         for (unsigned i=0; i<local_size; i++)
570                 local_syms.push_back(local_dummy_indices[i].op(0));
571         shaker_sort(local_syms.begin(), local_syms.end(), ex_is_less(), ex_swap());
572         for (unsigned i=0; i<global_size; i++)
573                 global_syms.push_back(global_dummy_indices[i].op(0));
574
575         // Remove common indices
576         exlist local_uniq, global_uniq;
577         set_difference(local_syms.begin(), local_syms.end(), global_syms.begin(), global_syms.end(), std::back_insert_iterator<exlist>(local_uniq), ex_is_less());
578         set_difference(global_syms.begin(), global_syms.end(), local_syms.begin(), local_syms.end(), std::back_insert_iterator<exlist>(global_uniq), ex_is_less());
579
580         // Replace remaining non-common local index symbols by global ones
581         if (local_uniq.empty())
582                 return e;
583         else {
584                 while (global_uniq.size() > local_uniq.size())
585                         global_uniq.pop_back();
586                 return e.subs(lst(local_uniq), lst(global_uniq));
587         }
588 }
589
590 /** Simplify product of indexed expressions (commutative, noncommutative and
591  *  simple squares), return list of free indices. */
592 ex simplify_indexed_product(const ex & e, exvector & free_indices, exvector & dummy_indices, const scalar_products & sp)
593 {
594         // Remember whether the product was commutative or noncommutative
595         // (because we chop it into factors and need to reassemble later)
596         bool non_commutative = is_ex_exactly_of_type(e, ncmul);
597
598         // Collect factors in an exvector, store squares twice
599         exvector v;
600         v.reserve(e.nops() * 2);
601
602         if (is_ex_exactly_of_type(e, power)) {
603                 // We only get called for simple squares, split a^2 -> a*a
604                 GINAC_ASSERT(e.op(1).is_equal(_ex2()));
605                 v.push_back(e.op(0));
606                 v.push_back(e.op(0));
607         } else {
608                 for (unsigned i=0; i<e.nops(); i++) {
609                         ex f = e.op(i);
610                         if (is_ex_exactly_of_type(f, power) && f.op(1).is_equal(_ex2())) {
611                                 v.push_back(f.op(0));
612                     v.push_back(f.op(0));
613                         } else if (is_ex_exactly_of_type(f, ncmul)) {
614                                 // Noncommutative factor found, split it as well
615                                 non_commutative = true; // everything becomes noncommutative, ncmul will sort out the commutative factors later
616                                 for (unsigned j=0; j<f.nops(); j++)
617                                         v.push_back(f.op(j));
618                         } else
619                                 v.push_back(f);
620                 }
621         }
622
623         // Perform contractions
624         bool something_changed = false;
625         GINAC_ASSERT(v.size() > 1);
626         exvector::iterator it1, itend = v.end(), next_to_last = itend - 1;
627         for (it1 = v.begin(); it1 != next_to_last; it1++) {
628
629 try_again:
630                 if (!is_ex_of_type(*it1, indexed))
631                         continue;
632
633                 bool first_noncommutative = (it1->return_type() != return_types::commutative);
634
635                 // Indexed factor found, get free indices and look for contraction
636                 // candidates
637                 exvector free1, dummy1;
638                 find_free_and_dummy(ex_to<indexed>(*it1).seq.begin() + 1, ex_to<indexed>(*it1).seq.end(), free1, dummy1);
639
640                 exvector::iterator it2;
641                 for (it2 = it1 + 1; it2 != itend; it2++) {
642
643                         if (!is_ex_of_type(*it2, indexed))
644                                 continue;
645
646                         bool second_noncommutative = (it2->return_type() != return_types::commutative);
647
648                         // Find free indices of second factor and merge them with free
649                         // indices of first factor
650                         exvector un;
651                         find_free_and_dummy(ex_to<indexed>(*it2).seq.begin() + 1, ex_to<indexed>(*it2).seq.end(), un, dummy1);
652                         un.insert(un.end(), free1.begin(), free1.end());
653
654                         // Check whether the two factors share dummy indices
655                         exvector free, dummy;
656                         find_free_and_dummy(un, free, dummy);
657                         unsigned num_dummies = dummy.size();
658                         if (num_dummies == 0)
659                                 continue;
660
661                         // At least one dummy index, is it a defined scalar product?
662                         bool contracted = false;
663                         if (free.empty()) {
664                                 if (sp.is_defined(*it1, *it2)) {
665                                         *it1 = sp.evaluate(*it1, *it2);
666                                         *it2 = _ex1();
667                                         goto contraction_done;
668                                 }
669                         }
670
671                         // Try to contract the first one with the second one
672                         contracted = it1->op(0).bp->contract_with(it1, it2, v);
673                         if (!contracted) {
674
675                                 // That didn't work; maybe the second object knows how to
676                                 // contract itself with the first one
677                                 contracted = it2->op(0).bp->contract_with(it2, it1, v);
678                         }
679                         if (contracted) {
680 contraction_done:
681                                 if (first_noncommutative || second_noncommutative
682                                  || is_ex_exactly_of_type(*it1, add) || is_ex_exactly_of_type(*it2, add)
683                                  || is_ex_exactly_of_type(*it1, mul) || is_ex_exactly_of_type(*it2, mul)
684                                  || is_ex_exactly_of_type(*it1, ncmul) || is_ex_exactly_of_type(*it2, ncmul)) {
685
686                                         // One of the factors became a sum or product:
687                                         // re-expand expression and run again
688                                         // Non-commutative products are always re-expanded to give
689                                         // simplify_ncmul() the chance to re-order and canonicalize
690                                         // the product
691                                         ex r = (non_commutative ? ex(ncmul(v, true)) : ex(mul(v)));
692                                         return simplify_indexed(r, free_indices, dummy_indices, sp);
693                                 }
694
695                                 // Both objects may have new indices now or they might
696                                 // even not be indexed objects any more, so we have to
697                                 // start over
698                                 something_changed = true;
699                                 goto try_again;
700                         }
701                 }
702         }
703
704         // Find free indices (concatenate them all and call find_free_and_dummy())
705         // and all dummy indices that appear
706         exvector un, individual_dummy_indices;
707         it1 = v.begin(); itend = v.end();
708         while (it1 != itend) {
709                 exvector free_indices_of_factor;
710                 if (is_ex_of_type(*it1, indexed)) {
711                         exvector dummy_indices_of_factor;
712                         find_free_and_dummy(ex_to<indexed>(*it1).seq.begin() + 1, ex_to<indexed>(*it1).seq.end(), free_indices_of_factor, dummy_indices_of_factor);
713                         individual_dummy_indices.insert(individual_dummy_indices.end(), dummy_indices_of_factor.begin(), dummy_indices_of_factor.end());
714                 } else
715                         free_indices_of_factor = it1->get_free_indices();
716                 un.insert(un.end(), free_indices_of_factor.begin(), free_indices_of_factor.end());
717                 it1++;
718         }
719         exvector local_dummy_indices;
720         find_free_and_dummy(un, free_indices, local_dummy_indices);
721         local_dummy_indices.insert(local_dummy_indices.end(), individual_dummy_indices.begin(), individual_dummy_indices.end());
722
723         ex r;
724         if (something_changed)
725                 r = non_commutative ? ex(ncmul(v, true)) : ex(mul(v));
726         else
727                 r = e;
728
729         // The result should be symmetric with respect to exchange of dummy
730         // indices, so if the symmetrization vanishes, the whole expression is
731         // zero. This detects things like eps.i.j.k * p.j * p.k = 0.
732         if (local_dummy_indices.size() >= 2) {
733                 lst dummy_syms;
734                 for (int i=0; i<local_dummy_indices.size(); i++)
735                         dummy_syms.append(local_dummy_indices[i].op(0));
736                 if (r.symmetrize(dummy_syms).is_zero()) {
737                         free_indices.clear();
738                         return _ex0();
739                 }
740         }
741
742         // Dummy index renaming
743         r = rename_dummy_indices(r, dummy_indices, local_dummy_indices);
744
745         // Product of indexed object with a scalar?
746         if (is_ex_exactly_of_type(r, mul) && r.nops() == 2
747          && is_ex_exactly_of_type(r.op(1), numeric) && is_ex_of_type(r.op(0), indexed))
748                 return r.op(0).op(0).bp->scalar_mul_indexed(r.op(0), ex_to<numeric>(r.op(1)));
749         else
750                 return r;
751 }
752
753 /** Simplify indexed expression, return list of free indices. */
754 ex simplify_indexed(const ex & e, exvector & free_indices, exvector & dummy_indices, const scalar_products & sp)
755 {
756         // Expand the expression
757         ex e_expanded = e.expand();
758
759         // Simplification of single indexed object: just find the free indices
760         // and perform dummy index renaming
761         if (is_ex_of_type(e_expanded, indexed)) {
762                 const indexed &i = ex_to<indexed>(e_expanded);
763                 exvector local_dummy_indices;
764                 find_free_and_dummy(i.seq.begin() + 1, i.seq.end(), free_indices, local_dummy_indices);
765                 return rename_dummy_indices(e_expanded, dummy_indices, local_dummy_indices);
766         }
767
768         // Simplification of sum = sum of simplifications, check consistency of
769         // free indices in each term
770         if (is_ex_exactly_of_type(e_expanded, add)) {
771                 bool first = true;
772                 ex sum = _ex0();
773                 free_indices.clear();
774
775                 for (unsigned i=0; i<e_expanded.nops(); i++) {
776                         exvector free_indices_of_term;
777                         ex term = simplify_indexed(e_expanded.op(i), free_indices_of_term, dummy_indices, sp);
778                         if (!term.is_zero()) {
779                                 if (first) {
780                                         free_indices = free_indices_of_term;
781                                         sum = term;
782                                         first = false;
783                                 } else {
784                                         if (!indices_consistent(free_indices, free_indices_of_term))
785                                                 throw (std::runtime_error("simplify_indexed: inconsistent indices in sum"));
786                                         if (is_ex_of_type(sum, indexed) && is_ex_of_type(term, indexed))
787                                                 sum = sum.op(0).bp->add_indexed(sum, term);
788                                         else
789                                                 sum += term;
790                                 }
791                         }
792                 }
793
794                 return sum;
795         }
796
797         // Simplification of products
798         if (is_ex_exactly_of_type(e_expanded, mul)
799          || is_ex_exactly_of_type(e_expanded, ncmul)
800          || (is_ex_exactly_of_type(e_expanded, power) && is_ex_of_type(e_expanded.op(0), indexed) && e_expanded.op(1).is_equal(_ex2())))
801                 return simplify_indexed_product(e_expanded, free_indices, dummy_indices, sp);
802
803         // Cannot do anything
804         free_indices.clear();
805         return e_expanded;
806 }
807
808 /** Simplify/canonicalize expression containing indexed objects. This
809  *  performs contraction of dummy indices where possible and checks whether
810  *  the free indices in sums are consistent.
811  *
812  *  @return simplified expression */
813 ex ex::simplify_indexed(void) const
814 {
815         exvector free_indices, dummy_indices;
816         scalar_products sp;
817         return GiNaC::simplify_indexed(*this, free_indices, dummy_indices, sp);
818 }
819
820 /** Simplify/canonicalize expression containing indexed objects. This
821  *  performs contraction of dummy indices where possible, checks whether
822  *  the free indices in sums are consistent, and automatically replaces
823  *  scalar products by known values if desired.
824  *
825  *  @param sp Scalar products to be replaced automatically
826  *  @return simplified expression */
827 ex ex::simplify_indexed(const scalar_products & sp) const
828 {
829         exvector free_indices, dummy_indices;
830         return GiNaC::simplify_indexed(*this, free_indices, dummy_indices, sp);
831 }
832
833 /** Symmetrize expression over its free indices. */
834 ex ex::symmetrize(void) const
835 {
836         return GiNaC::symmetrize(*this, get_free_indices());
837 }
838
839 /** Antisymmetrize expression over its free indices. */
840 ex ex::antisymmetrize(void) const
841 {
842         return GiNaC::antisymmetrize(*this, get_free_indices());
843 }
844
845 /** Symmetrize expression by cyclic permutation over its free indices. */
846 ex ex::symmetrize_cyclic(void) const
847 {
848         return GiNaC::symmetrize_cyclic(*this, get_free_indices());
849 }
850
851 //////////
852 // helper classes
853 //////////
854
855 void scalar_products::add(const ex & v1, const ex & v2, const ex & sp)
856 {
857         spm[make_key(v1, v2)] = sp;
858 }
859
860 void scalar_products::add_vectors(const lst & l)
861 {
862         // Add all possible pairs of products
863         unsigned num = l.nops();
864         for (unsigned i=0; i<num; i++) {
865                 ex a = l.op(i);
866                 for (unsigned j=0; j<num; j++) {
867                         ex b = l.op(j);
868                         add(a, b, a*b);
869                 }
870         }
871 }
872
873 void scalar_products::clear(void)
874 {
875         spm.clear();
876 }
877
878 /** Check whether scalar product pair is defined. */
879 bool scalar_products::is_defined(const ex & v1, const ex & v2) const
880 {
881         return spm.find(make_key(v1, v2)) != spm.end();
882 }
883
884 /** Return value of defined scalar product pair. */
885 ex scalar_products::evaluate(const ex & v1, const ex & v2) const
886 {
887         return spm.find(make_key(v1, v2))->second;
888 }
889
890 void scalar_products::debugprint(void) const
891 {
892         std::cerr << "map size=" << spm.size() << std::endl;
893         spmap::const_iterator i = spm.begin(), end = spm.end();
894         while (i != end) {
895                 const spmapkey & k = i->first;
896                 std::cerr << "item key=(" << k.first << "," << k.second;
897                 std::cerr << "), value=" << i->second << std::endl;
898                 ++i;
899         }
900 }
901
902 /** Make key from object pair. */
903 spmapkey scalar_products::make_key(const ex & v1, const ex & v2)
904 {
905         // If indexed, extract base objects
906         ex s1 = is_ex_of_type(v1, indexed) ? v1.op(0) : v1;
907         ex s2 = is_ex_of_type(v2, indexed) ? v2.op(0) : v2;
908
909         // Enforce canonical order in pair
910         if (s1.compare(s2) > 0)
911                 return spmapkey(s2, s1);
912         else
913                 return spmapkey(s1, s2);
914 }
915
916 } // namespace GiNaC