home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cset21v1.zip / IBMCPP / IBMCLASS / IIBSTKSS.H < prev    next >
Text File  |  1993-09-22  |  16KB  |  486 lines
  1. /*******************************************************************************
  2. *                                                                              *
  3. * COPYRIGHT:                                                                   *
  4. *   IBM C/C++ Tools Version 2.01 - Collection Class Library                    *
  5. *   Licensed Materials - Property of IBM                                       *
  6. *   (C) Copyright IBM Corporation 1992, 1993                                   *
  7. *   All Rights Reserved                                                        *
  8. *   US Government Users Restricted Rights - Use, duplication, or disclosure    *
  9. *   restricted by GSA ADP Schedule Contract with IBM Corp.                     *
  10. *                                                                              *
  11. *******************************************************************************/
  12. #ifndef _IIBSTKSS_H
  13. #define _IIBSTKSS_H
  14.  
  15. #include <iglobals.h>
  16.  
  17. class IBSTKeySortedSetImpl
  18. {
  19. public:
  20.  
  21.   class Node
  22.   {
  23.   public:
  24.  
  25.     virtual IBoolean isLeaf              () const = 0;
  26.  
  27.   };
  28.  
  29.   class Lnode : public Node
  30.   {
  31.   public:
  32.     virtual IBoolean  isLeaf                    () const;
  33.  
  34.   public:
  35.     virtual void const*
  36.                      getElement                () const = 0;
  37.  
  38.     virtual void*    getElement                () = 0;
  39.  
  40.     virtual void     replaceElement            (void const* element) = 0;
  41.  
  42.     virtual IBoolean  isKeyEqualTo              (void const* lnode) const = 0;
  43.  
  44.     virtual IBoolean  isKeyEqualToKeyOfElement  (void const* element) const = 0;
  45.  
  46.     virtual IBoolean  isKeyEqualToKey           (void const* key) const = 0;
  47.  
  48.   };
  49.  
  50.   class Inode : public Node
  51.   {
  52.     friend class IBSTKeySortedSetImpl;
  53.  
  54.   public:
  55.     inline          Inode           (Node**, void* keys);
  56.  
  57.     inline          Inode           (Inode const&, Node**, void* keys);
  58.  
  59.     virtual IBoolean isLeaf          () const;
  60.  
  61.   protected:
  62.     void*         ivKeys;
  63.     Node**        ivPtrs;
  64.     INumber       ivm;
  65.  
  66.   };
  67.  
  68.   class Operations
  69.   {
  70.   public:
  71.     virtual Lnode*   newLnode             (void const* element) const = 0;
  72.  
  73.     virtual Lnode*   newLnodeFromLnode    (void const* lnode) const = 0;
  74.  
  75.     virtual Inode*   newInode             () const = 0;
  76.  
  77.     virtual Inode*   newInode             (void const* inode) const = 0;
  78.  
  79.     virtual void*    newKey               () const = 0;
  80.  
  81.     virtual void     deleteLnode          (void* lnode) const = 0;
  82.  
  83.     virtual void     deleteInode          (void* inode) const = 0;
  84.  
  85.     virtual void     deleteKey            (void *key) const = 0;
  86.  
  87.     virtual IBoolean  isKeyLessThan        (void const* key1,
  88.                                            void const* key2) const = 0;
  89.  
  90.     virtual void     copyKey              (void* toKey,
  91.                                            unsigned int toIndex,
  92.                                            void const* fromKey,
  93.                                            unsigned int fromIndex) const = 0;
  94.             void     copyKey              (void* toKey,
  95.                                            void const* fromKey)
  96.             { copyKey (toKey, 0, fromKey, 0); }
  97.             void     copyKey              (void* toKey,
  98.                                            unsigned int toIndex,
  99.                                            void const* fromKey)
  100.             { copyKey (toKey, toIndex, fromKey, 0); }
  101.             void     copyKey              (void* toKey,
  102.                                            void const* fromKey,
  103.                                            unsigned int fromIndex)
  104.             { copyKey (toKey, 0, fromKey, fromIndex); }
  105.  
  106.     virtual IBoolean  isKeyLessThanLnode   (void const* key,
  107.                                            void const* lnode) const = 0;
  108.  
  109.     virtual void     copyKeyFromLnode     (void* key,
  110.                                            void const* lnode) = 0;
  111.  
  112.     virtual IBoolean  isKeyGreaterThanLnode(void const* key,
  113.                                            unsigned int index,
  114.                                            void const* lnode) const = 0;
  115.  
  116.     virtual IBoolean  isKeyGreaterThanKey  (void const* key1,
  117.                                            unsigned int index,
  118.                                            void const* key2) const = 0;
  119.  
  120.     virtual IBoolean  isKeyGreaterThanElement
  121.                                           (void const* key,
  122.                                            unsigned int index,
  123.                                            void const* element) const = 0;
  124.  
  125.     virtual IBoolean  constantFunctionIteration
  126.                                           (void *function,
  127.                                            void* env,
  128.                                            void const* lnode) const = 0;
  129.     virtual IBoolean  functionIteration    (void *function,
  130.                                            void* env,
  131.                                            void* lnode) const = 0;
  132.     virtual IBoolean  constantIteratorIteration
  133.                                           (void* iterator,
  134.                                            void const* lnode) const = 0;
  135.     virtual IBoolean  iteratorIteration    (void* iterator,
  136.                                            void* lnode) const = 0;
  137.  
  138.     virtual long     functionComparison   (void *compareFunction,
  139.                                            void const* lnode1,
  140.                                            void const* lnode2) const = 0;
  141.  
  142.   };
  143.  
  144.   inline           IBSTKeySortedSetImpl       (INumber, Operations*);
  145.  
  146.                    IBSTKeySortedSetImpl       (IBSTKeySortedSetImpl const&,
  147.                                                Operations*);
  148.  
  149.   inline          ~IBSTKeySortedSetImpl       ();
  150.  
  151.   inline IBoolean   add                        (void const* element);
  152.  
  153.          IBoolean   add                        (void const* element, Lnode*&);
  154.  
  155.   inline void      addAllFrom                 (IBSTKeySortedSetImpl const&);
  156.  
  157.   inline void const*
  158.                    elementAt                  (Lnode* const&) const;
  159.  
  160.   inline void*     elementAt                  (Lnode* const&);
  161.  
  162.   inline void const*
  163.                    anyElement                 () const;
  164.  
  165.          void      removeAt                   (Lnode* const&);
  166.  
  167.          INumber   removeAll                  (void* predicate,
  168.                                                void* environment);
  169.  
  170.   inline void      replaceAt                  (Lnode* const&, void const* element);
  171.  
  172.   inline void      removeAll                  ();
  173.  
  174.   inline IBoolean   isBounded                  () const;
  175.  
  176.   inline INumber   maxNumberOfElements        () const;
  177.  
  178.   inline INumber   numberOfElements           () const;
  179.  
  180.   inline IBoolean   isEmpty                    () const;
  181.  
  182.   inline IBoolean   isFull                     () const;
  183.  
  184.          IBoolean   setToFirst                 (Lnode*&) const;
  185.  
  186.          IBoolean   setToNext                  (Lnode*&) const;
  187.  
  188.          IBoolean   allElementsDo              (void* function,
  189.                                                void* environment) const;
  190.  
  191.          IBoolean   allElementsDo              (void* function,
  192.                                                void* environment);
  193.  
  194.          IBoolean   allElementsDo              (void* iterator) const;
  195.  
  196.          IBoolean   allElementsDo              (void* iterator);
  197.  
  198.          IBoolean   containsAllKeysFrom        (IBSTKeySortedSetImpl const&) const;
  199.  
  200.          IBoolean   containsElementWithKey     (void const* key) const;
  201.  
  202.          IBoolean   locateElementWithKey       (void const* key, Lnode*&) const;
  203.  
  204.          IBoolean   replaceElementWithKey      (void const* element);
  205.  
  206.          IBoolean   replaceElementWithKey      (void const* element,
  207.                                                Lnode*&);
  208.  
  209.          IBoolean   addOrReplaceElementWithKey (void const* element);
  210.  
  211.          IBoolean   addOrReplaceElementWithKey (void const* element, Lnode*&);
  212.  
  213.          IBoolean   removeElementWithKey       (void const* key);
  214.  
  215.          void const*
  216.                    elementWithKey             (void const* key) const;
  217.  
  218.          void*     elementWithKey             (void const* key);
  219.  
  220.          void      removeFirst                ();
  221.  
  222.          void      removeLast                 ();
  223.  
  224.          void      removeAtPosition           (IPosition);
  225.  
  226.   inline void const*
  227.                    firstElement               () const;
  228.  
  229.          void const*
  230.                    lastElement                () const;
  231.  
  232.          void const*
  233.                    elementAtPosition          (IPosition) const;
  234.  
  235.          IBoolean   setToLast                  (Lnode*&) const;
  236.  
  237.          IBoolean   setToPrevious              (Lnode*&) const;
  238.  
  239.          void      setToPosition              (IPosition, Lnode*&) const;
  240.  
  241.          IBoolean   isFirst                    (Lnode* const&) const;
  242.  
  243.          IBoolean   isLast                     (Lnode* const&) const;
  244.  
  245.          IBSTKeySortedSetImpl&
  246.                    operator =                 (IBSTKeySortedSetImpl const&);
  247.  
  248.          long      compare                    (IBSTKeySortedSetImpl const&,
  249.                                                void *function) const;
  250.  
  251.          IBoolean   checkNode                  (Lnode const*, Node const*) const;
  252.          IBoolean   checkNode                  (Lnode const*) const;
  253.  
  254.          IBoolean   isConsistent               () const;
  255.  
  256. private:
  257.   inline IBoolean   isUnderflown               (Inode const*) const;
  258.  
  259.          IBoolean   allElementsDoSubtree       (void* function,
  260.                                                void* environment,
  261.                                                Node const*) const;
  262.  
  263.          IBoolean   allElementsDoSubtree       (void* function,
  264.                                                void* environment,
  265.                                                Node*);
  266.  
  267.          IBoolean   allElementsDoSubtree       (void* iterator,
  268.                                                Node const*) const;
  269.  
  270.          IBoolean   allElementsDoSubtree       (void* iterator,
  271.                                                Node*);
  272.  
  273.          IPosition binarySearchInPage         (Inode const*,
  274.                                                Lnode const*) const;
  275.  
  276.          IPosition binarySearchInPageWithKey  (Inode const*,
  277.                                                void const* key) const;
  278.  
  279.          IPosition binarySearchInPageWithElement
  280.                                               (Inode const*,
  281.                                                void const* element) const;
  282.  
  283.          IBoolean   setToNextSubtree           (Lnode*&, Inode const*) const;
  284.  
  285.          IBoolean   setToPreviousSubtree       (Lnode*&, Inode const*) const;
  286.  
  287.          IBoolean   addAid                     (Node*,
  288.                                                Lnode*,
  289.                                                Node*&,
  290.                                                void* key,
  291.                                                Lnode*&);
  292.  
  293.          Lnode*    minimumLeaf                (Node*) const;
  294.  
  295.          Lnode*    maximumLeaf                (Node*) const;
  296.  
  297.          INumber   removeAllSubtree           (Node*);
  298.  
  299.          void      addAllFromSubtree          (Node const*, Lnode*&);
  300.  
  301.          void      removeAid                  (Inode*, Lnode*);
  302.  
  303.          void      handleUnderflow            (Inode*, Inode*, IPosition);
  304.  
  305.          void      joinInodes                 (Inode*, Inode*, Inode*,
  306.                                                IPosition);
  307.  
  308.          Node*     copySubtree                (Node const*);
  309.  
  310.          IBoolean   locateWithKeySubtree       (void const* key,
  311.                                                Lnode*&,
  312.                                                Node*) const;
  313.  
  314.          IBoolean   containsAllKeysFromSubtree (Node const*,
  315.                                                Lnode*&) const;
  316.  
  317.          IBoolean   locateElementWithKeySubtree(void const* key,
  318.                                                Lnode*&,
  319.                                                Node*) const;
  320.  
  321.          IBoolean   locateElementWithKeyOfElement
  322.                                               (void const* element,
  323.                                                Lnode*&) const;
  324.  
  325.          IBoolean   locateElementWithKeyOfElementSubtree
  326.                                               (void const* element,
  327.                                                Lnode*&,
  328.                                                Node*) const;
  329.  
  330.          IBoolean   containsElementWithKey     (Lnode const*) const;
  331.  
  332.          IBoolean   locateElementWithKey       (Lnode const*,
  333.                                                Lnode*&) const;
  334.  
  335.          IBoolean   locateElementWithKeySubtree(Lnode const* lnode,
  336.                                                Lnode*& cursor,
  337.                                                Node* node) const;
  338.  
  339. //
  340. // PRIVATE members
  341. //
  342. private:
  343.    Operations* ivOps;
  344.    Node*       ivRoot;
  345.    INumber     ivHeight;
  346.    INumber     ivTreeOrder;
  347.    INumber     ivNoElements;
  348.  
  349. };
  350.  
  351. //
  352. // INLINE methods
  353. //
  354.  
  355. #include <ibexcept.h>
  356.  
  357. //
  358. // Inode
  359. //
  360.  
  361. IBSTKeySortedSetImpl::Inode::
  362. Inode (Node** ptrs, void* keys)
  363. : ivPtrs(ptrs)
  364. , ivKeys(keys)
  365. { ivm = 0;
  366. }
  367.  
  368. IBSTKeySortedSetImpl::Inode::
  369. Inode(Inode const& inode, Node** ptrs, void* keys)
  370. : ivPtrs(ptrs)
  371. , ivKeys(keys)
  372. { ivm = inode.ivm;
  373. }
  374.  
  375. //
  376. // IBSTKeySortedSetImpl
  377. //
  378.  
  379. IBSTKeySortedSetImpl::
  380. IBSTKeySortedSetImpl (INumber order, Operations* ops)
  381. { ivOps        = ops;
  382.   ivTreeOrder  = order;
  383.   ivRoot       = 0;
  384.   ivHeight     = 0;
  385.   ivNoElements = 0;
  386. }
  387.  
  388. IBSTKeySortedSetImpl::
  389. ~IBSTKeySortedSetImpl ()
  390. { removeAll();
  391. }
  392.  
  393. IBoolean
  394. IBSTKeySortedSetImpl::
  395. add (void const* element)
  396. { Lnode* dummy;
  397.  
  398.   return add(element, dummy);
  399. }
  400.  
  401. void IBSTKeySortedSetImpl::
  402. addAllFrom (IBSTKeySortedSetImpl const& tree)
  403. { if (tree.ivRoot != 0) {
  404.     Lnode* dummy;
  405.  
  406.     addAllFromSubtree(tree.ivRoot, dummy);
  407.   }
  408. }
  409.  
  410. void const* IBSTKeySortedSetImpl::
  411. elementAt (Lnode* const& cursor) const
  412. { return cursor->getElement();
  413. }
  414.  
  415. void* IBSTKeySortedSetImpl::
  416. elementAt (Lnode* const& cursor)
  417. { return cursor->getElement();
  418. }
  419.  
  420. void const* IBSTKeySortedSetImpl::
  421. anyElement () const
  422. { return firstElement();
  423. }
  424.  
  425. void IBSTKeySortedSetImpl::
  426. replaceAt (Lnode* const& cursor, void const* element)
  427. { cursor->replaceElement(element);
  428. }
  429.  
  430. void IBSTKeySortedSetImpl::
  431. removeAll ()
  432. { if (ivRoot != 0) {
  433.     removeAllSubtree(ivRoot);
  434.     ivRoot       = 0;
  435.     ivHeight     = 0;
  436.     ivNoElements = 0;
  437.   }
  438.   else {
  439.     IASSERT(ivNoElements == 0);
  440.   }
  441. }
  442.  
  443. IBoolean IBSTKeySortedSetImpl::
  444. isBounded () const
  445. { return False;
  446. }
  447.  
  448. INumber IBSTKeySortedSetImpl::
  449. maxNumberOfElements () const
  450. { IASSERT(False);
  451.  
  452.   return 0;
  453. }
  454.  
  455. INumber IBSTKeySortedSetImpl::
  456. numberOfElements () const
  457. { return ivNoElements;
  458. }
  459.  
  460. IBoolean IBSTKeySortedSetImpl::
  461. isEmpty () const
  462. { return ivRoot == 0;
  463. }
  464.  
  465. IBoolean IBSTKeySortedSetImpl::
  466. isFull () const
  467. { return False;
  468. }
  469.  
  470. void const* IBSTKeySortedSetImpl::
  471. firstElement () const
  472. { Lnode* cursor;
  473.  
  474.   IBoolean b = setToFirst(cursor);
  475.   IASSERT (b);
  476.  
  477.   return elementAt (cursor);
  478. }
  479.  
  480. IBoolean IBSTKeySortedSetImpl::
  481. isUnderflown (Inode const* inode) const
  482. { return inode->ivm < (ivTreeOrder + 1) / 2;
  483. }
  484.  
  485. #endif
  486.