home *** CD-ROM | disk | FTP | other *** search
/ Troubleshooting Netware Systems / CSTRIAL0196.BIN / attach / pcc / v08n03 / math.exe / ALGED21.ZIP / ALGED.C < prev    next >
C/C++ Source or Header  |  1995-01-26  |  78KB  |  2,876 lines
  1. /*--------------------------------------------------------------------
  2.    Alged:  Algebra Editor
  3.  
  4.    Copyright (c) 1994 John Henckel
  5.    Permission to use, copy, modify, distribute and sell this software
  6.    and its documentation for any purpose is hereby granted without fee,
  7.    provided that the above copyright notice appear in all copies.
  8.  
  9.    Notes;
  10.    This was written using the excellent Borland Turbo C++ 3.0 Compiler.
  11.    One of the concepts that occurs regularly in this program is the clag.
  12.    A clag is a commutative-left-associative-group.  For instance,
  13.    x+y+z is a clag, but x-y-z is not, because SUB doesn't commute.
  14.    And x+(y+z) is not a clag because it is right associative.  Clags are
  15.    either additive or multiplicative.  You can sort, cancel, and combine
  16.    elements of a clag.  You can move numbers to the bottom (front) or
  17.    top (end) of a clag.  You can split and join clags by converting
  18.    MUL and ADD to/from DIV and SUB.  I think most people think in terms
  19.    of clags, though they don't call them that.
  20.  
  21.    Notes:  The following compiler flags are required:
  22.      word alignment off, memory large, signed chars, enums as int.
  23.    These are recommended:  floating point emulation, fast float, 8086 inst.
  24.  
  25.    If you make any enhancements to this code, please comment them well and
  26.    make a note below.  I would appreciate it if you send me your enhancements
  27.    also!  There are a number of utility function you should be aware of,
  28.    look at cons, newoper, newnode, freenode, freetree, debug, dumpnode.
  29.    I added cons just lately so you may see cases where I should have used
  30.    cons but didn't.
  31.  
  32.    Change log:
  33.    12/94 JDH first version       henckel@vnet.ibm.com
  34.    1/95  JDH second version
  35.  
  36. */
  37. #include <stdlib.h>
  38. #include <stdio.h>
  39. #include <string.h>
  40. #include <math.h>
  41. #include <conio.h>
  42. #include <time.h>
  43. #include "mouse.h"
  44. #define xx2
  45. #define MAXP 5
  46. typedef unsigned char uchar;
  47.  
  48. /* Note, the order and spacing of these is very important. see Bisect */
  49.  
  50. enum KIND { EQU,FUN,ADD,SUB,MUL,DIV,EXP,VAR,NUM,BAD };
  51.  
  52.  /* operator precedence (for display only) */
  53. int pr[20]={ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 9 , 9 , 9  };
  54. uchar kname[20][3] =
  55.            {"=","?","+","-","·","/","^","?","?","?" };
  56. uchar piname[10] = {227,0};
  57. uchar ename[10] = "e";
  58. uchar iname[10] = "i";
  59. uchar errname[10] = "BAD";         /* for divide by zero etc */
  60. uchar infname[10] = "INF";
  61. uchar halfname[10] = {171,0};
  62. uchar qtrname[10] = {172,0};
  63. uchar hline = 196;
  64. uchar vline = 179;
  65. uchar urc = 191;
  66. uchar llc = 192;
  67. uchar lrc = 217;
  68. uchar ulc = 218;
  69. uchar comma = ',';
  70.  
  71. #ifndef __IBMC__
  72. extern void _floatconvert();        /* force load float libs */
  73. #pragma extref _floatconvert
  74. #endif
  75.  
  76. /*-----------------------------------------------------------------
  77.    The following is the fundamental data structure for alged.
  78.    >> when you create a new node you need to set kind,nump,parm,
  79.    and name (or value for NUMbers).
  80.    >> tag is used to debug memory problems, if the node is allocated
  81.    then it should be 12345, else it should not be.
  82.    >> sx,sy,px,py,ay are set by the display functions and used by the
  83.    findnode.  name is set for numbers only.
  84.    >> ay is used to adjust the visual appearance of vertically stacked
  85.    operations like EXP and DIV.
  86. */
  87. typedef struct node {
  88.   char name[25];
  89.   int tag;
  90.   double value;
  91.   int sx,sy;       /* size */
  92.   int px,py;      /* location on scrn */
  93.   int ay;         /* adjust y */
  94.   int kind;
  95.   int nump;
  96.   struct node *parm[MAXP],*next;        /* next must be last */
  97. } node;
  98.  
  99. /*-----------------------------------------------------------------
  100.    GLOBAL VARIABLES
  101.  
  102.    There is an array of formulas read from the file.  numform is the
  103.    number of them, curform is the current formula being edited.
  104.    src and tgt are two selected nodes within the curform.
  105. */
  106. node *firf,*curf;
  107. node *src,*tgt;
  108. int sigdig = 13;        /* doubles have at most 16 sig dig. */
  109. double maxrat = 1000;
  110. int bold1=14,bold2=13,norm=7,mcolor=15+16;
  111. int panx=0,pany=0,yadj=1;
  112. int maxpow=100;
  113. int numsee = 0;         /* number of formulas currently visible */
  114. int ch8 = 1;                /* allow 8-bit characters (graphical) */
  115. struct text_info ti;         /* text mode information */
  116.  
  117. enum menui {
  118.     SIM, ASS, PCO, PLY, SBS, ADZ, SUZ, CLR,
  119.     DIS, COD, PRV, QUA, EXX, MUZ, DEL, LOD,
  120.     CAL, CH8, NXT, FAP, EXJ, DIZ, INK, SAV,
  121.     RAT, PPL, PP0, PPR, EQK, EXZ, ENT, WRI, numm };
  122.  
  123. char menu[numm][10] = {
  124.     "Simplify",  "Associate", "Poly Coef", "Poly Div",
  125.     "Substitut", "Add Key",   "Subtr Key", "Erase All",
  126.     "Distribut", "Comm Deno", "Prev",      "FactrQuad",
  127.     "^N expand", "Mult Key ", "DeleteTop", "Load",
  128.     "Calculate", "Char Mode", "Next",      "FactrPoly",
  129.     "Exp Join",  "Div Key ",  "Ins Key",   "Save",
  130.     "Integer",   "<<Left",    "Center",    "Right>>",
  131.     "Equal Key", "Exp Key",   "Enter Key", "Write"  };
  132.                   /*   .              .       .       .       */
  133. char hotkey[numm+1] = " ap\\u+-\x12" "dmHqn*SlcgPfj/RsiKGM=ekw";
  134. int mwidth = 10;             /* max menu item width */
  135. int mheight = 5;           /* see show_menu for calc */
  136. /*--------------------------------------------------------------------
  137.    MACROS
  138. */
  139. #define setmax(x,y) if ((x)<(y)) x=(y)
  140. #define relxy(x,y) gotoxy(wherex()+(x),wherey()+(y))
  141. #define PI 3.14159265358979292
  142. #define E  2.71828182845904509
  143. #define lf parm[0]
  144. #define rt parm[1]
  145. #define pause delay(500)
  146. void debug(node*);
  147. void simplify(node *p);
  148. void twirl(void);
  149. /*-----------------------------------------------------------------
  150.    memory allocation
  151. */
  152. void checknull(void *p) {
  153.   if (!p) {
  154.     printf("\n*********************************************\n");
  155.     printf(  "* Alged Error - heap memory is all used up. *\n");
  156.     printf(  "*********************************************\n");
  157.     delay(2000);
  158.     exit(1);
  159.   }
  160. }
  161.  
  162. node *newnode(void) {
  163.   node *p;
  164.   p = malloc(sizeof *p); checknull(p);
  165.   p->tag = 12345;
  166.   p->nump = 0;
  167.   p->kind = VAR;
  168.   strcpy(p->name,"??");
  169.   return p;
  170. }
  171.  
  172. node *newnum(double val) {
  173.   node *p;
  174.   p = malloc(sizeof *p); checknull(p);
  175.   p->tag = 12345;
  176.   p->nump = 0;
  177.   p->kind = NUM;
  178.   p->value = val;
  179.   return p;
  180. }
  181.  
  182. node *newoper(int kind) {
  183.   node *p;
  184.   p = malloc(sizeof *p); checknull(p);
  185.   p->tag = 12345;
  186.   p->nump = 2;
  187.   p->kind = kind;
  188.   p->lf = p->rt = NULL;
  189.   strcpy(p->name,kname[kind]);
  190.   return p;
  191. }
  192.  
  193. void freenode(node *p) {
  194.   if (!p || p->tag != 12345) {
  195.     printf("Error in freenode");
  196.     pause; return;
  197.   }
  198.   p->tag = 0;
  199.   p->nump = 0;
  200.   p->kind = VAR;
  201.   strcpy(p->name,"FREE");
  202.   free(p);
  203. }
  204.  
  205. void freetree(node *p) {
  206.   int i,n;
  207.   if (!p || p->tag != 12345) {
  208.     printf("Error in freetree");
  209.     pause; return;
  210.   }
  211.   n = p->nump;
  212.   p->tag = 0;
  213.   p->nump = 0;
  214.   p->kind = VAR;
  215.   strcpy(p->name,"FREE");
  216.   for (i=0; i<n; ++i)
  217.     freetree(p->parm[i]);
  218.   free(p);
  219. }
  220.  
  221. /*-----------------------------------------------------------------
  222.    nodecpy, use this to copy one node over another.  The only
  223.    thing is that "next" is preserved to not disrupt the main
  224.    node linked list.
  225. */
  226. void nodecpy(node *a, node *b) {
  227.   node *nx;
  228.   nx = a->next;
  229.   memcpy(a,b,sizeof(*a));
  230.   a->next = nx;
  231. }
  232.  
  233. /*-----------------------------------------------------------------
  234.    set a=b,
  235.    frees a, then copies b into it and frees b.
  236. */
  237. void movenode(node *a, node *b) {
  238.   int i;
  239.   for (i=0; i<a->nump; ++i)
  240.     freetree(a->parm[i]);        /* free children */
  241.   nodecpy(a,b);
  242.   freenode(b);
  243. }
  244.  
  245. /*-----------------------------------------------------------------
  246.    cons  -- create a new node with left,opr,right or if left is
  247.         null, just return right.
  248. */
  249. node *cons(node *left,int opr,node *right) {
  250.   node *a;
  251.   if (!left) return right;       /* empty list */
  252.   a = newoper(opr);
  253.   a->lf = left;
  254.   a->rt = right;
  255.   return a;
  256. }
  257. /*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  258.  
  259.     The following functions are related to the manipulation of
  260.     the algebraic expressions.  They fall roughly into the following
  261.     categories.
  262.       Sorting         b + a    ==>  a + b
  263.       Factoring       ac + ab  ==>  a(c + b)
  264.       Distributing    a(b + c) ==>  ac + ab
  265.       Calculating     b/1      ==>  b
  266.       Collecting      a*a*a    ==>  a^3
  267.       Other
  268. */
  269. /*-----------------------------------------------------------------
  270.    some macros used by simplify
  271. */
  272. #define swingb do { \
  273.       p->rt = b->rt; \
  274.       b->rt = b->lf; \
  275.       b->lf = p->lf; \
  276.       p->lf = b; } while(0)
  277. #define swinga do { \
  278.       p->lf = a->lf; \
  279.       a->lf = a->rt; \
  280.       a->rt = p->rt; \
  281.       p->rt = a; } while(0)
  282. #define aop(x) ((x)==ADD || (x)==SUB)
  283.  
  284. #define whole(x) (fmod((x),1)==0)
  285. /*-----------------------------------------------------------------
  286.    deepcopy a node
  287. */
  288. node *deepcopy(node *p) {
  289.   int j;
  290.   node *t;
  291.   t = newnode();
  292.   nodecpy(t,p);
  293.   for (j=0; j<p->nump; ++j)
  294.     t->parm[j] = deepcopy(p->parm[j]);
  295.   return t;
  296. }
  297.  
  298. /*-----------------------------------------------------------------
  299.    compare two nodes, if they are equal return 1, else 0.
  300. */
  301. int equal(node *p,node *q) {
  302.   int i;
  303.  
  304.   if (p->kind != q->kind) return 0;
  305.   if (p->nump != q->nump) return 0;
  306.   if (p->kind==NUM) return p->value==q->value;
  307.   if (p->kind==VAR) return !strcmp(p->name,q->name);
  308.   if (p->kind==FUN && strcmp(p->name,q->name)) return 0;
  309.  
  310.   for (i=0; i<p->nump; ++i)
  311.     if (!equal(p->parm[i],q->parm[i])) return 0;
  312.  
  313.   return 1;             /* identical */
  314. }
  315.  
  316. /*-----------------------------------------------------------------
  317.    lastnode
  318. */
  319. node *lastnode(node *p) {
  320.   while (p && p->next) p=p->next;
  321.   return p;
  322. }
  323.  
  324. /*-----------------------------------------------------------------
  325.    prevnode
  326. */
  327. node *prevnode(node *p) {
  328.   node *t;
  329.   for (t=firf; t && t->next!=p; ) t=t->next;
  330.   return t;
  331. }
  332.  
  333. /*-----------------------------------------------------------------
  334.    compare two nodes, return -1 if p<q ,0 if p==q ,1 if p>q.
  335.      1. anything < NUM
  336.      2. x < y
  337.      3. x^3 < x^2 < x < y^3
  338.    note: 3 < 2
  339.    other operators have same order as left operand.
  340.    Historical note... this function WAS used for both sorting and
  341.    testing for equality.  However, for maintenance and efficiency
  342.    reasons I found it better to make a separate "equal" function.
  343. */
  344. int cmp(node *p,node *q) {
  345.   int r,i,j,k;
  346.  
  347.   if (p->kind==NUM)                 /* NUMERIC */
  348.     if (q->kind==NUM)
  349.       return p->value==q->value ? 0 :
  350.              p->value < q->value ? 1 : -1;       /* hi to low */
  351.     else return 1;
  352.   else if (q->kind==NUM)
  353.     return -1;
  354.   j = (p->kind==MUL && p->rt->kind==NUM);
  355.   k = (q->kind==MUL && q->rt->kind==NUM);
  356.   if (j && !k) {
  357.     r = cmp(p->lf,q);              /* IGNORE COEFFICIENTS */
  358.     if (r) return r;
  359.     return 1;
  360.   }
  361.   if (k && !j) {
  362.     r = cmp(p,q->lf);
  363.     if (r) return r;
  364.     return -1;
  365.   }
  366.   if (p->kind==VAR) {                 /*  VARIABLES  */
  367.     if (q->kind==VAR)
  368.       return strcmp(p->name,q->name);
  369.     else if (q->nump) {
  370.       r = cmp(p,q->lf);
  371.       if (r) return r;
  372.     }
  373.     return 1;
  374.   }
  375.   else if (q->kind==VAR) {
  376.     if (p->nump) {
  377.       r = cmp(p->lf,q);
  378.       if (r) return r;
  379.     }
  380.     return -1;
  381.   }
  382.   if (p->kind==FUN && q->kind==FUN) {  /* FUNCTIONS */
  383.     r = strcmp(p->name,q->name);
  384.     if (r) return r;
  385.   }
  386.   k = q->kind-p->kind;
  387.   if (!k) k=p->nump-q->nump;
  388.  
  389.   if (!k) {                         /* ARE THEY IDENTICAL? */
  390.     for (i=0; i<p->nump; ++i) {
  391.       r = cmp(p->parm[i],q->parm[i]);
  392.       if (r) return r;
  393.     }
  394.     return 0;             /* identical */
  395.   }
  396.   if (p->nump && q->nump) {           /* DIFFERENT OPERATORS  */
  397.     if (k>0) r = cmp(p->lf,q);
  398.     else     r = cmp(p,q->lf);
  399.     if (r) return r;
  400.   }
  401.   return k;
  402. }
  403.  
  404.  
  405. /*-----------------------------------------------------------------
  406.    sort over operator.  oper = ADD or MUL.
  407.    This uses bubble sort.  It assumes that the nodes have been
  408.    adjusted to left association.  For best results, call bisect
  409.    before calling this.
  410. */
  411. int sortnode(node *p,int oper) {
  412.   int i,r=0;
  413.   node *s,**t;
  414.  
  415.   if (p->kind!=oper) {
  416.     for (i=0; i<p->nump; ++i)
  417.       r+=sortnode(p->parm[i],oper);
  418.     return r;
  419.   }
  420.   while (p->kind==oper) {
  421.     s=p;
  422.     t=p->parm+1;
  423.     while (s->lf->kind==oper) {
  424.       s = s->lf;
  425.       if (cmp(s->rt,*t)>0) t=s->parm+1;
  426.     }
  427.     if (cmp(s->lf,*t)>0) t=s->parm;
  428.     if (*t != p->rt) {             /* too much indirection? */
  429.       s = *t;
  430.       *t = p->rt;
  431.       p->rt = s;
  432.       ++r;
  433.     }
  434.     r+=sortnode(p->rt,oper);
  435.     p = p->lf;
  436.   }
  437.   r+=sortnode(p,oper);
  438.   return r;
  439. }
  440.  
  441. /*-----------------------------------------------------------------
  442.    prime factor - replace a number with prime factors
  443. */
  444. void primefact(node *p) {
  445.   int i;
  446.   double v,f;
  447.  
  448.   for (i=0; i<p->nump; ++i)
  449.     primefact(p->parm[i]);
  450.  
  451.   if (p->kind==NUM && !!(v=fabs(p->value)) && whole(v)) {
  452.     if (p->value<0) {
  453.       p->kind = MUL;
  454.       p->nump = 2;
  455.       p->lf = newnum(v);
  456.       p->rt = newnum(-1);
  457.       p = p->lf;
  458.     }
  459.     for (f=2; f<=maxrat && f<v; ++f)
  460.       if (whole(v/f)) {
  461.         v /= f;
  462.         p->kind = MUL;
  463.         p->nump = 2;
  464.         p->lf = newnum(v);
  465.         p->rt = newnum(f);
  466.         p = p->lf;
  467.         f = 1;         /* start loop at the beginning */
  468.       }
  469.   }
  470. }
  471.  
  472. /*--------------------------------------------------------------------
  473.    rational search - this searches for a denominator to a number.
  474. */
  475. int rational_search(node *p) {
  476.   int i,r=0,s=1;
  477.   static double v,n,x,d,n1,d1,x1;
  478.   double err = pow(10,-sigdig);
  479.  
  480.   twirl();
  481.   if (p->kind==NUM) {
  482.     v = fabs(p->value);
  483.     if (p->value<0) s=-1;        /* sign */
  484.     x = modf(v,&n);
  485.     if (x > err) {              /* v is not already an integer */
  486.       x1=5;
  487.       for (d=2; d<=maxrat; ++d) {
  488.         modf(d*v+0.5,&n);            /* n is the round(d*v) */
  489.         x = fabs(n/d - v);           /* x is the error */
  490.         if (x < x1) {
  491.           n1 = n; d1 = d; x1 = x;
  492.         }
  493.       }
  494.       if (x1 < err) {          /* convert p to a ratio of n/d */
  495.         if (n1==0) {
  496.           p->value = 0;
  497.         }
  498.         else {
  499.           p->kind = DIV;
  500.           p->nump = 2;
  501.           p->lf = newnum(n1*s);
  502.           p->rt = newnum(d1);
  503.         }
  504.         ++r;
  505.       }
  506.     }
  507.     else {                /* throw away the very small part */
  508.       p->value = n*s;
  509.       ++r;
  510.     }
  511.   }
  512.   return r;
  513. }
  514.  
  515.  
  516.  
  517. /*-----------------------------------------------------------------
  518.    reduce a/b to lowest terms (with positive denominator)
  519. */
  520. int reduce(double *a,double *b) {
  521.   int r=0;
  522.   double i;
  523.  
  524.   if (*b<0) { *a=-*a; *b=-*b; }
  525.   for (i=2; i<=maxrat && i<=fabs(*a) && i<=*b; ++i)
  526.     if (whole(*a/i) && whole(*b/i)) {
  527.       *a /= i; *b /= i;
  528.       ++r; i=1;
  529.     }
  530.   return r;
  531. }
  532.  
  533. /*---------------------------------------------------------------------------
  534.    ration - this converts all the numbers to ratios of integers if
  535.             possible.
  536. */
  537. int ration(node *p) {
  538.   static double v,u,h,n1,d1,w9,pf,pp,rp;
  539.   static int m,j,k,w,n,f;
  540.   int i,r=0;
  541.   char s[30];
  542.  
  543.   for (i=0; i<p->nump; ++i)
  544.     r+=ration(p->parm[i]);
  545.  
  546.   if (p->kind==NUM && !whole(p->value)) {
  547.     u = fabs(p->value);
  548.     v = frexp(u,&m);             /* u ==> v * 2**m */
  549.     if (m > 0) {
  550.       n = sigdig - m*log10(2);   /* convert m to base 10 logarithm */
  551.       if (n < 1) {
  552.         modf(p->value,&p->value);  /* truncate to integer */
  553.         return r+1;
  554.       }
  555.       v = modf(u,&h);
  556.       m = 0;
  557.     }
  558.     else {                   /* u is a small number */
  559.       h = 0;
  560.       v = modf(u,&h); m=0;  /* suppress tiny fractions */
  561.       n = sigdig;
  562.     }
  563.     sprintf(s,"%1.18f",v);      /* we know 0 < v < 1 */
  564.     /* Look for repeating pattern in s */
  565.     for (f=0; f<n; ++f) {
  566.       k = n-f-1;
  567.       for (w=1; w<k; ++w) {
  568.         for (i=0; i<w; ++i) {
  569.           for (j=f+i+w; j<n && s[j+2]==s[f+i+2]; ) j+=w;
  570.           if (j<n) break;    /* failed */
  571.         }
  572.         if (i==w) break;   /* success */
  573.       }
  574.       if (w<k) break;   /* success */
  575.     }
  576.     if (w<k) {          /* success */
  577.       s[f+w+2] = 0;
  578.       sscanf(s+f+2,"%lf",&rp);     /* repeating part */
  579.       s[f+2] = 0;
  580.       s[1] = '0';
  581.       sscanf(s+1,"%lf",&pp);       /* prefix part */
  582.       w9 = pow(10,w)-1;           /* w nines */
  583.       pf = pow(10,f);
  584.       n1 = (pf*h + pp)*w9 + rp;
  585.       d1 = w9*pf*pow(2,-m);
  586.       if (p->value<0) n1 = -n1;
  587.       reduce(&n1,&d1);
  588.       if (n1==0) p->value = 0;
  589.       else {
  590.         p->kind = DIV;
  591.         p->nump = 2;
  592.         p->lf = newnum(n1);
  593.         p->rt = newnum(d1);
  594.       }
  595.       ++r;
  596.     }
  597.     else             /* try to convert using the search method */
  598.       r += rational_search(p);
  599.   }
  600.   return r;
  601. }
  602.  
  603. /*--------------------------------------------------------------------
  604.    associate
  605.    rotate the association on add,sub,mul,div
  606.    a+b-c => a-c+b => b+a-c => b-c+a
  607.    note, we make use of the fact that ADD+1 = SUB and ADD is even.
  608. */
  609. void associate(node *p) {
  610.   node *a,*b;
  611.   int opr;
  612.  
  613.   opr = p->kind;
  614.   b = p->rt;
  615.  
  616.   if (opr==DIV && b->kind==MUL) {     /* special handle for bisected */
  617.     p->rt = b->rt;
  618.     b->rt = b->lf;
  619.     b->lf = p->lf;
  620.     p->lf = b;
  621.     b->kind = DIV;
  622.     b = p->rt;
  623.   }
  624.   if (opr==ADD || opr==MUL || opr==SUB || opr==DIV) {
  625.     a = p;
  626.     while ((a->lf->kind|1) == (opr|1)) {
  627.       a->kind = a->lf->kind;
  628.       a->rt = a->lf->rt;
  629.       a = a->lf;
  630.     }
  631.     a->kind = opr;
  632.     if (opr&1) {           /* subtr or divide */
  633.       a->rt = b;
  634.     }
  635.     else {
  636.       a->rt = a->lf;
  637.       a->lf = b;
  638.     }
  639.   }
  640.   else if (opr==EQU) {           /* commute equality */
  641.     p->rt = p->lf;
  642.     p->lf = b;
  643.   }
  644. }
  645.  
  646. /*--------------------------------------------------------------------
  647.    commute
  648.    commute on add,sub,mul,div
  649.    e.g.   a/b ==>  b^(-1)/a^(-1)
  650. */
  651. void commuteNOTUSED(node *p) {
  652.   node *a,*b;
  653.  
  654.   a = p->lf;
  655.   b = p->rt;
  656.   if (p->kind==MUL || p->kind==ADD || p->kind==EQU) {
  657.     p->lf=b; p->rt=a;
  658.   }
  659.   else if (p->kind==DIV || p->kind==SUB) {     /* non-commutative */
  660.     if (a->kind==p->kind+1 &&
  661.         b->kind==p->kind+1 &&
  662.         a->rt->kind==NUM &&
  663.         b->rt->kind==NUM) {              /* has coefficients */
  664.       p->lf=b; p->rt=a;
  665.       a->rt->value = -a->rt->value;
  666.       b->rt->value = -b->rt->value;
  667.     }
  668.     else {                          /* need to make coefficients */
  669.       p->lf = newoper(p->kind+1);
  670.       p->rt = newoper(p->kind+1);
  671.       p->lf->lf = b;
  672.       p->lf->rt = newnum(-1);
  673.       p->rt->lf = a;
  674.       p->rt->rt = newnum(-1);
  675.     }
  676.   }
  677. }
  678.  
  679. /*--------------------------------------------------------------------
  680.       a^x * a^y ==> a^(x+y)
  681.       x^a * y^a ==> (xy)^a
  682. */
  683. int expjoin(node *p) {
  684.   int i,r=0;
  685.   node *a,*b;
  686.  
  687.   for (i=0; i<p->nump; ++i)
  688.     r+=expjoin(p->parm[i]);
  689.  
  690.   a = p->lf;
  691.   b = p->rt;
  692.   if (p->kind==MUL || p->kind==DIV) {
  693.     if (a->kind==EXP && b->kind==EXP &&
  694.         equal(a->lf,b->lf)) {      /*  a^x * a^y = a^(x+y) */
  695.       freetree(a->lf);
  696.       a = a->rt;
  697.       freenode(p->lf);
  698.       b->kind = p->kind-2;
  699.       p->kind = EXP;
  700.       p->lf = b->lf;
  701.       b->lf = a;
  702.     }
  703.     else if (b->kind==EXP &&
  704.         equal(a,b->lf)) {               /*  a * a^y = a^(1+y) */
  705.       freetree(a);
  706.       a = newnum(1);
  707.       b->kind = p->kind-2;
  708.       p->kind = EXP;
  709.       p->lf = b->lf;
  710.       b->lf = a;
  711.     }
  712.     else if (a->kind==EXP &&
  713.              equal(a->lf,b)) {          /*  a^x * a = a^(x+1) */
  714.       freetree(b);
  715.       b = newnum(1);
  716.       a->kind = p->kind-2;
  717.       p->kind = EXP;
  718.       p->lf = a->lf;
  719.       a->lf = a->rt;
  720.       a->rt = b;
  721.       p->rt = a;
  722.     }
  723.     else if (a->kind==EXP && b->kind==EXP &&
  724.         equal(a->rt,b->rt)) {      /*  x^a * y^a = (xy)^a */
  725.       freetree(b->rt);
  726.       p->rt = a->rt;
  727.       a->rt = b->lf;
  728.       freenode(b);
  729.       a->kind = p->kind;
  730.       p->kind = EXP;
  731.     }
  732.     else return r;
  733.     ++r;
  734.   }
  735.   return r;
  736. }
  737.  
  738. /*--------------------------------------------------------------------
  739.    remove sub and div
  740.  
  741.    x/y  =  x*y^-1
  742.    x-y  =  x+y*-1
  743. */
  744. int nosubdiv(node *p) {
  745.   int i,r=0;
  746.   node *a,*b;
  747.  
  748.   for (i=0; i<p->nump; ++i)
  749.     r+=nosubdiv(p->parm[i]);
  750.  
  751.   a = p->lf;
  752.   b = p->rt;
  753.   if (p->kind==SUB || p->kind==DIV) {
  754.     ++r;
  755.     --p->kind;
  756.     if (b->kind==NUM && p->kind==ADD)           /* a-2 = a+(-2) */
  757.        b->value = -b->value;
  758.     else if (b->kind==NUM && !whole(b->value))
  759.        b->value = 1.0/b->value;
  760.     else {
  761.       a = newoper(p->kind+2);    /* MUL or EXP */
  762.       a->lf = b;
  763.       a->rt = newnum(-1);
  764.       p->rt = a;
  765.     }
  766.   }
  767.   return r;
  768. }
  769.  
  770. /*--------------------------------------------------------------------
  771.    bisect node
  772.  
  773.    This converts expressions to canonical form in which
  774.    1. + * are left assoc, ^ is right assoc.
  775.    2. scope of / is increased, e.g. (a/b)*c ==> ac/b,
  776.    3. x+y*-2 is changed to x-y*2
  777.    3' x+(-2) is changed to x-2
  778.    4. x*y^-2 is changed to x/y^2
  779.    4' x*(0.5) is changed to x/2
  780.    5. scope of ^ is reduced
  781.    The name "bisect" means that each MUL clag is broken into two pieces the
  782.    numerator elements and the denominator ones.
  783. */
  784. int bisect(node *p) {
  785.   int i,r=0;
  786.   node *a,*b;
  787.  
  788.   for (i=0; i<p->nump; ++i)
  789.     r+=bisect(p->parm[i]);
  790.  
  791.   a = p->lf;
  792.   b = p->rt;
  793.   switch (p->kind) {
  794.   case ADD:
  795.   case MUL:
  796.     /*--------------------------------------------------------------------
  797.        Add or Multiply
  798.     */
  799.     if (b->kind==p->kind ||              /* a+(b+c) = a+b+c */
  800.         b->kind==p->kind+1) {            /* a+(b-c) = a+b-c */
  801.       swingb;
  802.       i = b->kind;
  803.       b->kind = p->kind;
  804.       p->kind = i;
  805.     }
  806.     else if (p->kind==ADD &&             /* a+(-2) = a-2 */
  807.              b->kind==NUM &&
  808.              b->value < 0) {
  809.       p->kind = SUB;
  810.       b->value = -b->value;
  811.     }
  812.     else if (b->kind==p->kind+2 &&       /* a+b*-2 = a-b*2 */
  813.         b->rt->kind==NUM &&
  814.         b->rt->value < 0) {
  815.       ++p->kind;
  816.       b->rt->value = -b->rt->value;
  817.     }
  818.     /*--------------------------------------------------------------------
  819.        Add only
  820.     */
  821.     else if (p->kind==ADD &&
  822.         aop(b->kind)) {                   /* a+(b-c) = (a+b)-c */
  823.       swingb;
  824.       p->kind = b->kind;
  825.       b->kind = ADD;
  826.     }
  827.     /*--------------------------------------------------------------------
  828.        Multiply only
  829.     */
  830.     else if (p->kind==MUL &&
  831.         a->kind==p->kind+1) {       /* a-b+c = a+c-b */
  832.       p->rt = a->rt;
  833.       a->rt = b;
  834.       ++p->kind;
  835.       --a->kind;
  836.     }
  837.     else if (p->kind==MUL &&
  838.         a->kind==p->kind+2 &&       /* b*-2+a = a-b*2 */
  839.         a->rt->kind==NUM &&
  840.         a->rt->value < 0) {
  841.       ++p->kind;
  842.       p->lf = b;
  843.       p->rt = a;
  844.       a->rt->value = -a->rt->value;
  845.     }
  846.     else break;
  847.     ++r; break;
  848.   case SUB:
  849.   case DIV:
  850.     /*--------------------------------------------------------------------
  851.        Subtract or divide
  852.     */
  853.     if (b->kind==p->kind+1 &&       /* a-b*-2 = a+b*2   NOT NECES. */
  854.         b->rt->kind==NUM &&
  855.         b->rt->value < 0) {
  856.       --p->kind;
  857.       b->rt->value = -b->rt->value;
  858.     }
  859.     /*--------------------------------------------------------------------
  860.        Subtract only
  861.     */
  862.     else if (p->kind==SUB &&             /* a-(-2) = a+2 */
  863.         b->kind==NUM &&
  864.         b->value < 0) {
  865.       p->kind = ADD;
  866.       b->value = -b->value;
  867.     }
  868.     else if (p->kind==SUB &&
  869.          aop(b->kind)) {                   /* a-(b+c) = (a-b)-c */
  870.       swingb;
  871.       p->kind = (ADD+SUB) - b->kind;
  872.       b->kind = SUB;
  873.     }
  874.     /*--------------------------------------------------------------------
  875.        Divide only
  876.     */
  877.     else if (p->kind==DIV &&
  878.         b->kind==p->kind) {             /* a-(b-c) = a+c-b */
  879.       p->lf = b;
  880.       p->rt = b->lf;
  881.       b->lf = a;
  882.       --b->kind;
  883.     }
  884.     else if (p->kind==DIV &&
  885.         a->kind==p->kind) {        /* a-b-c = a-(b+c) */
  886.       swinga;
  887.       --a->kind;
  888.     }
  889.     else break;
  890.     ++r; break;
  891.   case EXP:
  892.     /*--------------------------------------------------------------------
  893.        exponent
  894.     */
  895.     if (a->kind==EXP) {                  /* (x^y)^z = x^(y*z) */
  896.       swinga;
  897.       a->kind = MUL;
  898.     }
  899.     else if (b->kind==NUM &&             /* a^(-2) = 1/a^2 */
  900.              b->value < 0) {
  901.       p->kind = DIV;
  902.       p->lf = newnum(1);
  903.       p->rt = newoper(EXP);
  904.       p->rt->lf = a;
  905.       p->rt->rt = b;
  906.       b->value = -b->value;
  907.     }
  908.     else break;
  909.     ++r; break;
  910.   }
  911.   return r;
  912. }
  913.  
  914. /*--------------------------------------------------------------------
  915.    exponent expand - expand any integer exponents less than 100.
  916. */
  917. int exexpand(node *p) {
  918.   int i,r=0;
  919.   node *a,*b;
  920.  
  921.   for (i=0; i<p->nump; ++i)
  922.     r+=exexpand(p->parm[i]);
  923.  
  924.   a = p->lf;
  925.   b = p->rt;
  926.   if (p->kind==EXP &&
  927.       b->kind==NUM &&           /* a^n = a^(n-1)*a */
  928.       b->value > 1 &&
  929.       b->value <= maxpow &&
  930.       whole(b->value)) {
  931.     if (--b->value == 1) {
  932.       p->lf = deepcopy(a);
  933.       freenode(b);
  934.     }
  935.     else {
  936.       b = newoper(EXP);
  937.       b->lf = deepcopy(a);
  938.       b->rt = p->rt;
  939.       p->lf = b;
  940.     }
  941.     p->rt = a;
  942.     p->kind = MUL;
  943.     ++r;
  944.   }
  945.   return r;
  946. }
  947.  
  948. /*--------------------------------------------------------------------
  949.    ComDeno - find common denominators.
  950. */
  951. int comdeno(node *p) {
  952.   int i,r=0;
  953.   double x;
  954.   node *a,*b,*nu,*de;
  955.  
  956.   for (i=0; i<p->nump; ++i)
  957.     r+=comdeno(p->parm[i]);
  958.  
  959.   a = p->lf;
  960.   b = p->rt;
  961.   if (aop(p->kind) && (a->kind==DIV || b->kind==DIV)) {
  962.     if (a->kind==DIV && b->kind==DIV) {
  963.       if (!equal(a->rt,b->rt)) {     /* a/c + b/d = (ad+bc)/cd */
  964.         a->kind = b->kind = MUL;
  965.         de = b->rt;
  966.         b->rt = a->rt;
  967.         a->rt = de;
  968.         de = newoper(MUL);
  969.         de->lf = deepcopy(b->rt);
  970.         de->rt = deepcopy(a->rt);
  971.       }
  972.       else {                         /* a/x + b/x = (a+b)/x */
  973.         freetree(b->rt);
  974.         de = a->rt;
  975.         a = a->lf;
  976.         b = b->lf;
  977.         freenode(p->lf);
  978.         freenode(p->rt);
  979.       }
  980.     }
  981.     else if (a->kind==DIV) {        /* a/b + c = (a + bc)/b */
  982.       a->kind = MUL;
  983.       de = a->lf;
  984.       a->lf = b;
  985.       b = a;
  986.       a = de;
  987.       de = deepcopy(b->rt);
  988.     }
  989.     else {                        /* a + b/c = (ac + b)/c */
  990.       b->kind = MUL;
  991.       de = b->lf;
  992.       b->lf = a;
  993.       a = b;
  994.       b = de;
  995.       de = deepcopy(a->rt);
  996.     }
  997.     nu = newoper(p->kind);
  998.     nu->lf = a;
  999.     nu->rt = b;
  1000.     p->kind = DIV;
  1001.     p->lf = nu;
  1002.     p->rt = de;
  1003.     ++r;
  1004.   }
  1005.   return r;
  1006. }
  1007.  
  1008. /*-----------------------------------------------------------------
  1009.    distribute2
  1010.  
  1011.    This applies the distributive laws
  1012.    1. division over addition.
  1013. */
  1014. int distribute2(node *p) {
  1015.   node *a,*b,*c;
  1016.   int i,r=0;
  1017.  
  1018.   for (i=0; i<p->nump; ++i)
  1019.     r+=distribute2(p->parm[i]);
  1020.  
  1021.   i=0;
  1022.   c = p->parm[i];
  1023.   if (p->kind==DIV && aop(c->kind)) {
  1024.     b = deepcopy(p->parm[1-i]);
  1025.     a = newoper(p->kind);
  1026.     a->parm[i] = c->parm[1-i];
  1027.     a->parm[1-i] = b;
  1028.     c->parm[1-i] = p->parm[1-i];
  1029.     p->parm[1-i] = a;
  1030.     p->kind = c->kind;
  1031.     c->kind = a->kind;
  1032.     ++r;
  1033.   }
  1034.   return r;
  1035. }
  1036.  
  1037. /*-----------------------------------------------------------------
  1038.    distribute
  1039.  
  1040.    This applies the distributive laws
  1041.    1. multiplication over addition.
  1042.    2. (ab)^2 = a^2*b^2
  1043.    3. x^(a+b) = x^a*x^b
  1044. */
  1045. int distribute(node *p) {
  1046.   node *a,*b,*c;
  1047.   int i,r=0;
  1048.  
  1049.   for (i=0; i<p->nump; ++i)
  1050.     r+=distribute(p->parm[i]);
  1051.  
  1052.   for (i=0; i<2; ++i) {
  1053.     c = p->parm[i];
  1054.     if (p->kind==MUL && aop(c->kind) ||
  1055.         i && p->kind==EXP && aop(c->kind) ||
  1056.         !i && p->kind==EXP && (c->kind==MUL || c->kind==DIV)) {
  1057.       b = deepcopy(p->parm[1-i]);
  1058.       a = newoper(p->kind);
  1059.       a->parm[i] = c->parm[1-i];
  1060.       a->parm[1-i] = b;
  1061.       c->parm[1-i] = p->parm[1-i];
  1062.       p->parm[1-i] = a;
  1063.       p->kind = c->kind;
  1064.       c->kind = a->kind;
  1065.       if (i && a->kind==EXP) p->kind+=2;    /* change ADD to MUL */
  1066.       ++r;
  1067.       break;   /* just to be safe */
  1068.     }
  1069.   }
  1070.   return r;
  1071. }
  1072.  
  1073. /*--------------------------------------------------------------------
  1074.    fixassoc
  1075.      + * are left assoc, ^ is right assoc.
  1076. */
  1077. int fixassoc(node *p) {
  1078.   int i,r=0;
  1079.   node *a,*b;
  1080.  
  1081.   for (i=0; i<p->nump; ++i)
  1082.     r+=fixassoc(p->parm[i]);
  1083.  
  1084.   a = p->lf;
  1085.   b = p->rt;
  1086.   switch (p->kind) {
  1087.   case ADD:
  1088.   case MUL:
  1089.     if (b->kind==p->kind ||              /* a+(b+c) = a+b+c */
  1090.         b->kind==p->kind+1) {            /* a+(b-c) = a+b-c */
  1091.       swingb;
  1092.       i=b->kind; b->kind=p->kind; p->kind=i;
  1093.     }
  1094.     else break;
  1095.     ++r; break;
  1096.   case SUB:
  1097.   case DIV:
  1098.     if (b->kind==p->kind) {             /* a-(b-c) = a-b+c */
  1099.       swingb;
  1100.       --p->kind;
  1101.     }
  1102.     else if (b->kind==p->kind-1) {      /* a-(b+c) = a-b-c */
  1103.       swingb;
  1104.       ++b->kind;
  1105.     }
  1106.     else break;
  1107.     ++r; break;
  1108.   case EXP:
  1109.     if (a->kind==EXP) {                  /* (x^y)^z = x^(y*z) */
  1110.       swinga;
  1111.       a->kind = MUL;
  1112.     }
  1113.     else break;
  1114.     ++r; break;
  1115.   }
  1116.   return r;
  1117. }
  1118.  
  1119. /*--------------------------------------------------------------------
  1120.    Move numbers within clag.
  1121. */
  1122. int movenums(node *p,int up,int oper) {
  1123.   int i,r=0;
  1124.   node *a,*b;
  1125.  
  1126.   for (i=0; i<p->nump; ++i)
  1127.     r+=movenums(p->parm[i],up,oper);
  1128.   if (p->kind!=oper) return r;
  1129.   a = p->lf;
  1130.   b = p->rt;
  1131.   i = 1;
  1132.   if (a->kind!=oper) {
  1133.     a=p; i=0;
  1134.   }
  1135.  
  1136.   if (a->parm[i]->kind==NUM) {
  1137.     if (p->rt->kind==NUM) {           /* combine nums */
  1138.       if (oper==ADD) a->parm[i]->value += p->rt->value;
  1139.       else           a->parm[i]->value *= p->rt->value;
  1140.       a = p->lf;
  1141.       nodecpy(p,a);
  1142.       freenode(a);
  1143.       freenode(b);
  1144.       ++r;
  1145.     }
  1146.     else if (up) {                         /* switch */
  1147.       p->rt = a->parm[i];
  1148.       a->parm[i] = b;
  1149.       ++r;
  1150.     }
  1151.   }
  1152.   else if (b->kind==NUM && !up) {   /* switch */
  1153.     p->rt = a->parm[i];
  1154.     a->parm[i] = b;
  1155.     ++r;
  1156.   }
  1157.   return r;
  1158. }
  1159.  
  1160. /*--------------------------------------------------------------------
  1161.    calcnode
  1162.    calculate as many numeric results as possible
  1163. */
  1164. int calcnode(node *p,int keeprat) {
  1165.   int i,r=0;
  1166.   node *a,*b;
  1167.  
  1168.   for (i=0; i<p->nump; ++i)
  1169.     r+=calcnode(p->parm[i],keeprat);
  1170.  
  1171.   a = p->lf;
  1172.   b = p->rt;
  1173.   switch (p->kind) {
  1174.   case ADD:
  1175.     if (a->kind==NUM && a->value==0) {          /* 0+x = x */
  1176.       nodecpy(p,b);
  1177.       freenode(a); freenode(b);
  1178.     }
  1179.     else if (b->kind==NUM && b->value==0) {     /* x+0 = x */
  1180.       nodecpy(p,a);
  1181.       freenode(a); freenode(b);
  1182.     }
  1183.     else if (a->kind==NUM && b->kind==NUM) {    /* n+n = n */
  1184.       p->kind = NUM;
  1185.       p->nump = 0;
  1186.       p->value = a->value + b->value;
  1187.       freenode(a); freenode(b);
  1188.     }
  1189.     else if (b->kind==MUL &&                   /* a+-1*b = a-b */
  1190.              b->lf->kind==NUM &&
  1191.              b->lf->value==-1) {
  1192.       p->kind = SUB;
  1193.       p->rt = b->rt;
  1194.       freenode(b->lf); freenode(b);
  1195.     }
  1196.     else if (b->kind==MUL &&                   /* a+b*(-1) = a-b */
  1197.              b->rt->kind==NUM &&
  1198.              b->rt->value==-1) {
  1199.       p->kind = SUB;
  1200.       p->rt = b->lf;
  1201.       freenode(b->rt); freenode(b);
  1202.     }
  1203.     else break; ++r;
  1204.     break;
  1205.   case SUB:
  1206.     if (a->kind==NUM && a->value==0) {          /* 0-x = -x */
  1207.       p->kind = MUL;
  1208.       a->value = -1;
  1209.     }
  1210.     else if (a->kind==NUM && b->kind==NUM) {    /* n-n = n */
  1211.       p->kind = NUM;
  1212.       p->nump = 0;
  1213.       p->value = a->value - b->value;
  1214.       freenode(a); freenode(b);
  1215.     }
  1216.     else if (b->kind==NUM && b->value==0) {     /* x-0 = x */
  1217.       nodecpy(p,a);
  1218.       freenode(a); freenode(b);
  1219.     }
  1220.     else break; ++r;
  1221.     break;
  1222.   case MUL:
  1223.     if (a->kind==NUM && b->kind==NUM) {         /* n*n = n */
  1224.       p->kind = NUM;
  1225.       p->nump = 0;
  1226.       p->value = a->value * b->value;
  1227.       freenode(a); freenode(b);
  1228.     }
  1229.     else if (a->kind==NUM && a->value==0) {     /* 0*x = 0 */
  1230.       p->kind = NUM;
  1231.       p->nump = 0;
  1232.       p->value = 0;
  1233.       freenode(a); freetree(b);
  1234.     }
  1235.     else if (b->kind==NUM && b->value==0) {     /* x*0 = 0 */
  1236.       p->kind = NUM;
  1237.       p->nump = 0;
  1238.       p->value = 0;
  1239.       freetree(a); freenode(b);
  1240.     }
  1241.     else if (a->kind==NUM && a->value==1) {     /* 1*x = x */
  1242.       nodecpy(p,b);
  1243.       freenode(a); freenode(b);
  1244.     }
  1245.     else if (b->kind==NUM && b->value==1) {     /* x*1 = x */
  1246.       nodecpy(p,a);
  1247.       freenode(a); freenode(b);
  1248.     }
  1249.     else break; ++r;
  1250.     break;
  1251.   case DIV:
  1252.     if (b->kind==NUM && b->value==0) {          /* x/0 = BAD */
  1253.       p->kind = BAD;
  1254.       p->nump = 0;
  1255.       p->value = 0;
  1256.       freetree(a); freenode(b);
  1257.     }
  1258.     else if (a->kind==NUM && a->value==0) {     /* 0/x = 0 */
  1259.       p->kind = NUM;
  1260.       p->nump = 0;
  1261.       p->value = 0;
  1262.       freenode(a); freetree(b);
  1263.     }
  1264.     else if (b->kind==NUM && b->value==1) {     /* x/1 = x */
  1265.       nodecpy(p,a);
  1266.       freenode(a); freenode(b);
  1267.     }
  1268.     else if (a->kind==NUM && b->kind==NUM) {    /* n/n = n */
  1269.       if (keeprat &&
  1270.           whole(a->value) &&       /* if both int, then reduce */
  1271.           whole(b->value)) {
  1272.         if (!reduce(&a->value,&b->value)) break;
  1273.       }
  1274.       else {
  1275.         p->kind = NUM;
  1276.         p->nump = 0;
  1277.         p->value = a->value / b->value;
  1278.         freenode(a); freenode(b);
  1279.       }
  1280.     }
  1281.     /*-----------------------------------------------------------------
  1282.        the following is called "stretch rule" to accomidate numbers
  1283.        separated by the bisection function.
  1284.     */
  1285.     else if (
  1286.         (a->kind==NUM || a->kind==MUL && a->rt->kind==NUM && !!(a=a->rt)) &&
  1287.         (b->kind==NUM || b->kind==MUL && b->rt->kind==NUM && !!(b=b->rt))) {
  1288.       if (keeprat &&
  1289.           whole(a->value) &&       /* if both int, then reduce */
  1290.           whole(b->value)) {
  1291.         if (!reduce(&a->value,&b->value)) break;
  1292.       }
  1293.       else {
  1294.         a->value = a->value / b->value;
  1295.         b->value = 1.0;
  1296.       }
  1297.     }
  1298.     else break; ++r;
  1299.     break;
  1300.   case EXP:
  1301.     if (b->kind==NUM && b->value==0) {          /* x^0 = 1 */
  1302.       p->kind = NUM;
  1303.       p->nump = 0;
  1304.       p->value = 1;
  1305.       freetree(a); freenode(b);
  1306.     }
  1307.     else if (a->kind==NUM && a->value==1) {     /* 1^x = 1 */
  1308.       p->kind = NUM;
  1309.       p->nump = 0;
  1310.       p->value = 1;
  1311.       freenode(a); freetree(b);
  1312.     }
  1313.     else if (b->kind==NUM && b->value==1) {     /* x^1 = x */
  1314.       nodecpy(p,a);
  1315.       freenode(a); freenode(b);
  1316.     }
  1317.     else if (a->kind==NUM && b->kind==NUM) {    /* n^n = n */
  1318.       if (keeprat && b->value<1 && whole(a->value) &&
  1319.              fabs(a->value) < pow(10,sigdig))
  1320.           break;
  1321.       if (a->value < 0 && !whole(b->value)) {   /* domain error */
  1322.         p->kind = MUL;
  1323.         a->value = pow(-a->value,b->value);
  1324.         b->kind = VAR;
  1325.         strcpy(b->name,"i");                /* imaginary */
  1326.       }
  1327.       else {
  1328.         p->kind = NUM;
  1329.         p->nump = 0;
  1330.         p->value = pow(a->value,b->value);
  1331.         freenode(a); freenode(b);
  1332.       }
  1333.     }
  1334.     else if (a->kind==VAR && !strcmp(a->name,"i") &&      /* i^2 = -1 */
  1335.           b->kind==NUM && (b->value>=2 || b->value<0)) {
  1336.       i=1;
  1337.       while (b->value >= 2) {
  1338.         i *= -1;
  1339.         b->value -= 2;
  1340.       }
  1341.       while (b->value < 0) {
  1342.         i *= -1;
  1343.         b->value += 2;
  1344.       }
  1345.       p->kind = MUL;
  1346.       p->lf = newnum(i);
  1347.       p->rt = newoper(EXP);
  1348.       p->rt->lf = a;
  1349.       p->rt->rt = b;
  1350.     }
  1351.     else break; ++r;
  1352.     break;
  1353.   case FUN:
  1354.     if (p->nump==1 && a->kind==NUM) {
  1355.       if (!strcmp(p->name,"sin")) p->value=sin(a->value);
  1356.       else if (!strcmp(p->name,"cos")) p->value=cos(a->value);
  1357.       else if (!strcmp(p->name,"tan")) p->value=tan(a->value);
  1358.       else if (!strcmp(p->name,"acos")) p->value=acos(a->value);
  1359.       else if (!strcmp(p->name,"asin")) p->value=asin(a->value);
  1360.       else if (!strcmp(p->name,"atan")) p->value=atan(a->value);
  1361.       else if (!strcmp(p->name,"cosh")) p->value=cosh(a->value);
  1362.       else if (!strcmp(p->name,"sinh")) p->value=sinh(a->value);
  1363.       else if (!strcmp(p->name,"tanh")) p->value=tanh(a->value);
  1364.       else if (!strcmp(p->name,"ln")) p->value=log(a->value);
  1365.       else if (!strcmp(p->name,"log")) p->value=log10(a->value);
  1366.       else if (!strcmp(p->name,"abs")) p->value=fabs(a->value);
  1367.       else break;
  1368.       p->kind = NUM;
  1369.       p->nump = 0;
  1370.       freenode(a);
  1371.     }
  1372.     break;
  1373.   }
  1374.   return r;
  1375. }
  1376.  
  1377. /*-----------------------------------------------------------------
  1378.    get term, return p without coefficient
  1379. */
  1380. node *get_term(node *p, int oper, double *r) {
  1381.   *r = 1.0;              /* default coeff */
  1382.   if (p->kind==oper && p->rt->kind==NUM) {
  1383.     *r = p->rt->value;
  1384.     return p->lf;
  1385.   }
  1386.   return p;
  1387. }
  1388. /*--------------------------------------------------------------------
  1389.    Combine all terms with common base within a clag.
  1390. */
  1391. int combine(node *p) {
  1392.   int i,oper,r=0;
  1393.   node *a,*b;
  1394.   node *t1,*t2;
  1395.   double c1,c2;
  1396.  
  1397.   for (i=0; i<p->nump; ++i)
  1398.     r+=combine(p->parm[i]);
  1399.  
  1400.   a = p->lf;
  1401.   b = p->rt;
  1402.   oper = p->kind;
  1403.   if (oper!=ADD && oper!=MUL)          /* not a clag */
  1404.     return r;
  1405.   i = 1;
  1406.   if (a->kind!=oper) {
  1407.     a=p; i=0;
  1408.   }
  1409.  
  1410.   t1 = get_term(a->parm[i],oper+2,&c1);
  1411.   t2 = get_term(b,oper+2,&c2);
  1412.   if (equal(t1,t2)) {            /* same base, combine terms */
  1413.     if (a->parm[i]==t1)
  1414.       freetree(t1);
  1415.     else {                    /* free one of the expressions */
  1416.       freetree(b);
  1417.       b = a->parm[i];
  1418.       t2 = t1;
  1419.     }
  1420.     c2 += c1;
  1421.     if (b==t2) {             /* make room for coeff */
  1422.       b = newoper(oper+2);
  1423.       b->lf = t2;
  1424.       b->rt = newnum(0);
  1425.     }
  1426.     b->rt->value = c2;
  1427.     if (c2==1.0) {            /* remove unit coeff */
  1428.       freenode(b->rt);
  1429.       freenode(b);
  1430.       b = t2;
  1431.     }
  1432.     if (i) {                  /* cleanup... 2 stage */
  1433.       nodecpy(p,a);
  1434.       freenode(a);
  1435.       p->rt = b;
  1436.     }
  1437.     else {                    /* 1 stage */
  1438.       nodecpy(p,b);
  1439.       freenode(b);
  1440.     }
  1441.     ++r;
  1442.   }
  1443.   return r;
  1444. }
  1445.  
  1446. /*-----------------------------------------------------------------
  1447.    make-tree convert a table of coefficients to a node tree.
  1448.    Note
  1449.    the coefficients are REUSED (NOT copied), so don't free them.
  1450. */
  1451. node *maketree(node **coef, int sz, node *base) {
  1452.   int i;
  1453.   node *p,*tmp;
  1454.  
  1455.   p = coef[0];
  1456.   for (i=1; i<sz; ++i) {
  1457.     if (coef[i]->kind==NUM && !coef[i]->value) {
  1458.       freenode(coef[i]);             /* throw away zeros */
  1459.     }
  1460.     else {
  1461.       tmp = p;
  1462.       p = newoper(ADD);
  1463.       p->lf = tmp;
  1464.       p->rt = tmp = newoper(MUL);
  1465.       tmp->lf = coef[i];             /* add coef[i]*base^i */
  1466.       if (i>1) {
  1467.         tmp->rt = newoper(EXP);
  1468.         tmp->rt->lf = deepcopy(base);
  1469.         tmp->rt->rt = newnum(i);
  1470.       }
  1471.       else tmp->rt = deepcopy(base);
  1472.     }
  1473.   }
  1474.   return p;
  1475. }
  1476.  
  1477. /*-----------------------------------------------------------------
  1478.    looks inside 'a' for any expression b or b^N.
  1479.    if found, it changes it to a 1 (ONE) and returns the exponent.
  1480.    Note, if N is not an integer (it's a fraction or expression)
  1481.    then findbase ignores it.
  1482.    When findbase returns 0, then  you can assume 'a' is unchanged.
  1483. */
  1484. int findbase(node *a, node *b) {
  1485.   int i,x=1;
  1486.  
  1487.   if (equal(a,b) ||                         /* any expression */
  1488.       a->kind==EXP && a->rt->kind==NUM &&       /* EXPONENTS */
  1489.       (x = a->rt->value, whole(x)) &&
  1490.       x >=0 && equal(a->lf,b)) {
  1491.     movenode(a,newnum(1));
  1492.     return x;
  1493.   }
  1494.   if (a->kind==MUL) {                     /* recurse on MULTIPLY */
  1495.     x = findbase(a->lf,b);
  1496.     if (x) return x;
  1497.     x = findbase(a->rt,b);
  1498.     return x;
  1499.   }
  1500.   return 0;
  1501. }
  1502.  
  1503. /*-----------------------------------------------------------------
  1504.    add entry to coef table          grow and init table
  1505. */
  1506. #define addcoef(k,a) do {                 \
  1507.   node *tmp;                              \
  1508.   if (sz<=i) {                            \
  1509.     coef = realloc((void*)coef,(i+1)*sizeof*coef);   \
  1510.     for ( ; sz<=i; ++sz)                  \
  1511.       coef[sz] = newnum(0);               \
  1512.   }                                       \
  1513.   tmp = coef[i];                          \
  1514.   coef[i] = newoper(k);                   \
  1515.   coef[i]->lf = tmp;                      \
  1516.   coef[i]->rt = a;                        \
  1517. } while(0)
  1518.  
  1519. /*-----------------------------------------------------------------
  1520.    MAKETABLE convert a tree to a table of coefficients which is indexed
  1521.    by the power of a given base.  For example, a*x^2 + 3*x - b would be
  1522.       0 -> 0 - b
  1523.       1 -> 0 + 3
  1524.       2 -> 0 + a
  1525.    the size returned is the index of the last non-zero coefficient + 1
  1526.    Note:
  1527.    the tree, p, is expected to have correct association.
  1528.    the coefficients always have a leading zero.
  1529.    the tree is not altered or referred to by the table.
  1530.    on return, you are guaranteed that result[i]->kind is one of NUM,
  1531.       ADD, SUB and if it is NUM then it is zero.
  1532. */
  1533. node **maketable(node *base, node *p, int *size) {
  1534.   node *a;
  1535.   int i,sz;
  1536.   node **coef;
  1537.  
  1538.   coef = malloc(sizeof*coef);        /* initial size = 1 */
  1539.   checknull(coef);
  1540.   *coef = newnum(0);
  1541.   sz = 1;
  1542.   a = deepcopy(p);                /* make a working copy */
  1543.   while (1) {
  1544.     i = findbase(a,base);
  1545.     if (!i && aop(a->kind)) {
  1546.       i = findbase(a->rt,base);
  1547.       addcoef(a->kind,a->rt);
  1548.     }
  1549.     else {
  1550.       addcoef(ADD,a);
  1551.       break;
  1552.     }
  1553.     a = a->lf;
  1554.   }
  1555.   *size = sz;
  1556.   return coef;
  1557. }
  1558.  
  1559. /*-----------------------------------------------------------------
  1560.    polynomial long division
  1561.  
  1562.    base is the expression on which the division is done (e.g. x)
  1563.    nm and dn are numerator and denominator
  1564.    returns:
  1565.    a new tree if success, else returns NULL
  1566. */
  1567. node *polydiv(node *base, node *nm, node *dn) {
  1568.   node **num,**den,**quo,**rem;
  1569.   int szn,szd,szq,szr;
  1570.   int i,j;
  1571.   node *tmp,*p;
  1572.  
  1573.   num = maketable(base,nm,&szn);
  1574.   den = maketable(base,dn,&szd);
  1575.  
  1576.   /*  If degree of numerator is less than denominator, or
  1577.       if the denominator does not contain base, then return failure */
  1578.  
  1579.   if (szn < szd || szd < 2) {
  1580.     for (i=0; i<szn; ++i) freetree(num[i]);
  1581.     for (i=0; i<szd; ++i) freetree(den[i]);
  1582.     free(num); free(den);
  1583.     return NULL;
  1584.   }
  1585.   szq = szn-szd+1;
  1586.   quo = malloc(szq*sizeof*quo);
  1587.   checknull(quo);
  1588.   szr = szd-1;
  1589.   rem = malloc(szr*sizeof*rem);
  1590.   checknull(rem);
  1591.  
  1592.   /*  Divide every coefficient by leading coeff in denominator */
  1593.  
  1594.   p = den[szd-1];
  1595.   if (!(p->kind==ADD && p->rt->kind==NUM && p->rt->value==1.0)) {
  1596.     for (i=0; i<szn; ++i) {
  1597.       if (num[i]->kind != NUM) {      twirl();
  1598.         tmp = num[i];
  1599.         num[i] = newoper(DIV);
  1600.         num[i]->lf = tmp;
  1601.         num[i]->rt = deepcopy(p);
  1602.       }
  1603.     }
  1604.     for (i=0; i<szd-1; ++i) {
  1605.       if (den[i]->kind != NUM) {      twirl();
  1606.         tmp = den[i];
  1607.         den[i] = newoper(DIV);
  1608.         den[i]->lf = tmp;
  1609.         den[i]->rt = deepcopy(p);
  1610.       }
  1611.     }
  1612.   }
  1613.  
  1614.   /*  Construct the coefficients of the quotient */
  1615.  
  1616.   for (i=1; i<=szq; ++i) {
  1617.     quo[szq-i] = deepcopy(num[szn-i]);
  1618.     for (j=1; j<i; ++j) if (i-j < szd) {      twirl();
  1619.       tmp = quo[szq-i];
  1620.       quo[szq-i] = newoper(SUB);
  1621.       quo[szq-i]->lf = tmp;
  1622.       quo[szq-i]->rt = tmp = newoper(MUL);
  1623.       tmp->lf = deepcopy(den[szd-i+j-1]);
  1624.       tmp->rt = deepcopy(quo[szq-j]);
  1625.     }
  1626.   }
  1627.  
  1628.   /*  Construct the coefficients of the remainder */
  1629.  
  1630.   for (i=0; i<szr; ++i) {
  1631.     rem[i] = deepcopy(num[i]);
  1632.     for (j=0; j<=i; ++j) if (i-j < szq) {      twirl();
  1633.       tmp = rem[i];
  1634.       rem[i] = newoper(SUB);
  1635.       rem[i]->lf = tmp;
  1636.       rem[i]->rt = tmp = newoper(MUL);
  1637.       tmp->lf = deepcopy(den[j]);
  1638.       tmp->rt = deepcopy(quo[i-j]);
  1639.     }
  1640.   }
  1641.  
  1642.   /*  Convert the quo and rem tables into a node tree */
  1643.  
  1644.   p = newoper(ADD);
  1645.   p->rt = newoper(DIV);
  1646.   p->rt->lf = maketree(rem,szr,base);
  1647.   p->rt->rt = deepcopy(dn);
  1648.   p->lf = maketree(quo,szq,base);
  1649.  
  1650.   /*  Clean up and return */
  1651.  
  1652.   for (i=0; i<szn; ++i) freetree(num[i]);
  1653.   for (i=0; i<szd; ++i) freetree(den[i]);
  1654.   free(num);
  1655.   free(quo);
  1656.   free(rem);
  1657.   free(den);
  1658.   return p;
  1659. }
  1660.  
  1661. /*-----------------------------------------------------------------
  1662.    polycoef - collect the coefficients of a polynomial
  1663. */
  1664. void polycoef(node *base, node *p) {
  1665.   node **coef;
  1666.   int sz;
  1667.   int i;
  1668.  
  1669.   if (!p || !base || p->kind==EQU || base->kind==EQU) return;
  1670.  
  1671.   coef = maketable(base,p,&sz);
  1672.   if (sz < 2) {
  1673.     if (sz) freetree(coef[0]);
  1674.     free(coef);
  1675.     return;
  1676.   }
  1677.   for (i=0; i<sz; ++i)              /* calculate the coefficients */
  1678.     while (calcnode(coef[i],1));
  1679.  
  1680.   movenode(p,maketree(coef,sz,base));     /* replace p */
  1681.   free(coef);
  1682. }
  1683.  
  1684. /*-----------------------------------------------------------------
  1685.    use quadratic equation to factor a degree-2 polynomial
  1686.                                      2                       2
  1687.      2                     b + sqrt(b - 4ac)       b - sqrt(b - 4ac)
  1688.    ax + bx + c  ==>  (ax + -----------------) (x + -----------------)
  1689.                                  2                        2a
  1690. */
  1691. void quadratic(node *base,node *p) {
  1692.   node **coef,*a;
  1693.   int sz;
  1694.   int i;
  1695.  
  1696.   coef = maketable(base,p,&sz);
  1697.  
  1698.   if (sz != 3) {
  1699.     for (i=0; i<sz; ++i) freetree(coef[i]);
  1700.     free(coef);
  1701.     return;
  1702.   }
  1703.  
  1704.   /* Construct the two binomials p = (ax + u)(x + v)  */
  1705.  
  1706.   a = newoper(ADD);
  1707.   a->lf = deepcopy(coef[1]);                     /* b */
  1708.   a->rt = newoper(EXP);
  1709.   a->rt->lf = newoper(SUB);
  1710.   a->rt->lf->lf = newoper(EXP);                  /* b^2 */
  1711.   a->rt->lf->lf->lf = deepcopy(coef[1]);
  1712.   a->rt->lf->lf->rt = newnum(2);
  1713.   a->rt->lf->rt = newoper(MUL);                  /* 4ac */
  1714.   a->rt->lf->rt->lf = newoper(MUL);
  1715.   a->rt->lf->rt->lf->lf = newnum(4);
  1716.   a->rt->lf->rt->lf->rt = deepcopy(coef[2]);
  1717.   a->rt->lf->rt->rt = deepcopy(coef[0]);
  1718.   a->rt->rt = newnum(0.5);
  1719.  
  1720.   movenode(p,newoper(MUL));
  1721.   p->lf = newoper(ADD);
  1722.   p->lf->lf = newoper(MUL);                      /* ax */
  1723.   p->lf->lf->lf = deepcopy(coef[2]);
  1724.   p->lf->lf->rt = deepcopy(base);
  1725.   p->lf->rt = newoper(DIV);
  1726.   p->lf->rt->lf = a;
  1727.   p->lf->rt->rt = newnum(2);
  1728.  
  1729.   p->rt = newoper(ADD);
  1730.   p->rt->lf = deepcopy(base);
  1731.   p->rt->rt = newoper(DIV);
  1732.   p->rt->rt->lf = deepcopy(a);
  1733.   p->rt->rt->lf->kind = SUB;
  1734.   p->rt->rt->rt = newoper(MUL);                  /* 2a */
  1735.   p->rt->rt->rt->lf = newnum(2);
  1736.   p->rt->rt->rt->rt = deepcopy(coef[2]);
  1737.  
  1738.   while(calcnode(p->lf->lf->lf,1));
  1739.   while(calcnode(p->lf->rt,1));
  1740.   while(calcnode(p->rt->rt,1));
  1741.  
  1742.   for (i=0; i<sz; ++i) freetree(coef[i]);
  1743.   free(coef);
  1744. }
  1745.  
  1746. /*-----------------------------------------------------------------
  1747.    next factor, returns the ith factor of an expression.
  1748.    it is a new nodetree.
  1749. */
  1750. node *nextfact(node *p,int i) {
  1751.   int j;
  1752.   double k;
  1753.   if (i<1) return newnum(1);          /* everything has factor 1 */
  1754.   if (p->kind==NUM && (k = fabs(p->value), k<maxrat) && whole(k)) {
  1755.     if (k==1) return NULL;            /* don't return 1 twice */
  1756.     for (j=2; j<maxrat && j*2<=k; ++j)
  1757.       if (fmod(k,j)==0 && !--i)
  1758.         return newnum(j);
  1759.   }
  1760.   else if (p->kind==MUL) {
  1761.     while (i>2 && p->kind==MUL) {
  1762.       p=p->lf; i-=2;
  1763.     }
  1764.     if (i==2 && p->kind==MUL)
  1765.       return deepcopy(p->rt);
  1766.   }
  1767.   if (i==1) return deepcopy(p);
  1768.   return NULL;
  1769. }
  1770.  
  1771. /*-----------------------------------------------------------------
  1772.    check root
  1773.    returns the new quotient on success, else null;
  1774. */
  1775. node *checkroot(node *base, node *p, node *den) {
  1776.   node *ans;
  1777.   twirl();
  1778.   ans = polydiv(base,p,den);
  1779.   if (!ans) return NULL;
  1780.   if (ans->kind==ADD && ans->rt->kind==DIV) {     /* always true!! */
  1781.     while (distribute(ans->rt));
  1782.     simplify(ans->rt);
  1783.     simplify(ans->rt);
  1784.     if (ans->rt->kind==NUM && ans->rt->value==0)    /* success!! */
  1785.       return ans;
  1786.   }
  1787.   freetree(ans);
  1788.   return NULL;
  1789. }
  1790.  
  1791. /*-----------------------------------------------------------------
  1792.    factor a polynomial using rational roots
  1793. */
  1794. void factrpoly(node *base,node *p) {
  1795.   node **coef,*a,*b,*q,*dn,*nm,*r;
  1796.   int sz;
  1797.   int i,j,n;
  1798.  
  1799.   coef = maketable(base,p,&sz);
  1800.   if (sz < 3) {
  1801.     for (i=0; i<sz; ++i) freetree(coef[i]);
  1802.     free(coef);
  1803.     return;
  1804.   }
  1805.  
  1806.   /* For every possible rational root, check it for divisibility  */
  1807.  
  1808.   while (exexpand(coef[0]));
  1809.   while (nosubdiv(coef[0]));
  1810.   while (fixassoc(coef[0]));
  1811.   while (calcnode(coef[0],0));
  1812.   while (calcnode(coef[sz-1],0));
  1813.   nm = deepcopy(p);        /* initialize numerator */
  1814.   n = 2;                   /* n is factor counter */
  1815.   r = NULL;                /* intialize the list of factors */
  1816.   for (i=0; n<sz; ++i) {
  1817.     b = nextfact(coef[sz-1],i);     /* get next factor */
  1818.     if (!b) break;
  1819.     for (j=0; n<sz;) {
  1820.       a = nextfact(coef[0],j);         /* next factor */
  1821.       if (!a) break;
  1822.       /*-----------------------------------------------------------------
  1823.          check roots a/b, -a/b, ia/b, -ia/b
  1824.       */
  1825.       dn = cons(deepcopy(base),SUB,cons(a,DIV,deepcopy(b)));
  1826.       simplify(dn->rt);                /* twice for good luck */
  1827. #define DO_CHECK          \
  1828.       simplify(dn->rt);    \
  1829.       q = checkroot(base,nm,dn); \
  1830.       if (q) {             \
  1831.         r = cons(r,MUL,dn);\
  1832.         freetree(nm);      \
  1833.         nm = q;            \
  1834.         simplify(nm);      \
  1835.         simplify(nm);      \
  1836.         ++n;               \
  1837.         continue;          \
  1838.       }
  1839.       DO_CHECK
  1840.       dn->rt = cons(dn->rt,MUL,newnum(-1));
  1841.       DO_CHECK
  1842.       a = newnode(); a->kind = VAR; strcpy(a->name,"i");
  1843.       dn->rt = cons(dn->rt,MUL,a);
  1844.       DO_CHECK
  1845.       dn->rt = cons(dn->rt,MUL,newnum(-1));
  1846.       DO_CHECK
  1847.       freetree(dn);
  1848.       ++j;
  1849.     }
  1850.     freetree(b);
  1851.   }
  1852.   if (n > 2) {
  1853.     r = cons(r,MUL,nm);
  1854.     movenode(p,r);           /* replace p with r */
  1855.   }
  1856.   for (i=0; i<sz; ++i) freetree(coef[i]);
  1857.   free(coef);
  1858.   return;
  1859. }
  1860.  
  1861. /*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1862.  
  1863.     The following functions relate to displaying expressions on the
  1864.     screen.
  1865. */
  1866.  
  1867. /*-----------------------------------------------------------------
  1868.    twirl - this spins a little status indicator on the bottom
  1869.    of the display to reassure the user in long calculations.
  1870. */
  1871. void twirl(void) {
  1872.   static char c[] = "/-\\|";
  1873.   static int i=0;
  1874.   gotoxy(5,ti.screenheight);
  1875.   putch(c[i]);
  1876.   if (++i > 3) i=0;
  1877. }
  1878. /*--------------------------------------------------------------------
  1879.    debug dump
  1880. */
  1881. void dumpnode(node *p,int tab) {
  1882.   int i;
  1883.   for (i=0; i<tab; ++i) putch(' ');
  1884.   cprintf("%p %d %d (%d %d) %d '%s'\r\n",p,p->kind,p->nump,
  1885.          p->px,p->py,p->sy,p->name);
  1886.   for (i=0; i<p->nump; ++i)
  1887.     dumpnode(p->parm[i],tab+2);
  1888. }
  1889.  
  1890. /*--------------------------------------------------------------------
  1891.    re compute size of each node
  1892. */
  1893. void resize(node *p,int ppr) {
  1894.   double x;
  1895.   int mpr,i;
  1896.   mpr = pr[p->kind];
  1897.   p->ay = 0;
  1898.   switch (p->kind) {
  1899.   case NUM:
  1900.     x = fabs(p->value);
  1901.     p->name[0] = 0;
  1902.     if (p->value<0) strcat(p->name,"-");
  1903.     if (x==PI)       strcat(p->name,piname);
  1904.     else if (x==E)   strcat(p->name,ename);
  1905.     else if (x==HUGE_VAL) strcat(p->name,infname);
  1906.     else if (ch8 && x==0.5) strcat(p->name,halfname);
  1907.     else if (ch8 && x==0.25) strcat(p->name,qtrname);
  1908.     else         sprintf(p->name,"%1.15G",p->value);
  1909.     p->sy=1;
  1910.     p->sx=strlen(p->name);
  1911.     break;
  1912.   case BAD:
  1913.     strcpy(p->name,errname);    /* fall thru */
  1914.   case VAR:
  1915.     p->sy=1;
  1916.     p->sx=strlen(p->name);
  1917.     break;
  1918.   case EQU:
  1919.   case ADD:
  1920.   case SUB:
  1921.     p->sx = 3;
  1922.     if (mpr<ppr) p->sx += 2;         /* parens */
  1923.     resize(p->lf,mpr);
  1924.     resize(p->rt,mpr+1);         /* +1 = a hack */
  1925.     p->sy = max(p->lf->sy,p->rt->sy);
  1926.     p->sx += p->lf->sx + p->rt->sx;
  1927.     strcpy(p->name,kname[p->kind]);
  1928.     break;
  1929.   case MUL:
  1930.     p->sx = 1;
  1931.     if (mpr<ppr) p->sx += 2;         /* parens */
  1932.     resize(p->lf,mpr);
  1933.     resize(p->rt,mpr+1);         /* +1 = a hack */
  1934.     p->sy = max(p->lf->sy,p->rt->sy);
  1935.     p->sx += p->lf->sx + p->rt->sx;
  1936.     strcpy(p->name,kname[p->kind]);
  1937.     break;
  1938.   case DIV:
  1939.     resize(p->lf,1);       /* 1 = div suppresses parens */
  1940.     resize(p->rt,1);
  1941.     p->sx = max(p->lf->sx,p->rt->sx) + 2;
  1942.     p->sy = p->lf->sy + p->rt->sy + 1;
  1943.     p->ay = p->lf->sy - p->rt->sy;
  1944.     if (p->ay <0) p->ay--;
  1945.     p->ay /= 2;
  1946.     if (mpr<ppr) p->sx += 2;         /* parens */
  1947.     strcpy(p->name,kname[p->kind]);
  1948.     break;
  1949.   case EXP:
  1950.     resize(p->lf,mpr+1);
  1951.     resize(p->rt,mpr);
  1952.     p->sx = p->lf->sx + p->rt->sx;
  1953.     p->sy = p->lf->sy + p->rt->sy;
  1954.     p->ay = p->rt->sy - p->lf->sy;
  1955.     if (p->ay >0) p->ay++;
  1956.     p->ay /= 2;
  1957.     if (mpr<ppr) p->sx += 2;         /* parens */
  1958.     strcpy(p->name,kname[p->kind]);
  1959.     break;
  1960.   case FUN:
  1961.     p->sx = strlen(p->name) + 2;    /* 2 parens */
  1962.     p->sy = 0;
  1963.     for (i=0; i<p->nump; ++i) {
  1964.       resize(p->parm[i],mpr);
  1965.       setmax(p->sy,p->parm[i]->sy);
  1966.       p->sx += 1 + p->parm[i]->sx;     /* 1 comma */
  1967.     }
  1968.     break;
  1969.   default:
  1970.     printf("Error in resize");
  1971.     pause;
  1972.   }
  1973. }
  1974. /*--------------------------------------------------------------------
  1975.    leftpar - print a left parenthesis
  1976. */
  1977. void leftpar(int h) {
  1978.   int i;
  1979.   if (h<2) {
  1980.     putch('('); return; }
  1981.   relxy(0,-h/2);
  1982.   putch(ulc);
  1983.   for (i=0; i<h-2; ++i) {
  1984.     relxy(-1,1);
  1985.     putch(vline);
  1986.   }
  1987.   relxy(-1,1);
  1988.   putch(llc);
  1989. }
  1990. /*--------------------------------------------------------------------
  1991.    rightpar - print a right parenthesis
  1992. */
  1993. void rightpar(int h) {
  1994.   int i;
  1995.   if (h<2) {
  1996.     putch(')'); return; }
  1997.   relxy(0,-h/2);
  1998.   putch(urc);
  1999.   for (i=0; i<h-2; ++i) {
  2000.     relxy(-1,1);
  2001.     putch(vline);
  2002.   }
  2003.   relxy(-1,1);
  2004.   putch(lrc);
  2005. }
  2006. /*-----------------------------------------------------------------
  2007.    fix attributes
  2008. */
  2009. int fixattr(node *p) {
  2010.   gettextinfo(&ti);
  2011.   if (p==src) textattr(bold1);
  2012. /*   else if (p==tgt) textattr(bold2);  */
  2013.   return ti.attribute;
  2014. }
  2015.  
  2016. #define seen (x > 0 && x < ti.screenwidth)
  2017.  
  2018. /*--------------------------------------------------------------------
  2019.    print expression
  2020. */
  2021. void show(node *p,int ppr,int x,int y) {
  2022.   int mpr,i,z,s0,s1,attr;
  2023.   mpr = pr[p->kind];
  2024.  
  2025.   if (yadj) y = y + p->ay;           /* adjust y */
  2026.   gotoxy(x,y);
  2027.   attr=fixattr(p);         /* save old attribute */
  2028.  
  2029.   switch (p->kind) {
  2030.   case NUM:
  2031.   case BAD:
  2032.   case VAR:
  2033.     p->px = x; p->py = y;
  2034.     if (seen) cputs(p->name);
  2035.     break;
  2036.   case EQU:
  2037.   case ADD:
  2038.   case SUB:
  2039.     if (mpr<ppr) { if (seen) leftpar(p->sy); ++x; }     /* parens */
  2040.     show(p->lf,mpr,x,y);
  2041.     x += p->lf->sx + 1;
  2042.     gotoxy(x-1,y);
  2043.     fixattr(p);
  2044.     if (seen) cprintf(" %s ",kname[p->kind]);
  2045.     show(p->rt,mpr+1,x+2,y);
  2046.     p->px = x; p->py = y;
  2047.     if (mpr<ppr) {
  2048.       x += 2+p->rt->sx;
  2049.       gotoxy(x,y);
  2050.       fixattr(p);
  2051.       if (seen) rightpar(p->sy);                 /* parens */
  2052.     }
  2053.     break;
  2054.   case MUL:
  2055.     if (mpr<ppr) { if (seen) leftpar(p->sy); ++x; }     /* parens */
  2056.     show(p->lf,mpr,x,y);
  2057.     x += p->lf->sx;
  2058.     gotoxy(x,y);
  2059.     fixattr(p);
  2060.     if (seen) cputs(ch8 ? kname[p->kind] : "*");
  2061.     show(p->rt,mpr+1,x+1,y);
  2062.     p->px = x; p->py = y;
  2063.     if (mpr<ppr) {
  2064.       x += 1+p->rt->sx;
  2065.       gotoxy(x,y);
  2066.       fixattr(p);
  2067.       if (seen) rightpar(p->sy);                 /* parens */
  2068.     }
  2069.     break;
  2070.   case DIV:
  2071.     if (seen) for (i=0; i<p->sx; ++i) {
  2072.       if (x+i < ti.screenwidth) putch(hline);
  2073.     }
  2074.     else if (x<1 && 0<(i=x+p->sx)) {
  2075.       gotoxy(1,y); while (--i) putch(hline);
  2076.     }
  2077.     p->px = x; p->py = y;
  2078.     if (mpr<ppr) {
  2079.       gotoxy(x,y);
  2080.       if (seen) leftpar(p->sy);       /* parens */
  2081.     }
  2082.     show(p->lf,1,x + (p->sx - p->lf->sx)/2,
  2083.                       y - (p->lf->sy + 1)/2);
  2084.     fixattr(p);
  2085.     show(p->rt,1,x + (p->sx - p->rt->sx)/2,
  2086.                       y + (p->rt->sy + 2)/2);
  2087.     if (mpr<ppr) {
  2088.       x+=p->sx-1;
  2089.       gotoxy(x,y);
  2090.       fixattr(p);
  2091.       if (seen) rightpar(p->sy);         /* parens */
  2092.     }
  2093.     break;
  2094.   case EXP:
  2095.     if (mpr<ppr) { if (seen) leftpar(p->sy); ++x; }     /* parens */
  2096.     show(p->rt,mpr  ,x + p->lf->sx,y - (p->rt->sy + 1)/2);
  2097.     fixattr(p);
  2098.     show(p->lf,mpr+1,x,            y + (p->lf->sy + 0)/2);
  2099.     p->px = x + p->lf->sx - 1;
  2100.     p->py = y - 1;
  2101.     if (mpr<ppr) {
  2102.       x += p->sx-2;
  2103.       gotoxy(x,y);
  2104.       fixattr(p);
  2105.       if (seen) rightpar(p->sy);         /* parens */
  2106.     }
  2107.     break;
  2108.   case FUN:
  2109.     p->px = x; p->py = y;
  2110.     if (seen) {
  2111.       cputs(p->name);
  2112.       leftpar(p->sy);
  2113.     }
  2114.     x += strlen(p->name) + 1;
  2115.     for (i=0; ; ) {
  2116.       show(p->parm[i],mpr,x,y);
  2117.       x += p->parm[i]->sx;
  2118.       gotoxy(x,y);
  2119.       fixattr(p);
  2120.       if (++i >= p->nump) break;
  2121.       if (seen) putch(comma);
  2122.       ++x;
  2123.     }
  2124.     if (seen) rightpar(p->sy);         /* parens */
  2125.     break;
  2126.   default:
  2127.     printf("Error in print\n");
  2128.     pause;
  2129.   }
  2130.   textattr(attr);
  2131. }
  2132. /*-----------------------------------------------------------------
  2133.    display menu
  2134. */
  2135. void show_menu(void) {
  2136.   int i,x,y,n;
  2137.   textattr(mcolor);
  2138.   for (i=0; i<numm; ++i) {
  2139.     n = ti.screenwidth / mwidth;
  2140.     x = (i%n)*mwidth+1;
  2141.     y = 1+i/n;
  2142.     gotoxy(x,y);
  2143.     if (x>1) putch(vline); else putch(' ');
  2144.     cputs(menu[i]);
  2145.     for (x=strlen(menu[i])+1; x<mwidth; ++x) putch(' ');
  2146.   }
  2147.   mheight = y+1;         /* number of lines used  by the menu */
  2148.   relxy(-1,0);
  2149.   for (x=wherex(); x>1 && x<=ti.screenwidth; ++x)
  2150.     if (x%mwidth!=1) putch(' '); else putch(vline);
  2151.  
  2152.   /*  MAKE THE BOX AROUND THE FORMULA  */
  2153.   if (ch8) {
  2154.     gotoxy(1,y+1);
  2155.     putch(201);
  2156.     for (i=2; i<ti.screenwidth; ++i) putch(205);
  2157.     putch(187);
  2158.     for (i=y+2; i<ti.screenheight; ++i) {
  2159.       gotoxy(1,i); putch(186); gotoxy(ti.screenwidth,i); putch(186);
  2160.     }
  2161.     gotoxy(1,ti.screenheight);
  2162.     putch(200);
  2163.     for (i=2; i<ti.screenwidth; ++i) putch(205);
  2164.     putch(188);
  2165.   }
  2166. /*  gotoxy(8,ti.screenheight); cprintf(" M=%ld ",farcoreleft()); */
  2167.   gotoxy(ti.screenwidth/2-12,ti.screenheight);
  2168.   cputs(" Algebra Editor 2.1 ");
  2169.   relxy(5,0); cputs(" F1=Help ");
  2170.   relxy(5,0); cputs(" Esc=Quit ");
  2171.  
  2172. }
  2173. /*-----------------------------------------------------------------
  2174.    Check for menu select
  2175. */
  2176. int selection(int x, int y) {
  2177.   int i,n;
  2178.   n = ti.screenwidth / mwidth;
  2179.   for (i=0; i<numm; ++i)
  2180.     if (x <= (i%n+1)*mwidth && y==1+i/n) return i;
  2181.   return -1;
  2182. }
  2183. /*--------------------------------------------------------------------
  2184.    display expressions (as many as possible) starting at p.
  2185. */
  2186. void display(node *p) {
  2187.   int x,y,i,ts=0;
  2188.  
  2189.   if (tgt) {
  2190.     resize(tgt,0);
  2191.     ts = ti.screenheight/2;
  2192.     if (ts > tgt->sy) ts=tgt->sy;
  2193.   }
  2194.   y=mheight+1;
  2195.   numsee = 0;
  2196.   while (p) {
  2197.     resize(p,0);
  2198.     x = (ti.screenwidth-2 - p->sx)/2 + 2 + panx;
  2199.     y += p->sy+1;
  2200.     if (y+ts >= ti.screenheight) break;
  2201.     show(p,0,x,y - (p->sy+1)/2);
  2202.     p = p->next;
  2203.     ++numsee;
  2204.   }
  2205.   if (!p && y+ts+1 < ti.screenheight) {          /* end of list */
  2206.     gotoxy(ti.screenwidth/2-6,y+1);
  2207.     cputs("(end of list)");
  2208.   }
  2209.   if (ts) {
  2210.     x = (ti.screenwidth-2 - tgt->sx)/2 + 2 + panx;
  2211.     y = ti.screenheight - ts + tgt->sy/2;
  2212.     show(tgt,0,x,y);
  2213.     textattr(mcolor);
  2214.     gotoxy(2,ti.screenheight-ts-1);
  2215.     for (i=2; i<ti.screenwidth; ++i) putch(hline);
  2216.     gotoxy(4,ti.screenheight-ts-1);
  2217.     cputs("KEY");
  2218.     textattr(norm);
  2219.   }
  2220. }
  2221.  
  2222. /*--------------------------------------------------------------------
  2223.    debug print out
  2224. */
  2225. void debug(node *p)  {
  2226.   int x,y;
  2227.   clrscr();
  2228.   resize(p,0);
  2229.   x = (ti.screenwidth-2 - p->sx)/2 + 2 + panx;
  2230.   y = ti.screenheight/2;
  2231.   show(p,0,x,y);
  2232.   getch();
  2233. }
  2234. /*-----------------------------------------------------------------
  2235.    Simplify
  2236.    This function converts a rational expression to normal form.
  2237.    Some of the attributes of normal form: no negative exponents,
  2238.    terms are sorted over mul and add.
  2239.    The first movenums pushes all numbers to the left so that
  2240.    when the sortnode runs it pushes them to the right and combines
  2241.    them.
  2242. */
  2243. void simplify(node *p)
  2244. {
  2245.   while (calcnode(p,1));
  2246.   while (fixassoc(p));
  2247.   while (nosubdiv(p));
  2248.   while (fixassoc(p));
  2249.   while (movenums(p,0,MUL));
  2250.   sortnode(p,MUL);
  2251.   while (movenums(p,0,ADD));
  2252.   sortnode(p,ADD);
  2253.   while (combine(p));
  2254.   while (calcnode(p,1));
  2255.   sortnode(p,MUL);
  2256.   sortnode(p,ADD);
  2257.   while (bisect(p));
  2258.   while (calcnode(p,1));         /* use stretch rule to reduce */
  2259.   while (movenums(p,0,MUL));
  2260. }
  2261.  
  2262. /*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2263.  
  2264.     The following functions relate to reading and writing data files.
  2265. */
  2266. /*--------------------------------------------------------------------
  2267.    load a sample expression
  2268. */
  2269. #define push(tt) tt->next = tos; tos = tt
  2270. #define pop(tt) tt=tos; \
  2271.    if (!tos) printf("stack underflow!\n"); else tos=tos->next
  2272.  
  2273. node *load(char *filename) {
  2274.   FILE *f;
  2275.   static char tok[80];
  2276.   node *tos,*p;
  2277.   int i;
  2278.   double t;
  2279.  
  2280.   f = fopen(filename,"r");
  2281.   if (f==NULL) {
  2282.     printf("unable to open %s for read\n",filename);
  2283.     pause;
  2284.     return NULL;
  2285.   }
  2286.   tos = NULL;
  2287.   while (1) {
  2288.     if (1 != fscanf(f,"%24s",tok)) break;
  2289.     if (tok[0]==';') {
  2290.       fgets(tok,sizeof tok,f);
  2291.       continue;
  2292.     }
  2293.     if (*tok=='?') {            /* --- Options ---- */
  2294.       switch (tok[1]) {
  2295.       case 's': fscanf(f,"%d",&bold1); break;
  2296.       case 'c': fscanf(f,"%d",&norm); break;
  2297.       case 'm': fscanf(f,"%d",&mcolor); break;
  2298.       case 'e': fscanf(f,"%d",&sigdig); break;
  2299.       case 'd': fscanf(f,"%lg",&maxrat); break;
  2300.       case 'p': fscanf(f,"%d",&maxpow); break;
  2301.       case 'a': fscanf(f,"%d",&ch8); break;
  2302.       case 'v': fscanf(f,"%d",&i); directvideo=(i>0); break;
  2303.       case 'y': fscanf(f,"%d",&yadj); break;
  2304.       }
  2305.       continue;
  2306.     }
  2307.     if (*tok=='*') {        /* ------------------ */
  2308.       p = newoper(MUL);
  2309.       pop(p->rt);
  2310.       pop(p->lf);
  2311.       push(p);
  2312.     }
  2313.     else if (*tok=='=') {        /* ------------------ */
  2314.       p = newoper(EQU);
  2315.       pop(p->rt);
  2316.       pop(p->lf);
  2317.       push(p);
  2318.     }
  2319.     else if (*tok=='+') {        /* ------------------ */
  2320.       p = newoper(ADD);
  2321.       pop(p->rt);
  2322.       pop(p->lf);
  2323.       push(p);
  2324.     }
  2325.     else if (*tok=='-' && !tok[1]) { /* ------------------ */
  2326.       p = newoper(SUB);
  2327.       pop(p->rt);
  2328.       pop(p->lf);
  2329.       push(p);
  2330.     }
  2331.     else if (*tok=='/') {         /* ------------------ */
  2332.       p = newoper(DIV);
  2333.       pop(p->rt);
  2334.       pop(p->lf);
  2335.       push(p);
  2336.     }
  2337.     else if (*tok=='^') {         /* ------------------ */
  2338.       p = newoper(EXP);
  2339.       pop(p->rt);
  2340.       pop(p->lf);
  2341.       push(p);
  2342.     }
  2343.     else if (*tok=='@') {         /* ------------------ */
  2344.       pop(p);
  2345.       if (p->kind != NUM) printf("missing function arity %s.\n",tok);
  2346.       strcpy(p->name,tok+1);
  2347.       p->kind = FUN;
  2348.       p->nump = p->value;
  2349.       if (p->nump < 0) printf("too few args to %s.\n",tok);
  2350.       if (p->nump >= MAXP) printf("too many args to %s.\n",tok);
  2351.       for (i=p->nump; i--; ) {
  2352.         pop(p->parm[i]);
  2353.       }
  2354.       push(p);
  2355.     }
  2356.     else if (*tok<='9' && *tok>='0' || *tok=='.' || *tok=='-') {
  2357.       sscanf(tok,"%lg",&t);
  2358.       p = newnum(t);
  2359.       push(p);
  2360.     }
  2361.     else {           /* non-operator, non-numeric */
  2362.       p = newnode();
  2363.       strcpy(p->name,tok);
  2364.       p->kind = VAR;
  2365.       p->nump = 0;
  2366.       push(p);
  2367.     }
  2368.   }
  2369.   fclose(f);
  2370.   return tos;
  2371. }
  2372.  
  2373. /*-----------------------------------------------------------------
  2374.    reverse the node list
  2375. */
  2376. node *reverse(node *b) {
  2377.   node *a,*c;
  2378.   a = NULL;
  2379.   while (b) {
  2380.     c = b->next;
  2381.     b->next = a;
  2382.     a = b;
  2383.     b = c;
  2384.   }
  2385.   return a;
  2386. }
  2387.  
  2388. /*-----------------------------------------------------------------
  2389.    loadfile
  2390. */
  2391. void loadfile(char *fn) {
  2392.   if (firf) lastnode(firf)->next = reverse(load(fn));
  2393.   else curf = firf = reverse(load(fn));
  2394. }
  2395. /*-----------------------------------------------------------------
  2396.    fprinttree
  2397. */
  2398. void fprinttree(FILE *f,node *p) {
  2399.   int i;
  2400.  
  2401.   for (i=0; i<p->nump; ++i)
  2402.     fprinttree(f,p->parm[i]);
  2403.  
  2404.   switch (p->kind) {
  2405.     case NUM: fprintf(f," %1.15g",p->value); break;
  2406.     case EQU: fprintf(f," ="); break;
  2407.     case FUN: fprintf(f," %d @%s",p->nump,p->name); break;
  2408.     case ADD: fprintf(f," +"); break;
  2409.     case SUB: fprintf(f," -"); break;
  2410.     case MUL: fprintf(f," *"); break;
  2411.     case DIV: fprintf(f," /"); break;
  2412.     case EXP: fprintf(f," ^"); break;
  2413.     case VAR: fprintf(f," %s",p->name); break;
  2414.     default: fprintf(f," ???"); break;
  2415.   }
  2416. }
  2417. /*-----------------------------------------------------------------
  2418.    savefile
  2419. */
  2420. void savefile(char *fn) {
  2421.   node *p;
  2422.   FILE *f;
  2423.   time_t t;
  2424.  
  2425.   f = fopen(fn,"w");
  2426.   if (!f) {
  2427.     printf("Unable to open %s for output\n",fn);
  2428.     pause;  return;
  2429.   }
  2430.   time(&t);
  2431.   fprintf(f,";\n;  Saved as %s on %s;\n",fn,ctime(&t));
  2432.   p = firf;
  2433.   while (p) {
  2434.     fprinttree(f,p);
  2435.     fprintf(f,"\n;\n");
  2436.     p = p->next;
  2437.   }
  2438.   fclose(f);
  2439. }
  2440.  
  2441. /*-----------------------------------------------------------------
  2442.    fwritetree           = f + - * / ^ V N
  2443.    precedence values:   0 0 2 2 4 4 6 8 8
  2444. */
  2445. int wpr[10] = { 0, 8, 2, 2, 4, 4, 6, 8, 8, 8 };
  2446.  
  2447. void fwritetree(FILE *f,node *p,int pr) {
  2448.   int i;
  2449.  
  2450.   if (pr > wpr[p->kind]) fprintf(f,"(");
  2451.   switch (p->kind) {
  2452.     case NUM: fprintf(f,"%1.15G",p->value); break;
  2453.     case EQU:
  2454.       fwritetree(f,p->lf,0);
  2455.       fprintf(f," = ");
  2456.       fwritetree(f,p->rt,0); break;
  2457.     case FUN:
  2458.       fprintf(f,"%s(",p->name);
  2459.       for (i=0; i<p->nump; ++i) {
  2460.         fwritetree(f,p->parm[i],0);
  2461.         if (i<p->nump-1) fprintf(f,",");
  2462.       }
  2463.       fprintf(f,")");
  2464.       break;
  2465.     case ADD:
  2466.       fwritetree(f,p->lf,2);
  2467.       fprintf(f," + ");
  2468.       fwritetree(f,p->rt,3); break;
  2469.     case SUB:
  2470.       fwritetree(f,p->lf,2);
  2471.       fprintf(f," - ");
  2472.       fwritetree(f,p->rt,3); break;
  2473.     case MUL:
  2474.       fwritetree(f,p->lf,4);
  2475.       fprintf(f,"*");
  2476.       fwritetree(f,p->rt,5); break;
  2477.     case DIV:
  2478.       fwritetree(f,p->lf,4);
  2479.       fprintf(f,"/");
  2480.       fwritetree(f,p->rt,5); break;
  2481.     case EXP:
  2482.       fwritetree(f,p->lf,7);
  2483.       fprintf(f,"^");
  2484.       fwritetree(f,p->rt,6); break;
  2485.     case VAR: fprintf(f,"%s",p->name); break;
  2486.     default: fprintf(f,"???"); break;
  2487.   }
  2488.   if (pr > wpr[p->kind]) fprintf(f,")");
  2489. }
  2490. /*-----------------------------------------------------------------
  2491.    writefile  this writes the file using infix notation.
  2492. */
  2493. void writefile(char *fn) {
  2494.   node *p;
  2495.   FILE *f;
  2496.   time_t t;
  2497.  
  2498.   f = fopen(fn,"w");
  2499.   if (!f) {
  2500.     printf("Unable to open %s for output\n",fn);
  2501.     pause;  return;
  2502.   }
  2503.   time(&t);
  2504.   fprintf(f,";\n;  Written as %s on %s;\n",fn,ctime(&t));
  2505.   p = firf;
  2506.   while (p) {
  2507.     fwritetree(f,p,0);
  2508.     fprintf(f,"\n");
  2509.     p = p->next;
  2510.   }
  2511.   fclose(f);
  2512. }
  2513.  
  2514. /*-----------------------------------------------------------------
  2515.    which node is pointed to?
  2516. */
  2517. node *find_node(node *p,int x,int y) {
  2518.   int i; node *t;
  2519.   switch (p->kind) {
  2520.   case ADD:  case MUL:  case EQU:
  2521.   case EXP:  case SUB:
  2522.     if (x == p->px && y==p->py) {
  2523.       return p;
  2524.     }
  2525.     break;
  2526.   case DIV:
  2527.     if (x >= p->px && y==p->py &&
  2528.         x < (p->px+p->sx)) {
  2529.       return p;
  2530.     }
  2531.     break;
  2532.   default:
  2533.     if (x >= p->px && y==p->py &&
  2534.         x < (p->px + p->sx)) {
  2535.       return p;
  2536.     }
  2537.   }
  2538.   for (i=0; i<p->nump; ++i)
  2539.     if (!!(t=find_node(p->parm[i],x,y))) return t;
  2540.   return NULL;
  2541. }
  2542.  
  2543. /*-----------------------------------------------------------------
  2544.    substitute -- prereq tgt MUST be an EQU.
  2545. */
  2546. void substitution(node *p) {
  2547.   int i;
  2548.   if (equal(p,tgt->lf))
  2549.     movenode(p,deepcopy(tgt->rt));
  2550.   else for (i=0; i<p->nump; ++i)
  2551.     substitution(p->parm[i]);
  2552. }
  2553.  
  2554.  
  2555. /*-----------------------------------------------------------------
  2556.    insert key
  2557.    has special handling for equations...
  2558. */
  2559. void insertkey(int opr) {
  2560.   node *tmp,*t1,*t2;
  2561.  
  2562.   if (!src || !tgt) return;
  2563.   if (tgt->kind==EQU) {
  2564.     t1 = tgt->lf; t2 = tgt->rt;
  2565.   } else t1 = t2 = tgt;
  2566.  
  2567.   if (src->kind==EQU) {
  2568.     tmp = src->lf;
  2569.     src->lf = newoper(opr);
  2570.     src->lf->lf = tmp;
  2571.     src->lf->rt = deepcopy(t1);
  2572.     tmp = src->rt;
  2573.     src->rt = newoper(opr);
  2574.     src->rt->lf = tmp;
  2575.     src->rt->rt = deepcopy(t2);
  2576.     src->rt->lf = tmp;
  2577.   }
  2578.   else if (opr==EXP) {
  2579.     tmp = newnode();
  2580.     nodecpy(tmp,src);
  2581.     src->kind = EXP;
  2582.     src->nump = 2;
  2583.     src->lf = cons(tmp,EXP,deepcopy(t1));
  2584.     src->rt = cons(newnum(1),DIV,deepcopy(t2));
  2585.     src = src->lf;
  2586.   }
  2587.   else {
  2588.     tmp = newnode();
  2589.     nodecpy(tmp,src);
  2590.     src->kind = opr ^ 1;
  2591.     src->nump = 2;
  2592.     src->lf = newoper(opr);
  2593.     src->rt = deepcopy(t2);
  2594.     src = src->lf;
  2595.     src->lf = tmp;
  2596.     src->rt = deepcopy(t1);
  2597.   }
  2598. }
  2599.  
  2600. /*-----------------------------------------------------------------
  2601.    prompt the user for oneline input
  2602.    return value is non-reuseable!
  2603. */
  2604. char *keyin(char *pmt) {
  2605.   static char buf[160];
  2606.   window(1,ti.screenheight-4,ti.screenwidth-1,ti.screenheight-1);
  2607.   textattr(norm);
  2608.   clrscr();
  2609.   cputs(pmt);
  2610.   cputs("\r\n");
  2611.   buf[0] = sizeof buf - 2;
  2612.   cgets(buf);
  2613.   window(1,1,ti.screenwidth,ti.screenheight);
  2614.   return buf+2;
  2615. }
  2616.  
  2617. /*-----------------------------------------------------------------
  2618.    show help file
  2619. */
  2620. void showhelp(char *argv0) {
  2621.   FILE *f;
  2622.   int i,c=0;
  2623.   static char s[85];
  2624.  
  2625.   strcpy(argv0+strlen(argv0)-3,"HLP");
  2626.   f = fopen(argv0,"r");
  2627.   if (!f) { printf("Unable to find help file '%s'\n",argv0);
  2628.     pause; return;
  2629.   }
  2630.   textattr(norm);
  2631.   clrscr();
  2632.   i = ti.screenheight-1;
  2633.   while (!feof(f)) {
  2634.     printf(fgets(s,80,f));
  2635.     if (!--i) {
  2636.       i = ti.screenheight-4;
  2637.       while (!(c=getch()));
  2638.       if (c==27) break;
  2639.     }
  2640.   }
  2641.   if (c!=27) getch();
  2642.   fclose(f);
  2643. }
  2644.  
  2645. /*--------------------------------------------------------------------
  2646.    main
  2647. */
  2648. void main(int argc,char *argv[]) {
  2649.   int i,x,y,b,done=0,dmp=0,mous=1;
  2650.   node *tmp,*p;
  2651.  
  2652.   directvideo = 1;          /* don't use bios */
  2653.   _wscroll = 0;            /* disable scrolling */
  2654.  
  2655.   gettextinfo(&ti);
  2656.  
  2657.   printf("ALGED: Algebra Editor by John Henckel, ver "__DATE__"\n\n");
  2658.   printf("Copyright (c) 1994 by John Henckel.\n");
  2659.   printf("Permission to use, copy, modify, distribute and sell this software\n");
  2660.   printf("and its documentation for any purpose is hereby granted without fee,\n");
  2661.   printf("provided that the above copyright notice appear in all copies.\n");
  2662.  
  2663.   /*-----------------------------------------------------------------
  2664.      init mouse
  2665.   */
  2666.   if (init_mouse() != -1) {
  2667.     printf("mouse driver not found\n");
  2668.     mous=0;
  2669.   }
  2670.   /*-----------------------------------------------------------------
  2671.      load data files
  2672.   */
  2673.   firf = NULL;
  2674.   loadfile("ALGED.1ST");
  2675.   for (i=1; i<argc; ++i)
  2676.     loadfile(argv[i]);
  2677.   curf = firf;
  2678.   /*-----------------------------------------------------------------
  2679.      main loop
  2680.   */
  2681.   src = curf;
  2682.   while (!done) {
  2683.     window(2,mheight+1,ti.screenwidth-1,ti.screenheight-1);
  2684.     textattr(norm);
  2685.     clrscr();
  2686.     window(1,1,ti.screenwidth,ti.screenheight);   /* full */
  2687.     display(curf);
  2688.     if (dmp && src) {
  2689.       putch('\r'); putch('\n');
  2690.       dumpnode(src,1);
  2691.     }
  2692.     show_menu();
  2693.     _setcursortype(_NOCURSOR);
  2694.     if (mous) show_mouse();
  2695.     if (mous) while (!!(b = get_mouse(&x,&y)));
  2696.     while (!mous || !(b = get_mouse(&x,&y)))
  2697.       if (kbhit()) {
  2698.         while (!(b = getch()));
  2699.         break;
  2700.       }
  2701.     if (mous) hide_mouse();
  2702.     _setcursortype(_NORMALCURSOR);
  2703.     /*-----------------------------------------------------------------
  2704.        check for keypresses
  2705.     */
  2706.     i=100;                    /* default = do nothing */
  2707.     if (b==27) break;        /* escape */
  2708.     else if (b==';') i=99;     /* help */
  2709.     else if (b=='v' && src) primefact(src);
  2710.     else if (b=='.' && src) {         /* copy pick to key */
  2711.       p = deepcopy(src);
  2712.       if (tgt) freetree(tgt);
  2713.       tgt = p;
  2714.     }
  2715.     else if (b==73) src=curf;     /* pgup = pick top */
  2716.     else if (b==79 && src && src->nump>1)        /* end = pick lf */
  2717.       src = src->lf;
  2718.     else if (b==81 && src && src->nump>1)      /* pgdn = pick rt */
  2719.       src = src->rt;
  2720.     else if (b > 7) {
  2721.       for (i=0; i<numm; ++i)
  2722.         if (hotkey[i]==b) break;
  2723.       if (i==numm) continue;     /* invalid key */
  2724.     }
  2725.     else {                /* mouse click */
  2726.       x=x/8+1; y=y/8+1;
  2727.       i = selection(x,y);
  2728.     }
  2729.     if (i>=0) {
  2730.       switch (i) {
  2731.       case 99: showhelp(argv[0]); break;
  2732.       case EQK:
  2733.         if (src && tgt && src->kind!=EQU && tgt->kind!=EQU) {
  2734.           tmp = newoper(EQU);
  2735.           tmp->lf = tgt;
  2736.           tmp->rt = deepcopy(src);
  2737.           tgt = tmp;
  2738.         }
  2739.         break;
  2740.       case DIS: if (src) while(distribute(src)); break;
  2741.       case CAL:
  2742.         if (src && (b==1||b=='c')) {
  2743.           while(movenums(src,1,MUL));    /* move up for stretch rule */
  2744.           while(calcnode(src,0));
  2745.           while(movenums(src,0,MUL));
  2746.         }
  2747.         else if (src) primefact(src);
  2748.         break;
  2749.       case COD:
  2750.         if (src)
  2751.           if (src->kind==DIV) while (distribute2(src));
  2752.           else                while (comdeno(src));
  2753.         break;
  2754.       case SIM: if (src) simplify(src); break;
  2755.       case ASS: if (src) associate(src); break;
  2756.       case PCO: if (src && tgt) polycoef(tgt,src); break;
  2757.       case RAT: if (src) ration(src); break;
  2758.       case EXX: if (src) while (exexpand(src));  break;
  2759.       case EXJ: if (src) while (expjoin(src));  break;
  2760.       case SBS: if (src && tgt && tgt->kind==EQU) substitution(src); break;
  2761.       case QUA: if (src && tgt) quadratic(tgt,src); break;
  2762.       case FAP: if (src && tgt) factrpoly(tgt,src); break;
  2763.       case PLY:
  2764.         if (tgt && src && src->kind==DIV) {
  2765.           tmp = polydiv(tgt,src->lf,src->rt);
  2766.           if (tmp) movenode(src,tmp);
  2767.           while (calcnode(src,1));          /* rmv 0+x and 0*x */
  2768.         }
  2769.         break;
  2770.       case PPR: panx -= 10; break;
  2771.       case PP0: panx = 0; break;
  2772.       case PPL: panx += 10; break;
  2773.       case CH8: ch8=1-ch8;
  2774.         if (ch8) {
  2775.           hline = 196;          vline = 179;
  2776.           urc = 191;            llc = 192;
  2777.           lrc = 217;            ulc = 218;
  2778.           strcpy(piname,"\xE3");
  2779.         }
  2780.         else {
  2781.           hline = '-';          vline = '|';
  2782.           urc = '\\';           llc = '\\';
  2783.           lrc = '/';            ulc = '/';
  2784.           strcpy(piname,"pi");
  2785.         }
  2786.         clrscr();
  2787.         break;
  2788.       case WRI:
  2789.         writefile(keyin("Enter filename to write to:"));
  2790.         break;
  2791.       case LOD:
  2792.         loadfile(keyin("Enter filename to load from:"));
  2793.         break;
  2794.       case SAV:
  2795.         savefile(keyin("Enter filename to save to:"));
  2796.         break;
  2797.       case CLR:
  2798.         while (firf) {
  2799.           tmp = firf;
  2800.           firf = firf->next;
  2801.           freetree(tmp);
  2802.         } curf = NULL;
  2803.         break;
  2804.       case ADZ: insertkey(ADD); break;
  2805.       case SUZ: insertkey(SUB); break;
  2806.       case MUZ: insertkey(MUL); break;
  2807.       case DIZ: insertkey(DIV); break;
  2808.       case EXZ: insertkey(EXP); break;
  2809.       case DEL:
  2810.         tmp = curf;
  2811.         if (!curf) break;
  2812.         if (curf==firf) curf = firf = firf->next;
  2813.         else curf = prevnode(curf)->next = curf->next;
  2814.         freetree(tmp);
  2815.         break;
  2816.       case INK:
  2817.         if (!tgt) break;
  2818.         tgt->next = curf;
  2819.         if (curf==firf) curf=firf=tgt;
  2820.         else {
  2821.           curf = prevnode(curf);
  2822.           curf->next = tgt;
  2823.           curf = tgt;
  2824.         }
  2825.         src = curf;
  2826.         tgt = deepcopy(tgt);
  2827.         break;
  2828.       case ENT:
  2829.         window(1,ti.screenheight-4,ti.screenwidth-1,ti.screenheight-1);
  2830.         textattr(norm);
  2831.         clrscr();
  2832.         cputs("Enter a new key using postfix notation;"
  2833.            " press F6 Enter when you are done.\r\n");
  2834.         if (tgt) freetree(tgt);
  2835.         tgt = load("con");
  2836.         window(1,1,ti.screenwidth,ti.screenheight);
  2837.         break;
  2838.       case NXT:
  2839.         if (curf) curf = curf->next;
  2840.         if (!curf) curf = firf;
  2841.         src = curf;
  2842.         break;
  2843.       case PRV:
  2844.         if (curf==firf) curf = lastnode(curf);
  2845.         else curf = prevnode(curf);
  2846.         src = curf;
  2847.         break;
  2848.       }
  2849.     }
  2850.     else {           /* not a menu selection */
  2851.       tmp = curf;
  2852.       p = NULL;
  2853.       for (i=0; i<numsee && tmp; ++i) {
  2854.         if (!!(p=find_node(tmp,x,y))) break;
  2855.         tmp = tmp->next;
  2856.       }
  2857.       if (!p && tgt)
  2858.         p = find_node(tgt,x,y);
  2859.       if (b==1)                /* LMB */
  2860.         src = p;
  2861.       else if (p) {            /* RMB on an expression */
  2862.         p = deepcopy(p);
  2863.         if (tgt) freetree(tgt);
  2864.         tgt = p;
  2865.       }
  2866.       else {                   /* RMB on nothing */
  2867.         if (tgt) freetree(tgt);
  2868.         tgt=NULL;
  2869.       }
  2870.     }
  2871.   }
  2872.   textattr(7);
  2873.   clrscr();
  2874. }
  2875.  
  2876.