home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cslio205.zip / INCLUDE / CSDAVL.H < prev    next >
C/C++ Source or Header  |  1997-01-21  |  4KB  |  171 lines
  1. /***********************************************************************
  2.  
  3.                       CSDB Library, Free Evaluation Version 2.0.5 
  4.                                        Release: January 22th 1997 
  5.  
  6.        Auxiliary class to support DLAY.
  7.  
  8.                                            Copyright(c) 1994-1997 
  9.                                                           ComBits 
  10.                                                   The Netherlands 
  11. ***********************************************************************/
  12.  
  13. #ifndef __CSDAVL_H
  14. #define __CSDAVL_H
  15.  
  16. #include "cspage.h"
  17. #include "csavl.h"
  18.  
  19.  
  20. typedef struct { U32 page; U16 off; } APOINT;
  21.  
  22.  
  23.  
  24. class AVLd: public PAGE
  25. {
  26.  
  27.   public:
  28.  
  29.  
  30.      typedef struct
  31.      {
  32.        S32 delta;
  33.        S8  balance;
  34.        APOINT l;
  35.        APOINT r;
  36.        APOINT u;
  37.        avl_dat data;
  38.      } block;
  39.  
  40.      typedef struct
  41.      {
  42.        APOINT pos;
  43.        U16   amount;
  44.        U8    TheEnd;
  45.      } edc;             // Empty Data Chain
  46.  
  47.      edc empty;
  48.  
  49.  
  50.      U32   lr_page;       //Last Referred Page
  51.      int   lr_dirty;      //..............page dirty
  52.      csCHAR *lr_add ;     //..............Address
  53.  
  54.      APOINT anchor;
  55.  
  56. protected:
  57.  
  58.      csCHAR *load_page_h(U32 page)
  59.      {
  60.         if(page==lr_page) return lr_add;
  61.         lr_dirty=FALSE;
  62.         return lr_add=load_page(lr_page=page);
  63.      }
  64.  
  65.      csCHAR *load_page_hd(U32 page)
  66.      {
  67.         if(page==lr_page)
  68.         {
  69.             if(!lr_dirty) { dirty(lr_add); lr_dirty=TRUE; }
  70.             return lr_add;
  71.         }
  72.         lr_dirty=TRUE;
  73.         return lr_add=load_page_d(lr_page=page);
  74.      }
  75.  
  76.      csCHAR *P2p(APOINT &p)
  77.      {
  78.         if(p.page==lr_page) return lr_add+p.off;
  79.         return (lr_add=load_page_ld(lr_page=p.page))+p.off;
  80.      }
  81.  
  82.      int  equ(APOINT &p,APOINT &q)  { return ((p.page==q.page) && (p.off==q.off)); }
  83.  
  84.      APOINT alloc_data(S32 delta,avl_dat data);
  85.  
  86.  
  87.      void upd_delta(APOINT &p,long add);
  88.  
  89.      int  rotate(APOINT *up,APOINT p);
  90.      void set_NULL(APOINT &p)   { p.page=0; }
  91.      int  is_NULL(APOINT &p)    { return !p.page; }
  92.      void set_NULL_edc(edc &p) { p.pos.page=0; }
  93.      int  is_NULL_edc(edc  &p) { return is_NULL(p.pos); }
  94.      void avl_free(APOINT &p);
  95.  
  96.      void init_vars(void);
  97.  
  98.  
  99. ////////////////////////// Support for delete //////////////////////////////
  100.  
  101.      int  sift_up(APOINT t);
  102.  
  103.  
  104. ////////////////////////// Import & Export /////////////////////////////////
  105. public:
  106.  
  107.      long import(FILE *fp,long num_bytes);
  108.      long export(FILE *fp)    { return export(fp,anchor,0); }
  109.      long export(FILE *fp,APOINT p,long pos);
  110.  
  111.  
  112. ////////////////////////// Rotations  //////////////////////////////////////
  113. protected:
  114.  
  115.      void srr2(APOINT *upd,APOINT a,APOINT b);
  116.      void slr2(APOINT *upd,APOINT a,APOINT b);
  117.      void drr(APOINT *up,APOINT a);
  118.      void dlr(APOINT *up,APOINT a);
  119.      void srr(APOINT *up,APOINT a)   { srr2(up,a,((block *)P2p(a))->l); }
  120.      void slr(APOINT *up,APOINT a)   { slr2(up,a,((block *)P2p(a))->r); }
  121.  
  122.  
  123.  
  124.    public:
  125.        AVLd(void);
  126.        virtual
  127.       ~AVLd(void);
  128.  
  129.        int insert(U32 key, avl_dat data);
  130.        int insert(U32 key, void *p)  { avl_dat data; data.p=p; return insert(key,data); }
  131.        int insert(U32 key, long l )  { avl_dat data; data.l=l; return insert(key,data); }
  132.  
  133.        int delet( U32 key);
  134.  
  135.        int search(U32 key, avl_dat &data);
  136.        int search_ge(U32 key,U32 &nkey, U32 &data);
  137.        int search_ge(U32 key,U32 &nkey, avl_dat &data);
  138.        int search_gt(U32 key,U32 &nkey, avl_dat &data);
  139.        int search_le(U32 key,U32 &nkey, U32     &data);
  140.        int search_lt(U32 key,U32 &nkey, avl_dat &data);
  141.  
  142.        void zap(APOINT p);
  143.  
  144.        int  report(csCHAR *name,int sub=1);
  145.        void report(FILE *fp,int sub=1);
  146.        void reporter(FILE *fp,APOINT ,int );
  147.        void report_sum(FILE *fp,APOINT ,U32 );
  148.  
  149.  
  150.        int  open(csCHAR *name,S16 kb_buff);
  151.        int  define(csCHAR *name,U16 page_length);
  152.        void define(csCHAR *name)              { define(name,lenpage); }
  153.        int  close(void);
  154.        void save(void);
  155.        void save_as(csCHAR *name);
  156.        virtual
  157.        void set_id(void);
  158.        virtual
  159.        int check_id(U32 id);
  160.        void zap(void);
  161.        void avl_empty(void);
  162.        void info(void);
  163.        virtual
  164.        int class_ID(void)  { return CS_CLID_DAVL; }
  165.  
  166.  
  167. };
  168.  
  169.  
  170. #endif
  171.