asgn3.c

asgn3.c

contents ::

  asgn3.c
  tree.c
  tree.h
  mylib.c
  mylib.h

/***************************************************************************
*                                                                         *
*     Tree Program in C                                                   *
*                                                                         *
*     COSC 242 Assignment 20/09/01                                        *
*                                                                         *
*     JAMES LITTLE                                                        *
*                                                                         *
***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "mylib.h"
#include "tree.h"

static int DO_RED_BLACK_INSERT = 0;

/**************************
*                        *
*   usage                *
*                        *
**************************

Prints a warning for illogical command line inputs to the standard output.

RETURN VALUE: none.

*/
static void usage() {
  fprintf(stderr, "asgn3: usage: asgn3 [-rh] <input from stdin>\n");
}

/**************************
*                        *
*   print_key            *
*                        *
**************************

Prints a word to the standard output.

PARAMETERS: key     = the character string that should be printed.

RETURN VALUE: none.

*/
static void print_key(char *key) {
  printf("%s\n", key);
}

/**************************
*                        *
*   main                 *
*                        *
**************************

Tree application: Operates one of two Tree forming techniques, that of the
standard Binary Search Tree and the Red-Black Tree. Both trees implement the
Binary Search Tree property. However the standard BST [Binary Search Tree]
does not guarantee that it is not a Linked List by another name. The [RBT]
Red-Black Tree does guarantee that it is not just a singly Linked List.

Therefore the height of a RBT is more likely to be log n.

Input to the Hash table is read through the Standard in, however this could
easily be altered to accept command line input.

The hash table insert function is the same for both methods of hashing,
however the technique differs greatly depending on the hashing method.

Note: The while loop picks out options that may have been entered through the
command line. This doesn't serve much purpose at present, but allows for
future modifications.

Note: The maximum size a word may be is 256 chars.

Note: A while loop reads input from the standard input, inserting words into
the tree. Passing an argument which identifies whether the tree insertion
should be treated as a BST or a RBT.

Note: A pre-order traversal prints the tree from the top down the left branch,
then the right branch. So this is no order at all.

PARAMETERS: argc    = the number of arguments passed thru the command line,
                       plus the program name.
             argv    = an array of command line arguments in string format.
                        And the program name.

RETURN VALUE: EXIT_SUCCESS, which just hides the value of zero, which signals
               a normal exit of the program in C.

*/
int main(int argc, char **argv) {

  const char *optstring = "hr";
  char option;
  char word[256];
  tree my_tree = tree_new();

  while ((option = getopt(argc, argv, optstring)) != EOF) {
      switch (option) {
      case 'h' :
         usage();
         return EXIT_FAILURE;
      case 'r' :
         DO_RED_BLACK_INSERT = 1;
         break;
      default :
         usage();
         return EXIT_FAILURE;
      }
  }

  while ((getword(word, sizeof word, stdin)) != EOF) {
      my_tree = tree_insert(my_tree, word, DO_RED_BLACK_INSERT);
  }

  tree_preorder(my_tree, print_key);

  /* Can use to check black heights */
  /* printf("average height: %d\n", black_height(my_tree, 0, 0)); */

  return EXIT_SUCCESS;
}

James Little