home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cset21v1.zip / IBMCPP / IBMCLASS / IIAVLKSS.H < prev    next >
Text File  |  1993-09-22  |  9KB  |  194 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 _IIAVLKSS_H
  13. #define _IIAVLKSS_H
  14.  
  15. #include <iglobals.h>
  16.  
  17. class IAvlKeySortedSetImpl {
  18. public:
  19.  
  20.   class Node {
  21.     friend class IAvlKeySortedSetImpl;
  22.     Node*          ivLeft;
  23.     Node*          ivRight;
  24.     Node*          ivParent;
  25.     short          ivDeeperSubtree;
  26.  
  27.     Node*&         link (short dir);
  28.     void           parent (Node*& P, short& dir);
  29.     void           connectChild (short dir, Node*);
  30.     void           connectChild0 (short dir, Node*);
  31.   public:
  32.     Node           ();
  33.   };
  34.  
  35.   class Operations {
  36.     virtual Node*    newNode              (void const* element) const = 0;
  37.     virtual Node*    copyNode             (void const* node) const = 0;
  38.     virtual void     deleteNode           (void* node) const = 0;
  39.     virtual void*    elementAt            (void* node) const = 0;
  40.     virtual void const*
  41.                      constElementAt       (void const* node) const = 0;
  42.     virtual void const*
  43.                      keyAt                (void const* node) const = 0;
  44.     virtual long     compareKeyToElement  (void const* node,
  45.                                            void const* element) const = 0;
  46.     virtual long     compareKeyToKey      (void const* node,
  47.                                            void const* key) const = 0;
  48.     virtual void     copyFrom             (void* node,
  49.                                            void const* element) const = 0;
  50.     virtual IBoolean  constantFunctionIteration
  51.                                           (void *function,
  52.                                            void* env,
  53.                                            void const* node) = 0;
  54.     virtual IBoolean  functionIteration    (void *function,
  55.                                            void* env,
  56.                                            void* node) = 0;
  57.     virtual IBoolean  constantIteratorIteration
  58.                                           (void* iterator,
  59.                                            void const* node) = 0;
  60.     virtual IBoolean  iteratorIteration    (void* iterator,
  61.                                            void* node) = 0;
  62.  
  63.     virtual long     functionComparison   (void *compareFunction,
  64.                                            void const* node1,
  65.                                            void const* node2) = 0;
  66.     friend class IAvlKeySortedSetImpl;
  67.   };
  68.  
  69. private :
  70.    Operations*         ivOps;
  71.    Node*               ivRoot;
  72.    INumber             ivNumberOfElements;
  73.  
  74.    void                replace             (Node* oldNode, Node* newNode);
  75.    void                deleteTree          (Node*);
  76.    void                balance             (Node*, short dir, IBoolean&);
  77.    void                disconnectAndRemove (Node*, IBoolean&);
  78.    Node*               copySubtree         (Node const*);
  79.    IBoolean            locateElementWithKeyOfElement
  80.                                            (void const* element,
  81.                                             Node*&) const;
  82.    IBoolean            containsAllKeysFromSubtree
  83.                                            (Node const*) const;
  84.    void                unionWithSubtree    (Node const*);
  85.  
  86.    IBoolean            allElementsDoSubtree(void* function,
  87.                                             void* environment,
  88.                                             Node const*) const;
  89.  
  90.    IBoolean            allElementsDoSubtree(void* function,
  91.                                             void* environment,
  92.                                             Node*);
  93.  
  94.    IBoolean            allElementsDoSubtree(void* iterator,
  95.                                             Node const*) const;
  96.  
  97.    IBoolean            allElementsDoSubtree(void* iterator,
  98.                                             Node*);
  99.  
  100. public:
  101.                        IAvlKeySortedSetImpl              (Operations*);
  102.                        IAvlKeySortedSetImpl              (IAvlKeySortedSetImpl const&,
  103.                                                   Operations*);
  104.    void                operator=           (IAvlKeySortedSetImpl const&);
  105.  
  106.   virtual             ~IAvlKeySortedSetImpl              ();
  107.  
  108.    IBoolean             add                 (void const* element);
  109.    IBoolean             add                 (void const* element,
  110.                                             Node*&);
  111.    void                addAllFrom          (IAvlKeySortedSetImpl const&);
  112.    void const*         elementAt           (Node const*) const;
  113.    void*               elementAt           (Node*);
  114.    void                removeAt            (Node*);
  115.    INumber             removeAll           (void* predicate,
  116.                                             void* environment);
  117.    void                replaceAt           (Node*,
  118.                                             void const* element);
  119.    void                removeAll           ();
  120.    IBoolean             isBounded           () const;
  121.    IPosition           numberOfElements    () const
  122.                        { return ivNumberOfElements; }
  123.    IBoolean             isEmpty             () const
  124.                        { return ivRoot == 0; }
  125.    IBoolean             isFull              () const;
  126.  
  127.    IBoolean             setToFirst          (Node*&) const;
  128.    IBoolean             setToNext           (Node*&) const;
  129.  
  130.    IBoolean             allElementsDo       (void* function,
  131.                                             void* environment) const;
  132.  
  133.    IBoolean             allElementsDo       (void* function,
  134.                                             void* environment);
  135.  
  136.    IBoolean             allElementsDo       (void* iterator) const;
  137.  
  138.    IBoolean             allElementsDo       (void* iterator);
  139.  
  140.    INumber             removeAllOccurences (void const* element);
  141.  
  142.    IBoolean             containsAllKeysFrom (IAvlKeySortedSetImpl const&) const;
  143.    IBoolean             containsElementWithKey
  144.                                            (void const* key) const;
  145.    IBoolean             locateElementWithKey(void const* key,
  146.                                             Node*&) const;
  147.    IBoolean             replaceElementWithKey
  148.                                            (void const* element,
  149.                                             Node*&);
  150.    IBoolean             replaceElementWithKey
  151.                                            (void const* element);
  152.    IBoolean             addOrReplaceElementWithKey
  153.                                            (void const* element,
  154.                                             Node*&);
  155.    IBoolean             addOrReplaceElementWithKey
  156.                                            (void const* element);
  157.    IBoolean             locateOrAddElementWithKey
  158.                                            (void const* element,
  159.                                             Node*&);
  160.    IBoolean             locateOrAddElementWithKey
  161.                                            (void const* element);
  162.    IBoolean             removeElementWithKey(void const* key);
  163.    void const*         elementWithKey      (void const* key) const;
  164.    void*               elementWithKey      (void const* key);
  165.  
  166.    void                removeFirst         ();
  167.    void                removeLast          ();
  168.    void                removeAtPosition    (IPosition);
  169.    void const*         firstElement        () const;
  170.    void const*         lastElement         () const;
  171.    void const*         elementAtPosition   (IPosition) const;
  172.    IBoolean             setToLast           (Node*&) const;
  173.    IBoolean             setToPrevious       (Node*&) const;
  174.    void                setToPosition       (IPosition,
  175.                                             Node*&) const;
  176.    IBoolean             isFirst             (Node const*) const;
  177.    IBoolean             isLast              (Node const*) const;
  178.  
  179.    long                compare             (IAvlKeySortedSetImpl const&,
  180.                                             void *function) const;
  181.  
  182.    IBoolean             checkNode           (Node const*, Node*) const;
  183.    IBoolean             checkNode           (Node const*) const;
  184.  
  185.    IBoolean             isConsistent        () const;
  186.  
  187. protected:
  188.  
  189.    IBoolean             isConsistent        (Node const* n,
  190.                                             int& depth, int& nrOfElm) const;
  191. };
  192.  
  193. #endif
  194.