/*****************************************************************************/
/*                                                                           */
/* File:       "DP_TRANS.C"                                                  */
/* Author:      R. Hammer                                                    */
/* Date:        12-18-89                                                     */
/* Last Change: Mar-07-92                                                    */
/*                                                                           */
/* History:     12-05-91 (Hammer):  Error in d_del_dymin() corrected. A      */
/*                                  multiplication node is to be examined    */
/*                                  for monadic plus signs, too.             */
/*                                                                           */
/* Implementation module for subprograms which act on the working tree by    */
/* transforming its structure.                                               */
/* Feb-01-92 Just : Macro WPRINT_ON and dependend include of                 */
/*                  "DP_UTIL.INC" added.                                     */
/* Mar-07-92 Just : macro 'NEW_PROTO' --> 'LINT_ARGS'                        */
/*                                                                           */
/*****************************************************************************/


/*  #define TRACE_ON  */
/* #define WPRINT_ON */

#include <stdio.h>

#include "impor.t"
#include    "error.h"
#include    "scan.h"
#include    "symtab.h"
#include    "idtab.h"
#include    "blktab.h"
#include    "optab.h"
#include    "bintab.h"
#include    "arrx.h"

#include    "dp_nodes.h"
#include    "dp_alloc.h"
#include    "dp_error.h"
#include "expor.t"
#include    "dp_trans.h"
#include "implemen.t"


#if defined(TRACE_ON) || defined(WPRINT_ON)
#include "dp_util.inc"
#endif


/*----------------------------------------------------*/
/* Prototype declarations of locally used subprograms */
/*----------------------------------------------------*/

#ifdef LINT_ARGS
  static void    d_inst_mminus    ( tNODE *, char      );
  static boolean d_check_Operator ( tNODE *, tNODENAME );
#else
  static void    d_inst_mminus    ();
  static boolean d_check_Operator ();
#endif


/*===========================================================================*/

#ifdef LINT_ARGS
static void d_inst_mminus (tNODE *p, char fdir)
                                                /* Insert Monadic Minus Sign */
                                                /* ---  - -       -----      */
#else
static void d_inst_mminus (p, fdir)
  tNODE    *p;
  char      fdir;   /* Direction to father */
#endif

/*----------------------------------------------------------------------------
 *
 *  1. The procedure inserts a monodic minus node just after the node where 'p'
 *     is pointing to. 'fdir' indicates whether the new monadic minus node is a
 *     left or right child of 'p'.
 *
 *  2. After returning from this procedure 'p' is pointing to the new node.
 *
 *
 *  Example (fdir = 'r'):
 *  ---------------------
 *
 *          father                ===>          father
 *          /   \                               /   \
 *               R    <-- p                          m-    <-- p
 *                                                 /   \
 *                                                      R
 *
 *
 *  I/O - Parameters:
 *  -----------------
 *
 *     Name      |   Type      |   I/O   |   Meaning
 *     ----------|-------------|---------|--------------------------------
 *     p         |   tNODE *   |   I/O   |   Pointer to the actual node
 *     fdir      |   char      |    I    |   Indicates direction to father
 *
 *
 *  Called Routines:
 *  ----------------
 *
 *     Name        |   Short description
 *     ------------|-----------------------------------------------------
 *     d_instnode  |   Insert a work node
 *
 *---------------------------------------------------------------------------*/

{ /* proc d_inst_mminus */
  /*--------------------*/

#ifdef TRACE_ON
  print("Trace 'd_instmminus()'"); printline();
#endif

  p = d_instnode(p,fdir,'r');            /* Insert new node                  */

  p->pos.col = p->right->pos.col;        /* Copy position of right child     */
  p->pos.line = p->right->pos.line;
  p->basetype = p->right->basetype;
  p->structure = p->right->structure;

  p->kind = d_Operator;                  /* Update kind and name for momadic */
  p->namekind = d_direct;                /* minus Operator                   */
  p->name.direct = d_mminus;

} /* proc d_inst_mminus */
  /*--------------------*/


