initial commitHEADmaster

5 files changed, 514 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..40dc53a
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,44 @@
+BIN = bst
+SRC = main.cpp
+CC = g++
+CFLAGS = -Wall -std=gnu++98 -pedantic -MD
+DBGFLAGS = -g -O0
+ifdef DEBUG
+    CFLAGS += $(DBGFLAGS)
+else
+    CFLAGS += -O2 -march=native -mtune=native
+endif
+LDFLAGS = -lm
+
+OBJ_DIR = obj
+DEPS_DIR = obj
+BIN_DIR = bin
+
+CPP_FILES = $(filter %.cpp, $(SRC))
+DEP_FILES = $(addprefix $(DEPS_DIR)/, $(addsuffix .d, $(notdir $(subst .cpp,,$(SRC)))))
+OBJ_FILES = $(addprefix $(OBJ_DIR)/, $(addsuffix .o, $(notdir $(subst .cpp,,$(SRC)))))
+
+INCL = -I/include
+
+define CPP_template
+$(1): $(2)
+	@mkdir -p $$(OBJ_DIR)
+	@mkdir -p $$(DEPS_DIR)
+	$$(CC) -c $$(CFLAGS) $$(INCL) $$< -o $$@
+endef
+
+all: $(BIN)
+
+$(foreach cppfile, $(CPP_FILES), $(eval $(call CPP_template, $(OBJ_DIR)/$(notdir $(subst .cpp,,$(cppfile))).o, $(cppfile))))
+
+$(BIN): $(OBJ_FILES)
+	@mkdir -p $(BIN_DIR)
+	$(CC) $(LDFLAGS) $(OBJ_FILES) -o $(BIN_DIR)/$@
+
+.PHONY: clean
+
+clean:
+	rm -rf $(OBJ_DIR)
+	rm -f $(BIN_DIR)/$(BIN)
+
+-include $(DEP_FILES)
diff --git a/bst.h b/bst.h
new file mode 100644
index 0000000..b639171
--- /dev/null
+++ b/bst.h
@@ -0,0 +1,280 @@
+/* definitions are residing in this header since that's how templates get
+ * expanded, we could have a separate bst.cpp is compiler supports export keyword,
+ * instantiations of code are compiled along with the translation units that spawn them
+ */
+
+#ifndef _BST_H_
+#define _BST_H_
+
+#include <iostream>
+#include <cstdio>
+#include <cassert>
+#include "node.h"
+
+using namespace std;
+
+template <class T>
+class Bst
+{
+    public:
+        Bst();
+        Bst(const Bst &);
+        /* Bst(Node<T> &); */
+        Bst(const T &); /* above was hairy, just startup a bst from a T t */
+        ~Bst();
+
+        int insert(const T &);
+        int remove(const T &);
+        int list(void) const;
+
+    private:
+        unsigned int element_count;
+        void traverse(Node<T> *) const;
+        void free();
+        void freePostOrder(Node<T> *);
+
+    protected:
+        Node<T> *root;
+};
+
+template <class T>
+Bst<T>::Bst() : element_count(0), root(NULL)
+{
+}
+
+template <class T>
+Bst<T>::Bst(const Bst& tree)
+{
+    this->free();
+    /* still a shallow copy, dupe it! */
+    this->root = tree.root;
+}
+
+template <class T>
+Bst<T>::Bst(const T& t)
+{
+    Node<T> *first = new Node<T>(t);
+    this->root = first;
+}
+
+template <class T>
+Bst<T>::~Bst()
+{
+    this->free();
+}
+
+
+template <class T>
+int Bst<T>::insert(const T& e)
+{
+    Node<T> *iter = this->root;
+    Node<T> *new_node = new Node<T>(e);
+
+    while (iter)
+    {
+        if (iter->getVal() == e)
+        {
+            std::cout << e << " is already in the tree" << std::endl;
+            return 1;
+        }
+        else if (iter->getVal() < e)
+        {
+            if (&iter->getRight() == NULL)
+            {
+                iter->setRight((new_node));
+                return 1;
+            }
+            else
+                iter = &iter->getRight(); /* taking addr of alias/reference? */
+        }
+        else
+        {
+            if (&iter->getLeft() == NULL)
+            {
+                iter->setLeft((new_node));
+                return 1;
+            }
+            else
+                iter = &iter->getLeft();
+        }
+    }
+
+    std::cout << "creating root node " << e << endl;
+    this->root = new_node;
+
+    return 0;
+}
+
+template <class T>
+int Bst<T>::remove(const T& e)
+{
+    /* assign the value of leftmost subtree of nodes right child to node to be
+     * removed, and delete the leaf where value was taken from */
+    if (!this->root)
+        return 1;
+
+    Node<T> *iter = this->root;
+    while (iter)
+    {
+        if (iter->getVal() < e)
+        {   /* working on right subtree */
+            if (&iter->getRight() && (iter->getRight().getVal() == e)) /* lookahead */
+            {
+                Node<T> *child_left = &iter->getRight().getLeft();
+                Node<T> *child_right = &iter->getRight().getRight();
+                Node<T> *node_toremove = &iter->getRight();
+
+                if (!child_left && !child_right)
+                {   /* leaf */
+                    delete node_toremove;
+                    iter->setRight(NULL);
+                }
+                else if (child_left && child_right)
+                {   /* node to be remove has 2 children */
+                    if (&child_right->getLeft() == NULL)
+                    {   /* move up righ subtree if right child has no left child */
+                        child_right->setLeft(&node_toremove->getLeft());
+                        iter->setRight(child_right);
+                        delete node_toremove;
+                    }
+                    else
+                    {
+                        Node<T> *iter = child_right;
+                        while (&iter->getLeft().getLeft())
+                            iter = &iter->getLeft(); /* seek */
+
+                        node_toremove->setVal(iter->getLeft().getVal());
+                        delete &iter->getLeft();
+                        iter->setLeft(NULL);
+                    }
+                }
+                else
+                {   /* got one child, delete e and link child to grandfather */
+                    if (child_left)
+                        iter->setRight(child_left);
+                    else
+                        iter->setRight(child_right);
+                    delete node_toremove;
+                }
+
+                return 0;
+            }
+            else
+                iter = &iter->getRight();
+        }
+        else if (iter->getVal() > e)
+        {    /* working with left subtree */
+            if (&iter->getLeft() && (iter->getLeft().getVal() == e)) /* lookahead */
+            {
+
+                Node<T> *child_left = &iter->getLeft().getLeft();
+                Node<T> *child_right = &iter->getLeft().getRight();
+                Node<T> *node_toremove = &iter->getLeft();
+
+                if (!child_left && !child_right)
+                {   /* leaf */
+                    delete node_toremove;
+                    iter->setLeft(NULL);
+                    return 0;
+                }
+                else if (child_left && child_right)
+                {   /* node to be remove has 2 children */
+                    if (&child_right->getLeft() == NULL)
+                    {   /* move up righ subtree if right child has no left child */
+                        child_right->setLeft(&node_toremove->getLeft());
+                        iter->setLeft(child_right);
+                        delete node_toremove;
+                    }
+                    else
+                    {
+                        Node<T> *iter = child_right;
+                        while (&iter->getLeft().getLeft())
+                            iter = &iter->getLeft(); /* seek */
+
+                        node_toremove->setVal(iter->getLeft().getVal());
+                        delete &iter->getLeft();
+                        iter->setLeft(NULL);
+                    }
+                }
+                else
+                {   /* got one child, delete e and link child to grandfather */
+                    if (child_left)
+                        iter->setLeft(child_left);
+                    else
+                        iter->setLeft(child_right);
+                    delete node_toremove;
+                }
+
+                return 0;
+            }
+            else
+                iter = &iter->getLeft();
+        }
+        else
+        {   /* root removal */
+            /* assign root left subtree into lowest leaf in the right subtree */
+            if ((&this->root->getLeft() == NULL) && (&this->root->getRight() == NULL))
+            {
+                delete this->root;
+                this->root = NULL;
+                return 0;
+            }
+
+            Node<T> *iter = &this->root->getRight();
+            while (&iter->getLeft())
+                iter = &iter->getLeft();
+            iter->setLeft(&this->root->getLeft()); /* set left subtree */
+            this->root = &root->getRight();
+            delete this->root;
+            return 0;
+        }
+    }
+
+    /* not in the tree */
+    return 2;
+}
+
+template <class T>
+int Bst<T>::list(void) const
+{
+    if (!this->root)
+        return 1;
+
+    this->traverse(this->root);
+    return 0;
+}
+
+template <class T>
+void Bst<T>::traverse(Node<T> *node) const
+{
+    if (!node)
+        return;
+
+    this->traverse(&node->getLeft());
+    std::cout << node->getVal() << " " << endl;
+    this->traverse(&node->getRight());
+}
+
+template <class T>
+void Bst<T>::free(void)
+{
+    if (this->root)
+        this->freePostOrder(this->root);
+}
+
+template <class T>
+void Bst<T>::freePostOrder(Node<T> *node)
+{
+    if (!node)
+        return;
+
+    this->freePostOrder(&node->getLeft());
+    this->freePostOrder(&node->getRight());
+    #ifdef DEBUGMSG
+    std::cout << "nuking " << node->getVal() << std::endl; 
+    #endif
+    delete node;
+}
+
+#endif
+
diff --git a/foo.cpp b/foo.cpp
new file mode 100644
index 0000000..58e9b21
--- /dev/null
+++ b/foo.cpp
@@ -0,0 +1,24 @@
+class c0
+{
+    public:
+        c0() : x(0) { }
+        c0(int e) : x(e) { }
+    protected:
+        int getVal(void) {
+            return x;
+        }
+    private:
+        int x;
+};
+
+class c1 : public c0
+{
+    c0 a;
+};
+
+int main(int argc, char *argv[])
+{
+
+    return 0;
+}
+
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..187ceb8
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,47 @@
+#include "bst.h"
+
+void intTree(void)
+{
+    Bst<int> *tree = new Bst<int>(7);
+    tree->insert(4);
+    tree->insert(12);
+    tree->insert(5);
+    tree->insert(2);
+    tree->insert(3);
+    tree->insert(9);
+    tree->insert(8);
+    tree->insert(10);
+    tree->insert(21);
+    tree->insert(33);
+    tree->insert(1);
+    tree->insert(1);
+    tree->list();
+    delete tree;
+}
+
+void floatTree(void)
+{
+    Bst<float> *tree = new Bst<float>(7.5f);
+    tree->insert(4.4f);
+    tree->insert(12.1f);
+    tree->insert(5.01f);
+    tree->insert(2.2f);
+    tree->insert(3.6f);
+    tree->insert(9.8f);
+    tree->insert(8.9f);
+    tree->insert(10.32f);
+    tree->insert(21.2f);
+    tree->insert(33.13f);
+    tree->insert(1.4f);
+    tree->list();
+    delete tree;
+}
+
+int main(int argc, char *argv[])
+{
+    intTree();
+    floatTree();
+
+    return 0;
+}
+
diff --git a/node.h b/node.h
new file mode 100644
index 0000000..94ef4e0
--- /dev/null
+++ b/node.h
@@ -0,0 +1,119 @@
+/* definitions are residing in this header since that's how templates get
+ * expanded, we could have a separate node.cpp is compiler supports export keyword,
+ * instantiations of code are compiled along with the translation units that spawn them
+ */
+
+#ifndef _MYNODE_H_
+#define _MYNODE_H_
+
+#include <cstdio>
+
+template <class T>
+class Node
+{
+    public:
+        Node();
+        Node(const Node &);
+        Node& operator=(const Node &);
+        Node(T);
+        Node(T &);
+        ~Node();
+
+        T getVal(void) const;
+        void setVal(T);
+        void setLeft(const Node *);
+        void setRight(const Node *);
+        Node<T>& getLeft(void) const;
+        Node<T>& getRight(void) const;
+
+    private:
+        T v;
+        Node *left;
+        Node *right;
+
+    protected:
+};
+
+template <class T>
+Node<T>::Node() : v(0), left(NULL), right(NULL)
+{
+}
+
+template <class T>
+Node<T>::Node(const Node& n)
+{
+    this->v = n.v;
+    this->left = n.left;
+    this->right = n.right;
+}
+
+template <class T>
+Node<T>& Node<T>::operator=(const Node &rhs)
+{
+                      /* don't assign same object */
+    if (this == &rhs) /* rhs is a rvalue, hence take addr of it */
+        return *this;
+
+    this->v = rhs.v;
+    /* these also will assign subtrees, use it wisely? */
+    this->left = rhs.left;
+    this->right = rhs.right;
+
+    return *this;
+}
+
+template <class T>
+Node<T>::Node(T n) : left(NULL), right(NULL)
+{
+    this->v = n;
+}
+
+template <class T>
+Node<T>::Node(T& n) : left(NULL), right(NULL)
+{
+    this->v = n;
+}
+
+template <class T>
+Node<T>::~Node()
+{
+}
+
+template <class T>
+T Node<T>::getVal(void) const
+{
+    return (this->v);
+}
+
+template <class T>
+void Node<T>::setVal(T v)
+{
+    this->v = v;
+}
+
+template <class T>
+void Node<T>::setLeft(const Node *n)
+{
+    this->left = const_cast<Node<T> *>(n);
+}
+
+template <class T>
+void Node<T>::setRight(const Node *n)
+{
+    this->right = const_cast<Node<T> *>(n);
+}
+
+template <class T>
+Node<T>& Node<T>::getLeft(void) const
+{
+    return *(this->left);
+}
+
+template <class T>
+Node<T>& Node<T>::getRight(void) const
+{
+    return *(this->right);
+}
+
+#endif
+