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