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