From 09011a62c843d5756291328c2042f7cc5f59dcff Mon Sep 17 00:00:00 2001 From: Kyle K Date: Wed, 11 Apr 2012 20:58:40 -0500 Subject: initial commit --- Makefile | 44 ++++++++++ bst.h | 280 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ foo.cpp | 24 ++++++ main.cpp | 47 +++++++++++ node.h | 119 +++++++++++++++++++++++++++ 5 files changed, 514 insertions(+) create mode 100644 Makefile create mode 100644 bst.h create mode 100644 foo.cpp create mode 100644 main.cpp create mode 100644 node.h 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 +#include +#include +#include "node.h" + +using namespace std; + +template +class Bst +{ + public: + Bst(); + Bst(const Bst &); + /* Bst(Node &); */ + 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 *) const; + void free(); + void freePostOrder(Node *); + + protected: + Node *root; +}; + +template +Bst::Bst() : element_count(0), root(NULL) +{ +} + +template +Bst::Bst(const Bst& tree) +{ + this->free(); + /* still a shallow copy, dupe it! */ + this->root = tree.root; +} + +template +Bst::Bst(const T& t) +{ + Node *first = new Node(t); + this->root = first; +} + +template +Bst::~Bst() +{ + this->free(); +} + + +template +int Bst::insert(const T& e) +{ + Node *iter = this->root; + Node *new_node = new Node(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 +int Bst::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 *iter = this->root; + while (iter) + { + if (iter->getVal() < e) + { /* working on right subtree */ + if (&iter->getRight() && (iter->getRight().getVal() == e)) /* lookahead */ + { + Node *child_left = &iter->getRight().getLeft(); + Node *child_right = &iter->getRight().getRight(); + Node *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 *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 *child_left = &iter->getLeft().getLeft(); + Node *child_right = &iter->getLeft().getRight(); + Node *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 *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 *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 +int Bst::list(void) const +{ + if (!this->root) + return 1; + + this->traverse(this->root); + return 0; +} + +template +void Bst::traverse(Node *node) const +{ + if (!node) + return; + + this->traverse(&node->getLeft()); + std::cout << node->getVal() << " " << endl; + this->traverse(&node->getRight()); +} + +template +void Bst::free(void) +{ + if (this->root) + this->freePostOrder(this->root); +} + +template +void Bst::freePostOrder(Node *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 *tree = new Bst(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 *tree = new Bst(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 + +template +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& getLeft(void) const; + Node& getRight(void) const; + + private: + T v; + Node *left; + Node *right; + + protected: +}; + +template +Node::Node() : v(0), left(NULL), right(NULL) +{ +} + +template +Node::Node(const Node& n) +{ + this->v = n.v; + this->left = n.left; + this->right = n.right; +} + +template +Node& Node::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 +Node::Node(T n) : left(NULL), right(NULL) +{ + this->v = n; +} + +template +Node::Node(T& n) : left(NULL), right(NULL) +{ + this->v = n; +} + +template +Node::~Node() +{ +} + +template +T Node::getVal(void) const +{ + return (this->v); +} + +template +void Node::setVal(T v) +{ + this->v = v; +} + +template +void Node::setLeft(const Node *n) +{ + this->left = const_cast *>(n); +} + +template +void Node::setRight(const Node *n) +{ + this->right = const_cast *>(n); +} + +template +Node& Node::getLeft(void) const +{ + return *(this->left); +} + +template +Node& Node::getRight(void) const +{ + return *(this->right); +} + +#endif + -- cgit v1.2.3