the destructor, copy constructor, and assignment operator (which were the
[ginac.git] / ginac / idx.cpp
1 /** @file idx.cpp
2  *
3  *  Implementation of GiNaC's indices. */
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
25 #include "idx.h"
26 #include "ex.h"
27 #include "lst.h"
28 #include "relational.h"
29 #include "archive.h"
30 #include "utils.h"
31 #include "debugmsg.h"
32
33 #ifndef NO_NAMESPACE_GINAC
34 namespace GiNaC {
35 #endif // ndef NO_NAMESPACE_GINAC
36
37 GINAC_IMPLEMENT_REGISTERED_CLASS(idx, basic)
38
39 //////////
40 // default constructor, destructor, copy constructor assignment operator and helpers
41 //////////
42
43 // public
44
45 idx::idx() : inherited(TINFO_idx), symbolic(true), covariant(false)
46 {
47         debugmsg("idx default constructor",LOGLEVEL_CONSTRUCT);
48         serial=next_serial++;
49         name=autoname_prefix()+ToString(serial);
50 }
51
52 // protected
53
54 void idx::copy(const idx & other)
55 {
56         inherited::copy(other);
57         serial=other.serial;
58         symbolic=other.symbolic;
59         name=other.name;
60         value=other.value;
61         covariant=other.covariant;
62 }
63
64 void idx::destroy(bool call_parent)
65 {
66         if (call_parent) inherited::destroy(call_parent);
67 }
68
69 //////////
70 // other constructors
71 //////////
72
73 // public
74
75 /** Construct symbolic index, using an automatically generated unique name.
76  *
77  *  @param cov Index is covariant (contravariant otherwise)
78  *  @return newly constructed index */
79 idx::idx(bool cov) : inherited(TINFO_idx), symbolic(true), covariant(cov)
80 {
81         debugmsg("idx constructor from bool",LOGLEVEL_CONSTRUCT);
82         serial = next_serial++;
83         name = autoname_prefix()+ToString(serial);
84 }
85
86 /** Construct symbolic index with specified name.
87  *
88  *  @param n Symbolic index name
89  *  @param cov Index is covariant (contravariant otherwise)
90  *  @return newly constructed index */
91 idx::idx(const std::string & n, bool cov) : inherited(TINFO_idx),  
92         symbolic(true), name(n), covariant(cov)
93 {
94         debugmsg("idx constructor from string,bool",LOGLEVEL_CONSTRUCT);
95         serial = next_serial++;
96 }
97
98 /** Construct symbolic index with specified name.
99  *
100  *  @param n Symbolic index name
101  *  @param cov Index is covariant (contravariant otherwise)
102  *  @return newly constructed index */
103 idx::idx(const char * n, bool cov) : inherited(TINFO_idx), symbolic(true), name(n), covariant(cov)
104 {
105         debugmsg("idx constructor from char*,bool",LOGLEVEL_CONSTRUCT);
106         serial = next_serial++;
107 }
108
109 /** Construct numeric index with specified value.
110  *
111  *  @param v Numeric index value
112  *  @param cov Index is covariant (contravariant otherwise)
113  *  @return newly constructed index */
114 idx::idx(unsigned v, bool cov) : inherited(TINFO_idx), symbolic(false), value(v), covariant(cov)
115 {
116         debugmsg("idx constructor from unsigned,bool",LOGLEVEL_CONSTRUCT);
117         serial = 0;
118 }
119
120 //////////
121 // archiving
122 //////////
123
124 /** Construct object from archive_node. */
125 idx::idx(const archive_node &n, const lst &sym_lst) : inherited(n, sym_lst)
126 {
127         debugmsg("idx constructor from archive_node", LOGLEVEL_CONSTRUCT);
128         n.find_bool("symbolic", symbolic);
129         n.find_bool("covariant", covariant);
130         if (symbolic) {
131                 serial = next_serial++;
132                 if (!(n.find_string("name", name)))
133                         name = autoname_prefix() + ToString(serial);
134         } else {
135                 serial = 0;
136                 n.find_unsigned("value", value);
137         }
138 }
139
140 /** Unarchive the object. */
141 ex idx::unarchive(const archive_node &n, const lst &sym_lst)
142 {
143         ex s = (new idx(n, sym_lst))->setflag(status_flags::dynallocated);
144
145         if (ex_to_idx(s).symbolic) {
146                 // If idx is in sym_lst, return the existing idx
147                 for (unsigned i=0; i<sym_lst.nops(); i++) {
148                         if (is_ex_of_type(sym_lst.op(i), idx) && (ex_to_idx(sym_lst.op(i)).name == ex_to_idx(s).name))
149                                 return sym_lst.op(i);
150                 }
151         }
152         return s;
153 }
154
155 /** Archive the object. */
156 void idx::archive(archive_node &n) const
157 {
158         inherited::archive(n);
159         n.add_bool("symbolic", symbolic);
160         n.add_bool("covariant", covariant);
161         if (symbolic)
162                 n.add_string("name", name);
163         else
164                 n.add_unsigned("value", value);
165 }
166
167 //////////
168 // functions overriding virtual functions from bases classes
169 //////////
170
171 // public
172
173 basic * idx::duplicate() const
174 {
175         debugmsg("idx duplicate",LOGLEVEL_DUPLICATE);
176         return new idx(*this);
177 }
178
179 void idx::printraw(std::ostream & os) const
180 {
181         debugmsg("idx printraw",LOGLEVEL_PRINT);
182
183         os << "idx(";
184
185         if (symbolic) {
186                 os << "symbolic,name=" << name;
187         } else {
188                 os << "non symbolic,value=" << value;
189         }
190
191         if (covariant) {
192                 os << ",covariant";
193         } else {
194                 os << ",contravariant";
195         }
196
197         os << ",serial=" << serial;
198         os << ",hash=" << hashvalue << ",flags=" << flags;
199         os << ")";
200 }
201
202 void idx::printtree(std::ostream & os, unsigned indent) const
203 {
204         debugmsg("idx printtree",LOGLEVEL_PRINT);
205
206         os << std::string(indent,' ') << "idx: ";
207
208         if (symbolic) {
209                 os << "symbolic,name=" << name;
210         } else {
211                 os << "non symbolic,value=" << value;
212         }
213
214         if (covariant) {
215                 os << ",covariant";
216         } else {
217                 os << ",contravariant";
218         }
219
220         os << ", serial=" << serial
221            << ", hash=" << hashvalue
222            << " (0x" << std::hex << hashvalue << std::dec << ")"
223            << ", flags=" << flags << std::endl;
224 }
225
226 void idx::print(std::ostream & os, unsigned upper_precedence) const
227 {
228         debugmsg("idx print",LOGLEVEL_PRINT);
229
230         if (covariant) {
231                 os << "_";
232         } else {
233                 os << "~";
234         }
235         if (symbolic) {
236                 os << name;
237         } else {
238                 os << value;
239         }
240 }
241
242 bool idx::info(unsigned inf) const
243 {
244         if (inf==info_flags::idx) return true;
245         return inherited::info(inf);
246 }
247
248 ex idx::subs(const lst & ls, const lst & lr) const
249 {
250         GINAC_ASSERT(ls.nops()==lr.nops());
251 #ifdef DO_GINAC_ASSERT
252         for (unsigned i=0; i<ls.nops(); i++) {
253                 GINAC_ASSERT(is_ex_exactly_of_type(ls.op(i),symbol)||
254                            is_ex_of_type(ls.op(i),idx));
255         }
256 #endif // def DO_GINAC_ASSERT
257
258         for (unsigned i=0; i<ls.nops(); i++) {
259                 if (is_equal(*(ls.op(i)).bp)) {
260                         return lr.op(i);
261                 }
262         }
263         return *this;
264 }
265
266 // protected
267
268 int idx::compare_same_type(const basic & other) const
269 {
270         GINAC_ASSERT(is_of_type(other,idx));
271         const idx &o = static_cast<const idx &>(&other);
272
273         if (covariant!=o.covariant) {
274                 // different co/contravariant
275                 return covariant ? -1 : 1;
276         }
277
278         if ((!symbolic) && (!o.symbolic)) {
279                 // non-symbolic, of equal type: compare values
280                 if (value==o.value) {
281                         return 0;
282                 }
283                 return value<o.value ? -1 : 1;
284         }
285
286         if (symbolic && o.symbolic) {
287                 // both symbolic: compare serials
288                 if (serial==o.serial) {
289                         return 0;
290                 }
291                 return serial<o.serial ? -1 : 1;
292         }
293
294         // one symbolic, one value: value is sorted first
295         return o.symbolic ? -1 : 1;
296 }
297
298 bool idx::is_equal_same_type(const basic & other) const
299 {
300         GINAC_ASSERT(is_of_type(other,idx));
301         const idx &o = static_cast<const idx &>(other);
302
303         if (covariant != o.covariant) return false;
304         if (symbolic != o.symbolic) return false;
305         if (symbolic && o.symbolic) return serial==o.serial;
306         return value==o.value;
307 }    
308
309 unsigned idx::calchash(void) const
310 {
311         hashvalue=golden_ratio_hash(golden_ratio_hash(tinfo_key ^ serial));
312         setflag(status_flags::hash_calculated);
313         return hashvalue;
314 }
315
316 //////////
317 // new virtual functions which can be overridden by derived classes
318 //////////
319
320 // public
321
322 /** Check whether the index forms a co-/contravariant pair with another
323  *  index (i.e. same name/value but opposite co-/contravariance). */
324 bool idx::is_co_contra_pair(const basic & other) const
325 {
326         // like is_equal_same_type(), but tests for different covariant status
327         GINAC_ASSERT(is_of_type(other,idx));
328         const idx & o=static_cast<const idx &>(const_cast<basic &>(other));
329
330         if (covariant==o.covariant) return false;
331         if (symbolic!=o.symbolic) return false;
332         if (symbolic && o.symbolic) return serial==o.serial;
333         return value==o.value;
334 }    
335
336 /** Toggle co-/contravariance of index. */
337 ex idx::toggle_covariant(void) const
338 {
339         idx * i_copy=static_cast<idx *>(duplicate());
340         i_copy->covariant = !i_copy->covariant;
341         i_copy->clearflag(status_flags::hash_calculated);
342         return i_copy->setflag(status_flags::dynallocated);
343 }
344
345 //////////
346 // non-virtual functions in this class
347 //////////
348
349 // private
350
351 std::string & idx::autoname_prefix(void)
352 {
353         static std::string * s = new std::string("index");
354         return *s;
355 }
356
357 //////////
358 // static member variables
359 //////////
360
361 // protected
362
363 unsigned idx::next_serial=0;
364
365 //////////
366 // other functions
367 //////////
368
369 /** Bring a vector of indices into a canonic order. This operation only makes
370  *  sense if the object carrying these indices is either symmetric or totally
371  *  antisymmetric with respect to the indices.
372  *
373  *  @param iv Index vector
374  *  @param antisymmetric Whether the object carrying the indices is antisymmetric (symmetric otherwise)
375  *  @return the sign introduced by the reordering of the indices. For symmetric
376  *          objects this is always +1. For antisymmetric objects this is either
377  *          +1 or -1 or 0 (if two equal indices were encountered). If the index
378  *          vector was unchanged this function returns INT_MAX. */
379 int canonicalize_indices(exvector & iv, bool antisymmetric)
380 {
381         if (iv.size()<2) {
382                 // nothing do to for 0 or 1 indices
383                 return INT_MAX;
384         }
385
386         bool something_changed=false;
387         int sig=1;
388
389         // simple bubble sort algorithm should be sufficient for the small number of indices needed
390         exvector::const_iterator last_idx=iv.end();
391         exvector::const_iterator next_to_last_idx=iv.end()-1;
392         for (exvector::iterator it1=iv.begin(); it1!=next_to_last_idx; ++it1) {
393                 for (exvector::iterator it2=it1+1; it2!=last_idx; ++it2) {
394                         int cmpval=(*it1).compare(*it2);
395                         if (cmpval==1) {
396                                 iter_swap(it1,it2);
397                                 something_changed=true;
398                                 if (antisymmetric) sig=-sig;
399                         } else if ((cmpval==0) && antisymmetric) {
400                                 something_changed=true;
401                                 sig=0;
402                         }
403                 }
404         }
405
406         return something_changed ? sig : INT_MAX;
407 }
408
409 /** Build a vector of indices as the set intersection of two other index
410  *  vectors (i.e. the returned vector contains the indices which appear in
411  *  both source vectors). */
412 exvector idx_intersect(const exvector & iv1, const exvector & iv2)
413 {
414         // Create union vector
415         exvector iv_union;
416         iv_union.reserve(iv1.size() + iv2.size());
417         iv_union.insert(iv_union.end(), iv1.begin(), iv1.end());
418         iv_union.insert(iv_union.end(), iv2.begin(), iv2.end());
419
420         // Sort it
421         canonicalize_indices(iv_union);
422
423         // Look for duplicates
424         exvector iv_intersect;
425         exvector::const_iterator cit = iv_union.begin(), citend = iv_union.end();
426         ex e;
427         if (cit != citend)
428                 e = *cit++;
429         while (cit != citend) {
430                 if (e.is_equal(*cit)) {
431                         iv_intersect.push_back(e);
432                         do {
433                                 cit++;
434                         } while (cit != citend && e.is_equal(*cit));
435                         if (cit == citend)
436                                 break;
437                 }
438                 e = *cit++;
439         }
440         return iv_intersect;
441 }
442
443 /** Given a vector iv3 of three indices and a vector iv2 of two indices
444  *  where iv2 is a subset of iv3, return the (free) index that is in iv3
445  *  but not in iv2 and the sign introduced by permuting that index to the
446  *  front.
447  *
448  *  @param iv3 Vector of 3 indices
449  *  @param iv2 Vector of 2 indices, must be a subset of iv3
450  *  @param sig Returns the sign introduced by permuting the free index to the
451  *             front if the object carrying the indices was antisymmetric (if
452  *             it's symmetric, you can just ignore the returned value).
453  *  @return the free index (the one that is in iv3 but not in iv2) */
454 ex permute_free_index_to_front(const exvector & iv3, const exvector & iv2, int * sig)
455 {
456         // match (return value,iv2) to iv3 by permuting indices
457         // iv3 is always cyclic
458
459         GINAC_ASSERT(iv3.size()==3);
460         GINAC_ASSERT(iv2.size()==2);
461
462         *sig=1;
463
464 #define TEST_PERMUTATION(A,B,C,P) \
465         if ((iv3[B].is_equal(iv2[0]))&&(iv3[C].is_equal(iv2[1]))) { \
466                 *sig=P; \
467                 return iv3[A]; \
468         }
469         
470         TEST_PERMUTATION(0,1,2,  1);
471         TEST_PERMUTATION(0,2,1, -1);
472         TEST_PERMUTATION(1,0,2, -1);
473         TEST_PERMUTATION(1,2,0,  1);
474         TEST_PERMUTATION(2,0,1,  1);
475         TEST_PERMUTATION(2,1,0, -1);
476         throw(std::logic_error("permute_free_index_to_front(): no valid permutation found"));
477 }
478         
479 /** Substitute one index in a vector of expressions.
480  *
481  *  @param v Vector to substitute in (will be modified)
482  *  @param is Index being substituted
483  *  @param ir Index to replace by
484  *  @return number of performed substitutions */
485 unsigned subs_index_in_exvector(exvector & v, const ex & is, const ex & ir)
486 {
487         exvector::iterator it;
488         unsigned replacements=0;
489         unsigned current_replacements;
490
491         GINAC_ASSERT(is_ex_of_type(is,idx));
492         GINAC_ASSERT(is_ex_of_type(ir,idx));
493    
494         for (it=v.begin(); it!=v.end(); ++it) {
495                 current_replacements=count_index(*it,is);
496                 if (current_replacements>0) {
497                         (*it)=(*it).subs(is==ir);
498                 }
499                 replacements += current_replacements;
500         }
501         return replacements;
502 }
503
504 /** Count number of times a given index appears in the index vector of an
505  *  indexed object.
506  *
507  *  @param e Indexed object
508  *  @param i Index to look for
509  *  @return number of times the index was found */
510 unsigned count_index(const ex & e, const ex & i)
511 {
512         exvector idxv=e.get_indices();
513         unsigned count=0;
514         for (exvector::const_iterator cit=idxv.begin(); cit!=idxv.end(); ++cit) {
515                 if ((*cit).is_equal(i)) count++;
516         }
517         return count;
518 }
519
520 /** Substitute multiple indices in an expression.
521  *
522  *  @param e Expression to substitute in
523  *  @param idxv_subs Vector of indices being substituted
524  *  @param idxv_repl Vector of indices to replace by (1:1 correspondence to idxv_subs)
525  *  @return expression with substituted indices */
526 ex subs_indices(const ex & e, const exvector & idxv_subs, const exvector & idxv_repl)
527 {
528         GINAC_ASSERT(idxv_subs.size()==idxv_repl.size());
529         ex res=e;
530         for (unsigned i=0; i<idxv_subs.size(); ++i) {
531                 res=res.subs(idxv_subs[i]==idxv_repl[i]);
532         }
533         return res;
534 }
535
536 #ifndef NO_NAMESPACE_GINAC
537 } // namespace GiNaC
538 #endif // ndef NO_NAMESPACE_GINAC