// IBM Open Class Library
//
// Licensed Materials - Property of IBM
//
// (C) Copyright IBM Corporation, 1992, 1997 All Rights Reserved
//
// Revision: 28 1.6.1.4 source/core/collect/iikssavl.h, collection, ioc.v400, 001006 
#ifndef _IIKSSAVL_
#define _IIKSSAVL_

#include <iiakss.h>







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






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

typedef short Direction;

const short kAvlNone  =  0;

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

struct IAKeySortedSetAsAvlTreeNodeImpl {

  IAKeySortedSetAsAvlTreeNodeImpl
          *ivLeft,
          *ivRight,
          *ivParent;

  Direction
           ivDeeperSubtree;

           IAKeySortedSetAsAvlTreeNodeImpl
                            ();

  IAKeySortedSetAsAvlTreeNodeImpl*&
           Link             (Direction);

  void     Parent           (IAKeySortedSetAsAvlTreeNodeImpl*&,
                             Direction&);

  void     ConnectChild     (Direction,
                             IAKeySortedSetAsAvlTreeNodeImpl*);

  void     ConnectChild0    (Direction,
                             IAKeySortedSetAsAvlTreeNodeImpl*);

};

template <class Element>
struct IKeySortedSetAsAvlTreeNodeImpl :
  public IAKeySortedSetAsAvlTreeNodeImpl {

  Element  ivElement;

           IKeySortedSetAsAvlTreeNodeImpl
                            (Element const&);

          ~IKeySortedSetAsAvlTreeNodeImpl
                            ();

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







};










class IC_EXPORTC IKeySortedSetAsAvlTreeCursorImpl : public ICursorImpl {

  typedef  ICursorImpl Inherited;

  typedef  IKeySortedSetAsAvlTreeCursorImpl Self;

public:

           IKeySortedSetAsAvlTreeCursorImpl
                            (IACollectionImpl const&);

           IKeySortedSetAsAvlTreeCursorImpl
                            (IKeySortedSetAsAvlTreeCursorImpl const&);

          ~IKeySortedSetAsAvlTreeCursorImpl
                            ();

  ICursorImpl*
           Clone            () const;

  void     Copy             (ICursorImpl const&);

  void     Invalidate       ();

  bool IsInBetween      () const;

  bool IsValid          () const;

  void     operator=        (IKeySortedSetAsAvlTreeCursorImpl const&);

  bool operator==       (ICursorImpl const&) const;

protected:

private:

  IAKeySortedSetAsAvlTreeNodeImpl*
           ivNode;

  friend
  class    IKeySortedSetAsAvlTreeImpl;










};






























































template <class Base>
class IKeySetOnKeySortedSetImpl;

template <class Base>
class ISortedBagOnKeySortedSetImpl;

template <class Base>
class ISortedMapOnKeySortedSetImpl;

class IAKeySortedSetAsAvlTreeOps;

class IC_EXPORTC IKeySortedSetAsAvlTreeImpl : public IAKeySortedSetImpl {

  typedef  IAKeySortedSetImpl Inherited;

  typedef  IKeySortedSetAsAvlTreeImpl Self;

  typedef  IAKeySortedSetAsAvlTreeNodeImpl Node;

#if ! defined (__INO_STREAMING__)
  typedef  IKeySortedSetAsAvlTreeNodeImpl<long> StreamerNode;
#endif

public:

  typedef  IAKeySortedSetAsAvlTreeOps Ops;

  typedef  IKeySortedSetAsAvlTreeCursorImpl Cursor;




  typedef  IKeySortedSetAsAvlTreeCursorImpl MngCursor;


           IKeySortedSetAsAvlTreeImpl
                            (Ops&, INumber);

           IKeySortedSetAsAvlTreeImpl
                            (Ops&, IKeySortedSetAsAvlTreeImpl const&);

          ~IKeySortedSetAsAvlTreeImpl
                            ();

  bool Add              (void const*, ICursorImpl&);

  void     AddAllFrom       (IACollectionImpl const&);

  bool AddOrReplaceElementWithKey
                            (void const*, ICursorImpl&);

  bool AllElementsDo    (IApplFunc, void*);

  void*    Any              () const;

  bool CheckCursor      (ICursorImpl const&) const;

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

  char const*
           ClassName        () const;

