home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / dtree.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-17  |  9.3 KB  |  310 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- // 
  5. // C++ Source Code File Name: dtree.cpp 
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced By: Doug Gaer   
  8. // File Creation Date: 02/07/1997  
  9. // Date Last Modified: 03/17/1999
  10. // Copyright (c) 1997 Douglas M. Gaer
  11. // ----------------------------------------------------------- // 
  12. // ------------- Program Description and Details ------------- // 
  13. // ----------------------------------------------------------- // 
  14. /*
  15. The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
  16. All those who put this code or its derivatives in a commercial
  17. product MUST mention this copyright in their documentation for
  18. users of the products in which this code or its derivative
  19. classes are used. Otherwise, you have the freedom to redistribute
  20. verbatim copies of this source code, adapt it to your specific
  21. needs, or improve the code and release your improvements to the
  22. public provided that the modified files carry prominent notices
  23. stating that you changed the files and the date of any change.
  24.  
  25. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  26. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  27. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  28. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  29. CORRECTION.
  30.  
  31. Disk-based binary search tree used to create file-based objects
  32. that reside on disk.
  33. */
  34. // ----------------------------------------------------------- // 
  35. #include "dtree.h"
  36.  
  37. void DTree::WriteHdr()
  38. {
  39.   if (!FilePtr->ReadOnly())
  40.      FilePtr->Write(&THeader, sizeof(TreeHeader), THeaderAddress);
  41. }
  42.  
  43. void DTree::ReadHdr()
  44. {
  45.   FilePtr->Read(&THeader, sizeof(TreeHeader), THeaderAddress);
  46. }
  47.  
  48. int DTree::Connect(VBDFilePtr &fp, int create, FAU FileAddress)
  49. // Connect to an already open file. If create is true,
  50. // then creating a new tree but not a new file.
  51. // The tree header is to be located at the file address. 
  52. // Returns 1 on success.
  53. {
  54.   FilePtr = fp; THeaderAddress = FileAddress;
  55.   cache.Connect(FilePtr);
  56.   if (create) {
  57.      Root = 0;
  58.      THeader.RootAddress = Root;
  59.      WriteHdr();
  60.   }
  61.   else {
  62.      ReadHdr();
  63.      Root = THeader.RootAddress;
  64.   }
  65.   if (FilePtr->IsOK()) return 1; else return 0;
  66. }
  67.  
  68. void DTree::Disconnect()
  69. // Disconnects the tree from the file.
  70. {
  71.   if (FilePtr) {
  72.      WriteHdr();         // Write out the tree header
  73.      Root.Release();     // Otherwise there might be a dangling ptr.
  74.      cache.Disconnect(); // Disconnect cache from the file
  75.      FilePtr = 0;        // Disconnect this tree from the file
  76.   }
  77. }
  78.  
  79. void DTree::Flush()
  80. {
  81.   if (FilePtr->IsOK()) {
  82.      if (FilePtr->ReadyForWriting()) {
  83.         cache.Flush();
  84.         WriteHdr();
  85.         FilePtr->Flush();
  86.      }
  87.   }
  88. }
  89.  
  90. int DTree::Create(char *FName, FAU FileAddress)
  91. // Create a new file to hold the tree. Close any file that
  92. // it may be connected to first. Returns 1 if successful
  93. // creating the file, else 0.
  94. {
  95.   Disconnect();
  96.   VBDFilePtr tmp(new VBDFile);
  97.   VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  98.   if (tmp == nul) return 0;
  99.   tmp->Create(FName, sizeof(TreeHeader));
  100.   if (!tmp->IsOK()) return 0;
  101.   return Connect(tmp, 1, FileAddress);
  102. }
  103.  
  104. int DTree::Open(char *FName, VBDFile::AccessMode mode, FAU FileAddress)
  105. // Opens an existing file to hold the tree. Close any file that
  106. // it may be connected to first. Returns 1 if successful
  107. // opening the file, else 0.
  108. {
  109.   Disconnect();
  110.   VBDFilePtr tmp(new VBDFile);
  111.   VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  112.   if (tmp == nul) return 0;
  113.   tmp->Open(FName, mode);
  114.   if (!tmp->IsOK()) return 0;
  115.   return Connect(tmp, 0, FileAddress);
  116. }
  117.  
  118. CachePointer DTree::GetMember(const DTYPE &X)
  119. // Returns pointer to node containing data X if there is
  120. // such a node in the tree,  otherwise, a 0 is returned.
  121. // Assumes DTYPE has comparison operators defined.
  122. {
  123.   CachePointer Tree = Root;
  124.   while ((__LWORD__)Tree) {
  125.     if (X == Tree->Data) break;
  126.     Tree = (X < Tree->Data) ? Tree->Left : Tree->Right;
  127.   }
  128.   return Tree;
  129. }
  130.  
  131. CachePointer DTree::SearchP(const DTYPE &X, CachePointer &p, int &side)
  132. // Returns pointer to node containing data X if there is such a
  133. // node in the tree, otherwise, a 0 is returned. Passes back
  134. // parent of node found in p, and also which side the child
  135. // occurs on. (If matching node is Tree, a 0 is returned in p.)
  136. // Assumes DTYPE has comparison operators defined.
  137. {
  138.   CachePointer Tree = Root;
  139.  
  140.   p = 0;
  141.   while ((__LWORD__)Tree) {
  142.     if (X == Tree->Data) break;
  143.     p = Tree;
  144.     if (X < Tree->Data) {
  145.        side = 0;
  146.        Tree = Tree->Left;
  147.     }
  148.     else {
  149.        side = 1;
  150.        Tree = Tree->Right;
  151.     }
  152.   }
  153.   return Tree;
  154. }
  155.  
  156. CachePointer DTree::Search(const DTYPE &X)
  157. // Returns pointer to node containing data X if there is
  158. // such a node in the tree,  otherwise, a 0 is returned.
  159. // Assumes DTYPE has comparison operators defined.
  160. {
  161.   CachePointer Tree = Root;
  162.   while ((__LWORD__)Tree) {
  163.     if (X == Tree->Data) break;
  164.     Tree = (X < Tree->Data) ? Tree->Left : Tree->Right;
  165.   }
  166.   return Tree;
  167. }
  168.  
  169. CachePointer DTree::Change(const DTYPE &A, const DTYPE &B)
  170. {
  171.   CachePointer p(cache);
  172.   int side;
  173.  
  174.   CachePointer n = SearchP(A, p, side);
  175.  
  176.   if ((__LWORD__)n == 0) return n; // Return false if object not found
  177.  
  178.   Delete(A);
  179.   new(n) TNode(B);
  180.   if ((__LWORD__)p) {
  181.     if (side) p->Right = n; else p->Left = n;
  182.     p->SetDirty(); 
  183.   }
  184.   else {
  185.     Root = n; // No parent, so this must be new Root
  186.     THeader.RootAddress = Root;
  187.      }
  188.  
  189.   return n;
  190. }
  191.  
  192. CachePointer DTree::Add(const DTYPE &X, int &existed)
  193. // Walks the tree looking for a place to insert a new node
  194. // containing X and inserts it there. If matching node
  195. // already existed, then existed is set to 1, else
  196. // existed is set to 0. Returns pointer to the new
  197. // or matching node.
  198. {
  199.   CachePointer p(cache);
  200.   int side;
  201.  
  202.   CachePointer n = SearchP(X, p, side);
  203.  
  204.   if ((__LWORD__)n == 0) { // No matching node found
  205.     new(n) TNode(X);
  206.         
  207.      if ((__LWORD__)p) {
  208.         if (side) p->Right = n; else p->Left = n;
  209.         p->SetDirty(); 
  210.      }
  211.      else {
  212.        Root = n; // No parent, so this must be new Root
  213.        THeader.RootAddress = Root;
  214.      }
  215.      existed = 0;
  216.   }
  217.   else existed = 1;
  218.  
  219.   return n;
  220. }
  221.  
  222. CachePointer DTree::ParentOfSuccessor(CachePointer Tree)
  223. // Returns parent of successor of Tree, assumed to be
  224. // a binary search tree. Successor is the Left child
  225. // of node returned, unless Tree itself is the parent.
  226. // Then the Right child is the successor. If Tree is a
  227. // leaf, a 0 is returned. Assumes Tree isn't null.
  228. {
  229.   CachePointer p(cache), q(cache);
  230.   // Go Right, then all the way Left
  231.   q = Tree->Right;
  232.   if ((__LWORD__)q) {
  233.      p = Tree;
  234.      while(q->Left) {
  235.        p = q;
  236.        q = q->Left;
  237.      }
  238.   }
  239.   return p;
  240. }
  241.  
  242. CachePointer DTree::DetachNode(CachePointer Tree, CachePointer p, int side)
  243. // Detaches node Tree with parent p from the tree. Node Tree is
  244. // the Left child if side = 0, else it's the Right child.
  245. // If p is 0, it means Tree is the Root, and that is handled
  246. // accordingly. Redundantly returns the pointer Tree. May
  247. // have to update Root pointer.
  248. {
  249.   CachePointer psucc(cache), replacement(cache);
  250.  
  251.   if ((__LWORD__)Tree) {
  252.      if (Tree->Left == 0 || Tree->Right == 0) {
  253.         // At least one child is null, so use the other
  254.         // as the replacement. (It may be null too.)
  255.       replacement = (Tree->Left) ? Tree->Left : Tree->Right;
  256.      }
  257.      else { // Neither child is null
  258.         psucc = ParentOfSuccessor(Tree); // guaranteed not null
  259.         if (psucc == Tree) { // Immediate successor
  260.            replacement = psucc->Right;
  261.         }
  262.         else {
  263.            // Detach replacement from where it is and relocate
  264.            // it to where Tree used to be.
  265.            replacement = psucc->Left;
  266.            psucc->Left = replacement->Right;
  267.            psucc->SetDirty();
  268.            replacement->Right = Tree->Right;
  269.         }
  270.         // Finish relocating replacement to go where Tree used to.
  271.         replacement->Left = Tree->Left;
  272.         replacement->SetDirty();
  273.      }
  274.      if ((__LWORD__)p) { // Fixup parent of Tree to point to replacement
  275.       if (side) p->Right = replacement; else p->Left = replacement;
  276.         p->SetDirty();
  277.      }
  278.      else {
  279.        Root = replacement; // No parent, so Tree was the Root
  280.        THeader.RootAddress = Root;
  281.      }
  282.   }
  283.   return Tree;
  284. }
  285.  
  286. CachePointer DTree::Detach(const DTYPE &X)
  287. // Finds the node with data matching X, detaches
  288. // that node from the tree, and returns a pointer
  289. // to the node.
  290. {
  291.   int side;
  292.   CachePointer p(cache);
  293.   CachePointer Tree = SearchP(X, p, side);
  294.   return DetachNode(Tree, p, side);
  295. }
  296.  
  297. int DTree::Delete(const DTYPE &X)
  298. // Deletes node matching X from the tree. Returns
  299. // 1 if node actually found, else 0.
  300. {
  301.   CachePointer n = Detach(X);
  302.   int rv = (__LWORD__)n != 0;
  303.   n.Delete();
  304.   return rv;
  305. }
  306. // ----------------------------------------------------------- //
  307. // ------------------------------- //
  308. // --------- End of File --------- //
  309. // ------------------------------- //
  310.