initial commit: an AVL tree

5 files changed, 182 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..7327ab6
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,8 @@
+.POSIX:
+OBJS = strbst.o
+CFLAGS = -Wall -pedantic
+tmplt: $(OBJS)
+	$(CC) $(CFLAGS) $(LDFLAGS) $(OBJS) -o $@
+clean:
+	rm -f $(OBJS) inter
+strbst.o: strbst.c strbst.h
diff --git a/README b/README
new file mode 100644
index 0000000..4bb969b
--- /dev/null
+++ b/README
@@ -0,0 +1,4 @@
+# tmplt
+
+A hierarchical filetype based on descriptions and a directed acyclic
+graph. `template` is an example of this filetype
diff --git a/strbst.c b/strbst.c
new file mode 100644
index 0000000..e4494ab
--- /dev/null
+++ b/strbst.c
@@ -0,0 +1,131 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include <stdio.h>
+
+#include "strbst.h"
+#define max(a,b) ((a > b) ? a : b)
+#define min(a,b) ((a < b) ? a : b)
+
+typedef char height;
+
+typedef struct strbstnode{
+    char* ind;
+    void* data;
+    struct strbstnode* left;
+    struct strbstnode* right;
+    int ht;
+} strbstnode;
+
+strbst* newbst(void) {
+    strbst* out = malloc(sizeof(strbst));
+    out->head = NULL;
+    return out;
+}
+
+static strbstnode* newbstnode(char* ind, void* data) { // does not ins
+    strbstnode* out = malloc(sizeof(strbstnode));
+    out->ind = ind;
+    out->data = data;
+    out->left = out->right = NULL;
+    out->ht = 0;
+    return out;
+}
+
+int getht(strbstnode* node) {
+    return node ? node->ht : -1;
+}
+
+static void rightrot(strbstnode** bst);
+static void leftrot(strbstnode** bst);
+
+int insnode(strbstnode** bst, strbstnode* new) { // Find good parent
+    if (!*bst){
+        *bst = new;
+        return 0;
+    }
+    strbstnode** node;
+    if (strcmp(new->ind, (*bst)->ind) < 0)
+        node = &((*bst)->left);
+    else
+        node = &((*bst)->right);
+    int heavy = insnode( node, new );
+    int diff = getht((*bst)->right) - getht((*bst)->left);
+    if (diff > 1) {
+        if (heavy == -1)
+            rightrot(node);
+        leftrot(bst);
+    } else if (diff < -1){
+        if (heavy == 1)
+            leftrot(node);
+        rightrot(bst);
+    }
+    (*bst)->ht = max( getht((*bst)->left), getht((*bst)->right) )+1;
+    return ( getht((*bst)->right) - getht((*bst)->left) );
+}
+
+void insbst(strbst* bst, char* ind, void* data) {
+    insnode(&(bst->head), newbstnode(ind, data)); // allows recursion
+}
+
+void* querynode(strbstnode* node, char* ind){
+    int cmp = strcmp(ind, node->ind);
+    if (cmp > 0)
+        return querynode(node->right, ind);
+    else if (cmp < 0)
+        return querynode(node->left, ind);
+    else if (node)
+        return node->data;
+    else
+        return NULL;
+}
+
+void* querybst(strbst* bst, char* ind) {
+    return querynode(bst->head, ind);
+}
+
+void rightrot(strbstnode** bst) {
+/*
+    a         b
+   / \       / \
+  b   e =>  c   a
+ / \           / \
+c   d         d   e
+*/
+    strbstnode* flip = (*bst)->left->right; // flip = d
+    (*bst)->left->right = *bst; // position of d = a
+    *bst = (*bst)->left; // tip = b
+    (*bst)->right->left = flip;
+}
+
+void leftrot(strbstnode** bst) {
+/*
+  a            b
+ / \          / \
+e   b   =>   a   c
+   / \      / \
+  d   c    e   d
+*/
+    strbstnode* flip = (*bst)->right->left; // flip = d
+    (*bst)->right->left = *bst; // position of d = a
+    *bst = (*bst)->right; // tip = b
+    (*bst)->left->right = flip;
+}
+
+void printnode(strbstnode* node) {
+    if (!node) return;
+    if (node->right)
+        printnode(node->right);
+    if (node->left)
+        printnode(node->left);
+    printf("node %s", node->ind);
+    if (node->right)
+        printf(" (right) %s",node->right->ind);
+    if (node->left)
+        printf(" (left) %s", node->left->ind);
+    printf("\n");
+}
+
+void printbst(strbst* bst) {
+    printnode(bst->head);
+}
diff --git a/strbst.h b/strbst.h
new file mode 100644
index 0000000..d1a07bf
--- /dev/null
+++ b/strbst.h
@@ -0,0 +1,18 @@
+#ifndef _STRBST_
+#define _STRBST_
+
+typedef struct strbstnode strbstnode;
+
+typedef struct {
+    strbstnode* head;
+} strbst;
+
+strbst* newbst(void);
+
+void insbst(strbst* bst, char* ind, void* data);
+
+void* query(strbst* bst, char* ind);
+
+void printbst(strbst* bst);
+
+#endif
diff --git a/template b/template
new file mode 100644
index 0000000..bb2aa73
--- /dev/null
+++ b/template
@@ -0,0 +1,21 @@
+UGAMUNC topic one
+:The Syrian Refugee Crisis
+- Actors
+- Previous Action
+- Solutions
+
+:Actors
+- Freedom Fighters
+- Government
+
+:Government
+- Chemical Warfare
+Government cannot be considered a reasonable or negotiable actor
+
+:Chemical Warfare
+Civilians are being killed by chemicals outlawed by Geneva Convention.
+
+:Previous Action
+- Chemical Warfare
+The United Nations has attempted, in ceasefires to get gov't to agree to
+stop chemical warfare in exchange for enemies'