/***********************************************************************

                      CSDB Library, Free Evaluation Version 2.0.5 
                                       Release: January 22th 1997 

       AVL tree.

                                           Copyright(c) 1994-1997 
                                                          ComBits 
                                                  The Netherlands 
***********************************************************************/

#ifndef __CSAVLr_H
#define __CSAVLr_H

#include "stdio.h"
#include "csavl.h"
#include "csstr.h"
#include "csheap.h"




class AVLr
{

  public:

     typedef void * RPOINT;

  protected:
     csSTR d_name;


     typedef struct
     {
       S32 delta;
       S8  balance;
       RPOINT l;
       RPOINT r;
       RPOINT u;
       avl_dat data;
     } block;

     block *anchor;

     HEAP  data;

     block *alloc_data(S32 delta,avl_dat data);
     void upd_delta(void *p,long add) { if(p!=NULL) ((block *)p)->delta+=add; }

     int  rotate(void **up,void *p);


////////////////////////// Support for delete //////////////////////////////

     int  sift_up(void *t);


////////////////////////// Import & Export /////////////////////////////////
public:

     long import(FILE *fp,long num_bytes);
     long export(FILE *fp)    { return export(fp,anchor,0); }
     long export(FILE *fp,void *p,long pos);


////////////////////////// Rotations  //////////////////////////////////////
protected:
     void srr2(void **upd,void *a,void *b);
     void slr2(void **upd,void *a,void *b);
     void drr(void **up,void *a);
     void dlr(void **up,void *a);
     void srr(void **up,void *a)   { srr2(up,a,((block *)a)->l); }
     void slr(void **up,void *a)   { slr2(up,a,((block *)a)->r); }



   public:
       AVLr(void);
       virtual
      ~AVLr(void);

       int insert(U32 key, avl_dat data);
       int insert(U32 key, void *p)  { avl_dat data; data.p=p; return insert(key,data); }
       int insert(U32 key, long l )  { avl_dat data; data.l=l; return insert(key,data); }

       int delet( U32 key);

       int search(U32 key, avl_dat &data);
       int search_ge(U32 key,U32 &nkey, U32 &data);
       int search_ge(U32 key,U32 &nkey, avl_dat &data);
       int search_gt(U32 key,U32 &nkey, avl_dat &data);
       int search_le(U32 key,U32 &nkey, U32     &data);
       int search_lt(U32 key,U32 &nkey, avl_dat &data);

       void zap(void );
       void empty(void);
       void close(void);
       void open(void)   { data.open(); }

       int  report(csCHAR *name,int sub);
       void report(FILE *fp,int sub);
       void reporter(FILE *fp,void *,int );
       void report_sum(FILE *fp,void *,U32 );

       csCHAR *e_name(void)  { return (csCHAR *)d_name; }
       virtual int class_ID(void)  { return CS_CLID_RAVL; }

};


#endif
