home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / tbtreimp.cxx < prev    next >
C/C++ Source or Header  |  1995-04-04  |  7KB  |  297 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31.  
  32. #ifndef _tbtreimp_cxx_ /* Wed May 18 15:39:57 1994 */
  33. #define _tbtreimp_cxx_
  34.  
  35.  
  36. #ifdef __GNUC__
  37. #pragma implementation
  38. #endif
  39.  
  40.  
  41. #include "base/basicops.h"
  42. #include "base/tbtree.h"
  43. #ifdef DEBUG
  44. #include "base/memory.h"
  45. #endif
  46.  
  47.  
  48. #include <iostream.h>
  49.  
  50.  
  51. template <class ItemType>
  52. class CL_TemplateNodeSpace: public CL_HeapBTreeNodeSpace {
  53.  
  54.     // The only purpose of this template class is to override the
  55.     // DestroyItem method with the appropriate destruction code.
  56. public:
  57.     CL_TemplateNodeSpace (short order, const CL_GenericBTree& tree,
  58.                           CL_AbstractComparator& cmp)
  59.         : CL_HeapBTreeNodeSpace (order, tree, cmp) {};
  60.     ~CL_TemplateNodeSpace ();
  61.     void DestroyItem (CL_VoidPtr item) const
  62.         {CL_Basics<ItemType>::Destroy (item);};
  63. };
  64.  
  65.  
  66. template <class ItemType>
  67. CL_TemplateNodeSpace<ItemType>::~CL_TemplateNodeSpace ()
  68. {
  69.     _DestroySubtree (_root);
  70.     _root = NULL; // This gets rid of the items also, because this class'
  71.                   // version of the virtual DestroyItem is called.
  72. }
  73.  
  74.  
  75. template <class ItemType>
  76. CL_BTree<ItemType>::CL_BTree (short order,  CL_BTreeNodeSpace* space)
  77. : _tree (_comparator, order,
  78.          space ? space : (_space = new CL_TemplateNodeSpace<ItemType>
  79.                           (order, _tree, _comparator))
  80.          )
  81. {
  82.     if (space)
  83.         _space = NULL; // We don't own the node space
  84. }
  85.  
  86.  
  87. template <class ItemType>
  88. CL_BTree<ItemType>::CL_BTree (CL_AbstractComparator& cmp,
  89.                               short order,  CL_BTreeNodeSpace* space)
  90. : _tree (cmp, order, space)
  91. {
  92. }
  93.  
  94.  
  95. template <class ItemType>
  96. CL_BTree<ItemType>::~CL_BTree ()
  97. {
  98.     if (_space)
  99.         delete _space; // We own it if it's non-null
  100. }
  101.  
  102.  
  103. //
  104. // ----------------------- Search and related methods ------------------
  105.  
  106.  
  107. template <class ItemType>
  108. const ItemType& CL_BTree<ItemType>::Find (const ItemType& item) const
  109. {
  110.     CL_VoidPtr p =  CL_Basics<ItemType>::MakePointer (item);
  111.     CL_VoidPtr q = _tree.Find (p);
  112.     if (q)
  113.         return CL_Basics<ItemType>::Deref (q);
  114.     static ItemType null;
  115.     null = CL_Basics<ItemType>::NullValue();
  116.     return null;
  117. }
  118.  
  119.  
  120.  
  121.  
  122. template <class ItemType>
  123. const ItemType& CL_BTree<ItemType>::ItemWithRank (long i) const
  124. {
  125.     CL_VoidPtr p = _tree.ItemWithRank (i);
  126.     if (p)
  127.         return CL_Basics<ItemType>::Deref (p);
  128.     static ItemType null;
  129.     null = CL_Basics<ItemType>::NullValue();
  130.     return null;
  131. }
  132.  
  133.  
  134.  
  135. template <class ItemType>
  136. long CL_BTree<ItemType>::RankOf (const ItemType& item) const
  137. {
  138.     CL_VoidPtr p = CL_Basics<ItemType>::MakePointer (item);
  139.     return _tree.RankOf (p);
  140. }
  141.  
  142.  
  143. template <class ItemType>
  144. long CL_BTree<ItemType>::Size () const
  145. {
  146.     return _tree.Size();
  147. }
  148.  
  149.  
  150. template <class ItemType>
  151. bool CL_BTree<ItemType>::Add  (const ItemType& item)
  152. {
  153.     if (!PrepareToChange())
  154.         return FALSE;
  155.     CL_VoidPtr p = CL_Basics<ItemType>::MakeCopy (item);
  156.     if (_tree.Add (p)) {
  157.         Notify();
  158.         return TRUE;
  159.     }
  160.     CL_Basics<ItemType>::Destroy (p);
  161.     return FALSE;
  162. }
  163.  
  164.  
  165.  
  166. template <class ItemType>
  167. ItemType CL_BTree<ItemType>::Remove (const ItemType& item)
  168. {
  169.     if (!PrepareToChange())
  170.         return CL_Basics<ItemType>::NullValue();
  171.     CL_VoidPtr p = CL_Basics<ItemType>::MakePointer (item);
  172.     CL_VoidPtr q = _tree.Remove (p);
  173.     if (q) {
  174.         ItemType r = CL_Basics<ItemType>::Deref(q);
  175.         CL_Basics<ItemType>::Destroy (q);
  176.         Notify ();
  177.         return r;
  178.     }
  179.     return CL_Basics<ItemType>::NullValue();
  180. }
  181.  
  182.  
  183. template <class ItemType>
  184. ItemType CL_BTree<ItemType>::ExtractMin ()
  185. {
  186.     if (!PrepareToChange())
  187.         return CL_Basics<ItemType>::NullValue ();
  188.     CL_VoidPtr p = _tree.ExtractMin ();
  189.     if (p) {
  190.         Notify();
  191.         ItemType t = CL_Basics<ItemType>::Deref (p);
  192.         CL_Basics<ItemType>::Destroy (p);
  193.         return t;
  194.     }
  195.     return CL_Basics<ItemType>::NullValue ();
  196. }
  197.  
  198.  
  199.  
  200.  
  201. template <class ItemType>
  202. void CL_BTree<ItemType>::IntoStream (ostream& strm) const
  203. {
  204.     CL_BTreeNodeSpace* space = _tree.NodeSpace ();
  205.     if (space) {
  206.         CL_BTreeNodeHandle h = space->RootHandle();
  207.         PrintTree (h, 0, strm);
  208.     }
  209. }
  210.  
  211.  
  212.  
  213.  
  214. template <class ItemType>
  215. void CL_BTree<ItemType>::PrintTree (CL_BTreeNodeHandle h, short level,
  216.                                     ostream& strm) const
  217. {
  218.     if (h == 0)
  219.         return;
  220.     CL_BTreeNodeSpace* space = _tree.NodeSpace ();
  221.     CL_GenericBTreeNode* z = space->BorrowNode (h);
  222.  
  223.     for (short i = 0; i < z->Size(); i++) {
  224.         PrintTree (z->Subtree(i), level+1, strm);
  225.         for (short j = 0; j < 4*level; j++)
  226.             strm << ' ';
  227.         CL_VoidPtr q = z->Item(i);
  228.         ItemType p = CL_Basics<ItemType>::Deref (q);
  229.     CL_String st = CL_Basics<ItemType>::PrintableForm (p);
  230.         strm << "------>" << (const char*) st << endl << flush;
  231.     }
  232.     PrintTree (z->Subtree(z->Size()), level+1, strm);
  233.     space->ReturnNode (z);
  234. }
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241. // ---------------------------------------------------------------------
  242. //                    CL_BTreeIterator methods
  243. // ---------------------------------------------------------------------
  244.  
  245.  
  246.  
  247.  
  248. template <class ItemType>
  249. CL_BTreeIterator<ItemType>::CL_BTreeIterator(const CL_BTree<ItemType>& t)
  250. : _iter (t._tree)
  251. {
  252. }
  253.  
  254. template <class ItemType>
  255. CL_BTreeIterator<ItemType>::CL_BTreeIterator
  256.     (const CL_BTreeIterator<ItemType>& itr) 
  257. : _iter (itr._iter)
  258. {
  259. }
  260.  
  261.  
  262. template <class ItemType>
  263. void CL_BTreeIterator<ItemType>::Reset()
  264. {
  265.     _iter.Reset();
  266. }
  267.  
  268.  
  269.  
  270. template <class ItemType>
  271. void CL_BTreeIterator<ItemType>::BeginFrom (const ItemType& t)
  272. {
  273.     const CL_VoidPtr p = CL_Basics<ItemType>::MakePointer (t);
  274.     _iter.BeginFrom (p);
  275. }
  276.  
  277.  
  278.  
  279. template <class ItemType>
  280. bool CL_BTreeIterator<ItemType>::More()
  281. {
  282.     return _iter.More ();
  283. }
  284.  
  285.  
  286. template <class ItemType>
  287. const ItemType& CL_BTreeIterator<ItemType>::Next()
  288. {
  289.     CL_VoidPtr q = _iter.Next();
  290.     _data = CL_Basics<ItemType>::Deref (q);
  291.     return _data;
  292. }
  293.  
  294.  
  295.  
  296. #endif /* _tbtreimp_cxx_ */
  297.