// IBM Open Class Library
//
// Licensed Materials - Property of IBM
//
// (C) Copyright IBM Corporation, 1992, 1997 All Rights Reserved
//
// Revision: 32 1.5.1.4 source/core/collect/iikssbst.h, collection, ioc.v400, 980918 
#ifndef _IIKSSBST_
#define _IIKSSBST_

#include <iiakss.h>
#include <stddef.h>







#pragma info (nocls, nocnd, nocns, nocnv, noext, nognr, novft)






#if __IBMCPP__ >= 400
#pragma namemangling(compat)
#endif

#pragma enum (4)
#pragma pack (push,4)

struct IAKeySortedSetAsBstTreeNodeImpl {

  bool ivIsLeaf;

};

struct IAKeySortedSetAsBstTreeINodeImpl :
  public IAKeySortedSetAsBstTreeNodeImpl {

  void*    ivKeys;

  IAKeySortedSetAsBstTreeNodeImpl**
           ivPtrs;

  INumber  ivm;

           IAKeySortedSetAsBstTreeINodeImpl
                            ();

           IAKeySortedSetAsBstTreeINodeImpl
                            (IAKeySortedSetAsBstTreeINodeImpl const&);
};

#define IBSTMAX(a,b)  ((a) < (b) ? (b) : (a))

#if ! defined (IBSTORDER)
#define IBSTORDER \
  IBSTMAX ((long)3, (((long)nodeSize) \
                   - (sizeof (IAKeySortedSetAsBstTreeINodeImpl) \
                    + sizeof (IAKeySortedSetAsBstTreeNodeImpl*)) \
                   ) / (sizeof (_Key) \
                    + sizeof (IAKeySortedSetAsBstTreeNodeImpl*)) + 1)
#endif

template <class _Key, size_t nodeSize>
struct IKeySortedSetAsBstTreeINodeImpl :
  public IAKeySortedSetAsBstTreeINodeImpl {

  typedef  IAKeySortedSetAsBstTreeINodeImpl Inherited;

  IAKeySortedSetAsBstTreeNodeImpl*
           ivPtrs [IBSTORDER];

  _Key     ivKeys [IBSTORDER - 1];

           IKeySortedSetAsBstTreeINodeImpl
                            ();

           IKeySortedSetAsBstTreeINodeImpl
                            (IKeySortedSetAsBstTreeINodeImpl
                              <_Key, nodeSize > const&);

          ~IKeySortedSetAsBstTreeINodeImpl
                            ();



};

struct IAKeySortedSetAsBstTreeLNodeImpl :
  public IAKeySortedSetAsBstTreeNodeImpl {
};

template <class Element>
struct IKeySortedSetAsBstTreeLNodeImpl :
  public IAKeySortedSetAsBstTreeLNodeImpl {

  Element  ivElement;

           IKeySortedSetAsBstTreeLNodeImpl
                            (Element const&);

          ~IKeySortedSetAsBstTreeLNodeImpl
                            ();

#if !defined(__INO_STREAMING__)
  void     StreamIn         (IACollectionStreamer*, IDataStream&);
#endif







};










class IC_EXPORTC IKeySortedSetAsBstTreeCursorImpl : public ICursorImpl {

  typedef  ICursorImpl Inherited;

  typedef  IKeySortedSetAsBstTreeCursorImpl Self;

#if !defined(__INO_STREAMING__)
  typedef  IAKeySortedSetAsBstTreeNodeImpl Node;
#endif

public:

           IKeySortedSetAsBstTreeCursorImpl
                            (IACollectionImpl const&);

           IKeySortedSetAsBstTreeCursorImpl
                            (IKeySortedSetAsBstTreeCursorImpl const&);

          ~IKeySortedSetAsBstTreeCursorImpl
                            ();

  ICursorImpl*
           Clone            () const;

  void     Copy             (ICursorImpl const&);

  void     Invalidate       ();

  bool IsInBetween      () const;

  bool IsValid          () const;

  void     operator=        (IKeySortedSetAsBstTreeCursorImpl const&);

  bool operator==       (ICursorImpl const&) const;

protected:

private:

  IAKeySortedSetAsBstTreeNodeImpl*
           ivNode;

  friend
  class    IKeySortedSetAsBstTreeImpl;










};






























































template <class Base>
class IKeySetOnKeySortedSetImpl;

template <class Base>
class ISortedBagOnKeySortedSetImpl;

template <class Base>
class ISortedMapOnKeySortedSetImpl;

class IAKeySortedSetAsBstTreeOps;

class IC_EXPORTC IKeySortedSetAsBstTreeImpl : public IAKeySortedSetImpl {

  typedef  IAKeySortedSetImpl Inherited;

  typedef  IKeySortedSetAsBstTreeImpl Self;

  typedef  IAKeySortedSetAsBstTreeNodeImpl   Node;

  typedef  IAKeySortedSetAsBstTreeINodeImpl INode;

  typedef  IAKeySortedSetAsBstTreeLNodeImpl LNode;

public:

  typedef  IAKeySortedSetAsBstTreeOps Ops;

