Friday, 20 February 2015

BST using smart pointers and templates in C++

I am here trying to implement BST using smart pointers and template. For implementation of BST, I will be creating following classes.
1. BinTreeNode
2. BinTree
Also, In order to test I will be writing simple unit test file (source.cpp)

1. BinTreeNode.h
 #pragma once  
 #include <memory>  
 #include <iostream>  
 #include <string>  
 template <class T>  
 class BinTreeNode;  
 template <class T>  
 std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode);  
 template <class T>  
 class BinTreeNode {  
 public:  
      T m_data;  
      std::shared_ptr<BinTreeNode> m_spleftNode, m_sprightNode;  
      std::weak_ptr<BinTreeNode> m_wpparentNode;  
      BinTreeNode(T data) :m_data(data), m_spleftNode(nullptr), m_sprightNode(nullptr) {}  
      ~BinTreeNode() {}  
      bool operator==(const BinTreeNode<T>& binNode) {  
           if (m_data == binNode.m_data)  
                return true;  
           return false;  
      }  
      bool insertNode(std::shared_ptr<BinTreeNode<T>> binNode) {  
           if (binNode->m_data > m_data) {  
                if (m_sprightNode == nullptr)  
                     m_sprightNode = binNode;  
                else  
                     m_sprightNode->insertNode(binNode);  
           }  
           else if (binNode->m_data == m_data) {  
                std::cout << "Data already present!!\n";  
                return false;  
           }  
           else {  
                if (m_spleftNode == nullptr)  
                     m_spleftNode = binNode;  
                else  
                     m_spleftNode->insertNode(binNode);  
           }  
           return true;  
      }  
      friend std::ostream& operator<< <>(std::ostream& out, const BinTreeNode<T>& binNode);  
 };  
 template <class T>  
 std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode) {  
      if (binNode.m_spleftNode != nullptr)  
           out << "[Left: " << *(binNode.m_spleftNode) << " ] ";  
      out << "(" << binNode.m_data << ")";  
      if (binNode.m_sprightNode != nullptr)  
           out << " [Right: " << *(binNode.m_sprightNode) << " ]";  
      return out;  
 }  

2. BinTree
#pragma once  
 #include <iostream>  
 #include <memory>  
 #include "BinTreeNode.h"  
 template <typename T>  
 class BinTree;  
 template <typename T>  
 std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree);  
 template <typename T>  
 class BinTree {  
 public:  
      std::shared_ptr<BinTreeNode<T> > m_sproot;  
      BinTree() {}  
      ~BinTree() {}  
      bool insertdata(T data) {  
           std::shared_ptr<BinTreeNode<T>> spbinNode(new BinTreeNode<T>(data));  
           if (m_sproot == nullptr) {  
                m_sproot = spbinNode;  
                return true;  
           }  
           std::shared_ptr<BinTreeNode<T>> binNode(new BinTreeNode<T>(data));  
           return m_sproot->insertNode(binNode);  
      }  
      friend std::ostream& operator<< <>(std::ostream& out, const BinTree<T>& binTree);  
 };  
 template <typename T>  
 std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree) {  
      out << *(binTree.m_sproot);  
      return out;  
 }  

3. Source.cpp
#include <iostream>  
 #include <string>  
 #include "BinTreeNode.h"  
 #include "BinTree.h"  
 int main() {  
      BinTree<std::string> bintree;  
      bintree.insertdata(std::string("text"));  
      bintree.insertdata(std::string("binary"));  
      bintree.insertdata(std::string("search"));  
      bintree.insertdata(std::string("tree"));  
      bintree.insertdata(std::string("implementation"));  
      std::cout << bintree;  
      getchar();  
 }  

No comments:

Post a Comment