adding initial files for binary tree

8 files changed, 253 insertions, 0 deletions

diff --git a/.atom-build.json b/.atom-build.json
new file mode 100644
index 0000000..0193d03
--- /dev/null
+++ b/.atom-build.json
@@ -0,0 +1,3 @@
+{
+  "cmd": "make -B"
+}
diff --git a/.clang_complete b/.clang_complete
new file mode 100644
index 0000000..30679be
--- /dev/null
+++ b/.clang_complete
@@ -0,0 +1 @@
+-Iinclude
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..4581ef2
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,29 @@
+# Compiled Object files
+*.slo
+*.lo
+*.o
+*.obj
+
+# Precompiled Headers
+*.gch
+*.pch
+
+# Compiled Dynamic libraries
+*.so
+*.dylib
+*.dll
+
+# Fortran module files
+*.mod
+*.smod
+
+# Compiled Static libraries
+*.lai
+*.la
+*.a
+*.lib
+
+# Executables
+*.exe
+*.out
+*.app
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..e553151
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,34 @@
+CC := g++ # this is the main compiler
+# CC := clange --analyze # and comment out the linker last line
+SRCDIR := src
+BUILDDIR := build
+TARGET := bin/binary_tree_test
+
+SRCEXT := cpp
+SOURCES := $(shell find $(SRCDIR) -type f -name "*.$(SRCEXT)")
+OBJECTS := $(patsubst $(SRCDIR)/%,$(BUILDDIR)/%,$(SOURCES:.$(SRCEXT)=.o))
+CFLAGS := -g -Wall -Wextra -Wpedantic -std=c++14
+LIB :=
+INC := -I include
+
+$(TARGET): $(OBJECTS)
+	@echo " Linking..."
+	@echo " $(CC) $^ -o $(TARGET) $(LIB)"; $(CC) $^ -o $(TARGET) $(LIB)
+
+$(BUILDDIR)/%.o: $(SRCDIR)/%.$(SRCEXT)
+	@mkdir -p $(BUILDDIR)
+	@echo " $(CC) $(CFLAGS) $(INC) -c -o $@ $<"; $(CC) $(CFLAGS) $(INC) -c -o $@ $<
+
+clean:
+	@echo " Cleaning..."
+	@echo " $(RM) -r $(BUILDDIR) $(TARGET)"; $(RM) -r $(BUILDDIR) $(TARGET)
+
+# Tests
+tester:
+	@echo " $(CC) $(CFLAGS) test/tester.cpp $(INC) $(LIB) -o bin/tester"; $(CC) $(CFLAGS) test/tester.cpp $(INC) $(LIB) -o bin/tester
+
+# Spikes
+ticket:
+	@echo " $(CC) $(CFLAGS) spikes/ticket.cpp $(INC) $(LIB) -o bin/ticket"; $(CC) $(CFLAGS) spikes/ticket.cpp $(INC) $(LIB) -o bin/ticket
+
+.PHONY: clean
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..8b05a40
--- /dev/null
+++ b/README.md
@@ -0,0 +1,2 @@
+# chess_ai
+A chess AI that was programmed parallel to a second year computing course and hence uses a lot of object oriented programming.
diff --git a/bin/binary_tree_test b/bin/binary_tree_test
new file mode 100755
index 0000000..daf75eb
--- /dev/null
+++ b/bin/binary_tree_test
diff --git a/include/binary_tree.hpp b/include/binary_tree.hpp
new file mode 100644
index 0000000..72977f0
--- /dev/null
+++ b/include/binary_tree.hpp
@@ -0,0 +1,170 @@
+#ifndef BINARY_TREE_HPP
+#define BINARY_TREE_HPP
+
+#include <cstdio>
+#include <iostream>
+
+template<typename T>
+class BinaryTree;
+
+template<typename T>
+class Node;
+
+// class that descibes a node in the tree
+template<typename T>
+class Node {
+    friend BinaryTree<T>;
+public:
+    // create an empty node with no next and only adding the item
+    Node(const T& it) : item(it), next_left(NULL), next_right(NULL) {}
+
+    // create a new node with next nodes
+    Node(const T& it, Node<T>* n_left, Node<T> n_right)
+        : item(it), next_left(n_left), next_right(n_right) {}
+
+    // nothing needed in destructor
+    ~Node() {
+        std::cout << "This is the Node destructor" << std::endl;
+    }
+
+    // overloading the operators for ease of use
+    friend bool operator==(const Node<T>& n1, const Node<T>& n2) {
+        return n1.item == n2.item;
+    }
+
+    friend bool operator!=(const Node<T>& n1, const Node<T>& n2) {
+        return !(n1 == n2);
+    }
+
+    friend bool operator<(const Node<T>& n1, const Node<T>& n2) {
+        return n1.item < n2.item;
+    }
+
+    friend bool operator>(const Node<T>& n1, const Node<T>& n2) {
+        return n1.item > n2.item;
+    }
+
+    friend bool operator<=(const Node<T>& n1, const Node<T>& n2) {
+        return !(n1.item > n2.item);
+    }
+
+    friend bool operator>=(const Node<T>& n1, const Node<T>& n2) {
+        return !(n1.item < n2.item);
+    }
+
+    friend std::ostream& operator<<(std::ostream& out, const Node<T>& n) {
+        out << n.item;
+        return out;
+    }
+
+    // return information of the values from the node
+    T get_item() {
+        return item;
+    }
+
+    Node<T>* get_next_left() {
+        return next_left;
+    }
+
+    Node<T>* get_next_right() {
+        return next_right;
+    }
+
+    unsigned int get_height() {
+        return height;
+    }
+
+    unsigned int get_depth() {
+        return depth;
+    }
+
+    signed int get_bf() {
+        return bf;
+    }
+protected:
+    void set_item(T it) {
+        item = it;
+    }
+
+    void set_next_left(Node<T> n_left) {
+        next_left = n_left;
+    }
+
+    void set_next_right(Node<T>* n_right) {
+        next_right = n_right;
+    }
+
+    void set_next(Node<T>* n_left, Node<T>* n_right) {
+        set_next_left(n_left);
+        set_next_right(n_right);
+    }
+private:
+    // item stored in the tree
+    T item;
+    // pointers to the next elements in the tree
+    Node<T> *next_left, *next_right;
+
+    // distance from node to leaf
+    unsigned int height;
+    // distance from node to root
+    unsigned int depth;
+    // height of the right subtree - height of the left subtree
+    signed int bf;
+};
+
+// tree of all the nodes
+template<typename T>
+class BinaryTree {
+    typedef Node<T>* node_ptr;
+public:
+    // empty tree node which will then be created when adding elements
+    BinaryTree() : root_node(NULL), tree_height(0) {}
+    ~BinaryTree() {
+        std::cout << "This is the Binary Tree destructor" << std::endl;
+        delete root_node;
+    }
+
+    // adds an element to the tree
+    void push_back(const T& element) {
+        // create new node with element
+        node_ptr new_node = new Node<T>(element);
+
+        if(root_node == NULL) {
+            root_node = new_node;
+        } else {
+            // make current node
+            node_ptr curr_node = root_node;
+            bool found = false;
+
+            // go to node that has to be added
+            while(!found) {
+                if(*new_node < *curr_node) {
+                    if(curr_node->next_left != NULL) {
+                        curr_node = curr_node->next_left;
+                    } else {
+                        found = true;
+                        curr_node->next_left = new_node;
+                    }
+                } else {
+                    if(curr_node->next_right != NULL) {
+                        curr_node = curr_node->next_right;
+                    } else {
+                        found = true;
+                        curr_node->next_right = new_node;
+                    }
+                }
+            }
+        }
+    }
+
+    Node<T> get_root() {
+        return *root_node;
+    }
+private:
+    // root of the tree
+    node_ptr root_node;
+    // height of the whole tree
+    unsigned int tree_height;
+};
+
+#endif
diff --git a/src/main.cpp b/src/main.cpp
new file mode 100644
index 0000000..e093a98
--- /dev/null
+++ b/src/main.cpp
@@ -0,0 +1,14 @@
+#include "binary_tree.hpp"
+
+#include <iostream>
+
+using namespace std;
+
+int main(int argc, char* argv[]) {
+    BinaryTree<int> int_bt;
+    int_bt.push_back(20);
+    Node<int> node(int_bt.get_root());
+
+    cout << "root node int: " << node.get_item() << endl;
+    return 0;
+}