home *** CD-ROM | disk | FTP | other *** search
/ Power GUI Programming with VisualAge C++ / powergui.iso / trialva / ibmcppw / include / iikssbst.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-22  |  15.0 KB  |  618 lines
  1. /**********************************************************************
  2. *                                                                     *
  3. *  IBM(R) VisualAge(TM) for C++ for Windows(R), Version 3.5           *
  4. *                                                                     *
  5. *  PID: 5622-880                                                      *
  6. *  - Licensed Material - Program-Property of IBM                      *
  7. *  (C) Copyright IBM Corp. 1991, 1995 - All Right Reserved.           *
  8. *                                                                     *
  9. *  US Government Users Restricted Rights - Use, duplication or        *
  10. *  disclosure restricted by GSA ADP Schedule Contract with IBM Corp.  *
  11. *                                                                     *
  12. *  VisualAge, and IBM are trademarks or registered trademarks of      *
  13. *  International Business Machines Corporation.                       *
  14. *  Windows is a registered trademark of Microsoft Corporation.        *
  15. *                                                                     *
  16. **********************************************************************/
  17.  
  18. #ifndef _IIKSSBST_H
  19. #define _IIKSSBST_H
  20.  
  21. #include <iiakss.h>
  22. #include <stddef.h>
  23.  
  24.  
  25. #pragma info (nocls, nocnd, nocns, nocnv, noext, nognr, novft)
  26. #pragma pack (4)
  27.  
  28. #pragma SOMAsDefault (off)
  29.  
  30. struct IAKeySortedSetAsBstTreeNodeImpl {
  31.  
  32.   IBoolean ivIsLeaf;
  33.  
  34. };
  35.  
  36. struct IAKeySortedSetAsBstTreeINodeImpl :
  37.   public IAKeySortedSetAsBstTreeNodeImpl {
  38.  
  39.   void*    ivKeys;
  40.  
  41.   IAKeySortedSetAsBstTreeNodeImpl**
  42.            ivPtrs;
  43.  
  44.   INumber  ivm;
  45.  
  46.            IAKeySortedSetAsBstTreeINodeImpl
  47.                             ();
  48.  
  49.            IAKeySortedSetAsBstTreeINodeImpl
  50.                             (IAKeySortedSetAsBstTreeINodeImpl const&);
  51. };
  52.  
  53. #define IBSTMAX(a,b)  ((a) < (b) ? (b) : (a))
  54.  
  55. #if ! defined (IBSTORDER)
  56. #define IBSTORDER \
  57.   IBSTMAX ((long)3, (((long)nodeSize) \
  58.                    - (sizeof (IAKeySortedSetAsBstTreeINodeImpl) \
  59.                     + sizeof (IAKeySortedSetAsBstTreeNodeImpl*)) \
  60.                    ) / (sizeof (Key) \
  61.                     + sizeof (IAKeySortedSetAsBstTreeNodeImpl*)) + 1)
  62. #endif
  63.  
  64. template <class Key, size_t nodeSize>
  65. struct IKeySortedSetAsBstTreeINodeImpl :
  66.   public IAKeySortedSetAsBstTreeINodeImpl {
  67.  
  68.   typedef  IAKeySortedSetAsBstTreeINodeImpl Inherited;
  69.  
  70.   IAKeySortedSetAsBstTreeNodeImpl*
  71.            ivPtrs [IBSTORDER];
  72.  
  73.   Key      ivKeys [IBSTORDER - 1];
  74.  
  75.            IKeySortedSetAsBstTreeINodeImpl
  76.                             ();
  77.  
  78.            IKeySortedSetAsBstTreeINodeImpl
  79.                             (IKeySortedSetAsBstTreeINodeImpl
  80.                               <Key, nodeSize > const&);
  81.  
  82.           ~IKeySortedSetAsBstTreeINodeImpl
  83.                             ();
  84.  
  85.  
  86.  
  87. };
  88.  
  89. struct IAKeySortedSetAsBstTreeLNodeImpl :
  90.   public IAKeySortedSetAsBstTreeNodeImpl {
  91. };
  92.  
  93. template <class Element>
  94. struct IKeySortedSetAsBstTreeLNodeImpl :
  95.   public IAKeySortedSetAsBstTreeLNodeImpl {
  96.  
  97.   Element  ivElement;
  98.  
  99.            IKeySortedSetAsBstTreeLNodeImpl
  100.                             (Element const&);
  101.  
  102.           ~IKeySortedSetAsBstTreeLNodeImpl
  103.                             ();
  104.  
  105.  
  106. };
  107.  
  108. #pragma SOMAsDefault (pop)
  109. #pragma SOMAsDefault (off)
  110.  
  111. class IKeySortedSetAsBstTreeCursorImpl : public ICursorImpl {
  112.  
  113.   typedef  ICursorImpl Inherited;
  114.  
  115.   typedef  IKeySortedSetAsBstTreeCursorImpl Self;
  116.  
  117. public:
  118.  
  119.            IKeySortedSetAsBstTreeCursorImpl
  120.                             (IACollectionImpl const&);
  121.  
  122.            IKeySortedSetAsBstTreeCursorImpl
  123.                             (IKeySortedSetAsBstTreeCursorImpl const&);
  124.  
  125.           ~IKeySortedSetAsBstTreeCursorImpl
  126.                             ();
  127.  
  128.   ICursorImpl*
  129.            Clone            () const;
  130.  
  131.   void     Copy             (ICursorImpl const&);
  132.  
  133.   void     Invalidate       ();
  134.  
  135.   IBoolean IsInBetween      () const;
  136.  
  137.   IBoolean IsValid          () const;
  138.  
  139.   void     operator=        (IKeySortedSetAsBstTreeCursorImpl const&);
  140.  
  141.   IBoolean operator==       (ICursorImpl const&) const;
  142.  
  143. protected:
  144.  
  145. private:
  146.  
  147.   IAKeySortedSetAsBstTreeNodeImpl*
  148.            ivNode;
  149.  
  150.   friend
  151.   class    IKeySortedSetAsBstTreeImpl;
  152.  
  153.  
  154. };
  155.  
  156.  
  157. template <class Base>
  158. class IKeySetOnKeySortedSetImpl;
  159.  
  160. template <class Base>
  161. class ISortedBagOnKeySortedSetImpl;
  162.  
  163. template <class Base>
  164. class ISortedMapOnKeySortedSetImpl;
  165.  
  166. class IAKeySortedSetAsBstTreeOps;
  167.  
  168. class IKeySortedSetAsBstTreeImpl : public IAKeySortedSetImpl {
  169.  
  170.   typedef  IAKeySortedSetImpl Inherited;
  171.  
  172.   typedef  IKeySortedSetAsBstTreeImpl Self;
  173.  
  174.   typedef  IAKeySortedSetAsBstTreeNodeImpl   Node;
  175.  
  176.   typedef  IAKeySortedSetAsBstTreeINodeImpl INode;
  177.  
  178.   typedef  IAKeySortedSetAsBstTreeLNodeImpl LNode;
  179.  
  180. public:
  181.  
  182.   typedef  IAKeySortedSetAsBstTreeOps Ops;
  183.  
  184.   typedef  IKeySortedSetAsBstTreeCursorImpl Cursor;
  185.  
  186.   typedef  IKeySortedSetAsBstTreeCursorImpl MngCursor;
  187.  
  188.            IKeySortedSetAsBstTreeImpl
  189.                             (Ops&, INumber);
  190.  
  191.            IKeySortedSetAsBstTreeImpl
  192.                             (Ops&, IKeySortedSetAsBstTreeImpl const&);
  193.  
  194.           ~IKeySortedSetAsBstTreeImpl
  195.                             ();
  196.  
  197.   IBoolean Add              (void const*, ICursorImpl&);
  198.  
  199.   void     AddAllFrom       (IACollectionImpl const&);
  200.  
  201.   IBoolean AddOrReplaceElementWithKey
  202.                             (void const*, ICursorImpl&);
  203.  
  204.   IBoolean AllElementsDo    (IApplFunc, void*);
  205.  
  206.   void*    Any              () const;
  207.  
  208.   char const*
  209.            ClassName        () const;
  210.  
  211.   IACollectionImpl*
  212.            Clone            () const;
  213.  
  214.   IBoolean CheckCursor      (ICursorImpl const&) const;
  215.  
  216.   IBoolean CheckReplacement (ICursorImpl const&, void const*) const;
  217.  
  218.   IBoolean ContainsAllKeysFrom
  219.                             (IACollectionImpl const&) const;
  220.  
  221.   IBoolean ContainsElementWithKey
  222.                             (void const*) const;
  223.  
  224.   void     Copy             (IACollectionImpl const&);
  225.  
  226.   Cursor*  CreateCursor     () const;
  227.  
  228.   MngCursor*
  229.            CreateMngCursor  () const;
  230.  
  231.   void*    ElementAt        (ICursorImpl const&) const;
  232.  
  233.   void*    ElementAtPosition
  234.                             (IPosition) const;
  235.  
  236.   void*    ElementWithKey   (void const*) const;
  237.  
  238.   void*    First            () const;
  239.  
  240.   IBoolean IsBounded        () const;
  241.  
  242.   IBoolean IsConsistent     () const;
  243.  
  244.   IBoolean IsEmpty          () const;
  245.  
  246.   IBoolean IsFirstAt        (ICursorImpl const&) const;
  247.  
  248.   IBoolean IsFull           () const;
  249.  
  250.   IBoolean IsLastAt         (ICursorImpl const&) const;
  251.  
  252.   void*    Key              (void const*) const;
  253.  
  254.   void*    Last             () const;
  255.  
  256.   IBoolean LocateElementWithKey
  257.                             (void const*, ICursorImpl&) const;
  258.  
  259.   IBoolean LocateNextElementWithKey
  260.                             (void const*, ICursorImpl&) const;
  261.  
  262.   IBoolean LocateOrAddElementWithKey
  263.                             (void const*, ICursorImpl&);
  264.  
  265.   INumber  NumberOfElements () const;
  266.  
  267.   IPosition
  268.            PositionAt       (ICursorImpl const&) const;
  269.  
  270.   INumber  RemoveAll        ();
  271.  
  272.   INumber  RemoveAll        (IPredFunc, void*);
  273.  
  274.   void     RemoveAt         (ICursorImpl&);
  275.  
  276.   void     RemoveAtPosition (IPosition);
  277.  
  278.   IBoolean RemoveElementWithKey
  279.                             (void const*);
  280.  
  281.   void     RemoveFirst      ();
  282.  
  283.   void     RemoveLast       ();
  284.  
  285.   void     ReplaceAt        (ICursorImpl const&, void const*);
  286.  
  287.   IBoolean ReplaceElementWithKey
  288.                             (void const*, ICursorImpl&);
  289.  
  290.   IBoolean SetToFirst       (ICursorImpl&) const;
  291.  
  292.   IBoolean SetToLast        (ICursorImpl&) const;
  293.  
  294.   IBoolean SetToNext        (ICursorImpl&) const;
  295.  
  296.   void     SetToPosition    (IPosition, ICursorImpl&) const;
  297.  
  298.   IBoolean SetToPrevious    (ICursorImpl&) const;
  299.  
  300.   void     operator=        (IKeySortedSetAsBstTreeImpl const&);
  301.  
  302.   TStream& operator<<=      (TStream&);
  303.  
  304.   TStream& operator>>=      (TStream&) const;
  305.  
  306. protected:
  307.  
  308.   void     Assign           (void*, void const*) const;
  309.  
  310.   long     CompareKeys      (void const*, void const*,
  311.                              IArgType) const;
  312.  
  313.   long     CompareKeys      (void const*, INumber, void const*,
  314.                              IArgType) const;
  315.  
  316.   void     CopyKey          (void*, INumber,
  317.                              void const*, INumber) const;
  318.  
  319.   void*    CreateINode      (void const* = 0) const;
  320.  
  321.   void*    CreateKey        () const;
  322.  
  323.   void*    CreateLNode      (void const*) const;
  324.  
  325.   void     DeleteINode      (void*) const;
  326.  
  327.   void     DeleteKey        (void*) const;
  328.  
  329.   void     DeleteLNode      (void*) const;
  330.  
  331.   void*    StreamIn         (TStream&) const;
  332.  
  333.   void     StreamOut        (void const*, TStream&) const;
  334.  
  335. private:
  336.  
  337.   enum { kOriginalVersion };
  338.  
  339.   static
  340.   char const*
  341.            cvClassName;
  342.  
  343.   MngCursor*
  344.            ivMngCursors;
  345.  
  346.   Node*    ivRoot;
  347.  
  348.   INumber  ivNumberOfElements;
  349.  
  350.   INumber  ivTreeOrder;
  351.  
  352.   INumber  ivHeight;
  353.  
  354.   IBoolean AddSubtree       (Node*, void const*,
  355.                              Node*&, void*, ICursorImpl&);
  356.  
  357.   void     AddAllFromSubtree
  358.                             (Node const*);
  359.  
  360.   IBoolean AllElementsDoSubtree
  361.                             (IApplFunc, void*, Node*);
  362.  
  363.   INumber  BinarySearchInPageWithKey
  364.                             (INode const*, void const*) const;
  365.  
  366.   INumber  BinarySearchInPageWithElement
  367.                             (INode const*, void const*) const;
  368.  
  369.  
  370.   IBoolean CheckCursorSubtree
  371.                             (ICursorImpl const&, Node const*) const;
  372.  
  373.   IBoolean ContainsAllKeysFromSubtree
  374.                             (Node const*) const;
  375.  
  376.   Node*    CopySubtree      (Node const*) const;
  377.  
  378.   INumber  DeleteSubtree    (Node*) const;
  379.  
  380.   void*    ElementOf        (LNode const*) const;
  381.  
  382.   IBoolean IsConsistentSubtree
  383.                             (Node const*) const;
  384.  
  385.   static
  386.   IBoolean IsInBetween      (ICursorImpl const&);
  387.  
  388.   void     JoinINodes       (INode*, INode*, INode*, INumber);
  389.  
  390.  
  391.   IBoolean LocateElementWithKeySubtree
  392.                             (void const*, ICursorImpl&, Node*) const;
  393.  
  394.   static
  395.   LNode*   MinimumLeaf      (Node*);
  396.  
  397.   static
  398.   LNode*   MaximumLeaf      (Node*);
  399.  
  400.   static
  401.   Node*&   NextNodeOf       (ICursorImpl const&);
  402.  
  403.   static
  404.   Node*&   NodeOf           (ICursorImpl const&);
  405.  
  406.   static
  407.   Ops&     OpsOf            (IKeySortedSetAsBstTreeImpl const&);
  408.  
  409.   static
  410.   Node*&   PreviousNodeOf   (ICursorImpl const&);
  411.  
  412.   void     RemoveSubtree    (INode*, ICursorImpl&);
  413.  
  414.   void     SetInBetween     (MngCursor&) const;
  415.  
  416.   IBoolean SetToNextSubtree (ICursorImpl&, INode const*) const;
  417.  
  418.   IBoolean SetToPreviousSubtree
  419.                             (ICursorImpl&, INode const*) const;
  420.  
  421.   friend
  422.   class    IKeySortedSetAsBstTreeMngCursorImpl;
  423.  
  424.   friend
  425.   class    IKeySetOnKeySortedSetImpl <Self>;
  426.  
  427.   friend
  428.   class    ISortedBagOnKeySortedSetImpl <Self>;
  429.  
  430.   friend
  431.   class    ISortedMapOnKeySortedSetImpl <Self>;
  432.  
  433.  
  434. };
  435.  
  436. class IAKeySortedSetAsBstTreeOps {
  437. public:
  438.  
  439.   virtual ~IAKeySortedSetAsBstTreeOps
  440.                             ();
  441.  
  442.   virtual
  443.   void     Assign           (void*, void const*) const = 0;
  444.  
  445.   virtual
  446.   IACollectionImpl*
  447.            Clone            () const = 0;
  448.  
  449.   virtual
  450.   long     CompareKeys      (void const*, void const*,
  451.                              IArgType) const = 0;
  452.  
  453.   virtual
  454.   long     CompareKeys      (void const*, INumber, void const*,
  455.                              IArgType) const = 0;
  456.  
  457.   virtual
  458.   void     CopyKey          (void*, INumber,
  459.                              void const*, INumber) const = 0;
  460.  
  461.   virtual
  462.   void*    CreateINode      (void const*) const = 0;
  463.  
  464.   virtual
  465.   void*    CreateKey        () const = 0;
  466.  
  467.   virtual
  468.   void*    CreateLNode      (void const*) const = 0;
  469.  
  470.   virtual
  471.   void     DeleteINode      (void*) const = 0;
  472.  
  473.   virtual
  474.   void     DeleteKey        (void*) const = 0;
  475.  
  476.   virtual
  477.   void     DeleteLNode      (void*) const = 0;
  478.  
  479.   virtual
  480.   void*    Key              (void const*) const = 0;
  481.  
  482.   virtual
  483.   void*    StreamIn         (TStream&) const = 0;
  484.  
  485.   virtual
  486.   void     StreamOut        (void const*, TStream&) const = 0;
  487.  
  488.   virtual
  489.   TStream& operator<<=      (TStream&) = 0;
  490.  
  491.   virtual
  492.   TStream& operator>>=      (TStream&) const = 0;
  493.  
  494.   virtual  operator INumber () const = 0;
  495.  
  496. protected:
  497.  
  498.            IAKeySortedSetAsBstTreeOps
  499.                             (IBoolean);
  500.  
  501. private:
  502.  
  503.   IBoolean ivContainsDTSObjects;
  504.  
  505.   friend
  506.   class    IKeySortedSetAsBstTreeImpl;
  507.  
  508.  
  509. };
  510.  
  511. #if ! defined (IBSTPAGESIZE)
  512. #define IBSTPAGESIZE 4096
  513. #endif
  514.  
  515. template <class Element, class _Key,
  516.           class ElementOps, class Implementation,
  517.           size_t nodeSize = IBSTPAGESIZE>
  518. class IKeySortedSetAsBstTreeOps : public IAKeySortedSetAsBstTreeOps {
  519.  
  520.   typedef  IAKeySortedSetAsBstTreeOps Inherited;
  521.  
  522.   typedef  IKeySortedSetAsBstTreeOps
  523.             <Element, _Key, ElementOps, Implementation, nodeSize> Self;
  524.  
  525.   typedef  IKeySortedSetAsBstTreeINodeImpl <_Key, nodeSize> INode;
  526.  
  527.   typedef  IKeySortedSetAsBstTreeLNodeImpl <Element> LNode;
  528.  
  529. public:
  530.  
  531.   typedef  Implementation ImplType;
  532.  
  533.   typedef  Element ElementType;
  534.  
  535.   typedef  _Key KeyType;
  536.  
  537.            IKeySortedSetAsBstTreeOps
  538.                             (INumber);
  539.  
  540.            IKeySortedSetAsBstTreeOps
  541.                             (INumber, void*);
  542.  
  543.            IKeySortedSetAsBstTreeOps
  544.                             (IKeySortedSetAsBstTreeOps
  545.                               <Element, _Key, ElementOps,
  546.                                Implementation, nodeSize> const&);
  547.  
  548.           ~IKeySortedSetAsBstTreeOps
  549.                             ();
  550.  
  551.   void     Assign           (void*, void const*) const;
  552.  
  553.   IACollectionImpl*
  554.            Clone            () const;
  555.  
  556.   long     CompareKeys      (void const*, void const*,
  557.                              IArgType) const;
  558.  
  559.   long     CompareKeys      (void const*, INumber, void const*,
  560.                              IArgType) const;
  561.  
  562.   void     CopyKey          (void*, INumber,
  563.                              void const*, INumber) const;
  564.  
  565.   void*    CreateINode      (void const*) const;
  566.  
  567.   void*    CreateKey        () const;
  568.  
  569.   void*    CreateLNode      (void const*) const;
  570.  
  571.   void     DeleteINode      (void*) const;
  572.  
  573.   void     DeleteKey        (void*) const;
  574.  
  575.   void     DeleteLNode      (void*) const;
  576.  
  577.   void*    Key              (void const*) const;
  578.  
  579.   void*    StreamIn         (TStream&) const;
  580.  
  581.   void     StreamOut        (void const*, TStream&) const;
  582.  
  583.   TStream& operator<<=      (TStream&);
  584.  
  585.   TStream& operator>>=      (TStream&) const;
  586.  
  587.            operator INumber () const;
  588.  
  589.            operator Implementation*
  590.                             ();
  591.  
  592.  
  593. protected:
  594.  
  595. private:
  596.  
  597.   ElementOps
  598.            ivElementOps;
  599.  
  600.   Implementation
  601.            ivImpl;
  602.  
  603.  
  604. };
  605.  
  606. #pragma SOMAsDefault (pop)
  607.  
  608. #include <iikssbst.inl>
  609.  
  610. #if ! defined (__TEMPINC__)
  611. #include <iikssbst.c>
  612. #endif
  613.  
  614. #pragma info (restore)
  615. #pragma pack ()
  616.  
  617. #endif
  618.