home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / L0 < prev    next >
Encoding:
Text File  |  1992-06-07  |  3.6 KB  |  105 lines
  1. #ifndef __RWBTREE_H__
  2. #define __RWBTREE_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWBTree -- in memory B-Tree.
  7.  *
  8.  * $Header:   E:/vcs/rw/btree.h_v   1.3   04 Mar 1992 09:07:24   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave 
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  * Voice: (503) 754-3010    FAX: (503) 757-6650
  16.  *
  17.  * Copyright (C) 1989, 1990, 1991. This software is subject to copyright 
  18.  * protection under the laws of the United States and other countries.
  19.  *
  20.  ***************************************************************************
  21.  *
  22.  * $Log:   E:/vcs/rw/btree.h_v  $
  23.  * 
  24.  *    Rev 1.3   04 Mar 1992 09:07:24   KEFFER
  25.  * Changed nil to rwnil
  26.  * 
  27.  *    Rev 1.2   18 Feb 1992 09:54:10   KEFFER
  28.  * 
  29.  *    Rev 1.1   28 Oct 1991 09:08:08   keffer
  30.  * Changed inclusions to <rw/xxx.h>
  31.  * 
  32.  *    Rev 1.0   28 Jul 1991 08:12:46   keffer
  33.  * Tools.h++ V4.0.5 PVCS baseline version
  34.  *
  35.  */
  36.  
  37. #include "rw/colclass.h"
  38. #include "rw/mempool.h"
  39.  
  40. #ifdef RDEBUG
  41. static const unsigned order         = 2;
  42. static const unsigned twoTimesOrder = 2*order;
  43. #else
  44. static const unsigned order         = 50;
  45. static const unsigned twoTimesOrder = 2*order;
  46. #endif
  47.  
  48.  
  49. class RWExport RWBTreeNode : public RWMemoryPool {
  50. friend class RWExport RWBTree;
  51.   typedef RWCollectable*     keyP;
  52.  
  53.   RWBTreeNode();                    // Private constructors.
  54.   RWBTreeNode(RWCollectable*);
  55.   unsigned    counter;            // How many of the [twoTimesOrder] 
  56.                         //       fields are used.
  57.   keyP        key[twoTimesOrder];        // Array of pointers keys.
  58.   RWBTreeNode*    next[twoTimesOrder+1];        // Array of pointers to children nodes.
  59.   int        binarySearch(const RWCollectable*) const;     // Binary search for insertion.
  60.   void        initialize();
  61.   void        siz(unsigned&) const;        // Count items in self & children.
  62.   RWBoolean    subSetOf(const RWBTree& bt) const;
  63. };
  64.  
  65. class RWExport RWBTree : public RWCollection {
  66.   RWBTreeNode*        root;            // root = first node in tree.
  67.   RWCollectable*     tempKey;        // Place holder to handle node over- and underflow
  68.   RWBTreeNode*        tempNode;        // Place holder to handle node over- and underflow
  69. protected:
  70.   void            apl(RWBTreeNode*, RWapplyCollectable, void*);    // Apply to all children
  71.   void            del(RWBTreeNode*);                // Delete all children.
  72.   int            ins(RWCollectable* a, RWBTreeNode*);        // Insert a in tree.
  73.   int            rem(const RWCollectable* a, RWBTreeNode*, RWCollectable*&); // Remove a
  74. public:
  75.   RWBTree();
  76.   ~RWBTree();
  77.   RWBTree(const RWBTree&);
  78.  
  79.   void            operator=(const RWBTree&);
  80.   RWBoolean        operator<=(const RWBTree& bt) const; // Subset of bt
  81.   RWBoolean        operator==(const RWBTree& bt) const;
  82.  
  83. // Special member function to return the height of the B-tree.
  84.   unsigned        height() const;
  85.  
  86. /************ Standard Collection classes functions **************/
  87.   virtual void        apply(RWapplyCollectable, void*);
  88.   virtual void        clear();
  89. //virtual void        clearAndDestroy();
  90. //virtual RWBoolean    contains(const RWCollectable*) const;
  91.   virtual unsigned    entries() const;        // Total entries
  92.   virtual RWCollectable*    find(const RWCollectable*) const;
  93.   virtual RWCollectable*    insert(RWCollectable*);
  94.   virtual RWBoolean    isEqual(const RWCollectable*) const;
  95.   virtual ClassID    isA() const {return __RWBTREE;}
  96.   virtual RWCollectable*    newSpecies() const;
  97.   virtual RWBoolean    isEmpty() const {return root==rwnil;}
  98.   virtual unsigned    occurrencesOf(const RWCollectable*) const;
  99.   virtual RWCollectable*    remove(const RWCollectable*);
  100. //virtual void        removeAndDestroy(const RWCollectable*);
  101. };    
  102.              
  103. pragma pop_align_members();
  104. #endif /* __RWBTREE_H__ */
  105.