Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

compiler problems...continued

By: a guest on Oct 26th, 2012  |  syntax: None  |  size: 6.29 KB  |  views: 91  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. RST.hpp
  2.  
  3. #ifndef RST_HP
  4. #define RST_HPP
  5. #include "BST.hpp"
  6. #include "RSTNode.hpp"
  7.  
  8. /*
  9.    set expandtab
  10.    set shiftwidth=2
  11.    set softtabstop=2
  12.    gg=G
  13.  */
  14. template <typename Data>
  15. class RST : public BST<Data> {
  16.   public:
  17.     virtual bool insert(const Data& item) {
  18.       if (addToTree(this->root, NULL, item))
  19.       {
  20.         this->isize++;
  21.         //perform rotations
  22.         return true;
  23.       }
  24.       else
  25.         return false;
  26.     }
  27.     virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) {
  28.       //this is assuming the right child is of higher priority than the parent
  29.       RSTNode<Data>* dummyone = ptr;  
  30.       RSTNode<Data>* dummytwo = ptr->parent;
  31.       RSTNode<Data>* dummythree = ptr->parent->parent;
  32.       bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent);
  33.       //need to bring up priority and maintain binary tree property
  34.       if(dummyone->priority > dummyone->parent->priority) {
  35.         if(isTheFatherToTheRightOfTheGrandParent){
  36.           ptr->parent->parent->right = dummyone;
  37.           ptr->left = dummytwo;
  38.         }
  39.         if(!isTheFatherToTheRightOfTheGrandParent){
  40.           ptr->parent->parent->left = ptr;
  41.           ptr->left = dummytwo;
  42.         }
  43.       }
  44.     }
  45.     virtual void rightRotate(RSTNode<Data>*& ptr) {
  46.                 return;
  47.     }
  48.     virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num)
  49.     {
  50.       if (ptr!=NULL)
  51.       {
  52.         if (num < ptr->data)
  53.         {
  54.           temp = ptr;
  55.           addToTree(ptr->left, temp, num);
  56.         }
  57.         else if (ptr->data < num)
  58.         {
  59.           temp = ptr;
  60.           addToTree(ptr->right, temp, num);
  61.         }
  62.         else
  63.           return false;                        
  64.       }
  65.       else
  66.       {
  67.         ptr =  new RSTNode<Data>(num);
  68.         ptr->parent = temp;
  69.         return true;
  70.       }
  71.     }
  72. };
  73. #endif // RST_HPP
  74.  
  75.  
  76. RSTNode.hpp
  77.  
  78. #ifndef RSTNODE_HPP
  79. #define RSTNODE_HPP
  80. #include "BSTNode.hpp"
  81. //for random #
  82. #include <cstdlib>
  83.  
  84. template <typename Data>
  85. class RSTNode : public BSTNode<Data> {
  86.   public:
  87.     RSTNode(Data const & d) : BSTNode<Data>(d) {
  88.       srand((unsigned)time(0));        
  89.       priority = rand();
  90.       left = right = parent = 0;
  91.     }
  92.     int const priority;
  93. };
  94. #endif // RSTNODE_HPP
  95.  
  96. the above should give enough info but just incase
  97.  
  98. BSTNode.hpp
  99. #ifndef BSTNODE_HPP
  100. #define BSTNODE_HPP
  101. #include <iostream>
  102. #include <iomanip>
  103.  
  104. template<typename Data>
  105. class BSTNode {
  106.  
  107.   public:
  108.  
  109.     /** Constructor.  Initialize a BSTNode with the given Data item,
  110.      *  no parent, and no children.
  111.      */
  112.     BSTNode(const Data & d) : data(d) {
  113.       left = right = parent = 0;
  114.     }
  115.  
  116.  
  117.     BSTNode<Data>* left;
  118.     BSTNode<Data>* right;
  119.     BSTNode<Data>* parent;
  120.     Data const data;   // the const Data in this node.
  121.  
  122.     /** Return the successor of this BSTNode in a BST, or 0 if none.
  123.      ** PRECONDITION: this BSTNode is a node in a BST.
  124.      ** POSTCONDITION:  the BST is unchanged.
  125.      ** RETURNS: the BSTNode that is the successor of this BSTNode,
  126.      ** or 0 if there is none.
  127.      */ // TODO
  128.     BSTNode<Data>* successor() {
  129.       BSTNode<Data>* cursor;
  130.       BSTNode<Data>* par;
  131.       cursor = this->right;
  132.       par = this->parent;
  133.  
  134.  
  135.       if (this->right != NULL)
  136.       {
  137.         while (cursor->left != NULL) {
  138.           cursor = cursor->left;
  139.         }
  140.         return cursor;
  141.       }
  142.       if ((this->right == NULL) &&  (this == par->left))
  143.         return this->parent;   
  144.  
  145.       if ((this->right == NULL) && (this == par->right))
  146.       {
  147.         do
  148.         {
  149.           cursor = par;
  150.           par = par->parent;
  151.           if (par ==  NULL)
  152.           {return cursor;}                             
  153.         }while(cursor != par->left);
  154.         return par;
  155.       }
  156.       if (this->right == NULL && this->parent == NULL)
  157.         return NULL;   
  158.     }
  159. };
  160.  
  161. /** Overload operator<< to print a BSTNode's fields to an ostream. */
  162. template <typename Data>
  163. std::ostream & operator<<(std::ostream& stm, const BSTNode<Data> & n) {
  164.   stm << '[';
  165.   stm << std::setw(10) << &n;                 // address of the BSTNode
  166.   stm << "; p:" << std::setw(10) << n.parent; // address of its parent
  167.   stm << "; l:" << std::setw(10) << n.left;   // address of its left child
  168.   stm << "; r:" << std::setw(10) << n.right;  // address of its right child
  169.   stm << "; d:" << n.data;                    // its data field
  170.   stm << ']';
  171.   return stm;
  172. }
  173.  
  174. #endif // BSTNODE_HPP
  175.  
  176.  
  177. RST.hpp
  178.  
  179. #ifndef RST_HP
  180. #define RST_HPP
  181. #include "BST.hpp"
  182. /*
  183.    set expandtab
  184.    set shiftwidth=2
  185.    set softtabstop=2
  186.    gg=G
  187.  */
  188. template <typename Data>
  189. class RST : public BST<Data> {
  190.   public:
  191.     virtual bool insert(const Data& item) {
  192.       if (addToTree(this->root, NULL, item))
  193.       {
  194.         this->isize++;
  195.         //perform rotations
  196.         return true;
  197.       }
  198.       else
  199.         return false;
  200.     }
  201.     virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) {
  202.       //this is assuming the right child is of higher priority than the parent
  203.       RSTNode<Data>* dummyone = ptr;  
  204.       RSTNode<Data>* dummytwo = ptr->parent;
  205.       RSTNode<Data>* dummythree = ptr->parent->parent;
  206.       bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent);
  207.       //need to bring up priority and maintain binary tree property
  208.       if(dummyone->priority > dummyone->parent->priority) {
  209.         if(isTheFatherToTheRightOfTheGrandParent){
  210.           ptr->parent->parent->right = dummyone;
  211.           ptr->left = dummytwo;
  212.         }
  213.         if(!isTheFatherToTheRightOfTheGrandParent){
  214.           ptr->parent->parent->left = ptr;
  215.           ptr->left = dummytwo;
  216.         }
  217.       }
  218.     }
  219.     virtual void rightRotate(RSTNode<Data>*& ptr) {
  220.                 return;
  221.     }
  222.     virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num)
  223.     {
  224.       if (ptr!=NULL)
  225.       {
  226.         if (num < ptr->data)
  227.         {
  228.           temp = ptr;
  229.           addToTree(ptr->left, temp, num);
  230.         }
  231.         else if (ptr->data < num)
  232.         {
  233.           temp = ptr;
  234.           addToTree(ptr->right, temp, num);
  235.         }
  236.         else
  237.           return false;                        
  238.       }
  239.       else
  240.       {
  241.         ptr =  new RSTNode<Data>(num);
  242.         ptr->parent = temp;
  243.         return true;
  244.       }
  245.     }
  246. };
  247. #endif // RST_HPP
clone this paste RAW Paste Data