  typedef  IKeySortedSetAsBstTreeCursorImpl Cursor;




  typedef  IKeySortedSetAsBstTreeCursorImpl MngCursor;


           IKeySortedSetAsBstTreeImpl
                            (Ops&, INumber);

           IKeySortedSetAsBstTreeImpl
                            (Ops&, IKeySortedSetAsBstTreeImpl const&);

          ~IKeySortedSetAsBstTreeImpl
                            ();

  bool Add              (void const*, ICursorImpl&);

  void     AddAllFrom       (IACollectionImpl const&);

  bool AddOrReplaceElementWithKey
                            (void const*, ICursorImpl&);

  bool AllElementsDo    (IApplFunc, void*);

  void*    Any              () const;

  char const*
           ClassName        () const;

  IACollectionImpl*
           Clone            () const;

  bool CheckCursor      (ICursorImpl const&) const;

  bool CheckReplacement (ICursorImpl const&, void const*) const;

  bool ContainsAllKeysFrom
                            (IACollectionImpl const&) const;

  bool ContainsElementWithKey
                            (void const*) const;

  void     Copy             (IACollectionImpl const&);

  Cursor*  CreateCursor     () const;

  MngCursor*
           CreateMngCursor  () const;

  void*    ElementAt        (ICursorImpl const&) const;

  void*    ElementAtPosition
                            (IPosition) const;

  void*    ElementWithKey   (void const*) const;

  void*    First            () const;

  bool IsBounded        () const;

  bool IsConsistent     () const;

  bool IsEmpty          () const;

  bool IsFirstAt        (ICursorImpl const&) const;

  bool IsFull           () const;

  bool IsLastAt         (ICursorImpl const&) const;

  void*    Key              (void const*) const;

  void*    Last             () const;

  bool LocateElementWithKey
                            (void const*, ICursorImpl&) const;

  bool LocateNextElementWithKey
                            (void const*, ICursorImpl&) const;

  bool LocateOrAddElementWithKey
                            (void const*, ICursorImpl&);

  INumber  NumberOfElements () const;

  IPosition
           PositionAt       (ICursorImpl const&) const;

  INumber  RemoveAll        ();

  INumber  RemoveAll        (IPredFunc, void*);

  void     RemoveAt         (ICursorImpl&);

  void     RemoveAtPosition (IPosition);

  bool RemoveElementWithKey
                            (void const*);

  void     RemoveFirst      ();

  void     RemoveLast       ();

  void     ReplaceAt        (ICursorImpl const&, void const*);

  bool ReplaceElementWithKey
                            (void const*, ICursorImpl&);

  bool SetToFirst       (ICursorImpl&) const;

  bool SetToLast        (ICursorImpl&) const;

  bool SetToNext        (ICursorImpl&) const;

  void     SetToPosition    (IPosition, ICursorImpl&) const;

  bool SetToPrevious    (ICursorImpl&) const;

  void     operator=        (IKeySortedSetAsBstTreeImpl const&);

protected:

  void     Assign           (void*, void const*) const;

  long     CompareKeys      (void const*, void const*,
                             IArgType) const;

  long     CompareKeys      (void const*, INumber, void const*,
                             IArgType) const;

  void     CopyKey          (void*, INumber,
                             void const*, INumber) const;

  void*    CreateINode      (void const* = 0) const;

  void*    CreateKey        () const;

  void*    CreateLNode      (void const*) const;

  void     DeleteINode      (void*) const;

  void     DeleteKey        (void*) const;

  void     DeleteLNode      (void*) const;

private:

  enum { kOriginalVersion };

  static
  char const*
           cvClassName;

  MngCursor*
           ivMngCursors;

  Node*    ivRoot;

  INumber  ivNumberOfElements;

  INumber  ivTreeOrder;

  INumber  ivHeight;

  bool AddSubtree       (Node*, void const*,
                             Node*&, void*, ICursorImpl&);

  void     AddAllFromSubtree
                            (Node const*);

  bool AllElementsDoSubtree
                            (IApplFunc, void*, Node*);

  INumber  BinarySearchInPageWithKey
                            (INode const*, void const*) const;

  INumber  BinarySearchInPageWithElement
                            (INode const*, void const*) const;


  bool CheckCursorSubtree
                            (ICursorImpl const&, Node const*) const;

  bool ContainsAllKeysFromSubtree
                            (Node const*) const;

  Node*    CopySubtree      (Node const*) const;

  INumber  DeleteSubtree    (Node*) const;

  void*    ElementOf        (LNode const*) const;

  bool IsConsistentSubtree
                            (Node const*) const;

  static
  bool IsInBetween      (ICursorImpl const&);

  void     JoinINodes       (INode*, INode*, INode*, INumber);


  bool LocateElementWithKeySubtree
                            (void const*, ICursorImpl&, Node*) const;

  static
  LNode*   MinimumLeaf      (Node*);

  static
  LNode*   MaximumLeaf      (Node*);

  static
  Node*&   NextNodeOf       (ICursorImpl const&);

  static
  Node*&   NodeOf           (ICursorImpl const&);

  static
  Ops&     OpsOf            (IKeySortedSetAsBstTreeImpl const&);

