// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: dtree.cpp 
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer   
// File Creation Date: 02/07/1997  
// Date Last Modified: 03/17/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ------------- Program Description and Details ------------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

Disk-based binary search tree used to create file-based objects
that reside on disk.
*/
// ----------------------------------------------------------- // 
#include "dtree.h"

void DTree::WriteHdr()
{
  if (!FilePtr->ReadOnly())
     FilePtr->Write(&THeader, sizeof(TreeHeader), THeaderAddress);
}

void DTree::ReadHdr()
{
  FilePtr->Read(&THeader, sizeof(TreeHeader), THeaderAddress);
}

int DTree::Connect(VBDFilePtr &fp, int create, FAU FileAddress)
// Connect to an already open file. If create is true,
// then creating a new tree but not a new file.
// The tree header is to be located at the file address. 
// Returns 1 on success.
{
  FilePtr = fp; THeaderAddress = FileAddress;
  cache.Connect(FilePtr);
  if (create) {
     Root = 0;
     THeader.RootAddress = Root;
     WriteHdr();
  }
  else {
     ReadHdr();
     Root = THeader.RootAddress;
  }
  if (FilePtr->IsOK()) return 1; else return 0;
}

void DTree::Disconnect()
// Disconnects the tree from the file.
{
  if (FilePtr) {
     WriteHdr();         // Write out the tree header
     Root.Release();     // Otherwise there might be a dangling ptr.
     cache.Disconnect(); // Disconnect cache from the file
     FilePtr = 0;        // Disconnect this tree from the file
  }
}

void DTree::Flush()
{
  if (FilePtr->IsOK()) {
     if (FilePtr->ReadyForWriting()) {
        cache.Flush();
        WriteHdr();
        FilePtr->Flush();
     }
  }
}

int DTree::Create(char *FName, FAU FileAddress)
// Create a new file to hold the tree. Close any file that
// it may be connected to first. Returns 1 if successful
// creating the file, else 0.
{
  Disconnect();
  VBDFilePtr tmp(new VBDFile);
  VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  if (tmp == nul) return 0;
  tmp->Create(FName, sizeof(TreeHeader));
  if (!tmp->IsOK()) return 0;
  return Connect(tmp, 1, FileAddress);
}

int DTree::Open(char *FName, VBDFile::AccessMode mode, FAU FileAddress)
// Opens an existing file to hold the tree. Close any file that
// it may be connected to first. Returns 1 if successful
// opening the file, else 0.
{
  Disconnect();
  VBDFilePtr tmp(new VBDFile);
  VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  if (tmp == nul) return 0;
  tmp->Open(FName, mode);
  if (!tmp->IsOK()) return 0;
  return Connect(tmp, 0, FileAddress);
}

CachePointer DTree::GetMember(const DTYPE &X)
// Returns pointer to node containing data X if there is
// such a node in the tree,  otherwise, a 0 is returned.
// Assumes DTYPE has comparison operators defined.
{
  CachePointer Tree = Root;
  while ((__LWORD__)Tree) {
    if (X == Tree->Data) break;
    Tree = (X < Tree->Data) ? Tree->Left : Tree->Right;
  }
  return Tree;
}

CachePointer DTree::SearchP(const DTYPE &X, CachePointer &p, int &side)
// Returns pointer to node containing data X if there is such a
// node in the tree, otherwise, a 0 is returned. Passes back
// parent of node found in p, and also which side the child
// occurs on. (If matching node is Tree, a 0 is returned in p.)
// Assumes DTYPE has comparison operators defined.
{
  CachePointer Tree = Root;

  p = 0;
  while ((__LWORD__)Tree) {
    if (X == Tree->Data) break;
    p = Tree;
    if (X < Tree->Data) {
       side = 0;
       Tree = Tree->Left;
    }
    else {
       side = 1;
       Tree = Tree->Right;
    }
  }
  return Tree;
}

CachePointer DTree::Search(const DTYPE &X)
// Returns pointer to node containing data X if there is
// such a node in the tree,  otherwise, a 0 is returned.
// Assumes DTYPE has comparison operators defined.
{
  CachePointer Tree = Root;
  while ((__LWORD__)Tree) {
    if (X == Tree->Data) break;
    Tree = (X < Tree->Data) ? Tree->Left : Tree->Right;
  }
  return Tree;
}

