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