home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cset21v1.zip / IBMCPP / IBMCLASS / IBSTKSS.H < prev    next >
Text File  |  1993-09-22  |  15KB  |  410 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 _IBSTKSS_H
  13. #define _IBSTKSS_H
  14.  
  15. #include <iglobals.h>
  16. #include <icursor.h>
  17. #include <iibstkss.h>
  18. #include <stdlib.h>
  19.  
  20. template < class Element, class Key, class ElementOps, size_t nodeSize >
  21. class IWBSTKeySortedSet
  22. {
  23. #define IBSTMAX(a,b)  ((a) < (b) ? (b) : (a))
  24. #define IBSTORDER \
  25.   IBSTMAX (2, (nodeSize \
  26.                - (sizeof(IBSTKeySortedSetImpl::Inode) \
  27.                   + sizeof(IBSTKeySortedSetImpl::Node*)) \
  28.               ) / (sizeof(Key) + sizeof(IBSTKeySortedSetImpl::Node*)) + 1)
  29.  
  30.   static ElementOps elementOps ()
  31.   { ElementOps ops;
  32.     return ops;
  33.   }
  34.  
  35.   class Lnode;
  36.   class Inode;
  37.   class KeyWrapper;
  38.   class Operations;
  39.   class Cursor;
  40.  
  41.   friend class Lnode;
  42.   friend class Inode;
  43.   friend class KeyWrapper;
  44.   friend class Operations;
  45.   friend class Cursor;
  46.  
  47.   class Lnode : public IBSTKeySortedSetImpl::Lnode
  48.   {
  49.     friend class IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize >;
  50.     friend class Operations;
  51.  
  52.   private :
  53.     Element ivItem;
  54.  
  55.   public:
  56.     Lnode (Element const& item) : ivItem (item)
  57.     {}
  58.  
  59.     Lnode (Lnode const& lnode) : ivItem (lnode.ivItem)
  60.     {}
  61.  
  62. #if defined (__IBMCPP__) && defined (__DEBUG_ALLOC__)
  63.     void* operator new        (size_t s, char const* fn, size_t ln)
  64.           { return elementOps().allocate (s, fn, ln); }
  65.  
  66.     void  operator delete     (void* p, char const* fn, size_t ln)
  67.           { elementOps().deallocate (p, fn, ln); }
  68. #else
  69.     void* operator new        (size_t s)
  70.           { return elementOps().allocate (s); }
  71.  
  72.     void operator delete     (void* p)
  73.          { elementOps().deallocate (p); }
  74. #endif // __IBMCPP__ && __DEBUG_ALLOC__
  75.  
  76.     virtual void const*
  77.                      getElement                () const;
  78.  
  79.     virtual void*    getElement                ();
  80.  
  81.     virtual void     replaceElement            (void const* element);
  82.  
  83.     virtual IBoolean  isKeyEqualTo              (void const* lnode) const;
  84.  
  85.     virtual IBoolean  isKeyEqualToKeyOfElement  (void const* element) const;
  86.  
  87.     virtual IBoolean  isKeyEqualToKey           (void const* key) const;
  88.  
  89.   };
  90.  
  91.   class Inode : public IBSTKeySortedSetImpl::Inode
  92.   {
  93.     friend class Operations;
  94.     IBSTKeySortedSetImpl::Node* ivNodeptrs [IBSTORDER];
  95.     Key ivKeys [IBSTORDER - 1];
  96.  
  97.   public:
  98.     Inode () : IBSTKeySortedSetImpl::Inode (ivNodeptrs, ivKeys)
  99.     {}
  100.  
  101.     Inode (Inode const& inode)
  102.     : IBSTKeySortedSetImpl::Inode (inode, ivNodeptrs, ivKeys)
  103.     {}
  104.  
  105. #if defined (__IBMCPP__) && defined (__DEBUG_ALLOC__)
  106.     void* operator new        (size_t s, char const* fn, size_t ln)
  107.           { return elementOps().allocate (s, fn, ln); }
  108.  
  109.     void  operator delete     (void* p, char const* fn, size_t ln)
  110.           { elementOps().deallocate (p, fn, ln); }
  111. #else
  112.     void* operator new        (size_t s)
  113.           { return elementOps().allocate (s); }
  114.  
  115.     void operator delete     (void* p)
  116.          { elementOps().deallocate (p); }
  117. #endif // __IBMCPP__ && __DEBUG_ALLOC__
  118.  
  119.   };
  120.  
  121.   class KeyWrapper
  122.   { Key key;
  123.   public:
  124.  
  125. #if defined (__IBMCPP__) && defined (__DEBUG_ALLOC__)
  126.     void* operator new        (size_t s, char const* fn, size_t ln)
  127.           { return elementOps().allocate (s, fn, ln); }
  128.  
  129.     void  operator delete     (void* p, char const* fn, size_t ln)
  130.           { elementOps().deallocate (p, fn, ln); }
  131. #else
  132.     void* operator new        (size_t s)
  133.           { return elementOps().allocate (s); }
  134.  
  135.     void operator delete     (void* p)
  136.          { elementOps().deallocate (p); }
  137. #endif // __IBMCPP__ && __DEBUG_ALLOC__
  138.  
  139.   };
  140.  
  141.   class Operations : public IBSTKeySortedSetImpl::Operations
  142.   {
  143.   public:
  144.     virtual IBSTKeySortedSetImpl::Lnode*
  145.                      newLnode             (void const* element) const;
  146.  
  147.     virtual IBSTKeySortedSetImpl::Lnode*
  148.                      newLnodeFromLnode    (void const* lnode) const;
  149.  
  150.     virtual IBSTKeySortedSetImpl::Inode*
  151.                      newInode             () const;
  152.  
  153.     virtual IBSTKeySortedSetImpl::Inode*
  154.                      newInode             (void const* inode) const;
  155.  
  156.     virtual void*    newKey               () const;
  157.  
  158.     virtual void     deleteLnode          (void* lnode) const;
  159.  
  160.     virtual void     deleteInode          (void* inode) const;
  161.  
  162.     virtual void     deleteKey            (void *key) const;
  163.  
  164.     virtual IBoolean  isKeyLessThan        (void const* key1,
  165.                                            void const* key2) const;
  166.  
  167.     virtual void     copyKey              (void* toKey,
  168.                                            unsigned int toIndex,
  169.                                            void const* fromKey,
  170.                                            unsigned int fromIndex) const;
  171.  
  172.     virtual IBoolean  isKeyLessThanLnode   (void const* key,
  173.                                            void const* lnode) const;
  174.  
  175.     virtual void     copyKeyFromLnode     (void* key,
  176.                                            void const* lnode);
  177.  
  178.     virtual IBoolean  isKeyGreaterThanLnode(void const* key,
  179.                                            unsigned int index,
  180.                                            void const* lnode) const;
  181.  
  182.     virtual IBoolean  isKeyGreaterThanKey  (void const* key1,
  183.                                            unsigned int index,
  184.                                            void const* key2) const;
  185.  
  186.     virtual IBoolean  isKeyGreaterThanElement
  187.                                           (void const* key,
  188.                                            unsigned int index,
  189.                                            void const* element) const;
  190.  
  191.     virtual IBoolean  constantFunctionIteration
  192.                                           (void *function,
  193.                                            void* env,
  194.                                            void const* lnode) const;
  195.     virtual IBoolean  functionIteration    (void *function,
  196.                                            void* env,
  197.                                            void* lnode) const;
  198.     virtual IBoolean  constantIteratorIteration
  199.                                           (void* iterator,
  200.                                            void const* lnode) const;
  201.     virtual IBoolean  iteratorIteration    (void* iterator,
  202.                                            void* lnode) const;
  203.  
  204.     virtual long     functionComparison   (void *compareFunction,
  205.                                            void const* lnode1,
  206.                                            void const* lnode2) const;
  207.  
  208.   };
  209.  
  210. private:
  211.  
  212.    Operations ivOps;
  213.    IBSTKeySortedSetImpl ivImpl;
  214.  
  215.    void init                 ();
  216.    void checkNotEmpty        () const;
  217.    void checkCursorIsForThis (ICursor const&) const;
  218.    void checkCursor          (ICursor const&) const;
  219.    void checkPositionExists  (IPosition) const;
  220.  
  221. public:
  222.  
  223.   class Cursor : public ICursor {
  224.   protected:
  225.     IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const* ivCollection;
  226.     IBSTKeySortedSetImpl::Lnode *ivNode;
  227.     friend class IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize >;
  228.     IBoolean isFor (IWBSTKeySortedSet
  229.                      < Element, Key, ElementOps, nodeSize > const& c) const
  230.     { return ivCollection == &c; }
  231.  
  232.   public:
  233.     Cursor (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const& c)
  234.     : ivCollection (&c), ivNode (0) {};
  235.  
  236.     IBoolean setToFirst ();
  237.     IBoolean setToNext  ();
  238.     IBoolean isValid    () const;
  239.     void    invalidate ();
  240.  
  241.     Element const& element      () const
  242.     { return ivCollection->elementAt (*this); }
  243.     IBoolean setToLast     ()
  244.     { return ivCollection->setToLast (*this); }
  245.     IBoolean setToPrevious ()
  246.     { return ivCollection->setToPrevious (*this); }
  247.     IBoolean operator== (Cursor const& cursor) const
  248.     { return ivCollection == cursor.ivCollection &&
  249.              ivNode == cursor.ivNode; }
  250.     IBoolean operator!= (Cursor const& cursor) const
  251.     { return ! operator== (cursor); }
  252.  
  253.   };
  254.  
  255.                   IWBSTKeySortedSet             (INumber
  256.                                                numberOfElements = 100);
  257.  
  258.                   IWBSTKeySortedSet             (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const&);
  259.  
  260.    IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize >&
  261.                   operator =                  (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const&);
  262.  
  263.                  ~IWBSTKeySortedSet             ();
  264.  
  265.    IBoolean       add                         (Element const&);
  266.  
  267.    IBoolean       add                         (Element const&,
  268.                                                ICursor&);
  269.  
  270.    void           addAllFrom                  (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const&);
  271.  
  272.    Element const& elementAt                   (ICursor const&) const;
  273.  
  274.    Element&       elementAt                   (ICursor const&);
  275.  
  276.    Element const& anyElement                  () const;
  277.  
  278.    void           removeAt                    (ICursor const&);
  279.  
  280.    INumber        removeAll                   (IBoolean (*property)
  281.                                                (Element const&, void*),
  282.                                                void* additionalArgument = 0);
  283.  
  284.    void           replaceAt                   (ICursor const&,
  285.                                                Element const&);
  286.  
  287.    void           removeAll                   ();
  288.  
  289.    IBoolean       isBounded                   () const;
  290.  
  291.    INumber        maxNumberOfElements         () const;
  292.  
  293.    INumber        numberOfElements            () const;
  294.  
  295.    IBoolean       isEmpty                     () const;
  296.  
  297.    IBoolean       isFull                      () const;
  298.  
  299.    ICursor*       newCursor                   () const;
  300.  
  301.    IBoolean       setToFirst                  (ICursor&) const;
  302.  
  303.    IBoolean       setToNext                   (ICursor&) const;
  304.  
  305.    IBoolean       allElementsDo               (IBoolean (*function)
  306.                                                   (Element&, void*),
  307.                                                void* additionalArgument = 0);
  308.  
  309.    IBoolean       allElementsDo               (IIterator <Element>&);
  310.  
  311.    IBoolean       allElementsDo               (IBoolean (*function)
  312.                                                (Element const&, void*),
  313.                                                void* additionalArgument = 0)
  314.                                                const;
  315.  
  316.    IBoolean       allElementsDo               (IConstantIterator
  317.                                                   <Element>&) const;
  318.  
  319.    IBoolean       isConsistent                () const;
  320.  
  321.    Key const&     key                         (Element const&) const;
  322.  
  323.    IBoolean       containsElementWithKey      (Key const&) const;
  324.  
  325.    IBoolean       containsAllKeysFrom         (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const&) const;
  326.  
  327.    IBoolean       locateElementWithKey        (Key const&, ICursor&)
  328.                                                const;
  329.  
  330.    IBoolean       replaceElementWithKey       (Element const&);
  331.  
  332.    IBoolean       replaceElementWithKey       (Element const&,
  333.                                                ICursor&);
  334.  
  335.    IBoolean       locateOrAddElementWithKey   (Element const&);
  336.  
  337.    IBoolean       locateOrAddElementWithKey   (Element const&,
  338.                                                ICursor&);
  339.  
  340.    IBoolean       addOrReplaceElementWithKey  (Element const&);
  341.  
  342.    IBoolean       addOrReplaceElementWithKey  (Element const&,
  343.                                                ICursor&);
  344.  
  345.    IBoolean       removeElementWithKey        (Key const&);
  346.  
  347.    Element const& elementWithKey              (Key const&) const;
  348.  
  349.    Element&       elementWithKey              (Key const&);
  350.  
  351.    void           removeFirst                 ();
  352.  
  353.    void           removeLast                  ();
  354.  
  355.    void           removeAtPosition            (IPosition);
  356.  
  357.    Element const& firstElement                () const;
  358.  
  359.    Element const& lastElement                 () const;
  360.  
  361.    Element const& elementAtPosition           (IPosition) const;
  362.  
  363.    IBoolean       setToLast                   (ICursor&) const;
  364.  
  365.    IBoolean       setToPrevious               (ICursor&) const;
  366.  
  367.    void           setToPosition               (IPosition,
  368.                                                ICursor&) const;
  369.  
  370.    IBoolean       isFirst                     (ICursor const&) const;
  371.  
  372.    IBoolean       isLast                      (ICursor const&) const;
  373.  
  374.    long           compare                     (IWBSTKeySortedSet < Element, Key, ElementOps, nodeSize > const&,
  375.                                                long (*comparisonFunction)
  376.                                                   (Element const&,
  377.                                                   Element const&)) const;
  378.  
  379. };
  380.  
  381. #include <ibstkss.if>
  382.  
  383. #ifndef IBSTPAGESIZE
  384. #define IBSTPAGESIZE 4096
  385. #endif
  386.  
  387. template < class Element, class Key, class ElementOps >
  388. class IGBSTKeySortedSet :
  389.   public IWBSTKeySortedSet < Element, Key, ElementOps, IBSTPAGESIZE > {
  390. public:
  391.   IGBSTKeySortedSet (INumber n = 100) :
  392.     IWBSTKeySortedSet < Element, Key, ElementOps, IBSTPAGESIZE > (n) {}
  393. };
  394.  
  395. template < class Element, class Key >
  396. class IBSTKeySortedSet :
  397.   public IGBSTKeySortedSet < Element, Key, IKCOps < Element, Key > > {
  398. public:
  399.   IBSTKeySortedSet (INumber n = 100) :
  400.     IGBSTKeySortedSet < Element, Key, IKCOps < Element, Key > > (n) {}
  401. };
  402.  
  403. #ifdef __IBMCPP__
  404. #ifndef __TEMPINC__
  405. #include <ibstkss.c>
  406. #endif
  407. #endif
  408.  
  409. #endif
  410.