// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Header File Name: dtree.h 
// 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
// ----------------------------------------------------------- // 
// ---------- Include File 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.
*/
// ----------------------------------------------------------- //   
#ifndef __DTREE_HPP
#define __DTREE_HPP

// NOTE: To avoid portablity problems with template classes, enable
// the __NOT_USING_TEMPLATE_CLASS__ macro and directly code the
// Bucket class, Cache class, and the CachePtr class for the data
// type that will be used.

// Default to using template class
#ifndef __NOT_USING_TEMPLATE_CLASS__
#define __USING_TEMPLATE_CLASS__
#endif

#ifdef __USING_TEMPLATE_CLASS__
#include "tnode.h"
#endif

#ifdef __NOT_USING_TEMPLATE_CLASS__
#include "cacheptr.h"
typedef CachePtr CachePointer; // Pointer to cache
#endif

// (T)ree (H)eader
struct TreeHeader
{
  FAU RootAddress;
}; 

// DTree class (Disk-based binary search Tree)
class DTree
{
public:
  DTree(int cache_sz = 8) : FilePtr(0), cache(cache_sz), Root(cache) { }
  ~DTree() { Disconnect(); }

public:
  int Open(char *FName, VBDFile::AccessMode mode,
	   FAU FileAddress=sizeof(FileHeader));
  
  int Connect(VBDFilePtr &fp, int create,
	      FAU FileAddress = sizeof(FileHeader));
  
  void Disconnect();
  int Create(char *FName, FAU FileAddress = sizeof(FileHeader));
  void Flush();
  void Close() { Disconnect(); }
  CachePointer GetMember(const DTYPE &X);
  CachePointer Add(const DTYPE &X, int &existed);
  CachePointer Change(const DTYPE &A, const DTYPE &B);
  CachePointer Search(const DTYPE &X);
  CachePointer Detach(const DTYPE &X);
  int Delete(const DTYPE &X);
  CachePointer GetRoot() { return Root; }

#ifdef __USING_TEMPLATE_CLASS__
  Cache<TNode> GetCache() { return cache; }
#endif

#ifdef __NOT_USING_TEMPLATE_CLASS__
  Cache GetCache() { return cache; }
#endif

protected:
  void WriteHdr();
  void ReadHdr();
  CachePointer ParentOfSuccessor(CachePointer Tree);
  CachePointer SearchP(const DTYPE &X, CachePointer &p, int &side);
  CachePointer DetachNode(CachePointer Tree, CachePointer p, int side);

protected:
  VBDFilePtr FilePtr; // File manager for the tree
  TreeHeader THeader; // Tree header
  FAU THeaderAddress; // Where the tree header is stored

public:
  CachePointer Root;

#ifdef __USING_TEMPLATE_CLASS__
  Cache<TNode> cache;
#endif

#ifdef __NOT_USING_TEMPLATE_CLASS__
  Cache cache;
#endif
};

#endif  // __DTREE_HPP //
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
