ginac/basic.cpp

   1 /** @file basic.cpp
   2  *
   3  *  Implementation of GiNaC's ABC. */
   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 <iostream>
  24 #include <stdexcept>
  25 #ifdef DO_GINAC_ASSERT
  26 #  include <typeinfo>
  27 #endif
  28
  29 #include "basic.h"
  30 #include "ex.h"
  31 #include "numeric.h"
  32 #include "power.h"
  33 #include "symbol.h"
  34 #include "lst.h"
  35 #include "ncmul.h"
  36 #include "relational.h"
  37 #include "wildcard.h"
  38 #include "print.h"
  39 #include "archive.h"
  40 #include "utils.h"
  41
  42 namespace GiNaC {
  43
  44 GINAC_IMPLEMENT_REGISTERED_CLASS_NO_CTORS(basic, void)
  45
  46 //////////
  47 // default ctor, dtor, copy ctor, assignment operator and helpers
  48 //////////
  49
  50 // public
  51
  52 basic::basic(const basic & other) : tinfo_key(TINFO_basic), flags(0), refcount(0)
  53 {
  54         copy(other);
  55 }
  56
  57 const basic & basic::operator=(const basic & other)
  58 {
  59         if (this != &other) {
  60                 destroy(true);
  61                 copy(other);
  62         }
  63         return *this;
  64 }
  65
  66 // protected
  67
  68 // none (all conditionally inlined)
  69
  70 //////////
  71 // other ctors
  72 //////////
  73
  74 // none (all conditionally inlined)
  75
  76 //////////
  77 // archiving
  78 //////////
  79
  80 /** Construct object from archive_node. */
  81 basic::basic(const archive_node &n, const lst &sym_lst) : flags(0), refcount(0)
  82 {
  83         // Reconstruct tinfo_key from class name
  84         std::string class_name;
  85         if (n.find_string("class", class_name))
  86                 tinfo_key = find_tinfo_key(class_name);
  87         else
  88                 throw (std::runtime_error("archive node contains no class name"));
  89 }
  90
  91 /** Unarchive the object. */
  92 DEFAULT_UNARCHIVE(basic)
  93
  94 /** Archive the object. */
  95 void basic::archive(archive_node &n) const
  96 {
  97         n.add_string("class", class_name());
  98 }
  99
 100 //////////
 101 // new virtual functions which can be overridden by derived classes
 102 //////////
 103
 104 // public
 105
 106 /** Output to stream.
 107  *  @param c print context object that describes the output formatting
 108  *  @param level value that is used to identify the precedence or indentation
 109  *               level for placing parentheses and formatting */
 110 void basic::print(const print_context & c, unsigned level) const
 111 {
 112         if (is_of_type(c, print_tree)) {
 113
 114                 c.s << std::string(level, ' ') << class_name()
 115                     << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec
 116                     << ", nops=" << nops()
 117                     << std::endl;
 118                 for (unsigned i=0; i<nops(); ++i)
 119                         op(i).print(c, level + static_cast<const print_tree &>(c).delta_indent);
 120
 121         } else
 122                 c.s << "[" << class_name() << " object]";
 123 }
 124
 125 /** Little wrapper around print to be called within a debugger.
 126  *  This is needed because you cannot call foo.print(cout) from within the
 127  *  debugger because it might not know what cout is.  This method can be
 128  *  invoked with no argument and it will simply print to stdout.
 129  *
 130  *  @see basic::print */
 131 void basic::dbgprint(void) const
 132 {
 133         this->print(std::cerr);
 134         std::cerr << std::endl;
 135 }
 136
 137 /** Little wrapper around printtree to be called within a debugger.
 138  *
 139  *  @see basic::dbgprint
 140  *  @see basic::printtree */
 141 void basic::dbgprinttree(void) const
 142 {
 143         this->print(print_tree(std::cerr));
 144 }
 145
 146 /** Return relative operator precedence (for parenthizing output). */
 147 unsigned basic::precedence(void) const
 148 {
 149         return 70;
 150 }
 151
 152 /** Create a new copy of this on the heap.  One can think of this as simulating
 153  *  a virtual copy constructor which is needed for instance by the refcounted
 154  *  construction of an ex from a basic. */
 155 basic * basic::duplicate() const
 156 {
 157         return new basic(*this);
 158 }
 159
 160 /** Information about the object.
 161  *
 162  *  @see class info_flags */
 163 bool basic::info(unsigned inf) const
 164 {
 165         // all possible properties are false for basic objects
 166         return false;
 167 }
 168
 169 /** Number of operands/members. */
 170 unsigned basic::nops() const
 171 {
 172         // iterating from 0 to nops() on atomic objects should be an empty loop,
 173         // and accessing their elements is a range error.  Container objects should
 174         // override this.
 175         return 0;
 176 }
 177
 178 /** Return operand/member at position i. */
 179 ex basic::op(int i) const
 180 {
 181         return (const_cast<basic *>(this))->let_op(i);
 182 }
 183
 184 /** Return modifyable operand/member at position i. */
 185 ex & basic::let_op(int i)
 186 {
 187         throw(std::out_of_range("op() out of range"));
 188 }
 189
 190 ex basic::operator[](const ex & index) const
 191 {
 192         if (is_ex_exactly_of_type(index,numeric))
 193                 return op(ex_to<numeric>(index).to_int());
 194
 195         throw(std::invalid_argument("non-numeric indices not supported by this type"));
 196 }
 197
 198 ex basic::operator[](int i) const
 199 {
 200         return op(i);
 201 }
 202
 203 /** Test for occurrence of a pattern.  An object 'has' a pattern if it matches
 204  *  the pattern itself or one of the children 'has' it.  As a consequence
 205  *  (according to the definition of children) given e=x+y+z, e.has(x) is true
 206  *  but e.has(x+y) is false. */
 207 bool basic::has(const ex & pattern) const
 208 {
 209         lst repl_lst;
 210         if (match(pattern, repl_lst))
 211                 return true;
 212         for (unsigned i=0; i<nops(); i++)
 213                 if (op(i).has(pattern))
 214                         return true;
 215
 216         return false;
 217 }
 218
 219 /** Construct new expression by applying the specified function to all
 220  *  sub-expressions (one level only, not recursively). */
 221 ex basic::map(map_function & f) const
 222 {
 223         unsigned num = nops();
 224         if (num == 0)
 225                 return *this;
 226
 227         basic *copy = duplicate();
 228         copy->setflag(status_flags::dynallocated);
 229         copy->clearflag(status_flags::hash_calculated | status_flags::expanded);
 230         ex e(*copy);
 231         for (unsigned i=0; i<num; i++)
 232                 e.let_op(i) = f(e.op(i));
 233         return e.eval();
 234 }
 235
 236 /** Return degree of highest power in object s. */
 237 int basic::degree(const ex & s) const
 238 {
 239         return 0;
 240 }
 241
 242 /** Return degree of lowest power in object s. */
 243 int basic::ldegree(const ex & s) const
 244 {
 245         return 0;
 246 }
 247
 248 /** Return coefficient of degree n in object s. */
 249 ex basic::coeff(const ex & s, int n) const
 250 {
 251         return n==0 ? *this : _ex0;
 252 }
 253
 254 /** Sort expanded expression in terms of powers of some object(s).
 255  *  @param s object(s) to sort in
 256  *  @param distributed recursive or distributed form (only used when s is a list) */
 257 ex basic::collect(const ex & s, bool distributed) const
 258 {
 259         ex x;
 260         if (is_ex_of_type(s, lst)) {
 261
 262                 // List of objects specified
 263                 if (s.nops() == 0)
 264                         return *this;
 265                 if (s.nops() == 1)
 266                         return collect(s.op(0));
 267
 268                 else if (distributed) {
 269
 270                         // Get lower/upper degree of all symbols in list
 271                         int num = s.nops();
 272                         struct sym_info {
 273                                 ex sym;
 274                                 int ldeg, deg;
 275                                 int cnt;  // current degree, 'counter'
 276                                 ex coeff; // coefficient for degree 'cnt'
 277                         };
 278                         sym_info *si = new sym_info[num];
 279                         ex c = *this;
 280                         for (int i=0; i<num; i++) {
 281                                 si[i].sym = s.op(i);
 282                                 si[i].ldeg = si[i].cnt = this->ldegree(si[i].sym);
 283                                 si[i].deg = this->degree(si[i].sym);
 284                                 c = si[i].coeff = c.coeff(si[i].sym, si[i].cnt);
 285                         }
 286
 287                         while (true) {
 288
 289                                 // Calculate coeff*x1^c1*...*xn^cn
 290                                 ex y = _ex1;
 291                                 for (int i=0; i<num; i++) {
 292                                         int cnt = si[i].cnt;
 293                                         y *= power(si[i].sym, cnt);
 294                                 }
 295                                 x += y * si[num - 1].coeff;
 296
 297                                 // Increment counters
 298                                 int n = num - 1;
 299                                 while (true) {
 300                                         ++si[n].cnt;
 301                                         if (si[n].cnt <= si[n].deg) {
 302                                                 // Update coefficients
 303                                                 ex c;
 304                                                 if (n == 0)
 305                                                         c = *this;
 306                                                 else
 307                                                         c = si[n - 1].coeff;
 308                                                 for (int i=n; i<num; i++)
 309                                                         c = si[i].coeff = c.coeff(si[i].sym, si[i].cnt);
 310                                                 break;
 311                                         }
 312                                         if (n == 0)
 313                                                 goto done;
 314                                         si[n].cnt = si[n].ldeg;
 315                                         n--;
 316                                 }
 317                         }
 318
 319 done:           delete[] si;
 320
 321                 } else {
 322
 323                         // Recursive form
 324                         x = *this;
 325                         for (int n=s.nops()-1; n>=0; n--)
 326                                 x = x.collect(s[n]);
 327                 }
 328
 329         } else {
 330
 331                 // Only one object specified
 332                 for (int n=this->ldegree(s); n<=this->degree(s); ++n)
 333                         x += this->coeff(s,n)*power(s,n);
 334         }
 335
 336         // correct for lost fractional arguments and return
 337         return x + (*this - x).expand();
 338 }
 339
 340 /** Perform automatic non-interruptive term rewriting rules. */
 341 ex basic::eval(int level) const
 342 {
 343         // There is nothing to do for basic objects:
 344         return this->hold();
 345 }
 346
 347 /** Function object to be applied by basic::evalf(). */
 348 struct evalf_map_function : public map_function {
 349         int level;
 350         evalf_map_function(int l) : level(l) {}
 351         ex operator()(const ex & e) { return evalf(e, level); }
 352 };
 353
 354 /** Evaluate object numerically. */
 355 ex basic::evalf(int level) const
 356 {
 357         if (nops() == 0)
 358                 return *this;
 359         else {
 360                 if (level == 1)
 361                         return *this;
 362                 else if (level == -max_recursion_level)
 363                         throw(std::runtime_error("max recursion level reached"));
 364                 else {
 365                         evalf_map_function map_evalf(level - 1);
 366                         return map(map_evalf);
 367                 }
 368         }
 369 }
 370
 371 /** Function object to be applied by basic::evalm(). */
 372 struct evalm_map_function : public map_function {
 373         ex operator()(const ex & e) { return evalm(e); }
 374 } map_evalm;
 375
 376 /** Evaluate sums, products and integer powers of matrices. */
 377 ex basic::evalm(void) const
 378 {
 379         if (nops() == 0)
 380                 return *this;
 381         else
 382                 return map(map_evalm);
 383 }
 384
 385 /** Perform automatic symbolic evaluations on indexed expression that
 386  *  contains this object as the base expression. */
 387 ex basic::eval_indexed(const basic & i) const
 388  // this function can't take a "const ex & i" because that would result
 389  // in an infinite eval() loop
 390 {
 391         // There is nothing to do for basic objects
 392         return i.hold();
 393 }
 394
 395 /** Add two indexed expressions. They are guaranteed to be of class indexed
 396  *  (or a subclass) and their indices are compatible. This function is used
 397  *  internally by simplify_indexed().
 398  *
 399  *  @param self First indexed expression; it's base object is *this
 400  *  @param other Second indexed expression
 401  *  @return sum of self and other
 402  *  @see ex::simplify_indexed() */
 403 ex basic::add_indexed(const ex & self, const ex & other) const
 404 {
 405         return self + other;
 406 }
 407
 408 /** Multiply an indexed expression with a scalar. This function is used
 409  *  internally by simplify_indexed().
 410  *
 411  *  @param self Indexed expression; it's base object is *this
 412  *  @param other Numeric value
 413  *  @return product of self and other
 414  *  @see ex::simplify_indexed() */
 415 ex basic::scalar_mul_indexed(const ex & self, const numeric & other) const
 416 {
 417         return self * other;
 418 }
 419
 420 /** Try to contract two indexed expressions that appear in the same product.
 421  *  If a contraction exists, the function overwrites one or both of the
 422  *  expressions and returns true. Otherwise it returns false. It is
 423  *  guaranteed that both expressions are of class indexed (or a subclass)
 424  *  and that at least one dummy index has been found. This functions is
 425  *  used internally by simplify_indexed().
 426  *
 427  *  @param self Pointer to first indexed expression; it's base object is *this
 428  *  @param other Pointer to second indexed expression
 429  *  @param v The complete vector of factors
 430  *  @return true if the contraction was successful, false otherwise
 431  *  @see ex::simplify_indexed() */
 432 bool basic::contract_with(exvector::iterator self, exvector::iterator other, exvector & v) const
 433 {
 434         // Do nothing
 435         return false;
 436 }
 437
 438 /** Check whether the expression matches a given pattern. For every wildcard
 439  *  object in the pattern, an expression of the form "wildcard == matching_expression"
 440  *  is added to repl_lst. */
 441 bool basic::match(const ex & pattern, lst & repl_lst) const
 442 {
 443 /*
 444         Sweet sweet shapes, sweet sweet shapes,
 445         That's the key thing, right right.
 446         Feed feed face, feed feed shapes,
 447         But who is the king tonight?
 448         Who is the king tonight?
 449         Pattern is the thing, the key thing-a-ling,
 450         But who is the king of Pattern?
 451         But who is the king, the king thing-a-ling,
 452         Who is the king of Pattern?
 453         Bog is the king, the king thing-a-ling,
 454         Bog is the king of Pattern.
 455         Ba bu-bu-bu-bu bu-bu-bu-bu-bu-bu bu-bu
 456         Bog is the king of Pattern.
 457 */
 458
 459         if (is_ex_exactly_of_type(pattern, wildcard)) {
 460
 461                 // Wildcard matches anything, but check whether we already have found
 462                 // a match for that wildcard first (if so, it the earlier match must
 463                 // be the same expression)
 464                 for (unsigned i=0; i<repl_lst.nops(); i++) {
 465                         if (repl_lst.op(i).op(0).is_equal(pattern))
 466                                 return is_equal(ex_to<basic>(repl_lst.op(i).op(1)));
 467                 }
 468                 repl_lst.append(pattern == *this);
 469                 return true;
 470
 471         } else {
 472
 473                 // Expression must be of the same type as the pattern
 474                 if (tinfo() != ex_to<basic>(pattern).tinfo())
 475                         return false;
 476
 477                 // Number of subexpressions must match
 478                 if (nops() != pattern.nops())
 479                         return false;
 480
 481                 // No subexpressions? Then just compare the objects (there can't be
 482                 // wildcards in the pattern)
 483                 if (nops() == 0)
 484                         return is_equal_same_type(ex_to<basic>(pattern));
 485
 486                 // Check whether attributes that are not subexpressions match
 487                 if (!match_same_type(ex_to<basic>(pattern)))
 488                         return false;
 489
 490                 // Otherwise the subexpressions must match one-to-one
 491                 for (unsigned i=0; i<nops(); i++)
 492                         if (!op(i).match(pattern.op(i), repl_lst))
 493                                 return false;
 494
 495                 // Looks similar enough, match found
 496                 return true;
 497         }
 498 }
 499
 500 /** Substitute a set of objects by arbitrary expressions. The ex returned
 501  *  will already be evaluated. */
 502 ex basic::subs(const lst & ls, const lst & lr, bool no_pattern) const
 503 {
 504         GINAC_ASSERT(ls.nops() == lr.nops());
 505
 506         if (no_pattern) {
 507                 for (unsigned i=0; i<ls.nops(); i++) {
 508                         if (is_equal(ex_to<basic>(ls.op(i))))
 509                                 return lr.op(i);
 510                 }
 511         } else {
 512                 for (unsigned i=0; i<ls.nops(); i++) {
 513                         lst repl_lst;
 514                         if (match(ex_to<basic>(ls.op(i)), repl_lst))
 515                                 return lr.op(i).subs(repl_lst, true); // avoid infinite recursion when re-substituting the wildcards
 516                 }
 517         }
 518
 519         return *this;
 520 }
 521
 522 /** Default interface of nth derivative ex::diff(s, n).  It should be called
 523  *  instead of ::derivative(s) for first derivatives and for nth derivatives it
 524  *  just recurses down.
 525  *
 526  *  @param s symbol to differentiate in
 527  *  @param nth order of differentiation
 528  *  @see ex::diff */
 529 ex basic::diff(const symbol & s, unsigned nth) const
 530 {
 531         // trivial: zeroth derivative
 532         if (nth==0)
 533                 return ex(*this);
 534
 535         // evaluate unevaluated *this before differentiating
 536         if (!(flags & status_flags::evaluated))
 537                 return ex(*this).diff(s, nth);
 538
 539         ex ndiff = this->derivative(s);
 540         while (!ndiff.is_zero() &&    // stop differentiating zeros
 541                nth>1) {
 542                 ndiff = ndiff.diff(s);
 543                 --nth;
 544         }
 545         return ndiff;
 546 }
 547
 548 /** Return a vector containing the free indices of an expression. */
 549 exvector basic::get_free_indices(void) const
 550 {
 551         return exvector(); // return an empty exvector
 552 }
 553
 554 ex basic::simplify_ncmul(const exvector & v) const
 555 {
 556         return simplified_ncmul(v);
 557 }
 558
 559 // protected
 560
 561 /** Function object to be applied by basic::derivative(). */
 562 struct derivative_map_function : public map_function {
 563         const symbol &s;
 564         derivative_map_function(const symbol &sym) : s(sym) {}
 565         ex operator()(const ex & e) { return diff(e, s); }
 566 };
 567
 568 /** Default implementation of ex::diff(). It maps the operation on the
 569  *  operands (or returns 0 when the object has no operands).
 570  *
 571  *  @see ex::diff */
 572 ex basic::derivative(const symbol & s) const
 573 {
 574         if (nops() == 0)
 575                 return _ex0;
 576         else {
 577                 derivative_map_function map_derivative(s);
 578                 return map(map_derivative);
 579         }
 580 }
 581
 582 /** Returns order relation between two objects of same type.  This needs to be
 583  *  implemented by each class. It may never return anything else than 0,
 584  *  signalling equality, or +1 and -1 signalling inequality and determining
 585  *  the canonical ordering.  (Perl hackers will wonder why C++ doesn't feature
 586  *  the spaceship operator <=> for denoting just this.) */
 587 int basic::compare_same_type(const basic & other) const
 588 {
 589         return compare_pointers(this, &other);
 590 }
 591
 592 /** Returns true if two objects of same type are equal.  Normally needs
 593  *  not be reimplemented as long as it wasn't overwritten by some parent
 594  *  class, since it just calls compare_same_type().  The reason why this
 595  *  function exists is that sometimes it is easier to determine equality
 596  *  than an order relation and then it can be overridden. */
 597 bool basic::is_equal_same_type(const basic & other) const
 598 {
 599         return compare_same_type(other)==0;
 600 }
 601
 602 /** Returns true if the attributes of two objects are similar enough for
 603  *  a match. This function must not match subexpressions (this is already
 604  *  done by basic::match()). Only attributes not accessible by op() should
 605  *  be compared. This is also the reason why this function doesn't take the
 606  *  wildcard replacement list from match() as an argument: only subexpressions
 607  *  are subject to wildcard matches. Also, this function only needs to be
 608  *  implemented for container classes because is_equal_same_type() is
 609  *  automatically used instead of match_same_type() if nops() == 0.
 610  *
 611  *  @see basic::match */
 612 bool basic::match_same_type(const basic & other) const
 613 {
 614         // The default is to only consider subexpressions, but not any other
 615         // attributes
 616         return true;
 617 }
 618
 619 unsigned basic::return_type(void) const
 620 {
 621         return return_types::commutative;
 622 }
 623
 624 unsigned basic::return_type_tinfo(void) const
 625 {
 626         return tinfo();
 627 }
 628
 629 /** Compute the hash value of an object and if it makes sense to store it in
 630  *  the objects status_flags, do so.  The method inherited from class basic
 631  *  computes a hash value based on the type and hash values of possible
 632  *  members.  For this reason it is well suited for container classes but
 633  *  atomic classes should override this implementation because otherwise they
 634  *  would all end up with the same hashvalue. */
 635 unsigned basic::calchash(void) const
 636 {
 637         unsigned v = golden_ratio_hash(tinfo());
 638         for (unsigned i=0; i<nops(); i++) {
 639                 v = rotate_left_31(v);
 640                 v ^= (const_cast<basic *>(this))->op(i).gethash();
 641         }
 642
 643         // mask out numeric hashes:
 644         v &= 0x7FFFFFFFU;
 645
 646         // store calculated hash value only if object is already evaluated
 647         if (flags & status_flags::evaluated) {
 648                 setflag(status_flags::hash_calculated);
 649                 hashvalue = v;
 650         }
 651
 652         return v;
 653 }
 654
 655 /** Function object to be applied by basic::expand(). */
 656 struct expand_map_function : public map_function {
 657         unsigned options;
 658         expand_map_function(unsigned o) : options(o) {}
 659         ex operator()(const ex & e) { return expand(e, options); }
 660 };
 661
 662 /** Expand expression, i.e. multiply it out and return the result as a new
 663  *  expression. */
 664 ex basic::expand(unsigned options) const
 665 {
 666         if (nops() == 0)
 667                 return (options == 0) ? setflag(status_flags::expanded) : *this;
 668         else {
 669                 expand_map_function map_expand(options);
 670                 return ex_to<basic>(map(map_expand)).setflag(options == 0 ? status_flags::expanded : 0);
 671         }
 672 }
 673
 674
 675 //////////
 676 // non-virtual functions in this class
 677 //////////
 678
 679 // public
 680
 681 /** Substitute objects in an expression (syntactic substitution) and return
 682  *  the result as a new expression.  There are two valid types of
 683  *  replacement arguments: 1) a relational like object==ex and 2) a list of
 684  *  relationals lst(object1==ex1,object2==ex2,...), which is converted to
 685  *  subs(lst(object1,object2,...),lst(ex1,ex2,...)). */
 686 ex basic::subs(const ex & e, bool no_pattern) const
 687 {
 688         if (e.info(info_flags::relation_equal)) {
 689                 return subs(lst(e), no_pattern);
 690         }
 691         if (!e.info(info_flags::list)) {
 692                 throw(std::invalid_argument("basic::subs(ex): argument must be a list"));
 693         }
 694         lst ls;
 695         lst lr;
 696         for (unsigned i=0; i<e.nops(); i++) {
 697                 ex r = e.op(i);
 698                 if (!r.info(info_flags::relation_equal)) {
 699                         throw(std::invalid_argument("basic::subs(ex): argument must be a list of equations"));
 700                 }
 701                 ls.append(r.op(0));
 702                 lr.append(r.op(1));
 703         }
 704         return subs(ls, lr, no_pattern);
 705 }
 706
 707 /** Compare objects to establish canonical ordering.
 708  *  All compare functions return: -1 for *this less than other, 0 equal,
 709  *  1 greater. */
 710 int basic::compare(const basic & other) const
 711 {
 712         unsigned hash_this = gethash();
 713         unsigned hash_other = other.gethash();
 714
 715         if (hash_this<hash_other) return -1;
 716         if (hash_this>hash_other) return 1;
 717
 718         unsigned typeid_this = tinfo();
 719         unsigned typeid_other = other.tinfo();
 720
 721         if (typeid_this<typeid_other) {
 722 //              std::cout << "hash collision, different types: "
 723 //                        << *this << " and " << other << std::endl;
 724 //              this->print(print_tree(std::cout));
 725 //              std::cout << " and ";
 726 //              other.print(print_tree(std::cout));
 727 //              std::cout << std::endl;
 728                 return -1;
 729         }
 730         if (typeid_this>typeid_other) {
 731 //              std::cout << "hash collision, different types: "
 732 //                        << *this << " and " << other << std::endl;
 733 //              this->print(print_tree(std::cout));
 734 //              std::cout << " and ";
 735 //              other.print(print_tree(std::cout));
 736 //              std::cout << std::endl;
 737                 return 1;
 738         }
 739
 740         GINAC_ASSERT(typeid(*this)==typeid(other));
 741
 742 //      int cmpval = compare_same_type(other);
 743 //      if ((cmpval!=0) && (hash_this<0x80000000U)) {
 744 //              std::cout << "hash collision, same type: "
 745 //                        << *this << " and " << other << std::endl;
 746 //              this->print(print_tree(std::cout));
 747 //              std::cout << " and ";
 748 //              other.print(print_tree(std::cout));
 749 //              std::cout << std::endl;
 750 //      }
 751 //      return cmpval;
 752
 753         return compare_same_type(other);
 754 }
 755
 756 /** Test for equality.
 757  *  This is only a quick test, meaning objects should be in the same domain.
 758  *  You might have to .expand(), .normal() objects first, depending on the
 759  *  domain of your computation, to get a more reliable answer.
 760  *
 761  *  @see is_equal_same_type */
 762 bool basic::is_equal(const basic & other) const
 763 {
 764         if (this->gethash()!=other.gethash())
 765                 return false;
 766         if (this->tinfo()!=other.tinfo())
 767                 return false;
 768
 769         GINAC_ASSERT(typeid(*this)==typeid(other));
 770
 771         return is_equal_same_type(other);
 772 }
 773
 774 // protected
 775
 776 /** Stop further evaluation.
 777  *
 778  *  @see basic::eval */
 779 const basic & basic::hold(void) const
 780 {
 781         return setflag(status_flags::evaluated);
 782 }
 783
 784 /** Ensure the object may be modified without hurting others, throws if this
 785  *  is not the case. */
 786 void basic::ensure_if_modifiable(void) const
 787 {
 788         if (this->refcount>1)
 789                 throw(std::runtime_error("cannot modify multiply referenced object"));
 790         clearflag(status_flags::hash_calculated);
 791 }
 792
 793 //////////
 794 // global variables
 795 //////////
 796
 797 int max_recursion_level = 1024;
 798
 799 } // namespace GiNaC