prop-src/timespace.ph

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file describes the structure of the time and space complexity
   4 //  datatypes.  These datatypes are used to represent time and space
   5 //  complexity in the SETL-like extension language.
   6 //
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #ifndef time_and_space_complexity_h
   9 #define time_and_space_complexity_h
  10
  11 #include "basics.ph"
  12
  13 ///////////////////////////////////////////////////////////////////////////////
  14 //
  15 //  Forward type declaration
  16 //
  17 ///////////////////////////////////////////////////////////////////////////////
  18 class std::ostream;
  19
  20 ///////////////////////////////////////////////////////////////////////////////
  21 //
  22 //  Complexity expression is represented by the datatype Complexity.
  23 //
  24 ///////////////////////////////////////////////////////////////////////////////
  25 datatype Complexity : MEM =
  26      Var      Id                           // variable
  27    | Add      (Complexity, Complexity)     // f(x) + g(x)
  28    | Mul      (Complexity, Complexity)     // f(x) * g(x)
  29    | Div      (Complexity, Complexity)     // f(x) / g(x)
  30    | Power    (Complexity, Complexity)     // f(x) ^ g(x)
  31    | Log      (Complexity)                 // log f(x)
  32    | Const    (double)                     // constant
  33    | BigOh    Complexity                   // O(f(x))
  34    | Omega    Complexity                   // Omega(f(x))
  35    | LittleOh Complexity                   // o(f(x))
  36
  37 ///////////////////////////////////////////////////////////////////////////////
  38 //
  39 //  Time complexity is represented by the datatype Time.
  40 //
  41 ///////////////////////////////////////////////////////////////////////////////
  42 and      Time  : MEM = TIME Complexity
  43
  44 ///////////////////////////////////////////////////////////////////////////////
  45 //
  46 //  Similarly, space complexity is represented by the datatype Space.
  47 //
  48 ///////////////////////////////////////////////////////////////////////////////
  49 and      Space : MEM = SPACE Complexity
  50 ;
  51
  52 ///////////////////////////////////////////////////////////////////////////////
  53 //
  54 //  Pretty printing routines.
  55 //
  56 ///////////////////////////////////////////////////////////////////////////////
  57 extern std::ostream& operator << (std::ostream&, Complexity);
  58 extern std::ostream& operator << (std::ostream&, Time);
  59 extern std::ostream& operator << (std::ostream&, Space);
  60
  61 ///////////////////////////////////////////////////////////////////////////////
  62 //
  63 //  Functions to simplify and manipulate complexity expressions.
  64 //
  65 ///////////////////////////////////////////////////////////////////////////////
  66 extern Complexity simplify (Complexity);
  67
  68 #endif