/*===========================================================================*/

#ifdef LINT_ARGS
static boolean d_check_Operator (tNODE *p, tNODENAME opname)
                                                      /* Check Operator Name */
                                                      /* ----- --------      */
#else
static boolean d_check_Operator (p, opname)
  tNODE       *p;
  tNODENAME    opname;
#endif

/*----------------------------------------------------------------------------
 *
 *  The function checks if the node where 'p' is pointing to represents
 *  an Operator with name 'opname'.
 *
 *---------------------------------------------------------------------------*/

{ /* func d_check_Operator */
  /*-----------------------*/

#ifdef TRACE_ON
  print("Trace 'd_check_Operator()'"); printline();
#endif

  return( (p->kind == d_Operator) && (p->name.direct == opname) );

} /* func d_check_Operator */
  /*-----------------------*/


/*===========================================================================*/

#ifdef LINT_ARGS
extern void d_del_dymin (tNODE *p)
                                                /* Delete Dyadic Minus Signs */
                                                /* ---    --     ---         */
#else
extern void d_del_dymin (p)
  tNODE   *p;
#endif

/*----------------------------------------------------------------------------
 *
 *  1. All dyadic minus signs of the working tree will be deleted and will be
 *     replaced by combinations of dyadic plus and monadic minus signs.
 *
 *  2. Monadic plus signs will be deleted.
 *
 *  3. The procedure is implemented recursively.
 *
 *
 *  For deletion of dyadic minus signs or monadic plus signs the following
 *  cases are to be considered:
 *
 *    L   : Left Subtree
 *    R   : Right Subtree
 *    [.] : Call 'del_dymin' recursively, for the (sub-) tree in brackets.
 *
 *    1. Case        m-                             m-         Monadic Minus
 *                 /   \           ===>           /   \
 *                      R                             [R]
 *
 *    2. Case        |                              |          Delete Monadic
 *                   m+                            [R]         Plus
 *                 /   \           ===>
 *                      R
 *
 *    3. Case        -                              +          Dyadic Minus
 *                 /   \           ===>           /   \
 *                L     R                       [L]    m-
 *                                                   /   \
 *                                                       [R]
 *
 *    4. Case        +                              +          Dyadic Plus
 *                 /   \            ===>          /   \
 *                L     R                       [L]   [R]
 *
 *
 *    5. Case       sum             ===>           sum         Summation
 *                /     \                        /     \
 *                       to                             to
 *                     /    \                         /    \
 *                           R                             [R]
 *
 *
 *  I/O - Parameters:
 *  -----------------
 *
 *     Name      |   Type      |   I/O   |   Meaning
 *     ----------|-------------|---------|-----------------------------
 *     p         |   tNODE *   |   I/O   |   Pointer to the root of the
 *               |             |         |   working (sub-) tree.
 *
 *
 *  Called Routines:
 *  ----------------
 *
 *     Name          |   Short description
 *     --------------|-------------------------------------------------
 *     d_extrnode    |   Delete a work node
 *     d_inst_mminus |   Insert a monadic minus work node
 *     d_del_dymin   |   Recursively called
 *
 *---------------------------------------------------------------------------*/