  static
  Node*&   PreviousNodeOf   (ICursorImpl const&);

  void     RemoveSubtree    (INode*, ICursorImpl&);

  void     SetInBetween     (MngCursor&) const;

  bool SetToNextSubtree (ICursorImpl&, INode const*) const;

  bool SetToPreviousSubtree
                            (ICursorImpl&, INode const*) const;

  friend
  class    IKeySortedSetAsBstTreeMngCursorImpl;

  friend
  class    IKeySetOnKeySortedSetImpl <Self>;

  friend
  class    ISortedBagOnKeySortedSetImpl <Self>;

  friend
  class    ISortedMapOnKeySortedSetImpl <Self>;

#if ! defined (__INO_STREAMING__)
protected:
  void*    CreateLNodeWithStreamer
                            (IDataStream&) const;

public:
  IStreamerPtr&
           StreamerOf       (IACollectionImpl const&);

  void     StreamIn         (IDataStream&);

  void     StreamOut        (IDataStream&) const;

  void     AdoptStreamer    (IACollectionStreamer*);
#endif





























































};

class IC_EXPORTC IAKeySortedSetAsBstTreeOps {
public:

  virtual ~IAKeySortedSetAsBstTreeOps
                            ();

  virtual
  void     Assign           (void*, void const*) const = 0;

  virtual
  IACollectionImpl*
           Clone            () const = 0;

  virtual
  long     CompareKeys      (void const*, void const*,
                             IArgType) const = 0;

  virtual
  long     CompareKeys      (void const*, INumber, void const*,
                             IArgType) const = 0;

  virtual
  void     CopyKey          (void*, INumber,
                             void const*, INumber) const = 0;

  virtual
  void*    CreateINode      (void const*) const = 0;

  virtual
  void*    CreateKey        () const = 0;

  virtual
  void*    CreateLNode      (void const*) const = 0;

  virtual
  void     DeleteINode      (void*) const = 0;

  virtual
  void     DeleteKey        (void*) const = 0;

  virtual
  void     DeleteLNode      (void*) const = 0;

  virtual
  void*    Key              (void const*) const = 0;

  virtual  operator INumber () const = 0;

protected:

           IAKeySortedSetAsBstTreeOps
                            (bool);

private:

  bool ivContainsDTSObjects;

  friend
  class    IKeySortedSetAsBstTreeImpl;

#if ! defined (__INO_STREAMING__)
public:
  virtual
  void*    CreateLNodeWithStreamer
                         (IACollectionStreamer*, IDataStream&) const = 0;
#endif
























};

#if ! defined (IBSTPAGESIZE)
#define IBSTPAGESIZE 4096
#endif

template <class Element, class _Key,
          class ElementOps, class Implementation,
          size_t nodeSize = IBSTPAGESIZE>
class IC_EXPORTC IKeySortedSetAsBstTreeOps : public IAKeySortedSetAsBstTreeOps {

  typedef  IAKeySortedSetAsBstTreeOps Inherited;

  typedef  IKeySortedSetAsBstTreeOps
            <Element, _Key, ElementOps, Implementation, nodeSize> Self;

  typedef  IKeySortedSetAsBstTreeINodeImpl <_Key, nodeSize> INode;

  typedef  IKeySortedSetAsBstTreeLNodeImpl <Element> LNode;

public:

  typedef  Implementation ImplType;

  typedef  Element ElementType;

  typedef  _Key KeyType;

           IKeySortedSetAsBstTreeOps
                            (INumber);

           IKeySortedSetAsBstTreeOps
                            (INumber, void*);

           IKeySortedSetAsBstTreeOps
                            (IKeySortedSetAsBstTreeOps
                              <Element, _Key, ElementOps,
                               Implementation, nodeSize> const&);

          ~IKeySortedSetAsBstTreeOps
                            ();

  void     Assign           (void*, void const*) const;

  IACollectionImpl*
           Clone            () const;

  long     CompareKeys      (void const*, void const*,
                             IArgType) const;

  long     CompareKeys      (void const*, INumber, void const*,
                             IArgType) const;

  void     CopyKey          (void*, INumber,
                             void const*, INumber) const;

  void*    CreateINode      (void const*) const;

  void*    CreateKey        () const;

  void*    CreateLNode      (void const*) const;

  void     DeleteINode      (void*) const;

  void     DeleteKey        (void*) const;

  void     DeleteLNode      (void*) const;

  void*    Key              (void const*) const;

           operator INumber () const;

           operator Implementation*
                            ();





















protected:

private:

  ElementOps
           ivElementOps;

  Implementation
           ivImpl;

#if ! defined (__INO_STREAMING__)
public:
  void*    CreateLNodeWithStreamer
                            (IACollectionStreamer*, IDataStream&) const;
#endif












};

#pragma pack (pop)
#pragma enum (pop)

#if __IBMCPP__ >= 400
#pragma namemangling()
#endif






#pragma info (restore)


#include <iikssbst.inl>




#if ! defined (__TEMPINC__)
#include <iikssbst.c>
#endif


#endif // _IIKSSBST_
