Started on default main routines

git-svn-id: http://svn.cactuscode.org/flesh/trunk@19 17b73243-c579-4c4c-a9d2-2d5706c11dac

2 files changed, 300 insertions, 0 deletions

diff --git a/src/util/BinaryTree.c b/src/util/BinaryTree.c
new file mode 100644
index 00000000..8407980b
--- /dev/null
+++ b/src/util/BinaryTree.c
@@ -0,0 +1,261 @@
+ /*@@
+   @file      BinaryTree.c
+   @date      Mon Oct  5 11:00:01 1998
+   @author    Tom Goodale
+   @desc 
+   Routines to deal with binary trees
+   @enddesc 
+ @@*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "BinaryTree.h"
+
+static char *rcsid = "$Id$";
+
+
+ /*@@
+   @routine    TreeStoreData
+   @date       Mon Oct  5 11:04:55 1998
+   @author     Tom Goodale
+   @desc 
+   Stores data in a binary tree.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+t_tree *TreeStoreData(t_tree *root, t_tree *subtree, void *data, int (*compare)(const void *, const void *))
+{
+  int order;
+
+  if(!subtree)
+  {
+    /* Create a new element. */ 
+    subtree = (t_tree *)malloc(sizeof(t_tree));
+    if(subtree)
+    {
+      subtree->left=NULL;
+      subtree->right=NULL;
+
+      subtree->data = data;
+
+      if(root) 
+      {
+	if((order = compare(data, root->data)) < 0)
+	{
+	  root->left = subtree;
+	}
+	else
+	{
+	  root->right = subtree;
+	}
+      }
+    }
+  }
+  else
+  {
+    /* Go down left or right branch. */
+    if((order = compare(data, root->data)) < 0)
+    {
+      subtree = TreeStoreData(subtree, subtree->left, data, compare);
+    }
+    else if(order > 0) 
+    {
+      root = TreeStoreData(subtree, subtree->right, data, compare);
+    }
+    else if(order==0)
+    {
+      /* Duplicate key. */
+      subtree = NULL;
+    }
+  }
+
+  /* Return either the new node, or NULL if either a duplicate value or
+   * memory failure.
+   */
+
+  return subtree;
+
+}
+
+ /*@@
+   @routine    TreeTraverseInorder
+   @date       Mon Oct  5 11:05:54 1998
+   @author     Tom Goodale
+   @desc 
+   Traverse a tree 'inorder'
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+int TreeTraverseInorder(t_tree *root, int (*process)(void *, void *), void *info)
+{
+  int terminate;
+
+  terminate = 0;
+
+  if(root)
+  {
+    terminate = TreeTraverseInorder(root->left, process, info);
+    if(!terminate) terminate = process(root->data,info);
+    if(!terminate) terminate = TreeTraverseInorder(root->right, process, info);
+  }
+
+  return terminate;
+}
+
+ /*@@
+   @routine    TreeTraversePreorder
+   @date       Mon Oct  5 11:05:54 1998
+   @author     Tom Goodale
+   @desc 
+   Traverse a tree 'preorder'
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+int TreeTraversePreorder(t_tree *root, int (*process)(void *, void *), void *info)
+{
+  int terminate;
+
+  terminate = 0;
+
+  if(root)
+  {
+    terminate = process(root->data, info);
+    if(!terminate) terminate = TreeTraversePreorder(root->left, process, info);
+    if(!terminate) terminate = TreeTraversePreorder(root->right, process,info);
+  }
+
+  return terminate;
+}
+		     
+ /*@@
+   @routine    TreeTraversePostorder
+   @date       Mon Oct  5 11:05:54 1998
+   @author     Tom Goodale
+   @desc 
+   Traverse a tree 'postorder'
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+int TreeTraversePostorder(t_tree *root, int (*process)(void *, void *), void *info)
+{
+  int terminate;
+
+  terminate = 0;
+
+  if(root)
+  {
+    terminate = TreeTraversePostorder(root->left, process, info);
+    if(!terminate) terminate = TreeTraversePostorder(root->right, process, info);
+    if(!terminate) terminate = process(root->data, info);
+  }
+
+  return terminate;
+}
+
+ /*@@
+   @routine    TreePrintNodes
+   @date       Mon Oct  5 11:06:52 1998
+   @author     Tom Goodale
+   @desc 
+   Allows a binary tree to be printed out.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+void TreePrintNodes(t_tree *root, int depth, void (*print_node)(void *, int))
+{
+  if(root)
+  {
+    TreePrintNodes(root->left, depth+1,print_node);
+    print_node(root->data,depth);
+    TreePrintNodes(root->right, depth+1, print_node);
+  }
+}
+
+/* Stuff to test the routines. */
+
+#define TEST_BinaryTree
+#ifdef TEST_BinaryTree
+
+typedef struct 
+{
+  int i;
+} t_infodata ;
+
+int process(char *data, t_infodata *infodata)
+{
+  printf("%d, %s\n", infodata->i, data);
+
+  infodata->i++;
+
+  return 0;
+}
+
+void print_node(char *data, int depth)
+{
+  int i;
+  for(i=0; i < depth; i++) printf("*");
+  printf("%s\n", data);
+}
+
+int main(void)
+{
+  t_tree *root;
+  t_infodata infodata;
+  char instring[500];
+  char *newstring;
+
+  infodata.i=0;
+
+  root = NULL;
+  
+  while(scanf("%s", instring) && strcmp("quit", instring))
+  {
+    newstring = malloc(strlen(instring)*sizeof(char));
+    strcpy(newstring, instring);
+
+    if(!root)
+    {
+      root = TreeStoreData(root, root, newstring, (int (*)(const void *, const void *))strcmp);
+    }
+    else
+    {
+      TreeStoreData(root, root, newstring, (int (*)(const void *, const void *))strcmp);
+    }  
+  }
+
+  TreeTraverseInorder(root, (int (*)(void *, void *))process, (void *)&infodata);
+
+  TreePrintNodes(root, 0, (void (*)(void *, int))print_node);
+
+
+  return 0;
+}
+
+#endif
diff --git a/src/util/BinaryTree.h b/src/util/BinaryTree.h
new file mode 100644
index 00000000..8be9a956
--- /dev/null
+++ b/src/util/BinaryTree.h
@@ -0,0 +1,39 @@
+ /*@@
+   @header    BinaryTree.h
+   @date      Mon Oct  5 11:01:20 1998
+   @author    Tom Goodale
+   @desc 
+   Prototypes and data definitions for binary tree routines.
+   @enddesc 
+ @@*/
+
+#ifndef _BINARYTREE_H_
+#define _BINARYTREE_H_
+
+typedef struct T_TREE
+{
+  struct T_TREE *left;
+  struct T_TREE *right;
+
+  void *data;
+} t_tree;
+
+#ifdef _cplusplus
+extern "C" {
+#endif
+
+t_tree *TreeStoreData(t_tree *root, t_tree *subtree, void *data, int (*compare)(const void *, const void *));
+
+int TreeTraverseInorder(t_tree *root, int (*process)(void *, void *), void *info);
+
+int TreeTraversePreorder(t_tree *root, int (*process)(void *, void *), void *info);
+
+int TreeTraversePostorder(t_tree *root, int (*process)(void *, void *), void *info);
+
+void TreePrintNodes(t_tree *root, int depth, void (*print_node)(void *, int));
+
+#ifdef _cplusplus
+	   }
+#endif
+
+#endif