{ postype  save_pos;   /* To store the global position 'pos' */
                       /* when executing code of this module */

  /* proc d_del_dymin */
  /*------------------*/

  /* No Trace information, if TRACE_ON is defined, because of recursive */
  /* implementation !                                                   */
  /*--------------------------------------------------------------------*/

  save_pos = pos;           /* Set 'pos' to the correct position of the */
  pos = p->pos;             /* work node within the source line         */


  if (p->kind == d_Operator)              /* Act only on Operator nodes */
    switch (p->name.direct)
    {
    case d_lpard       :
    case d_lparu       :
    case d_sharp       :
    case d_sharpnext   :
    case d_sharpdown   :
    case d_sharpup     :
    case d_sharpintval :
    case d_mminus      :  /* Monadic Minus or Sharp Operators */
                          /*----------------------------------*/

                          d_del_dymin(p->right);
                          break;

    case d_mplus       :  /* Monadic Plus */
                          /*--------------*/

                          p = d_extrnode(p);
                          d_del_dymin(p);
                          break;

    case d_minus       :  /* Dyadic Minus */
                          /*--------------*/

                          p->name.direct = d_plus;

                          d_del_dymin(p->left);
                          d_inst_mminus(p,'r');
                          d_del_dymin(p->right);
                          break;

    case d_plus        :  /* Dyadic Plus */
                          /*-------------*/

                          d_del_dymin(p->left);
                          d_del_dymin(p->right);
                          break;

    case d_sum         :  /* Summation */
                          /*-----------*/

                          d_del_dymin(p->right->right);
                          break;

    case d_mult        :  /* Multiplication */
                          /*----------------*/

                          /* no dyadic minus sign to delete, because  */
                          /* multiplication of expressions like       */
                          /* (a-b) * (c-d) are not allowed so far.    */
                          /*                                          */
                          /* But there could be a monodic plus sign,  */
                          /* so we have to examine its child trees.   */
                          /*------------------------------------------*/

                          d_del_dymin(p->left);
                          d_del_dymin(p->right);
                          break;

    default            :; /* Implementation error */
                          /*----------------------*/
#ifdef CHECK
                          print("'d_del_dymin()'  ->   implement. error ");
                          printline();
                          print("   error in a case of a switch (No 1)");
                          printline();
                          break;
#endif

    } /* switch, if */

  pos = save_pos;     /* Rebuild global position pointer */

} /* proc d_del_dymin */
  /*------------------*/


/*===========================================================================*/

#ifdef LINT_ARGS
extern void d_push_mminus (tNODE *p)
                                                       /* Push Monadic Minus */
                                                       /* ---- -       ----- */
#else
extern void d_push_mminus (p)
  tNODE   *p;
#endif

