home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / APPS / hl10osrc.zoo / Include / vBTree.h < prev    next >
Text File  |  2009-11-06  |  5KB  |  161 lines
  1. /* -*- Mode: C -*- */
  2. /* vBTree.h - virtual BTrees - a modification of the BTree class
  3.  *          described in "C++, a guide for C programmers", by
  4.  *          Sharam Hekmatpour, (c) 1990 by Prentice Hall of
  5.  *          Australia Pty Ltd.
  6.  *
  7.  * Created by Robert Heller on Fri Dec  6 20:55:06 1991
  8.  *
  9.  * ------------------------------------------------------------------
  10.  * Home Libarian by Deepwoods Software
  11.  * Common Header Files
  12.  * ------------------------------------------------------------------
  13.  * Modification History:
  14.  * ------------------------------------------------------------------
  15.  * Contents:
  16.  * ------------------------------------------------------------------
  17.  * 
  18.  * 
  19.  * Copyright (c) 1991,1992 by Robert heller (D/B/A Deepwoods Software)
  20.  *        All Rights Reserved
  21.  * 
  22.  */
  23. #ifndef _VBTREE_
  24. #define _VBTREE_
  25. #include <common.h>
  26. #include <vm.h>
  27.  
  28. // This class implements a Library Card Catalog as a group a four
  29. // (virtual) BTrees of Order 10.
  30. // The nodes of the BTrees are handled using the virtual memory management
  31. // of the PageFile class.
  32. class vBTree : public PageFile {
  33.     OpenStatus openstat;    // open status
  34.     HomeBlock homeblock;    // home (header) block
  35.     Boolean homedirty;    // has the home block been modified?
  36.     Item* buf;        // scratch buffer
  37.     DiskPage LastSearchPage; // Last page searched.  Set by SearchAux,
  38.                 // used and updated by SearchAgain
  39.     Key LastSearchKey;    // Last search key.
  40.     int LastSearchIdx;    // Last search index
  41.     LSType LastSearchType;    // Last search type
  42.     ErrFun errFun;        // Error hander function
  43.     DiskPage NewPage    (); // Get a new empty page
  44.     void FreePage        (DiskPage page); // Free up a page
  45.     // Searching functions
  46.     Boolean SearchAux    (DiskPage dtree,Key key,CoreItem* item);
  47.     Boolean SearchAgain    (CoreItem* item);
  48.     Boolean BinarySearch    (Page* node,Key key,int* idx);
  49.     // Insertion function
  50.     Item* InsertAux        (Item* item,DiskPage dnode);
  51.     // Deletion functions
  52.     void DeleteAux1        (Key key,DiskPage dnode,Boolean* underflow);
  53.     void DeleteAux2        (DiskPage dparent,DiskPage dnode,int idx,
  54.                  Boolean* underflow);
  55.     void Underflow        (DiskPage dnode,DiskPage dchild,int idx,
  56.                  Boolean* underflow);
  57.     // Parentage adjustment
  58.     void AdjustParent    (DiskPage dparent);
  59.     // Item vector hacking
  60.     int CopyItems        (Item* src,Item* dest,int count);
  61.     int InsertItem        (Item* item,Item* items,int idx,int size);
  62.     int DeleteItem        (Item* items,int idx,int size);
  63.     // Raw tree print function
  64.     void PrintAux        (DiskPage node,int margin);
  65.     // Page counter
  66.     int CountPagesAux    (DiskPage node);
  67.     // Key compare function
  68.     int CompareKeys        (Key keypat, Key key);
  69.     // Tree traversal function
  70.     void TravAux        (DiskPage node,TravFunc tfun,int level);
  71. public:
  72.     OpenStatus OpenStat()    {return openstat;}
  73.     // Error function reference operator
  74.     ErrFun& ErrorFun ()    {return errFun;}
  75.     // Error handler
  76.     void Error    (ErrKind err,const char* msg);
  77.     // Open file function
  78.     OpenStatus open        (char *filename,OpenMode mode = ReadOnly,
  79.                  int nfree = MaxNumFree / 10);
  80.     // Constructors
  81.          vBTree        ();
  82.          vBTree        (char *filename,OpenMode mode = ReadOnly,
  83.                  int nfree = MaxNumFree / 10);
  84.     // Destructor
  85.         ~vBTree        ();
  86.     // Search Id tree
  87.     Boolean SearchId    (Key key,CoreItem* item)
  88.                     {LastSearchType = id;
  89.                      LastSearchIdx = -1;
  90.                      return(SearchAux(homeblock.IdRoot,key,
  91.                               item));}
  92.     Boolean SearchIdAgain    (CoreItem* item)
  93.                     {return(LastSearchType == id && 
  94.                         SearchAgain(item));}
  95.     // Search Title tree
  96.     Boolean SearchTitle    (Key key,CoreItem* item)
  97.                     {LastSearchType = title;
  98.                      LastSearchIdx = -1;
  99.                      return(SearchAux(homeblock.TitleRoot,
  100.                               key,item));}
  101.     Boolean SearchTitleAgain (CoreItem* item)
  102.                     {return(LastSearchType == title &&
  103.                         SearchAgain(item));}
  104.     // Search Author tree
  105.     Boolean SearchAuthor    (Key key,CoreItem* item)
  106.                     {LastSearchType = author;
  107.                      LastSearchIdx = -1;
  108.                      return(SearchAux(homeblock.AuthorRoot,
  109.                               key,item));}
  110.     Boolean SearchAuthorAgain (CoreItem* item)
  111.                     {return(LastSearchType == author &&
  112.                         SearchAgain(item));}
  113.     // Search Subject tree
  114.     Boolean SearchSubj    (Key key,CoreItem* item)
  115.                     {LastSearchType = subj;
  116.                      LastSearchIdx = -1;
  117.                      return(SearchAux(homeblock.SubjRoot,
  118.                               key,item));}
  119.     Boolean SearchSubjAgain    (CoreItem* item)
  120.                     {return(LastSearchType == subj &&
  121.                         SearchAgain(item));}
  122.     // Insertion
  123.     DiskRecord InsertId    (Key key,Record* newdata);
  124.     DiskRecord InsertTitle    (Key key,Record* newdata);
  125.     DiskRecord InsertAuthor    (Key key,Record* newdata);
  126.     DiskRecord InsertSubj    (Key key,Record* newdata);
  127.     // Deletion
  128.     void DeleteId        (Key key);
  129.     void DeleteTitle    (Key key);
  130.     void DeleteAuthor    (Key key);
  131.     void DeleteSubj        (Key key);
  132.     // Raw printing
  133.     void Print        (int margin=0)
  134.                 {
  135.                     PrintAux(homeblock.IdRoot,margin);
  136.                     PrintAux(homeblock.TitleRoot,margin);
  137.                     PrintAux(homeblock.AuthorRoot,margin);
  138.                     PrintAux(homeblock.SubjRoot,margin);
  139.                 }
  140.     // Page counter
  141.     int CountPages        ()
  142.                 {
  143.                     return (CountPagesAux(homeblock.IdRoot) +
  144.                         CountPagesAux(homeblock.TitleRoot) +
  145.                         CountPagesAux(homeblock.AuthorRoot) +
  146.                         CountPagesAux(homeblock.SubjRoot));
  147.                 }
  148.     // Tree traversal
  149.     void TraverseId        (TravFunc tfun)
  150.                     {TravAux(homeblock.IdRoot,tfun,0);}
  151.     void TraverseAuthor    (TravFunc tfun)
  152.                     {TravAux(homeblock.AuthorRoot,tfun,0);}
  153.     void TraverseTitle    (TravFunc tfun)
  154.                     {TravAux(homeblock.TitleRoot,tfun,0);}
  155.     void TraverseSubj    (TravFunc tfun)
  156.                     {TravAux(homeblock.SubjRoot,tfun,0);}
  157. };
  158.  
  159. #endif
  160.  
  161.