prop-src/timespace.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.6),
   3 //  last updated on Nov 2, 1999.
   4 //  The original source file is "timespace.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_REWRITING_USED
   8 #define PROP_QUARK_USED
   9 #include <propdefs.h>
  10 #line 1 "timespace.pcc"
  11 ///////////////////////////////////////////////////////////////////////////////
  12 //
  13 //  This file implements the time and space complexity
  14 //  datatypes.  These datatypes are used to represent time and space
  15 //  complexity in the SETL-like extension language.
  16 //
  17 ///////////////////////////////////////////////////////////////////////////////
  18 #include <math.h>
  19 #include <iostream>
  20 #include "basics.h"
  21 #include "timespace.h"
  22
  23 ///////////////////////////////////////////////////////////////////////////////
  24 //
  25 //  Instantiate the time and space datatypes
  26 //
  27 ///////////////////////////////////////////////////////////////////////////////
  28 #line 18 "timespace.pcc"
  29 #line 18 "timespace.pcc"
  30 ///////////////////////////////////////////////////////////////////////////////
  31 //
  32 // Interface specification of datatype Complexity
  33 //
  34 ///////////////////////////////////////////////////////////////////////////////
  35 #line 18 "timespace.pcc"
  36
  37
  38 ///////////////////////////////////////////////////////////////////////////////
  39 //
  40 // Interface specification of datatype Time
  41 //
  42 ///////////////////////////////////////////////////////////////////////////////
  43 #line 18 "timespace.pcc"
  44
  45
  46 ///////////////////////////////////////////////////////////////////////////////
  47 //
  48 // Interface specification of datatype Space
  49 //
  50 ///////////////////////////////////////////////////////////////////////////////
  51 #line 18 "timespace.pcc"
  52
  53
  54 ///////////////////////////////////////////////////////////////////////////////
  55 //
  56 // Instantiation of datatype Complexity
  57 //
  58 ///////////////////////////////////////////////////////////////////////////////
  59 #line 18 "timespace.pcc"
  60 Complexity_Var::Complexity_Var (Id x_Var)
  61  : a_Complexity(tag_Var), Var(x_Var)
  62 {
  63 }
  64 a_Complexity * Var (Id x_Var)
  65 {
  66    return new Complexity_Var (x_Var);
  67 }
  68 Complexity_Add::Complexity_Add (Complexity x_1, Complexity x_2)
  69  : a_Complexity(tag_Add), _1(x_1), _2(x_2)
  70 {
  71 }
  72 a_Complexity * Add (Complexity x_1, Complexity x_2)
  73 {
  74    return new Complexity_Add (x_1, x_2);
  75 }
  76 Complexity_Mul::Complexity_Mul (Complexity x_1, Complexity x_2)
  77  : a_Complexity(tag_Mul), _1(x_1), _2(x_2)
  78 {
  79 }
  80 a_Complexity * Mul (Complexity x_1, Complexity x_2)
  81 {
  82    return new Complexity_Mul (x_1, x_2);
  83 }
  84 Complexity_Div::Complexity_Div (Complexity x_1, Complexity x_2)
  85  : a_Complexity(tag_Div), _1(x_1), _2(x_2)
  86 {
  87 }
  88 a_Complexity * Div (Complexity x_1, Complexity x_2)
  89 {
  90    return new Complexity_Div (x_1, x_2);
  91 }
  92 Complexity_Power::Complexity_Power (Complexity x_1, Complexity x_2)
  93  : a_Complexity(tag_Power), _1(x_1), _2(x_2)
  94 {
  95 }
  96 a_Complexity * Power (Complexity x_1, Complexity x_2)
  97 {
  98    return new Complexity_Power (x_1, x_2);
  99 }
 100 Complexity_Log::Complexity_Log (Complexity x_Log)
 101  : a_Complexity(tag_Log), Log(x_Log)
 102 {
 103 }
 104 a_Complexity * Log (Complexity x_Log)
 105 {
 106    return new Complexity_Log (x_Log);
 107 }
 108 Complexity_Const::Complexity_Const (double x_Const)
 109  : a_Complexity(tag_Const), Const(x_Const)
 110 {
 111 }
 112 a_Complexity * Const (double x_Const)
 113 {
 114    return new Complexity_Const (x_Const);
 115 }
 116 Complexity_BigOh::Complexity_BigOh (Complexity x_BigOh)
 117  : a_Complexity(tag_BigOh), BigOh(x_BigOh)
 118 {
 119 }
 120 a_Complexity * BigOh (Complexity x_BigOh)
 121 {
 122    return new Complexity_BigOh (x_BigOh);
 123 }
 124 Complexity_Omega::Complexity_Omega (Complexity x_Omega)
 125  : a_Complexity(tag_Omega), Omega(x_Omega)
 126 {
 127 }
 128 a_Complexity * Omega (Complexity x_Omega)
 129 {
 130    return new Complexity_Omega (x_Omega);
 131 }
 132 Complexity_LittleOh::Complexity_LittleOh (Complexity x_LittleOh)
 133  : a_Complexity(tag_LittleOh), LittleOh(x_LittleOh)
 134 {
 135 }
 136 a_Complexity * LittleOh (Complexity x_LittleOh)
 137 {
 138    return new Complexity_LittleOh (x_LittleOh);
 139 }
 140
 141
 142 ///////////////////////////////////////////////////////////////////////////////
 143 //
 144 // Instantiation of datatype Time
 145 //
 146 ///////////////////////////////////////////////////////////////////////////////
 147 #line 18 "timespace.pcc"
 148 a_Time::a_Time (Complexity x_TIME)
 149  : TIME(x_TIME)
 150 {
 151 }
 152 a_Time * TIME (Complexity x_TIME)
 153 {
 154    return new a_Time (x_TIME);
 155 }
 156
 157
 158 ///////////////////////////////////////////////////////////////////////////////
 159 //
 160 // Instantiation of datatype Space
 161 //
 162 ///////////////////////////////////////////////////////////////////////////////
 163 #line 18 "timespace.pcc"
 164 a_Space::a_Space (Complexity x_SPACE)
 165  : SPACE(x_SPACE)
 166 {
 167 }
 168 a_Space * SPACE (Complexity x_SPACE)
 169 {
 170    return new a_Space (x_SPACE);
 171 }
 172
 173
 174 #line 18 "timespace.pcc"
 175 #line 18 "timespace.pcc"
 176
 177
 178 ///////////////////////////////////////////////////////////////////////////////
 179 //
 180 //  Pretty print the complexity
 181 //
 182 ///////////////////////////////////////////////////////////////////////////////
 183 std::ostream& operator << (std::ostream& f, Complexity c)
 184 {
 185 #line 26 "timespace.pcc"
 186 #line 36 "timespace.pcc"
 187 {
 188    switch (c->tag__) {
 189       case a_Complexity::tag_Var: {
 190 #line 27 "timespace.pcc"
 191         f << ((Complexity_Var *)c)->Var;
 192 #line 27 "timespace.pcc"
 193          } break;
 194       case a_Complexity::tag_Add: {
 195 #line 28 "timespace.pcc"
 196         f << '(' << ((Complexity_Add *)c)->_1 << " + " << ((Complexity_Add *)c)->_2 << ')';
 197 #line 28 "timespace.pcc"
 198          } break;
 199       case a_Complexity::tag_Mul: {
 200 #line 29 "timespace.pcc"
 201         f << '(' << ((Complexity_Mul *)c)->_1 << " * " << ((Complexity_Mul *)c)->_2 << ')';
 202 #line 29 "timespace.pcc"
 203          } break;
 204       case a_Complexity::tag_Div: {
 205 #line 30 "timespace.pcc"
 206         f << '(' << ((Complexity_Div *)c)->_1 << " / " << ((Complexity_Div *)c)->_2 << ')';
 207 #line 30 "timespace.pcc"
 208          } break;
 209       case a_Complexity::tag_Power: {
 210 #line 31 "timespace.pcc"
 211         f << '(' << ((Complexity_Power *)c)->_1 << " ^ " << ((Complexity_Power *)c)->_2 << ')';
 212 #line 31 "timespace.pcc"
 213          } break;
 214       case a_Complexity::tag_Log: {
 215 #line 32 "timespace.pcc"
 216         f << "log " << ((Complexity_Log *)c)->Log;
 217 #line 32 "timespace.pcc"
 218          } break;
 219       case a_Complexity::tag_Const: {
 220 #line 33 "timespace.pcc"
 221         f << ((Complexity_Const *)c)->Const;
 222 #line 33 "timespace.pcc"
 223          } break;
 224       case a_Complexity::tag_BigOh: {
 225 #line 34 "timespace.pcc"
 226         f << "O(" << ((Complexity_BigOh *)c)->BigOh << ')';
 227 #line 34 "timespace.pcc"
 228          } break;
 229       case a_Complexity::tag_Omega: {
 230 #line 35 "timespace.pcc"
 231         f << "Omega(" << ((Complexity_Omega *)c)->Omega << ')';
 232 #line 35 "timespace.pcc"
 233          } break;
 234       default: {
 235 #line 36 "timespace.pcc"
 236         f << "o(" << ((Complexity_LittleOh *)c)->LittleOh << ')';
 237 #line 36 "timespace.pcc"
 238          } break;
 239    }
 240 }
 241 #line 37 "timespace.pcc"
 242 #line 37 "timespace.pcc"
 243
 244    return f;
 245 }
 246
 247 ///////////////////////////////////////////////////////////////////////////////
 248 //
 249 //  Pretty print the time complexity
 250 //
 251 ///////////////////////////////////////////////////////////////////////////////
 252 std::ostream& operator << (std::ostream& f, Time t)
 253 {  return f << "Time(" << t << ")"; }
 254
 255 ///////////////////////////////////////////////////////////////////////////////
 256 //
 257 //  Pretty print the space complexity
 258 //
 259 ///////////////////////////////////////////////////////////////////////////////
 260 std::ostream& operator << (std::ostream& f, Space s)
 261 {  return f << "Space(" << s << ")"; }
 262
 263 ///////////////////////////////////////////////////////////////////////////////
 264 //
 265 //  Function to simplify a complexity expression
 266 //
 267 ///////////////////////////////////////////////////////////////////////////////
 268 Complexity simplify (Complexity c)
 269 {
 270 #line 63 "timespace.pcc"
 271 #line 69 "timespace.pcc"
 272    extern void  _t_i_m_e_s_p_a_c_eco_X1_rewrite(Complexity & );
 273    _t_i_m_e_s_p_a_c_eco_X1_rewrite(c);
 274 #line 69 "timespace.pcc"
 275 #line 69 "timespace.pcc"
 276
 277    return c;
 278 }
 279 #line 72 "timespace.pcc"
 280 class _t_i_m_e_s_p_a_c_eco_X1 : public BURS {
 281 private:
 282    _t_i_m_e_s_p_a_c_eco_X1(const _t_i_m_e_s_p_a_c_eco_X1&);               // no copy constructor
 283    void operator = (const _t_i_m_e_s_p_a_c_eco_X1&); // no assignment
 284 public:
 285    struct _t_i_m_e_s_p_a_c_eco_X1_StateRec * stack__, * stack_top__;
 286 public:
 287    void labeler(const char *, int&, int);
 288    void labeler(Quark, int&, int);
 289           void  labeler(Complexity & redex, int&, int);
 290    inline virtual void  operator () (Complexity & redex) { int s; labeler(redex,s,0); }
 291 private:
 292    public:
 293       inline _t_i_m_e_s_p_a_c_eco_X1() {}
 294 };
 295 void  _t_i_m_e_s_p_a_c_eco_X1_rewrite(Complexity &  _x_)
 296 {  _t_i_m_e_s_p_a_c_eco_X1 _r_;
 297    _r_(_x_);
 298 }
 299
 300 ///////////////////////////////////////////////////////////////////////////////
 301 //
 302 // This macro can be redefined by the user for debugging
 303 //
 304 ///////////////////////////////////////////////////////////////////////////////
 305 #ifndef DEBUG__t_i_m_e_s_p_a_c_eco_X1
 306 #define DEBUG__t_i_m_e_s_p_a_c_eco_X1(repl,redex,file,line,rule) repl
 307 #else
 308 static const char * _t_i_m_e_s_p_a_c_eco_X1_file_name = "timespace.pcc";
 309 #endif
 310
 311 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_theta_1[2][2] = {
 312    { 0, 0 },
 313    { 0, 2 }
 314 };
 315
 316
 317 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_theta_2[2][2] = {
 318    { 0, 0 },
 319    { 0, 3 }
 320 };
 321
 322
 323 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_theta_3[2][2] = {
 324    { 0, 0 },
 325    { 0, 4 }
 326 };
 327
 328
 329 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_theta_4[2][2] = {
 330    { 0, 0 },
 331    { 0, 5 }
 332 };
 333
 334
 335 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_theta_5[2] = {
 336    0, 6
 337 };
 338
 339
 340 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_1_0[7] = {
 341    0, 1, 0, 0, 0, 0, 0
 342 };
 343
 344
 345 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_1_1[7] = {
 346    0, 1, 0, 0, 0, 0, 0
 347 };
 348
 349
 350 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_2_0[7] = {
 351    0, 1, 0, 0, 0, 0, 0
 352 };
 353
 354
 355 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_2_1[7] = {
 356    0, 1, 0, 0, 0, 0, 0
 357 };
 358
 359
 360 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_3_0[7] = {
 361    0, 1, 0, 0, 0, 0, 0
 362 };
 363
 364
 365 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_3_1[7] = {
 366    0, 1, 0, 0, 0, 0, 0
 367 };
 368
 369
 370 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_4_0[7] = {
 371    0, 1, 0, 0, 0, 0, 0
 372 };
 373
 374
 375 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_4_1[7] = {
 376    0, 1, 0, 0, 0, 0, 0
 377 };
 378
 379
 380 static const TreeTables::ShortState _t_i_m_e_s_p_a_c_eco_X1_mu_5_0[7] = {
 381    0, 1, 0, 0, 0, 0, 0
 382 };
 383
 384
 385 inline void  _t_i_m_e_s_p_a_c_eco_X1::labeler(char const * redex,int& s__,int)
 386 {
 387    {
 388 s__ = 0;
 389    }
 390 }
 391
 392 inline void  _t_i_m_e_s_p_a_c_eco_X1::labeler(Quark redex,int& s__,int)
 393 {
 394    {
 395 s__ = 0;
 396    }
 397 }
 398
 399 void  _t_i_m_e_s_p_a_c_eco_X1::labeler (Complexity & redex, int& s__, int r__)
 400 {
 401 replacement__:
 402    switch(redex->tag__) {
 403       case a_Complexity::tag_Var: {
 404          int s0__;
 405          labeler(((Complexity_Var *)redex)->Var, s0__, r__);
 406          s__ = 0;} break;
 407       case a_Complexity::tag_Add: {
 408          int s0__;
 409          int s1__;
 410          labeler(((Complexity_Add *)redex)->_1, s0__, r__);
 411          labeler(((Complexity_Add *)redex)->_2, s1__, r__);
 412          s__ = _t_i_m_e_s_p_a_c_eco_X1_theta_1[_t_i_m_e_s_p_a_c_eco_X1_mu_1_0[s0__]][_t_i_m_e_s_p_a_c_eco_X1_mu_1_1[s1__]]; } break;
 413       case a_Complexity::tag_Mul: {
 414          int s0__;
 415          int s1__;
 416          labeler(((Complexity_Mul *)redex)->_1, s0__, r__);
 417          labeler(((Complexity_Mul *)redex)->_2, s1__, r__);
 418          s__ = _t_i_m_e_s_p_a_c_eco_X1_theta_2[_t_i_m_e_s_p_a_c_eco_X1_mu_2_0[s0__]][_t_i_m_e_s_p_a_c_eco_X1_mu_2_1[s1__]]; } break;
 419       case a_Complexity::tag_Div: {
 420          int s0__;
 421          int s1__;
 422          labeler(((Complexity_Div *)redex)->_1, s0__, r__);
 423          labeler(((Complexity_Div *)redex)->_2, s1__, r__);
 424          s__ = _t_i_m_e_s_p_a_c_eco_X1_theta_3[_t_i_m_e_s_p_a_c_eco_X1_mu_3_0[s0__]][_t_i_m_e_s_p_a_c_eco_X1_mu_3_1[s1__]]; } break;
 425       case a_Complexity::tag_Power: {
 426          int s0__;
 427          int s1__;
 428          labeler(((Complexity_Power *)redex)->_1, s0__, r__);
 429          labeler(((Complexity_Power *)redex)->_2, s1__, r__);
 430          s__ = _t_i_m_e_s_p_a_c_eco_X1_theta_4[_t_i_m_e_s_p_a_c_eco_X1_mu_4_0[s0__]][_t_i_m_e_s_p_a_c_eco_X1_mu_4_1[s1__]]; } break;
 431       case a_Complexity::tag_Log: {
 432          int s0__;
 433          labeler(((Complexity_Log *)redex)->Log, s0__, r__);
 434          s__ = _t_i_m_e_s_p_a_c_eco_X1_theta_5[_t_i_m_e_s_p_a_c_eco_X1_mu_5_0[s0__]]; } break;
 435       case a_Complexity::tag_Const: {
 436          int s0__;
 437          s0__ = 0; // double
 438          s__ = 1;} break;
 439       case a_Complexity::tag_BigOh: {
 440          int s0__;
 441          labeler(((Complexity_BigOh *)redex)->BigOh, s0__, r__);
 442          s__ = 0;} break;
 443       case a_Complexity::tag_Omega: {
 444          int s0__;
 445          labeler(((Complexity_Omega *)redex)->Omega, s0__, r__);
 446          s__ = 0;} break;
 447       default: {
 448          int s0__;
 449          labeler(((Complexity_LittleOh *)redex)->LittleOh, s0__, r__);
 450          s__ = 0;} break;
 451    }
 452    switch (s__) {
 453       case 6: {
 454 #line 68 "timespace.pcc"
 455          { redex = DEBUG__t_i_m_e_s_p_a_c_eco_X1(Const(log(((Complexity_Const *)((Complexity_Log *)redex)->Log)->Const)),redex,_t_i_m_e_s_p_a_c_eco_X1_file_name,68,"Log Const i: ...");
 456            r__ = 1; goto replacement__; }
 457 #line 69 "timespace.pcc"
 458 } break;
 459       case 5: {
 460 #line 67 "timespace.pcc"
 461          { redex = DEBUG__t_i_m_e_s_p_a_c_eco_X1(Const(exp((log(((Complexity_Const *)((Complexity_Power *)redex)->_1)->Const) * ((Complexity_Const *)((Complexity_Power *)redex)->_2)->Const))),redex,_t_i_m_e_s_p_a_c_eco_X1_file_name,67,"Power (Const i, Const j): ...");
 462            r__ = 1; goto replacement__; }
 463 #line 68 "timespace.pcc"
 464 } break;
 465       case 4: {
 466 #line 66 "timespace.pcc"
 467          { redex = DEBUG__t_i_m_e_s_p_a_c_eco_X1(Const((((Complexity_Const *)((Complexity_Div *)redex)->_1)->Const / ((Complexity_Const *)((Complexity_Div *)redex)->_2)->Const)),redex,_t_i_m_e_s_p_a_c_eco_X1_file_name,66,"Div (Const i, Const j): ...");
 468            r__ = 1; goto replacement__; }
 469 #line 67 "timespace.pcc"
 470 } break;
 471       case 3: {
 472 #line 65 "timespace.pcc"
 473          { redex = DEBUG__t_i_m_e_s_p_a_c_eco_X1(Const((((Complexity_Const *)((Complexity_Mul *)redex)->_1)->Const * ((Complexity_Const *)((Complexity_Mul *)redex)->_2)->Const)),redex,_t_i_m_e_s_p_a_c_eco_X1_file_name,65,"Mul (Const i, Const j): ...");
 474            r__ = 1; goto replacement__; }
 475 #line 66 "timespace.pcc"
 476 } break;
 477       case 2: {
 478 #line 64 "timespace.pcc"
 479          { redex = DEBUG__t_i_m_e_s_p_a_c_eco_X1(Const((((Complexity_Const *)((Complexity_Add *)redex)->_1)->Const + ((Complexity_Const *)((Complexity_Add *)redex)->_2)->Const)),redex,_t_i_m_e_s_p_a_c_eco_X1_file_name,64,"Add (Const i, Const j): ...");
 480            r__ = 1; goto replacement__; }
 481 #line 65 "timespace.pcc"
 482 } break;
 483    }
 484
 485 }
 486
 487 /*
 488 ------------------------------- Statistics -------------------------------
 489 Merge matching rules         = yes
 490 Number of DFA nodes merged   = 0
 491 Number of ifs generated      = 0
 492 Number of switches generated = 1
 493 Number of labels             = 0
 494 Number of gotos              = 0
 495 Adaptive matching            = enabled
 496 Fast string matching         = disabled
 497 Inline downcasts             = enabled
 498 --------------------------------------------------------------------------
 499 */