/*----------------------------------------------------------------------------
 *
 *  1. This procedure may only be called after a previous call of
 *     'd_del_dymin', i. e. there may be no dyadic minus signs or monadic
 *     plus signs within the tree.
 *
 *  2. Allowed Operator signs are
 *
 *         - sharp Operators
 *         - monadic minus
 *         - dyadic plus
 *         - multiplication
 *         - sum
 *
 *  3. Monadic minus signs will be moved down in the tree just in front of the
 *     tree's summands. I. e. after handling the tree by 'd_push_mminus'
 *     monadic minus signs may only be placed in front of a
 *
 *         -  constant
 *         -  variable
 *         -  function call
 *         -  multiplication sign
 *
 *     After handling the whole working tree with 'd_push_mminus()' there will
 *     be no longer any multiplication node whose factors are negated by a
 *     preceeding monadic minus.
 *
 *  4. A sharp Operator will be skipped.
 *
 *  5. The procedure is implemented recursively.
 *
 *
 *  For pushing monadic minus signs the following cases are to be considered:
 *
 *    L   : Left Subtree
 *    R   : Right Subtree
 *    [.] : Call 'push_mminus' recursively, for the (sub-) tree in brackets.
 *
 *
 *    1. Case (Monadic Minus): According to its right child one of the trans-
 *                             formations displayed below is to be performed.
 *
 *            |             ===>             |                Double monadic
 *            m-                            [R]               minus
 *          /   \
 *               m-
 *             /   \
 *                  R
 *
 *
 *            m-            ===>             +                Monadic minus in
 *          /   \                         /     \             front of dyadic
 *               +                      [m-]    [m-]          plus
 *             /   \                   /   \   /   \
 *            L     R                       L       R
 *
 *
 *            m-            ===>            sum               Monadic minus in
 *          /   \                          /   \              front of sum
 *              sum                            to
 *             /   \                         /    \
 *                  to                            [m-]
 *                /    \                         /    \
 *                      R                              R
 *
 *
 *    2. Case (Dyadic Plus): 'd_push_mminus' is called recursively for both
 *                            childs.
 *
 *            +             ===>             +
 *          /   \                          /   \
 *         L     R                       [L]   [R]
 *
 *
 *
 *    3. Case (Multiplication): 'd_push_mminus' is called recursively for both
 *                               childs for deleting multiple monadic minus
 *                               signs in front of both factors.
 *
 *            *             ===>             *
 *          /   \                          /   \
 *         L     R                       [L]   [R]
 *
 *       Thereafter one or both of the factors may be negated by a monadic
 *       minus sign in front of it. The following transformations are to be
 *       done.
 *                    *            ===>            *           Both factors
 *                 /     \                       /   \         negated
 *                m-      m-                    L     R
 *              /   \   /   \
 *                   L       R
 *
 *
 *       If only one factor is to be negated we look for the father node. If
 *       it is a monadic minus sign, we preceed by transforming as follows
 *
 *                   m-            ===>           *            Father is mon.
 *                 /   \                        /   \          minus and left
 *                      *                      L     R         child negated
 *                    /   \
 *                   m-    R
 *                 /   \
 *                      L
 *
 *
 *                   m-            ===>           *            Father is mon.
 *                 /   \                        /   \          minus and right
 *                      *                      L     R         child negated
 *                    /   \
 *                   L     m-
 *                       /   \
 *                            R
 *
 *       If the father node is not a monadic minus sign, we preceed by
 *       transforming as follows
 *
 *                   *             ===>          m-            Father is not
 *                 /   \                       /   \           a mon. minus
 *                m-    R                           *          and left child
 *              /   \                             /   \        is negated
 *                   L                           L     R
 *
 *
 *                   *             ===>          m-            Father is not
 *                 /   \                       /   \           a mon. minus
 *                L     m-                          *          and right child
 *                    /   \                       /   \        is negated
 *                         R                     L     R
 *
 *
 *    4. Case (Sum Operator): 'd_push_mminus' is called recursively for its
 *                             expression subtree.
 *
 *           sum                            sum
 *          /   \                          /   \
 *               to                             to
 *             /    \                         /    \
 *
 *
 *  I/O - Parameters:
 *  -----------------
 *
 *     Name      |   Type      |   I/O   |   Meaning
 *     ----------|-------------|---------|-----------------------------
 *     p         |   tNODE *   |   I/O   |   Pointer to the root of the
 *               |             |         |   working (sub-) tree.
 *
 *  Called Routines:
 *  ----------------
 *
 *     Name             |   Short description
 *     -----------------|----------------------------------------------
 *     d_extrnode       |   Delete a work node
 *     d_inst_mminus    |   Insert a monadic minus work node
 *     d_check_Operator |   Checking an Operator node
 *     d_push_mminus    |   Recursively called
 *
 *---------------------------------------------------------------------------*/

