home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c063 / 1.ddi / CLASSINC.ZIP / BTREE.H < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-18  |  12.0 KB  |  468 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BTREE.H                                                               */
  4. /*                                                                        */
  5. /*  Copyright Borland International 1991                                  */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( __BTREE_H )
  11. #define __BTREE_H
  12.  
  13. #if !defined( __CHECKS_H )
  14. #include <Checks.h>
  15. #endif  // __CHECKS_H
  16.  
  17. #if !defined( __SORTABLE_H )
  18. #include <Sortable.h>
  19. #endif  // __SORTABLE_H
  20.  
  21. #if !defined( __COLLECT_H )
  22. #include <Collect.h>
  23. #endif  // __COLLECT_H
  24.  
  25. _CLASSDEF(Node)
  26. _CLASSDEF(Item)
  27. _CLASSDEF(Btree)
  28. _CLASSDEF(InnerNode)
  29. _CLASSDEF(LeafNode)
  30. _CLASSDEF(BtreeIterator)
  31.  
  32. class _CLASSTYPE Node
  33. {
  34.  
  35. public:
  36.  
  37.     /*dbg*/int debugKey; // !*!*!*! not for distribution!
  38.  
  39.     Node( int b, InnerNode _FAR * P, Btree _FAR * T = 0 );
  40.     virtual ~Node();
  41.  
  42.     virtual void add( Sortable _FAR *, int ) = 0;
  43.     virtual void remove( int ) = 0;
  44.  
  45.     virtual Object _FAR & operator[]( long i ) const = 0;
  46.     virtual Object _FAR & found( Sortable _FAR *,
  47.                                  Node _FAR * _FAR *,
  48.                                  int _FAR *
  49.                                ) = 0;
  50.  
  51.     virtual long findRank( Sortable _FAR * ) const = 0;
  52.     virtual long nofKeys() const = 0; // # keys in or below this node
  53.  
  54.     virtual LeafNode _FAR * firstLeafNode() = 0;
  55.     virtual LeafNode _FAR * lastLeafNode() = 0;
  56.  
  57.     virtual void split() = 0;
  58.  
  59.     virtual void printOn(ostream _FAR &) const = 0;
  60.     friend ostream _FAR & operator <<( ostream _FAR &, const Node _FAR & );
  61.  
  62.     int last;   // for inner node 1 <= last <= InnerMaxIndex
  63.                 // for leaf node  1 <= last <= LeafMaxIndex
  64.                 // (last==0 only temporarily while the tree is being
  65.                 //  updated)
  66.     InnerNode _FAR *parent; // a parent is always an inner node (or 0 for the root)
  67.     Btree _FAR *tree;   // the tree of which this node is a part
  68.     int isLeaf; // run-time type flag
  69.  
  70. };
  71.  
  72. class _CLASSTYPE Item
  73. {
  74.  
  75. public:
  76.  
  77.     Item();
  78.     Item(Node _FAR * n, Sortable _FAR * o);
  79.     Item(Sortable _FAR * o, Node _FAR * n);
  80.     ~Item();
  81.     // data
  82.     long nofKeysInTree; // tree can have more than 32K elements
  83.     Sortable _FAR *key;
  84.     Node _FAR *tree;
  85.  
  86. };
  87.  
  88. class _CLASSTYPE InnerNode : public Node
  89. {
  90.  
  91. public:
  92.  
  93.     InnerNode( InnerNode _FAR *, Btree _FAR * = 0 );
  94.     InnerNode( InnerNode _FAR *, Btree _FAR *, Node _FAR * );
  95.     ~InnerNode();
  96.  
  97.     void add( Sortable _FAR *, int );
  98.     void add( Item _FAR &, int );
  99.     void add( int, Sortable _FAR *, Node _FAR * );
  100.     void addElt( Item _FAR &, int );
  101.     void addElt( int, Sortable _FAR *, Node _FAR * );
  102.     void remove( int );
  103.     void removeItem( int );
  104.  
  105.     Object _FAR & operator[]( long i ) const;
  106.     Object _FAR & found( Sortable _FAR *, Node _FAR * _FAR *, int _FAR * );
  107.  
  108.     long nofKeys( int i ) const;
  109.     void setTree( int i, Node _FAR * node );
  110.     void setKey( int i, Sortable _FAR * obj );
  111.     void setItem( int i, Item _FAR & itm );
  112.     void setItem( int i, Sortable _FAR * obj, Node _FAR * node );
  113.     long getNofKeys( int i ) const;
  114.     void setNofKeys( int i, long r );
  115.     long incNofKeys( int i, long N=1 );
  116.     long decNofKeys( int i, long N=1 );
  117.     long findRank( Sortable _FAR * ) const;
  118.     long findRank_bu( const Node _FAR * ) const;
  119.     Node _FAR *getTree( int i ) const;
  120.     Sortable _FAR *getKey( int i ) const;
  121.     Item _FAR & getItem( int i ) const;
  122.  
  123.  
  124.     int  indexOf( const Node _FAR * ) const;
  125.     void incrNofKeys( Node _FAR * np );
  126.     void decrNofKeys( Node _FAR * np );
  127.     long nofKeys() const;
  128.  
  129.     LeafNode _FAR *firstLeafNode();
  130.     LeafNode _FAR *lastLeafNode();
  131.  
  132.     void informParent();
  133.  
  134.     void split();
  135.     void splitWith( InnerNode _FAR *, int );
  136.     void mergeWithRight( InnerNode _FAR *, int );
  137.     void balanceWithLeft( InnerNode _FAR *, int );
  138.     void balanceWithRight( InnerNode _FAR *, int );
  139.     void balanceWith( InnerNode _FAR *, int );
  140.     void pushLeft( int cnt, InnerNode _FAR * leftsib, int parentIdx );
  141.     void pushRight( int cnt, InnerNode _FAR * rightsib, int parentIdx );
  142.     void appendFrom( InnerNode _FAR *, int, int );
  143.     void append( Sortable _FAR *, Node _FAR * );
  144.     void append( Item _FAR & );
  145.     void shiftLeft( int );
  146.  
  147.     int Psize() const;
  148.     int Vsize() const;
  149.     int maxIndex() const;
  150.     int maxPsize() const;
  151.  
  152.     void printOn(ostream&) const;
  153.  
  154.     int isFull() const;
  155.     void isFull( Node _FAR * );
  156.     int isAlmostFull() const;
  157.     int isLow() const;
  158.     void isLow( Node _FAR * );
  159.  
  160. private:
  161.  
  162.     Item _FAR *item; // actually items[maxIndex()+1] is desired
  163.  
  164. };
  165.  
  166. class _CLASSTYPE LeafNode : public Node
  167. {
  168.  
  169. public:
  170.  
  171.     LeafNode(InnerNode _FAR * P, Sortable _FAR * obj = 0, Btree _FAR * T = 0 );
  172.     ~LeafNode();
  173.  
  174.     void add( Sortable _FAR * , int );
  175.     void remove( int i );
  176.     void removeItem( int i);
  177.  
  178.     Object _FAR & operator[]( long i ) const;
  179.     Object _FAR & found( Sortable _FAR *, Node _FAR * _FAR *, int _FAR * );
  180.  
  181.     long nofKeys( int i ) const;
  182.     long nofKeys() const;
  183.     long findRank( Sortable _FAR * ) const;
  184.     Sortable _FAR *getKey( int idx ) { return item[idx]; }
  185.     void setKey( int idx, Sortable _FAR * obj ) { item[idx] = obj; }
  186.  
  187.     int indexOf( const Sortable _FAR * ) const;
  188.  
  189.     LeafNode _FAR *firstLeafNode();
  190.     LeafNode _FAR *lastLeafNode();
  191.  
  192.     void split();
  193.     void splitWith( LeafNode _FAR *, int );
  194.     void mergeWithRight( LeafNode _FAR *, int );
  195.     void balanceWithLeft( LeafNode _FAR *, int );
  196.     void balanceWithRight( LeafNode _FAR *, int );
  197.     void balanceWith( LeafNode _FAR *, int );
  198.     void pushLeft( int cnt, LeafNode _FAR *, int parentIndex );
  199.     void pushRight( int cnt, LeafNode _FAR *, int parentIndex );
  200.     void appendFrom( LeafNode _FAR *, int, int );
  201.     void append( Sortable _FAR * );
  202.     void shiftLeft ( int );
  203.  
  204.     int Psize() const;
  205.     int Vsize() const;
  206.     int maxIndex() const;
  207.     int maxPsize() const;
  208.  
  209.     void printOn(ostream _FAR &) const;
  210.  
  211.     int isFull() const;
  212.     int isAlmostFull() const;
  213.     int isLow() const;
  214.  
  215.     Sortable _FAR * _FAR *item; // actually Sortable* item[maxIndex()+1] is desired
  216.  
  217. };
  218.  
  219. class _CLASSTYPE Btree : public Collection
  220. {
  221.  
  222. public:
  223.  
  224.     Btree( int ordern = 3 );//-create a Btree of order n
  225.     ~Btree();
  226.  
  227.     void add( Object _FAR & );
  228.     void detach( Object _FAR &, DeleteType = NoDelete );
  229.     void flush( DeleteType = DefDelete );
  230.     virtual int hasMember( Object _FAR & ) const;
  231.     virtual Object _FAR & findMember( Object _FAR & ) const;
  232.  
  233.     virtual int isEmpty() const { return itemsInContainer == 0; }
  234.     virtual countType getItemsInContainer() const { return itemsInContainer; }
  235.  
  236.     virtual classType isA() const { return btreeClass; }
  237.     virtual char _FAR *nameOf() const { return "Btree"; }
  238.     virtual int isEqual( const Object _FAR & ) const;
  239.     virtual void printOn( ostream _FAR & ) const;
  240.     virtual ContainerIterator _FAR & initIterator() const;
  241.  
  242.  
  243.  
  244.     int order();
  245.     Object _FAR & operator[]( long i ) const;
  246.     long rank( const Object _FAR & ) const;
  247.  
  248. protected:
  249.  
  250.     void incrNofKeys() { itemsInContainer++; }
  251.     void decrNofKeys() { itemsInContainer--; }
  252.  
  253.     long i_add( const Object _FAR & );
  254.          //-add the object to the tree; return the index
  255.          // in the tree at which the object was inserted
  256.          // (C++ doesn't allow signatures
  257.          // to differ in only the return value).
  258.          // NOTE: other insertions and deletions may
  259.          // change this object's index.
  260. private:
  261.  
  262.     int Order;          //-the order of the tree (should be > 2)
  263.     int Order2;         //-always == order*2+1 (assumes a memory access
  264.                         // is cheaper than a multiply and increment by one
  265.     int Inner_LowWaterMark;
  266.     int Leaf_LowWaterMark;
  267.     int Inner_MaxIndex;
  268.     int Leaf_MaxIndex;
  269.  
  270.     Node _FAR *root;
  271.  
  272.     void finishInit(int);
  273.     void rootIsFull();   // called when the root node is full
  274.     void rootIsEmpty();  // called when root is empty
  275.  
  276.     unsigned itemsInContainer;
  277.  
  278.     friend Node;
  279.     friend InnerNode;
  280.     friend LeafNode;
  281.  
  282. };
  283.  
  284.  
  285. inline Node _FAR *InnerNode::getTree( int i ) const
  286. {
  287.     return item[i].tree;
  288. }
  289.  
  290. inline Sortable _FAR * InnerNode::getKey( int i ) const
  291. {
  292.     return item[i].key;
  293. }
  294.  
  295. inline Item _FAR & InnerNode::getItem( int i ) const
  296. {
  297.     return item[i];
  298. }
  299.  
  300. inline void InnerNode::setTree( int i, Node _FAR * node )
  301. {
  302.     item[i].tree = node;
  303.     node->parent = this;
  304. }
  305.  
  306. inline void InnerNode::setKey( int i, Sortable _FAR * obj )
  307. {
  308.     item[i].key = obj;
  309. }
  310.  
  311. inline void InnerNode::setItem( int i, Item _FAR & itm )
  312. {
  313.     item[i] = itm;
  314.     itm.tree->parent = this;
  315. }
  316.  
  317. inline void InnerNode::setItem( int i, Sortable _FAR * obj, Node _FAR * node )
  318. {
  319.     setTree(i, node);
  320.     setKey(i, obj);
  321. }
  322.  
  323. inline long InnerNode::getNofKeys( int i ) const
  324. {
  325.     PRECONDITION( i >= 0 && i <= last );
  326.     return item[i].nofKeysInTree;
  327. }
  328.  
  329. inline void InnerNode::setNofKeys( int i, long r )
  330. {
  331.     item[i].nofKeysInTree = r;
  332. }
  333.  
  334. inline long InnerNode::incNofKeys( int i, long N )
  335. {
  336.     return ( item[i].nofKeysInTree += N );
  337. }
  338.  
  339. inline long InnerNode::decNofKeys( int i, long N )
  340. {
  341.     return ( item[i].nofKeysInTree -= N );
  342. }
  343.  
  344. inline long InnerNode::nofKeys( int i ) const
  345. {
  346.     return getNofKeys(i);
  347. }
  348.  
  349. inline int InnerNode::Psize() const
  350. {
  351.     return last;
  352. }
  353.  
  354. inline int InnerNode::Vsize() const
  355. {
  356.     PRECONDITION( parent != 0 && parent->getTree(0) != (Node _FAR *)this );
  357.     return Psize()+1;
  358. }
  359.  
  360. inline int InnerNode::maxIndex() const
  361. {
  362.     return tree->Inner_MaxIndex;
  363. }
  364.  
  365. inline int InnerNode::maxPsize() const
  366. {
  367.     return tree->Inner_MaxIndex;
  368. }
  369.  
  370. inline int InnerNode::isFull() const
  371. {
  372.     return last == maxIndex();
  373. }
  374.  
  375. inline int InnerNode::isAlmostFull() const
  376. {
  377.     return last >= maxIndex() - 1;
  378. }
  379.  
  380. inline int InnerNode::isLow() const
  381. {
  382.     return last < tree->Inner_LowWaterMark;
  383. }
  384.  
  385. inline void LeafNode::removeItem( int i)
  386. {
  387.     remove(i);
  388. }
  389.  
  390. inline Object _FAR & LeafNode::operator[]( long i ) const
  391. {
  392.     PRECONDITION( i >=0 && i <= last );
  393.     return *((Object _FAR *)item[(int)i]);    // CHECK - cast to int OK?
  394. }
  395.  
  396. inline int LeafNode::Psize() const
  397. {
  398.     return last+1;
  399. }
  400.  
  401. inline int LeafNode::Vsize() const
  402. {
  403.     PRECONDITION( parent != 0 && parent->getTree(0) != (Node _FAR *)this );
  404.     return Psize()+1;
  405. }
  406.  
  407. inline int LeafNode::maxIndex() const
  408. {
  409.     return tree->Leaf_MaxIndex;
  410. }
  411.  
  412. inline int LeafNode::maxPsize() const
  413. {
  414.     return tree->Leaf_MaxIndex + 1;
  415. }
  416.  
  417. inline int LeafNode::isFull() const
  418. {
  419.     return last == maxIndex();
  420. }
  421.  
  422. inline int LeafNode::isAlmostFull() const
  423. {
  424.     return last >= maxIndex() - 1;
  425. }
  426.  
  427. inline int LeafNode::isLow() const
  428. {
  429.     return last < tree->Leaf_LowWaterMark;
  430. }
  431.  
  432. inline int Btree::order()
  433. {
  434.     return Order;
  435. }
  436.  
  437. inline ostream _FAR & operator <<( ostream& outputStream, const Node _FAR & aNode)
  438. {
  439.     aNode.printOn( outputStream );
  440.     return outputStream;
  441. }
  442.  
  443. class _CLASSTYPE BtreeIterator : public ContainerIterator
  444. {
  445. public:
  446.             BtreeIterator( const Btree _FAR & );
  447.     virtual ~BtreeIterator();
  448.  
  449.     virtual operator int();
  450.     virtual Object _FAR & current();
  451.     virtual Object _FAR & operator ++();
  452.     virtual Object _FAR & operator ++( int );
  453.     virtual void restart();
  454.  
  455. private:
  456.     const   Btree _FAR & beingIterated;
  457.             long index;
  458. };
  459.  
  460. inline BtreeIterator::BtreeIterator( const Btree _FAR & toIterate ) :
  461.     beingIterated( toIterate ), index( 0 )
  462. {
  463. }
  464.  
  465. inline Object _FAR & Btree::operator[]( long i ) const { return (*root)[i]; }
  466.  
  467. #endif
  468.