- enforced GiNaC coding standards :-)
[ginac.git] / ginac / idx.cpp
1 /** @file idx.cpp
2  *
3  *  Implementation of GiNaC's indices.
4  *
5  *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
6  *
7  *  This program is free software; you can redistribute it and/or modify
8  *  it under the terms of the GNU General Public License as published by
9  *  the Free Software Foundation; either version 2 of the License, or
10  *  (at your option) any later version.
11  *
12  *  This program is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  *  GNU General Public License for more details.
16  *
17  *  You should have received a copy of the GNU General Public License
18  *  along with this program; if not, write to the Free Software
19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  */
21
22 #include <stdexcept>
23
24 #include "ginac.h"
25 #include "utils.h"
26
27 //////////
28 // default constructor, destructor, copy constructor assignment operator and helpers
29 //////////
30
31 // public
32
33 idx::idx() : basic(TINFO_IDX), symbolic(true), covariant(false)
34 {
35     debugmsg("idx default constructor",LOGLEVEL_CONSTRUCT);
36     serial=next_serial++;
37     name="index"+ToString(serial);
38 }
39
40 idx::~idx() 
41 {
42     debugmsg("idx destructor",LOGLEVEL_DESTRUCT);
43     destroy(0);
44 }
45
46 idx::idx(idx const & other)
47 {
48     debugmsg("idx copy constructor",LOGLEVEL_CONSTRUCT);
49     copy(other);
50 }
51
52 idx const & idx::operator=(idx const & other)
53 {
54     debugmsg("idx operator=",LOGLEVEL_ASSIGNMENT);
55     if (this != &other) {
56         destroy(1);
57         copy(other);
58     }
59     return *this;
60 }
61
62 // protected
63
64 void idx::copy(idx const & other)
65 {
66     basic::copy(other);
67     serial=other.serial;
68     symbolic=other.symbolic;
69     name=other.name;
70     value=other.value;
71     covariant=other.covariant;
72 }
73
74 void idx::destroy(bool call_parent)
75 {
76     if (call_parent) basic::destroy(call_parent);
77 }
78
79 //////////
80 // other constructors
81 //////////
82
83 // public
84
85 idx::idx(bool cov) : basic(TINFO_IDX), symbolic(true), covariant(cov)
86 {
87     debugmsg("idx constructor from bool",LOGLEVEL_CONSTRUCT);
88     serial=next_serial++;
89     name="index"+ToString(serial);
90 }
91
92 idx::idx(string const & n, bool cov) : basic(TINFO_IDX),  
93     symbolic(true), name(n), covariant(cov)
94 {
95     debugmsg("idx constructor from string,bool",LOGLEVEL_CONSTRUCT);
96     serial=next_serial++;
97 }
98
99 idx::idx(char const * n, bool cov) : basic(TINFO_IDX),  
100     symbolic(true), name(n), covariant(cov)
101 {
102     debugmsg("idx constructor from char*,bool",LOGLEVEL_CONSTRUCT);
103     serial=next_serial++;
104 }
105
106 idx::idx(unsigned const v, bool cov) : basic(TINFO_IDX),
107     symbolic(false), value(v), covariant(cov)
108 {
109     debugmsg("idx constructor from unsigned,bool",LOGLEVEL_CONSTRUCT);
110     serial=0;
111 }
112
113
114 //////////
115 // functions overriding virtual functions from bases classes
116 //////////
117
118 // public
119
120 basic * idx::duplicate() const
121 {
122     debugmsg("idx duplicate",LOGLEVEL_DUPLICATE);
123     return new idx(*this);
124 }
125
126 void idx::printraw(ostream & os) const
127 {
128     debugmsg("idx printraw",LOGLEVEL_PRINT);
129
130     os << "idx(";
131
132     if (symbolic) {
133         os << "symbolic,name=" << name;
134     } else {
135         os << "non symbolic,value=" << value;
136     }
137
138     if (covariant) {
139         os << ",covariant";
140     } else {
141         os << ",contravariant";
142     }
143
144     os << ",serial=" << serial;
145     os << ",hash=" << hashvalue << ",flags=" << flags;
146     os << ")";
147 }
148
149 void idx::printtree(ostream & os, unsigned indent) const
150 {
151     debugmsg("idx printtree",LOGLEVEL_PRINT);
152
153     os << string(indent,' ') << "idx: ";
154
155     if (symbolic) {
156         os << "symbolic,name=" << name;
157     } else {
158         os << "non symbolic,value=" << value;
159     }
160
161     if (covariant) {
162         os << ",covariant";
163     } else {
164         os << ",contravariant";
165     }
166
167     os << ", serial=" << serial
168        << ", hash=" << hashvalue << " (0x" << hex << hashvalue << dec << ")"
169        << ", flags=" << flags << endl;
170 }
171
172 void idx::print(ostream & os, unsigned upper_precedence) const
173 {
174     debugmsg("idx print",LOGLEVEL_PRINT);
175
176     if (covariant) {
177         os << "_";
178     } else {
179         os << "~";
180     }
181     if (symbolic) {
182         os << name;
183     } else {
184         os << value;
185     }
186 }
187
188 bool idx::info(unsigned inf) const
189 {
190     if (inf==info_flags::idx) return true;
191     return basic::info(inf);
192 }
193
194 ex idx::subs(lst const & ls, lst const & lr) const
195 {
196     ASSERT(ls.nops()==lr.nops());
197 #ifdef DOASSERT
198     for (int i=0; i<ls.nops(); i++) {
199         ASSERT(is_ex_exactly_of_type(ls.op(i),symbol)||
200                is_ex_of_type(ls.op(i),idx));
201     }
202 #endif // def DOASSERT
203
204     for (int i=0; i<ls.nops(); i++) {
205         if (is_equal(*(ls.op(i)).bp)) {
206             return lr.op(i);
207         }
208     }
209     return *this;
210 }
211
212 // protected
213
214 int idx::compare_same_type(basic const & other) const
215 {
216     ASSERT(is_of_type(other,idx));
217     idx const & o=static_cast<idx const &>
218                              (const_cast<basic &>(other));
219
220     if (covariant!=o.covariant) {
221         // different co/contravariant
222         return covariant ? -1 : 1;
223     }
224     if ((!symbolic) && (!o.symbolic)) {
225         // non-symbolic, of equal type: compare values
226         if (value==o.value) {
227             return 0;
228         }
229         return value<o.value ? -1 : 1;
230     }
231     if (symbolic && o.symbolic) {
232         // both symbolic: compare serials
233         if (serial==o.serial) {
234             return 0;
235         }
236         return serial<o.serial ? -1 : 1;
237     }
238     // one symbolic, one value: value is sorted first
239     return o.symbolic ? -1 : 1;
240 }
241
242 bool idx::is_equal_same_type(basic const & other) const
243 {
244     ASSERT(is_of_type(other,idx));
245     idx const & o=static_cast<idx const &>
246                              (const_cast<basic &>(other));
247
248     if (covariant!=o.covariant) return false;
249     if (symbolic!=o.symbolic) return false;
250     if (symbolic && o.symbolic) return serial==o.serial;
251     return value==o.value;
252 }    
253
254 unsigned idx::calchash(void) const
255 {
256     hashvalue=golden_ratio_hash(golden_ratio_hash(tinfo_key ^ serial));
257     setflag(status_flags::hash_calculated);
258     return hashvalue;
259 }
260
261 //////////
262 // new virtual functions which can be overridden by derived classes
263 //////////
264
265 // public
266
267 bool idx::is_co_contra_pair(basic const & other) const
268 {
269     // like is_equal_same_type(), but tests for different covariant status
270     ASSERT(is_of_type(other,idx));
271     idx const & o=static_cast<idx const &>
272                              (const_cast<basic &>(other));
273
274     if (covariant==o.covariant) return false;
275     if (symbolic!=o.symbolic) return false;
276     if (symbolic && o.symbolic) return serial==o.serial;
277     return value==o.value;
278 }    
279
280 bool idx::is_symbolic(void) const
281 {
282     return symbolic;
283 }
284
285 unsigned idx::get_value(void) const
286 {
287     return value;
288 }
289
290 bool idx::is_covariant(void) const
291 {
292     return covariant;
293 }
294
295 ex idx::toggle_covariant(void) const
296 {
297     idx * i_copy=static_cast<idx *>(duplicate());
298     i_copy->covariant = !i_copy->covariant;
299     i_copy->clearflag(status_flags::hash_calculated);
300     return i_copy->setflag(status_flags::dynallocated);
301 }
302
303 //////////
304 // non-virtual functions in this class
305 //////////
306
307 // none
308
309 //////////
310 // static member variables
311 //////////
312
313 // protected
314
315 unsigned idx::next_serial=0;
316
317 //////////
318 // global constants
319 //////////
320
321 const idx some_idx;
322 type_info const & typeid_idx=typeid(some_idx);
323
324 //////////
325 // other functions
326 //////////
327
328 int canonicalize_indices(exvector & iv, bool antisymmetric)
329 {
330     if (iv.size()<2) {
331         // nothing do to for 0 or 1 indices
332         return INT_MAX;
333     }
334
335     bool something_changed=false;
336     int sig=1;
337     // simple bubble sort algorithm should be sufficient for the small number of indices needed
338     exvector::const_iterator last_idx=iv.end();
339     exvector::const_iterator next_to_last_idx=iv.end()-1;
340     for (exvector::iterator it1=iv.begin(); it1!=next_to_last_idx; ++it1) {
341         for (exvector::iterator it2=it1+1; it2!=last_idx; ++it2) {
342             int cmpval=(*it1).compare(*it2);
343             if (cmpval==1) {
344                 iter_swap(it1,it2);
345                 something_changed=true;
346                 if (antisymmetric) sig=-sig;
347             } else if ((cmpval==0) && antisymmetric) {
348                 something_changed=true;
349                 sig=0;
350             }
351         }
352     }
353     return something_changed ? sig : INT_MAX;
354 }
355
356 exvector idx_intersect(exvector const & iv1, exvector const & iv2)
357 {
358     // build a vector of symbolic indices contained in iv1 and iv2 simultaneously
359     // assumes (but does not test) that each index occurs at most twice
360     exvector iv_intersect;
361     for (exvector::const_iterator cit1=iv1.begin(); cit1!=iv1.end(); ++cit1) {
362         ASSERT(is_ex_of_type(*cit1,idx));
363         if (ex_to_idx(*cit1).is_symbolic()) {
364             for (exvector::const_iterator cit2=iv2.begin(); cit2!=iv2.end(); ++cit2) {
365                 ASSERT(is_ex_of_type(*cit2,idx));
366                 if ((*cit1).is_equal(*cit2)) {
367                     iv_intersect.push_back(*cit1);
368                     break;
369                 }
370             }
371         }
372     }
373     return iv_intersect;
374 }
375
376 #define TEST_PERMUTATION(A,B,C,P) \
377     if ((iv3[B].is_equal(iv2[0]))&&(iv3[C].is_equal(iv2[1]))) { \
378         if (antisymmetric) *sig=P; \
379         return iv3[A]; \
380     }
381
382 ex permute_free_index_to_front(exvector const & iv3, exvector const & iv2,
383                                bool antisymmetric, int * sig)
384 {
385     // match (return value,iv2) to iv3 by permuting indices
386     // iv3 is always cyclic
387
388     ASSERT(iv3.size()==3);
389     ASSERT(iv2.size()==2);
390
391     *sig=1;
392     
393     TEST_PERMUTATION(0,1,2,  1);
394     TEST_PERMUTATION(0,2,1, -1);
395     TEST_PERMUTATION(1,0,2, -1);
396     TEST_PERMUTATION(1,2,0,  1);
397     TEST_PERMUTATION(2,0,1,  1);
398     TEST_PERMUTATION(2,1,0, -1);
399     throw(std::logic_error("permute_free_index_to_front(): no valid permutation found"));
400 }
401     
402 unsigned subs_index_in_exvector(exvector & v, ex const & is, ex const & ir)
403 {
404     exvector::iterator it;
405     unsigned replacements=0;
406     unsigned current_replacements;
407
408     ASSERT(is_ex_of_type(is,idx));
409     ASSERT(is_ex_of_type(ir,idx));
410    
411     for (it=v.begin(); it!=v.end(); ++it) {
412         current_replacements=count_index(*it,is);
413         if (current_replacements>0) {
414             (*it)=(*it).subs(is==ir);
415         }
416         replacements += current_replacements;
417     }
418     return replacements;
419 }
420
421 unsigned count_index(ex const & e, ex const & i)
422 {
423     exvector idxv=e.get_indices();
424     unsigned count=0;
425     for (exvector::const_iterator cit=idxv.begin(); cit!=idxv.end(); ++cit) {
426         if ((*cit).is_equal(i)) count++;
427     }
428     return count;
429 }
430
431 ex subs_indices(ex const & e, exvector const & idxv_subs,
432                 exvector const & idxv_repl)
433 {
434     ASSERT(idxv_subs.size()==idxv_repl.size());
435     ex res=e;
436     for (unsigned i=0; i<idxv_subs.size(); ++i) {
437         res=res.subs(idxv_subs[i]==idxv_repl[i]);
438     }
439     return res;
440 }
441
442
443
444