home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 347_01 / example2.c < prev    next >
C/C++ Source or Header  |  1991-10-20  |  6KB  |  213 lines
  1. /*
  2.  *  program: Example2
  3.  *  purpose: Test shell for threaded avl-tree. Program reads a file
  4.  *           which contains a list of words, one per line.  As words
  5.  *           are read, they are written to monitor screen and inserted
  6.  *           into the threaded AVL tree.  After file is read, a prompt
  7.  *           line is written to the bottom of the screen, and user is
  8.  *           presented with choices. Additional words may be inserted,
  9.  *           tree can be searched for a word, the tree can listed in
  10.  *           forward or reverse order, words may be deleted from the
  11.  *           tree, the predecessor or successor of the last found word
  12.  *           may be listed.
  13.  *
  14.  *  Usage:   Example2 <filename>    where filename is the name of a
  15.  *                                  text file which contains left-adjusted
  16.  *                                  words, one per line.
  17.  *
  18.  *  Copyright (c) 1990, 1991   Bert C. Hughes
  19.  *                             200 N. Saratoga
  20.  *                             St.Paul, MN 55104
  21.  *                             Compuserve 71211,577
  22.  */
  23.  
  24. #include <stdio.h>
  25. #include <stdlib.h>
  26. #include <string.h>
  27. #include "tavltree.h"
  28.  
  29. #if defined __TURBOC__
  30. #include <conio.h>
  31. #else
  32. #define cprintf printf
  33.  
  34. int getche(void)
  35. {
  36.     char s[128];
  37.     gets(s);
  38.     return (strlen(s) ? s[0] : '\n');
  39. }
  40. #endif
  41.  
  42.  
  43. void list(TAVL_treeptr , TAVL_nodeptr (*)(TAVL_nodeptr));
  44.  
  45. main (int argc, char *argv[])
  46. {
  47.     char s[128];
  48.     FILE *fp;
  49.     TAVL_treeptr tree;
  50.     TAVL_nodeptr p;
  51.     int cmpfunc();
  52.     void *id();
  53.     void *cpy();
  54.     void *rdstr();
  55.  
  56.     TAVL_nodeptr (*dirfunc)(TAVL_nodeptr);
  57.  
  58. #if defined __TURBOC__
  59.     directvideo = 0;  /* change to 1 if there is "snow" on your screen */
  60. #endif
  61.  
  62.     /* open a file which contains a list of words, one per line */
  63.  
  64.     if (argc < 2)
  65.         strcpy(s,"WORDLIST");
  66.     else
  67.         strcpy(s,argv[1]);
  68.  
  69.     if ((fp = fopen(s,"r")) == NULL) {
  70.         cprintf("Unable to open file: %s\r\n",s);
  71.         exit(1);
  72.     }
  73.  
  74.     /* initialize the tree */
  75.     if ((tree = tavl_init(cmpfunc,id,cpy,free,rdstr,malloc,free)) == NULL) {
  76.       cprintf("\r\nError initializing tree.");
  77.       exit(1);
  78.     }
  79.  
  80.     while (!(fscanf(fp,"%s",s) == EOF)) {
  81.     cprintf("%-16.14s",s);
  82.     if (tavl_insert(tree,s,0) == NULL) {
  83.         cprintf("\r\nError inserting into tree.");
  84.         exit(1);
  85.     }
  86.     }
  87.  
  88.     fclose(fp);
  89.  
  90. /* Several cases of direct use of a field of TAVL_NODE below. */
  91. /* All TAVL fields are READONLY! Only tavl-library routines */
  92. /* alter tree & node field values. */
  93.  
  94.     p = tavl_reset(tree);
  95.  
  96.     do  {
  97. #if !defined __TURBOC__
  98.     printf("\n ...press selection key, then <ENTER> ...");
  99. #endif
  100.     cprintf("\r\n\:select:   <I>nsert   <F>ind   <D>elete   <L>ist   <S>ucc   <P>red   <Q>uit  ");
  101.     switch (getche()) {
  102.             case 'I': case 'i':
  103.                         cprintf("\r\nInsert: ");
  104.                         gets(s);
  105.                         tavl_insert(tree,s,1);
  106.                         break;
  107.  
  108.             case 'F': case 'f':
  109.                         cprintf("\r\nFind: ");
  110.                         p = tavl_find(tree,gets(s));
  111.                         if (p != NULL)
  112.                             cprintf("\r\nfind OK: %s\r\n",p->dataptr);
  113.                         else
  114.                             cprintf("\r\nNot found.\r\n");
  115.                         break;
  116.  
  117.             case 'D': case 'd':
  118.                         cprintf("\r\nDelete: ");
  119.                         gets(s);
  120.                         tavl_delete(tree,s);
  121.                         break;
  122.  
  123.             case 'L': case 'l':
  124.                         cprintf("\r\n<F>orward or <R>everse?  ");
  125.                         if (getche() != 'r')
  126.                             dirfunc = tavl_succ;
  127.                         else
  128.                             dirfunc = tavl_pred;
  129.                         cprintf("\r\n");
  130.                         list(tree,dirfunc);
  131.                         break;
  132.  
  133.             case 'S': case 's':
  134.                         if ((p = tavl_succ(p)) != NULL)
  135.                             cprintf("\r\n\nSuccessor: %s\r\n",p->dataptr);
  136.                         else
  137.                             cprintf("\r\n\nNo more.\r\n");
  138.                         break;
  139.  
  140.             case 'P': case 'p':
  141.                         if ((p = tavl_pred(p)) != NULL)
  142.                             cprintf("\r\n\nPredecessor: %s\r\n",p->dataptr);
  143.                         else
  144.                             cprintf("\r\n\nNo more.\r\n");
  145.                         break;
  146.  
  147.             case 'Q': case 'q':
  148.                         tavl_destroy(tree);
  149.                         exit(0);
  150.  
  151.             default:
  152.                         cprintf("\r\n");
  153.         }
  154.     }   while (1);
  155. }
  156.  
  157.  
  158. int cmpfunc(void *p, void *q)
  159. /* function compares two identifiers. Required parameter of tavl_init */
  160. {
  161.     return strcmp(p,q);
  162. }
  163.  
  164. void *id(void *s)
  165. /* function returns identifier of items inserted into tree,
  166.    which in this case are simply strings.
  167. */
  168. {
  169.     return s;
  170. }
  171.  
  172. void *cpy(void *p)
  173. /* create a copy of data item p - which must be a string in this example. */
  174. {
  175.     int size = 1 + strlen(p);
  176.     char *s = malloc(size);
  177.     return(memcpy(s,p,size));
  178. }
  179.  
  180. void *rdstr(char *dest, const char *src)
  181. {
  182.     return((void *)strcpy(dest,src));
  183. }
  184.  
  185. void list(TAVL_treeptr tree, TAVL_nodeptr (*f)(TAVL_nodeptr))
  186. {
  187.     TAVL_nodeptr p = tavl_reset(tree);
  188.     long i = 0;
  189.     while ((p = (*f)(p)) != NULL) {
  190.  
  191. #if defined __TURBOC__
  192. /* TurboC users can stop the output... */
  193.  
  194.         if (kbhit()) {
  195.             while (kbhit())
  196.                 getch(); /* remove it */
  197.             cprintf("\r\n\nHalt?  <y/n> ");
  198.             if (getche() == 'y') {
  199.                 cprintf("\r\n\n");
  200.                 i = -1;
  201.                 break;
  202.             }
  203.             cprintf("\r\n\n");
  204.         }
  205.  
  206. #endif
  207.     cprintf("%-16.14s",p->dataptr);
  208.         i++;
  209.     }
  210.     cprintf("\r\n         >> %ld items in TAVLtree <<\r\n",i);
  211. }
  212.  
  213.