  IACollectionImpl*
           Clone            () 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*);

  void     ReplaceAtPosition
                            (IPosition, void const*);

  bool ReplaceElementWithKey
                            (void const*, ICursorImpl&);

  bool SetToFirst       (ICursorImpl&) const;

  bool SetToNext        (ICursorImpl&) const;

  bool SetToLast        (ICursorImpl&) const;

  void     SetToPosition    (IPosition, ICursorImpl&) const;

  bool SetToPrevious    (ICursorImpl&) const;

  void     operator=        (IKeySortedSetAsAvlTreeImpl const&);

protected:

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

  void*    CreateNode       (void const*) const;

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

  void     DeleteNode       (void*) const;

private:

  enum { kOriginalVersion };

  static
  char const*
           cvClassName;

  MngCursor*
           ivMngCursors;

  Node*    ivRoot;

  INumber  ivNumberOfElements;

  void     AddAllFromSubtree
                            (Node const*);

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

  void     Balance          (Node*, Direction, bool&);

  bool CheckNode        (Node const*, Node*) const;

  bool ContainsAllKeysFromSubtree
                            (Node const*) const;

  Node*    CopySubtree      (Node const*) const;

  void     DeleteSubtree    (Node*) const;

  void     DisconnectAndRemove
                            (Node*, bool&);

  void*    ElementOf        (Node const*) const;

  bool IsConsistentSubtree
                            (Node const*, int&, INumber&) const;

  static
  bool IsInBetween      (ICursorImpl const&);

  static
  Node*&   NextNodeOf       (ICursorImpl const&);

  static
  Node*&   NodeOf           (ICursorImpl const&);

  static
  Ops&     OpsOf            (IKeySortedSetAsAvlTreeImpl const&);

  static
  Node*&   PreviousNodeOf   (ICursorImpl const&);

  void     ReplaceNode      (Node*, Node*);

  void     SetInBetween     (MngCursor&) const;

  friend
  class    IKeySortedSetAsAvlTreeMngCursorImpl;

  friend
  class    IKeySetOnKeySortedSetImpl <Self>;

  friend
  class    ISortedBagOnKeySortedSetImpl <Self>;

  friend
  class    ISortedMapOnKeySortedSetImpl <Self>;

#if ! defined (__INO_STREAMING__)
protected:
  void     AddFromStream
                            (IDataStream&, ICursorImpl&);

  void*    CreateNodeWithStreamer
                              (IDataStream&) const;

public:
  IStreamerPtr&
           StreamerOf       (IACollectionImpl const&);

  void     StreamIn         (IDataStream&);

  void     StreamOut        (IDataStream&) const;

  void     AdoptStreamer    (IACollectionStreamer*);
#endif












































};

class IC_EXPORTC IAKeySortedSetAsAvlTreeOps {
public:

  virtual ~IAKeySortedSetAsAvlTreeOps
                            ();

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

  virtual
  IACollectionImpl*
           Clone            () const = 0;

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

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

  virtual
  void     DeleteNode       (void*) const = 0;

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

protected:

           IAKeySortedSetAsAvlTreeOps
                            (bool);

private:

  bool ivContainsDTSObjects;

  friend
  class    IKeySortedSetAsAvlTreeImpl;

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
















};

template <class Element, class _Key,
          class ElementOps, class Implementation>
class IC_EXPORTC IKeySortedSetAsAvlTreeOps : public IAKeySortedSetAsAvlTreeOps {

  typedef  IAKeySortedSetAsAvlTreeOps Inherited;

  typedef  IKeySortedSetAsAvlTreeOps
            <Element, _Key, ElementOps, Implementation> Self;

  typedef  IKeySortedSetAsAvlTreeNodeImpl <Element> Node;

public:

  typedef  Implementation ImplType;

  typedef  Element ElementType;

  typedef  _Key KeyType;

           IKeySortedSetAsAvlTreeOps
                            (INumber);

           IKeySortedSetAsAvlTreeOps
                            (INumber, void*);

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

          ~IKeySortedSetAsAvlTreeOps
                            ();

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

  IACollectionImpl*
           Clone            () const;

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

  void*    CreateNode       (void const*) const;

  void     DeleteNode       (void*) const;

  void*    Key              (void const*) const;

           operator Implementation*
                            ();



















protected:

private:

  ElementOps
           ivElementOps;

  Implementation
           ivImpl;

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












};

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

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






#pragma info (restore)


#include <iikssavl.inl>





#ifndef IC_BUILD
#include <iikssavl.c>
#else
#if ! defined (__TEMPINC__)
#include <iikssavl.c>
#endif
#endif



#endif // _IIKSSAVL_