{ tNODE   *pl, *pr, *q;          /* Help pointers */

  boolean lmminus, rmminus;      /* Flags for indicating negative */
                                 /* left or right factors         */

  postype  save_pos;             /* To store the global position 'pos' */
                                 /* when executing code of this module */

  /* proc d_push_mminus */
  /*--------------------*/

  /* No Trace information, if TRACE_ON is defined, because of recursive */
  /* implementation !                                                   */
  /*--------------------------------------------------------------------*/

  save_pos = pos;           /* Set 'pos' to the correct position of the */
  pos = p->pos;             /* work node within the source line         */


  if (p->kind == d_Operator)              /* Act only on Operator nodes */

    switch (p->name.direct)
    {
    case d_lpard       :
    case d_lparu       :
    case d_sharp       :
    case d_sharpnext   :
    case d_sharpdown   :
    case d_sharpup     :
    case d_sharpintval :

                    /* Sharp Operators */
                    /*-----------------*/

                    d_push_mminus(p->right);
                    break;

    case d_mminus : /* Monadic Minus */
                    /*---------------*/

                    q = p->right;                  /* Examine right child of */
                    if (q->kind == d_Operator)     /* monadic minus          */
                      switch (q->name.direct)
                      {
                      case d_mminus :

                           /* Double Monadic Minus */
                           /*----------------------*/

                           p = d_extrnode(p);
                           p = d_extrnode(p);

                           d_push_mminus(p);
                           break;

                      case d_plus :

                           /* Monadic Minus and Dyadic Plus */
                           /*-------------------------------*/

                           p = d_extrnode(p);

                           d_inst_mminus(p,'l');    /* Insert monadic minus  */
                           d_inst_mminus(p,'r');    /* left and right        */

                           d_push_mminus(p->left);
                           d_push_mminus(p->right);
                           break;

                      case d_mult :

                           /* Monadic Minus and Multiplication */
                           /*----------------------------------*/

                           d_push_mminus(q);
                           break;

                      case d_sum :

                           /* Monadic Minus and Sum Operator */
                           /*--------------------------------*/

                           p = d_extrnode(p);
                           d_inst_mminus(p->right,'r');
                           d_push_mminus(p->right->right);
                           break;

                      default :;

                            /* Implementation Error */
                            /*----------------------*/
#ifdef CHECK
                            print("'d_push_mminus()'  ->  implement. error");
                            printline();
                            print("   error in a case of a switch (No 1)");
                            printline();
                            break;
#endif

                    } /* switch */
                    break;

    case d_plus  :  /* Dyadic Plus */
                    /*-------------*/

                    d_push_mminus(p->left);
                    d_push_mminus(p->right);
                    break;

    case d_mult  :  /* Multiplication */
                    /*----------------*/

                    d_push_mminus(p->left);       /* Delete multiple monadic */
                    d_push_mminus(p->right);      /* minus signs             */

                    pl = p->left; pr = p->right;

                    lmminus = d_check_Operator(pl,d_mminus);    /* Set flags */
                    rmminus = d_check_Operator(pr,d_mminus);

                    if (lmminus && rmminus)             /* Both factors neg. */
                      {                                 /*-------------------*/
                      pl = d_extrnode(pl);
                      pr = d_extrnode(pr);
                      }

                    else if (lmminus && ! rmminus)      /* Left factor neg.  */
                      {                                 /*-------------------*/
                      pl = d_extrnode(pl);
                      q  = p->father;

                      if (d_check_Operator(q,d_mminus))
                        p->father = d_extrnode(p->father);
                      else
                        if (q->left == p)           /* insert mon minus */
                          d_inst_mminus(q,'l');     /* as father node   */
                        else
                          d_inst_mminus(q,'r');
                      }

                    else if (! lmminus && rmminus)      /* Right factor neg. */
                      {                                 /*-------------------*/
                      pr = d_extrnode(pr);
                      q  = p->father;

                      if (d_check_Operator(q,d_mminus))
                        p->father = d_extrnode(p->father);
                      else
                        if (q->left == p)           /* insert mon minus */
                          d_inst_mminus(q,'l');     /* as father node   */
                        else
                          d_inst_mminus(q,'r');
                      }
                    break;

    case d_sum   :  /* Summation */
                    /*-----------*/

                    d_push_mminus(p->right->right);
                    break;

    default      :; /* Implementation error */
                    /*----------------------*/
#ifdef CHECK
                    print("'push_mminus()'  ->   implement. error");
                    printline();
                    print("   error in a case of a switch (No 2) ");
                    printline();
                    break;
#endif

    } /* switch, if */

  pos = save_pos;     /* Rebuild global position pointer */

} /* proc d_push_mminus */
  /*--------------------*/


/*===========================================================================*/

#ifdef LINT_ARGS
extern void d_make_linear_tree (tNODE *p)
                                            /* Make Left-Linear Ordered Tree */
                                            /* ----      ------         ---- */
#else
extern void d_make_linear_tree (p)
  tNODE   *p;
#endif

