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

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

       Auxiliary class to support DLAY.

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

#ifndef __CSDAVL_H
#define __CSDAVL_H

#include "cspage.h"
#include "csavl.h"


typedef struct { U32 page; U16 off; } APOINT;



class AVLd: public PAGE
{

  public:


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

     typedef struct
     {
       APOINT pos;
       U16   amount;
       U8    TheEnd;
     } edc;             // Empty Data Chain

     edc empty;


     U32   lr_page;       //Last Referred Page
     int   lr_dirty;      //..............page dirty
     csCHAR *lr_add ;     //..............Address

     APOINT anchor;

protected:

     csCHAR *load_page_h(U32 page)
     {
        if(page==lr_page) return lr_add;
        lr_dirty=FALSE;
        return lr_add=load_page(lr_page=page);
     }

     csCHAR *load_page_hd(U32 page)
     {
        if(page==lr_page)
        {
            if(!lr_dirty) { dirty(lr_add); lr_dirty=TRUE; }
            return lr_add;
        }
        lr_dirty=TRUE;
        return lr_add=load_page_d(lr_page=page);
     }

     csCHAR *P2p(APOINT &p)
     {
        if(p.page==lr_page) return lr_add+p.off;
        return (lr_add=load_page_ld(lr_page=p.page))+p.off;
     }

     int  equ(APOINT &p,APOINT &q)  { return ((p.page==q.page) && (p.off==q.off)); }

     APOINT alloc_data(S32 delta,avl_dat data);


     void upd_delta(APOINT &p,long add);

     int  rotate(APOINT *up,APOINT p);
     void set_NULL(APOINT &p)   { p.page=0; }
     int  is_NULL(APOINT &p)    { return !p.page; }
     void set_NULL_edc(edc &p) { p.pos.page=0; }
     int  is_NULL_edc(edc  &p) { return is_NULL(p.pos); }
     void avl_free(APOINT &p);

     void init_vars(void);


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

     int  sift_up(APOINT t);


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

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


////////////////////////// Rotations  //////////////////////////////////////
protected:

     void srr2(APOINT *upd,APOINT a,APOINT b);
     void slr2(APOINT *upd,APOINT a,APOINT b);
     void drr(APOINT *up,APOINT a);
     void dlr(APOINT *up,APOINT a);
     void srr(APOINT *up,APOINT a)   { srr2(up,a,((block *)P2p(a))->l); }
     void slr(APOINT *up,APOINT a)   { slr2(up,a,((block *)P2p(a))->r); }



   public:
       AVLd(void);
       virtual
      ~AVLd(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(APOINT p);

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


       int  open(csCHAR *name,S16 kb_buff);
       int  define(csCHAR *name,U16 page_length);
       void define(csCHAR *name)              { define(name,lenpage); }
       int  close(void);
       void save(void);
       void save_as(csCHAR *name);
       virtual
       void set_id(void);
       virtual
       int check_id(U32 id);
       void zap(void);
       void avl_empty(void);
       void info(void);
       virtual
       int class_ID(void)  { return CS_CLID_DAVL; }


};


#endif