CachePointer DTree::Change(const DTYPE &A, const DTYPE &B)
{
  CachePointer p(cache);
  int side;

  CachePointer n = SearchP(A, p, side);

  if ((__LWORD__)n == 0) return n; // Return false if object not found

  Delete(A);
  new(n) TNode(B);
  if ((__LWORD__)p) {
    if (side) p->Right = n; else p->Left = n;
    p->SetDirty(); 
  }
  else {
    Root = n; // No parent, so this must be new Root
    THeader.RootAddress = Root;
     }

  return n;
}

CachePointer DTree::Add(const DTYPE &X, int &existed)
// Walks the tree looking for a place to insert a new node
// containing X and inserts it there. If matching node
// already existed, then existed is set to 1, else
// existed is set to 0. Returns pointer to the new
// or matching node.
{
  CachePointer p(cache);
  int side;

  CachePointer n = SearchP(X, p, side);

  if ((__LWORD__)n == 0) { // No matching node found
    new(n) TNode(X);
        
     if ((__LWORD__)p) {
        if (side) p->Right = n; else p->Left = n;
        p->SetDirty(); 
     }
     else {
       Root = n; // No parent, so this must be new Root
       THeader.RootAddress = Root;
     }
     existed = 0;
  }
  else existed = 1;

  return n;
}

CachePointer DTree::ParentOfSuccessor(CachePointer Tree)
// Returns parent of successor of Tree, assumed to be
// a binary search tree. Successor is the Left child
// of node returned, unless Tree itself is the parent.
// Then the Right child is the successor. If Tree is a
// leaf, a 0 is returned. Assumes Tree isn't null.
{
  CachePointer p(cache), q(cache);
  // Go Right, then all the way Left
  q = Tree->Right;
  if ((__LWORD__)q) {
     p = Tree;
     while(q->Left) {
       p = q;
       q = q->Left;
     }
  }
  return p;
}

CachePointer DTree::DetachNode(CachePointer Tree, CachePointer p, int side)
// Detaches node Tree with parent p from the tree. Node Tree is
// the Left child if side = 0, else it's the Right child.
// If p is 0, it means Tree is the Root, and that is handled
// accordingly. Redundantly returns the pointer Tree. May
// have to update Root pointer.
{
  CachePointer psucc(cache), replacement(cache);

  if ((__LWORD__)Tree) {
     if (Tree->Left == 0 || Tree->Right == 0) {
        // At least one child is null, so use the other
        // as the replacement. (It may be null too.)
      replacement = (Tree->Left) ? Tree->Left : Tree->Right;
     }
     else { // Neither child is null
        psucc = ParentOfSuccessor(Tree); // guaranteed not null
        if (psucc == Tree) { // Immediate successor
           replacement = psucc->Right;
        }
        else {
           // Detach replacement from where it is and relocate
           // it to where Tree used to be.
           replacement = psucc->Left;
           psucc->Left = replacement->Right;
           psucc->SetDirty();
           replacement->Right = Tree->Right;
        }
        // Finish relocating replacement to go where Tree used to.
        replacement->Left = Tree->Left;
        replacement->SetDirty();
     }
     if ((__LWORD__)p) { // Fixup parent of Tree to point to replacement
      if (side) p->Right = replacement; else p->Left = replacement;
        p->SetDirty();
     }
     else {
       Root = replacement; // No parent, so Tree was the Root
       THeader.RootAddress = Root;
     }
  }
  return Tree;
}

CachePointer DTree::Detach(const DTYPE &X)
// Finds the node with data matching X, detaches
// that node from the tree, and returns a pointer
// to the node.
{
  int side;
  CachePointer p(cache);
  CachePointer Tree = SearchP(X, p, side);
  return DetachNode(Tree, p, side);
}

int DTree::Delete(const DTYPE &X)
// Deletes node matching X from the tree. Returns
// 1 if node actually found, else 0.
{
  CachePointer n = Detach(X);
  int rv = (__LWORD__)n != 0;
  n.Delete();
  return rv;
}
// ----------------------------------------------------------- //
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