/*----------------------------------------------------------------------------
 *
 *  1. The input tree will be transformed into a left-linear ordered tree
 *     with respect to plus operations. I. e. after transformation there will
 *     be no plus Operator in the tree which itself has a plus Operator as
 *     right child.
 *
 *  2. Sharp Operators and monadic minus signs will be skipped.
 *
 *  3. The expression tree of a sum Operator will be transformed, too.
 *
 *  4. The algorithm terminates normally if a multiplication, a vriable, a
 *     constant, or a function is reached.
 *
 *  5. The procedure is implemented recursively.
 *
 *
 *  The transformation is performed according to the following scheme:
 *
 *    A, B, C    :  Subtrees
 *    p, q, r, s :  Pointers to subtrees
 *
 *              |                                        |
 *       p ->   +                   ===>          p ->   +
 *            /   \                                    /   \
 *    q ->   A     +   <- r                    r ->   +     C   <- s
 *               /   \                              /   \
 *              B     C   <- s                     B     A   <- q
 *
 *
 *  I/O - Parameters:
 *  -----------------
 *
 *     Name      |   Type      |   I/O   |   Meaning
 *     ----------|-------------|---------|-----------------------------
 *     p         |   tNODE *   |   I/O   |   Pointer to the root of the
 *               |             |         |   working (sub-) tree.
 *
 *  Called Routines:
 *  ----------------
 *
 *     Name               |   Short description
 *     -------------------|----------------------------------------------
 *     d_check_Operator   |   Checking an Operator node
 *     d_make_linear_tree |   Recursively called
 *
 *---------------------------------------------------------------------------*/

{ tNODE *q, *r, *s;      /* Help pointers */

  postype  save_pos;     /* To store the global position 'pos' */
                         /* when executing code of this module */

  /* proc d_make_linear_tree */
  /*-------------------------*/

  /* No Trace information, if TRACE_ON is defined, because of recursive */
  /* implementation !                                                   */
  /*--------------------------------------------------------------------*/

  save_pos = pos;           /* Set 'pos' to the correct position of the */
  pos = p->pos;             /* work node within the source line         */


  if ( p->kind == d_Operator )      /* Act only on dyadic plus or */
                                    /* or sum Operators           */
    switch ( p->name.direct )
    {
    case d_lpard       :
    case d_lparu       :
    case d_mminus      :
    case d_sharp       :
    case d_sharpnext   :
    case d_sharpdown   :
    case d_sharpup     :
    case d_sharpintval :

                     /* Sharp Operators */
                     /*-----------------*/

                     d_make_linear_tree(p->right);
                     break;


    case d_mult   :  /* no action, algorithm */
                     /* terminates normally  */
                     /*----------------------*/

                     return;


    case d_plus   :  /* Dyadic Plus */
                     /*-------------*/

                     r = p->right;   /* After returning from the body of the */
                                     /* following if statement 'r' points    */
                                     /* again to the right child of 'p'      */

                     while ( d_check_Operator(r,d_plus) )
                       {
                         /* If the right child of 'p' is a plus node, then */
                         /* append the right child as new left child       */
                         /*------------------------------------------------*/

                         q = p->left;
                         s = r->right;

                         p->left = r;
                         p->right = s; s->father = p;
                         r->right = q; q->father = r;

                         r = s;       /* 'r' points to right child again */
                       }
                     /* end while */


                     /* The remaining right subtree will transformed */
                     /*----------------------------------------------*/

               d_make_linear_tree(r);


                     /* Transform now the new left child */
                     /*----------------------------------*/

                     d_make_linear_tree(p->left);
                     break;


    case d_sum    :  /* Summation */
                     /*-----------*/

                     d_make_linear_tree(p->right->right);
                     break;


    default       :; /* Implementation error */
                     /*----------------------*/
#ifdef CHECK
                     print("'d_make_linear_tree()'  ->   implement. error");
                     printline();
                     print("   error in a case of a switch (No 1)        ");
                     printline();
                     break;
#endif

    } /* switch, if */

  pos = save_pos;     /* Rebuild global position pointer */

} /* proc d_make_linear_tree */
  /*-------------------------*/
