/*---------------------------------------------------------------------+
|                Copyright (c) 1996, SAS Institute Inc.                |
|                  Unpublished - All Rights Reserved                   |
|                      S A S / C   S A M P L E                         |
|                                                                      |
|         NAME: BTREE                                                  |
|     LANGUAGE: C                                                      |
|      PURPOSE: SAS/C DEBUGGER example program                         |
|               This program generates a binary tree. When run under   |
|               the control of the debugger, it opens up a Termin      |
|               window that you can use to enter several data lines.   |
|               The program inserts the lines in a binary tree, then   |
|               performs an in-order traversal, printing the data lines|
|               in sorted order.                                       |
|               See SAS/C Debugger User's Guide and Reference Third    |
|               Edition, Chapter 10, pgs. 209-212 .                    |
|   MISC NOTES: This program is used in conjunction with the DUMPTREE  |
|               program to demonstrate how to use a REXX EXEC with a   |
|               C program running under control of the SAS/C Debugger. |
| INPUT/OUTPUT: stdin/stdout                                           |
|               Since the input is stdin, you could type some lines in |
|               a file and redirect stdin to the file. However, the    |
|               simplest way to enter the lines is from the Termin     |
|               window.                                                |
|                                                                      |
| MVS -                                                                |
|    COMPILE, LINK: SUBMIT prefix.SAMPLE.AUX(BTREE)                    |
|               make sure to use the =DEBUG compile option             |
|               where "prefix" is the installation defined high-level  |
|               qualifier for the SAS/C product.                       |
|      EXECUTE: execute under TSO, see below                           |
| TSO -                                                                |
|    COMPILE: LC370 CLIST                                              |
|       LINK: CLK370 CLIST                                             |
|    EXECUTE: CALL your.load.lib(BTREE) '=DEBUG'                       |
| CMS -                                                                |
|    COMPILE: LC370 BTREE (DEBUG                                       |
|       LINK: CLINK BTREE (GENMOD                                      |
|    EXECUTE: BTREE =DEBUG                                             |
+---------------------------------------------------------------------*/
#eject
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef struct TREENODE {
   size_t length;
   char *value;
   struct TREENODE *left, *right;
   } TreeNode;

static TreeNode *alloc_TreeNode(size_t, const char *);
static void insert_TreeNode(TreeNode *, size_t, const char *);
static void print_Tree(TreeNode *);

void main(void)
   {
   TreeNode *tree = NULL;
   char io_buffer[258];

   fgets(io_buffer, 256, stdin);
   while (!feof(stdin) && !ferror(stdin)) {
      size_t length = strlen(io_buffer) - 1;
      if (io_buffer[length] != '\n') {
         printf("String \"%.40s\" is too long.\n", io_buffer);
         exit(8);
         }
      if (tree == NULL)
         tree = alloc_TreeNode(length, io_buffer);
      else
         insert_TreeNode(tree, length, io_buffer);
      fgets(io_buffer, 256, stdin);
      }

   if (ferror(stdin)) {
      puts("Error reading input file.");
      exit(8);
      }

   print_Tree(tree);
   exit(0);
   }

static void insert_TreeNode(TreeNode *root, size_t length,
                                                   const char *string)
   {
   int cmp;

   cmp = memcmp(string, root->value, min(length, root->length));
   if (cmp == 0)
      cmp = length - root->length;

   if (cmp > 0) {
      if (root->left != NULL)
         insert_TreeNode(root->left, length, string);
      else
         root->left = alloc_TreeNode(length, string);
      }
   else if (cmp < 0) {
      if (root->right != NULL)
         insert_TreeNode(root->right, length, string);
      else
         root->right = alloc_TreeNode(length, string);
      }
   else
      return;
   }

static void print_Tree(TreeNode *root)
   {
   if (root->right != NULL)
      print_Tree(root->right);

   printf("%.*s\n", root->length, root->value);

   if (root->left != NULL)
      print_Tree(root->left);

   }

static TreeNode *alloc_TreeNode(size_t length, const char *string)
   {
   TreeNode *new;
   char *val;

   new = malloc(sizeof(TreeNode));

   if (new == NULL || (val = malloc(length)) == NULL) {
      puts("Can't allocate a new node");
      exit(8);
      }

   memcpy(val, string, length);
   new->length = length;
   new->value = val;
   new->left = new->right = NULL;

   return new;
   }