home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / mag&info / cujmay93.zip / 1105049A < prev    next >
Text File  |  1993-03-04  |  4KB  |  215 lines
  1. // ==================================================================
  2. // os.h
  3. //    Header for order statistics tree (OSTree) class.
  4. // ==================================================================
  5.  
  6. #include "btree.h"
  7.  
  8. template<class T> class OSNode : public BinaryNode<T> {
  9. public:
  10.     int size;
  11. public:
  12.     OSNode(const T& x, int Size);
  13.     OSNode(const T& x, OSNode<T> *p = 0, 
  14.     OSNode<T> *l = 0, OSNode<T> *r = 0);
  15.  
  16.  
  17.     BinaryNode<T> *LeftRotate(BinaryNode<T> *root);
  18.     BinaryNode<T> *RightRotate(BinaryNode<T> *root);
  19.     BinaryNode<T> *DeleteNode(BinaryNode<T> *z);
  20.     BinaryNode<T> *Insert(const T& AddMe);
  21.  
  22.     T *Select(int i);
  23.     void PrintNodes();
  24.     int NumNodes();
  25.     int Rank();
  26.     friend void CheckNumNodes(BinaryNode<T> *x);
  27. };
  28.  
  29. template<class T>
  30. OSNode<T>::OSNode(const T& X, int Size): BinaryNode<T>(X)
  31. {
  32.     size = Size;
  33. }
  34.  
  35. template<class T>
  36. OSNode<T>::OSNode(const T& x, OSNode<T> *p = 0, 
  37.     OSNode<T> *l = 0, OSNode<T> *r = 0):
  38.     BinaryNode<T>(x, p, l, r)
  39. {
  40.     size = 0;
  41. }
  42.  
  43. template<class T>
  44. BinaryNode<T> *
  45. OSNode<T>::LeftRotate(BinaryNode<T> *root) 
  46. {
  47.     OSNode<T> *ret = (OSNode<T> *) BinaryNode<T>::LeftRotate(root);
  48.  
  49.     ((OSNode<T> *) p)->size = size;
  50.     size = (l) ? ((OSNode<T> *) l)->size + 1 : 0;
  51.     size += (r) ? ((OSNode<T> *) r)->size + 1 : 0;
  52.  
  53.     return ret;
  54. }
  55.  
  56. template<class T>
  57. BinaryNode<T> *
  58. OSNode<T>::RightRotate(BinaryNode<T> *root) 
  59. {
  60.     OSNode<T> *ret = (OSNode<T> *) BinaryNode<T>::RightRotate(root);
  61.  
  62.     ((OSNode<T> *) p)->size = size;
  63.     size = (l) ? ((OSNode<T> *) l)->size + 1 : 0;
  64.     size += (r) ? ((OSNode<T> *) r)->size + 1 : 0;
  65.  
  66.     return ret;
  67. }
  68.  
  69. template<class T>
  70. T *
  71. OSNode<T>::Select(int i) 
  72. {
  73.     OSNode<T> *trav = this;
  74.     while (trav) {
  75.     int rank = (trav->l) ? ((OSNode<T> *) trav->l)->size + 1 : 0;
  76.     if (i == rank)
  77.         return &trav->x;
  78.     if (i < rank)
  79.         trav = (OSNode<T> *) trav->l;
  80.     else {
  81.         trav = (OSNode<T> *) trav->r;
  82.         i -= rank + 1;
  83.     }
  84.     }
  85.     return 0;
  86. }
  87.  
  88. template<class T>
  89. int
  90. OSNode<T>::NumNodes()
  91. {
  92.     int ret = (l) ? ((OSNode<T> *) l)->NumNodes() : 0;
  93.     ret += (r) ? ((OSNode<T> *) r)->NumNodes() : 0;
  94.     return ret + 1;
  95. }
  96.  
  97. template<class T>
  98. int 
  99. OSNode<T>::Rank() 
  100. {
  101.     int ret = (l) ? ((OSNode<T> *) l)->size : 0;
  102.     return ret + 1;
  103. }
  104.  
  105.  
  106.  
  107.  
  108. template<class T> void
  109. CheckNumNodes(BinaryNode<T> *x)
  110. {
  111.     if (((OSNode<T> *) x)->NumNodes() !=
  112.     ((OSNode<T> *) x)->size)
  113.     cerr << "Problems\n";
  114. }
  115.  
  116. template<class T> 
  117. BinaryNode<T> *
  118. OSNode<T>::DeleteNode(BinaryNode<T> *z)
  119. {
  120.     OSNode<T> *trav;
  121.     if (z && z->l && z->r)
  122.     trav = (OSNode<T> *) z->Succ();
  123.     else
  124.     trav = (OSNode<T> *) z;
  125.  
  126.     while (trav) {
  127.     trav->size--;
  128.     trav = (OSNode<T> *) trav->p;
  129.     }
  130.     return BinaryNode<T>::DeleteNode(z);
  131. }
  132.  
  133. template<class T> BinaryNode<T> *
  134. OSNode<T>::Insert(const T& AddMe)
  135. {
  136.     OSNode<T> *x = this;
  137.     OSNode<T> *y = 0;
  138.     while (x) {
  139.     x->size++;
  140.     y = x;
  141.     x = (AddMe < x->x) ? (OSNode<T> *) x->l : (OSNode<T> *) x->r;
  142.     }
  143.     OSNode<T> *addme = new OSNode<T>(AddMe, y);
  144.     return BinaryNode<T>::InsertNode(addme);
  145. }
  146.  
  147. template<class T> void
  148. OSNode<T>::PrintNodes()
  149. {
  150.     OSNode<T> *trav = (OSNode<T> *) Min();
  151.     while (trav) {
  152.     cout << trav->x << "(" << trav->size << ") ";
  153.     trav = (OSNode<T> *) trav->Succ();
  154.     }
  155. }
  156.  
  157. template<class T> class OSTree : public BinaryTree<T> {
  158. public:
  159.     OSTree();
  160.     T *Select(int i);
  161.     void Insert(const T& AddMe);
  162.     void PrintNodes();
  163.     void CheckNodes();
  164.  
  165. };
  166.  
  167. template<class T>
  168. OSTree<T>::OSTree()
  169. {
  170.     root = 0;
  171. }
  172.  
  173. template<class T>
  174. T *
  175. OSTree<T>::Select(int i)
  176. {
  177.     return (root) ? ((OSNode<T> *) root)->Select(i) : 0;
  178. }
  179.  
  180. template<class T>
  181. void
  182. OSTree<T>::Insert(const T& AddMe)
  183. {
  184.     if (root)
  185.         root = ((OSNode<T> *) root)->Insert(AddMe);
  186.     else
  187.         root = new OSNode<T>(AddMe);
  188. }
  189.  
  190. template<class T>
  191. void
  192. OSTree<T>::PrintNodes()
  193. {
  194.     if (root) 
  195.     ((OSNode<T> *) root)->PrintNodes(); 
  196. }
  197.  
  198. template<class T>
  199. void
  200. OSTree<T>::CheckNodes()
  201. {
  202.     if (root) {
  203.         BinaryNode<T> *trav = root->Min();
  204.         while (trav) {
  205.         if (((OSNode<T> *) trav)->NumNodes() != ((OSNode<T> *) trav)->size + 1)
  206.             cerr << "Problems\n";
  207.         trav = trav->Succ();
  208.         }
  209.     }
  210. }
  211.  
  212.  
  213.  
  214.  
  215.